Panda3D
 All Classes Functions Variables Enumerations
triangulator.h
00001 // Filename: triangulator.h
00002 // Created by:  drose (17Jan07)
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 #ifndef TRIANGULATOR_H
00016 #define TRIANGULATOR_H
00017 
00018 #include "pandabase.h"
00019 #include "luse.h"
00020 #include "vector_int.h"
00021 
00022 ////////////////////////////////////////////////////////////////////
00023 //       Class : Triangulator
00024 // Description : This class can triangulate a convex or concave
00025 //               polygon, even one with holes.  It is adapted from an
00026 //               algorithm published as:
00027 //
00028 //               Narkhede A. and Manocha D., Fast polygon
00029 //               triangulation algorithm based on Seidel's Algorithm,
00030 //               UNC-CH, 1994.
00031 //
00032 //               http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
00033 //
00034 //               It works strictly on 2-d points.  You'll have to
00035 //               convert your polygon into a plane if you have 3-d
00036 //               points.
00037 ////////////////////////////////////////////////////////////////////
00038 class EXPCL_PANDA_MATHUTIL Triangulator {
00039 PUBLISHED:
00040   Triangulator();
00041 
00042   void clear();
00043   int add_vertex(const LPoint2d &point);
00044   INLINE int add_vertex(double x, double y);
00045 
00046   INLINE int get_num_vertices() const;
00047   INLINE const LPoint2d &get_vertex(int n) const;
00048   MAKE_SEQ(get_vertices, get_num_vertices, get_vertex);
00049 
00050   void clear_polygon();
00051   void add_polygon_vertex(int index);
00052   INLINE bool is_left_winding() const;
00053 
00054   void begin_hole();
00055   void add_hole_vertex(int index);
00056 
00057   void triangulate();
00058 
00059   int get_num_triangles() const;
00060   int get_triangle_v0(int n) const;
00061   int get_triangle_v1(int n) const;
00062   int get_triangle_v2(int n) const;
00063 
00064 private:
00065   typedef pvector<LPoint2d> Vertices;
00066   Vertices _vertices;
00067 
00068   vector_int _polygon;
00069 
00070   typedef pvector<vector_int> Holes;
00071   Holes _holes;
00072 
00073   class Triangle {
00074   public:
00075     INLINE Triangle(Triangulator *t, int v0, int v1, int v2);
00076     int _v0, _v1, _v2;
00077   };
00078 
00079   typedef pvector<Triangle> Result;
00080   Result _result;
00081 
00082   
00083   typedef struct {
00084     double x, y;
00085   } point_t, vector_t;
00086   
00087 
00088   struct segment_t {
00089     INLINE segment_t();
00090     INLINE segment_t(Triangulator *t, int v0_i, int v1_i, int prev, int next);
00091 
00092     point_t v0, v1;             /* two endpoints */
00093     int is_inserted;            /* inserted in trapezoidation yet ? */
00094     int root0, root1;           /* root nodes in Q */
00095     int next;                   /* Next logical segment */
00096     int prev;                   /* Previous segment */
00097     int v0_i; // index to user's vertex number
00098   };
00099 
00100   typedef pvector<segment_t> Segments;
00101   Segments seg;
00102   vector_int permute;
00103   int choose_idx;
00104 
00105   /* Trapezoid attributes */
00106 
00107   typedef struct {
00108     int lseg, rseg;             /* two adjoining segments */
00109     point_t hi, lo;             /* max/min y-values */
00110     int u0, u1;
00111     int d0, d1;
00112     int sink;                   /* pointer to corresponding in Q */
00113     int usave, uside;           /* I forgot what this means */
00114     int state;
00115   } trap_t;
00116   
00117   
00118   /* Node attributes for every node in the query structure */
00119   
00120   typedef struct {
00121     int nodetype;                       /* Y-node or S-node */
00122     int segnum;
00123     point_t yval;
00124     int trnum;
00125     int parent;                 /* doubly linked DAG */
00126     int left, right;            /* children */
00127   } node_t;
00128 
00129 
00130   typedef struct {
00131     int vnum;
00132     int next;                   /* Circularly linked list  */
00133     int prev;                   /* describing the monotone */
00134     int marked;                 /* polygon */
00135   } monchain_t;
00136   
00137   
00138   typedef struct {
00139     point_t pt;
00140     int vnext[4];                       /* next vertices for the 4 chains */
00141     int vpos[4];                        /* position of v in the 4 chains */
00142     int nextfree;
00143     int user_i;  // index to user's vertex number
00144   } vertexchain_t;
00145   
00146   
00147   typedef pvector<node_t> QueryStructure;
00148   QueryStructure qs;
00149   typedef pvector<trap_t> TrapezoidStructure;
00150   TrapezoidStructure tr;
00151   
00152   /* Table to hold all the monotone */
00153   /* polygons . Each monotone polygon */
00154   /* is a circularly linked list */
00155   pvector<monchain_t> mchain;
00156 
00157   /* chain init. information. This */
00158   /* is used to decide which */
00159   /* monotone polygon to split if */
00160   /* there are several other */
00161   /* polygons touching at the same */
00162   /* vertex  */
00163   pvector<vertexchain_t> vert;
00164 
00165   /* contains position of any vertex in */
00166   /* the monotone chain for the polygon */
00167   vector_int mon;
00168 
00169   vector_int visited;
00170 
00171   bool check_left_winding(const vector_int &range) const;
00172   void make_segment(const vector_int &range, bool want_left_winding);
00173 
00174   int choose_segment();
00175   static double math_log2(double v);
00176   static int math_logstar_n(int n);
00177   static int math_N(int n, int h);
00178 
00179   int newnode();
00180   int newtrap();
00181   int _max(point_t *yval, point_t *v0, point_t *v1);
00182   int _min(point_t *yval, point_t *v0, point_t *v1);
00183   int _greater_than(point_t *v0, point_t *v1);
00184   int _equal_to(point_t *v0, point_t *v1);
00185   int _greater_than_equal_to(point_t *v0, point_t *v1);
00186   int _less_than(point_t *v0, point_t *v1);
00187   int init_query_structure(int segnum);
00188   int is_left_of(int segnum, point_t *v);
00189   int inserted(int segnum, int whichpt);
00190   int locate_endpoint(point_t *v, point_t *vo, int r);
00191   int merge_trapezoids(int segnum, int tfirst, int tlast, int side);
00192   int add_segment(int segnum);
00193   int find_new_roots(int segnum);
00194   int construct_trapezoids(int nseg);
00195 
00196   int inside_polygon(trap_t *t);
00197   int newmon();
00198   int new_chain_element();
00199   double get_angle(point_t *vp0, point_t *vpnext, point_t *vp1);
00200   int get_vertex_positions(int v0, int v1, int *ip, int *iq);
00201   int make_new_monotone_poly(int mcur, int v0, int v1);
00202   int monotonate_trapezoids(int n);
00203   int traverse_polygon(int mcur, int trnum, int from, int dir);
00204   void triangulate_monotone_polygons(int nvert, int nmonpoly);
00205   void triangulate_single_polygon(int nvert, int posmax, int side);
00206 
00207   friend class Triangle;
00208   friend struct segment_t;
00209 };
00210 
00211 #include "triangulator.I"
00212 
00213 #endif
00214 
 All Classes Functions Variables Enumerations