into two polygons and move them to the respective lists of polygons behind and in front of P. If that polygon lies in the plane containing P, add it to the list of polygons at node N. Apply this algorithm to the list of polygons in front of P. 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. 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. 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