TrinityCore
G3D::ConvexPolyhedron Class Reference

`#include <ConvexPolyhedron.h>`

## Public Member Functions

ConvexPolyhedron ()

ConvexPolyhedron (const Array< ConvexPolygon > &_face)

bool isEmpty () const

float getVolume () const

void cut (const Plane &plane, ConvexPolyhedron &above, ConvexPolyhedron &below)

## Public Attributes

Array< ConvexPolygonface

## Constructor & Destructor Documentation

 G3D::ConvexPolyhedron::ConvexPolyhedron ( )
inline
120 {}
 G3D::ConvexPolyhedron::ConvexPolyhedron ( const Array< ConvexPolygon > & _face )
223  : face(_face) {
224  // Intentionally empty
225 }
Array< ConvexPolygon > face
Definition: ConvexPolyhedron.h:118

## Member Function Documentation

 void G3D::ConvexPolyhedron::cut ( const Plane & plane, ConvexPolyhedron & above, ConvexPolyhedron & below )

Cuts the polyhedron at the plane. If the polyhedron is entirely above or below the plane, one of the returned polyhedra will be empty.

Parameters
 above The part of the polyhedron above (on the side the normal points to or in the plane) the plane below The part of the polyhedron below the plane.
258  {
259  above.face.resize(0);
260  below.face.resize(0);
261
262  Array<DirectedEdge> edge;
263
264  int f;
265
266  // See if the plane cuts this polyhedron at all. Detect when
267  // the polyhedron is entirely to one side or the other.
268  //{
269  int numAbove = 0, numIn = 0, numBelow = 0;
270  bool ruledOut = false;
271  double d;
272  Vector3 abc;
273  plane.getEquation(abc, d);
274
275  // This number has to be fairly large to prevent precision problems down
277  const float eps = 0.005f;
278  for (f = face.length() - 1; (f >= 0) && (!ruledOut); f--) {
279  const ConvexPolygon& poly = face[f];
280  for (int v = poly._vertex.length() - 1; (v >= 0) && (!ruledOut); v--) {
281  double r = abc.dot(poly._vertex[v]) + d;
282  if (r > eps) {
283  ++numAbove;
284  } else if (r < -eps) {
285  ++numBelow;
286  } else {
287  ++numIn;
288  }
289
290  ruledOut = (numAbove != 0) && (numBelow !=0);
291  }
292  }
293
294  if (numBelow == 0) {
295  above = *this;
296  return;
297  } else if (numAbove == 0) {
298  below = *this;
299  return;
300  }
301  //}
302
303  // Clip each polygon, collecting split edges.
304  for (f = face.length() - 1; f >= 0; f--) {
305  ConvexPolygon a, b;
306  DirectedEdge e;
307  face[f].cut(plane, a, b, e);
308
309  bool aEmpty = a.isEmpty();
310  bool bEmpty = b.isEmpty();
311
312  //debugPrintf("\n");
313  if (! aEmpty) {
314  //debugPrintf(" Above %f\n", a.getArea());
315  above.face.append(a);
316  }
317
318  if (! bEmpty) {
319  //debugPrintf(" Below %f\n", b.getArea());
320  below.face.append(b);
321  }
322
323  if (! aEmpty && ! bEmpty) {
324  //debugPrintf(" == Split\n");
325  edge.append(e);
326  } else {
327  // Might be the case that the polygon is entirely on
328  // one side of the plane yet there is an edge we need
329  // because it touches the plane.
330  //
331  // Extract the non-empty _vertex list and examine it.
332  // If we find exactly one edge in the plane, add that edge.
333  const Array<Vector3>& _vertex = (aEmpty ? b._vertex : a._vertex);
334  int L = _vertex.length();
335  int count = 0;
336  for (int v = 0; v < L; ++v) {
337  if (plane.fuzzyContains(_vertex[v]) && plane.fuzzyContains(_vertex[(v + 1) % L])) {
338  e.start = _vertex[v];
339  e.stop = _vertex[(v + 1) % L];
340  ++count;
341  }
342  }
343
344  if (count == 1) {
345  edge.append(e);
346  }
347  }
348  }
349
350  if (above.face.length() == 1) {
351  // Only one face above means that this entire
352  // polyhedron is below the plane. Move that face over.
353  below.face.append(above.face[0]);
354  above.face.resize(0);
355  } else if (below.face.length() == 1) {
356  // This shouldn't happen, but it arises in practice
357  // from numerical imprecision.
358  above.face.append(below.face[0]);
359  below.face.resize(0);
360  }
361
362  if ((above.face.length() > 0) && (below.face.length() > 0)) {
363  // The polyhedron was actually cut; create a cap polygon
364  ConvexPolygon cap;
365
366  // Collect the final polgyon by sorting the edges
367  int numVertices = edge.length();
368 /*debugPrintf("\n");
369 for (int xx=0; xx < numVertices; ++xx) {
370  std::string s1 = edge[xx].start.toString();
371  std::string s2 = edge[xx].stop.toString();
372  debugPrintf("%s -> %s\n", s1.c_str(), s2.c_str());
373 }
374 */
375
376  // Need at least three points to make a polygon
377  debugAssert(numVertices >= 3);
378
379  Vector3 last_vertex = edge.last().stop;
380  cap._vertex.append(last_vertex);
381
382  // Search for the next _vertex. Because of accumulating
383  // numerical error, we have to find the closest match, not
384  // just the one we expect.
385  for (int v = numVertices - 1; v >= 0; v--) {
386  // matching edge index
387  int index = 0;
388  int num = edge.length();
389  double distance = (edge[index].start - last_vertex).squaredMagnitude();
390  for (int e = 1; e < num; ++e) {
391  double d = (edge[e].start - last_vertex).squaredMagnitude();
392
393  if (d < distance) {
394  // This is the new closest one
395  index = e;
396  distance = d;
397  }
398  }
399
400  // Don't tolerate ridiculous error.
401  debugAssertM(distance < 0.02, "Edge missing while closing polygon.");
402
403  last_vertex = edge[index].stop;
404  cap._vertex.append(last_vertex);
405  }
406
407  //debugPrintf("\n");
408  //debugPrintf("Cap (both) %f\n", cap.getArea());
409  above.face.append(cap);
410  below.face.append(cap.inverse());
411  }
412
413  // Make sure we put enough faces on each polyhedra
414  debugAssert((above.face.length() == 0) || (above.face.length() >= 4));
415  debugAssert((below.face.length() == 0) || (below.face.length() >= 4));
416 }
Array< ConvexPolygon > face
Definition: ConvexPolyhedron.h:118
#define debugAssertM(exp, message)
Definition: debugAssert.h:161
double distance(double x, double y)
Definition: g3dmath.h:731
#define debugAssert(exp)
Definition: debugAssert.h:160
double eps(double a, double b)
Definition: g3dmath.h:824

