Фрактал Мандельброта
Одним из примеров графики, когда быстродействие функции SetPixel не имеет особого значения, можно считать рисование фрактала Мандельброта
(рис. 7.7).
Здесь для каждого пиксела выполняется не больше, чем 512 итераций. Номер последней итерации для каждой точки комплексной плоскости (от 0 до 511)
определяет цвет пиксела в окне отображения. Преобразование номера в цвет сделано в виде отдельной функции indexToCoior. Эта функция очень проста, ее следует рассматривать лишь как возможный вариант. Для того чтобы получить более яркие цветные изображения этого же фрактала, можно запрограммировать другие способы преобразования индексов в цвета. Поэкспериментируйте с этим, возможно в результате вы получите такой код функции IndexToCoior, который будет значительно превышать по объему весь код вычисления фрактала. Кардинально меняет изображение изменение диапазона (minx, maxx, minY, maxY) . В нашем примере программы показываются четыре изображения — весь фрактал и три его фрагмента.
Рисование фрагментов фрактала — это не простое увеличение изображения, оно дает все новые и новые детали. Поэкспериментируйте с увеличением фрагментов (интересные изображения располагаются у границы фигуры). Для этого вызовите функцию Mandelbrot с соответствующими значениями
аргументов minX,maxX,minY,maxY.
Еще одним примером программы, для которой быстродействие функции Setpixei не критично, может служить реализация метода обратной трассировки лучей.
Здесь использован алгоритм, основанный на локальных преобразованиях координат, в общих чертах уже рассмотренный в главе 4. Мы обсудим несколько усеченный вариант данного алгоритма. Будем выводить только зеркальные и матовые (диффузные) поверхности, заданные плоскими гранями. Тем не менее, это позволяет ощутить основные особенности метода обратной трассировки. Текст программы studeExl3 достаточно объемный.
В этом примере объекты являются, либо только зеркальными, либо только диффузными. Кроме того, не показывается сам источник света — предполагается, что он не виден ни прямо, ни в отраженном виде. Источник света здесь один — точечный, светит равномерно во все стороны белым светом.
Поскольку объектов немного и они просты, то здесь не используется метод оболочек.
Данную программу можно усовершенствовать для показа более сложных изображений. Например, предусмотреть несколько разноцветных источников света, зеркальные блики, прозрачность объектов. Сделайте это самостоятельно в качестве упражнения.
В состав API Windows входит несколько функций, которые рисуют прямые и кривые линии:
□ AngleArc — дуга окружности с заданием углов;
□ Arc, ArcTo — дуга эллипса;
□ LineDDA — вычисление координат пикселов отрезка прямой линии и вызов определяемой пользователем функции вывода пикселов;
LineTo — рисование отрезка прямой линии от текущей позиции к заданной точке;
□ MoveToEx — задание текущей позиции графического вывода;
□ PoIyBezier, PolyBezierTo — один или несколько связанных между собой кубических сплайнов Безье;
□ PoIyDraw — несколько связанных отрезков прямых и сплайнов Безье;
□ Polyline, PolylineTo — ломаная линия из многих связанных между собой
отрезков прямых (полилиния);
□ PolyPolyline — несколько полилиний как единый объект.
Примеры для линий — графических примитивов API Windows — даны в табл. 7.1.
Стиль линии. Перо
В терминологии Windows API перо описывает следующие характеристики линии — цвет, толщину и стиль (пунктир). Перо — один из атрибутов контекста графического устройства. По умолчанию в контекст выбрано перо, которое соответствует черной тонкой непрерывной линии. Такое перо относится к стандартным перьям.
Все линии, рисуемые вашей программой с помощью функций GDI Windows API, выводятся одним и тем же цветом, имеют одинаковую толщину и тот же стиль до тех пор, пока не изменить перо. Функции рисования линий не имеют аргументов для указания текущих атрибутов линий (это характерно для графических библиотек, в которых подобные характеристики рисуемых объектов записываются как глобальные переменные, чтобы уменьшить количество аргументов вызова функций рисования).
Перо относится ко всем линиям и контурам фигур.
Чтобы начать рисовать линии, например, другим цветом, необходимо создать новое перо и выбрать его в контексте графического устройства. Отныне все линии будут рисоваться данным пером до тех пор, пока вы не выберете в контексте устройства очередное перо.
Важно то, что, создавая новое перо, нужно обязательно позаботиться об уничтожении предыдущего пера. Перо есть объект GDI, для него выделяется специальная область памяти. Перо существует до тех пор, пока его не уничтожить. Завершение работы прикладной программы может и не привести к автоматическому уничтожению объектов GDI и освобождению памяти компьютера. Своевременное уничтожение неиспользуемых объектов GDI возлагается на вашу программу. Иначе для некоторых версий Windows могут возникнуть утечки памяти, накопление которых может привести к нежелательным последствиям.
Не следует пытаться уничтожить стандартные перья.
Для определения стиля линий используются функции, которые имеют в своем названии —Реп—. Типичная последовательность для вывода линии с заданным стилем может быть такой:
Здесь создается перо, которое соответствует тонкой красной штрих-пунктирной линии. После использования перо уничтожается.
Рассмотрим пример программы, в которой используются функции MoveToEx и LineTo для рисования меридианов и параллелей шара.
Текст программы studex20. срр:
Изображение шара приведено на рис. 7.9.
Запустите программу, выберите пункт меню "Графика" и вы увидите шар, который, как кажется, вращается вокруг оси. Здесь вращается не шар, а система координат. Для этого использовано соответствующее преобразование координат при создании проекции — повороты координат. Углы наклона камеры в этом примере следующие: а=0...18О, β =45 градусов
. Меридианы и параллели рисуются только для тех точек поверхности, для которых координата Z больше нуля (в повернутой системе). Положительные значения Z соответствуют видимой части шара. Рисование меридианов и параллелей сделано в виде одной функции MeridOrParal для уменьшения размера текста программы. Необходимо отметить, что эта программа разработана как раз для шара. Чтобы-
В следующем примере программы мы используем линии для рисования фрактала. Этот фрактал немного напоминает папоротник (рис. 7.10). Используем перья различных оттенков зеленого цвета для имитации ствола, ветвей и листвы.
В этом примере рисуются линии различной толщины: для листвы линии толстые, а для ствола и ветвей — тонкие (можно и наоборот — для листвы более толстые линии).
В API Windows есть несколько графических примитивов, которые предназначены для рисования фигур с заполнением:
О Chord — хорда эллипса;
□ Ellipse — эллипс;
□ Pie — сектор эллипса;
□ Polygon — полигон;
□ PolyPolygon — несколько полигонов и (или) полигоны с пустотами; П Rectangle — прямоугольник;
□ RoundRect — прямоугольник со скругленными углами.
По умолчанию в контексте графического устройства устанавливается стиль заполнения сплошным белым цветом. Для того чтобы рисовать определенную фигуру другим стилем, необходимо создать соответствующую кисть. Кисть и стиль заполнения — синонимы в API Windows.
Кисть — это объект GDI. Он требует памяти. Кроме того, все кисти, созданные во время работы программы, необходимо уничтожить, иначе они могут остаться в памяти после завершения программы. Общая схема использования кистей такая же, как и для перьев:
1. Создание кисти, выбор ее в контекст.
2. Рисование фигур с заполнением.
3. Освобождение контекста, уничтожение кисти.
Сплошная кисть создается функцией CreateSolidBrush. Рассмотрим пример использования оранжевой кисти.
Рассмотрим пример программы для рисования поверхности, заданной в виде функции z =f(x, у), например:
Для рисования с удалением невидимых точек поверхности используем метод сортировки граней по глубине, а точнее, будем прямо рисовать грани от самых дальних к самым близким. Каждую грань можно рисовать четырехугольником-полигоном (рис. 7.11.).
7.4. Шрифт TrueType
Рассмотрим пример использования шрифтов TrueType (рис. 7.12).
В некоторых версиях Windows, возможно, эта программа не будет корректно работать. Может потребоваться задать другое имя шрифта. Но для того, чтобы буквы показывались с наклоном, этот шрифт обязательно должен быть типа TrueType (подойдет и Ореn Туре для Win2000).
ГЛАВА 8
Примеры использования
классов языка C++
Рассмотрим пример графической программы, создающей изображения объектов на основе нескольких простых элементов (рис. 8.1).
Используем объектно-ориентированную методологию. Каждый элемент будем считать, объектом трехмерного пространства, а несколько таких объектов образовывают модель сложного объекта. Для описания объектов используем классы C++. Процитируем автора языка C++ Б. Страустрапа: "Определите, какие классы вам нужны; предусмотрите полный набор операций для каждого класса; опишите общие черты явным образом, используя наследование" [24].
Сложный пространственный объект в нашей программе построим с использованием таких элементов: куб, сфера и пирамида. Фундамент и колонны будем считать производными элементами, их определим как множество кубов, специальным образом располагающихся в пространстве (рис. 8.2).
В качестве базового элемента определим абстрактный класс фигуры с такими свойствами: размер, цвет, расположение в пространстве, описываемое координатами ее центра. Также предусмотрим для фигур возможность перемещения, изменения размера, цвета и возможность быть нарисованной. Такие общие свойства выразим в классе shape. В этом классе также предусмотрим операцию преобразования координат для отображения в определенной проекции (функция-член Prepare Vertex).
Теперь обсудим способ отображения объектов. Поскольку у нас есть элементы-многогранники (куб и пирамида), то можно было бы использовать достаточно быстродействующую функцию Polygon API Windows для рисования граней. А удаление невидимых точек осуществлять сортировкой граней по глубине. Однако такой способ отображения в нашем случае не приемлем. Чуть позже мы покажем почему, а пока что обсудим довольно интересные нюансы объектно-ориентированного стиля программирования. Если бы у нас все объекты были многогранниками, то сортировка граней по глубине означала бы определенную последовательность рисования граней. Например, сначала одну грань одного объекта, потом соответствующую грань другого объекта и так далее. Последовательность рисования в этом случае должна быть от самых дальних граней к самым близким. Однако это усложняет объектно-ориентированную реализацию программы, поскольку желательно было бы, чтобы объект был самодостаточным с точки зрения каждой операции, выполняемой над ним, — а это невозможно, так как операция сортировки граней должна обеспечивать доступ к отдельным граням, а не только к объекту в целом. Хотя объектно-ориентированная методология не накладывает столь жестких ограничений на реализацию объектов, однако, такое нарушение самодостаточности (инкапсуляции) выглядит не очень эстетично.
Поскольку среди элементов кроме многогранников есть сфера, то метод сортировки граней по глубине нельзя использовать, так как сфера — это не многогранник, и она рисуется по пикселам (хотя можно было бы определить ее как многогранник, закрашенный, например, по методу Гуро, однако это намного сложнее, и в данном примере программы не рассматривается). Необходимо использовать Z-буфер, а функция polygon его не поддерживает. Более того, в составе функций API Windows нет ни одной функции рисования, рассчитанной на использование Z-буфера. Такие функции мы вынуждены сконструировать сами. Относительно объектной ориентированности — метод Z-буфера позволяет полностью инкапсулировать операцию рисования объекта в виде одной функции-члена (мы ее назовем : :Draw). Один вызов функции Draw обеспечивает полный цикл отображения объекта соответствующего класса.
Скомпилируйте и запустите программу studex34. Необходимо предупредить, что цикл показа может затянуться надолго. В программе выполняется полный оборот камеры на 360 градусов с шагом в один градус. Время создания и отображение всех 361 кадров в соответствующих ракурсах на компьютере с процессором AMD K6-2, 300 МГц, в 24-битном видеорежиме составляло 807 секунд. То есть, на один кадр расходуется в среднем 807/361 = 2.24 секунды. Размеры окна не изменялись после запуска программы, это отвечает размерам изображения 392 на 239 пикселов. Необходимо признать, что эта программа демонстрирует черепашью скорость рендеринга
.
8.1. Анализ и оптимизация программы
Каждую программу можно усовершенствовать. Можно попробовать уменьшить текст программы, уменьшить размер выполняемого файла, улучшить структурированность, модульность и так далее. В данном случае мы попытаемся повысить скорость рендеринга — уменьшить время формирования кадров изображения.
Как оптимизировать программу по быстродействию? Для этого необходимо выполнить анализ работы программы. В результате анализа нужно обнаружить операции, которые обуславливают быстродействие программы. После , того как будут найдены критические места программы, можно сделать выводы относительно конкретных путей оптимизации.
Для измерения времени выполнения операций в программе для Windows
можно воспользоваться функцией API GetLocalTime :
.
Необходимо предупредить, что миллисекунды измеряются, не очень точно, поэтому для повышения точности измерения для некоторой отдельной операции можно делать цикл из многих (сотен, тысяч, ...) одинаковых операций ' (если вспомогательные операции создания цикла сами по себе не длительные). Кроме того, различные сеансы измерений могут давать различные значения, поэтому необходимо как-то усреднять результаты. Понятно, что все измерения должны выполняться на одном и том же компьютере и обязательно в одинаковых условиях выполнения программы. Также необходимо учитывать, что в полночь измерение времени может дать ошибку, — если переход на 0 часов случится в ходе измерений. Впрочем, я и не рекомендую вам по ночам засиживаться за компьютером — ночью надо спать.
Теперь приступим к анализу программы studex34. Вся работа по созданию объектов, их отображение в различных ракурсах и уничтожение объектов делается в теле функции DrawstudyExample. Сделаем измерения времени основных операций. На создание объектов, открытие контекста, подготовку битмапа двойного буфера и создание Z-буфера расходуется менее десяти миллисекунд (измерения с точностью до процентов секунд дают 0.00). Таким образом, в ходе дальнейшего анализа сосредоточимся на цикле создания 361 кадра.
Как измерить время, расходуемое во всех 361 кадрах на выполнение функции Clear MyZbufferO Это сделаем способом, который можно назвать "способом контрольно-измерительного стенда". Такой "стенд" можно сделать на основе текста нашей программы, например, следующим образом:
Разумеется, подобный способ измерений можно считать корректным лишь тогда, когда время выполнения функции CiearMyZbufferO значительно больше, чем время выполнения операций организации цикла по.
Время выполнения 361 операции ClearMyZbuffer составляет в среднем 2.1 секунды. Аналогично можно сделать измерения для PatBit— 0.06 сек., setCameraViewMatrix — 0.00 сек., BitBlt — 0.5 сек. Однако делать измерения времени для цикла отображения объектов таким "стендовым" способом нельзя. Для корректного создания изображения обязательно выполнение всех подготовительных операций в полном объеме. Для измерений времени здесь можно предложить другой способ. Суть его такова. Вначале измеряем время выполнения полного цикла создания изображений:
и измеряем время выполнения без нее. Полный цикл — 807 сек., без исключенной операции — 2.6 сек. Назовем такой способ "временным исключением". Необходимо заметить, что цифру 2.6 можно было бы получить и иначе, если от времени полного цикла вычесть уже измеренное время других операций. Однако способ "временного исключения" предназначен в первую очередь для тех случаев, когда измерение всех составных операций затруднено или не нужно. Продолжим измерения дальше.
Как мы видим, в цикле создания кадров на подготовительные операции расходуется мало времени в сравнении с отображением объектов. В ходе отображения объектов выполняется много операций. Какая из них самая длительная? Осуществим поиск способом "временного исключения". Однако для применения этого способа есть много ограничений. Сформулируем основные условия корректного использования данного способа.
1. Временно исключить можно не любую операцию, а только ту, отсутствие которой не нарушает логику работы программы. Другие операции должны выполняться в полном объеме и в той же последовательности. Это главное условие. Остальные условия можно сформулировать как следствие.
2. Необходимо быть внимательными, если вы работаете с оптимизирующим компилятором. Он может сделать такие изменения в программе во время компиляции, о которых мы и не подозреваем. Мы можем исключить одну операцию — а компилятор исключит еще несколько и никак нам об этом не сообщит. Это приведет к иллюзии значительной роли временно исключенной операции.
3. Нельзя изменять стратегию использования виртуальной памяти (если это специально не анализируется). Например, в функции DrawStudyExampie нами не используется ни одна из файловых операций. Однако в ходе выполнения этой функции, программа может часто обращаться к диску. Это может быть в случаях, когда открываются значительные по объему массивы, и операционная система делает перераспределение виртуальной памяти между оперативной памятью (RAM) и диском. А в данное время мы временно выключили эту операцию, и обращения к диску прекратились — это может быть свидетельством того, что отныне все массивы целиком размещаются в RAM. Последнее может привести к ускорению выполнения программы, поскольку обращение к RAM осуществляется намного быстрее, чем к диску. Кроме того, когда размера RAM недостаточно для полной программы, то даже уменьшение объема кода при исключении может привести к тому, что программа будет работать быстрее —^таК"как отныне все размещается в RAM. Однако в этом случае уменьшения времени не пропорционально времени выполнения исключенной функции, и это не позволит рассчитать ее вклад в общее время выполнения программы. Таким образом, необходимо пользоваться правилом: объем оперативной памяти должен быть достаточным как для полной программы, так и программы, с исключением.
Способ временного исключения отдельных операций можно трактовать так: если после исключения некоторой операции время выполнения программы уменьшается не существенно, то эту операцию не нужно оптимизировать в первую очередь. Однако если в результате анализа мы и обнаружим некоторую длительную операцию, то это еще не означает, что ее можно ускорить.
Продолжим дальше анализ программы. Временно выключить функцию MyPolygon нельзя, поскольку тогда будет рисоваться только шар, а это означает другой порядок заполнения пикселами Z-буфера и растра битмапа двойного буфера. По аналогичной причине нельзя временно выключить функцию Sphere: : Draw (HDC hdc). А ЧТО же тогда МОЖНО?
Рассмотрим функцию SetPixMyZ. Если ее исключить, то прекратится запись пикселов в оба растра — Z-буфера и растра битмапа. Однако те функции, которые остались, выполняются так же, как и до исключения. Временно исключим setPixMyz. Результат— 57.5. То есть, из 807 секунд почти все время расходуется на запись пикселов.
Составная часть функции SetPixMyz — вызовы функции SetPixei. Временно исключим ее. Результат— 70 секунд. Результаты временных исключений отобразим следующей диаграммой (рис. 8.3).
По диаграмме исключения можно рассчитать, сколько времени расходуется в программе на выполнение отдельных операций:
Этот перечень неполон, можно анализировать еще некоторые функции, однако уже ясно, что основная причина низкой скорости — это использование функции SetPixei. Ее мы никак не можем изменить, ибо это функция API Windows. Но можно попробовать обойтись без нее.
Один из способов работы с растром — непосредственный доступ к памяти, хранящей растровый массив. Такой способ достаточно известен. Он использовался при разработке почти всех быстрых графических программ для когда-то популярной операционной среды MS-DOS. Среди функций MS-DOS предусмотрена функция рисования пиксела на экране, но она работала так же медленно, как и функция API Windows SetPixei. Поэтому для создания изображений на экране часто использовались операции непосредственной записи в видеопамять. В операционной системе Windows обращение прикладных программ к видеопамяти запрещено, а вся растровая графика основывается на понятии контекста графического устройства. Через контекст мы рисуем на экране, через контекст — в растрах битмапов. Кажется, это и все. Однако разработчики Windows предусмотрели еще одну возможность работы с растрами — операции с растрами в формате DIB (Device Independent Bitmap).
Можно создавать растр, не привязанный к какому-то графическому устройству по формату пикселов, а самое главное — предусмотрен доступ к растру по указателю на массив в памяти. С этим массивом можно производить любые операции, поскольку становится известным его адрес в виртуальной памяти. В том числе и выполнять операции над отдельными байтами и битами, которые представляют пикселы растра. Это открывает широкие возможности для создания собственных графических библиотек.
В программе использована одна из функций API Windows для работы с растрами DIB. Это функция stretchDiBits, которая осуществляет вывод растра из памяти по адресу pRastBuf в определенный контекст. Растровый буфер DIB здесь в формате 24-битного цвета— это позволяет достаточно просто моделировать различные интенсивности отражения света для цветных объектов. Для корректности сравнения работы обеих программ (studex34,35) все испытания следует производить в видеорежиме True Color 24 бит на пиксел.
В 24-битном режиме цвет каждого пиксела определяется тройкой байтов RGB. Как раз эти байты и записываются в память функцией SetPixRastrMem.
Скомпилируйте и проверьте работу программы studex35. Полный оборот камеры в ней делается за 88 секунд в отличие от studex34, где полный оборот составлял 807 секунды. Таким образом, создание одного кадра выполняется в среднем за 88/361 = 0.24 секунды. Благодаря замене функции SetPixel нашей собственной функцией SetPixRastrMem достигнуто уменьшение времени рендеринга более, чем в 9 раз. И это несмотря на то, что функция stretchoiBits работает медленнее, чем BitBit.
Необходимо отметить, что функция SetPixRastrMem предназначена только для 24-битных растров, a SetPixel корректно работает во всех цветовых форматах, поэтому она и работает медленнее.