УПРОЩЕНИЕ ТРИАНГУЛЯЦИОННЫХ МОДЕЛЕЙ ПОВЕРХНОСТИ
Мирза Н.С., Скворцов А.В., Чадов Р.В.
Мирза Н.С., Скворцов А.В., Чадов Р.В.
Факультет информатики Томского государственного университета
В настоящее время очень много графических программных систем использует цифровые модели поверхности.
Для задач ГИС, САПР, систем трёхмерного моделирования и других графических систем очень актуальной является проблема обработки
больших (детализированных) поверхностей, так как для работы с поверхностями, которые могут не помещаться в оперативную память
компьютера, требуется мощное аппаратное обеспечение. Поэтому разработано большое число алгоритмов генерализации (упрощения) поверхности,
которые позволяют значительно уменьшить детализацию поверхности, вызывая существенное увеличение скорости выполнения задач, связанных
с обработкой поверхностей.
В данной статье под термином «поверхность» будем понимать однозначную функцию высот от планового положения точек. Такие поверхности ещё называют 2,5-мерными, чтобы отличить это понятие от значения общего понятия «3-мерная поверхность», принятого в математике.
Одним из самых распространённых методов представления поверхности явля- ется нерегулярная сеть треугольников (TIN), представляющая собой набор тре- угольников, образующих в проекции на ось XY триангуляцию – планарный граф, все конечные грани которого являются треугольниками [1]. Таким образом, TIN – это триангуляция, каждому узлу которой поставлена в соответствие его высота (координата Z).
Определение. Пусть имеется TIN T, содержащая N узлов. В задаче построения упрощающей TIN (задаче генерализации) требуется найти такую TIN t, что [1]:
- она содержит заданное количество узлов n = t < N и имеет минимальное отклонение d от T: d(T,t) = min d(T,τ), |τ| n (задача, управляемая геометрией);
- она имеет отклонение d по вертикали от T не более чем на заданную величину n(t) = min n(τ), и имеет минимальное количество узлов n(t) = min n(τ), d(T,τ) < ε (задача, управляемая ошибкой).
Задача упрощения TIN в обоих вариантах является NP-сложной, поэтому на практике используются приближённые алгоритмы [1], которые применяют некоторый критерий качества упрощённой модели. Все методы упрощения триангуляционных поверхностей можно разделить на следующие классы в зависимости от критерия оптимальности [2]: - методы, основанные на локальном критерии оптимальности, то есть методы, в которых точность вычисления связана с каждым элементом поверхности (таким как узел, ребро или треугольник);
- методы, основанные на глобальном критерии оптимальности, т.е. методы, в которых точность вычисления связана исключительно со всей поверхностью;
- методы, основанные на некотором специальном критерии оптимальности;
- экспертные методы, не использующие критерий оптимальности (экспертные методы), то есть методы, полностью основанные на визуальной оценке пользователя.
Основные понятия и постановка задачи
В данной статье под термином «поверхность» будем понимать однозначную функцию высот от планового положения точек. Такие поверхности ещё называют 2,5-мерными, чтобы отличить это понятие от значения общего понятия «3-мерная поверхность», принятого в математике.
Одним из самых распространённых методов представления поверхности явля- ется нерегулярная сеть треугольников (TIN), представляющая собой набор тре- угольников, образующих в проекции на ось XY триангуляцию – планарный граф, все конечные грани которого являются треугольниками [1]. Таким образом, TIN – это триангуляция, каждому узлу которой поставлена в соответствие его высота (координата Z).
Определение. Пусть имеется TIN T, содержащая N узлов. В задаче построения упрощающей TIN (задаче генерализации) требуется найти такую TIN t, что [1]:
- она содержит заданное количество узлов n = t < N и имеет минимальное отклонение d от T: d(T,t) = min d(T,τ), |τ| n (задача, управляемая геометрией);
- она имеет отклонение d по вертикали от T не более чем на заданную величину n(t) = min n(τ), и имеет минимальное количество узлов n(t) = min n(τ), d(T,τ) < ε (задача, управляемая ошибкой).
Задача упрощения TIN в обоих вариантах является NP-сложной, поэтому на практике используются приближённые алгоритмы [1], которые применяют некоторый критерий качества упрощённой модели. Все методы упрощения триангуляционных поверхностей можно разделить на следующие классы в зависимости от критерия оптимальности [2]: - методы, основанные на локальном критерии оптимальности, то есть методы, в которых точность вычисления связана с каждым элементом поверхности (таким как узел, ребро или треугольник);
- методы, основанные на глобальном критерии оптимальности, т.е. методы, в которых точность вычисления связана исключительно со всей поверхностью;
- методы, основанные на некотором специальном критерии оптимальности;
- экспертные методы, не использующие критерий оптимальности (экспертные методы), то есть методы, полностью основанные на визуальной оценке пользователя.
