Глава 18 Упрощённый пошаговый конусный метод ( конусное отображение)в рельефном моделировании –Часть 1 (Перевод)

18.1 – Введение

Присутствие геометрических деталей на поверхности объекта кардинально меняет распределение света по его поверхности. Хотя синтез реалистичных картинок требует симуляции этого распределения настолько точно, насколько возможно, на самом-то деле моделирование распределения до мельчайших деталей является непрактичным. Чтобы разобраться в этих вопросах была разработана особая техника рельефного отображения , основанная на добавлении некоторых фрагментов и деталей в произвольные полигональные модели. ( Поликарпов, 2005). Техника позволяет отрендерить скорректированные силуэты ( Оливера и Поликарпо, 2005), а так же управлять некоторыми деталями на поверхности объекта, не скорректированных по высоте.

( Поликарпов и Оливера, 2006).

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

( несводимости, ступенчитости), а так же пропускает некоторые небольшие структуры, как например на рисунке 18 – 1а.

Некоторые «скачковые» техники до сих пор используются для ускорения (поиска) узлов векторов высоты, а так же для минимизации ступенчатости функции. (Donnelly 2005, Dummer 2006, Baboud and Décoret 2006). Пошаговый метод конусов (конусное отображение) ( ПМК) ((CSM) (Dummer 2006)) предоставляет интересное решение проблемы ускорения расчёта таких узлов в большинстве случаев, а так же исключает потери приподнятых областей, используя для этого данные полученные на основе предыдущих расчётов ( конусное отображение). Однако, т.к. ПМК использует устаревший подход, вектора обычно не доходят до нужной поверхности, что даёт неверное представление о реальной структуре объекта, как например на рисунке 18-1b. Используя улучшенный ПМК, который содержит 4 различных радиуса для каждого фрагмента ( по сторонам света – север, юг, запад, восток), мы можем немного уменьшить количество данных неточностей, несовпадений. Мы называем этот подход – 4-х направленный пошаговый конусный метод (QDCSM)( 4-х направленное конусное отображение) . Его результаты показаны на фигуре 18 – 1с.

Рис. 18-1. 4 примера нахождения узлов приподнятых областей, основанные на map-рендеринге 256x256 текстуры

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

( конусным отображением). (CSM). Идея состоит в том чтобы заменить линейный поиск на более быстрый «скачковый» поиск, запускаемый сразу же после бинарного. В то время как ЦСМ является медленным, с трудом определяя радиусы конусов, даже не смотря на то что вектор никогда не достигнет искомой поверхности, при использовании RSC вектор достигает искомой поверхности с первого же раза. Такой метод производит вычисления по расширяющимся конусам, что существенно ускоряет сходимость метода. Как только мы узнали, что вектор достиг поверхности, мы можем сразу же применять бинарный поиск, чтобы уточнить координаты искомых узлов. Комбинация RCS и бинарного поиска существенно увеличивает качество рендеринга, так например, как мы видим на рисунке 18 – 1d. Заметим, что весь ализинг ( все неточности), замеченные ранее на фигурах а, b, с – в данный момент пропали. Т.к. РСЦ базируется на «скачковом» алгоритме, он может быть использован с другими стратегиями для решения тех же проблем ограниченных областей, таких например, как интервальное отображение ( метод интервалов). (Risser et al. 2005).

18.2 Краткий обзор рельефного моделирования.

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

Глубинная отображение (значения точек лежат в промежутке от 0 до 1) геометрически отрисованно, в соответствии с характером полигональной поверхности. Глубинные и нормальные отображения в индивидуальной RGBa текстуре (32 бита на каждый элемент текстуры), называются текстурой рельефа (Oliveira et al. 2000).

Для получения лучших результатов мы бы рекомендовали разделять объёмные и обычные компоненты на 2 различные текстуры. Тогда сжатие текстур, их компрессия, будет работать значительно лучше, т.к. специальное «нормальное» сжатие может быть использовано независимо от сжатия объёмного, причём, с получением лучших результатов, по качеству сжатия, а так же по количеству неточностей. Так же мы получаем, в итоге, лучшие результаты по визуализации, т.к. во время вычисления рельефного отображения необходим только один канал ( по глубине, объёму) – остальная информация нужна только в конце – для подсветки, для создания освещения. На рисунке 18 -2 показаны нормальное и глубинное отображения рельефной текстуры, поперечное сечение которых показано на рисунке 18 – 3. Составление рельефного отображения и преобразование его в полигональное сделано обычным способом, с помощью присваивания пар текстурных координат вершинам (пикам) модели ( объекта) . Во время рендеринга, глубинное отображение может динамически изменяться, для достижения различных эффектов, а правильная абсорбция достигается, в свою очередь, за счёт обновления глубинного буфера.

Рис. 18-2 Примеры рельефной текстуры.

Рис.18-3 Рельефный рендеринг

Рельефный рендеринг полностью представлен в GPU и может быть фактически разделён на три шага. Для каждого фрагмента f с координатами текстур (s,t) осуществляется преобразование из пространства V в соседнее пространство из f. Затем мы находим пересечение P с оттрансформированным ( изменённым) лучом, на глубинном отображении. Пусть (k, l) будут координатами текстур каждого узла ( см. Рисунок 18-3) . Далее, воспользуемся соответствующей позицией Р, расположенной в замкнутом, закрытом пространстве и нормалью ( нормальной позицией Р) расположенной в (k, l) чтобы оттенить f. Тень может быть настроена (наложена) с помощью проверки точки пересечения светового вектора и вектора Р, причём до того как он достигнет хоть одной точки рельефа. Рисунок 18-3 показывает весь этот процесс. Обсорбция рельефного отображения, а так же других объектов, достигается всего лишь при помощи обновления з-буффера, который хранит з-координаты от Р ( к примеру в закрытом пространстве или после выделения w и дальнейшего деления на его скаляр). Этот з-буффер так же поддерживает совместное теневое (Williams 1978) и рельефное моделирования соответственно.

