An approach towards offsetting of object in non-manifold 3-D geometric modeling.

Tiwari, Amod ; Chatterjee, A. ; Pandey, A. 等

Introduction

While NURBS is de facto standard for exact curve and surface, triangular mesh (T-mesh for short) is probably the most popular choice for approximate shape representation in many engineering applications including FE analysis, tool path generation, and reverse engineering, as well as computer graphics and approximate shape representation in many engineering applications, Tiller [15]. It is often required to offset a T-mesh that consists of two major steps:

Raw offsetting

Raw offsetting is to obtain a T-mesh apart from the original mesh by the given distance and the resulting mesh may have regenerated into triangles.

Regularization

Regularization is the step to remove those abnormalities. We obtain a regular T-mesh, which is a 2-D manifold triangular mesh free from regenerated triangles. Computing offset model of a shape represented by a T-mesh can be used for tool path generation and process planning of a sculptured surface such as mold & die, Choi [7]. Geometric operation between T-meshes [8] is very similar to T-mesh regularization as it finds segmentation between T-meshes and selectively collects portions as specified by the Cartesian operators. Hence, the algorithm described in this paper can be applied to geometric operation between T-meshes. The primary advantage is that in geometric operation problem the triangle set is already separated into two groups that make the segmentation search easier.

Related work

Several researchers have developed strategies for offsetting of planar environments. Offsetting modeling technology has significantly outgrown its original scope of computer-aided mechanical design and manufacturing automation. It plays an important role in many domains like medical imaging and therapy planning, architecture and construction, digital video-production for entertainment and advertising Arnold [1].

Although no publications on three-dimensional non-manifold offsetting were found in journals Lee [3], much research on offsetting operations on solids and sheets has been made and published, Masuda [4]. Since offsetting operations on nonmanifold objects encompass those on solids, sheets and wire frames, previous works on solid and sheet offsetting will be reviewed as related work instead.

Solid modeling theory and technology are becoming increasingly well understood, and their commercial and industrial exploitation is progressing rapidly Requicha [11], Voelcker [12].However, the range of operations on solids supported by current modelers are very limited. Typically, solids represented in a modeler can be transformed by rigid motions which are straightforward and well known in computer graphics, Newman [13], Dam [14], and can be combined by Boolean operations, which are complex but important.

Many researchers already proposed a 3D curve offsetting methods Shin [16] which has a wide variety of applications and seems to be a natural extension of 2D curve offsetting. However, there is no commonly accepted definition of 3D curve offsetting and fundamental operation in geometric modeling.

Objective

Research related with offsetting has been carried out for over three hundred years and it may be classified into two main categories

(i) Offset geometry

(ii) Offset topology

The area of offset geometry deals with the exact or approximate methods for generating offset curves and surfaces, which are well surveyed by Pham's [5]. The area of offset topology deals with the development of topological operations for generating offset solids or converting sheets into solids in geometric modeling systems.

The purpose of this work is to develop a generic algorithm, to do an offset between planners and spherical 3D objects through segmentation and non-manifold operations with the help of 3D coordinate geometry.

Methodology

Offsetting operations like adding or removing a uniform thickness from a given object. To offset an object X, on to object Y, by distance r. In such case, all interior points of X coaxially overlap on Y within a distance r (positive offsetting) and vice versa.

Offsetting operations can be applied not only to solid models but also to sheet or wire frame models. Here, a sheet model is defined as a degenerated solid model with zero thickness and thus it looks like a generalized surface model that allows an edge to be adjured to more than two faces. Potential applications of offsetting operations cover a wide range. Wire frame offsetting can be used to generate sheet or solid models for pipelines of plants or ships. Sheet offsetting has been used to generate solid models for plastic or sheet metal parts with thin and uniform thickness efficiently, Chan [9]. Solid offsetting has been used for tolerance analysis, clearance testing, NC and CNC tool path generation, planning collision-free paths for robots, Kaul [2], constant-radius rounding and filleting and so on Rossignac [6].

[FIGURE 1 OMITTED]

After surveying the offsetting area of an object to get the altitudes and coordinates of both objects with respect to initial line (x-axis). It is needed to scale the boundary Dimension Cosine (BDC) with respect to altitude.

