1. GENERAL STRUCTURE 
2. CLASS HIERARCHIES 
3. INPUT/OUTPUT CLASS HIERARCHY 
4. GEOMETRY CLASSES 
5. BSP TREE TYPES 
6. PROCESSING FUNCTIONS 
7. A MINIMAL BSP COMPILER

All interface classes of BspLib (that is, all classes normally used by the user) using dynamic storage are separated into handle and representation classes. The handle class is what the application programmer actually uses. Basically, a handle class is just a pointer to the representation class. Every time a handle is instanced, the reference count contained in the representation is incremented. Dynamic storage will only be freed when this count reaches zero. This scheme allows for efficient copying of objects containing large amounts of dynamically allocated data (without provoking storage maintenance problems, or mandating deep-copy of objects). A representation class for a handle class Test is named TestRep. The representation class should never be used directly, in order to allow for correct reference-counting and avoid problems with handling of dynamic storage! 

Another important concept in BspLib is the so-called chunk. A chunk (implemented via templates Chunk<> and ChunkRep<>) basically is just an array that expands itself if too few indexes are available, performs index validation, and so on. Primitives in BspLib are most of the time either stored in singly linked lists or in such chunks. For example, a 3-D object contains chunks for vertices, faces, textures, mappings, and a list for polygons. The basic array nature of a chunk notwithstanding it is dynamic storage referenced via a pointer, can be copied very easily (using reference-counting to avoid deep-copy, see preceding paragraph) and provides data abstraction, since the implementation is hidden from the user. 

Note that BspLib uses RTTI (run-time type information), so this feature must be supported and enabled in order to compile and use BspLib.

BspLib's I/O hierarchy currently supports input and output of the proprietary AOD and BSP formats, as well as VRML V1.0 input (VRML output is not available). 

The following figure shows the entire I/O class hierarchy of BspLib, arrows denote inheritance: 

 

In the following we describe each of these I/O classes briefly (the only two classes important for an application programmer using BspLib are InputData3D and OutputData3D): 

• SystemIO

This is the base class for all I/O classes (and also all other classes needing host system-services, e.g., message output). It encapsulates host system-dependent code and provides basic facilities like file access, error message output, and the like. 
 
• IOData3D

This is the base class for all classes related to file I/O. 
• InputData3D

This class encapsulates all input functionality. It provides an abstract input interface to the application programmer. The user can instance an InputData3D object, passing the input file's name and an object of class BspObjectList to the constructor. The input file will then be read and parsed automatically, the input format is directly determined from the specified file itself. The passed in BspObjectList will then contain 3-D object representations for all data contained in the input file. That is, after correctly instancing an InputData3D object, the resulting BspObjectList is ready to be used for geometrical processing, rendering, and so on. InputData3D will instance AodInput, BspInput, and VrmlFile objects, according to the detected input format. If automatic format detection is not desired these classes may be used directly. 
• OutputData3D

This class encapsulates all output functionality. It provides an abstract output interface to the application programmer. The user can instance an OutputData3D object, passing the output file's name and an object of class BspObjectList to the constructor. Everything described by the passed in BspObjectList will then be written to the output file upon destruction of the OutputData3D object, the output format being determined by the file name's extension. Alternatively, an InputData3D object may be provided to the constructor, along with the desired output format. The input file name with an accordingly altered file name extension will then be used as output file. OutputData3D will instance AodOutput and BspOutput objects, according to the desired output format. If this semi-automatic output format detection is not desired these classes may be used directly. 
 
• VrmlFile

A VrmlFile object is used to read and parse VRML V1.0 files. This class employs Silicon Graphics' QvLib for parsing. An object of class BRep is used to interface QvLib to BspLib. BRep is capable of tessellating VRML primitives and converting VRML shape nodes to BspLib 3-D objects. This class will also apply necessary transformations and other conversions (e.g., texture transformations via VRML's Texture2Transform node, material application, and so on) to facilitate BspLib's further operation on the VRML scene graph. 
 
• SingleFormat
• SingleInput
• SingleOutput

SingleFormat contains everything AOD and BSP files have in common. SingleInput provides input functionality for the common part of AOD and BSP files. SingleOutput provides output functionality for the common part of AOD and BSP files. 
 
• AodFormat
• AodInput
• AodOutput

These classes contain everything that the AOD format supports in addition to the common format (SingleFormat). 
 
• BspFormat
• BspInput
• BspOutput

These classes contain everything that the BSP format supports in addition to the common format (SingleFormat). 
 
• ObjectAodFormat

Inherits 3-D object properties from BspObject and file format properties from AodFormat. The result is an object that is able to write 3-D information in AOD format. 
 
• ObjectBspFormat

Inherits 3-D object properties from BspObject and file format properties from BspFormat. The result is an object that is able to write 3-D information in BSP format.

