Понятие о триангуляции
Объекты пространства описываются функцией 2 переменных. Т.к. аналитические выражения для таких объектов весьма сложны и при непосредственном использовании требуют больших вычислительных ресурсов (это видно даже для простейшего случая прямой - программа п. 6.4.1), применяется аппроксимация более простыми фигурами. Наиболее часто используется кусочно-линейная аппроксимация, когда поверхность составляется из каких-либо плоских фигур. Имеются некоторые каноны аппроксимации, позволяющие получать наиболее рациональные результаты. Так, кривая аппроксимируется отрезками прямой, плоская фигура сложной формы - прямоугольниками или квадратами. Гладкие поверхности - непересекающимися треугольниками. Процесс триангуляции состоит в создании сети непересекающихся треугольников с вершинами в заданных точках.
По сравнению с прямоугольной сеткой триангуляция имеет преимущества:
1. Отсутствует единый масштаб для всех данных, когда размер ячейки прямоугольной сетки автоматически устанавливает предел подробности карты, и сгущения точек отображаются только в пределах размера решетки. Размер треугольника при триангуляции не устанавливается. Там, где исходные точки разрежены (поверхность приближается к плоской), треугольники крупнее, при сгущении точек (большой кривизне поверхности) треугольники мельче. Количество треугольников определяется количеством исходных точек аппроксимации. Эйлер доказал теорему, что оно не превышает удвоенного количества исходных точек;
2. У прямоугольной сетки есть два выделенных направления, никак не согласованных с исходными данными. Для адекватного отображения поверхностей с высокой степенью кривизны приходится значительно измельчать сетку, что ведет к большим затратам вычислительных ресурсов.
За преимущества триангуляции приходится платить усложнением программирования.
В настоящее время в большинстве приложений используется триангуляция Делоне. Она строится однозначно и соединяет исходные точки в сеть наиболее правильных треугольников. Это удобнее в расчетах. Более подробно алгоритм построения триангуляции Делоне изложен в [ 2 ].
Пример использования триангуляции - построение линий уровня (топографические карты, изотермы и т.д.). Плоскость проектирования - область определения (задания) функции 2 переменных. Пусть это плоскость XY. Она разбивается на прямоугольные ячейки. Каждая ячейка сет-
ки делится на 2 треугольника. В результате получаем
стандартную триангуляцию области задания функции.
Проведя действия, обратные параллельному проектиро-
ванию вдоль оси Z, находим на поверхности точки ап-
проксимации. Далее решается задача пересечения тре-
угольников, составляющих поверхность, с плоскостями,
параллельными плоскости XY (горизонтального сечения). Здесь возможны случаи:
1. треугольник и плоскость не пересекаются, т.е. все вершины лежат по одну сторону плоскости;
2. треугольник касается плоскости одной вершиной, все вершины лежат по одну сторону плоскости;
3. треугольник пересекается с плоскостью по ребру, две вершины лежат на плоскости, все вершины лежат по одну сторону плоскости;
4. треугольник пересекается с плоскостью, т.е. имеется пара вершин, лежащих по разные стороны плоскости;
5. треугольник лежит в плоскости, т.е. все вершины лежат в плоскости.
Случай 1 Случай 2 Случай 3 Случай 4 Случай 5
Перечисление случаев показывает, как важен просчет всех вариантов. В некоторых задачах невыявленные варианты может обойти пользователь, знающий, где программа работает некорректно. В машинной графике это не проходит, получается плохое изображение.