From 827b227ae53884109b6885ccd1424dda8c0b3725 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Tue, 21 May 2013 20:53:09 +0300
Subject: [PATCH] Properly sort intersection points for complex shapes

Code structure in simpler shapes have been adjusted to keep it similar.
---
 source/geometry/compositeshape.h | 21 +++++++--------------
 source/geometry/extrudedshape.h  | 17 ++++++-----------
 source/geometry/hyperbox.h       | 11 ++++++-----
 source/geometry/hypersphere.h    |  6 ++----
 source/geometry/surfacepoint.h   | 15 +++++++++++++++
 5 files changed, 36 insertions(+), 34 deletions(-)

diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
index fd55c8e..50b04e8 100644
--- a/source/geometry/compositeshape.h
+++ b/source/geometry/compositeshape.h
@@ -105,14 +105,13 @@ template<typename T, unsigned D, typename O>
 inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray, SurfacePoint<T, D> *points, unsigned size) const
 {
 	unsigned n = 0;
-	for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
+	for(typename ShapeArray::const_iterator i=shapes.begin(); (n<size && i!=shapes.end()); ++i)
 	{
 		unsigned base = n;
 		unsigned count = (*i)->get_intersections(ray, points+base, size-base);
-		for(unsigned j=0; j<count; ++j)
+		for(unsigned j=0; (n<size && j<count); ++j)
 		{
-			// XXX Devise a way to reduce copies here
-			SurfacePoint<T, D> pt = points[base+j];
+			SurfacePoint<T, D> &pt = points[base+j];
 
 			bool surface = Ops::init_surface();
 			for(typename ShapeArray::const_iterator k=shapes.begin(); k!=shapes.end(); ++k)
@@ -121,22 +120,16 @@ inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray,
 
 			if(surface)
 			{
-				if(points)
-				{
-					unsigned k;
-					for(k=n; (k>0 && points[k-1].distance>pt.distance); --k)
-						points[k] = points[k-1];
-					if(base+j!=k)
-						points[k] = pt;
-				}
+				if(points && base+j!=n)
+					points[n] = pt;
 
 				++n;
-				if(n==size)
-					return n;
 			}
 		}
 	}
 
+	sort_points(points, n);
+
 	return n;
 }
 
