Panda3D
Loading...
Searching...
No Matches
eggMesherFanMaker.cxx
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 eggMesherFanMaker.cxx
10 * @author drose
11 * @date 2005-03-22
12 */
13
14#include "eggMesherFanMaker.h"
15#include "eggMesher.h"
16#include "eggPolygon.h"
17#include "eggGroupNode.h"
18
19/**
20 *
21 */
22EggMesherFanMaker::
23EggMesherFanMaker(int vertex, EggMesherStrip *tri,
24 EggMesher *mesher) {
25 _vertex = vertex;
26 const EggMesherEdge *edge = tri->find_opposite_edge(vertex);
27 if (edge != nullptr) {
28 _edges.push_back(edge);
29 }
30 _strips.push_back(tri);
31 _planar = tri->_planar;
32 _mesher = mesher;
33}
34
35/**
36 *
37 */
38EggMesherFanMaker::
39EggMesherFanMaker(const EggMesherFanMaker &copy) :
40 _vertex(copy._vertex),
41 _edges(copy._edges),
42 _strips(copy._strips),
43 _planar(copy._planar),
44 _mesher(copy._mesher)
45{
46}
47
48/**
49 *
50 */
51void EggMesherFanMaker::
52operator = (const EggMesherFanMaker &copy) {
53 _vertex = copy._vertex;
54 _edges = copy._edges;
55 _strips = copy._strips;
56 _planar = copy._planar;
57 _mesher = copy._mesher;
58}
59
60/**
61 * Attempts to connect two fans end-to-end. They must both share the same
62 * common vertex and a common edge.
63 *
64 * The return value is true if the fans were successfully joined, or false if
65 * they could not be.
66 */
68join(EggMesherFanMaker &other) {
69 nassertr(_vertex == other._vertex, false);
70 nassertr(_mesher == other._mesher, false);
71
72 nassertr(!_edges.empty() && !other._edges.empty(), false);
73
74 const EggMesherEdge *my_back = _edges.back();
75 const EggMesherEdge *other_front = other._edges.front();
76 nassertr(my_back != nullptr &&
77 other_front != nullptr, false);
78
79 int my_back_b = my_back->_vi_b;
80 int other_front_a = other_front->_vi_a;
81
82 if (my_back_b == other_front_a) {
83 _planar = is_coplanar_with(other);
84 _edges.splice(_edges.end(), other._edges);
85 _strips.splice(_strips.end(), other._strips);
86 return true;
87 }
88
89 const EggMesherEdge *my_front = _edges.front();
90 const EggMesherEdge *other_back = other._edges.back();
91 nassertr(my_front != nullptr &&
92 other_back != nullptr, false);
93
94 int my_front_a = my_front->_vi_a;
95 int other_back_b = other_back->_vi_b;
96
97 if (my_front_a == other_back_b) {
98 _planar = is_coplanar_with(other);
99 _edges.splice(_edges.begin(), other._edges);
100 _strips.splice(_strips.begin(), other._strips);
101 return true;
102 }
103
104 return false;
105}
106
107/**
108 * Returns the overall angle subtended by the fan, from the leading edge to
109 * the trailing edge, in degrees.
110 */
112compute_angle() const {
113 // We sum up the angles of each triangle. This is more correct than taking
114 // the net angle from the first edge to the last (since we may not be in a
115 // plane).
116 nassertr(is_valid(), 0.0);
117
118 EggVertexPool *vertex_pool = _mesher->_vertex_pool;
119
120 double angle = 0.0;
121 LPoint3d v0 = vertex_pool->get_vertex(_vertex)->get_pos3();
122
123 Edges::const_iterator ei;
124 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
125 LVector3d v1 = vertex_pool->get_vertex((*ei)->_vi_a)->get_pos3() - v0;
126 LVector3d v2 = vertex_pool->get_vertex((*ei)->_vi_b)->get_pos3() - v0;
127
128 v1 = normalize(v1);
129 v2 = normalize(v2);
130 angle += acos(dot(v1, v2));
131 }
132
133 return rad_2_deg(angle);
134}
135
136/**
137 * Begins the fanning process. Searches for triangles and connects them into
138 * a fan.
139 *
140 * In certain cases, if egg_unroll_fans is enabled, the resulting fan may be
141 * retesselated into a series of zig-zag triangles, which are stored in
142 * unrolled_tris. Otherwise, an EggMesherStrip (representing the fan) is
143 * created and added to the mesher.
144 *
145 * The return value is (loosely) the number of primitives created.
146 */
148build(EggGroupNode *unrolled_tris) {
149 nassertr(_edges.size() == _strips.size(), 0);
150
151 int num_tris = _edges.size();
152 double net_angle = compute_angle();
153 double avg_angle = net_angle / (double)num_tris;
154
155 if (avg_angle > egg_max_tfan_angle) {
156 // The triangles are too loose to justify making a fan; it'll probably
157 // make a better quadsheet.
158 return 0;
159 }
160
161 if (egg_min_tfan_tris == 0 || num_tris < egg_min_tfan_tris) {
162 // Oops, not enough triangles to justify a fan.
163 if (!egg_unroll_fans) {
164 return 0;
165 }
166
167 // However, we could (maybe) make it a few tristrips!
168
169 // Each section of the fan which is made up of coplanar tris, with
170 // identical properties, may be retesselated into a tristrip. What a
171 // sneaky trick! To do this, we must first identify each such qualifying
172 // section.
173
174 // We define a seam as the edge between any two tris which are noncoplanar
175 // or have different properties. Then we can send each piece between the
176 // seams to unroll().
177
178 Strips::iterator si, last_si;
179 Edges::iterator ei, last_ei;
180
181 // First, rotate the fan so it begins at a seam. We do this so we won't
182 // be left out with part of one piece at the beginning and also at the
183 // end.
184 si = _strips.begin();
185 last_si = si;
186 ei = _edges.begin();
187 last_ei = ei;
188 int found_seam = false;
189
190 for (++si, ++ei; si != _strips.end() && !found_seam; ++si, ++ei) {
191 nassertr(ei != _edges.end(), 0);
192 if ( ((*si)->_prims.front()->compare_to(*(*last_si)->_prims.front()) != 0) ||
193 !(*si)->is_coplanar_with(*(*last_si), egg_coplanar_threshold)) {
194 // Here's a seam. Break the fan here.
195 found_seam = true;
196 _edges.splice(_edges.begin(), _edges, ei, _edges.end());
197 _strips.splice(_strips.begin(), _strips, si, _strips.end());
198 }
199 }
200
201 // Now break the fan up along its seams and unroll each piece separately.
202 si = _strips.begin();
203 last_si = si;
204 ei = _edges.begin();
205 last_ei = ei;
206
207 int count = 0;
208 for (++si, ++ei; si != _strips.end(); ++si, ++ei) {
209 nassertr(ei != _edges.end(), 0);
210 if ( ((*si)->_prims.front()->compare_to(*(*last_si)->_prims.front()) != 0) ||
211 !(*si)->is_coplanar_with(*(*last_si), egg_coplanar_threshold)) {
212 // Here's the end of a run of matching pieces.
213 count += unroll(last_si, si, last_ei, ei, unrolled_tris);
214 last_si = si;
215 last_ei = ei;
216 }
217 }
218 count += unroll(last_si, si, last_ei, ei, unrolled_tris);
219
220 return count;
221
222 } else {
223 EggMesherStrip new_fan(EggMesherStrip::PT_trifan, EggMesherStrip::MO_fanpoly);
224 new_fan._verts.push_back(_vertex);
225
226 new_fan._verts.push_back(_edges.front()->_vi_a);
227 Edges::iterator ei;
228 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
229 new_fan._verts.push_back((*ei)->_vi_b);
230 }
231
232 Strips::iterator si;
233 for (si = _strips.begin(); si != _strips.end(); ++si) {
234 new_fan._prims.splice(new_fan._prims.end(), (*si)->_prims);
235 (*si)->remove_all_edges();
236 (*si)->_verts.clear();
237 (*si)->_status = EggMesherStrip::MS_dead;
238 }
239
240 // If we'd built our list of edges and strips right, this sum should come
241 // out so that there are two more vertices than triangles in the new fan.
242 nassertr(new_fan._verts.size() == new_fan._prims.size() + 2, 0);
243
244 // Now we've built a fan, and it won't be able to mate with anything else,
245 // so add it to the done list.
246 _mesher->_done.push_back(new_fan);
247 }
248
249 return 1;
250}
251
252/**
253 * Unrolls a planar subset of the current working fan, defined by the given
254 * iterators, into a series of triangles that zig-zag back and forth for
255 * better tristripping properties. The new triangles are added to
256 * unrolled_tris; the return value is 1 if successful, or 0 otherwise.
257 */
259unroll(Strips::iterator strip_begin, Strips::iterator strip_end,
260 Edges::iterator edge_begin, Edges::iterator edge_end,
261 EggGroupNode *unrolled_tris) {
262 Edges::iterator ei;
263 Strips::iterator si;
264
265 int num_tris = 0;
266 for (ei = edge_begin; ei != edge_end; ++ei) {
267 num_tris++;
268 }
269
270 if (num_tris < 3) {
271 // Don't even bother.
272 return 0;
273 }
274
275 PT(EggPolygon) poly = new EggPolygon;
276
277 // Now we build an n-sided polygon the same shape as the fan. We'll
278 // decompose it into tris in a second.
279 poly->copy_attributes(*(*strip_begin)->_prims.front());
280 EggVertexPool *vertex_pool = _mesher->_vertex_pool;
281
282 ei = edge_end;
283 --ei;
284 if ((*ei)->_vi_b != (*edge_begin)->_vi_a) {
285 // If the fan is less than a full circle, we need to keep the hub vertex
286 // and initial vertex in the poly. Otherwise, we'll discard them.
287 poly->add_vertex(vertex_pool->get_vertex(_vertex));
288 poly->add_vertex(vertex_pool->get_vertex((*edge_begin)->_vi_a));
289 }
290
291 for (ei = edge_begin; ei != edge_end; ++ei) {
292 poly->add_vertex(vertex_pool->get_vertex((*ei)->_vi_b));
293 }
294
295 bool result = true;
296
297 if (egg_show_quads) {
298 // If we're showing quads, also show retesselated triangles.
299
300 // We can't add it directly to the mesher, that's unsafe; instead, we'll
301 // just add it to the end of the unrolled_tris list. This does mean we
302 // won't be able to color it a fancy color, but too bad.
303 // _mesher->add_polygon(poly, EggMesherStrip::MO_fanpoly);
304 unrolled_tris->add_child(poly);
305
306 } else {
307 // Now decompose the new polygon into triangles.
308 result = poly->triangulate_into(unrolled_tris, true);
309 }
310
311 if (result) {
312 // Now that we've created a new poly, kill off all the old ones.
313 for (si = strip_begin; si != strip_end; ++si) {
314 (*si)->remove_all_edges();
315 (*si)->_verts.clear();
316 (*si)->_prims.clear();
317 (*si)->_status = EggMesherStrip::MS_dead;
318 }
319 return 1;
320 } else {
321 return 0;
322 }
323}
324
325/**
326 *
327 */
328void EggMesherFanMaker::
329output(std::ostream &out) const {
330 out << _vertex << ":[";
331 if (!_edges.empty()) {
332 Edges::const_iterator ei;
333 for (ei = _edges.begin(); ei != _edges.end(); ++ei) {
334 out << " " << (*ei)->_vi_a;
335 }
336 out << " " << _edges.back()->_vi_b;
337 }
338 out << " ]";
339
340 if (_planar) {
341 out << " (planar)";
342 }
343}
A base class for nodes in the hierarchy that are not leaf nodes.
EggNode * add_child(EggNode *node)
Adds the indicated child to the group and returns it.
Represents one edge of a triangle, as used by the EggMesher to discover connected triangles.
This class is used by EggMesher::find_fans() to attempt to make an EggTriangleFan out of the polygons...
double compute_angle() const
Returns the overall angle subtended by the fan, from the leading edge to the trailing edge,...
bool join(EggMesherFanMaker &other)
Attempts to connect two fans end-to-end.
int unroll(Strips::iterator strip_begin, Strips::iterator strip_end, Edges::iterator edge_begin, Edges::iterator edge_end, EggGroupNode *unrolled_tris)
Unrolls a planar subset of the current working fan, defined by the given iterators,...
int build(EggGroupNode *unrolled_tris)
Begins the fanning process.
bool is_coplanar_with(const EggMesherFanMaker &other) const
Returns true if the strip and the other strip are coplanar.
bool is_valid() const
Returns true if the fan maker has enough edges to define at least one fan, false otherwise.
Represents a triangle strip or quad strip in progress, as assembled by the mesher.
const EggMesherEdge * find_opposite_edge(int vi) const
Returns the first edge found that does not contain the given vertex.
Collects together unrelated EggPrimitives, determines their edge connectivity, and generates a set of...
Definition eggMesher.h:33
A single polygon.
Definition eggPolygon.h:24
void copy_attributes(const EggAttributes &other)
Copies the rendering attributes from the indicated primitive.
A collection of vertices.
EggVertex * get_vertex(int index) const
Returns the vertex in the pool with the indicated index number, or NULL if no vertices have that inde...
LVertexd get_pos3() const
Valid if get_num_dimensions() returns 3 or 4.
Definition eggVertex.I:131
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.