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

DOI **.1007/s00170-005-0060-7

ORIGINA L ARTI CLE

H. Woo . T. K. Dey

Updating 3D triangular mesh models based

on locally added point clouds

Received: 13 October 2004 / Accepted: 3 June 2005 / Published online: 17 November 2005

# Springer-Verlag London Limited 2005

1 Introduction

Abstract In a manufacturing area, design changes for an

original surface model are frequently required: for example,

when the physical parts are modified or when the parts are In recent years, as 3D non-contact scanning devices be-

partially manufactured from analogous shapes. In this case, come popular, the reverse engineering technique is fre-

an efficient surface updating method by locally adding scan quently adopted to create 3D surface models in many areas

data for the modified area is highly desirable. For this pur- such as computer graphics, CAD/CAM, e-commerce, vir-

pose, this paper presents a new procedure to update an tual reality, etc. Reverse engineering (RE) refers to the

initial model that is composed of combinatorial triangular process of obtaining a 3D surface model from an existing

facets based on a set of locally added point data. Nowadays, physical part. This technique enables us to design aesthetic

many people are using surface models that are represented free-form shapes rapidly from a clay model by an artist and

by triangular facets in reverse engineering, since it is fast to inspect or modify the products [1, 2].

and easy to create the triangular meshes directly from large In practice, even though a designer creates the initial

amounts of point data. The initial surface model is first surface model of a product on the computer, the product

created from the initial point set by tight cocone, which is a encounters frequent design changes in development cycles

water-tight surface reconstructor; and then the point cloud or the final product needs to be updated for some reason,

data for the updates is locally added onto the initial model such as to fix the assembly problems, to improve functional

maintaining the same coordinate system. In order to update quality, or to customize the product for various customer

the initial model, the special region on the initial surface orders. If the products are modified for any reason, the initial

that needs to be updated is recognized through the detection design data also should be revised based on the modification

of the overlapping area between the initial model and the of the products. In addition, when products are partially

boundary of the newly added point cloud. After that, the manufactured from analogous shapes, it also requires up-

initial surface model is eventually updated to the final out- dates of the initial design data. Fig. 1 shows the product

put by replacing the recognized region with the newly development process that can modify initial prototypes and

added point cloud. The proposed method has been im- it constructs the closed loop. In the case that the prototypes

plemented and tested with several examples. This algorithm are modified, it is more desirable to update the initial surface

will be practically useful to modify the surface model with model by locally digitizing the regions of the object that are

physical part changes and free-form surface design. of interest, rather than by scanning the whole part again.

In reverse engineering, surface models can be recon-

Keywords Point cloud . Reverse engineering . Surface structed by largely two approaches: through the parametric

updating . 3D scan data . Tight cocone . Triangular facets curve/surface fitting process or the triangulation process [3,

4]. Even though the typical manufacturing process has

H. Woo required the parametric surface data because of accuracy

Dept. of Precision Machinery Systems, problems, the surface model represented by triangular facets

Kyounggi Institute of Technology, is widely used in reverse engineering nowadays since it is

2121-3 Jeongwang Dong,

fast and easy to create directly and automatically from the

429-792 Shi-heung City, Kyounggi Do South Korea

point cloud data, whereas a parametric surface model is

e-mail: abpjow@r.postjobfree.com

usually constructed through a series of tedious manual op-

T. K. Dey erations such as segmentation and curve fitting processes

Dept. of Computer and Information Science,

[1]. Especially, this representation is very useful and ef-

The Ohio State University,

ficient to reconstruct sculptured or free-form shapes from

2015 Neil Avenue,

the unorganized point data; and furthermore, it can be di-

Columbus, OH 43210, USA

262

Fig. 1 Product development by

Surface Fabricate No

modifying the prototypes Scan data Final object

Modified ?

reconstruction prototypes

Yes

Re-scan the surface

problems, they performed the local surface updating by

rectly applied to rapid prototyping as well as converted to

treating the surface as a whole without the need to espe-

parametric surfaces later if necessary [5, 6].

cially identify the re-measured regions. However, they also

