Hierarchical Data Structures Scene Graph and Quaternion Jian Huang CS594 Fall 2002 This set of slides reference the text book and Comps Graphics Virtual Environments Slater et al AddisonWesley slides used at Princeton by Prof Tom Funkhouser and Gahli et al SIGGRAPH course note 15 on OO API Spatial Data Structure Octree Quadtree BSP tree K D tree Spatial Data Structures Data structures for efficiently storing geometric information They are useful for Collision detection will the spaceships collide Location queries which is the nearest post office Chemical simulations which protein will this drug molecule interact with Rendering is this aircraft carrier on screen and more Good data structures can give speed up rendering by 10x 100x or more Bounding Volume Simple notion wrap things that are hard to check for ray intersection in things that are easy to check Example wrap a complicated polygonal mesh in a box Ray can t hit the real object unless it hits the box Adds some overhead but generally pays for itself Can build bounding volume hierarchies Bounding Volumes Choose Bounding Volume s Spheres Boxes Parallelepipeds Oriented boxes Ellipsoids Convex hulls Quad trees Quad tree is the 2 D generalization of binary tree node cell is a square recursively split into four equal sub squares stop when leaves get simple enough Octrees Octree is the 3 D generalization of quad tree node cell is a cube recursively split into eight equal sub cubes stop splitting when the number of objects intersecting the cell gets small enough or the tree depth exceeds a limit internal nodes store pointers to children leaves store list of surfaces more expensive to traverse than a grid adapts to non homogeneous clumpy scenes better K D tree The K D approach is to make the problem space a rectangular parallelepiped whose sides are in general of unequal length The length of the sides is the maximum spatial extent of the particles in each spatial dimension K D tree K D Tree in 3 D Similarly the problem space in three dimensions is a parallelepiped whose sides are the greatest particle separation in each of the three spatial dimensions Motivation for Scene Graph Three fold Performance Generality Ease of use How to model a scene Java3D Open Inventor Open Performer VRML etc Scene Graph Example Scene Graph Example Scene Graph Example Scene Graph Example Scene Description Set of Primitives Specify for each primitive Transformation Lighting attributes Surface attributes Material BRDF Texture Texture transformation Scene Graphs Scene Elements Interior Nodes Have children that inherit state transform lights fog color Leaf nodes Terminal geometry text Attributes Additional sharable state textures Scene Element Class Hierarchy Scene Graph Graph Representation What do edges mean Inherit state along edges group all red object instances together group logical entities together parts of a car Capture intent with the structure Scene Graph Inheritance Overloaded Term Behavior inheritance subclassing Benefit of OO design Implementation inheritance Perhaps provided by implementation language Not essential for a good API design Implied inheritance Designed into the API Scene Graph Scene Graph VRML 2 0 Example Scene Graph Scene Graph Traversal Simulation Animation Intersection Collision detection Picking Image Generation Culling Detail elision Attributes Scene Graph Considerations Functional Organization Semantics Bounding Volumes Culling Intersection Levels of Detail Detail elision Intersection Attribute Management Eliminate redundancies Functional Organization Semantics Logical parts Named parts Functional Organization Articulated Transformations Animation Difficult to optimize animated objects Bounding Volume Hierarchies View Frustum Culling Level Of Detail LOD Each LOD nodes have distance ranges Attribute Management Minimize transformations Each transformation is expensive during rendering intersection etc Need automatic algorithms to collapse adjust transform hierarchy Attribute Management Minimize attribute changes Each state change is expensive during rendering Question How do you manage your light sources OpenGL supports only 8 lights What if there are 200 lights The modeler must scope the lights in the scene graph Sample Scene Graph Think How to handle optimization of scene graphs with multiple competing goals Function Bounding volumes Levels of Detail Attributes Scene Graphs Traversal Perform operations on graph with traversal Like STL iterator Visit all nodes Collect inherited state while traversing edges Also works on a sub graph Typical Traversal Operations Typical operations Render Search pick find by name View frustum cull Tessellate Preprocess optimize Scene Graphs Organization Tree structure best No cycles for simple traversal Implied depth first traversal not essential Includes lists single node etc as degenerate trees If allow multiple references instancing Directed acyclic graph DAG Difficult to represent cell portal structures State Inheritance General left to right top to bottom all state Open Inventor Need Separator node to break inheritance Need to visit all children to determine final state Top to bottom only IRIS Performer Java3D State can be determined by traversing path to node Scene Graphs Appearance Overrides One attempt to solve the highlighting problem After picking an object want to display it differently Don t want to explicitly edit and restore its appearance Use override node in the scene graph to override appearance of children Only works if graph organization matches model organization Appearance Override Multiple Referencing Instancing Convenient for representing multiple instances of an object rivet in a large assembly Save memory Need life time management is the object still in use garbage collection reference counts Multiple Referencing Changes trees into DAGs Instance of an object represented by its path path is like a mini scene Difficult to attach instance specific properties e g caching transform at leaf node Other Scene Graph Organizations Logical structure part assembly etc Used by modeling applications Topology structure e g boundary surfaces faces edges vertices Useful for CAD applications Behaviors e g engine graph Environment graph fog lights etc Scene graph is not just for rendering Specifying Rotation How to parameterize rotation Traditional way use Euler angles rotation is specified by using angles with respect to three mutually perpendicular axes Roll pitch and yaw angles one
View Full Document
Unlocking...