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