BOXTREE: A hierarchical representation for surfaces in 3D

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

doi:10.1111/1467-8659.1530387

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 journal › Article › peer-review

102 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 language	English (US)
Pages (from-to)	387-396
Number of pages	10
Journal	Computer Graphics Forum
Volume	15
Issue number	3
DOIs	https://doi.org/10.1111/1467-8659.1530387
State	Published - 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Graphics and Computer-Aided Design

Keywords

Collision detection
Hierarchical data structures
Ray shooting

Access to Document

10.1111/1467-8659.1530387

Cite this

@article{b0d4b92957fa48aeb3aa813c7b01f229,

title = "BOXTREE: A hierarchical representation for surfaces in 3D",

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.",

keywords = "Collision detection, Hierarchical data structures, Ray shooting",

author = "Gill Barequet and Bernard Chazelle and Guibas, {Leonidas J.} and Mitchell, {Joseph S.B.} and Ayellet Tal",

year = "1996",

doi = "10.1111/1467-8659.1530387",

language = "English (US)",

volume = "15",

pages = "387--396",

journal = "Computer Graphics Forum",

issn = "0167-7055",

publisher = "Wiley-Blackwell Publishing Ltd",

number = "3",

}

TY - JOUR

T1 - BOXTREE

T2 - A hierarchical representation for surfaces in 3D

AU - Barequet, Gill

AU - Chazelle, Bernard

AU - Guibas, Leonidas J.

AU - Mitchell, Joseph S.B.

AU - Tal, Ayellet

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

KW - Collision detection

KW - Hierarchical data structures

KW - Ray shooting

UR - http://www.scopus.com/inward/record.url?scp=0030246101&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030246101&partnerID=8YFLogxK

U2 - 10.1111/1467-8659.1530387

DO - 10.1111/1467-8659.1530387

M3 - Article

AN - SCOPUS:0030246101

SN - 0167-7055

VL - 15

SP - 387

EP - 396

JO - Computer Graphics Forum

JF - Computer Graphics Forum

IS - 3

ER -

BOXTREE: A hierarchical representation for surfaces in 3D

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this