Int J Adv Manuf Technol (****) **:*** ***

DOI **.1007/s00170-008-1586-2

ORIGINAL ARTICLE

Development of automatic surface reconstruction technique

in reverse engineering

Yao-Chen Tsai & Chung-Yi Huang & Kuan-Yuan Lin &

Jiing-Yih Lai & Wen-Der Ueng

Received: 25 October 2007 / Accepted: 26 May 2008 / Published online: 16 July 2008

# Springer-Verlag London Limited 2008

Abstract The computer-aided design model reconstruction 1 Introduction

process is generally very complex, as it requires substantial

efforts in planning and editing data points, curves, and The computer-aided design (CAD) model reconstruction

surfaces. A novel method is developed in this study for process in reverse engineering is generally very complex.

automatic surface reconstruction from a huge number of It involves pre-processing of digitized points, curve net

triangular meshes. The proposed method is mainly com- construction, surface fitting, as well as post-blending and

posed of the following five steps: mesh simplification, trimming. Most of the above-mentioned processes are

quadrilateral mesh generation, curve net construction, currently done manually, which requires interactive and

connectivity data preparation, and multiple surfaces fitting iterative procedures for editing and modifying the CAD

with G1 continuity across the boundaries. The first three model. For objects that primarily contain freeform surfaces,

steps build the boundary curves of the surfaces. The fourth such as organs of human bodies and stylish products, it is

step prepares the data needed for surface fitting, which difficult to establish appropriate CAD models using the

includes segmented points, continuity conditions on the current reverse engineering tools because substantial efforts

boundaries, and topological relationship of the data. In the are required to deal with the scanned points, curves, and

final step, all regions of points are fitted into appropriate surfaces step by step. For automatic surface reconstruction,

surfaces, with the accuracy and smoothness of the surfaces complex continuity conditions exist between adjacent

controlled and G1 continuity between the surfaces. A detailed regions of points. If any of the above steps is not performed

discussion for each of the above algorithms is provided. appropriately, the fitted surfaces may easily be distorted.

Successful examples are also presented to demonstrate the The purpose of this study is to develop an integrated

feasibility of the proposed method. procedure for automatic reconstruction of B-spline surfaces

from a huge number of triangular meshes.

Keywords Automatic surface generation . Tensor-based B-splines and non-uniform rational B-

Mesh simplification . Quadrilateral meshes . Curve nets . spline (NURBS) models are widely used in reverse engi-

Constrained surface fitting . G1 continuity neering, as they are currently industrial standards for surface

representation. Thus, a number of researches have been

conducted for surface fitting using B-spline and NURBS

models [1 3]. The quality of the reconstructed surface, such

as the accuracy, smoothness, and boundary continuity, has

Y.-C. Tsai : C.-Y. Huang : K.-Y. Lin : J.-Y. Lai also been addressed extensively. However, they are generally

Department of Mechanical Engineering,

available only for single patch fitting or fitting of multiple

National Central University,

patches whose network is known in advance. Recently,

Taiwan, Republic of China

e-mail: abpxwv@r.postjobfree.com automatic surface reconstruction from triangular meshes has

received increasing attention. Eck and Hoppe [4] developed

W.-D. Ueng

an integrated procedure for the reconstruction of tensor

Department of Mechanical Engineering, Tungnan University,

product B-spline surfaces from a set of scanned points. They

Taiwan, Republic of China

Int J Adv Manuf Technol (2009) 42:152 167 153

first applied a reparametrizing process to acquire a simple quadrangle. A three-step procedure is then implemented to

triangular base complex and then utilized harmonic maps to improve the quality of the quadrangles. Lee et al. [16]

combine triangles into a quadrilateral domain complex. A B- propose a constrained algorithm to force the edges of the

spline surface-fitting algorithm is finally employed to reach quadrangles to pass several pre-defined boundary curves.

G1 continuity between adjacent patches. Regarding the boundary continuity of adjacent surfaces,

