The BSP tree construction and rendering/traversing algorithm is implemented as a part of the practical training. The core code (written in ANSI C) has been taken from Graphics Gems [2] and modified to suit the needs. Certain additions have been made to accept the 3D objects in standard OFF format files as the input and to display the rendered output using a simple viewer using the standard X Window libraries.
The algorithm implemented here takes care of only objects consisting of convex polygons, as the polygon splitting algorithm is implemented only for convex polygons. This is because convex polygons are generally easier to deal with in BSP tree construction than concave ones, because splitting them with a plane always results in exactly two convex pieces. Furthermore, the algorithm for splitting convex polygons is straightforward and robust. Splitting of concave polygons, especially self intersecting ones, is a significant problem in its own right.
The choice of the the dividing polygon is made by testing the first N polygons in the list (denoted by the global variable MAX_CANDIDATES in the program written) and checking for the number of intersections of each polygon with the other polygons in the list. The polygon giving rise to the minimum number of intersections is chosen as the dividing polygon. This is an O(N2) process. Ideally, N should be equal to the number of polygons in the list (although even this does not guarantee the minimum number of intersections in totality, as this will also affect the decision for the choice of the next dividing polygon in the recursive algorithm), but practically it is taken anywhere from 5-100 depending on the tradeoff between the number of resulting output polygons due to the artificial intersections (the intersections resulting from division of the polygons in the list by the dividing polygon) and time. Large N is recommended where the time taken for traversing of the tree (for displaying) for various viewpoints is more important that the time required for the construction of the BSP tree, as in the case of map constructors in DOOM like games where the BSP tree is the input to the renderer.