Binary Space Partitioning - Traversal

Traversal

A BSP tree is traversed in a linear time, in an order determined by the particular function of the tree. Again using the example of rendering double-sided polygons using the painter's algorithm, to draw a polygon P correctly requires that all polygons behind the plane P lies in must be drawn first, then polygon P, then finally the polygons in front of P. If this drawing order is satisfied for all polygons in a scene, then the entire scene renders in the correct order. This procedure can be implemented by recursively traversing a BSP tree using the following algorithm. From a given viewing location V, to render a BSP tree,

  1. If the current node is a leaf node, render the polygons at the current node.
  2. Otherwise, if the viewing location V is in front of the current node:
    1. Render the child BSP tree containing polygons behind the current node
    2. Render the polygons at the current node
    3. Render the child BSP tree containing polygons in front of the current node
  3. Otherwise, if the viewing location V is behind the current node:
    1. Render the child BSP tree containing polygons in front of the current node
    2. Render the polygons at the current node
    3. Render the child BSP tree containing polygons behind the current node
  4. Otherwise, the viewing location V must be exactly on the plane associated with the current node. Then:
    1. Render the child BSP tree containing polygons in front of the current node
    2. Render the child BSP tree containing polygons behind the current node

Applying this algorithm recursively to the BSP tree generated above results in the following steps:

  • The algorithm is first applied to the root node of the tree, node A. V is in front of node A, so we apply the algorithm first to the child BSP tree containing polygons behind A
    • This tree has root node B1. V is behind B1 so first we apply the algorithm to the child BSP tree containing polygons in front of B1:
      • This tree is just the leaf node D1, so the polygon D1 is rendered.
    • We then render the polygon B1.
    • We then apply the algorithm to the child BSP tree containing polygons behind B1:
      • This tree is just the leaf node C1, so the polygon C1 is rendered.
  • We then draw the polygons of A
  • We then apply the algorithm to the child BSP tree containing polygons in front of A
    • This tree has root node B2. V is behind B2 so first we apply the algorithm to the child BSP tree containing polygons in front of B2:
      • This tree is just the leaf node D2, so the polygon D2 is rendered.
    • We then render the polygon B2.
    • We then apply the algorithm to the child BSP tree containing polygons behind B2:
      • This tree has root node C2. V is in front of C2 so first we would apply the algorithm to the child BSP tree containing polygons behind C2. There is no such tree, however, so we continue.
      • We render the polygon C2.
      • We apply the algorithm to the child BSP tree containing polygons in front of C2
        • This tree is just the leaf node D3, so the polygon D3 is rendered.

The tree is traversed in linear time and renders the polygons in a far-to-near ordering (D1, B1, C1, A, D2, B2, C2, D3) suitable for the painter's algorithm.

Read more about this topic:  Binary Space Partitioning

Other articles related to "traversal":

Graph Traversal
... In computer science, graph traversal is the problem of visiting all the nodes in a graph in a particular manner, updating and/or checking their values along the way ... Tree traversal is a special case of graph traversal ...
Non Recursive Inorder Traversal For A Threaded Binary Tree
... As this is a non-recursive method for traversal, it has to be an iterative procedure meaning, all the steps for the traversal of a node have to be under a loop so that the same can be applied to all ... We will consider the INORDER traversal again ...
Bounding Interval Hierarchy - Operations - Ray Traversal
... The traversal phase closely resembles a kd-tree traversal One has to distinguish 4 simple cases, where the ray just intersects the left child just intersects the right child intersects both children ... Traversal continues until a leaf node is found ... It is also possible to add a 5th traversal case, but which also requires a slightly complicated construction phase ...
TCP Hole Punching
... TCP hole punching is a commonly used NAT traversal technique, for sending 2-way messages between nodes in an Internet computer network ... The term "NAT traversal" is a general term for techniques that establish and maintain TCP/IP network and/or TCP connections traversing network-address-translation (NAT) gateways ... NAT traversal techniques are typically required for client-to-client networking applications, especially peer-to-peer and Voice-over-IP (VoIP) deployments ...
Comparison Of Layout Engines (Document Object Model) - Traversal
... interfaces provide easy-to-use, robust, selective traversal of a document's contents Trident Tasman Gecko WebKit KHTML Presto Interface NodeIterator DOM2 root No ? 1.9.1 ? ? 1.0 whatToShow ...