--- title: "Triangulation of 3-D Objects" authors: - "Jean-Daniel Boissonnat" - "Olivier D. Faugeras" doi: "" url: "https://ijcai.org/proceedings/1981/123" pdf: "https://ijcai.org/proceedings/1981/0123.pdf" venue: "Proceedings of the Seventh International Joint Conference on Artificial Intelligence" year: 1981 pages: "658-659" track: "Vision: 3-d" keywords: --- # Triangulation of 3-D Objects Jean-Daniel Boissonnat, Olivier D. Faugeras *Proceedings of the Seventh International Joint Conference on Artificial Intelligence*, pages 658-659. ## Abstract ## Full text ## Introduction In this paper we describe an efficient way of building a polyhedral approximation of a set of point on a surface in 3-D space obtained by a laser range finder. The algorithm is a generalization of an existing algorithm for polygonal approximation of a curve in 2D space [1]. First we recast algorithm ( l J in the setting of graph theory which allows us to generalize it to 3-D. Second we briefly explain how the surface graph which is the basis of the present algorithm can be obtained experimentally. Third we describe the main components of our algorithm. ## Description of the two-dimensional algorithm We will describe the planar algorithm for dis­ crete simple closed curves in the sense of [2 ] . Let A; i=O, ... ,n be a set of points forming a curve C on a discrete grid. For reasons which will become evident later we will not assume that these points are ordered along the curve, that is that A;-1 and Aitl (all indexes are taken modulo n) are the two ne1ghbors of A;. Nonetheless we assume that the structure of the set of points A; is given to us as a graph G=(V,A) where the set of vertexes V is the set of points Ai and A the set of edges. A is a subset of VxV ind1cating neighboring vertexes that is to say neighbors on the curve. The planar algorithm then goes as follows : ## Algorithm 1 : i) pick any two points P and Q on C which are not neighbors. The line PQ is the zero order appro­ ximation of the curve C. ii) find the shortest path from P to Q in G. This separates the curve into two curves C1 and C2 and the graph G into two disconnected subgraphs G1 and Gz. 1ii) process Gl and G2 independently : find the most distant po1nt P; on C; to the line PQ (i=l,2). The polygon PP1QP2 is the first order appro­ ximation to the curve C. iv) we then recursively split the curves C; in two by finding the shortest path in G; from A to P; and iterating step iii) on the corresponding sub­ graphs untils we reach an acceptable error level. In practice of course the need to find shortest paths between vertices in a graph can be avoided in the planar case by the fact that points on a curve can be ordered as a sequence of neighbors. This ## TRIANGULATION of 3-D objects J.D. Boissonnat O.D. Faugeras INRIA Domaine de Voluceau-Rocquencourt BP 105 78153 Le Chesnay Cedex FRANCE unfortunately is not true in higher dimensions and this is why we have cast the well known algorithm 1 into a more general setting which in return will allow us to generalize it in a straightforward man­ ner to the case of surfaces . ## Description of the three-dimensional algorithm These discrete surfaces have been obtained by scanning real objects whit~oul holes (in our case industrial parts) with a laser range finder built at INRIA . The object being positioned in front of the acquisition system, we "raster scan" the cor­ responding vi ew by moving a laser beam from top to bottom and left to ri ght of the object. The posi ­ tion in space of the laser spot is computed by triangulation . The laser range finder system is described elsewere [3J. Right now we have an accuracy of . 75mm at distance of 5m for a depth of field of 75cm and make a mea­ surement every !Oms. We then rotate the object in a controlled manner to "see" all of it . This pro­ vides us with a set of points A; (i=O, . . . ,n) in 3-D space every point having a number of neighbours . Some processing has to take place to obtain this information for all points in every view . Thi s is described elsewhere 14J . We are now able to build from the set of poi nt s A; and their neighbors the corresponding graph G=(V,A) as in the planar case . From there we can design an algorithm which i s almost the same Algorithm 1 and which "almost" works : ## Algorithm 2 : i) pick three points P,Q and Ron the surface S which are not neighbors. The plane PQR i s the zero order approximation of the surface S. ii) find the shortest most pl anar cycle through PQR . Thi s forms a cycle in the graph G which we denote by (PQR) . This cycle separates the surface into two surfaces S1 and s2 and the ~raph G into two disconnected su~9ruphs ~ 1 and Gz (we arbitra r ily as sociate the points of PQR) either to G1 or to G? ) . iii) proress Gl dnd Gz independently : find the most distant po1nt P; of Si to the plane PQR ( i =1 ,2) 0 The polyhedron (PP1Q,QP1R,RP1P,PP2Q,QPzR,RPzP) i s the first order approximation of the surface S. iv) we then recursively split the surfaces Si i=l,2 in three as follows : find the cycle {PPiQ) which does not contain R in Gi . This cycle is cho­ sen in such a way that the path PPi, for example, is the shortest in terms of a set of weights equal to the distances of each point to the bissector of planes PPiR and PPiO· This splits Gi in Gi 1 and Gi 2 . Suppose Gi? is the component of Gj that contains R. Then f1nd the cycle (QPiR) in Gi . This achieves the splitting in three : Gi 1 ,Gi 2 an~ Gi 3 correspond to triangles PPiQ, QPiR and RPiP, respective­ ly (i=l,2). Each subgraph (subsurface) is then processed independently in the same way as in iii) until we reach an acceptable error level. The net result is an approximation of the original surface S by a po­ lyhedron whose faces are triangles . Oth, first and second order approximation of a sphere are shown in f i gure 1. Notice an undesirable fact about Algo­ r1thm 2, namely that once an edge of the polyhedron has been created, it can never disappear even though it may be quite a bad approximation to the surface. We therefore added the following refine­ ment. Remember that to every triangular face PQR of the approximating polyhedron we can associate a subgraph G' of the original graph G or to put it another way a piece S' of the original surface S. To every face PQR we can also associate three neighboring faces PQP1,QRP2 and RPP3 and their cor­ responding graphs G},G2 and G3 as shown in figure 2. To explain the process by which we break edges in the polyhedron let us suppose that we find that the plane defi ned by the triangle PQR is not a good enough approximation of S'. Let M be the most dis­ tant on point on the surface S' to this plane . Let us also suppose that PQP1 and QRP2 are in the same situation and that we associate points M1 and M2 to them. Finally we will assume that triangle RPP3 is a good approximation to S'. Algorithm 2 would proceed as i ndicated in Figu~e 3, Algorithm 3 pro­ ceeds as indicated in Figure 4. Notice that edges PQ and QR have disappeared in the new polyhedral representation. One crucial point is of course how we bu i ld the piece Sl of S {the subgraph G1 of G) that we associate to triangle PMMl, for example . Very simply by considering G" = G UG' which is a connected subgraph of G containing t~e points PQRP1MM1 we can firid the cycle {PMM1) in G" which disconnects it in G1 and G2· G! is the component which does not contain Q. Oth, first and second order approximation of a sphere are shown in Figure 5. ## Conclusion We have developed an al gorithm for approxi­ mation 3-D polyhedral surfaces with triangular faces . These surfaces are first digitized with a laser range finder yielding a set of points on the surface in 3-D space. A graph representation is then built which includes neighboring information for every point. A recursive split of the set of points is then obtained by using the graph repre­ sentation of the surface to find paths between po i nts on the surface. Since we know that graphs have compact machine representations and that there are efficient algorithms for finding a shortest path between two points in a graph we think that our technique is promising . We hope to have results on i ndustrial parts at the time of the conference.