Binary Space Partitioning - Generation

Generation

The canonical use of a BSP tree is for rendering polygons (that are double-sided, that is, without back-face culling) with the painter's algorithm. Such a tree is constructed from an unsorted list of all the polygons in a scene. The recursive algorithm for construction of a BSP tree from that list of polygons is:

  1. Choose a polygon P from the list.
  2. Make a node N in the BSP tree, and add P to the list of polygons at that node.
  3. For each other polygon in the list:
    1. If that polygon is wholly in front of the plane containing P, move that polygon to the list of nodes in front of P.
    2. If that polygon is wholly behind the plane containing P, move that polygon to the list of nodes behind P.
    3. If that polygon is intersected by the plane containing P, split it into two polygons and move them to the respective lists of polygons behind and in front of P.
    4. If that polygon lies in the plane containing P, add it to the list of polygons at node N.
  4. Apply this algorithm to the list of polygons in front of P.
  5. Apply this algorithm to the list of polygons behind P.

The following diagram illustrates the use of this algorithm in converting a list of lines or polygons into a BSP tree. At each of the eight steps (i.-viii.), the algorithm above is applied to a list of lines, and one new node is added to the tree.

Start with a list of lines, (or in 3-D, polygons) making up the scene. In the tree diagrams, lists are denoted by rounded rectangles and nodes in the BSP tree by circles. In the spatial diagram of the lines, direction chosen to be the 'front' of a line is denoted by an arrow.
i. Following the steps of the algorithm above,
  1. We choose a line, A, from the list and,...
  2. ...add it to a node.
  3. We split the remaining lines in the list into those in front of A (i.e. B2, C2, D2), and those behind (B1, C1, D1).
  4. We first process the lines in front of A (in steps ii–v),...
  5. ...followed by those behind (in steps vi–vii).
ii. We now apply the algorithm to the list of lines in front of A (containing B2, C2, D2). We choose a line, B2, add it to a node and split the rest of the list into those lines that are in front of B2 (D2), and those that are behind it (C2, D3).
iii. Choose a line, D2, from the list of lines in front of B2. It is the only line in the list, so after adding it to a node, nothing further needs to be done.
iv. We are done with the lines in front of B2, so consider the lines behind B2 (C2 and D3). Choose one of these (C2), add it to a node, and put the other line in the list (D3) into the list of lines in front of C2.
v. Now look at the list of lines in front of C2. There is only one line (D3), so add this to a node and continue.
vi. We have now added all of the lines in front of A to the BSP tree, so we now start on the list of lines behind A. Choosing a line (B1) from this list, we add B1 to a node and split the remainder of the list into lines in front of B1 (i.e. D1), and lines behind B1 (i.e. C1).
vii. Processing first the list of lines in front of B1, D1 is the only line in this list, so add this to a node and continue.
viii. Looking next at the list of lines behind B1, the only line in this list is C1, so add this to a node, and the BSP tree is complete.

The final number of polygons or lines in a tree is often larger (sometimes much larger) than the original list, since lines or polygons that cross the partitioning plane must be split into two. It is desirable to minimize this increase, but also to maintain reasonable balance in the final tree. The choice of which polygon or line is used as a partitioning plane (in step 1 of the algorithm) is therefore important in creating an efficient BSP tree.

Read more about this topic:  Binary Space Partitioning

Famous quotes containing the word generation:

    “There may perhaps be a new generation of doctors horrified by lacerations, infections, women who have douched with kitchen cleanser. What an irony it would be if fanatics continued to kill and yet it was the apathy and silence of the medical profession that most wounded the ability to provide what is, after all, a medical procedure.”
    —Anna Quindlen (b. 1952)

    “What makes this Generation of Vermin so very Prolifick, is the indefatigable Diligence with which they apply themselves to their Business. A Man does not undergo more watchings and fatigues in a Campaign, than in the Course of a vicious Amour. As it is said of some Men, that they make their Business their Pleasure, these Sons of Darkness may be said to make their Pleasure their Business. They might conquer their corrupt Inclinations with half the Pains they are at in gratifying them.”
    —Joseph Addison (1672–1719)

    “I do not mean to imply that the good old days were perfect. But the institutions and structure—the web—of society needed reform, not demolition. To have cut the institutional and community strands without replacing them with new ones proved to be a form of abuse to one generation and to the next. For so many Americans, the tragedy was not in dreaming that life could be better; the tragedy was that the dreaming ended.”
    —Richard Louv (20th century)