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 while ((v != endv) || (ri > 1))
2198 PN_stdfloat crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
2200 if ( crossResult >= 0 )
2202 if ( crossResult > 0)
2203 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));
2207 nassertv(ri + 1 == (
int)rc.size());
2213 nassertv(ri + 1 == (
int)rc.size());
2214 vpos = mchain[vpos].next;
2215 v = mchain[vpos].vnum;
2222 nassertv(ri + 1 == (
int)rc.size());
2223 vpos = mchain[vpos].next;
2224 v = mchain[vpos].vnum;
2229 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));
void triangulate()
Does the work of triangulating the specified polygon.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
int get_triangle_v0(int n) const
Returns vertex 0 of the nth triangle generated by the previous call to triangulate().
void begin_hole()
Finishes the previous hole, if any, and prepares to add a new hole.
int get_triangle_v2(int n) const
Returns vertex 2 of the nth triangle generated by the previous call to triangulate().
void add_hole_vertex(int index)
Adds the next consecutive vertex of the current hole.
void clear_polygon()
Removes the current polygon definition (and its set of holes), but does not clear the vertex pool.
int random_int(int range)
Returns a random integer in the range [0, range).
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
int get_num_triangles() const
Returns the number of triangles generated by the previous call to triangulate().
void clear()
Removes all vertices and polygon specifications from the Triangulator, and prepares it to start over.
void add_polygon_vertex(int index)
Adds the next consecutive vertex of the polygon.
A handy class to return random numbers.
int get_triangle_v1(int n) const
Returns vertex 1 of the nth triangle generated by the previous call to triangulate().
int add_vertex(const LPoint2d &point)
Adds a new vertex to the vertex pool.