МЕТОД ГЕОМЕТРИЧЕСКОГО УПРОЩЕНИЯ 3D ПОЛИГОНАЛЬНЫХ ОБЪЕКТОВ
В.Т. Тозик, А.В. Меженин
6 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК 004.92
МЕТОД ГЕОМЕТРИЧЕСКОГО УПРОЩЕНИЯ 3D ПОЛИГОНАЛЬНЫХ ОБЪЕКТОВ
В.Т. Тозик, А.В. Меженин
В статье рассматривается метод геометрического упрощения 3D полигональных моделей объектов с целью сокращения объема данных, что приводит к повышению скорости процессов передачи и визуализации. Предлагаемый метод упрощения трехмерных полигональных объектов использует операции свертывания ребер. Дополнительно выполняется проверка, направленная на устранение эффекта вырожденной полигональной сетки. Для оценки качества упрощения полигональной сети предлагается использовать размерность Хаусдорфа. Ключевые слова: многомасштабное представление, упрощение сеток.
Введение
Одной из основных проблем передачи и отображения трехмерных данных является передача больших объемов данных, необходимых для описания сложных трехмерных моделей в условиях ограничения пропускной способности каналов передачи данных, таких как Интернет, космическая связь и т.д. [1]. Упрощение сложных 3D объектов является важным направлением исследований в компьютерной графике. Уменьшение уровней детализации Level of Detail (LOD) упрощает не только задачу передачи данных, но и задачу визуализации, особенно для небольших дисплеев мобильных устройств и специальной аппаратуры.
Большинство итерационных алгоритмов упрощения полигональных моделей можно разделить на три категории: прореживание вершин, свертывание ребер, прореживание граней [2, 3] (рис. 1).
v1 t1 er t2 v2
Рис. 1. Прореживание вершин и свертывание ребер
Алгоритм кластеризации вершин относится к категории прореживания вершин и состоит в объединении вершин, находящихся в одном кластере пространства, в одну. Его достоинство – высокая скорость, а недостаток в некоторых случаях – нарушение топологии получаемых моделей. Более точно топологию модели передает алгоритм прореживания вершин, выполняемый в несколько проходов. На каждом этапе происходит удаление вершин, расположенных на расстоянии меньше заданного от усредненной плоскости соседних вершин. Одна из проблем, возникающая при реализации алгоритма – исчезновение граней, принадлежащих удаляемым вершинам. При этом могут образоваться разрывы, которые необходимо заполнить, выполняя операции триангуляции, что требует дополнительного времени.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
81
МЕТОД ГЕОМЕТРИЧЕСКОГО УПРОЩЕНИЯ 3D ПОЛИГОНАЛЬНЫХ ОБЪЕКТОВ
Алгоритмы, основанные на свертывании ребер, можно рассматривать как частный случай удаления вершин, однако они не требуют выполнения дополнительных операций триангуляции. Поэтому их реализация дает хорошие результаты с точки зрения качества и быстродействия. Свертывание ребра представляет собой слияние двух вершин, образующих ребро, в одну. При этом в общем случае происходит удаление двух треугольных ячеек. Последовательность свертывания ребер определяется мерой ошибки, которая отражает локальное геометрическое отклонение ячеек. Способы вычисления этой ошибки определяют различие между алгоритмами этого класса.
Известны следующие меры ошибки, используемые для выбора стратегии при свертывании ребра: – определение среднего расстояния между новыми треугольниками и типовыми точ-
ками на исходной модели; – нахождение величины допуска как выпуклой комбинации сфер, расположенных в
каждой вершине упрощения. Выбор граней основывается на самой малой длине, а новая вершина позиционируется таким образом, что новая поверхность будет гарантированно лежать в пределах этого допуска; – поддержка связи между точками исходной модели и соответствующими окрестностями на упрощенной модели.
Метод кластеризации ограничивающего объема и операции свертывания ребер
Предлагаемый авторами подход к задаче упрощения трехмерных полигональных объектов и организации прогрессивной сетки основан на кластеризации ограничивающего объема и операциях свертывания ребер. Очевидно, что в первую очередь необходимо обрабатывать только те вершины, которые не влияют существенно на форму объекта. Вершины, в которых поверхность объекта существенно меняется, будем называть опорными. Такие вершины выделяются на стадии предварительной обработки и постоянно присутствуют при синтезе объекта. Выделение опорных вершин производится следующим образом.
Шаг 1. Строится ограничивающий объем, представляющий собой параллелепипед, стороны которого параллельны осям координат. Координаты вершин параллелепипеда находятся как значения минимальных и максимальных координат вершин объекта по осям:
xmin min(x1, x2 ,..., xn ) , xmax max( x1, x2 ,..., xn ) ,
ymin min( y1, y2 ,..., yn ) , ymax max( y1, y2 ,..., yn ) ,
zmin min(z1, z2 ,..., zn ) , zmax max( z1, z2 ,..., zn )
Шаг 2. Координаты ограничивающих объемов находятся из предыдущих значений следующим образом:
xck
xmin xmax 2k x
,
yck
ymin ymax 2k y
,
zck
zmin zmax , 2k z
где kx , ky , kz – количество разбиений по осям X, Y, Z.
Шаг 3. Определяется принадлежность вершин к каждой области разбиения путем
проверки условий
xmin xi xmax , ymin yi ymax , zmin zi zmax .
Шаг 4. Определяется квадрат расстояния от вершин области до центров областей разбиения:
d
2 i
(xck 1
xi )2
( yck 1
yi )2
(zck 1
zi )2 .
82 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
В.Т. Тозик, А.В. Меженин
Шаг 5. Находятся минимальные и максимальные квадраты расстояний. Вершины, расположенные на минимальном и максимальном расстояниях, удаляться не будут.
Дальнейшее упрощение основано на свертывании ребер. В качестве критериев используются угол между нормалями граней и изменение площади свертываемой грани. На каждом шаге производятся следующие действия. – Вычисляется показатель ошибки для каждой операции свертывания ребра и выпол-
няется упорядочивание по приоритетам. – Выбирается ребро er (v0, v) v с минимальной величиной ошибки и заменяется на
v . Во время этой операции треугольники, имеющие общие ребра с er , становятся сингулярными и удаляются. Оставшиеся грани, инцидентные вершине v0 , модифи– цПмиоерсрутеьюсчтоисштяыитбвакакеиитмссяхолбворепалзыиовчмаи,ннчиатяоошвeсиеб,(кчvит0о,сvбв1ы)ерлвтоктсиувярчзеаабснртоаьсоevrч0(еv,р1зе,адvм)ие,нкяоеvтт.осДяраонябаасvввл.яязеатнсаясствоеир-шиной v1 , и модифицируется очередь по приоритетам. В результате формируется прогрессивная структура сети.
Когда происходит свертывание произвольного ребра er (v0 , v) v , две грани, примыкающие к ребру, становятся выродившимися. Свертывание ребра er {v0 , v} приводит к отображению треугольника t (v0 , v1, v2 ) в треугольник t ' (v, v1, v2 ) . Ребра {v0 , v1} и {v0 , v2}треугольника t (v0 , v1, v2 ) вырождаются (рис. 2).
1-ый этап: схлопывание ребер
v0
er
n t
'
t'
v 2-ой этап: вычисление ошибки v1
v0 t
er
v
nt v1 t
v3-й этап:
обработка граничных граней
2
v1 e (v1,v2 )
e (v2 ,v1)
e1 v2 v0
e1'
v
v2
0 e2 e2'
v3
Рис. 2. Свертывание ребер
В результате смещения оставшихся граней происходит изменение геометрической формы поверхности. Величина этого изменения может характеризоваться, с одной стороны, углом поворота грани t (v0 , v1, v2 ) , с другой стороны, площадью треуголь-
ника t'' (v0 , v, v1) . Чем больше та или другая величина, тем больше изменение формы
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
83
МЕТОД ГЕОМЕТРИЧЕСКОГО УПРОЩЕНИЯ 3D ПОЛИГОНАЛЬНЫХ ОБЪЕКТОВ
поверхности. Таким образом, для грани t (v0 , v1, v2 ) величина ошибки может характеризоваться произведением этих величин:
Qt A ,
где
1a 2
b , a = v0 – v1, b = v1 – v,
– угол между векторами нормалей двух тре-
угольников. Суммарная величина ошибки er (v0, v) v может быть определена как
сумма ошибок сверток всех граней, примыкающих к v0 : Cost(er )
Qt .
t (v0 ,v) v
Граничные грани требуют специальной обработки для сохранения формы модели.
РоСeдеобнорут(аvв,1ев,треvсар2тсш)вп.еиоРннленуобожр,неоаенснeлг1ыриеан{свvивд0ецо,реvлт1ьы}eгвпрааое(нтвvсио,ярцv1аы)чe,идивеа(леvрит2есм,бvяр1н)ана,,а
две категории: ребра, которые имеют
имеющие две вершины на границе
угол
при
свертывании
e
(v1, v2 ) .
то ребро e2 {v2 , v3} повернется на
угол 0 , при этом получается 0 . В результате схлопывания ребра e {v0 , v} тре-
угольСнивекрtтыв(аvн0 ,иvе1,рvе2 )брмаожe ет(пvеs ,рvеtк)рытvьt
грань (рис. 2). с конечной вершиной,
находящейся
на
грани-
це, не требует специальной обработки. Однако, если начальная вершина находится на
границе, то свертывание ребра исказит границу, и это необходимо учитывать.
Ребро e {v0 , v1 ) может быть свернуто в вершины v1 или v2 , но лучший резуль-
тат будет при сворачивании в v1 . Для достижения этого необходимо измерить угол и
0 между ребрами e1 и e1 ' и e2 и e2 ' соответственно.
Результаты апробации алгоритма
На рис. 3 представлены результаты апробации предлагаемого метода. Исходная
полигональная модель содержит 3679 граней, т.е. 100% (a), а результаты упрощения – 2856 граней, т.е. 80% (б), и 2441 грань, т.е. 60% (в). На рис. 3 видно сохранение топологии, отсутствие разрывов и вырожденных граней.
Для оценки качества работы алгоритма и сравнения с другими известными алго-
ритмами предлагается вычислять ошибку аппроксимации между двумя полигональны-
ми моделями, которая базируется на вычислении расстояния аппроксимации (approximate distance) и может быть определена следующим образом. Дана точка p и поверх-
ность S. Определим расстояние e(p, S), и расстояние между двумя поверхностями S1, S2
как e( p, S)
min d ( p, p' ) , E(S1, S2 )
p' S
max p S1
e(
p,
S2
)
,
где
d()–
евклидово
расстояние
между
двумя точками в E 3 . Необходимо отметить, что это расстояние несимметрично. Суще-
ствуют поверхности такие, что E(S1, S2 ) E(S2 , S1) . Хаусдорфово расстояние (двустороннее) может быть получено как максимум E(S1, S2 ) и E(S2 , S1) . Среднее (mean) Em расстояние между двумя поверхностями можно определить как интеграл по поверхно-
сти, определенный областью S1 :
1
Em (S1, S2 )
S1
e( p, S2 )ds .
S1
На рис. 4 приведены графики средней ошибки (расстояния аппроксимации) при
уменьшении количества граней тестовой полигональной модели для разных алгорит-
мов упрощения [2, 3]. Разработанный алгоритм показал лучшие результаты.
84 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
В.Т. Тозик, А.В. Меженин
а Em Em
б Рис. 3. Результат работы алгоритма
в
Число полигонов
Рис. 4. Графики средней ошибки
Заключение
В работе предложен алгоритм, обладающий следующими характеристиками. – Алгоритм алгоритмически сохраняет визуально важные особенности полигональ-
ной модели лучшим образом по сравнению с известными алгоритмами упрощения. – Предложенный способ накопления ошибки не требует сохранения истории геомет-
рических изменений, что позволяет эффективно упрощать большие полигональные модели, не требуя больших объемов памяти. – Алгоритм в вычислительном отношении показывает лучшие результаты по сравнению с известными алгоритмами, основанными на свертывании ребер. – Алгоритм автоматически предотвращает появление искажений типа сверток.
Литература
1.Парамонов П.П., Видин Б.В., Меженин А.В., Тозик В.Т. Методы представления сложных полигональных моделей в графических системах, работающих в режиме реального времени / // Изв. вузов. Приборостроение. – 2006. – Т. 49. – № 6. – С. 17–19.
2. Hoppe H. Progressive Meshes // Computer Graphics. – Vol. 30. –SIGGRAPH 96.
3.Garland M. Heckbert P. Multiresolution Modeling for Fast Rendering // Proceedings of Graphics Interface ’94. – 1994.
Тозик Вячеслав Трофимович – Санкт-Петербургский государственный университет информаци-
онных технологий, механики и оптики, кандидат технических
наук, доцент, заведующий кафедрой, tozik@mail.ifmo.ru
Меженин Александр Влади- – Санкт-Петербургский государственный университет информаци-
мирович
онных технологий, механики и оптики, кандидат технических
наук, доцент, mejenin@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
85
6 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК 004.92
МЕТОД ГЕОМЕТРИЧЕСКОГО УПРОЩЕНИЯ 3D ПОЛИГОНАЛЬНЫХ ОБЪЕКТОВ
В.Т. Тозик, А.В. Меженин
В статье рассматривается метод геометрического упрощения 3D полигональных моделей объектов с целью сокращения объема данных, что приводит к повышению скорости процессов передачи и визуализации. Предлагаемый метод упрощения трехмерных полигональных объектов использует операции свертывания ребер. Дополнительно выполняется проверка, направленная на устранение эффекта вырожденной полигональной сетки. Для оценки качества упрощения полигональной сети предлагается использовать размерность Хаусдорфа. Ключевые слова: многомасштабное представление, упрощение сеток.
Введение
Одной из основных проблем передачи и отображения трехмерных данных является передача больших объемов данных, необходимых для описания сложных трехмерных моделей в условиях ограничения пропускной способности каналов передачи данных, таких как Интернет, космическая связь и т.д. [1]. Упрощение сложных 3D объектов является важным направлением исследований в компьютерной графике. Уменьшение уровней детализации Level of Detail (LOD) упрощает не только задачу передачи данных, но и задачу визуализации, особенно для небольших дисплеев мобильных устройств и специальной аппаратуры.
Большинство итерационных алгоритмов упрощения полигональных моделей можно разделить на три категории: прореживание вершин, свертывание ребер, прореживание граней [2, 3] (рис. 1).
v1 t1 er t2 v2
Рис. 1. Прореживание вершин и свертывание ребер
Алгоритм кластеризации вершин относится к категории прореживания вершин и состоит в объединении вершин, находящихся в одном кластере пространства, в одну. Его достоинство – высокая скорость, а недостаток в некоторых случаях – нарушение топологии получаемых моделей. Более точно топологию модели передает алгоритм прореживания вершин, выполняемый в несколько проходов. На каждом этапе происходит удаление вершин, расположенных на расстоянии меньше заданного от усредненной плоскости соседних вершин. Одна из проблем, возникающая при реализации алгоритма – исчезновение граней, принадлежащих удаляемым вершинам. При этом могут образоваться разрывы, которые необходимо заполнить, выполняя операции триангуляции, что требует дополнительного времени.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
81
МЕТОД ГЕОМЕТРИЧЕСКОГО УПРОЩЕНИЯ 3D ПОЛИГОНАЛЬНЫХ ОБЪЕКТОВ
Алгоритмы, основанные на свертывании ребер, можно рассматривать как частный случай удаления вершин, однако они не требуют выполнения дополнительных операций триангуляции. Поэтому их реализация дает хорошие результаты с точки зрения качества и быстродействия. Свертывание ребра представляет собой слияние двух вершин, образующих ребро, в одну. При этом в общем случае происходит удаление двух треугольных ячеек. Последовательность свертывания ребер определяется мерой ошибки, которая отражает локальное геометрическое отклонение ячеек. Способы вычисления этой ошибки определяют различие между алгоритмами этого класса.
Известны следующие меры ошибки, используемые для выбора стратегии при свертывании ребра: – определение среднего расстояния между новыми треугольниками и типовыми точ-
ками на исходной модели; – нахождение величины допуска как выпуклой комбинации сфер, расположенных в
каждой вершине упрощения. Выбор граней основывается на самой малой длине, а новая вершина позиционируется таким образом, что новая поверхность будет гарантированно лежать в пределах этого допуска; – поддержка связи между точками исходной модели и соответствующими окрестностями на упрощенной модели.
Метод кластеризации ограничивающего объема и операции свертывания ребер
Предлагаемый авторами подход к задаче упрощения трехмерных полигональных объектов и организации прогрессивной сетки основан на кластеризации ограничивающего объема и операциях свертывания ребер. Очевидно, что в первую очередь необходимо обрабатывать только те вершины, которые не влияют существенно на форму объекта. Вершины, в которых поверхность объекта существенно меняется, будем называть опорными. Такие вершины выделяются на стадии предварительной обработки и постоянно присутствуют при синтезе объекта. Выделение опорных вершин производится следующим образом.
Шаг 1. Строится ограничивающий объем, представляющий собой параллелепипед, стороны которого параллельны осям координат. Координаты вершин параллелепипеда находятся как значения минимальных и максимальных координат вершин объекта по осям:
xmin min(x1, x2 ,..., xn ) , xmax max( x1, x2 ,..., xn ) ,
ymin min( y1, y2 ,..., yn ) , ymax max( y1, y2 ,..., yn ) ,
zmin min(z1, z2 ,..., zn ) , zmax max( z1, z2 ,..., zn )
Шаг 2. Координаты ограничивающих объемов находятся из предыдущих значений следующим образом:
xck
xmin xmax 2k x
,
yck
ymin ymax 2k y
,
zck
zmin zmax , 2k z
где kx , ky , kz – количество разбиений по осям X, Y, Z.
Шаг 3. Определяется принадлежность вершин к каждой области разбиения путем
проверки условий
xmin xi xmax , ymin yi ymax , zmin zi zmax .
Шаг 4. Определяется квадрат расстояния от вершин области до центров областей разбиения:
d
2 i
(xck 1
xi )2
( yck 1
yi )2
(zck 1
zi )2 .
82 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
В.Т. Тозик, А.В. Меженин
Шаг 5. Находятся минимальные и максимальные квадраты расстояний. Вершины, расположенные на минимальном и максимальном расстояниях, удаляться не будут.
Дальнейшее упрощение основано на свертывании ребер. В качестве критериев используются угол между нормалями граней и изменение площади свертываемой грани. На каждом шаге производятся следующие действия. – Вычисляется показатель ошибки для каждой операции свертывания ребра и выпол-
няется упорядочивание по приоритетам. – Выбирается ребро er (v0, v) v с минимальной величиной ошибки и заменяется на
v . Во время этой операции треугольники, имеющие общие ребра с er , становятся сингулярными и удаляются. Оставшиеся грани, инцидентные вершине v0 , модифи– цПмиоерсрутеьюсчтоисштяыитбвакакеиитмссяхолбворепалзыиовчмаи,ннчиатяоошвeсиеб,(кчvит0о,сvбв1ы)ерлвтоктсиувярчзеаабснртоаьсоevrч0(еv,р1зе,адvм)ие,нкяоеvтт.осДяраонябаасvввл.яязеатнсаясствоеир-шиной v1 , и модифицируется очередь по приоритетам. В результате формируется прогрессивная структура сети.
Когда происходит свертывание произвольного ребра er (v0 , v) v , две грани, примыкающие к ребру, становятся выродившимися. Свертывание ребра er {v0 , v} приводит к отображению треугольника t (v0 , v1, v2 ) в треугольник t ' (v, v1, v2 ) . Ребра {v0 , v1} и {v0 , v2}треугольника t (v0 , v1, v2 ) вырождаются (рис. 2).
1-ый этап: схлопывание ребер
v0
er
n t
'
t'
v 2-ой этап: вычисление ошибки v1
v0 t
er
v
nt v1 t
v3-й этап:
обработка граничных граней
2
v1 e (v1,v2 )
e (v2 ,v1)
e1 v2 v0
e1'
v
v2
0 e2 e2'
v3
Рис. 2. Свертывание ребер
В результате смещения оставшихся граней происходит изменение геометрической формы поверхности. Величина этого изменения может характеризоваться, с одной стороны, углом поворота грани t (v0 , v1, v2 ) , с другой стороны, площадью треуголь-
ника t'' (v0 , v, v1) . Чем больше та или другая величина, тем больше изменение формы
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
83
МЕТОД ГЕОМЕТРИЧЕСКОГО УПРОЩЕНИЯ 3D ПОЛИГОНАЛЬНЫХ ОБЪЕКТОВ
поверхности. Таким образом, для грани t (v0 , v1, v2 ) величина ошибки может характеризоваться произведением этих величин:
Qt A ,
где
1a 2
b , a = v0 – v1, b = v1 – v,
– угол между векторами нормалей двух тре-
угольников. Суммарная величина ошибки er (v0, v) v может быть определена как
сумма ошибок сверток всех граней, примыкающих к v0 : Cost(er )
Qt .
t (v0 ,v) v
Граничные грани требуют специальной обработки для сохранения формы модели.
РоСeдеобнорут(аvв,1ев,треvсар2тсш)вп.еиоРннленуобожр,неоаенснeлг1ыриеан{свvивд0ецо,реvлт1ьы}eгвпрааое(нтвvсио,ярцv1аы)чe,идивеа(леvрит2есм,бvяр1н)ана,,а
две категории: ребра, которые имеют
имеющие две вершины на границе
угол
при
свертывании
e
(v1, v2 ) .
то ребро e2 {v2 , v3} повернется на
угол 0 , при этом получается 0 . В результате схлопывания ребра e {v0 , v} тре-
угольСнивекрtтыв(аvн0 ,иvе1,рvе2 )брмаожe ет(пvеs ,рvеtк)рытvьt
грань (рис. 2). с конечной вершиной,
находящейся
на
грани-
це, не требует специальной обработки. Однако, если начальная вершина находится на
границе, то свертывание ребра исказит границу, и это необходимо учитывать.
Ребро e {v0 , v1 ) может быть свернуто в вершины v1 или v2 , но лучший резуль-
тат будет при сворачивании в v1 . Для достижения этого необходимо измерить угол и
0 между ребрами e1 и e1 ' и e2 и e2 ' соответственно.
Результаты апробации алгоритма
На рис. 3 представлены результаты апробации предлагаемого метода. Исходная
полигональная модель содержит 3679 граней, т.е. 100% (a), а результаты упрощения – 2856 граней, т.е. 80% (б), и 2441 грань, т.е. 60% (в). На рис. 3 видно сохранение топологии, отсутствие разрывов и вырожденных граней.
Для оценки качества работы алгоритма и сравнения с другими известными алго-
ритмами предлагается вычислять ошибку аппроксимации между двумя полигональны-
ми моделями, которая базируется на вычислении расстояния аппроксимации (approximate distance) и может быть определена следующим образом. Дана точка p и поверх-
ность S. Определим расстояние e(p, S), и расстояние между двумя поверхностями S1, S2
как e( p, S)
min d ( p, p' ) , E(S1, S2 )
p' S
max p S1
e(
p,
S2
)
,
где
d()–
евклидово
расстояние
между
двумя точками в E 3 . Необходимо отметить, что это расстояние несимметрично. Суще-
ствуют поверхности такие, что E(S1, S2 ) E(S2 , S1) . Хаусдорфово расстояние (двустороннее) может быть получено как максимум E(S1, S2 ) и E(S2 , S1) . Среднее (mean) Em расстояние между двумя поверхностями можно определить как интеграл по поверхно-
сти, определенный областью S1 :
1
Em (S1, S2 )
S1
e( p, S2 )ds .
S1
На рис. 4 приведены графики средней ошибки (расстояния аппроксимации) при
уменьшении количества граней тестовой полигональной модели для разных алгорит-
мов упрощения [2, 3]. Разработанный алгоритм показал лучшие результаты.
84 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
В.Т. Тозик, А.В. Меженин
а Em Em
б Рис. 3. Результат работы алгоритма
в
Число полигонов
Рис. 4. Графики средней ошибки
Заключение
В работе предложен алгоритм, обладающий следующими характеристиками. – Алгоритм алгоритмически сохраняет визуально важные особенности полигональ-
ной модели лучшим образом по сравнению с известными алгоритмами упрощения. – Предложенный способ накопления ошибки не требует сохранения истории геомет-
рических изменений, что позволяет эффективно упрощать большие полигональные модели, не требуя больших объемов памяти. – Алгоритм в вычислительном отношении показывает лучшие результаты по сравнению с известными алгоритмами, основанными на свертывании ребер. – Алгоритм автоматически предотвращает появление искажений типа сверток.
Литература
1.Парамонов П.П., Видин Б.В., Меженин А.В., Тозик В.Т. Методы представления сложных полигональных моделей в графических системах, работающих в режиме реального времени / // Изв. вузов. Приборостроение. – 2006. – Т. 49. – № 6. – С. 17–19.
2. Hoppe H. Progressive Meshes // Computer Graphics. – Vol. 30. –SIGGRAPH 96.
3.Garland M. Heckbert P. Multiresolution Modeling for Fast Rendering // Proceedings of Graphics Interface ’94. – 1994.
Тозик Вячеслав Трофимович – Санкт-Петербургский государственный университет информаци-
онных технологий, механики и оптики, кандидат технических
наук, доцент, заведующий кафедрой, tozik@mail.ifmo.ru
Меженин Александр Влади- – Санкт-Петербургский государственный университет информаци-
мирович
онных технологий, механики и оптики, кандидат технических
наук, доцент, mejenin@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
85