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

введение.

0.1 Неявные / изоповерхности.

0.1.1 Задание поверхностей с использованием математических функций.

0.1.2 Задание поверхностей с помощью процедурных методов.

0.1.3 Задание поверхностей с помощью дискретных данных.

0.1.4 Способы визуализации неявных поверхностей.

0.1.5 Интерактивная визуализация.

0.2 Актуальность работы.

0.3 Цели и задачи работы.

0.3.1 Контроль количества аппроксимирующих изоповерхность полигонов.

0.3.2 Осуществление полигонизации "налету".

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

0.3.4 Повышение качества полигонизации в областях высокой кривизны изоповерхности.

0.3.5 Разработка архитектуры системы геометрического моделирования.

0.4 Научная новизна работы.

0.5 Апробация результатов.1В

0.6 Структура работы.

глава 1. визуализация изоповерхностей.

1.1 Существующие методы полигонизации.

1.2 Базов ы й метод полигонизации.

1.2.1 Полигонизаг1ия изоповерхности внутри ячейки.

1.2.2 Разрешение неоднозначностей при полигонизации.

1.3 Адаптивная иерархическая реконструкция изоповерхности.

1.3.1 Обход иерархии ячеек при реконструкции изоповерхности.

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

1.4 Результаты.

1.5 Промежуточные итоги.

глава 2. обновление изоповерхности.

2.1 Обработка перемещения наблюдателя.

2.2 Обработка изменения степени детализации.

2.3 Обработка модификаций данных в исходном представлении.

2.4 Результаты.

2.5 Промежуточные итоги.

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

3.1 Модификация рёбер базового полигона.

3.2 Добавление внутренней точки базового полигона.

3.3 Триангуляция расширенного полигона.

3.4 Анализ метода повышения точности полигонизации.

3.5 Альтернативный способ выбора дополнительных точек.

3.6 Результаты.

3.7 Промежуточные итоги.

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

4.1 Организация систем объёмного моделирования.

4.2 Концепция объёмной модели.

4.3 Функциональное представление.

4.4 Воксельное представление.

4.5 Гибридное представление.

4.6 Входные данные системы.

4.7 Интерактивное геометрическое моделирование.

4.8 Результаты.

4.9 Промежуточные итоги.

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

По определению, р принадлежит поверхности, если f(p) = 0. Функция Дописывает поверхность неявным образом, подразумевая её существование.

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

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

0.1.1 Задание поверхностей с использованием математических функций

Использование математических функций позволяет определять точки поверхности путём задания соотношений между их координатами. При явном способе задания одна из координат принадлежащих поверхности точек выражается через две других: z=f(x,y). Таким образом заданную поверхность часто называют полем высот. Выделенность одной из координат при этом ограничивает форму поверхности, задаваемой таким образом. В частности, такая поверхность не может быть параллельна оси Z.

Существуют как минимум два подхода, симметрично использующих координаты принадлежащих поверхности точек и поэтому лишённых проблем с явным заданием одной из координат. Первый подход является параметрическим, когда каждая из координат задаётся определяемым геометрической размерностью объекта числом параметров. Так, для одномерной кривой в двумерном пространстве x—fx(t)и y=fy(t). Для двумерной поверхности, расположенной в трёхмерном пространстве, x=fx(s,t), y=fy(s,t) и Z=fz(s,t). Параметрические кривые и поверхности предоставляют возможность удобного отображения объекта в провтранство, в которое он помещён. Прямое отображение, или параметризация, полезна при визуализации поверхности, наложении текстур и т.д.

Другой симметричный подход является неявным, где координаты рассматриваются как аргументы функции, а не значения функции. В общем случае, связь между координатами точек поверхности задаётся уравнением вида f(x,y,z)=C, где с является точкой в пространстве и /отображает 9?3 в 5Я" .Для большинства приложений, п = 1 и с является скалярной константой. В случае с=0 f неявным образом определяет множество точек, называемой неявной поверхностью, т.е. множество {/> е 9r : / (р) = 0}. Функция/ называется в таком случае неявной функцией. Иногда она называется скалярным полем, функцией поля или потенциалом. Неявная поверхность называется нулевым множеством (или нулевой поверхностью) функции f и обозначается как f~l(0) или Z(f). Связаная с неявной поверхностью изоповерхность определяется как {р е : f(p) — c}, где с называется изозначением для такой поверхности. Изоповерхности часто представляют интерес в областях научной и медицинской визуализации, в то время как неявные поверхности более близки областям, связанным с геометрическим проектированием.

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

Неявно определённая поверхность может быть ограниченной (т.е. иметь конечные размеры), а может быть неограниченной (например, для случая f(x,y,z)=x+y+z+1 =0). Если функция/является непрерывной, то её значение в точке р может в некоторых случаях служить мерой расстояния от поверхности до точки р. Обычно эта мера не является евклидовой. Для алгебраических поверхностей, такая мера называется алгебраическим расстоянием (если функция /линейна, то такое расстояние пропорционально расстоянию, определяемому с помощью евклидовой меры).

Для возможности определения нормалей на неявной поверхности, соответствующая неявная функция должна быть непрерывной и дифференцируемой, т.е. во всех точках поверхности частные производные д/ /дх, df /ду, of /dz должны быть непрерывными и не обращаться одновременно в ноль. Такая функция считается аналитической (по крайней мере в той области, в которой выполняются эти условия). Если градиент V/ = (З/'/ох, не равен нулю в точке р, то такая точка называется регулярной и градиент совпадает по направлению с нормалью к поверхности в точке р. В противном случае точка р является сингулярной и направление нормали в ней не может быть определено. Если каждая точка изоповерхности для некоторого изозначения с является регулярной, то такое значение называется регулярным значением для функции

2 2 2 Например, функция j=-x +}> +z имеет сингулярную точку при x—y—z—О. Поэтому ноль не является регулярным значением для этой функции, в отличие от всех остальных значений. Если все точки поверхности регулярны и вторые частные проиводные непрерывны на ней, то эта поверхность имеет непрерывную кривизну.

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

