November 6, 2003Doug JamesCarnegie Mellon Universityhttp://www.cs.cmu.edu/~djames/Fall03/15-462Hierarchical Bounding VolumesRegular GridsOctreesBSP TreesConstructive Solid Geometry (CSG)[Angel 9.10]Hierarchical Bounding VolumesRegular GridsOctreesBSP TreesConstructive Solid Geometry (CSG)[Angel 9.10]Spatial Data StructuresSpatial Data Structures15-462 Computer Graphics ILecture 1711/7/2003 15-462 Graphics I 2AnnouncementsAnnouncements• Ray tracing handouts online (CMU access only)– Supplements text• Last written assignment out tomorrow– Due Tuesday, Nov 18.• Last programming assignment– Ray tracing – Out Tuesday, Nov 18.– Due Tuesday, Dec 2.11/7/2003 15-462 Graphics I 3Ray Tracing AccelerationRay Tracing Acceleration• Faster intersections– Faster ray-object intersections• Object bounding volume• Efficient intersectors– Fewer ray-object intersections• Hierarchical bounding volumes (boxes, spheres)• Spatial data structures• Directional techniques• Fewer rays– Adaptive tree-depth control– Stochastic sampling• Generalized rays (beams, cones)11/7/2003 15-462 Graphics I 4Spatial Data StructuresSpatial Data Structures• Data structures to store geometric information• Sample applications– Collision detection– Location queries– Chemical simulations– Rendering• Spatial data structures for ray tracing– Object-centric data structures (bounding volumes)– Space subdivision (grids, octrees, BSP trees)– Speed-up of 10x, 100x, or more11/7/2003 15-462 Graphics I 5Bounding VolumesBounding Volumes• Wrap complex objects in simple ones• Does ray intersect bounding box?– No: does not intersect enclosed objects– Yes: calculate intersection with enclosed objects• Common types– Boxes, axis-aligned– Boxes, oriented– Spheres– Finite intersections or unions of above11/7/2003 15-462 Graphics I 6Selection of Bounding VolumesSelection of Bounding Volumes• Effectiveness depends on:– Probability that ray hits bounding volume, but not enclosed objects (tight fit is better)– Expense to calculate intersections with bounding volume and enclosed objects• Amortize calculation of bounding volumes• Use heuristicsgoodbad11/7/2003 15-462 Graphics I 7Hierarchical Bounding VolumesHierarchical Bounding Volumes• With simple bounding volumes, ray casting still has requires O(n) intersection tests• Idea: use tree data structure– Larger bounding volumes contain smaller ones etc.– Sometimes naturally available (e.g. human figure)– Sometimes difficult to compute• Often reduces complexity to O(log(n))11/7/2003 15-462 Graphics I 8Ray Intersection AlgorithmRay Intersection Algorithm• Recursively descend tree• If ray misses bounding volume, no intersection• If ray intersects bounding volume, recurse with enclosed volumes and objects• Maintain near and far bounds to prune further• Overall effectiveness depends on model and constructed hierarchy11/7/2003 15-462 Graphics I 9Spatial SubdivisionSpatial Subdivision• Bounding volumes enclose objects, recursively• Alternatively, divide space• For each segment of space keep list of intersecting surfaces or objects• Basic techniques– Regular grids– Octrees (axis-aligned, non-uniform partition)– BSP trees (recursive Binary Space Partition, planes)11/7/2003 15-462 Graphics I 10GridsGrids• 3D array of cells (voxels) that tile space• Each cell points to all intersecting surfaces• Intersection algsteps from cellto cell11/7/2003 15-462 Graphics I 11Caching Intersection pointsCaching Intersection points• Objects can span multiple cells• For A need to test intersection only once• For B need to cache intersection and check next cell for closer one• If not, C could be missed(yellow ray)ABC11/7/2003 15-462 Graphics I 12Assessment of GridsAssessment of Grids• Poor choice when world is non-homogeneous• Size of grid– Too small: too many surfaces per cell– Too large: too many empty cells to traverse– Can use alg like Bresenham’s for efficient traversal• Non-uniform spatial subdivision more flexible– Can adjust to objects that are present11/7/2003 15-462 Graphics I 13OutlineOutline• Hierarchical Bounding Volumes• Regular Grids• Octrees• BSP Trees• Constructive Solid Geometry (CSG)11/7/2003 15-462 Graphics I 14QuadtreesQuadtrees• Generalization of binary trees in 2D– Node (cell) is a square– Recursively split into 4 equal sub-squares– Stop subdivision based on number of objects• Ray intersection has to traverse quadtree• More difficult to step to next cell11/7/2003 15-462 Graphics I 15OctreesOctrees• Generalization of quadtree in 3D• Each cell may be split into 8 equal sub-cells• Internal nodes store pointers to children• Leaf nodes store list of surfaces• Adapts well to inhomogeneous scenes11/7/2003 15-462 Graphics I 16Assessment for Ray TracingAssessment for Ray Tracing• Grids– Easy to implement– Require a lot of memory– Poor results for inhomogeneous scenes• Octrees– Better on most scenes (more adaptive)• Alternative: nested grids• Spatial subdivision expensive for animations• Hierarchical bounding volumes– Natural for hierarchical objects– Better for dynamic scenes11/7/2003 15-462 Graphics I 17Other Spatial Subdivision TechniquesOther Spatial Subdivision Techniques• Relax rules for quadtrees and octrees• k-dimensional tree (k-d tree)– Split at arbitrary interior point– Split one dimension at a time• Binary space partitioning tree (BSP tree)– In 2 dimensions, split with any line– In k dims. split with k-1 dimensional hyperplane– Particularly useful for painter’s algorithm– Can also be used for ray tracing [see handout]11/7/2003 15-462 Graphics I 18OutlineOutline• Hierarchical Bounding Volumes• Regular Grids• Octrees• BSP Trees• Constructive Solid Geometry (CSG)11/7/2003 15-462 Graphics I 19BSP TreesBSP Trees• Split space with any line (2D) or plane (3D)• Applications– Painters algorithm for hidden surface removal– Ray casting• Inherent spatial ordering given viewpoint– Left subtree: in front, right subtree: behind• Problem: finding good space partitions– Proper ordering for any viewpoint– Balance tree• For details, see http://reality.sgi.com/bspfaq/11/7/2003 15-462 Graphics I 20Building a BSP TreeBuilding a BSP Tree• Use hidden surface removal as intuition• Using line 1 or line 2 as root is easyLine 2Line 3Line 1Viewpoint1123B A C Da BSP treeusing 2
View Full Document
Unlocking...