Context sensitive assistance facilitates the integration of design and manufacturing. Context sensitive assistance in computer aided design systems may be provided by recognizing design intent. In this article, design intent is recognized for mechanical object categories based on a construction tree model. Context sensitive assistance may include completion of a CAD model, retrieving detailed models from approximate models, design for manufacturability and assembly, and providing detailed technical information. Gears are used as the mechanical object category in this paper. The methodology outlined can be extended to include other categories and may also be combined with feature recognizers for improved performance.
Introduction
Computer aided design (CAD) systems are an essential tool for mechanical engineering designs. Current CAD systems model objects through constructive solid geometry and boundary representation (B-Rep) models. Some CAD systems support feature-based modeling and allow the designer to build a model by drawing functional features and assembling them to form the product model. Typical features include protrusions, cuts, slots, etc.
CAD packages provide assistance in feature modeling by setting up simple geometric constraints during the modeling process. These geometric constraints are translated into a set of algebraic equations and solved simultaneously using iterative algorithms. Constraint solvers may be rule-based or graph-based. For example, the “intent manager” in Pro/ENGINEER intelligently adds constraints to an ongoing sketch. When a certain drawn entity lies within the tolerance limit of a constraint, the system automatically snaps to that constraint and thus eliminates the need for a precise sketch.
Some CAD systems and other dedicated computer aided engineering (CAE) systems provide methods to generate NC tool paths, finite element analysis for example. While CAD systems offer different types of assistance to facilitate model generation, and CAE systems offer analysis tools, there has been little work in providing intelligent assistance seamlessly to the user. Intelligent help can be made available by trying to determine the designer’s final intent during the model development phase. Determination of the designer’s intent can be done either by requesting the user for information, or by recognizing the user’s incomplete drawing during the design phase.
In this paper, the design intent is recognized for the category of mechanical gears. The construction tree model is a specific instance of an object represented as a difference of volumes.
The recognition process builds the construction tree of the design being created and identifies if it belongs to the gear category. Context sensitive design assistance may then be provided in the form of retrieving accurate and detailed models from approximate models, and also by offering technical information on the part being designed. Manufacturing and assembly information can also be provided at this stage for improved design and manufacturing. It can thus significantly improve the productivity of the designer. Other downstream applications include searching through a catalog of parts and collaborative commerce between firms through Internet search engines.
The rest of the paper is organized as follows. First a brief background on feature recognition and model-based object recognition is provided. Next, the construction tree model for the gear category is introduced. A set of recognition rules needed to identify if an object belongs to a certain category is discussed next. The recognition system and its implementation in a Pro/ENGINEER environment are then discussed. Finally, case studies are presented, and the extension of the method to other categories is discussed.
Background
Feature recognition is an active area of research in CAD. The objective of recognizing a feature ranges from design for assembly and disassembly, design for manufacture, and design for serviceability, etc. Model-based object recognition is an important area of research in robotics. The aim is to identify objects in a scene from a database or library of objects. Recent research has also focused on functional part recognition as opposed to model-based object recognition. Research in the areas of feature recognition, model-based object recognition, and functional object recognition are briefly reviewed in the next few paragraphs.
The Alternating Sum of Volumes (ASV) algorithm developed by Woo and Tang [10] converts a B-Rep representation of a model to a CSG representation, simultaneously extracting features with convex decomposition. The object is represented as a series of convex components with alternating signs, with the negative signs indicating material removal. The ASV algorithm can have convergence problems, however. De Floriani [4] proposed an edge-face graph representation of a B-Rep model, which is then decomposed to smaller components denoting the features in the model. Joshi and Chang [8] proposed the concept of an Attribute Adjacency Graph (AAG) for feature extraction from a B-Rep of a solid. Henderson and Chuang [7] suggested a vertex-edge graph-based approach, with the vertices of the solid forming the nodes in the graph and the edges connecting the vertices constituting the arcs. Ahluwalia et al [1] developed the dynamic feature generation method, where feature extraction is carried out after the addition of each feature during the design phase of the model.
Feature-based design systems, where feature recognition is simpler in general, have several advantages over other traditional techniques for facilitating design [6]. Particularly, integration of CAD/CAM for Computer Aided Process Planning (CAPP) is facilitated.
Model-based object recognition involves matching an input image with a set of predefined models. The methods are based on 2D image representations, 2.5D surface representation, or 3D object representations [3]. The recognition process involves feature extraction, modeling, and matching. In the 2D-image representation method, each 3D part is modeled by a set of one or more distinct views, most often selected as stable equilibrium positions. Local features such as a line segment or a corner, and global features such as perimeter, centroid, and moment of inertia are extracted from the image and are then used for matching with the model. In the 2.5D surface representation method, range data is segmented into different surfaces. Surface properties such as surface type, centroid and perimeter, orientation, and relationship between adjacent surfaces are used for matching. In the 3D-object representation method, range data is used to create a 3D model of the object. Surface patch graph models, hierarchical generalized cylinders, and multi-view feature vectors may then be used for model matching.
The shortcoming of the model-based approach is that it is difficult to supply an accurate description of the object, which is general enough to cover all the possible variations in shape. More recent developments in object recognition have concentrated on function-based reasoning, where an object is defined by the simple entities that are needed for the object to satisfy its function. Function-based models do not use specific geometric patterns to identify models, but rely on more abstract details such as the fundamental units needed for the object to perform its function. As an example, Di Manzo et al [5] used functional-based reasoning for computer vision systems and recognized objects in the “chair” category. More recently, Stark and Bowyer [9] have developed GRUFF (Generic Recognition Using Form and Function), to recognize the category “furniture.”
In summary, the literature indicates that in CAD, research has focused on feature recognition, and in robotics, research has focused on object recognition. We have not noted any work on object recognition in CAD systems as such [2]. The research in this paper thus follows a new direction in this regard.
Model Construction Tree
For a part to belong to a particular category, it must satisfy certain geometric, functional, and physical characteristics that define the category. These characteristics can be mapped onto the features that must be present in a part for it to be called a member of the category. Besides the presence of features, the relationships between these features are necessary.
The parent-child relationship among the features denotes the dependency of a child feature on its parents. The parent-child relations can be graphically displayed as a construction tree where each node–except for the root node–can have more than one parent. A construction tree in essence indicates which features must precede other features for the model to be generated. The levels in the tree thus represent levels in the design phase of the product model.
The nodes in the construction tree represent the features that make up the object, and the edges represent the relations between these features. A node has attributes for the shape and size, and relative position and orientation of that feature. The features in the construction tree of a category form the minimal set of features that must be present in a model for it to be classified as a member of the category. The construction tree for different types of gears is developed below.
External Spur Gear
The external spur gear is of cylindrical shape with teeth on its periphery and a slot for the shaft. The construction tree (Figure 1) of the external spur gear is comprised of a cylindrical protrusion at the root node followed by a through hole and a number of cuts at the nodes in the second level. Figure 2 shows the steps needed to construct a simple external spur gear model.
Internal Spur Gear
The internal spur gear can be generalized as having a protrusion with no specific shape requirements and a through hole where the gear teeth are located. Figure 3 depicts the construction tree and Figure 4 indicates the model development.
Rack Gear
Rack gears are linear spur gears having cogs set in a straight line, which meshes with a pinion. The cogs are cuts on one of the surfaces of a rectangular prism, which makes up the root node in the construction tree of a rack gear model. The nodes in the second level of the tree represent the cuts (Figure 5). Figure 6 describes the mode development.
Straight Bevel Gear
Straight bevel gears are useful for changing the direction of the rotation of a shaft. They are akin to the external spur gear, but with a conical shape. The parent-child relationships for a simple straight bevel gear are illustrated in Figure 7 and Figure 8 shows model images of the corresponding steps. The model construction tree forms the basis for recognizing complete and in-process objects. Context sensitive design assistance may thus be offered by interpreting the construction tree. The levels in the tree are an indicator for the “completeness” of the model. The recognition process is feature-based in the sense that it tries to determine the level of completeness after the addition of each feature.
It should be noted that the construction tree approach is well suited for categories in which the object is modeled conveniently as a sequence of subtracted volumes. If the object were not modeled in this way, then feature recognition algorithms mentioned in the background section would have to be invoked to obtain an instance of the construction tree. In this paper we do not address this aspect and assume the construction tree is naturally obtained.
Other Examples
The construction tree approach can be generalized to include other object categories as well. For example, for the category of hand-held tools, a screwdriver and a spanner may be considered. The construction tree for the screwdriver is shown in Figure 9, and for the spanner in Figure 9. The model development is shown in Figure 10 and Figure 11. A systematic recognition strategy for the category of hand tools can be developed in a similar way to the gear category.
Recognition Rules
To classify an input model as a member of a particular category, information about the shape and relationships among the features that explicitly define the category are needed. These requirements can be perceived as hints or rules that must be reasonably satisfied for the grouping of the input CAD model. Four broad groups are developed for this purpose, namely: 1) Shape Rules; 2) Dimension Rules; 3) Similarity Rules, and; 4) Placement and Orientation Rules.
Shape Rules
Shape rules are used to check the geometry of the feature by determining if the surfaces that make up the feature are of the right profile and in the proper position. Parameters that need to be verified include the number of feature surfaces, the type of surfaces present, the number of edges between surfaces, edge types, the angle between the surfaces, and the relative dimensions of the surfaces.
For instance, the protrusion at the root node of an external spur gear construction tree should be a cylinder. For the straight bevel gear construction tree, the root node should contain a conical protrusion comprising of three surfaces; two conical and one planar. The axes of the conical surfaces should coincide and should be perpendicular to the planar surface.
Cuts are needed following the initial protrusion in the construction trees to make gears. These cuts, referred to as gear cuts, can be generalized for simplicity as a feature having three quadrilateral surfaces placed end to end. The side surfaces must be exactly similar and at equal angles with the middle surface. The hole feature, which is present in the construction trees of certain gears, is understood as one having two cylindrical surfaces. The surfaces must be similar, i.e. they must have equal radii and should have coincident axes.
The shape rules help in quickly eliminating objects that do not belong to a certain category. Shape rules are represented as functions, with the feature consisting of the input parameter and the return data types as either Boolean or a real number between 0 and 100. For example, in the system developed, the angle between the side surfaces and the middle surface of the gear cut feature should lie between 90ƒ and 135ƒ, with the optimum being 112.5ƒ. The function corresponding to this rule would return a zero in case the angle lies outside the above range and would return 100 if the angle is exactly 112.5ƒ. The return value linearly decreases from 100 to zero as the deviation of the angle increases from the optimum.
Dimension Rules
Dimension rules are applied following the shape rules. They check for the relative dimensions of the features to ensure that they would be able to perform their respective functions. The optimum relative dimensions of the features may lie within a range of values. For example, the depth of the gear cuts in an external spur gear model should not be too large for the gear to appear like a fan, nor should it be too small for it to be insignificant. The dimension rules do not act as a screening layer, but affect the systems’ confidence in classifying a part to a specific category.
Similarity Rules
Similarity rules are used prior to or along with the placement rules. Features are similar if they are alike geometrically and are placed in similar positions with respect to the main protrusion. For example, while constructing a model of the gear category, all gear cuts must have the same dimensions for the gear to mesh properly with its mate. Accordingly, similar gear cuts are grouped and inspected to see if they form a circle, and also if they are located at exactly the same distance from each other.
Placement and Orientation Rules
After screening of features of suitable shape and sizes, the position of the features in the part needs to be ascertained in order to understand the geometry of the part. The placement and orientation rules check for the position of the feature in the part. These rules are computationally expensive and should be modeled with proper data structures for efficiency.
In the case of the external spur gear, the gear cuts must be placed on the cylindrical surfaces of the protrusion, while for an internal spur gear they must lie on the cylindrical surfaces of a hole in the protrusion. For the straight bevel gear the gear cuts should be located on the conical surfaces of the protrusion, and they can be placed on any of the protrusion planes of a rack gear.
While the aforesaid rules check for position of a feature relative to the main protrusion of the gear, other placement rules check for position of a feature with respect to other features in the model. This ensures that the gear cuts are placed within a specific distance from each other. Thus for the spur and bevel gears, the gear cuts must form a circle, and for the rack gear they must be in a straight line. Analogous to the placement rules, the orientation rules ensure that a feature is oriented in the right direction with respect to other features in the part. For example, the axis of the hole should be parallel to the axis of the protrusion cylinder in an external spur gear model.
Recognition System
A prototype system is developed that recognizes complete as well incomplete CAD models of the category “Gear” with four sub-categories; the “External Spur Gear,” the “Internal Spur Gear,” the “Straight Bevel Gear,” and the “Rack Gear.” The system generates a recognition parameter termed as the “confidence level,” which indicates the degree to which the system considers the input model to be a member of the sub-category.
Input Files
The current system requires model information as features and subtractive material volumes from stock with data clearly portraying the parent-child relationships among features. The “inf” and “neutral” files in Pro/ENGINEER, have the required feature information. The “inf” file format stores information concerning the parent-child relationships among features. It references features by a unique ID assigned to them during model generation and for each feature and displays the IDs of its parents and its children. The assumption is made that the user develops the input model using subtractive material volumes.
Recognition Methodology
A tree data structure is used to describe the construction tree of a category in which each node, excluding the root node, can have any number of parents and children, thereby similar to a directed acyclic graph. Along with this tree data structure are functions that correspond to the specific rules that must be sufficiently satisfied to classify the input model. An object-oriented design is developed in C++. The categories are represented as classes, and the rules are member functions of these classes. A base class called “Gear” corresponds to the gear category, and derived classes ExternalSpurGear, InternalSpurGear, StraightBevelGear and RackGear correspond to the four sub-categories.
Recognition Process
The recognition process starts with the parsing of the input files. The relevant data in the input files is used to initialize objects of different classes such as the “feature” class, the “surface” class, and the “edge” class. These objects are used to create a construction tree representation of the input model. The construction tree is then compared to that of a gear sub-category to obtain a confidence level.
The protrusion in the input model is first checked for shape rules. If the protrusion successfully passes the shape rules of the gear sub-category, the confidence level is suitably raised and the input model is said to have completely passed the first level as a member of that particular category. If the input protrusion is not passed, the system invokes a pattern recognizer to recognize the input model. The pattern recognizer is invoked whenever an intermediate level fails during the recognition process. For example, the pattern recognizer in the external spur gear category searches for a group of gear cuts with the same shape, size, and orientation, placed within reasonable distances from each other and forming a circle.
If the first level is completed successfully, the system begins a search for features that make up the next level in the particular category’s construction tree. For instance, the module for the external spur gear category would search the input model’s construction tree for gear cuts and a hole that are of the right shape, size, and orientation, and placed in the correct position relative to the main protrusion. The confidence level is increased if rules are successfully passed. Besides testing for the presence of appropriate features, the system ensures that there are no features interfering with the surfaces needed for the part to perform its functions. In the gear category, the gear teeth surfaces are the surfaces needed for the gear to mesh with its mate, and hence carry out its function. The presence of any features on these surfaces brings about a reduction in the final confidence level of the input model.
In all the gear sub-categories described in this system, the gear cuts have to be similar in shape, size, and in the position where they are located in the part. As a result, the gear cuts found in the construction tree of the input model are first grouped by the similarity rules and then checked against the placement rules. The presence of a single group of gear cuts with a sufficient number of gear cuts that pass all the placement rules increases the confidence level of the input model. If all the rules are satisfactorily passed, the input model is said to be complete in the last level of the category’s construction tree.
The entire recognition process can be viewed as a traversal along a graph to find the path with the largest confidence level. The traversal strategy is thus a depth first search where the recognition process stops when it finds a path with a 100-percent confidence level, or when all the paths have been exhausted.
Test Cases
The recognition system is tested with test cases. A confidence level as described in the earlier section is used for object classification. The system also displays a “level of completeness” pointing to the levels and features which are completed or missing from the construction tree of the input model when compared to the construction tree of the category. For example, a bevel gear with only a protrusion is level 1 complete. When a cut is made to create a frustum, it is level 2 complete.
When a hole and cuts for the gear teeth are made, it is level 3 complete. The confidence level calculation is explained with reference to Figure 12(h). The protrusion contributes to a confidence level of 20 percent. When the cut is detected (frustum), the confidence level is increased to 35 percent. Level 3 features are checked next. First, the slot for the shaft is detected, and the confidence level is increased to 45 percent. The gear cuts are detected next using shape, and the confidence level is increased to 53 percent. The gear cuts are checked for being similar in shape, size, orientation, and location, and this increases the confidence level to 94 percent. Finally the gear cuts are checked for circularity, and this increases the confidence level to 98 percent.
The model in Figure 12(a) is level 1 complete, in Figure 12(b) is level 2 complete, in Figure 12(c) is level 3 partially complete, and in Figure 12(d) level 3 partially complete, with higher confidence. Other models in Figure 12 are also tested for bevel gears. In Figure 12(e) the shaft hole is missing. In Figure 12(f) the shaft hole is too big. In Figure 12(g) the teeth are too narrow and long.
Models in Figure 13 are tested for an external spur gear. In Figure 13(a) the hole for the shaft is missing. In Figure 13(b) the teeth are too narrow and long. In Figure 13(c) the teeth are too shallow. In Figure 13(d) the teeth are on a square. In Figure 13(e) the teeth have wrong angles. In Figure 13(f) the hole is too big. Both Figure 13(g) and Figure 13(h) are almost perfect external spur gears. The confidence levels are indicated alongside the figures.
Based on the recognition of design intent, context sensitive assistance may be provided. Incomplete drawings may be completed, and detailed CAD models may be retrieved from a database. Tagged rules and information about a particular sub-category may be retrieved. For example, if a spur gear is being designed, some information on the design, functioning, and manufacture of spur gears may be retrieved as:
• Features: Parallel shafting, high speeds and loads, highest efficiency Application: All types of gear trains and wide variety of velocity ratios
• Precision: Simplest tooth element offering maximum precision. First choice for moderate speeds
• Gear ratio: Equal ratio of teeth in the respective gears.
• Line of action: Common tangent to the base circles, and passes through the pitch point of any pair of mating gears.
 The manufacturing process involves hobbing, shaping, gear grinding, heat treating, burnishing, and deburring. |