Актуальность неявных поверхностей, являющихся двумерными многообразиями, проявляется в свете следующего имеющего место утверждения: если ноль является регулярным значением для функции^ то f!(0) описывает двумерное многообразие и каждая ограниченная, целая компонента fl(0) является поверхностью, которая разделяет конечную внутреннюю часть объёма от бесконечной внешней. Это утверждение естественным образом обобщается на изоповерхности f(p)=c, если с является регулярным значением. Таким образом, для изоповерхностей, являющихся двумерными многообразиями, существует возможность определить понятия внутренней по отношению к ней части пространства, в которое помещена изоповерхность, и внешней, что является важным свойством изоповерхностей, позволяющим легко решать ряд актуальных для геометрического проектирования задач.

В некоторых случаях для визуализации неявной поверхности достаточно её математического определения. Типичным примером являются методы трассировки лучей [38,39]. В ряде других задач возникает необходимость аппроксимировать поверхность с помощью некоторого другого конкретного представления, как, например, набора треугольников или полигонов. Любое дифференцируемое многообразие может быть аппроксимировано набором полигонов [119]. Это значит, что достаточно гладкая, ограниченная неявная поверхность может быть покрыта набором полигонов. Процесс, при котором порождается этот набор полигонов, часто называется полигонизацией. Обычно полигонизация использует наложение некоторой трёхмерной сетки на область, содержащую поверхность, с целью определения точек пересечения поверхности с сеткой и их соединения. В некоторых случаях получаемое полигональное представление, несмотря на определённую неточность, возникающую при аппроксимации им исходной поверхности, является единственным практически используемым представлением. Так, существуют значительные математические затруднения [47] при получении точных математических определений (и параметрических, и неявных) для таких концептуально простых поверхностей, как поверхность смещения (находящаяся на некотором фиксированном расстоянии от некоторой базовой поверхности) и эквидистантная поверхность (равноудалённая от двух базовых поверхностей). В то же время существуют достаточно простые процедурные определения для этих поверхностей и они легко конвертируются путём полигонизации в полигональное представление.

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

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

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

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

0.1.2 Задание поверхностей с помощью процедурных методов

Процедурные методы позволяют использовать для задания поверхности произвольный вычислительный процесс [88], который для заданной точки трёхмерного пространства генерирует скалярное значение. Этот процесс может использовать математические функции, условия, таблицы и т.д.; возможно и использование стохастических методов [87]. В общем случае, процедурное представление не может быть выражено в замкнутой форме, в силу чего аналитическое изучение определяемой таким образом поверхности затруднено или невозможно. В то же время, процедурные методы обеспечивают, возможно, наибольшую гибкость при определении поверхности. Один из подходов, использующих процедурное представление, называется функциональным представлением [83]. В нём описание объекта представляет собой древообразную структуру, в листьях которой находятся некоторые определяемые с помощью неявных функций геометрические примитивы. Примитив может задаваться произвольной функцией - черным ящиком и быть достаточно сложным. В узлах этой структуры находятся операции, комбинирующие примитивы, такие как теоретико-множественные, оффсеттинга (смещения поверхности вдоль нормали на заданное расстояние), афинные преобразования и т.д. В принципе, возможно использование произвольных операций, относительно которых замкнуто множество конструируемых неявных функций. Важной особенностью является использование в функциональном представлении так называемых R-функций [2] в реализации теоретико-множественных операций. В отличие от широко используемых минимаксных функций для реализации теоретико-множественных операций, не сохраняющих С1 непрерывность, использование определённых классов R-функций позволяет сохранить любую наперёд заданную гладкость в результате применения реализованных с их помощью операций.

0.1.3 Задание поверхностей с помощью дискретных данных

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

1, 82, 123], а также с использованием методов прямой визуализации объёма [28, 63, 91, 111, 117, 118, 120]. К недостаткам дискретного представления можно отнести повышенные требования к памяти, используемой для хранения данных, а также ограниченную сложность объектов, которые можно задать с использованием такого представления, поскольку она ограничена разрешением сетки, на которой представлены данные. Другая форма дискретного представления состоит в наборе точек, лежащих на неявной поверхности. В этом случае требуется реконструкция неявной функции, описывающей такую поверхность. Примером подхода к реконструкции поверхности в таком случае является [49], где в каждой точке неявная поверхность аппроксимируется плоскостью, которая предположительно перпендикулярна к поверхности. Неявная функция определяется как расстояние от точки, в которой она вычисляется, до ближайшей такой плоскости. Для того, чтобы ноль был регулярным значением таким образом построенной неявной функции, требуется, чтобы расстояние имело знак, а значит, все плоскости должны быть ориентированы согласованным образом.

0.1.4 Способы визуализации неявных поверхностей

Методы визуализации неявных поверхностей исторически связаны с двумя следующими типами исходного представления - дискретного и использующего математические функции. Популярность дискретного представления, как указывалось выше, связана с распространённым использованием объёмных сканеров в медицине, научных дисциплинах и т.д., что, в свою очередь, стимулирует развитие методов визуализации такого представления. Ранние методики основывались на построении изолиний на срезах полученного массива данных с последующим их соединением для формирования изоповерхности [112]. В настоящее время такие методы практически полностью заменились методами полигонизации изоповерхности [1, 66, 82, 123]. Такие методы применимы, когда интересующим результатом является собственно поверхность, особенно при меняющемся изозначении. Если интересуют свойства материала, заключённого в охватываемом сеткой объёме, то используются методы объёмной визуализации. В них учитывается вклад каждого отдельного скалярного значения в результат, получаемый на экране [28, 63, 91, 1 11, 117, 118, 120]. Некоторые их таких методов частично визуализируют поверхности внутри объёма [28, 35]. Большей частью объёмная визуализация применяется к данным, представленным на регулярной, возможно, подвергнутой аффинному преобразованию сетке, и использует ортогональное проецирование. Также существуют методы, поддерживающие перспективную проекцию [77, 118] и работающие с нерегулярными сетками [37].

