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

- 3 ПАР 1997

Российская Академия Наук Вычислительный Центр

На правах рукописи УДК 519.3

ФА» ДАТ ФУК

ТРЕХМЕРНОЕ МОДЕЛИРОВАНИЕ НА ОСНОВЕ ПАРАМЕТРИЧЕСКИХ ОБЪЕДИНЕНИЙ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата фнзнко-математнческих наук

Специальность 05.13.11 — Математическое н программное обеспечение вычислительных машин, комплексов, систем и сетей

Москва 1997

Работа выполнена в Российском Государственном Открытом Техническом Университете Путей Сообщений и Вычислительном центре Российской Академии Наук.

Научный руководитель:

кандидат физико-математических наук ГТеданов И, Е,

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

докгор физико-математических наук Клеменко С. В. кандидат физико-математических наук Голиков К. П.

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

Российский Космический Комплекс - Энергия

Защита состоится '¿2*7" фс^ппля 1997г. в час, на заседании диссертационного совета К 002.32.01 в Вычислительном центре РАН.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра РАН.

Автореферат разослан"//" февраля 1997г.

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

доктор физико-матемагаческнх наук, профессор

Рудаков К. В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

Цель работы. Целью работы является:

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

• разработка программного ядра, реализующего метод параметрического объединения с помощью объектно-ориентированного программирования.

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на международной конференции "Эволюция Инфосферы" (г. Москва, 1995г.).

Объем и структура диссертации. Диссертации состоит из введения, четырех глав, заключения и трех приложений, изложенных на 106 страниц машинописного текста. В диссертации 17 рисунок; Приложения содержат 16 страниц. Список литературы состоит из 51 наименований.

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

Во введении приводится постановка изучаемой проблемы,

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

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

В разделе 1.1 делается обзор методов трехмерного моделирования. Даются краткие определения шести методов:

1 ) метода конструирования из примитивов;

2) метода перечисления занятого пространства;

3) метода разбиения на клетки;

4) метода описания границ;

5) метода конструктивной геометрии;

6) метода параметрического объединения.

В разделах 1.2 и 1.3 анализируется тенденция использования методов трехмерного моделирования в современных системах. Делается анализ на примере трех мощных и популярных программных продуктов:

1) AutoCad Release 13 фирмы Autodesk Inc.

2) MicroStation 95 фирмы Bentley System Inc.

3) 3D Studio version 4.0 фирмы Autodesk Inc.

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

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

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

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

1) некомпланарность характеристической плоскости с направлением (вектором) прямолинейного равномерного движения характеристической плоскости, и

2) неортогоналыюсть характеристической плоскости с вектором оси вращения равномерного вращательного движения характеристической плоскости,

Педанов И. Е. показал, что для определенного таким образом параметрического объединения, имеет место (существует) двухместный предикат "точка х из Е3 является точкой параметрического объединения А" (назовем его предикатом принадлежности), для всех точек из В3 (за исключением точек пересечения характеристической плоскости с осью вращения равномерного вращательного движения характеристической плоскости) и всех параметрических объединений.

В разделе 2.2 исследуется математическая модель параметрических объединений.

Для любого множества АсЕ" можно определить функцию о/гредглення таким образом: ГгЕ"-»!?. | (Г(х)£0 УхеА) и (С(х)>0

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

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

двухмерных полупространств с непрерывной функцией определения £:Е2х[а,Ь]-»Я, где УаеЕ2, 1е[а,Ь] £(а^)=Г1(а) определяет

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

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

{1ГХ | Х=Р(Аи1), 1е[а,Ь]} , где . некоторая заметающая фигура, а Р - равномерное прямолинейное или равномерное вращательное движение.

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

1) Параметрические объединения являются замкнутыми множествами;

2) Любое трехмерное полупространство является некоторым параметрическим объединением;