На самом деле, поиск точки пересечения Р может быть представлен для начала на 2Д тектсурах. Таким образом пусть (u, v) это координаты 2Д текстуры, соответствующие той точке, в которой глубина проникновения вектора видимости достигает 1.0. (Рис. 18-3). Мы вычисляем (u, v) основанные на (s, t), на изменённом векторе видимости и на скалярной величине, установленной для глубинного отображения. Далее мы производим поиск Р для упрощенного глубинного отображения по шагам от (s, t) до (u, v), и проверяем, не достиг ли вектор видимости рельефа (а он должен достичь, иначе получится что глубина видимости превышает хранимую величину), пока не окажемся в (u, v). Если мы обнаруживаем точку, где наш вектор попадает под рельеф – местонахождение пересечения Р легче найти с помощью бинарного поиска.

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

Такая ситуация отображена на рисунке 18-4a, где значение глубины хранящееся в текстурных координатах, уже на половине процесса преобразования из (s, t)в (u, v) больше чем глубинная величина в видимой точке 1, т.к. луч уже пересёк плоскость поверхности. В таком случае, бинарный поиск приводит нас в ошибочную точку Q. Чтобы минимизировать такие упущения ализинга , Policarpo et al. (2005) использовал линейный поиск, чтобы ограничить область проведения бинарного поиска. Это отображено на Рисунке 18-4b, где шаги уменьшены для достижения точки 3 под плоскостью. Впоследствии, точки 2 и 3 служат входными параметрами для бинарного поиска. Линейный поиск, сам по себе, однако, используется для ализинга присутствующих тонких, небольших структур как например на рисунке 18-1a. Этим и обуславливается предложенное некоторыми исследователями использование дополнительных, предэксперементальных данных, для избегания потерь именно таких незначительных объектов (Donnelly 2005, Dummer 2006, Baboud and Décoret 2006). Техника, представленная в этой главе была разработана на основе пошагового метода конусов Dummer-а ( конусного отображения), который подробнее описан дальше.

Рис. 18-4 бинарная версия линейного поиска

18.3 Пошаговый метод конусов ( конусное отображение)

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

(Dummer 2006). Метод конусов ( конусное отображение) присваивает каждому циркулярному, круговому конусу пару точек глубинной текстуры. Угол каждого конуса – максимально допустимый, при условии что конус не пересекает верхнюю границу фигуры. Изображение на рисунке 18-5 описывает случай для трёх элементов текстуры в точках, с координатами (s, t), (a, b), и (c, d), чьи конусы изображены жёлтым, голубым и зелёным цветом соответственно.

Рисунок 18-5 Пошаговый метод конусов ( конусное отображение)

Начиная с фигуры f, во время изменения вида ( передвижения камеры) поиск узла пересечения происходит следующим образом: узел пересечения вектора и конуса хранится в (s, t). Полученная точка 1 – в текстурных координатах (а, b). Затем вектор продлевается до пересечения с конусом (а, b) , и мы получаем таким образом точку 2, с координатами (c, d).

Далее пересекаем луч с конусом из (c, d), получаем точку 3 и т.д. В этом простом примере точка 3 совпадает с искомым узлом. Так же, пошаговый конусный метод ( конусного отображения) гарантирует пересечение проекционного вектора с вершиной объекта, однако может понадобиться множество шагов, для достижения нужного пересечения.

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

Более того, 3D проекция получившегося пересечения P', в замкнутом пространсве так же не верна. Эти ошибки показывают нам об искажении результатов рендеринга, как например на фигуре 18-1b и 18-1c.

18.4 Упрощённый пошаговый конусный метод ( конусное отображение).

Пошаговый конусный метод ( конусное отображение), предложенный Даммером, заменяет оба поиска, и линейный и пошаговый ( описанные Поликарповым 2005) на простой поиск, базирующийся на конусном моделировании.

Улучшение эффективности алгоритма поиска узлов приподнятых плоскостей достигается с помощью комбинирования сильных сторон вышеуказанных алгоритмов: «прыжковые качества» пошагового конусного моделирования дополнены улучшенной точностью бинарного поиска.

Т.к. для бинарного поиска требуется наличие хотя бы двух входных параметров- точки под поверхностью рельефа, и точки над поверхностью рельефа, мы можем не рассматривать, не принимать во внимание то препятствие, из-за которого конусы из конусного метода ( конусного отображения) не могут достичь искомой плоскости. В нашем новом алгоритме, кроме всего прочего, мы продляем конусы до пересечения с плоскостью, когда это возможно. Идея состоит в том, чтобы увеличить радиус конуса настолько, насколько это возможно, соблюдая одно условие: если вектор видимости проникает внутрь конуса – то он не может пересечь рельеф больше, чем один раз. Мы называем получившийся алгоритм упрощённым конусным методом (конусным отображением). На рисунке 18-7a (в следующей подсекции) сопоставляются радиусы конусов, получившихся в ходе пошагового конусного метода ( голубой) и с помощью упрощённого конусного метода ( зелёный), для заданного фрагмента плоскости. Заметим, что радиус, полученный с помощью упрощенного конусного метода имеет большую величину, что даёт возможность алгоритму сойтись в точке пересечения за меньшее количество шагов. Использование более широких конусов из упрощенного конусного метода подходит для проведения линейного поиска, и, следовательно, для нахождения искомых результатов. Т.к. луч пересекает плоскость лишь единожды, можно так же использовать быстрый и более точный бинарный поиск.