The most important graphical entity in BspLib is the BspObject (class BspObject) which describes a single b-rep object, its material properties, and - if already compiled - its BSP tree. In order to be able to operate on many objects at once, BspObjects can be part of a BspObjectList (class BspObjectList). Normally, a BspObjectList is used to represent the entire scene. Processing functions can be invoked for such a list and BspLib will process all objects contained in it in the same way. Thus, the entire scene can be operated upon (for example, BSP compiled) very easily. 

The following figure shows what a scene consisting of multiple objects could look like on the data-structure level: 
 

The most important member of each BspObject is a PolygonList, which essentially is the object's boundary representation. For a description of a BspObject and all its fields see class BspObject. (Remember that all interface objects in BspLib are separated into handle and representation classes. Thus, the actual lists are of classes BSPObjectListRep and PolygonListRep, respectively, although the user uses class BSPObjectList and class PolygonList.) 

Here is a list of all other major geometry-related classes provided/used by BspLib: 

• BoundingBox
• BSPNode
• BSPNodeFlat
• BSPTree
• BSPTreeFlat
• Face
• LineSeg2
• LineSeg3
• Mapping
• Material
• ObjectBSPNode
• ObjectBSPTree
• Plane
• Polygon
• PolygonList
• Texture
• Transform2
• Transform3
• TriMapping
• Vector2
• Vector3
• Vertex2
• Vertex3
• VIndx

4.1 Geometry class descriptions

4.1.1 class BspObject

• List of vertices (chunk of class Vertex3)

An object's vertices are triplets specifying the vertex's x, y, and z coordinates. (Well, actually there is also a w component, but this is normally not used for ordinary vertices.) 
 
• List of polygons (class PolygonList)

A polygon is comprised of a list of vertexindexes. These index into the vertexlist and specify the polygon's vertices as seen from their front-side in clockwise order. The polygonlist contains all polygons prior to BSP compilation in no specific order. During BSP compilation the original polygonlist is dissolved. Afterwards, polygons can only be accessed through the BSP tree. Every BSP node has one or more polygons attached to it. (There may also be BSP nodes with no attached polygons at all, these are separator planes only.) 
 
• List of faces (chunk of class Face)

In contrast to polygons, faces primarily specify surface properties, say, in terms of material and color (there may be color information not already included in the material). A face is comprised of one to many polygons. Originally, faces and polygons have a one to one correspondence. During BSP compilation, however, polygons have to be split. Split polygons retain their original properties apart from geometry, that is, they still belong to the same face afterwards. This also holds for face normals, which, of course, stay the same when polygons get split. Hence, normals are also associated with faces instead of with every polygon. 
 
• List of textures (chunk of class Texture)

This list specifies all textures that may be used by this object. This specification is only done in terms of texture properties, texture coordinates are not involved here! 
 
• List of mappings (chunk of class Mapping)

This list specifies correspondences for texture mapping. This is normally only used during parsing, correspondences will be converted to affine mappings and be contained directly in the faces of the object later on. 
 
• Linked bsp tree (class BSPTree)

If a BSP tree has been compiled for this object, it is contained in this field. Such a BSP tree is dynamically linked. 
 
• Flat bsp tree (class BSPTreeFlat)

In addition to a dynamically linked BSP tree there may be a flat (array) version of it. This is usually used immediately after parsing, because it's easier to parse the tree line by line into an array and build the dynamic version afterwards. 
 
• Attached transformation (class Transform3)

A general transformation matrix may be attached. As long as this transformation is only attached, it has not been applied yet. In order to actually transform the object and alter vertex coordinates accordingly, BspObject::ApplyTransformation() must be invoked. 
 
• Object name

Every BspObject may have a name assigned to it. 
 
• Pointer to next BspObject in list

This field points to the next node in the list of BspObjects.

4.1.2 class BspObjectList

4.1.3 class BoundingBox

4.1.4 class BSPNode

Each BSPNode consists of the following fields: 
 
 

So, each node actually contains two lists of polygons. The first list contains polygons lying in the same plane as the splitter (the first element of the front-facing list) and also facing in the same direction as the splitter. The second list contains polygons facing in the opposite direction (and also lying in the same plane, of course). Simple nodes with only one polygon (i.e, no coplanar polygons) have a front-facing list of just one polygon (the splitter itself) and no back-facing list at all (i.e., the field is NULL). 
Note that the node id allocation is sort of shared between real tree nodes and nodes of polygon lists. That is, each polygon in one of these lists except the splitter has also a unique node id. Node ids of polygon nodes don't occur as node ids of tree nodes. This is done in order to make unique identification possible when storing the entire tree to a file. Each pointer is then replaced by the id of the node pointed to. And because not only other BSP (sub)trees can be pointed to, but also ordinary polygons, unique ids have to be allocated for those nodes too. We said this is true except for the splitter, since the splitter has exactly the same id as the BSP tree node it belongs to. Within BspLib polygon node ids are actually not stored anywhere, because they can be inferred from tree node ids at any time. 

4.1.5 class BSPNodeFlat

4.1.6 class BspTree

4.1.7 class BspTreeFlat

4.1.8 class Face

4.1.9 class Lineseg2, class Lineseg3

4.1.10 class Mapping

