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