DOC PREVIEW
UTK CS 594 - Hierarchical Data Structures, Scene Graph and Quaternion

This preview shows page 1-2-3-24-25-26-27-49-50-51 out of 51 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Hierarchical Data Structures, Scene Graph and QuaternionSpatial Data StructureSpatial Data StructuresBounding VolumeBounding VolumesQuad-treesOctreesK-D treeSlide 9K-D Tree in 3-DMotivation for Scene GraphScene Graph ExampleSlide 13Slide 14Slide 15Scene DescriptionScene GraphsScene Element Class HierarchyScene GraphSlide 20Slide 21Scene Graph (VRML 2.0)Example Scene GraphScene Graph TraversalScene Graph ConsiderationsFunctional OrganizationSlide 27Bounding Volume HierarchiesView Frustum CullingLevel Of Detail (LOD)Attribute ManagementSlide 32Question: How do you manage your light sources?Sample Scene GraphThink!Scene Graphs TraversalTypical Traversal OperationsScene Graphs OrganizationState InheritanceScene Graphs Appearance OverridesAppearance OverrideMultiple Referencing (Instancing)Multiple ReferencingOther Scene Graph OrganizationsSpecifying RotationQuaternionQuaternion multiplicationPolar Representation of QuaternionQuaternion RotationQuaternion InterpolationMoreHierarchical Data Structures, Scene Graph and QuaternionJian Huang, CS594, Fall 2002This set of slides reference the text book and Comps Graphics & Virtual Environments (Slater et. al, Addison-Wesley), 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 treeSpatial 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 moreBounding 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 hierarchiesBounding Volumes•Choose Bounding Volume(s)–Spheres–Boxes–Parallelepipeds–Oriented boxes–Ellipsoids–Convex hullsQuad-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 betterK-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 treeK-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 ExampleScene Graph ExampleScene Graph ExampleScene Graph ExampleScene Description•Set of Primitives•Specify for each primitive• Transformation• Lighting attributes• Surface attributes•Material (BRDF)•Texture•Texture transformationScene 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 HierarchyScene 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 structureScene 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 APIScene GraphScene Graph (VRML 2.0)Example Scene GraphScene Graph Traversal•Simulation–Animation•Intersection–Collision detection–Picking•Image Generation–Culling–Detail elision–AttributesScene Graph Considerations•Functional Organization–Semantics•Bounding Volumes–Culling–Intersection•Levels of Detail–Detail elision–Intersection•Attribute Management–Eliminate redundanciesFunctional Organization•Semantics:–Logical parts–Named partsFunctional Organization•Articulated Transformations–Animation–Difficult to optimize animated objectsBounding Volume HierarchiesView Frustum CullingLevel Of Detail (LOD)•Each LOD nodes have distance rangesAttribute 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 renderingQuestion: 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 GraphThink!•How to handle optimization of scene graphs with multiple competing goals–Function–Bounding volumes–Levels of Detail–AttributesScene 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-graphTypical 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 structuresState 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


View Full Document

UTK CS 594 - Hierarchical Data Structures, Scene Graph and Quaternion

Documents in this Course
Load more
Download Hierarchical Data Structures, Scene Graph and Quaternion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Hierarchical Data Structures, Scene Graph and Quaternion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Hierarchical Data Structures, Scene Graph and Quaternion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?