- Email: [email protected]

0097 8493/83 $3.00+ .00 Pergamon Press Ltd.

C o m p u t e r G r a p h i c s in J a p a n

A SOLID MODELLING SYSTEM: FREEDOM-II FUJtO YAMAGUCHIand TOSHIYA TOKIEDA Department of Industrial Design, Kyushu Institute of Design, 9-1, Shiobaru 4-chome, Minami-ku, Fukuoka, 815, Japan

(Received 26 August 1983) Abstract--A compact solid modelling system FREEDOM-II is discussed using simple algorithms for Boolean shape operations and hidden line-surface elimination. l. INTRODUCTION The F R E E D O M - I I is a system which makes it possible to design solid objects with planar or curved surfaces interactively with the computer. The approach taken in the design of the system is to realize a small system, employing unified algorithms. In the system F R E E D O M - I I a face is treated in a unified way whether it is holed or not. Ordinarily a holed face is either split into a few pieces of faces or a new geometric element, a loop, associated with each hole is introduced in the object representation. But in the F R E E D O M - I I a holed face is treated as a single entity in the same way as a face without a hole by introducing a particular edge, "a bridge edge". Data structure manipulating routines in this case will be explained in this paper. In the system F R E E D O M - I I Boolean shape operations are performed between two polyhedra. In this case potentially intersecting faces are triangulated prior to the operation. Therefore, a main processing unit of the operation is one to process a mutually intersecting triangle pair. This is found to be very effective in simplifying the shape operation algorithm and realizing a small system. This shape operation algorithm based on the face triangulation can be extended to deal with objects made up of free form surfaces. Lastly, a hidden line and surface elimination algorithm is explained, which can be used both for hidden line and hidden surface detections. Roughly speaking the computation time of the algorithm increases, not depending on the complexity of the scene or the complexity of the visible image, but on the number of visible faces hidden partially.

NFACE

PFACE Edge NVT

\

"~~..' "

Fig. 1. Face representation. vertex of the outer perimeter (Fig. 2). We name this particular edge "bridge edge (B-edge)". The purpose of introducing the B-edge is to deal with a holed face as a single entity in almost the same way as an ordinary face without a hole. The B-edge is particular in that E d g e T . P F A C E t is the same as Edge T .NFACE. Because of this property the data structure must be manipulated with special care. 3. DATASTRUCTURE MANIPULATINGROUTINES By introducing Bedges, a holed face seems to be dealt with quite easily in the same way as an ordinary face without a hole. For example all the vertices of a holed face seem to be visited as a sequence of V,, V 2, V3, V4, V 5, V 6, V7, Vs, V6, Vs, V9 (see Fig. 2). A difficulty with this method is that a topological

2. FACE REPRESENTATION Objects are represented by employing the basic concept of the Winged Edge Data Structure[4] (Fig. 1). In the case of a holed face it is ordinarily either split into a few pieces of faces, or it is represented by introducing a new geometric element, "a loop". But in the F R E E D O M - I I it is represented by using an "invisible" edge between a vertex of a hole and a

VI

V

2

~

V9 ridgeedge

V4 V~ V3 Fig. 2. A bridge edge.

tEdgeT.PFACE should be read as PFACE of Edge. 225

226

FuJlO YAMAGUCH1and TOSHIYA TOKIEDA

position of a vertex on a vertex perimeter of a face can not necessarily be specified uniquely if the vertex is given alone . The same is true of a topological position of an edge on an edge perimeter of a face. In order to specify a position of a vertex or an edge on a perimeter of a face, the edge or the vertex adjacent to the given vertex or edge must be specified in addition to the given vertex or edge respectively. That is, a vertex-edge pair is necessary in specifying a topological position in a face representation including B-edges. Some of the data structure manipulating routines proposed by Baumgart could be modified in the following ways, taking the foregoing into consideration. (1) Edge clocking routines (ECCW, ECW) Edge clocking routines, ECCW, ECW, are ones which return an edge counter-clockwise or clockwise from a given edge with respect to a given face. When the given edge is a B-edge, the solution can not be determined uniquely with the edge and face specification method, becasue B-edge T .PFACE is the same as B-edge T .NFACE. In order to specify a topological position uniquely, a vertex adjacent to the given edge is required in addition to the edge and face. For example, in the case of returning a counterclockwise edge, the New-edge can be found by turning clockwise at the Given-vertex from the Givenedge as shown in Fig. 3. (2) New edge and vertex making routine (MKEV) A New Edge and Vertex Making Routine, MKEV, is one which creates a new edge and a new vertex, attaching the edge to a given vertex as a spur in the perimeter of a given face. In the case where the given vertex is on a bridge edge, the side where the Newedge is attached is not unique as shown in Fig. 4. An adjacent edge either clockwise or counter-clockwise from the given vertex must be given to specify the position uniquely. This edge can be found topologically by capitalizing on the face triangulation during the determination process of intersection line loops as will be described later. (3) New.face and edge making routine (MKFE) A New Face and Edge Making Routine, M K F E , is one which creates a new face and a new edge, placing the edge between the two given vertices on a face. When one of the given vertices is on a bridge

