АННОТАЦИЯ 3
ВВЕДЕНИЕ 7
1 Триангуляция Делоне 8
2 Системы и алгоритмы построения триангуляции Делоне 9
2.1 Обзор программных продуктов 9
2.2 Итеративный алгоритм для двухмерного пространства 10
2.3 Итеративный алгоритм для трехмерного пространства 11
3 Предлагаемый подход 13
3.1 Нормализация координат 13
3.2 Хранение тетраэдров в памяти 14
3.2.1 Уравнение плоскости и нормальный вектор, положение точки
относительно плоскости 15
3.2.2 Вершины и грани тетраэдра 16
3.2.3 Структуры данных для хранения 3 D-триангуляции 16
3.3 Построение начальной триангуляции (6 тетраэдров) 17
3.4 Локализация новой точки в существующей триангуляции 19
3.5 Перестроение тетраэдра, в который попала новая точка 19
3.6 Проверка условия Делоне 21
3.7 Перестроение пары смежных тетраэдров 21
4 Ускорение локализации новой точки 23
4.1 Использование статического кэша 24
4.2 Использование динамического кэша 25
5 Сортировка новых точек на основе кривых Гильберта 27
6 Проверка условия Делоне 30
6.1 Подстановка в уравнение описанной сферы (Матрица 5 х 5) 30
6.2 Подстановка в уравнение описанной сферы (Матрица 4 х 4) 31
6.3 Нахождение центра и радиуса описанной сферы через матрицы 4 х 4.32
6.4 Нахождение центра и радиуса описанной сферы через снижение
размерности и барицентрические координаты через длины сторон 34
6.5 Нахождение центра и радиуса описанной сферы через снижение
размерности и барицентрические координаты взятые через вершины тетраэдра 37
6.6 Нахождение центра и радиуса описанной сферы через равенство
скалярных произведений векторов и барицентрические координаты 38
6.7 Сравнение методов 39
7 Реализация 42
ЗАКЛЮЧЕНИЕ 45
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 46
Триангуляция - сетка, составленная из симплексов, т.е. простейших фигур в данном пространстве. Двумерная триангуляция - простейший вид триангуляции, состоящий из множества треугольников. Построение двумерной триангуляции обычно производят по набору точек на плоскости. Таким образом, если задать каждой точке значение какой-то функции, то триангуляция является кусочно-линейной интерполяцией трехмерной функции. Такое применение триангуляции используется при моделировании рельефов местности. Также двумерная триангуляция помогает решить многочисленные задачи пространственного анализа и задач на графах
Трехмерная триангуляции применяется для построения физических моделей различных реальных тел. Обобщение двумерной триангуляции до трехмерной усложняет как представление и отображение результата, так и сами алгоритмы построения.
Триангуляция Делоне вышла за границы области генерации сеток для численных вычислений и вошла в область кристаллографии, металлургии, картографии, геологии, а также в область компьютерной графики. Она используется во многих приложениях, например, для реконструкции объектов по точкам рассеянных данных, моделирования твердых тел, интерполяции и извлечения изоповерхности. Она также используется в виртуальной реальности для виртуальной хирургии и т. д.
Цель данной работы состоит в следующем: найти методы оптимизации времени работы итеративного алгоритма построения триангуляции Делоне, исследовать и реализовать их.
Для достижение цели было выбрано разбить задачу на подзадачи:
1. Изучить материалы по двумерной триангуляции Делоне
2. Адаптировать итеративный алгоритм для трехмерного случая
3. Разработать кэш для локализации точки
4. Разработать алгоритм для выбора оптимального порядка точек
5. Найти и реализовать быстрый способ проверки условия Делоне
В ходе работы была найдена и изучена литература по 3D триангуляции, исследована задача и сложности, которые возникают при ее решении. Были рассмотрены программные продукты, решающие задачу построения трехмерной триангуляции Делоне.
Был выбран, описан итеративный алгоритм построения трехмерной триангуляции, основанный на аналогичном алгоритме для двумерной триангуляции. Были описаны методы ускорения алгоритма и реализованы необходимые для них структуры и классы. Ускорение достигалось при помощи ускорения локализации новой точки, упорядоченного ввода новых точек в триангуляцию и при помощи оптимизации проверки условия Делоне
