Panda3D
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  */
22 EggMesherFanMaker::
23 EggMesherFanMaker(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  */
38 EggMesherFanMaker::
39 EggMesherFanMaker(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  */
51 void EggMesherFanMaker::
52 operator = (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  */
68 join(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  */
112 compute_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  */
148 build(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  */
259 unroll(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  */
328 void EggMesherFanMaker::
329 output(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.
Definition: eggGroupNode.h:46
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.
Definition: eggMesherEdge.h:29
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.
Definition: eggVertexPool.h:41
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...
EggVertex * add_vertex(EggVertex *vertex, int index=-1)
Adds the indicated vertex to the pool.
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.