Главная » Разработка для Windows Phone 7 » Множество Мандельброта

0

В 1980 году Бенуа Мандельброт (1924-2010), рожденный в Польше французский и американский математик, который работал на IBM, впервые получил графическую визуализацию рекурсивного уравнения с комплексными числами, которое было выведено несколько ранее. Эта визуализация выглядела примерно следующим образом:

С тех пор множество Мандельброта (как его стали называть) стало самой любимой забавой разработчиков ПО.

строится в комплексной плоскости, где горизонтальная ось представляет действительные числа (отрицательные слева и положительные справа), и вертикальная ось представляет мнимые числа (отрицательные внизу и положительные вверху). Возьмем любую точку на плоскости и назовем ее c, зададим z равным 0:

z = 0

Теперь выполним следующую рекурсивную операцию:

z ? z2 + с

Если модуль z не стремится к бесконечности, тогда c принадлежит множеству Мандельброта и в приведенном выше снимке экрана закрашивается черным.

Для некоторых комплексных чисел (например, действительного числа 0) абсолютно очевидно, что число принадлежит множеству. Для других чисел (например, действительного числа 1) абсолютно очевидно, что они не принадлежат этому множеству. Для многих других чисел всего лишь необходимо вычислить значения. К счастью, если после конечного числа итераций модуль z превышает 2, мы знаем, что c не принадлежит множеству Мандельброта.

Для каждого числа c, не принадлежащего множеству Мандельброта, существует связанный с ним коэффициент «итераций», который соответствует числу итераций по вычислению z, которые имели место до момента, когда модуль z стал больше 2. Многие разработчики, занимающиеся визуализациями множества Мандельброта, используют этот коэффициент итераций для выбора цвета соответствующей точки. Это приводит к тому, что области, не принадлежащие множеству Мандельброта, выглядят намного интересней:

В верхнем правом углу отображаются комплексные координаты, ассоциированные с этим углом, и то же самое для нижнего правого угла. Число в верхнем правом углу – общее число итераций.

Это характеризует множество Мандельброта как фрактал. Бенуа Мандельброт считается основателем фрактальной геометрии. Учитывая простоту алгоритма, лежащего в основе этого изображения, получаемые результаты просто ошеломительные.

Можно ли представить лучшее приложение для демонстрации перетягивания и масштабирования посредством мультисенсорного ввода, а также алгоритмического формирования значений пикселов для Texture2D?

Очень часто при создании приложений с использование множества Мандельброта разработчики задают максимальный коэффициент итераций, например, 100 или 1000. Затем z вычисляется для каждого пиксела необходимое число раз, но не более этого заданного максимума. Если к этому моменту значение не расходится, пиксел закрашивается черным. С помощью псевдокода это можно записать следующим образом:

Для каждого пиксела {

Выполняем не более MAX итераций Закрашиваем пиксел черным либо другим цветом

}

Проблема с этим подходом в том, что он может обеспечивать неверные результаты при многократном увеличении. Как правило, чем больше увеличение определенной области множества Мандельброт, тем больше итераций необходимо для определения принадлежности пиксела множеству и цвета, которым он должен закрашиваться.

Эта проблема привела меня к другому подходу: мое приложение MandelbrotSet () изначально закрашивает все пикселы черным и затем во втором потоке выполнения делает следующее:

Выполнять бесконечное число раз {

Для каждого пиксела {

Выполняем еще одну итерацию, если необходимо Возможно, закрашиваем пиксел некоторым цветом

}

}

Одной из любопытных характеристик множества Мандельброта является то, что независимо от того, насколько увеличивается масштаб изображения, его сложность не уменьшается:

При таком подходе мы получаем экран, который чем больше времени проходит, тем все более красочным становится. Оборотная сторона в том, что для поддержки структуры данных, необходимой для этого, требуется 17 МБ памяти. Это слишком большой объем,

который невозможно сохранять при захоронении. И общая производительность ниже, чем при более традиционных подходах.

Рассмотрим структуру PixelInfo, используемую для хранения данных каждого пиксела. Приложение сохраняет массив этих структур параллельно с обычным массивом pixels, используемым для записи данных в Texture2D:

Проект XNA: MandelbrotSet Файл: PixelInfo.cs

using Microsoft.Xna.Framework;

