Scene ManagementCSE 167, UCSD, Winter 2006Steve RotenbergScene Management The scene management system is responsible forefficiently rendering complex scenes We will mainly focus on real time scene management,but many of these techniques are also useful for offlinerendering The system maintains a world full of objects anddetermines what gets drawn and in what order Some of the primary components include: Scene graph Culling Level of detail (LOD) Draw order Instancing PagingLayers The scene management layer dealsprimarily with objects The rendering layer deals primarily withtriangles and graphics state.Scene Graph Computer graphics often makes use of a scenegraph of some sort At a minimum, graphics scene graphs wouldprobably have a tree structure where each nodein the tree stored some geometry and atransformation (matrix or some other form) The hand from project 2, for example, can berepresented as a scene graph. Each node in thetree would have a box model and a transformthat does one or two rotationsHand Scene GraphPalmDigit00Digit01Digit02Digit10Digit11Digit12Digit20Digit21Digit22Digit30Digit31Digit32Real Time Scene Graph Combining the transformation and geometry into a single nodemakes sense, but for more complex scenes, it is more common toseparate the two into different nodes As always, there are different ways to do this, but today, we willconsider a scene graph with a base node class and various derivednodes that perform specific functions Our base Node will not really do anything, but will have a generic‘Draw()’ function that can be overridden by higher level nodesclass Node {public:virtual void Draw();};Transform Node The Transform node is just a local transformation in the scene graph(exactly like the local joint rotations we did in project 2)class Transform:public Node {Matrix44 Mtx;Node *Child;public:void Draw() {if(Child==0) return;glPushMatrix();glMultMatrix(&Mtx); // need to convert Mtx* to float[]…Child->Draw();glPopMatrix();}};Model Node The ‘Instance’ node is an instance of some piece of geometry It stores a pointer to a Model class, so that multiple instances couldpotentially share the same model data Notice that Instance doesn’t have any ‘child’ nodes, and cantherefore only be a leaf node in the scene treeclass Model:public Node {Geometry *Mod;public:void Draw() {if(Mod) Model->Draw();}};Group Node We define a ‘Group’ node which stores an array of child nodes, but doesn’tperform any real computation Groups are used when one needs to parent several nodes to a single node(like the fingers on the hand)class Group:public Node {int NumChildren;Node *Child;public:void Draw() {for(int i=0;i<NumChildren;i++)Child[i]->Draw();}};Hand Scene Graph (version 2)GroupInstance (palm)TransformGroupInstance(digit00)TransformGroupInstance(digit01)TransformInstance(digit02)etc…etc…TransformGroupInstance(digit10)TransformGroupInstance(digit11)TransformInstance(digit12)Scene Graph The second version of the scene graphmight look a bit more complicated, but theextra flexibility offered by the techniqueusually justifies itSub-Tree Instancing We can also have nodes parented to more than one node, as longas we avoid any cyclic loops in our tree graph Having nodes parented to more than one parent changes the treegraph into a directed acyclic graph or DAG For example, if we wanted several copies of the hand at differentlocations:Groupetc…GroupTransform Transform Transform(hand fromprevious slide)Bounding Volume CullingCulling The term cull means to remove from a group In graphics, it means to determine which objects in thescene are not visible We looked at culling of individual triangles. Today, wewill consider culling of objects There are many approaches to object culling (and theycan usually be combined easily) Bounding volumes (spheres, boxes…) Cull-planes, face clustering Occlusion surfaces Portals Potentially Visible Sets (PVS)Camera View Volume The main data that defines areal-time perspective cameraincludes: World space camera matrix Field of view (FOV) Aspect ratio Near & far clipping planedistancesBackface Culling Backface culling refers to the removal ofindividual triangles that face away from thecamera This is usually built into the lower levelrenderer (OpenGL / Direct3D…) and is notreally a part of scene managementBounding Volumes Objects are contained within simplebounding volumes (sphere, cylinder, box…) Before drawing an object, its boundingvolume is tested against the camera’sviewing volume. There are 3 possibleoutcomes: Totally visible Totally invisible Partially visible (may require clipping)Bounding Volume Types Sphere Cylinder Hot dog / capsule / lozenge AABB: axis-aligned bounding box OBB: oriented bounding box Convex polyhedronGenerating Bounding Spheres Method 1: Average vertex positions Step 1: Compute average of all vertex positions andplace the center of the bounding sphere there. Step 2: Find the vertex farthest from the center andset the radius to that distance Will rarely, if ever, generate optimal resultsOptimal Enclosing SphereSphere ComputeSphere(int N,Point P[]) {randomly mix up points P[0]…P[N-1];Sphere sphere(P[0],0);i=1;while (i<N) {if(P[i] not in support) {if(P[i] not in sphere) {add P[i] to support and remove any unnecessary points;compute sphere from current support;i=0; // start over when support changescontinue;}}i++;}return sphere;}Testing Bounding Spheres Transform bounding sphere to viewspace Compare against all 6 view volumefaces Object is totally invisible if it iscompletely outside any one plane Object is totally visible if it iscompletely inside all planes Otherwise, the object may intersectthe view volume and may requireclippingTransforming to Camera Space Object’s world matrix: W Camera’s world matrix: C Sphere position in object space: s Sphere position in view space: s´=C-1•W•sTesting Near & Far Planesif(s.z-radius > -NearClip) then outsideelse if(s.z+radius<-FarClip) then outsideelse if(s.z+radius>-NearClip) thenintersectelse if(s.z-radius<-FarClip) then intersectelse insideTesting Right, Left, Top, & Bottomdist = n · s'if(dist>radius) then outsideif(dist<-radius) then insideelse intersectRight plane:n=[cos(FOV/2), 0, sin(FOV/2)]Top plane:n=~[0, cos(FOV/2)/Aspect,sin(FOV/2)]Performance
View Full Document
Unlocking...