2. ViewBSP Input and Output Formats

ViewBSP is able to read standard VRML V1.0 files. Additionally, it can read the proprietary AOD (*.aod files) and BSP (*.bsp files) formats. AOD is a simple text-format that can be used to specify objects consisting of vertices and faces (indexes of vertices in clock-wise order). It has primarily been designed for hand-editing simple objects. BSP is the most important format that ViewBSP is able to write, because it is the only one containing BSP tree information. It can of course also be read back in, to display objects that have already been bsp-compiled earlier on. Basically, the BSP format is identical to the AOD format but contains additional information, like the BSP tree, or a list of split polygons that have been created during BSP compilation.

This section contains the following subsections:

2.1 VRML V1.0 Issues (*.wrl files)
2.2 ASCII Object Data Format (*.aod files)
2.3 BSP Format (*.bsp files)

2.1 VRML V1.0 Issues (*.wrl files)

ViewBSP is able to parse VRML V1.0 files. However, not all VRML nodes are supported. Unsupported nodes are mostly specific to the WWW or other information not directly related to polygonal geometry, like camera and lighting information. The VRML LOD node is also unsupported!

The following is a list of all supported VRML nodes:

Supported shape nodes:
Cone
Cube
Cylinder
IndexedFaceSet
Sphere
Coordinate3
Material
MaterialBinding
Texture2
Texture2Transform
TextureCoordinate2
ShapeHints

Supported transformation nodes:
MatrixTransform
Rotation
Scale
Transform
Translation

Supported group nodes:
Group
Separator
Switch
TransformSeparator

Generally speaking, the VRML format is not really conducive to BSP compilation. In order to compile a BSP tree for a scene, the entire geometry has to be known explicitly. To achieve this, ViewBSP performs the following operations after parsing the VRML scene graph:

All VRML primitives will be tessellated. The resolution of this tessellation can be altered via the Compiler Options in tessellation steps per PI/2.
All transformations will be applied, and new vertices will probably be created in the process. That is, if the same object is instanced four times via USE with different transformations applied, this object will actually exist explicitly four times afterwards.
Texture coordinate transformations will be applied to yield explicit texture coordinates.

In order to facilitate BSP compilation, ViewBSP makes several assumptions about the geometry contained in the VRML scene graph. Most important of all, all polygons have to be convex! ViewBSP will assume that this is indeed the case but never check for it explicitly, i.e. if non-convex polygons are contained in the input data the compiler's behavior is undefined.
The only field used from a ShapeHints node is vertexOrdering. If nothing is specified, COUNTERCLOCKWISE will be assumed. Note that this has to be done since polygons with their front-side undefined cannot be BSP compiled!

2.2 ASCII Object Data Format (*.aod files)

Every AOD file has to start with the line:

#AOD V1.1 ascii

The rest of the file is structured in so-called sections, each starting with a '#'. Comments starting with a ';' are ignored throughout the file.
The following sections are valid within an AOD file and they have to be specified in the following order (most of them may be omitted, though):

#vertices
#faces
#facenormals
#faceproperties
#correspondences
#textures
#palette
#scalefactors
#setorigin
#xchange
#worldlocation
#camera

We are now going to describe each section's format in detail:

2.2.1 Section 'vertices'

This section defines all vertices of a polygon. Each vertex has to be specified on its own line, like so:

50.0, 60.0, 70.0 ;these are the (x,y,z) coordinates of the vertex

2.2.2 Section 'faces'

This section defines all faces of a polygon. Each face has to be specified on its own line by listing the indexes (numbers starting with 1) of its vertices in clock-wise order (as seen from the front side), like so:

1, 2, 3 ;these are a triangle's vertex indexes in clock-wise order

2.2.3 Section 'facenormals'

This section specifies face normals (not vertex normals!) for each face in the same format as vertices are specified. Normally, this section can be omitted. ViewBSP will calculate face normals from the face specifications themselves in this case. If an AOD file is written using ViewBSP they will be included, though.

