# BSP2D

Published on September 14, 2007

Author: Alien

Source: authorstream.com

Motivation for BSP Trees:The Visibility Problem:  Motivation for BSP Trees: The Visibility Problem We have a set of objects (either 2d or 3d) in space. We have an 'eye' at some point in this space, looking at the objects from a particular direction. Drawing the Visible Objects:  Drawing the Visible Objects We want to generate the image that the eye would see, given the objects in our space. How do we draw the correct object at each pixel, given that some objects may obscure others in the scene? A Simple Solution: The Z-buffer:  A Simple Solution: The Z-buffer Keep a buffer that holds the z-depth of the pixel currently at each point on screen Draw each polygon: for each pixel, test its depth versus current screen depth to decide if we draw it or not Drawbacks to Z-buffering:  Drawbacks to Z-buffering This used to be a very expensive solution! Requires memory for the z-buffer – extra hardware cost was prohibitive Requires extra z-test for every pixel So, a software solution was developed … The Painter's Algorithm:  The Painter's Algorithm Avoid extra z-test andamp; space costs by scan converting polygons in back-to-front order Is there always a correct back-to-front order? How Do We Deal With Cycles?:  How Do We Deal With Cycles? In 3 dimensions, polygons can overlap, creating cycles in which no depth ordering would draw correctly. How do we deal with these cases? BSP Trees:  BSP Trees Having a pre-built BSP tree will allow us to get a correct depth order of polygons in our scene for any point in space. We will build a data structure based on the polygons in our scene, that can be queried with any point input to return an ordering of those polygons. The Big Picture:  The Big Picture Assume that no objects in our space overlap. Use planes to recursively split our object space, keeping a tree structure of these recursive splits. Choose a Splitting Line:  Choose a Splitting Line Choose a splitting plane, dividing our objects into three sets – those on each side of the plane, and those fully contained on the plane. Choose More Splitting Lines:  Choose More Splitting Lines What do we do when an object (like object 1) is divided by a splitting plane? It is divided into two objects, one on each side of the plane. Split Recursively Until Done:  Split Recursively Until Done When we reach a convex space containing exactly zero or one objects, that is a leaf node. Continue:  Continue Continue:  Continue Finished:  Finished Once the tree is constructed, every root-to-leaf path describes a single convex subspace. Querying the Tree:  Querying the Tree If a point is in the positive half-space of a plane, then everything in the negative half-space is farther away -- so draw it first, using this algorithm recursively. Then draw objects on the splitting plane, and recurse into the positive half-space. What Order Is Generated From This Eye Point?:  What Order Is Generated From This Eye Point? How much time does it take to query the BSP tree, asymptotically? Structure of a BSP Tree:  Structure of a BSP Tree Each internal node has a +half space, a -half space, and a list of objects contained entirely within that plane (if any exist). Each leaf has a list of zero or one objects inside it, and no subtrees. The size of a BSP tree is the total number of objects stored in the leaves andamp; nodes of the tree. This can be larger than the number of objects in our scene because of splitting. Building a BSP Tree From Line Segments in the Plane:  Building a BSP Tree From Line Segments in the Plane We’ll now deal with a formal algorithm for building a BSP tree for line segments in the 2D plane. This will generalize for building trees of D-1 dimensional objects within D-dimensional spaces. Auto-Partitioning:  Auto-Partitioning Auto-partitioning: splitting only along planes coincident on objects in our space Algorithm for the 2d Case:  Algorithm for the 2d Case If we only have one segment 's', return a leaf node containing s. Otherwise, choose a line segment 's' along which to split. For all other line segments, one of four cases will be true: 1) The segment is in the +half space of s 2) The segment is in the -half space of s 3) The segment crosses the line through s 4) The segment is entirely contained within the line through s. Split all segments who cross 's' into two new segments -- one in the +half space, and one in the -half space. Create a new BSP tree from the set of segments in the +half space of s, and another on the set of segments in the -half space. Return a new node whose children are these +/- half space BSP’s, and which contains the list of segments entirely contained along the line through s. How Small Is the BSP From This Algorithm?:  Different orderings result in different trees Greedy approach doesn't always work -- sometimes it does very badly, and it is costly to find How Small Is the BSP From This Algorithm? Random Approach Works Well:  Random Approach Works Well If we randomly order segments before building the tree, then we do well in the average case. Expected Number of Fragments: O(n Log n):  Expected Number of Fragments: O(n Log n) Expected Running Time: O(n2log n):  Expected Running Time: O(n2log n) Optimization: Free Splits:  Optimization: Free Splits Sometimes a segment will entirely cross a convex region described by some interior node -- if we choose that segment to split on next, we get a 'free split' -- no splitting needs to occur on the other segments since it crosses the region. Our Building Algorithm Extends to 3D!:  Our Building Algorithm Extends to 3D! The same procedure we used to build a tree from two-dimensional objects can be used in the 3D case – we merely use polygonal faces as splitting planes, rather than line segments. A Slight Modification, for the Sake of Analysis::  A Slight Modification, for the Sake of Analysis: Split both the + and - half space of a node with the same plane, when we choose to do a split. An exception: When a split does not subdivide some cell, it isn't necessary to include an extra node for it. Expected number of fragments: O(n^2):  Expected number of fragments: O(n^2) More analysis: How good are auto-partitions?:  There are sets of triangles in 3-space for which autopartitions guarantee W(n2) fragments. More analysis: How good are auto-partitions? Can we do better by not using autopartitions? Sometimes, No:  Sometimes, No There are actually sets of triangles for which any BSP will have W(n2) fragments! More applications:  More applications Querying a point to find out what convex space it exists within Cell visibility -- put extra data into your BSP leaves, such as links to adjacent convex subspaces

