15 #include "triangulator.h"
16 #include "randomizer.h"
47 int index = (int)_vertices.size();
48 _vertices.push_back(point);
78 _polygon.push_back(index);
89 _holes.push_back(vector_int());
105 nassertv(!_holes.empty());
106 _holes.back().push_back(index);
122 cleanup_polygon_indices(_polygon);
124 for (hi = _holes.begin(); hi != _holes.end(); ++hi) {
125 cleanup_polygon_indices(*hi);
128 if (_polygon.size() < 3) {
135 seg.push_back(segment_t());
136 make_segment(_polygon,
true);
138 for (hi = _holes.begin(); hi != _holes.end(); ++hi) {
139 if ((*hi).size() >= 3) {
140 make_segment(*hi,
false);
145 int num_segments = (int)seg.size() - 1;
146 permute.reserve(num_segments);
148 for (i = 0; i < num_segments; ++i) {
149 permute.push_back(i + 1);
177 while (construct_trapezoids(num_segments) != 0) {
180 for (i = 0; i < num_segments; ++i) {
182 nassertv(j >= 0 && j < num_segments);
184 permute[i] = permute[j];
210 int nmonpoly = monotonate_trapezoids(num_segments);
214 triangulate_monotone_polygons(num_segments, nmonpoly);
232 return _result.size();
246 nassertr(n >= 0 && n < (
int)_result.size(), -1);
247 return _result[n]._v0;
261 nassertr(n >= 0 && n < (
int)_result.size(), -1);
262 return _result[n]._v1;
276 nassertr(n >= 0 && n < (
int)_result.size(), -1);
277 return _result[n]._v2;
286 cleanup_polygon_indices(vector_int &polygon) {
289 while (pi < polygon.size()) {
290 if (polygon[pi] >= 0 && (
size_t)polygon[pi] < _vertices.size()) {
295 polygon.erase(_polygon.begin() + pi);
301 while (pi < polygon.size()) {
302 if (_vertices[polygon[pi]] != _vertices[polygon[pi - 1]]) {
307 polygon.erase(_polygon.begin() + pi);
311 if (polygon.size() > 1 && _vertices[polygon.back()] == _vertices[_polygon.front()]) {
330 #define REALLY_BIG 1<<30
346 #define SP_SIMPLE_LRUP 1
347 #define SP_SIMPLE_LRDN 2
349 #define SP_2UP_LEFT 4
350 #define SP_2UP_RIGHT 5
351 #define SP_2DN_LEFT 6
352 #define SP_2DN_RIGHT 7
353 #define SP_NOSPLIT -1
362 #define CROSS(v0, v1, v2) (((v1).x - (v0).x)*((v2).y - (v0).y) - \
363 ((v1).y - (v0).y)*((v2).x - (v0).x))
365 #define DOT(v0, v1) ((v0).x * (v1).x + (v0).y * (v1).y)
367 #define FP_EQUAL(s, t) (fabs(s - t) <= C_EPS)
370 #define CROSS_SINE(v0, v1) ((v0).x * (v1).y - (v1).x * (v0).y)
371 #define LENGTH(v0) (sqrt((v0).x * (v0).x + (v0).y * (v0).y))
381 check_left_winding(
const vector_int &range)
const {
386 size_t j = range.size() - 1;
387 for (
size_t i = 0; i < range.size(); ++i) {
388 const LPoint2d &p0 = _vertices[range[j]];
389 const LPoint2d &p1 = _vertices[range[i]];
390 area += p0[0] * p1[1] - p0[1] * p1[0];
406 make_segment(
const vector_int &range,
bool want_left_winding) {
407 int num_points = (int)range.size();
408 nassertv(num_points >= 2);
410 int first = (int)seg.size();
411 int last = first + num_points - 1;
413 if (want_left_winding == check_left_winding(range)) {
415 int first = (int)seg.size();
416 int last = first + num_points - 1;
418 seg.push_back(segment_t(
this, range[0], range[1],
421 for (
int i = 1; i < num_points - 1; ++i) {
422 seg.push_back(segment_t(
this, range[i], range[i + 1],
423 first + i - 1, first + i + 1));
426 seg.push_back(segment_t(
this, range[num_points - 1], range[0],
431 seg.push_back(segment_t(
this, range[0], range[num_points - 1],
434 for (
int i = 1; i < num_points - 1; ++i) {
435 seg.push_back(segment_t(
this, range[num_points - i], range[num_points - i - 1],
436 first + i - 1, first + i + 1));
439 seg.push_back(segment_t(
this, range[1], range[0],
449 nassertr(choose_idx < (
int)permute.size(), 0);
452 return permute[choose_idx++];
455 double Triangulator::
456 math_log2(
double v) {
457 static const double log2 = log(2.0);
458 return log(v) / log2;
463 math_logstar_n(
int n) {
467 for (i = 0, v = (
double) n; v >= 1; i++)
475 math_N(
int n,
int h) {
479 for (i = 0, v = (
int) n; i < h; i++)
482 return (
int) ceil((
double) 1.0*n/v);
487 int Triangulator::newnode() {
488 int index = (int)qs.size();
489 qs.push_back(node_t());
495 int Triangulator::newtrap() {
496 int tr_idx = (int)tr.size();
497 tr.push_back(trap_t());
498 tr[tr_idx].lseg = -1;
499 tr[tr_idx].rseg = -1;
500 tr[tr_idx].state = ST_VALID;
507 int Triangulator::_max(point_t *yval, point_t *v0, point_t *v1) {
508 if (v0->y > v1->y + C_EPS)
510 else if (FP_EQUAL(v0->y, v1->y))
512 if (v0->x > v1->x + C_EPS)
525 int Triangulator::_min(point_t *yval, point_t *v0, point_t *v1) {
526 if (v0->y < v1->y - C_EPS)
528 else if (FP_EQUAL(v0->y, v1->y))
543 _greater_than(point_t *v0, point_t *v1) {
544 if (v0->y > v1->y + C_EPS)
546 else if (v0->y < v1->y - C_EPS)
549 return (v0->x > v1->x);
554 _equal_to(point_t *v0, point_t *v1) {
555 return (FP_EQUAL(v0->y, v1->y) && FP_EQUAL(v0->x, v1->x));
559 _greater_than_equal_to(point_t *v0, point_t *v1) {
560 if (v0->y > v1->y + C_EPS)
562 else if (v0->y < v1->y - C_EPS)
565 return (v0->x >= v1->x);
569 _less_than(point_t *v0, point_t *v1) {
570 if (v0->y < v1->y - C_EPS)
572 else if (v0->y > v1->y + C_EPS)
575 return (v0->x < v1->x);
593 init_query_structure(
int segnum) {
594 int i1, i2, i3, i4, i5, i6, i7, root;
596 segment_t *s = &seg[segnum];
602 tr.push_back(trap_t());
603 qs.push_back(node_t());
606 qs[i1].nodetype = T_Y;
607 _max(&qs[i1].yval, &s->v0, &s->v1);
612 qs[i2].nodetype = T_SINK;
618 qs[i3].nodetype = T_Y;
619 _min(&qs[i3].yval, &s->v0, &s->v1);
624 qs[i4].nodetype = T_SINK;
629 qs[i5].nodetype = T_X;
630 qs[i5].segnum = segnum;
635 qs[i6].nodetype = T_SINK;
640 qs[i7].nodetype = T_SINK;
648 tr[t4].lo = qs[i1].yval;
649 tr[t2].hi = qs[i1].yval;
650 tr[t1].hi = qs[i1].yval;
651 tr[t3].hi = qs[i3].yval;
652 tr[t2].lo = qs[i3].yval;
653 tr[t1].lo = qs[i3].yval;
654 tr[t4].hi.y = (double) (REALLY_BIG);
655 tr[t4].hi.x = (double) (REALLY_BIG);
656 tr[t3].lo.y = (double) -1* (REALLY_BIG);
657 tr[t3].lo.x = (double) -1* (REALLY_BIG);
658 tr[t2].lseg = segnum;
659 tr[t1].rseg = segnum;
674 tr[t2].state = ST_VALID;
675 tr[t1].state = ST_VALID;
676 tr[t4].state = ST_VALID;
677 tr[t3].state = ST_VALID;
684 s->is_inserted =
true;
695 is_left_of(
int segnum, point_t *v) {
696 segment_t *s = &seg[segnum];
699 if (_greater_than(&s->v1, &s->v0))
701 if (FP_EQUAL(s->v1.y, v->y))
708 else if (FP_EQUAL(s->v0.y, v->y))
716 area = CROSS(s->v0, s->v1, (*v));
720 if (FP_EQUAL(s->v1.y, v->y))
727 else if (FP_EQUAL(s->v0.y, v->y))
735 area = CROSS(s->v1, s->v0, (*v));
751 inserted(
int segnum,
int whichpt) {
752 if (whichpt == FIRSTPT)
753 return seg[seg[segnum].prev].is_inserted;
755 return seg[seg[segnum].next].is_inserted;
763 locate_endpoint(point_t *v, point_t *vo,
int r) {
765 node_t *rptr = &qs[r];
767 switch (rptr->nodetype)
773 if (_greater_than(v, &rptr->yval))
774 return locate_endpoint(v, vo, rptr->right);
775 else if (_equal_to(v, &rptr->yval))
777 if (_greater_than(vo, &rptr->yval))
778 return locate_endpoint(v, vo, rptr->right);
780 return locate_endpoint(v, vo, rptr->left);
783 return locate_endpoint(v, vo, rptr->left);
786 if (_equal_to(v, &seg[rptr->segnum].v0) ||
787 _equal_to(v, &seg[rptr->segnum].v1))
789 if (FP_EQUAL(v->y, vo->y))
792 return locate_endpoint(v, vo, rptr->left);
794 return locate_endpoint(v, vo, rptr->right);
797 else if (is_left_of(rptr->segnum, vo))
798 return locate_endpoint(v, vo, rptr->left);
800 return locate_endpoint(v, vo, rptr->right);
802 else if (is_left_of(rptr->segnum, v))
803 return locate_endpoint(v, vo, rptr->left);
805 return locate_endpoint(v, vo, rptr->right);
808 fprintf(stderr,
"Haggu !!!!!\n");
823 merge_trapezoids(
int segnum,
int tfirst,
int tlast,
int side) {
831 while ((t > 0) && _greater_than_equal_to(&tr[t].lo, &tr[tlast].lo))
834 cond = ((((tnext = tr[t].d0) > 0) && (tr[tnext].rseg == segnum)) ||
835 (((tnext = tr[t].d1) > 0) && (tr[tnext].rseg == segnum)));
837 cond = ((((tnext = tr[t].d0) > 0) && (tr[tnext].lseg == segnum)) ||
838 (((tnext = tr[t].d1) > 0) && (tr[tnext].lseg == segnum)));
842 if ((tr[t].lseg == tr[tnext].lseg) &&
843 (tr[t].rseg == tr[tnext].rseg))
847 ptnext = qs[tr[tnext].sink].parent;
849 if (qs[ptnext].left == tr[tnext].sink)
850 qs[ptnext].left = tr[t].sink;
852 qs[ptnext].right = tr[t].sink;
857 if ((tr[t].d0 = tr[tnext].d0) > 0) {
858 if (tr[tr[t].d0].u0 == tnext) {
860 }
else if (tr[tr[t].d0].u1 == tnext) {
865 if ((tr[t].d1 = tr[tnext].d1) > 0) {
866 if (tr[tr[t].d1].u0 == tnext) {
868 }
else if (tr[tr[t].d1].u1 == tnext) {
873 tr[t].lo = tr[tnext].lo;
874 tr[tnext].state = ST_INVALID;
896 add_segment(
int segnum) {
901 int tu, tl, sk, tfirst, tlast;
902 int tfirstr = 0, tlastr = 0, tfirstl = 0, tlastl = 0;
905 int tritop = 0, tribot = 0, is_swapped = 0;
909 if (_greater_than(&s.v1, &s.v0))
921 if ((is_swapped) ? !inserted(segnum, LASTPT) :
922 !inserted(segnum, FIRSTPT))
926 tu = locate_endpoint(&s.v0, &s.v1, s.root0);
928 tr[tl].state = ST_VALID;
930 tr[tl].hi.y = s.v0.y;
931 tr[tu].lo.y = s.v0.y;
932 tr[tl].hi.x = s.v0.x;
933 tr[tu].lo.x = s.v0.x;
939 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u0 == tu))
941 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u1 == tu))
944 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u0 == tu))
946 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u1 == tu))
956 qs[sk].nodetype = T_Y;
958 qs[sk].segnum = segnum;
962 qs[i1].nodetype = T_SINK;
966 qs[i2].nodetype = T_SINK;
976 tfirst = locate_endpoint(&s.v0, &s.v1, s.root0);
981 if ((is_swapped) ? !inserted(segnum, FIRSTPT) :
982 !inserted(segnum, LASTPT))
986 tu = locate_endpoint(&s.v1, &s.v0, s.root1);
989 tr[tl].state = ST_VALID;
991 tr[tl].hi.y = s.v1.y;
992 tr[tu].lo.y = s.v1.y;
993 tr[tl].hi.x = s.v1.x;
994 tr[tu].lo.x = s.v1.x;
1000 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u0 == tu))
1002 if (((tmp_d = tr[tl].d0) > 0) && (tr[tmp_d].u1 == tu))
1005 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u0 == tu))
1007 if (((tmp_d = tr[tl].d1) > 0) && (tr[tmp_d].u1 == tu))
1017 qs[sk].nodetype = T_Y;
1019 qs[sk].segnum = segnum;
1023 qs[i1].nodetype = T_SINK;
1027 qs[i2].nodetype = T_SINK;
1037 tlast = locate_endpoint(&s.v1, &s.v0, s.root1);
1048 _greater_than_equal_to(&tr[t].lo, &tr[tlast].lo))
1056 qs[sk].nodetype = T_X;
1057 qs[sk].segnum = segnum;
1061 qs[i1].nodetype = T_SINK;
1065 qs[i2].nodetype = T_SINK;
1068 tr[tn].state = ST_VALID;
1073 if (_equal_to(&tr[t].lo, &tr[tlast].lo))
1084 if ((tr[t].d0 <= 0) && (tr[t].d1 <= 0))
1087 fprintf(stderr,
"add_segment: error\n");
1095 else if ((tr[t].d0 > 0) && (tr[t].d1 <= 0))
1097 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1099 if (tr[t].usave > 0)
1101 if (tr[t].uside == S_LEFT)
1103 tr[tn].u0 = tr[t].u1;
1105 tr[tn].u1 = tr[t].usave;
1107 tr[tr[t].u0].d0 = t;
1108 tr[tr[tn].u0].d0 = tn;
1109 tr[tr[tn].u1].d0 = tn;
1114 tr[tn].u0 = tr[t].u1;
1115 tr[t].u1 = tr[t].u0;
1116 tr[t].u0 = tr[t].usave;
1118 tr[tr[t].u0].d0 = t;
1119 tr[tr[t].u1].d0 = t;
1120 tr[tr[tn].u0].d0 = tn;
1127 tr[tn].u0 = tr[t].u1;
1130 tr[tr[tn].u0].d0 = tn;
1135 int tmp_u = tr[t].u0;
1137 if (((td0 = tr[tmp_u].d0) > 0) &&
1138 ((td1 = tr[tmp_u].d1) > 0))
1140 if ((tr[td0].rseg > 0) &&
1141 !is_left_of(tr[td0].rseg, &s.v1))
1146 tr[tr[tn].u0].d1 = tn;
1153 tr[tr[t].u0].d0 = t;
1158 tr[tr[t].u0].d0 = t;
1159 tr[tr[t].u0].d1 = tn;
1163 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1164 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1168 tmptriseg = seg[segnum].prev;
1170 tmptriseg = seg[segnum].next;
1172 if ((tmptriseg > 0) && is_left_of(tmptriseg, &s.v0))
1175 tr[tr[t].d0].u0 = t;
1182 tr[tr[tn].d0].u1 = tn;
1189 if ((tr[tr[t].d0].u0 > 0) && (tr[tr[t].d0].u1 > 0))
1191 if (tr[tr[t].d0].u0 == t)
1193 tr[tr[t].d0].usave = tr[tr[t].d0].u1;
1194 tr[tr[t].d0].uside = S_LEFT;
1198 tr[tr[t].d0].usave = tr[tr[t].d0].u0;
1199 tr[tr[t].d0].uside = S_RIGHT;
1202 tr[tr[t].d0].u0 = t;
1203 tr[tr[t].d0].u1 = tn;
1210 else if ((tr[t].d0 <= 0) && (tr[t].d1 > 0))
1212 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1214 if (tr[t].usave > 0)
1216 if (tr[t].uside == S_LEFT)
1218 tr[tn].u0 = tr[t].u1;
1220 tr[tn].u1 = tr[t].usave;
1222 tr[tr[t].u0].d0 = t;
1223 tr[tr[tn].u0].d0 = tn;
1224 tr[tr[tn].u1].d0 = tn;
1229 tr[tn].u0 = tr[t].u1;
1230 tr[t].u1 = tr[t].u0;
1231 tr[t].u0 = tr[t].usave;
1233 tr[tr[t].u0].d0 = t;
1234 tr[tr[t].u1].d0 = t;
1235 tr[tr[tn].u0].d0 = tn;
1243 tr[tn].u0 = tr[t].u1;
1246 tr[tr[tn].u0].d0 = tn;
1251 int tmp_u = tr[t].u0;
1253 if (((td0 = tr[tmp_u].d0) > 0) &&
1254 ((td1 = tr[tmp_u].d1) > 0))
1256 if ((tr[td0].rseg > 0) &&
1257 !is_left_of(tr[td0].rseg, &s.v1))
1262 tr[tr[tn].u0].d1 = tn;
1269 tr[tr[t].u0].d0 = t;
1274 tr[tr[t].u0].d0 = t;
1275 tr[tr[t].u0].d1 = tn;
1279 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1280 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1283 tmptriseg = seg[segnum].prev;
1285 tmptriseg = seg[segnum].next;
1287 if ((tmptriseg > 0) && is_left_of(tmptriseg, &s.v0))
1290 tr[tr[t].d1].u0 = t;
1297 tr[tr[tn].d1].u1 = tn;
1304 if ((tr[tr[t].d1].u0 > 0) && (tr[tr[t].d1].u1 > 0))
1306 if (tr[tr[t].d1].u0 == t)
1308 tr[tr[t].d1].usave = tr[tr[t].d1].u1;
1309 tr[tr[t].d1].uside = S_LEFT;
1313 tr[tr[t].d1].usave = tr[tr[t].d1].u0;
1314 tr[tr[t].d1].uside = S_RIGHT;
1317 tr[tr[t].d1].u0 = t;
1318 tr[tr[t].d1].u1 = tn;
1332 int tnext, i_d0, i_d1;
1336 if (FP_EQUAL(tr[t].lo.y, s.v0.y))
1338 if (tr[t].lo.x > s.v0.x)
1347 yt = (y0 - s.v0.y)/(s.v1.y - s.v0.y);
1348 tmppt.x = s.v0.x + yt * (s.v1.x - s.v0.x);
1350 if (_less_than(&tmppt, &tr[t].lo))
1359 if ((tr[t].u0 > 0) && (tr[t].u1 > 0))
1361 if (tr[t].usave > 0)
1363 if (tr[t].uside == S_LEFT)
1365 tr[tn].u0 = tr[t].u1;
1367 tr[tn].u1 = tr[t].usave;
1369 tr[tr[t].u0].d0 = t;
1370 tr[tr[tn].u0].d0 = tn;
1371 tr[tr[tn].u1].d0 = tn;
1376 tr[tn].u0 = tr[t].u1;
1377 tr[t].u1 = tr[t].u0;
1378 tr[t].u0 = tr[t].usave;
1380 tr[tr[t].u0].d0 = t;
1381 tr[tr[t].u1].d0 = t;
1382 tr[tr[tn].u0].d0 = tn;
1390 tr[tn].u0 = tr[t].u1;
1393 tr[tr[tn].u0].d0 = tn;
1398 int tmp_u = tr[t].u0;
1400 if (((td0 = tr[tmp_u].d0) > 0) &&
1401 ((td1 = tr[tmp_u].d1) > 0))
1403 if ((tr[td0].rseg > 0) &&
1404 !is_left_of(tr[td0].rseg, &s.v1))
1409 tr[tr[tn].u0].d1 = tn;
1416 tr[tr[t].u0].d0 = t;
1421 tr[tr[t].u0].d0 = t;
1422 tr[tr[t].u0].d1 = tn;
1426 if (FP_EQUAL(tr[t].lo.y, tr[tlast].lo.y) &&
1427 FP_EQUAL(tr[t].lo.x, tr[tlast].lo.x) && tribot)
1433 tr[tr[t].d0].u0 = t;
1434 tr[tr[t].d0].u1 = -1;
1435 tr[tr[t].d1].u0 = tn;
1436 tr[tr[t].d1].u1 = -1;
1438 tr[tn].d0 = tr[t].d1;
1447 tr[tr[t].d0].u0 = t;
1448 tr[tr[t].d0].u1 = tn;
1449 tr[tr[t].d1].u0 = tn;
1450 tr[tr[t].d1].u1 = -1;
1461 tr[tr[t].d0].u0 = t;
1462 tr[tr[t].d0].u1 = -1;
1463 tr[tr[t].d1].u0 = t;
1464 tr[tr[t].d1].u1 = tn;
1469 tr[tn].d0 = tr[t].d1;
1478 tr[tn_sav].lseg = segnum;
1479 tr[t_sav].rseg = segnum;
1489 merge_trapezoids(segnum, tfirstl, tlastl, S_LEFT);
1490 merge_trapezoids(segnum, tfirstr, tlastr, S_RIGHT);
1492 seg[segnum].is_inserted =
true;
1502 find_new_roots(
int segnum) {
1504 segment_t *s = &seg[segnum];
1509 s->root0 = locate_endpoint(&s->v0, &s->v1, s->root0);
1510 s->root0 = tr[s->root0].sink;
1512 s->root1 = locate_endpoint(&s->v1, &s->v0, s->root1);
1513 s->root1 = tr[s->root1].sink;
1520 construct_trapezoids(
int nseg) {
1528 root = init_query_structure(choose_segment());
1530 for (i = 1; i <= nseg; i++) {
1531 seg[i].root1 = root;
1532 seg[i].root0 = root;
1535 for (h = 1; h <= math_logstar_n(nseg); h++)
1537 for (i = math_N(nseg, h -1) + 1; i <= math_N(nseg, h); i++) {
1538 if (add_segment(choose_segment()) != 0) {
1545 for (i = 1; i <= nseg; i++)
1549 for (i = math_N(nseg, math_logstar_n(nseg)) + 1; i <= nseg; i++)
1550 add_segment(choose_segment());
1559 inside_polygon(trap_t *t) {
1562 if (t->state == ST_INVALID)
1565 if ((t->lseg <= 0) || (t->rseg <= 0))
1568 if (((t->u0 <= 0) && (t->u1 <= 0)) ||
1569 ((t->d0 <= 0) && (t->d1 <= 0)))
1570 return (_greater_than(&seg[rseg].v1, &seg[rseg].v0));
1579 int index = (int)mon.size();
1588 new_chain_element() {
1589 int index = (int)mchain.size();
1590 mchain.push_back(monchain_t());
1596 double Triangulator::
1597 get_angle(point_t *vp0, point_t *vpnext, point_t *vp1) {
1600 v0.x = vpnext->x - vp0->x;
1601 v0.y = vpnext->y - vp0->y;
1603 v1.x = vp1->x - vp0->x;
1604 v1.y = vp1->y - vp0->y;
1606 if (CROSS_SINE(v0, v1) >= 0)
1607 return DOT(v0, v1)/LENGTH(v0)/LENGTH(v1);
1609 return (-1.0 * DOT(v0, v1)/LENGTH(v0)/LENGTH(v1) - 2);
1616 get_vertex_positions(
int v0,
int v1,
int *ip,
int *iq) {
1617 vertexchain_t *vp0, *vp1;
1630 for (i = 0; i < 4; i++)
1632 if (vp0->vnext[i] <= 0)
1634 if ((temp = get_angle(&vp0->pt, &(vert[vp0->vnext[i]].pt),
1647 for (i = 0; i < 4; i++)
1649 if (vp1->vnext[i] <= 0)
1651 if ((temp = get_angle(&vp1->pt, &(vert[vp1->vnext[i]].pt),
1670 make_new_monotone_poly(
int mcur,
int v0,
int v1) {
1672 int mnew = newmon();
1674 vertexchain_t *vp0, *vp1;
1676 if (v0 <= 0 || v1 <= 0) {
1683 get_vertex_positions(v0, v1, &ip, &iq);
1691 i = new_chain_element();
1692 j = new_chain_element();
1694 mchain[i].vnum = v0;
1695 mchain[j].vnum = v1;
1697 mchain[i].next = mchain[p].next;
1698 mchain[mchain[p].next].prev = i;
1701 mchain[j].prev = mchain[q].prev;
1702 mchain[mchain[q].prev].next = j;
1707 nf0 = vp0->nextfree;
1708 nf1 = vp1->nextfree;
1710 vp0->vnext[ip] = v1;
1713 vp0->vnext[nf0] = mchain[mchain[i].next].vnum;
1715 vp1->vnext[nf1] = v0;
1721 fprintf(stderr,
"make_poly: mcur = %d, (v0, v1) = (%d, %d)\n",
1723 fprintf(stderr,
"next posns = (p, q) = (%d, %d)\n", p, q);
1736 monotonate_trapezoids(
int n) {
1745 vert.insert(vert.begin(), n + 1, vertexchain_t());
1746 mchain.insert(mchain.begin(), n + 1, monchain_t());
1748 visited.insert(visited.begin(), tr.size(), 0);
1752 for (i = 1; i < (int)tr.size(); i++)
1753 if (inside_polygon(&tr[i]))
1755 if (i >= (
int)tr.size()) {
1766 for (i = 1; i <= n; i++)
1768 mchain[i].prev = i - 1;
1769 mchain[i].next = i + 1;
1771 vert[i].pt = seg[i].v0;
1772 vert[i].vnext[0] = i + 1;
1773 vert[i].vpos[0] = i;
1774 vert[i].nextfree = 1;
1775 vert[i].user_i = seg[i].v0_i;
1779 vert[n].vnext[0] = 1;
1780 vert[n].vpos[0] = n;
1786 for (i = 1; i <= n; i++)
1788 mchain[i].prev = seg[i].prev;
1789 mchain[i].next = seg[i].next;
1791 vert[i].pt = seg[i].v0;
1792 vert[i].vnext[0] = seg[i].next;
1793 vert[i].vpos[0] = i;
1794 vert[i].nextfree = 1;
1795 vert[i].user_i = seg[i].v0_i;
1804 if (tr[tr_start].u0 > 0)
1805 traverse_polygon(0, tr_start, tr[tr_start].u0, TR_FROM_UP);
1806 else if (tr[tr_start].d0 > 0)
1807 traverse_polygon(0, tr_start, tr[tr_start].d0, TR_FROM_DN);
1816 traverse_polygon(
int mcur,
int trnum,
int from,
int dir) {
1819 if (mcur < 0 || trnum <= 0)
1825 trap_t *t = &tr[trnum];
1830 int do_switch =
false;
1834 visited[trnum] =
true;
1846 if ((t->u0 <= 0) && (t->u1 <= 0))
1848 if ((t->d0 > 0) && (t->d1 > 0))
1850 v0 = tr[t->d1].lseg;
1855 mnew = make_new_monotone_poly(mcur, v1, v0);
1856 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1857 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1861 mnew = make_new_monotone_poly(mcur, v0, v1);
1862 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1863 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1868 retval = SP_NOSPLIT;
1869 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1870 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1871 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1872 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1876 else if ((t->d0 <= 0) && (t->d1 <= 0))
1878 if ((t->u0 > 0) && (t->u1 > 0))
1881 v1 = tr[t->u0].rseg;
1885 mnew = make_new_monotone_poly(mcur, v1, v0);
1886 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1887 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1891 mnew = make_new_monotone_poly(mcur, v0, v1);
1892 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1893 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1898 retval = SP_NOSPLIT;
1899 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1900 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1901 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1902 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1906 else if ((t->u0 > 0) && (t->u1 > 0))
1908 if ((t->d0 > 0) && (t->d1 > 0))
1910 v0 = tr[t->d1].lseg;
1911 v1 = tr[t->u0].rseg;
1912 retval = SP_2UP_2DN;
1913 if (((dir == TR_FROM_DN) && (t->d1 == from)) ||
1914 ((dir == TR_FROM_UP) && (t->u1 == from)))
1917 mnew = make_new_monotone_poly(mcur, v1, v0);
1918 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1919 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1920 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1921 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1925 mnew = make_new_monotone_poly(mcur, v0, v1);
1926 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1927 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1928 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1929 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1934 if (_equal_to(&t->lo, &seg[t->lseg].v1))
1936 v0 = tr[t->u0].rseg;
1937 v1 = seg[t->lseg].next;
1939 retval = SP_2UP_LEFT;
1940 if ((dir == TR_FROM_UP) && (t->u0 == from))
1943 mnew = make_new_monotone_poly(mcur, v1, v0);
1944 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1945 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1946 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1947 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1951 mnew = make_new_monotone_poly(mcur, v0, v1);
1952 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1953 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1954 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1955 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1961 v1 = tr[t->u0].rseg;
1962 retval = SP_2UP_RIGHT;
1963 if ((dir == TR_FROM_UP) && (t->u1 == from))
1966 mnew = make_new_monotone_poly(mcur, v1, v0);
1967 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1968 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
1969 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
1970 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
1974 mnew = make_new_monotone_poly(mcur, v0, v1);
1975 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1976 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
1977 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1978 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
1983 else if ((t->u0 > 0) || (t->u1 > 0))
1985 if ((t->d0 > 0) && (t->d1 > 0))
1987 if (_equal_to(&t->hi, &seg[t->lseg].v0))
1989 v0 = tr[t->d1].lseg;
1991 retval = SP_2DN_LEFT;
1992 if (!((dir == TR_FROM_DN) && (t->d0 == from)))
1995 mnew = make_new_monotone_poly(mcur, v1, v0);
1996 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
1997 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
1998 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
1999 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2003 mnew = make_new_monotone_poly(mcur, v0, v1);
2004 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2005 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2006 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2007 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2012 v0 = tr[t->d1].lseg;
2013 v1 = seg[t->rseg].next;
2015 retval = SP_2DN_RIGHT;
2016 if ((dir == TR_FROM_DN) && (t->d1 == from))
2019 mnew = make_new_monotone_poly(mcur, v1, v0);
2020 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2021 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2022 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2023 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2027 mnew = make_new_monotone_poly(mcur, v0, v1);
2028 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2029 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2030 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2031 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2037 if (_equal_to(&t->hi, &seg[t->lseg].v0) &&
2038 _equal_to(&t->lo, &seg[t->rseg].v0))
2042 retval = SP_SIMPLE_LRDN;
2043 if (dir == TR_FROM_UP)
2046 mnew = make_new_monotone_poly(mcur, v1, v0);
2047 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2048 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2049 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2050 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2054 mnew = make_new_monotone_poly(mcur, v0, v1);
2055 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2056 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2057 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2058 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2061 else if (_equal_to(&t->hi, &seg[t->rseg].v1) &&
2062 _equal_to(&t->lo, &seg[t->lseg].v1))
2064 v0 = seg[t->rseg].next;
2065 v1 = seg[t->lseg].next;
2067 retval = SP_SIMPLE_LRUP;
2068 if (dir == TR_FROM_UP)
2071 mnew = make_new_monotone_poly(mcur, v1, v0);
2072 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2073 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2074 traverse_polygon(mnew, t->d1, trnum, TR_FROM_UP);
2075 traverse_polygon(mnew, t->d0, trnum, TR_FROM_UP);
2079 mnew = make_new_monotone_poly(mcur, v0, v1);
2080 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2081 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2082 traverse_polygon(mnew, t->u0, trnum, TR_FROM_DN);
2083 traverse_polygon(mnew, t->u1, trnum, TR_FROM_DN);
2088 retval = SP_NOSPLIT;
2089 traverse_polygon(mcur, t->u0, trnum, TR_FROM_DN);
2090 traverse_polygon(mcur, t->d0, trnum, TR_FROM_UP);
2091 traverse_polygon(mcur, t->u1, trnum, TR_FROM_DN);
2092 traverse_polygon(mcur, t->d1, trnum, TR_FROM_UP);
2107 triangulate_monotone_polygons(
int nvert,
int nmonpoly) {
2110 int p, vfirst, posmax, posmin, v;
2111 int vcount, processed;
2114 for (i = 0; i < nmonpoly; i++)
2116 fprintf(stderr,
"\n\nPolygon %d: ", i);
2117 vfirst = mchain[mon[i]].vnum;
2118 p = mchain[mon[i]].next;
2119 fprintf (stderr,
"%d ", mchain[mon[i]].vnum);
2120 while (mchain[p].vnum != vfirst)
2122 fprintf(stderr,
"%d ", mchain[p].vnum);
2123 if (mchain[p].vnum == -1) {
2124 fprintf(stderr,
" xx");
2130 fprintf(stderr,
"\n");
2133 for (i = 0; i < nmonpoly; i++)
2137 vfirst = mchain[mon[i]].vnum;
2141 ymin = vert[vfirst].pt;
2145 mchain[mon[i]].marked =
true;
2146 p = mchain[mon[i]].next;
2147 while ((v = mchain[p].vnum) != vfirst)
2152 if (mchain[p].marked)
2158 mchain[p].marked =
true;
2160 if (_greater_than(&vert[v].pt, &ymax))
2165 if (_less_than(&vert[v].pt, &ymin))
2179 _result.push_back(Triangle(
this, mchain[p].vnum,
2180 mchain[mchain[p].next].vnum,
2181 mchain[mchain[p].prev].vnum));
2185 v = mchain[mchain[posmax].next].vnum;
2186 if (_equal_to(&vert[v].pt, &ymin))
2188 triangulate_single_polygon(nvert, posmax, TRI_LHS);
2191 triangulate_single_polygon(nvert, posmax, TRI_RHS);
2202 triangulate_single_polygon(
int nvert,
int posmax,
int side) {
2206 int endv, tmp, vpos;
2210 if (side == TRI_RHS)
2212 rc.push_back(mchain[posmax].vnum);
2213 tmp = mchain[posmax].next;
2214 rc.push_back(mchain[tmp].vnum);
2217 vpos = mchain[tmp].next;
2218 v = mchain[vpos].vnum;
2220 if ((endv = mchain[mchain[posmax].prev].vnum) == 0)
2225 tmp = mchain[posmax].next;
2226 rc.push_back(mchain[tmp].vnum);
2227 tmp = mchain[tmp].next;
2228 rc.push_back(mchain[tmp].vnum);
2231 vpos = mchain[tmp].next;
2232 v = mchain[vpos].vnum;
2234 endv = mchain[posmax].vnum;
2237 while ((v != endv) || (ri > 1))
2246 PN_stdfloat crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
2248 if ( crossResult >= 0 )
2250 if ( crossResult > 0)
2251 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));
2255 nassertv(ri + 1 == (
int)rc.size());
2261 nassertv(ri + 1 == (
int)rc.size());
2262 vpos = mchain[vpos].next;
2263 v = mchain[vpos].vnum;
2270 nassertv(ri + 1 == (
int)rc.size());
2271 vpos = mchain[vpos].next;
2272 v = mchain[vpos].vnum;
2277 _result.push_back(Triangle(
this, rc[ri - 1], rc[ri], v));
int get_triangle_v0(int n) const
Returns vertex 0 of the nth triangle generated by the previous call to triangulate().
void triangulate()
Does the work of triangulating the specified polygon.
int get_triangle_v1(int n) const
Returns vertex 1 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.
This is a two-component point in space.
int get_triangle_v2(int n) const
Returns vertex 2 of the nth triangle generated by the previous call to triangulate().
int get_num_triangles() const
Returns the number of triangles 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).
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 add_vertex(const LPoint2d &point)
Adds a new vertex to the vertex pool.