Conclusion
In this paper we have developed a system to recognize complete and incomplete CAD models for the gear category. The method is based on the concept of modeling an object by a construction tree. The input file is parsed and processed to determine if it matches the parent-child relationships as determined in the construction tree. Shape rules, dimension rules, similarity rules, and placement and orientation rules are used to attribute a confidence level to the object being recognized.
The construction tree approach may be generalized to other categories. In the general case, feature recognition algorithms may be incorporated to convert models into the construction tree form. The ability to recognize complete and incomplete CAD models in a particular category offers the possibility of making CAD systems intelligent. Context sensitive assistance in the form of completing an in-process CAD model, retrieving a more sophisticated model, or even obtaining technical information to permit design for manufacture or assembly is possible. CAD databases may further be queried to identify category matches.
Future work will focus on expanding the categories for recognition. Advances in feature recognition based on wavelet encoding and binary space partitioning will be investigated.
References
- Ahluwalia R.S. and Miller J.E., (1994), “Dynamic Feature Generation During Design,” Journal of Design and Manufacturing, vol. 19, 115-126.
- Narayanaswami R. and Ajmera A. (2002), “Context Sensitive Assistance in CAD Systems,” Transactions of the North American Manufacturing Research Institute, Vol. 30, pp. 689-696.
- Chin R.T. and Dyer C.R., (1986), “Model-Based Recognition in Robot Vision,” ACM Computing Surveys, vol. 18, 67-108, 1986.
- De Floriani L., (1989), “Feature Extraction from Boundary Models of 3-Dimensional Objects,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 8, pp. 299-314.
- Di Manzo M., Truco E., Giunchiglia F. and Ricci F., (1989), “FUR: Understanding Functional Reasoning,” International Journal of Intelligent Systems, vol. 4, pp. 431-457.
- Dixon J.R., (1988), “Designing with Features: Building Manufacturing Knowledge into more Intelligent CAD Systems,” Proceedings of ASME Manufacturing International, vol. 1.
- Henderson M.R. and Chuang S.H., (1990), “Three Dimensional Shape Pattern Recognition using Vertex-Edge Graphs,” Computers in Industry, vol. 22, no. 6, pp. 121-126.
- Joshi S. and Chang T.C., (1988), “Graph Based Heuristics for Recognition of Machined Features from a 3D Solid Model,” Computer Aided Design, vol. 20, pp. 58-66.
- Stark L. and Bowyer K.W., Function-Based Generic Recognition for Multiple Object Categories, CVGIP: Image Understanding, vol. 59, no. 1, 1-21, January 1994.
- Woo T. and Tang K., (1991), “Algorithmic Aspects of Alternating Sum of Volumes: Data Structure and Difference Operation,” Computer Aided Design, vol. 23, no. 5, pp. 357-366.