05. 01. 2008
0 views

15. 10. 2007
0 views

14. 09. 2007
0 views

23. 12. 2007
0 views

30. 04. 2008
0 views

28. 04. 2008
0 views

22. 04. 2008
0 views

17. 04. 2008
0 views

16. 04. 2008
0 views

14. 04. 2008
0 views

13. 04. 2008
0 views

10. 04. 2008
0 views

09. 04. 2008
0 views

07. 04. 2008
0 views

14. 09. 2007
0 views

14. 09. 2007
0 views

14. 09. 2007
0 views

14. 09. 2007
0 views

14. 09. 2007
0 views

12. 10. 2007
0 views

15. 10. 2007
0 views

16. 10. 2007
0 views

21. 10. 2007
0 views

22. 10. 2007
0 views

14. 09. 2007
0 views

14. 09. 2007
0 views

14. 09. 2007
0 views

14. 09. 2007
0 views

23. 10. 2007
0 views

23. 10. 2007
0 views

14. 09. 2007
0 views

01. 12. 2007
0 views

02. 11. 2007
0 views

22. 10. 2007
0 views

13. 11. 2007
0 views

20. 08. 2007
0 views

20. 08. 2007
0 views

20. 08. 2007
0 views

20. 08. 2007
0 views

20. 08. 2007
0 views

29. 10. 2007
0 views

23. 10. 2007
0 views

29. 10. 2007
0 views

28. 12. 2007
0 views

29. 12. 2007
0 views

23. 11. 2007
0 views

26. 11. 2007
0 views

01. 01. 2008
0 views

04. 01. 2008
0 views

22. 10. 2007
0 views

20. 08. 2007
0 views

22. 10. 2007
0 views

06. 11. 2007
0 views

16. 11. 2007
0 views

04. 10. 2007
0 views

22. 10. 2007
0 views

23. 10. 2007
0 views

09. 07. 2007
0 views

09. 07. 2007
0 views

09. 07. 2007
0 views

20. 08. 2007
0 views

09. 10. 2007
0 views

19. 10. 2007
0 views

14. 02. 2008
0 views

16. 02. 2008
0 views

14. 09. 2007
0 views

24. 02. 2008
0 views

17. 10. 2007
0 views

26. 02. 2008
0 views

14. 09. 2007
0 views

07. 11. 2007
0 views

20. 02. 2008
0 views

11. 03. 2008
0 views

12. 03. 2008
0 views

17. 12. 2007
0 views

23. 10. 2007
0 views

14. 09. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

17. 10. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

05. 10. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

01. 10. 2007
0 views

10. 10. 2007
0 views

19. 06. 2007
0 views

19. 06. 2007
0 views

24. 02. 2008
0 views

19. 06. 2007
0 views

12. 10. 2007
0 views

19. 06. 2007
0 views

11. 12. 2007
0 views

09. 07. 2007
0 views

03. 01. 2008
0 views

02. 01. 2008
0 views

04. 10. 2007
0 views

09. 07. 2007
0 views

14. 09. 2007
0 views

24. 10. 2007
0 views

26. 03. 2008
0 views

22. 11. 2007
0 views

20. 08. 2007
0 views

12. 10. 2007
0 views

03. 01. 2008
0 views

19. 06. 2007
0 views

22. 10. 2007
0 views

09. 07. 2007
0 views

17. 11. 2007
0 views

24. 10. 2007
0 views

13. 03. 2008
0 views

03. 10. 2007
0 views

15. 11. 2007
0 views

12. 10. 2007
0 views

04. 01. 2008
0 views

03. 01. 2008
0 views