Owing to the rectangular structure of the tensor product constrained surface fitting is an essential process to keep

B-spline, the original triangular meshes must be converted the surface accuracy and boundary continuity simultaneous-

into a network of quadrilateral regions so that each of them ly. Milroy et al. [17] introduce a constrained surface fitting

for two sets of points with G1 continuity between the

can be fitted into a B-spline surface. Moreover, constrained

surface fitting must be developed to achieve the desired patches. Chen et al. [18] developed the boundary conditions

continuity across the boundaries. To avoid the above dif- for constrained surface fitting, which ensure the continuity

ficulties, Ying and Hong [5] introduce a triangular B-spline of adjacent surfaces. Lai and Ueng [19] deal with simulta-

neous fitting of multiple sets of data, concentrating on G2

model and propose algorithms for fitting the points into a

network of triangular B-spline surfaces automatically. The continuity across the common boundary. Other studies

triangular B-spline model, however, is not accepted by regarding the continuity of multiple Bezier surfaces include

many modeling systems. Ma and Zhao [6] propose an Du and Schmitt [20], which review several algorithms to

integrated procedure, with Catmull Clark surfaces imple- reach G1 continuity, and Sarraga [21], which discusses the

mented, for simultaneous fitting of smoothly connected stitching of three, four, or five patches.

multiple surfaces from point clouds. The fitted surfaces are

G2 continuous across all surface boundaries except at a

finite number of extraordinary points where G1 continuity 2 Problem statement

is obtained. Nevertheless, it still requires a manual planning

of quadrilateral network. There are essentially four issues for automatic surface

The planning of quadrilateral regions from triangular reconstruction from triangular meshes. First, a pre-processing

meshes involves two steps: mesh (or surface) simplification of triangular meshes is generally necessary. Typical pre-

and quadrilateral mesh generation. Schroeder et al. [7] processing techniques are such as mesh detection [22, 23],

propose a simplification algorithm derived from vertex hole filling [24] and mesh smoothing [25], which are

decimation. The vertices are classified into different types employed to correct the errors, noise, or missing data on

in terms of a distance function evaluated at each vertex. Six triangular meshes. Second, a set of curve net must be

types of vertices are kept, while the others are removed. established by which the data points are segmented and

Cohen et al. [8] propose a simplification algorithm by the surface boundaries are determined. Quadrilateral curve

offsetting a mesh along its surface normal. However, it may net is typically employed because B-spline and NURBS

result in the occurrence of mesh intersection. Additional surface models are generally employed. The curve net

algorithm is developed to overcome such a problem. The must be carefully planned such that the feature boundaries

remaining vertices are then retriangulated. Hoppe [9] and can be maintained. Third, a connectivity data structure must

Garland and Heckbert [10] use edges as the base of the be created to prepare all information needed for surface

simplification and propose different rules for simplifying reconstruction. Fourth, a constrained surface fitting must be

the meshes. Garland and Zhou [11] propose a quadratic established, which can minimize the error but keep the

error metric to determine which edge should be removed continuity of adjacent patches. Since the first issue is typically

and implement the algorithm iteratively until a pre-specified addressed independently, it is not considered in this study.

number of meshes is reached. The reduced model can be Based on the available literature mentioned above, there

employed to represent the envelope or overall appearance are still some problems that have not been addressed

of the original meshes. considerately. First, the available mesh simplification is

Quadrilateral mesh generation is originally developed primary for the use in computer graphics, such as level of

from finite element analysis and is now employed to detail for 3D graphics, where the outline shape rather than

represent 3D model in rendering and computation. Lau the quality of the meshes is more important. For automatic

et al. [12] combine each pair of triangles into a quadrangle surface reconstruction, however, the topology and geometry

using the topological relationship of the triangular meshes, of the simplified meshes may affect the feasibility of the

in which four angles of a quadrangle are employed for later work. The quality of the fitted surfaces may also be