In recent years, many researchers have studied inten-

focused on updating the single surface patch and assumed

sively for reconstructing surface models from point cloud

data [4, 7 12] and there are also a number of techniques for that an initial approximation of the object shape is available.

Biermann et al. [19] presented a technique for cut-and-paste

shape deformations or editing in the area of computer-aided

editing of multi-resolution surfaces to add special features

geometric design(CAGD) [13, 14]. However, little research

onto an initial surface model interactively. The algorithm

has been done for updating the surface model based on the

allows the user to select an area of interest on the source

additional scan data. Moreover, most of the research has

surface and then separates both the source and the target

focused on handling parametric surfaces by repositioning

surfaces into base and detail, so that the detail surface

the control points or adjusting knots. Some research related

represents a vector offset over the base surface. After that,

to the update of an initial model by adding the modified

the detail surface is pasted onto the target surface by

shape information is reviewed below.

interactively adjusting a location and an orientation of the

Reuding and Sreckovic [15] proposed the steps in the

source feature through the re-parameterization. In this

process that locally updates the existing non-uniform ra-

paper, the subdivision surfaces are used and the source

tional B-spline(NURB) surfaces subject to different kinds

surface and the target surfaces should be available. This

of modifiers, such as discrete measurement points of a clay

technique is very efficient to edit the existing surface using

model and other existing NURB curves and surfaces. The

another existing surface, but it is difficult to be generalized

shape modifiers are all converted into modifier point sets

and may result in higher distortion for complex shapes.

first, and then computed to a matching point on the updated

The above research has been done for updating the

surface for each point in the modifier point set by per-

existing surface models based on the locally added surface

forming a normal projection of that point onto the surface.

information, but there has been little research for updating

Finally, the constrained least-square method is used to

3D triangular mesh models subject to locally and addition-

obtain a smooth surface approximation result. In this paper,

ally measured point cloud data, even though many surface

they focused on closing the loop between the designers

reconstruction algorithms from the unorganized point cloud

working on the computer and those working on the physical

data result in non-manifold triangular mesh models.

model and tried to use geometric entities as tools to in-

In this paper, a new method is proposed to update initial

fluence the shape of the main geometry in controllable

3D triangular mesh models based on the newly added point

fashion. They assumed the required changes are small

cloud data. In order to construct the initial surface and

compared to the original shape, and used the normal pro-

obtain the final updated surface model, we adopt the sur-

jection of all added points which encounters geometric

face reconstruction algorithm called tight cocone [11]. The

problems for the complicated shapes. Ma and He [16]

proposed method will help to reduce the scanning time and

presented an approach to update a local area of B-spline or

it will be practically useful to modify the surface model

NURB surfaces based on a set of locally distributed points.

based on the physical part and free-form surface design.

The region of the original surface to be updated was identi-

This paper is organized as follows. Section 2 describes the

fied by projecting all the points onto the surface; the control

basic definitions and method for reconstructing the initial

points affecting these regions were identified and only this

surface model by tight cocone. Section 3 details a proposed

subset of the control points are allowed to affect in fitting.

new method to update the initial model by locally adding

The main idea of this paper is to avoid the singularity

point cloud data. Several experimental results by the pro-

problem of least-square methods [17] by excluding from

posed algorithm are shown in Sect. 4. We conclude this

fitting the control points for which the position is not

paper in Sect. 5.

defined by the data. However, this method is only focused

on modifying a single parametric surface patch and has still

the possibility of facing ill-condition problems due to the

2 Initial surface model reconstruction

sparse data in some regions. It is not practical at all since

fitting, knot insertion and measuring may need to be reiter-

ated a number of times. Brujic et al. [18] proposed a new We assume the initial point set has been sampled from a

closed surface S R3 which has no boundary. The initial

method for linear least-squares surface updating and also

addressed the rank-deficient and ill-condition problems from surface model is constructed from this point set using the

insufficient number of data points. To overcome these surface reconstruction algorithm called tight cocone [11].

263

We briefly review several definitions for tight cocone that