2.2.4 Section 'faceproperties'

This section specifies material properties for faces, in the following format (one such line per face):

<shading-type> [<color-model>] [<parameters>] ; face xx

Since ViewBSP is only a simple object viewer, most of this shading information is ignored and simply written into the output file unaltered.

<shading-type> can be one of the following (don't specify the <> characters!):

no_shad        ; no shading, constant color
flat_shad      ; flat shading
gouraud_shad   ; gouraud shading
afftex_shad    ; affine texture mapping
persptex_shad ; perspective corrected texture mapping

<color-model> can be one of the following (don't specify the <> characters!):

indexed_col ; indexed color (8bit palette index)
rgb_col ; rgb color, separate color channels

If <shading-type> uses a texture map, <parameters> must be the texture's name in double quotation marks (like "my_texture_name"). In this case <color-model> must not be specified! Textures are identified via their names only, the correspondence between texture names and their files (file names) is established in the #textures section.

If <color-model> is omitted and the shading type uses color, indexed_col will be assumed.

<parameters> is the color index (unsigned integer: 0..255) for indexed_col and three float values for rgb_col, specifying the red, green, and blue components of the color, respectively.

Some examples for valid face-property specifications:

flat_shad rgb_col 1.0 1.0 0.0 ; face #1 (flat shading, r=1 g=1 b=0)
persptex_shad "texname" ; face #2 (texture-mapped with "texname")
no_shad 20 ; face #3 (fill face with palette color 20)

2.2.5 Section 'correspondences'

This section specifies point correspondences for texture-mapped faces. For each face there must be a block of lines like so:

5, 3, 7, 1 ; list of vertices to be mapped
0.0, 0.0    ; (u,v) coordinates for first vertex (index 5)
1.0, 0.0    ; (u,v) coordinates for second vertex (index 3)
1.0, 1.0    ; (u,v) coordinates for third vertex (index 7)
0.0, 1.0    ; (u,v) coordinates for fourth vertex (index 1)

The first line contains a list of vertex-indexes followed by as much lines as indexes have been specified. Each of these following lines contains a single (u,v) coordinate.
The list order of faces in #correspondences is from faces with lower to faces with higher number. If a face is not texture-mapped at all, it is simply omitted from this section!

2.2.6 Section 'textures'

This section specifies a list of textures. That is, file names corresponding to texture names and texture width and height, like so:

128/128 "my_texture_name" c:\textures\mytex1.tga ; one line for each texture!

2.2.7 Section 'palette'

This section must have only one entry (line). It can be used to specify the filename of a palette file (768 bytes, 256 colors with 3 bytes in r,g,b order each. Only the least significant 6 bits of each byte will be used, i.e. the palette must be in standard VGA format). Mostly, this line will be written to the output file unaltered, without ever being used! If some faces use indexed colors and ViewBSP is able to locate the palette file, however, it will be used to translate color indexes to (r,g,b)-triplets. Note that the color specification of such a face will then be changed from indexed_col to rgb_col! This conversion from color indexes to (r,g,b)-triplets can be explicitly enabled/disabled via the Compiler Options.

2.2.8 Sections 'scalefactors', 'setorigin', 'xchange', 'worldlocation', 'camera'

These sections should not be used anymore and ignored on parsing!

2.3 BSP Format (*.bsp files)

BSP files use the same format as AOD files for most of their sections. Some sections have different meaning, though, and some are unique to BSP files. Every BSP file has to start with the line:

#BSP V1.1 ascii

The following sections are new with BSP files:

#polygons
#bsptree

The following sections have a different format/meaning in BSP files:

#faces
#correspondences

2.3.1 Section 'polygons'

This section defines all polygons of an object in the same format as #faces are specified in an AOD file. That is, polygons consist of vertex-indexes listed in clock-wise order as seen from their front-side. The reason for the altered section-name is the different meaning of faces in a BSP file:

2.3.2 Section 'faces'

Since faces may be split into multiple polygons during BSP compilation, faces are specified by listing the numbers (id's) of their constituting polygons. That is, each face consists of a list of polygons that this face consists of, like so:

1, 87, 90 ; this face consists of polygon 1, 87, and 90

In this example face 1 now actually consists of three polygons. For some reason the BSP compiler had to split face 1 two times, first creating the new polygon 87 and then polygon 90.

2.3.3 Section 'correspondences'

The format of point correspondences for texture-mapping is entirely different in BSP files as compared to their AOD counterpart. There are as many blocks in this section as there are texture-mapped faces. That is, this section operates on faces, not on polygons! Each correspondence for a texture-mapped face consists of exactly 6 lines. The first three contain the (x,y,z) coordinates of three points on the face's plane. The second three lines specify (u,v,w) coordinates for these points in texture-space. Like so:

0.0, 170.0, 0.0 ; object-space point 1 (x,y,z)
0.0, 250.0, 80.0 ; object-space point 2 (x,y,z)
25.0,    2.0, 80.0 ; object-space point 3 (x,y,z)
0.0,   128.0, 1.0 ; texture-space point 1 (u,v,w)
128.0,   0.0, 1.0 ; texture-space point 2 (u,v,w)
128.0, 128.0, 1.0 ; texture-space point 3 (u,v,w)

What this actually specifies is an affine mapping defined by three point-correspondences. For each point on the face's plane, texture coordinates can be calculated using these six vectors.

2.3.4 Section 'bsptree'

This section describes the BSP tree (that is to say, it is really important!). Each line corresponds to either a BSP tree node or a node of a list of polygons attached to a tree node. Since polygons that lie in the same plane are not stored in their own BSP nodes, this distinction is necessary. Every line starts with a unique node number, followed by a ':' and the node description. Nodes are described in key/value pairs. That is, there are always pairs of a key (a string) followed by the corresponding value (an integer). Polygon 20 would be specified as polygon 20 ("polygon" being the key and "20" being the value, i.e. the polygon's id).

The following table describes all possible key/value pairs:

key (string)	value (integer)
polygon	polygon id (splitter)
frontlist	nodeid of front-list
backlist	nodeid of back-list
fronttree	nodeid of front-subtree
backtree	nodeid of back-subtree
plane	plane specification (four float values)
boundingbox	subtree bounding box (six float values)

An example BSP tree specification could look like this:

1: fronttree 2 backtree 5 plane 0.0 1.0 0.0 50.0
2: polygon 1 fronttree 3
3: polygon 2 frontlist 4
4: polygon 3
5: polygon 5 backlist 6
6: polygon 4

The actual BSP tree would then look like in Figure 1:

A bounding box is specified by its minimum and maximum extents in all three coordinate axes, like so:

5: polygon 5 fronttree 6 backtree 28 boundingbox -2.0 -2.0 -2.0 2.0 2.0 2.0

These bounding boxes can for example be used to cull entire subtrees if the bounding box doesn't intersect the viewing frustum at all.

2.3.4.1 BSP Tree Parsing Issues

When parsing the BSP tree contained in a *.bsp file it is sensible to parse each line independently. Each line is parsed and inserted sequentially into an array representing the entire tree. Since the node numbers (before the colon) in each line are always sequential (counting from one up) they can be ignored. Thus, each new line is stored into the next free array index. Values of fronttree, backtree, frontlist, and backlist keys then refer to array indexes where the tree or list is continued. Each array element contains at most one polygon. Normally, it contains exactly one polygon, but there may be nodes consisting of separator planes only. If a BSP tree without separator plane only nodes is desired, multiple objects have to be merged (using "Tools/Merge Objects") prior to compilation. After the BSP tree has been read and the array has been filled in correctly, a dynamically linked version of the tree can be built recursively if desired. For most purposes this is not necessary, though, because the tree will never change anyway. If the tree is always represented by an array it can be allocated in a single contiguous memory block, and following links is just stepping to another index in the array. Needless to say, this is much faster than following actual pointers for each link.