Extraction of Boundary Representation

Although the STL file represents a fully conforming grid (see the vertex-to-vertex rule in Section 2) the construction of boundary representation suitable for further processing is not trivial. The whole process is demonstrated on a simple academic example (Figure 1). First of all, the STL file has to be converted to a topologically more consistent form (called background (bg) file thereafter) containing initially a list of vertices (called bg nodes thereafter), each one defined by identification number (id) and three coordinates, and a list of facets (called bg faces thereafter), each one defined by id and three bg nodes ids. The background file is then extended by a list of bg edges, each defined by id and two bg nodes ids. Note that each bg edge must coincide with side (called bg side thereafter) of at least one bg face. Firstly, bg edges corresponding to topological features are detected. These are all those bg sides that are not shared exactly by two bg faces (Figure 2a). Then bg edges corresponding to geometrical (sharp) features are identified. Three criteria are used in the following order. The first criterion is based on finding all neighbouring bg faces that form a continuous plane. Then those bg sides that are shared only by one bg face corresponding to a particular plane formed by at least three bg faces is marked as a bg edge (Figure 2b). The second criterion whether a bg side forms a sharp feature uses the dihedral angle (based on the angle of normals) between the two neighbouring bg faces sharing that bg side. Should this angle exceed a user specified threshold the bg side is marked as bg edge (Figure 2c). Taking into account that the aspect ratio of bg faces corresponds to the curvature of the surface, the third criterion is based on the ratio of heights of two neighbouring bg faces with respect to the shared bg side. Should this ratio exceed a user prescribed threshold and the normals of those bg faces are not same and do not exceed the angle threshold, then the bg side is marked as bg edge (Figure 2d). When all bg edges are identified, bg nodes corresponding to topological features are detected and classified as model vertex. These are all bg nodes that are not shared exactly by two bg edges (Figure 3a). Then bg nodes corresponding to geometrical features are searched for. Again three criteria are used. The first criterion is based on finding all neighbouring bg edges that form a continuous straight line. Then those bg nodes that are shared only by one bg edge corresponding to a particular line formed by at least two bg edges is classified as model vertex. The second criterion classifies as model vertex all those bg nodes that are shared by two bg edges at turning angle above a user prescribed value (Figure 3b). And thirdly, if the ratio of lengths of two neighbouring non-colinear bg edges exceeds a user specified value, the bg node shared by those bg edges is also classified as model vertex (Figure 3b). Note that the current implementation makes no attempt to detect a sharp vertex not connected to any bg edge (e.g. tip of a cone). Note also that each model vertex keeps list of all bg edges connected to it. Once the model vertices are identified, model curves can be determined by traversing the chains of connected bg edges from a starting vertex until ending vertex is reached. Every visited bg edge and its not yet classified end nodes are classified to the corresponding model curve (Figure 4a). Loops of not visited bg edges (there is no model vertex on any of those bg edges) and their end nodes are also classified to particular model curve (Figure 4b). Finally, the model surfaces are identified. This is simply accomplished by assembling all neighbouring bg faces that are not sharing the same bg edge (Figure 5). Each face and its not yet classified corner nodes are classified to the corresponding model surface. Since the border of each model surface is formed by bg edges, that are in turn classified to model curves, it is easy to setup for each surface the list of boundary curves. This makes the extraction of the boundary representation complete.

The problem of the above concept consists in the fact that it gives no guide how to choose the individual thresholds. This is the consequence of the fact that the STL file does not possess information about the original tolerance used to generate it and that the identification of original geometry from the STL file is generally not unique. In other words, there may exist several geometries that are represented by the same STL file generated for the same tolerance. Clearly, setting the threshold to the value corresponding to the ``smallest'' of all geometrical features that are to be detected might not be proper choice as it may result in identification of features that are not considered significant or even worse, that are considered undesirable. A reasonable strategy to tackle this problem is to use an iterative approach in which the algorithm accepts the already identified features from previous iterations. Initially, conservative values, that yield only really ``sharp'' features, are chosen to produce the first boundary representation of the object. Alternatively, no values may be specified at all, resulting in boundary representation based solely on topological features. Next, suitable values are interactively specified for individual entities of the model to further precise the boundary representation. But even such approach can fail to detect some significant features of the object (or can detect them only at the cost of detecting simultaneously some undesirable ones). A very simple example of such a situation is a pipe changing shape from cylindrical to conical surface. If the angle between the cylindrical part and the conical part is small enough then the specification of the appropriate threshold angle will result in detecting bg edges between bg faces on each of both surfaces. Therefore the identification procedure cannot rely only on the threshold values and must accept also an interactive input of manually selected (or deselected) bg edges. This makes, however, the process of the extraction of boundary representation tedious.

*Daniel Rypl
2005-11-05*