are used in this paper below.

2.1 Definitions

The point data needs to be dense enough to contain detailed

information about the features of S. In the view of it, tight

cocone is developed based on -sampling of smooth sur-

faces [8, 9]. Let P be a point sample on a surface S. The

definition of -sampling was introduced in [8] and it is

defined by the medial axisM of S and the local feature size

f . The medial axisM of S is the closure of the set of

centers of all medial balls that tangentially touch at least

two points on S; and the local feature size f is defined as a

function f:S R where f(p) is the least distance between

a point p and the medial axis M. If every point p S has a

sample within the distance f(p), a oint set P S is called an

-sampling of S. If P is sufficiently dense for S, it turns out

that the Voronoi cell Vp of P is elongated along the nomals

to S. This fact is used to estimate the normals at the sample

Fig. 2 Poles and Cocone

points with poles which is defined below [8, 20].

Poles: The farthest Voronoi vertex p+ in Vp is called

the positive pole of P and the negative pole of P is the region are chosen for each point from the Delaunay tri-

farthest point p- Vp from p such that the two vectors angulation whose dual Voronoi edges are intersected by the

from p to p+ and p- make an angle more than /2. We cocones. Finally, a primary surface is constructed by ex-

call vp=p+- p, the pole vector for p. If Vp is un- tracting a manifold surface out of these candidate triangles.

bounded, p+ is taken at infinity, and the direction of vp This manifold is homeomorphic and geometrically close to

is taken as the average of all directions given by un- S, but it leaves some holes in the surface near the vicinity of

bounded Voronoi edges. undersampling. Therefore, in order to fill all holes, a sub-

sequent marking and peeling phase is performed.

The normal np of S at a point p can be estimated by this Tight cocone designates the Delaunay tetrahedra com-

pole vector vp so that the plane passing through p with the puted from the input sample as in or out according to a

normal as vp approximates the tangent plane at p. It mo- primary surface by cocone and then peels off all out tetra-

tivates the following definition of cocone which is useful hedra. This leaves the in tetrahedra, and the boundary of the

for the surface reconstruction [20, 25]. union of in tetrahedra becomes the water-tight surface,

which is the output surface. The details are described in

Cocone: The set Cp y 2 Vp : y p ; vp ! 3 =8g [11]. In this paper, this tight cocone algorithm is used to

is called the cocone of p where ((y-p),vp) denotes the generate the initial surface model from the point cloud data

acute angle between the supporting lines of the as well as to update it to the final surface model based on

vectors y p and vp. In words, Cp is the complement the locally added point cloud data. Fig. 3 shows two initial

of a double cone(clipped within Vp) contered at p with example models that are reconstructed by tight cocone.

an opening angle 3 /8 around the axis aligned with

vp. See Fig. 2 for an example of a cocone.

3 Updating the surface model

2.2 Creation of an initial model by tight cocone 3.1 Overview of the updating process

In order to generate the initial model from a point cloud, A new surface updating method is designed to modify the

tight cocone is used in this paper. Tight cocone is a water- initial model based on the locally added point cloud data. In

tight surface reconstruction algorithm [11] and it works on order to make our algorithm efficient and simple, we as-

a primary surface using the cocone algorithm which almost sumed that the new point cloud data for the special region

completes the reconstruction except at the vicinity of the that should be updated has been already registered onto the

undersamplings. The cocone algorithm begins with the initial surface model sharing the same coordinate system by

calculation of Voronoi diagram which is dual to Delaunay the special fixtures and registration algorithms [21, 22].

triangulation. It detects the boundary points in undersam- And we also assumed the new point cloud data is obtained

pling regions from the input point set; and then the can- containing some overlapping regions with the initial model

didate triangles which do not belong to the undersampling at the boundaries of the point cloud data, which makes the

264

Fig. 3 Surface reconstruction

by tight cocone

Point cloud

Point cloud

Reconstructed surface

Reconstructed surface

a b

surface smooth at the overlapping area. Actually, it is very two boundary points of the point cloud as vertices. The

