Computer-Aided Design 37 (2005) 109122 www.elsevier.

com/locate/cad

Drawing curves onto a cloud of points for point-based modelling

Department of Product & Systems Design Engineering, University of the Aegean, Ermoupolis, Syros 84100, Greece b ELKEDETechnology & Design Centre SA, Research & Technology Department, 14452 Metamorphosis, Greece Received 18 December 2003; received in revised form 30 April 2004; accepted 4 May 2004

Abstract Point-based geometric models are gaining popularity in both the computer graphics and CAD elds. A related design/modelling problem is the focus of the reported research: drawing curves onto digital surfaces represented by clouds of points. The problem is analyzed and solved, and a set of design tools are proposed which allow the user/designer to efciently perform product development (alternative name: detail design) tasks which require efcient processing of a digital surface. The primary tool is a robust and efcient point projection algorithm combined with a smoothing technique for producing smooth digital curves lying onto the cloud surface. The new design tools are tested on a real-life industrial example with very satisfactory results, which are thoroughly presented in the paper. q 2004 Elsevier Ltd. All rights reserved.
Keywords: Digital curves; Digital surfaces; Point-based representation; Point projection algorithm; Polylines; Smoothing polylines

1. Introduction During the last 5 6 years, an increasing trend has been developing in Computer-Graphics, as well as in the CAD community, towards surface models based on discrete elements like polygons, triangles and, very recently, points. Regarding polygons and triangles, these have long been the standard basic element in graphics, and recently their importance has also been increasing in CAD/CAE/CAM. Indeed, modern design-technologies like Reverse Engineering (RE) [7], Virtual Engineering [15] and Rapid Prototyping [37] are using, almost exclusively, polygon meshes. Collaborative design methods are also using meshes [28]; e.g. Ref. [36] contributes to network-based integrated design and reports that "faceted models have become the de facto standard model for describing complex geometry over the Internet". Finally, concept development systems most often use a polygon mesh [28,30] rather than analytic geometric models. Very recently, the above trend, towards discrete models, has been culminating by bringing to the foreground
* Corresponding author. Address: Department of Product and Systems Design Engineering, University of the Aegean, Ermoupolis, Syros, 84100, Greece. Tel.: 30-228-109-7129; fax: 30-228-109-7009. E-mail addresses: azar@aegean.gr (P.N. Azariadis), sapidis@aegean.gr (N.S. Sapidis). 0010-4485//$ - see front matter q 2004 Elsevier Ltd. All rights reserved. doi:10.1016/j.cad.2004.05.004

the plainest of all geometric elements, the point! The reasons are very convincing: regarding modern computer graphics, in complex models the triangle size is decreasing to pixel resolution [3], thus, points, and more specically connectivity-free points, are the obvious choice for a primary surface model. Many recent papers (see Refs. [2,40] and references therein) adopt this approach, and develop efcient algorithms to solve related problems. For CAD, since the design process starts with points (user dened or imported using RE) and ends with points (VE/simulation/ analysis models or NC data), why use as primary model something else? This argument is developed in Ref. [10], which updates the related discussion rst presented, long time ago, by McLaughlin [23]. Cripps [10] presents a comprehensive point-based CAD/CAM system for design/visualization and tool-path generation using subdivision-surfaces for model renement, when this is needed. The pioneering work [16] reviews geometric modelling methods for NC machining and proposes point-based approximations as the most appropriate. Vergeest et al. [31] focus on shape reuse in modern design and proposes a novel methodology combining a primary CAD model with many auxiliary shape models in a corporate library. This family of shape models includes feature-, geometric-, CAD-, as well as point cloud models used as descriptors of library items.

110

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

In RE, current systems allow acquisition/processing of clouds of points so dense that triangulation is meaningless, in complete analogy to computer-graphics applications. Some very recent examples of publications, adopting this approach, are: Woo et al. [34] proposing a new segmentation method combining unorganized points with et al. [6] enhance the standard reversean octree. Benko engineering problem with constraints; the whole development is based on point clouds. Corbo et al. [11] combine up to 50 views of objects, measuring 1.2 m 0.6 m 2 m, producing clouds with millions of points. This work proposes novel design analysis tools solely based on point clouds. Point-based models, enhanced with atomic-level physics, lead to the so-called particle systems, which are extensively used in discrete mechanics models for virtual claying (see Refs. [17,20] and references therein) competing against standard methods based on nite elements or th and his co-workers [15,29] boundary elements. Horva enhance point-based models and propose vague discrete modelling, capable of simultaneously describing multiple objects, to support concept development in collaborative virtual environments. Concluding this short review of point-based surface modelling, we note that similar proposals for describing volumes/solids are constantly appearing, with typical examples the various volumetric representations, like voxels [8], and the ray- and triple-ray representations [9,24,25].

1.1. Drawing curves on clouds of points The present paper deals with product design using a point cloud and focuses on drawing curves on (more accurately: within) a thick or thin cloud of points. The core of the proposed product design approach is shown in Fig. 1: initially the user constructs a rough shoe design composed of polylines which only look like they lie onto the cloud surface (e.g. of a shoe last). The system eventually replaces these polylines by smoothed ones lying exactly onto the cloud surface (according to a specic mathematical model) as it is shown in Fig. 1c. The transformation of the initial design (Fig. 1a) to the nal smooth one (Fig. 1c) requires the elimination of intermediate side effects, like the line wrinkles shown in Fig. 1b. Designing curves onto a cloud of points is a surprisingly difcult problem, and although no publication on it has been yet identied, few recent papers deal with 2D versions of the and problem and clearly show the related difculties. Benko rady [7] deal with segmentation of thin, and thus Va triangulated, points, yet curve-tting to thick 2D clouds of points does emerge, and heuristics are used to thin a cloud before curve tting. Curve-tting to a thick 2D point set is a vital subproblem in Ref. [26], too. Again, 2D curve-tting is preceded by thinning, based on related tools from image processing. Polygonal curve-tting to a 3D point cloud appears in Ref. [21]; this is heuristically treated by solving the corresponding 2D problem, which is a reasonable approach given the papers subject (rapid prototyping).

