Panda3D
|
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