**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,

- If the current node is a leaf node, render the polygons at the current node.
- Otherwise, if the viewing location
*V*is in front of the current node:- Render the child BSP tree containing polygons behind the current node
- Render the polygons at the current node
- Render the child BSP tree containing polygons in front of the current node

- Otherwise, if the viewing location
*V*is behind the current node:- Render the child BSP tree containing polygons in front of the current node
- Render the polygons at the current node
- Render the child BSP tree containing polygons behind the current node

- Otherwise, the viewing location
*V*must be exactly on the plane associated with the current node. Then:- Render the child BSP tree containing polygons in front of the current node
- 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.

- This tree is just the leaf node
- 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.

- This tree is just the leaf node

- This tree has root node
- 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.

- This tree is just the leaf node
- 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.

- This tree is just the leaf node

- This tree has root node

- This tree has root node

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":

**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**...

**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 ...

**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 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 ...

**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 ...