If Boundary Dimension Cosine (BDC) of both objects are not equal then one need to correct the position of altitude. This process continues until BDC of both objects become equal. During the segmentation, it is necessary that the sum of Boundary Direction Cosine (BDC) should be unity [L.sup.2] + [M.sup.2] + [N.sup.2] = 1. After computation of surface (target) coordinates and Boundary Dimension Cosine (BDC), we get required segmented area.

However, it is necessary that center and origin will be fixed of both objects. We may provide slope to the object to change the Boundary Dimension Cosine (BDC) with respect to centre. Coordinate scaling may be arbitrary according to the outer surface of an object.

Segmentation

Segmentation is a technique to break a solid structure into a number of equal or unequal sizes. In this paper, we discuss segmentation method uses three angles [alpha], [beta], [gamma] to control the surface area, boundary angle through (Cos[alpha], Cos[beta], and Cos[gamma]) and Boundary Direction Cosine (BDC). BDC defines following properties.

(1) Cos [alpha] Control the horizontal surface area through the normal from the centre.

(2) Cos [beta] Control the vertical height of the normal from centre of object.

(3) Cos [gamma] Control the slant height from the centre of object.

Segmentation can be used as a part of surface offsetting in that the segmented regions are often described in terms of surfaces. In addition, where there are unwanted objects, segmentation provides a means to remove them. In the case of modeling mining surfaces, it is a requirement to remove extraneous data such as mining equipment. Two different approaches to segmentation may be considered, namely, edge-based and face-based methods, Arnold [1]. Edge-based segmentations rely on edges found in an object by edge detecting operators. The most common problems of edge-based segmentation is noise, also it has been observed that other problem happens where an edge is presence but no border and vice-versa.

It is suggested that to detect the edge coordinates of a hemisphere through edge-based method and generate Boundary Dimension Cosine (BDC) with respect to planner surface object (cubide). During this process, unrepresented boundary or extra surface automatically is segmented.

[FIGURE 1.5 OMITTED]

In figure (1.5) a cube and a cylinder, the cube contains plane surface (MN) and the cylinder contains radial surface (PQ). To measure the length PQ and NM, if (PQ = MN) then measure the circumference distance of cylinder which we need for offsetting. This radial shape self- segments in form of plane surface object (cube).

Centre of curvature

Let P be the point (x, y, z) and Q the point (x + h, y + k, z + w). Let the centre of curvature for P, Q, S be ([alpha], [beta], [gamma]) respectively.

The normal at P is (Y - y) [phi] Where [phi](x) stand for dy/dx (1)

The normal at Q is (Y - y - k) [phi] (x+h) + X - x -h = 0 (2)

The normal at (Y - y - k) [phi] (z+w) + (Z - z - w) = 0 (3)

[FIGURE 1.1 OMITTED]

To find the coordinate of the point of intersection of these normals, subtract (1) from (2). We have (Y - y) {[phi] (x+h) + [phi](x)} - k [phi] (x + h) - h = 0 (4)

