BSP TreesSpace PartitioningSlide 3Slide 4Objects in 2DSlide 6Slide 7Slide 8Slide 9Slide 10Collision DetectionVisibility OrderingBSP Tree ConstructionPartitioning Hyperplane SelectionSlide 15AutopartitionSlide 17Slide 18Slide 193D ExampleSlide 21Slide 22Slide 23Another 3D ExampleSlide 25BSP Tree of an ObjectSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Classifying Object z2DSlide 373DBasic Draw Back to FrontBasic Draw Front to BackRandomizationRandomization—2D AnalysisRandomization —2D AnalysisRandomization—3D AnalysisFree PartitionsSlide 46Slide 47BSP Trees•Binary space partitioning trees.•Used to store a collection of objects in n-dimensional space.•Tree recursively divides n-dimensional space using (n-1)-dimensional hyperplanes.Space Partitioningd-dimensional spacesplitting hyperplane(d-1)-dimensionala1x1 + a2x2 + … adxd + ad+1 = 0ax + by + c = 0 (2D)ax+by+cz+d = 0 (3D)Space Partitioningd-dimensional space+ve half spaceax + by + c > 0ax+by+cz+d > 0-ve half spaceax + by + c < 0ax+by+cz+d < 0coincidentax + by + c = 0ax+by+cz+d = 0Space Partitioningd-dimensional space-ve +ve -ve+ve coincident listObjects in 2DabcdgefhObjects in 2DabcdgefhObjects in 2Dabcdgefha-d e-hObjects in 2Dabcdgefha-d e-hObjects in 2Dabcdgefha-b e-fc-d g-hObjects in 2Dabcdgefha bc defg hCollision Detectionabcdgefha bc defg hVisibility Orderingabcdgefha bc defg hBSP Tree Construction•Select partitioning hyperplanes.•Partition objects.•Repeat on partitions.Partitioning Hyperplane Selection•Face of an object.abcdgefhPartitioning Hyperplane Selection•Face of an object.abcdgefhAutopartition•Only object faces are used as splitting hyperplanesabcdgefhPartitioning Hyperplane Selection•Axis-aligned orthogonal hyperplanesabcdgefhPartitioning Hyperplane Selection•Axis-aligned orthogonal hyperplanesabcdgefhPartitioning Hyperplane Selection•Balance # objects (pieces) on each side of hyperplane•Minimize increase in number of objects/pieces.abcdgefh3D Example3D Example3D Example3D ExampleAnother 3D ExampleAnother 3D ExampleBSP Tree of an Object•Each leaf represents a region that is either wholly inside or outside the object.•Object surface is considered inside object.•Surface planes are used as partitioning planes.•Orient partitioning hyperplanes so that interior is to left.aaBSP Tree of an Object•Each leaf represents a region that is either wholly inside or outside the object.•Object surface is considered inside object.•Surface planes are used as partitioning planes.•Orient partitioning hyperplanes so that interior is to left.aabbBSP Tree of an Object•Each leaf represents a region that is either wholly inside or outside the object.•Object surface is considered inside object.•Surface planes are used as partitioning planes.•Orient partitioning hyperplanes so that interior is to left.aabbccBSP Tree of an Object•Each leaf represents a region that is either wholly inside or outside the object.•Object surface is considered inside object.•Surface planes are used as partitioning planes.•Orient partitioning hyperplanes so that interior is to left.aabbccddBSP Tree of an Object•Each leaf represents a region that is either wholly inside or outside the object.•Object surface is considered inside object.•Surface planes are used as partitioning planes.•Orient partitioning hyperplanes so that interior is to left.aabbcdeedcBSP Tree of an Object•Each leaf represents a region that is either wholly inside or outside the object.•Object surface is considered inside object.•Surface planes are used as partitioning planes.•Orient partitioning hyperplanes so that interior is to left.aabbcdeedffcBSP Tree of an Object•Orient partitioning hyperplanes so that interior is to left.•With this orientation, left leaves are interior and right leaves are exterior.aabbcdeedffcBSP Tree Construction•Node structure:ph = equation of partitioning hyperplanecList = list of objects coincident with phleftChildrightChildBSP Tree ConstructionBSPtree(O)// O is object setif O is empty, return null;Create a new node N;N.ph = partitioning hyperplane for O;lList = rList = N.cList = null;for each object z in O doif z is coincident to ph, add z to N.cList;if z is left of ph, add z to lList;if z is right of ph, add z to rList;if z spans ph, split z and add pieces to lList and rList;N.leftChild = BSPTree(lList);N.rightChild = BSPTree(rList);return N;Classifying Object z•In 2D, ph is the line ax + by + c = 0.Compute ax + by + c for all vertices of z.If all values are < 0; z is left of ph.If all values are > 0; z is right of ph.If all values are = 0; z is coincident to ph.Otherwise, z spans ph and is to be split by finding intersection points with ph.2DabcdgefhEquation of ph isx – 6 = 062DabcdgefhEquation of ph isy –x –2 = 023DxzyEquation of ph isz –2 = 0General: ax + by + cz + d = 0Basic Draw Back to Frontdraw(N)if eye left of N.ph{draw(N.rightChild); draw N.cList; draw(N.leftChild)};else if eye right of N.ph{draw(N.leftChild); draw N.cList; draw(N.rightChild)};else // eye coincident to N.ph{draw(N.leftChild); draw(N.rightChild)};Basic Draw Front to Backdraw(N)if eye left of N.ph{draw(N.leftChild); draw N.cList; draw(N.reightChild)};else if eye right of N.ph{draw(N.rightChild); draw N.cList; draw(N.leftChild)};else // eye coincident to N.ph{draw(N.rightChild); draw(N.leftChild)};Randomization•Autopartition.•Splitting hyperplane is randomly selected to be one of the object faces.•Lines in 2D; planes in 3D.abgehRandomization—2D Analysis•Start with n (nonintersecting) line segments.•Total number of line segments in autopartition bsp is expected to be <= n + 2n ln n. •If this bound is exceeded; rerun construction.•Expected number of construction rounds before this bound is not exceeded is 2.83846n = 29•So, number of nodes in bsp is O(n log n).•Construction time at each node is O(n) as at each node O(n) segments need to be partitioned.•Time is O(n2log n) per construction round.•2 rounds expected.•Expected complexity is O(n2log n).Randomization —2D Analysis83846n = 29Randomization—3D Analysis•Start with n (nonintersecting) triangles.•Total number of triangles in autopartition bsp using a weaker variant is O(n2).•There exist n-triangle examples for which every autopartition has (n2) triangle.n = 24Free Partitions•One that does not split an object.•Do a free partition whenever possible; otherwise,