BOXTREE: A hierarchical representation for surfaces in 3D

Gill Barequet, Bernard Chazelle, Leonidas J. Guibas, Joseph S.B. Mitchell, Ayellet Tal

Research output: Contribution to journalArticle

86 Scopus citations

Abstract

We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing and collision detection. It is simple and robust, and requires minimal space. In situations where storage is at a premium, boxtrees are effective alternatives to octrees and BSP trees. They are also more flexible and efficient than R-trees, and nearly as simple to implement.

Original languageEnglish (US)
Pages (from-to)387-396
Number of pages10
JournalComputer Graphics Forum
Volume15
Issue number3
DOIs
StatePublished - Jan 1 1996

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design

Keywords

  • Collision detection
  • Hierarchical data structures
  • Ray shooting

Fingerprint Dive into the research topics of 'BOXTREE: A hierarchical representation for surfaces in 3D'. Together they form a unique fingerprint.

  • Cite this