G3D::ConvexPolygon Class Reference

#include <ConvexPolyhedron.h>

Public Member Functions
	ConvexPolygon ()
	ConvexPolygon (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2)
	ConvexPolygon (const Array< Vector3 > &__vertex)
virtual	~ConvexPolygon ()
const Vector3 &	vertex (int i) const
void	setVertex (int i, const Vector3 &v)
int	numVertices () const
void	setNumVertices (int n)
bool	isEmpty () const
void	cut (const Plane &plane, ConvexPolygon &above, ConvexPolygon &below, DirectedEdge &newEdge)
void	cut (const Plane &plane, ConvexPolygon &above, ConvexPolygon &below)
void	removeDuplicateVertices ()
float	getArea () const
Vector3	normal () const
ConvexPolygon	inverse () const

Private Attributes
Array< Vector3 >	_vertex

Friends
class	ConvexPolyhedron

Constructor & Destructor Documentation

G3D::ConvexPolygon::ConvexPolygon ( )

inline

{}

G3D::ConvexPolygon::ConvexPolygon	(	const Vector3 &	v0,
		const Vector3 &	v1,
		const Vector3 &	v2
	)

 {
 _vertex.append(v0, v1, v2);
}

G3D::ConvexPolygon::ConvexPolygon

(

const Array< Vector3 > &

__vertex

)

 : _vertex(__vertex) {
 // Intentionally empty
}

virtual G3D::ConvexPolygon::~ConvexPolygon ( )

inlinevirtual

{}

Member Function Documentation

void G3D::ConvexPolygon::cut	(	const Plane &	plane,
		ConvexPolygon &	above,
		ConvexPolygon &	below,
		DirectedEdge &	newEdge
	)

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

Parameters

