Panda3D
Loading...
Searching...
No Matches
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 */
32class EXPCL_PANDA_MATHUTIL Triangulator {
33PUBLISHED:
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
59protected:
60 void cleanup_polygon_indices(vector_int &polygon);
61
63 Vertices _vertices;
64
65 vector_int _polygon;
66
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.
This is our own Panda specialization on the default STL vector.
Definition pvector.h:42
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.