difficult to obtain the additional scan data that only rep- definition of boundary points and edges are summarized

resents the exact modified features. below and Fig. 5 depicts the boundary points and edges on

The proposed method starts from recognizing the special the restricted Voronoi diagram.

region on the initial surface model that should be updated,

and then the surfaces in that region are updated based on Interior and boundary points: Let Vp,s be the re-

the added point cloud data. In our algorithm, this special stricted Voronoi diagram [23] of a point sample p on a

compact surface S R3 with or without boundaries. A

region is identified by projecting the boundaries of the new

point cloud onto the initial surface and the boundaries of sample point p from a sample P of S is called interior

the newly added point cloud are calculated by the boundary if Vp,s does not contain a boundary point of S. Sample

detection algorithm used in cocone [20]. By these bound- points that are not interior are called boundary

aries, the region that should be updated is automatically sample points.

recognized. In order to choose the region that should be

updated automatically, the angle condition is used and the Boundary edges of a point cloud: Let pb1 and pb2 be

initial surface model is finally reconstructed by replacing boundary points of a point cloud P. An edge Ei by

the region that should be updated with the locally added

point cloud data. Fig. 4 shows the overall procedure for

updating the initial surface model. Initial surface model

A new point cloud

3.2 Detecting boundaries of a point cloud

Detecting Boundaries

Since the added point cloud data represents the local sur-

from the locally added point cloud

face shapes which should be updated from the initial

surface, the point cloud data is not for a closed surface but

for an open surface that has boundaries. In order to update

Detecting the overlapping

the surface model, the region on the initial model that needs

facets on the initial surface

to be updated should be first recognized. Since the over-

lapping area between the boundaries of the new point cloud

and the initial surface model makes the border of the region Segmentation of

that is of interest, the boundary detection algorithm for a the initial surface

point cloud called boundary that is used in cocone is

employed. The algorithm, boundary, has been devised by

Dey and Giesen [20] for detecting the boundary points that Selection of the region

that should be updated

lie in the undersampled regions from a point cloud data.

Using the cocone algorithm with boundary, the boundary

points and edges can be extracted from the locally added

Final updated model

point cloud data. The boundary points of a point cloud are

well defined in [20] and the boundary edges of the point

cloud are defined as the cocone edges that are connected by Fig. 4 Overall procedure for updating the initial surface model

265

Through this algorithm, the boundary points and edges

can be detected as shown in Fig. 6. Fig. 6a shows a point

cloud and Fig. 6b,c shows the detected boundaries and

the reconstructed surface by cocone. After detecting the

boundaries of a point cloud, the walking process is per-

formed to construct a boundary edge list which keeps the

connectivity of boundary edges and generates closed edge

loops.

3.3 Finding overlapping facets

After detecting the boundaries of the added point cloud

Fig. 5 The boundary points and edges on the restricted Voronoi

data, the overlapping facets on the initial surface with these

diagram

boundaries are identified. Practically, even though the bound-

aries of the added point cloud data overlap with the initial

Cocone of P is called a boundary edge of P if Ei is model, the boundary points do not always exist on the initial

connected by Pb1 and Pb2 as the vertices. surface. When the new point cloud data is locally added

onto the initial surface, the boundary points may exist

The Voronoi cells of the boundary points are not thin and outside or inside the water-tight initial model since the

long along the normal direction of the surface. Thus, initial surface has been reconstructed by the linear interpo-

boundary points cannot be flat, whereas interior samples lation of the 3D points. Thus, the projection of boundaries

with well sampled neighborhoods are flat. Based on this of the point cloud onto the initial model is performed along

intuition, the boundary points are detected by two con- the normals to the initial surfaces and the Euclidean distance

ditions called ratio and normal conditions. The ratio con- is also considered to avoid the projection of the boundary

dition tests the skinniness of the Voronoi cells and the points onto wrong surfaces. In this paper, the following

normal condition tests if its elongation matches with those procedures are performed in order to identify the over-

of its cocone neighbors. From the boundary points, the lapping facets on the initial surface model.

When a point, Pb, of boundary points from the point

