39 int index = (int)_vertices.size();
40 _vertices.push_back(point);
64 _polygon.push_back(index);
72 _holes.push_back(vector_int());
84 nassertv(!_holes.empty());
85 _holes.back().push_back(index);
98 cleanup_polygon_indices(_polygon);
100 for (hi = _holes.begin(); hi != _holes.end(); ++hi) {
101 cleanup_polygon_indices(*hi);
104 if (_polygon.size() < 3) {
111 seg.push_back(segment_t());
112 make_segment(_polygon,
true);
114 for (hi = _holes.begin(); hi != _holes.end(); ++hi) {
115 if ((*hi).size() >= 3) {
116 make_segment(*hi,
false);
121 int num_segments = (int)seg.size() - 1;
122 permute.reserve(num_segments);
124 for (i = 0; i < num_segments; ++i) {
125 permute.push_back(i + 1);
153 while (construct_trapezoids(num_segments) != 0) {
156 for (i = 0; i < num_segments; ++i) {
158 nassertv(j >= 0 && j < num_segments);
160 permute[i] = permute[j];
186 int nmonpoly = monotonate_trapezoids(num_segments);
190 triangulate_monotone_polygons(num_segments, nmonpoly);
207 return _result.size();
219 nassertr(n >= 0 && n < (
int)_result.size(), -1);
220 return _result[n]._v0;
232 nassertr(n >= 0 && n < (
int)_result.size(), -1);
233 return _result[n]._v1;
245 nassertr(n >= 0 && n < (
int)_result.size(), -1);
246 return _result[n]._v2;
253 cleanup_polygon_indices(vector_int &polygon) {
256 while (pi < polygon.size()) {
257 if (polygon[pi] >= 0 && (
size_t)polygon[pi] < _vertices.size()) {
262 polygon.erase(_polygon.begin() + pi);
268 while (pi < polygon.size()) {
269 if (_vertices[polygon[pi]] != _vertices[polygon[pi - 1]]) {
274 polygon.erase(_polygon.begin() + pi);
278 if (polygon.size() > 1 && _vertices[polygon.back()] == _vertices[_polygon.front()]) {
297 #define REALLY_BIG 1<<30
313 #define SP_SIMPLE_LRUP 1
314 #define SP_SIMPLE_LRDN 2
316 #define SP_2UP_LEFT 4
317 #define SP_2UP_RIGHT 5
318 #define SP_2DN_LEFT 6
319 #define SP_2DN_RIGHT 7
320 #define SP_NOSPLIT -1
329 #define CROSS(v0, v1, v2) (((v1).x - (v0).x)*((v2).y - (v0).y) - \
330 ((v1).y - (v0).y)*((v2).x - (v0).x))
332 #define DOT(v0, v1) ((v0).x * (v1).x + (v0).y * (v1).y)
334 #define FP_EQUAL(s, t) (fabs(s - t) <= C_EPS)
337 #define CROSS_SINE(v0, v1) ((v0).x * (v1).y - (v1).x * (v0).y)
338 #define LENGTH(v0) (sqrt((v0).x * (v0).x + (v0).y * (v0).y))
346 check_left_winding(
const vector_int &range)
const {
351 size_t j = range.size() - 1;
352 for (
size_t i = 0; i < range.size(); ++i) {
353 const LPoint2d &p0 = _vertices[range[j]];
354 const LPoint2d &p1 = _vertices[range[i]];
355 area += p0[0] * p1[1] - p0[1] * p1[0];
368 make_segment(
const vector_int &range,
bool want_left_winding) {
369 int num_points = (int)range.size();
370 nassertv(num_points >= 2);
372 int first = (int)seg.size();
373 int last = first + num_points - 1;
375 if (want_left_winding == check_left_winding(range)) {
377 int first = (int)seg.size();
378 int last = first + num_points - 1;
380 seg.push_back(segment_t(
this, range[0], range[1],
383 for (
int i = 1; i < num_points - 1; ++i) {
384 seg.push_back(segment_t(
this, range[i], range[i + 1],
385 first + i - 1, first + i + 1));
388 seg.push_back(segment_t(
this, range[num_points - 1], range[0],
393 seg.push_back(segment_t(
this, range[0], range[num_points - 1],
396 for (
int i = 1; i < num_points - 1; ++i) {
397 seg.push_back(segment_t(
this, range[num_points - i], range[num_points - i - 1],
398 first + i - 1, first + i + 1));
401 seg.push_back(segment_t(
this, range[1], range[0],
411 nassertr(choose_idx < (
int)permute.size(), 0);
415 return permute[choose_idx++];
418 double Triangulator::
419 math_log2(
double v) {
420 static const double log2 = log(2.0);
421 return log(v) / log2;
426 math_logstar_n(
int n) {
430 for (i = 0, v = (
double) n; v >= 1; i++)
438 math_N(
int n,
int h) {
442 for (i = 0, v = (
int) n; i < h; i++)
445 return (
int) ceil((
double) 1.0*n/v);
450 int Triangulator::newnode() {
451 int index = (int)qs.size();
452 qs.push_back(node_t());
458 int Triangulator::newtrap() {
459 int tr_idx = (int)tr.size();
460 tr.push_back(trap_t());
461 tr[tr_idx].lseg = -1;
462 tr[tr_idx].rseg = -1;
463 tr[tr_idx].state = ST_VALID;
470 int Triangulator::_max(point_t *yval, point_t *v0, point_t *v1) {
471 if (v0->y > v1->y + C_EPS)
473 else if (FP_EQUAL(v0->y, v1->y))
475 if (v0->x > v1->x + C_EPS)
488 int Triangulator::_min(point_t *yval, point_t *v0, point_t *v1) {
489 if (v0->y < v1->y - C_EPS)
491 else if (FP_EQUAL(v0->y, v1->y))
506 _greater_than(point_t *v0, point_t *v1) {
507 if (v0->y > v1->y + C_EPS)
509 else if (v0->y < v1->y - C_EPS)
512 return (v0->x > v1->x);
517 _equal_to(point_t *v0, point_t *v1) {
518 return (FP_EQUAL(v0->y, v1->y) && FP_EQUAL(v0->x, v1->x));
522 _greater_than_equal_to(point_t *v0, point_t *v1) {
523 if (v0->y > v1->y + C_EPS)
525 else if (v0->y < v1->y - C_EPS)
528 return (v0->x >= v1->x);
532 _less_than(point_t *v0, point_t *v1) {
533 if (v0->y < v1->y - C_EPS)
535 else if (v0->y > v1->y + C_EPS)
538 return (v0->x < v1->x);
556 init_query_structure(
int segnum) {
557 int i1, i2, i3, i4, i5, i6, i7, root;
559 segment_t *s = &seg[segnum];
565 tr.push_back(trap_t());
566 qs.push_back(node_t());
569 qs[i1].nodetype = T_Y;
570 _max(&qs[i1].yval, &s->v0, &s->v1);
575 qs[i2].nodetype = T_SINK;
581 qs[i3].nodetype = T_Y;
582 _min(&qs[i3].yval, &s->v0, &s->v1);
587 qs[i4].nodetype = T_SINK;
592 qs[i5].nodetype = T_X;
593 qs[i5].segnum = segnum;
598 qs[i6].nodetype = T_SINK;
603 qs[i7].nodetype = T_SINK;
611 tr[t4].lo = qs[i1].yval;
612 tr[t2].hi = qs[i1].yval;
613 tr[t1].hi = qs[i1].yval;
614 tr[t3].hi = qs[i3].yval;
615 tr[t2].lo = qs[i3].yval;
616 tr[t1].lo = qs[i3].yval;
617 tr[t4].hi.y = (double) (REALLY_BIG);
618 tr[t4].hi.x = (double) (REALLY_BIG);
619 tr[t3].lo.y = (double) -1* (REALLY_BIG);
620 tr[t3].lo.x = (double) -1* (REALLY_BIG);
621 tr[t2].lseg = segnum;
622 tr[t1].rseg = segnum;
637 tr[t2].state = ST_VALID;
638 tr[t1].state = ST_VALID;
639 tr[t4].state = ST_VALID;
640 tr[t3].state = ST_VALID;
647 s->is_inserted =
true;
658 is_left_of(
int segnum, point_t *v) {
659 segment_t *s = &seg[segnum];
662 if (_greater_than(&s->v1, &s->v0))
664 if (FP_EQUAL(s->v1.y, v->y))
671 else if (FP_EQUAL(s->v0.y, v->y))
679 area = CROSS(s->v0, s->v1, (*v));
683 if (FP_EQUAL(s->v1.y, v->y))
690 else if (FP_EQUAL(s->v0.y, v->y))
698 area = CROSS(s->v1, s->v0, (*v));
714 inserted(
int segnum,
int whichpt) {
715 if (whichpt == FIRSTPT)
716 return seg[seg[segnum].prev].is_inserted;
718 return seg[seg[segnum].next].is_inserted;
726 locate_endpoint(point_t *v, point_t *vo,
int r) {
729 node_t *rptr = &qs[r];
731 switch (rptr->nodetype)
737 if (_greater_than(v, &rptr->yval))
738 return locate_endpoint(v, vo, rptr->right);
739 else if (_equal_to(v, &rptr->yval))
741 if (_greater_than(vo, &rptr->yval))
742 return locate_endpoint(v, vo, rptr->right);
744 return locate_endpoint(v, vo, rptr->left);
747 return locate_endpoint(v, vo, rptr->left);
750 if (_equal_to(v, &seg[rptr->segnum].v0) ||
751 _equal_to(v, &seg[rptr->segnum].v1))
753 if (FP_EQUAL(v->y, vo->y))
756 return locate_endpoint(v, vo, rptr->left);
758 return locate_endpoint(v, vo, rptr->right);
761 else if (is_left_of(rptr->segnum, vo))
762 return locate_endpoint(v, vo, rptr->left);
764 return locate_endpoint(v, vo, rptr->right);
766 else if (is_left_of(rptr->segnum, v))
767 return locate_endpoint(v, vo, rptr->left);
769 return locate_endpoint(v, vo, rptr->right);
772 fprintf(stderr,
"Haggu !!!!!\n");
787 merge_trapezoids(
int segnum,
int tfirst,
int tlast,
int side) {
796 while ((t > 0) && _greater_than_equal_to(&tr[t].lo, &tr[tlast].lo))
799 cond = ((((tnext = tr[t].d0) > 0) && (tr[tnext].rseg == segnum)) ||
800 (((tnext = tr[t].d1) > 0) && (tr[tnext].rseg == segnum)));
802 cond = ((((tnext = tr[t].d0) > 0) && (tr[tnext].lseg == segnum)) ||
803 (((tnext = tr[t].d1) > 0) && (tr[tnext].lseg == segnum)));
807 if ((tr[t].lseg == tr[tnext].lseg) &&
808 (tr[t].rseg == tr[tnext].rseg))
812 ptnext = qs[tr[tnext].sink].parent;
814 if (qs[ptnext].left == tr[tnext].sink)
815 qs[ptnext].left = tr[t].sink;
817 qs[ptnext].right = tr[t].sink;
822 if ((tr[t].d0 = tr[tnext].d0) > 0) {
823 if (tr[tr[t].d0].u0 == tnext) {
825 }
else if (tr[tr[t].d0].u1 == tnext) {
830 if ((tr[t].d1 = tr[tnext].d1) > 0) {
831 if (tr[tr[t].d1].u0 == tnext) {
833 }
else if (tr[tr[t].d1].u1 == tnext) {
838 tr[t].lo = tr[tnext].lo;
839 tr[tnext].state = ST_INVALID;
861 add_segment(
int segnum) {
866 int tu, tl, sk, tfirst, tlast;
867 int tfirstr = 0, tlastr = 0, tfirstl = 0, tlastl = 0;
870 int tribot = 0, is_swapped = 0;
874 if (_greater_than(&s.v1, &s.v0))
886 if ((is_swapped) ? !inserted(segnum, LASTPT) :
887 !inserted(segnum, FIRSTPT))
891 tu = locate_endpoint(&s.v0, &s.v1, s.root0);
893 tr[tl].state = ST_VALID;
895 tr[tl].hi.y = s.v0.y;
896 tr[tu].lo.y = s.v0.y;
897 tr[tl].hi.x = s.v0.x;
898 tr[tu].lo.x = s.v0.x;
904 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u0 == tu))
906 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u1 == tu))
909 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u0 == tu))
911 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u1 == tu))
921 qs[sk].nodetype = T_Y;
923 qs[sk].segnum = segnum;
927 qs[i1].nodetype = T_SINK;
931 qs[i2].nodetype = T_SINK;
941 tfirst = locate_endpoint(&s.v0, &s.v1, s.root0);
945 if ((is_swapped) ? !inserted(segnum, FIRSTPT) :
946 !inserted(segnum, LASTPT))
950 tu = locate_endpoint(&s.v1, &s.v0, s.root1);
953 tr[tl].state = ST_VALID;
955 tr[tl].hi.y = s.v1.y;
956 tr[tu].lo.y = s.v1.y;
957 tr[tl].hi.x = s.v1.x;
958 tr[tu].lo.x = s.v1.x;
964 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u0 == tu))
966 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u1 == tu))
969 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u0 == tu))
971 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u1 == tu))
981 qs[sk].nodetype = T_Y;
983 qs[sk].segnum = segnum;
987 qs[i1].nodetype = T_SINK;
991 qs[i2].nodetype = T_SINK;
1001 tlast = locate_endpoint(&s.v1, &s.v0, s.root1);
1012 _greater_than_equal_to(&tr[t].lo, &tr[tlast].lo))
1020 qs[sk].nodetype = T_X;
1021 qs[sk].segnum = segnum;
1025 qs[i1].nodetype = T_SINK;
1029 qs[i2].nodetype = T_SINK;
1032 tr[tn].state = ST_VALID;
1037 if (_equal_to(&tr[t].lo, &tr[tlast].lo))
1048 if ((tr[t].d0 <= 0) && (tr[t].d1 <= 0))
1051 fprintf(stderr,
"add_segment: error\n");
1059 else if ((tr[t].d0 > 0) && (tr[t].d1 <= 0))
1061 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1063 if (tr[t].usave > 0)
1065 if (tr[t].uside == S_LEFT)
1067 tr[tn].u0 = tr[t].u1;
1069 tr[tn].u1 = tr[t].usave;
1071 tr[tr[t].u0].d0 = t;
1072 tr[tr[tn].u0].d0 = tn;
1073 tr[tr[tn].u1].d0 = tn;
1078 tr[tn].u0 = tr[t].u1;
1079 tr[t].u1 = tr[t].u0;
1080 tr[t].u0 = tr[t].usave;
1082 tr[tr[t].u0].d0 = t;
1083 tr[tr[t].u1].d0 = t;
1084 tr[tr[tn].u0].d0 = tn;
1091 tr[tn].u0 = tr[t].u1;
1094 tr[tr[tn].u0].d0 = tn;
1099 int tmp_u = tr[t].u0;
1101 if (((td0 = tr[tmp_u].d0) > 0) &&
1102 ((td1 = tr[tmp_u].d1) > 0))
1104 if ((tr[td0].rseg > 0) &&
1105 !is_left_of(tr[td0].rseg, &s.v1))
1110 tr[tr[tn].u0].d1 = tn;
1117 tr[tr[t].u0].d0 = t;
1122 tr[tr[t].u0].d0 = t;
1123 tr[tr[t].u0].d1 = tn;
1127 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1128 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1132 tmptriseg = seg[segnum].prev;
1134 tmptriseg = seg[segnum].next;
1136 if ((tmptriseg > 0) && is_left_of(tmptriseg, &s.v0))
1139 tr[tr[t].d0].u0 = t;
1146 tr[tr[tn].d0].u1 = tn;
1153 if ((tr[tr[t].d0].u0 > 0) && (tr[tr[t].d0].u1 > 0))
1155 if (tr[tr[t].d0].u0 == t)
1157 tr[tr[t].d0].usave = tr[tr[t].d0].u1;
1158 tr[tr[t].d0].uside = S_LEFT;
1162 tr[tr[t].d0].usave = tr[tr[t].d0].u0;
1163 tr[tr[t].d0].uside = S_RIGHT;
1166 tr[tr[t].d0].u0 = t;
1167 tr[tr[t].d0].u1 = tn;
1174 else if ((tr[t].d0 <= 0) && (tr[t].d1 > 0))
1176 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1178 if (tr[t].usave > 0)
1180 if (tr[t].uside == S_LEFT)
1182 tr[tn].u0 = tr[t].u1;
1184 tr[tn].u1 = tr[t].usave;
1186 tr[tr[t].u0].d0 = t;
1187 tr[tr[tn].u0].d0 = tn;
1188 tr[tr[tn].u1].d0 = tn;
1193 tr[tn].u0 = tr[t].u1;
1194 tr[t].u1 = tr[t].u0;
1195 tr[t].u0 = tr[t].usave;
1197 tr[tr[t].u0].d0 = t;
1198 tr[tr[t].u1].d0 = t;
1199 tr[tr[tn].u0].d0 = tn;
1207 tr[tn].u0 = tr[t].u1;
1210 tr[tr[tn].u0].d0 = tn;
1215 int tmp_u = tr[t].u0;
1217 if (((td0 = tr[tmp_u].d0) > 0) &&
1218 ((td1 = tr[tmp_u].d1) > 0))
1220 if ((tr[td0].rseg > 0) &&
1221 !is_left_of(tr[td0].rseg, &s.v1))
1226 tr[tr[tn].u0].d1 = tn;
1233 tr[tr[t].u0].d0 = t;
1238 tr[tr[t].u0].d0 = t;
1239 tr[tr[t].u0].d1 = tn;
1243 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1244 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1247 tmptriseg = seg[segnum].prev;
1249 tmptriseg = seg[segnum].next;
1251 if ((tmptriseg > 0) && is_left_of(tmptriseg, &s.v0))
1254 tr[tr[t].d1].u0 = t;
1261 tr[tr[tn].d1].u1 = tn;
1268 if ((tr[tr[t].d1].u0 > 0) && (tr[tr[t].d1].u1 > 0))
1270 if (tr[tr[t].d1].u0 == t)
1272 tr[tr[t].d1].usave = tr[tr[t].d1].u1;
1273 tr[tr[t].d1].uside = S_LEFT;
1277 tr[tr[t].d1].usave = tr[tr[t].d1].u0;
1278 tr[tr[t].d1].uside = S_RIGHT;
1281 tr[tr[t].d1].u0 = t;
1282 tr[tr[t].d1].u1 = tn;
1299 if (FP_EQUAL(tr[t].lo.y, s.v0.y))
1301 if (tr[t].lo.x > s.v0.x)
1308 yt = (y0 - s.v0.y)/(s.v1.y - s.v0.y);
1309 tmppt.x = s.v0.x + yt * (s.v1.x - s.v0.x);
1311 if (_less_than(&tmppt, &tr[t].lo))
1318 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1320 if (tr[t].usave > 0)
1322 if (tr[t].uside == S_LEFT)
1324 tr[tn].u0 = tr[t].u1;
1326 tr[tn].u1 = tr[t].usave;
1328 tr[tr[t].u0].d0 = t;
1329 tr[tr[tn].u0].d0 = tn;
1330 tr[tr[tn].u1].d0 = tn;
1335 tr[tn].u0 = tr[t].u1;
1336 tr[t].u1 = tr[t].u0;
1337 tr[t].u0 = tr[t].usave;
1339 tr[tr[t].u0].d0 = t;
1340 tr[tr[t].u1].d0 = t;
1341 tr[tr[tn].u0].d0 = tn;
1349 tr[tn].u0 = tr[t].u1;
1352 tr[tr[tn].u0].d0 = tn;
1357 int tmp_u = tr[t].u0;
1359 if (((td0 = tr[tmp_u].d0) > 0) &&
1360 ((td1 = tr[tmp_u].d1) > 0))
1362 if ((tr[td0].rseg > 0) &&
1363 !is_left_of(tr[td0].rseg, &s.v1))
1368 tr[tr[tn].u0].d1 = tn;
1375 tr[tr[t].u0].d0 = t;
1380 tr[tr[t].u0].d0 = t;
1381 tr[tr[t].u0].d1 = tn;
1385 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1386 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1392 tr[tr[t].d0].u0 = t;
1393 tr[tr[t].d0].u1 = -1;
1394 tr[tr[t].d1].u0 = tn;
1395 tr[tr[t].d1].u1 = -1;
1397 tr[tn].d0 = tr[t].d1;
1406 tr[tr[t].d0].u0 = t;
1407 tr[tr[t].d0].u1 = tn;
1408 tr[tr[t].d1].u0 = tn;
1409 tr[tr[t].d1].u1 = -1;
1420 tr[tr[t].d0].u0 = t;
1421 tr[tr[t].d0].u1 = -1;
1422 tr[tr[t].d1].u0 = t;
1423 tr[tr[t].d1].u1 = tn;
1428 tr[tn].d0 = tr[t].d1;
1437 tr[tn_sav].lseg = segnum;
1438 tr[t_sav].rseg = segnum;
1448 merge_trapezoids(segnum, tfirstl, tlastl, S_LEFT);
1449 merge_trapezoids(segnum, tfirstr, tlastr, S_RIGHT);
1451 seg[segnum].is_inserted =
true;
1461 find_new_roots(
int segnum) {
1463 segment_t *s = &seg[segnum];
1468 s->root0 = locate_endpoint(&s->v0, &s->v1, s->root0);
1469 s->root0 = tr[s->root0].sink;
1471 s->root1 = locate_endpoint(&s->v1, &s->v0, s->root1);
1472 s->root1 = tr[s->root1].sink;
1479 construct_trapezoids(
int nseg) {
1487 root = init_query_structure(choose_segment());
1489 for (i = 1; i <= nseg; i++) {
1490 seg[i].root1 = root;
1491 seg[i].root0 = root;
1494 for (h = 1; h <= math_logstar_n(nseg); h++)
1496 for (i = math_N(nseg, h -1) + 1; i <= math_N(nseg, h); i++) {
1497 if (add_segment(choose_segment()) != 0) {
1504 for (i = 1; i <= nseg; i++)
1508 for (i = math_N(nseg, math_logstar_n(nseg)) + 1; i <= nseg; i++)
1509 add_segment(choose_segment());
1518 inside_polygon(trap_t *t) {
1521 if (t->state == ST_INVALID)
1524 if ((t->lseg <= 0) || (t->rseg <= 0))
1527 if (((t->u0 <= 0) && (t->u1 <= 0)) ||
1528 ((t->d0 <= 0) && (t->d1 <= 0)))
1529 return (_greater_than(&seg[rseg].v1, &seg[rseg].v0));
1538 int index = (int)mon.size();
1547 new_chain_element() {
1548 int index = (int)mchain.size();
1549 mchain.push_back(monchain_t());
1555 double Triangulator::
1556 get_angle(point_t *vp0, point_t *vpnext, point_t *vp1) {
1559 v0.x = vpnext->x - vp0->x;
1560 v0.y = vpnext->y - vp0->y;
1562 v1.x = vp1->x - vp0->x;
1563 v1.y = vp1->y - vp0->y;
1565 if (CROSS_SINE(v0, v1) >= 0)
1566 return DOT(v0, v1)/LENGTH(v0)/LENGTH(v1);
1568 return (-1.0 * DOT(v0, v1)/LENGTH(v0)/LENGTH(v1) - 2);
1575 get_vertex_positions(
int v0,
int v1,
int *ip,
int *iq) {
1576 vertexchain_t *vp0, *vp1;
1589 for (i = 0; i < 4; i++)
1591 if (vp0->vnext[i] <= 0)
1593 if ((temp = get_angle(&vp0->pt, &(vert[vp0->vnext[i]].pt),
1606 for (i = 0; i < 4; i++)
1608 if (vp1->vnext[i] <= 0)
1610 if ((temp = get_angle(&vp1->pt, &(vert[vp1->vnext[i]].pt),
1629 make_new_monotone_poly(
int mcur,
int v0,
int v1) {
1631 int mnew = newmon();
1633 vertexchain_t *vp0, *vp1;
1635 if (v0 <= 0 || v1 <= 0) {
1642 get_vertex_positions(v0, v1, &ip, &iq);
1650 i = new_chain_element();
1651 j = new_chain_element();
1653 mchain[i].vnum = v0;
1654 mchain[j].vnum = v1;
1656 mchain[i].next = mchain[p].next;
1657 mchain[mchain[p].next].prev = i;
1660 mchain[j].prev = mchain[q].prev;
1661 mchain[mchain[q].prev].next = j;
1666 nf0 = vp0->nextfree;
1667 nf1 = vp1->nextfree;
1669 vp0->vnext[ip] = v1;
1672 vp0->vnext[nf0] = mchain[mchain[i].next].vnum;
1674 vp1->vnext[nf1] = v0;
1680 fprintf(stderr,
"make_poly: mcur = %d, (v0, v1) = (%d, %d)\n",
1682 fprintf(stderr,
"next posns = (p, q) = (%d, %d)\n", p, q);
1695 monotonate_trapezoids(
int n) {
1704 vert.insert(vert.begin(), n + 1, vertexchain_t());
1705 mchain.insert(mchain.begin(), n + 1, monchain_t());
1707 visited.insert(visited.begin(), tr.size(), 0);
1711 for (i = 1; i < (int)tr.size(); i++)
1712 if (inside_polygon(&tr[i]))
1714 if (i >= (
int)tr.size()) {
1725 for (i = 1; i <= n; i++)
1727 mchain[i].prev = i - 1;
1728 mchain[i].next = i + 1;
1730 vert[i].pt = seg[i].v0;
1731 vert[i].vnext[0] = i + 1;
1732 vert[i].vpos[0] = i;
1733 vert[i].nextfree = 1;
1734 vert[i].user_i = seg[i].v0_i;
1738 vert[n].vnext[0] = 1;
1739 vert[n].vpos[0] = n;
1745 for (i = 1; i <= n; i++)
1747 mchain[i].prev = seg[i].prev;
1748 mchain[i].next = seg[i].next;
1750 vert[i].pt = seg[i].v0;
1751 vert[i].vnext[0] = seg[i].next;
1752 vert[i].vpos[0] = i;
1753 vert[i].nextfree = 1;
1754 vert[i].user_i = seg[i].v0_i;
1763 if (tr[tr_start].u0 > 0)
1764 traverse_polygon(0, tr_start, tr[tr_start].u0, TR_FROM_UP);
1765 else if (tr[tr_start].d0 > 0)
1766 traverse_polygon(0, tr_start, tr[tr_start].d0, TR_FROM_DN);
1775 traverse_polygon(
int mcur,
int trnum,
int from,
int dir) {
1778 if (mcur < 0 || trnum <= 0)
1784 trap_t *t = &tr[trnum];
1793 visited[trnum] =
true;
1805 if ((t->u0 <= 0) && (t->u1 <= 0))
1807 if ((t->d0 > 0) && (t->d1 > 0))
1809 v0 = tr[t->d1].lseg;
1813 mnew = make_new_monotone_poly(mcur, v1, v0);
1814 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1815 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1819 mnew = make_new_monotone_poly(mcur, v0, v1);
1820 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1821 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1826 retval = SP_NOSPLIT;
1827 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1828 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1829 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1830 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1834 else if ((t->d0 <= 0) && (t->d1 <= 0))
1836 if ((t->u0 > 0) && (t->u1 > 0))
1839 v1 = tr[t->u0].rseg;
1842 mnew = make_new_monotone_poly(mcur, v1, v0);
1843 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1844 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1848 mnew = make_new_monotone_poly(mcur, v0, v1);
1849 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1850 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1855 retval = SP_NOSPLIT;
1856 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1857 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1858 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1859 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1863 else if ((t->u0 > 0) && (t->u1 > 0))
1865 if ((t->d0 > 0) && (t->d1 > 0))
1867 v0 = tr[t->d1].lseg;
1868 v1 = tr[t->u0].rseg;
1869 retval = SP_2UP_2DN;
1870 if (((dir == TR_FROM_DN) && (t->d1 == from)) ||
1871 ((dir == TR_FROM_UP) && (t->u1 == from)))
1873 mnew = make_new_monotone_poly(mcur, v1, v0);
1874 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1875 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1876 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1877 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1881 mnew = make_new_monotone_poly(mcur, v0, v1);
1882 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1883 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1884 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1885 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1890 if (_equal_to(&t->lo, &seg[t->lseg].v1))
1892 v0 = tr[t->u0].rseg;
1893 v1 = seg[t->lseg].next;
1895 retval = SP_2UP_LEFT;
1896 if ((dir == TR_FROM_UP) && (t->u0 == from))
1898 mnew = make_new_monotone_poly(mcur, v1, v0);
1899 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1900 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1901 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1902 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1906 mnew = make_new_monotone_poly(mcur, v0, v1);
1907 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1908 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1909 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1910 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1916 v1 = tr[t->u0].rseg;
1917 retval = SP_2UP_RIGHT;
1918 if ((dir == TR_FROM_UP) && (t->u1 == from))
1920 mnew = make_new_monotone_poly(mcur, v1, v0);
1921 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1922 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1923 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1924 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1928 mnew = make_new_monotone_poly(mcur, v0, v1);
1929 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1930 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1931 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1932 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1937 else if ((t->u0 > 0) || (t->u1 > 0))
1939 if ((t->d0 > 0) && (t->d1 > 0))
1941 if (_equal_to(&t->hi, &seg[t->lseg].v0))
1943 v0 = tr[t->d1].lseg;
1945 retval = SP_2DN_LEFT;
1946 if (!((dir == TR_FROM_DN) && (t->d0 == from)))
1948 mnew = make_new_monotone_poly(mcur, v1, v0);
1949 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1950 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1951 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1952 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1956 mnew = make_new_monotone_poly(mcur, v0, v1);
1957 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1958 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1959 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1960 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1965 v0 = tr[t->d1].lseg;
1966 v1 = seg[t->rseg].next;
1968 retval = SP_2DN_RIGHT;
1969 if ((dir == TR_FROM_DN) && (t->d1 == from))
1971 mnew = make_new_monotone_poly(mcur, v1, v0);
1972 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1973 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1974 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1975 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1979 mnew = make_new_monotone_poly(mcur, v0, v1);
1980 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1981 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1982 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1983 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1989 if (_equal_to(&t->hi, &seg[t->lseg].v0) &&
1990 _equal_to(&t->lo, &seg[t->rseg].v0))
1994 retval = SP_SIMPLE_LRDN;
1995 if (dir == TR_FROM_UP)
1997 mnew = make_new_monotone_poly(mcur, v1, v0);
1998 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1999 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2000 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2001 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2005 mnew = make_new_monotone_poly(mcur, v0, v1);
2006 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2007 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2008 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2009 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2012 else if (_equal_to(&t->hi, &seg[t->rseg].v1) &&
2013 _equal_to(&t->lo, &seg[t->lseg].v1))
2015 v0 = seg[t->rseg].next;
2016 v1 = seg[t->lseg].next;
2018 retval = SP_SIMPLE_LRUP;
2019 if (dir == TR_FROM_UP)
2021 mnew = make_new_monotone_poly(mcur, v1, v0);
2022 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2023 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2024 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2025 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2029 mnew = make_new_monotone_poly(mcur, v0, v1);
2030 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2031 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2032 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2033 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2038 retval = SP_NOSPLIT;
2039 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2040 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2041 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2042 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2057 triangulate_monotone_polygons(
int nvert,
int nmonpoly) {
2060 int p, vfirst, posmax, posmin, v;
2061 int vcount, processed;
2064 for (i = 0; i < nmonpoly; i++)
2066 fprintf(stderr,
"\n\nPolygon %d: ", i);
2067 vfirst = mchain[mon[i]].vnum;
2068 p = mchain[mon[i]].next;
2069 fprintf (stderr,
"%d ", mchain[mon[i]].vnum);
2070 while (mchain[p].vnum != vfirst)
2072 fprintf(stderr,
"%d ", mchain[p].vnum);
2073 if (mchain[p].vnum == -1) {
2074 fprintf(stderr,
" xx");
2080 fprintf(stderr,
"\n");
2083 for (i = 0; i < nmonpoly; i++)
2087 vfirst = mchain[mon[i]].vnum;
2091 ymin = vert[vfirst].pt;
2095 mchain[mon[i]].marked =
true;
2096 p = mchain[mon[i]].next;
2097 while ((v = mchain[p].vnum) != vfirst)
2102 if (mchain[p].marked)
2108 mchain[p].marked =
true;
2110 if (_greater_than(&vert[v].pt, &ymax))
2115 if (_less_than(&vert[v].pt, &ymin))
2129 _result.push_back(Triangle(
this, mchain[p].vnum,
2130 mchain[mchain[p].next].vnum,
2131 mchain[mchain[p].prev].vnum));
2135 v = mchain[mchain[posmax].next].vnum;
2136 if (_equal_to(&vert[v].pt, &ymin))
2138 triangulate_single_polygon(nvert, posmax, TRI_LHS);
2141 triangulate_single_polygon(nvert, posmax, TRI_RHS);
2152 triangulate_single_polygon(
int nvert,
int posmax,
int side) {
2156 int endv, tmp, vpos;
2161 if (side == TRI_RHS)
2163 rc.push_back(mchain[posmax].vnum);
2164 tmp = mchain[posmax].next;
2165 rc.push_back(mchain[tmp].vnum);
2168 vpos = mchain[tmp].next;
2169 v = mchain[vpos].vnum;
2171 if ((endv = mchain[mchain[posmax].prev].vnum) == 0)
2176 tmp = mchain[posmax].next;
2177 rc.push_back(mchain[tmp].vnum);
2178 tmp = mchain[tmp].next;
2179 rc.push_back(mchain[tmp].vnum);
2182 vpos = mchain[tmp].next;
2183 v = mchain[vpos].vnum;
2185 endv = mchain[posmax].vnum;
2188 int num_triangles = 0;
2190 while ((v != endv) || (ri > 1))
2200 PN_stdfloat crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
2202 if ( crossResult >= 0 )
2204 if (crossResult > 0) {
2205 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));
2206 if (++num_triangles >= nvert - 2) {
2214 nassertv(ri + 1 == (
int)rc.size());
2220 nassertv(ri + 1 == (
int)rc.size());
2221 vpos = mchain[vpos].next;
2222 v = mchain[vpos].vnum;
2229 nassertv(ri + 1 == (
int)rc.size());
2230 vpos = mchain[vpos].next;
2231 v = mchain[vpos].vnum;
2236 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));