Scene ManagementCSE 167, UCSD, Fall 2005Steve RotenbergScene ManagementThe scene management system is responsible for efficiently rendering complex scenesWe will mainly focus on real time scene management, but many of these techniques are also useful for offline renderingThe system maintains a world full of objects and determines what gets drawn and in what orderSome of the primary components include:Scene graphCullingLevel of detail (LOD)Draw orderInstancingPagingLayersThe scene management layer deals primarily with objectsThe rendering layer deals primarily with triangles and graphics state.Scene GraphComputer graphics often makes use of a scene graph of some sortAt a minimum, graphics scene graphs would probably have a tree structure where each node in the tree stored some geometry and a transformation (matrix or some other form)The hand from project 2, for example, can be represented as a scene graph. Each node in the tree would have a box model and a transform that does one or two rotationsHand Scene GraphPalmDigit00Digit01Digit02Digit10Digit11Digit12Digit20Digit21Digit22Digit30Digit31Digit32Real Time Scene GraphCombining the transformation and geometry into a single node makes sense, but for more complex scenes, it is more common to separate the two into different nodesAs always, there are different ways to do this, but today, we will consider a scene graph with a base node class and various derived nodes that perform specific functionsOur 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 NodeThe 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();}};Instance NodeThe ‘Instance’ node is an instance of some piece of geometryIt stores a pointer to a Model class, so that multiple instances could potentially share the same model dataNotice that Instance doesn’t have any ‘child’ nodes, and can therefore only be a leaf node in the scene treeclass Instance:public Node {Model *Mod;public:void Draw() {if(Mod) Model->Draw();}};Group NodeWe define a ‘Group’ node which stores an array of child nodes, but doesn’t perform any real computationGroups 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 GraphThe second version of the scene graph might look a bit more complicated, but the extra flexibility offered by the technique usually justifies itSub-Tree InstancingWe can also have nodes parented to more than one node, as long as we avoid any cyclic loops in our tree graphHaving nodes parented to more than one parent changes the tree graph into a directed acyclic graph or DAGFor example, if we wanted several copies of the hand at different locations:Groupetc…GroupTransform Transform Transform(hand from previous slide)Bounding Volume CullingCullingThe term cull means to remove from a groupIn graphics, it means to determine which objects in the scene are not visibleWe looked at culling of individual triangles. Today, we will consider culling of objectsThere are many approaches to object culling (and they can usually be combined easily)Bounding volumes (spheres, boxes…)Cull-planes, face clusteringOcclusion surfacesPortalsPotentially Visible Sets (PVS)Camera View VolumeThe main data that defines a real-time perspective camera includes:World space camera matrixField of view (FOV)Aspect ratioNear & far clipping plane distancesxzFOVNear clipFar clipBackface CullingBackface culling refers to the removal of individual triangles that face away from the cameraThis is usually built into the lower level renderer (OpenGL / Direct3D…) and is not really a part of scene managementBounding VolumesObjects are contained within simple bounding volumes (sphere, cylinder, box…)Before drawing an object, its bounding volume is tested against the camera’s viewing volume. There are 3 possible outcomes:Totally visibleTotally invisiblePartially visible (may require clipping)xzBounding Volume TypesSphereCylinderHot dog / capsule / lozengeAABB: axis-aligned bounding boxOBB: oriented bounding boxConvex polyhedronGenerating Bounding SpheresMethod 1: Average vertex positionsStep 1: Compute average of all vertex positions and place the center of the bounding sphere there.Step 2: Find the vertex farthest from the center and set the radius to that distanceWill 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 SpheresTransform bounding sphere to view spaceCompare against all 6 view volume facesObject is totally invisible if it is completely outside any one planeObject is totally visible if it is completely inside all planesOtherwise, the object may intersect the view volume and may require clippingxzTransforming to Camera SpaceObject’s world matrix: WCamera’s world matrix: CSphere position in object space: sSphere position in view space: s´=C-1•W•sTesting Near & Far Planesxzs'Far clipNear clipif(s.z-radius > -NearClip) then outsideelse if(s.z+radius<-FarClip) then outsideelse if(s.z+radius>-NearClip) then intersectelse 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,
View Full Document
Unlocking...