Построение гладких параметрических CAD/CAM моделей деформированных деталей по сетке МКЭ-решения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Долгополик, Олег Дмитриевич

• Долгополик, Олег Дмитриевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Долгополик, Олег Дмитриевич

Оглавление

Введение

1 Анализ предшествующих работ

1.1 Обзор систем построения 30 моделей по реальным объектам

1.2 Обзор методов автоматической сегментации поверхности

1.3 Анализ полигональных поверхностей

1.3.1 Алгоритм расчета геометрических свойств дискретной поверхности

1.4 Обзор методов сглаживания, как кусочно-линейных кривых,

так и полигональных поверхностей

1.5 Введение в проблему реконструкции поверхностей

1.5.1 Связанные термины

1.5.2 Классификация

1.5.3 Методы построения неявно заданных поверхностей

1.5.4 Радиальные базисные функции. (РБФ)

1.5.5 Методы ноль множеств {Ъ{\))

1.5.6 Методики основанные на физических принципах и деформируемых моделях

1.5.7 Методы вычислительной геометрии

1.5.8 Параметрические и основанные на проецировании методы

1.5.9 Методы структурирования

1.5.10 Надежные методы

1.5.11 Обучающиеся методы

1.6 Отличия представленной задачи от существующих систем

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

2.0.1 Построение разделительных ребер на расчетной сетке

в деформированном состоянии

2.0.2 Выделение участков поверхности

2.0.3 Построение охватывающих поверхности контуров

3 Сглаживание и построение В-сплайновых граничных кривых деформированной расчетной сетки

3.1 Идентификация точек перегиба

3.2 Управление точками перегиба

3.3 Реализация алгоритма

3.4 Объединение двух сплайнов Безье

3.5 Объединение двух сплайнов Безье и В-сплайна

4 Сглаживание поверхностей

5 Реконструкция поверхностей и комплекс программ построения ЗБ модели по расчетной сетке

5.1 Реконструкция поверхностей

5.2 Требования к комплексу программ

5.3 Характеристика входных данных

5.4 Представление фасетной модели и выбор языка программирования

5.5 Сглаживание

5.6 Анализ участков поверхностей и распознавание их типов

5.7 Построение плоских, цилиндрических и линейчатых участков поверхности в Unigraphics

5.8 Построение участков поверхности произвольной формы

5.9 Результаты применения программы

6 ПРИЛОЖЕНИЕ

6.1 Module CompPointLinks

6.2 Модуль Buildeds

Литература

Введение диссертации (часть автореферата) на тему «Построение гладких параметрических CAD/CAM моделей деформированных деталей по сетке МКЭ-решения»

Введение

Объект исследования и актуальность темы. За последние несколько лет резко возрос объём проектно - конструкторских и проектно - технологических работ. Это связано прежде всего с тем, что отечественные предприятия смогли адаптироваться к современным условиям работы. Новый менеджмент предприятий увеличивает число заказчиков, а следовательно расширяется номенклатура выпускаемых изделий. При этом проходит очень большое число модификаций этих изделий, но в целом серийность, то есть количество одного выпускаемого изделия уменьшается. Одновременно с этим, резко сократилось число высококлассных станочников, технологов, проектировщиков оснастки, но появились молодые специалисты. У них нет накопленного опыта и знаний "старой гвардии", но они свободно работают с современными вычислительными средствами. Кроме того, более актуальными становятся проблемы увеличения производительности труда разработчиков новых изделий, сокращения сроков проектирования, повышения качества разработки проектов, решение которых определяет уровень научно-технического прогресса общества. Всё это является определяющим фактором для активного использования в современном производстве компьютерной техники и станков с ЧПУ, что в свою очередь увеличивает потребность в автоматизированных САЭ/САМ/САЕ системах. Также необходимо отметить, что произошло очень существенное сокращение времени, отводимого на подготовку производства. Это ещё один довод

в пользу CAD/CAM/CAE систем, так как разработка и отладка электронной модели изделия и управляющей программы в соответствии с созданной электронной моделью и технологией изготовления изделия являются одним из важнейших: этапов подготовки производства. Ещё больше перечисленные проблемы усугубляются при производстве деталей с пространственно - сложными поверхностями. Это связано с существенными ограничениями технологических решений, применяемых при изготовлении, которые в свою очередь вызваны функциональными возможностями существующего оборудования и инструментально - станочной базы. В качестве входной информации для этих систем выступает параметрическая гладкая модель геометрии детали, которую обычно создаёт конструктор. Однако к настоящему времени значительно расширился круг задач, в которых исходная модель оказывается неизвестной, но даны координаты множества точек поверхностей объекта (детали), либо реально уже существующего, либо полученного численным расчетом, например методом конечных элементов. Характерной особенностью этого множества является то, что его элементы (точки) заданы со значительным шумом (случайным искажением), который сопряжен, например, с погрешностями расчета или сканирования. Требуется так обработать данное множество, чтобы получить (восстановить) гладкую параметрическую модель геометрии объекта в пределах заданного допуска. Такой допуск, например, может быть равным заданной точности фрезерования. В следствии актуальности и важности для практики, сформулированная задача обработки данных множеств получила специальное название - задача обратного проектирования (в англоязычной литературе -Reverse Engineering (RE)). В общем случае до сих пор эта задача не имеет

решения. Известны работы, как отечественных авторов: Попов Е.В., Чмыхов Д.В., Конушин A.C., Беляев А.Г., Зорин Д., Фоменко А. Т. и других, так и зарубежных авторов: Taubin G., Chen Y., Desbrun M., Lavoue G. и других в которых описаны решения узкоспециализированных задач реконструкции поверхностей. Из-за постоянного, широкого и высокого спроса на решение задач RE на рынке появился ряд коммерческих программных пакетов построения пространственной (3D) геометрии объекта по множеству его точек сканирования. Однако опыт показывает, что их применение в случае деталей с пространственно - сложными поверхностями не приводит к решению, удовлетворяющему технологическим ограничениям, причина кроется в ошибках процесса сегментации, а без него, ключевого этапа реконструкции, результаты других этапов также дают неудовлетворительный результат.

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

СТП и ТУ

Программы идах обработки

Плита

Изготовление развертки панели

У2Р

Развертка —►

Формование панели У2Ф

•—► Панель -

Контроль параметроь

У2К

V 1 4 к *

Станок с ЧПУ Фориолок Оборудование Контрольный § стенд

Рис. 0.1. Схема процесса изготовления крыльевой панели

путем. В ряде случаев этот путь сопряжен с недопустимо большими материальными и временными затратами. Именно поэтому так актуальна замена старых методов проектирования оснастки для крупногабаритных деталей сложной пространственной формы, как крыльевые обшивки и панели. Схема изготовления таких панелей представлена на на Рис. 0.1). Поэтому современная организация труда и работы требует внедрения более точных и дешевых методов проектирования оснастки с использованием расчетных технологий CAD/CAM/CAE с целью выполнения этих итераций на компьютере, а не в металле на производстве. В работах Олейникова А.И. предложен и реализован итерационный алгоритм вычисления этих объектов. Предложенная ими схема представлена на Рис. 0.2.

Результатом численных расчетов являются сеточные (полигональные) 3D модели, модель заготовки (развертки) и модель конечного состояния деформирования панели, необходимая для проектирования штамповой оснастки. Эти модели необходимо передать в CAD/CAM систему, при этом упростив их, чтобы получить качественные поверхности после обработки заготовок на станках с ЧПУ с использованием уже имеющегося программного обеспечения и опыта его использования и для снижения времени

i I рое кти ро ван и е ос н астк н

Рис. 0.2. Модель автоматизированного процесса проектирования оснастки

обработки, что важно для серийного производства. В современных САМ (Unigraphics, Catia) системах используется гладкое, аналитическое, параметрическое (например, онлайновое) представление поверхностей заготовок в CAD системе. Таким образом, для более эффективного использования высокопроизводительного обрабатывающего оборудования необходимо преобразовать полигональную модель в аналитическую максимально рационально, где возможно, в пределах допуска и расчетной ошибки, построить плоские, цилиндрические и линейчатые поверхности. Как известно все эти поверхности относятся к классу разворачиваемых на плоскость без растяжений и разрывов. Обработка таких поверхностей может быть осуществлена более эффективно, поскольку формообразование таких поверхностей производится при контакте инструмента с заготовкой по линии или торцевой плоскости режущего инструмента, в то время как обработка поверх-

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

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

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

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

• сегментация триангулированной сетки поверхности объемного тела на подобласти (участки) однородной кривизны и выделение их дискретных граничных кривых;

• сглаживание граничных кривых и выделенных подобластей, определение их типов: плоских, цилиндрических и линейчатых и получение их гладких параметрических уравнений;

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

заготовки и оснастки с выделенными плоскими, цилиндрическими и линейчатыми участками;

• опытно промышленные испытания полученного комплекса программ.

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

Научная новизна:

• Разработан новый метод и алгоритм сегментации (выделения) деформированных поверхностей полигональных объемных моделей заготовок авиационных деталей путем нахождения соответствия с поверхностями исходной модели детали и методы их преобразования согласно типу поверхности: плоскость, цилиндр, линейчатая поверхность в параметрическое представление в системе иш£гарЫс5.

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

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

• Разработаны новые методы и алгоритмы выделения граничных кри-

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

Практическая значимость заключается:

• в реализации комплекса программного обеспечения для функционирования в составе интегрированной САО/САМ/САЕ-системы, который позволяет получить решение обратного проектирования по построению разверток крупногабаритных деталей типа крыльевых панелей для пассажирских самолетов и оснастки для их формовки по сетке МКЭ-решения;

• в применении модифицированной интегрированной САО/САМ/САЕ-системы для преобразования расчетных данных в эффективные для производства модели, что позволяет без преобразования передать эти модели для дальнейшего использования в производстве;

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

Положения, выносимые на защиту:

• Методы и алгоритмы анализа полигональных трехмерных моделей, сегментации (выделения) и распознавания типов участков поверхно-

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

• Методы и алгоритмы реконструкции поверхностей полигональных трехмерных моделей в аналитическое представление, основанные на полученных типах поверхностей.

• Комплекс программ, использующий имеющийся программный интерфейс и реализующий разработанные алгоритмы в системе 30-моделирования иг^гарЫсэ, позволяющий упростить разработку программ для станков с ЧПУ и уменьшить время обработки.

Обоснованность и достоверность результатов была проверена опытным путем в производстве, для чего с использованием разработанного комплекса программ по результатам моделирования процессов штамповки были спроектированы развертка и штамповая оснастка панели консоли крыла пассажирского самолета. По спроектированным 30 моделям была изготовлена оснастка и выполнено формование панели. Результатом стало то, что более 50% контрольных точек лежали в допуске на изготовление с первого предъявления, а остальные участки потребовали незначительной ручной доводки. В то же время, применяемые на производстве методы потребовали пятикратной модернизации моделей развертки и соответственно программ механообработки и штамповой оснастки. Таким образом, применение расчетных методов проектирования оснастки и соответственно разработанного программного комплекса на практике показало как работоспособность, так и эффективность расчетного метода и разработанного программного комплекса.

Основное содержание диссертации опубликовано в работах:

1. Олейников А.И., Долгополик ОД. Сглаживание и построение В-сплайновых граничных кривых деформированной расчетной сетки. //Информатика и системы управления. - 2011. - N-2. -С. 133-139.*

2. Лекарш А.И., Олейников А.И., Бакаев В.В., Долгополик ОД., Сары-ков С.Э. Подготовка производства сложных деталей двойной знакопеременной. кривизны методом конечно-элементного анализа геометрической модели с комплексной разработкой формообразующей оснастки, развертки детали и рекомендаций по технологическому процессу. //САПР и График. - 2009. - №-2. - С.88-96.*

3. Guzev M., Oleinikov A., Bormotin К., Dolgopolik Multithreaded Integrated Design of Airframe Panel Manufacture Processes. //Methods and Tools of Parallel Programming Multicomputers, Revised selected papers of the 2nd Russia-Taiwan Sypposium,MTPPM-2010, Vladivostok, Russia, May 2010, LNCS 6083, Spring-Verlag, Berlin Heidelberg, 2010. C.283-292.

4. Долгополик О. Д., Марьин Б. H,, Фролов Д. Н. Методика автоматизированного определения положения листовой заготовки сложной криволинейной формы в штампе с использованием CAD систе-мы//Сборка в машиностроении и приборостроении. - 2006. - N4. -С. 120-126.*

5. Олейников А.И., Бормотин К. С., Долгополик О. Д., Пекарил А.И. Интегрированная компьютерная система моделирования и проектирования процессов формовки крупноразмерных деталей //Труды 5й Московской Международной Конференции ТПКММ. - 2007. -С. 245-

6. Олейников А.И., Бормотин К.С., Долгополик ОД. Интегрированная многопоточная система проектирования процессов изготовления панелей планера самолета //Параллельные вычислительные технологии (ПаВТ2008): Труды международной научной конференции (Санкт-Петербург, 28 января - 1 февраля 2008 г.). - Челябинск: Изд. ЮУр-ГУ, 2008. - С. 199-206.

7. Олейников А.И., Коробейников С.Н., Бормотин К.С, Долгополик О.Д., Пекарш А.И. Интегрированное проектирование и моделирование процессов формообразования крыльевых пане-лей//Прикладные задачи механики деформируемого твердого тела и прогрессивные технологии в машиностроении: сб.ст., Вып.3.-Ч.1., Комсомольск-на-Амуре,2009. -С. 190-252.

8. Долгополик О.Д., Бакаев В.В., Олейников А.И., Пекарш А.И. Программно-вычислительный комплекс для расчета 3D разверток штамповой оснастки и техпараметров формообразования панелей //Свидетельство о регистрации программы для ЭВМ Ае2009612260. М.: Роспатент, 2011

* - Статьи в ведущих рецензируемых научных журналах, рекомендованных Высшей аттестационной комиссией РФ.

1. Анализ предшествующих работ

1.1. Обзор систем построения 3D моделей по реальным объектам

Уже свыше 25 лет ведутся работы по созданию и совершенствованию технологии и систем создание цифровых моделей по реальным объектам. Эта область Reverse Engineering или обратного проектирования. Технология обратного проектирования находит все более и более разнообразное применение. Исследования в таких областях как обработка образов, компьютерная графика, автоматизация производства и виртуальная реальность встречаются с задачами обратного проектирования при создании компьютерного представления реального образца. В инженерных применениях полная реконструкция формы детали необходима для создания оригинального объекта, при отклонении от измеренных точек на величину меньшую заданного допуска. В производстве обратное проектирование нашло применение для таких задач, как:

• контроль геометрии изготовленной детали;

• контроль износа инструмента и штампов и их восстановление;

• восстановление CAD модели по детали;

• создание чертежей построенных изделий и систем "с реальными размерами".

Традиционно обратное проектирование выполняется в три стадии:

\||) 1С II.

Рис. 1.1. Этапы реконструкции модели

• сбор данных об изделии;

• реконструкция поверхностей;

• создание модели изделия;

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

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

1.2. Обзор методов автоматической сегментации поверхности

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

применения ищут способы автоматизированной трансформации реального объекта в трехмерную модель. Наибольшего прогресса достигли два продукта Paraform и Geomagic Studio. Имеется еще несколько систем, такие как Spider (Wavefront), Polywork, Rhino, RE2 (Dasault) для CATIA и другие. Все эти продукты имеют общую функциональность: импорт сканированных данных, их очистка, построение полигональной модели, построение сечений, сегментация поверхности на участки и построение CAD модели. Многие из них распознают плоские, сферические и цилиндрические поверхности. Распознавание линейчатых поверхностей не упоминается ни у одного из продуктов. Кроме того, алгоритмы распознавания не раскрываются. Системы эти дорогие до 70 тыс. долларов и предназначены в первую очередь для задач обработки сканированных данных и создания CAD модели, однако вопрос оптимизации этой модели для программирования ме-хобработки в этих системах не рассматривается.

1.3. Анализ полигональных поверхностей

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

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

Оценка кривизны еще остается активной областью исследования со многими применениями. Одно направление исследования - это оценить кривизну основываясь на полиномиальной интерполяции сетки. Многие другие подходы используют более или менее специфическое описание тензора кривизны из дифференциальной геометрии и стараются найти подходящую дискретизацию. В этих случаях, корректная дискретизация полного интеграла малым количеством значений в направлении ребер исходящих из центральной вершины представляет отдельную проблему. Таубин предложил веса площадей (треугольников, которым принадлежат соответствующие ребра), Ватанабе и Беляев используют угловые веса, которые дает трапецеидальная аппроксимация интеграла. Аналогично, Мейер и др. вычисляют среднюю кривизну, используя "котангенсные" веса. Как и ожидалось, ни один из этих весовых коэффициентов не дает точного результата, даже если длины ребер стремятся к нулю. Таким образом, вводятся систематические ошибки.

Следовательно, не все аппроксимации тензора кривизны асимптотиче-

ски корректны. Несмотря на это Кохен-Стейнер и Морван доказали сходимость их подхода, основанного на циклах нормалей для случая ограниченной триангуляции Делоне. Мик и Ваултон доказали точечную сходимость нескольких схем для оценки вектора нормали и Гауссовой кривизны. Они показали, что вектор нормали, вычисляемый как средняя величина нормалей соприкасающихся треугольников, сходится линейно, если используются в качестве весовых коэффициентов площади треугольников. Беляевым и др. был предложены весовые коэффициенты, позволяющие получить точные квадратуры для интегралов средней кривизны, Гауссовой кривизны и тензора Таубина и предложены методы как эти веса могут быть оценены, чтобы достичь быстрого и надежного вычисления тензора кривизны гладкой поверхности аппроксимированной плотной триангулированной сеткой. Этот метод асимптотически корректен и легко реализуем.

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

к{ф) = ктах cos2 ф + ктт sin2 ф (1.1)

Где ктах И kmin максимальная и минимальная главные кривизны, соответственно к{ф) нормальная кривизна соответствующая направлению касательной t(ф), и ф угол между Ь(ф) и направлением максимальной кривизны в касательной плоскости. Два других уравнения это интегралы для вычисления средней и Гауссовой кривизны:

1 Г2ж