namespace MandelbrotSet {

public struct PixelInfo {

public static int pixelWidth; public static int pixelHeight;

public static double xPixelCoordAtComplexOrigin; public static double yPixelCoordAtComplexOrigin; public static double unitsPerPixel;

public static bool hasNewColors; public static int firstNewIndex; public static int lastNewIndex;

public double cReal; public double cImag; public double zReal; public double zImag; public int iteration; public bool finished; public uint packedColor;

public PixelInfo(int pixelIndex, uint[] pixels) {

int x = pixelIndex % pixelWidth; int y = pixelIndex / pixelWidth;

cReal = (x – xPixelCoordAtComplexOrigin) * unitsPerPixel;

cImag = (yPixelCoordAtComplexOrigin – y) * unitsPerPixel;

zReal = 0;

zImag = 0;

iteration = 0;

finished = false;

packedColor = pixels != null ? pixels[pixelIndex] :

Color.Black.PackedValue; }

public bool Iterate() {

double zImagSquared = zImag * zImag;

zImag = 2 * zReal * zImag + cImag;

zReal = zReal * zReal – zImagSquared + cReal;

if (zReal * zReal + zImag * zImag >= 4.0) {

finished = true; return true;

}

iteration++; return false;

Перейдем сразу к полям экземпляра. Изначально я написал структуру Complex (Комплексный) для инкапсуляции комплексных чисел и осуществления операций над ними, но, как обнаружилось, работа с действительной и мнимой частями напрямую существенно повышает производительность. Наша структура сохраняет описываемые выше значения c и z, текущую итерацию (iteration) и переменную finished (завершен) типа Boolean, которая принимает значение true, когда модуль z отличен от бесконечности. В этот момент значение iteration может использоваться для определения значения цвета.

Конструктор вычисляет cReal (Действительная часть с) и cImag (Мнимая часть с) из pixelIndex (Индекс пиксела), диапазон допустимых значений которого лежит от 0 до (но не включая) произведения ширины и высоты экрана в пикселах. Значения статических полей pixelWidth и pixelHeight зависят от размеров экрана и остаются неизменными в ходе всего приложения.

В вычислении cReal и cImag также участвуют три других статических поля. Поля xPixelCoordAtComplexOrigin (Координата х начала координат комплексной плоскости) и yPixelCoordAtComplexOrigin указывают горизонтальные и вертикальные координаты в пикселах, соответствующие началу координат комплексной плоскости. Очевидно, что использование типа double для этих полей свидетельствует о возможности представления дробных пикселов. Эти два поля меняют значения при операциях переноса. Поле unitsPerPixel (Единиц на пиксел) указывает на диапазон действительных или мнимых чисел, ассоциированный в настоящий момент с одним пикселом. Это значение меняется при операциях масштабирования.

Данная структура PixelInfo включает больше значений типа double, чем все остальные приложения на XNA этой книги вместе взятые. Сначала я, конечно же, сделал все эти значения типа float (и pixelCoordAtComplexOrigin было типа Vector2), но перешел к double, как только исчерпал точность float при масштабировании. Любопытно, что переход от float к double очень мало сказался на производительности.

Второй аргумент конструктора является необязательным. Если он присутствует, конструктор будет копировать соответствующий цвет из массива pixels в свое поле packedColor (Цвет в компактной форме). Вскоре мы рассмотрим, как это работает.

Остальные три статических поля используются для обмена данными внутри потока. Поток, осуществляющий вычисления, задает эти поля при изменении значения цвета; значения полей сбрасываются, когда массив структур PixelInfo используется для обновления массива pixels и объекта Texture2D.

Наконец, метод Iterate (Выполнять итерации) осуществляет основные итеративные вычисления, используя умножение, а не вызовы Math.Pow, из соображений производительности. Iterate возвращает значение true, если z не стремится к бесконечности.

Благодаря этим статическим полям структуры PixelInfo мне удалось сохранить количество полей в производном от Game классе в разумных пределах. В данном фрагменте можно увидеть и обычный массив pixels, и массив PixelInfo. Объект pixelInfosLock (Блокировка pixellnfo) используется для синхронизации потоков.

Проект XNA: MandelbrotSet Файл: Game1.cs (фрагмент, демонстрирующий поля)

public class Game1 : Microsoft.Xna.Framework.Game {

GraphicsDeviceManager graphics; SpriteBatch spriteBatch;

Viewport viewport; Texture2D texture;

uint[] pixels;

PixelInfo[] pixelInfos;

Matrix drawMatrix = Matrix.Identity;

int globalIteration = 0;

object pixelInfosLock = new object();

SpriteFont segoe14;

StringBuilder upperLeftCoordText = new StringBuilder(); StringBuilder lowerRightCoordText = new StringBuilder(); StringBuilder upperRightStatusText = new StringBuilder(); Vector2 lowerRightCoordPosition, upperRightStatusPosition;

public Game1() {

graphics = new GraphicsDeviceManager(this); Content.RootDirectory = "Content";

// Частота кадров по умолчанию для всех устройств Windows Phone – 30

кадров/с

TargetElapsedTime = TimeSpan.FromTicks(333333);

// Задаем полноэкранный режим и активируем жесты graphics.IsFullScreen = true;

TouchPanel.EnabledGestures = GestureType.FreeDrag | GestureType.DragComplete

I

GestureType.Pinch | GestureType.PinchComplete;

}

}

Среди полей также включен объект Matrix, который обрабатывает перемещение и масштабирование, но только в процессе выполнения операций жеста. Как только палец снимается с экрана – и поскольку жесты DragComplete и PinchComplete активированы, приложение может определять, когда это происходит – массивы pixels и PixelInfo полностью перестраиваются, и объект Matrix возвращается к своему значению по умолчанию. Это оказывается одной из самых сложных частей приложения.

Перегруженный LoadContent на удивление прост: Проект XNA: MandelbrotSet Файл: Game1.cs (фрагмент)

protected override void LoadContent() {

// Создаем новый SpriteBatch, который может использоваться для отрисовки текстур spriteBatch = new SpriteBatch(GraphicsDevice);

viewport = this.GraphicsDevice.Viewport;

segoe14 = this.Content.Load<SpriteFont>("Segoe14");

}

Но такая простота обусловлена лишь тем, что вся остальная инициализация выполняется в сочетании с захоронением. Конечно, я хотел бы сохранять весь массив объектов PixelInfo, но учитывая то, что каждый из них размером 44 байта, и размер всего массива достигает 17 мегабайт, можно понять, почему операционная система Windows Phone 7, кажется, сопротивляется моим желаниям.

Вместо этого приложение выполняет захоронение четырех элементов, необходимых для его корректного перезапуска. Статические поля xPixelCoordAtComplexOrigin, yPixelCoordAtComplexOrigin и в unitsPerPixel обеспечивают приложению возможность восстановить массив PixelInfo. Кроме того, приложение сохраняет изображение всего экрана как файл в формате PNG и затем восстанавливает и его тоже. При возвращении из

захоронения приложение выглядит точно так же, как до него. Но это лишь обманчивый внешний вид, поскольку все вычисления для каждого пиксела требуется начинать заново. Как следствие, некоторое время после возвращения из захоронения экран может оставаться без изменений.

Код для сохранения и восстановления объектов Texture2D при захоронении стандартен и довольно прост, но я решил создать пару методов, которые будут выполнять всю эту работу. Статический класс Texture2DExtensions (Расширения двухмерной текстуры) библиотеки Petzold.Phone.Xna включает следующие два метода. Первый – это метод расширения, поэтому он может вызываться прямо для объекта Texture2D:

Проект XNA: Petzold.Phone.Xna Файл: Texture2DExtensions.cs (фрагмент)

public static void SaveToPhoneServiceState(this Texture2D texture, string key) {

MemoryStream memoryStream = new MemoryStream();

texture.SaveAsPng(memoryStream, texture.width, texture.Height); PhoneApplicationService.Current.State[key] = memoryStream.GetBuffer();

}

Этот метод создает объект MemoryStream и просто передает его в метод SaveAsPng (Сохранить как PNG) объекта Texture2D. Сам объект MemoryStream не может быть сериализован, но его метод GetBuffer возвращает массив байт, который может быть сериализован.

Вспомогательный метод загрузки не является методом расширения, потому что приводит к созданию нового объекта Texture2D. Байтовый массив извлекается из хранилища и передается в конструктор MemoryStream, и этот MemoryStream затем используется со статическим методом Texture2D.FromStream:

Проект XNA: Petzold.Phone.Xna Файл: Texture2DExtensions.cs (фрагмент)

public static Texture2D LoadFromPhoneServiceState(GraphicsDevice graphicsDevice,

string key) {

Texture2D texture = null;

if (PhoneApplicationService.Current.State.ContainsKey(key)) {

byte[] buffer = PhoneApplicationService.Current.State[key] as byte[]; MemoryStream memoryStream = new MemoryStream(buffer); texture = Texture2D.FromStream(graphicsDevice, memoryStream); memoryStream.Close();

}

return texture;

}

Рассмотрим перегруженные OnActivated и OnDeactivated приложения MandelbrotSet, которые используют описанные выше два метода, и метод под именем InitializePixelInfo (Инициализировать Pixellnfo):

Проект XNA: MandelbrotSet Файл: Game1.cs (фрагмент)

protected override void OnActivated(object sender, EventArgs args) {

PhoneApplicationService appService = PhoneApplicationService.Current;

if (appService.State.ContainsKey("xOrigin") && appService.State.ContainsKey("yOrigin") && appService.State.ContainsKey("resolution"))

{

PixelInfo.xPixelCoordAtComplexOrigin = (double)appService.State["xOrigin"]; PixelInfo.yPixelCoordAtComplexOrigin = (double)appService.State["yOrigin"]; PixelInfo.unitsPerPixel = (double)appService.State["resolution"];

}

else {

// Первоначальный запуск приложения

PixelInfo.xPixelCoordAtComplexOrigin = 2 * viewport.Width / 3f; PixelInfo.yPixelCoordAtComplexOrigin = viewport.Height / 2; PixelInfo.unitsPerPixel = Math.Max(2.5 / viewport.Height,

3.0 / viewport.Width);

}

UpdateCoordinateText();

// Повторное создание или восстановление растрового изображения после захоронения

texture = Texture2DExtensions.LoadFromPhoneServiceState(this.GraphicsDevice,

"mandelbrotBitmap");

if (texture == null)

texture = new Texture2D(this.GraphicsDevice, viewport.Width, viewport.Height);

// Получение данных текстуры и массива пикселов PixelInfo.pixelWidth = texture.Width; PixelInfo.pixelHeight = texture.Height;

int numPixels = PixelInfo.pixelWidth * PixelInfo.pixelHeight; pixels = new uint[numPixels]; texture.GetData<uint>(pixels);

// Создание и инициализация массива PixelInfo pixelInfos = new PixelInfo[numPixels]; InitializePixelInfo(pixels);

// Запуск потока вычислений

Thread thread = new Thread(PixelSetterThread); thread.Start();

base.OnActivated(sender, args);

}

protected override void OnDeactivated(object sender, EventArgs args) {

PhoneApplicationService.Current.State["xOrigin"] = PixelInfo.xPixelCoordAtComplexOrigin;

PhoneApplicationService.Current.State["yOrigin"] = PixelInfo.yPixelCoordAtComplexOrigin;

PhoneApplicationService.Current.State["resolution"] = PixelInfo.unitsPerPixel;

texture.SaveToPhoneServiceState("mandelbrotBitmap");

base.OnDeactivated(sender, args);

}

void InitializePixelInfo(uint[] pixels) {

for (int index = 0; index < pixelInfos.Length; index++) {

pixelInfos[index] = new PixelInfo(index, pixels);

}

PixelInfo.hasNewColors = true; PixelInfo.firstNewIndex = 0;

PixelInfo.lastNewIndex = pixelInfos.Length – 1;

К концу выполнения метода OnActivated все поля и объекты инициализированы и готовы к работе, поэтому запускается второй поток выполнения на базе метода PixelSetterThread (Поток метода задания значений пикселов). Этот метод выполняется в течение всего остального времени жизни приложения, постоянно перебирая все члены массива PixelInfo, индексированные pixelIndex, и вызывая метод Iterate. Если Iterate возвращает true, пикселу задается значение цвета:

Проект XNA: MandelbrotSet Файл: Game1.cs (фрагмент)

void PixelSetterThread() {

int pixelIndex = 0;

while (true) {

lock (pixelInfosLock) {

if (!pixelInfos[pixelIndex].finished) {

if (pixelInfos[pixelIndex].Iterate()) {

int iteration = pixelInfos[pixelIndex].iteration; pixelInfos[pixelIndex].packedColor =

GetPixelColor(iteration).PackedValue;

PixelInfo.hasNewColors = true;

PixelInfo.firstNewIndex = Math.Min(PixelInfo.firstNewIndex,

pixelIndex);

PixelInfo.lastNewIndex = Math.Max(PixelInfo.lastNewIndex,

pixelIndex);

}

else {

// Особый случай: при увеличении масштаба предотвращаем // сохранение цветных блоков внутри множества Мандельброта if (pixelInfos[pixelIndex].iteration == 500 && pixelInfos[pixelIndex].packedColor !=

Color.Black.PackedValue) {

pixelInfos[pixelIndex].packedColor =

Color.Black.PackedValue;

PixelInfo.hasNewColors = true; PixelInfo.firstNewIndex =

Math.Min(PixelInfo.firstNewIndex,

pixelIndex);

PixelInfo.lastNewIndex =

Math.Max(PixelInfo.lastNewIndex,

pixelIndex);

}

}

}

if (++pixelIndex == pixelInfos.Length) {

pixelIndex = 0; globalIteration++;

}

}

}

}

Color GetPixelColor(int iteration) {

float proportion = (iteration / 32f) % 1;

if (proportion < 0.5)

return new Color(1 – 2 * proportion, 0, 2 * proportion);

proportion = 2 * (proportion – 0.5f);

return new Color(0, proportion, 1 – proportion);

}

Несмотря на то что для этого потока важно выполнять вычисления максимально быстро, он также пытается взять на себя некоторые функции перегруженного Update (грядущего). В статических полях структуры PixelInfo этот поток указывает минимальный и максимальный индексы измененных пикселов.

Я упоминал ранее, что в более простых приложениях для вычисления множества Мандельброта обычно задается максимальное число итераций. (В статье Википедии, посвященной множеству Мандельброта, приведен алгоритм псевдокода, где max_iteration задано значение 1000.) В своем приложении мне пришлось задать максимум для количества итераций только здесь. Как будет показано вскоре, при масштабировании посредством пары пальцев приложению приходится начинать все с самого начала и использовать новый массив структур PixelInfo. Но для целей визуализации и создания приближенного изображения объект Texture2D просто растягивается. Это обычно приводит к тому, что некоторые цветные пикселы оказываются в области множества Мандельброта, и используемый здесь алгоритм никогда не обеспечит закрашивание этих пикселов черным опять. Поэтому если число итераций для конкретного пиксела достигает 500, и цвет этого пиксела не черный, он закрашивается черным. Впоследствии этот пиксел может быть опять закрашен в какой-либо другой цвет, но на данный момент нам это не известно.

Рассмотрим первую часть перегруженного метода Update. В ней данные цвета из массива PixelInfo, вычисленного во втором потоке, передаются в массив pixels, и затем объект Texture2D обновляется значениями из этого массива:

Проект XNA: MandelbrotSet Файл: Game1.cs (фрагмент)

protected override void Update(GameTime gameTime) {

// Обеспечиваем возможность выхода из игры

if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed) this.Exit ();

// Обновляем текстуру пикселов массивом pixelInfos

if (PixelInfo.hasNewColors) {

lock (pixelInfosLock) {

// Передаем новые цвета в массив pixels

for (int pixelIndex = PixelInfo.firstNewIndex;

pixelIndex <= PixelInfo.lastNewIndex; pixelIndex++)

{

pixels[pixelIndex] = pixelInfos[pixelIndex].packedColor;

}

// Передаем новый pixels в текстуру

int firstRow = PixelInfo.firstNewIndex / texture.Width; int numRows = PixelInfo.lastNewIndex / texture.Width – firstRow + 1; Rectangle rect = new Rectangle(0, firstRow, texture.Width, numRows); texture.SetData<uint>(0, rect, pixels, firstRow * texture.Width,

numRows * texture.Width);

// Перезадаем PixelInfo

PixelInfo.hasNewColors = false; PixelInfo.firstNewIndex = Int32.MaxValue; PixelInfo.lastNewIndex = 0;

// Обновляем отображаемое значение globalIteration upperRightStatusText.Remove(0, upperRightStatusText.Length); upperRightStatusText.AppendFormat("{0}", globalIteration + 1); Vector2 textSize = segoe14.MeasureString(upperRightStatusText); upperRightStatusPosition = new Vector2(viewport.Width – textSize.X, 0);

}

Источник: Чарльз Петзольд, Программируем Windows Phone 7, Microsoft Press, © 2011.

По теме:

  • Комментарии