3) Параметрическое объединение является трехмерным регулярным множеством, если функция определения заметающей фигуры Г:Е2х[а,Ь]->11 ие имеет экстремума в тех точках, где функция обращается в нуль, т.е.

аеЕ2х[а,Ъ] (Г<а>=0) =>

(Уе>0 Зх,уеЕ5х[а,Ь]

<1(х,а)<е, й(у,а)<е 1 |-(х)>0, £(у)<0).

Третья глава посвящена проблемам построения программного обеспечения, реализующего метод параметрического объединения.

Построенное программное обеспечение должно удовлетворять следующим требованиям:

1) Метод параметрического объединения должен быть реализован в полном масштабе;

2) Аппарат конструктивной геометрии должен быт включен и

3) Преобразование в граничное представление должно быть поддержано.

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

3 2Э~

и уравнение его поверхности £:ОсЕ —»-Б . Заметим, что для трехмерных объектов с поверхностью второго порядка (т.е. функции определения которых являются многочленами второго порядка) эти требования являются тривиальными.

Аналогично, для задания заметающей фигуры требуются и функция определения £:Е2х[а,Ь]-Ж, и уравнения кривой g:Dx[a,b]->E2. Такой способ позволяет получить уравнение поверхности параметрического объединения в явном виде:

1) 5(и,1) = О+ух1+Оххх(и,0+Оуху(и,0 для прямолинейного параметрического объединения и

2) ё(ц,0 = О(1)+Ох(1)хх(ц,1)+Оуху(и,0,где 0({)=т+(0-т)хсо8(0+пх(п*(0-т))х(1-со5(1)) + (п®(0-т))х5т(0,

0*(t)=0xxcos(t)+nx(n»0x)x(l-cos(t))+ (n®Ox)xsin{t),

Oy(t)=Oyxcos(t)+iix(n»Oy)x(l-cos(t))+

(n®Oy)xsm(t) для вращательного параметрического объединения,

В разделе 3.2 обсуждается центральный вопрос реализации параметрического объединения • моделирование заметающей фигуры. Отмечается, что помимо своей универсальности, способ задания заметающей фигуры с помощью функции определения и уравнения кривой не является удобным для пользователя. Поэтому предлагается модель заметающей фигуры, которая состоит из трех частей - начальной плоской фигуры, конечной плоской фигуры и механического движения в плоскости. Пусть теперьначальная кривая имеет уравнение x=xi(u), у=у i (и), а конечная-х=хг(и), у—у 2 (и), и <= [0,1 ]. Тогда заметающая фигура имеет уравнение кривой

x(u,t)=x2(u)xtH x,(u)x(l-t), y(u,t)=y2(u)xt+yf(u)x(J-t), uefO.l], te{0,1 ]. Задача проверки принадлежности точки заметающей фигуре решается с помощью теоремы Жордана (Jordan), согласно которой точка принадлежит, плоской фигуре, если луч с концом в данной точке пересекает данную кривую нечетное число раз, при этом точка касаикя считается два раза

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

Такая модель заметающей фигуры имеет следующие преимущества:

1) сохраняется универсальность метода параметрического объединения;

2) удобно для пользователя;

3) легко к быстро можно расширять класс заметающей фигуры благодаря разделению процесса на деформацию и перемещение.

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

1) Ъ(Ап*В) = 1(ЪАгпВ)и(ЪВгиА)]и [ЬАг»ЬВпк{| АгмВ)];

2) Ь(Ли*В) = [(ЬАпсВ)и(ЬВпсА)]и [Ь Аг>ЬВпк(сАГ1сВ)];

3) Ь(Л\*В)=[(ЬАпсВ)и(ЬВгиА)]и [ЬАг>ЬВпкОАпсВ)].

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

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

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

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