Fig. 1. Product design using a cloud of points. (a) The user denes design polylines in one or more views, (b) the system projects the design polylines onto the cloud, (c) the system calculates projected smooth cubic B-splines which are nally described as digital curves, i.e., dense polylines.

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

111

The work of Lee [19] is devoted almost entirely to the problem of curve-tting to thick point clouds. It identies shortcomings in existing methods and focuses on the major issue of difculties caused by varying thickness. A new solution is proposed for the 2D case, based on thinning using the moving least-squares technique. The author recognizes that this new method cannot be directly extended into the 3D case, yet he describes an interesting heuristic that performs well for a number of examples. Finally, the recent publication [37] deals with direct construction of a layerbased rapid prototyping model from cloud data. A signicant part of this work is devoted to tting to a 2D cloud a polygonal curve with as few linear pieces as possible. Related difculties are identied and an interesting algorithm is proposed, which suffers from several deciencies: (a) selection of the starting point is accomplished by trialand-error, (b) it involves four parameters that the user must specify, and (c) no proof of converge is presented, neither any measure for the required execution time.

(c) Since the point cloud is thick, one should not assume that the given points are equipped with normal-vector and/or orientation. (d) It is quite possible that the underlying surface of a point cloud is neither smooth (i.e. it may have sharp edges) nor closed (i.e. it may have a boundary). The above characteristics render many published surface reconstruction methods, from the elds of Computational Geometry and Computer Graphics, inappropriate for industrial use. This is the case, e.g. for the crust algorithm [4], which contradicts all the above characteristics, as it needs to operate on a good sample from a smooth surface, it interpolates data using a normal ltering step, and handles neither sharp edges nor boundaries. Another example is natural neighbour interpolation [5], which also contradicts all characteristics stated above, as it requires a sufciently dense sample (see Theorems 2 and 3 in Ref. [5]), interpolates the input points (see Introduction in Ref. [5]), assumes that the given points are equipped with normal directions and handles neither sharp edges nor boundaries. Regarding the surface reconstruction methods offered by RE and CAD, it is fair to say that early efforts (including those of the second author), reviewed in Ref. [32], were quite far from satisfactory, as manifested by the current intense research on the various components of the Reverse Engineering problem, like data parameterization [1], free-form surface tting [33,38], standard shape reconstruction [6], and cloud segmentation [7,39]. In conclusion, it is the immaturity of this eld and remark (1) above that force us to adopt the strategy of avoiding, as much as possible, surface reconstruction in designing with point clouds. Note 1. Though the proposed curve-drawing method is in accordance with point (a) above (i.e. it imposes no a priori requirements on a clouds density), its performance is surely affected by the local density of the given point cloud. Extensive numerical tests (some are presented in Section 2.5) demonstrate that the methods performance is very stable even for a point cloud with a varying density. Despite this, inuence of density variation on curve-drawing is one of the main topics of the authors current research. 2. Point projection onto a cloud of points The surface model considered in this paper is a collection of (possibly noisy) points, sampled on a physical object, without any topological information. A vital component of the digital-curve design methods, presented below, is a method to project points onto a cloud surface. This is exactly the subject of this section. Projecting an arbitrary point onto a cloud surface is based on the following methodology: Firstly, an error function is dened for measuring the distance between the point to be projected and the point cloud.

1.2. Drawing curves onto a point cloud based on point projection The proposed Curve-Drawing technique, detailed in Section 3, (a) is based on projecting points onto a cloud (this problem is analyzed and solved in Section 4) and (b) is not using any surface tted to (in other words: reverseengineered from) the given point cloud. Part (b) of this strategy is due to the following reasons: 1. Drawing curves on a point cloud is viewed as a low level procedure, employed by many high level operations, including surface reconstruction (e.g. methods using curve networks [32]). In this framework, it does not make sense for the Curve-Drawing procedure to employ a surface reconstruction method. For the current highly accurate and dense (and thus often thick) point clouds, surface reconstruction is always an approximation operation that causes some loss of information ([4, Section 2]). This is avoided when one operates directly on the given point cloud. Current scanning systems produce highly accurate and dense (thick) point clouds, implying the following characteristics for the point set and the corresponding surface reconstruction problem: (a) Although point clouds are usually dense, it is not rare for a pointset to include undersampled areas. Thus, it is vital for an industrial system to employ processing algorithms that are free of any strict conditions regarding sampling density. (b) It is meaningless to try to reconstruct an interpolating surface. Only surface approximation is a reasonable framework for surface reconstruction.

2.

3.

112

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