Given-vertex

New-edge ~

~

New-vertex

Fig.4. MKEVroutine. edge, then wing pointers between corresponding edges can not be uniquely determined. For example, in Fig. 5 the PCCW of the New-edge can be either E1 or E2. In order to remove this ambiguity adjacent edges must be specified to both Given-vertexl and Given-vertex2. (4) WING The routine, W I N G (New-edge, Given-edge) sets the wing pointers of the two specified edges, Newedge and Given-edge. If Given-edge is a bridge edge, wing connection can not be uniquely determined. For example, in Fig. 6, New-edge can be connected to Given-edge from both sides. In order to resolve this ambiguity, a vertex either clockwise or counter-clockwise from a Givenedge must be specified in addition to Given-edge. 4. F A C E T R I A N G U L A T I O N

Before the main processing, the Boolean shape operator of the system standardizes the face representation by triangulating potentially intersecting faces, in order to localize and simplify the processing. The triangulation is simple. Go to each vertex of a face by using the edge clocking routine, ECCW or ECW, find a concave vertex and if present try to triangulate with the two successive edges from the vertex. If the triangle made by the two edges includes

~

New-edge

~ F"E2~~~Given-vertex 2

~

Givenvertex I Fig. 5. MKFE.

iidge

vertex

Fig. 3. ECCW routine.

Fig. 6. WING.

A solid modelling system: FREEDOM-II

227

a vertex, triangulation is impossible; otherwise, it is possible. If triangulation is possible, remove the triangle and repeat this process until the vertex becomes convex or the triangulation is impossible. Repeat the above process with other vertices until all the vertices are convex. Emanate edges from any one vertex to all the others, then the face triangulation is completed. The above triangulation process is the same whether the face is holed or not. The edges generated as a result of the triangulation process are called "'T-edge". The others except Bedge and T-edge are called "R-edge".

one of the generated triangles having EDR by TRR. If the R-edge intersects with an edge of the other triangle, then split the intersected edge there and denote the generated vertex by VIB. Retriangulate the two triangles on both sides of the intersected edge by inserting edges between VIB and the third vertices. If the R-edge happens to intersect with a vertex of the other triangle, then the vertex itself becomes VIB. We denote the triangle intersected by the R-edge by TRS. In the case where the R-edge intersects with either an edge or a vertex, then any triangle sharing VIB can become TRS.

5. AN ALGORITHM FOR BOOLEAN SHAPE OPERATIONS

(3) Determination o f intersection line loops We suppose an R-edge, EDR of a triangle TRR intersects with a triangle TRS at Q+. The next intersection point Q~+~ on an intersection line loop is found by tracing intersecting triangle pairs. Intersection line loops are determined by repeating this process in the following way.

Suppose two mutually intersecting polyhedral bodies "'a", ++b" are given in 3-space. (1) Initial processing

First of all, the common space of the bounding boxes of two intersecting bodies is computed. Test each face for intersection with the common space. Among these faces satisfying the above condition, find face pairs of which the bounding boxes intersect mutually and push them into a stack called IPSTACK. IPSTACK contains face pairs which potentially intersect each other. Each face in IPSTACK is triangulated and the generated triangles are linked in TLISTI field of the original face block. Then find intersecting triangle pairs, link them in a list named ITLIST and make a list of pairing triangles of which the header is in the TLIST2 field of each intersecting triangle block as in Fig. 7. In making the ITLIST the number of the triangles in the ITLIST which belong to an original face is recorded in the T R C O U N T field of the face. (2) Initial intersection point Take a triangle pair out of the ITLIST which has an intersecting R-edge. We denote the intersection position vector by Q , Split the R-edge at Q1- Denote the generated vertex by VIA and the outer edge (with respect to the other body) by EDR. Retriangulate the two triangles on both sides of the R-edge by inserting edges between VIA and the third vertices of the triangles. We denote

