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 journalArticlepeer-review

102 Scopus citations


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
Issue number3
StatePublished - 1996

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design


  • Collision detection
  • Hierarchical data structures
  • Ray shooting


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

Cite this