PN-треугольники

PN треугольники (англ. curved point-normal triangles, PN triangles) — способ геометрического представления трёхмерных объектов для их визуализации.

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

Каждый PN треугольник представляет собой кубический треугольник Безье, основанный на трёх вершинах (b₃₀₀, b₀₃₀, b₀₀₃) и трёх нормалях (n₂₀₀, n₀₂₀, n₀₀₂) этих вершин исходного плоского («базового») треугольника. Основная идея метода заключается в использовании информации о вершинах и нормалях базового треугольника в создании кубического треугольника Безье для каждого такого исходного треугольника, а также в возможности генерирования любого количества треугольников из треугольника Безье.

Математические моделиПравить

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

Примечание: в данной статье рассматривается квадратичная функция распределения нормалей, но возможно также использование линейной функции, что тоже даёт хорошие результаты.

Модель поверхности криволинейного треугольникаПравить

 

${\begin{aligned}b(u,v)=&\sum _{i+j+k=3}b_{ijk}{\frac {3!}{i!j!k!}}u^{i}v^{j}w^{k}\\=&b_{300}w^{3}+b_{030}u^{3}+b_{003}v^{3}\\&+b_{210}3w^{2}u+b_{120}3wu^{2}+b_{201}3w^{2}v\\&+b_{021}3u^{2}v+b_{102}3wv^{2}+b_{012}3uv^{2}\\&+b_{111}6wuv\end{aligned}}$ 

Здесь u, v и w — барицентрические координаты. u, v, w ≥ 0; w = 1 — u — v.

Коэффициенты b_ijk вычисляются следующим образом:

${\begin{aligned}b_{300}&=P_{1}\\b_{030}&=P_{2}\\b_{003}&=P_{3}\\b_{210}&={\frac {(2P_{1}+P_{2}-w_{12}N_{1})}{3}}\\b_{120}&={\frac {(2P_{2}+P_{1}-w_{21}N_{2})}{3}}\\b_{021}&={\frac {(2P_{2}+P_{3}-w_{23}N_{2})}{3}}\\b_{012}&={\frac {(2P_{3}+P_{2}-w_{32}N_{3})}{3}}\\b_{102}&={\frac {(2P_{3}+P_{1}-w_{31}N_{3})}{3}}\\b_{201}&={\frac {(2P_{1}+P_{3}-w_{13}N_{1})}{3}}\\b_{111}&={\frac {E+(E-V)}{2}}\\E&={\frac {b_{210}+b_{120}+b_{021}+b_{012}+b_{102}+b_{201}}{6}}\\V&={\frac {(P_{1}+P_{2}+P_{3})}{3}}\\w_{ij}&=(P_{j}-P_{i})\cdot N_{i}\in \mathbb {R} \end{aligned}}$ 

Здесь P_k — это вектор координат исходной вершины k, k=1,3.
N_k — это вектор координат нормали исходной вершины k, k=1,3.

Модель распределения нормалей криволинейного треугольникаПравить

 

${\begin{aligned}n(u,v)=&\sum _{i+j+k=2}n_{ijk}u^{i}v^{j}w^{k}\\=&n_{200}w^{2}+n_{020}u^{2}+n_{002}v^{2}\\&+n_{110}wu+n_{011}uv+n_{101}wv\end{aligned}}$ 

Здесь u, v и w — барицентрические координаты. u, v, w ≥ 0; w = 1 — u — v.

Коэффициенты n_ijk вычисляются следующим образом:

${\begin{aligned}n_{200}&=N_{1}\\n_{020}&=N_{2}\\n_{002}&=N_{3}\\n_{110}&={\frac {h_{110}}{\left\Vert h_{110}\right\Vert }},\quad h_{110}=N_{1}+N_{2}-v_{12}(P_{2}-P_{1})\\n_{011}&={\frac {h_{011}}{\left\Vert h_{011}\right\Vert }},\quad h_{011}=N_{2}+N_{3}-v_{23}(P_{3}-P_{2})\\n_{101}&={\frac {h_{101}}{\left\Vert h_{101}\right\Vert }},\quad h_{101}=N_{3}+N_{1}-v_{31}(P_{1}-P_{3})\\v_{ij}&=2{\frac {(P_{j}-P_{i})\cdot (N_{i}+N_{j})}{(P_{j}-P_{i})\cdot (P_{j}-P_{i})}}\in \mathbb {R} \end{aligned}}$ 

Здесь P_k — это вектор координат исходной вершины k, k=1,3.
N_k — это вектор координат нормали исходной вершины k, k=1,3.

Функции с конкретными коэффициентамиПравить

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

ДетализацияПравить

Для улучшения визуального качества исходного объекта, состоящего из плоских треугольников, входящим в его состав треугольникам придают криволинейную форму, что делает объект более гладким. Также для исходных треугольников задают некоторый уровень детализации. Чем выше уровень детализации, тем, соответственно, более гладким выглядит визуализируемый объект. Именно благодаря детализации «запускается» механизм PN треугольников.

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

Разбиение треугольника осуществляется в барицентрических координатах. В результате, каждый «маленький» треугольничек получает свои барицентрические координаты u, v и w, уникальные в пределах ограничивающего его исходного треугольника.

В реальной модели объекта, состоящей из исходных плоских треугольников, каждому их «маленькому» треугольничку впоследствии будет соответствовать ровно один «новый маленький» треугольничек («поднятый» над поверхностью исходного плоского треугольника), имеющий свои три вершины (и их абсолютные координаты) и свои три нормали. Вычисляются они через функции с конкретными коэффициентами, выведенные из моделей 1.1 и 1.2 отдельно для каждого исходного «большого» треугольника. Барицентрические координаты u, v и w (w = 1 — u — v) вершин всех «маленьких» треугольничков, полученные относительно внешнего для них исходного треугольника, поочерёдно подставляются в эти функции. Как было сказано выше, эти функции должны быть определены для каждого исходного плоского треугольника. Сами эти функции есть формулы и остаются неизменными. Детализация криволинейного треугольника реализуется именно через подстановку в эти формулы координат u и v, поскольку барицентрические координаты каждой отдельно взятой точки на криволинейном треугольнике идентичны барицентрическим координатам соответствующей ей точки на исходном «большом» треугольнике. В результате подстановки для каждой вершины всякого «нового маленького» треугольничка получаются её абсолютные координаты и её нормаль, что впоследствии позволит «отправить» такие треугольнички на визуализацию.

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

Сравнение с другими методамиПравить

 

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

ПроизводительностьПравить

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

СсылкиПравить

• Vlachos, A., Peters, J., Boyd, C., Mitchell, J.: Curved PN triangles. In: Proceedings of the 2001 Symposium on Interactive 3D Graphics, pp. 159—166. ACM (2001)