Н = — к(ф)(1ф (1.2)

J о

Рис. 1.3. Весовые коэффициенты и область диаграммы Вороного

1 Г2ж

к = ЗЯ2 - - / к2{ф)с1ф (1.3)

1.3.1. Алгоритм расчета геометрических свойств дискретной поверхности

Пусть Р будет центральной вершиной кольца первого уровня на сетке, которая интерполирует гладкую поверхность и пусть п будет единичный вектор нормали в точке Р. Пусть Qi вершины этого кольца первого уровня и пусть а^ := Р0г соединяющее ребро длиной а* Рис 1.2.

Угол между гц и обозначим как а* и будем использовать как аппроксимацию соответствующего угла на касательной плоскости см. Рис 1.3 справа. В тоже время к{ := 2(%,п) будет обозначать обычную

г

аппроксимацию локмальной кривизны кг в направлении ец. Будем задавать среднюю кривизну как квадратуру Х^^г интеграла средней кривизны (1.2) с добавлением весов:

+ А

н = У

о J

На практике это ведет к следующей дискретной аппроксимации Н:

Чтобы вычислить Гаусову кривизну К мы вычислим интерграл из уравнения (1.3) С = ^ к(ф)аф похожим способом

Отсюда Гауссова кривизна вычисляется из средней кривизны Я и скорректированной весами суммы нормальных кривизн, где веса вычисляются по формуле (2.4).

К — ЗЯ2 — 2Х^А2 + 4Я(][>А - я)-

г г

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

Описанный алгоритм был реализован автором в комплексе программ.

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

Как при сканировании поверхностей, так и при применении расчетных методов было выявлено значительное колебание точек в пределе до 0,5 миллиметра, что превышает размеры отдельных элементов обшивок.Эти колебания вызваны погрешностями сканирования и накоплением расчетных погрешностей при неоднократных итерациях. Чтобы снизить влияние этих ошибок на построение аппроксимируемых поверхностей применяют сглаживание.

Было предложено много методов сглаживания поверхностей и методов удаления шумов. Часто различные цели методов смешивались, алгоритмы сглаживания предлагались для удаления шумов. Классическое Ла-пласианово сглаживание [51, 140] является наипростейшим и наиболее быстрым методом сглаживания поверхностей. Однако при применении к зашумленным ЗЭ поверхностям, удаление шумов сопровождается искажениями поверхности и стягиванием. Чтобы преодолеть проблему стягивания поверхности Таубин [127] предложил метод фильтрации с положительными и отрицательными факторами демпфирования. Фильтр первого порядка с положительным фактором демпфирования стягивает и сглаживает полигональную поверхность, в тоже время фильтр первого порядка с отрицательным демпфирующим фактором растягивает поверхность, чтобы компенсировать стягивание. Этот метод быстрый и простой, но ему все еще присущи искажения выпуклых элементов поверхности. Вдобавок, если параметры двух фильтров не тщательно подобраны, алгоритм может быть нестабильным. Десбрун и др. [38] ввели диффузионный поток и поток

кривизны в сглаживание поверхности, предлагая простой и стабильный неявный метод фильтрации, который работает на нерегулярных сетках. Они преодолевают проблему стягивания масштабированием сетки, чтобы сохранить её объем. Однако искажения выпуклых элементов поверхности остаются. Пенг и другие в [104] применили к сеткам локальную адаптивную фильтрацию Винера.

С точки зрения обработки сигнала методы Таубина [127] и Десбру-на и др. [38] можно рассматривать как методы фильтрации. Первый может рассматриваться как метод фильтрации скользящей средней (MA) или фильтрации конечной импульсной характеристики (FIR), в тоже время второй метод можно считать авторегрессивным методом фильтрации или фильтрации бесконечной импульсной характеристики(1Ш). Объединив оба вышеприведенных метода, Ким и Россиньяк [78] разработали метод фильтрации - авторегрессивный со скользящей средней. При подборе соответствующих параметров фильтр может действовать, как низкочастотный, высокочастотный или двухдиапазонный фильтр, усиления или ослабления полос частот, таким образом позволяя фильтровать, например высокочастотный шум и в тоже время усиливая или подавляя определенные свойства. Однако сложно сконструировать подходящий фильтр, выполняющий обе задачи одинаково хорошо. Выше приведенные методы фильтрации являются изотропными, однородными, т.е. фильтр действует независимо от направления. Это не позволяет сохранить на сетке элементы с резким изменением свойств, например ребра стыковки различных участков поверхности под углом, наличие которых характерно для CAD моделей. Поэтому были разработаны различные анизотропные схемы фильтрации, сглажи-

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

Первый класс основан на анизотропной геометрической диффузии [28, 39, 125, 12, 69]. Такие методы использовались для сглаживания полей высот и двумерных данных [39], множества поверхностей уровня [125], общих дискретизированных поверхностей [28, 12, 69]. Второй класс основан на двунаправленных фильтрах [77, 53]. Флейшман и др. в [53] используют итеративный одно шаговый подход, в котором новые координаты вершин рассчитываются по координатам соседей. Этот подход достаточно быстрый, поскольку одно шаговые вычисления используются для каждой итерации изменения вершин. Однако эксперименты показали, что метод не всегда точно сохраняет мелкие элементы на сетке. Подход, предложенный Джонсом и др. в [77] сглаживание на основе грубой оценки является не итеративным двух шаговым. Хотя метод не итеративный, он достаточно медленный, поскольку он рассматривает сглаживание нормалей и изменение координат вершин как глобальную проблему. Третий класс основан на объединении фильтрации нормалей изменении позиций вершин [101, 129, 142, 143, 115, 25]. Метод предложенный в [101] является нелинейным диффузионным методом, в [142, 143] предложены методы сглаживания по средней, медиане и альфа обрезке, в [25] метод зависящий от остроты ребер является перемежающимся итеративным двух шаговым. В [145] представлен метод сглаживания на примере.

Рис. 1.4. Схема потока данных Геометрического Моделирования

1.5. Введение в проблему реконструкции поверхностей

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

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

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

точек была впервые поставлена Хоупом и другими в [74, 72]. Множество точек рассматривается как неупорядоченное или неструктурированное, когда оно не содержит иной информации кроме координат точек. Структурированное множество можно рассматривать как не упорядоченное, если игнорировать дополнительную информацию. Много усилий было приложено в этом направлении. К настоящему времени множество методов было предложено, часто внушенных идеями из физики и математики или использующие их. До сих пор эта область продолжает оставаться широко исследуемой темой, в которой ученые и практики продолжают постоянно совершенствовать существующие методы и предлагать новые.

Одна из причин, почему так много усилий было положено на проблему реконструкции поверхностей это та, что как упоминалась ранее, проблема возникает во множестве дисциплин. Литература по теме объемная и приходит из разных областей деятельности человека, таких как компьютерное зрение, обработка медицинских образов, вычислительная геометрия, визуализация научных результатов, моделирование поверхностей и конечно компьютерная графика. Фанке и другие сделали интересное наблюдение в [59], где показали, что результат проблемы реконструкции поверхностей это обычно структура порядка 0(п), в то же время, для большинства методов требуются гораздо большие усилия. Они теоретизируют неформально, что должен быть алгоритм пропорциональный по стоимости для решения проблемы. Возможно, поиск этого оптимального решения и движет исследователями. Недавно интерес к реконструкции поверхностей возрос благодаря проекту "Цифровой Микеланджело'в котором доступны огромные массивы данных порядка миллионов или миллиардов точек.

Методы для реконструкции поверхностей из облака точек Р многочисленны и могут быть классифицированы различными способами. С первого взгляда, полигональные техники реконструируют поверхности как полигональные сетки, в то же время неявные методы дают неявное, функциональное представление объекта. Неструктурированные методы реконструируют поверхность из точек заданных только их координатами. Такие наборы точек называются неупорядоченными. Структурированные методы используют дополнительную информацию представленную с множеством точек. Интерполяционные схемы выдают поверхность, которая проходит через входные точки. Тесно связанными с интерполяционными схемами являются схемы прямой триангуляции, которые триангулируют входные точки. Аппроксимационные методы используют множество Р, чтобы сгенерировать поверхность, которая может не проходить через некоторые или все точки. Объемные техники сначала строят некоторое объемное представление Р и затем выделяют поверхность из него, обычно использую один из вариантов алгоритма подгонки кубиков [88]. Параметрические методы реконструируют поверхность как Зх мерную функцию заданную на 2х мерной области параметров. Методы, основанные на физических принципах, начинают с деформированной модели, которая изменяется под действием процесса минимизации некоей энергии до тех пор, пока она не станет удовлетворять точкам множества Р. Узлы, обычно добавляются в модель шагами разделения. Большинство из выше приведенных методов предполагают незначительный шум или его отсутствие в Р. В то время как другие могут естественно справиться с некоторым шумом, качественные методы придуманы специально для данных с шумом и

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

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

1.5.1. Связанные термины.

Имеется множество терминов касающихся темы реконструкции поверхности. Однако входными данными любого метода реконструкции поверхности является множество точек, а результатом является представление поверхности. Имеются также методы представления не только полых форм, но и их внутренних объемов, такие методы называются твердотельным моделированием. Эти методы находят применение в машиностроении и медицине. В этом контексте, методы реконструкции поверхностей называются еще моделированием форм, реконструкцией форм, подгонка поверхностей, построение сетки на поверхности. Схемы твердотельного моделирования также называют схемами 30 реконструкции. В этом контексте, методы моделирования форм можно расположить посредине между 20 и 30 и называть методами реконструкции 2,50. 2,50 относится к 20 поверхностям, встроенным в 30 или в ограниченном случае как данным по высотам. Данная терминология относится к области реконструкции местности по данным, полученным с авиационного высотомера.

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

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

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

1.5.2. Классификация.

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

1.5.3. Методы построения неявно заданных поверхностей

Эти методы являются расширением идеи Блина [18] скругления локальных неявнозаданных примитивов. В отличие от методов реконструкции кусочно-линейных представлений Р [50, 103, 137], они обычно подбирают функцию для всех точек. Таким образом, они, по сути своей, интерполирующие. По желанию, функция может быть аппроксимирована, чтобы построить кусочно-линейную (полигональную) аппроксимацию [3, 88]. Часто, различие между разнообразными неявными методами это выбор функции для представления поверхности. Кришнамурти и Левой [82] рассчитывают детальные векторы смещения и подбирают В-сплайн поверхности к данным. Моор и другие в [94] подбирают рекурсивно кусочные полиномиалы и затем сглаживают их соединение с помощью произвольного скругления. В [86], объединение сфер скругляется, чтобы построить поверхность. Сферы первоначально строятся с использованием соединения точек Р четырехугольниками методом Делоне [36]. Отаке и другие [100] используют весовые кусочно-квадратичную функции для многоуровневой локальной аппроксимации. Квадратичные функции также используются в [32]. Баджай и другие [10] используют модифицированную форму заплаток Безье-Берштейна. Р моделируется с использованием сплайнов в [11, 33, 65, 66].

Некоторые методы неявных функций [2, 11, 10, 32, 33, 55, 65, 66, 98] имеют недостаток, они требуют на входе триангулированную поверхность, для того чтобы подогнать гладкие заплатки неявно-заданных поверхностей, в тоже время другие [10, 95] не требуют. Однако, такие методы строят промежуточное полигональное представление сами. Хопп и другие в их

работе из трех этапов [74, 75, 73] также стоят полигональную модель для того чтобы получить гладкое представление поверхности Р.

1.5.4. Радиальные базисные функции. (РБФ).

Много работ по реконструкции поверхностей с использованием неявных функций было сделано на основе радиальных базисных функций. Ранние методики [22, 133, 134] не могли воспользоваться РБФ из-за высоких требований к вычислительным ресурсам [45, 54, 118]. Янгл и Тёрк [144] предложили работать с уменьшенным набором точек, но упрощение вступает в противоречие с возможностью представлять сложные объекты произвольной топологии без потери деталей. В [23], Kapp и другие сделали модификации в потребные вычисления, чтобы получить очень быстрый алгоритм, который интерполирует заданные точки использую полигармонические РБФ. Недавние работы по использованию РБФ это [43, 81, 96, 102]. Классикой реконструкции поверхностей неявными функциями являются работы [23, 44, 135].

1.5.5. Методы ноль множеств (Z(f)).

Отдельный класс методик применения неявных функций старается аппроксимировать данные "наиболее подходящей" функцией. Выбирается та функция, чье ноль множество Z{f) ближе к заданным точкам. [107, 126] минимизируют сумму квадратов расстояний Хаусдорфа от заданных точек до Z(f) где / это многочлен трех переменных. Мураки [97] взял в качестве / линейную комбинацию Зх Гауссовых корней. Помимо близости / к 0 на заданных точках его оценка подходящей функции из-

меряет и то, насколько хорошо единичные нормали Z(f) соответствуют нормалям получаемым из входных данных. В [74, 75, 73], Хопп и другие описывают процедуру из трех стадий, чтобы извлечь гладкое функциональное представление из Р. Сначала они генерируют триангулированную сетку из Р. Первый шаг состоит в назначении касательных плоскостей каждой точке, используя информацию о соседних точках. Эти плоскости помогают определить функцию знаковой дистанции, /, которая равна нулю для точек на поверхности, положительна для точек вне её и отрицательна для точек внутри её. Затем используется алгоритм подобранных кубиков [3], чтобы извлечь полигональное представление Полученная сетка

оптимизирована по количеству треугольников и расстоянию от Р. Гладкая поверхность затем конструируется из сетки. Курлис и Левой [30, 31] используют похожий подход в том, что они используют знаковые функции расстояния от касательных плоскостей. Баджай и другие [10] используют а-формы [46, 47], чтобы построить функцию /, в то же время Боисонат и Казалс используют интерполяцию, построенную на естественных соседях, которых легко найти с помощью диаграммы Вороного множества от Р [116, 117, 141]. Бернарди и другие в [15] и Фоменко и Куньи в [56] представили дополнительные Z(f) методы.

1.5.6. Методики основанные на физических принципах и деформируемых моделях.

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

метод для подгонки деформируемой сферы к множеству точек используя деформации суперквадрики. Кобелт и другие в [79] моделируют оборачивание пластичной мембраны вокруг объекта. Лиао и Медиони используют модифицированную версию двухмерных сплайнов, которые они назвали "В-змейки". Они многократно подгоняют В-змейки к Р и делают соответствующие изменения в начальную модель так чтобы модифицировать её среднюю ось. Методы основанные на физических принципах описывают виды энергии, чья минимизация контролирует рост начальной модели. Различные типы энергии измеряют близость модели множеству Р, гладкость модели и другие атрибуты. Хопп и другие в [76] деформируют начальную сетку при таких условиях. В [105, 131] вводятся концепции змеек и активных поверхностей в этом смысле. Чен и Медиони в [26] инициализируют их сетку в виде воздушного шара, который полностью содержится в Р. Затем они "накачивают'шар пока он не будет соответствовать Р. В [114] используются различные вариационные принципы, чтобы деформировать при определенных энергетических условиях мембрану охватывающую Р. Зао и Ошер в [148] представили другой подход с другими вариационными условиями.

Чейн в [24] использует термин "поток введенный в Компьютерную Графику в [106, 61], и преобразует физическую конвективную схему представленную Зао и другими [149] в геометрический алгоритм, основанный на трехмерной триангуляции Делоне множества Р. Он выделяет замкнутую и ориентированную поверхность в трехмерной триангуляции Р и трансформирует её, используя физическую конвекционную схему. Таубин в [128] предложил подход, основанный на теории сигналов, к проблеме

реконструкции поверхности.

1.5.7. Методы вычислительной геометрии.

Методы, описанные ранее, можно классифицировать как методы компьютерной графики для реконструкции поверхностей. Их суть - это построение модели, достаточно близкой к заданным точкам. Алгоритмы тестировались эмпирически - они проверялись на облаках точек для известных поверхностей и результат сравнивался с исходной поверхностью. Методами вычислительной геометрии стремятся не только получить эмпирические обоснования алгоритмов, но и обосновать их теоретически или найти гарантии их работоспособности. В [92] приводиться хорошая классификация методов реконструкции поверхностей как основанных на подходах компьютерной графики, так и на подходах вычислительной геометрии. Методы вычислительной геометрии являются комбинаторными по природе -они генерируют триангуляцию точек, обычно триангуляцию Делоне и выводят несколько сгенерированных поверхностей. Одна из первых работ по реконструкции поверхностей в этой области, это работа Эдельсбрунера и других [46] на а- областях. Это параметризированные конструкции диаграмм Вороного и триангуляции Делоне, которые связывают полигональные поверхности с неорганизованным облаком точек. Симплекс (ребро, треугольник, тетраэдр) включается в а-область, если его описанная сфера радиуса не больше а не включает других заданных точек. Спектр а-областей, множество а-областей для всех а, дает представление о форме поверхности облака точек, а-области широко используются для реконструкции поверхностей [16, 130]. Баджай и другие в [10] используют а-области чтобы по-

лучить промежуточное объемное представление Р. Саккалис и Чаритос в [111] и Мелкеми в [90] используют а-области для реконструкции кривых. Другая ранняя работа это работа Боиссоната [20]. Его алгоритм лепки на базе алгоритма Делоне последовательно исключает тетраэдры из Делоне тетраидизации Р на основе их описывающих сфер. Использование триангуляции Делоне и его двойственного представления диаграммы Вороного для реконструкции поверхностей получило повсеместное распространение. Для двухмерного случая в [6, 9, 14, 35, 62] приводятся теоретические обоснования реконструкции гладких кривых, основанной на двухмерной триангуляции Делоне, а в [4, 41, 42, 60] обосновывается тоже самое для методов реконструкции кривых, основанных на технике решения задачи коммивояжера и других идеях из вычислительной геометрии. Амента и другие в [5, 7] были первыми, кто дал теоретические гарантии для их алгоритма "Crust (Корка)"для трехмерного случая. Их алгоритм похож на алгоритм Делоне лепки Боиссоната и метод Мелкеми [90] для 2D. Они используют диаграмму Вороного точек Р, чтобы выделить среднюю ось М. Ребра в Делоне триангуляции М U Р которые соединяют точки из Р включаются в корку. Для трехмерного случая, они выбирают две вершины диаграммы Вороного для каждой точки Р , чтобы аппроксимировать М. Они доказали, что при условии достаточно большого количества исходных точек их реконструкция близка к оригинальной поверхности. В работе [8] Амента и другие представили алгоритм под названием "Соконус который упрощает и доказательство и алгоритм "Crust (Корка)". Они доказали, что при определенных начальных условиях их реконструкция гомеоморфна исходной поверхности.

Дей и другие в [40] привели более быструю реализацию алгоритма "Соконуса'и при более слабых ограничениях, а Фанке и другие в [59] еще больше ослабили ограничения.

В противовес методу Аменты и её коллег, Боиссоната и Казалс представили алгоритм без ограничений к исходным данным. Они в [116, 117, 141] компенсируют нехватку исходных данных использованием диаграммы Вороного точек Р, чтобы сгенерировать естественное соседство, через которое они и стоят гладкую поверхность. Однако для их алгоритма потребна информация о нормалях.

Затем Амента и её коллеги усовершенствовали их алгоритм и назвали его "Powercrust-Крепкая корка где они используют диаграмму Вороного точек Р , чтобы реконструировать поверхность как объединение конечного числа шаров. Алгоритм похож по технике на алгоритм реконструкции кривых предложенный Саккалисом и Чаритосом в [111]. Обе эти методики обеспечивают топологические гарантии при удовлетворении заданных точек определенным условиям.

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

1.5.8. Параметрические и основанные на проецировании методы.

Параметрические методики представляют поверхность как функцию двух параметров. Область определения обычно плоскость [67, 139, 138]

или сфера [21, 112].

Проекционные методы преобразуют поверхность, которую нужно реконструировать локально к графику функции или плоскости. Они назначают плоскость каждой группе соседних точек и триангулируют точки Р, проецируя соседние точки на плоскость. В [1, 52, 99] представлено несколько таких методик. Левин в [84] триангулирует оценочную функцию используя: аппроксимации методом наименьших квадратов.

1.5.9. Методы структурирования.

Распространение относительно дешевых и высокоточных оптических сканеров и их последующее широкое распространение потребовало разработки специализированных алгоритмов для обработки данных представленных отдельными диапазонами. Среди таких методов выделяются методики предложенные Курлисом и Левойем в [30, 31] и Тёрком и Левойем [132]. Курлис и Левой используют данные по диапазонам, чтобы получить оценку ошибки и информацию по касательной плоскости способом, похожим на метод предложенный Хоппом и другими в [74, 72]. Они используют эту информацию, чтобы представить полную поверхность как одну непрерывную функцию, которую они рассчитывают локально на сетке вокселей (объемных элементов). Поскольку они применяют локальные вычисления их метод очень быстр и может обрабатывать большие объемы данных. Они делают последовательные шаги по заполнение разрывов в данных, в которых используют специфическую информацию. Так как метод использует одну функцию, чтобы представить всю поверхность, он может быть представлен как неявный или объемный. Метод Хилтона и других [70] похож

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

В [132], Тёрк и Левой предложили инкрементальный алгоритм, который объединяет сканированные данные, сначала удаляя излишние данные о геометрии и затем сшивает области вдоль границ. В конце они выполняют шаг "выравнивания", восстанавливая оригинальную геометрию, чтобы получить окончательные позиции вершин.

Первые методики, включая методику Соуси и Лаурендеу [119], использовали диаграммы Венна, чтобы обнаружить перекрытие сканированных областей, затем выполнялась репараметризация и объединение областей. Ратишаузер и другие в работе [ПО] используют ошибки вдоль линий чувствительности сенсора, чтобы обеспечить выравнивание поверхности, затем выполнялась новая разбивка, которая встраивала дополнительные данные. Пали и другие в [108] построили иерархическое объемное представление Р используя октодерево [121]. Гроссо и другие [64] генерировали карты глубины со стерео данных и усредняли по плотности распределения точек по объему дискретно её изменяя вдоль изменяющихся уклонов поверхности. Саси и другие [122] также создают карты глубин по стерео или оптических данным и объединяют их по объему используя прямое усреднение распределения точек по вокселям. Реконструированная поверхность - это изоповерхность, выделяемая по произвольно заданному порогу.

Другие методики структурирования полагаются на назначение значений сетке вокселей. Значения могут быть бинарными, третичными или могут следовать вероятности распределения. Конноли [29] испускают лучи из области сканированных данных представленных в виде квадраде-

лi РОССИЙСКАЯ

ГОСУДАРСТВЕННАЯ БИБЛИОТЕКА

рева в воксельную сетку представленную как октодерево. В [27] Чейн и другие генерируют модели октадеревьев при условии, что линии визирования направлены по шести сторонам куба. В [85, 124] описывается методы для генерирования бинарных воксельных сеток из сканированных данных. Элснер и другие в [49] пропускают лучи через сканированные данные в объемную сетку и назначают значения вероятности элементам сетки.

1.5.10. Надежные методы.

Часто при обработке сканированных данных методы, описанные выше хорошо работают на данных содержащих только отклонения по Гауссово-му распределению шума. Например, методы наименьших квадратов [107] дают оптимальные результаты для данных такого типа. Однако любые выбросы в данных, такие, что данные не соответствуют Гауссовому распределению, приводят к ошибочным результатам. Методики, которые дают хорошие результаты в присутствии выбросов называются надежными.

Имеется два основных типа выбросов данных, требующие рассмотрения. Во-первых, неструктурированные выбросы, вызванные ошибками измерения в устройстве. Во-вторых, структурированные выбросы, это точки на поверхности, не принадлежащие поверхности, которую нужно аппроксимировать. Мир и другие в [89] дают обзор различных надежных методов восстановления. Их "оценщики'применяют функцию к отклонениям, сумма которых является минимальной, min f(r). В случае метода наименьших квадратов /(г) — г2. Другие функции ищут, чтобы минимизировать эффект больших отклонений. Детали других функций представлены Зангом в [147].

Отношение числа выбросов к общему числу точек, которые оценочная функция может распознать до того как натягивать поверхность называется моментом разрыва. Оценка по метод наименьших квадратов имеет момент разрыва около 0%, a LMedS [109] имеет момент разрыва около 50%. Некоторые другие авторы описывают методы для достижения более 50%, но с дополнительными вычислительными расходами.

Наименьшая средняя квадратов (Least median of squares (LMedS)) метод неоднократно выбирает случайным образом экземпляры данных и натягивает на них поверхность. Выбор дающий наименьшую среднюю отклонений выбирается как наилучший и выводится. Стюарт в [120] описывает алгоритм MINPRAN, который похож на LMedS, но использует другую критериальную функцию. В [83] используется вариация оценочной функции метода LMedS, чтобы подобрать плоскую поверхность к сканированным данным. Вместо среднего отклонения они используют К-е отклонение. Они также получают момент разрыва превышающий 50%. Подбор осуществляется через значения К. Выбор с наименьшей ошибкой принимается как лучший выбор.

1.5.11. Обучающиеся методы.

Новая перспектива в реконструкции поверхности увидеть, что это проблема обучения. Методы основываются на подходе предполагающем, что вся необходимая информация о моделируемой форме содержится в данных. Реконструкция затем сводится к вопросу просто обучения по этой информации. Тема статистического обучения описана в деталях в [68].

Принятие подхода на обучение открывает дверь к автоматизирован-

ным методам обучения, более специфические искусственные нейронные сети. Детальное описание использования нейронных сетей в форме обучения может быть найдено в [17]. В [80], Кохонен ввел самоорганизующиеся карты (СОК) тип нейронной сети. Основываясь на СОК Фризке ввел растущие клеточные структуры (РКС) в [57]. Они представлены в деталях в [19]. В то время как СОК сети обычно статические, РКС сети инкрементальные [58]. СОК подход нашел применение в компьютерной графике для визуализации данных больших размерностей [63], в реконструкции поверхностей свободной формы [71], в натягивании сеток [13], и генерации сеток [146]. Метод представленный в [136] близок к методу нейронной сети, который использует РКС для реконструкции поверхности.

1.6. Отличия представленной задачи от существующих систем

Главное отличие решаемой задачи в том, что входными данными является параметризованная 30 модель исходной детали и её расчетная сетка, т.е. триангулированная поверхность, и расчетные сетки результатов расчета (развертки и оснастки), параметрические 30 модели которых и нужно построить. Неточность узлов сетки вызвана не ошибками измерения, а накоплением погрешностей при много итерационном расчете.

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

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

Анализ показал, что максимальное отклонение геодезического расстояния не превышало 1мм на 10000мм т.е. модели изометрически близки и это позволяет значительно упростить алгоритмы обратного инжиниринга для нашей задачи

Поэтому задача, исходя из анализа существующих систем и поставленных целей разбивается на следующие этапы см Рис 1.6. :

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

2. Сглаживание выделенных участков поверхности и их ребер, снижение ошибок, вызванных накоплением погрешностей при расчетах;

3. Распознавание плоских, цилиндрических и линейчатых участков поверхности, что позволяет снизить машинное время обработки на станке с ЧПУ;

4. Построение элементов ЗЭ модели в иг^гарЫсБ, ребер и выделенных и распознанных участков поверхностей.

Рис. 1.5. Примеры вычисления и построения траектории кривых геодезического расстояния

рсда

Модул

--- г 1

Сегментирование поверхности модели Сегмекгы поверхности Сглаживание сегментов поверхности

30 РО

ЭВМ

I

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Долгополик, Олег Дмитриевич

ВЫВОДЫ

1. Разработан алгоритм сегментации (выделения) деформированных поверхностей и выделения граничных кривых полигональных объемных моделей заготовок авиационных деталей путем нахождения соответствия с поверхностями исходной модели детали и методы их преобразования согласно типу поверхности: плоскость, цилиндр, линейчатая поверхность в параметрическое представление в системе Ш^гарЫсэ;

2. Предложен метод сглаживания неровностей выделенных поверхностей и граничных кривых, за счет использования соответствия с поверхностями исходной аналитической модели;

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

Ожидаемый экономический эффект от внедрения всего расчетного комплекса проектирования оснастки составляет 1 млн. рублей на одном комплекте панелей, а течении производства одного типа самолета около 20-30 млн.рублей.

Список литературы диссертационного исследования кандидат технических наук Долгополик, Олег Дмитриевич, 2012 год

Литература

1. Alexa, М., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, С. T. Point set surfaces. In Visualization 2001: proceedings: October 21-26, 2001, San Diego, California (1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, October 2001), T. Ertl, K. Joy, and A. Varshney, Eds., IEEE Computer Society Press, pp. 21-28.

2. Alfeld, P. Scattered data interpolation in three or more variables. In Mathematical Methods in Computer Aided Geometric Design, T. Lyche and L. Schumaker, Eds. Academic Press, 1989, pp. 1-34.

3. Allgower, E. L., and Schmidt, P. H. An algorithm for piecewise-linear approximation of an implicitly defined manifold. S1AM Journal on Numerical Analysis 22(2) (April 1985), 322-346.

4. Althaus, E., and Mehlhorn, K. Tsp-based curve reconstruction in polynomial time. In Proceedings of the Eleventh Annual ACMSIAM Symposium on Discrete Algorithms (N.Y., January 2000), ACM Press, pp. 686-695.

5. Amenta, N., and Bern, M. Surface reconstruction by voronoi filtering. In Proceedings of the Fourteenth Annual Symposium on Computational Geometry (SCG'98) (New York, June 1998), Association for Computing Machinery, pp. 39-48.

6. Amenta, N., Bern, M., and Eppstein, D. The crust and the /3-skeleton: Combinatorial curve reconstruction. In Graphical models and image processing: GMIP (1998), vol. 60(2), pp. 125-??

7. Amenta, N., Bern, M., and Kamvysselis, M. A new voronoibased surface reconstruction algorithm. In Proceedings of SIGGRAPH 98, M. Cohen, Ed. Addison Wesley, 1998, pp. 415-422.

8. Amenta, N., Choi, S., Dey, T. K., and Leekha, N. Simple algorithm for homeomorphic surface reconstruction. In Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00) (N. Y., June 2000), ACM Press, pp. 213-222.

9. Attali, D. r-regular shape reconstruction from unorganized points. In Proceedings of the 13th International Annual Symposium on Computational Geometry (SCG-97) (New York, June 1997), ACM Press, pp. 248-253.

10. Bajaj, C. L., Bernardini, F., and Xu, G. Automatic reconstruction of surfaces and scalar fields from 3d scans. In Computer Graphics, 29(Annual Conference Series) (November 1995), pp. 109-118.

11. Bajaj, C. L., and Ihm, I. Smoothing polyhedra using implicit algebraic splines. In Computer Graphics, vol. 26(2). July 1992, pp. 79-88.

12. BAJAJ, C. L., and XU, G. Anisotropic diffusion of surfaces and functions on surfaces. In ACM Trans. Graphics 22 (2003), vol. 1, pp. 432. 9.

13. Barhak, J., and Fischer, A. Adaptive reconstruction of freeform objects with 3d som neural network grids. In Proceedings Ninth Pacific Conference on Computer Graphics and Applications, Pacific Graphics 2001 (Los Alamitos, CA, USA, 2001), IEEE Comput. Soc, pp. 97-105.

14. Bernardini, F., and Bajaj, C. Sampling and reconstructing manifolds using alpha-shapes, technical report csd-tr-97-013. Tech. rep., Department of Computer Science, Purdue University, West Lafayette, IN, 1997.

15. Bernardini, F., Bajaj, C. L., Chen, J., and Schikore, D. R. A triangulation-based object reconstruction method. In Proc. 13th ACM Symp. Computational Geometry (June 1997), ACM Press, pp. 481-484.

16. Bernardini, F., Bajaj, C. L., Chen, J., and Schikore, D. R. Automatic reconstruction of 3d cad models from digital scans. International Journal of Computational Geometry and Applications (IJCGA) 9(4-5) (1999), 327-,

17. Bishop, C. M. Neural Networks for Pattern Recognition. Oxford University Press, Oxford, UK, 1995.

18. Blinn, J. F. A generalization of algebraic surface drawing. In ACM Transactions on Graphics, vol. 1(3). July 1982, pp. 235-256.

19. Bohn, C.-A. Radiosity on Evolving Networks. PhD thesis, Fachbereich Informatik, Universität Dortmund, Dortmund, Germany, 2000.

20. Boissonnat, J.-D. Geometric structures for three-dimensional shape representation. In ACM Transactions on Graphics, vol. 3(4). October 1984, pp. 266-286.

21. Brinkley, J. F. Knowledge-driven ultrasonic three-dimensional organ modeling.: In IEEE-Transactions, vol. 7(4) of PAMI. 1985, pp. 431-441.

22. Carr, J., Fright, W., and Beatson, R. Surface interpolation with radial basis functions for medical imaging. In IEEE Transactions Med. Imag. (February 1997), vol. 16.

23. Carr, J. C., Mitchell, T. J., Beatson, R., Cherrie, J. B., Fright, W. R., McCallum, B. C., and Evans, T. R. Reconstruction and representation of 3d objects with radial basis functions. In Proceedings of the Annual Computer Graphics Conference (SIGGRAPH-01). ACM Press, New York, August 2001, pp. 67-76.

24. Chaîne, R. A geometric-based convection approach of 3-d reconstruction. In Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing (2003), Eurographics Association, pp. 218-229.

25. CHEN, C.-Y., and CHENG, H.-Y. A sharp dependent filter for mesh smoothing. In Computer Aided Geometric Design 22 (2005), pp. 376391. 18.

26. Chen, Y., and Medioni, G. Description of complex objects from multiple range images using an inflating balloon model. In Computer Vision and Image Understanding: CVIU (May 1995), vol. 61(3), pp. 325-334.

27. Chien, C. H., Sim, Y. B., and Aggarwal, J. K. Generation of volume/surface octree from range data. In CVPR'88 (IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Ann Arbor, MI, June 5-9, 1988). Computer Society Press, Washington, DC., June 1988, pp. 254-260.

28. CLARENZ, U., DIEWALD, U., and RUMPF, M. Anisotropic geometric diffusion in surface processing. In Proceedings of the Conference on Visualization 2000 (2000), IEEE Computer Society, pp. 145-152. 6.

29. Connolly, C. I. Cumulative generation of octree models from range data. In IEEE International Conference on Robotics and Automation, March, 1984 (March 1984), pp. 25-32.

30,. Curless, B., and Levoy, M. A volumetric method for building complex models from range images. In Proceedings of the ACM Conference on Computer Graphics (New York, August 1996), ACM, pp. 303-312.

31. Curless, B. L. New methods for surface reconstruction from range images. PhD thesis, Stanford University, Computer Systems Laboratory, June 1997. PhD Thesis CSL-TR-97-733.

32. Dahmen, W. Smooth piecewise quadric surfaces. In Mathematical Methods in Computer Aided Geometric Design. Academic Press, 1989, pp. 181-194.

33. Dahmen, W., and Thamm-Schaar, T.-M. Cubicoids: modeling and visualization. Computer Aided Geometric Design 10(2) (April 1993), 89-108.

34. Davies, E. Machine vision: Theory, algorithms. In Practicalities, Microelectronics and Signal Processing Series. Academic Press, New York, 1991.

35. de Figueiredo, L. H., and Gomes, J. Computational morphology of curves. The Visual Computer 11(2) (1995), 105-112.

36. Delaunay, B. Sur la sph'ere vide. In Izvestia Akademia Nauk SSSR, VII Seria, Otdelenie Matematicheskii i Estestvennyka Nauk, vol. 7. 1934, pp. 793-800.

37. Deng, C., and Yang, X. A local fitting algorithm for converting planar curves to b-splines. In Computer Aided Geometric Design, vol. 25. 2008, pp. 837-849.

38. DESBRUN, M., MEYER, M„ SCHRÖDER, P., and BARR, A. H. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proceedings of SIGGRAPH'99 (1999), pp. 317-324. 4.

39. DESBRUN, M., MEYER, M., SCHRODER, P., and BARR, A. H. Anisotropic feature-preserving denoising of height fields and bivariate data. In Graphics Interface 2000 Proceedings (2000), pp. 145-152. 7.

40. Dey, T., Funke, S., and Ramos, E. Surface reconstruction in almost linear time under locally uniform sampling. In Proceedings of the 17th European Workshop on Computational Geometry (EUROCG-Ol) (Berlin, Germany, March 2001), vol. 2, Institute of Computer Science, Freie Universität Berlin, pp. 129-132.

41. Dey, T. K., and Kumar, P. A simple provable algorithm for curve reconstruction. In Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms (N.Y., January 1999), ACM-SIAM, pp. 893-894.

42. Dey, T. K., Mehlhorn, K., and Ramos, E. A. Curve reconstruction: Connecting dots with good reason. In Proceedings of the Conference on Computational Geometry (SCG '99) (New York, N.Y., June 1999), ACM Press, pp. 197-206.

43. Dinh, H. Q., Turk, G., and Slabaugh, G. Reconstructing surfaces using anisotropic basis functions. In Proceedings of the Eighth International Conference On Computer Vision (ICCV-01). Los Alamitos, CA, July 2001, pp. 606-613.

44. Dinh, H. Q., Turk, G., and Slabaugh, G. Reconstructing surfaces by volumetric regularization using radial basis functions. IEEE Trans. Pattern Anal. Mach. Intell. 24(10) (2002), 1358-1371.

45. Dyn, N., Levin, D., and Rippa, S. Numerical procedures for surface fitting of scattered data by radial basis functions. SIAM J Sci. Stat. Comput. 7 (1986), 639-659.

46. Edelsbrunner, H., Kirkpatrick, D. G., and Seidel, R. On the shape of a set of points in the plane. In IEEE Trans. Information Theory IT-29. 1983, pp. 551-559.

47. Edelsbrunner, H., and Mucke, E. P. Three-dimensional alpha shapes. In ACM Transactions on Graphics, vol. 13(1). January 1994, pp. 43-72.

48. Elber, G. Model fabrication using surface layout projection. In Computer-Aided Design (1995), vol. 27, pp. 283-291.

49. Elsner, D. L., Whitaker, R. T., and Abidi, M. A. A volumetric technique for 3d modeling through fusing multiple noisy range images. In International Workshop on Image Analysis and Information Fusion (Adelaide, Austalia, November 1997), pp. 405-416.

50. faugeras, 0., hebert, M., MUSSI, P., and boissonnat, J.-D. Polyhedral approximation of 3-d objects without holes. Computer Vision, Graphics, and Image Processing 25 (1984), 169-183.

51. FIELD, D. A. Laplacian smoothing and delaunay triangulations. In Communications in Numerical Methods in Engineering 4 (1988), pp. 709-712. 1.

52. Fleishman, S., Cohen-Or, D., Alexa, M., and Silva, C. T. Progressive point set surfaces. ACM Transactions on Graphics 22(4) (October 2003), 997-1011.

53. FLEISHMAN, S., DRORI, I., and COHEN-OR, D. Bilateral mesh denoising. In ACM Trans.Graphics 22 (2003), vol. 3, pp. 950-953. 12.

54. Flusser, J. An adaptive method for image registration. Pattern Recognition 25 (1992), 45-54.

55. Foley, T. A., Lane, D. A., Nielson, G. M., Franke, R., and Hagen, H. Interpolation of scattered data on closed surfaces. Computer Aided Geometric Design 7 (June 1990), 303-312.

56. Fomenko, A. T., and Kunii, T. L. Topological Modeling for Visualization. Springer Verlag, April 1988.

57. Fritzke, B. Growing cell structures - a self-organizing network for unsupervised and supervised learning. Tech. rep., International Computer Science Institute, Berkeley, May 1993.

58. Fritzke, B. Growing self-organizing networks - why? In ESANN'96:European Symposium on Artificial Neural Networks (1996), pp. 61-72.

59. Funke, S., and Ramos, E. A. Smooth-surface reconstruction in near-linear time. In Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02) (New York, January 2002), ACM Press, pp. 781-790.

60. Giesen, J. Curve reconstruction, the traveling salesman problem, and menger's theorem on length. In Proceedings of the Conference on Computational Geometry (SCG '99) (New York, N.Y., June 1999), ACM Press, pp. 207-216.

61. Giesen, J., and John, M. Surface reconstruction based on a dynamical system. In Computer Graphics Forum, vol. 21(3). 2002, pp. 363-363.

62. Gold, C. Crust and anti-crust: A one-step boundary and skeleton extraction algorithm. In Proceedings of the Conference on Computational Geometry (SCG '99) (New York, N.Y., June 1999), ACM Press, pp. 189-196.

63. Gross, M., and Seibert., F. Visualization of multidimensional data sets using a neural network. The Visual Computer 10(3) (1993), 145-159.

64. Grosso, E., Sandini, G., and Frigato, C. Extraction of 3d information and volumetric uncertainty from multiple stereo images. In Proceedings of the 8th European Conference on Artificial Intelligence. Pitman Publishers, Munich, FRG, August 1988, pp. 683-689.

65. Guo, B. Surface generation using implicit cubics. In Scientific Visualization of Physical Phenomena (Proceedings of CG International '91). Springer-Verlag, 1991, pp. 485-503.

66. Guo, B. Nonsplitting macro patches for implicit cubic spline surfaces. In Eurographics '93, Eurographics. Blackwell Publishers, Oxford, UK, 1993, pp. 433-445.

67. Hastie, T., and Stuetzle, W. Principal curves. Journal of the American Statistical Association, 84 (1989), 502-516.

68. Hastie, T., Tibshirani, R., and Friedman, J. Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Verlag, New York, 2001.

69. HILDEBRANDT, K., and POLTHIER, K. Anisotropic filtering of nonlinear surface features. In Computer Graphics Forum 23 (2004), vol. 3, pp. 391-400. 10.

70. Hilton, A., Stoddart, A. J., Illingworth, J., and Windeatt, T. Reliable surface reconstruction from multiple range images. Lecture Notes in Computer Science, 1064 (1996), 117.

71. Hoffman, M., and V'arady, L. Free-form modeling for scattered data by neural networks. Journal for Geometry and Graphics (1998).

72. Hoppe, H. Surface Reconstruction from Unorganized Points. PhD thesis, Dept. of Computer Science and Engineering, U. of Washington, 1994.

73. Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., and Stuetzle, W. Piecewise smooth surface reconstruction. In Proceedings of SIGGRAPH '94(Orlando, Florida, July 24-29,1994) (July 1994), Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, ACM Press, pp. 295-302.

74. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. Surface reconstruction from unorganized points. In Computer Graphics (SIGGRAPH '92 Proceedings), vol. 26. July 1992, pp. 71-78.

75. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. Mesh optimization. In Proceedings of SIGGRAPH'93 (1993), pp. 1926.

76. Hoppe, H., DeRose, T. D., DuChamp, T., McDonald, J., and Stuetzle, W. Mesh optimization. Tech. Rep. Technical Report TR-93-01-01, University of Washington, Department of Computer Science and Engineering, January 1993.

77. JONES, T. R., DURAND, F., and DESBRUN, M. Noniterative, feature-preserving mesh smoothing. In ACM Trans.Graphics 22 (2003), vol. 3, pp. 943-949. 11.

78. KIM, B., and J., R. Geofilter: Geometric selection of mesh filter parameters. In Computer Graphics Forum 24 (2005), vol. 3, pp. 295302. 5.

79. Kobbelt, L. P., Vorsatz, J., Labsik, U., and Seidel, H.-P. A shrink wrapping approach to remeshing polygonal surfaces. In Computer Graphics Forum, vol. 18(3). September 1999, pp. 119-130.

80. Kohonen, T. Self-organized formation of topological^ correct feature maps. Biological Cybernetics, 43 (1982), 59-69.

81. Kojekine, N., Hagiwara, I., and Savchenko, V. Software tools using csrbfs for processing scattered data. In Computers and Graphics, vol. 27(2). April 2003, pp. 311-319.

82. Krishnamurthy, V., and Levoy, M. Fitting smooth surfaces to dense polygon meshes. In SIGGRAPH 96 Conference Proceedings (New Orleans, Louisiana, August 1996), Annual Conference Series, ACM SIGGRAPH, Addison Wesley, August 1996, pp. 313-324.

83. Lee, K.-M., Meer, P., and Park, R.-H. Robust adaptive segmentation of range images. IEEE Trans. Pattern Analysis and Machine Intelligence, 20(2) (February 1998), 200-205.

84. Levin, D. Mesh-independent surface interpolation. 2003.

85. Li, A., and Crebbin, G. Octree encoding of objects from range images. Pattern Recognition, 27 (1994), 727-739.

86. Lim, C. T., Turkiyyah, G. M., Ganter, M. A., and Storti, D. W. Implicit reconstruction of solids from cloud point sets. In

SMA '95: Proceedings of the Third Symposium on Solid Modeling and Applications. ACM, May 1995, Salt Lake City, Utah, May 1995, pp. 393-402.

87. Liu, Y., Tang, K., and Joneja, A. Modeling dynamic developable meshes by hamilton principle. In Computer-Aided Design (2007), p. 757bT)"763.

88. Lorensen, W. E., and Cline, H. E. Marching cubes: A high resolution 3d surface construction algorithm. In Computer Graphics (SIGGRAPH '87 Proceedings), vol. 21. July 1987, pp. 163-169.

89. Meer, P., Mintz, D., Kim, D. Y., and Roseneeld, A. Robust regression methods for computer vision:a review. International Journal of Computer Vision, 6(1) (April 1991), 59-70.

90. Melkemi, M. a -shapes and their derivatives. June 1997.

91. Mencl, R. Surface reconstruction from unorganized points in space. 1995.

92. Mencl, R., and Muller, H. Interpolation and approximation of surfaces from three-dimensional scattered data points. 1998.

93. Meyer, F. Automatic screening of cytological. In Comput. Vision, Graphics Image Process. 1986, p. 356ni'S369.

94. Moore, D., and Warren, J. Adaptive mesh generation ii: Packing solids. Tech. rep., Rice University, 1990. TR90-139.

95. Moore, D., and Warren, J. Approximation of dense scattered data using algebraic surfaces. In 24th Annual Hawaii International Conference on System Sciences (1991), pp. 681-690.

96. Morse, B. S., Yoo, T. S., Rheingans, P., Chen, D. T., and Subramanian, K. R. Interpolating implicit surfaces from scattered surface data using compactly supported radial basis functions. In Proceedings of the International Conference on Shape Modeling and Applications (SMI-01) (Los Alamitos, CA, May 2001), IEEE Computer Society, pp. 89-98.

97. Muraki, S. Volumetric shape description of range data using "blobby model

In Computer Graphics (SIGGRAPH '91 Proceedings), vol. 25. July 1991, pp. 227-235.

98. Nielson, G. Modeling and visualizing volumetric and surface-onsurface data. In Focus on Scientific Visualization. Springer-Verlag, 1993, pp. 191-242.

99. Oblonsek, C., and Guid, N. A fast surface-based procedure for object reconstruction from 3d scattered points. Computer Vision and Image Understanding: CVIU, 69(2) (February 1998), 185-195.

100. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. Multi-level partition of unity implicits. In Proceedings of ACM SIGGRAPH 2003 (2003), vol. 22(3), ACM Transactions on Graphics, ACM Press, pp. 463-470.

101. OHTAKE, Y., BELYAEV, A., and BOGAEVSKI, I. Mesh regularization and adaptive smoothing. In Computer-Aided Design 33 (2001), vol. 11, pp. 789-800. 13.

102. Ohtake, Y., Belyaev, A., and Seidel, H.-P. A multiscale approach to 3d scattered data interpolation with compactly supported basis functions. In International Conference on Shape Modeling and Applications 2003 (Seoul, Korea, May 2003).

103. O'Rourke, J. Polyhedra of minimal area as 3d object models. In Proceedings of International Joint Conference on Artificial Intelligence (1981), pp. 664-666.

104. Peng, J., V., S., and Zorin, D. A simple algorithm for surface denoising. In Proceedings of IEEE Visualization (2001), pp. 107-112. 23.

105. Pentland, A., and Sclaroff, S. Closed-form solutions for physically based shape modeling and recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(7) (July 1991), 715-729.

106. Pollack, R., and Festschrift, E. G. Springer-Verlag, 2002, ch. Surface reconstruction by wrapping finite point sets in space.

107. Pratt, V. Direct least-squares fitting of algebraic surfaces. In Computer Graphics (SIGGRAPH '87 Proceedings) (July 1987), vol. 21, pp. 145152.

108. Pulli, K., Duchamp, T., Hoppe, H., McDonald, J., Shapiro, L., and Stuetzle, W. Robust meshes from multiple range maps. In Proceedings

of IEEE Int. Conf. on Recent Advances in 3-D Digital Imaging and Modeling (May 1997).

109. Rousseeuw, p. J., and Leroy, a. M. Robust Regression and Outlier Detection. John Wiley & sons, December 1987.

110. Rutishauser, M., Stricker, M., and Trobina, M. Merging range images of arbitrarily shaped objects. In Proceedings of the Conference on Computer Vision and Pattern Recognition (Los Alamitos, CA, USA, June 1994), IEEE Computer Society Press, pp. 573-580.

111. Sakkalis, T., and Charitos, C. Approximating curves via alpha shapes. Graphical models and image processing: GMIP, 61(3) (May 1999), 165176.

112. Schudy, R. B., and Ballard, D. H. Towards an anatomical model of heart motion as seen in 4-d cardiac ultrasound data. In Proceedings of the 6th Conference on Computer Applications in Radiology and Computer-Aided Analysis of Radiological Images (1979).

113. Sclaroff, S., and Pentland, A. Generalized implicit functions for computer graphics. In Computer Graphics (SIGGRAPH '91 Proceedings) (July 1991), vol. 25, pp. 247-250.

114. Sethian, J. A. Level Set Methods. Cambridge University Press, 1996.

115. SHEN, Y., and BARNER, K. E. Fuzzy vector medianbased surface smoothing. In IEEE Trans. Visualization and Computer Graphics 10 (2004), vol. 3, pp. 252-265. 17.

116. Sibson, R. A vector identity for the dirichlet tessellation. In Mathematical Proceedings of the Cambridge Philosophical Society (1980), vol. 87, pp. 151-155.

117. Sibson, R. A brief description of natural neighbour interpolation. 1981, pp. 21-36.

118. Sibson, R., and Stone, G. Computation of thin-plate splines. SIAM Journal on Scientific and Statistical Computing, 12(6) (November 1991), 1304-1313.

119. Soucy, M., and Laurendeau, D. Multi-resolution surface modeling from multiple range views. In Conf. on Computer Vision and Pattern Recognition (CVPR '92) (June 1992), pp. 348-353.

120. Stewart, C. V. Minpran: a new robust estimator for computer vision. In IEEE Transactions on Pattern Analysis and Machine Intelligence (October 1995), vol. 17, pp. 925-938.

121. Subramanian, K., and Fussel, D. A search structure based on k-d trees for efficient ray tracing. Tech. rep., The University of Texas at Austin, 1992. Tx 78712-1188.

122. Succi, G., Sandini, G., Grosso, E., and Tistarelli, M. 3d feature extraction from sequences of range data. In Proceedings of the 5th International Symposium on Robotics Research (1991), pp. 116-127.

123. Tang, K., and C.Wang. Modeling developable folds on a strip. Journal of Computing and Information Science in Engineering 5 (2005), 35-47.

124. Tarbox, G., and Gottschlich, S. Ivis: An integrated volumetric inspection system. In Proceedings of the 2nd CAD-Based Vision Workshop (1994), pp. 220-227.

125. TASDIZEN, T., WHITAKER, R., BURCHARD, P., and OSHER, S. Geometric surface smoothing via anisotropic diffusion of normals. In Proceedings of the Conference on Visualization 2002 (2002), IEEE Computer Society, pp. 125-132. 8.

126. Taubin, G. Estimation of planar curves, surfaces and non-planar space curves defined by implicit equations, with applications to edge and range image segmentation. In Proceedings of the IEEE Transaction on Pattern Analysis and Machine Intelligence (November 1991), vol. 13, pp. 11151138.

127. TAUBIN, G. A signal processing approach to fair surface design. In SIGGRAPH'95 Conference Proceedings (1995), pp. 351-358. 3.

128. Taubin, G. A signal processing approach to fair surface design. In SIGGRAPH 95 Conference Proceedings (Los Angeles, California, August 1995), Annual Conference Series, ACMSIGGRAPH, Addison Wesley, pp. 351-358.

129. TAUBIN, G. Linear anisotropic mesh filtering. Tech. rep., IBM Research Report RC22213(W0110-051), 2001. 14.

130. Teichmann, M., and Capps, M. Surface reconstruction with anisotropic density-scaled alpha shapes. In IEEE Visualization '98 (1998), IEEE, pp. 67-72.

131. Terzopoulos, D. Regularization of inverse visual problems involving discontinuities. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(4) (1986), 413-424.

132. Turk, G., and Levoy, M. Zippered polygon meshes from range images. In Proceedings of SIGGRAPH '94 (Orlando, Florida, July 24-29, 1994) (July 1994), Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, ACM Press, pp. 311-318.

133. Turk, G., and O'Brien, J. F. Variational implicit surfaces. Tech. rep., Georgia Institute of Technology, 1998. GIT-GVU-99-15.

134. Turk, G., and O'Brien, J. F. Shape transformation using variational implicit functions. In Computer Graphics, vol. 33 of Annual Conference Series. 1999, pp. 335-342.

135. Turk, G., and O'brien, J. F. Modelling with implicit surfaces that interpolate. ACM Transactions on Graphics, 21(4) (October 2002), 855=873.

136. Varady, L., Hoffman, M., and Kovacs, E. Improved free-form modeling of scattered data by dynamic neural networks. Journal for Geometry and Graphics 3 (1999), 177-181.

137. Veltkamp, R. C. 3d computational morphology. In Eurographics '93. Eurographics, Blackwell Publishers, Oxford, UK, 1993, pp. 115-127.

138. Vemuri, B. C. Representation and recognition of objects from dense range maps. PhD thesis, University of Texas at Austin, 1987.

139. Vemuri, B. C., Mitiche, A., and Aggarwal, J. K. Curvature-based representation of objects from range data. Image and Vision Computing 4(2) (May 1986), 107-114.

140. VOLLMER, J., MENCL, R., and MULLER, H. Improved laplacian smoothing of noisy surface meshes. In Proceedings of Eurographics (1999), pp. 131-138. 2.

141. Watson, D. F. Contouring: A guide to the Analysis and Display of Spatial Data. Pergamon Press, 1992.

142. YAGOU, H., OHTAKE, Y., and BELYAEV, A. G. Mesh smoothing via mean and median filtering applied to face normals. In Proceedings of Geometric Modeling and Processing (2003), pp. 124-131. 15.

143. YAGOU, H., OHTAKE, Y., and BELYAEV, A. U. Mesh denoising via iterative alpha-trimming and nonlinear diffusion of normals with automatic thresholding. In Computer Graphics International 2003 (CGI'03) (2003), pp. 28-34. 16.

144. Yngve, G., and Turk, G. Creating smooth implicit surfaces from polygonal meshes. 1999.

145. Yoshizawa, S., Belyaev, A., and Seidel, H.-P. Smoothing by example, mesh denoising by averaging with similarity-based weights. 19.

146. Yu, Y. Surface reconstruction from unorganized points using selforganizing neural networks. In IEEE Visualization 99, Conference Proceedings (1999), pp. 61-64.

147. Zhang, Z. Parameter estimation techniques: A tutorial with application to conic fitting. Tech. rep., Inria, Institut National de Recherche en Informatique et en Automatique, October 1995. RR-2676.

148. Zhao, H., and Osher, S. Visualization, analysis and shape reconstruction of unorganized data sets. In Geometric Level Set Methods in Imaging, Vision and Graphics (2002), Springer-Verlag.

149. Zhao, H.-K., Osher, S., and Fedkiw, R. Fast surface reconstruction using the level set method. In Proceedings of the IEEE Workshop on Variational and Level Set Methods in Computer Vision (Vancouver, BC, Canada, July 2001), pp. 194-202.