swapping the edges. Kobbelt [13] and Borouchaki and Frey affected by the size and shape of the segmented points.

[14] subdivide each triangle into three quadrangles using a Similar problems exist when converting triangular meshes

subdivision strategy. Maza et al. [15] propose an edge into quadrilateral meshes. Therefore, additional algorithms

removal algorithm to combine a pair of triangles into a must be developed to ensure the quality of the simplified

Int J Adv Manuf Technol (2009) 42:152 167

154

meshes iteratively, while keeping the overall appearance,

meshes as well as the quadrilateral meshes. Second, the

such that the framework of the quadrilateral meshes can be

feature boundaries on the original model should be pre-

built. Each quadrilateral mesh describes the range of a

served, but limited study is available to handle such an issue.

surface to be generated. If too many vertices are left, it

Several studies are available to deal with the recognition of

becomes difficult to handle the continuity problem between

feature regions or feature edges [26, 27]. However, as far as

the patches because many of the meshes are too small. On

automatic surface reconstruction is concerned, the preser-

the contrary, if the remaining vertices are too few, the

vation of feature boundaries is still an active research issue.

reduced meshes may not be accurate enough to describe the

Third, to fit multiple regions of points simultaneously while

framework of the original meshes. The following two

keeping appropriate continuity between adjacent surfaces, it

criteria are proposed for developing the mesh simplification

requires an integrated approach to prepare all information

algorithm: (1) The errors between the original and reduced

needed for surface fitting, including a suitable data structure,

models should be controlled, and (2) the feature boundaries

a set of curve net lying on the meshes, appropriate boundary

of the original model should be maintained.

constraints, and a constrained surface fitting algorithm. All

The proposed mesh simplification algorithm is essential-

these issues are correlated to each other and must be

ly based on edge contraction, as depicted in Fig. 1, where

considered simultaneously. However, they have not received

an edge is reduced to a vertex in each run and it is

a detailed discussion in literature.

performed iteratively for the entire model until a desired

In this study, an integrated procedure for B-spline

goal is reached. To determine which edge should be

surface reconstruction from triangular meshes is developed,

contracted, a quadric error metric proposed by Garland

which can overcome most of the above-mentioned prob-

et al. [10, 11] is applied, which defines an error cost on

lems. It primarily involves the following five steps: mesh

each edge. The quadric error metric can be expressed as

simplification, quadrilateral mesh generation, curve net

[10]:

construction, connectivity data preparation, and constrained

surface fitting. Simplification of meshes yields a set of

X

characteristic triangles describing the outer shape of the v v T p pT v 1

original model. The feature boundaries are preserved as P2plane v

0 1

much as possible during the simplification of the meshes.

X X

v ppT v vT @ K p Av

Owing to the rectangular structure of a B-spline surface, the T

characteristic triangles must be converted into quadrangles. P2plane v P2plane n

There are many ways of converting triangles into quad-

T

rangles, and the results may be different. The main goal

where v vx vy vz 1 represents a point with respect to a

here is to avoid obtaining long and narrow quadrangles, as

vertex vo on the original meshes, (v) represents the error

they may induce continuity problem between adjacent

metric in a quadratic form, p a b c d T represents the

patches. A network of curves is then constructed from the

plane defined by the equation ax by cz d 0, where

framework of the quadrangles. Each side of the quadrilat-

a2 b2 c2 1, and Kp represents the fundamental error

eral meshes may not necessarily be located on the triangular

quadric. There are basically several meshes neighboring vo,

meshes. Thus, a series of procedures is developed to ensure

and each of them can yield a plane p. The geometric

that the curve nets are located precisely on triangular meshes.

meaning of (v) represents the summation of the squared

For automatic surface fitting, a connectivity database must

distance from v to each of the p s. When v = vo, (v)=0.

be established to provide the data needed for surface fitting,

which includes segmented points, continuity conditions on

the boundaries, and topological relationship of the data.

