Mechanisms of Persistent Identification of Topological Entities in CAD Systems: A Review

1. Introduction

Existing CAD design systems are parametric and history-based feature modeling systems which uses a parametric model definition of the CAD object with a boundary representation (b-rep) model of the final shape. The parametric definition comprises of a variety of information, such as parameterized feature instances, constraints, geometric entities, etc. The order of creation of feature instances is defined as the design model history [1]. In the feature based CAD modeling systems, successful retrieval of the topological entities in necessary once a designer wants to translate his design model from one CAD system to another CAD system. CAD model translation can be of two types-direct translation and translation based on XML format neutral macro file. The limitation of direct translation is, the design intent (product creation and modification history) could be lost which should not be altered in successful CAD data translation. Macro-parametric approach enables the CAD designer to able to exchange the parametric information of CAD models comprising of product creation history and modification history. In this approach, a set of standard modeling commands is defined in the format of an XML format neutral macro file. The history based macro-parametric approach of KAIST (iCAD lab) solves these issues by using XML format neutral macro file (Fig. 3, Fig. 4). Once a CAD design model is modified/new feature is created, old topological entities lost their identity/previous feature modification information [18], [20].

Persistent identification problem should be solved by identification of all the referenced topological entities every time after design modification. This mechanism attaches names to topological entities after creation based on the operations of creation and retrieve those topological entities every time after the modification occurs. Names are necessary to represent the entities referenced in the parametric specification whether they exist in the model or not. Where every single constructive gesture creates several entities, which have to be distinguished from each other and therefore named. The names shall be defined using such a way to generate a new geometric model, the geometric entity, referenced by a name in the re- evaluated model is the same as the same as the one referenced by the same name in the initial model. Two different kinds of geometric and topological entities may be distinguished [1], [2], [3], [4], [5], [6], [17], [18], [20]. There are several distinguished researches from last 20 years about persistent identification mechanism, which all have both their advantages and disadvantages. But until now, there are no standards for persistent identification mechanism and consistently using them in all parametric features based CAD systems. The focus of this review paper is to theoretically classify the persistent identification mechanism and analyze the existing researches for their advantages and limitations to conclude on a new approach to solve the current problems to make a standard [18], [20].

2. Parametric CAD systems

In the feature based design, part models are created. To redesign a part, features are edited; their descriptions are automatically modified and recorded by the design interface and are compiled serially by a design compiler (CAD feature editing operations). Feature based parametric modeling systems usually define models by a sequential history of modeling steps. Each step contains operations and parameters. A parametric modeler is a system for geometric design which preserves not only the designed object but also the set of constructive gestures used to design it.

It follows a two-fold data structure. They record the geometric shape of the currently designed product, often as a Boundary representation model as representation of current instance. They record the conceptual design of which the current instances results, its parametric specification, which consists of constraints represented as expressions that reference the current model entity which encompasses various kinds of operations.

This two-fold data structure raises three different types of issues: Define a data model that provides for the simultaneous exchange of expressions, of variables involved in these expressions & of variables involved in these expressions and of values of these variables. Topological naming problem which are to assign persistent names to geometric and topological entities that may not exist or that may cut into different parts in the geometry of the current instance. And this topological naming problem can happen at the design process which is entity naming problem. Or after design reevaluation which is known as name matching problem.

In feature based design, editing operations can be classified into the following broad categories:

E1: Inserting or deleting a feature. E2: Changing feature attributes. E3: Modifying dimension values.
E4: Changing the dimension schemes.
E5: Changing the feature shape definition. E1 to E4 requires name matching.

3. Persistent identification mechanism

In the parametric CAD modeling systems, the structure of topological entity naming should be unique, must be applicable for same type of topological entities (applicable to generally for all entities), independent of all parametric CAD modeling systems and which will generate unambiguous names (Fig. 2). Topological entities created with different feature modeling operations should be retrieved and named using the same method. If the persistent identification mechanism is dependent on CAD systems, the mechanism may not be applicable to each type of CAD systems (topology based CAD system/geometry based CAD system) which will drive the integration between heterogeneous CAD systems with successful CAD data exchange impossible. And the naming rule should be unambiguous to retrieve the names of topological entities modified through topology splitting and topology merging.

