Panda3D
triangulator.h
1 // Filename: triangulator.h
2 // Created by: drose (17Jan07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #ifndef TRIANGULATOR_H
16 #define TRIANGULATOR_H
17 
18 #include "pandabase.h"
19 #include "luse.h"
20 #include "vector_int.h"
21 
22 ////////////////////////////////////////////////////////////////////
23 // Class : Triangulator
24 // Description : This class can triangulate a convex or concave
25 // polygon, even one with holes. It is adapted from an
26 // algorithm published as:
27 //
28 // Narkhede A. and Manocha D., Fast polygon
29 // triangulation algorithm based on Seidel's Algorithm,
30 // UNC-CH, 1994.
31 //
32 // http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
33 //
34 // It works strictly on 2-d points. See Triangulator3
35 // for 3-d points.
36 ////////////////////////////////////////////////////////////////////
37 class EXPCL_PANDA_MATHUTIL Triangulator {
38 PUBLISHED:
39  Triangulator();
40 
41  void clear();
42  int add_vertex(const LPoint2d &point);
43  INLINE int add_vertex(double x, double y);
44 
45  INLINE int get_num_vertices() const;
46  INLINE const LPoint2d &get_vertex(int n) const;
47  MAKE_SEQ(get_vertices, get_num_vertices, get_vertex);
48 
49  void clear_polygon();
50  void add_polygon_vertex(int index);
51  INLINE bool is_left_winding() const;
52 
53  void begin_hole();
54  void add_hole_vertex(int index);
55 
56  void triangulate();
57 
58  int get_num_triangles() const;
59  int get_triangle_v0(int n) const;
60  int get_triangle_v1(int n) const;
61  int get_triangle_v2(int n) const;
62 
63 protected:
64  void cleanup_polygon_indices(vector_int &polygon);
65 
67  Vertices _vertices;
68 
69  vector_int _polygon;
70 
71  typedef pvector<vector_int> Holes;
72  Holes _holes;
73 
74  class Triangle {
75  public:
76  INLINE Triangle(Triangulator *t, int v0, int v1, int v2);
77  int _v0, _v1, _v2;
78  };
79 
80  typedef pvector<Triangle> Result;
81  Result _result;
82 
83 
84  typedef struct {
85  double x, y;
86  } point_t, vector_t;
87 
88 
89  struct segment_t {
90  INLINE segment_t();
91  INLINE segment_t(Triangulator *t, int v0_i, int v1_i, int prev, int next);
92 
93  point_t v0, v1; /* two endpoints */
94  int is_inserted; /* inserted in trapezoidation yet ? */
95  int root0, root1; /* root nodes in Q */
96  int next; /* Next logical segment */
97  int prev; /* Previous segment */
98  int v0_i; // index to user's vertex number
99  };
100 
102  Segments seg;
103  vector_int permute;
104  int choose_idx;
105 
106  /* Trapezoid attributes */
107 
108  typedef struct {
109  int lseg, rseg; /* two adjoining segments */
110  point_t hi, lo; /* max/min y-values */
111  int u0, u1;
112  int d0, d1;
113  int sink; /* pointer to corresponding in Q */
114  int usave, uside; /* I forgot what this means */
115  int state;
116  } trap_t;
117 
118 
119  /* Node attributes for every node in the query structure */
120 
121  typedef struct {
122  int nodetype; /* Y-node or S-node */
123  int segnum;
124  point_t yval;
125  int trnum;
126  int parent; /* doubly linked DAG */
127  int left, right; /* children */
128  } node_t;
129 
130 
131  typedef struct {
132  int vnum;
133  int next; /* Circularly linked list */
134  int prev; /* describing the monotone */
135  int marked; /* polygon */
136  } monchain_t;
137 
138 
139  typedef struct {
140  point_t pt;
141  int vnext[4]; /* next vertices for the 4 chains */
142  int vpos[4]; /* position of v in the 4 chains */
143  int nextfree;
144  int user_i; // index to user's vertex number
145  } vertexchain_t;
146 
147 
149  QueryStructure qs;
151  TrapezoidStructure tr;
152 
153  /* Table to hold all the monotone */
154  /* polygons . Each monotone polygon */
155  /* is a circularly linked list */
156  pvector<monchain_t> mchain;
157 
158  /* chain init. information. This */
159  /* is used to decide which */
160  /* monotone polygon to split if */
161  /* there are several other */
162  /* polygons touching at the same */
163  /* vertex */
165 
166  /* contains position of any vertex in */
167  /* the monotone chain for the polygon */
168  vector_int mon;
169 
170  vector_int visited;
171 
172  bool check_left_winding(const vector_int &range) const;
173  void make_segment(const vector_int &range, bool want_left_winding);
174 
175  int choose_segment();
176  static double math_log2(double v);
177  static int math_logstar_n(int n);
178  static int math_N(int n, int h);
179 
180  int newnode();
181  int newtrap();
182  int _max(point_t *yval, point_t *v0, point_t *v1);
183  int _min(point_t *yval, point_t *v0, point_t *v1);
184  int _greater_than(point_t *v0, point_t *v1);
185  int _equal_to(point_t *v0, point_t *v1);
186  int _greater_than_equal_to(point_t *v0, point_t *v1);
187  int _less_than(point_t *v0, point_t *v1);
188  int init_query_structure(int segnum);
189  int is_left_of(int segnum, point_t *v);
190  int inserted(int segnum, int whichpt);
191  int locate_endpoint(point_t *v, point_t *vo, int r);
192  int merge_trapezoids(int segnum, int tfirst, int tlast, int side);
193  int add_segment(int segnum);
194  int find_new_roots(int segnum);
195  int construct_trapezoids(int nseg);
196 
197  int inside_polygon(trap_t *t);
198  int newmon();
199  int new_chain_element();
200  double get_angle(point_t *vp0, point_t *vpnext, point_t *vp1);
201  int get_vertex_positions(int v0, int v1, int *ip, int *iq);
202  int make_new_monotone_poly(int mcur, int v0, int v1);
203  int monotonate_trapezoids(int n);
204  int traverse_polygon(int mcur, int trnum, int from, int dir);
205  void triangulate_monotone_polygons(int nvert, int nmonpoly);
206  void triangulate_single_polygon(int nvert, int posmax, int side);
207 
208  friend class Triangle;
209  friend struct segment_t;
210 };
211 
212 #include "triangulator.I"
213 
214 #endif
215 
This is a two-component point in space.
Definition: lpoint2.h:424
This class can triangulate a convex or concave polygon, even one with holes.
Definition: triangulator.h:37