автореферат диссертации по инженерной геометрии и компьютерной графике, 05.01.01, диссертация на тему:Реконструкция поверхностей геометрических моделей, представленных дискретным множеством цифровых данных

На правах рукописи

Оноприйко Марина Дмитриевна

РЕКОНСТРУКЦИЯ ПОВЕРХНОСТЕЙ ГЕОМЕТРИЧЕСКИХ МОДЕЛЕЙ, ПРЕДСТАВЛЕННЫХ ДИСКРЕТНЫМ МНОЖЕСТВОМ ЦИФРОВЫХ ДАННЫХ

05.01.01 - Инженерная геометрия и компьютерная графика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород - 2003

РАБОТА ВЫПОЛНЕНА В НИЖЕГОРОДСКОМ ГОСУДАРСТВЕННОМ АРХИТЕКТУРНО-СТРОИТЕЛЬНОМ УНИВЕРСИТЕТЕ

Научный руководитель доктор технических наук, профессор Попов Евгений Владимирович

Официальные оппоненты:

доктор технических наук, профессор Кетков Юлий Лазаревич, кандидат технических наук, доцент Тарасова Светлана Валерьевна

Ведущая организация

Нижегородский государственный технический университет

Защита состоится 4 ноября 2003 года в 13 часов на заседании диссертационного совета Д 212.162.04 при Нижегородском государственном архитектурно-строительном университете по адресу: 603950, Нижний Новгород, ул. Ильинская, д.65, корпус 5, аудитория 202.

С диссертационной работой можно ознакомиться в библиотеке Нижегородского государственного архитектурно-строительного университета.

I

Автореферат разослан «_3_» _октября_ 2003 г. <

Ученый секретарь диссертационного совета, кандидат

технических наук, профессор

В.И. Дергунов

