Reverse Engineering - Post-Process Step
By John M. Switlik, Boeing Define, Bill Macy, Boeing Phantom Works

This article continues the look at Reverse Engineering (RE) as a necessary component of modern computational processes. As discussed earlier, RE is necessary for CAD/CAM/CAE (CoT) and Knowledge Based Engineering (KBE) as described by the following (see bottom of article for definitions).

For CoT, RE is central for several reasons. For instance, one must answer questions about an as-built entity in terms of the as-designed specification. This is a focus for quality. Also, there are many times when the results of numeric computation are in a format similar to that provided by the RE acquisition step. In this case, transformations to a CAD-quality solid can leverage RE methods to obtain repeatable results.

For KBE, RE-type functionality must provide a basis for knowledge completion via empirical feedback. This would involve a general mechanism that could verify computational states in terms of the associated real world phenomena. Such functionality will either be a superset of RE or RE will morph to cover the broader context. This type of RE use is not unlike the sensing required for autonomous behavior in an environment.

In total, RE deals with data that originate from physical entities and creates useful models from this data. Like all forms of modeling, RE faces trades related to representation (structure, parameter), methods (in-house/COTS, procedures, algorithms/heuristics, physics), and quality (measurement, fit, continuity, footprint, completeness). RE, as well, deals with data that arises from computational entities, such as a mathematical modeler providing an optimal result via points or a mesh.

Earlier, an article defined the two major steps for geometry-oriented RE as acquisition and modeling. This article changes 'modeling' to the more specific 'post-process.' Acquisition, the subject of the prior article, involves obtaining data from physical objects. Or, if the source is another computer model, acquisition deals with obtaining data from the related objects. This article looks at the post-process step in terms of 'geometry' modeling. There is a potential for RE to be an enabler of more powerful KBE which will be the subject of a future article. For geometry, values at the points may be of scalar or vector type. The more involved types of RE will support functional and objects types of attachments as well.

Background
RE post-process approaches vary over a wide range with each having its related software. This basis is continually expanding and improving due to progress in research and development, and the related software packages are getting to be more capable.

In post-process approaches, the use of the software requires specialized knowledge and highly trained operators. Many of the operations are powerful, however many types of activity are a collection of a large amount of tedious steps. The Methods section describes a range of activity that may be necessary to meet Quality requirements. Movement along this axis can be a daunting task even for a small problem. The issues are worse when the amount of entities in the view provided by RE acquisition is very large.

One goal is to have more automated capability in areas that require highly-specific knowledge. To accomplish this, there needs to be progress in understanding the trades, how to measure alternatives, and how to decide comparability issues.

The end result of RE post-processing would be data that are in a useable form within the required tolerance. One of the main concerns of RE Quality will be 'use' and what is 'good enough' to meet the use. Other concerns relate to choices that abound during the RE process that need to be better understood.

Representation
The results of the RE acquisition step can be in various forms. Some are richer in content than others; some are immediately usable depending upon the goal; others may take a bit of processing in order to meet a requirement.

For instance, strict visualization may necessitate a different set of requirements than does design in context. The former can be more lax about measurement than the latter. Both examples can easily use the data as it is represented by the acquisition step with little post-processing.

But, at the far end of a spectrum of use is CAD-quality solid modeling with its requirements for continuous splines. Attaining such a representation may require expenditure of time and expertise.

This type of expertise may be suitable for automation, as we'll see in methods. However, the quality issues will involve trades that are currently more amenable to human judgment than they are to strict numeric resolution.

One main outcome of acquisition may be a mesh overlaid on the acquired points. Or, the creation of the mesh may be left to post-process.

In a mesh, points are related to their nearest neighbors. In this representation, points are vertices of a polygonal figure. Points are connected with edges. One popular approach is to use triangles. Other options exist, such as the quadrilateral. Generally, the connecting edges are minimal in length. That is, for a particular point, the edges would join to points that are closest according to a measure. The measure does not have to be 3D distance. For instance, in the triangular representation, rules that control how angles within the triangles are formed can conflict with the minimal edge rule.

