Prism Trees: A Hierarchical Representation for 3-D Objects

A3STRACT

In this paper we propose a hi e rarch ic al structure for describing objects, called the Pr ism Tree. ternary tree structure, inspired from planar Strip Tree, is built from initial triangulation of the object usi ng a polyhedral approximation algorithm. Differ ent propert ies of r e presentation are shown, as well a lgorithms for intersecting objetts neighbor finding techniques. new 3-D This the an by this as and

INTRODUCTI0\1

Multilevel repres entation s have been found us eful in Computer Vision for se veral years now [1,3,4,5]. By a llowing the access and manipulation of regions and objects at various levels of details, they prov i de a natural dat a structure for thinking about objects in the context of a given task. They also are excellent tools for speeding up various algorithms by the fact that "divide and conquer" techniques are easily implemented on such data structures. In this paper we propose a representation for 3-D objects which is a generalization of Ballard's Strip Tree s DJ. In this method space curves or surfaces are hierarchically approximated by using a prism as enclosing box, yield i ng a ternary tree structure called the Prism Tree. One advantage of this structure is that it is intrinsic to the object shape, and therefore invariant through rigid transformations. Moreover, this tree stru~ture allows to implement efficiently neighbor finding operations and surfaces intersections as tree traversal algorithms. We first explain the general principle of our approach and show how to build a Prism Tree from a polyhedral representation of an object, then prove a theorem that allows to efficiently t~st intersections of surfaces, and describe algorithms for performing various operations on objects.

')'l b 1 ·1 TilEES : A HIERARCHICAL REPRESENTATIO~ POR 3-J O~JECTS

O. D. PAUGERAS and J. PO~CE

!NRIA 9omaine de Voluceau, Rocquencuurt BP 105-78153 le Chesnay Cedex PRANCE

THE ENCLOSING BOX SC~fME

Ther e a re two basic approaches to the hierarchical description of shapes ~n Computer Vision: The representation ma y be ei ther attached to a fixed grid, or t o the object i t se lf. The form e r a3proach gavE; b:..rtl, t :> IJu oJdtte e ~ ond thei r 1-IJ qenera l i za t i on, the Oct-Trees [3,4,5]. Ba llard DJ investigated the second approach. The idea is to use a recur sive polygonal ap;Hoximatiun a lgorit.hm [6] fur curves and, at each level of the recursion, to asso cia te to each lin e segment SEG the smallest r ec tangul a r bo x wi th sides parallel to SEG wh ic h encloses the part of the curve delimited by the ex tr emi t ies of SEG ( f ig . 1 ) . Such a box (ca ll ed a Strip by Ballard) represents a pa rt of the object as a pixel would but it has the advant age of being a tt ac hed to the c urve itself. As the r ec ur si on proc eeds, eac h l i ne se gment is sp l i t into two par t s , and one can associate to the initial box the corresponding "children" boxes. So a b ina ry tree structure is built quite naturally, that is i nvari ant through rot a tions and tran s lat io ns , an d on wh ic h a varie ty of a lgor i thm s (intersections · . ) can be ef f icien tly imp l emen t ed . A simple example of application is veri fy ing th1t two obj ects do no t int ~ r sec t O ) tr~ v~r s in] thei r Strip Tr ees and checking a t each node that the Strips do not inter sec t. Other app l ica t i ons a re in Gr aphics, with multilevel displays.

The idea of enclosing the object in a succession of boxes is read i ly extendable to the 3-D s pa ce . Using a polyhedron for describing 3-D objects is a way of s tructuring the space quite analog to representing a planar sh3pe by a circular ordered l is t of points. In th is context, we presented elsewhere [2] a generalization of the pr eviously mentioned polygonal approx i mat i on, the object being split in triangles instead of segments. In the next Section, we briefly describe thi s algorithm and show how one can associate to each triangle a part of the surface and a prismatic box enclosing it.

II POLYHEDRAL APPROXIMATIO~ A~O ?RISM TREE CONSTRUCTIO~