(

n

1^2 4г

1

Актуальность исследования

Современные достижения в области измерительной технологии, например, такие как лазерное сканирование, предоставляют возможность цифрового описания исследуемых объектов с достаточно высокой степенью точности. Это обстоятельство обусловило значительное повышение спроса на создание математических моделей, сгенерированных по данным, полученным в результате измерений, в таких областях как медицина, геология, археология, компьютерная графика и автоматизированное проектирование. При оцифровке поверхности бесконтактные сенсоры с высоким разрешением позволяют получить свыше 100000-500000 исходных точек. Представление той же поверхности параметрической математической моделью гораздо более компактно, так как требует всего 50-500 параметров. Кроме того, параметрическое представление дает возможность модификации формы поверхности путем изменения небольшого количества параметров, таких как управляющие точки, узловые вектора или весовые коэффициенты. Построение математического описания формы физических поверхностей является сравнительно новой областью исследования под названием реконструкция поверхности. Процесс преобразования набора дискретных оцифрованных точек в гладкую поверхностную модель представляет собой главную составляющую часть инженерного анализа - RE (Reverse Engineering). В области моделирования поверхностей за последние 30 лет создано множество методов, начиная от классических методов аналитической и дифференциальной геометрии, кончая современными методами сплайновой геометрии. Однако в инженерном анализе задача прямой генерации геометрической модели из дискретных оцифрованных точек по-прежнему не решена полностью, поскольку в процессе реконструкции поверхностной модели чрехзвычай-но трудно минимизировать численную ошибку, одновременно повысив гладкость поверхности.

Существуют два основных подхода к реконструкции поверхности на основе облака точек, представляющего модель объекта, - интерполяция и аппроксимация. Интерполяционный тип подгонки поверхности использует каждую точку исходных данных в реконструируемой поверхности, тогда как при аппроксимации поверхности отыскивается наилучшая подгонка гладкой поверх-

ности к оцифрованным данным с минимальным откло

тичная аппроксимация широко используется для минимизации численной ошибки с одновременным повышением гладкости поверхности в процессе моделирования.

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

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

Объектом исследования является оптимальная реконструкция поверхности по облаку дискретных оцифрованных точек с использованием NURBS-аппроксимации и интерполяции. В геометрическом моделировании реконструкция поверхностей является эффективным инструментом для преобразования физических объектов в математическое представление для последующих исследований и компьютерной доработки. Использование для этих целей NURBS обусловлено тем, что они приводят к классу наиболее гибких дискретных методов интерполяции и аппроксимации.

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

■ на основе обобщения теоретических основ реконструкции поверхностей по облаку дискретных точек разработать двухшаговый алгоритм аппроксима-

ции и интерполяции поверхности для случая положительных NURBS-весовых коэффициентов;

■ разработать полный набор алгоритмов для реконструкции поверхности сложной формы по набору пространственных сечений;

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

■ доказать эффективность разработанного компьютерного инструментария для решения практических задач геометрического моделирования.

В соответствии с целью исследования решались следующие задачи:

■ обосновать возможность достижения положительной интерполяции и наилучшей положительной подгонки при построении поверхности по облаку дискретных точек;

■ сформулировать двухшаговый алгоритм поиска положительных NURBS-весовых коэффициентов для подгонки поверхности по облаку дискретных точек;

■ показать преимущества сформулированного двухшагового алгоритма при решении выделенного класса задач по сравнению с В-сплайновой подгонкой.

Научная новизна исследования состоит в следующем:

= разработан новый математический аппарат оптимальной реконструкции поверхности по облаку дискретных точек с использованием NURBS, обеспечивающий эффективное решение разнообразных задач, возникающих при моделировании поверхностей;

■ доказана применимость данного аппарата реконструкции поверхности и его эффективность, по сравнению с другими способами геометрического моделирования при построении гладких поверхностей судового корпуса по дис-

кретному набору точек; при реконструкции формы поверхности геодезических объектов по результатам лазерного сканирования.

Практическая ценность исследования заключается в разработке специализированных алгоритмов и компьютерных процедур, реализующих возможности алгоритма реконструкции поверхности, для конструирования и сглаживания поверхностей судового корпуса, построенных по дискретному набору точек; восстановления формы поверхности геодезических объектов по результатам лазерного сканирования, в частности при выполнении работ по договору № 27/4 от 25.08.2003. На базе созданных алгоритмов и компьютерных процедур разработаны специализированные системы КЗ-Ship (автоматизированное проектирование, геометрическое моделирование и модификация поверхностей и конструкций судового корпуса), КЗ, КЗ-Design (реконструкция и моделирование поверхностей свободной формы с использованием NURBS). Системы являются законченными коммерческими программными продуктами, используемыми отечественными и зарубежными судостроительными (Польши, Норвегии и Нидерландов) и промышленными предприятиями.

Диссертационное исследование выполнено в рамках Фундаментальной НИР «Разработка теоретических основ алгоритмов и программ геометрии и графики для параллельных технологий проектирования» (ГР № 01970004538, Нижегородский государственный архитектурно-строительный университет).

Апробация работы

Материалы диссертационной работы представлялись на следующих конференциях и семинарах:

■ Международная конференция по компьютерной графике и визуализации "ГР АФИКОН-1994"(Нижний Новгород, 1994),

■ Всероссийская конференция КОГРАФ-95 (Нижний Новгород, 1995);

■ Всероссийская конференция КОГРАФ-96 (Нижний Новгород, 1996);

■ Международная конференция по компьютерной графике и визуализации "ГРАФИКОН-2001 " (Нижний Новгород, 2001).

Разработанное программное обеспечение демонстрировалось на Международных выставках "8оЛТоо1-2000", "8ойТоо1-2001", "8ойТоо1-2002" и "НЕ-I ВА-2001".

Публикации. Материалы диссертационного исследования опубликованы в 11 статьях.

Структура диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений, общим объемом: 124 страницы, 10 рисунков, 3 таблицы, 1 гистограмма. Список используемых литературных источников содержит 165 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность, определяется объект и цель, ставятся задачи исследования, формулируется научная новизна и практическая ценность работы.

В главе I проводится анализ составных частей процесса реконструкции поверхностей как средства сокращения сроков проведения работ при моделировании поверхностей.

Реконструкция поверхностей - одна из наиболее динамично развивающихся областей НЕ, целью которой является поиск математического описания ' формы физической поверхности для преобразования реальных объектов в ин-

женерные модели. В настоящее время использование новых средств бесконтактных измерений формы объекта (сканирование) резко повысило интерес к

I

реконструкции поверхностей и НЕ в целом, поскольку новые средства оцифровки дают возможность получать набор дискретных данных, описывающих различные поверхности, с высокой скоростью и достаточно высокой точностью.

Появление НЕ-технологий было обусловлено необходимостью получения математического описания существующих объектов или произведенных ранее деталей механизмов для последующих расчетных процессов и/или дополни-

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

Та часть КЕ, которая непосредственно связана с реконструкцией поверхности объекта, может быть более подробно представлена в виде последовательности следующих базовых этапов:

1. Получение оцифрованных данных (сканирование).

Основные методы получения оцифрованных данных объекта: бесконтактные (акустические, магнитные, оптические) и тактильные (робот, СММ-машина).

2. Обработка данных.

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

ния найдены, данные отдельных образов преобразуются в единое представление в общей системе координат (объединения образов).

I б) глобальная характеристика формы. Для создания качественной модели

физического объекта кроме облака точек необходима дополнительная информация об объекте (сегментация и классификация сегментов) и структуре дан' ных (топология).

Подгонка поверхности

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

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

> Сеть.

> Триангулированная (полигональная) сеть.

* > Разделяющаяся поверхность.

> Явное представление поверхности.

4 > Неявное представление поверхности.

* > Параметрическое представление поверхности.

> Поверхности тензорного произведения (В-сплайны).

> МиНВБ-представление поверхности.

В главе 2 проводится обоснование выбранного способа представления поверхности при реконструкции поверхностей объекта, заданных нерегулярным облаком точек.

Представление поверхностей, используемое в RE, с точки зрения реконструирования поверхностей для промышленных приложений, требует наличия следующих свойств:

> Непрерывность. '

> Свойство локальной модификации.

> Гибкость.

У Применимость.