Finally, a constrained surface fitting algorithm is developed

to fit each region of points into a surface, preserving the

accuracy and smoothness of the patch and the boundary

continuity across the patches. Successful examples are

presented to illustrate the detailed process and to demon-

strate the feasibility of the proposed method.

3 Mesh simplification

The purpose of mesh simplification is to generate an

approximation of the original model by reducing the Fig. 1 Concept of edge contraction

Int J Adv Manuf Technol (2009) 42:152 167 155

Here, Kp is related only to the parameters of the plane p and

can be expressed as

22 3

a ab ac ad

6 ab b2 bc bd 7

K p ppT 6 7 2

4 ac bc c2 cd 5

ad bd cd d 2

The error quadrics for all planes neighboring vo can thus

be expressed as the following matrix form

(a)

X (b )

Q v Kp 3

Fig. 2 Mesh inversions: a the original meshes, and b some triangles

P2plane v

intersect each other after the removal of one edge

The overall procedure of the mesh simplification

algorithm is summarized as follows. An error quadric Q

error quadric such that the boundary edge will never be

at each vertex of the original model is first computed. For a

contracted. In addition, when a vertex belongs to a

pair of vertices (v1 v2) corresponding to an edge, a new

boundary vertex, the non-boundary vertex is forced to

error quadric Q is set as Q0 Q1 Q2, where Q1 and Q2

contract to the boundary vertex.

correspond to v1 and v2, respectively. The midpoint vm of v1

3. Checking minimum angles: It is necessary to avoid the

and v2 are also computed. Three errors, (v1), (v2), and

occurrence of a sharp angle in a triangle, as it may

(vm), are then computed, and the one with the minimum

increase the difficulty of multiple surface fitting. Once

error is defined as the error of the edge v1v2. It is carried out

an edge is contracted, all new triangles must be tested.

for all edges, and the one with the minimum error is chosen

When a triangle has an angle smaller than the minimum

for contraction. The above procedure is repeated until the

angle allowed, the corresponding edge is marked and

desired number of meshes or the tolerance allowed is

will be contracted in the next iteration. The sharp

reached. In general, more meshes are reduced near the flat

triangle can thus be removed. After mesh simplifica-

regions, while less meshes are reduced near the round and

tion, all angles are checked again. Whenever an angle is

sharp regions.

too small, a swap process can be implemented to shift

To avoid the occurrence of inappropriate meshes,

the common edge of two neighboring triangles.

additional steps must be taken to improve the quality of

4. Eliminating tiny meshes: It is unavoidable that some

the reduced model. From the viewpoint of surface fitting,

tiny meshes may appear after mesh simplification. Such

tiny regions as well as long and narrow regions should be

tiny meshes should be removed, as it may easily result

avoided as they may lead to inappropriate surfaces or ill

in interaction of the control points. To eliminate tiny

boundary conditions. Moreover, during mesh simplifica-

meshes, the areas of all triangles are computed. When a

tion, some topological problems may occur, such as mesh

triangle has an area smaller than the minimum area

inversion, overlay, and boundary distortion. Therefore, the

allowed, one of its edges with the minimum error

following conditions are checked and corrected:

quadric is contracted.

1. Mesh inversion: Mesh inversion denotes a problem

In surface reconstruction, appropriate planning of the

when the surface normal of adjacent meshes is reverse.

characteristic curves is essential. When planning the curve

This may occur when new triangles intersect each

net, it is important to recognize the feature boundaries and

other, as shown in Fig. 2. To eliminate such a problem,

place some of the curves on them. There are various feature

an angle for each pair of adjacent triangles neighboring

edge detection algorithms in literature [26]. The second-

the target edge is computed. If any of these angles is

order difference (SOD) method [27] is employed in this

larger than the allowed angle, mesh inversion occurs,

study, as it gives a good estimation of the variation of the

and this edge should not be contracted.

surface normal between adjacent meshes. The SOD method

