Technical Description
The tool reads a VRML file and generates LODs for each IndexedFaceSet
and IndexedLineSet. As described in the picture below the program replaces
each IndexedFaceSet by a LOD node and inserts in this node a new IndexedFaceSet
for each Level of Detail. It can happen that faces are collapsed into lines.
If this lines are equal to an edge of another face this lines will be discarded.
But the remainding lines will be written out into an extra IndexedLineSet.
In this case the IndexedFaceSet and IndexedLineSet node of this Level of
Detail must be surrounded by a Separator node (e.g. see LOD 1 in the picture
below).
The LOD-generator can't accept some bindings (PER_FACE, PER_PART, PER_VERTEX)
these bindings are 1:1 relations and they can't maintained if different
LODs uses the same materials or normals. For that reason these bindings
will be transformed into an appropriate indexed binding and indices will
be sythesized. In this case it is necessary to write out an additionally
MaterialBinding respectively NormalBinding node.
Because the tool splits non convex faces into triangles the face type
can be set to CONVEX. If the face type isn't convex in the actual state,
the program generates an additional ShapeHints node for setting the type
to convex.
If the program has generated one or more additional nodes (MaterialBinding,
NormalBinding, ShapeHints) than a surrounding Separator must be generated.
If a name was assigned to the original IndexedFaceSet using the DEF
statement the DEF will be moved before the outermost node. This is either
a Separator (e.g. in the picture below) or the LOD node.
IndexedLineSet nodes are handled similar. Polylines will always be split
into single lines.
Outline of the Method
- Parse the inputfile with lex and yacc - a complete parsetree will be
generated
- Traverse the tree for setting up the dependencies between the nodes.
This includes information such as: e.g. which Coordinate3, Material, Normal
node uses a IndexedFaceSet node, which bindings are currently used, the
current transformation matrix.
- If the camera height angle isn't explicit set by the commandline option
-c a camera is searched by traversing the
tree. The program takes the first perspective camera found in the inputfile.
If no camera was found, the default camera is taken (height angle = pi/4).
- If option join is specified traverse the tree and try to join nodes
such as Coordinate3, Material, Normal, IndexedLineSet, IndexedFaceSet and
other nodes. For a detailed description see: Joining
VRML nodes
- Traverse the tree for:
- Setup the specific data structures for coordinates, materials, normals
and texture coordinates:
- materials, normals and texture coordinates will be inserted into binary
trees. The insert-methods removes automatically doublettes.
- coordinates will be inserted into an octree
data structure. The insert-method removes automatically doublettes.
For a detailed description see: Inserting
coordinates into an octree
- Generate LODs for each IndexedFaceSet and IndexedLineSet:
- Reset the datastructure with the coordinates which are used by this
node to LOD0 and delete all references from this coordinates to faces (lines).
- Insert the faces (lines) into an datastructure FaceSet (LineSet) for
LOD0. The insert-method removes faces (lines) which are equal or part of
already inserted faces (lines). Also the insert-method is setting up the
reference lists from each coordinate to the faces (lines) which uses this
coordinate for LOD0. Further the insert-method splits quadrangles into
triangles if they are not convex or too much distorted in 3D (see options
-q, -s, see:
Split algorithm for quadrangles). Faces
with more than four vertices will always be split into triangles using
a triangulator. The faces are inserted internally
in a linear list.
- Generate the next lod of the coordinates using the reference lists
to the faces (lines). The following algorithm is applied to all leaf-nodes
whose depths have the depth of the octree:
Combine the leaf-nodes with the greatest depth into parent-nodes. This
is made by selecting a representative of
the leaf nodes, setting the data of the parent-node to the data of the
representative and converting the parent-node into a quasi leaf-node (if
in a node the variable lod >= 0 the node is supposed to be a leaf-node.
It doesn't matter that possibly the node has subnodes - these subnodes
will be ignored by the methods). The selection of the representative is
made using various algorithms (errorarea,
errorvolume, weightedmean).
Note: for lines only the weightedmean algorithm will be used.
The depth of the resulting tree is decreased by one (because the subnodes
of the new quasi leaf-nodes are ignored). If the difference in the count
of the coordinates of the new lod and the old lod is less then mindiff*(count
of coordinates old lod) then the algorithm is applied again to the tree.
- Create a new FaceSet (LineSet) for the next lod and fill this FaceSet
(LineSet) with the faces (lines) of the next lod. The faces (lines) of
the current FaceSet (LineSet) are mapped onto the representatives of the
coordinates in the next lod (see: Getting
the representative of coordinates). Doublettes and collapsed faces
(lines) will be discarded. If a face is collapsed into a line and it is
equal to an egde of a face or the line is equal to a line already in the
set, the line will be eliminated. For each LOD of an IndexedFaceSet the
remainding lines will be witten out into an extra IndexedLineSet node.
Also the the reference lists from each coordinate to faces (lines)
of the new generated lod which uses this coordinate will be generated.
- return to step 3 until the depth of the octree for the coordinates
is 1.
- Calculate the ranges of the LODs
- Print out the nodes.
Summary of used Algorithms