При работе с математическим представлением неявных поверхностей, как правило, отсутствует возможность порождения точек, принадлежащих поверхности, с помощью подстановки, как при использовании параметрических поверхностей. В силу этого обстоятельства, визуализация математически заданных неявных поверхностей практически всегда требует нахождения корней уравнения, определяющего неявную поверхность. Для простых случаев (вроде алгебраических поверхностей второго порядка) отыскание корней (и, следовательно, положения точек на поверхности) может производиться аналитически. В случае произвольной неявной функции требуется использование численных методов. Такая задача возникает при визуализации изоповерхностей методами трассировки лучей, полигонизации поверхности, построении контурных линий (линий уровня) при пересечении поверхности плоскостью, или визуализации методом частиц для точек на поверхности. Скорость поиска корней зачастую улучшается при использовании пространственного подразделения объёма, при котором он покрывается набором соседствующих, но не перекрывающихся ячеек [93]. Большинство интересующих в таких случаях объектов имеют конечные размеры и могут быть полностью покрыты таким набором ячеек. Для дифференцируемых неявных функций это означает, что в каждой из таких ячеек, содержащих участок изоповерхности, есть точка, в которой функция принимает положительное значение, и есть точка, в которой она принимает отрицательное значение. В большинстве реализаций, вычисление функции производится в вершинах ячеек.

При полигонизации строится полигональная аппроксимация поверхности, использующая вычисление значений неявной функции на заданной сетке. Шаг сетки может быть избыточным в областях малой кривизны поверхности и недостаточным при высокой кривизне. Для решения таких проблем были разработаны адаптивные методы, локально изменяющие шаг сетки [12, 43] для сохранения качества полигонизации.

Для изображений, получаемых с помощью трассировки лучей, корни функции /должны определяться для каждого нового направления взгляда на сцену; для сравнения, при полигонизации такая процедура производится только один раз за всё время возможной анимации. Трассировка лучей редко достигает интерактивных темпов [86], хотя существуют определённые оптимизации для конкретных видов моделей [76]. В общем случае, неявные поверхности проще визуализировать методами трассировки лучей, чем параметрические [54].

Альтернативой методам визуализации поверхностей является построение набора контурных линий, получаемых пересечением поверхности набором перпендикулярных направлению взгляда плоскостей [88]. Для каждой плоскости строится линия нулевого значения неявной функции, за исключением тех её частей, которые скрыты за впереди идущими линиями.

Другие методы визуализации используют набор частиц, распределённых по неявной поверхности. Равномерность распределения достигается за счёт эмулирования эффекта взаимного отталкивания. Частицы при этом удачно представляют поверхность [13, 34] и могут служить точками модификации при геометрическом моделировании [121], а также служить основой при полигонизации [33]. При анимации поверхности, топология поверхности может поддерживаться при определении тех точек, в которых происходят топологические изменения. Как указано в [105], такие точки являются точками сингулярности (т.е. теми, где V/ = 0).

0.1.5 Интерактивная визуализация

Существует ряд подходов, позволяющих повысить интерактивность визуализации объектов, определяемых с помощью неявных поверхностей. Обзор таких методов можно найти в [13]. Для геометрического моделирования такие методы включают в себя использование примитивных неявных функций (в скелетных моделях [18]), упрощённые методы визуализации (визуализация значений функции в сечении), или использование объёмной визуализации. Непосредственно при визуализации используются ограничивающие параллелепипеды, когерентность изображения между кадрами, переменная точность при полигонизации, указываемая пользователем, адаптивное подразделение объёма, применяемое локально или глобально (согласно указаниям пользователя), кусочно-линейная аппроксимация криволинейных скелетных элементов, а также повышение точности аппроксимации во время малой нагрузки на процессор.

Использование методов частиц также предоставляет средства для интерактивной визуализации неявных поверхностей, причём положения этих точек зачастую определяется с помощью эвристик (например, с использованием значений градиента неявной функции [13, 34]).

0.2 Актуальность работы

Актуализация проблемы интерактивной визуализации изоповерхностей связана с рядом факторов. Широкое распространение и использование трёхмерных сканеров, представляющих сканируемый объект в виде массива скалярных данных, заданных на регулярной сетке, и их применение в медицине, точных науках и т.д., требует разработки средств, облегчающих изучение полученных результатов исследователями. Визуализация изоповерхностей, как способ наглядного представления данных, позволяет во многом облегчить решение такой задачи. Впрочем, в области визуализации статичных данных уже достигнуты определённые успехи. В то же время задаче визуализации динамически меняющихся изоповерхностей внимание стало уделяться сравнительно недавно [107], хотя в ряде работ на возможность визуализации меняющихся данных при наличии достаточных вычислительных мощностей указывалось давно [15]. Возможность визуализации происходящих изменений в исходных данных / функциях в случае научных исследований позволяет показать динамику процесса, что может быть также весьма полезно с точки зрения решения задач, стоящих перед исследователем. Возможность внесения интерактивных изменений пользователем и их визуализация позволяет оценить результаты определённых модификаций и выбрать приемлемый вариант. Примером может являться оценка результатов какого-либо оперативного вмешательства в случае медицины.

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