We assume th~t at the lowest level, the objects are represented by polyhedra: Our data is the graph GO defined D) the points in 3-D space, and the polyhedral edges joining them. There are several ways of obtaining such polyhedra from riln::Je data [7 's].

ll_~£lt~~2~l-~££££~l~~lio~

We use a top-down approach. We consider a triangulation of the object which is refined at each step until some error threshold THR is reached. Durin:) the execution of the algorithm, the triangulation is considered ilS a "face"-graph GF'. We associate to each triangle T a node with diverse attributes: the vertices, denoted P, Q, R, the "part ST of the surface associated to T" (we will see later what we mean by these words), and the corresponding error ERR (e.g. The maximal distance from the triangle to the surface). The edges of GP are defined oy the neighborin::J reliltions of the triangles (two triangles sharing an edge are neighbors). The algorithm loops over the following steps

.SP~IT STEP (fig. 2)

F' or-each-tr i a n g l e T v e r if y i n g E R R g r e a t e r th3n THR do

Pind M, point of ST lying at maximum distance of T

Let Tl, TZ, T3 be the nodes defined by:

the vertices of Tl are P, Q, M

the vertices of TZ are Q, R, M

the vertices of T3 are R, P, M

ST "has been split" into three parts corresponding to Tl, TZ, T3, ERRl, ERRZ, ERR3 are the corresponding errors, then - replace the node T by Tl, TZ, T3 in the graph (in particular update the neighbors 0 f T) ·

. ADJUSTMENT STEP (fig. 3)

If-;e-unry-ug;~the SP~IT STEP , old edges would ever remain, even if they are very far from the surface.This is the reason why we add this step which removes the edge between two faces having just been split

Par each pair Tl, TZ of such triangles do find M, point of STl union STZ which is the closest from the bissector plane of Tl and TZ , and the furthest from their common edge

split Tl in two triangles of vertices Pl,Q,M and Pl,R,M, split TZ in two triangles of vertices PZ,Q,M and PZ,R,M update the graph the same way as in the SPLIT STEP.

Let us add some details. Pirst the algorithm has to be initialized with a starting graph: it is usually obtained by taking three points which define a first triangle. This triangle is then split in a way quite analog to the SP~IT STEP, so the starting GP describes a 5 faces polyhedron made of two tetrahedra sharing a face that is the initial triangle (fig. 4). But notice that any other triangulation could be used as we 11. It is now time to define clearly the meaning of ST and the way to cut it in three (or two for the adjustments) parts. In fgct there are two possible algorithms, denoted ALGRA and ALGLI) :

The first one, described in [z], works for objects defined by polyhedra without holes (genus zero). It uses the property th3t in this case GO is planar, so each cycle drawn on this grap~ cuts it into two connected components. Let us consider a pair of neighboring triangles Tl and TZ of GP, let Q and R ~e their common vertices, if we associate with each of these p3irs a path (Q,R) in GO, we define for each node T of GP a cycle (P,Q),(Q,R),(R,P) of GO 3nd, as it is a planar graph, a connected su~set ST of GO. Thus we only have to give an algorithm for finding non intersecting paths to define a partition of the surface in ST's. We define them recursively by using the SP~IT STEP (the case of the ADJUSTMENT STEP is quite analog and will be omitted). Let T be a node to split (fig. 5), and M the splitting point. We suppose the paths (P,Q), (Q,R), and (R,P) defined. Let Tl, TZ, and T3 be the triangles PQM, QRM, and RPM , and Pl, PZ, and P3 the bissector planes of the pairs T2,T3 , Tl,T3 and Tl,TZ. We define (P,M) as the path in ST which is the closest to the plane PZ. The path (Q,M) is defined similarly using the plane P3 and only considering points which do not belong to (P,M). These two paths and the path (P,Q) define a cycle which cuts ST in two components Cl and CZ. Let Ci be the component which contains R, we now find a path (R,M) in Ci by using the plane Pl. The three paths do not intersect, and they split ST into three components STl, STZ, and ST3 which correspond to the cycles (P,M,Q), (Q,M,R), and (R,M,P).

The second possible way of defining the ST's does not make explicit use of the graph GO. ST is no more a subgraph but simply a list of points. We will also define it recursively by using the SP~IT STEP. Suppose ST is defined for a triangle T that we are going to split. We keep the same notations and still call Pl, PZ, P3 the three bissector planes defined by the splitting. STl will simply be the subset of ST composed of the points of ST which lie between the planes P2 and P3, STZ and ST3 will be defined similarly, and it is clear that we so obtain a partition of ST. We must though remark that there is in general no guaranty that ST is connected (fig. 6), so we have to be cautious when using this method (in the case of a convex shape, one can nevertheless easily prove that the ST's sta) connected).

