Novosibirsk, Russia, May, 30 – June, 4, 2011

International Conference
"Modern Problems of Applied Mathematics and Mechanics: Theory, Experiment and Applications", devoted to the 90th anniversary of professor Nikolai N. Yanenko

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

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

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

Abstracts file: Vengersky.doc
Full text file: Vengersky_intervalnie_metody_peresechenia_2.pdf


To reports list
© 1996-2019, Institute of computational technologies of SB RAS, Novosibirsk