Dividing by, h [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

Now as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

Hence, we obtain on taking limits [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] are centre of curvature.

For this, we can get [(x- [alpha]).sup.2] + [(y - [beta]).sup.2] + [(z - [gamma]).sup.2] = [[rho].sup.2] where ? is the radius of sphere.

Chord of Curvature of spherical object

When we get planner and spherical two objects for offsetting through self-segmentation and non-manifold operation, the chord of curvature of spherical object is an important aspect. First, we calculate boundary edge of planner surface about x, y, z-axis then after calculate chord of curvature of spherical surface. For the good offsetting, it is the state, that the chord of curvature should be equal to the boundary edge of planner surface. We know that the greatest chord of sphere is known as diameter.

[FIGURE 1.2a OMITTED]

[FIGURE 1.2b OMITTED]

In figure, 1.2(a) is self-segmented hemisphere in cube and figure 1.2(b) is self-segmented cone in cube. If we plot segmentation graph between spherical and planner (cube) two object figure (1.3) then a spherical object show cycle graph and planner object show a linear graph. Cyclic curve as a spherical object and straight line show a plane surface object.

[FIGURE 1.3 OMITTED]

Chords of Curvature Parallel to the Co-ordinate Axis Let C be the centre of curvature at any point P on the given curve and RP is the diameter of sphere PQRS. If [rho] be the radius of curvature at P, then CP = [rho] and so PR = 2 [rho]. Let PQ and PS be the chords of curvature parallel to the axes of x and y respectively. If [psi] is the angle, which the tangent at P makes which the x-axis, then from the right-angled triangle PQR, we have

PQ = PRSin[psi] = 2 [rho]Sin[psi]

Similarly PS = QR = PRCos[psi] = 2 [rho]Cos[psi]

[FIGURE 1.4 OMITTED]

[FIGURE 1.6 OMITTED]

Chord of Curvature through the Pole (or Origin):

Let C is the centre of Curvature and P is a point such that on the given curve, RP is the diameter of sphere PQRS. Then CP = [rho] and RP = 2[rho]. Join OP to meet the sphere of curvature in Q. Clearly, PQ is the chord of curvature through the pole (or Origin).

If [phi] be the angle between the radius vector OP and the tangent PT then from the right angled triangle PQR, [angle]PQR = [phi], we have PQ = RP Sin[phi] i.e. PQ = 2 [rho]Sin[phi]

Chord of Curvature Perpendicular to the Radius Vector: In above figure (1.6) PS is the chord of curvature perpendicular to the radius vector. in triangle QRP and triangle RPS there for [angle]PSR = [angle]PSR = [pi]/2 We have PS = QR = RP Cos [phi] and P S = 2 [rho] C os [psi]

Algorithm

We want to compute the shortest distance between two points measured on the surfaces. A path of shortest distance connecting two point as geometric curve and the arc length of that curve are called geometric distance between two points. The object must be 3D or 2.5D. In figure (1.7 & 1.8) a Hemisphere and Cubide are three dimensionally oriented, having their initial coordinate X, Y, Z and projected coordinates are ([X.sub.1],[Y.sub.1],[Z.sub.1]),([X.sub.2],[Y.sub.2],[Z.sub.2]) respectively. The Direction Cosine (Cosine angle) of first object (hemisphere) about axis of x, about axis of y, about axis of z respectively are Cos ([[alpha].sub.1]) = [L.sub.1]; Cos ([[alpha].sub.2]) = [M.sub.1]; Cos ([[alpha].sub.3]) = [N.sub.1]. Direction Cosine (Cosine angle) of second object about axis of x, about axis of y, about axis of z respectively are Cos ([[beta].sub.]1) = [L.sub.2]; Cos ([[beta].sub.2]) = [M.sub.2]; Cos ([[beta].sub.3]) = [N.sub.2].

At first, the purpose of algorithm automatically identifies the shortest distance and then to merge one object into second object.

Therefore we will input arbitrary variable value in place of ([X.sub.1], [Y.sub.1], [Z.sub.1]), ([X.sub.2], [Y.sub.2], [Z.sub.2]) and merge one object on second object in arbitrary position.

X - [X.sub.1]/[x.sub.1] - [x.sub.2] = Y - [y.sub.1]/ [y.sub.2] - [y.sub.1] = Z - [z.sub.1]/[z.sub.2] - [z.sub.1] (7)

X - [X.sub.2]/[x.sub.2] - [x.sub.1] = Y - [y.sub.2]/ [y.sub.2] - [y.sub.1] = Z - [z.sub.1]/[z.sub.2] - [z.sub.1] (8)

Now [L.sub.1], [M.sub.1], [N.sub.1] and [L.sub.2], [M.sub.2], [N.sub.2] are the direction cosines of object PQ and RS respectively and T1T2 is the shortest distance. A, B, C are the direction ratio between two objects.

From the definition of direction ratio [x.sub.2] - [x.sub.1] = L, [y.sub.2] - [y.sub.1] = M, [z.sub.2] - [z.sub.1] = N

X - [X.sub.2]/L = Y - [y.sub.1]/ M = Z - [z.sub.1]/N (9)

X - [X.sub.2]/L = Y - [y.sub.2]/ M = Z - [z.sub.2]/N (10)

[FIGURE 1.7 OMITTED]

[FIGURE 1.8 OMITTED]

We have seen various types of offsetting betweens Planner-to-Planner, Radial-to-Radial surfaces etc. However, we are discussing a different type of offsetting between Radial-to-Planner surfaces. In figure (1.7), a hemisphere gets radially outer surface and in figure (1.8), a cubide gets planner outer surface. However, both objects are having deferent type direction cosines (Dcs) and direction ratios (Drs). In these type surfaces, we need self-intersection segmentation for removing odd boundary of a hemisphere.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (12)

[FIGURE 1.9 OMITTED]

If both objects Orthogonal to each other then applying condition Orthogonal and put ([theta] = [PHI] =[pi]/2) put in equation number (12) and we gets

L [L.sub.1] + M[M.sub.1] +N[N.sub.1] = 0 (13)

And

L [L.sub.2] + M[M.sub.2] +N[N.sub.2] = 0 (14)

Solving equation (11) and equation (12) with the help of Cross Multiplication method, we get direction cosines of distance T1T2

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (15)

Now if we consider

([M.sub.1][N.sub.2]--[M.sub.2][N.sub.1]) = [K.sub.1] (16)

([L.sub.2][N.sub.1]--[N.sub.2][L.sub.1]) = [K.sub.2] (17)

([L.sub.1][M.sub.2]--[M.sub.2][L.sub.1]) = [K.sub.3] (18)

[K.sub.1], [K.sub.2], [K.sub.3] are arbitrary variable to make for easy calculation.

Find the actual direction cosine between hemisphere and cubide.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (19)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (20)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (21)

Now projection of object PQ on RS

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (22)

[FIGURE 2 OMITTED]

Now equation of an offsetting object

P(x, y, z) =   X-[X.sub.1]   Y-[Y.sub.1]   Z-[Z.sub.1] (23)
               [L.sub.1]     [M.sub.1]     [N.sub.1]
               [L.sub.2]     [M.sub.2]     [N.sub.2]

Or

P(x, y, z) =   X-[X.sub.2]   Y-[Y.sub.2]   Z-[Z.sub.2] (24)
               [L.sub.2]     [M.sub.2]     [N.sub.2]
               [L.sub.3]     [M.sub.3]     [N.sub.3]

Tangents between objects

During segmentation, different asymptotes (tangent) generate different angle from origin about axis of X, Y, Z respectively Wan [10]. By this cause, each of asymptotes creates at least one normal. Some normals pass through centre and design triangles SHK figure (2.1). Chord HK bisect [angle]OHS and [angle]OKS however [angle]OHS = [rho]/2 = [angle]OKS In addition, HS is the [perpendicular to] on tangent O[P.sub.1] similar KS is the [perpendicular to] on tangent O[P.sub.2]. Each tangent contains angle [alpha], [beta], [gamma] from origin and centre. Equation of sphere [(x - [alpha]).sup.2] + [(y - [beta]]).sup.2] + [(z - [gamma]]).sup.2] [[rho].sup.2], with centre at [alpha], [beta], [gamma] and radius [rho]. if Boundary Direction Cosine (BDC) of normal are L, M, N then [L.sup.2] + [M.sup.2] + [N.sup.2] =1 Equation of Planer surface

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (25)

