Panda3D
|
00001 // Filename: eggPolygon.cxx 00002 // Created by: drose (16Jan99) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 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 // Function: EggPolygon::cleanup 00028 // Access: Published, Virtual 00029 // Description: Cleans up modeling errors in whatever context this 00030 // makes sense. For instance, for a polygon, this calls 00031 // remove_doubled_verts(true). For a point, it calls 00032 // remove_nonunique_verts(). Returns true if the 00033 // primitive is valid, or false if it is degenerate. 00034 //////////////////////////////////////////////////////////////////// 00035 bool EggPolygon:: 00036 cleanup() { 00037 remove_doubled_verts(true); 00038 00039 // Use calculate_normal() to determine if the polygon is degenerate. 00040 LNormald normal; 00041 return calculate_normal(normal); 00042 } 00043 00044 //////////////////////////////////////////////////////////////////// 00045 // Function: EggPolygon::calculate_normal 00046 // Access: Published 00047 // Description: Calculates the true polygon normal--the vector 00048 // pointing out of the front of the polygon--based on 00049 // the vertices. This does not return or change the 00050 // polygon's normal as set via set_normal(). 00051 // 00052 // The return value is true if the normal is computed 00053 // correctly, or false if the polygon is degenerate and 00054 // does not have at least three noncollinear vertices. 00055 //////////////////////////////////////////////////////////////////// 00056 bool EggPolygon:: 00057 calculate_normal(LNormald &result, CoordinateSystem cs) const { 00058 result = LNormald::zero(); 00059 00060 // Project the polygon into each of the three major planes and 00061 // calculate the area of each 2-d projection. This becomes the 00062 // polygon normal. This works because the ratio between these 00063 // different areas corresponds to the angle at which the polygon is 00064 // tilted toward each plane. 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 // The polygon is degenerate: it has zero area in each plane. 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 // In a left-handed coordinate system, we must flip the result. 00084 result = -result; 00085 } 00086 return true; 00087 } 00088 00089 //////////////////////////////////////////////////////////////////// 00090 // Function: EggPolygon::is_planar 00091 // Access: Published 00092 // Description: Returns true if all of the polygon's vertices lie 00093 // within the same plane, false otherwise. 00094 //////////////////////////////////////////////////////////////////// 00095 bool EggPolygon:: 00096 is_planar() const { 00097 if (size() <= 3) { 00098 // If we don't have more than three vertices, we can't be 00099 // non-planar. 00100 return true; 00101 } 00102 00103 LNormald normal; 00104 if (!calculate_normal(normal)) { 00105 // A degenerate polygon--all of the vertices are within one line, 00106 // or all in the same point--is technically planar. Not sure if 00107 // this is a useful return value or not. 00108 return true; 00109 } 00110 00111 // There should be at least one vertex (actually, at least three) 00112 // since we have already shown that the polygon is nondegenerate. 00113 nassertr(!empty(), false); 00114 00115 // Create a plane perpendicular to the polygon's normal, containing 00116 // the first vertex. 00117 const_iterator vi = begin(); 00118 LVecBase3d first_point = (*vi)->get_pos3(); 00119 LPlaned plane(normal, first_point); 00120 00121 // And check that all of the remaining vertices are sufficiently 00122 // close to the plane. 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 // Nope, too far away--the polygon is nonplanar. 00131 return false; 00132 } 00133 } 00134 ++vi; 00135 } 00136 00137 // All vertices are close enough to pass. 00138 return true; 00139 } 00140 00141 //////////////////////////////////////////////////////////////////// 00142 // Function: EggPolygon::triangulate_in_place 00143 // Access: Published 00144 // Description: Subdivides the polygon into triangles and adds those 00145 // triangles to the parent group node in place of the 00146 // original polygon. Returns a pointer to the original 00147 // polygon, which is likely about to be destructed. 00148 // 00149 // If convex_also is true, both concave and convex 00150 // polygons will be subdivided into triangles; 00151 // otherwise, only concave polygons will be subdivided, 00152 // and convex polygons will be copied unchanged into the 00153 // container. 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 // Function: EggPolygon::write 00169 // Access: Published, Virtual 00170 // Description: Writes the polygon to the indicated output stream in 00171 // Egg format. 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 // Function: EggPolygon::decomp_concave 00182 // Access: Private 00183 // Description: Decomposes a concave polygon into triangles. Returns 00184 // true if successful, false if the polygon is 00185 // self-intersecting. 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 /* Make linked list of verts */ 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 // There shouldn't be two consecutive identical vertices. If 00217 // there are, skip one. 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 /* Polygon is self-intersecting so punt */ 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 /* current angle is concave */ 00254 p0 = p1; 00255 p1 = p2; 00256 p2 = p2->next; 00257 00258 } else { 00259 /* current angle is convex */ 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 // Here's a triangle to output. 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 // One more triangle to output. 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 // Function: EggPolygon::triangulate_poly 00348 // Access: Private 00349 // Description: Breaks a (possibly concave) higher-order polygon into 00350 // a series of constituent triangles. Fills the 00351 // container up with EggPolygons that represent the 00352 // triangles. Returns true if successful, false on 00353 // failure. 00354 // 00355 // If convex_also is true, both concave and convex 00356 // polygons will be subdivided into triangles; 00357 // otherwise, only concave polygons will be subdivided, 00358 // and convex polygons will be copied unchanged into the 00359 // container. 00360 // 00361 // It is assumed that the EggPolygon is not already a 00362 // child of any other group when this function is 00363 // called. 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 // First see if the polygon is already a triangle 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 // Or if it's a degenerate polygon. 00384 return false; 00385 } 00386 00387 // calculate signed areas 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 /* select largest signed area */ 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 /* pointer offsets */ 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: // case 2 00434 x = 1; 00435 y = 2; 00436 break; 00437 } 00438 00439 /* concave check */ 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 // It's a concave polygon. This is a little harder. 00463 return decomp_concave(container, flag, x, y); 00464 } 00465 } 00466 00467 // It's a convex polygon. 00468 if (!convex_also) { 00469 // Make sure that it's also coplanar. If it's not, we should 00470 // triangulate it anyway. 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 * Convert to triangles only. Do not fan out from a single vertex 00485 * but zigzag into triangle strip. 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 }