We now consider GP at some level of the recursion. Let T be one of its nodes, and ST the associated part of the surface (which can be either a list or a subgraph). We wish to define an enclosing box of ST. With its three neighboring triangles, T defines three bissector planes Pl, P2, and P3 (fig. 7). The "Prism" associated to T will be the smallest 5-faces polyhedron of which three faces are parallel to Pl, P2, and P3, and the two remaining ones are p~rallel to the PQR plane, that contains all the points of ST (fig. 8). These five planes will be denoted PPl, PP2, PP3, PBl, and PB2 and the two triangles of the prism parallel to T will be denoted TBl and TB2. We can now build a ternary tree as the recursion proceeds. Although it is surely not the most concise description of a prism, we suppose for the sake of clarity and efficiency that one finds at each node of the tree the following informations: P, Q, R, PPl, PP2, PP3, TBl, TB2, three flag bits REG , MARK (we will explain their use in the sequel) and ADJ (=1 if the node has been obtained through an adjustment), and four pointers SO~l. S0~2. S0~3. and PATHER. The root points on two nodes (first pointer at NIL) associated to the two half surfaces defined by the initial t r ian g l e . We de fin e t he chi 1 d r en n f 1 ,, ~ >i -:; recur~' : ·' ly·. A triangle T split into three sub-triangles Tl,T2,T3 corresponds to a node the three children of which are defined by Tl,T2,T3. An adjusted triangle has only two children, the third pointer being set at NIL. In turn, each child points towards its father. In the sequel, a pointer to a node will be denoted PT, and the corresponding node PT'. Pig. 9 shows an example of Prism Tree for a simple object.

III SO~E PROPERTIES OP THE PRISM TREES

In order to prove some important properties of Prism Trees, we need to define a l~~lar prism: a prism will be said to be regular if the associated ST is connected, and if its three planes PPl, PP2, and PP3 are Pl, P2, and P3 themselves (fig. 10). This notion is quite similar to the regular strips of Ballard [f] and prevents pathological configurations (fig. 8). This is the reason why at each node of the Prism Tree we keep the regularity bit REG which will be set if the corresponding prism is regular.

It is clear that a node of a tr c:e :>u : Jt b ) u ~; :. rq .~L�RA :s regular :Ff PPl, PP2, :wd PP3 ;one Pl, P2, C~nd P3 themse lves. Conversely, if th~ tre e is built by using AL�~I the condition is the connexity of ST (which can easily be checked after each splitting by using GO ). We now give two lemmas (only indications of their proofs are given for space savings) and prove a theorem.

3) ~emma 1: Surface-Prism Intersection --------------------------------------

~et T be a l~3~l~l node Pr ism Tree. Th e n the intersection with PPl,PP2,PP3 is a closed curve 10). (easy to verify with ALGRA and of a of ST (fig. AL�~ l)

4) Lemma 2: Curve-Surface Intersection --------------------------------------

~ e t T be a l~3~l~l node of a Prism Tree. Then any continuous curve C starting from a point U inside TBl, ending ~t a point V inside TB2, and sta)ing within the prism intersects the surface of the object an odd nu~ber of times (fig . 11). (use the previous lemma and the Jordan closed surface theorem)

5) Prism-Prism Intersection Theorem -----------------------------------

~et T and T' be two l~3~l~l nodes of Prism Trees, and TBl, TB2 and TBl', TB2' the associated basis triangles. Then if for any i and j (i,j=l,2), the intersection of the interiors of of the triangles TBi and TBj' is non empty (CLEAR intersection) then the underlying surfaces STand ST' intersect (fig. 12).

(analog of the Clear Intersection Lemma for Strip Trees)

PROOP: Prom the hypothesis we deduce that the intersections of at least one PPk' with both TBl and TB2 are non empty , and so consist of two segments A,B and C,D. Prom Lemma 1, the intersection of PPk' with ST' is a continuous curve, and so is the intersection of ST' with the pol~gon A,B,C,D. The extremities of this curve l ie inside TBl and TB2, so from Lemma 2 we deduce that it intersects ST. Q.ErD