And persistent identification should be done with the minimum data required for CAD model translation; that are feature type, attributes of a feature, parameters of a feature, local coordinates of a feature, etc. Naming can be classified as basic naming and ambiguity solving part (Fig. 1). Basic naming involves attaching names with topological entities associated with that feature (face, edge, vertices) based on their unique properties. But in different cases, topological entities could have same basic name; which is defined as ambiguity problem, because feature modification information cannot be reflected in the original basic name of the entities. Ambiguity could arise from topology merging or topology splitting case, or from pattern feature operations while modifying the CAD model. It can also happen during the creation stage of CAD model. For solving these issues, name matching should be conducted between homogeneous CAD systems (name matching) or heterogeneous CAD systems (name mapping) (Fig. 1). Name matching involves two different ways. Local matching between the modified topological entities (1: N comparison) or global matching between topological entities (N: N comparison). Local matching compares a single entity from evaluated model with all the referenced entity is the pre-edit model; whereas global matching tries to match among the subset of topological entities in pre-edit model of with the subset of topological entities in post-edit model [12], [13], [14], [21].

3.1. Basic naming

Persistent identification mechanism can be broadly classified into two different types in case of basic naming; Topology based or geometry based which is dependent on the CAD systems. In can also be a combined method comprised of topology and geometry. CATIA follows topology based basic naming, where SolidWorks follows geometry based basic naming [22], [23] (Fig. 5). Previous researches shows, the basic naming order of topology based method can be either of face > edge > vertex or else. In face > edge > vertex order, faces are named first where face names are used to assign names to edges and vertices. Entities can also be classified as invariant or contingent entities. Significant researches are mentioned through Fig. 6.

Invariant entities:

Geometric or topological entities which can be completely and unambiguously characterized by the structure of a constructive gesture and its input parameters, independently of involved values.

Contingent entities:

Geometric or topological entities that results from an interaction between the pre-existing geometric model and invariant entities resulting from a particular constructive gesture.

3.2. Ambiguity solving

Ambiguity occurs in CAD part models when after feature creation operations (product design phase) or feature editing operation (design review phase), two or more topological entities have the same basic name (topology splitting, Fig. 8) or two or more entities whose basic names were different were added into one (topology merging, Fig. 7). Then a different phenomenon arises when basic naming based on topology is not only sufficient to solve this problem. Ambiguous entities can be distinguished using geometry based method, because their geometric dimensions should be something different from the initial one (Fig. 9).

In topology based naming of iCAD lab KAIST, ambiguity problems are solved with the Object space information system(OSI) based ambiguity solving method; which enables the geometry comparison of entities and then new entity name is returned which contains original basic name with ambiguity solving information [20], [13], [18] (see Fig. 10).

3.3. Name matching

Name matching is required between topological entities of initial CAD model and corresponding topological entities of re-evaluated CAD model. And after name matching if there in any modified topological entities then they are given different names from the initial model to identify them persistently. Also, name matching can be of global matching or local matching. Local matching compares identified entity with the other entities in the initial model; whereas global matching compares the subset of topological entities of new model with the subset of topological entities in old model.

Its N: N matching technique which requires much computation time and skill with greater accuracy. But In case of local matching, it’s 1: N leaves lower accuracy of matching result and fastest computational ability. In previous studies, different approaches were followed. In the persistent identification mechanism of iCAD lab KAIST (topology based method), local matching between entities are applied. If one entity is modified all the corresponding entities are added to the candidate matching set (Fig. 11).

Name mapping is the matching between entities when a model from one CAD system is converted into CAD model of another CAD system and the new model requires some design review; then the corresponding topological entities need to be matched (Fig. 12).

3.4. Persistent identification problems of commercial CAD systems

Fig. 13, Fig. 14, Fig. 15, Fig. 16, Fig. 17 are used to explain the existing problems of persistent identification in commercial CAD systmes. Fig. 14 describes the problems of SolidWorks, which occurs during modeling of a block. Similarly, Fig. 15 describes the persistent identification problem of FreeCAD. Fig. 16, Fig. 17 is used to describe the persistent identification problem of Siemens JT (topology splitting and topology merging).

4. Classifications of persistent identification mechanisms

Persistent identification can be classified based on 6 different mechanisms. Previous researches try to classify persistent identification mechanism based on entity type/entity information used for classification. We have classified persistent identification system based on the mechanism it followed.

4.1. Feature orientation based persistent identification

For achieving product modeler independence from the recorded design history, Capoyleas mechanism substitute all design reference such as the edge to be rounded by generic persistent names. During design compilation, these generic names are first persistently mirrored to geometric references in the B-rep a solid modeler. When the design is changed a new variant is constructed based on the generic descriptions and on the history of the previous variant. This describes matching generic names that may not be unambiguous to b-rep entities in the new design variant.