We know that if any plane touches any spherical surface then perpendicular distance from the centre of spherical object onto the plane object is equal to the radius of spherical object.

Hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (26)

Where [D.sub.i] P is the [perpendicular to] distance from centre of spherical object and [rho] the radius of spherical object.

[FIGURE 2.1a OMITTED]

[FIGURE 2.1b OMITTED]

There for [D.sub.i] (P) = [rho] (27)

Algorithm Procedure

Step 1: In the above algorithm, first conceder the position of origin coordinate points (X=0, Y=0, Z=0) of the given objects.

Step 2: Fix the coordinate of consider object {equation (1)} and in put the arbitrary value in equation (2) as second object.

Step 3: Input value of coordinate point {equation number (2)} will be in decreasing order, for the merge of second object into first.

Step 4: The input values of angle should lie between (0< [theta] [less than or equal to] [pi]/2) and (0< [PHI] [less than or equal to] [pi]/2) equation number (5, 6).

Step 5: Find the direction angle (Direction cosine) from equation number (7 & 8). It is must that direction cosine should be directly proportional to direction ratio.

Step 6: The above proportional condition depends on input parameter (as a coordinates point).

Step 7: Now finds the projection on fixed object figure (2) of variable object figure (3) from equation number (16).

Step 8: When the second object is projected on first object figure (6), and then find the combined equation of merged object from equation number (17 & 18).

Step 9: Graph plot between two-offseted object. It would be straight line because during the perfect offsetting Boundary Direction Cosine of both objects equal

[FIGURE 2.2c OMITTED]

Result

In this paper, an attempt is made of designing a new algorithm for segmentation and offsetting. In this work, we have seen that segmentation can be more flexible by applying coordinate geometry. We make equal BDC of both objects and create parallel surface figure (2.3a). By this algorithm, we have provided a valuable offsetting between radial and planner surface figure (2.3b).

