Интерполяция триангулированной поверхности в задачах синтеза изображений методом обратного трассирования

УДК 681.323

В.М. ГУСЯТИН, канд. техн. наук, ХНУРЭ,

Р.В. СОРОКИН, ХНУРЭ

ИНТЕРПОЛЯЦИЯ ТРИАНГУЛИРОВАННОЙ ПОВЕРХНОСТИ В ЗАДАЧАХ СИНТЕЗА ИЗОБРАЖЕНИЙ МЕТОДОМ ОБРАТНОГО ТРАССИРОВАНИЯ

Розглядається метод інтерполяції тріангульованої поверхні при синтезі зображення методом зворотнього трасування. Вхідними даними для інтерполяції є сітка трикутників з визначеними нормалями у вершинах сітки. Метод, що пропонується, дозволяє, з одного боку, використовувати існуючу базу програмних засобів створення полігональних моделей, а з іншого - використати можливість геометричної інтерполяції поверхні при синтезі зображення методом зворотнього трасування.

The method for smooth interpolation of triangulated surfaces is considered. Input data for algorithm are triangle mesh with normal at each vertex. Purposed method make possible to use current modeling software for creation polygonal models, on the one hand, and use possibility of analytically interpolation of polygonal surfaces during visualization with ray-tracing, on the other hand.

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

Анализ литературы. В работе [1] описан способ интерполяции с использованием сплайнов Безье. Однако поиск точки пересечения с параметрическими сплайнами требует больших вычислительных затрат [2, 3]. В работах [4, 5] рассматривается способ интерполяции с помощью радиал-базисных функций. Интерполирующая поверхность строится глобально и охватывает все вершины, потому уравнение поверхности громоздкое и требует больших вычислительных ресурсов для поиска точки пересечения. Авторами работ [6, 7] предлагается использовать для интерполяции алгебраические поверхности высоких порядков. Недостатком такого подхода является сложность расчета коэффициентов таких поверхностей, которая ограничивает использование этого подхода для интерполяции сеток, конфигурация которых меняется при синтезе анимации. В статье [8] рассмотрен метод интерполяции треугольных сеток при синтезе изображений методом обратного

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

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

Область определения поверхности. На рис. 1 изображен треугольник РРР . п0, п, п2 - предварительно рассчитанные нормали в вершинах треугольной сетки. ю - вспомогательная плоскость, проходящая параллельно плоскости треугольника Р0Р1Р2 . Q0, Q1, Q2 - точки пересечения плоскости ю с прямыми, проходящими через вершины Р0, р, Р2 в направлении нормалей п0, п1, п2 соответственно.

Рис. 1. Построение линии сопряжения

Область определения интерполирующей поверхности ограничена линейчатыми поверхностями Ц (5, /), проходящими через ребра рРг+1 интерполируемого треугольника:

Ь,