Большое число работ посвящено визуализации изоповерхности путём построения полигонального приближения для неё [17]. Как правило, сам процесс полигонизации в них производится на этапе препроцессирования и требует значительного времени. Кроме того, количество получаемых полигонов достигает величин, способных перегрузить доступные графические ускорители. В связи с этим в ряде работ были представлены методы сокращения числа полигонов при полигонизации в областях небольшой кривизны изоповерхности и удалённых он наблюдателя её частях. Только небольшое количество из этих работ позволяет производить полигонизацию "на лету", во время визуализации, а не на длительном этапе препроцессирования [17, 18, 116]. Потенциально это делает возможной в некоторых случаях работу с динамически меняющимися данными, визуализацией динамики какого-либо процесса или позволяет пользователю вносить изменения в геометрию поверхности, но рассматривающие такую возможность работы появились сравнительно недавно [107].

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

0.3 Цели и задачи работы

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

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

0.3.1 Контроль количества аппроксимирующих изоповерхность полигонов

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

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

0.3.2 Осуществление полигонизации "на лету"

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

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

0.3.3 Визуализация динамически меняющихся изоповерхностей

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

0.3.4 Повышение качества полигонизации в областях высокой кривизны изоповерхности

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

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

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

0.4 Научная новизна работы

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

- интеграции с методами упрощения построенного полигонального представления для изоповерхности;

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

0.5 Апробация результатов

Основные результаты работы были представлены: на XXXIX Юбилейной научной конференции "Современные проблемы фундаментальной и прикладной физики и математики" Московского физико-технического института (г. Долгопрудный, 1997 г.); на конференции Графикон '98 (г. Москва, 7-11 сентября 1998 г.); на конференции International Conference on Imaging Science, Systems, and Technology (CISST'2000: Las Vegas, Nevada, USA; June 26-29, 2000) на конференции Графикон '2000 (г. Москва, 28 августа-2 сентября 2000 г.); на конференции Shape Modeling International (SMI'2001, Genova, Italy, May 7-11, 2001) на конференции Virtual environment on a PC cluster Workshop 2001, г. Протвино, 22-25 сентября 2001 г.

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

0.6 Структура работы

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

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

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

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

Заключение

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

Базовый метод полигонизации изоповерхности для таким образом заданной скалярной функции состоит в последовательном построении наборов полигонов, аппроксимирующих участок изоповерхности в каждой ячейке сетки. Их совокупность формирует полигональную модель изоповерхности во всём рассматриваемом объёме, дной из основных проблем, ограничивающих применение таких методов полигонизации изоповерхности, вляется большое число полигонов, получаемых для возникающих в приложениях размеров сеток. В • •••• 1 для ешения этой проблемы используется метод адаптивно-иерархической полигонизации. Основная идея этого етода состоит в том, что 8 соседних ячеек исходной сетки могут быть рекурсивно объединены в суперячейку. ри полигонизации участка изоповерхности для суперячейки может быть увеличен размер полигонов и окращено их количество. Ячейки одного размера принадлежат одному уровню иерархии, и его выбор при олитонизации изоповерхности в той или иной области сетки позволяет адаптировать степень детализации олучаемой полигональной модели к критерию выбора уровня иерархии. Как показывают приведённые в главе езультаты визуализации тестовой сцены, использование такого метода позволяет достичь сокращения числа енерируемых треугольников в 3.6 раза при использовании двух уровней иерархии ячеек и в 10 раз при спользовании трёх уровней иерархии. Значительная часть методов, базирующихся на адаптивно-иерархическом одходе к полигонизации изоповерхности, использует структуру восьмидерева (восьмеричного дерева) для хранения информации о ячейках, относящихся к различным уровням иерархии. В частности, эта структура используется для определения факта наличия участка изоповерхности в ячейке. В случае, если построение участков полигональной модели осуществляется во время визуализации, требуется быстрая и эффективная локализация пересекаемых изоповерхностью ячеек. В данной работе для решения этой задачи предлагается альтернативная восьмидереву структура, представляющая собой набор битовых масок, относящихся к каждому из используемых при полигонизации уровней иерархии ячеек. В силу своей организации, решение задачи определения содержащих участок изоповерхности ячеек для такой структуры требует 0(1) операций в отличие от O(logN) операций при использовании восьмидерева, где N — линейный размер сетки.

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

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

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

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

Устранить этот недостаток призван второй из предложенных методов модификации базового полигона. В нём используется информация о направлении нормалей в вершинах базового полигона для построения набора плоскостей, касательных к изоповерхности в этих вершинах. В качестве дополнительных вершин на рёбрах базового полигона используются точки пересечения этих плоскостей с соответствующими гранями ячейки, а внутренняя точка определяется как точка пересечения всех касательных плоскостей. Таким образом, в этом случае для аппроксимации линий излома изоповерхности используются линии пересечения касательных плоскостей. Аналогичные методы ограничиваются только добавлением внутренней точки, причём для получения её положения используется метод Singular Value Decomposition (SVD), предоставляющий некоторое решение и в случае отсутствия общей точки плоскостей. В данной работе предлагается в качестве внутренней точки (в случае отсутствия общей точки всех плоскостей) использовать общую точку для касательных плоскостей, построенных в некотором подмножестве вершин базового полигона. Это позволяет избежать существенных вычислительных затрат, связанных с определением некоторого приближения к общей точке всех касательных плоскостей, в частности, методом SVD. Такой подход позволяет лучше восстанавливать острые рёбра в случае объектов, полученных с использованием конструктивной твёрдотельной геометрии, а в некоторых точно аппроксимировать их.

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

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

Благодарности

Автор благодарит кафедру вычислительной математики МФТИ за содействие в создании диссертационной работы.

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

1. Пасько А.А., Пилюгин В.В., Покровский В.Н. Геометрическое моделирование в задаче анализа функций трех переменных//Сообщение О ИЛИ Р10-86-310, Дубна, 1986.