boundary edges can be extracted easily from the cocone

surface. cloud is given, the candidate facets, Tc, are identified by

Fig. 6 Detection of Boundaries

of a point cloud

Boundary points

and edges

a Point cloud data b Boundary points and edges

c Reconstructed surface by Cocone

266

Fig. 7 Detecting overlapping

facets

checking the Euclidean distance first. If the closest vertex By this procedure, the overlapping facets on the initial

of the initial model to the point Pb is recognized, all model of the boundaries of the new point cloud data can be

triangular facets that share the closest vertex are marked as recognized. Fig. 8a shows the point cloud that is added

the candidate facets as shown in Fig. 7a. All these can- onto the initial surface model and Fig. 8b,c shows the

didate facets can be directly used as the overlapping facets; candidate facets and the final overlapping facets with the

however, it makes a thick border that contains unnecessary projected boundary edges of the new point cloud data,

triangular facets and it causes bigger errors on the curved respectively.

shape in the final model. Therefore, one overlapping facet

v1 v0 v2 v0

which is corresponding to Pb is chosen from the candidate

n (1)

jv 1 v 0 v 2 v 0 j

facets by the projection operation.

The triangle Ti is selected as the overlapping facet of Pb

if the projected point Pproj of Pb onto the plane that passes

through three vertices of Ti is placed inside the triangle. The pb v1 n jpb v1 j cos Di (2)

overlapping facets are depicted in Fig. 7b. The projected

point Pproj and the distance Di to the plane passing through

P where is the angle between pb v1 and n and 0 .

Ti is calculated by Eqs. (2) and (3). If 3 0 i 2 as shown

i

Pproj Pb Di n

in Fig. 7c, the triangle is selected as the overlapping facet of (3)

the point Pb.

Fig. 8 An example of the

overlapping facets

a The initial model and the locally added point cloud

Projected

boundary edges

Overlapping facets

a All candidate facets b Overlapping facets c Projected boundary edges

267

Locally added shape

Overlapping region

2 > 1

Initial surface model

B

1

2

Boundary point

2

A

1

A B

2D Section view

Fig. 9 An example of the angle condition

3.4 Updating surface model different groups as shown in Fig. 10a. So, two triangles can

be considered respectively by connecting one vertex in

In the previous section, the detection procedure for over- each region and two vertices of a boundary edge Ei.

Let Tik represents the triangle connecting one vertex in

lapping facets on the initial model was described. The

overlapping facets construct the closed border of the region the group Rk and the vertices of a boundary edge, Ei. In this

paper, in order to create Tik, one closest vertex in Rk to the

that needs to be updated. So, the initial model can be seg-

mented into different regions by these overlapping facets. midpoint of Ei is selected from the vertices of the over-

To segment the initial model, one triangle on the initial lapping facets by Ei. Fig. 10a shows an example of the

model that does not belong to any overlapping facets is triangles Til and Tim that are connecting each region

selected as a seed triangle. From the seed triangle, the sharing one boundary edge Ei. By these triangles, the di-

initial model can be segmented by the region growing

approach [3, 24]. The seed triangle grows gradually by

merging the adjacent facets until it meets the overlapping

facets. This process separates the vertices in the initial

model into different groups, Rk, where k is the group index

and k=m+1, where the number of the closed overlapping

facet loops is m. In order to choose the groups in the region

that should be updated from the segmented groups, the

angle condition is applied here.

The final model creates the smooth surface in the over-

lapping region between the initial model and the added point

cloud. Practically, when the additional scanning operation is

applied to the modified parts, the scan data is obtained with

partially overlapping the initial surface model. In this case,

the surface of the newly added point cloud is smoothly

connected to the initial surface model after discarding the

region that should be replaced. Thus, at the boundaries of

the added point cloud, the angle between the surface recon-

structed from the added point cloud and the initial surface in

the region that needs to be updated becomes smaller than

the angle for the other region. Fig. 9 describes the angle

condition with the cross-section view. In this example, the

angle 1 for the region R1 that needs to be updated is smaller

than the other angle 2 for R2. The region that should be

