doxygen: intern/boolop tagged
[blender.git] / intern / boolop / intern / BOP_Triangulator.cpp
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file boolop/intern/BOP_Triangulator.cpp
29  *  \ingroup boolopintern
30  */
31
32  
33 #include "BOP_Triangulator.h"
34 #include <iostream>
35 using namespace std;
36
37 void BOP_addFace(BOP_Mesh* mesh, BOP_Faces *faces, BOP_Face* face, BOP_TAG tag);
38 void BOP_splitQuad(BOP_Mesh* mesh, MT_Plane3 plane, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, 
39                                    BOP_Face* triangles[], BOP_Index original);
40 BOP_Index BOP_getTriangleVertex(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4);
41 BOP_Index BOP_getNearestVertex(BOP_Mesh* mesh, BOP_Index u, BOP_Index v1, BOP_Index v2);
42 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5);
43 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index w);
44 void BOP_triangulateC_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 
45                                                         BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5);
46 void BOP_triangulateD_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 
47                                                         BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5);
48
49 /**
50  * Triangulates the face in two new faces by splitting one edge.
51  *
52  *         *
53  *        /|\
54  *       / | \
55  *      /  |  \
56  *     /   |   \
57  *    /    |    \
58  *   *-----x-----*
59  *
60  * @param mesh mesh that contains the faces, edges and vertices
61  * @param faces set of faces that contains face and will contains new faces
62  * @param face input face to be triangulate
63  * @param v vertex index that intersects the edge
64  * @param e relative edge index used to triangulate the face
65  */
66
67
68 void BOP_triangulateA(BOP_Mesh *mesh, BOP_Faces *faces, BOP_Face * face, BOP_Index v, unsigned int e)
69 {
70         BOP_Face *face1, *face2;
71         if (e == 1) {
72                 face1 = new BOP_Face3(face->getVertex(0), v, face->getVertex(2), face->getPlane(),
73                                                           face->getOriginalFace());
74                 face2 = new BOP_Face3(v, face->getVertex(1), face->getVertex(2), face->getPlane(),
75                                                           face->getOriginalFace());
76         }
77         else if (e == 2) {
78                 face1 = new BOP_Face3(face->getVertex(0), face->getVertex(1), v, face->getPlane(),
79                                                           face->getOriginalFace());
80                 face2 = new BOP_Face3(face->getVertex(0), v, face->getVertex(2), face->getPlane(),
81                                                           face->getOriginalFace());
82         }
83         else if (e == 3) {
84                 face1 = new BOP_Face3(face->getVertex(0), face->getVertex(1), v, face->getPlane(),
85                                                           face->getOriginalFace());
86                 face2 = new BOP_Face3(face->getVertex(1), face->getVertex(2), v, face->getPlane(),
87                                                           face->getOriginalFace());
88         }
89         else {
90                 return;
91         }
92         
93         BOP_addFace(mesh, faces, face1, face->getTAG());
94         BOP_addFace(mesh, faces, face2, face->getTAG());
95         face1->setSplit(face->getSplit());
96         face2->setSplit(face->getSplit());
97         
98         face->setTAG(BROKEN);
99         face->freeBBox();
100 }
101
102 /**
103  * Triangulates the face in three new faces by one inner point.
104  *
105  *         *
106  *        / \
107  *       /   \
108  *      /     \
109  *     /   x   \
110  *    /         \
111  *   *-----------*
112  *
113  * @param mesh mesh that contains the faces, edges and vertices
114  * @param faces set of faces that contains face and will contains new faces
115  * @param face input face to be triangulate
116  * @param v vertex index that lays inside face
117  */
118 void BOP_triangulateB(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_Index v)
119 {
120         BOP_Face *face1 = new BOP_Face3(face->getVertex(0), face->getVertex(1), v, face->getPlane(),
121                                                                         face->getOriginalFace());
122         BOP_Face *face2 = new BOP_Face3(face->getVertex(1), face->getVertex(2), v, face->getPlane(),
123                                                                         face->getOriginalFace());
124         BOP_Face *face3 = new BOP_Face3(face->getVertex(2), face->getVertex(0), v, face->getPlane(),
125                                                                         face->getOriginalFace());
126   
127         BOP_addFace(mesh,faces,face1,face->getTAG());
128         BOP_addFace(mesh,faces,face2,face->getTAG());
129         BOP_addFace(mesh,faces,face3,face->getTAG());
130         face1->setSplit(face->getSplit());
131         face2->setSplit(face->getSplit());
132         face3->setSplit(face->getSplit());
133         face->setTAG(BROKEN);
134         face->freeBBox();
135 }
136
137
138 /**
139  * Triangulates the face in five new faces by two inner points.
140  *
141  *         *
142  *        / \
143  *       /   \
144  *      /     \
145  *     /  x x  \
146  *    /         \
147  *   *-----------*
148  *
149  * @param mesh mesh that contains the faces, edges and vertices
150  * @param faces set of faces that contains face and will contains new faces
151  * @param face input face to be triangulate
152  * @param v1 first vertex index that lays inside face
153  * @param v2 second vertex index that lays inside face
154  */
155 void BOP_triangulateC(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_Index v1, BOP_Index v2)
156 {
157         if (!BOP_isInsideCircle(mesh, face->getVertex(0), v1, v2, face->getVertex(1), face->getVertex(2))) {
158                 BOP_triangulateC_split(mesh, faces, face, face->getVertex(0), face->getVertex(1), 
159                                                            face->getVertex(2), v1, v2);
160         }
161         else if (!BOP_isInsideCircle(mesh, face->getVertex(1), v1, v2, face->getVertex(0), face->getVertex(2))) {
162                 BOP_triangulateC_split(mesh, faces, face, face->getVertex(1), face->getVertex(2), 
163                                                            face->getVertex(0), v1, v2);
164         }
165         else if (!BOP_isInsideCircle(mesh, face->getVertex(2), v1, v2, face->getVertex(0), face->getVertex(1))) {
166                 BOP_triangulateC_split(mesh, faces, face, face->getVertex(2), face->getVertex(0), 
167                                                            face->getVertex(1), v1, v2);
168         }
169         else {
170                 BOP_triangulateC_split(mesh, faces, face, face->getVertex(2), face->getVertex(0),
171                                                            face->getVertex(1), v1, v2);
172         }  
173 }
174
175 /**
176  * Triangulates the face (v1,v2,v3) in five new faces by two inner points (v4,v5), where
177  * v1 v4 v5 defines the nice triangle and v4 v5 v2 v3 defines the quad to be tesselated.
178  * @param mesh mesh that contains the faces, edges and vertices
179  * @param faces set of faces that contains face and will contains new faces
180  * @param face input face to be triangulate
181  * @param v1 first vertex index that defines the original triangle
182  * @param v2 second vertex index that defines the original triangle
183  * @param v3 third vertex index that defines the original triangle
184  * @param v4 first vertex index that lays inside face
185  * @param v5 second vertex index that lays inside face
186  */
187 void BOP_triangulateC_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 
188                                                         BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5)
189 {
190         BOP_Index v = BOP_getTriangleVertex(mesh, v1, v2, v4, v5);
191         BOP_Index w = (v == v4 ? v5 : v4);
192         BOP_Face *face1 = new BOP_Face3(v1, v, w, face->getPlane(), face->getOriginalFace());
193         BOP_Face *face2 = new BOP_Face3(v1, v2, v, face->getPlane(), face->getOriginalFace());
194         BOP_Face *face3 = new BOP_Face3(v1, w, v3, face->getPlane(), face->getOriginalFace());
195         
196         // v1 v w defines the nice triangle in the correct order
197         // v1 v2 v defines one lateral triangle in the correct order
198         // v1 w v3 defines the other lateral triangle in the correct order
199         // w v v2 v3 defines the quad in the correct order
200         
201         BOP_addFace(mesh, faces, face1, face->getTAG());
202         BOP_addFace(mesh, faces, face2, face->getTAG());
203         BOP_addFace(mesh, faces, face3, face->getTAG());
204
205         face1->setSplit(face->getSplit());
206         face2->setSplit(face->getSplit());
207         face3->setSplit(face->getSplit());
208         
209         BOP_Face *faces45[2];
210         
211         BOP_splitQuad(mesh, face->getPlane(), v2, v3, w, v, faces45, face->getOriginalFace());
212         BOP_addFace(mesh, faces, faces45[0], face->getTAG());
213         BOP_addFace(mesh, faces, faces45[1], face->getTAG());
214         faces45[0]->setSplit(face->getSplit());
215         faces45[1]->setSplit(face->getSplit());
216         
217         face->setTAG(BROKEN); 
218         face->freeBBox();
219 }
220
221
222 /**
223  * Triangulates the face in three new faces by splitting twice an edge.
224  *
225  *         *
226  *        / \
227  *       /   \
228  *      /     \
229  *     /       \
230  *    /         \
231  *   *---x---x---*
232  *
233  * @param mesh mesh that contains the faces, edges and vertices
234  * @param faces set of faces that contains face and will contains new faces
235  * @param face input face to be triangulate
236  * @param v1 first vertex index that intersects the edge
237  * @param v2 second vertex index that intersects the edge
238  * @param e relative edge index used to triangulate the face
239  */
240 void BOP_triangulateD(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_Index v1, 
241                                           BOP_Index v2, unsigned int e)
242 {
243         if (e == 1) {
244                 BOP_triangulateD_split(mesh, faces, face, face->getVertex(0), face->getVertex(1),
245                                                            face->getVertex(2), v1, v2);
246         }
247         else if (e == 2) {
248                 BOP_triangulateD_split(mesh, faces, face, face->getVertex(1), face->getVertex(2),
249                                                            face->getVertex(0), v1, v2);
250         }
251         else if (e == 3) {
252                 BOP_triangulateD_split(mesh, faces, face, face->getVertex(2), face->getVertex(0),
253                                                            face->getVertex(1), v1, v2);
254         }
255 }
256
257 /**
258  * Triangulates the face (v1,v2,v3) in three new faces by splitting twice an edge.
259  * @param mesh mesh that contains the faces, edges and vertices
260  * @param faces set of faces that contains face and will contains new faces
261  * @param face input face to be triangulate
262  * @param v1 first vertex index that defines the original triangle
263  * @param v2 second vertex index that defines the original triangle
264  * @param v3 third vertex index that defines the original triangle
265  * @param v4 first vertex index that lays on the edge
266  * @param v5 second vertex index that lays on the edge
267  */
268 void BOP_triangulateD_split(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 
269                                                         BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5)
270 {
271         BOP_Index v = BOP_getNearestVertex(mesh, v1, v4, v5);
272         BOP_Index w = (v == v4 ? v5 : v4);
273         BOP_Face *face1 = new BOP_Face3(v1, v, v3, face->getPlane(), face->getOriginalFace());
274         BOP_Face *face2 = new BOP_Face3(v, w, v3, face->getPlane(), face->getOriginalFace());
275         BOP_Face *face3 = new BOP_Face3(w, v2, v3, face->getPlane(), face->getOriginalFace());
276         
277         BOP_addFace(mesh, faces, face1, face->getTAG());
278         BOP_addFace(mesh, faces, face2, face->getTAG());
279         BOP_addFace(mesh, faces, face3, face->getTAG());
280         face1->setSplit(face->getSplit());
281         face2->setSplit(face->getSplit());
282         face3->setSplit(face->getSplit());
283
284         face->setTAG(BROKEN);
285         face->freeBBox();
286 }
287
288
289 /**
290  * Triangulates the face in three new faces by splitting two edges.
291  *
292  *         *
293  *        / \
294  *       /   \
295  *      x     x
296  *     /       \
297  *    /         \
298  *   *-----------*
299  *
300  * @param mesh mesh that contains the faces, edges and vertices
301  * @param faces set of faces that contains face and will contains new faces
302  * @param face input face to be triangulate
303  * @param v1 vertex index that intersects the first edge
304  * @param v1 vertex index that intersects the second edge
305  * @param e1 first relative edge index used to triangulate the face
306  * @param e2 second relative edge index used to triangulate the face
307  */
308 void BOP_triangulateE(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 
309                                           BOP_Index v1, BOP_Index v2, unsigned int e1, unsigned int e2)
310 {
311         // Sort the edges to reduce the cases
312         if (e1 > e2) {
313                 unsigned int aux = e1;
314                 e1 = e2;
315                 e2 = aux;
316                 aux = v1;
317                 v1 = v2;
318                 v2 = aux;
319         }
320         // e1 < e2!
321         BOP_Face *face1;
322         BOP_Face *faces23[2];
323         if (e1 == 1 && e2 == 2) {
324                 // the vertex is 2
325                 face1 = new BOP_Face3(face->getVertex(1), v2, v1, face->getPlane(), 
326                                                           face->getOriginalFace());
327                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(2), face->getVertex(0), v1, v2,
328                                           faces23, face->getOriginalFace());
329         }
330         else if (e1 == 1 && e2 == 3) {
331                 // the vertex is 1
332                 face1 = new BOP_Face3(face->getVertex(0), v1, v2, face->getPlane(), 
333                                                           face->getOriginalFace());
334                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(1), face->getVertex(2), v2, v1, 
335                                           faces23, face->getOriginalFace());
336         }
337         else if (e1 == 2 && e2 == 3) {
338                 // the vertex is 3
339                 face1 = new BOP_Face3(face->getVertex(2), v2, v1, face->getPlane(), 
340                                                           face->getOriginalFace());
341                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(0), face->getVertex(1), v1, v2, 
342                                           faces23, face->getOriginalFace());
343         }
344         else {
345                 return;
346         }
347         
348         BOP_addFace(mesh, faces, face1, face->getTAG());
349         BOP_addFace(mesh, faces, faces23[0], face->getTAG());
350         BOP_addFace(mesh, faces, faces23[1], face->getTAG());
351         face1->setSplit(face->getSplit());
352         faces23[0]->setSplit(face->getSplit());
353         faces23[1]->setSplit(face->getSplit());
354         face->setTAG(BROKEN);
355         face->freeBBox();
356 }
357
358 /**
359  * Triangulates the face in four new faces by one edge and one inner point.
360  *
361  *         *
362  *        / \
363  *       /   \
364  *      x  x  \
365  *     /       \
366  *    /         \
367  *   *-----------*
368  *
369  * @param mesh mesh that contains the faces, edges and vertices
370  * @param faces set of faces that contains face and will contains new faces
371  * @param face input face to be triangulate
372  * @param v1 vertex index that lays inside face
373  * @param v2 vertex index that intersects the edge
374  * @param e relative edge index used to triangulate the face
375  */
376 void BOP_triangulateF(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, 
377                                           BOP_Index v1, BOP_Index v2, unsigned int e)
378 {
379         BOP_Face *faces12[2];
380         BOP_Face *faces34[2];
381         if (e == 1) {      
382                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(2), face->getVertex(0), v2, v1,
383                                           faces12, face->getOriginalFace());
384                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(1), face->getVertex(2), v1, v2,
385                                           faces34, face->getOriginalFace());
386         }
387         else if (e == 2) {
388                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(0), face->getVertex(1), v2, v1,
389                                           faces12, face->getOriginalFace());
390                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(2), face->getVertex(0), v1, v2,
391                                           faces34, face->getOriginalFace());
392         }
393         else if (e==3) {
394                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(1), face->getVertex(2), v2, v1,
395                                           faces12, face->getOriginalFace());
396                 BOP_splitQuad(mesh, face->getPlane(), face->getVertex(0), face->getVertex(1), v1, v2,
397                                           faces34, face->getOriginalFace());
398         }
399         else {
400                 return;
401         }
402         
403         BOP_addFace(mesh, faces, faces12[0], face->getTAG());
404         BOP_addFace(mesh, faces, faces12[1], face->getTAG());
405         BOP_addFace(mesh, faces, faces34[0], face->getTAG());
406         BOP_addFace(mesh, faces, faces34[1], face->getTAG());
407         faces12[0]->setSplit(face->getSplit());
408         faces12[1]->setSplit(face->getSplit());
409         faces34[0]->setSplit(face->getSplit());
410         faces34[1]->setSplit(face->getSplit());
411         
412         face->setTAG(BROKEN);
413         face->freeBBox();
414 }
415
416 /**
417  * Adds the new face into the faces set and the mesh and sets it a new tag.
418  * @param mesh mesh that contains the faces, edges and vertices
419  * @param faces set of faces that contains oldFace
420  * @param face input face to be added
421  * @param tag tag of the new face
422  */
423 void BOP_addFace(BOP_Mesh* mesh, BOP_Faces* faces, BOP_Face* face, BOP_TAG tag)
424 {
425         BOP_Index av1 = face->getVertex(0);
426         BOP_Index av2 = face->getVertex(1);
427         BOP_Index av3 = face->getVertex(2);
428
429         /*
430          * Before adding a new face to the face list, be sure it's not
431          * already there.  Duplicate faces have been found to cause at
432          * least two instances of infinite loops.  Also, some faces are
433          * created which have the same vertex twice.  Don't add these either.
434          *
435          * When someone has more time to look into this issue, it's possible
436          * this code may be removed again.
437          */
438         if( av1==av2 || av2==av3  || av3==av1 ) return;
439
440         for(unsigned int idxFace=0;idxFace<faces->size();idxFace++) {
441                 BOP_Face *faceA = (*faces)[idxFace];
442                 BOP_Index bv1 = faceA->getVertex(0);
443                 BOP_Index bv2 = faceA->getVertex(1);
444                 BOP_Index bv3 = faceA->getVertex(2);
445
446                 if( ( av1==bv1 && av2==bv2 && av3==bv3 ) ||
447                 ( av1==bv1 && av2==bv3 && av3==bv2 ) ||
448                 ( av1==bv2 && av2==bv1 && av3==bv3 ) ||
449                 ( av1==bv2 && av2==bv3 && av3==bv1 ) ||
450                 ( av1==bv3 && av2==bv2 && av3==bv1 ) ||
451                 ( av1==bv3 && av2==bv1 && av3==bv3 ) )
452                         return;
453         }
454
455         face->setTAG(tag);    
456         faces->push_back(face);
457         mesh->addFace(face);
458 }
459
460 /**
461  * Computes the best quad triangulation.
462  * @param mesh mesh that contains the faces, edges and vertices
463  * @param plane plane used to create the news faces
464  * @param v1 first vertex index
465  * @param v2 second vertex index
466  * @param v3 third vertex index
467  * @param v4 fourth vertex index
468  * @param triangles array of faces where the new two faces will be saved
469  * @param original face index to the new faces
470  */
471 void BOP_splitQuad(BOP_Mesh* mesh, MT_Plane3 plane, BOP_Index v1, BOP_Index v2, 
472                                    BOP_Index v3, BOP_Index v4, BOP_Face* triangles[], BOP_Index original)
473 {
474         MT_Point3 p1 = mesh->getVertex(v1)->getPoint();
475         MT_Point3 p2 = mesh->getVertex(v2)->getPoint();
476         MT_Point3 p3 = mesh->getVertex(v3)->getPoint();
477         MT_Point3 p4 = mesh->getVertex(v4)->getPoint();
478         
479         int res = BOP_concave(p1,p2,p3,p4);
480         
481         if (res==0) {
482                 MT_Plane3 plane1(p1, p2, p3);
483                 MT_Plane3 plane2(p1, p3, p4);
484                 
485                 if (BOP_isInsideCircle(mesh, v1, v2, v4, v3) && 
486                         BOP_orientation(plane1, plane) &&
487                         BOP_orientation(plane2, plane)) {
488                         triangles[0] = new BOP_Face3(v1, v2, v3, plane, original);
489                         triangles[1] = new BOP_Face3(v1, v3, v4, plane, original);
490                 }
491                 else {
492                         triangles[0] = new BOP_Face3(v1, v2, v4, plane, original);
493                         triangles[1] = new BOP_Face3(v2, v3, v4, plane, original);
494                 }
495         }
496         else if (res==-1) {
497                 triangles[0] = new BOP_Face3(v1, v2, v4, plane, original);
498                 triangles[1] = new BOP_Face3(v2, v3, v4, plane, original);
499         }
500         else {
501                 triangles[0] = new BOP_Face3(v1, v2, v3, plane, original);
502                 triangles[1] = new BOP_Face3(v1, v3, v4, plane, original);
503         }
504 }
505
506 /**
507  * Returns the vertex (v3 or v4) that splits the quad (v1,v2,v3,v4) in the best pair of triangles.
508  * @param mesh mesh that contains the faces, edges and vertices
509  * @param v1 first vertex index
510  * @param v2 second vertex index
511  * @param v3 third vertex index
512  * @param v4 fourth vertex index
513  * @return v3 if the best split triangles are (v1,v2,v3) and (v1,v3,v4), v4 otherwise
514  */
515 BOP_Index BOP_getTriangleVertex(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4)
516 {
517         if (BOP_isInsideCircle(mesh, v1, v2, v4, v3)) {
518                 return v3;
519         }
520         return v4; 
521 }
522
523 /**
524  * Returns which of vertex v1 or v2 is nearest to u.
525  * @param mesh mesh that contains the faces, edges and vertices
526  * @param u reference vertex index
527  * @param v1 first vertex index
528  * @param v2 second vertex index
529  * @return the nearest vertex index
530  */
531 BOP_Index BOP_getNearestVertex(BOP_Mesh* mesh, BOP_Index u, BOP_Index v1, BOP_Index v2)
532 {
533         MT_Point3 q = mesh->getVertex(u)->getPoint();
534         MT_Point3 p1 = mesh->getVertex(v1)->getPoint();
535         MT_Point3 p2 = mesh->getVertex(v2)->getPoint();
536         if (BOP_comp(q.distance(p1), q.distance(p2)) > 0) return v2;
537         else return v1;
538 }
539
540 /**
541  * Computes if vertexs v4 and v5 are not inside the circle defined by v1,v2,v3 (seems to be a nice triangle)
542  * @param mesh mesh that contains the faces, edges and vertices
543  * @param v1 first vertex index
544  * @param v2 second vertex index
545  * @param v3 third vertex index
546  * @param v4 fourth vertex index
547  * @param v5 five vertex index
548  * @return if v1,v2,v3 defines a nice triangle against v4,v5
549  */
550 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, BOP_Index v5)
551 {
552         return BOP_isInsideCircle(mesh->getVertex(v1)->getPoint(),
553                                                           mesh->getVertex(v2)->getPoint(),
554                                                           mesh->getVertex(v3)->getPoint(),
555                                                           mesh->getVertex(v4)->getPoint(),
556                                                           mesh->getVertex(v5)->getPoint());
557 }
558
559 /**
560  * Computes if vertex w is not inside the circle defined by v1,v2,v3 (seems to be a nice triangle)
561  * @param mesh mesh that contains the faces, edges and vertices
562  * @param v1 first vertex index
563  * @param v2 second vertex index
564  * @param v3 third vertex index
565  * @param w fourth vertex index
566  * @return if v1,v2,v3 defines a nice triangle against w
567  */
568 bool BOP_isInsideCircle(BOP_Mesh* mesh, BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index w) 
569 {
570         return BOP_isInsideCircle(mesh->getVertex(v1)->getPoint(),
571                                                           mesh->getVertex(v2)->getPoint(),
572                                                           mesh->getVertex(v3)->getPoint(),
573                                                           mesh->getVertex(w)->getPoint());
574 }