В разделе 3.4 вводится новый метод визуализации трехмерных объектов. Обычно для получения высоко реалистического изображения используют метод трассировки лучей (ray tracing). Основной недостаток этого метода - огромные вычислительные затраты. Тем более, что для трехмерных объектов типа заметания невозможно непосредственно решить основное уравнение - нахождение пересечения луча с объектом.

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

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

О

поверхности которого известно F:[MinU,MaxU] х fMinV,MaxV]—>E .

Очевидно, что реалистическое изображение объекта можно получить, если мы будем проектировать на экран все точки F ( u i, Vj), где Ui=MmU + ix(MaxU-MmU)/M, Vj=MinV-i-jx(MaxY-MmV)/N,

i = 0... M, j = 0... N, при достаточно больших значениях М и N, применяя метод z-buffer. Проблема состоит в выборе шагов для и и v. Если выбираем слишком маленькие шаги, то теряем эффективность (потому, что для одной точки экрана надо вычислять много раз значение F ( u, v )). Если же выбираем не достаточно маленькие шаги, то на изображении объекта появляются "дырки".

Было доказано, что отсутствие «дырки» гарантируется, если максимальное расстояние соседних точек не превышает Iт.е. га ах {d ( project( F (u;, v j) ,project( F ( и, + i, Vj))), dtprojectiFCui.VjJ.projectiFiui.Vj+i)))} il/-/2 Vi,j

Если поверхность объекта достаточно гладкая, то можно использовать более удобные условия:

гле

DP,iU=max{öP*/9u(u,v) I ue[MinU,MaxU],ve [MinV.MaxV]}, DPyU=max{ 3Py/9u(ii,v) j u e [MinU,MaxU],ve [MinV.MaxV]}, DPx»=n)ax{5Px/3v(u,v) I ue [MinU,MaxU],ve [MinV.MaxV]}, DPyv=niax{3P,/3v(a,v) | ue [MinU,MaxU],ve [MinV.MaxV]}.

Заметим, что эти формулы уже задают способ выбора шагов. Однако они не очень эффективны. Если предварительно разбить отрезки [MinU.MaxU] и [MinV.MaxV] на М и N равных частей (такая процедура всегда проводится для получения приближенного изображения) и проводить выбор шагов отдельно на каждом отрезке, то суммарное число точек, для которых надо построить изображения значительно уменьшается. Другое преимущество такого разбиения заключается в том, что для достаточно маленьких отрезков можно предполагать, что максимальные значения частных производных функции Р принимаются на концах отрезка. Кроме того, значения частных производных функции Р уже частично вычислены при построении приближенного изображения объекта.

Именно такой метод был использован в программе «Solid Modeler» и он позволяет получить реалистическое изображение трехмерных объектов

примерно в течение 1 • 2 минуты на IBM PC 486DX2 с 8Mb памяти и в течение 10-15 секунд на IBM PC Pentium 120 с 16Mb памяти.

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

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

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

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

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

На основе построенной модели трехмерных объектов можно легко создать новую систему трехмерного моделирования, ориентированную на конкретную область применения. Примером такой системы может служит программа «Solid Modeler«.

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

Программа «Solid Modeler» способна работать на любом IBM -совместимом персональном компьютере, который поддерживает Microsoft Windows версии 3.1 или более поздние с 4Mb оперативной памяти. Для получения цветного изображения трехмерного моделируемого объекта требуется способность видео-карты работать в режиме не меньше 256 цветов.

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

В приложении А приведены использованные в диссертации математические понятия, в приложении Б исследуется вопрос определения значения параметров в задаче проверки принадлежности точки параметрическому объединению. В приложении В приведены некоторые трехмерные объекты, моделируемые с помощью прмраммы «Solid Modelen».

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Приведем основные результаты диссертационной работы:

1) Метод параметрического объединения исследован системно. Предложено н реализовано новое внутреннее представление параметрических объединений.

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

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

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

5) На базе разработанного ядра была проектирована программа «Solid Modeler», которая является мощным инструментом для моделирования трехмерных объектов типа заметания.