[Yake-svn] SF.net SVN: yake:[1931] trunk/yake/yake/base/math/yakePolygonClipper.h

[<psy...@us...>]

Revision: 1931
          http://yake.svn.sourceforge.net/yake/?rev=1931&view=rev
Author:   psyclonist
Date:     2008-07-28 23:15:51 +0000 (Mon, 28 Jul 2008)

Log Message:
-----------
* [base/math] added 3D polygon clipper (math::Clipper<>) for clipping polygons against one or more planes

Added Paths:
-----------
    trunk/yake/yake/base/math/yakePolygonClipper.h

Added: trunk/yake/yake/base/math/yakePolygonClipper.h
===================================================================
--- trunk/yake/yake/base/math/yakePolygonClipper.h	                        (rev 0)
+++ trunk/yake/yake/base/math/yakePolygonClipper.h	2008-07-28 23:15:51 UTC (rev 1931)
@@ -0,0 +1,162 @@
+/*
+   ------------------------------------------------------------------------------------
+   This file is part of YAKE
+   Copyright (c) 2004 - 2008 The YAKE Team
+   For the latest information visit http://www.yake.org
+   ------------------------------------------------------------------------------------
+   This program is free software; you can redistribute it and/or modify it under
+   the terms of the GNU Lesser General Public License as published by the Free Software
+   Foundation; either version 2 of the License, or (at your option) any later
+   version.
+
+   This program is distributed in the hope that it will be useful, but WITHOUT
+   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+   FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public License along with
+   this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+   Place - Suite 330, Boston, MA 02111-1307, USA, or go to
+   http://www.gnu.org/copyleft/lesser.txt.
+   ------------------------------------------------------------------------------------
+   If you are interested in another license model contact the Yake Team via
+   E-Mail: te...@ya....
+   For more information see the LICENSE file in the root directory of the
+   source code distribution.
+   ------------------------------------------------------------------------------------
+*/
+#ifndef YAKE_BASE_MATH_POLYGONCLIPPER_H
+#define YAKE_BASE_MATH_POLYGONCLIPPER_H
+
+#include "yake/base/yakePrerequisites.h"
+#include "yake/base/math/yakeMath.h"
+#include "yake/base/math/yakeVector3.h"
+#include "yake/base/math/yakePoint3.h"
+#include "yake/base/math/yakePlane.h"
+
+namespace yake {
+namespace math {
+
+	/**
+	For the vertex type the following free (!) functions need to be available:
+	@code
+		Point3 get_position(const VertexType&);
+		void set_position(VertexType&, const Point3&);
+		VertexType interpolate(const VertexType& from, const VertexType& to, const real s);
+	@endcode
+	Yake ships with functions for VertexType = Point3.
+	The PolygonType needs to provide the following member (!) functions:
+	@code
+		const VertexType& at(size_t) const;
+		size_t size() const; // return the number of vertices in the polygon
+		R push_back(const VertexType&); // appends the vertex to the polygon (return value is not used)
+	@endcode
+	Example Usage:
+	@code
+		struct vertex;
+		Plane p(...);
+		boost::array<vertex,4> quad = {{...}};
+		std::deque<vertex> clipped;
+		Clipper<vertex>::clip(p, quad, clipped);
+	@endcode
+	*/
+	template<class VertexType/*, class PolygonType = std::deque<VertexType> */>
+	struct Clipper
+	{
+		typedef VertexType vertex_type;
+		//typedef PolygonType polygon_type;
+		/** Clips the (convex or concave) polygon inPoly against all the planes and returns the (possibly)
+			clipped polygon in currPoly.
+			The container for the planes needs to provide two functions:
+		@code
+			const Plane& at(size_t) const;
+			size_t size() const;
+		@endcode
+		@note If the polygon did not need to be clipped then the returned currPoly will nevertheless 
+			contain the same vertices as inPoly.
+		@todo Optimize: Remove unnecessary copies in the intersection loop (currPoly=outPoly).
+		*/
+		template<typename Ct, class polygon_type_in, class polygon_type_out>
+		static void clip(const Ct& planes, const polygon_type_in& inPoly, polygon_type_out& currPoly)
+		{
+			currPoly.clear();
+			if (inPoly.empty())
+				return;
+
+			//currPoly = inPoly;
+			std::copy(inPoly.begin(),inPoly.end(),std::back_inserter(currPoly));
+
+			YAKE_ASSERT(currPoly.size() >= 3)(currPoly.size());
+			for (size_t planeIdx=0; planeIdx<planes.size(); ++planeIdx)
+			{
+				const Plane& plane = planes.at(planeIdx);
+				polygon_type_out outPoly;
+				clip(plane,currPoly,outPoly);
+				currPoly = outPoly;
+			}
+		}
+		/** Clips the (convex or concave) polygon inPoly against the plane and returns the
+			(possibly) clipped polygon in outPoly.
+		@note If the polygon did not need to be clipped then outPoly will nevertheless contain the
+			same vertices as inPoly.
+		@todo Optimize: Use references as return values of get_position() ?
+		@note Algorithm used is Sutherland-Hodgman for simplicity.
+		*/
+		template<class polygon_type_in, class polygon_type_out>
+		static void clip(const Plane& plane, const polygon_type_in& inPoly, polygon_type_out& outPoly)
+		{
+			outPoly.clear();
+			if (inPoly.empty())
+				return;
+
+			const real eps = std::numeric_limits<real>::epsilon();
+			YAKE_ASSERT(inPoly.size() >= 3)(inPoly.size());
+
+			// for each edge:
+			for (size_t vtxIdx=0; vtxIdx<inPoly.size(); ++vtxIdx)
+			{
+				const vertex_type& from_vtx = inPoly.at(vtxIdx);
+				const vertex_type& to_vtx = inPoly.at((vtxIdx == inPoly.size()-1) ? 0 : (vtxIdx+1));
+
+				const Point3 from = get_position(from_vtx);
+				const Point3 to = get_position(to_vtx);
+
+				const bool start_in = plane.distanceTo(from) > .01;
+				const bool end_in = plane.distanceTo(to) > .01;
+				if (end_in)
+				{
+					if (!start_in)
+					{
+#if 0
+						const Vector3 delta = (to-from);
+						const double delta_length = delta.length();
+						Ray r(from, delta / delta_length/*delta.normalisedCopy()*/);
+						const std::pair<bool,real> intResult = intersect(plane,r);
+						outPoly.push_back(interpolate(from_vtx,to_vtx,intResult.second / delta_length));
+#else
+						// We can avoid a sqrt() call and a division by using the
+						// vector (end-start) as the ray direction, i.e. without normalization!
+						// This way intersect() returns the intersection parameter as [0..1] which we can feed
+						// directly into interpolate() thereby avoiding a division.
+						const Vector3 delta = (to-from);
+						Ray r(from, delta);
+						const std::pair<bool,real> intResult = intersect(plane,r);
+						outPoly.push_back(interpolate(from_vtx,to_vtx,intResult.second));
+#endif
+					}
+					outPoly.push_back(to_vtx);
+				}
+				else if (start_in)
+				{
+					const Vector3 delta = (to-from);
+					Ray r(from, delta);
+					const std::pair<bool,real> intResult = intersect(plane,r);
+					outPoly.push_back(interpolate(from_vtx,to_vtx,intResult.second));
+				}
+			}
+		}
+	};
+
+} // math
+} // yake
+
+#endif // YAKE_BASE_MATH_POLYGONCLIPPER_H


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.