|
В докладе я собираюсь рассказать о геометрические алгоритмах, используемых в ходе разработки программного
обеспечения для обратного моделирования (ОМ). Грубо говоря, ОМ — это воссоздание геометрии
реального трехмерного предмета, пригодной для дальнейшей компьютерной обработки. Подробнее: на практике данные
о предмете выдаются трехмерным сканером в виде «облака точек» — множества точек
в R3. Исследуемые предметы (и дальнейшие сценарии их
«компьютерной жизни») могут быть весьма разнообразны: детали автомобилей или мотоциклов, статуи, предметы
интерьера, здания, ландшафты и т.д. Но независимо от предметной области, достаточно общей является
задача нахождения более детальных геометрических характеристик сканированных объектов, нежели простое получение при помощи
сканера некоторого множества точек на поверхности объекта.
В задачи ОМ часто входят
| – |
триангуляция — нахождение триангулированной поверхности (обычно с краем), вершинами треугольников которой являются
точки облака; здесь, довольно остро стоит проблема корректной обработки острых ребер модели;
|
| – |
приближение триангулированной поверхности (или ее части) «аналитической» поверхностью (или же
набором поверхностей); например приближенное представление поверхности набором NURBS-поверхностей (обобщение поверхностей
Безье).
|
Тут интересны следующие задачи:
| 1) |
построение разбиения триангулированной поверхности на заданное число криволинейных четырехугольников
(в результате каждому четырехугольнику отвечает один патч);
|
| 2) |
гладкое «сшивание» патчей, то есть получение гладкой объединенной поверхности;
|
| 3) |
нахождение параметризации аппроксимируемых точек;
|
| 4) |
выбор сглаживающего функционала;
|
| 5) |
поиск «полулокального» алгоритма.
|
|