2. Владимир Рвачёв. Теория R-функций и некоторые приложения//Киев, Наукова Думка, 1982

3. Дональд Э. Кнут. Искусство программирования (в Зх томах)//Москва, изд. Виллиамс, т. 3, ч. 6.3 "Хэширование".

4. Valery Adzhiev, Maxim Kazakov, Alexander Pasko and Vladimir Savchenko. Hybrid system architecture for volume modeling//Computers & Graphics, vol. 24, issue 1, Feb. 2000, pp. 67-78.

5. H. Arata, Y. Takai, N. Takai, T. Yamamoto. Free-form shape modeling by 3D cellular automata//Shape Modeling International '99 Proceedings, IEEE Computer Society Press, 1999, pp. 242-247.

6. R. Avila, L. Sobierajski. A haptic interaction method for volume visualization//IEEE Visualization '96 Proceedings, Yagel R. and Nielson G. (Eds.), IEEE Computer Society Press, 1996, pp. 197-204.

7. Ronald J. Balsys, Kevin G. Suffern. Visualisation of implicit surfaces//Computers & Graphics, vol. 25, 2001, pp. 89-107.

8. J. Baerentzen. Octree-based volume sculpting//lEEE Visualization '98, Late Breaking Hot Topics Proceedings, IEEE Computer Society, 1998, pp. 9-12.

9. A. Barr. Global and local deformations of solid primitives//Computer Graphics (SIGGRAPH'84 Proceedings), vol. 18, no. 3, 1984, pp. 21-30.

10. Alexander G. Belyaev, Alexander A. Pasko, Tosiyasu L. Kunii. Ridges and Ravines on Implicit Surfaces'/Computer Graphics International '98 (June 22-26 1998, Hannover, Germany), IEEE Computer Society, 1998, pp.530-535.

11. James Blinn. A Generalization of Algebraic Surface Drawing//ACM Transations on Graphics, vol. 1, no. 3, 1982, pp. 135-256

12. Jules Bloomenthal. Polygonization of implicit surfaces//Computer-Aided Geometric Design, vol. 5, no. 4, 1988, pp.341-355.

13. Jules Bloomenthal and Brian Wyvill. Interactive Techniques for Implicit Modeling//Computer Graphics, vol. 24, no. 2, 1990, pp. 109-116 (Symposium on Interactive 3D Computer Graphics)

14. Jules Bloomenthal and Ken Shoemake. Convolution Surfaces//Computer Graphics, vol. 25, no. 4, 1991, pp. 109116 (Proceedings of SIGGRAPH 91)

15. J. Bloomenthal, eds. Introduction into implicit surfaces//Morgan Kaufman Publishers, San Francisco, CA, 1997.

16. I. A. Bogaevsky, V. Lang, A. G. Belyaev, and T. L. Kunii. Color Ridges on Implicit Polynomial Surfaces//Technical Report 96-1-014, University of Aizu, Japan, 1996.

17. Ken Brodlie and Jason Wood. Recent Advances in Volume Visualization//Computer Graphics Forum, vol. 20, no. 2, 2001, pp. 125-148

18. Marie-Paule Cani, Samuel Hornus. Subdivision Curve Primitives: a New Solution for Interactive Implicit Modeling//Shape Modelling International'2001 proceedings, IEEE Computer Society, 2001, pp. 82-87.

19. V. Chandru, S. Manohar, C.E. Prakash. Voxel-based modeling for layered manufacturing//IEEE Computer Graphics and Applications, vol. 15, no. 6, 1995, pp. 42-47.

20. Peter Charrot and John Gregory. A Pentagonal Surface Patch for Computer-Aided Geometric Design//Computer-Aided Geomteric Design, vol. 1, no.l, 1984, pp.87-94.

21. E.V. Chernyaev. Marching Cubes 33: construction of topologically correct isosurfaces//Technical report CN/95-17, CERN, 1995.

22. P. Cignoni, P. Marino, C. Montani, E. Puppo, R. Scopigno. Speeding Up Isosurface Extraction Using Interval Trees//IEEE Transactions on Visualization and Computer Graphics, vol. 3, no. 2, 1997.

23. P. Cignoni, F. Ganovelli, C. Montani, R. Scopigno. Reconstruction of Topologically Correct and Adaptive Trilinear Isosurfaces//Computers & Graphics, vol. 24, issue 3, 2000, pp. 399-418.

24. Cline et al. System and method for the display of surface structures contained within the interior region of a solid body//US Patent #4,710,876, Dec. 1, 1987.

25. J. Cohen, A. Varshney, D.Manocha, G. Turk, H. Weber, P. Agarwal, F. P. Brooks Jr. and W. V. Wright. Simplification Envelopes//Computer Graphics (Proc. Ann. Conf. Series (Proc. Siggraph'96)), 1996, pp. 119-128.

26. Steven Colburn. Solid Modeling with Machining Dies and Patterns//SAE Technical Paper Series #900878, Society of Automotive Engineers, Inc., 1990

27. A. Doi and A. Koide. An efficient method of triangulating equi-valued surfaces by using tetrahedral cells//IEICE Trans Commun Elec Inf Syst, vol. E-74, no. 1, 1991, pp.214-224.

28. Robert Drebin, Loren Carpenter, and Pat Hanrahan. Volume Rendering//Computer Graphics, vol. 22, no. 4, 1988, pp.65-74 (Proceedings of SIGGRAPH 88)

29. Martin Durst. Letters: additional reference to marching cubes//Computer graphics, vol. 22, no. 2, 1988, pp. 7273.

30. D. S. Ebert et al. Texturing and Modeling, 2nd edition/VAcademic Press, San Diego, 1998.

