Multi-threaded Implementation

The algorithm can be easily divided into two threads: a Simplify-Thread and a Render-Thread. The Simplify-Thread traverses the Vertex Tree and changes the Active Triangle List accordingly by inserting or removing triangles. The Render-Thread continually renders the triangles of the Active Triangle List. This approach has the disadvantage that holes appear in some frames, if the Render-Thread draws triangles which vertices had been corrected to fit another triangle inside the hole, but the appropriate triangle was not yet inserted to the Active Triangle List by the Simplify-Thread. Synchronizing the access to the Active Triangle List would disgrace the advantage of two consecutive threads. A detailed consideration shows, that traversing the Vertex Tree requires much more time than the actual collapse and expand operations. Hence, following approach can be developed: The Simplify-Thread only traverses the Vertex Tree and decides which nodes should be collapsed or expanded. These nodes and the operations are inserted into a queue, which is read from the Render-Thread. The Render-Thread executes the actual collapse and expand operations, corrects the vertices and adapts the Active Triangle List. Then the scene is rendered. This approach requires only synchronized access to the queue and both threads are able to run almost independently. To ensure a correct behavior, a copy of the node's label (active, boundary, inactive) has to be stored additionally in each node of the Vertex Tree. This copy of the label indicates the current state of the node for the Simplify-Thread. This ensures that nodes, which are waiting for a collapse or expand operation, are not inserted again into the queue and the Simplify-Thread is able to look for other nodes, which should be collapsed or expanded.