где р, (0 = Р, (1- 0 + Р+^, д, (0 = Qi (1- 0 + QI+lt, г е [0, 1]; 5 - параметр, задающий точку на образующей линейчатой поверхности.

45

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

Для построения линий сопряжения для ребер интерполируемого треугольника рассчитываются координаты центров и радиусы сфер Б1, 5г2, проходящих через вершины ,-го ребра Ррм. Причем, центр каждой сферы лежит на продолжении соответствующих нормалей в вершинах. Таким образом, центр сферы Б1 лежит на продолжении нормали п, а центр сферы

Б2 лежит на продолжении нормали пм . Линия сопряжения сг (О строится как линейная интерполяция между точками пересечения ограничивающей поверхности и сфер вдоль образующих прямых ограничивающей поверхности:

с,

где у](Г), у2(/) - линии пересечения ограничивающей поверхности Ц(5,t) и

сфер Б1, Б2 соответственно.

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

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

Нормали к поверхности вдоль линий сопряжения. Для гладкого соединения смежных интерполирующих поверхностей для каждой точки на линии сопряжения с\ ^) задается вектор нормали, общий для смежных поверхностей, с помощью функции:

п*

где пт^) - векторная функция касательных векторов к кривой сг(0 .

Радиус-вектор интерполирующей поверхности. Интерполирующая поверхность задается параметрическим способом. В процессе вычисления радиус-вектора поверхности для заданных параметров (барицентрических координат Хи, Ху) выполняются следующие этапы:

1. По барицентрическим координатам определяются точки Р и Q на треугольниках Р0Р1Р2 и 606162 соответственно:

Р  РоХи + РхХу + Р2(1 -Хи -Ху), 6 = 6оХм + ЄіХу + 62(1 -Хи -Ху).

2. Вычисляются точки пересечения Р\ прямых РР, + 2 , с ребрами РР+1 .

3. Вычисляются точки Сі на линиях сопряжения и соответствующие этим точкам нормали N по соотношениям:

с

4. Вычисляются центры шести сфер §/ , у  1, 2. Сферы ^ проходят через ребра РІСІ+1 с центрами, расположенными на продолжении нормалей пі. Сферы §2 проходят через ребра РіСі+1 с центрами, расположенными на продолжении нормалей Ні+1.

5. Определяются ближайшие точки пересечения Vі отрезка Р6 с каждой их сфер £/ .

6. Окончательно, радиус-вектор поверхности р5 для параметров Хи, Ху определяется по соотношениям:

р8  Уі1Хи + У'ХУ + У'Х„ + Кі2 ^ Ьр- + Кз2 ,

где Хж  1 - Хи - Ху .

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

На рис. 2 приведен пример триангулированной поверхности тора, состоящей из 128 треугольников (слева), и результирующая гладко интерполированная поверхность тора (справа).

Рис. 2

Выводы. Предложен метод интерполяции триангулированной поверхности, который позволяет повысить реалистичность визуализации полигональных поверхностей методом обратного трассирования. Интерполирующая поверхность строится локально для каждого треугольника входной треугольной сетки. Локальное задание поверхности позволяет использовать данный способ интерполяции для динамически изменяемых в процессе синтеза кадров изображения полигональных моделей (например, при синтезе скелетной анимации). Авторы предполагают в дальнейшей статье изложить метод нахождения точек пересечения проекционного луча с данной поверхностью с помощью итерационного алгоритма [10]. Использование такого итерационного алгоритма позволит находить точку пересечения с построенной поверхностью с заданной точностью за заданное количество итераций.

Список литературы: 1. Stefanie Hahmann, George-Pierre Bonneau. Polinimial Surface Interpolating Arbitrary Triangulations // IEEE Transaction On Visualization And Computer Graphics. - 2003. - Vol. 9.

- №. 1. — P. 99-109. 2. Barth W., Sturzlinger W. Efficient Ray Tracing for Bezier and B-Spline Surfaces // Computers & Graphics,. - 1993. - 17 (4). - P. 423-430. 3. Campagna Swen, Slusallek Philipp, Seidel Hans-Peter. Ray tracing of spline surfaces: Bezier clipping, chebyshev boxing, and bounding volume hierarchy - a critical comparison with new results // Visual Computer. - 1997. - 13 (6). - P. 265-282. 4. Kajiya J.T. Ray Tracing Parametric Patches // Computer Graphics. - 1982. - 16 (3).

- P. 245-254. 5. Yngve G., Turk G. Creating smooth implicit surfaces from polygonal meshes. -Technical report, College of Computing, Georgia Institute of Technology.- 1999. - Tech Report GIT-GVU-99-42. 6. Turk G., Brien J.O. Modelling with Implicit Surfaces that Interpolate // ACM Transactions on Graphics. - 2002. - 21 (4). - P. 855-873. 7. Bajaj C., Chen J, Xu G. Modeling with Cubic A-Patches // ACM Trans. on Graphics. - 1995. - Vol. 14. - I. 2. - P. 103-133. 8. Bajaj C., Ihm I. Algebraic Surface Design with Hermite Interpolation // ACM Transactions on Graphics. - 1992. -Vol. 11. - N°. 1. - P. 61-91. 9. Formella Arno, Muller Kerstin View point dependent approach to ray trace free-form Surfaces. Computer Graphics Forum. - Vol. 23. - I. 2. - P. 14-156. 10. Гусятин В.М. Итерационный алгоритм синтеза изображения в растровой графике реального масштаба времени // Харьков, ХТУРЭ, Радиоэлектроника и информатика. - 1998. - № 3. - С. 81-83.

Поступила в редакцию 11.10.2007