For the more rich representations from RE Acquisition, both the points and the links can contain information. Points or links may record properties. Color is a good example.

Depending upon the density of the acquisition settings, a mesh may be a fairly large data structure. In many cases, there is a requirement for decimation. For instance, a plane only needs a scattering of points. This may be true for any type of constant curvature geometry, such as the cylinder, that exists in the mesh.

In general, points are only needed if they contribute unique information. However, there are times when a process might look for multiple occurrences of data in order to establish some weighting scheme. These types of decisions will differ by the application. Geometry has a different set of requirements than does the higher-order characteristics, such as physical properties. A simple example is color. Points that denote changes in color are necessary even if they share the same planes.

Depending upon the representation used for the mesh, a parametric mapping will allow definition of a polygonal surface. This type of entity allows for fairly rich graphical representation in terms of shading and of illustrations of properties, such as smoothness. Other types of representation would be curves that provide a 1-parameter estimation of the 2-parameter surface. How these curves and surfaces relate to the mesh and original points will be a quality issue and a difficult area requiring expert opinion. Additional concerns for representation deal with the well-documented NURBS and solids that are so essential to CoT.

Another area of concern for representation would be data transfer in any of the states. A top-notch RE package will allow many types of transfer formats, each having their own peculiarities. The next paper in the series will discuss this aspect of RE more fully.

In acquisition across multiple views, it may fall on the RE post-process step to join the data resulting in additional data handle requirements. As discussed in the earlier paper, such data merging activity can be better handling in the acquisition step.

Methods
RE Post-process Representation/Methods move from "good enough" to the "CAD-quality solid" along a Quality axis. This type of movement can be associated with incremental steps. On one hand, "Good enough" may require only a little additional processing past acquisition, thereby being highly cost effective. On the other hand, successful completion of all the post-process steps to CAD-quality can take a significant amount of time and effort. As well, it may take specialized expertise that come via experience and not training.

Hence, going beyond "good enough" can, in general, be costly, taking a lot of talent and computational time/power in order to accomplish steps that look trivial. A lot of research is being directed to reducing the cost of moving beyond "good enough" by standardizing the process and by increasing the amount of automation.

There are many ways to define the RE post-process steps. For this paper, we will use the following. For each, there is a brief description of the approach and issues. The next article about the future and the 'wish list' will cover these in more detail.

Points to polygonal mesh - the step of relating points may have been accomplished during the Acquisition step. No matter where done, the basic algorithm looks at a point and tries to find its neighbors. Generally, these will be points that are one link away. Relating points on a plane is easier than doing this in a non-planar area. Yet, on the plane, conflicting constraints of area and angle can cause wide differences in how the mesh appears visually. In 3D, problematic points, such as a point on a fillet within a hole, may have neighbors that are near by distance but not related in actuality. The software needs to know the difference. The experience of the user can be a big factor in accomplishing a useful mesh.

Polygonal mesh to polygonal surface - given a mesh, additional processing can allow generation of surface displays that are useful for visualization and some types of analysis. In many cases, this can be handled by a display option selected by the user.

Point decimation - the results from the acquisition step may be fairly dense such that the file size is heavy and the computational time grows. One option would be to filter out excess points. The motivation would be to reduce the clutter in the model, however transforming to richer representations will influence downstream processes. Common approaches utilize curvature information, with the chord-height driven scheme being an example. Others may be more brute force, such as simply applying a spherical limit between points. Additional motivation for decimation may be a requirement related to feature extraction. Recognizing geometric features can reduce the model size. There are entities, such as a plane, that do not require a dense point set. An entity such as a tube could be turned into surface, thereby resulting in fewer points. But, more meaningful recognition of features would result in a smarter model. There are active areas of research looking to better support this important step.

Curve network - a mesh generally has all points linked to show how they relate. As we saw, this mesh can also provide a rudimentary surfacing capability. Depending upon the acquired data, there may be points that actually represent an edge of a real entity and be of importance to feature extraction. As well, within vertex sets there may be collections that appear to be on a curve. If the requirement is CAD-quality, a feature such as an edge would have to be exact when extracted. In addition, transitions from the polygonal surface to the CAD-quality surface can use a network of curves, given that they have the correct properties. Other transitions to CAD-quality may use both the curves and the points. The fit that these curves and surfaces have to the mesh is an issue of Trades to be resolved by Quality. There are various strategies for accomplishing these curves.

