Доклад на ІІ Республіканській науковій конференції студентів , аспірантів та молодих вчених
«Комп ’ютерний моніторинг та інформаційні технології»
Донецк ДонНТУ 15 мая 2006г

ВОССОЗДАНИЕ ПОВЕРХНОСТИ ПО ПРОИЗВОЛЬНОМУ НАБОРУ ТОЧЕК. ПОДЗАДАЧА ПОСТРОЕНИЯ ПЛОСКОСТИ, НАИМЕНЕЕ УДАЛЕННОЙ ОТ СОВОКУПНОСТИ ТОЧЕК.

Е.Н. Хромова, Д.П. Пауков, Е.А. Башков

Донецкий национальный технический университет

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

Среди основных задач компьютерной графики в научной сфере можно выделить такие как:

- представление обучающего материала наиболее доступным для понимания способом;

- компьютерное представление объектов реального мира;

- моделирование поведения объектов в виртуальных трехмерных средах;

- представления данных эксперимента в наиболее эффективной для анализа форме.

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

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

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

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

Заключительным, третьим этапом работы алгоритма является построение сеточной модели объекта по его плоскостям, а также ее сглаживание.

Как можно видеть из алгоритма, подзадача построения плоскости, наименее удаленной от совокупности точек, составляют основу, на которую опираются все дальнейшие этапы работы. Основными параметрами плоскости являются базовая точка, через которую проходит плоскость, а также нормальный вектор плоскости, что можно записать как пару ( c, n). Базовая точка получается путем нахождения геометрического центра массива точек подмножества:

, где p i – точки множества.

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

Удобным для реализации является представление параметра минимизации в виде функции Лагранжа [2], где к сумме квадратов расстояний добавляется выражение, значение которого фактически равно нулю. Задача нахождения экстремума сводится к решению системы уравнений, формируемых из частных производных функции Лагранжа по неизвестным, приравненных к нулю.

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

Литература

1. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle. Surface reconstruction from unorganized points. ACM SIGGRAPH 1992, 71-78.

2. Бугров Я.С., Никольский С.М. Дифференциальное и интегральное исчисление: Учебник для вузов. – М: Наука, 1988