2. Maintaining boundary edges: The boundary edges

defines a weight on each edge. As Fig. 3 depicts, the weight

represent the outer shape of the object and should be

w(e) of the edge e = {i, j} is defined as w(e) = nfa nfb, where

preserved. Garland and Heckbert [10] propose an

nfa and nfb are the surface normal of two adjacent faces fa =

algorithm of creating virtual planes on the boundary

{i,j,k} and fb = {i,l,j}, respectively. A feature edge is

edges to increase their quadratic errors. Garland and

considered as an edge with a weight smaller than a pre-

Zhou [11] add weights on the boundary edges to keep

defined threshold, while a feature boundary is a set of

the boundary shape. In this study, a virtual plane is put

feature edges connected sequentially. The following proce-

on each boundary edge to increase the value of the

Int J Adv Manuf Technol (2009) 42:152 167

Fig. 3 Edge weighted by the SOD method

ek-1

Q

dure describes the process of detecting feature edges and

feature boundaries:

c

1. Feature edge determination: For each edge e in the

simplified meshes, compute its weight w(e). Set a

threshold wt. If w(e)

edge. Otherwise, it is not.

2. Noise removal: The isolated feature edges and feature

cells are considered as noise and should be removed.

An isolated feature edge is a feature edge where its two

end points do not connect to other feature edges. A

feature cell represents three continuative feature edges

Fig. 4 Feature boundary growing. a inappropriate feature edges, b

that locate on the same triangle. Figure 4a depicts an

feature edge growing at free end point, and c result of feature

example of isolated feature edges and feature cells.

boundary growing

3. End-point computation: In general, when a feature edge

is located inside a feature boundary, both of its end

reaches the boundary of the mesh model or when it

points should be connected to other feature edges.

forms a close curve. All feature boundaries can be

When only one end point of a feature edge is connected

obtained by repeating the search continuously until all

to another feature edge while the other end point is free,

feature edges have been checked. Figure 4c depicts one

additional algorithm must be implemented to detect if

result of the feature boundary growing.

it should be considered as the last edge of a feature

boundary. Take Fig. 4b as an example. The point P is a

free end point, namely, it is connected to one feature

edge ek 1 only. All the weights of its neighboring edges,

except ek 1, are computed, and the maximum weight, 4 Generation of quadrilateral meshes

say w(ek), is compared with that of ek 1. If w(ek 1) w

(ek) , where is a small error, ek is considered as a There are generally two approaches to convert triangular

feature edge, and the free end point is shifted from P to meshes into quadrilateral meshes. In one approach, each

Q, as depicted in Fig. 4b. Such a test continues until the triangle is divided into three quadrangles by connecting its

free end point touches the end point of another feature centroid to the midpoints of its three edges. This approach

edge or the mesh boundary. guarantees that all triangles can be converted into quad-

4. Feature boundary growing: It is now possible to find a rangles successfully. However, it may yield excessive

sequence of feature edges to form a feature boundary. number of quadrilateral regions, and some of them may

We can identify one end point of a feature boundary be too small to be used. In the other approach, every two

and perform the search in terms of the topological neighboring triangles are combined into a quadrangle. The

relationship of the edges. The search stops when it resulting quadrilateral regions are larger and can easily be

Int J Adv Manuf Technol (2009) 42:152 167 157

manipulated in surface fitting. The only problem is that not

all triangles can be converted into quadrangles because

some isolated triangles may exist. Therefore, both methods

are applied in this study, where the second method deals

with the combination of most triangles, while the first

method handles the residual triangles.

The procedure of combining every two triangles into a

quadrangle must be carefully designed such that inappro-

Fig. 6 The sharp triangle and one of its neighborhoods combined into

priate quadrangles or isolated triangles are as few as

a quadrangle

possible. Since the feature boundaries should be preserved,

they should be processed first. Each edge in a feature

boundary is adjacent to two triangles. All these triangles are first. When there is an external boundary, all triangles