31. S. Fang, H. Chen. Hardware accelerated voxelization//International Workshop on Volume Graphics, 24-25 March 1999, Swansea, UK, 1999, pp. 185-203.

32. Gerald Farin. Curves and Surfaces for Computer-Aided Geometric Design: A Practical Guide (3rd edition)//Boston, Academic Press, 1993

33. Luiz de Figueiredo, Jonas de Miranda Gomes, Dimitri Terzopoulos, and Luiz Velho. Physically Based Methods for Polygonization of Implicit Surfaces//Graphics Interface 92, Toronto, Ontario, Canadian Information Processing Society, 1992, pp. 250-257

34. Luiz de Figueiredo and Jonas de Miranda Gomes. Sampling Implicit Objects with Physically Based Particle Systems/ZComputers and Graphics, vol. 20, no. 3, 1996, pp. 363-375

35. Richard Gallagher and Joop Nagtegaal. An Efficient 3D Visualization Technique for Finite Element Models and Other Coarse Volumes//Computer Graphics, vol. 23, no. 4, 1988, pp. 185-195 (Proceedings of SIGGRAPH 88)

36. T.A. Galyean, J.F. Hughes. Sculpting: an interactive volumetric modeling technique//Computer Graphics (SIGGRAPH'91 proceedings), vol. 25, no. 4, 1991, pp. 267-274.

37. Michael Garrity. Raytracing Irregular Volume Data//Computer Graphics, vol. 24, no. 5, 1990, pp. 35-40 (Proceeding of the Workshop on Volume Visualization)

38. Andrew Glassner (ed.). An Introduction to Ray Tracing//London, Academic Press, 1989

39. Andrew Glassner. Principles of Digital Image Synthesis//Morgan Kaufmann Publishers Co., San Francisco, 1995

40. Golub, G. H., and Van Loan, C. F. Matrix Computations, 2nd edition//Baltimore, John Hopkins University Press.

41. L. Grisoni, C. Schlick. Multiresolution representation of implicit objects//Implicit Surfaces'98 Proceedings, Seattle, 1998, pp. 1-10.

42. A Gueziec. Surface Simplification with Variable Tolerance//Proc. Second Int'l Symp. Medical Robotics and Computer Assisted Surgery, 1995.

43. Mark Hall and Joe Warren. Adaptive Polygonization of Implicitly Defined Surfaces//IEEE Computer Graphics and Applications, vol. 10, no. 6, 1990, pp.33-42

44. T. He, L. Hong, A. Varshney, S. Wang. Controlled topology simplification//IEEE Transactions on Visualization and Computer Graphics, vol.2, no. 2, 1996.

45. T. He, A. Kaufman. Collision detection for volumetric objects//IEEE Visualization '97 Proceedings, IEEE Computer Society, 1997, pp. 27-34.

46. Christoph Hoffman and John Hopcroft. The Potential Method for Blending Surfaces and Corners//Geometric Modeling. Edited by Gerald Farin, Philadelphia, SIAM Publications, 1987

47. Christoph Hoffman. Implicit Curves and Surfaces in Computer-Aided Geometric Design//IEEE Computer Graphics and Applications, vol. 13, no. 1, 1993, pp.79-88

48. L. Hong, S. Muraki, A. Kaufman, D. Bartz, T. He. Virtual Voyage: interactive voyage in human colon// Proceeding of the 24th Annual Conference on Computer Graphics and Interactive Techniques, Adison-Wesley Publishing Co., 1997, pp. 27-34.

49. Hugues Hoppe, Tony DeRose, Tom DuChamp, John McDonald, and Werner Stuetzle. Surface Reconstruction from Unorganized Points//Computer Graphics, vol. 26, no.2, 1992, pp. 71-78 (Proceedings of SIGGRAPH 92)

50. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh Optimization//Computer Graphics (Proc. Ann. Conf. Series (Proc. Siggraph'93)), 1993, pp. 19-26.

51. H. Hoppe. Progressive meshes//Computer Graphics (SIGGRAPH 1996 Proceedings), 1996, pp. 99-108.

52. J. Hughes. Scheduled Fourier volume morphing//Proceedings of the 19th annual conference on Computer graphics, ACM Press, 1992, pp. 43-46.

53. HyperFun: Language for F-rep Geometric Modeling//http://www.u-aizu.ac.jp/labs/sw-sm/FrepWWW/HF descr.html, 1998.

54. James Kajiya. Ray Tracing Parametric Patches//Computer Graphics, vol. 16, no. 3, 1982, pp.245-254 (Proceedings of SIGGRAPH 82)

55. Alan Kalvin and Russel Teylor. Superfaces: Polygonal Mesh Simplification with Bounded Error//IEEE Computer Graphics and Applications, vol. 16, no. 3, 1996, pp. 64-77

56. A. Kaufman. Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes//SIGGRAPH'87 Proceedings, 1987, pp. 171-179.

57. A. Kaufman, D. Cohen, R. Yagel. Volume graphics//IEEE Computer, vol. 26, no. 7, 1993, pp.51-64.

58. Maxim Kazakov, Alexander Pasko, Valery Adzhiev. Fast Navigation through an Frep Sculpture Garden//Shape Modeling International '2001 conference proceedings. Genova, Italy, 7-11 May 2001, pp. 104-113.

59. Maxim Kazakov, Alexander Pasko, Valery Adzhiev. Interactive Metamorphosis and Carving in a Multi-Volume Scene//Virtual Environment on a PC Cluster Workshop 200 Г Proceedings. Protvino, Sept. 22-25, Lake Baikal, Sept. 26-29, 2001, pp. 66-77.

60. G. Kisacikoglu. Volumetric rendering and the F-rep of solids for motion picture visual effects//Implicit Surfaces'98 Proceedings, Seattle, 1998, pp. 47-53.