By using this theorem and the obvious fact that if two prisms do not intersect (NU~~ intersection) then the underlying surfaces do not in tersect either, the next two Sections will show how one can check whether two surfaces intersect, and find their intersection curve considered as a Prism Tree. Prom now on, we suppose that we dispose of two functions VOL(PT) and PRISMINT(PT,PT'). VO~(PT) returns the volume of the prism associated to PT'. PRISMINT(PT,PT') returns CLEAR, POSSIBLE, or NU~L according to the type of intersection of the prisms associated to PT' and PT''. Moreover, if a node is not regular (REG=O) PRISMINT will never return CLEAR unless both nodes are leaves (in this case we assume that the intersection is either CLEAR or ~U~~). If one of the pointers is NIL, PRISMINT returns NU~~. As they are highly recursive, we will express our intersection algorithms in a pseudo PASCAL form and, following Ballard, we take the heuristic to divide first the largest prism during the recursion (so the prisms compared are always approximatively equal s i zc: d) ·

IV TESTI~� SURPACE-SURPACE INTERSECTION

Our algorithm is a direct extension of the Ballard's one. The two trees pointed by PT and PT' are visited until a CLEAR intersection has been found or all the nodes have been checked. Punction CHECKI(PT,PT'):boolean; begin case PRISMI~T(PT,PT') of NU~L CHECKI::false; CLEAR : CHECKI:=true; POSSIBLE: if VOL(PT) > VOL(PT') then CMECKI::(CHECKI(PTT.SONl,PT') or CHECKI(PTT.SQ'JZ,PT') or cHEcK I ( p Tj . s Q ~ 3' p T I ) else CHECKI::(CHECKI(PT,PT'j.SQNl) or CHECKI(PT,PT'j.SQN2) or CHECKI(PT,PT'T.SON3) end

end;

V INTERSECTION OP TWO SURPACES

1 Ne now wish to find the intersection curve of two surfaces. This will be done by finding and marking (using the MARK flag) in the two trees all the nudes whose prism intersects the other surface. We use the ob~ious property that if a node intersects a sur face , then all - its ancestors intersect this surface. Conversely, all the descendants of a node that does not intersect a surface do not intersect it either. This gives the following algorithm, where all the flags MARK have previously been initialized 0.

Procedure SURP INTER(PT,PT'); begin (*P~ISMINT = NU~~ is the stopping condition. It corresponds to the case where a node is at nil or has an empty intersection with the surface*) if PRISMINT(PT,PT') <> NU~L then begin if PRISMINT(PT,PT') = CLEAR (*nodes intersect the other surface*) then begin PTT.MARK::l;PT'T.MARK::l end; (*the recursion proceeds*) if VOL(PT) > VOL(PT') then begin SURP INTER(PTT.SQNl,PT'); SURP-INTER(PTf.SONZ,PT'); SURP-I r-.JTER (PTT. SQN3' PT I); (*if the mark of the childten is l*) (*then PT" intersects the surface*) if(PTT .SONl<>NIL)and(PTf .SONl T .MARK=l) or(PTf.SO'J2<>NIL)and(PTf.SON2f.MARK=l) or(PTf .SQr-.J30NIL)and(PTf .SO:'Of .MARK=l) thenPTT.MARK:= l end else begin SURP INTER(PT,PT'f.SONl); SURP-INTER(PT,PT'j.SQNZ); SURP-INTER(PT,PT'j.SON3); (*if-the mark of the children is 1*) (*then PT'" intersects the surface*) if ( p T I r . s 0 N l <> N I L ) and ( p T I i . s 0 N l r . M .l\ R K = l ) or(PT'f.SONZ<>NIL)and(PT'T.SONZI.MARK=l) or(PT'f.SON3<>NIL)and(PT'T.SQN3f.MARK:l) then PT' T .M.ARK: =1 end end;

When the execution of the algorithm is complete, all nodes ha~ing a ~cLEAR~ descendant have been marked, and no descendant of a ~NU~L~ node has been marked. To obtain the intersection curve, one has only to visit one of the trees ~nd to prune it from all the nodes marked 0 (in that case, the regularity flag of all the ancestors of these nodes must be set to 0). Notice that we have two representations of the curve, one for each tree.

VI A NEIGHBOR PINDING ALGORITHM

Algorithms which operate on hierarchical structures often need to explore the ~neighbors~ of the visited nodes [5 ]. In our case, the neighbors of .'J node are clearly defined : During the construction of the tree, a graph structure has been maintained. So at each level of the tree, the neighbors of a node T can be defined as the nodes corresponding to the neighbors in GP of the triangle associated to T. By storing GP at each level of the tree, one would have an easy, but very memory consuming, way of finding the neighbors. We will show in this Section how one can find the neighbors of each node without storing the GP's. Notice first th~t the only tree transformation we have defined is the SURP INTER procedure, which prunes the tree without modifying its structure, so that each node of a tree has always three neighbors, some of them being eventually empty (~IL pointer).

w~ first define the "eldest" son of a node. When splitting a nod;-fi~--using the approximation algorithm, three new triangles, and three new edges are created, so that each triangle h~s always two "new" and one "old" edge. The child of a node which corresponds to this "old" ed~e will be called the eldest son of the node (e.g. in fig. 9, the triangle 853 is an eldest son). In the case of an adjustment, it is clear that the eldest son will be the missing one. During the construction the pointer SONl will always represent the eldest son.

We first consider the case where no adjustment has occured. Then we find the three neighbors of a node using the following algorithm:

Let T be the node visited

.two of its neighbors are its two brothers

.let E be the remaining edge (it can be found by examining the vertices of T) .if T is an eldest son

then ascend the tree until the current nod; is no more an eldest son. let Tl be this son

else Tl:=T

.let-r2 be the father of Tl

.descend the tree by visiting at each level the only son that shares E with T until the node is a leaf or it is at the s:Jme level as T

.this node is the third neighbor of T (exterior)

It is easy to see that the ~lgorithm "works": if a node is an eldest son, its father shares E with a neighbor which is not its brother (obvious), so we have to ascend the tree. Moreover the edge E of a node is always the "old" one, suppose that the node is not an eldest son, then E is an edge of· its f~ther, but cannot be its "oldest" one, so the father shares it with one of its brothers.

We can now extend this method to the case of the adjusted nodes (ADJ=l). The difference is that an adjusted node T has not two neighboring brothers, but only one, the third one is its adjustment neighbor(e.g. triangles 753 and 736 in Pig. 9). Let E be the corresponding edge. We find the two usual neighbors by the previous algorithm. Par the adjustment neighbor, we look at the father Tl. Tl has been adjusted with one of its neighbors T2, which is its exterior neighbor. We simp! have to find T2 by the algor thm, and the neighbor of . T son o T2 which shares E with T. previous is the

VII INTERSECTIO~ OP TWO VOLUI~ES

In [1], Ballard ::jives an algorithm for computing the intersection of two areas defined by the Strip Trees of their boundaries. The method consists in finding in each of the trees all the nodes which intersect or are inside the other area. The intersection area is then obtained by considering all these nodes. Let us denot~ A and A' the areas, and S and S' the corresponding trees. Ballard uses ~ function STRIP INSIDE to check wether a node of S w~ich has a NU~L intersection with S' lies or not inside A'. This is verified by traversing the whole tree S', and counting the number of CLEAR intersections of a semi-infinite .Strip issued from the node with S'. If this number is odd the node lies inside A' (analog to the usu3l method for testing wether a point lies within a polygon). The dis~dvantage of this algorithm is th3t it computes the function STRIP INSIDE for each ~ULL intersection node, implying at each time a full traversal of S'.

Such a method could be used for Prism Trees. A 3-0 solid is defined b> its closed surface, and the associated Prism Tree PT. Any prism can be classified in one (and one only) of the three following types:

1: the intersection of the prism with the surface i~ non empty

2: prism fully inside the surface

3: prism fully outside the surface

Let us consider two objects represented by two Prism Trees PT and PT', it is possible to mark all their nodes of type 1 by using the algorithm of section V. Testing the type of a NULL intersection node can be made by the following 3-D equivalent (P INSIDE) of the function STRIP INSIDE: Lei us consider a node T of PT. -We can associate to it a semi-infinite straight line L normal to T, issued from the barycenter of this triangle on the TBl side (Pig. 13). The notion of CLEAR intersection can be extended by saying that L has a CLEAR intersection with 3 regular prism T' if it intersects the corresponding TBl' and TB2'. Prom Lemma 2 we deduce th3t in this case L intersects ST' an odd number of times. The function P INSIDE is then computed by traversing pf· and counting the number of these CLEAR intersections, it returns the type (2 or 3) of the node. The intersection of the two objects is described by the two trees pruned of their nodes of type 3. Remark that a node of type 2 or 3 has all its descendants of same type, so they do not need to be examined.

However, one has still tu traverse PT' at each NULL node. The situation is even wor se than in the 2-D case as we deal with a ternary tree and a more complex INSIDE function. We propose a slightly different algorit hm for avoiding tuo many computations of P INS[DE. It is based on the f::Jct th3t if two neighboring prisms of PT have a NULL intersection wit h PT', then they lie both inside or outside the surface associated to PT' (proof : suppose that one lies inside and the other outside, then their common edge lies at the sa~e time inside and outside the surface, which is impossible) . So one has only to compute P INSIDE fur a few nodes, and to explore anJ mark for each of these nodes its connected component of NULL intersection nodes by using the neighbor finding algorithm of the previous section. This gives the following algorithm:

Procedure VOL INTER(PT ,PT'); (*marks the n;des of PT. (*SURP INTER ~1s already been begin if PT <> NIL then ~egin . ) applied·) (*look at the mark of the node*) case PTT .MARK of 0: begin (*NULL intersection. Inside?*) M:=P INSIDE(PT,PT'); (*we - mark the node,and its neighbors using the algorithm of section V*) MARK(PTT,M); EXPL~RE_AND_MARK(PT,M); end; 1: begin (*inters . Look a t children*) VOL INTER(PTf.SONl,PT'); VQL-INTER(PTl.S'JN2,PT' ); VQL-INTER ( PT1. SON3, PT'); end; otherwise:STOP(*alriady marked 2 or 3*) end; end;

Notice that in the descendant phase of the neighbor finding algorithm, one can mark all the ancestors of the desired node that h1ve a NULL intersection with PT' (if a node is inside a surface, all its ancestors having an empty intersection with the surface are inside it). When the execution of this algorithm is complete for the ~wo trees, one has only to prune them from their nodes marked 3. In spite of the complexity of the neighbor finding procedure, it is clear that this algorithm is more efficient than the previous one, as finding a neighbor only ne eds to simply follow two br anches of a tree, which is faster than traversing a full tree.

CONCLUSIO'l

We have presented a new for representing 3-D objects. method The representation is object-centered and is therefore invariant to rigid motions. It is hierarchical and allows us to think a~out and describe objects at various levels of resolution. Last but not least it is gn efficient tool for performing various boolean operations on objects . We are pursuing the analysis of the corresponding algorithms . It is clear th3t they will be more efficient for trees composed essentially of regular nodes . This implies that the polyhedral approxima t ion described in Section II be adapted to the object sh3pe. It turns out that this is true for convex (or almost convex) objects and therefore we plan to use the prism tree representation on such subparts when necess3r). We are also exploring applications in CAD (combin!ng primitive solids ~) boolean operations) and Robotics (obstacle collision avoidance b) interference checking).

