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< ConvexPolygon >	face

Constructor & Destructor Documentation

G3D::ConvexPolyhedron::ConvexPolyhedron ( )

inline

{}

G3D::ConvexPolyhedron::ConvexPolyhedron

(

const Array< ConvexPolygon > &

_face

)

 : face(_face) {
 // Intentionally empty
}

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.

 {
 above.face.resize(0);
 below.face.resize(0);

 Array<DirectedEdge> edge;

 int f;
 
 // See if the plane cuts this polyhedron at all. Detect when
 // the polyhedron is entirely to one side or the other.
 //{
 int numAbove = 0, numIn = 0, numBelow = 0;
 bool ruledOut = false;
 double d;
 Vector3 abc;
 plane.getEquation(abc, d);

 // This number has to be fairly large to prevent precision problems down
 // the road.
 const float eps = 0.005f;
 for (f = face.length() - 1; (f >= 0) && (!ruledOut); f--) {
 const ConvexPolygon& poly = face[f];
 for (int v = poly._vertex.length() - 1; (v >= 0) && (!ruledOut); v--) { 
 double r = abc.dot(poly._vertex[v]) + d;
 if (r > eps) {
 ++numAbove;
 } else if (r < -eps) {
 ++numBelow;
 } else {
 ++numIn;
 }

 ruledOut = (numAbove != 0) && (numBelow !=0);
 }
 }

 if (numBelow == 0) {
 above = *this;
 return;
 } else if (numAbove == 0) {
 below = *this;
 return;
 }
 //}

 // Clip each polygon, collecting split edges.
 for (f = face.length() - 1; f >= 0; f--) {
 ConvexPolygon a, b;
 DirectedEdge e;
 face[f].cut(plane, a, b, e);

 bool aEmpty = a.isEmpty();
 bool bEmpty = b.isEmpty();

 //debugPrintf("\n");
 if (! aEmpty) {
 //debugPrintf(" Above %f\n", a.getArea());
 above.face.append(a);
 }

 if (! bEmpty) {
 //debugPrintf(" Below %f\n", b.getArea());
 below.face.append(b);
 }

 if (! aEmpty && ! bEmpty) {
 //debugPrintf(" == Split\n");
 edge.append(e);
 } else {
 // Might be the case that the polygon is entirely on 
 // one side of the plane yet there is an edge we need
 // because it touches the plane.
 // 
 // Extract the non-empty _vertex list and examine it.
 // If we find exactly one edge in the plane, add that edge.
 const Array<Vector3>& _vertex = (aEmpty ? b._vertex : a._vertex);
 int L = _vertex.length();
 int count = 0;
 for (int v = 0; v < L; ++v) {
 if (plane.fuzzyContains(_vertex[v]) && plane.fuzzyContains(_vertex[(v + 1) % L])) {
 e.start = _vertex[v];
 e.stop = _vertex[(v + 1) % L];
 ++count;
 }
 }

 if (count == 1) {
 edge.append(e);
 }
 }
 }

 if (above.face.length() == 1) {
 // Only one face above means that this entire 
 // polyhedron is below the plane. Move that face over.
 below.face.append(above.face[0]);
 above.face.resize(0);
 } else if (below.face.length() == 1) {
 // This shouldn't happen, but it arises in practice
 // from numerical imprecision.
 above.face.append(below.face[0]);
 below.face.resize(0);
 }

 if ((above.face.length() > 0) && (below.face.length() > 0)) {
 // The polyhedron was actually cut; create a cap polygon
 ConvexPolygon cap;

 // Collect the final polgyon by sorting the edges
 int numVertices = edge.length();
/*debugPrintf("\n");
for (int xx=0; xx < numVertices; ++xx) {
 std::string s1 = edge[xx].start.toString();
 std::string s2 = edge[xx].stop.toString();
 debugPrintf("%s -> %s\n", s1.c_str(), s2.c_str());
}
*/

 // Need at least three points to make a polygon
 debugAssert(numVertices >= 3);

 Vector3 last_vertex = edge.last().stop;
 cap._vertex.append(last_vertex);

 // Search for the next _vertex. Because of accumulating
 // numerical error, we have to find the closest match, not 
 // just the one we expect.
 for (int v = numVertices - 1; v >= 0; v--) {
 // matching edge index
 int index = 0;
 int num = edge.length();
 double distance = (edge[index].start - last_vertex).squaredMagnitude();
 for (int e = 1; e < num; ++e) {
 double d = (edge[e].start - last_vertex).squaredMagnitude();

 if (d < distance) {
 // This is the new closest one
 index = e;
 distance = d;
 }
 }

 // Don't tolerate ridiculous error.
 debugAssertM(distance < 0.02, "Edge missing while closing polygon.");

 last_vertex = edge[index].stop;
 cap._vertex.append(last_vertex);
 }
 
 //debugPrintf("\n");
 //debugPrintf("Cap (both) %f\n", cap.getArea());
 above.face.append(cap);
 below.face.append(cap.inverse());
 }

 // Make sure we put enough faces on each polyhedra
 debugAssert((above.face.length() == 0) || (above.face.length() >= 4)); 
 debugAssert((below.face.length() == 0) || (below.face.length() >= 4));
}

Here is the call graph for this function:

float G3D::ConvexPolyhedron::getVolume

(

)

const

O(n) in the number of edges

 {

 if (face.length() < 4) {
 return 0;
 }

 // The volume of any pyramid is 1/3 * h * base area.
 // Discussion at: http://nrich.maths.org/mathsf/journalf/oct01/art1/

 float sum = 0;

 // Choose the first _vertex of the first face as the origin.
 // This lets us skip one face, too, and avoids negative heights.
 Vector3 v0 = face[0]._vertex[0];
 for (int f = 1; f < face.length(); ++f) { 
 const ConvexPolygon& poly = face[f];
 
 float height = (poly._vertex[0] - v0).dot(poly.normal());
 float base = poly.getArea();

 sum += height * base;
 }

 return sum / 3;
}

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

 {
 return (face.length() == 0) || (getVolume() <= fuzzyEpsilon32);
}

Here is the call graph for this function:

Member Data Documentation

Array<ConvexPolygon> G3D::ConvexPolyhedron::face

Zero faces indicates an empty polyhedron

---

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

• dep/g3dlite/include/G3D/ConvexPolyhedron.h
• dep/g3dlite/source/ConvexPolyhedron.cpp