Data Model
Resume:
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: ****@*****.**.**
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