REPERENCES

[1] O.H. Ballard, "Strip Trees: . .!\ Hierarchical Represent'ltion Por Curves", Comm. of the ACM, Vol 24, No 5, 1981 [2] O.D. Pau-::~eras, M. Hebert, P. Mussi and J.D. Boissonnat, "Polyhedral Approximation uf 3-D Objects Without Holes", Computer Graphics and Image Process!ng, in press [3] S. T3nimoto and T. Pavlidis, "A Hierarchical Data Structure for Picture Processing", Computer Graphics and Image Processing, Vol. 4 ~o 2, 1975 [4] C.L. Jackins CJnd S.L. Tanimoto, "Oct-Trees and their Use in Representing 3-D Clbjects", Tec hn. Report No 79-07-D6, Dept. of Comptr. Science, Univ. of Washington, l93CJ [5] H. Samet, "Neighbor Pinding Techniques for Images Represented by Quadtrees", Computer Graphics and Image Processing, Vol. 18, 1982 [6] R.O. Duda and P.E . H3rt, "Pattern Classification and Scene Analysis", Wiley-Interscience, New York, 1973 [7] CJ.D. Paugeras and E. Pauchon, "Measuring the Shape of 3-D Objects, " CVPR-83 [ 8 ] J.D. Bo issonna t, "Representation of Objects by Triangulating Points in 3-D Space," Proc. Of the 6th Int. Conf. On Pattern Recognition, pp.830-832 , Munich, 1992