An algorithm for detection of intersections between polygonal objects by oriented bounding boxes

Authors

  • A.A. Zakharov
  • S.S. Sadykov

Keywords:

пересечения объектов
ограничивающие объемы
полигональные объекты
автоматизированное проектирование
итерационные алгоритмы
математическое моделирование
компьютерная графика

Abstract

The problem on detection of intersections between objects with the use of bounding boxes is considered. The examples of bounding boxes most frequently used in practice are briefly described. Several criteria of accuracy for approximation and rate of detection are discussed. An improved algorithm for detection of intersection by oriented bounding boxes is proposed.

New computational technologies

Downloads

Published

2003-06-05

Issue

Vol. 4 (2003): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

A.A. Zakharov

Vladimir State University,
Murom Institute

S.S. Sadykov

Vladimir State University,
Murom Institute

References

  1. Захаров А.А. Масанов А.Н. Некоторые задачи представления местности для тренажеров наземного транспорта. Деп. в ВИНИТИ РАН 28.03.02. № 561-B2002.
  2. Препарата Ф., Шеймос М. Вычислительная геометрия. М.: Мир, 1989.
  3. Садыков С.С., Захаров А.А. Исследование алгоритмов генерации изображений в тренажерных системах // Данные, информация и их обработка. М.: Телеком, 2002. 38-42.
  4. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. М.: ДИАЛОГ-МИФИ, 2000.
  5. Эйнджел Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGl. М.: Издательский дом «Вильямс», 2001.
  6. Компьютерные технологии в науке, производстве, социальных и экономических процессах. Тр. III Междунар. науч.-практ. конф. Новочеркасск: ООО НПО «ТЕМП», 2002.
  7. Проблемы передачи и обработки информации в сетях и системах телекоммуникаций. Тр. Междунар. науч.-техн. конф. Рязань: РГРА, 2002.
  8. Cohen J., Lin M., Manocha D., Ponamgi M. I-collide: an interactive and exact collision detection system for large-scale environments // Proc. of ACM Interactive 3D Graphics Conference. New York: ACM SIGGRAPH, 1995. 189-196.
  9. Gottschalk S., Lin M., Manocha D. Obb-tree: a hierarachical structure for rapid interference detection // Proc. of ACM Siggraph-96. New York: ACM SIGGRAPH, 1996. 171-180.
  10. Hopcroft J.E., Schwartz J.T., Sharir M. Efficient detection of intersections among spheres // The Intern. J. of Robotics Research. 1983. 4, N 4. 77-80.
  11. Hubbard P.M. Collision detection for interactive graphics applications // IEEE Trans. on Visualization and Computer Graphics. 1995. 3, N 1. 218-230.
  12. Hubbard P.M. Approximating polyhedra with spheres for time-critical collision detection // ACM Trans. on Graphics. 1996. N 3. 179-210.
  13. Klosowski J. Held M., Mitchell J.S. B., Sowizral H., Zikan K. Efficient collision detection using bounding volume hierarchies of k-dops // Proc. of ACM Siggraph-96. New York: ACM SIGGRAPH, 1996. 151.
  14. Weghorst H., Hooper G., Greenberg D. Improved computational methods for ray tracing // ACM Trans. on Graphics. 1984. 3, N 1. 52-69.