CAD-quality curves/surfaces - given a network of curves and the points, surfaces can be built by several methods as mentioned in Curve network. By whatever means the surfaces are obtained, this step will need to produce good edges between surfaces that are neighbors. Depending upon the Quality requirement of the solid modeler, this one step can become a major focus both in time and effort.

CAD-quality Solid - depending upon the geometry, this representation can have the smallest footprint. It is the richest in terms of supporting logical and numeric operations. Success at this step will be dependent upon success at all the preceding steps, thereby arises the necessity of the expert driver who can follow the causal chain from RE acquisition to the CAD-quality solid.

At each of these steps, there are various stages of automation in the software packages. Yet, the current practice involves a lot of tedious work. This type of repeatable activity will be alleviated (it is hoped) through more intelligent computational assistance. It is unclear how that intelligence will unfold given that there is no underlying theory that drives this practice. The tedium is related to the necessity for iterations that is common to numeric approaches. These can ripple within an area as decisions are made that relate to the important trades. The current state of computational modeling does allow more options for saving intermediate work and recovering states. Given the current state of the art, a process focus to encourage repeatability and quantifiable decisions is imperative.

Quality
Quality applies to both the representation and methods. As mentioned earlier, the "use" requirement will be a critical factor and ranges from "Good enough" to "CAD-quality" with several positions along the way. Quality can be measurable and help guide the process. But, it is a matter of trades that result from the fact that the decision spaces related to reverse engineering do not easily lend themselves to optimization.

In the research, one sees emphasis on adaptive means. It may be that "learning" to co-exist with a human expert may be a requirement for reverse engineering. As well, there needs to be agreement on common approaches. For example, continuity measures, such as Gaussian curvature, can be applied all along the Quality axis, albeit the meaning may be stronger toward the "CAD-quality" end of the spectrum than it is for the polygonal-surface representation. Yet, it is through consistent use and evaluation of these types of measures that the quasi-empirical experience will eventually derive the appropriate 'theoretic' views that can drive the practice and the evolution of the software.

Of note may be research that looks at resolving these RE problems using mesh-less approaches. Perhaps, some combination of the mesh and mesh-less will be the winning approach.

Conclusion
The article looks at the second step of RE which is post-processing. The step unfolds along a Quality axis and applies many approaches to several types of goals. Currently, issues related to this step require human expertise that knows about many types of representation and methods and that can handle major Quality trades. There is a research focus looking to provide more automated handling of some types of knowledge. A bottleneck results from practice being the basis of the approaches, rather than a robust understanding of the requirements and the associated 'theoretic' issues. The next article will discuss the RE future in terms of processes and capabilities that will relate to the modeling and to the trades of acquisition and post-process.

For further discussion of the content of this article, please e-mail the authors.

About the authors
John M. Switlik is an Associate Technical Fellow (Boeing, Commercial Airplane, Wichita Define Systems, KBS, john.m.switlik@boeing.com). His interests are varied: computational support for applied science, mathematics, and management; lifecycle/veracity control for system, application, and domain engineering; integration, use, and quality of computational knowledge.

Bill Macy is a Senior Project Engineer (Boeing, Phantom Works, St. Louis, william.d.macy@boeing.com). His interests focus on the need to leverage reverse engineering metrology and software to provide affordable and better quality engineering, fabrication, and support of products.

Definitions:
CoT - CAD/CAM/CAE/etc. plus "Top Gun" talents (see Discussion).
KBE - Knowledge Based Engineering
RE - Reverse Engineering covers all activities related to capturing geometry data about a physical part and to creating a computer model that can be used by CoT. In this sense, RE serves as a prototype for a fuller link between computational models and associated physical states. Additionally, RE can be applied to outputs from numeric processes that are represented by points, meshes, or polygonal surfaces in order to transform to a NURBS or solids representation.