Editing Binary space partitioning (section)

==Traversal==
A BSP tree is [[Tree traversal|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.<ref name="fuchs80" /> 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

[[File:Example of BSP tree traversal.svg|center]]
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.