4. Методы построения реалистичных трехмерных изображений

4.5. Удаление невидимых частей изображений

Для формирования объемных изображений используются каркасный, контурный и полутоновой методы.

В каркасных конструкциях (рис.4.11) видимыми являются все линии конструкции. Объемность изображенного пространства основано на перспективном эффекте, создающем иллюзию глубины изображения. Реализация метода требует наименьших вычислительных затрат, однако приемлема только для относительно несложных конструкций, поскольку наглядность изображения падает с увеличением числа граней.   

Рис. 4.11. Каркасная модель.            Рис. 4.12. Контурная модель.   

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

В контурном (рис.4.12) и полутоновом методах (рис.4.13) производится удаление линий, отрезков прямых и граней объектов, закрытых их поверхностями или поверхностями других объектов.   

Рис. 4.13. Полутоновая модель с удалением невидимых частей изображения   

Удаление невидимых линий и поверхностей считается классической задачей машинной графики. К настоящему времени разработано большое количество таких алгоритмов. Среди множества алгоритмов удаления невидимых линий и поверхностей нельзя выделить наилучший или универсальный, пригодный для различных применений. Выбор конкретного алгоритма зависит от ряда факторов: от принятой модели описания изображаемых объектов, вида изображений, требуемой точности представления объекта, ограничений на объем вычислений и память.  

Удаление невидимых линий и поверхностей требует существенных вычислительных затрат. Для упрощения используют ряд упрощений, к числу которых относят:  

*  вычерчивание только контуров граней объектов;  

*  аппроксимацию контуров ломаной линией;  

*  использование только плоских граней.  

Задача удаления невидимых частей изображения значительно упрощается, если использовать ортогональное проецирование. При центральном проецировании необходимо определять точки пересечения граней объекта с лучами, исходящими из точки наблюдения, что требует дополнительных вычислений.  

Удаление невидимых линий используют в основном при каркасном представлении объектов, а поверхностей при контурном и полутоновом.  

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

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

В алгоритме выделяют ряд стандартных ситуаций для различных случаев взаимных расположений граней объекта, при котором удаление невидимых частей разрешимо. Объектное пространство условно просекают прямоугольной трубой. Если сцена, заключенная в трубу, не принадлежит ни к одной из стандартных ситуаций, то трубу делят на четыре подпространства с сечениями, представляющими собой четыре части исходного сечения и производят их сопоставление со стандартными ситуациями. Безусловно, что при постепенном уменьшении сечения рассматриваемых подпространств вероятность встретить такую ситуацию возрастает. В наихудшем случае деление выполняют до одной точки.

Рис. 4.14. Принцип алгоритма Варнока

На рис. 4.14 показан пример выполнения одной итерации алгоритма Варнока.

Будем считать, что полученное сечение не принадлежит к установленным стандартным ситуациям, поэтому производят его деление на 4 части ( в общем случае разбиение можно производить на любое число).  

Поскольку подокно 3 пусто, то оно изображается на экране фоновой интенсивностью. Аналогично, подокно 4 полностью "просекает" только одну грань объекта, поэтому оно изображается на экране цветом этой грани.  

В подокне 1 находится только один многоугольник, следовательно он является видимым. Площадь вне этого многоугольника заполняется фоновым значением интенсивности, а сам многоугольник – цветом соответствующей ему грани.  

Сечение в подокне 2 содержит две грани, следовательно, его необходимо разделить на 4 части и выполнить описанные выше действия.  

Количество итераций алгоритма Варнока прямо пропорционально насыщенности изображения.  

С увеличением числа стандартных ситуаций количество делений на подпространства уменьшается.  

Алгоритм Варнока можно использовать для получения как векторных, так и растровых изображений.  

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

Рис. 4.15. Принцип удаления невидимых граней путем сортировки по глубине

Рассмотрим для примера сцену, которая состоит из четырех граней (рис.4.15). Пусть грань под номером 4 наиболее удалена от наблюдателя, а грань под номером 1 находится наиболее близко к наблюдателю. Вывод производится с грани, которая наиболее удалена (в нашем примере это грань 4). Затем выводятся поочередно грани 3, 2, 1.  

При реализации алгоритма необходимо учитывать прозрачность граней.  

Возможны случаи, когда новая грань не перекрывает предыдущую грань или новая грань частично или полностью перекрывает предыдущую грань.  

При варианте, когда грань не перекрывается другими гранями, она выводится без изменения (в примере это грань под номером 2). Когда новая грань частично или полностью перекрывает предыдущую грань, то для формирования изображения заменяется общая часть (в случае когда новая грань непрозрачна), либо осуществляется комбинирование цветов (в случае если новая грань прозрачна).  

Алгоритм обеспечивает формирование реалистичных сцен за счет возможности комбинирования цветов в каждой точке изображения.  

 В алгоритме Уоткинса трехмерная задача удаления невидимых линий и поверхностей сводится к двухмерной. Для этого осуществляется рассечения сцены плоскостями, перпендикулярными поверхности экрана, и выполняется анализ полученных в сечении проекций. Алгоритм выполняется по строкам развертки экрана. Плоскости сечения называют плоскостями развертки.   

Рис. 4.16. Принцип алгоритма Уоткинса   