updated can be recognized by this angle condition.

To calculate these angles for each boundary edge of the

added point cloud data, two triangles that share the bound-

ary edge are considered. Since the initial model is seg-

mented by the overlapping facets that are calculated by the

boundary edges of the added point cloud data, the bound-

ary edges exist over the overlapping facets between two Fig. 10 Calculation of the boundary angles

268

Tik can be calculated using the normals of the triangles

hedral angles between the triangle out of the surface of the

whose orientations are harmonized based on Tic . In Fig. 10b,

point cloud and these triangles are calculated as follows.

If Tic means one triangle that shares a boundary edge, Ei, the normals of the triangles can be calculated by Eq. (4).

in the reconstructed surface by cocone from the added point

cloud as shown in Fig. 10b, the angle ik between Tic and

Po P1 P0 P2 P P P0 P1 P P P0 P1

nTic 03 04

Po P1 P0 P2 ; nTil P0 P3 P0 P1 ; nTi P0 P4 P0 P1 ; (4)

m

Fig. 11 An example of a test

block model

a Initial data b Finding the overlapping facets

Group I Point cloud

Overlapping facets

Group II

Group II

c Segmentation d Region selection

e The final updated model

269

By the oriented normals, the dihedral angles, ik, between Once all angles corresponding to each boundary edge are

Tic and Tik are estimated by Eq. (5). calculated for each group, the angle condition by compar-

ing the average values of the angles corresponding to each

0 1

group is finally applied to choose the region that needs to

nTic : nTik C

B be updated. The angle condition used in this paper is sum-

lk Tic Tik cos 1 @ A; (5)

nT c n k marized as follows.

Ti

i

Angle condition: Let mean be the average value of ik,

k

for i 0; n and k 0 m; Pn k

k

that is mean i 0 i =n, where k is the segmented

group index and n is the number of boundary edges.

where 0 ik , n is the number of boundary edges, and

When vertices that belong to either group m or l are

m is the number of the segmented group.

Fig. 12 An example of an air-

bag model

a Initial data b Finding the overlapping facets

Group III Point clouds

Group II

Group IV

Group I

Overlapping facets Group IV

c Segmentation d Region selection

e The final updated model

270

m l

known, if mean

updated, the angle condition described in Sect. 3.4 is

m should be replaced with the locally added point

applied. In Fig. 11c, the average boundary angle for

cloud.

I

group I, mean ; is 4.45 degree, whereas the average

II

boundary angle for Group II mean is 173.76 degree. Thus,

Through this angle condition, the vertices in the region

that should be updated are marked and the marked vertices group I was chosen as the replacement of the locally added

are replaced with the added point cloud. After that, the final point cloud. Through this process, the vertices in the region

updated surface models are automatically reconstructed that needs to be updated are recognized automatically.

from the locally added point cloud and the unmarked ver- Fig. 11d shows the remaining facets and the point cloud

tices in the initial surface model by tight cocone. after discarding the vertices in the region of the initial

model that should be updated. Finally, the updated model is

created from this data set by tight cocone as shown in

4 Experimental results Fig. 11e.

For the second example, the test model of an airbag

The proposed algorithms were tested with several example shape was experimented by the proposed method. In this

parts. These algorithms were implemented in Visual C++ example, three point clouds that require the subtractive

and the CGAL library was used for the Voronoi and operation were added onto the initial model as shown in

Delaunay computation while detecting the boundaries of Fig. 12a. From these initial data, the boundaries of each

point clouds and reconstructing the initial and updated point cloud are detected and the overlapping facets for each

models by tight cocone. All experiments were run on a point cloud are extracted from the initial model through the

Pentium IV 1.6GHz PC with 512 MB. projection process. Fig. 12b shows the detected over-

For the first example, the U-shape point cloud was lapping facets on the initial model and these overlapping

locally added on the initial test block as shown in Fig. 11a. facets segment the initial model into four groups as shown

The initial surface model was generated from the initial in Fig. 12c. For each point cloud, the average boundary