identified and a search is performed for each of them to find neighboring the boundary edges are selected and serve as

its counterpart. It is noted that when two adjacent triangles the initial circle of triangles, as shown in Fig. 7a. When

share the same feature edge, they should not be combined. there is no external boundary, i.e., it is watertight, the error

metric (v ) evaluated previously in mesh simplification can

Once all such triangles have been processed, the remaining

triangles, namely, the ones which are not adjacent to any be used as the reference of the combination. When a circle of

feature edge, are then processed. triangles is acquired, a pair of adjacent triangles must be

Each triangle is generally adjacent to more than one combined. In general, a triangle has two neighborhoods.

The error metric (v ) is employed to determine which

triangle, and there are many possible combinations for

the entire set of meshes. A basic consideration is that the pair of triangles should be combined. In mesh simplification,

the edge corresponding to a smaller (v ) is merged. Using

maximum and minimum angles of a quadrangle should be

restricted. When the minimum angle of a quadrilateral mesh is such a concept, we combine the triangles with a common

edge of smaller (v ). Such a procedure is implemented for

too sharp, as shown in Fig. 5a, it may not have enough space

to place the control points near the sharp area and hence the entire circle of triangles to convert each pair of triangles

results in distortion of the surface. When the maximum angle into quadrangles. It is noted that some of the triangles may

of a quadrilateral mesh is larger than 180, as shown in not find suitable neighborhoods and will be kept alone.

Fig. 5b, it is also difficult to handle the boundary continuity Figure 7b depicts that each pair of triangles in a circle of

between the surfaces. triangles is converted into a quadrangle. An additional

The proposed conversion algorithm is divided into four topological database is also established.

steps. The first step, a pre-processing step, deals with sharp

triangles. When the smallest angle of a triangle is less than

the minimum angle min, this triangle is regarded as a sharp

triangle and should be processed first. It is combined with

one of its neighboring triangles to form a quadrangle. As

Fig. 6 depicts, the triangle neighboring the longest side of

the sharp triangle is selected and combined with the sharp

triangle. The flags of these two triangles are also changed

such that they will no longer be used.

(b)

(a)

The second step converts most triangles into quadrangles

circle by circle. An initial circle of triangles is obtained

(c) (d )

(b) >180o

(a) 180o proposed curve fitting algorithm is a constrained curve

fitting, where the initial and final points of the data are

Fig. 8 Post-processing of inappropriate quadrangles and isolated

passed exactly. Second, to reach better quality of the curve,

triangles: a boundary triangles converted into quadrangles, and b the

both the accuracy and smoothness of the curve should be

quadrangle with an angle larger than 180 is divided

Int J Adv Manuf Technol (2009) 42:152 167 159

Fig. 9 Comparison of the orig-

inal meshes, reduced meshes,

and quadrilateral meshes for a

shoe last: a the original meshes,

b the reduced meshes, and c the

quadrilateral meshes

(a) (b)

(c)

controlled. The accuracy control can maintain the curve boundary curves. A connectivity data structure is required

located on triangular meshes, and the smoothness control can for automatic generation of the surfaces corresponding to

ensure a smooth boundary of the surface to be generated. A the entire set of triangular meshes. A face table described in

detailed description of the proposed constrained curve fitting [31] is applied as the basic framework of the proposed data

algorithm can be seen in [30]. structure. Each face in the table represents a region of

points. It is surrounded by four edges, representing four

boundary curves. Additional continuity conditions on each

edge is computed and attached to the data structure. Thus,

6 Connectivity data preparation

for each region of points, we can immediately acquire its

The constrained surface fitting of a B-spline surface four boundary curves and the continuity conditions

requires the following information: a set of data points, corresponding to each curve. Specific information required

four boundary curves, and constrained conditions on the in this data structure is described below.

Fig. 10 A planar slicing

Nm

algorithm for finding the inter-

mediate points between two

edge points Q0 and Qm