Изображения в плоскостях развертки имеют вид набора отрезков прямых, представляющих собой ортогональные проекции плоских граней трехмерных объектов. Для формирования изображения в каждой плоскости развертки производится анализ отрезков прямых и определяют их положение относительно наблюдателя. Задача удаления невидимых граней сводится к задаче о том, какой отрезок видим для каждой точки сканирующей строки. Отрезки расположенные ближе к наблюдателю, закрывают полностью или частично отрезки, расположенные сзади (рис.4.16).  

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

Алгоритм Уоткинса одним из первых был реализован аппаратно.  

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

Основная идея метода состоит в следующем.  

Свет, излучаемый некоторым источником света, достигает наблюдателя, если он отражается от некоторой поверхности, преломившись или пройдя через нее. По результатам расчета интенсивности света, который достигает наблюдателя, можно определить невидимые поверхности (свет не достигает наблюдателя) или определить степень прозрачности объекта, определив разность интенсивностей света от источника и интенсивности света, достигшего наблюдателя. Однако полный расчет лучей, исходящих из всех источников, называемый прямой трассировкой (raytracing), из-за огромного количества применяется достаточно редко. Кроме того, большая часть работы на прослеживание лучей, не попавших в глаз наблюдателю и на определение освещенности невидимых поверхностей окажется проведенной впустую.  

Для снижения вычислительных затрат отслеживают лучи в обратном направлении (raycasting), т.е. от наблюдателя к объекту, как показано на рис.4.17. По пересечению лучей трассировки и объектов определяют видимые поверхности.  

Источник света находится в бесконечности на оси z, поэтому все лучи, исходящие из него, параллельны оси z. Каждому лучу, исходящему из источника света, отвечает свой пиксел на экране. Лучи проводятся от наблюдателя через гипотетическую растровую сетку экрана и далее в отображаемое пространство. Траектория каждого луча отслеживается, чтобы определить, какие именно объекты изображения, если такие существуют, она пересекает. Необходимо проверить пересечение каждого такого луча с каждым объектом изображения. Если луч пересекает объект, то определяются все возможные точки пересечения луча и объекта. Все точки пересечения упорядочиваются по глубине. Точка пересечения с максимальным значением глубины представляет видимую поверхность для соответствующего пиксела. Если ни одна из поверхностей не была пересечена лучом, то пикселу присваивается цвет фона.  

Значение интенсивностей лучей, трассированных через все узлы растровой сетки, рассчитываются для трех цветовых составляющих R, G, B и заносятся в кадровый буфер, откуда выводятся на экран.   

Рис. 4.17. Принцип алгоритма трассировки лучей   

Поскольку 75-95% времени, затрачиваемого алгоритмом трассировки лучей, используется на определение пересечений луча трассировки с объектом, то стремятся уменьшить вычислительную сложность этой процедуры. Например, реальные объекты условно помещают в простые оболочки (параллелепипед или сферу) и ищут пересечение луча с оболочкой (рис.4.18).   

Рис. 4.18. Размещение объектов в оболочку в алгоритме трассировки лучей.   

Если луч не пересекает оболочку, то следовательно, не пересекает и сам объект. Безусловно, что задание граней оболочки существенно проще, чем граней самого объекта.  

Максимальная "глубина" трассировки лучей либо задается пользователем, либо определяется самой программой-трассировщиком в зависимости от наличия свободной памяти.  

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

 В графических акселераторах наибольшего распространения получил алгоритм удаления невидимых поверхностей с использованием Z-буфера. Для реализации алгоритма кроме традиционной видеопамяти для хранения кадра изображения используют двухмерный массив памяти для хранения глубины (Z-координаты) каждого видимого элемента изображения.  

При разложение в растр элементов изображения вычисляется значение глубины Z для каждой точки. Если значение глубины Z текущей точки изображения меньше чем значение Z точки, которая ранее хранилась в видеопамяти по соответствующему адресу, то в видеопамять заносят значение текущей точки, а в Z-буфер ее глубину. В этом случае текущий элемент изображения перекрывает исходный. В противном случае модификация видеопамяти и Z-буфера не выполняется.   

Рис. 4.19. Принцип алгоритма с использованием Z-буфера   

Для реализации высококачественного рендеринга требуется большая разрядность Z-буфера. Чем выше разрешающая способность задания глубины, тем выше дискретность z-координат и точнее выполняется рендеринг удаленных объектов. 24-разрядный z-буфер обеспечивает более 16,7 млн. уровней задания глубины, 32-разрядный – более 2,8 млрд., а 16-разрядный – только 65536. Если при рендеринге разрешающей способности не хватает, то может случиться, что два перекрывающихся объекта получат одну и ту же z-координату, в результате не будет установлено, какой объект ближе к наблюдателю, что может вызвать артефакт, называемый triangle disposition.  

В современных графических акселераторах используют выделенный для Z-буфера блок памяти. В некоторых акселераторах для удешевления конструкции для этой функции используют основной буфер, что безусловно сказывается на производительности.  

Z-aлгоритм имеет простую аппаратную реализация, не требует предварительно сортировки примитивов, делает тривиальной визуализацию пересечений сложных поверхностей. Недостатки алгоритма состоят в необходимости введения дополнительного объема памяти, а также в сложности реализации эффектов прозрачности и просвечения. Затруднительно устранение лестничного эффекта.  

В OpenGL, одном из самых популярных программных интерфейсов (API) для разработки приложений в области двумерной и трехмерной графики, предопределяется удаление невидимых линий и поверхностей производить с использованием Z-буфера.  

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

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

     Содержание