Понятие о триангуляции

Объекты пространства описываются функцией 2 переменных. Т.к. аналитические выражения для таких объектов весьма сложны и при непосредственном использовании требуют больших вычислительных ресурсов (это видно даже для простейшего случая прямой - программа п. 6.4.1), применяется аппроксимация более простыми фигурами. Наиболее часто используется кусочно-линейная аппроксимация, когда поверхность составляется из каких-либо плоских фигур. Имеются некоторые каноны аппроксимации, позволяющие получать наиболее рациональные результаты. Так, кривая аппроксимируется отрезками прямой, плоская фигура сложной формы - прямоугольниками или квадратами. Гладкие поверхности - непересекающимися треугольниками. Процесс триангуляции состоит в создании сети непересекающихся треугольников с вершинами в заданных точках.

По сравнению с прямоугольной сеткой триангуляция имеет преимущества:

1. Отсутствует единый масштаб для всех данных, когда размер ячейки прямоугольной сетки автоматически устанавливает предел подробности карты, и сгущения точек отображаются только в пределах размера решетки. Размер треугольника при триангуляции не устанавливается. Там, где исходные точки разрежены (поверхность приближается к плоской), треугольники крупнее, при сгущении точек (большой кривизне поверхности) треугольники мельче. Количество треугольников определяется количеством исходных точек аппроксимации. Эйлер доказал теорему, что оно не превышает удвоенного количества исходных точек;

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

За преимущества триангуляции приходится платить усложнением программирования.

В настоящее время в большинстве приложений используется триангуляция Делоне. Она строится однозначно и соединяет исходные точки в сеть наиболее правильных треугольников. Это удобнее в расчетах. Более подробно алгоритм построения триангуляции Делоне изложен в [ 2 ].

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

ки делится на 2 треугольника. В результате получаем

стандартную триангуляцию области задания функции.

Проведя действия, обратные параллельному проектиро-

ванию вдоль оси Z, находим на поверхности точки ап-

проксимации. Далее решается задача пересечения тре-

угольников, составляющих поверхность, с плоскостями,

параллельными плоскости XY (горизонтального сечения). Здесь возможны случаи:

1. треугольник и плоскость не пересекаются, т.е. все вершины лежат по одну сторону плоскости;

2. треугольник касается плоскости одной вершиной, все вершины лежат по одну сторону плоскости;

3. треугольник пересекается с плоскостью по ребру, две вершины лежат на плоскости, все вершины лежат по одну сторону плоскости;

4. треугольник пересекается с плоскостью, т.е. имеется пара вершин, лежащих по разные стороны плоскости;

5. треугольник лежит в плоскости, т.е. все вершины лежат в плоскости.

Случай 1 Случай 2 Случай 3 Случай 4 Случай 5

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

Дата добавления: 2014-01-11