Qm

N0

V

Q0

Int J Adv Manuf Technol (2009) 42:152 167

160

6.1 Data segmentation

Data segmentation is a process of partitioning the data

points using the curve nets to yield separated regions of

points. The four boundary curves of a region are also

recognized and recorded. The detailed procedure of the data

segmentation algorithm is shown below:

1. Digitize a curve into a sequence of points that are dense

enough to describe its profile. The points are denoted as

Qi, i = 1,, n, where n denotes the total number of points.

2. Start from the first point Qi, i =1.

3. Find the mesh closest to Qi and record its neighboring

meshes. All such meshes are denoted as characteristic

meshes of Qi.

4. Increase i by 1 and repeat step 3 to find the

characteristic meshes of Qi.

5. Check if there are overlapped meshes for the above two

sets of meshes. If yes, go to step 6. If not, there is no

connection between the two sets of characteristic

meshes. The algorithm described in Section 5 is

employed to search for the missing meshes between

them using the topological data structure.

6. Repeat steps 4 and 5 until all points have been tested.

All sets of characteristic meshes are indexed between

i =0~n.

7. Repeat steps 1 to 6 for the other curves to yield a set of

characteristic meshes for each curve. All characteristic E4

E1

meshes are combined to yield multiple isolated regions

F1

of meshes.

E3

8. The vertices in each isolated region are separated into a E2

group of points individually. A region growing algo-

rithm is employed to search for each group of points,

where a seed point is assigned and the topological

relationship of the meshes is applied for growing the

Fig. 11 Data segmentation: a the original meshes and curve nets

region.

given, b characteristic meshes, and c all regions of points separated

9. When all regions of points are separated completely,

the data segmentation process is finished.

points, indicated in different colors. It is noted that the

In the above process, each curve can generate a set of vertices of the characteristic meshes do not belong to any

characteristic meshes. A curve index is marked on each set region. A face table in the data structure records the

of characteristic meshes to indicate the curve that it belongs relationship of a face and its neighboring edges. For

to. During data segmentation, the indices of the character- example, the edges {E1, E2, E3, E4} shown in Fig. 11c

istic meshes on the boundary of each data region can also are adjacent to the face F1 and are recorded in the face

be recorded. Therefore, when a region of meshes is table.

obtained, we can obtain all indices of the characteristic

6.2 G1 continuity conditions on curve nets

meshes corresponding to this region. The indices of the

corresponding boundary curves can also be obtained.

Figure 11 depicts an example showing the input data and The stitching technique is generally applied in CAD

the output result of data segmentation. The original systems to achieve the desired continuity between adjacent

triangular meshes and curve nets are shown in Fig. 11a. surfaces. When two surfaces are represented in B-spline,

Figure 11b shows the distribution of the characteristic the boundary conditions can be represented as the relation-

meshes, which are essentially near the neighborhoods of the ship of several arrays of control points near the common

boundary. If G1 continuity across the boundary is enforced,

curve nets. Figure 11c illustrates the separated regions of

Int J Adv Manuf Technol (2009) 42:152 167 161

two arrays of control points in each surface must be

involved; while for G2 continuity, three arrays of control

points in each surface are involved. For the latter, the

overall smoothness of a surface may be affected due to

additional restriction on the third array of control points.

For fitting multiple surfaces, such a problem becomes even

more serious, as all four sides of a surface must satisfy the

desired continuity conditions. Therefore, G1 continuity is

generally applied when fitting multiple surfaces, as it can

maintain the smoothness of a surface to a certain extent, while

leaving more arrays of control points for the optimization of

the surface.

When fitting multiple surfaces, three kinds of data must

be given, namely, data points, four boundary curves, and

continuity information on each curve. Since there is no

other information except the input points, represented as

triangular meshes, it is necessary to evaluate the desired

continuity conditions on each curve and combine them with

other data for use in fitting multiple surfaces. The geometric

meaning of G1 continuity is that the surface normal of two