4.1.11 class Material

4.1.12 class ObjectBSPNode

4.1.13 class ObjectBSPTree

4.1.14 class Plane

4.1.15 class Polygon

4.1.16 class PolygonList

4.1.17 class Texture

4.1.18 class Transform2, class Transform3

4.1.19 class TriMapping

4.1.20 class Vector2, class Vector3

4.1.21 class Vertex2, class Vertex3

4.1.22 class VIndx

5.1 Polygon BSP trees

The structure of a polygon BSP tree in BspLib can be seen in the following figure: 
 

(Remember that all interface objects in BspLib are separated into handle and representation classes. Thus, the actual tree is of class BSPTreeRep, although the user uses class BSPTree.) 

An overview of all the fields comprising a BSPNode may be found at the description of class BSPNode. This class description also describes how lists of polygons may be attached to each BSPNode. 

5.2 Object BSP trees

The structure of an object BSP tree in BspLib can be seen in the following figure: 
 

 

(Remember that all interface objects in BspLib are separated into handle and representation classes. Thus, the actual tree is of class ObjectBSPTreeRep, although the user uses class ObjectBSPTree.) 

This figure shows an object BSP tree containing two objects that are separated with a single separator plane. The tree itself references objects' bounding boxes which in turn reference the objects themselves. Such an object BSP tree containing multiple objects may be used to create a single object and BSP tree that is the union of all contained objects and BSP trees. This can be achieved by using the ObjectBSPTree::CreateMergedBSPTree() member function. (If the resulting BspObject should be the sole object contained in a BspObjectList the BspObjectList::MergeObjectBSPTree() member function may be used, as described in the preceding paragraph.)

Valid object processing flags are: 

• APPLY_TRANSFORMATIONS
• CALC_PLANE_NORMALS
• BUILD_FROM_FLAT
• CHECK_PLANES
• BUILD_BSP
• BUILD_BSP_WITH_CHECKS
• CHECK_VERTICES
• CALC_BOUNDING_BOXES
• CALC_SEPARATOR_PLANES
• CHECK_EDGES
• DISPLAY_STATS

6.1 Object processing flags

6.1.1 APPLY_TRANSFORMATIONS

6.1.2 CALC_PLANE_NORMALS

6.1.3 BUILD_FROM_FLAT

6.1.4 CHECK_PLANES

6.1.5 BUILD_BSP

6.1.6 BUILD_BSP_WITH_CHECKS

6.1.7 CHECK_VERTICES

6.1.8 CALC_BOUNDING_BOXES

6.1.9 CALC_SEPARATOR_PLANES

6.1.10 CHECK_EDGES

6.1.11 DISPLAY_STATS

First, let's state that we want to use BspLib's classes without prefixing them with BspLib:: every time: 

using namespace BspLib; 

As first real action, we have to create an (initially empty) object of class BspObjectList, which will contain our entire input scene: 

BspObjectList testscene; 

Next, we have to create an object of class InputData3D, which reads and parses our input file, and builds a scene representation in memory (that is, it fills our testscene object), all during its construction: 

InputData3D inputdata( testscene, "test.wrl" ); 

Now, if everything went alright (if not, BspLib will already have exited with an appropriate error message; to avoid this, error response must be overridden/configured) the entire scene specified within the VRML file is in memory, contained in BspLib's 3-D data structures. Given this, we are going to perform some functions to get ready for BSP compilation: 

testscene.ProcessObjects( BspObjectList::CALC_PLANE_NORMALS ); 
testscene.ProcessObjects( BspObjectList::CHECK_PLANES ); 

This is necessary to ensure plane information (plane normal and distance to origin) is available for every polygon and all polygons are indeed planar. (These two function calls could be combined into one by OR'ing the two flags together, avoiding the overhead of scanning the BspObjectList twice.) 

Next, we will compile an object BSP tree for all objects contained in the scene (see Object BSP trees and class ObjectBSPTree): 

ObjectBSPTree objbsptree; 
testscene.PrepareObjectBSPTree( objbsptree ); 

Now, we get to something really interesting: BSP compilation! A polygon BSP tree will be compiled for each object (see Polygon BSP trees): 

testscene.ProcessObjects( BspObjectList::BUILD_BSP_WITH_CHECKS ); 

At this stage, the object BSP tree is valid and contains polygon BSP trees for each of the objects. We, however, want a unified BSP tree in order to be able to write a single object to the output file: 

testscene.MergeObjectBSPTree( objbsptree ); 

Well, we are nearly finished! Let's quickly write our (only) object to the output file using an object of class OutputData3D: 

OutputData3D outputdata( inputdata, IOData3D::BSP_FORMAT_1_1 ); 

That's it! The output file will be written when our outputdata object goes out of scope (and therefore its destructor is invoked). 

Note that, since we have used BspLib's default options we didn't have to configure them. Note also that all that object BSP tree stuff is only necessary since a VRML file may contain multiple objects. If we would have read an AOD file, or a VRML file containing only one object, we could have shortened this process even more!