Dummy ITLIST

block

[. "--r

'[o,I 0 ~

(3.1) With respect to the coordinates of the third vertex of TRR, compute s = a x + by + c z + d, where a, b, c and d are plane parameters of the triangles TRS and check whether one of the edges of T R R except EDR intersects with TRS. If there is such an edge, then the edge becomes the new EDR (see Fig. 8. I). The other triangle across the new EDR becomes the new TRR and the old TRS is again the new TRS. Go to (3.3). (3.2) If there is no intersecting edge found in (3.1), then find an intersecting edge of TRS with TRR by computing s = a x + by + c: + d with respect to the coordinates of each of the three vertices of TRS using the plane parameters of the triangle TRR (see Fig. 8.2). There is always an intersecting edge, which becomes the new EDR. The other face across the new EDR becomes the new TRR and the old TRR becomes the new TRS this time. (3.3) The pair of old TRR and old TRS is removed from the ITLIST by utilizing the list TLIST2. The TRCOUNTs of the original faces of the triangles are decremented by one. If the old intersection point (the intersection of the old EDR and the old TRS) is shared by other triangle pairs, then these pairs are also removed from the ITLIST (this is the case where the intersection is on an edge or a vertex).

Jl

TLIST2 %, ~~ - - - - ~ TLIST2 (I)

Fig. 7. Relation between ITLIST and TLIST2.

(2)

Fig. 8. Two cases of an intersecting triangle pair.

228

FUJlO YAMAGUCHI and TOSHIYA TOKIEDA

(3.4) I f a new edge EDR is a T-edge, then return to (3.1). If a new edge EDR is not a T-edge, the edge is either an R-edge or a B-edge. If one of the end vertices of the edge coincides with either VIA or VIB, this means returning to the initial intersection point. If so, go to (3.5). Otherwise, compute the intersection point, which is a point Q,+I on the intersection line loop. Then detriangulate the processed face, pushing into a stack (TRSTACK) the pairing triangles to the triangles of the processed face if the T R C O U N T of the face is not zero, and split the face by the intersection lines. If the T R C O U N T of the face is zero, this means there is no triangle in the ITLIST which belongs to the processed face. In this case split faces are marked inner or outer according to whether they are inner or outer against the other body. If the T R C O U N T of the face is not zero, retriangulate the split faces, make new intersecting triangle pairs between the triangles of the split faces and the triangles in the TRSTACK, and insert them in the ITLIST. In making new intersecting triangle pairs, the pairs must

TrianguLation

be excluded which intersect at the points already determined on an intersection line loop. Then return to (3.1). Some of the cases mentioned above are illustrated in Fig. 9.

(3.5) There may be other intersection line loops to be processed. Check if there are some triangle pairs left unprocessed in the ITLIST. If there are some, repeat the above algorithm by returning to (2). If there is no triangle pair in the ITLIST, the processing of the intersection line loops are completed. (3.6) The intersecting faces have been marked as inner or outer faces. Faces surrounded by an intersection line loop are either inner or outer faces. According to the rules listed in Table 1 either inner or outer faces must be removed from the data structure. These faces can be removed continuously beginning with one of the intersecting faces which have already been found to

Computation of intersection points

Detriangulation

TRCOUNT=O

CLassification of split faces into inner and outer faces

Face splitting

TRCOUNT>O

Retriangutation of split faces

Fig.9(a). Processing of a face without holes.

A solid modelling system: FREEDOM-II

TrianguLation

229

Computation of intersection points

Detriangutotion

Removal of O port of B-edge This B-edge must be removed because o B-edge must be E$ PFACE=E~ NFACE.

Face splitting

Retriongutotion

OetrianguLotion

Computation of intersection points

Face splitting

Cl.ossification of split faces into inner and outer faces

Fig. 9(b). Processing of a holed face (I). Table 1. The rules to reorganize the data structure A or B body A

body

B

A and B

A dif B

o u t e r face

t o be l e f t

t o be removed

t o be l e f t

i n n e r face

t o be removed

t o be l e f t

t o be removed

outer

face

to

be

]eft

to

ve

removed

to

inner

face

to

be

removed

to