point data set by tight cocone and the locally added point angles to choose the region that needs to be updated are

cloud data was simulated by our own point sampling calculated and compared. In this example, the average angle

program to test the proposed algorithm. After adding the for group IV is compared with that for group I, II, and III

point cloud to the initial model, the boundaries of the point respectively. By the angle condition, the vertices in all

cloud are calculated using the boundary detection algo- groups except group IV are discarded and replaced with the

rithm and then the overlapping facets on the initial model locally added point clouds. Fig. 12d shows the remaining

are extractred by projecting the boundaries onto the initial facets and the point clouds for updating the initial model

model. Figure 11b shows the overlapping facets on the and the final updated model is obtained as shown in

initial model. After that, the initial model is divided into Fig. 12e.

two groups based on the overlapping facets as shown Figure 13 shows the example of updating a golf club

Fig. 11c. Here, one of these two groups should be replaced model. When the final product is slightly changed, the

with the added point cloud for updating the initial model. In initial surface model should be updated by locally adding

Fig. 13 An example of a golf Group I

club model

Group II

a Initial data b Segmentation

d The final updated model

271

b c d

a

e f g

Fig. 14 An example of a joystick model

the point cloud data for the modified region. The initial Figure 14 shows an example of updating a joystick

surface model and the point cloud that is registered into the model. The initial surface model is displayed in Fig. 14a

same coordinate system are shown in Fig. 13a. For this and two different point cloud data for updating the initial

example model, the added point samples exist both inside model are respectively shown in Fig. 14b,e. By adding

and outside the initial surface model but the region that these different point clouds, the initial surface model can be

needs to be modified is successfully detected using the customized differently. Fig. 14c,f show the initial model

approach by the boundaries of the point cloud data. with each different point cloud respectively and the initial

Fig. 13b shows the overlapping facets on the initial model model is updated to different shapes based on each added

detected by the boundaries of the point cloud and the two point cloud by the proposed method. As the result of the

segmented groups based on the detected overlapping facets. proposed method, the final updated surface models for each

After replacing the vertices in the group I region that needs added point cloud are shown in Fig. 14d,f respectively and

to be updated with the point cloud by the angle condition, Table 1 summarizes the number of points and the com-

the initial model is updated automatically based on the puting time for all examples tested in this paper.

locally added point cloud as shown in Fig. 13c.

Table 1 The computing time of the proposed method

Model Number of points Computing time(s)

Initial Point Updated Boundary Overlapping facets Segmentation and Reconstruction of the

model cloud model detection detection region selection updated model

Test block (Fig. 11) 5,991 11,488 17,057 62.27 29.70 1.22 44.86

Airbag (Fig. 12) 28,650 34,866 60,959 150.02 228.05 10.97 337.32

Golf club (Fig. 13) 49,380 4,572 53,570 9.25 75.265 7.42 388.80

Joystick I (Fig. 14d) 37,122 10,574 45,893 24.73 134.34 7.45 370.80

Joystick II (Fig. 14g) 37,122 32,187 65,956 204.00 170.88 8.86 367.12

272

4. Sun W, Bradley C, Zhang YF, Loh HT (2001) Cloud data

5 Conclusions

modeling employing a unified, non-redundant triangular mesh.

Comput Aided Des 33:183 193

In this paper, we proposed the surface updating algorithm 5. Krishnamurthy V, Levoy M (1996) Fitting smooth surfaces to

based on the locally added point cloud data. When the dense polygon meshes. International conference on computer

graphics and interactive techniques

scanning operation is applied to the partially modified

6. Navau JC, Garcia NP (2000) Modeling surfaces from meshes of

parts, new point cloud data that represent the change of the

arbitrary topology. Comput Aided Geom Des 17:643 671

parts are locally added to the initial surface model. In this 7. Edelsbrunner H, Mucke EP (1994) Three-dimensional a shapes.

case, the proposed procedure can be efficiently applied for ACM Trans Graph 13:43 72

updating the initial model based on the locally added point 8. Amenta N, Bern M, Kamvysselis M (1998) A new Voronoi-

