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));
void triangulate()
Does the work of triangulating the specified polygon.
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.
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().
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).
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.