61. Leif P. Kobbelt, Mario Botsch, Ulrich Schwanecke, Hans-Peter Seidel. Feature sensitive surface extraction from volume data//Proceedings of the 2001 conference on Computer Graphics, 2001, pp. 57-66.

62. Eric LaMar, Bernd Hamann, Kenneth I. Joy. High-Quality rendering of Smooth Isosurfaces//Journal of Visualization and Computer Animation, vol. 10, 1999, pp. 79-90.

63. David Laur and Par Hanrahan. Hierarchical Splatting: A Progressive Refinement Algorithm for Volume Rendering//Computer Graphics, vol. 25, no.4, 1991, pp.285-288 (Proceedings of SIGGRAPH 91)

64. A. Lerios, C.D. Garfinkle, M. Levoy. Feature-based volume metamorphosis//SIGGRAPH'95, Computer Graphics Proceedings, 1995, pp. 449-456.

65. Adriano Lopes. Accuracy in scientific visualization//Ph.D. Thesis, 1999.

66. William Lorensen and Harvey Cline. Marching Gubes:A High Resolution 3D Surface Contruction Algorithm//Computer Graphics, vol. 21, no. 4, 1987, pp. 163-169 (Proceedings of SIGGRAPH 87)

67. Luebke, D., and Erikson, C. View-Dependent Simplification of Arbitrary Polygonal Environments//UNC Chapel Hill Computer Science Technical Report TR97-005, 1997.

68. J. McCormack, A. Sherstyuk. Creating and rendering convolution surfaces//Computer Graphics Forum, vol. 17, no. 2, 1998, pp. 113-120.

69. Alan Middletich and Kenneth Sears. Blend Surfaces for Set Theoretic Volume Modeling Systems//Computer Graphics, vol. 26, no. 3, 1985, pp. 161-170 (Proceedings of SIGGRAPH 85)70. http://www.microsoft.com/directx

70. В. K. Natarajan. On generating topologically consistent isosurfaces from uniform samples//The Visual Computer, vol. 11, no. 1, 1994, pp. 52-62.

71. D.R. Ney, E.K. Fishman. Editing tools for 3D medical imaging//IEEE Computer Graphics and Applications, vol. 11, no. 6, 1991, pp. 63-71.

72. G.M. Nielson, T.A. Foley, B. Hamann, D. Lane. Visualizing and modeling scattered multivariate data//IEEE Computer Graphics and Applications, vol. 11, no. 3, 1991, pp. 47-55.

73. G. M. Nielson and B. Hamann. The asymptotic decider: resolving ambiguity in marching cubes//Proc. IEEE Vis' 92, IEEE, 1991, pp. 93-91.

74. Tomoyuki Nishita and Eihachiro Nakamae. A Method for Displaying Metaballs by Using Bezier Clipping//Computer Graphics Forum, vol. 13, 1994, pp. C271-C280 (Proceedings of Eurographics 1994)

75. M. Ohlberger, M. Rumpf. Hierarchical and Adaptive Visualization on Nested Grids//Computing, vol. 59, 1997, pp. 365-385.

76. A. Pasko and V. V. Pilyugin. Geometric Modeling in the Analisys of Trivariate Function//Computers and Graphics, vol. 12, nos. 3/4, pp. 457-465

77. A. Pasko, V. Adzhiev, A. Sourin, V. Savchenko. Function representation in geometric modeling: concepts, implementation and applications//The Visual Computer, vol. 11, no. 8, 1995, pp. 429-446.

78. A. Pasko, A. Savchenko, V. Savchenko. Polygon-to-function conversion for sweeping//The Eurographics/SIGGRAPH Workshop on Implicit Surfaces, J.Hart, K. van Overveld (Eds.), Eindhoven, The Netherlands, October 7-8, 1996, pp. 163-171.

79. A. Pasko, V. Savchenko. Projection operation for multidimensional geometric modeling with real functions//Geometric Modeling: Theory and Practice, W. Strasser, R. Klein, R. Rau (Eds.), Springer-Verlag, Berlin/Heidelberg, 1997, pp. 197-205.

80. Pasko A., Savchenko V., Sourin A. Synthetic carving with implicit surface primitives//Computer Aided Design, vol.33, no.5, 2001, pp.379-388.

81. Ken Perlin and Eric Hoffert. Hypertexture//Computer Graphics, vol. 23, no. 4, 1989, pp.287-296 (Proceedings of SIGGRAPH 89)

82. A. Ricci. A Constructive Geometry for Computer Graphics//The Computer Journal, vol.16, no. 2, 1973, pp. 157160

83. Alyn Rockwood and John Owen. Blending Surfaces in Solid Modeling//Geometric Modeling, edited by Gerald Farin, Philadelphia, SIAM Publications, 1987

84. J. Rossignac, P. Borrel. Multi-Resolution 3D Approximations for Rendering Complex Scenes//Geometric Modeling in Computer Graphics, Springer-Verlag, pp 455-465

85. Paolo Sabella. A Rendering Algorithm for Visualising 3D scalar fields//Computer Graphics, vol. 22, no. 4, 1988, pp. 51-58 (Proceedings of SIGGRAPH 88)

86. George Salmon. A Treatise on Algebraic Geometry of Three Dimensions (vols. 1 and 2), edited by R. Rogers//Chelsea Publichers, New York, 1914

87. Hanan Samet. Design and Analysis of Spatial Data Structures//Reading, MA, Addison-Wesley, 1990

88. V. Savchenko, A. Pasko, O. Okunev, T. Kunii. Function representation of solids reconstructed from scattered surface points and contours//Computer Graphics Forum, vol. 14, no. 4, 1995, pp. 181-188.

