1Hierarchical 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 StructuresOutlineOutline• Ray tracing review – what rays matter?• Ray tracing speedup– faster intersection tests: simple enclosing geometry• bounding volumes– fewer intersection tests: avoid testing many objects• hierarchical bounding volumes• regular grid• octree• BSP tree• CSG and ray tracing2Spatial Data StructuresSpatial Data Structures• Data structures to store geometric information• Sample applications– Height field representation– Collision detection (hierarchical bounding volumes)– Surgical simulations (finite element method)– 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 moreBounding VolumesBounding Volumes• Suppose you are ray tracing teapots...– need to intersect ray with a collection of Bezier patches...– ...or a large number of triangles3Bounding 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 aboveSelection 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• Use heuristics / your best judgmentgoodbad4Hierarchical Bounding VolumesHierarchical Bounding Volumes• With simple bounding volumes, ray casting still requires O(n) intersection tests...Hierarchical 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))5Ray 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 hierarchyFocus on ObjectsFocus on Objects• Bounding volumes are object centric– place simple bounding volume around each object– group these simple bounding volumes into a hierarchy6Focus on ObjectsFocus on Objects• Bounding volumes are object centric– place simple bounding volume around each object– group these simple bounding volumes into a hierarchy• Problems:– finding a good grouping can be difficult– if objects are moving, a group that is compact now may not be compact later .. – (logical groupings such as an object or animated character, however, are easy to group and maintain)Focus on Objects Æ Focus on the SpaceFocus on Objects Æ Focus on the Space• Bounding volumes are object centric– place simple bounding volume around each object– group these simple bounding volumes into a hierarchy• Problems:– finding a good grouping is difficult– if objects are moving, a group that is compact now may not be compact later..• If there are many distinct objects, dividing up space and registering objects in that space may be a better option7Spatial SubdivisionSpatial Subdivision• Regular grids• Octrees• BSP treesGridsGrids• 3D array of cells (voxels) that tile space• Each cell points to all intersecting surfaces• Intersectionalgorithmsteps from cellto cell8Caching 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)ABCAssessment 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 present9QuadtreesQuadtrees• Goal: a hierarchical subdivision of an entire (bounded) 2D spaceQuadtreesQuadtrees• Generalization of binary trees to 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 cell10OctreesOctrees• Generalization of quadtree to 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 scenesAssessment 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)• Spatial subdivision expensive for dynamic scenes (animations)• Hierarchical bounding volumes– Natural for hierarchical objects– Better for dynamic scenes11BSP TreesBSP Trees• Binary space partitioning• Goal: divide space in a more efficient way, with results depending on the particular sceneBSP 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 tree12Building 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 as rootABDC32the subdivisionof space it impliesSplitting of surfacesSplitting of surfaces• Using line 3 as root requires splittingLine 2aLine 3Line 1Viewpoint12a2bLine 2b313Painter’s Algorithm with BSP TreesPainter’s Algorithm with BSP Trees• Building the tree– May need to split some polygons– Slow, but done only once• Traverse back-to-front or
View Full Document
Unlocking...