Debian Codegraph @

apps/nodes/GeneralizedCylinder/Triangulator.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 //
38 // Code for a Generalized Cylinder class. This is not really very
39 // robust or well-designed (or complete or...).
40 //
41
42 #include <cstdio>
43 #include <Inventor/SbLinear.h>
44 #include <Inventor/fields/SoMFInt32.h>
45 #include <Inventor/fields/SoMFVec3f.h>
46
47 #include "Triangulator.h"
48
49
50
51 //**********************************************************************
52 //
53 // Returns FALSE if the two line segments intersect each other at only
54 // one point.
55 // Returns TRUE if they are parallel or if they intersect at a point
56 // external to either line segment.
57 //
58 // Assumes that the four points lie in the y = 0 plane.
59 //
60 //**********************************************************************
61
62 SbBool
63 Triangulator::triangEdgeTest(const SoMFVec3f &coords,
64 int32_t e0p0, int32_t e0p1, int32_t e1p0, int32_t e1p1 )
65 {
66 float x00 = coords[(int) e0p0][0];
67 float x10 = coords[(int) e1p0][0];
68 float z00 = coords[(int) e0p0][2];
69 float z10 = coords[(int) e1p0][2];
70
71 float dx0 = coords[(int) e0p1][0] - x00;
72 float dx1 = coords[(int) e1p1][0] - x10;
73 float dz0 = coords[(int) e0p1][2] - z00;
74 float dz1 = coords[(int) e1p1][2] - z10;
75
76 float diffx = x10 - x00;
77 float diffz = z10 - z00;
78
79 float determ = dx0 * -dz1 - dz0 * -dx1;
80
81 if (determ == 0) // lines are parallel
82 return( TRUE );
83
84 // otherwise, solve for intersection point
85 // first, solve for parametric length on edge 1 from e0p0 to e0p1
86 float parametric_val = (-dz1 * diffx + dx1 * diffz) / determ;
87
88 #define SMALL_VAL 0.00001
89
90 if (parametric_val > 1.0 - SMALL_VAL || parametric_val < SMALL_VAL)
91 // value lies outside line segment
92 return( TRUE );
93
94 // next, solve for parametric length on edge 1 from e1p0 to e1p1
95 parametric_val = (-dz0 * diffx + dx0 * diffz) / determ;
96
97 if (parametric_val > 1.0 - SMALL_VAL || parametric_val < SMALL_VAL)
98 // value lies outside line segment
99 return( TRUE );
100
101 #undef SMALL_VAL
102
103 // otherwise, intersection point lies within both segments
104 return(FALSE);
105 }
106
107 SbBool
108 Triangulator::clockWiseTest( const SoMFVec3f &coords,
109 const SoMFInt32 &indices, int startVert, int numVerts )
110 {
111 // ARE THE COORDS GIVEN BY THIS POLYGON CLOCKWISE ORDERED WHEN VIEWED
112 // FROM ABOVE?
113 // ASSUME THAT ALL THE POINTS LIE IN THE Y=0 PLANE.
114 // How do we know? Well, the total of the interior angles
115 // for an n-sided polygon is:
116 // interior_angles = (PI * n) - (2 * PI)
117 // while:
118 // exterior_angles = (PI * n) + (2 * PI)
119 // So we total up the interior angles, and reverse the
120 // order of the vertices if it is the wrong amount
121 float angle_total = 0;
122 for( int vNum = 0; vNum < numVerts; vNum++ ) {
123 int nextP = (vNum == numVerts - 1) ? 0 : vNum + 1;
124 int prevP = (vNum == 0) ? numVerts - 1 : vNum - 1;
125 SbVec3f nextEdge = coords[(int) indices[startVert + nextP]] -
126 coords[(int) indices[startVert + vNum]];
127 SbVec3f prevEdge = coords[(int) indices[startVert + prevP]] -
128 coords[(int) indices[startVert + vNum]];
129 nextEdge.normalize();
130 prevEdge.normalize();
131
132 // WE WANT ALL ANGLES IN THE SENSE OF ROTATING ABOUT THE
133 // POSITIVE Y AXIS
134 SbVec3f crossProd = prevEdge.cross( nextEdge );
135 if (crossProd[1] > 0.0) {
136 angle_total += acos( prevEdge.dot( nextEdge ) );
137 }
138 else {
139 angle_total += 2 * M_PI - acos( prevEdge.dot( nextEdge ) );
140 }
141 }
142 if ( angle_total > M_PI * numVerts )
143 return FALSE;
144 else
145 return TRUE;
146 }
147
148 //**********************************************************************
149 //
150 // Returns TRUE if the first point lies inside the triangle formed by
151 // the other three.
152 //
153 // Assumes that all of the points lie in the plane y = 0
154 // Assumes that the triangle is ordered clockwise when viewed from above
155 // when travelling in the order: pt0 to pt1 to pt2
156 //
157 // Performs the check by doing a cross product between edges of the
158 // triangle and vectors connecting the vertices to the test point.
159 // If the point is inside the triangle, the cross products are positive.
160 // If any are negative, the point lies outside the trianggle.
161 // We only need to check the y values of the cross product, since the
162 // points lie in a horizontal plane.
163 //**********************************************************************
164
165 SbBool
166 Triangulator::triangInsideTest( const SoMFVec3f &coords,
167 int32_t testPt, int32_t pt0, int32_t pt1, int32_t pt2)
168 {
169 SbVec3f edge0 = coords[(int)pt1] - coords[(int)pt0];
170 SbVec3f edge1 = coords[(int)pt2] - coords[(int)pt1];
171 SbVec3f edge2 = coords[(int)pt0] - coords[(int)pt2];
172
173 SbVec3f ptEdge0 = coords[(int)testPt] - coords[(int)pt0];
174 SbVec3f ptEdge1 = coords[(int)testPt] - coords[(int)pt1];
175 SbVec3f ptEdge2 = coords[(int)testPt] - coords[(int)pt2];
176
177 #define TEENY_VAL 0.0000001
178
179 if ( ptEdge0[2] * edge0[0] - ptEdge0[0] * edge0[2] > TEENY_VAL
180 && ptEdge1[2] * edge1[0] - ptEdge1[0] * edge1[2] > TEENY_VAL
181 && ptEdge2[2] * edge2[0] - ptEdge2[0] * edge2[2] > TEENY_VAL)
182 return( TRUE );
183 else
184 return( FALSE );
185
186 #undef TEENY_VAL
187
188 }
189
190 //**********************************************************************
191 //
192 // 1] assume all points lie in the y = 0 plane
193 // 2] perform triangulation on the projected polygon, copy the order later
194 // 3] for each point, find two others that form a triangle which meets
195 // the following conditions:
196 // a] Doesn't cut through any other edges
197 // b] Any new edges are on the interior
198 //
199 //**********************************************************************
200
201 SbBool
202 Triangulator::triangulate(
203 const SoMFVec3f &coords,
204 const SoMFInt32 &inVals, // indices describing the input
205 // polygons
206 SoMFInt32 &outVals) // indices describing the output
207 // polygons
208 {
209 // CHECK THAT ALL COORDS LIE IN THE y = 0.0 PLANE
210 for( int i = 0; i < coords.getNum(); i++ ){
211 if ( coords[i][1] != 0.0 ) {
212 fprintf(stderr,"Error in triangulation: not all points \n");
213 fprintf(stderr," lie in the y = 0 plane\n");
214 return FALSE;
215 }
216 }
217
218 // COPY THE INPUT INTO THE OUTPUT
219 if ( outVals.getNum() < inVals.getNum() )
220 outVals.insertSpace( 0, inVals.getNum() - outVals.getNum());
221 else if ( outVals.getNum() > inVals.getNum() )
222 outVals.deleteValues( 0, outVals.getNum() - inVals.getNum());
223 outVals = inVals;
224
225
226 int curInd0 = 0;
227 int curNumVerts = 0;
228
229 SbBool got_a_tri, tri_ok, keep_going;
230 SbVec3f edge2, edge0, prevEdge, nextEdge;
231 int ind0, ind1, ind2, test_ind0, test_ind1;
232 int vNum;
233
234 //***** WALK DOWN THE LIST OF POLYS *****
235
236 int shift_count = 0;
237
238 for ( curInd0 = 0; curInd0 < outVals.getNum(); ) {
239 int j;
240 for( j = curInd0, curNumVerts = 0; j < outVals.getNum(); j++ ) {
241 if ( outVals[j] >= 0 )
242 curNumVerts++;
243 else
244 break;
245 }
246
247 // IF ANY THREE CONSECUTIVE POINTS ARE COLINEAR, REMOVE THE
248 // CENTER POINT
249 // Note: we don't have to check that there are three points.
250 // The algorithm will just wind up removing all the points
251 // if there are two or less, or if all the points in the polygon
252 // are colinear.
253 for( vNum = 0; vNum < curNumVerts; vNum++ ) {
254 int nextP = (vNum == curNumVerts - 1) ? 0 : vNum +1;
255 int prevP = (vNum == 0) ? curNumVerts - 1 : vNum - 1;
256 nextEdge = coords[(int) outVals[curInd0 + nextP]] -
257 coords[(int) outVals[curInd0 + vNum]];
258 prevEdge = coords[(int) outVals[curInd0 + prevP]] -
259 coords[(int) outVals[curInd0 + vNum]];
260
261 // CROSS PRODUCT IS ZERO IF THEY ARE CO-LINEAR
262 SbVec3f crossProd = prevEdge.cross( nextEdge );
263
264 #define TEENY_VAL 0.0000001
265 #define IS_COORD_TEENY(a) ( (a)[0] < TEENY_VAL && (a)[1] < TEENY_VAL \
266 && (a)[2] < TEENY_VAL && (a)[0] > -TEENY_VAL \
267 && (a)[1] > -TEENY_VAL && (a)[2] > -TEENY_VAL )
268
269 if (IS_COORD_TEENY( crossProd) ) {
270 // remove the index of this point from the poly
271 outVals.deleteValues( curInd0 + vNum, 1);
272
273 curNumVerts--;
274
275 vNum--; // decrement, because everyone's been shifted
276 // down by 1
277 }
278 #undef TEENY_VAL
279 #undef IS_COORD_TEENY
280 }
281
282 if ( curNumVerts == 0) {
283 // The polygon has no vertices (this could happen because the
284 // whole polygon was colinear and got removed in the step above.)
285 // Remove the '-1' index that signals the end of the polygon.
286 outVals.deleteValues( curInd0, 1 );
287
288 // Do not increment curInd0. By removing the '-1' entry, the
289 // next polygon moves up a slot to have *ITS* first index at
290 // curInd0.
291 }
292 else if ( curNumVerts <= 3) {
293 // Just move on to the next polygon.
294 // (We add an extra 1, because each polygon has a
295 // extra index entry of -1 to indicate the end of the poly
296 curInd0 += curNumVerts + 1;
297 }
298 else {
299
300 // REVERSE ORDER IF NECESSARY
301 if ( !clockWiseTest( coords, outVals, curInd0, curNumVerts) ) {
302 int32_t *outIndices = outVals.startEditing();
303
304 int32_t tempI, early, late;
305 for ( early = 0, late = curNumVerts - 1;
306 early < late; early++, late-- ) {
307 tempI = outIndices[curInd0 + early];
308 outIndices[curInd0 + early] = outIndices[curInd0 + late];
309 outIndices[curInd0 + late] = tempI;
310 }
311
312 outVals.finishEditing();
313 }
314
315 // find a triangle formed by the first point and two other points
316 // The new triangle must satisfy the condition that no new
317 // Edges intersect any already existing edges in the polygon
318 ind0 = curInd0;
319 keep_going = TRUE;
320 for (ind1 = curInd0 + 1, ind2 = curInd0 + 2, got_a_tri = FALSE;
321 got_a_tri == FALSE && keep_going == TRUE; ) {
322 // TEST EACH NEW EDGE AGAINST ALL OTHER EDGES
323 tri_ok = TRUE;
324
325 // make sure ordering of new triangle is clockwise
326 // Normal points down if (edge2 cross edge0)[1] < 0.0
327 edge2 = coords[(int)outVals[ind2]] - coords[(int)outVals[ind0]];
328 edge0 = coords[(int)outVals[ind1]] - coords[(int)outVals[ind0]];
329 if (edge0[0] * edge2[2] - edge2[0] * edge0[2] <= 0.0)
330 tri_ok = FALSE;
331
332 // make sure no other points fall inside the newly formed
333 // triangle
334 if (tri_ok == TRUE) {
335 for( vNum = curInd0; vNum < curInd0 + curNumVerts; vNum++) {
336 if (vNum != ind0 && vNum != ind1 && vNum != ind2) {
337 if ( triangInsideTest(coords,outVals[vNum],outVals[ind0], outVals[ind1], outVals[ind2]))
338 tri_ok = FALSE;
339 }
340 }
341 }
342
343 // edge between ind0 and ind1
344 if (ind1 != curInd0 + 1) {
345 // edge between point0 and point1 is ok, since part of
346 // original polygon
347 for( test_ind0 = curInd0, test_ind1 = curInd0 + 1;
348 tri_ok == TRUE && test_ind0 < curInd0 + curNumVerts;
349 test_ind0++, test_ind1++) {
350 if (test_ind1 == curInd0 + curNumVerts)
351 test_ind1 = curInd0;
352 tri_ok = triangEdgeTest(coords, outVals[ind0], outVals[ind1],
353 outVals[test_ind0], outVals[test_ind1]);
354 }
355 }
356
357 // edge between ind1 and ind2 is part of the original polygon
358 // except when forming tri between v0, v1, and final point
359 if (ind2 != ind1 + 1) {
360 for( test_ind0 = curInd0, test_ind1 = curInd0 + 1;
361 tri_ok == TRUE && test_ind0 < curInd0 + curNumVerts;
362 test_ind0++, test_ind1++) {
363 if (test_ind1 == curInd0 + curNumVerts)
364 test_ind1 = curInd0;
365 tri_ok = triangEdgeTest(coords, outVals[ind1], outVals[ind2],
366 outVals[test_ind0], outVals[test_ind1]);
367 }
368 }
369
370 // edge between ind2 and ind0
371 if (ind2 != curInd0 + curNumVerts -1) {
372 // edge between point0 and last point in poly is ok,since
373 // part of original polygon
374 for( test_ind0 = curInd0, test_ind1 = curInd0 + 1;
375 tri_ok == TRUE && test_ind0 < curInd0 + curNumVerts;
376 test_ind0++, test_ind1++) {
377 if (test_ind1 == curInd0 + curNumVerts)
378 test_ind1 = curInd0;
379 tri_ok = triangEdgeTest(coords, outVals[ind2], outVals[ind0],
380 outVals[test_ind0], outVals[test_ind1]);
381 }
382 }
383 if (tri_ok == TRUE)
384 got_a_tri = TRUE;
385 else {
386 if (ind1 == curInd0 + 1 && ind2 == curInd0 + curNumVerts -1)
387 keep_going = FALSE;
388 ind1++;
389 ind2++;
390 if (ind2 == curInd0 + curNumVerts) {
391 // If none others worked, try the case where the
392 // the points are first, second, and last
393 ind1 = curInd0 + 1;
394 ind2 = curInd0 + curNumVerts - 1;
395 }
396 }
397 }
398
399 if (got_a_tri == FALSE) {
400 // Could not draw a triangle using the first vertex.
401 // Shift all of the vertices in the polygon over and try again
402 shift_count++;
403
404 int32_t *outIndices = outVals.startEditing();
405
406 int32_t temp_index = outIndices[ curInd0 + 0];
407
408 for( vNum = curInd0; vNum < curInd0 + curNumVerts - 1; vNum++ )
409 outIndices[ vNum] = outIndices[ vNum + 1];
410 outIndices[ curInd0 + curNumVerts - 1] = temp_index;
411
412 outVals.finishEditing();
413
414 if (shift_count >= curNumVerts) {
415 printf("Error: could not triangulate this polygon\n");
416 printf("It may look funny!\n");
417 return(FALSE );
418 }
419
420 // Do not increment the value of curInd0.
421 // This will mean that the 'for' loop will repeat the entire
422 // process on this polygon (but THIS time, the indices have
423 // been shifted in order.
424 }
425 else {
426
427 shift_count = 0;
428
429 // Create a new triangle which connects the first point
430 // to these two new points
431 // Add this new triangle to the end of the outVals
432
433 int32_t newIndices[4];
434 newIndices[0] = outVals[ ind0];
435 newIndices[1] = outVals[ ind1];
436 newIndices[2] = outVals[ ind2];
437 newIndices[3] = -1;
438
439 outVals.setValues( outVals.getNum(), 4, newIndices );
440
441 // Make necessary changes to the old polygon
442 if (ind1 == curInd0 + 1 && ind2 == curInd0 + curNumVerts - 1) {
443 // triangle was first, second, and last points
444 // we need to get rid of first point in the current poly
445 outVals.deleteValues( curInd0, 1);
446 curNumVerts--;
447 }
448 else if (ind1 == curInd0 + 1) {
449 // triangle was first three points
450 // we need to get rid of second point
451 outVals.deleteValues( curInd0 + 1, 1 );
452 curNumVerts --;
453 }
454 else if (ind2 == curNumVerts - 1) {
455 // triangle was last three points
456 // we need to get rid of last point
457 outVals.deleteValues( curInd0 + curNumVerts - 1, 1 );
458 curNumVerts --;
459 }
460 else {
461 // we need to break the poly into 2, since we just created
462 // an interior-type triangle
463 // The first polygon will go from ind0 to ind1
464 // and will reside in the original polygon data structure
465 // The second will continue from ind2 back to ind0
466 // and will be added to the end of outVals.
467
468 // FIRST, ADD THE LATTER POLY TO THE END OF outVals...
469
470 int newPolNumVerts = curInd0 + curNumVerts - ind2 + 1;
471
472 // Add an extra slot for the '-1' which signifies end
473 // of polygon
474 int newPolInd0 = outVals.getNum();
475 outVals.insertSpace( newPolInd0, newPolNumVerts + 1 );
476
477 int32_t *outIndices = outVals.startEditing();
478 // Copy the points from ind2 to the end of the poly
479 for ( int j = newPolInd0, vNum = ind2;
480 vNum < curInd0 + curNumVerts; j++, vNum++ ) {
481 outIndices[j] = outIndices[vNum];
482 }
483 // Copy the initial point...
484 outIndices[newPolInd0 + newPolNumVerts - 1]
485 = outIndices[curInd0];
486
487 // Add the -1 to signify the end
488 outIndices[newPolInd0 + newPolNumVerts] = -1;
489
490 outVals.finishEditing();
491
492
493 // NEXT, REMOVE THE LATTER HALF OF THE FIRST POLY...
494 outVals.deleteValues( ind2, newPolNumVerts - 1 );
495
496 // Reduce the num of coords being used from the original
497 // polygon
498 curNumVerts -= newPolNumVerts - 1;
499 }
500 }
501 }
502 }
503
504 return TRUE;
505 }
506