Properly sort intersection points for complex shapes

Code structure in simpler shapes have been adjusted to keep it similar.

diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
index fd55c8e6e090875cd147f57697a35190fa26206e..50b04e80c506e93f7dc995187140e871dec66e27 100644 (file)
--- 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 0d895ac5bc0aecbac9d6de46f5e93c9c932ca0dd..7aeedb0cd146e30e761e3c88b41d54dde680cdfb 100644 (file)
--- 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 42e4d61a75a49ce0824aaf231388013246c1413f..9a161f35fb0fdbc5ff604735d51eb6e1d060eeaf 100644 (file)
--- 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 35cddd1ac36461f4ee2a0e00122abda491ce3b0a..cbec2d99af744e7182f4b5f0081379b059a14d95 100644 (file)
--- 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 a5bd794f90052bc96fcc307dfdb67b74244707c8..57a66d1e95f3898bf1f050ed65afa77bf8d89cae 100644 (file)
--- 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