00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "eggPolygon.h"
00016 #include "eggGroupNode.h"
00017 #include "plane.h"
00018
00019 #include "indent.h"
00020
00021 #include <algorithm>
00022
00023 TypeHandle EggPolygon::_type_handle;
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 bool EggPolygon::
00036 cleanup() {
00037 remove_doubled_verts(true);
00038
00039
00040 LNormald normal;
00041 return calculate_normal(normal);
00042 }
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056 bool EggPolygon::
00057 calculate_normal(LNormald &result, CoordinateSystem cs) const {
00058 result = LNormald::zero();
00059
00060
00061
00062
00063
00064
00065 size_t num_verts = size();
00066 for (size_t i = 0; i < num_verts; i++) {
00067 LVertexd p0 = get_vertex(i)->get_pos3();
00068 LVertexd p1 = get_vertex((i + 1) % num_verts)->get_pos3();
00069 result[0] += p0[1] * p1[2] - p0[2] * p1[1];
00070 result[1] += p0[2] * p1[0] - p0[0] * p1[2];
00071 result[2] += p0[0] * p1[1] - p0[1] * p1[0];
00072 }
00073
00074 if (!result.normalize()) {
00075
00076 return false;
00077 }
00078
00079 if (cs == CS_default) {
00080 cs = get_default_coordinate_system();
00081 }
00082 if (cs == CS_zup_left || cs == CS_yup_left) {
00083
00084 result = -result;
00085 }
00086 return true;
00087 }
00088
00089
00090
00091
00092
00093
00094
00095 bool EggPolygon::
00096 is_planar() const {
00097 if (size() <= 3) {
00098
00099
00100 return true;
00101 }
00102
00103 LNormald normal;
00104 if (!calculate_normal(normal)) {
00105
00106
00107
00108 return true;
00109 }
00110
00111
00112
00113 nassertr(!empty(), false);
00114
00115
00116
00117 const_iterator vi = begin();
00118 LVecBase3d first_point = (*vi)->get_pos3();
00119 LPlaned plane(normal, first_point);
00120
00121
00122
00123 ++vi;
00124 while (vi != end()) {
00125 LVecBase3d this_point = (*vi)->get_pos3();
00126 if (!this_point.almost_equal(first_point)) {
00127 double dist = plane.dist_to_plane(this_point);
00128 double tol = dist / length(this_point - first_point);
00129 if (!IS_THRESHOLD_ZERO(tol, 0.0001)) {
00130
00131 return false;
00132 }
00133 }
00134 ++vi;
00135 }
00136
00137
00138 return true;
00139 }
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155 PT(EggPolygon) EggPolygon::
00156 triangulate_in_place(bool convex_also) {
00157 EggGroupNode *parent = get_parent();
00158 nassertr(parent != (EggGroupNode *)NULL, this);
00159
00160 PT(EggPolygon) save_me = this;
00161 parent->remove_child(this);
00162 triangulate_poly(parent, convex_also);
00163
00164 return save_me;
00165 }
00166
00167
00168
00169
00170
00171
00172
00173 void EggPolygon::
00174 write(ostream &out, int indent_level) const {
00175 write_header(out, indent_level, "<Polygon>");
00176 write_body(out, indent_level+2);
00177 indent(out, indent_level) << "}\n";
00178 }
00179
00180
00181
00182
00183
00184
00185
00186
00187 bool EggPolygon::
00188 decomp_concave(EggGroupNode *container, int asum, int x, int y) const {
00189 #define VX(p, c) p->coord[c]
00190
00191 struct DecompVtx {
00192 int index;
00193 LPoint3d coord;
00194 struct DecompVtx *next;
00195 };
00196
00197 DecompVtx *p0, *p1, *p2, *t0, *vert;
00198 DecompVtx *m[3];
00199 double xmin, xmax, ymin, ymax;
00200 int i, init, csum, chek;
00201 double a[3], b[3], c[3], s[3];
00202
00203 int num_verts = size();
00204 nassertr(num_verts >= 3, false);
00205
00206
00207 vert = (DecompVtx *) alloca(sizeof(DecompVtx));
00208 vert->index = 0;
00209 vert->coord = get_vertex(0)->get_pos3();
00210 p1 = vert;
00211
00212 for (i = 1; i < num_verts; i++) {
00213 p0 = (DecompVtx *) alloca(sizeof(DecompVtx));
00214 p0->index = i;
00215 p0->coord = get_vertex(i)->get_pos3();
00216
00217
00218 if (!(p0->coord == p1->coord)) {
00219 p1->next = p0;
00220 p1 = p0;
00221 }
00222 }
00223 p1->next = vert;
00224
00225 p0 = vert;
00226 p1 = p0->next;
00227 p2 = p1->next;
00228 m[0] = p0;
00229 m[1] = p1;
00230 m[2] = p2;
00231 chek = 0;
00232
00233 while (p0 != p2->next) {
00234
00235 if (chek &&
00236 m[0] == p0 &&
00237 m[1] == p1 &&
00238 m[2] == p2) {
00239
00240 return false;
00241 }
00242
00243 chek = 1;
00244
00245 a[0] = VX(p1, y) - VX(p2, y);
00246 b[0] = VX(p2, x) - VX(p1, x);
00247 a[2] = VX(p0, y) - VX(p1, y);
00248 b[2] = VX(p1, x) - VX(p0, x);
00249
00250 csum = ((b[0] * a[2] - b[2] * a[0] >= 0.0) ? 1 : 0);
00251
00252 if (csum ^ asum) {
00253
00254 p0 = p1;
00255 p1 = p2;
00256 p2 = p2->next;
00257
00258 } else {
00259
00260 xmin = (VX(p0, x) < VX(p1, x)) ? VX(p0, x) : VX(p1, x);
00261 if (xmin > VX(p2, x))
00262 xmin = VX(p2, x);
00263
00264 xmax = (VX(p0, x) > VX(p1, x)) ? VX(p0, x) : VX(p1, x);
00265 if (xmax < VX(p2, x))
00266 xmax = VX(p2, x);
00267
00268 ymin = (VX(p0, y) < VX(p1, y)) ? VX(p0, y) : VX(p1, y);
00269 if (ymin > VX(p2, y))
00270 ymin = VX(p2, y);
00271
00272 ymax = (VX(p0, y) > VX(p1, y)) ? VX(p0, y) : VX(p1, y);
00273 if (ymax < VX(p2, y))
00274 ymax = VX(p2, y);
00275
00276 for (init = 1, t0 = p2->next; t0 != p0; t0 = t0->next) {
00277 if (VX(t0, x) >= xmin && VX(t0, x) <= xmax &&
00278 VX(t0, y) >= ymin && VX(t0, y) <= ymax) {
00279 if (init) {
00280 a[1] = VX(p2, y) - VX(p0, y);
00281 b[1] = VX(p0, x) - VX(p2, x);
00282 init = 0;
00283 c[0] = VX(p1, x) * VX(p2, y) - VX(p2, x) * VX(p1, y);
00284 c[1] = VX(p2, x) * VX(p0, y) - VX(p0, x) * VX(p2, y);
00285 c[2] = VX(p0, x) * VX(p1, y) - VX(p1, x) * VX(p0, y);
00286 }
00287
00288 s[0] = a[0] * VX(t0, x) + b[0] * VX(t0, y) + c[0];
00289 s[1] = a[1] * VX(t0, x) + b[1] * VX(t0, y) + c[1];
00290 s[2] = a[2] * VX(t0, x) + b[2] * VX(t0, y) + c[2];
00291
00292 if (asum) {
00293 if (s[0] >= 0.0 && s[1] >= 0.0 && s[2] >= 0.0)
00294 break;
00295 } else {
00296 if (s[0] <= 0.0 && s[1] <= 0.0 && s[2] <= 0.0)
00297 break;
00298 }
00299 }
00300 }
00301
00302 if (t0 != p0) {
00303 p0 = p1;
00304 p1 = p2;
00305 p2 = p2->next;
00306 } else {
00307
00308
00309 PT(EggPolygon) triangle = new EggPolygon(*this);
00310 triangle->clear();
00311 triangle->add_vertex(get_vertex(p0->index));
00312 triangle->add_vertex(get_vertex(p1->index));
00313 triangle->add_vertex(get_vertex(p2->index));
00314
00315 if (triangle->cleanup()) {
00316 container->add_child(triangle.p());
00317 }
00318
00319 p0->next = p1->next;
00320 p1 = p2;
00321 p2 = p2->next;
00322
00323 m[0] = p0;
00324 m[1] = p1;
00325 m[2] = p2;
00326 chek = 0;
00327 }
00328 }
00329 }
00330
00331
00332 PT(EggPolygon) triangle = new EggPolygon(*this);
00333 triangle->clear();
00334 triangle->add_vertex(get_vertex(p0->index));
00335 triangle->add_vertex(get_vertex(p1->index));
00336 triangle->add_vertex(get_vertex(p2->index));
00337
00338 if (triangle->cleanup()) {
00339 container->add_child(triangle.p());
00340 }
00341
00342 return true;
00343 }
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365 bool EggPolygon::
00366 triangulate_poly(EggGroupNode *container, bool convex_also) {
00367 LPoint3d p0, p1, as;
00368 double dx1, dy1, dx2, dy2, max;
00369 int i, flag, asum, csum, index, x, y, v0, v1, v, even;
00370
00371 if (!cleanup()) {
00372 return false;
00373 }
00374
00375
00376 int num_verts = size();
00377 if (num_verts == 3) {
00378 container->add_child(this);
00379
00380 return true;
00381
00382 } else if (num_verts < 3) {
00383
00384 return false;
00385 }
00386
00387
00388 as[0] = 0.0;
00389 as[1] = 0.0;
00390 as[2] = 0.0;
00391
00392 for (i = 0; i < num_verts; i++) {
00393 p0 = get_vertex(i)->get_pos3();
00394 p1 = get_vertex((i + 1) % num_verts)->get_pos3();
00395 as[0] += p0[0] * p1[1] - p0[1] * p1[0];
00396 as[1] += p0[0] * p1[2] - p0[2] * p1[0];
00397 as[2] += p0[1] * p1[2] - p0[2] * p1[1];
00398 }
00399
00400
00401 max = 0.0;
00402 index = 0;
00403 flag = 0;
00404 for (i = 0; i < 3; i++) {
00405 if (as[i] >= 0.0) {
00406 if (as[i] > max) {
00407 max = as[i];
00408 index = i;
00409 flag = 1;
00410 }
00411 } else {
00412 as[i] = -as[i];
00413 if (as[i] > max) {
00414 max = as[i];
00415 index = i;
00416 flag = 0;
00417 }
00418 }
00419 }
00420
00421
00422 switch (index) {
00423 case 0:
00424 x = 0;
00425 y = 1;
00426 break;
00427
00428 case 1:
00429 x = 0;
00430 y = 2;
00431 break;
00432
00433 default:
00434 x = 1;
00435 y = 2;
00436 break;
00437 }
00438
00439
00440 p0 = get_vertex(0)->get_pos3();
00441 p1 = get_vertex(1)->get_pos3();
00442 dx1 = p1[x] - p0[x];
00443 dy1 = p1[y] - p0[y];
00444 p0 = p1;
00445 p1 = get_vertex(2)->get_pos3();
00446
00447 dx2 = p1[x] - p0[x];
00448 dy2 = p1[y] - p0[y];
00449 asum = ((dx1 * dy2 - dx2 * dy1 >= 0.0) ? 1 : 0);
00450
00451 for (i = 0; i < num_verts - 1; i++) {
00452 p0 = p1;
00453 p1 = get_vertex((i+3) % num_verts)->get_pos3();
00454
00455 dx1 = dx2;
00456 dy1 = dy2;
00457 dx2 = p1[x] - p0[x];
00458 dy2 = p1[y] - p0[y];
00459 csum = ((dx1 * dy2 - dx2 * dy1 >= 0.0) ? 1 : 0);
00460
00461 if (csum ^ asum) {
00462
00463 return decomp_concave(container, flag, x, y);
00464 }
00465 }
00466
00467
00468 if (!convex_also) {
00469
00470
00471 if (is_planar()) {
00472 container->add_child(this);
00473 return true;
00474 }
00475 }
00476
00477 v0 = 0;
00478 v1 = 1;
00479 v = num_verts - 1;
00480
00481 even = 1;
00482
00483
00484
00485
00486
00487 for (i = 0; i < num_verts - 2; i++) {
00488 if (even) {
00489 PT(EggPolygon) triangle = new EggPolygon(*this);
00490 triangle->clear();
00491 triangle->add_vertex(get_vertex(v0));
00492 triangle->add_vertex(get_vertex(v1));
00493 triangle->add_vertex(get_vertex(v));
00494
00495 if (triangle->cleanup()) {
00496 container->add_child(triangle.p());
00497 }
00498
00499 v0 = v1;
00500 v1 = v;
00501 v = v0 + 1;
00502 } else {
00503 PT(EggPolygon) triangle = new EggPolygon(*this);
00504 triangle->clear();
00505 triangle->add_vertex(get_vertex(v1));
00506 triangle->add_vertex(get_vertex(v0));
00507 triangle->add_vertex(get_vertex(v));
00508
00509 if (triangle->cleanup()) {
00510 container->add_child(triangle.p());
00511 }
00512
00513 v0 = v1;
00514 v1 = v;
00515 v = v0 - 1;
00516 }
00517
00518 even = !even;
00519 }
00520
00521 return true;
00522 }