be

left

*To be left after invertin

~C¢ normal.

be *

removed

230

FuJIO YAMAGUCHI and TOSHIYA TOKIEDA

Triangutation

Face splitting

Computation of intersection points

Computation of intersection points

Removal of B-edge This B-edge must be removed because a B - e d g e must be ET.PFACE = ET.NFACE

DetrianguLation

DetrianguLation

Retriongulation

Face splitting

CLassification of split faces into inner and outer faces

Fig. 9(c). Processing of a holed face (2). be inner or outer faces. Then the data structures of the two bodies are reorganized into a single data structure. In Fig. l0 some of the designed shapes using the FREEDOM-I! are shown. 6. HIDDEN LINE AND SURFACE ELIMINATION

A unified algorithm is used to eliminate either hidden lines or surfaces. We call it a "segment chain"

algorithm. It is a type of scan line algorithms. That is, detection of visible faces are processed scan line by scan line, from bottom to top. An outline of the algorithm is as follows. In the beginning all the data of the given scene are perspective-transformed and further transformed into screen coordinates, x~, Ys, z,. All the edges making up the scene are sorted by their smaller y-coordinate into a list called Y-sort list. At each

231

A solid modelling system: FREEDOM-If

\

1

Fig. 10. Some examples of designed shapes.

scan line another list called X-sort list is created with which the algorithm detects which faces are visible. At each scan line a set of polyhedra of the scene are cut by a plane (scan line plane) passing through the scan line and parallel to xs-Ys plane. The sections are a set of sectional polygons of which the sides we call "segment". The endpoints of each segment are intersections of edges and the scan line plane. The connected front segments, which are intersections of front faces and the scan line plane, are named "segment chain". By a front face we mean a face which is facing the eye. An X-sort list is a list in which all the segment chains at a scan line are sorted by their smallest x-coordinate. A slit-like window with unit height and a horizontal sample span length is supposed on each scan line. Initially the sample span is set from the smallest x-coordinate to the largest x-coordiante of segment chains in the X-sort list. From relationships of a segment chain to a window, the segment chain is classified into the following three types: (1) a segment chain which extends to or beyond the edges of the window (type A) (2) a segment chain which is included in the window partially or wholly (type B) (3) a segment chain which is separated from the window (type C). If there is only one segment chain or a type-A segment chain hiding all the other segment chains in the window, the segment chain is clearly visible. In these cases the light intensities of all the segments in the visible segment chain are written in the frame buffer. Otherwise the situation is considered to be complicated and the window is subdivided at an edge CAG Vol. 7, No. 3 - 4 - - B

of the smallest x-coordinate in the window into two smaller windows. Then the same judgment as mentioned above is applied to each of the subdivided windows, first to the left window, and then to the right window. This simple algorithm is repeated until the whole span of the present scan line is covered. The foregoing processing is repeated scan line by scan line until all of the scan lines are completely covered. In case of outputting visible edges, not visible faces, the edges of visible faces are kept in a list and the whole parts of visible edges are output when each visible edge is completely processed. The computation time of this hidden line and surface elimination algorithm grows roughly as the number of partially hidden, visible faces increases. In the case of relatively simple polyhedron, the "segment chain" algorithm is about twice as fast as Watkins' algorithm. And the more complex the objects are, the more efficient this algorithm is, compared to Watkins' algorithm. 7. C O N C L U S I O N

A small solid modeling system has been realized, of which the program size of the Boolean shape operations is approx. 25KW. The system can deal with simple, curved surfaces, such as cylinders, cones and spheres by approximating with planar polygons and applying the same tracing algorithm of intersecting triangle pairs as mentioned in this paper. At present the system is being generalized such that the tracing algorithm can be applied to free form surfaces.

FUJIO YAMAGUCHIand TOSHIYATOKIEDA

232 REFERENCES

1. 1. C. Braid, The synthesis of solids bounded by many faces. CACM 18, 209-216 (April 1975). 2. Hosaka et al., A unified method for processing polyhedra. Proc. 1974 IFIP Conf. (1975). 3. TIPS Working Group, TIPS-I, Institute of Precision Engineering, Hokkaido University, Japan (1978).

4. B. G. Baumgart, Geometric Modeling for Computer Vision. Computer Science, Standford University (1974). 5. G. S. Watkins, A real time visible surface algorithm. UTEC-CSc-70-101. University of Utah (1970).