Decomposition of complex models for Rapid Prototyping
T. Lim,
H. Medellin,
J.R. Corney,
J.M. Ritchie,
J.B.C. Davies
Scottish Manufacturing Institute,
School of Engineering and Physical Sciences,
Heriot-Watt University,
Riccarton, Edinburgh, Scotland, EH14 4AS, U.K.
Phone: (44) 0131 4514385, Fax: (44) 0131 451 3129
J.R.Corney@hw.ac.uk
Contents
·
Abstract
·
3. Decompising for manufacture
·
4. Implementation and Examples
Complex components are often decomposed into smaller
elements in order to simplify the overall manufacturing processes. Inspired by
this observation the aim of the research reported here is to automatically
sub-divided models to generate sets of interlocking components that can be
easily manufactured, and assembled, to form the desired shape. Central to the
algorithm is a novel feature recognition technique that both identifies and
separates protrusions bounded by complex surface geometries. The method adopted
for partitioning an object also generates complimentary male/female (i.e.
matching protrusion/depression) assembly features at the interface between
components.
In contrast to previous academic work, that has
described algorithms for the sub-division of mould cavities, this paper
describes a method for separating protrusions from the complex surfaces
frequently found on components manufactured by, say, casting. The objective is to enable production of
large complex components on rapid prototyping machines whose build volume is
less than the size of the desired component.
A novel heuristic, that uses edge curvature continuity
to direct the search, guides the construction of protrusion boundaries. The
resulting subdivision is represented as a cellular model that can be decomposed
into separated manifold solids. After describing the algorithm and presenting
some examples of its application the paper ends by discussing the approaches
limitations.
Keywords: Shape decomposition, Feature recognition, Assembly features, Rapid
prototyping
Although rapid prototyping (RP) machines are extremely flexible compared to traditional manufacturing methods, they also have their limitations such as surface finish, materials and geometry. One of the most obvious constraints on rapid prototyping systems is the size of the models that can be generated. Consequently, large components have to be ‘chopped up’ to enable their creation. Table 1 list some available rapid prototyping systems in the market and their corresponding build volumes.
|
RP system |
Build volume |
|
Z Corporation (Z310 printer) |
200x250x200 mm |
|
Stratasys (Prodigy Plus) |
200x200x300 mm |
|
3D Systems (InVision 3D printer) |
127x178x50 mm |
|
3D Systems (Viper si2) |
250x250x250 mm |
|
EOS Systems (EOSINT M) |
250x250x200 mm |
Table 1: Typical build volumes for
midrange RP systems.
For example, Fig. 1a shows an example of a large distributor nozzle whose “branching” form was designed to be produced by casting. Prototyping such a component as a single part would be very difficult or even impossible on many commercial RP machines because of its dimensions.
(a) (b)
Fig. 1. Large distributor casting (300x400x300mm) (a) The
model. (b) Lattice subdivision of distributor nozzle section.
However, the part can be modelled on small capacity RP systems if it is sub-divided into several geometrically simpler sub-components (see Fig. 6 and Fig. 7), and then assembled to form the desired shape. While strict subdivision (e.g. by a lattice of evenly spaced planes) can be used to decompose the model, it may inadvertently produce variable results. In the worst case the resulting components can contain difficult RP features such as cusps and thin sections (as highlighted in Fig. 1b).
In contrast, this paper proposes a subdivision scheme that uses geometric reasoning to identify a natural decomposition defined by the features on the body.
But defining such a sub-division manually is a difficult task; cast components frequently incorporate complex surface geometry to create smooth transitions between distinct volumes and cavities on the component model. Hence, the boundaries defining the limits of a given sub-division are frequently indistinct. Further more, in practice, some form of assembly features (e.g. machining male/female geometry) is required at the interface between separated components to aid the physical location of one part to another.
This paper describes a method for automatically defining such subdivisions for a range of objects. The algorithm overcomes several problems:
1. Identification of sub-component boundaries,
2. Generating subdivision laminas,
3. Formation of interface assembly feature.
The rest of this paper is structured as follows. Section 2 briefly reviews recent research on automated segmentation for manufacture and feature recognition on complex surfaces. Section 3 describes the details of the algorithm and Section 4 presents the results of the implementation. Section 5 discusses the results and difficulties of the implementation before, finally, some conclusions are drawn.
2. Related Work
The work presented in this paper contributes to two distinct areas of the literature. Firstly the application’s overall approach echo’s other recent work on sub-division (i.e. assembly) based methods for manufacturing. Secondly, the algorithm itself needs to be contrasted against other developments in feature recognition on complex surfaces. Both of these areas is now considered.
Recent literature suggests that there is growing interest in using subdivision to solve a variety of manufacturing problems associated with the production of large or complex components.
Gupta et al [1] describe a system for subdividing large moulds. While Chan and Tan [2] present a system for automatically creating assembly features at the interfaces between subdivided parts. They describe a system that represents the components of a subdivided model as cells inside the original model.
Lim et al [3] describe an ambition system to create an integrated rapid prototyping system enabled by the automated manufacture and assembly of subdivided components.
Although a vast literature exists on feature recognition [4]-[5] for manufacturing it has until recently been almost exclusively focus on components bounded by analytical surfaces (rather than NURBs). The authors speculate that there are two reasons for the absence of a large body of prior work in freeform feature recognition:
1.
Complex modelling operations (e.g. Booleans) commonly used on 2.5D
feature recognition have only recently become able to robustly handle complex
surfaces.
2.
Feature recognition has been considered an ill-defined question on
highly blended parts where types of features sought and the boundaries between
them are often indistinct.
Whatever the reason present
feature recognition techniques still lack the ability to handle solid models
with complex surfaces. Indeed several researchers have cited specific problems
in extending existing Feature Recognition methods to this new domain. For
example Woo [6] points out that feature recognition methods that use
“face-extension” decomposition are only applicable to objects with analytic
surfaces because there is no unique way to extend faces of free-form surfaces.
Similarly Joshi and Dutta [7] state that on spline surfaces: “… a hole boundary may
be defined by a single edge or a sequence of many edges. Consequently it is
almost impossible to define some features based on the topological
relationships between faces as is done in “graph based” and “hint based”
approaches.”
However despite these
difficulties some recent some work has appeared which addresses the problems of
freeform feature recognition.
Lim et al [8], describe an approach that uses the edges of surfaces
to subdivide a component’s faces into a number of laminar that are stitched
together to form manifold solids. Although feature volumes incorporating
complex surfaces can be formed by this approach it requires that they be
bounded by “well behaved” edges.
Joshi and Dutta’s recent
paper address the identification and removal of small features on free form
surface models of sheet metal parts. The representation used in this work models
components as a non-manifold, laminar surface that has zero thickness. The
proposed algorithm exploits the laminar nature of the part by identifying
chains of edges that have no adjacent edges. Having identified hole boundaries
the features are removed by a creating a covering surface. The results are
impressive but use a heuristic that cannot be applied to manifold models.
Realising the difficulties
extending existing graph based methods to feature recognition on complex
surfaces, Lee and Menq [9] proposed a method of characterising features in terms
of their curvature discontinuities along a sequence of edges they termed
‘character line’. This enabled recognition of three basic feature categories -
positive, negative and transition features. Sonthi et al [10] claim that their CR (curvature region) approach
recognises features on non-linear surfaces and is applicable to multiple
domains. They compute a graph of CRs by evaluating surface principal curvatures
and characterise surface regions using six curvature combinations; the user
then defines a library of depression and protrusion features using these. However, it is unclear if either of these
approaches could be extended to complex, multi-sided freeform shapes.
The algorithm present in the
next section makes novel use of a combination of three concepts that appear in
the reviewed literature.
1) Edge
vexity to guide the search: The location of inner-loops of entirely convex, or
concaved edges, on boundary representation model was one of the first feature
recognition methods to be proposed for the identification of protrusions and
depressions [4]. In this work, frequently, no inner-loops
exist and the challenge is to form chains of edges in a robust way.
2) Covering
of edge circuits to create filling surfaces: Joshi and Dutta describe the use
of a covering surface to “fill” small features on complex parts. Although the
same operation is used in this work the resulting bodies are used to internally
partition the volume rather than fill-in depressions.
3) Use of a cellular representation to define the subdivision: The use of cellular data structures to model sub-divisions has been reported by several authors who formed them by subtraction operations. In this work a non-manifold Boolean between the original part and a separation volume is used to both partitions and creates an assembly features in a single operation.
3. Decomposing for manufacture
The aim of the algorithm is to decompose a given solid
model such that protruding features are separated into manifold solids to
simplify the prototyping of a component for a small capacity RP machine. The
approach exploits the observation that the boundary between a protrusion and a
complex surface is usually blended to create a smooth transition between the
surfaces. This geometry gives rise to a contiguous sequence of smoothly connected
(or blend) edges with tangent continuity. Once all smoothly connected edges are
identified, they are formed into circuits and covered to create separating
laminas. There are four principal steps to the decomposition algorithm: -
A.
Given
the 3D solid model a vertex-edge-graph (VEG) of all concave edges is generated.
The VEG is then simplified by the removal of cut-edges.
B.
The
VEG is searched for smoothly connected chains of concave edges. Each chain is a
single un-branched sequence of edges that does not self-intersect. There are
two types of chains: open and closed. A closed chain will have identical start
and end positions. Open chains are
closed by the addition of a linear edge.
C.
Each
chain is covered to make a lamina (i.e. zero thickness) to subdivide the model.
There are circumstances where special cases of chains are located (e.g.
single-edge, open) and these are verified separately prior to covering. The
faces of the resulting lamina are offset to form a volume whose non-regularise
intersection with the model partitions it with additional internal faces.
D.
Once
the model has been decomposed, cellular topology is then attached to the model.
Each subdivided section forms a 3D cell that contains topological entities
enclosed within the model. Each cell is processed to form a manifold solid,
separate from the body.
The use of cellular topology
allows localised operations to be performed on each individual cell. Each cell
can also be augmented with data such as manufacturing details and instructions.
However, its greatest advantage lies in it adjacency graph that defines cell
adjacency and connectivity data for use in automated process planning for
machining and assembly. Each of these steps is now described in detail.
A.
Vertex-Edge-Graph (VEG)
The VEG represents the
connectivity of all edges in the component model. Convexities relate to a
change in shape and so provide clues to direct a decomposition procedure.
Consequently, graph navigation begins by searching for, and marking concave
edges. Fig.
2 shows an example of a shape with several distinct
features that are joined through a series of spline edges. Notice in Fig. 2(b) that the boundary of the features forms a chain of
vertices and edges in the VEG.
(a) (b)
Fig. 2. (a) The
component. (b) Associated VEG.
However, a brute force search
for feature related chains of edges in a raw VEG would be infeasible on all but
the simplest part since there are numerous permutations of potential chains.
Consequently, prior to searching for the chain of edges that bound protruding
features the VEG of concave edges is filtered to remove cut or dangling edges (Fig. 3). The removal of the cut-edges both simplifies the
graph and identifies isolate structures within the model as separate
components.
(a) Identification of
cut-edges (b)
Cut-edges removed
Fig. 3. Filtering
cut-edges.
B.
Identifying separation
circuits
The algorithm processes each
component of the VEG by searching for closed and open cycles of smoothly
connected concave edges. The search algorithm starts by identifying and
grouping edges that are smoothly connected (e.g. vertex adjacent edges having
G1 continuity), Fig.
4.
Fig. 4: G1 continuous edge-loops.
The smooth edge sequences are
constructed by selecting a random concave seed edge as a ‘starting edge’ for a
depth first search that examine the edges, which emanate from the seed. The
algorithm investigates the graph in such a way that each individual arc is
examined only once. Where branching occurs, the algorithm backs up along a path
to the last branch point and sets off through the graph in a new direction.
Chains are discovered when the path being followed is found to be cyclic. When
a path ends abruptly at a vertex with no G1 adjacent edge an ‘open’ attribute
is set to the path.
Fig. 5. Detail
showing the maze of edges associated with the fillets.
The result of the graph search
is a set of smoothly connected chain of edges that can be open or closed (Fig. 5). Adding a connector, i.e. a linear edge that bridges
the gap of the open chain, closes open chains. Only closed chains that do not
self-intersect and form an un-branched loop of edges are kept.
C.
Generating separators
The process of generating
separators for subdividing the model requires converting each chain into a wire
body and then covering it with a surface.
The covering procedure fits a
surface over a boundary defined by a closed connected circuit of edges. There
are two distinct methods of covering. One uses a wire body that has no
associated face or surface information. The second, distinctly different,
operation fills an opening in a sheet body.
For wire bodies (i.e. cycles) that are planar, the covering surface will be a planar surface. Those that are non-planar are first queried for its surround face type. If every edge of the cycle lies on a common face, the underlying surface of that face will be used to cover the wire body. However, in many instances the wire body spans different faces, in this case the wire body is split into either four segments (for closed wires) or two segments (for open wires) and covered.
Several types of separators
can be generated depending on the users preference. Fig. 6(a) shows chains that have been covered with a
single-sided face and converted to a sheet body. Such sheets can be used
directly to slice and separate a component model. Fig. 6(b) shows the laminas thickened to form slicing
volumes for use in an assembly application. Since open chains represent an
abrupt interruption to a smoothly connected chain of edges, they frequently
arise when a protruding feature encounters the edge of a continuous surface.
(a) Single-sided covered
circuits (b)
Volume separators
Fig. 6. Generating
separators from covered circuits.
In these situations, a recess
is required to locate the protruding feature on the surface both visually and
physically. The slicing volume forms this naturally when a non-regularise
Boolean subtraction is performed between the component model and the separating
lamina. This creates a cell whose volume represents an assembly-interface
feature (Fig.
7).
Fig. 7. Assembly
interface feature formed by separator volume
D.
Generation of manifold
representation
Subdividing with the lamina separators decomposes the
component model into sub-regions within the solid representation. This lends
itself naturally to the formation of a cellular structure. Cellular topology
allows the modelling of sub-regions in a solid with the added benefit that
unique information can be associated with each cell. Not all the volumes
generated are appropriate for individual manufacture; some are physical too
small or have complex geometry. Because of this the results are returned within
a user interface (Fig.
9) that allows volumes to be manually inspected and, if
necessary, united with adjacent cells to form lager shapes for manufacture.
4. Implementation and examples
The subdivision system has been implemented using Version 7.0 of the ACIS Kernel modeller [10],[12]. In addition to supporting geometric operations such as assessing edge convexity, covering edge loops with interpolated surfaces and performing non-manifold Booleans, ACIS include routines for extracting and analysing various graphs from the Boundary Representation data-structure. This facility was not only used to create and manipulate the VEG, but also support the removal of convex and cut edges from the network. ACIS’s boundary representation also supported the cellular structure that resulted from the Boolean operations used to create the subdivision.
(a) Nozzle
separator volumes (b)
Exploded view of decomposition results.
Fig. 8.
Decomposition of distributor head.
The most challenging aspect of the implementation was the design of a robust approach for separating the identified protrusions. Because the feature boundaries were formed from copies of edges in the model early attempts to simply partition the model with a laminar sheet frequently failed due to coincident geometry. However the approach in (Fig. 8) of using separator volumes (rather than lamina) has performed robustly on a significant number of component models.
(a) Sheet lamina decomposition
of turbine section, cockpit and nose cone. (b) Close up of
manifold cell bodies
Fig. 9.
Decomposition of space ship model.
Fig. 10.
Highlighted cells (i.e. turbine blades) obtained by the sub-division
process.
In Fig. 9 and Fig.
10 the subdivisions were achieved by directly slicing
with the sheet lamina. Here the laminas were made into double-sided sheet
bodies and a non-regularised Boolean subtraction was performed.
The
component parts of the distributor head section generated by the algorithm (Fig. 8) were produced on Z-Corporations 310 system and
assembled to form the complete model (Fig.
11).
(a)
Distributor component parts
(b)
Detail of assembly features and assembly interface feature (centre and right
images)
(d)
Distributor assembly (top half).
Fig.
11. Plaster print of
distributor components.
5. Discussion
Figures 9 and 10 illustrate the results obtained from subdividing a
model of a toy spaceship and a turbine rotor. In both cases the protrusions
have been successfully identified and disconnected from the model.
In the context of general feature recognition this research is
significant in two respects: firstly its objective is unusual, the
identification and removal of protrusions has received little attention in the
feature recognition literature where the objective is more frequently the
identification of depressions and cavity volumes. However, the second, and,
more important, contribution is the demonstration of a feasible approach to
feature recognition on complex surfaces (rather than, say 2.5D geometry).
While the use of edge vexity is a well-established technique in B-Rep
feature recognition the authors’ believe that the employment of G1 continuity as
a heuristic to direct the search for loops in VEG is a novel and powerful
technique in this domain.
The current implementation’s ability to accurately define the boundary of protrusions is dependent on the presence of edges at appropriate place on the object’s surface. In practice edges frequently occur at changes of curvature because of the way in which objects are constructed (i.e. major volumes are united together before the edges arising from the intersection are blended together). Future work will seek to eliminate this limitation by generating “virtual edges” or contours that reflect specific changes in surface curvature.
In terms of the application it must be emphasised that the subdivision generated may not be optimum for manufacturing. Human judgement is required to assess production issues such as workpiece set-up and stability. Because of this the subdivision results are returned to a user interface for review. Fig. 8 and Fig. 9 shows the results of a subdivision operation with in the systems user interface. The panel on the right displays a tree control that summarizes the properties of each cell in the body.
6. Conclusion
This paper has presented a method of subdividing an object along boundaries defined by circuits of concaved edges. The use of edge vexity and G1 continuity generate boundary geometry that can be used the enable Boolean operations that effectively form the protrusions into separate volumes. Since concave edges frequently give rise to manufacturing difficulties the work is motivated by the desire to divide complex parts into sets of smaller components that can be easily produced and assembled to form the desired shape.
Although
the method has some limitations it demonstrates how concepts originally
developed to support 2.5D feature recognition can be extended, and potentially,
generalised, for used on objects with complex spline geometry.
This
work is supported by the EPSRC grant GR/R35285/01. The authors also gratefully
acknowledge the support of the following industrial partners: BAE Systems, C.A
Models, Pathtrace and Renishaw.
[1] J. Huang, S.K. Gupta, K.
Stoppel, “Generating sacrificial multi-piece molds using accessibility driven
spatial partitioning,” Computer-Aided Design, Vol. 35, 2003, pp. 1147-1160.
[2]
C.K. Chan and S.T. Tan, “Generating assembly features onto split solid
models,” Computer-Aided Design,
Vol. 35, 2003, pp. 1315-1336.
[4]
J.H. Han, M. Pratt, and W.C. Regli, “Manufacturing Feature Recognition from
Solid Models: A Status Report,” IEEE Transactions on Robotics and Automation
2000, Vol. 16, No. 6, pp. 782-796.
[6] Y.H. Woo, “Fast
cell-based decomposition and applications to solid modelling”, Computer Aided
Design, 2003, 35, pp. 969-977.
[8]
T. Lim, J. Corney, and D.E.R. Clark, “Laminae-Based Feature Recognition,”
IEEE Transactions on Pattern Analysis and Machine Intelligence 2001, Vol. 29,
No. 9, pp. 1043-1048.
[9]
N. L. Lee and C. H. Menq, “Automatic Recognition of Geometric Forms From
B-Rep Models, “ Proc. of the 1995 International ASME Computers in Engineering
Conference, September 12-15, 1995, Boston, MA, pp.805-816.
[10]
R. Sonthi, G. Kunjur, and R. Gadh, “Shape feature determination using
Curvature Region Representation,” in Proc. Fourth ACM symposium on Solid
Modeling and Applications, Atlanta, Georgia, United States, 1997, pp. 285 –
296.
[11] T. Lim, J. Corney, J.M.
Ritchie, and B.J. Davies, “RPBloX – Building prototypes the Tetris way”, Technical
Report HWU01, May 2003.
[12]
J. Corney and T. Lim, “3D Modeling with ACIS,” Saxe-Coburg Press 2001.