Secondly, the point of interest is projected onto the cloud surface by minimizing the above error function. The current literature does not offer a satisfactory solution to the problem of specifying an appropriate point cloud error function. Only Ref. [13] proposes a related error function (and employs it in developing an LOD surface representation), yet this cannot be used in the present research as it is based on a polygonal representation of the models surface. The rest of this section derives an appropriate point cloud error function and uses it to solve the problem of projecting a point onto a cloud. 2.1. The directed projection problem Let CN {pm xm ; ym ; zm lm 0; ; N 2 1} be the given cloud of points and let p x; y; z be an arbitrary 3D point, hereafter called a vertex, with n nx ; ny ; nz an associated projection vector. The pair p; n is denoted by ^ kp; nl: Then, p Denition 1 (The directed projection problem). The directed projection pp of p; in the direction of n; onto the cloud of points CN is dened as follows. Each pm [ CN is associated to a positive weight am : Then, pp is the solution of the problem: Find pp minimizing Epp
N 21 X

have a theoretical justication for this. A possible approach would be to consider a point set CN lying on a known parametric surface S Su; v: Then, if Spp is the ^ onto S; the method (2) (3) should produce projection of p a vertex pp sufciently close to Spp : Though no theoretical results have been produced yet along this direction, the related numerical experiments (see Section 2.5) are very convincing. 2.1.2. Error analysis of the projection method of Denition 1 The present analysis relates the measurement error 1 in the point cloud with the implied error in the solution of the directed projection problem (expressed by Eq. (3)). It is assumed that a cloud has been derived with points lying within a maximum Euclidean distance 1 from their true location: C0N {p0m x0m ; y0m ; z0m ; lkp0m 2 pm k # 1; m 0; ; N 2 1}: Using C0N the corresponding solution of the directed projection problem is given by t0

l0 2 pn knk2

where

l0
am kpp 2 pm k2 : 1

m 0

^ The point pp is also called the directed projection of p kp; nl onto CN : For given weights {am } (these are specied in Section 2.2), one writes pp xp ; yp ; zp as pp pp t p tn; t[R 2

c01 nx c02 ny c03 nz and c00 c0 ; c00 N 21 N 21 N 21 X X X c01 am x0m ; c02 am y0m ; c03 am z0m :
m 0 m0 m0

Then lt 0 2 t l and ll0 2 ll knk2 lc01 2 c1 nx c02 2 c2 ny c03 2 c3 nz l c0 1 # lc01 2 c1 llnx l lc02 2 c2 llny l c0 lc03 2 c3 llnz l 2 3 21 X 14 N # 1 am lnx l lny l lnz l5 c0 m0 6

Then, the solution of problem (1) is [1]

l 2 pn t knk2
where
N 21 X c 1 nx c 2 ny c 3 nz ; and c0 am ; c0 m0 N 21 X

ll0 2 ll

l
c1

am x m ; c 2

N 21 X

am y m ; c 3

N 21 X

am zm :

m0

m0

m 0

Intuitively, the projection process dened by Eqs. (2) and (3) can be regarded as a method for intersecting a given ^: cloud surface with the semi-innite line dened by p
0

Then one derives

am lnx l lny l lnz l c0 knk2 #1

lt 2 t l # 1 2.1.1. Investigating the intuitive correctness of Denition 1 Although the projection method developed here, on the basis of Eqs. (2) and (3), produces reasonable results (see sections with examples below), one would certainly like to

m0

3knkc0 c0 knk2

3 knk 7

Conclusion. Eq. (7) proves that there is a constant scalar k; independent of the cloud of points, such that

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

113

lt0 2 tl # k1: In other words, the error in the computed solution (3) is always bounded and depends linearly on the error in the measured cloud points. 2.2. Selecting an appropriate weight function The weights am play a dominant role in the computation of pp and thus they should be chosen very carefully. In general, the weight am $ 0 of pm [ CN should take a larger value when pm is closer to the vertex p; to be projected, and a descending value as the distance from pm to p increases. The weight function used in Ref. [1] is am 1 k p 2 pm k 4 ; am [ 0; 1 ; 8

which is adequate for the introduced point-parameterization method. Eq. (8) takes into account only the distance between pm and p: Erikson and Manocha [13] utilize a weight function based on the surface area of the faces adjacent to pm : This is inapplicable to the present surfacerepresentation which is solely a pointset without any topological information. Solving the problem described by Denition 1 requires a new weight function taking under consideration also the direction n associated to the given vertex p: Systematic experiments have led to the conclusion that one should use a weight function taking under consideration both the distance between p and pm ; kpm 2 pk; as well as the quantity kpm 2 p nk measuring the distance between pm and the axis dened by p and n: We propose: am 1 1 kpm 2 pk2 kpm 2 p nk2 ; am [ 0; 1 9

Fig. 2. (a) Directed projection of a vertex p onto the cloud of points CN : (b) Colour map representing values of the weight function (9).

We force am [ 0; 1 in order to ensure numerical stability of this quantity; am 1 when p [ CN ; i.e. p coincides with one of the cloud points or when pm lies onto the projection axis. Fig. 2a shows the difference between Eqs. (8) and (9): the former takes a maximum value for points in the vicinity of the top-left part of the cloud while the latter is maximized at cloud points near the axis of projection. Fig. 2b shows the improved local value-distribution of the weight function (9). Several vertices are projected onto the cloud surface of a shoe last along the directions shown as dark lines. The larger am is, the darker we paint the corresponding part of the cloud. It is obvious that the weights are maximized in the vicinity of the axis of projection. Indeed, the darkest points correspond to the intersection of projection axes with the cloud. 2.3. Specication of projection vectors

to dene, through a Graphics Interface tool, projection vectors. In general, the geometric pipeline utilizes viewing and projection matrices and a viewport for clipping to transform the world (or object) coordinates of a point into window (or screen) coordinates. For interactive curve design one has to reverse this process. Specically, in the present implementation, users utilize the mouse to specify the image of a vertex in the rest of this paper, all user-dened points will be called verticesas a location in the two-dimensional screen. Then, the system reverses the transformation process and maps the specied screen point onto the near and far clipping planes as it is shown in Fig. 3, producing the two auxiliary vertices pn and pf ; marked with small circles. These two vertices dene both the input vertex and the associated projection vector (see Denition 1), as follows: * + p f 2 pn ^ p kp; nl pn ; : 10 kpf 2 pn k Eq. (10) holds also for parallel viewing transformations. 2.4. The proposed point-projection algorithm

The directed projection problem (Denition 1) and formulae (3), (4) and (9) require specication of adequate projection directions. The present research deals with interactive curve-drawing and thus it relies on the user

The outline of an algorithm for projecting an arbitrary vertex onto a cloud of points, called PointProjection, ^ is given in Fig. 4. The algorithm takes as input a vertex p

114

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

Fig. 3. The perspective viewing volume and the ray dened through users input.

^ and a cloud surface CN and computes the projection pp of p onto CN : This is achieved through an iterative procedure with the aid of a local variable cn which is a working subcloud of CN ; initially, cn ; CN : During the projection calculation, the cardinality of cn is gradually reduced by removing from it cloud points which are found to be insignicant for the projection calculation. In this way, one is able to reduce processing time and also increase the accuracy of the projection procedure. The signicance of each cloud point in the current cn is determined by the corresponding weight am ; calculated using Eq. (9); all weights are stored in a single vector a [ Rn : In order to decide which cloud points should be ignored in the K th iteration, another local variable named alimit is dened 8 amax 2 amean > ; K,9 < amean 10 2 K alimit 11 amax 2 amean > :a ; otherwise mean 2 where the real parameters amax ; amean ; correspond to the maximum and mean value of the computed weights {am }: Eq. (11) is dened in such a way that cloud points with a small inuence (i.e. small am ) are discarded in the rst iterations of the algorithm. This is particularly useful for large data sets with tenths or hundreds of thousands of points, improving considerably the efciency of the algorithm. According to Fig. 4, the proposed algorithm is initiated by setting the working sub-cloud equal to the initial one ^ with cn U CN : Then a loop begins and the given vertex p the current working cloud cn is passed into the OptimProjectToCloud procedure (Fig. 5) producing pp ; which is the ^ onto cn : current estimation for the projection of p OptimProjectToCloud also returns the weight vector a ^ : If the Euclidean distance with respect to the input vertex p between the current projection estimation pp and the vertex ^ is less than a threshold 1; the procedure is terminated. p

Fig. 4. The fundamental PointProjection algorithm.

^ onto cn : Fig. 5. The algorithm for estimating the optimal projection of p

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

115

^ is moved to the current pp In the opposite case, the vertex p p p U p and a new iteration commences with redening cn : cloud points with a weight smaller than the current alimit are removed from cn ; for the reasons explained above. Finally, if amax 1 ak ; the algorithm terminates and returns as projection vertex the cloud point pk : An in-depth experimental evaluation of the accuracy and robustness of the proposed point-projection method is given in the following section. 2.5. Numerical/experimental results In order to investigate the performance of the proposed PointProjection algorithm, several experiments have been conducted. Two representative sets of results are discussed to illustrate the accuracy and robustness of this algorithm. 2.5.1. Testing the effectiveness of the PointProjection algorithm for a thin cloud of points The rst experiment investigates the accuracy of PointProjection for thin point clouds, i.e. clouds of points lying exactly on a mathematical surface (this is the case here) or on a polygonal surface. Several clouds CN ; with a varying density, have been derived from a known cubic B-spline surface. The number of points ranges from ^ i k pi ; N 10; 000 to 300,000. Four specic vertices p ni l; i 0; ; 3; are projected onto each CN using PointProjection, producing four pp i;N vertices per cloud. The intersection ps i;N of the axis dened by pi and ni with the given B-spline surface is pre-computed using a modied Newton method. Finally, the Euclidean norm p Ri;N kps i;N 2 pi;N k is used for measuring the accuracy of PointProjection. Table 1 summarizes the obtained results. Several interesting conclusions are derived: The accuracy of the projection (measured by Ri;N ) is very satisfactory: the average value of Ri;N is 0.05 mm even when N is relatively small. Although the employed threshold 1 1026 mm is quite small, the convergence of the algorithm is fast; in the worse case, seven iterations are required. The required execution time is quite small (see fth column of Table 1) despite the fact that no special acceleration techniques (like bucketing) are included in this version of PointProjection. Generally, when the number of points is increased the corresponding projection error is reduced. Although, some minor deviations have been observed (i.e. for i 2; 3), these are due to two reasons: the numerical p nature of the computation of both ps i;N and pi;N ; and the varying cardinality of the nal working sub-cloud cn : Generally a change in the cardinality of the working subcloud implies a change in relations (4) which in turn may result to slightly altered results.

Table 1 Numerical results of the PointProjection algorithm with a cloud surface with increasing density i iter Ri;N (mm) Final sub-cloud 1 1 2 1 1 1 1 1 1 2 2 3 3 4 1 2 3 3 1 1 1 1 1 2 2 2 3 3 Time (s) N

0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3

4 4 8 4 4 4 4 4 4 5 5 5 5 6 4 6 6 6 4 4 4 4 4 6 6 7 6 6

0.070434 0.070434 0.018149 0.008543 0.008543 0.008543 0.008543 0.123624 0.123624 0.113043 0.113043 0.075981 0.075981 0.063970 0.015238 0.012163 0.009992 0.009992 0.010989 0.010989 0.010989 0.062142 0.062142 0.029960 0.029960 0.029960 0.031314 0.031314

0.005844 0.017753 0.040418 0.065357 0.086174 0.123222 0.186434 0.005813 0.018155 0.037524 0.062263 0.087527 0.125088 0.194163 0.005459 0.017900 0.038129 0.064427 0.084991 0.120740 0.184584 0.005572 0.017471 0.037981 0.063716 0.092502 0.129766 0.231826

10,000 30,000 60,000 100,000 140,000 200,000 300,000 10,000 30,000 60,000 100,000 140,000 200,000 300,000 10,000 30,000 60,000 100,000 140,000 200,000 300,000 10,000 30,000 60,000 100,000 140,000 200,000 300,000

The surface bounding box is 246 38 102 mm, 1 1026 mm.

2.5.2. Testing the effectiveness of the PointProjection algorithm for a thick cloud of points The second experiment focuses on the efciency of the PointProjection algorithm for a thick cloud of points, which is dened to be any cloud that is not thin. Indeed, in many modern applications, one deals with highly accurate clouds where the point-density is comparable to the point-error (or cloud thickness). Here, it is meaningless to triangulate the given points as this would produce triangles of sub-pixel size [3] or a surface which would not be unambiguously dened. Our aim is to test whether the projected vertices lie within the boundaries of the given thick cloud. Also, a robust algorithm should produce consistent results with respect to the cloud thickness: when the thickness is reduced the projection error should be reduced accordingly. For this experiment, a series of clouds Cr N with a varying thickness have been produced. The initial cloud C0 N is derived by calculating points on a known cubic B-spline surface, i.e. p0 m Sum ; vm : Additional clouds are produced by adding to each cloud point in C0 N a noise factor along the corresponding normal direction of the initial B-spline surface S: Specically, the cloud Cr N

116

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122 Table 2 Numerical results of the PointProjection algorithm with a series of cloud surfaces with decreasing thickness i iter Ri;r (mm) Final sub-cloud 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 7 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

includes the points

12

r (mm)

where r is the clouds thickness factor, dr represents a random number dr [ 21; 1 which is different for each pr m ; and num ; vm is the unit normal-vector of the surface S: Thus, the actual thickness of Cr N is not constant and varies between 2r; r with respect to the rst cloud C0 N ; which corresponds to r 0 (this cloud is also considered as the mean cloud). This thickness variation increases signicantly the complexity of the experiment. ^ i kpi ; ni l; i 0; ; 3 (different from Four vertices p those used in Section 2.5.1) are projected onto each Cr N using the PointProjection algorithm, producing four pp i;r vertices per cloud. The intersection of the axis dened by pi and ni with S is ps i;r : Finally, the Euclidean norm Ri;r p kps i;r 2 pi;r k is used for quantifying the accuracy of the projection. All the obtained results are listed in Table 2. Some observations: Although the employed threshold 1 1026 mm is quite small, the convergence of the algorithm is fast: on an average, less than 14 iterations are required. The computed error Ri;r is signicantly smaller than r; implying that the proposed algorithm is consistently accurate for cloud surfaces with variable thicknesses. The produced results comply with the general observation: if r ! 0 then Ri;r ! 0; which is a direct consequence of the conclusion derived in Section 2.1.2. There are some cases, though, that this observation does not hold, like for instance i; r 0; 0:5 and i; r 1; 4: In the rst case, we notice a decrease in the projection accuracy, while in the latter case, the projection accuracy is higher than that of the thin clouds produced for r , 4: Both cases are explained if we take into account that the thickness of each cloud is not constant but varies between 2r; r: Thus, it is likely that in the neighbourhood of a point ps i;r the cloud thickness is much smaller than r resulting to a very small Ri;r and vice versa. 2.5.3. Conclusions Two extensive experiments have been presented establishing the accuracy and robustness of the proposed PointProjection algorithm. The former is conrmed by projecting a series of vertices onto thin clouds with a varying number of points. The latter is illustrated by projecting a set of vertices onto a series of thick clouds of varying thickness. It must be emphasized that (a) for both experiments, we have visually conrmed that the produced results are compatible with the intuitively expected output, and (b) similar results have been obtained for about a dozen

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3

17 13 11 9 10 10 10 13 76 20 17 18 15 13 13 5 10 10 9 10 8 7 7 5 10 11 13 16 15 13 11 11

2.233382 1.835266 1.482495 1.441944 1.084490 0.414982 0.004411 0.061961 0.035033 0.538647 0.308358 0.159938 0.096234 0.050045 0.067558 0.053186 0.837105 0.610330 0.410340 0.107808 0.069722 0.037446 0.356098 0.018793 1.120749 0.874228 0.632466 0.336782 0.222144 0.122572 0.254029 0.085678

4 3.2 2.5 2 1.5 1 0.5 0 4 3.2 2.5 2 1.5 1 0.5 0 4 3.2 2.5 2 1.5 1 0.5 0 4 3.2 2.5 2 1.5 1 0.5 0

The surface bounding box is 246 38 102 mm, N 10; 000; 1 1026 mm.

other data-sets including both academic and industrial cases. 3. Interactive design of discrete curves onto a cloud of points This section focuses on constructing discrete (or digital) curves onto a given digital surface. The proposed design paradigm is point-based, thus, the surface model is the cloud of points while smooth curves are approximated by a nite number of vertices, dened interactively by a designer/stylist. Given as input an ordered sequence of ^ i kpi ; ni l the output of the following design tools vertices p is either a linear or a higher-order curve (in the pointwise sense) which either interpolates or approximates the ^ i onto CN and lies onto the given projections pp i of p cloud surface. The PointProjection algorithm is the main part of this process, which is supported by the method for specifying the projection directions described in Section 2.3.

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

117

3.1. Designing line segments onto a cloud of points Utilizing the proposed point projection algorithm, it is possible to develop a scheme where the user will be able to trace digital curves onto clouds of points. The simplest type of curves that can be constructed are piecewise linear curves or polylines. Each polyline is created after ^ i onto the cloud surface projecting user-dened vertices p and connecting successive projected-vertices pp i with line segments. Since the cloud surface is curved, these line segments, in general, do not lie, in any sense, on the given cloud. Thus, the curve tracing application is equivalent to Denition 2 (Line-segment projection: explicit de^i nition). Given a cloud of points CN and two vertices p ^ i1 kpi1 ; ni1 l; the line-segment qi is dened kpi ; ni l; p p with end-points the projected (onto CN ) vertices pp i and pi1
p qi u 1 2 upp i upi1 ;

(3) Examine the projection distance for all midpoints considered in step 2. When this is found to be smaller than the working accuracy epsilon, the corresponding segments are labelled as terminal, OR (4) If the length of a line segment is smaller that a minimum allowed value then label it as terminal. GOTO step 2. Note 2. In the rest of this paper, we consider that the projection of a line-segment according to Denition 3 is ^ i;k kpi;k ; ni;k llk ^ i {p equivalent to projecting a set p 0; ; ki 2 1} of ki distinct nodes pi;k derived through Denition 3/Step 2. Although each segment qi is linear, its projection qp i onto CN ; according to Denition 3, is a polyline following the local curvature of the cloud surface. To illustrate this effect, we consider the cloud of points shown in Fig. 6. The three vertices shown in Fig. 6a dene a two-segment polyline which clearly is far from being on (in any possible sense) the cloud surface. Fig. 6b depicts the projection of this polyline onto the cloud, according to Denition 3, which follows the local curvature of the given cloud surface. In the following discussion, the polylines designed by the user will be called design polylines or d-polylines, not to be confused with projected polylines or p-polylines. We will also use the terms d-segments and p-segments for userdened and projected line-segments, respectively. An industrial example for the introduced 3D polyline design method is presented in Fig. 7: in footwear industry, the designers make several sketches onto the surface of a last. These sketches correspond to the basic style lines of the shoe design which are eventually utilized in the pattern engineering process. In Fig. 7a the style lines of a shoe are designed using d-polylines which are then projected onto the last as in Fig. 7b. The projected design in Fig. 7b lies onto the cloud surface as it is apparent near the surface silhouette. The wrinkling effect. Taking a closer look at the p-polylines of Figs. 6b and 7b, one is able to trace certain

u [ 0; 1

Then, the projection of qi onto CN is the curve qp i u dened as follows: each point qi u is equipped with the projection vector ni u 1 2 uni uni1 ; u [ 0; 1; and is projected onto CN according to Denition 1. Denition 3 (Line-segment projection: approximate construction). Given a cloud of points CN and two vertices ^ i k pi ; n i l ; p ^ i1 kpi1 ; ni1 l; the line-segment qi is p dened with end-points the projected (onto CN ) vertices p pp i and pi1
p qi u 1 2 upp i upi1 ;

u [ 0; 1

Then, the projection of qi onto CN is the curve qp i dened by the following procedure:
p p (1) Initialization: qp i {pi pi1 } (2) For each line-segment in qp i which is not labelled as terminal, project its midpoint and replace it with the two new line-segments.

Fig. 6. The projection of d-polylines onto a cloud of points. (a) Initial d-polyline. (b) Final p-polyline.

118

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

Fig. 7. (a) A basic shoe design sketched onto the cloud surface of a last N 6000 utilizing d-polylines. (b) The projection of polylines onto the cloud surface (p-polylines).

wrinkles in some of them; see, e.g. the girth line in the shoe design of Fig. 7b, located in the forepart of the last. This wrinkling is a direct result of the 3D nature of the polyline projection-problem and of the fact that different parts of a p-polyline are affected by different cloud points. Thus, one faces the problem of smoothing p-polylines, which is a direct extension to 3D of the standard 2D polyline smoothing problem [14]. This is exactly the subject of the following sub-section. 3.2. Smoothing projected segments The projection of a line segment qi onto a cloud of points transforms qi into a polyline qp i : Since this transformation is performed by taking into account solely the minimization of Eq. (1), random local variations may occur in qp i ; which, in turn, cause the wrinkling effect described in Section 3.1. One way to construct a smoothed projection of qi onto CN is to incorporate into the projection process the constraint that the length of the resulted p-polyline qp i must be minimized. In this way, it is possible to reduce the wrinkling effect by stretching the produced p-polyline. Similar approaches have been adopted by other researchers to solve related modelling problems: Felderman [14] deals with 2D polyline fairing and proposes a procedure adjusting vertices, within a given tolerance, so that the total length of the polyline is minimized. Furthermore, the discrete-curvature notion is used by others to fair pointsets in two or three-dimensions [12,22]. None of the published works addresses the problem of smoothing a polyline drawn onto a point cloud. This problem is studied and solved below. In view of Denition 3 and Note 2, there are two ways to enhance the projection method of Denition 3 towards an algorithm that also smoothes the projection: Smoothing methodology A: Incorporate a smoothing method into Denition 3. This approach is not efcient

(our experiments have conrmed this) as Denition 3 calculates the projected vertices sequentially, thus one can only employ a local smoothing technique optimizing the location of a specic projected vertex in relation to those already calculated. Smoothing methodology B: Simultaneously projecting and smoothing a discretization of a line segment. With respect to Note 2, we conclude to an alternative denition for a smooth projection: Denition 4 (Smooth projection). Given a line segment qi ^ i;k kpi;k ; ni;k llk 0; ; ki 2 1} ^ i {p represented by a set p of ki distinct nodes pi;k ; the smooth projection of qi onto p CN is a p-polyline qp i {pi;k } minimizing the energy function Ei 1 2 gPi gLi ; where Pi and Li
k i22 X k0 2 p k pp i ; k 2 pi ; k 1 k k i21 X k1

g [ 0; 1 ;

13

E pp i;k

14

15

expresses the length of the p-segment qp i:

1 2 gI gAt 1 2 gb gc;

16

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

119

i.e. t tg 1 2 gI gA21 1 2 gb gc 17

which is a second-degree vector equation with respect to g: A is a ki 2 2 ki 2 2 tridiagonal and symmetric matrix. The three non-zero elements of the kth row of A are Ak;k21 2ni;k21 ni;k A k ;k 2 ; for k 2; ; ki 2 3; 18 Ak;k1 2ni;k ni;k1 With A1;1 2; A1;2 2ni;1 ni;2 Aki22;ki23 2ni;k22 ni;k23 Aki22;ki22 2 The kth element of vector c is given by ck pi;k21 2 pi;k ni;k pi;k 2 pi;k1 ni;k ; for k 1; ; ki 2 1 While the kth element of vector b is 20 19

l 2 pi;k ni;k bk k ; kni;k k2

for k 1; ; ki 2 1;

21

Fig. 8. The proposed algorithm for the smooth projection of a segment qi onto a cloud of points.

lk

x 2 y 3 z c1 i;k ni;k ci;k ni;k ci;k ni;k c0 i ;k

results. In practical applications, selection of g is based on a trial-and-error approach where the user interactively selects g via an appropriate user interface tool. 3.3. Designing digital splines onto clouds of points Although polylines are quite exible and relatively easy to construct, designers also need smooth curves which, in current CAD systems, are modelled as splines of low degree. With current CAD technology, tracing curves on polynomial surfaces is not a straightforward operation as the user or the CAD system has to ensure that the designed curve will not overshoot the given surface. Below, it is

1 2 3 and the scalars c0 i;k ; ci;k ; ci;k ; ci;k are dened by Eq. (4) for ^ each pi;k ; and I is the ki 2 2 ki 2 2 identity matrix. A smoother projected polyline, with larger deviation from the cloud of points, will be produced by a large g than the one corresponding to a small g: For g 0; one obtains a highly accurate projection but, most probably, with the wrinkling effect shown in Figs. 1b, 6b and 7b. For g 1; the result is a straight line segment connecting the two boundary vertices pi;0 and pi;ki21 ; see Fig. 6a. Fig. 8 presents the pseudo-code implementation of the above smooth projection method. The procedure SmoothSegProjection computes the related matrices and vectors using Eqs. (18) (21). We use LU decomposition and a fast forward/backward substitution (: an Oki process), to compute the solution (17). This directly produces the p spatial position of the nodes pp i;k of the p-polyline qi : Fig. 9 shows the result of applying the aforementioned procedure to the polylines of the basic shoe design of Fig. 7. Notice the signicant improvement in the shoe girth polyline which now is quite smooth, i.e. free of undesirable wrinkles. The same holds for all polylines in this shoe design. For the majority of our experiments we have used g 0:5 which corresponds to an acceptable compromise between smoothness and accuracy. One may wish to ne-tune g to further improve the obtained

Fig. 9. The smooth projection of d-polylines onto the cloud surface of a last g 0:5:

120

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

Fig. 10. Two approaches to construct digital curves onto a cloud surface. The initial d-polylines have been replaced by pointsets derived from the original cubic B-splines. (a) Digital curves designed onto the cloud surface without smoothing j 3: (b) Smooth Digital Curves designed onto the cloud surface (j 3; g 0:5).

established that curve design on point clouds is not as complicated as its counterpart in standard continuous CAD systems. Our approach for designing polynomial-spline curves onto cloud surfaces uses an interpolation method [27, Section 9.3.4] to construct a smooth spline of j-degree pj u interpolating user-dened vertices of a d-polyline. Using the same scheme, it is also possible to calculate the ^ j of corresponding projection direction nj u: A node-set p j distinct nodes is derived from p u which is eventually projected onto the cloud surface. The nal result is a polyline tracing a smooth trajectory onto the cloud of points. The discretization of pj u can be achieved using the method in Ref. [35], which ensures that the topology of the resulting linear approximation is consistent with that of the initial curve. ^ j onto the cloud of points is a straightforward Projecting p application of either the PointProjection or the SmoothSegProjection algorithm provided that at least the two ^ j are xed. Two alternative boundary vertices of p denitions for a digital curve are proposed: Denition 5 (Digital curve). A digital curve is dened as ^ j onto CN the result of the projection of the node-set p according to Denition 1. Denition 6 (Smooth digital curve). A smooth digital curve is dened as the result of the smooth projection of the ^ j onto CN according to Denition 4. node-set p An example of designing digital curves is shown in Fig. 10a. The wrinkling effect is present again especially in the girth curve in the forepart of the shoe last. This problem is resolved utilizing smooth digital curves with very satisfactory results as shown in Fig. 10b (see also Fig. 1c).

Fig. 11. Application of the proposed methods for designing wearing apparel in a human body cloud surface.

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122

121

The lines of the shoe design are smooth and lie onto the cloud surface. Similar results have been obtained for many other design scenarios, which provide ample justication for the effectiveness of the proposed digital curve designmethod. As far as execution time is concerned, the total computational time for constructing all the digital curves in Fig. 10b did not exceed 0.3 s, demonstrating also the methods efciency.

the European Commission). This data set was scanned at the Hohenstein Institute with a Human Solutions Vitus-Smart Scanner.

References
[1] Azariadis P. Parameterization of clouds of unorganized points using dynamic base surfaces. Comput-Aided Des 2004;36(7):60723. rder P, Hoppe H, editors. [2] Adamson A, Alexa M. In: Kobbelt L, Scho Approximating and intersecting surfaces from points, in eurographics symposium on geometry processing. 2003. p. 230 9. [3] Alexa M, Behr J, Cohen-Or D, Fleishman S, Levin D, Silva C. Computing and rendering point set surfaces. IEEE TVCG 2003;9(1): 315. [4] Amenta N, Bern M, Kamvysselis M. A new Voronoi-based surface reconstruction algorithm. In: Proceedings of the SIGGRAPH 98, Computer Graphics Proceedings, Annual Conference Series; 1998. p. 415 22. [5] Jean-Daniel B, Frederic C. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Comput Geom 2000; 22332. s G, Va rady T, Andor L, Martin R. Constrained tting P, Ko [6] Benko in reverse engineering. Comput Aided Geom Des 2002;19(3): 173205. rady T. Segmentation methods for smooth point regions P, Va [7] Benko of conventional engineering objects. Comput-Aided Des 2004;36(6): 51123. onning R, Mu ller H. Interactive sculpturing and visualization of [8] Bo unbounded voxel volumes. Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications; 2002. p. 2129. [9] Benouamer M, Michelucci D. Bridging the gap between CSG and Brep via a triple ray representation. Proceedings of the Fourth ACM Symposium on Solid Modeling and Applications; 1997. p. 68-79. [10] Cripps R. Algorithms to support point-based cadcam. Int J Mach Tools Manufact 2003;43(4):42532. [11] Corbo P, Germani M, Mandorli F. Aesthetic and functional analysis for product model validation in reverse engineering applications. Comput-Aided Des 2004;36(1):65 74. [12] Eck M, Jaspert R. In: Sapidis N, editor. Automatic fairing of point sets, designing fair curves and surfaces: shape quality in geometric modelling and computer-aided design. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); 1994. p. 45 60. [13] Erikson C, Manocha D. GAPS: general and automatic polygonal simplication. Seventh ACM Symposium on Solid Modelling and Applications, Tutorial T4: Handling Large Geometric Datasets; 2002. [14] Felderman M. In: Sapidis N, editor. Tight string method to fair piecewise linear curves, designing fair curves and surfaces: shape quality in geometric modelling and computer-aided design. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); 1994. p. 6172. th I, Rusa k Z. Collaborative virtual design environments: [15] Horva collaborative shape conceptualization in virtual design environments. Commun ACM 2001;44(12):59 63. [16] Jerard R, Angleton J, Drysdale R, Su P. The use of surface points sets for generation, simulation, verication and automatic correction of NC machining programs. Proceedings of the NSF Design and Manufacturing Systems Conference, Tempe, AZ, Society of Manufacturing Engineers; 1990. p. 1438. [17] Jansson J, Vergeest J. A discrete mechanics model for deformable bodies. Comput-Aided Des 2002;34(12):913 28. [18] Kobbelt L, Schroder P. A multiresolution framework for variational subdivision. ACM Trans Graph 1998;17:20937. [19] Lee I. Curve reconstruction from unorganized points. Comput Aided Geom Des 2000;17(2):16177.

4. Discussion conclusions Using digital surfaces, dened by clouds of points, as a primary CAD-model is an increasing trend in the ComputerAided Design and Graphics communities, caused primarily by the availability of powerful desktop systems able to swiftly process hundredths of thousands of points. This requires development of appropriate tools for designing with these new models, including digital curve-drawing which is the subject of this paper. Currently, the proposed techniques have been successfully implemented in a prototype CAD system for footwear design, developed by ELKEDETechnology and Design Centre. Further, preliminary experiments have been conducted regarding application of the present curve-design methods to garment design, and the results have been satisfactory. Such an example is shown in Fig. 11, where a t-shirt is sketched onto the cloud surface of a human body. There are a lot of issues that should be further investigated in relation to the proposed tools for curve design. One approach is to search for more accurate or faster point projection methods and/or better weight functions. Another point for future research is the derivation of smoothing functionals for resolving the wrinkling effect, which will be based on minimizing discrete curvature. Our future research will also be focus on integrating the proposed design tools with variational subdivision schemes [18]. These curve/surface models seem appropriate for point-based CAD since they are based on the methodology used also here: computing pointsets by minimizing energy functionals (Denitions).

Acknowledgements The authors wish to express their sincere appreciation to the Editor John Woodwark and three anonymous referees, whose comments signicantly improved this paper. Part of this research has been conducted in the R and D Department of the Research Centre ELKEDETechnology and Design Centre (www.elkede.gr) for the development of a footwear CAD system. The human body data-set of Fig. 11 was offered by Athens Technology Centre SA and originated in the European Anthropometric Database (Pilot Sizing Survey data/E-Tailor project, IST-1999-10549, funded by

122

P.N. Azariadis, N.S. Sapidis / Computer-Aided Design 37 (2005) 109122 [40] Zwicker M, Pauly M, Knoll O, Gross M. Pointshop 3D: an interactive system for point-based surface editing. ACM Trans Graph 2002; 21(3):3229. Special issue: Proceedings of ACM SIGGRAPH.

[20] Llamas I, Kim B, Gargus J, Rossignac J, Shaw C. Twister: a spacewarp operator for the two-handed editing of 3D shapes. ACM Trans Graph 2003;22(3):6638. [21] Liu G, Wong Y, Zhang Y, Loh H. Error-based segmentation of cloud data for direct rapid prototyping. Comput-Aided Des 2002;35(7): 63345. [22] Liu GH, Wong YS, Zhang YF, Loh HT. Adaptive fairing of digitized point data with discrete curvature. Comput-Aided Des 2002;34(4): 30920. [23] McLaughlin W. Describing the surface: algorithms for geometric modelling. Comput Mech Eng 1986;38 41. [24] Menon J, Marisa R, Zagajac J. More powerful solid modeling through ray representations. IEEE Comput Graph Appl 1994;14(3):2235. [25] Muller H, Surmann T, Stautner M, Albersmann F, Weinert K. Online sculpting and visualization of multi-dexel volumes. Proceedings of the Eighth Symposium on Solid Modeling and Applications 2003; 25861. [26] Pottmann H, Randrup T. Rotational and helical surface approximation for reverse engineering. Computing 1998;60(4):30722. [27] Piegl L, Tiller W. The NURBS book. Berlin: Springer; 1997. [28] Qin S, Harrison R, West A, Jordanov I, Wright D. A framework of web-based conceptual design. Comput Ind 2003;50(2):153 64. th I, Kuczogi G, Akar E. Shape instance generation [29] Rusak Z, Horva from domain distributed vague models. Proceedings of the DETC 02 ASME Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Montreal; 2002. [30] Schweikardt E, Gross M. Digital clay: deriving digital models from freehand sketches. Automat Construct 2000;9(1):10715. th I, Spanjaard S. A methodology for reusing [31] Vergeest J, Horva freeform shape content. Proceedings of the Design Theory and Methodology Conference, DETC01/DTM-21708, New York: ASME; 2001. rady T, Martin RR, Cox J. Reverse engineering of geometric [32] Va modelsan introduction. Comput-Aided Des 1997;29(4):25568. rady T. Advanced surface tting [33] Weiss V, Andor L, Renner G, Va techniques. Comput Aided Geom Des 2002;19(1):1942. [34] Woo H, Kang E, Wang S, Lee K. A new segmentation method for point cloud data. Int J Mach Tools Manufact 2002;42(2): 16778. [35] Cho W, Takashi M, Nicholas PM. Topologically reliable approxi zier curves. Comput Aided Geom Des 1996; mation of composite Be 13(6):497 520. [36] Wu D, Sarma R. The incremental editing of faceted models in an integrated design environment. Comput-Aided Des 2004; in press. [37] Wu Y, Wong Y, Loh H, Zhang Y. Modelling cloud data using an adaptive slicing approach. Comput-Aided Des 2004;36(3):231 40. [38] Yin Z. Reverse engineering of a NURBS surface from digitized points subject to boundary conditions. Comput Graph 2004;28(2):20712. [39] Yin Z, Jiang S. Automatic segmentation and approximation of digitized points for reverse engineering. Int J Product Res 2003; 41(13):3045 58.

Phillip N. Azariadis holds a mathematics degree from the Department of Mathematics (19901994) and a PhD from the Mechanical Engineering and Aeronautics Department (19951999) of the University of Patras, Greece. Currently he is Director of the Research & Technology Department of the Greek research centre ELKEDETechnology and Design Centre SA and also an instructor at the Department of Product and Systems Design Engineering of the University of the Aegean. His background and research activities are focused in the areas of Computer-Aided Design and Manufacture, Reverse Engineering, Computer Graphics and Robotics. His work has been published in leading international scientic journals and conference proceedings. He has participated in various research projects funded by EC or national bodies. Nickolas S. Sapidis is currently an Associate Professor with the Department of Product and Systems Design Engineering of the University of the Aegean. He holds degrees in Naval Architecture & Marine Engineering, Applied Mathematics and Mechanical Engineering. He received his PhD in Mechanical and Aerospace Sciences from the University of Rochester in 1993. He has taught at the Hellenic Air Force Academy, the National Technical University of Athens (NTUA), the University of Athens and the Polytechnic University of Catalunya (Spain). Also, he has been providing education/training services to major Greek corporations like Elefsis Shipyards and the Bank of Greece. His industrial experience, on CAD/CAE research/development/application, includes General Motors R&D Center and GM Design Center (USA) as well as Marine Technology Development Co (Greece). For six years, he was a researcher with NTUA Ship-Design Laboratory where he led research activities of an Autodesk Educational Software Development Team. Sapidis is the author of more than 40 papers on curve and surface modeling/fairing/visualization, discrete solid models, nite-element meshing, reverse engineering of surfaces, and recently on solid modeling of design constraints. His research has been implemented in industrial CAD/CAE systems by MIT, GM, Intergraph and KCS (now Tribon Solutions). He has edited two books, guest-edited three journal special-issues and served on 10 conference program-committees. N. Sapidis is on the Advisory Editorial Board of CAD and of the International Journal of Product Development (IJPD).