adjacent surfaces along the common boundary should be

equal. Such a concept is employed here to derive the

necessary continuity conditions on the triangular model.

The following steps describe the procedures for preparing

the continuity conditions on each boundary curve:

1. Compute the surface normal NCi for all meshes Ci in

the original triangular model.

2. For each vertex Pti, use its neighboring meshes to

evaluate a normal vector NPti at Pti. Assume that the

neighboring meshes are C0 Cm, and their surface

normal are NC0 NCm. Then, the normal vector at Pti

can be represented as

1X m

NPt i NC j 4

m 1 j 0

3. A point on the curve Q(v) can be represented as Q(v0).

Set Q(v0) and r, respectively, as the center and radius of

a circle, and search for a set of points Pti, which are

within this circle. Compute an average normal vector

using the normal vectors of all Pti. Such a normal

vector serves as the normal vector NQ(v0) of Q(v0).

4. Repeat step 3 for all points on a curve. They represent

the surface normal of the points on a boundary curve. Fig. 12 Generation of G1 continuity conditions on the boundary

curves: a evaluation of NPti, b evaluation of NQ(vi), and c the surface

5. Repeat step 4 for all curves. The entire surface normal

field is denoted as NQ(v). normal evaluated at each boundary point

Figure 12 depicts an example showing the evaluation of

within a radius r from the point Pti are used for evaluating

the surface normal on the curve nets. Figure 12a shows the

computation of NPti, where the neighboring triangles the surface normal NQ(vi). Figure 12c shows the distribu-

surrounding Pti are C0 Cm and the surface normal on each tion of the surface normal located on the digitized points of

triangle are NC0 NCm. Figure 12b indicates that the points the curve nets.

Int J Adv Manuf Technol (2009) 42:152 167

162

where S1 and S2 are cubic blend surfaces and T is a bicubic

7 Constrained surface fitting

tensor product surface. The bicubically blended Coons

In conventional surface fitting algorithms [4, 6], each set of surface can better be employed to represent a curved shape.

cloud points is fitted into a surface independently, without This surface is primarily used for better estimation of the

considering the neighboring relationship of the surfaces. A parametric values.

post-editing process must be employed for modifying the The parametric values (ui,vi) for each data point can be

fitted surfaces to reach the desired continuity. The post-editing evaluated in terms of the base surface. Consider that a

vertex on the triangular meshes is Pi and its closest point on

process may easily lead to unnatural distortion of the fitted

0 0

the base surface is P i . Thus, the (ui,vi) of P i represents the

surfaces, especially near the corners of the surfaces. In this

parametric values. In general, we can project Pi onto the

study, a constrained surface fitting algorithm is developed to

0 0

base surface to yield P i . Other methods for evaluating P i

include the boundary constraints owing to the continuity

requirement between adjacent surfaces. The constraint con- are also available [2].

ditions on four boundary sides of a surface are obtained

7.2 Constrained equation for G1 continuity

directly from triangular meshes. The surface fitting algorithm

is formulated as a least-square optimization problem, which

A necessary and sufficient condition for two surfaces R(u,v)

optimizes the smoothness and surface error simultaneously,

and S(u,v) to be G1 continuous is that the surface normal of

while maintaining the desired constrained conditions on four

boundary profiles. the above two surfaces on the common boundary curve is

A B-spline surface S(u, v) can be represented in the coincident; that is, the first differential of two surfaces on

following Cartesian product form: the common boundary curve is coplanar. Assume that the

common boundary curves for R(u,v) and S(u,v) are R(1,v)

XX

m n

and S(0,v), respectively. As Fig. 13 depicts, the continuity

S u; v Ni;k u Nj;l v P i;j 5

i 0 j 0 condition can be expressed as

where Pi,j are the control points; (m +1) and (n +1) are the

a v S 1;0 0; v b v R 1;0 1; v g v S 0;1 0; v 0

num

Contact this candidate