Open AccessA new space subdivision method for ray tracing CSG modelled scenes
Author(s) -
Bruno Arnaldi,
Thierry Priol,
Kadi Bouatouch
Publication year - 1987
Publication title -
the visual computer
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.316
H-Index - 67
eISSN - 1432-2315
pISSN - 0178-2789
DOI - 10.1007/bf02153666
Subject(s) - constructive solid geometry , subdivision , bounding overwatch , ray tracing (physics) , computer science , tracing , data structure , computer graphics , bounding volume , algorithm , path (computing) , tree (set theory) , projection plane , set (abstract data type) , space (punctuation) , projection (relational algebra) , theoretical computer science , mathematics , computer graphics (images) , artificial intelligence , collision detection , combinatorics , physics , computer security , archaeology , quantum mechanics , image (mathematics) , history , programming language , collision , operating system
A new algorithm for space tracing with CSG modelled scenes is presented. Space is divided in an irregular fashion to fit the objects as closely as possible. For this reason, primitive minimal bounding boxes are computed. Space subdivision is achieved in two steps: partitioning in projection plane and depth partitioning. A set of 3D regions named cells are then created. A Boolean CSG tree is distributed into the cell structure to form in each cell the minimal boolean CSG tree using the relevant primitives. The searching process for the “next cell” along the ray path is performed by using a local data structure associated with each cell. The goal of this structure is to link the cells together. An improvement, named “mailbox”, for all space tracing algorithms is detailed. Results are presented for two scenes to compare this new algorithm with Roth's algorithm.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom