Новосибирск, Россия, 30 мая – 4 июня 2011 г.

Международная конференция
«Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященная 90-летию со дня рождения академика Н.Н. Яненко
№ гос. регистрации 0321101160, ISBN 978-5-905569-01-2

Венгерский П.С.  

Эффективные интервальные алгоритмы нахождения пересечений поверхностей в компьютерной графике

     Одной  из основных задач компьютерной графики является аппроксимация формы поверхности или кривой набором простых фигур. Задача сильно усложняется при комбинации поверхностей, когда результат не представляется явно заданием функции результата. Прямым методом решения такого рода задач является полный перебор всех пикселей, которые удовлетворяют заданному условию. Используя методы интервального анализа, можно достигнуть улучшения быстродействия алгоритмов, поскольку они работают не со всеми пикселями из рассмотренной области определения, а только с граничными пикселями этой области.
     Общая схема алгоритмов включает следующие этапы:
1. Нахождение множества аппроксимирующих интервалов;
2. Нахождение пересечения неявной кривой (заданное условие) с границами интервалов;
3. Глобальная параметризация;
4. Уточнение решения задачи;
5. Визуализация результата.
     На этапе уточнения решения задачи использовались интервальные итерационные методы Ньютона и методы типа Рунге. Проведено сравнение эффективности рассмотренных методов, а также быстродействия разработанных алгоритмов с другими подходами решения такого рода задач. Разработано программное обеспечения для реализации этих алгоритмов.
 

Файл тезисов: Vengersky.doc
Файл с полным текстом: Vengersky_intervalnie_metody_peresechenia_2.pdf


К списку докладов
© 1996-2019, Институт вычислительных технологий СО РАН, Новосибирск