This mechanism relies with the assumption that the order in which the features are defined is not changed, but these restrictions can be relaxed with suitable adjustments to the algorithms. The elements referenced for constituting the particular feature are always evaluated with respect to the geometry that exists at the time when the feature is added to the design.

Feature orientation: The topological entity information derived from the feature modelling procedure is called as feature orientation. Feature orientation information can be broadly entitled based on the extrusion direction or the spin of revolution.

Local orientation: Feature Orientation information which is derived locally from the boundary elements geometry information is called local orientation which is based on the direction of adjacent face which involves an edge and on orientation of faces in the solid boundary.

Le = [f1, v1, v2] or Le = [f2, v2, v1]
Or
Le = [f1, f3, f4] or Le = [f2, f4, f3]

Or in the case of vertices,
Sv = sgn ((n1xn2) n3)
Lv1 = [f1, f3, f2] Lv2 = [f1, f2, f3]
Lv3 = [f1, f2, f4] Lv4 = [f1, f4, f2]

Distinguishing edges with feature orientation:

Edge = [F, f, c]
Where F = feature
f = face
c = +/− according to whether the edge is used by f in the direction of feature orientation.

Distinguishing vertices with feature orientation:

Vertices = [F, f′, I]
Where F = feature
f′ = incident face that is not adjacent to the intersection edge of the feature F.
I = records the sign of inner product.

Naming intersection edges:

Ee = [Ce, Le, fe]
Where, Ce = all the adjacent faces of the topological entity.
Le = local orientation. Fe = feature orientation.

Naming intersection vertices:

Ev = [Cv, Lv, fv]
Where, Cv = all the adjacent faces of the topological entity.
Lv = local orientation. Fv = feature orientation.

And persistent naming starts with naming of the intersection edges, secondly with the intersection edges and non-intersecting edges(Fig. 18 [1]).

In Chen’s research, name matching is performed based on feature orientation method followed by Capoyleas research.

Matching a vertex:

In Chen’s research of topological entity matching, vertices are being matched to define the constraints, to build the datum features, to be utilized by changing features. In the feature dimensioning case, vertex in the three dimensional space need to be identified. Moreover according to their method, while modifying the features they can accept multiple number of vertexes with the same name.

Matching an edge:

Name of the edges are given by defining constraints to construct the datum features, to be utilized by chamfers and rounds features. For constraints and datum features ambiguous edges are acceptable if they are collinear line segments which contains constraint orientation.

Matching a face:

Face matching is performed to determine the limits of feature attachment operations, defining draft operations, identifying a sketch plane or constraining a datum definition. The degree of entity matching with which a face should be matched varies with the feature modelling operation. This mechanism doesn’t consider ambiguity in naming matching phase. So as a whole, they tried to name all the entities which are unnecessary. They also didn’t consider the ambiguity in the naming matching phase. Implementation is also very difficult [2], [3], [4].

4.2. faceIDgraph based persistent identification

StepID = history of modeling steps. FaceID = [StepID, faceIndex, SurfaceType]
EdgeID = [adjFaceIDs, endFaceIDs, edgeIntersCode]
VertexID = [adjFaceIDs, vertexIntersCode]
faceIDGraph is updated every time when topology of the model changes. Incoming edges to faceIDNode reflects incoming edges which will change and outcome represents the outgoing edges, what happened to that edges(Fig. 19).
1. Download : Download high-res image (48KB)
2. Download : Download full-size image
Fig. 19. Name attaching system by Kripac’s method [5], [6].

If there is more than one incoming edge in FaceIDNode then face is merged. If there is more than one outgoing edge in FaceIDNode then face is split. And if no outgoing edge from faceIDNode then faces are living in the same state.Itproposes an intersecting structure for identifying contingent entities based on face history(creations, merges and deletion of faces) & a complex name matching among them.

1.
Face graph structure allowing both naming of all entities (edges and vertices are named in terms of their adjacent faces) & naming matching.
2.
Table recording name of the contingent entities that are referenced together with pointers on the geometry more, some information for the matching algorithm.
3.
Geometry of the designed object.

This method has some limitations like:

1.
They do not explain how the initial faces are named.
2.
Limitation in naming approach.
3.
More memory space required.

Kripac [5], [6] proposed a topological system of API (application programming interface) that introduces a faceIDGraph describing basic naming and name matching mechanism while the table is changed and updated every time once the model is modified. Topological entity matching is based on the compare and contrast between one or more faces in two graphs. But his way of distinguishing between edges/faces with the exactly same basic name is not clear which can leads to unpredictable results. Kripac also didn’t address how to calculate intersCode and basic naming of face was not considered [5], [6].

