1 /***********************************************************************/
2 /* Open Visualization Data Explorer */
3 /* (C) Copyright IBM Corp. 1989,1999 */
4 /* ALL RIGHTS RESERVED */
5 /* This code licensed under the */
6 /* "IBM PUBLIC LICENSE - Open Visualization Data Explorer" */
7 /***********************************************************************/
8
9 #include <dxconfig.h>
10
11 #if defined(HAVE_STRING_H)
12 #include <string.h>
13 #endif
14
15 #define TRIANGULATE_ALWAYS 1
16 #define TRIANGULATE_DEBUG 1
17 #define TRIANGULATE_MAIN 0
18 #define FIX_TRIANGLE_ORIENTATION 1
19
20
21 #include <stdio.h>
22 #include <math.h>
23 #include <dx/dx.h>
24 #include "_normals.h"
25 #include "_newtri.h"
26
27
28 #ifndef TRUE
29 #define TRUE 1
30 #define FALSE 0
31 #endif
32
33 #define LOCAL_LOOPS 256
34
35 /*
36 * To make this more efficient declare a register float _det_ in any
37 * routine that uses this macro.
38 */
39
40 static double _det_;
41 #define DetSign(p0,p1,p2)\
42 (\
43 _det_ = (double)(p0.u * ((double)p1.v - p2.v)) +\
44 (double)(p1.u * ((double)p2.v - p0.v)) +\
45 (double)(p2.u * ((double)p0.v - p1.v)),\
46 _det_ < (float) 0.0 ? -1 : _det_ > (float) 0.0 ? 1 : 0\
47 )
48
49 #define Determinant(p0,p1,p2)\
50 ( p0.u * (p1.v - p2.v) + p1.u * (p2.v - p0.v) + p2.u * (p0.v - p1.v))
51
52
53 static void FlipLoop (Loop *loops);
54 static int IntersectsEdge (Loop *loops, BVertex *p, BVertex *q);
55 static void LoopSign (Loop *lp);
56 static void LoopBBox (Loop *lp);
57 static int PointInTri (Point2 p, Point2 plast, Point2 pnext,
58 Point2 v0, Point2 v1, Point2 v2, int tsign);
59 static void ProjectPoints (Point *normal, float *vertices,
60 int nloops, Loop *loops, int nDim);
61 static int AddLinkNested (Loop *loops, BVertex *p, BVertex *spares,
62 int *nvert, BVertex **first, BVertex **end);
63 static int AnyInsideNested (TreeNode holes, BVertex *p0, BVertex *p1,
64 BVertex *p2, int psign);
65 static Error TriangulateNestedLoops (int nloops, Loop *loops,
66 float *vertices,
67 Point *normal, int np,
68 Triangle *tptr, int *rntri, int nDim);
69 static Error InitLoopsNested (int *, Loop **, int);
70 static void LoopSignNested (Loop *lp);
71 static int AddLink (Loop *loops, BVertex *p, BVertex **spares,
72 int *nvert, BVertex **first, BVertex **end);
73 static int AnyInside (Loop *loops, BVertex *p0, BVertex *p1,
74 BVertex *p2, int psign);
75 static Error InitLoops (int *nloops, Loop **loops, BVertex *spares,
76 int np);
77 static Error TriangulateLoops (int nloops, Loop *loops, float *vertices,
78 Point *normal, int np,
79 Triangle *tptr, int *rntri, int nDim);
80 static Error AssignTreeLevel(TreeNode, int);
81 static Error TriangulateLoopWithHoles(TreeNode, int *, Triangle *);
82
83
84
85 #if 0
86 void ShowLoop(BVertex *);
87 #endif
88
89 static int srprint = 0;
90 #if TRIANGULATE_DEBUG
91 #define srprintf if (srprint) printf
92 #else
93 #define srprintf
94 #endif
95
96
97 int
_dxf_TriangleCount(int * f,int nf,int * l,int nl,int * e,int ne)98 _dxf_TriangleCount (int *f, int nf, int *l, int nl, int *e, int ne)
99 {
100 FLEP in;
101
102 in.faces = f;
103 in.loops = l;
104 in.edges = e;
105 in.nfaces = nf;
106 in.nloops = nl;
107 in.nedges = ne;
108
109 return (_dxf__TriangleCount (&in));
110 }
111
112
113 int
_dxf__TriangleCount(FLEP * in)114 _dxf__TriangleCount (FLEP *in)
115 {
116 FLEP lin;
117 int f;
118 int l, ls, le;
119 int es, ee;
120 int ntri = 0;
121 int nvert;
122
123 lin = *in;
124
125 for (f = 0; f < lin.nfaces; f++)
126 {
127 nvert = 0;
128
129 ls = lin.faces[f];
130 le = f < lin.nfaces - 1 ? lin.faces[f + 1] : lin.nloops;
131
132 for (l = ls; l < le; l++)
133 {
134 es = lin.loops[l];
135 ee = l < lin.nloops - 1 ? lin.loops[l + 1] : lin.nedges;
136 nvert += ee - es;
137 }
138
139 nvert += 2 * (le - ls);
140 ntri += nvert - 2;
141 }
142
143 return (ntri);
144 }
145
146
147
148 Error
_dxfTriangulateField(Field field)149 _dxfTriangulateField(Field field)
150 {
151 Error ret = ERROR;
152 Array af, al, ae, ap, an;
153 int *f, *l, *e;
154 int nf, nl, ne, np;
155 float *p;
156 Vector *n;
157 Triangle *tri = NULL;
158 int ntri;
159 int newtri = 0;
160 Array arr;
161 int size;
162 int i, *map = NULL;
163 Array sA=NULL, dA=NULL;
164 char *name;
165 int nDim;
166
167 af = (Array) DXGetComponentValue (field, "faces");
168 al = (Array) DXGetComponentValue (field, "loops");
169 ae = (Array) DXGetComponentValue (field, "edges");
170 ap = (Array) DXGetComponentValue (field, "positions");
171
172 if (af == NULL || al == NULL || ae == NULL || ap == NULL)
173 {
174 DXSetError (ERROR_BAD_PARAMETER,
175 "missing at least one of faces/loops/edges/positions");
176 goto cleanup;
177 }
178
179 f = (int *) DXGetArrayData (af);
180 l = (int *) DXGetArrayData (al);
181 e = (int *) DXGetArrayData (ae);
182 p = (float *) DXGetArrayData (ap);
183
184 DXGetArrayInfo (af, &nf, NULL, NULL, NULL, NULL);
185 DXGetArrayInfo (al, &nl, NULL, NULL, NULL, NULL);
186 DXGetArrayInfo (ae, &ne, NULL, NULL, NULL, NULL);
187 DXGetArrayInfo (ap, &np, NULL, NULL, NULL, &nDim);
188
189 if (nDim == 2 || nDim == 3)
190 {
191 an = (Array) DXGetComponentValue(field, "normals");
192 if (! an)
193 {
194 an = _dxf_FLE_Normals(f, nf, l, nl, e, ne, p, nDim);
195 if (! an)
196 goto cleanup;
197
198 if (! DXSetComponentValue(field, "normals", (Object)an))
199 {
200 DXDelete((Object)an);
201 goto cleanup;
202 }
203
204 if (! DXSetStringAttribute((Object)an, "dep", "faces"))
205 goto cleanup;
206 }
207
208 n = (Vector *) DXGetArrayData(an);
209 }
210 else
211 {
212 DXSetError(ERROR_DATA_INVALID,
213 "Faces/Loops/Edges vertices must be 2 or 3D");
214 goto cleanup;
215 }
216
217 ntri = _dxf_TriangleCount (f, nf, l, nl, e, ne);
218 size = ntri * sizeof (Triangle);
219 tri = (Triangle *) DXAllocateLocal (size);
220 if (tri == NULL)
221 goto cleanup;
222
223 map = (int *)DXAllocate(nf*sizeof(int));
224 if (! map)
225 goto cleanup;
226
227 if (! _dxf_TriangulateFLEP (f, nf, l, nl, e, ne,
228 p, np, n, tri, &newtri, map, nDim))
229 goto cleanup;
230
231 if (newtri == 0)
232 {
233 ret = OK;
234 goto cleanup;
235 }
236
237 #define STRING(_x) ((Object) DXNewString (_x))
238 arr = DXNewArray (TYPE_INT, CATEGORY_REAL, 1, 3);
239 if (arr == NULL)
240 goto cleanup;
241 if (! DXAddArrayData (arr, 0, newtri, (Pointer) tri))
242 goto cleanup;
243 if (! DXSetComponentValue (field, "connections", (Object) arr))
244 goto cleanup;
245 arr = NULL;
246 if (! DXSetComponentAttribute (field, "connections", "element type",
247 STRING ("triangles")))
248 goto cleanup;
249
250 i = 0;
251 while (NULL != (sA = (Array)DXGetEnumeratedComponentValue(field, i++, &name)))
252 {
253 if (! strcmp(name, "invalid faces"))
254 {
255 int i, j, k;
256 InvalidComponentHandle ifaces, itris;
257
258 ifaces = DXCreateInvalidComponentHandle((Object)field,
259 NULL, "faces");
260 itris = DXCreateInvalidComponentHandle((Object)field,
261 NULL, "connections");
262
263 if (! ifaces || ! itris)
264 goto cleanup;
265
266 DXSetAllValid(itris);
267
268 for (i = k = 0; i < nf; i++)
269 {
270 if (DXIsElementInvalid(ifaces, i))
271 {
272 for (j = 0; j < map[i]; j++)
273 DXSetElementInvalid(itris, k++);
274 }
275 else
276 k += map[i];
277 }
278
279 if (! DXSaveInvalidComponent(field, itris))
280 {
281 DXFreeInvalidComponentHandle(itris);
282 DXFreeInvalidComponentHandle(ifaces);
283 goto cleanup;
284 }
285
286 DXFreeInvalidComponentHandle(itris);
287 DXFreeInvalidComponentHandle(ifaces);
288 }
289 else
290 {
291 int itemSize;
292 Type type;
293 Category cat;
294 int rank, shape[30];
295 Object attr = DXGetComponentAttribute(field, name, "dep");
296
297 dA = NULL;
298
299 if (! attr)
300 continue;
301
302 if (strcmp(DXGetString((String)attr), "faces"))
303 continue;
304
305 DXGetArrayInfo(sA, NULL, &type, &cat, &rank, shape);
306 itemSize = DXGetItemSize(sA);
307
308 if (DXQueryConstantArray(sA, NULL, NULL))
309 {
310 dA = (Array)DXNewConstantArrayV(newtri,
311 DXGetConstantArrayData(sA), type, cat, rank, shape);
312 if (! dA)
313 goto cleanup;
314 }
315 else
316 {
317 int i, j;
318 char *srcPtr;
319 char *dstPtr;
320
321 dA = DXNewArrayV(type, cat, rank, shape);
322 if (! dA)
323 goto cleanup;
324
325 if (! DXAddArrayData(dA, 0, newtri, NULL))
326 goto cleanup;
327
328 dstPtr = (char *)DXGetArrayData(dA);
329 srcPtr = (char *)DXGetArrayData(sA);
330
331 for (i = 0; i < nf; i++)
332 {
333 for (j = 0; j < map[i]; j++)
334 {
335 memcpy(dstPtr, srcPtr, itemSize);
336 dstPtr += itemSize;
337 }
338 srcPtr += itemSize;
339 }
340 }
341
342 if (! DXSetComponentValue(field, name, (Object)dA))
343 goto cleanup;
344 dA = NULL;
345
346 if (! DXSetComponentAttribute(field, name, "dep",
347 (Object)DXNewString("connections")))
348 goto cleanup;
349
350 }
351 }
352
353 /*
354 * Get rid of the old stuff
355 */
356
357 DXDeleteComponent (field, "invalid faces");
358 DXDeleteComponent (field, "faces");
359 DXDeleteComponent (field, "loops");
360 DXDeleteComponent (field, "edges");
361 if (! DXEndField (field))
362 goto cleanup;
363
364 ret = OK;
365
366 cleanup:
367 if (newtri == 0 && ret == OK)
368 {
369 char *name;
370
371 while (DXGetEnumeratedComponentValue (field, 0, &name))
372 DXDeleteComponent (field, name);
373 }
374
375 DXDelete((Object) dA);
376 DXFree ((Pointer) tri);
377 DXFree ((Pointer) map);
378 return (ret);
379 }
380
381 Error
_dxf_TriangulateFLEP(int * f,int nf,int * l,int nl,int * e,int ne,float * p,int np,Vector * normal,Triangle * tris,int * ntri,int * map,int nDim)382 _dxf_TriangulateFLEP (int *f, int nf, int *l, int nl, int *e, int ne,
383 float *p, int np, Vector *normal, Triangle *tris, int *ntri,
384 int *map, int nDim)
385 {
386 FLEP in;
387
388 in.faces = f;
389 in.loops = l;
390 in.edges = e;
391 in.points = p;
392 in.map = map;
393 in.nfaces = nf;
394 in.nloops = nl;
395 in.nedges = ne;
396 in.npoints = np;
397 in.nDim = nDim;
398
399 return (_dxf__TriangulateFLEP (&in, normal, tris, ntri, NULL));
400 }
401
402
403 Error
_dxf__TriangulateFLEP(FLEP * in,Vector * normal,Triangle * tris,int * ntri,FLEP * valid)404 _dxf__TriangulateFLEP (FLEP *in, Vector *normal, Triangle *tris, int *ntri,
405 FLEP *valid)
406 {
407 Vector tri_direction;
408 int temp, k;
409 float dir;
410 FLEP lin;
411 FLEP lvalid= {NULL, NULL};
412 Error ret = ERROR;
413 Loop *loops = NULL;
414 int size;
415 Triangle *ltris, *tmp_tris;
416 int lntri=0;
417 int ftri;
418 int f;
419 int l, ls, le;
420 int es, ee;
421 int skips;
422
423 lin = *in;
424 if (valid)
425 lvalid = *valid;
426
427 size = lin.nloops * sizeof (Loop);
428 loops = (Loop *) DXAllocateLocal (size);
429 if (loops == NULL)
430 goto cleanup;
431
432 ltris = tris;
433 lntri = 0;
434
435 for (f = 0; f < lin.nfaces; f++)
436 {
437 if (valid && ! lvalid.faces[f])
438 continue;
439
440 skips = 0;
441 ls = lin.faces[f];
442 le = f < lin.nfaces - 1 ? lin.faces[f + 1] : lin.nloops;
443
444 memset (loops, 0, (le - ls) * sizeof (Loop));
445
446 for (l = ls; l < le; l++)
447 {
448 if (valid && ! lvalid.loops[l])
449 {
450 skips++;
451 continue;
452 }
453
454 es = lin.loops[l];
455 ee = l < lin.nloops - 1 ? lin.loops[l + 1] : lin.nedges;
456
457 loops[l - ls - skips].nvert = ee - es;
458 loops[l - ls - skips].vids = lin.edges + es;
459 }
460
461 if (getenv("DX_SIMPLE_LOOPS"))
462 {
463 if (! TriangulateLoops (le - ls - skips, loops, lin.points,
464 (normal) ? normal + f : NULL, lin.npoints, ltris, &ftri, lin.nDim))
465 {
466 #if TRIANGULATE_ALWAYS
467 if (DXGetError () == ERROR_INTERNAL)
468 DXResetError ();
469 else
470 #endif
471 goto cleanup;
472 }
473 }
474 else
475 {
476 if (! TriangulateNestedLoops (le - ls - skips, loops, lin.points,
477 (normal) ? normal + f : NULL, lin.npoints, ltris, &ftri, lin.nDim))
478 {
479 #if TRIANGULATE_ALWAYS
480 if (DXGetError () == ERROR_INTERNAL)
481 DXResetError ();
482 else
483 #endif
484 goto cleanup;
485 }
486 }
487
488
489
490
491 #if FIX_TRIANGLE_ORIENTATION
492 for (k=0, tmp_tris=ltris; k<ftri; k++) {
493 if (lin.nDim == 2)
494 {
495 float *p = lin.points + 2*tmp_tris->p;
496 float *q = lin.points + 2*tmp_tris->q;
497 float *r = lin.points + 2*tmp_tris->r;
498 float x0 = q[0] - p[0];
499 float y0 = q[1] - p[1];
500 float x1 = r[0] - q[0];
501 float y1 = r[1] - q[1];
502
503 tri_direction.x = 0.0;
504 tri_direction.y = 0.0;
505 tri_direction.z = x0*y1 - x1*y0;
506 }
507 else
508 {
509 Point *pts = (Point *)lin.points;
510
511 tri_direction = DXCross(DXSub(pts[tmp_tris->q], pts[tmp_tris->p]),
512 DXSub(pts[tmp_tris->r], pts[tmp_tris->q]));
513
514 }
515
516 dir = DXDot(tri_direction, normal[f]);
517
518 if (dir < 0) {
519 temp = tmp_tris->r;
520 tmp_tris->r = tmp_tris->q;
521 tmp_tris->q = temp;
522 }
523 tmp_tris++;
524 }
525
526 #endif
527
528
529 lntri += ftri;
530 ltris += ftri;
531 in->map[f] = ftri;
532 }
533
534 ret = OK;
535
536 cleanup:
537 if (ret == OK && ntri)
538 *ntri = lntri;
539
540 DXFree ((Pointer) loops);
541 return (ret);
542 }
543
544
545 #define Shift \
546 { \
547 p0 = p1; \
548 p1 = p2; \
549 p2 = p2->next; \
550 continue; \
551 }
552
553 #define EmitTri012 \
554 { \
555 i0 = p0->id; \
556 i1 = p1->id; \
557 i2 = p2->id; \
558 if (i0 != i1 && i0 != i2 && i1 != i2) \
559 { \
560 tptr->p = p0->id; \
561 tptr->q = p1->id; \
562 tptr->r = p2->id; \
563 tptr++; \
564 ntri++; \
565 } \
566 p0->next = p2; \
567 p2->prev = p0; \
568 }
569
570
571 /*
572 * $$$$$ NOTE: This code, as did the previous version from Jarek et al,
573 * $$$$$ assumes that the first loop is the outer loop and that
574 * $$$$$ all subsequent loops are holes _dxf_inside of it.
575 */
576
577 #if 0
578 static int dumpLoop = 0;
579 static int loopLimit = 99999;
580
581 static void
582 DumpLoop(BVertex *p0)
583 {
584 FILE *fd;
585 int n = 0;
586 BVertex *b0, *b1;
587
588 fd = fopen("dump.out", "w");
589
590 b0 = b1 = p0;
591 do
592 {
593 n++;
594 b0 = b0->next;
595 } while (b0 != b1);
596 fprintf(fd, "%d\n", n);
597 b0 = b1 = p0;
598 do
599 {
600 fprintf(fd, " %d\n", b0->id);
601 b0 = b0->next;
602 } while (b0 != b1);
603
604 fclose(fd);
605 }
606 #endif
607
608
609 static Error
TraverseTree(TreeNode node,int * rntri,Triangle * tbase)610 TraverseTree(TreeNode node, int *rntri, Triangle *tbase)
611 {
612 TreeNode child;
613
614 if (! node)
615 return OK;
616
617 if ((node->level & 0x1) != 0)
618 {
619 /*
620 * Then its an outer contour
621 */
622 if (! TriangulateLoopWithHoles(node, rntri, tbase))
623 goto error;
624 }
625
626 for (child = node->children; child; child = child->sibling)
627 if (! TraverseTree(child, rntri, tbase))
628 goto error;
629
630 return OK;
631
632 error:
633 return ERROR;
634 }
635
636 static Error
TriangulateLoopWithHoles(TreeNode node,int * rntri,Triangle * tbase)637 TriangulateLoopWithHoles(TreeNode node, int *rntri, Triangle *tbase)
638 {
639 Loop *loop = node->loop;
640 int nvert = loop->nvert, not_done;
641 BVertex *p0 = loop->base, *p1=NULL, *p2=NULL;
642 BVertex *end = NULL;
643 BVertex *first = NULL;
644 int i0, i1, i2;
645 int nholes;
646 TreeNode holes;
647 BVertex *spares;
648 int n;
649 int tsign, psign = loop->sign;
650 Triangle *tptr = tbase + *rntri;
651 int ntri = *rntri;
652 int pass = 0;
653 Loop *l;
654
655 if (! psign)
656 return OK;
657
658 /*
659 * Get spares required for linking. While you're at it, make sure
660 * the holes are oriented opposite to the outer contour. Also - create
661 * linked list of loops
662 */
663 node->loop->next = node->loop->prev = node->loop;
664 for (holes = node->children, nholes = 0; holes; holes = holes->sibling)
665 {
666 nholes ++;
667 holes->loop->next = node->loop->next;
668 node->loop->next = holes->loop;
669 if (holes->loop->sign == psign)
670 FlipLoop(holes->loop);
671 }
672
673 /*
674 * and doubly link the list
675 */
676 l = node->loop;
677 do {
678 l->next->prev = l;
679 } while ((l = l->next) != node->loop);
680
681 spares = (BVertex *)DXAllocateZero(nholes * 2 * sizeof(BVertex));
682 if (! spares)
683 goto error;
684
685 n = 0;
686 while (1)
687 {
688 do
689 {
690 not_done = 0;
691 pass ++;
692
693 if (first != NULL)
694 p0 = first;
695
696 if (first == end)
697 end = NULL;
698
699 while (p0->pass < pass && p0 != end)
700 {
701 p0->pass = pass;
702
703 p1 = p0->next;
704 p2 = p1->next;
705
706 if (!p0->tried)
707 {
708 srprintf ("DXTri: %2d %2d %2d (%3d)",
709 p0->id, p1->id, p2->id, nvert);
710
711 if (p0->id == p1->id || p1->id == p2->id ||
712 (tsign = DetSign(p0->pos, p1->pos, p2->pos)) == 0)
713 {
714 /*
715 * degenerate triangle. eliminate p1 from the loop.
716 */
717 p0->next = p2;
718 p2->prev = p0;
719 not_done++;
720 nvert--;
721 }
722 else if (tsign != psign ||
723 AnyInsideNested (node->children, p0, p1, p2, psign))
724 {
725 p0->tried = 1;
726 }
727 else
728 {
729 not_done++;
730 p0->prev->tried = 0;
731 if (p0 == first)
732 first = first->prev;
733 if (p2 == end)
734 {
735 if (end == first)
736 end = NULL;
737 else
738 end = end->next;
739 }
740
741 if (p1 == first)
742 first = p0;
743
744 EmitTri012;
745 nvert--;
746
747 while (nvert > 2)
748 {
749 p1 = p0->next;
750 p2 = p1->next;
751
752 if (DetSign(p0->pos, p1->pos, p2->pos) == 0)
753 {
754 p0->next = p2;
755 p2->prev = p0;
756 if (p1 == first)
757 first = p0;
758 nvert --;
759 }
760 else
761 break;
762 }
763 }
764 }
765
766 p0 = p0->next;
767 }
768
769 } while (not_done && nvert >= 3);
770
771 if (! AddLinkNested(node->loop, p0, spares+2*n, &nvert, &first, &end))
772 break;
773
774 n ++;
775 }
776
777 if (nvert == 3)
778 EmitTri012;
779
780 *rntri = ntri;
781
782 DXFree((Pointer)spares);
783 return OK;
784
785 error:
786 DXFree((Pointer)spares);
787 return ERROR;
788 }
789
790 static TreeNode CreateNestingTree(int nLoops, Loop *loops);
791
TriangulateNestedLoops(int nloops,Loop * loops,float * vertices,Point * normal,int np,Triangle * tptr,int * rntri,int nDim)792 static Error TriangulateNestedLoops (int nloops, Loop *loops, float *vertices,
793 Point *normal, int np,
794 Triangle *tptr, int *rntri, int nDim)
795 {
796 Error ret = ERROR; /* return status */
797 BVertex *vbase = NULL; /* base of list blocks */
798 int nvert; /* total vertex count */
799 int size; /* size temporary */
800 int i, j;
801 BVertex *bptr;
802 TreeNode tree = NULL;
803
804 if (rntri)
805 *rntri = 0;
806
807 for (nvert = 0, i = 0; i < nloops; i++)
808 nvert += loops[i].nvert;
809
810 size = nvert * sizeof (BVertex);
811 vbase = (BVertex *) DXAllocateLocal (size);
812 if (vbase == NULL)
813 goto error;
814
815 /*
816 * For each loop:
817 * Initialize its boundary vertex list as a circularly linked list.
818 * For now we'll just put in the vertex id. We'll fill in the
819 * vertex positions later. We separate this for two reasons. First,
820 * it involves random accessing and we don't want to guarantee that
821 * we destroy any savings we get from the PVS's line cache, and
822 * second we want to use tight loops for the projection from 3-space
823 * to 2-space.
824 */
825 bptr = vbase;
826 for (j = 0; j < nloops; j++)
827 {
828 loops[j].base = bptr;
829
830 for (i = 0, bptr = loops[j].base; i < loops[j].nvert; i++, bptr++)
831 {
832 bptr->next = bptr + 1;
833 bptr->prev = bptr - 1;
834 bptr->lp = loops + j;
835 bptr->id = *loops[j].vids++;
836 }
837
838 /*
839 * Circularly link the list
840 */
841
842 loops[j].base[loops[j].nvert - 1].next = loops[j].base;
843 loops[j].base->prev = loops[j].base + (loops[j].nvert - 1);
844 }
845
846 ProjectPoints (normal, vertices, nloops, loops, nDim);
847
848 /*
849 * Get rid of colinear loops and loops with fewer than 3 points and
850 * link all of the others together.
851 */
852
853 if (! InitLoopsNested (&nloops, &loops, np))
854 goto error;
855
856 tree = CreateNestingTree(nloops, loops);
857 if (! tree)
858 goto error;
859
860 AssignTreeLevel(tree, 0);
861
862 if (! TraverseTree(tree, rntri, tptr))
863 goto error;
864
865 ret = OK;
866
867 error:
868 /* cleanup */
869 DXFree((Pointer)tree);
870 DXFree ((Pointer) vbase);
871 return (ret);
872 }
873
874
875 #if 1
876 static int nShow = 0;
877
878 void
ShowLoop(BVertex * first)879 ShowLoop(BVertex *first)
880 {
881 int i, n;
882 BVertex *p0;
883 char buf[32];
884 FILE *foo;
885
886 sprintf(buf, "bad%d.dx", nShow++);
887
888 foo = fopen(buf, "w");
889 if ( foo )
890 {
891 n = 0;
892 p0 = first;
893 do
894 {
895 n++;
896 } while ((p0 = p0->next) != first);
897
898 fprintf(foo,
899 "object \"faces\" class array type int rank 0 items 1 data follows\n0\nattribute \"ref\" string \"loops\"\n");
900
901 fprintf(foo,
902 "object \"loops\" class array type int rank 0 items 1 data follows\n0\nattribute \"ref\" string \"edges\"\n");
903
904 fprintf(foo,
905 "object \"edges\" class array type int rank 0 items %d data follows\n", n);
906 for (i = 0; i < n; i++)
907 fprintf(foo, "%d\n", i);
908 fprintf(foo, "attribute \"ref\" string \"positions\"\n");
909
910 fprintf(foo,
911 "object \"positions\" class array type float rank 1 shape 3 items %d data follows\n", n);
912 for (i = 0, p0 = first; i < n; i++, p0 = p0->next)
913 fprintf(foo, "%f %f 0\n", p0->pos.u, p0->pos.v);
914
915 fprintf(foo,
916 "object \"data\" class array type int rank 0 items %d data follows\n", n);
917 for (i = 0, p0 = first; i < n; i++, p0 = p0->next)
918 fprintf(foo, "%d\n", p0->id);
919 fprintf(foo, "attribute \"dep\" string \"positions\"\n");
920
921 fprintf(foo, "object \"fle\" class field\n");
922 fprintf(foo, " component \"faces\" \"faces\"\n");
923 fprintf(foo, " component \"loops\" \"loops\"\n");
924 fprintf(foo, " component \"edges\" \"edges\"\n");
925 fprintf(foo, " component \"positions\" \"positions\"\n");
926 fprintf(foo, " component \"data\" \"data\"\n");
927 fprintf(foo, "end\n");
928
929 fclose(foo);
930 }
931
932 }
933 #endif
934
935 /*
936 * Figure out what the smallest dimension of the polygon is, e.g. the
937 * dimension that contains the portion of the normal vector with the
938 * largest magnitude. Now copy in the vertices, projecting them from
939 * 3D space to the appropriate 2D space.
940 */
941
ProjectPoints(Point * normal,float * vertices,int nloops,Loop * loops,int nDim)942 static void ProjectPoints (Point *normal, float *vertices,
943 int nloops, Loop *loops, int nDim)
944 {
945 Point lnormal;
946 int elim;
947 int i, j;
948 BVertex *bptr;
949
950 if (nDim == 2)
951 {
952 float *pptr;
953 Loop *loop;
954
955 for (j = 0, loop = loops; j < nloops; j++, loop++)
956 for (i = 0, bptr = loop->base; i < loop->nvert; i++, bptr++)
957 {
958 pptr = vertices + 2*bptr->id;
959 bptr->pos.u = pptr[0];
960 bptr->pos.v = pptr[1];
961 }
962 }
963 else
964 {
965 Point *vptr = (Point *)vertices;
966 Point *pptr;
967 Loop loop;
968
969 lnormal = *normal;
970 if (lnormal.x < (float) 0.0) lnormal.x = -lnormal.x;
971 if (lnormal.y < (float) 0.0) lnormal.y = -lnormal.y;
972 if (lnormal.z < (float) 0.0) lnormal.z = -lnormal.z;
973
974 elim = 0;
975 if (lnormal.y > lnormal.x)
976 elim = 1;
977 if (lnormal.z > (elim == 0 ? lnormal.x : lnormal.y))
978 elim = 2;
979
980 for (j = 0; j < nloops; j++)
981 {
982 loop = loops[j];
983
984 switch (elim)
985 {
986 case 0: /* get rid of X */
987 for (i = 0, bptr = loop.base; i < loop.nvert; i++, bptr++)
988 {
989 pptr = vptr + bptr->id;
990 bptr->pos.u = pptr->y;
991 bptr->pos.v = pptr->z;
992 }
993 break;
994
995 case 1: /* get rid of Y */
996 for (i = 0, bptr = loop.base; i < loop.nvert; i++, bptr++)
997 {
998 pptr = vptr + bptr->id;
999 bptr->pos.u = pptr->x;
1000 bptr->pos.v = pptr->z;
1001 }
1002 break;
1003
1004 case 2: /* get rid of Z */
1005 for (i = 0, bptr = loop.base; i < loop.nvert; i++, bptr++)
1006 {
1007 pptr = vptr + bptr->id;
1008 bptr->pos.u = pptr->x;
1009 bptr->pos.v = pptr->y;
1010 }
1011 break;
1012 }
1013 }
1014 }
1015 }
1016
1017
1018 static PseudoKey
HashPoint(Key k)1019 HashPoint(Key k)
1020 {
1021 PseudoKey pk;
1022
1023 Point2 *p = &((*(BVertex **)k)->pos);
1024 pk = (PseudoKey)(*(int *)((&p->u))*17 + *((int *)(&p->v))*53);
1025
1026 return pk;
1027 }
1028
1029 static int
ComparePoint(Key k0,Key k1)1030 ComparePoint(Key k0, Key k1)
1031 {
1032 Point2 *p0 = &((*(BVertex **)k0)->pos);
1033 Point2 *p1 = &((*(BVertex **)k1)->pos);
1034
1035 return ! (p0->u == p1->u && p0->v == p1->v);
1036 }
1037
1038
1039 #define A_INSIDE_B 1
1040 #define B_INSIDE_A 2
1041 #define A_OUTSIDE_B 3
1042 #define AB_CROSS 4
1043 #define AB_DISJOINT 5
1044 #define AB_INDETERMINATE 6
1045
1046
1047 static Error
_CheckNesting(Loop * A,Loop * B,int * result)1048 _CheckNesting(Loop *A, Loop *B, int *result)
1049 {
1050 BVertex *i, *o;
1051 int j, knt, inside = 0, outside = 0;
1052 float ui, uo0, uo1;
1053 float vi, vo0, vo1;
1054 float u, t;
1055 float mU, MU, mV, MV;
1056
1057 /*
1058 * Determine the overlap region
1059 */
1060 if (A->box.ll.u > B->box.ll.u) mU = A->box.ll.u;
1061 else mU = B->box.ll.u;
1062 if (A->box.ll.v > B->box.ll.v) mV = A->box.ll.v;
1063 else mV = B->box.ll.v;
1064 if (A->box.ur.v < B->box.ur.v) MU = A->box.ur.u;
1065 else MU = B->box.ur.u;
1066 if (A->box.ur.v < B->box.ur.v) MV = A->box.ur.v;
1067 else MV = B->box.ur.v;
1068
1069
1070 for (i = A->base, j = 0; j < A->nvert; j++, i = i->next)
1071 {
1072 ui = i->pos.u;
1073 vi = i->pos.v;
1074
1075 if (ui < mU || ui > MU || vi < mV || vi > MV)
1076 {
1077 outside ++;
1078 continue;
1079 }
1080
1081 o = B->base;
1082 knt = 0;
1083 do
1084 {
1085 uo1 = o->pos.u;
1086 uo0 = o->next->pos.u;
1087 vo1 = o->pos.v;
1088 vo0 = o->next->pos.v;
1089
1090 /*
1091 * Orient the edge endpoints so that vo0 <= vo1
1092 */
1093 if (vo0 > vo1)
1094 {
1095 t = vo0; vo0 = vo1; vo1 = t;
1096 t = uo0; uo0 = uo1; uo1 = t;
1097 }
1098
1099 /*
1100 * if the edge is horizontal, forget it.
1101 */
1102 if (vo0 == vo1)
1103 continue;
1104
1105 /*
1106 * if both endpoints of the edge lie to the left of
1107 * the point, forget it.
1108 */
1109 if (ui > uo0 && ui > uo1)
1110 continue;
1111
1112 /*
1113 * If the edge lies entirely above or below the point,
1114 * forget it.
1115 */
1116 if (vi > vo1 || vi < vo0)
1117 continue;
1118
1119 /*
1120 * If the v exactly coincides with the upper endpoint, count
1121 * it a cross. If it exactly coincides with the lower, skip it.
1122 */
1123 if (vi == vo1 && ui < uo1)
1124 {
1125 knt ++;
1126 continue;
1127 }
1128 else if (vi == vo0)
1129 continue;
1130
1131 /*
1132 * Get the edge value of u at v = vi. If thats to the right
1133 * of the test point, count it a cross.
1134 */
1135 t = (vi - vo0) / (vo1 - vo0);
1136 u = uo0 + t*(uo1 - uo0);
1137 if (u > ui)
1138 {
1139 knt ++;
1140 continue;
1141 }
1142 }
1143 while ((o = o->next) != B->base);
1144
1145 if (knt & 0x1)
1146 inside ++;
1147 else
1148 outside ++;
1149 }
1150
1151 if (! inside && ! outside)
1152 {
1153 DXSetError(ERROR_INTERNAL, "empty loop?");
1154 return ERROR;
1155 }
1156
1157 if (inside && !outside)
1158 *result = A_INSIDE_B;
1159 else if (!inside && outside)
1160 *result = A_OUTSIDE_B;
1161 else if (!inside && !outside)
1162 *result = AB_CROSS;
1163
1164 return OK;
1165 }
1166
1167 static Error
_CheckNestingBoxes(Loop * A,Loop * B,int * result)1168 _CheckNestingBoxes(Loop *A, Loop *B, int *result)
1169 {
1170 if (A->box.ll.u > B->box.ur.u) *result = AB_DISJOINT;
1171 else if (A->box.ll.v > B->box.ur.v) *result = AB_DISJOINT;
1172 else if (A->box.ur.u < B->box.ll.u) *result = AB_DISJOINT;
1173 else if (A->box.ur.v < B->box.ll.v) *result = AB_DISJOINT;
1174 else *result = AB_INDETERMINATE;
1175
1176 return OK;
1177 }
1178
1179
1180 static Error
CheckNesting(Loop * A,Loop * B,int * result)1181 CheckNesting(Loop *A, Loop *B, int *result)
1182 {
1183 /*
1184 * If boxes don't overlap, loops are disjoint
1185 */
1186 if (! _CheckNestingBoxes(A, B, result))
1187 return ERROR;
1188 else if (*result == AB_DISJOINT)
1189 return OK;
1190
1191 /*
1192 * Check points of A against B loop. If all are inside,
1193 * then A is inside B and we're done. Also - if points
1194 * of A are both inside and outside B, then we're also done.
1195 */
1196 if (!_CheckNesting(A, B, result))
1197 return ERROR;
1198
1199 if (*result == A_INSIDE_B || *result == AB_CROSS)
1200 return OK;
1201
1202 /*
1203 * All points of A are outside B. Check to see if A is nested
1204 * inside B or whether they are disjoint.
1205 */
1206 if (! _CheckNesting(B, A, result))
1207 return ERROR;
1208
1209 if (*result == A_INSIDE_B)
1210 {
1211 *result = B_INSIDE_A;
1212 return OK;
1213 }
1214 else if (*result == AB_CROSS)
1215 {
1216 DXSetError(ERROR_INTERNAL, "B x A but A !x B");
1217 return ERROR;
1218 }
1219 else
1220 {
1221 *result = AB_DISJOINT;
1222 return OK;
1223 }
1224 }
1225
1226 static Error
InsertTreeNode(TreeNode current,TreeNode new)1227 InsertTreeNode(TreeNode current, TreeNode new)
1228 {
1229 TreeNode last = NULL, next;
1230
1231 last = NULL;
1232 next = current->children;
1233 while (next)
1234 {
1235 int ab;
1236
1237 if (! CheckNesting(new->loop, next->loop, &ab))
1238 return ERROR;
1239
1240 if (ab == A_INSIDE_B)
1241 {
1242 if (new->children)
1243 {
1244 DXSetError(ERROR_INTERNAL, "topology error");
1245 return ERROR;
1246 }
1247 else
1248 return InsertTreeNode(next, new);
1249 }
1250 else if (ab == B_INSIDE_A)
1251 {
1252 TreeNode tmp = next;
1253
1254 if (last)
1255 last->sibling = next->sibling;
1256 else
1257 current->children = next->sibling;
1258
1259 next = next->sibling;
1260
1261 tmp->sibling = new->children;
1262 new->children = tmp;
1263 }
1264 else if (ab == AB_CROSS)
1265 {
1266 DXSetError(ERROR_INTERNAL, "topology error");
1267 return ERROR;
1268 }
1269 else
1270 {
1271 last = next;
1272 next = next->sibling;
1273 }
1274 }
1275
1276 new->sibling = current->children;
1277 current->children = new;
1278
1279 return OK;
1280 }
1281
1282 static Error
AssignTreeLevel(TreeNode node,int level)1283 AssignTreeLevel(TreeNode node, int level)
1284 {
1285 TreeNode next;
1286
1287 if (! node)
1288 return OK;
1289
1290 node->level = level;
1291
1292 for (next = node->children; next; next = next->sibling)
1293 {
1294 if (! AssignTreeLevel(next, level+1))
1295 return ERROR;
1296 }
1297
1298 return OK;
1299 }
1300
1301 static TreeNode
CreateNestingTree(int nLoops,Loop * loops)1302 CreateNestingTree(int nLoops, Loop *loops)
1303 {
1304 int i;
1305 struct treenode *root;
1306 struct treenode *nodes;
1307
1308 nodes = (struct treenode *)DXAllocate((nLoops+1) * sizeof(struct treenode));
1309 if (! nodes)
1310 goto error;
1311
1312 root = nodes + 0;
1313
1314 root->sibling = NULL;
1315 root->children = NULL;
1316 root->nChildren = 0;
1317 root->loop = NULL;
1318
1319 for (i = 0; i < nLoops; i++)
1320 {
1321 /*
1322 * remember that forst node is the root
1323 */
1324 TreeNode node = nodes + (i+1);
1325
1326 node->loop = loops + i;
1327 node->sibling = NULL;
1328 node->children = NULL;
1329 node->nChildren = 0;
1330
1331 if (! InsertTreeNode(root, node))
1332 goto error;
1333 }
1334
1335 return root;
1336
1337 error:
1338 DXFree((Pointer)nodes);
1339 return NULL;
1340 }
1341
1342 static Error
InitLoopsNested(int * nloopsPtr,Loop ** loopsPtr,int np)1343 InitLoopsNested (int *nloopsPtr, Loop **loopsPtr, int np)
1344 {
1345 int nloops = *nloopsPtr;
1346 Loop *loops = *loopsPtr;
1347 int i, j;
1348 BVertex *p0, *p1, *p2;
1349 int maxLoops = *nloopsPtr;
1350 HashTable ptHash =
1351 DXCreateHash(sizeof(BVertex *), HashPoint, ComparePoint);
1352 if (! ptHash)
1353 goto error;
1354
1355 for (j = 0; j < nloops; j++)
1356 {
1357 p0 = loops[j].base;
1358 do
1359 {
1360 BVertex **q;
1361 q = (BVertex **)DXQueryHashElement(ptHash, (Key)&p0);
1362 if (q)
1363 p0->id = (*q)->id;
1364 else
1365 if (! DXInsertHashElement(ptHash, (Element)&p0))
1366 goto error;
1367 p0 = p0->next;
1368 }
1369 while (p0 != loops[j].base);
1370 }
1371
1372 DXDestroyHash(ptHash);
1373 ptHash = NULL;
1374
1375 for (j = 0; j < nloops; j++)
1376 {
1377 p0 = loops[j].base;
1378 do
1379 {
1380 for (p1 = loops[j].base; p1 != p0; p1 = p1->next)
1381 if (p1->id == p0->id)
1382 {
1383 if (p0->next == p1)
1384 {
1385 p0->next = p1->next;
1386 p0->next->prev = p0;
1387 loops[j].nvert -= 1;
1388 }
1389 else
1390 {
1391 int p1loop, p0loop;
1392
1393 for (p1loop = 0, p2 = p1; p2 != p0; p2 = p2->next, p1loop++);
1394 p0loop = loops[j].nvert - p1loop;
1395
1396 p2 = p0->prev;
1397
1398 p0->prev = p1->prev;
1399 p0->prev->next = p0;
1400
1401 p1->prev = p2;
1402 p1->prev->next = p1;
1403
1404 if (p0loop > 2 && p1loop <= 2)
1405 {
1406 loops[j].nvert = p0loop;
1407 loops[j].base = p0;
1408 }
1409 else if (p0loop <= 2 && p1loop > 2)
1410 {
1411 loops[j].nvert = p1loop;
1412 loops[j].base = p1;
1413 }
1414 else if (p0loop > 2 && p1loop > 2)
1415 {
1416 loops[j].nvert = p0loop;
1417 loops[j].base = p0;
1418
1419 if (nloops == maxLoops)
1420 {
1421 Loop *newloops = (Loop *)
1422 DXAllocate(2*maxLoops*sizeof(Loop));
1423 if (! newloops)
1424 goto error;
1425
1426 memcpy(newloops, loops, nloops*sizeof(Loop));
1427
1428 if (loops != *loopsPtr)
1429 DXFree((Pointer)loops);
1430
1431 loops = newloops;
1432
1433 maxLoops *= 2;
1434 }
1435
1436 loops[nloops] = loops[j];
1437
1438 loops[nloops].base = p1;
1439 loops[nloops].nvert = p1loop;
1440 nloops ++;
1441
1442 /*
1443 * If its the outer loop, then one may lie inside
1444 * the other. If so, its a hole. Otherwise,
1445 * it should be handled as a single outer loop.
1446 * So check.
1447 */
1448 }
1449 else
1450 loops[j].nvert = 0;
1451 }
1452
1453 p1 = p0 = loops[j].base;
1454 break;
1455 }
1456
1457 p0 = p0->next;
1458
1459 } while (p0 != loops[j].base);
1460 }
1461
1462 for (j = 0; j < nloops; j++)
1463 {
1464 p0 = loops[j].base;
1465 if (p0)
1466 {
1467 int nv = loops[j].nvert;
1468
1469 if (nv)
1470 {
1471 do
1472 {
1473 if (nv > 3 && p0->id == p0->next->next->id)
1474 {
1475 nv -= 2;
1476 loops[j].base = p0;
1477 p0->next = p0->next->next->next;
1478 p0->next->prev = p0;
1479 }
1480 p0 = p0->next;
1481 } while (p0 != loops[j].base);
1482
1483 loops[j].nvert = nv;
1484 }
1485 }
1486 }
1487
1488 for (i = j = 0; j < nloops; j++)
1489 if (loops[j].nvert != 0)
1490 {
1491 if (j != 0)
1492 loops[i] = loops[j];
1493 i++;
1494 }
1495
1496 nloops = i;
1497
1498 for (i = 0; i < nloops; i++)
1499 {
1500 p0 = loops[i].base;
1501 do
1502 {
1503 p0->tried = 0;
1504 p0->pass = 0;
1505 p0 = p0->next;
1506 } while (p0 != loops[i].base);
1507 }
1508
1509 *nloopsPtr = nloops;
1510 *loopsPtr = loops;
1511
1512 for (j = 0; j < nloops; j++)
1513 {
1514 LoopBBox (loops + j);
1515 LoopSignNested (loops + j);
1516 }
1517
1518 for (j = 0; j < nloops; j++)
1519 if (loops[j].sign == 0 || loops[j].nvert < 3)
1520 loops[j].merged = TRUE;
1521
1522 return OK;
1523
1524 error:
1525 if (ptHash)
1526 DXDestroyHash(ptHash);
1527 return ERROR;
1528 }
1529
1530
FlipLoop(Loop * loops)1531 static void FlipLoop (Loop *loops)
1532 {
1533 Loop loop;
1534 int i;
1535 BVertex *curr;
1536 BVertex *next;
1537
1538 loop = *loops;
1539
1540 for (i = 0, curr = loop.base; i < loop.nvert; i++, curr = next)
1541 {
1542 next = curr->next;
1543 curr->next = curr->prev;
1544 curr->prev = next;
1545 }
1546
1547 loops->sign *= -1;
1548 }
1549
1550
1551 static void
LoopBBox(Loop * lp)1552 LoopBBox (Loop *lp)
1553 {
1554 BVertex *p;
1555 Point2 pos;
1556 Point2 ll;
1557 Point2 ur;
1558
1559 if (! lp->base)
1560 {
1561 lp->box.ll.u = lp->box.ll.v = 0.0;
1562 lp->box.ur.u = lp->box.ur.v = 0.0;
1563 return;
1564 }
1565
1566 ur = ll = lp->base->pos;
1567 for (p = lp->base->next; p != lp->base; p = p->next)
1568 {
1569 pos = p->pos;
1570
1571 if (pos.u < ll.u) ll.u = pos.u;
1572 if (pos.u > ur.u) ur.u = pos.u;
1573
1574 if (pos.v < ll.v) ll.v = pos.v;
1575 if (pos.v > ur.v) ur.v = pos.v;
1576 }
1577
1578 lp->box.ll = ll;
1579 lp->box.ur = ur;
1580
1581 return;
1582 }
1583
LoopSignNested(Loop * lp)1584 static void LoopSignNested (Loop *lp)
1585 {
1586 BVertex *p;
1587 BVertex *p0, *p1, *p2;
1588 BVertex *tmp;
1589 Point2 pos;
1590 Point2 ll; /* the lower left */
1591 int psign;
1592
1593 /*
1594 * Find the "leftmost bottom-most" vertex for use as our starting midpoint.
1595 * While were at it, find the rest of the bounding box too.
1596 */
1597
1598 p = lp->base;
1599 p1 = lp->base;
1600 ll = p1->pos;
1601 for (p = lp->base->next; p != lp->base; p = p->next)
1602 {
1603 pos = p->pos;
1604
1605 if (pos.u < ll.u)
1606 {
1607 ll.u = pos.u;
1608 p1 = p;
1609 }
1610 else if (pos.u == ll.u && pos.v < ll.v)
1611 {
1612 ll.v = pos.v;
1613 p1 = p;
1614 }
1615 }
1616
1617 /*
1618 * Walk around the polygon until we either get a non-zero sign for the
1619 * determinant or until we've come all the way around. If we do get
1620 * a sign then that is the characteristic direction for the polygon
1621 * and we can return it immediately. Otherwise all of the points in
1622 * the polygon are colinear.
1623 */
1624
1625 tmp = p1;
1626 p0 = p1->prev;
1627 p2 = p1->next;
1628
1629 do
1630 {
1631 psign = DetSign (p0->pos, p1->pos, p2->pos);
1632 if (psign)
1633 {
1634 lp->sign = psign;
1635 return;
1636 }
1637
1638 p0 = p1;
1639 p1 = p2;
1640 p2 = p2->next;
1641
1642 } while (p2 != tmp);
1643
1644 lp->sign = 0;
1645 }
1646
1647
1648 #define CheckPoint()\
1649 {\
1650 ip = p->id;\
1651 if (ip == i0 || ip == i1 || ip == i2)\
1652 continue;\
1653 ppos = p->pos;\
1654 if (ppos.u < tribox.ll.u || ppos.v < tribox.ll.v ||\
1655 ppos.u > tribox.ur.u || ppos.v > tribox.ur.v)\
1656 continue;\
1657 if (PointInTri (ppos, p->prev->pos, p->next->pos, v0, v1, v2, psign))\
1658 return (TRUE);\
1659 }
1660
AnyInsideNested(TreeNode holes,BVertex * p0,BVertex * p1,BVertex * p2,int psign)1661 static int AnyInsideNested (TreeNode holes, BVertex *p0,
1662 BVertex *p1, BVertex *p2, int psign)
1663 {
1664 BVertex *p;
1665 int i0, i1, i2;
1666 Point2 v0, v1, v2;
1667 Point2 ppos;
1668 BBox tribox, loopbox;
1669 int ip;
1670 Loop *lp;
1671 int i;
1672 int nvert;
1673 TreeNode hole;
1674
1675 i0 = p0->id; i1 = p1->id; i2 = p2->id;
1676 v0 = p0->pos; v1 = p1->pos; v2 = p2->pos;
1677
1678 tribox.ll.u = v0.u<v1.u ? v0.u<v2.u ? v0.u : v2.u : v1.u<v2.u ? v1.u : v2.u;
1679 tribox.ll.v = v0.v<v1.v ? v0.v<v2.v ? v0.v : v2.v : v1.v<v2.v ? v1.v : v2.v;
1680 tribox.ur.u = v0.u>v1.u ? v0.u>v2.u ? v0.u : v2.u : v1.u>v2.u ? v1.u : v2.u;
1681 tribox.ur.v = v0.v>v1.v ? v0.v>v2.v ? v0.v : v2.v : v1.v>v2.v ? v1.v : v2.v;
1682
1683 /*
1684 * Check the boundary
1685 */
1686
1687 for (p = p2->next; p != p0; p = p->next)
1688 CheckPoint ();
1689
1690 /*
1691 * Check the other loops.
1692 */
1693
1694 for (hole = holes; hole; hole = hole->sibling)
1695 {
1696 lp = hole->loop;
1697 loopbox = lp->box;
1698 if (loopbox.ur.u < tribox.ll.u || loopbox.ll.u > tribox.ur.u ||
1699 loopbox.ur.v < tribox.ll.v || loopbox.ll.v > tribox.ur.v)
1700 continue;
1701
1702 for (i = 0, nvert = lp->nvert, p = lp->base;
1703 i < nvert;
1704 i++, p = p->next)
1705 CheckPoint ();
1706 }
1707
1708 return (FALSE);
1709 }
1710
1711
1712 #if 0
1713 foreach point P on the boundary
1714 foreach unconnected loop L
1715 foreach point Q on an unconnected loop
1716 if P or Q has been split then continue
1717 make the edge PQ
1718 foreach vertex V on the boundary and all loops
1719 W = V->next;
1720 if (PQ intersects VW)
1721 continue on to next Q or P
1722 no intersections so connect PQ
1723 could not form a link return FALSE
1724
1725 NOTE: the above has been changed slightly. It now finds
1726 the first inside loop visible from some point on the outside
1727 loop. Then of all the possible pairs between these two,
1728 it chooses the closest.
1729
1730 #endif
1731
1732 static int
AddLinkNested(Loop * loops,BVertex * p0,BVertex * spares,int * nvert,BVertex ** first,BVertex ** end)1733 AddLinkNested(Loop *loops, BVertex *p0, BVertex *spares, int *nvert,
1734 BVertex **first, BVertex **end)
1735 {
1736 BVertex *sp;
1737 BVertex *p, *q;
1738 BVertex *np, *nq;
1739 Loop *lp;
1740 int i, maxi;
1741 int j, maxj;
1742 int k;
1743
1744 sp = spares;
1745
1746 for (j = 0, maxj = *nvert, p = p0; j < maxj; j++, p = p->next)
1747 {
1748 for (k = 1, lp = loops->next; lp != loops; lp = lp->next, k++)
1749 {
1750 if (lp->merged)
1751 continue;
1752
1753 for (i = 0, maxi = lp->nvert, q = lp->base;
1754 i < maxi;
1755 i++, q = q->next)
1756 {
1757 if (p->id == q->id)
1758 continue;
1759
1760 if (IntersectsEdge (loops, p, q))
1761 continue;
1762
1763 srprintf ("LINKING at %2d - %2d\n", p->id, q->id);
1764 np = sp++;
1765 nq = sp++;
1766 *np = *p;
1767 *nq = *q;
1768
1769 np->pass = 0;
1770 nq->pass = 0;
1771
1772 np->next = q;
1773 nq->next = p;
1774 np->prev = p->prev;
1775 nq->prev = q->prev;
1776 p->prev->next = np;
1777 q->prev->next = nq;
1778 p->prev = nq;
1779 q->prev = np;
1780
1781 lp->merged = TRUE;
1782 lp->next->prev = lp->prev;
1783 lp->prev->next = lp->next;
1784 lp->next = NULL;
1785 lp->prev = NULL;
1786
1787 *nvert += lp->nvert + 2;
1788 loops->nvert = *nvert;
1789 loops->base = p0;
1790
1791 np->prev->tried = 0;
1792 np->tried = 0;
1793
1794 *first = np->prev;
1795 *end = nq->next;
1796
1797 return (TRUE);
1798
1799 }
1800 }
1801 }
1802
1803 return FALSE;
1804 }
1805
1806 /*
1807 * If the edge we are looking at contains one of the link points then
1808 * just move on. If we find that a vertex has been replicated then we
1809 * assume an intersection since if we don't we run the risk of introducing
1810 * a loop that runs counter to the real direction of the boundary.
1811 * Next we check the rotations of the triangles formed by connecting the
1812 * endpoints of the segments. Basically, if we find that both triangles
1813 * formed using one segment as the base rotate the same way then there
1814 * isn't an intersection.
1815 */
1816
1817 #define CheckEdge(_V)\
1818 {\
1819 v1 = v0->next;\
1820 srprintf (" %2d - %2d: ", v0->id, v1->id);\
1821 if (v0 == _V || v1 == _V)\
1822 {\
1823 srprintf ("point match\n");\
1824 continue;\
1825 }\
1826 v0i = v0->id;\
1827 v1i = v1->id;\
1828 if (pid == v0i || pid == v1i || qid == v0i || qid == v1i)\
1829 {\
1830 srprintf ("ID MATCH\n");\
1831 return (TRUE);\
1832 }\
1833 v0os = v0->pos;\
1834 v1os = v1->pos;\
1835 if ((v0os.u < pqbox.ll.u && v1os.u < pqbox.ll.u) ||\
1836 (v0os.v < pqbox.ll.v && v1os.v < pqbox.ll.v) ||\
1837 (v0os.u > pqbox.ur.u && v1os.u > pqbox.ur.u) ||\
1838 (v0os.v > pqbox.ur.v && v1os.v > pqbox.ur.v))\
1839 {\
1840 srprintf ("no bbox overlap\n");\
1841 continue;\
1842 }\
1843 abc = DetSign (ppos, qpos, v0os);\
1844 abd = DetSign (ppos, qpos, v1os);\
1845 cda = DetSign (v0os, v1os, ppos);\
1846 cdb = DetSign (v0os, v1os, qpos);\
1847 srprintf ("%2d %2d %2d %2d ", abc, abd, cda, cdb);\
1848 if ((abc * abd) == 1 || (cda * cdb) == 1)\
1849 {\
1850 srprintf ("no intersection\n");\
1851 continue;\
1852 }\
1853 srprintf ("INTERSECTION\n");\
1854 return (TRUE);\
1855 }
1856
IntersectsEdge(Loop * loops,BVertex * p,BVertex * q)1857 static int IntersectsEdge (Loop *loops, BVertex *p, BVertex *q)
1858 {
1859 int pid, qid;
1860 Point2 ppos, qpos;
1861 BVertex *v0, *v1;
1862 int v0i, v1i;
1863 Point2 v0os, v1os;
1864 Loop *lp;
1865 int i;
1866 int nvert;
1867 int abc, abd, cda, cdb;
1868 BBox pqbox;
1869 BBox loopbox;
1870
1871 pid = p->id;
1872 qid = q->id;
1873 ppos = p->pos;
1874 qpos = q->pos;
1875
1876 if (ppos.u < qpos.u)
1877 {
1878 pqbox.ll.u = ppos.u;
1879 pqbox.ur.u = qpos.u;
1880 }
1881 else
1882 {
1883 pqbox.ll.u = qpos.u;
1884 pqbox.ur.u = ppos.u;
1885 }
1886
1887 if (ppos.v < qpos.v)
1888 {
1889 pqbox.ll.v = ppos.v;
1890 pqbox.ur.v = qpos.v;
1891 }
1892 else
1893 {
1894 pqbox.ll.v = qpos.v;
1895 pqbox.ur.v = ppos.v;
1896 }
1897
1898 /*
1899 * Check around the boundary
1900 */
1901
1902 for (v0 = p->next; v0 != p; v0 = v0->next)
1903 CheckEdge (p);
1904
1905 /*
1906 * Check around each loop
1907 */
1908
1909 for (lp = loops->next; lp != loops; lp = lp->next)
1910 {
1911 loopbox = lp->box;
1912 if (loopbox.ur.u < pqbox.ll.u || loopbox.ll.u > pqbox.ur.u ||
1913 loopbox.ur.v < pqbox.ll.v || loopbox.ll.v > pqbox.ur.v)
1914 continue;
1915
1916 for (i = 0, nvert = lp->nvert, v0 = lp->base;
1917 i < nvert;
1918 i++, v0 = v0->next)
1919 {
1920 CheckEdge (q);
1921 }
1922 }
1923
1924 return (FALSE);
1925 }
1926
1927
1928 /*
1929 * Determines whether a point is _dxf_inside a triangle by examining the
1930 * rotations in the triangles formed by each pair of vertices in the
1931 * test triangle and the point. If all of the rotations are the same
1932 * then the point is _dxf_inside of the triangle, if one is different then
1933 * the point is outside, if one doesn't rotate then the point is either
1934 * on or coincident with one of the triangle's edges.
1935 */
1936
PointInTri(Point2 p,Point2 plast,Point2 pnext,Point2 v0,Point2 v1,Point2 v2,int psign)1937 static int PointInTri (Point2 p, Point2 plast, Point2 pnext,
1938 Point2 v0, Point2 v1, Point2 v2, int psign)
1939 {
1940 int det01p, det12p, det20p;
1941 int np = 0, nn = 0, nz = 0;
1942 Point2 e0, e1;
1943
1944 det01p = DetSign (v0, v1, p);
1945 if (det01p > 0)
1946 np ++;
1947 else if (det01p == 0)
1948 {
1949 memcpy(&e0, &v0, sizeof(Point2));
1950 memcpy(&e1, &v1, sizeof(Point2));
1951 nz ++;
1952 }
1953 else
1954 nn ++;
1955
1956 det12p = DetSign (v1, v2, p);
1957 if (det12p > 0)
1958 np ++;
1959 else if (det12p == 0)
1960 {
1961 memcpy(&e0, &v1, sizeof(Point2));
1962 memcpy(&e1, &v2, sizeof(Point2));
1963 nz ++;
1964 }
1965 else
1966 nn ++;
1967
1968 det20p = DetSign (v2, v0, p);
1969 if (det20p > 0)
1970 np ++;
1971 else if (det20p == 0)
1972 {
1973 memcpy(&e0, &v2, sizeof(Point2));
1974 memcpy(&e1, &v0, sizeof(Point2));
1975 nz ++;
1976 }
1977 else
1978 nn ++;
1979
1980 if (nn == 3 || np == 3)
1981 return TRUE;
1982 else if ((nn == 0 || np == 0) && nz == 1)
1983 {
1984 int p0, p1;
1985
1986 p0 = DetSign(e0, e1, plast);
1987 p1 = DetSign(e0, e1, pnext);
1988 if (p0 == psign || p1 == psign)
1989 return TRUE;
1990 else
1991 return FALSE;
1992 }
1993 else
1994 return FALSE;
1995 }
1996
1997
1998 #if TRIANGULATE_MAIN
main()1999 main ()
2000 {
2001 Point pvals [100];
2002 int ids[1000];
2003 Loop loops[100];
2004 Triangle tris[1000];
2005 int ntri;
2006 int nloops = 0;
2007 int npts = 0;
2008 int i, j, k;
2009 Point *pptr;
2010 Point p;
2011 Point normal;
2012
2013 p.x = p.y = p.z = 0.0;
2014 for (i = 0, pptr = pvals; i < 10; i++)
2015 {
2016 p.x = (float) i;
2017 for (j = 0; j < 10; j++)
2018 {
2019 p.y = (float) j;
2020 *pptr++ = p;
2021 }
2022 }
2023
2024 normal.x = 0.0;
2025 normal.y = 0.0;
2026 normal.z = 1.0;
2027
2028 for (;;)
2029 {
2030 printf ("enter number of loops: ");
2031 fflush (stdout);
2032 scanf ("%d", &nloops);
2033 if (nloops == 0)
2034 exit (0);
2035 if (nloops < 0)
2036 {
2037 nloops = -nloops;
2038 srprint = TRUE;
2039 }
2040 for (j = 0; j < nloops; j++)
2041 {
2042 loops[j].vids = ids + npts;
2043 printf (" loop %2d: enter cnt & indices: ", j);
2044 fflush (stdout);
2045 scanf ("%d", &loops[j].nvert);
2046 for (i = 0; i < loops[j].nvert; i++)
2047 scanf ("%d", &ids[npts++]);
2048 }
2049 printf ("\n");
2050
2051 TriangulateLoops (nloops, loops, pvals, &normal, 100, tris, &ntri);
2052 printf (" %3d triangles in buffer %x\n", ntri, tris);
2053 for (i = 0; i < ntri; i++)
2054 printf ("%3d: %3d %3d %3d\n", i, tris[i].p, tris[i].q, tris[i].r);
2055 }
2056 }
2057 #endif
2058
2059
TriangulateLoops(int nloops,Loop * loops,float * vertices,Point * normal,int np,Triangle * tptr,int * rntri,int nDim)2060 static Error TriangulateLoops (int nloops, Loop *loops, float *vertices,
2061 Point *normal, int np,
2062 Triangle *tptr, int *rntri, int nDim)
2063 {
2064 Error ret = ERROR; /* return status */
2065 int nvert; /* total vertex count */
2066 BVertex *vbase = NULL; /* base of list blocks */
2067 BVertex *spares; /* spare nodes for splitting */
2068 int size; /* size temporary */
2069 Loop loop; /* local copy of current loop */
2070 int psign; /* sign of the polygon's rotation */
2071 int tsign; /* sign of the triangle's rotation */
2072 BVertex *p0, *p1=NULL, *p2=NULL; /* vertices of tri being considered */
2073 int i0, i1, i2;
2074 int pass;
2075 int ntri = 0; /* # of triangles generated */
2076 int i, j;
2077 BVertex *bptr;
2078 Loop *orig_loops = loops;
2079 BVertex *first, *end;
2080 int not_done;
2081 #if 0
2082 int loopknt = 0;
2083 #endif
2084
2085 if (rntri)
2086 *rntri = 0;
2087
2088 /*
2089 * Since each loop requires a link and each link requires splitting 2
2090 * vertices we end up with the following for the maximum number of
2091 * vertices.
2092 */
2093
2094 for (nvert = 0, i = 0; i < nloops; i++)
2095 nvert += loops[i].nvert;
2096 nvert += 2 * (nloops - 1);
2097
2098 size = nvert * sizeof (BVertex);
2099 vbase = (BVertex *) DXAllocateLocal (size);
2100 if (vbase == NULL)
2101 goto error;
2102 spares = vbase;
2103 memset (vbase, 0, size);
2104
2105 /*
2106 * For each loop:
2107 * * Initialize its boundary vertex list as a circularly linked list.
2108 * * We first have to chunk off the necessary number of BVertex nodes
2109 * for use with this list and set the rest aside as the spares.
2110 * * For now we'll just put in the vertex id. We'll fill in the
2111 * vertex positions later. We separate this for two reasons. First,
2112 * it involves random accessing and we don't want to guarantee that
2113 * we destroy any savings we get from the PVS's line cache, and
2114 * second we want to use tight loops for the projection from 3-space
2115 * to 2-space.
2116 */
2117
2118 for (j = 0; j < nloops; j++)
2119 {
2120 loops[j].base = spares;
2121 spares += loops[j].nvert;
2122 loop = loops[j];
2123
2124 for (i = 0, bptr = loop.base; i < loop.nvert; i++, bptr++)
2125 {
2126 bptr->next = bptr + 1;
2127 bptr->prev = bptr - 1;
2128 bptr->lp = loops + j;
2129 bptr->id = *loop.vids++;
2130 }
2131
2132 /*
2133 * Circularly link the list
2134 */
2135
2136 bptr = loop.base + (loop.nvert - 1);
2137 bptr->next = loop.base;
2138 loop.base->prev = bptr;
2139 }
2140
2141 ProjectPoints (normal, vertices, nloops, loops, nDim);
2142
2143 /*
2144 * Get rid of colinear loops and loops with fewer than 3 points and
2145 * link all of the others together.
2146 */
2147
2148 if (! InitLoops (&nloops, &loops, spares, np))
2149 goto error;
2150
2151 psign = loops->sign;
2152 if (psign == 0)
2153 {
2154 ret = OK;
2155 goto error;
2156 }
2157
2158
2159 first = loops->base;
2160 end = NULL;
2161 pass = 0;
2162 nvert = loops->nvert;
2163 p0 = loops->base;
2164 first = NULL;
2165 while (nloops > 0)
2166 {
2167 do
2168 {
2169 if (first != NULL)
2170 p0 = first;
2171
2172 not_done = 0;
2173 pass++;
2174
2175 if (first == end)
2176 end = NULL;
2177
2178 while (p0->pass < pass && p0 != end)
2179 {
2180 p0->pass = pass;
2181
2182 p1 = p0->next;
2183 p2 = p1->next;
2184
2185 if (!p0->tried)
2186 {
2187 srprintf ("DXTri: %2d %2d %2d (%3d/%3d)",
2188 p0->id, p1->id, p2->id, pass, nvert);
2189
2190 if (p0->id == p1->id || p1->id == p2->id ||
2191 (tsign = DetSign(p0->pos, p1->pos, p2->pos)) == 0)
2192 {
2193 /*
2194 * degenerate triangle. eliminate p1 from the loop.
2195 */
2196 p0->next = p2;
2197 p2->prev = p0;
2198 not_done++;
2199 nvert--;
2200 }
2201 else if (tsign != psign ||
2202 AnyInside (loops, p0, p1, p2, psign))
2203 {
2204 p0->tried = 1;
2205 }
2206 else
2207 {
2208 not_done++;
2209 p0->prev->tried = 0;
2210 if (p0 == first)
2211 first = first->prev;
2212 if (p2 == end)
2213 {
2214 if (end == first)
2215 end = NULL;
2216 else
2217 end = end->next;
2218 }
2219
2220 #if 0
2221 if (pass >= which_pass)
2222 {
2223 fprintf(stderr, "output: %d %d %d\n", p0->id, p1->id, p2->id);
2224 ShowLoop(p2);
2225 }
2226 #endif
2227
2228 EmitTri012;
2229 nvert--;
2230
2231 while (nvert > 2)
2232 {
2233 p1 = p0->next;
2234 p2 = p1->next;
2235
2236 if (DetSign(p0->pos, p1->pos, p2->pos) == 0)
2237 {
2238 p0->next = p2;
2239 p2->prev = p0;
2240 nvert --;
2241 }
2242 else
2243 break;
2244 }
2245 }
2246 }
2247
2248 p0 = p0->next;
2249 }
2250
2251 } while (not_done && nvert >= 3);
2252
2253 if (nloops > 1)
2254 if (! AddLink (loops, p0, &spares, &nvert, &first, &end))
2255 {
2256 DXSetError (ERROR_INTERNAL, "Couldn't add link");
2257 goto error;
2258 }
2259
2260 nloops--;
2261 }
2262
2263 if (nvert > 3)
2264 {
2265 DXSetError(ERROR_DATA_INVALID, "topology error");
2266 #if 0
2267 {
2268 FILE *foo = fopen("bad.dx", "w");
2269 if ( foo )
2270 {
2271 if (! first)
2272 first = p0;
2273
2274 for (i = 0, p0 = first; p0->next != first; p0 = p0->next)
2275 i++;
2276
2277 fprintf(foo,
2278 "object \"faces\" class array type int rank 0 items 1 data follows\n0\nattribute \"ref\" string \"loops\"\n");
2279
2280 fprintf(foo,
2281 "object \"loops\" class array type int rank 0 items 1 data follows\n0\nattribute \"ref\" string \"edges\"\n");
2282
2283 fprintf(foo,
2284 "object \"edges\" class array type int rank 0 items %d data follows\n", nvert);
2285 for (i = 0; i < nvert; i++)
2286 fprintf(foo, "%d\n", i);
2287 fprintf(foo,
2288 "attribute \"ref\" string \"positions\"\n ", nvert);
2289
2290 fprintf(foo,
2291 "object \"positions\" class array type float rank 1 shape 3 items %d data follows\n", nvert);
2292 for (i = 0, p0 = first; i < nvert; i++, p0 = p0->next)
2293 fprintf(foo, "%f %f 0\n", p0->pos.u, p0->pos.v);
2294
2295 fprintf(foo, "object \"fle\" class field\n");
2296 fprintf(foo, " component \"faces\" \"faces\"\n");
2297 fprintf(foo, " component \"loops\" \"loops\"\n");
2298 fprintf(foo, " component \"edges\" \"edges\"\n");
2299 fprintf(foo, " component \"positions\" \"positions\"\n");
2300 fprintf(foo, "end\n");
2301
2302 fclose(foo);
2303 }
2304 }
2305 #endif
2306 goto error;
2307 }
2308
2309 if (nvert == 3)
2310 EmitTri012;
2311
2312 #if 0
2313 if (dumpLoop || loopknt == loopLimit)
2314 DumpLoop(p0);
2315 #endif
2316
2317 ret = OK;
2318 goto cleanup;
2319
2320 error:
2321 #if ! TRIANGULATE_ALWAYS
2322 ntri = 0;
2323 #endif
2324
2325 cleanup:
2326 if (orig_loops != loops)
2327 DXFree((Pointer)loops);
2328 DXFree ((Pointer) vbase);
2329 if (rntri)
2330 *rntri = ntri;
2331 return (ret);
2332 }
2333
2334 static int
AnyInside(Loop * loops,BVertex * p0,BVertex * p1,BVertex * p2,int psign)2335 AnyInside (Loop *loops, BVertex *p0,
2336 BVertex *p1, BVertex *p2, int psign)
2337 {
2338 BVertex *p;
2339 int i0, i1, i2;
2340 Point2 v0, v1, v2;
2341 Point2 ppos;
2342 BBox tribox, loopbox;
2343 int ip;
2344 Loop *lp;
2345 int i;
2346 int nvert;
2347
2348 i0 = p0->id; i1 = p1->id; i2 = p2->id;
2349 v0 = p0->pos; v1 = p1->pos; v2 = p2->pos;
2350
2351 tribox.ll.u = v0.u<v1.u?v0.u<v2.u?v0.u : v2.u : v1.u<v2.u?v1.u : v2.u;
2352 tribox.ll.v = v0.v<v1.v?v0.v<v2.v?v0.v : v2.v : v1.v<v2.v?v1.v : v2.v;
2353 tribox.ur.u = v0.u>v1.u?v0.u>v2.u?v0.u : v2.u : v1.u>v2.u?v1.u : v2.u;
2354 tribox.ur.v = v0.v>v1.v?v0.v>v2.v?v0.v : v2.v : v1.v>v2.v?v1.v : v2.v;
2355
2356 /*
2357 * Check the boundary
2358 */
2359
2360 for (p = p2->next; p != p0; p = p->next)
2361 CheckPoint ();
2362
2363 /*
2364 * Check the other loops.
2365 */
2366
2367 for (lp = loops->next; lp != loops; lp = lp->next)
2368 {
2369 loopbox = lp->box;
2370 if (loopbox.ur.u < tribox.ll.u || loopbox.ll.u > tribox.ur.u ||
2371 loopbox.ur.v < tribox.ll.v || loopbox.ll.v > tribox.ur.v)
2372 continue;
2373
2374 for (i = 0, nvert = lp->nvert, p = lp->base;
2375 i < nvert;
2376 i++, p = p->next)
2377 CheckPoint ();
2378 }
2379
2380 return (FALSE);
2381 }
2382
2383 static Error
InitLoops(int * nloopsPtr,Loop ** loopsPtr,BVertex * spares,int np)2384 InitLoops (int *nloopsPtr, Loop **loopsPtr, BVertex *spares,
2385 int np)
2386 {
2387 int nloops = *nloopsPtr;
2388 Loop *loops = *loopsPtr;
2389 int i, j, k;
2390 int flip;
2391 BVertex *p0, *p1, *p2;
2392 int maxLoops = *nloopsPtr;
2393 HashTable ptHash =
2394 DXCreateHash(sizeof(BVertex *), HashPoint, ComparePoint);
2395 if (! ptHash)
2396 goto error;
2397
2398 for (j = 0; j < nloops; j++)
2399 {
2400 p0 = loops[j].base;
2401 do
2402 {
2403 BVertex **q;
2404 q = (BVertex **)DXQueryHashElement(ptHash, (Key)&p0);
2405 if (q)
2406 p0->id = (*q)->id;
2407 else
2408 if (! DXInsertHashElement(ptHash, (Element)&p0))
2409 goto error;
2410 p0 = p0->next;
2411 }
2412 while (p0 != loops[j].base);
2413 }
2414
2415 DXDestroyHash(ptHash);
2416 ptHash = NULL;
2417
2418 for (j = 0; j < nloops; j++)
2419 {
2420 p0 = loops[j].base;
2421 do
2422 {
2423 for (p1 = loops[j].base; p1 != p0; p1 = p1->next)
2424 if (p1->id == p0->id)
2425 {
2426 if (p0->next == p1)
2427 {
2428 p0->next = p1->next;
2429 p0->next->prev = p0;
2430 loops[j].nvert -= 1;
2431 }
2432 else
2433 {
2434 int p1loop, p0loop;
2435
2436 for (p1loop = 0, p2 = p1; p2 != p0; p2 = p2->next, p1loop++);
2437 p0loop = loops[j].nvert - p1loop;
2438
2439 p2 = p0->prev;
2440
2441 p0->prev = p1->prev;
2442 p0->prev->next = p0;
2443
2444 p1->prev = p2;
2445 p1->prev->next = p1;
2446
2447 if (p0loop > 2 && p1loop <= 2)
2448 {
2449 loops[j].nvert = p0loop;
2450 loops[j].base = p0;
2451 }
2452 else if (p0loop <= 2 && p1loop > 2)
2453 {
2454 loops[j].nvert = p1loop;
2455 loops[j].base = p1;
2456 }
2457 else if (p0loop > 2 && p1loop > 2)
2458 {
2459 loops[j].nvert = p0loop;
2460 loops[j].base = p0;
2461
2462 if (nloops == maxLoops)
2463 {
2464 Loop *newloops = (Loop *)
2465 DXAllocate(2*maxLoops*sizeof(Loop));
2466 if (! newloops)
2467 goto error;
2468
2469 memcpy(newloops, loops, nloops*sizeof(Loop));
2470
2471 if (loops != *loopsPtr)
2472 DXFree((Pointer)loops);
2473
2474 loops = newloops;
2475
2476 maxLoops *= 2;
2477 }
2478
2479 loops[nloops] = loops[j];
2480
2481 loops[nloops].base = p1;
2482 loops[nloops].nvert = p1loop;
2483 nloops ++;
2484 }
2485 else
2486 loops[j].nvert = 0;
2487 }
2488
2489 p1 = p0 = loops[j].base;
2490 break;
2491 }
2492
2493 p0 = p0->next;
2494
2495 } while (p0 != loops[j].base);
2496 }
2497
2498 for (j = 0; j < nloops; j++)
2499 loops[j].merged = FALSE;
2500
2501 for (j = 0; j < nloops; j++)
2502 LoopSign (loops + j);
2503
2504 loops->next = loops->prev = loops;
2505 if (nloops == 1)
2506 return OK;
2507
2508 /*
2509 * If one of the inner loops (a hole) rotates the same way as the
2510 * outer loop then we need to flip its sense. We do this by
2511 * interchanging its next and its prev pointers. But first, we
2512 * want to make sure that all of our outer loops always rotate
2513 * the same way, this way thin faces will have their tops & bottoms
2514 * (or fronts & backs) triangulated the same way rather than oppositely.
2515 * This is particularly important for reducing the triangle count when
2516 * a thin solid collapses to a face during simplification.
2517 */
2518
2519 if (loops->sign == 1)
2520 FlipLoop (loops);
2521 flip = loops->sign;
2522 for (j = 1; j < nloops; j++)
2523 if (loops[j].sign == flip)
2524 FlipLoop (loops + j);
2525
2526 for (j = 0; j < nloops; j++)
2527 if (loops[j].sign == 0 || loops[j].nvert < 3)
2528 loops[j].merged = TRUE;
2529
2530 for (j = 0; j < nloops; j++)
2531 {
2532 p0 = loops[j].base;
2533 if (p0)
2534 {
2535 do
2536 {
2537 for (k = j+1; k < nloops; k++)
2538 if ((p1 = loops[k].base) != NULL)
2539 do
2540 {
2541 if (p1->id == p0->id)
2542 {
2543 p2 = p0->next;
2544 p0->next = p1->next;
2545 p0->next->prev = p0;
2546 p1->next = p2;
2547 p2->prev = p1;
2548 loops[j].nvert += loops[k].nvert;
2549 loops[k].nvert = 0;
2550 loops[k].base = NULL;
2551 if (loops[j].box.ll.u > loops[k].box.ll.u)
2552 loops[j].box.ll.u = loops[k].box.ll.u;
2553 if (loops[j].box.ll.v > loops[k].box.ll.v)
2554 loops[j].box.ll.v = loops[k].box.ll.v;
2555 if (loops[j].box.ur.u < loops[k].box.ur.u)
2556 loops[j].box.ur.u = loops[k].box.ur.u;
2557 if (loops[j].box.ur.v < loops[k].box.ur.v)
2558 loops[j].box.ur.v = loops[k].box.ur.v;
2559 p1 = NULL;
2560 }
2561 else
2562 p1 = p1->next;
2563 } while (p1 != loops[k].base);
2564 p0 = p0->next;
2565 } while (p0 != loops[j].base);
2566 }
2567
2568 p0 = loops[j].base;
2569 if (p0)
2570 {
2571 int nv = loops[j].nvert;
2572
2573 if (nv)
2574 {
2575 do
2576 {
2577 if (nv > 3 && p0->id == p0->next->next->id)
2578 {
2579 nv -= 2;
2580 loops[j].base = p0;
2581 p0->next = p0->next->next->next;
2582 p0->next->prev = p0;
2583 }
2584 p0 = p0->next;
2585 } while (p0 != loops[j].base);
2586
2587 loops[j].nvert = nv;
2588 }
2589 }
2590 }
2591
2592 for (i = j = 0; j < nloops; j++)
2593 if (loops[j].nvert != 0)
2594 {
2595 if (j != 0)
2596 loops[i] = loops[j];
2597 i++;
2598 }
2599
2600 nloops = i;
2601
2602 for (i = 0; i < nloops; i++)
2603 {
2604 p0 = loops[i].base;
2605 do
2606 {
2607 p0->tried = 0;
2608 p0->pass = 0;
2609 p0 = p0->next;
2610 } while (p0 != loops[i].base);
2611 }
2612
2613 /*
2614 * Set up the loop linked lists
2615 */
2616
2617 for (j = 0; j < nloops; j++)
2618 {
2619 loops[j].next = loops + j + 1;
2620 loops[j].prev = loops + j - 1;
2621 }
2622 loops[nloops - 1].next = loops;
2623 loops[0].prev = loops + nloops - 1;
2624
2625 for (j = 0; j < nloops; j++)
2626 {
2627 if (loops[j].merged)
2628 {
2629 loops[j].prev->next = loops[j].next;
2630 loops[j].next->prev = loops[j].prev;
2631 }
2632 }
2633
2634 *nloopsPtr = nloops;
2635 *loopsPtr = loops;
2636 return OK;
2637
2638 error:
2639 if (ptHash)
2640 DXDestroyHash(ptHash);
2641 return ERROR;
2642 }
2643
2644 static int
AddLink(Loop * loops,BVertex * p0,BVertex ** spares,int * nvert,BVertex ** first,BVertex ** end)2645 AddLink(Loop *loops, BVertex *p0, BVertex **spares, int *nvert,
2646 BVertex **first, BVertex **end)
2647 {
2648 BVertex *sp;
2649 BVertex *p, *q;
2650 BVertex *np, *nq;
2651 Loop *lp;
2652 int i, maxi;
2653 int j, maxj;
2654 int k;
2655
2656 sp = *spares;
2657
2658 for (j = 0, maxj = *nvert, p = p0; j < maxj; j++, p = p->next)
2659 {
2660 for (k = 1, lp = loops->next; lp != loops; lp = lp->next, k++)
2661 {
2662 for (i = 0, maxi = lp->nvert, q = lp->base;
2663 i < maxi;
2664 i++, q = q->next)
2665 {
2666 if (p->id == q->id)
2667 continue;
2668
2669 if (IntersectsEdge (loops, p, q))
2670 continue;
2671
2672 srprintf ("LINKING at %2d - %2d\n", p->id, q->id);
2673 np = sp++;
2674 nq = sp++;
2675 *np = *p;
2676 *nq = *q;
2677
2678 np->pass = 0;
2679 nq->pass = 0;
2680
2681 np->next = q;
2682 nq->next = p;
2683 np->prev = p->prev;
2684 nq->prev = q->prev;
2685 p->prev->next = np;
2686 q->prev->next = nq;
2687 p->prev = nq;
2688 q->prev = np;
2689
2690 lp->merged = TRUE;
2691 lp->next->prev = lp->prev;
2692 lp->prev->next = lp->next;
2693 lp->next = NULL;
2694 lp->prev = NULL;
2695
2696 *nvert += lp->nvert + 2;
2697 *spares = sp;
2698 loops->nvert = *nvert;
2699 loops->base = p0;
2700
2701 np->prev->tried = 0;
2702 np->tried = 0;
2703
2704 if (srprint)
2705 {
2706 printf("sequence after adding nested loop:");
2707 for (j = 0, maxj = *nvert, p = p0; j < maxj; j++, p = p->next)
2708 printf("%d\n", p->id);
2709 }
2710
2711 *first = np->prev;
2712 *end = nq->next;
2713
2714 return (TRUE);
2715
2716 }
2717 }
2718 }
2719
2720 return FALSE;
2721 }
2722
LoopSign(Loop * lp)2723 static void LoopSign (Loop *lp)
2724 {
2725 BVertex *p;
2726 BVertex *p0, *p1, *p2;
2727 BVertex *tmp;
2728 Point2 pos;
2729 Point2 ll; /* the lower left */
2730 Point2 ur;
2731 int psign;
2732
2733 /*
2734 * Find the "leftmost bottom-most" vertex for use as our starting midpoint.
2735 * While were at it, find the rest of the bounding box too.
2736 */
2737
2738 p = lp->base;
2739
2740 for (p1 = p2 = p, ll = ur = p->pos, tmp = p->next;
2741 tmp != p;
2742 tmp = tmp->next)
2743 {
2744 pos = tmp->pos;
2745
2746 if (pos.u < ll.u)
2747 {
2748 ll.u = pos.u;
2749 p1 = tmp;
2750 }
2751 else if (pos.u == ll.u)
2752 {
2753 if (pos.v < p1->pos.v)
2754 p1 = tmp;
2755 }
2756 else if (pos.u > ur.u)
2757 ur.u = pos.u;
2758
2759 if (pos.v < ll.v)
2760 ll.v = pos.v;
2761 else if (pos.v > ur.v)
2762 ur.v = pos.v;
2763 }
2764
2765 /*
2766 * Walk around the polygon until we either get a non-zero sign for the
2767 * determinant or until we've come all the way around. If we do get
2768 * a sign then that is the characteristic direction for the polygon
2769 * and we can return it immediately. Otherwise all of the points in
2770 * the polygon are colinear.
2771 */
2772
2773 tmp = p1;
2774 p0 = p1->prev;
2775 p2 = p1->next;
2776
2777 do
2778 {
2779 psign = DetSign (p0->pos, p1->pos, p2->pos);
2780 if (psign)
2781 {
2782 lp->sign = psign;
2783 lp->box.ll = ll;
2784 lp->box.ur = ur;
2785 return;
2786 }
2787
2788 p0 = p1;
2789 p1 = p2;
2790 p2 = p2->next;
2791 } while (p2 != tmp);
2792
2793 lp->sign = 0;
2794 ll.u = ll.v = 0.0;
2795 lp->box.ll = ll;
2796 lp->box.ur = ll;
2797 }
2798
2799
2800