# eggPolygon.cxx

```00001 // Filename: eggPolygon.cxx
00002 // Created by:  drose (16Jan99)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
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 {
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();
00314
00315         if (triangle->cleanup()) {
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();
00337
00338   if (triangle->cleanup()) {
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) {
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()) {
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();
00494
00495       if (triangle->cleanup()) {
00497       }
00498
00499       v0 = v1;
00500       v1 = v;
00501       v = v0 + 1;
00502     } else {
00503       PT(EggPolygon) triangle = new EggPolygon(*this);
00504       triangle->clear();
00508
00509       if (triangle->cleanup()) {
00511       }
00512
00513       v0 = v1;
00514       v1 = v;
00515       v = v0 - 1;
00516     }
00517
00518     even = !even;
00519   }
00520
00521   return true;
00522 }
```