4.3. ShellGraph based persistent identification

Naming is based on shell graph, invariant and

contingent entities. They propose to identify invariant and contingent entities unambiguously.

Name matching- Nodes of the shell graph are matched from the initial design of shell graph onto the current reevaluation shell graph. Other topological entities are matched by reference to the shell graph.

Shell graph is classified into different sections:

1.
Hierarchical Shells: shells and subshells to be able to apprehend the geometry at various levels of granularity defined for each class if feature.
2.
Connected Shells: each shell is comprised of jointed sub-shells. Represents the history (split, merge or deletion) of the invariant initial structure.
3.
Overlapping Shells: A subshell can be a part of several shells. The overlapping hierarchical structure enables, during construction, the creation of any shell aggregates.
4.
Aggregation Shells: For the designer to be able to reference geometry at various levels of granularity.

Agbodan [7] presented a persistent identification mechanism based on Shell graph [7] which is similar to Kripac’s faceIDGraph except shell and sub shell information. This approach involves hierarchical architecture of the graph which is difficult to implement (Fig. 20 [7]).

They proposed a complete method for identifying and matching topological entities based on their underlying topology which is based on the invariant structure of each class of form features and on its topological evolution. The matching method compares the initial and the reevaluated topological histories which consist of two phases. During the local phase, two measures of topological similarity are computed between any couple of entities in the reevaluated model and in the initial model. And in the global phase the final matching maximizes the topological similarity between the matched entities of both models [7], [26].

They have proposed a method for persistent naming which was associated with a hierarchical architecture involving tracing the historical evolution of invariant entities in each constructive gesture. The suggested method defines a shell graph, which have a hierarchical structure of shells of an historical structure of faces (Fig. 22).

The shells characterization enables on the one hand to represent the different types of shells required in CAD during initial modelling operation, also to identify the important shells matching to the referenced shells during model modification. A shell could be connected or overlapping. The matching method is a global method of topological matching in the sense that it involves two sets of faces in order to find the best possible matching for all faces. Then, it addresses the tracability loss problems.

In another paper, Marchiex have identified five common concepts which result from most of the studies. First, the distinction between invariant and contingent entities. Second, the naming mechanisms used for invariant entities resulting from constructive gestures. Third, the invariant entity names used to name contingent entities. Fourth, the capability to trace the face history either uses a dedicated structure. Fifth, the global software architecture. They also proposed criterion refers to the use of pure topology or of both geometry and topology in the naming phase. The second criterion refers to the locality or globality of the matching method during the reevaluation phase [19].

In another paper, Marchiex have proposed some additional information about the surfaces to improve the global matching between topological entities. This method considered the shape of non-planar faces and it also considered each surface as a collection of hollow(s) and/or hump(s). Practically, a decomposition operation according to the product shape criterion was implemented [26].

4.4. Feature ID based persistent identification

Wu suggest that the name of face is decided by a type of feature creation and location of face in the feature. So Wu defines naming method as types of feature, profile based feature, entity based feature, and feature based feature.

For example extrude, revolve and sweep, profile based feature is a feature made from a profile. Basic form of profile based feature is

ONside = [FeatID, FeatIDp, IDelement, FeatIDPath, IDtrajectory

FeatID means ID of feature; feature type like “Sweep”, “Revolve” can be of this value. FeatIDp is defined as the ID of Profile of the feature, and FeatIDPath is the ID of Path. IDelement and IDtrajectory is the ID of the corresponding element and trajectory. Starting face is -1, end face is -2 as IDelement, and other IDs become 0.

So, the definition of naming format of profile based feature is

ON (F) = [FeatID, 0, -1, 0, 0], if F is the starting face
- = [FeatID, FeatIDp, IDelement, FeatIDp -1, 0, 0], if F is a side face
- = [FeatID, 0, -2, 0, 0], if F is the ending face

For example chamfer, round and shell, entity based feature is the feature created using reference entity in the part for special operations. Basic form of entity based feature is

ON (F) = [FeatID, FeatIDFF1, IDelement, FeatIDFF2, IDelement2]

FeatIDFF1 and FeatIDFF2 means selected adjacent faces F1, F2. If adjacent face is only one, values of FeatIDFF1 and FeatIDFF2 are same. IDelement and IDelement2 are values of corresponding part in F1 and F2.

For example Linear Pattern, Circular Pattern and Mirror, Feature based feature is the feature created using existing feature. Basic form of entity based feature is

ON (F) = [FeatID, FeatIDp, IDelement, FeatIDPath, IDtrajectory, InsNum] (Fig. 21).