[FIGURE 2.3a OMITTED]

[FIGURE 2.3b OMITTED]

Conclusion

This algorithm proposed here has defined the segmentation without performing local and global iteration. We may segment the raw offset mesh model into a several areas. Non-manifold operations provide flexible offset. Now if we compute the segmentation pattern between these areas, it might be possible to reduce the number of iteration and gap between two objects of interior and exterior boundaries.

Segmentation and offsetting techniques are two different methods. To the best of our knowledge, the combination of these two methods and application of its mathematical definition is a new area of study. This type of research work has not been under-taken in either of the fields. Segmentation and offsetting have their own mathematical definition but our work has brought them together under a common generic algorithm.

References

[1] Aaron Greenfield, David C. Conner "Hierarchical Segmentation of Surfaces Embedded in R3 for Auto-Body Painting" Carnegie Mellon University, Pittsburgh PA 15213, USA

[2] Kaul, A., "Murkowski Sums: A Simulation Tool for CAD/CAM", Computers in Engineering, Vol. 1, pp. 447-456, ASME, 1992

[3] Lee, S. H. "Offsetting Operations on Non-manifold Boundary Representation Models With Simple Geometry" ACM, 9-11 June (1999) New York USA.

[4] Masuda, H., "Topological operators and Boolean operations for complex-based non-manifold geometric models," Computer Aided Design, Vol. 25, No. 2, pp. 119-129, 1993.

[5] Pham, B., "Offset Curves and Surfaces: a Brief Survey", Computer-Aided Design, Vol. 24, No. 4, pp. 223-229, April 1992.

[6] Rossignac, J. R. and Requicha, A. A. E., "Offsetting Operations in Solid Modeling," Computer Aided Geometric Design, Vol. 3, pp. 129-148, 1986.

[7] Choi, B.K., Kim, D.H. and Jerard, R.B., C-space approach to tool-path generation for die and mould machining, Computer-Aided Design, Vol.29, No.9, 1997, pp 657-669

[8] Cardan, Y. and Perrin, E., An algorithm reducing 3D Boolean operations to a 2D problem: concepts and results, Computer-Aided Design, Vol. 28, No.4, 1996, pp 277~287

[9] Lau, R. W.H., Chan, O., Luk, M., Li, F. W.B., A Collision Detection Framework for Deformable Objects, ACM VRST'02, November 11-13, 2002

[10] Wan C. Tang and Y. Leonard Chow "Inverse of Exact Solution by Synthetic Asymptote--An Example of Stripline" IEEE MICROWAVE AND GUIDED WAVE LETTERS, VOL. 10, NO. 11, NOVEMBER 2000

[11] Yong Tsui Lee, Aristides A. G. Requicha University of Rochester "Algorithms for computing the volume and other integral properties of solids. Volume 25, ISSN: 0001-0782 (Sep-1982).

[12] Requicha A.A.G. and Voelcker H.B. "Solid modeling: current status and research directions, IEEE Computer Graphics and Applications, (1983).

[13] Newman W.M. and Sproull R.F., Principles of interactive Computer Graphics, McGraw-Hill, (1979) New York

[14] Foley J.D. and Van Dam A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, Reading, MA. 1982.

[15] Peigl L, Tiller W, "Computing offsets of NURBS curves and surfaces", Computer-Aided Design, 1999, v31(2), pp.147-156

[16] Hayong Shin, Su K. Cho "Directional Offset of a 3D Curve" Advanced Institute of Science and Technology, 373-1 Daejeon, S. Korea +82-42-869-3124.

Amod Tiwari (1), A. Chatterjee (2), A. Pandey (3), V. Pathak (4) and S.G. Dhande (5)

(1) Research Scholar, Cad Laboratory IIT Kanpur, India, E-mail: amod@iitk.ac.in

(2) Sr.Research Engineer, Cad Lab IIT Kanpur, India, E-mail: achat@iitk.ac.in

(3) Research Scholar Annamalai University, Tamil Nadu E-mail : akhil_pandey_05@yahoo.co.in

(4) HBTI Kanpur, Asstt Professor, India, E-mail: vpathak@lycos.com

(5) Professor (ME and CSE), IIT Kanpur, India E-mail: sgd@iitk.ac.in