89. V. Savchenko, A. Pasko, A. Sourin, T. Kunii. Volume modelling: representations and advanced operations//Computer Graphics International '98 (June 22-26 1998, Hannover, Germany), IEEE Computer Society, Los Alamitos CA, 1998, pp. 4-13.

90. V. Savchenko, A. Pasko. Transformation of functionally defined shapes by extended space mappings//The Visual Computer, vol. 14, nos. 5/6, 1998, pp. 257-270.

91. W. J. Schroeder, J. A. Zarge, and W. E. Lorensen. Decimation of Triangle Meshes//Computer Graphics (Proc. Ann. Conf. Series (Proc. Siggraph'92)), vol. 26, no. 2, 1992, pp. 65-70.

92. Stan Sclaroff and Alex Petland. Generalized Implicit Functions for Computer Graphics//Computer Graphics, vol. 25, no. 4, 1991, pp.65-70

93. Thomas Sederberg. Algebraic Geometry for Surface ans Solid Modeling//Geometric Modeling: Algorithms and Trends, Philadelphia, SIAM Publications, 1987

94. Andrei Sherstyuk. Kernel Functions in Convolution Surfaces: comparative analysis//The Visual Computer, vol. 15, no. 4, 1999

95. Andrei Sherstyuk. Interactive Shape Design with Convolution Surfaces//Proceeding of Shape Modeling International^, 1999, pp. 56-65, Aizu-Wakamatsu, Japan

96. A. Sourin, A. Pasko. Function representation for sweeping by a moving solid//IEEE Transactions on Visualization and Computer Graphics, vol. 2, no. 1, 1996, pp. 11-18.

97. Bart Stander and John Hart. Topologically Garanteed Blobby Surface Polygonization// Computer Graphics, 1997 (Proceedings of SIGGRAPH 97)

98. N. Stolte, A. Kaufman. Parallel spatial enumeration of implicit surfaces using interval arithmetic for octree generation and its direct visualization//Implicit Surfaces'98 Proceedings, Seattle, USA, 1998, pp. 81-87.

99. Philip M. Sutton and Charles D. Hansen. Accelerated Isosurface Extraction in Time-Varying Fields//IEEE Transactions on Visualization and Computer Graphics, vol. 6, no. 2, 2000108.http://www.terarecon.com/3dproducts.shtml

100. Greg Turk. Re-tiling polygonal surfaces//Computer Graphics (SIGGRAPH '92 Proceedings), vol. 26, no. 2, 1992, pp. 55-64.

101. K.J. Udupa, D. Odhner. Fast visualization, manipulation, and analysis of binary volumetric objects//lEEE Computer Graphics and Applications, vol. 11, no. 6, 191, pp. 53-62.

102. Craig Upson and Michael Keeler. V-Buffer: Visible Volume Rendering//Computer Graphics, vol. 22, no.4, 1988, pp. 59-64 (Proceedings of SIGGRAPH 88)

103. Michael Vannier, Jeffrey Marsh, and James Warren. Three-Dimensional Computer Graphics for Craniofacial Surgical Planning and Evaluation//Computer Graphics, vol. 17, no. 3, 1983, pp. 263-273 (Proceedings of SIGGRAPH 83)

104. S. Vyatkin, B. Dolgovesov, A. Yesin, R. Scherbakov, S. Chizhik. Voxel Volumes: volume-oriented visualization system//Shape Modeling International '99, IEEE Computer Society Press, 1999, pp.234-241.

105. S. Wang and A. Kaufman. Volume sculpting//Symposium on Interactive 3D Graphics, ACM Press, 1995, pp. 151-156.

106. Alan Watt. 3D Computer Graphics//Addison-Wesley Publishing Company, 1993.

107. R. Westermann, L. Kobbelt, T. Ertl. Real-time Exploration of Regular Volume Data by Adaptive Reconstruction of Iso-Surfaces//The Visual Computer, vol. 15, no. 2, 1999, pp. 100-111.

108. Lee Westover. Interactive Volume Rendering//Proceedings of the 1989 Chapel Hill Workshop on Colume Visualization, 1989, pp. 9-16

109. Lee Westover. Footprint Evaluation for Volume Rendering//Computer Graphics, vol. 24, no. 4, 1990, pp.367-376 (Proceedings of SIGGRAPH 90)

110. Hassler Whitney. Elementary Structure of Real Algebraic Varieties//Annals of Mathematics, vol.66, no. 3, 1957, pp. 545-556

111. Jane Wilhelnis and Allen van Gelder. A Coherent Projection Approach for Dsirect Volume rendering//Computer Graphics, vol. 25, no. 4, 1991, pp. 275-284 (Proceedings of SIGGRAPH 91)

112. Andrew Witkin and Paul Heckbert. Using Particles to Sample and Control Implicit Surfaces//Computer Graphics, Annual Conference Series, 1994, pp. 269-278 (Proceedings of SIGGRAPH 94)

113. J. Woodwark. Blends in geometric modeling//The Mathematics of Surfaces II, R. Martin (Ed.), Clarendon Press, Oxford UK, 1987, pp. 255-297.

114. Geoff Wyvill, Craig McPheeters, and Brian Wyvill. Data Structure for Soft Objects//The Visual Computer, vol. 2, no. 4, 1986, pp.227-234

115. J. Xia and A. Varshney. Dynamic View-Dependent Simplification for Polygonal Models//Proceedings of the IEEE Visualization '96 Oct 27 Nov 1, 1996, San Francisco, CA, pp 327 - 334.

116. J. Xia, J. El-Sana, and A. Varshney. Adaptive Real-Time Level-of-Detail-Based Rendering for Polygonal Models//IEEE Transactions on Visualization and Computer Graphics, vol. 3, no. 2, June 1997, pp 171 183.

117. Nt/sec Na/sec Nd/sec ■ Nu/sec