CMSC 341 Binary Trees Application Example Visibility AA Example Visibility The problem Given a geometric model list of polygons and a view specification generate the image which represents that scene viewed in that way Many ways to approach the problem 9 13 2007 Ivan Sutherland A Characterization of Ten Hidden Surface Algorithms 1974 More approaches in the decades since UMBC CMSC 341 AA Example 2 1 Visibility Algorithm Taxonomy 9 13 2007 UMBC CMSC 341 AA Example 3 Painter s Algorithm Approach 9 13 2007 Sort polygons Draw polygons in order furthest to closest UMBC CMSC 341 AA Example 4 2 Painter s Algorithm Problems Depth sort is hard Time consuming Dealing with ambiguities For interactive 3D applications View point changes as viewer moves through scene Requires new sort of pgon list with every new view position 9 13 2007 UMBC CMSC 341 AA Example 5 Binary Space Partition BSP Tree Concept Create a view independent organization of pgons that can accelerate sorted drawing of primitives Approach 9 13 2007 Build binary tree capturing spatial pgon relationships do once per model Traverse tree for particular view position do once per frame UMBC CMSC 341 AA Example 6 3 BSP Tree Polygons in Scene 2D top view view position at left 9 13 2007 UMBC CMSC 341 AA Example 7 BSP Tree Algorithm Building the Tree BSPTree 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 root frontlist add p else if root inBack p p in back of root backlist add p else p crosses plane of root p split root frontpart backpart frontlist add frontpart backlist add backpart return BSPTree MakeBSPTree frontlist root MakeBSPTree backlist 9 13 2007 UMBC CMSC 341 AA Example 8 4 BSPTree Building the Tree 1 9 13 2007 UMBC CMSC 341 AA Example 9 BSPTree Building the Tree 2 9 13 2007 UMBC CMSC 341 AA Example 10 5 BSPTree Building the Tree 3 9 13 2007 UMBC CMSC 341 AA Example 11 BSPTree Root choice 9 13 2007 UMBC CMSC 341 AA Example 12 6 BSP Tree Algorithm Displaying the Tree void 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 13 BSPTree The Tree 9 13 2007 UMBC CMSC 341 AA Example 14 7 BSPTree Displaying the Tree 1 For view point at C At 3 viewpoint in front display back first 9 13 2007 UMBC CMSC 341 AA Example 15 BSPTree Displaying the Tree 2 For view point at C At 3 viewpoint in front display back first At 4 viewpoint in back display front first 9 13 2007 UMBC CMSC 341 AA Example 16 8 BSPTree Displaying the Tree 3 For view point at C At 3 viewpoint in front display back first At 4 viewpoint in back display front first none display self 9 13 2007 UMBC CMSC 341 AA Example 17 BSPTree Displaying the Tree 4 For view point at C At 3 viewpoint in front display back first At 4 viewpoint in back display front first none display self display back 5b at 5b viewpoint in back display front none display self display back none 9 13 2007 UMBC CMSC 341 AA Example 18 9 BSPTree Displaying the Tree 5 For view point at C At 3 viewpoint in front display back first done with 4 5b display self 9 13 2007 UMBC CMSC 341 AA Example 19 BSPTree Displaying the Tree 6 For view point at C At 3 viewpoint in front display back first with 4 5b display self display front 2 At 2 viewpoint in back display front first 9 13 2007 UMBC CMSC 341 AA Example 20 10 BSPTree Displaying the Tree 7 For view point at C At 3 viewpoint in front display back first done with 4 5b display self display front 2 At 2 viewpoint in back display front first at 5a viewpoint in back display front none display self display back none 9 13 2007 UMBC CMSC 341 AA Example 21 BSPTree Displaying the Tree 8 For view point at C At 3 viewpoint in front display back first done with 4 5b display self display front 2 At 2 viewpoint in back display front first done with 5a display self 9 13 2007 UMBC CMSC 341 AA Example 22 11 BSPTree Displaying the Tree 9 For view point at C At 3 viewpoint in front display back first done with 4 5b display self display front 2 At 2 viewpoint in back display front first done with 5a display self display back 1 At 1 viewpoint in back display front first none display self display back none 9 13 2007 UMBC CMSC 341 AA Example 23 12
View Full Document
Unlocking...