Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polygon3.h
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polygon3.h	(revision 2912)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polygon3.h	(revision 2912)
@@ -0,0 +1,108 @@
+#ifndef _Polygon3_h__
+#define _Polygon3_h__
+
+
+#include "common.h"
+#include "Vector3.h"
+#include <iomanip>
+#include <iostream>
+
+
+namespace CHCDemoEngine 
+{
+
+	
+class Polygon3;
+class Plane3;
+class AxisAlignedBox3;
+struct Triangle3;
+
+
+
+typedef std::vector<Vector3> VertexArray;
+
+
+/** Class representing a planar convex polygon in 3d.
+*/
+class Polygon3
+{
+public:
+
+	enum {BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT};
+
+	/** Default constructor creating an empty polygon.
+	*/
+	Polygon3();
+	/** Constructor creating a polygon from the vertices.
+	*/
+	Polygon3(const VertexArray &vertices);
+
+	~Polygon3();
+	/** Returns supporting plane of this polygon.
+	*/
+	Plane3 GetSupportingPlane() const;
+	/** Splits polygon.
+		@param partition the split plane
+		@param front returns the front polygon
+		@param back returns the back polygon
+		@param epsilon epsilon where two points are considered equal
+	*/
+	void Split(const Plane3 &partition, Polygon3 &front, Polygon3 &back, float eps);
+
+	/** Returns the area of this polygon.
+	*/
+	float GetArea() const;
+	
+	/** Classify polygon with respect to the plane.
+	    @param epsilon tolerance value
+		@returns one of BACK_SIDE, FRONT_SIDE, SPLIT, COINCIDENT
+
+	*/
+	int ClassifyPlane(const Plane3 &plane, const float eps) const;
+	/** Side of the polygon with respect to the plane.
+		@returns 1 if on front side, -1 if on back side, 0 else.
+	*/
+	int Side(const Plane3 &plane, float eps) const;
+	/** Computes the center of mass of the polygon
+	 */
+	Vector3 Center() const;
+	/** Checks if the polygon is valid, i.e., not degenerated.
+		@returns true if polygon is valid.
+	*/
+	bool Valid(const float epsilon) const; 
+	/** Returns the surface normal.
+	*/
+	Vector3 GetNormal() const;
+	/** Returns new polygon with reverse orientation.
+	*/
+	Polygon3 *CreateReversePolygon() const;
+
+	AxisAlignedBox3 GetBoundingBox() const;
+
+	
+	//////////////////////////////////////////
+	
+	/// vertices are connected in counterclockwise order.
+	VertexArray mVertices;
+
+};
+
+
+// Overload << operator for C++-style output
+inline std::ostream&
+operator<< (std::ostream &s, const Polygon3 &A)
+{
+	VertexArray::const_iterator it;
+
+	//s << setprecision(6) << "Polygon:\n";
+	for (it = A.mVertices.begin(); it != A.mVertices.end(); ++ it)
+	{
+		s << *it << " ";
+	}
+
+	return s;
+}
+
+}
+
+#endif
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polyhedron.h
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polyhedron.h	(revision 2912)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polyhedron.h	(revision 2912)
@@ -0,0 +1,107 @@
+#ifndef _POLYHEDRON_H__
+#define _POLYHEDRON_H__
+
+
+#include "common.h"
+#include "AxisAlignedBox3.h"
+#include "Polygon3.h"
+
+#include <iostream>
+
+
+
+namespace CHCDemoEngine 
+{
+
+class Plane3;
+class AxisAlignedBox3;
+class Vector3;
+
+
+/** Class representing a convex polyhedron.
+*/
+class Polyhedron
+{
+public:
+	
+	Polyhedron();
+	/** Copy constructor making a deep copy of the polygons.
+	*/
+	Polyhedron(const Polyhedron &rhs);
+	/** Initialises the Polyhedron with the given polygons. 
+		@NOTE The polygons are NOT duplicated, only
+		a shallow copy is used.
+	*/	
+    Polyhedron(const PolygonContainer &polys);
+
+	~Polyhedron();
+	/** Computes the intersection of the polyhedron with the given plane
+		@returns NULL if the geometry is not split by this plane
+	*/
+	Polyhedron *CalcIntersection(const Plane3 &splitPlane) const;
+	/** Adds a polygon to the polyhedron.
+	*/
+	void Add(Polygon3 *poly);
+	/** Computes bounding box of the geometry.
+	*/
+	AxisAlignedBox3 GetBoundingBox() const;
+	/** Returns 
+		1 if geometry in front of the plane
+		0 if plane intersects geometry,
+		-1 if geometry is behind the plane
+	*/
+	int Side(const Plane3 &plane) const;
+	/** Returns true if this geometry is well shaped.
+	*/
+	bool Valid() const;
+	/** Number of polygons.
+	*/
+	int NumPolygons() const;
+	/** Returns the polygons in a container.
+	*/
+	const PolygonContainer &GetPolygons() const;
+
+	float GetArea() const;
+
+	float GetVolume() const;
+
+	Vector3 CenterOfMass() const;
+	/** Returns all the vertices of this polyhedron
+	*/
+	void CollectVertices(VertexArray &vertices) const;
+	
+	inline friend std::ostream &operator<<(std::ostream &s, const Polyhedron &a);
+
+
+
+protected:
+
+	/** Splits the given polygon with the polyhedron
+		Returns the part of the polygon inside of the polyhedron.
+	*/
+	Polygon3 *SplitPolygon(Polygon3 *polygon) const;
+
+	
+	
+	///////////////
+
+	/// the polygons
+	PolygonContainer mPolygons;
+	/// the bounding box
+	AxisAlignedBox3 mBox;
+};
+
+
+std::ostream &operator<<(std::ostream &s, const Polyhedron &a)
+{
+	PolygonContainer::const_iterator it, it_end = a.mPolygons.end();
+
+	for (it = a.mPolygons.begin(); it != it_end; ++ it)
+		s << *(*it) << std::endl;
+	return s << std::endl;
+}
+
+
+}
+
+#endif
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polyhedron.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polyhedron.cpp	(revision 2912)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polyhedron.cpp	(revision 2912)
@@ -0,0 +1,334 @@
+#include "Polyhedron.h"
+#include "common.h"
+#include "Polygon3.h"
+#include "Plane3.h"
+
+
+using namespace std;
+
+
+namespace CHCDemoEngine 
+{
+
+static const float epsilon = 1e-6f;
+
+/**********************************************************/
+/*             class Polyhedron Implementation             */
+/**********************************************************/
+
+
+Polyhedron::Polyhedron()
+{
+	mBox.Initialize();
+}
+
+
+Polyhedron::Polyhedron(const PolygonContainer &polys)
+{
+	mPolygons = polys;
+
+	mBox.Initialize();
+	mBox.Include(mPolygons);
+}
+
+
+Polyhedron::Polyhedron(const Polyhedron &rhs)
+{
+	mPolygons.reserve(rhs.mPolygons.size());
+	mBox = rhs.mBox;
+
+	PolygonContainer::const_iterator it, it_end = rhs.mPolygons.end();
+
+	for (it = rhs.mPolygons.begin(); it != it_end; ++ it)
+		Add(new Polygon3(*(*it)));
+}
+
+
+Polyhedron::~Polyhedron()
+{
+	CLEAR_CONTAINER(mPolygons);
+}
+
+
+int Polyhedron::NumPolygons() const
+{
+	return (int)mPolygons.size();
+}
+
+
+void Polyhedron::Add(Polygon3 *p)
+{
+    mPolygons.push_back(p);
+	mBox.Include(*p);
+}
+
+
+const PolygonContainer &Polyhedron::GetPolygons() const
+{
+	return mPolygons;
+}
+
+
+float Polyhedron::GetArea() const 
+{ 
+	float area = 0;
+
+	for (size_t i = 0; i < mPolygons.size(); ++ i)
+	{
+		area += mPolygons[i]->GetArea();
+	}
+
+	return area;
+}
+
+
+float Polyhedron::GetVolume() const
+{
+	// computes volume by tetrahedralization of the geometry
+	// We just compute the sum of the tetrahedron volumes
+	float volume = 0;
+	const float f = 1.0f / 6.0f;
+
+	PolygonContainer::const_iterator pit, pit_end = mPolygons.end();
+
+	// note: can take arbitrary point, e.g., the origin. However,
+	// we rather take the center of mass to prevents precision errors
+	const Vector3 center = CenterOfMass();
+
+	for (pit = mPolygons.begin(); pit != pit_end; ++ pit)
+	{
+		Polygon3 *poly = *pit;
+		const Vector3 v0 = poly->mVertices[0] - center;
+
+		for (int i = 1; i < (int)poly->mVertices.size() - 1; ++ i)
+		{
+			const Vector3 v1 = poly->mVertices[i] - center;
+			const Vector3 v2 = poly->mVertices[i + 1] - center;
+
+			// more robust version using abs and the center of mass
+			volume += fabs (f * (DotProd(v0, CrossProd(v1, v2))));
+		}
+	}
+
+	return volume;
+}
+
+
+AxisAlignedBox3 Polyhedron::GetBoundingBox() const
+{
+	return mBox;
+}
+
+
+int Polyhedron::Side(const Plane3 &plane) const
+{
+	int boxSide = mBox.Side(plane);
+	// plane does not intersect bounding box
+	if (boxSide != 0) return boxSide;
+
+	PolygonContainer::const_iterator it, it_end = mPolygons.end();
+
+	int s = 0;
+
+	for (it = mPolygons.begin(); it != it_end; ++ it)
+	{
+        const int side = (*it)->Side(plane, epsilon);
+
+		if (side != 0)
+		{
+			if (side == -s)
+				return 0; // sign changed => intersects
+
+			s = side;
+		}
+	}
+
+	return s;
+}
+
+
+Vector3 Polyhedron::CenterOfMass() const
+{
+	int n = 0;
+
+	Vector3 center(0,0,0);
+
+	PolygonContainer::const_iterator pit, pit_end = mPolygons.end();
+
+	for (pit = mPolygons.begin(); pit != pit_end; ++ pit)
+	{
+		Polygon3 *poly = *pit;
+		
+		VertexArray::const_iterator vit, vit_end = poly->mVertices.end();
+
+		for(vit = poly->mVertices.begin(); vit != vit_end; ++ vit)
+		{
+			center += *vit;
+			++ n;
+		}
+	}
+
+	return center / (float)n;
+}
+
+
+bool Polyhedron::Valid() const
+{
+	// polyhedron is degenerated
+	if (mPolygons.size() < 3)
+		return false;
+	else
+		return true;
+}
+
+
+Polyhedron *Polyhedron::CalcIntersection(const Plane3 &splitPlane) const
+{	
+	// first test plane intersection with geometry
+	const int intersect = Side(splitPlane);
+	
+	if (intersect == 1)
+		// on the other side of the plane, the intersection is empty
+		return NULL; 
+	else if (intersect == -1)
+		return NULL;
+		// does not intersect, just return a copy
+		//return new Polyhedron(*this);
+
+
+	//////////
+	//-- finally, create and add new polygon to close polyhedron
+
+	// get cross section of new polygon
+	Polygon3 *planePoly = mBox.CrossSection(splitPlane);
+
+	// create new face: split polygon with all other polygons
+	planePoly = SplitPolygon(planePoly);
+
+	// something is wrong, probably some numerical error: just bail out
+	if (!planePoly) 
+	{ 
+		cerr << "should not happen" << endl; 
+		return NULL;//new Polyhedron(*this); 
+	}
+
+	Polyhedron *clippedPolyhedron = new Polyhedron();
+
+	// add the new polygon to the polyhedron
+	clippedPolyhedron->Add(planePoly);
+
+
+
+	/////////////
+	//-- plane splits all polygons
+
+	for (int i = 0; i < (int)mPolygons.size(); ++ i)
+	{
+		Polygon3 *poly = mPolygons[i];
+
+		const int cf = mPolygons[i]->ClassifyPlane(splitPlane, epsilon);
+			
+		switch (cf)
+		{
+			// split case: split polygon and add it
+			case Polygon3::SPLIT:
+				{
+					Polygon3 *poly = mPolygons[i];
+
+					Polygon3 *frontPoly = new Polygon3();
+					Polygon3 *backPoly = new Polygon3();
+				
+					poly->Split(splitPlane, *frontPoly, *backPoly, epsilon);
+
+					// we are only interested in the polytope behind the plane
+					DEL_PTR(frontPoly);
+
+					if (backPoly->Valid(epsilon))
+						clippedPolyhedron->Add(backPoly);
+					else
+						DEL_PTR(backPoly);
+				}
+				
+				break;
+			case Polygon3::BACK_SIDE:
+			case Polygon3::COINCIDENT:
+				clippedPolyhedron->Add(new Polygon3(mPolygons[i]->mVertices));
+				break;
+			default:
+				// polygon is not in intersection
+				break;
+		}
+	}
+	
+
+	return clippedPolyhedron;
+}
+
+
+Polygon3 *Polyhedron::SplitPolygon(Polygon3 *polygon) const
+{
+	if (!polygon->Valid(epsilon)) DEL_PTR(polygon);
+
+	// polygon is split by all other planes
+	for (size_t i = 0; (i < mPolygons.size()) && polygon; ++ i)
+	{
+		const Plane3 plane = mPolygons[i]->GetSupportingPlane();
+
+		int cf = polygon->ClassifyPlane(plane, epsilon);
+
+		// split new polygon with all previous planes
+		switch (cf)
+		{
+			case Polygon3::SPLIT:
+				{
+					Polygon3 *frontPoly = new Polygon3();
+					Polygon3 *backPoly = new Polygon3();
+
+					polygon->Split(plane, *frontPoly, *backPoly, epsilon);
+					
+					// don't need these anymore
+					DEL_PTR(frontPoly);
+					DEL_PTR(polygon);
+
+					// back polygon belongs to geometry
+					if (backPoly->Valid(epsilon))
+						polygon = backPoly;
+					else
+						DEL_PTR(backPoly);
+				}
+				break;
+			case Polygon3::FRONT_SIDE:
+				cerr << "SplitPolygon: should not come here" << endl;
+				DEL_PTR(polygon);
+                break;
+			// polygon is taken as it is
+			case Polygon3::BACK_SIDE:
+			case Polygon3::COINCIDENT:
+			default:
+				break;
+		}
+	}
+
+	return polygon;
+}
+
+
+void Polyhedron::CollectVertices(VertexArray &vertices) const
+{
+	PolygonContainer::const_iterator it, it_end = mPolygons.end();
+
+	for (it = mPolygons.begin(); it != it_end; ++ it)
+	{
+		Polygon3 *poly = *it;
+
+		VertexArray::const_iterator vit, vit_end = poly->mVertices.end();
+
+		for (vit = poly->mVertices.begin(); vit != vit_end; ++ vit)
+		{
+			vertices.push_back(*vit);
+		}
+	}
+}
+
+
+}
Index: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polygon3.cpp
===================================================================
--- GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polygon3.cpp	(revision 2912)
+++ GTP/trunk/App/Demos/Vis/FriendlyCulling/src/Polygon3.cpp	(revision 2912)
@@ -0,0 +1,288 @@
+#include "Polygon3.h"
+#include "AxisAlignedBox3.h"
+#include "Plane3.h"
+
+
+using namespace std;
+
+namespace CHCDemoEngine 
+{
+
+Polygon3::Polygon3()
+{
+}
+
+
+Polygon3::Polygon3(const VertexArray &vertices)
+{
+	mVertices.reserve(vertices.size());
+	mVertices = vertices;
+}
+
+
+Polygon3::~Polygon3() 
+{
+}
+
+
+Plane3 Polygon3::GetSupportingPlane() const
+{
+	return Plane3(mVertices[0], mVertices[1], mVertices[2]);
+}
+
+
+Vector3 Polygon3::GetNormal() const 
+{
+    return Normalize(CrossProd(mVertices[2] - mVertices[1],
+							   mVertices[0] - mVertices[1]));
+}
+
+
+void Polygon3::Split(const Plane3 &partition, 
+					 Polygon3 &front, 
+					 Polygon3 &back, float epsilon)
+{
+	Vector3 ptA = mVertices.back();
+	int sideA = partition.Side(ptA, epsilon);
+	bool foundSplit = false;
+    Vector3 lastSplit;
+		
+	/////////////
+	//-- find line - plane intersections
+
+	VertexArray::const_iterator it, it_end = mVertices.end();
+
+	for (it = mVertices.begin(); it != it_end; ++ it)
+	{
+		Vector3 ptB = *it;
+		int sideB = partition.Side(ptB, epsilon);
+	
+		// vertices on different sides => split
+	    if (sideB > 0)
+		{
+			if (sideA < 0)
+			{
+				//-- plane - line intersection
+				Vector3 splitPt = partition.FindIntersection(ptA, ptB);
+			
+				// test if split point not too close to previous split point
+				if (!foundSplit || (!EpsilonEqualV3(splitPt, lastSplit, epsilon)))
+				{
+					// add vertex to both polygons
+					front.mVertices.push_back(splitPt);
+					back.mVertices.push_back(splitPt);
+					
+					lastSplit = splitPt;
+					foundSplit = true;
+				}
+			}
+			front.mVertices.push_back(ptB);
+		}
+		else if (sideB < 0)
+		{
+			if (sideA > 0)
+			{
+				////////////
+				//-- plane - line intersection
+
+				Vector3 splitPt = partition.FindIntersection(ptA, ptB);
+				
+				// test if split point not too close to previous split point
+				if (!foundSplit || (!EpsilonEqualV3(splitPt, lastSplit, epsilon)))
+				{
+					// add vertex to both polygons
+					front.mVertices.push_back(splitPt);
+					back.mVertices.push_back(splitPt);
+
+					lastSplit = splitPt;
+					foundSplit = true;
+				}	
+			}
+
+			back.mVertices.push_back(ptB);
+		}
+		else
+		{
+			// vertex on plane => add vertex to both polygons
+			front.mVertices.push_back(ptB);
+			back.mVertices.push_back(ptB); 
+		}
+	
+		ptA = ptB;
+		sideA = sideB;
+	}
+}
+
+
+float Polygon3::GetArea() const
+{
+	Vector3 v = CrossProd(mVertices.back(), mVertices.front());
+    
+    for (int i=0; i < mVertices.size() - 1; ++i)
+		v += CrossProd(mVertices[i], mVertices[i+1]);
+    
+    return 0.5f * fabs(DotProd(GetNormal(), v));
+}
+
+
+int Polygon3::Side(const Plane3 &plane, 
+				   const float epsilon) const
+{
+	int classification = ClassifyPlane(plane, epsilon);
+	
+	if (classification == BACK_SIDE)
+		return -1;
+	else if (classification == FRONT_SIDE)
+		return 1;
+	// plane splits polygon
+	return 0;
+}
+
+
+int Polygon3::ClassifyPlane(const Plane3 &plane, 
+							const float epsilon) const
+{
+	VertexArray::const_iterator it, it_end = mVertices.end();
+
+	bool onFrontSide = false;
+	bool onBackSide = false;
+	
+	int count = 0;
+	// find possible line-plane intersections
+	for (it = mVertices.begin(); it != it_end; ++ it)
+	{
+		const int side = plane.Side(*it, epsilon);
+		
+		if (side > 0)
+		{
+			onFrontSide = true;
+		}
+		else if (side < 0)
+		{
+			onBackSide = true;
+		}
+
+		//TODO: check if split goes through vertex
+		if (onFrontSide && onBackSide) // split 
+		{
+			return SPLIT;
+		}
+		// 3 vertices enough to decide if coincident
+		else if (((++ count) >= 3) && !onFrontSide && !onBackSide)
+		{   
+			return COINCIDENT; 
+		}
+	}
+
+	if (onBackSide)
+	{
+		return BACK_SIDE;
+	}
+	else if (onFrontSide)
+	{
+		return FRONT_SIDE;
+	}
+	
+	return COINCIDENT; // plane and polygon are coincident
+}
+
+
+Vector3 Polygon3::Center() const
+{
+	int i;
+	Vector3 sum = mVertices[0];
+	for (i=1; i < mVertices.size(); i++)
+		sum += mVertices[i];
+	
+	return sum / (float)i;
+}
+
+
+bool Polygon3::Valid(const float epsilon) const
+{
+	if (mVertices.size() < 3)
+		return false;
+
+	// matt: removed for performance issues
+	// check if area exceeds certain size
+	if (GetArea() < 1e-10)
+	{
+		cerr << "area too small: " << GetArea() << std::endl;
+		return false;
+	}
+		
+	Vector3 vtx = mVertices.back();
+	VertexArray::const_iterator it, it_end = mVertices.end();
+
+	for (it = mVertices.begin(); it != it_end; ++it)
+	{
+		if (EpsilonEqualV3(vtx, *it, epsilon))
+		{
+			cerr << "Double vertices:\n" << *this << endl;
+			return false;
+		}
+		vtx = *it;
+	}
+	
+	return true;
+}
+
+
+// int_lineseg returns 1 if the given line segment intersects a 2D
+// ray travelling in the positive X direction.	This is used in the
+// Jordan curve computation for polygon intersection.
+inline int int_lineseg(float px,
+					   float py,
+					   float u1,
+					   float v1,
+					   float u2,
+					   float v2)
+{
+	float t;
+	float ydiff;
+
+	u1 -= px; u2 -= px; 	  // translate line
+	v1 -= py; v2 -= py;
+
+	if ((v1 > 0 && v2 > 0) ||
+		(v1 < 0 && v2 < 0) ||
+		(u1 < 0 && u2 < 0))
+		return 0;
+
+	if (u1 > 0 && u2 > 0)
+		return 1;
+
+	ydiff = v2 - v1;
+
+	if (fabs(ydiff) < Limits::Small) 
+	{	 
+		// denominator near 0
+		if (((fabs(v1) > Limits::Small) || (u1 > 0) || (u2 > 0)))
+			return 0;
+
+		return 1;
+	}
+
+	t = -v1 / ydiff; // Compute parameter
+
+	return (u1 + t * (u2 - u1)) > 0;
+}
+
+
+AxisAlignedBox3 Polygon3::GetBoundingBox() const
+{
+	AxisAlignedBox3 box;
+	box.Initialize();
+
+	VertexArray::const_iterator vit, vit_end = mVertices.end();
+
+	for (vit = mVertices.begin(); vit != vit_end; ++ vit)
+	{
+		box.Include(*vit);
+	}
+
+	return box;
+}
+
+
+}