Here is the call graph for this function:

 float G3D::ConvexPolyhedron::getVolume ( ) const

O(n) in the number of edges

228  {
229
230  if (face.length() < 4) {
231  return 0;
232  }
233
234  // The volume of any pyramid is 1/3 * h * base area.
235  // Discussion at: http://nrich.maths.org/mathsf/journalf/oct01/art1/
236
237  float sum = 0;
238
239  // Choose the first _vertex of the first face as the origin.
240  // This lets us skip one face, too, and avoids negative heights.
241  Vector3 v0 = face[0]._vertex[0];
242  for (int f = 1; f < face.length(); ++f) {
243  const ConvexPolygon& poly = face[f];
244
245  float height = (poly._vertex[0] - v0).dot(poly.normal());
246  float base = poly.getArea();
247
248  sum += height * base;
249  }
250
251  return sum / 3;
252 }
Array< ConvexPolygon > face
Definition: ConvexPolyhedron.h:118
float dot(float a, float b)
Definition: g3dmath.h:445

Here is the call graph for this function:

Here is the caller graph for this function:

 bool G3D::ConvexPolyhedron::isEmpty ( ) const

O(n) in the number of edges

254  {
255  return (face.length() == 0) || (getVolume() <= fuzzyEpsilon32);
256 }
Array< ConvexPolygon > face
Definition: ConvexPolyhedron.h:118
#define fuzzyEpsilon32
Definition: g3dmath.h:132
float getVolume() const
Definition: ConvexPolyhedron.cpp:228

Here is the call graph for this function:

## Member Data Documentation

 Array G3D::ConvexPolyhedron::face

Zero faces indicates an empty polyhedron

The documentation for this class was generated from the following files: