1CMSC 341Binary TreesApplication Example: Visibility9/13/2007 UMBC CMSC 341 AA Example 2AA Example: Visibility The problem: Given a geometric model (list ofpolygons) and a view specification, generate theimage which represents that scene viewed inthat way Many ways to approach the problem Ivan Sutherland, A Characterization of Ten HiddenSurface Algorithms, 1974 More approaches in the decades since29/13/2007 UMBC CMSC 341 AA Example 3Visibility Algorithm Taxonomy9/13/2007 UMBC CMSC 341 AA Example 4Painter’s Algorithm Approach Sort polygons Draw polygons in order: furthest to closest39/13/2007 UMBC CMSC 341 AA Example 5Painter’s Algorithm Problems Depth sort is hard Time-consuming Dealing with ambiguities For interactive 3D applications View point changes as viewer moves throughscene Requires new sort of pgon list with every newview position9/13/2007 UMBC CMSC 341 AA Example 6Binary Space Partition (BSP) Tree Concept Create a view-independent organization of pgonsthat can accelerate sorted drawing of primitives Approach Build binary tree capturing spatial pgonrelationships (do once per model) Traverse tree for particular view position (do onceper frame)49/13/2007 UMBC CMSC 341 AA Example 7BSP Tree: Polygons in Scene(2D top view, view position at left)9/13/2007 UMBC CMSC 341 AA Example 8BSP Tree Algorithm: Building the TreeBSPTree MakeBSP( PolygonList list) {PolygonList frontlist, backlist;Polygon root, p;if (list.isEmpty()) return null;else {root = list.somePolygon();list.remove(root);for (Polygon p : list) {if (root.inFront(p) // p in front of rootfrontlist.add(p);else if (root.inBack(p)) // p in back of rootbacklist.add(p);else{ // p crosses plane of rootp.split(root, frontpart, backpart);frontlist.add(frontpart);backlist.add(backpart);}return (BSPTree(MakeBSPTree(frontlist), root,MakeBSPTree(backlist));}}59/13/2007 UMBC CMSC 341 AA Example 9BSPTree: Building the Tree (1)9/13/2007 UMBC CMSC 341 AA Example 10BSPTree: Building the Tree (2)69/13/2007 UMBC CMSC 341 AA Example 11BSPTree: Building the Tree(3)9/13/2007 UMBC CMSC 341 AA Example 12BSPTree: Root choice79/13/2007 UMBC CMSC 341 AA Example 13BSP Tree Algorithm: Displaying the Treevoid DisplayBSP( BSPTree tree, ViewPoint viewer) {if (!tree.isEmpty()) {if (root.inFront(viewer)) {DisplayBSP(tree->back);DisplayPolygon (tree->root);DisplayBSP(tree->front);}else {DisplayBSP(tree->front);DisplayPolygon (tree->root);DisplayBSP(tree->back);}}}}9/13/2007 UMBC CMSC 341 AA Example 14BSPTree: The Tree89/13/2007 UMBC CMSC 341 AA Example 15BSPTree: Displaying the Tree (1) For view point at C: At 3: viewpoint in front -> display back first9/13/2007 UMBC CMSC 341 AA Example 16BSPTree: Displaying the Tree (2) For view point at C: At 3: viewpoint in front -> display back first At 4: viewpoint in back -> display front first99/13/2007 UMBC CMSC 341 AA Example 17BSPTree: Displaying the Tree (3)For view point at C:At 3: viewpoint in front -> display back firstAt 4: viewpoint in back -> display front first (none)display self9/13/2007 UMBC CMSC 341 AA Example 18BSPTree: Displaying the Tree (4)For view point at C:At 3: viewpoint in front -> display back firstAt 4: viewpoint in back -> display front first (none)display selfdisplay back (5b)at 5b: viewpoint in back -> display front (none)display selfdisplay back (none)109/13/2007 UMBC CMSC 341 AA Example 19BSPTree: Displaying the Tree (5)For view point at C:At 3: viewpoint in front -> display back first // done with 4, 5bdisplay self9/13/2007 UMBC CMSC 341 AA Example 20BSPTree: Displaying the Tree (6)For view point at C:At 3: viewpoint in front -> display back first // with 4, 5bdisplay selfdisplay front (2)At 2: viewpoint in back -> display front first119/13/2007 UMBC CMSC 341 AA Example 21BSPTree: Displaying the Tree (7)For view point at C:At 3: viewpoint in front -> display back first // done with 4, 5bdisplay selfdisplay front (2)At 2: viewpoint in back -> display front firstat 5a: viewpoint in back -> display front (none)display selfdisplay back (none)9/13/2007 UMBC CMSC 341 AA Example 22BSPTree: Displaying the Tree (8)For view point at C:At 3: viewpoint in front -> display back first // done with 4, 5bdisplay selfdisplay front (2)At 2: viewpoint in back -> display front first // done with 5adisplay self129/13/2007 UMBC CMSC 341 AA Example 23BSPTree: Displaying the Tree (9)For view point at C:At 3: viewpoint in front -> display back first // done with 4, 5bdisplay selfdisplay front (2)At 2: viewpoint in back -> display front first // done with 5adisplay selfdisplay back (1)At 1: viewpoint in back -> display front first (none)display selfdisplay back
View Full Document
Unlocking...