diff --git a/source/geometry/extrudedshape.h b/source/geometry/extrudedshape.h
index 0d895ac..7aeedb0 100644
--- a/source/geometry/extrudedshape.h
+++ b/source/geometry/extrudedshape.h
@@ -141,7 +141,7 @@ inline unsigned ExtrudedShape<T, D>::get_intersections(const Ray<T, D> &ray, Sur
 			base_points = reinterpret_cast<SurfacePoint<T, D-1> *>(points+size)-size;
 
 		unsigned count = base->get_intersections(base_ray, base_points, size);
-		for(unsigned i=0; i<count; ++i)
+		for(unsigned i=0; (n<size && i<count); ++i)
 		{
 			if(points)
 			{
@@ -152,23 +152,21 @@ inline unsigned ExtrudedShape<T, D>::get_intersections(const Ray<T, D> &ray, Sur
 			}
 
 			++n;
-			if(n==size)
-				return n;
 		}
 	}
 
 	/* If the ray is not parallel to the base space, it may pass through the
 	caps. */
-	if(ray_direction[D-1])
+	if(n<size && ray_direction[D-1])
 	{
-		for(int i=-1; i<=1; i+=2)
+		for(int i=-1; (n<size && i<=1); i+=2)
 		{
 			T x = (half_length*i-ray_start[D-1])/ray_direction[D-1];
 			if(!ray.check_limits(x))
 				continue;
 
 			LinAl::Vector<T, D> p = ray_start+ray_direction*x;
-			if(base->contains(LinAl::Vector<T, D-1>(p)) && n<size)
+			if(base->contains(LinAl::Vector<T, D-1>(p)))
 			{
 				if(points)
 				{
@@ -176,16 +174,13 @@ inline unsigned ExtrudedShape<T, D>::get_intersections(const Ray<T, D> &ray, Sur
 					points[n].normal = LinAl::Vector<T, D>();
 					points[n].normal[D-1] = i;
 					points[n].distance = x;
-
-					if(n==1 && x<points[0].distance)
-						swap(points[0], points[1]);
 				}
 
 				++n;
-				if(n==size)
-					return n;
 			}
 		}
+
+		sort_points(points, n);
 	}
 
 	return n;
diff --git a/source/geometry/hyperbox.h b/source/geometry/hyperbox.h
index 42e4d61..9a161f3 100644
--- a/source/geometry/hyperbox.h
+++ b/source/geometry/hyperbox.h
@@ -88,14 +88,17 @@ inline unsigned HyperBox<T, D>::get_intersections(const Ray<T, D> &ray, SurfaceP
 {
 	using std::abs;
 
+	if(size>2)
+		size = 2;
+
 	LinAl::Vector<T, D> half_dim = dimensions/T(2);
 	unsigned n = 0;
-	for(unsigned i=0; i<D; ++i)
+	for(unsigned i=0; (n<size && i<D); ++i)
 	{
 		if(!ray.get_direction()[i])
 			continue;
 
-		for(int j=-1; j<=1; j+=2)
+		for(int j=-1; (n<size && j<=1); j+=2)
 		{
 			T x = (T(j)*half_dim[i]-ray.get_start()[i])/ray.get_direction()[i];
 			if(!ray.check_limits(x))
@@ -107,7 +110,7 @@ inline unsigned HyperBox<T, D>::get_intersections(const Ray<T, D> &ray, SurfaceP
 			for(unsigned k=0; (inside && k<D); ++k)
 				inside = (k==i || abs(p[k])<=half_dim[k]);
 
-			if(inside && n<size)
+			if(inside)
 			{
 				if(points)
 				{
@@ -121,8 +124,6 @@ inline unsigned HyperBox<T, D>::get_intersections(const Ray<T, D> &ray, SurfaceP
 				}
 
 				++n;
-				if(n==size || n==2)
-					return n;
 			}
 		}
 	}
diff --git a/source/geometry/hypersphere.h b/source/geometry/hypersphere.h
index 35cddd1..cbec2d9 100644
--- a/source/geometry/hypersphere.h
+++ b/source/geometry/hypersphere.h
@@ -89,10 +89,10 @@ inline unsigned HyperSphere<T, D>::get_intersections(const Ray<T, D> &ray, Surfa
 	T offset = sqrt(offset_sq);
 
 	unsigned n = 0;
-	for(int i=-1; i<=1; i+=2)
+	for(int i=-1; (n<size && i<=1); i+=2)
 	{
 		T x = mid+offset*i;
-		if(ray.check_limits(x) && n<size)
+		if(ray.check_limits(x))
 		{
 			if(points)
 			{
@@ -102,8 +102,6 @@ inline unsigned HyperSphere<T, D>::get_intersections(const Ray<T, D> &ray, Surfa
 			}
 
 			++n;
-			if(n==size)
-				return n;
 		}
 	}
 
diff --git a/source/geometry/surfacepoint.h b/source/geometry/surfacepoint.h
index a5bd794..57a66d1 100644
--- a/source/geometry/surfacepoint.h
+++ b/source/geometry/surfacepoint.h
@@ -1,6 +1,7 @@
 #ifndef MSP_GEOMETRY_SURFACEPOINT_H_
 #define MSP_GEOMETRY_SURFACEPOINT_H_
 
+#include <algorithm>
 #include <msp/linal/vector.h>
 
 namespace Msp {
@@ -17,6 +18,20 @@ struct SurfacePoint
 	T distance;
 };
 
+template<typename T, unsigned N>
+void sort_points(SurfacePoint<T, N> *points, unsigned size)
+{
+	for(unsigned i=0; i<size; ++i)
+	{
+		unsigned n = i;
+		for(unsigned j=i+1; j<size; ++j)
+			if(points[j].distance<points[n].distance)
+				n = j;
+		if(n!=i)
+			std::swap(points[i], points[n]);
+	}
+}
+
 } // namespace Geometry
 } // namespace Msp
 
-- 
2.43.0