above	The part of the polygon above (on the side the normal points to or in the plane) the plane
below	The part of the polygon below the plane.
newEdge	If a new edge was introduced, this is that edge (on the above portion; the below portion is the opposite winding.

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

 if (isEmpty()) {
 //debugPrintf("Empty\n");
 return;
 }

 int v = 0;
 int length = _vertex.length();


 Vector3 polyNormal = normal();
 Vector3 planeNormal= plane.normal();

 // See if the polygon is *in* the plane.
 if (planeNormal.fuzzyEq(polyNormal) || planeNormal.fuzzyEq(-polyNormal)) {
 // Polygon is parallel to the plane. It must be either above,
 // below, or in the plane.

 double a, b, c, d;
 Vector3 pt = _vertex[0];

 plane.getEquation(a,b,c,d);
 float r = (float)(a * pt.x + b * pt.y + c * pt.z + d);

 if (fuzzyGe(r, 0)) {
 // The polygon is entirely in the plane.
 //debugPrintf("Entirely above\n");
 above = *this;
 return;
 } else {
 //debugPrintf("Entirely below (1)\n");
 below = *this;
 return;
 }
 }


 // Number of edges crossing the plane. Used for 
 // debug assertions.
 int count = 0;

 // True when the last _vertex we looked at was above the plane
 bool lastAbove = plane.halfSpaceContains(_vertex[v]);

 if (lastAbove) {
 above._vertex.append(_vertex[v]);
 } else {
 below._vertex.append(_vertex[v]);
 }

 for (v = 1; v < length; ++v) {
 bool isAbove = plane.halfSpaceContains(_vertex[v]);
 
 if (lastAbove ^ isAbove) {
 // Switched sides.
 // Create an interpolated point that lies
 // in the plane, between the two points.
 Line line = Line::fromTwoPoints(_vertex[v - 1], _vertex[v]);
 Vector3 interp = line.intersection(plane);
 
 if (! interp.isFinite()) {

 // Since the polygon is not in the plane (we checked above), 
 // it must be the case that this edge (and only this edge)
 // is in the plane. This only happens when the polygon is
 // entirely below the plane except for one edge. This edge
 // forms a degenerate polygon, so just treat the whole polygon
 // as below the plane.
 below = *this;
 above._vertex.resize(0);
 //debugPrintf("Entirely below\n");
 return;
 } 

 above._vertex.append(interp);
 below._vertex.append(interp);
 if (lastAbove) {
 newEdge.stop = interp;
 } else {
 newEdge.start = interp;
 }
 ++count;
 }

 lastAbove = isAbove;
 if (lastAbove) {
 above._vertex.append(_vertex[v]);
 } else {
 below._vertex.append(_vertex[v]);
 }
 }

 // Loop back to the first point, seeing if an interpolated point is
 // needed.
 bool isAbove = plane.halfSpaceContains(_vertex[0]);
 if (lastAbove ^ isAbove) {
 Line line = Line::fromTwoPoints(_vertex[length - 1], _vertex[0]);
 Vector3 interp = line.intersection(plane);
 if (! interp.isFinite()) {
 // Since the polygon is not in the plane (we checked above), 
 // it must be the case that this edge (and only this edge)
 // is in the plane. This only happens when the polygon is
 // entirely below the plane except for one edge. This edge
 // forms a degenerate polygon, so just treat the whole polygon
 // as below the plane.
 below = *this;
 above._vertex.resize(0);
 //debugPrintf("Entirely below\n");
 return;
 } 

 above._vertex.append(interp);
 below._vertex.append(interp);
 debugAssertM(count < 2, "Convex polygons may only intersect planes at two edges.");
 if (lastAbove) {
 newEdge.stop = interp;
 } else {
 newEdge.start = interp;
 }
 ++count;
 }

 debugAssertM((count == 2) || (count == 0), "Convex polygons may only intersect planes at two edges.");
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

 {
 DirectedEdge edge;
 cut(plane, above, below, edge);
}

Here is the call graph for this function:

float G3D::ConvexPolygon::getArea

(

)

const

O(n) in the number of edges

 {

 if (_vertex.length() < 3) {
 return 0;
 }

 float sum = 0;

 int length = _vertex.length();
 // Split into triangle fan, compute individual area
 for (int v = 2; v < length; ++v) {
 int i0 = 0;
 int i1 = v - 1;
 int i2 = v;

 sum += (_vertex[i1] - _vertex[i0]).cross(_vertex[i2] - _vertex[i0]).magnitude() / 2; 
 }

 return sum;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ConvexPolygon G3D::ConvexPolygon::inverse

(

)

const

Returns the same polygon with inverse winding.

 {
 ConvexPolygon result;
 int length = _vertex.length();
 result._vertex.resize(length);
 
 for (int v = 0; v < length; ++v) {
 result._vertex[v] = _vertex[length - v - 1];
 }

 return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool G3D::ConvexPolygon::isEmpty

(

)

const

O(n) in the number of edges

 {
 return (_vertex.length() == 0) || (getArea() <= fuzzyEpsilon32);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Vector3 G3D::ConvexPolygon::normal ( ) const

inline

 {
 debugAssert(_vertex.length() >= 3);
 return (_vertex[1] - _vertex[0]).cross(_vertex[2] - _vertex[0]).direction();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

int G3D::ConvexPolygon::numVertices ( ) const

inline

Zero vertices indicates an empty polygon (zero area).

 {
 return _vertex.size();
 }

Here is the call graph for this function:

void G3D::ConvexPolygon::removeDuplicateVertices

(

)

When a cut plane grazes a vertex in the polygon, two near-identical vertices may be created. The closeness of these two points can cause a number of problems, such as ConvexPolygon::normal() returning an infinite vector. It should be noted, however, that not all applications are sensitive to near-identical vertices.

removeDuplicateVertices() detects and eliminates redundant vertices.

 {
 // Any valid polygon should have 3 or more vertices, but why take chances?
 if (_vertex.size() >= 2){

 // Remove duplicate vertices.
 for (int i=0;i<_vertex.size()-1;++i){
 if (_vertex[i].fuzzyEq(_vertex[i+1])){
 _vertex.remove(i+1);
 --i; // Don't move forward.
 }
 }
 
 // Check the last vertex against the first.
 if (_vertex[_vertex.size()-1].fuzzyEq(_vertex[0])){
 _vertex.pop();
 }
 }
}

Here is the call graph for this function:

void G3D::ConvexPolygon::setNumVertices ( int  n )

inline

 {
 _vertex.resize(n);
 }

Here is the call graph for this function:

void G3D::ConvexPolygon::setVertex ( int  i, const Vector3 &  v  )

inline

 {
 _vertex[i] = v;
 }

const Vector3& G3D::ConvexPolygon::vertex ( int  i ) const

inline

Counter clockwise winding order.

 {
 return _vertex[i];
 }

Friends And Related Function Documentation

friend class ConvexPolyhedron

friend

Member Data Documentation

Array<Vector3> G3D::ConvexPolygon::_vertex

private

---

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

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