NURBS-представление полностью удовлетворяет все приведенные выше требования:

1) Создание NURBS-представления кривой или поверхности достаточно быстро и вычислительно недорого. NURBS использует общее математическое представление как для стандартных аналитических кривых и поверхностей (конус, куб, поверхности вращения и т.д.), так и для кривых и поверхностей свободной формы. Это унифицирует процесс нахождения точек и линий пересечения для кривых и поверхностей. NURBS обладают свойством локальной модификации и инвариантны относительно аффинных преобразований.

2) В настоящее время NURBS являются частью таких национальных и интернациональных стандартов как IGES(USA), SET(France), VDAFS(Germany), STEP(ISO) и другие.

3) NURBS-моделирование активно используется как в программах для промышленного проектирования (CATIA, Pro/Engineer, SolidWorks, Гемма, KoMnac-3D), так и в пакетах художественного моделирования (3DSMAX, Maya, Softimage3D, SolidThinking).

4) Математический аппарат работы с NURBS хорошо развит, и на дан- • ный момент не существует методов моделирования, способных полностью за- ' менить NURBS-моделирование.

Таким образом, в настоящее время NURBS являются наиболее t

привлекательным форматом представления поверхностей в RE.

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

ный набор алгоритмов для построения поверхности по заданным поперечным сечениям произвольной формы.

К

Параметризация. Необходимым этапом в подгонке дискретных данных NURBS-пoвepxнocтью является параметризация точек исходных данных. Сле-I дует отметить, что в приложениях, связанных с реконструкцией поверхностей, исходные точки чаще всего произвольно расположены в пространстве. По этой причине классические методы параметризации не применимы. Для построения гладкой параметрической поверхности по дискретному набору произвольно расположенных точек была предложена концепция базовой поверхности.

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

Эффективная и корректная параметризация должна удовлетворять следующие три условия:

> свойство взаимно-однозначного отображения;

> гладкость;

> соответствие параметризации базовой и реконструируемой поверхности.

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

Кроме того, данный метод позволяет параметризовать не только неструктурированное облако точек, но, зачастую, дает более приемлемый результат при параметризации структурированного облака по сравнению с классическими методами параметризации.

Двухшаговый алгоритм

Постановка задачи может быть сформулирована следующим образом. Пусть задано:

- множество из / дискретных, произвольно расположенных в пространстве точек Ь,:={Р( =[*7,р7,г7]г >5, представляющих собой поверхность произвольной формы;

- локальные параметры и:= {«,}', и У:= {у,}{, приписанные исходным точкам;

- р, д - степень поверхности в соответствующих параметрических направлениях;

- п, т - число вершин управляющей сети поверхности, которые необходимо вычислить в соответствующих параметрических направлениях;

- 11:= {и, }"*'' и У:= {V, Ц"' узловые вектора, соответствующие локальным параметрам в параметрических направлениях и и V.

Необходимо найти интерполяцию или наилучшую подгонку исходных данных 1Ч1Л1В8-поверхностью с заданными параметрами, т.е. найти вершины управляющей сети поверхности и соответствующие им веса. Шаг 1: Идентификация ШЖВв-весов управляющей сети поверхности Уравнение, определяющее 1ЧШ1В8-поверхность в 40-пространстве может быть записано в следующей форме:

вгв 0 0 -вгхв х"

0 вгв 0 -ВГУВ У

0 0 в7 в -вггв ъ

0 0 0 м

= [0]4,

(1)

где

М = М0-(МЛ. +Му +мг) Мд. = (В' ХВ)(ВТ В)-' (ВГ ХВ) М, =(ВГ УВ)(ВГ В)"1 (В1 УВ)

м г = (Вг гв)(в' в)-' (вг гв) Таким образом, веса могут быть отделены от управляющих вершин и получены из следующей однородной системы:

М* = [0Ь (2)

где М - квадратная пхп симметрическая неотрицательная матрица.

Учитывая то, что М - симметрическая неотрицательная матрица, наиболее эффективным методом решения полученной однородной системы является преобразование Хаусхолдера и ОЬ-алгоритм. Соответствующие процедуры характеризуются высокой скоростью, кроме того, ортогональность собственных век-

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

М = РБРГ (3)

где T} = diag{dvdг,...dn}- диагональная матрица с диагональными элементами, являющимися собственными значениями матрицы М, расположенными в порядке убывания d¡ ¿dltl >0.

Р - ортогональная матрица, столбцы которой р, являются собственными векторами матрицы М, соответствующие собственному значению dí.

Общее решение уравнения (2) для случая весов чеЗ?" и М2 *0 может быть записано как:

п

5>,Р, (4)

<=/?+1

где

р - индекс в векторе собственных значений, для которого выполняется

d >d , =...= d .

Р Р+1 Я

{р(}("_ собственные вектора, соответствующие наименьшим собствен-

ным значениям Ц}"

р* 1

(а>}"-,,+!' произвольные коэффициенты.

Если ранг г матрицы М удовлетворяет условие г<п (т.е. {*/,}", =0 и, следовательно, решение иеЯ""''), то существует точное нетривиальное решение уравнения (2). Это означает, что (4) дает ТЧХЖВБ-интерполяцию исходных точек. Если ранг г матрицы М удовлетворяет условие г=п (т.е. dr, * 0), то (4) дает наилучшую ЖГКВЯ-подгонку исходных точек.

Общее решение (4) предполагает наличие отрицательных и нулевых ГЧиКВ8-весов, однако в практических приложениях отрицательные веса могут вызывать нежелательные особенности на реконструируемой поверхности. По этой причине необходимо найти наилучшее решение уравнения (2) в собственном пространстве матрицы М, основываясь только на положительных весах.

Базисная стратегия предполагает поиск решения в виде (4), такого, что IV €9*""'' и >0,41. Для решения этой задачи требуется минимизировать среднеквадратичное отклонение при наличии ограничений:

где

ХДР, - решение уравнения (2), записанное в виде (4).

= [Ц,...1]Г е9?"- единичные веса, определяющие В-сплайны. ™„ррег > > 0 - заданная верхняя и нижняя граница изменения веса.

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

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

1) Предположим, что ц - индекс в векторе собственных значений, для которого выполняется ><1,,^ =...=</„, тогда 1-п-д и еЭ?'.

п

2) Положительные значения р, мо1-ут быть найдены используя сим-

1~р-1+1

плекс-метод для минимизации функционала (5) при условии, что V ей' пЯ". Если минимум найден, то И' - наилучшее подпространство, содержащее положительные веса, ач1- возможное решение.

3) Чтобы увеличить размерность подпространства Я', значение / должно быть изменено так, чтобы текущее подпространство включило в себя новую группу собственных векторов, соответствующих следующим большим собственным значениям. Шаги 2 и 3 данного алгоритма выполняются до тех

пор, пока возможно минимизировать функционал (5).

Когда наилучшее подпространство максимальной размерности 9?' и возможные решения внутри него построены, может быть найдено множество наилучших решений в этом подпространстве. Наилучшие положительные веса для

подгонки в 9?' могут быть записаны как № = Др,, где коэффициенты могут

Ыр-и\

быть получены минимизацией следующего функционала:

1дчг

н2

i-n-W

nun

' I л2

l-n-l* I

^tower "upper* * •

Шаг 2: Построение вершин управляющей сети реконструируемой поверхности

Идентифицированные веса могут быть подставлены в уравнение (1) как известные параметры. В результате подстановки будет получена система из пит линейных уравнений относительно неизвестных X,Y,Z:

Bx = d

где d - правая часть, полученная в результате подстановки идентифицированных весов;

x = [x,wl,...x„w„,y,wl,...y„w„,z{wi,...zllw„¥ - вектор, содержащий неизвестные координаты вершин управляющей сети поверхности в однородном пространстве.

Данная система линейных уравнений является недостаточной и может быть разрешена методом наименьших квадратов с использованием преобразований Хаусхолдера и QR-алгоритма. Если ранг матрицы меньше к, то существует бесчисленное множество решений данной системы линейных уравнений. Из них может быть выделено решение с минимальной евклидовой нормой, которое будет оптимальным, т.е. minld- Вх£.

В результате решения системы будут получены вершины управляющей сети реконструируемой поверхности в однородном пространстве. Преобразование вершины управляющей сети поверхности из однородного пространства в 3D-MepHoe Евклидово пространство может быть получено перспективным проецированием.

В отличие от классической глобальной интерполяции, методы среднеквадратичной NURBS-подгонки обеспечивают эффективное решение, удовле- • творяющее требования моделирования гладких поверхностей. Предложенный двухшаговый алгоритм может быть применен для интерполяции или оптималь-

ной подгонки обобщенными NURBS-поверхностями дискретного множества точек. Если для данного набора данных оптимальной подгонки не существует, алгоритм позволяет найти NURBS-подгонку с положительными весами, которая, как правило, намного лучше, чем В-сплайновая подгонка. '

Алгоримы реконструкции поверхности по поперечным сечениям произвольной формы. В настоящее время в большом количестве приложений |

(медицина, биомедицинское моделирование, CAD/CAM) объект определяется последовательностью поперечных сечений. По этой причине главная задача, которая ставится в этих областях, - реконструировать поверхность объекта по '

заданным сечениям для создания затем копии исследуемого объекта при помощи станков с 4ny(NC) или быстрого прототайпирования(КР). Развитие акустических и имиджевых методик, таких как томография (CT), создание магнитно-резонансных (ММ) и ультразвуковых (USI) образов, позволило намного уп- 1 ростить процесс получения сечений исследуемого объекта. Это увеличило актуальность поисков эффективного решения задачи реконструкции поверхности ' по последовательности сечений произвольной формы.

Для решения задачи реконструкции поверхности по сечениям представлены следующие алгоритмы:

• Повышение степени NURBS-кривой.

• Повышение степени сегмента Безье.

• Понижение степени NURBS-кривой.

• Понижение степени сегмента Безье.

• Извлечение сегмента Безье из NURBS-кривой.

• Объединение сегментов Безье в NURBS-кривую. ^

• Репараметризация NURBS-кривой.

• Удаление узлов для минимального представления NURBS-кривой. <

Представлена методика гладкой аппроксимации поверхности по множе- '

ству поперечных сечений. Метод позволяет сконструировать поверхность по промежуточным контурным кривым, которые подгоняются к исходным контурным точкам с заданной точностью. Все контурные кривые представляются 1 NURBS-кривыми, определенными на общем узловом векторе. Результирующая поверхность также является NURBS-поверхностью.

С целью получения более компактного представления реконструируемой поверхности представляется алгоритм удаления узлов из общего узлового вектора.

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

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

Реконструкция геодезической поверхности. Алгоритмы реконструкции поверхностей были использованы в рамках работ, связанных с визуализацией и обработкой результатов геодезических съемок бетонного покрытия поля стадиона "Сормово". Геодезическая съемка бетонного покрытия поля стадиона была осуществлена с помощью лазерного теодолита в точках поверхности, расположенных в узлах прямоугольной сети с шагом 2000 мм. Размерность исходной прямоугольной сети - 96x38 узлов. На базе полученных данных реконструирована поверхность покрытия стадиона с целью ее визуализации, анализа качества поверхности бетонного покрытия и получения рабочих чертежей для доведения качества поверхности поля до требований Международного Олимпийского комитета. В качестве метода реконструкции поверхности был выбран двухшаговый алгоритм оптимальной подгонки Г^ЦИВв-поверхностью. В этом случае построенная поверхность является либо интерполяцией исходных точек, либо, если интерполяция не существует, наилучшей NURBS-пoдгoнкoй исходных точек. Кроме того, выбранный метод реконструкции поверхности не может привести к появлению пиков или линий складок (т.е. разрывов первой или второй производных) в получаемой поверхности. В качестве базовой по-

верхности в данном случае может быть выбрана плоскость, параллельная плоскости ХОУ декартовой системы координат, в которой получены оцифрованные точки, поскольку выполняется:

> свойство взаимно-однозначного отображения исходных данных на базовую поверхность;

> выбранная базовая поверхность является гладкой;

> параметризация базовой поверхности будет полностью соответствовать параметризации реконструируемой поверхности.

Направление проецирования было выбрано по нормали к базовой поверхности. Полученная параметризация исходных данных была использована для реконструкции поверхности NURBS-пoдгoнкoй с различной степенью гладкости.

Из таблицы 1 видно, что подгонка РШНВ8-поверхностыо позволяет получить поверхность с меньшими отклонениями от контрольных реперных точек, чем В-сплайновая подгонка с интегральной нормой.

Сравнение методов реконструкции поверхности для данного класса задач

Таблица 1

Метод реконструкции поверхности Отклонение от истинной поверхности (по Гауссу) в мм и % от шага измерения Время, затраченное на построение поверхности (сек)

с.» а

В-сплайновая интерполяция 8.01003 (0.4%) 3.89895 (0.2%) 5.5026 (0.28%) 11.45

ЖЖВБ-интерполяция 6.35382 (0.32%) 2.211 (0.11%) 4.0745 (0.2%) 11.20

Реконструированная поверхность была подвергнута пересечению горизонтальными поверхностями с шагом, заданным заказчиком, для получения линии равного уровня.

По построенным линиям уровня был создан комплект рабочих чертежей с числовыми отметками, который послужил основой для доведения бетонного покрытия поля стадиона "Сормово" до качества, соответствующего требованиям Международного Олимпийского комитета к спортивным сооружениям такого типа. При создании комплекта чертежей был проведен анализ реконструированной поверхности на предмет выбора условной нулевой отметки, позволяющей осуществить минимизацию отделочных строительных работ.

; 17

I 1

Рис. 1. Линии равного уровня, полученные в результате пересечения реконструированной поверхности горизонтальными плоскостями с заданным шагом.

Моделирование поверхностей судового корпуса. Первым этапом создания трехмерных твердотельных компьютерных моделей проектируемых изделий в судостроении является построение поверхности наружной обшивки корабельного корпуса. Чаще всего возникает задача построения корабельной поверхности по существующему набору дискретных точек, заданных в системе "Теоретические шпангоуты - Теоретические ватерлинии".

Подгонка поверхности судового корпуса ГЧиКВв-поверхностью тензорного произведения - наиболее гибкий инструмент моделирования, поскольку позволяет выбирать степень моделируемой поверхности и число управляющих вершин в каждом направлении. Огромное влияние на распределение управ-< ляюгцих вершин и общую геометрию результирующей ГШКВв-поверхности

имеет базисный узловой вектор и назначение параметров для каждой исходной декартовой точки. Если построение узловых векторов достаточно формализо-»ч ванный процесс, то для полностью автоматического вычисления параметров в данном классе задач простых алгоритмов не существует. Это приводит к необходимости привлекать проектировщика к процессу моделирования для построения наиболее эффективной 1ЧШ1В8-подгонки исходных точек. Проектировщик создает теоретическую поверхность с учетом всех ее топологических особенностей. Затем, в автоматическом режиме могут быть вычислены параметрические значения всех декартовых точек и построена интерполяция или

оптимальная 1Чи1Ш8-подгонка этих точек. При необходимости проектировщик может легко отредактировать полученную поверхность вручную. Надо отметить, что такой полуавтоматический способ построения поверхности судового корпуса дает достаточно хорошие результаты.

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

Поверхность судового корпуса, реконструированная ШЛШв-подгонкой точек теоретической поверхности с учетом имеющихся особенностей топологии, удовлетворяет самые высокие требования, предъявляемые к судовым поверхностям. Оптимальная МШШБ-подгонка является наиболее продуктивным подходом к реконструкции судовых поверхностей, поскольку позволяет получить гладкую поверхность, которая, при необходимости, может быть легко легко отредактирована проектировщиком вручную.

Рис.2 Буксирный теплоход.

В качестве примера на Рис. 2 представлены судовые поверхности буксирного теплохода заказ номер 376, сгенерированные с помощью разработанных подходов.

I 19

ЗАКЛЮЧЕНИЕ

I

1. RE (Reverse Engineering) - одна из наиболее динамично развивающихся дис-^ циплин современного автоматизированного проектирования, базирующаяся

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

2. Учитывая то, что сокращение сроков проектирования является жизненно

I

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

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

4. На базе созданного математического аппарата создан двухшаговый алгоритм, который может применяться для интерполяции или оптимальной подгонки обобщенными NURBS-поверхностями дискретного множества точек. Если для данного набора данных оптимальной подгонки не существует, алгоритм позволяет найти NURBS-подгонку с положительными весами, которая, как правило, намного лучше, чем В-сплайновая подгонка.

5. Представлена методика гладкой аппроксимации поверхности по набору поперечных сечений. С целью получения более компактного представления

f реконструируемой поверхности, представляется алгоритм удаления узлов из

^ общего узлового вектора.

6. Доказана применимость данного метода реконструкции поверхности и его ^ эффективность по сравнению с другими способами геометрического моделирования при построении гладких поверхностей судового корпуса по дискретному набору точек; при реконструкции формы поверхности геодезических объектов по результатам лазерного сканирования.

7. На базе созданных алгоритмов и компьютерных процедур разработаны специализированные системы КЗ-Ship (автоматизированное проектирование, геометрическое моделирование и модификация поверхностей и конструкций судового корпуса), КЗ, КЗ-Design (реконструкция и моделирование поверх-

ностей свободной формы с использованием NURBS). Системы являются законченными коммерческими программными продуктами, используемыми отечественными и зарубежными судостроительными (Польши, Норвегии и <

Нидерландов) и промышленными предприятиями. 8. Практическое использование алгоритмов при проектировании судов различ- ^

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

Публикации по теме диссертационной работы

1. Оноприйко, М.Д. Построение расчетных схем оболочек используя кусок Кунса./Оноприйко М.Д., Пантелеев В.Ю.//Материалы научной конференции молодых ученых мех.-мат. факультета и НИИ механики, Горький, 1988.

2. Оноприйко, М.Д. Геометрическое моделирование трехмерных конструкций в МКЭ./Оноприйко М.Д., Пантелеев В.Ю.//Материалы V Всесоюзной конференции по машинной графике "Машинная графика-89", Новосибирск, 1989.

3. Оноприйко, М.Д. Построение расчетных схем оболочек и массивных тел средствами подсистемы "Ввод"./Оноприйко М.Д., Пантелеев В.Ю.//Материалы I научно-технической конференции "Вопросы надежности и оптимизации строительных конструкций и машин", Севастополь, 1991.

4. Оноприйко, М.Д. Автоматизация процесса проектирования конструкций и анализа с помощью МКЭ./Оноприйко М.Д., Пантелеев В.Ю.//Материалы I научно-технической конференции "Вопросы надежности и оптимизации строи- « тельных конструкций и машин", Севастополь, 1992. *

5. Оноприйко, М.Д. Система компьютерной анимации результатов прочностных расчетов./Лабутин С.Е., Митин C.B., Оноприйко М.Д., Шубин • В.П.//Материалы Всероссийской конференции "КОГРАФ-95", Нижний Новгород, 1995.

6. Оноприйко, М.Д. Геометрические проблемы лазерной стереолитографии и подготовка данных для установки лазерной стереолитографии./Аристова Е.В., Митин C.B., Оноприйко М.Д., Шубин В.П., Евсеев A.B., Новиков

! 21

М.М.//Материалы II Всероссийского семинара "Лазерно-компьютерные техно-

« логии создания деталей сложной формы", НИЦТЛ РАН, Шатура, 1997.

^ 7. Оноприйко, М.Д. Геометрические проблемы лазерной стереолитогра-

фии./Аристова Е.В., Митин C.B., Оноприйко М.Д., Шубин В.П.//Материалы семинара-совещания заведующих кафедр "Начертательная геометрия, инже-^ нерная и компьютерная графика", НГАСА, Нижний Новгород, 1997.

' 8. Оноприйко, М.Д. Моделирование кривых сложной формы./Оноприйко М.Д.,

' Шубин В.П.//Материалы семинара-совещания заведующих кафедр "Начерта-

1 тельная геометрия, инженерная и компьютерная графика", НГАСА, Нижний

Новгород, 1997.

9. Оноприйко, М.Д. Геометрические проблемы лазерной стереолитографии и подготойка данных для установки лазерной стереолитографии./Аристова Е.В., Митин C.B., Оноприйко М.Д., Шубин В.П., Евсеев A.B., Новиков М.М.// "Оптическая техника", Вестник отделений и национальных комитетов SPIE, №1(13), 1998.

10. Оноприйко, М.Д. Моделирование поверхностей в системе трехмерного компьютерного моделирования "К3"./Оноприйко М.Д., Попов Е.В .//Материалы Международной конференции по компьютерной графике и визуализации "ГРАФИКОН-2001 ", Нижний Новгород, 2001.

11. Оноприйко, М.Д. Декомпозиция NURBS-кривых и поверхностей в представлении Безье./Оноприйко М.Д.//С6. тр. аспирантов и магистрантов. Техн. науки.-2002.

* О

к

*

i

<

ЛР№ 020823 от 21.09.98

Подписано к печати 15.09.2003г. Формат 60x90 1/16. Бумага писчая. Печать офсетная.

Объем 1 печ.л. Тираж 100 экз. Заказ № 18д

Нижегородский государственный архитектурно-строительный университет, 603950

Н.Новгород, Ильинская, 65

Полиграфцентр ННГАСУ, 603950, Н.Новгород, Ильинская,65

î

?

о

»

<

4

I

à

I

î

I

I

s

I i

I

í

t )

!

i

i

4 *

i

'J

! i

015 2 4 2

2ооН

Введение

Глава I ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ И РЕКОНСТ- 9 РУКЦИЯ ПОВЕРХНОСТЕЙ

1.1. Методы снятия оцифрованных данных с поверхности объекта

1.2. Обработка данных

1.3. Подгонка поверхности по облаку точек

1.3.1. Соотношение между компактностью, точностью и гладкостью

1.3.2. Способы представления поверхности

1.4. Краткий обзор существующих систем реконструкции поверхно- 23 стей объекта

Выводы

Глава II NURBS-ПРЕДСТАВЛЕНИЕ ПОВЕРХНОСТИ

2.1. Краткий исторический обзор

2.2. Математическое определение NURBS-поверхности

2.3. Аналитические и геометрические свойства

2.4. Однородные координаты

Выводы

Глава III ФОРМИРОВАНИЕ NURBS-ПРЕДСТАВЛЕНИЯ ПО- 42 ВЕРХНОСТЕЙ НА ОСНОВЕ ОЦИФРОВАННЫХ ДАННЫХ

3.1. Методы параметризации поверхностей

3.1.1. Методы параметризации регулярной сети данных

3.1.2. Параметризация облака точек с помощью базовой поверхности

3.2. Квадратичная подгонка поверхности

3.3. Двух шаговый алгоритм интерполяции и оптимальной подгонки 58 NURBS-поверхностью

3.3.1. Постановка задачи

3.3.2. Шаг 1: Идентификация NURBS весов управляющей сети по- 61 верхности

3.3.3. Шаг 2: Построение вершин управляющей сети реконструи- 66 руемой поверхности

3.4. Реконструкция поверхности по последовательности поперечных 67 сечений

3.4.1. Достижение совместимости сечений по степени

3.4.2. Достижение совместимости сечений по узловому вектору

Выводы

Глава IV ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ РАЗРАБО- 85 ТАННЫХ ПОДХОДОВ РЕКОНСТРУКЦИИ ПОВЕРХНОСТЕЙ

4.1. Реконструкция геодезической поверхности

4.2. Моделирование поверхности корабельного корпуса 90 * Выводы

Актуальность исследования

Современные достижения в области измерительной технологии, например, такие как лазерное сканирование, предоставляют возможность цифрового описания исследуемых объектов с достаточно высокой степенью точности. Это обстоятельство обусловило значительное повышение спроса на создание математических моделей, сгенерированных по данным, полученным в результате измерений, в таких областях как медицина, геология, археология, компьютерная графика и автоматизированное проектирование. При оцифровке поверхности бесконтактные сенсоры с высоким разрешением позволяют получить свыше 100000-500000 исходных точек. Представление той же поверхности параметрической математической моделью гораздо более экономичное, так как требует всего 50-500 параметров. Кроме того, параметрическое представление дает возможность простого редактирования формы поверхности путем изменения небольшого количества параметров, таких как управляющие точки, узловые вектора или весовые коэффициенты. Построение математического описания формы физических поверхностей является сравнительно новой областью исследования под названием реконструкция поверхности. Процесс преобразования дискретных оцифрованных точек в гладкую поверхностную модель представляет собой главную составляющую часть инженерного анализа - RE (Reverse Engineering). В области моделирования поверхностей за последние 30 лет создано множество методов, начиная от классических методов аналитической и дифференциальной геометрии, кончая современными методами сплайновой геометрии [72],[73],[126],[127]. Однако в инженерном анализе задача прямой генерации геометрической модели из дискретных оцифрованных точек по-прежнему не решена полностью, поскольку в процессе реконструкции поверхностной модели невозможно минимизировать численную ошибку, одновременно повысив гладкость поверхности [80],[89],[92].

Существует два основных подхода к реконструкции поверхности по облаку точек, представляющему модель объекта, - интерполяция и аппроксимация [99],[101],[106]. Интерполяционный тип подгонки поверхности использует каждую точку исходных данных в реконструируемой поверхности, тогда как при аппроксимации поверхности отыскивается наилучшая подгонка гладкой поверхностью к оцифрованным данным с минимальным отклонением. Для минимизации численной ошибки с одновременным повышением гладкости поверхности в процессе моделирования широко используется среднеквадратичная аппроксимация.

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

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

Объектом исследования является оптимальная реконструкция поверхности по облаку дискретных оцифрованных точек с использованием NURBS-аппроксимации и интерполяции. В геометрическом моделировании реконструкция поверхностей является эффективным инструментом для преобразования физических объектов в математическое представление для последующих исследований и компьютерной доработки. Использование для этих целей NURBS обусловлено тем, что они приводят к классу наиболее гибких дискретных методов интерполяции и аппроксимации.

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

В соответствии с целью исследования решались следующие задачи:

1. Обосновать возможность достижения положительной интерполяции и наилучшей положительной подгонки при построении поверхности по облаку дискретных точек.

2. Сформулировать двух шаговый алгоритм для поиска положительных NURBS весовых коэффициентов для подгонки поверхности по облаку дискретных точек.

3. Показать преимущества сформулированного двух шагового алгоритма при решении выделенного класса задач по сравнении с В-сплайновой подгонкой.

Научная новизна исследования состоит в следующем:

- Разработан математический аппарат для оптимальной реконструкции поверхности по облаку дискретных точек с использованием NURBS, обеспечивающий эффективное решение разнообразных задач, возникающих при моделировании поверхностей.

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

Практическая ценность исследования заключается в разработке специализированных алгоритмов и компьютерных процедур, реализующих возможности алгоритма реконструкции поверхности, для конструирования и сглаживания поверхностей судового корпуса, построенных по дискретному набору точек; восстановления формы поверхности геодезических объектов по результатам лазерного сканирования. На базе созданных алгоритмов и компьютерных процедур разработаны специализированные системы КЗ-Ship (автоматизированное проектирование, геометрическое моделирование и модификация поверхностей и конструкций судового корпуса), КЗ, КЗ-Design (реконструкция и моделирование поверхностей произвольной формы с использованием NURBS). Системы являются законченными коммерческими программными продуктами, используемыми отечественными и зарубежными судостроительными (Польши, Норвегии и Нидерландов) и промышленными предприятиями.

Апробация работы.

Материалы диссертационной работы представлялись на Международной конференция по компьютерной графике и визуализации "ГРАФИКОН-1994" (Нижний Новгород, 1994), ТРАФИКОН-2001" (Нижний Новгород, 2001), Всероссийской конференции КОГРАФ-95 (Нижний Новгород, 1995), КОГРАФ-96 (Нижний Новгород, 1996). Разработанное программное обеспечение демонстрировалось на Международных выставках "SoftTool-2000", "SoftTool-2001", "SoftTool-2002" и "НЕВА-2001".

На защиту выносятся следующие положения:

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

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

3. Созданный компьютерный инструментарий применительно к решению практических задач, возникающих при геометрическом моделировании. 0 Ф

ВЫВОДЫ.

1. Двухшаговый алгоритм оптимальной NURBS-подгонки является эффективным алгоритмом одинаково хорошо позволяющим реконструировать поверхности как по регулярной сетке данных, так и по дискретному набору произвольно расположенных точек.

2. Оптимальная ЖЖВБ-подгонка позволяет реконструировать геодезическую поверхность с минимальными отклонениями от заданных реперных точек, что позволяет создать качественную документацию для последующих строительных работ.

3. Реконструкция поверхности судового корпуса по набору дискретных точек является сложной проблемой, до настоящего времени не имеющая своего полного решения.

4. Подход, основанный на использовании В-сплайнов, имеет тенденцию давать переопределенную модель поверхности, которая содержит осцилляции, трудно удаляемые даже вручную.

5. Поверхность судового корпуса, реконструированная ГШИВБ-подгонкой точек теоретической поверхности с учетом имеющихся особенностей топологии, удовлетворяет самым высоким требованиям, предъявляемым к качеству судовых поверхностей.

6. Оптимальная МиИВЗ-подгонка является наиболее продуктивным подходом к реконструкции судовых поверхностей, поскольку позволяет получить гладкую поверхность, которая, при необходимости, может быть легко отредактирована проектировщиком вручную. Данный подход апробирован в процессе практических работ по заданиям отечественных и зарубежных заказчиков-судостроителей и может быть внедрен в практику проектирования судостроительных организаций.