based surface reconstruction algorithm. SIGGRAPH 98

cloud. In order to update the initial model, we have first

9. Amenta N, Choi S, Kolluri RK (2001) The power crust. In:

recognized the special region on the initial model that Proc. Solid Modeling 01

needs to be updated by marking the overlapping facets on 10. Edelsbrunner H (1998) Shape reconstruction with Delaunay

the initial surface based on the boundaries of the added complex. In: LNCS 1380, LATIN'98: Theoretical Informatics

119 132

point cloud data; and then the initial model has been finally

11. Dey TK, Goswami S (2003) Tight cocone: a water-tight surface

updated by replacing the recognized region with the newly reconstructor. In: 8th ACM Sympos. Solid Modeling Applications

added point cloud. Here, for the purpose of creating the 12. Boissonnat JD, Cazals F (2000) Smooth surface reconstruction

initial model and detecting the boundaries of the point via natural neighbor interpolation of distance functions. In:

Proc. 16th. ACM Sympos Comput Geom

cloud, we have adopted the cocone and tight cocone algo-

13. Coquillart S (1990) Extended free-form deformation: a sculpturing

rithms, which are the surface reconstruction algorithms

tool for 3D geometric modeling. In: Proc. ACM SIGGRAPH 90

from unorganized point data. The proposed method will 14. Cavendish JC (1995) Integrating feature-based surface design

enable us to create the customized model from the initial with freeform deformation. Comput Aided Des 27(9):703 711

design rapidly and it might shorten the additional scanning 15. Reuding T, Sreckovic M (1993) Automatic Local Updating of

CAD Surface Models. In: the Third SIAM Conference on

time. It will be practically useful for the surface modifi-

Geometric Design

cation based on the physical part changes and free-form 16. Ma W, He P (1998) B-spline surface local updating with un-

surface design. organized points. Comput Aided Des 30(11):853 862

As for further work, when the existing mesh models such 17. A. Bjorck (1996) Numerical methods for least squares problems.

Society for Industrial and Applied Mathematics, Philadelphia

as STL files generated from CAD models are used, the

18. Brujic D, Ristic M, Ainsworth I (2002) Measurement-based

density of points could be very different from that of the modification of NURBS surfaces. Comput Aided Des 34:173

locally added point clouds. In this case, the skinny triangles 183

can be generated. To avoid these problems, some re-sam- 19. Biermann M, Martin I, Bernardini F, Zorin D (2002) Cut-and-

paste editing of multiresolution surfaces. In: SIGGRAPH 2002

pling or subdivision techniques can be considered to create

20. Dey TK, Giesen J (2001) Detecting undersampling in surface

the high quality mesh models.

reconstruction. In: 17th Ann Sympos Comput Geom

21. Lee KH, Lee SK, Kim SM (2002) Design of a universal fixture

for laser scanning. Adv Manuf Technol 19:426 431

References 22. Yau H, Chen C, Wilhelm RG (2000) Registration and inte-

gration of multiple laser scanned data for reverse engineering of

complex 3D models. Int J Prod Res 38(2):269 285

1. Varady T, Martin R, Cox J (1997) Reverse engineering of

23. Edelsbrunner H (2001) Geometry and topology for mesh gen-

geometric models-an introduction. Comput Aided Des 29(4):

eration. Cambridge University Press

255 268

24. Hoffman RL, Jain AK (1987) Segmentation and classification

2. Tai C, Huang M (2000) The processing of data points basing on

of range images. IEEE Trans Pattern Anal Mach Intell 9(5):

design intent in reverse engineering. Mach Tools Manuf 40:

608 620

1913 1927

25. Dey TK, Woo H, Zhao W (2003) Approximate medial axis for

3. Woo H, Kang E, Wang S, Kwan H, Lee (2002) A new seg-

CAD models In: Proceedings of 8th ACM Symposium on Solid

mentation method for point cloud data. Int J Mach Tools Manuf

Modeling and Applications, 16 20 Jun 2003, Seattle, WA,

42:167 178

USA pp 280 283

Contact this candidate