Grid-based loose octree for spatial partitioning

Details Grid-based loose octree for spatial partitioning Grid-based loose octree for spatial partitioning

2006-02-21

2006-02-21

Chauhan, Ulka J. (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

Reexamination Certificate

active

07002571

ABSTRACT:
A technique for spatial partitioning and a data structure for storing references to objects in a scene. A grid-based loose octree (GLOtree) is a data structure that combines advantages of a uniform grid-based subdivision method and an octree-based subdivision method to provide a general purpose spatial partitioning method that works well with both static and dynamic scenes. In a GLOtree, objects are located at lower levels of the tree than in the prior art octree. This allows traversals to search for specific objects to be accomplished more quickly when a starting search level of the GLOtree is predicted. The GLOtree uses loose octree nodes that adapt the sizes of octants to the scene.

REFERENCES:
patent: 2003/0117397 (2003-06-01), Hubrecht et al.
Postorder Traversal. National Institute of Standards and Technology. May 2002. http://www.nist.gov/dads/HTML/postordrtrvs.html.
Data Structures, Algorithms. R. Mukundan. Feb. 2002. http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BTree.html.
Daniel Aliaga, et al., “MMR: An Interactive Massive Model Rendering System Using Geometric And Image-Based Acceleration,” Symposium on Interactive 3D Graphics, 1999, pp. 199-206 and 237, Atlanta, GA, USA.
Frederic Cazals, et al., “Filtering, Clustering and Hierarchy Construction: A New Solution for Ray-Tracing Complex Scenes,” Eurographics, 1995, pp. C-371-C-382, Blackwell Publishers.
Frederic Cazals, et al., “Bucket-Like Space Partitioning Data Structures with Applications to Ray-Tracing,” Computational Geometry, 1997, pp. 11-20, Nice, France.
Foley, et al., “Computer Graphics: Principles and Practice in C: 12.6.3 Octrees,” 2nd Edition, Jul. 1997, pp. 550-557, Addison-Wesley Longman, Inc., ISBN: 0-201-84840-6.
Henry Fuchs, “On Visible Surface Generation By A Priori Tree Structures,” 1980, pp. 124-133.
Alan Fournier, et al., “The Stochastic Modelling of Trees,” Graphics Interface '86/ Vision Interface '86, 1986, pp. 1-9, Computer Systems Research Inst., University of Toronto, Ontario.
Andrew S. Glassner, “Space Subvision for Fast Ray Tracing,” IEEE CG&A, Oct. 1984, pp. 15-22.
JaaP Suter, “Flipcode: Introduction to Octrees,” Apr. 13, 1999, http://www.flipcode.com/tutorials/tut—octrees.shtml, Apr. 23, 2002.

Affiliated with

Also associated with

Rating

Grid-based loose octree for spatial partitioning does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Grid-based loose octree for spatial partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Grid-based loose octree for spatial partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3658578