Rework CompositeShape algorithms

The old version had problems with coplanar surfaces and sometimes failed
to produce intersections when it should have.

diff --git a/source/geometry/compositeshape.h b/source/geometry/compositeshape.h
index f0b1f529544c12913202640c1e22604e5e5d5ded..0c2c838ec7d13364e6408872cc8dfad113ce5914 100644 (file)
--- a/source/geometry/compositeshape.h
+++ b/source/geometry/compositeshape.h
@@ -21,7 +21,6 @@ protected:
 
        ShapeArray shapes;
        unsigned max_isect;
-       unsigned min_scratch;
 
        CompositeShape() { }
        CompositeShape(const Shape<T, D> &, const Shape<T, D> &);
@@ -66,20 +65,14 @@ template<typename T, unsigned D, typename O>
 inline void CompositeShape<T, D, O>::init()
 {
        max_isect = 0;
-       min_scratch = 0;
        for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
-       {
-               unsigned mi = (*i)->get_max_ray_intersections();
-               max_isect += mi;
-               min_scratch = std::max(min_scratch, mi);
-       }
+               max_isect += (*i)->get_max_ray_intersections();
 }
 
 template<typename T, unsigned D, typename O>
 inline CompositeShape<T, D, O>::CompositeShape(const CompositeShape<T, D, O> &other):
        shapes(other.shapes),
-       max_isect(other.max_isect),
-       min_scratch(other.min_scratch)
+       max_isect(other.max_isect)
 {
        for(typename ShapeArray::iterator i=shapes.begin(); i!=shapes.end(); ++i)
                *i = (*i)->clone();
@@ -96,7 +89,6 @@ inline CompositeShape<T, D, O> &CompositeShape<T, D, O>::operator=(const Composi
                *i = (*i)->clone();
 
        max_isect = other.max_isect;
-       min_scratch = other.min_scratch;
 }
 
 template<typename T, unsigned D, typename O>
@@ -123,12 +115,12 @@ inline BoundingBox<T, D> CompositeShape<T, D, O>::get_axis_aligned_bounding_box(
 template<typename T, unsigned D, typename O>
 inline bool CompositeShape<T, D, O>::contains(const LinAl::Vector<T, D> &point) const
 {
-       bool inside = Ops::init_inside();
+       bool inside = false;
        for(typename ShapeArray::const_iterator i=shapes.begin(); i!=shapes.end(); ++i)
        {
-               inside = Ops::combine_inside(inside, (*i)->contains(point));
-               if(Ops::is_inside_decided(inside))
-                       break;
+               inside = (*i)->contains(point);
+               if(Ops::shortcircuit(inside))
+                       return inside;
        }
        return inside;
 }
@@ -138,39 +130,58 @@ inline unsigned CompositeShape<T, D, O>::get_intersections(const Ray<T, D> &ray,
 {
        SurfacePoint<T, D> *buffer = points;
        unsigned buf_size = size;
-       if(!points)
+       if(!points && !Ops::shortcircuit(true))
        {
-               buffer = new SurfacePoint<T, D>[min_scratch];
-               buf_size = min_scratch;
+               buffer = new SurfacePoint<T, D>[max_isect];
+               buf_size = max_isect;
        }
 
+       int start_nesting = 0;
        unsigned n = 0;
-       for(typename ShapeArray::const_iterator i=shapes.begin(); (n<size && i!=shapes.end()); ++i)
+       for(typename ShapeArray::const_iterator i=shapes.begin(); (n<buf_size && i!=shapes.end()); ++i)
        {
-               unsigned base = (points ? n : 0);
+               unsigned base = n;
                unsigned count = (*i)->get_intersections(ray, buffer+base, buf_size-base);
-               for(unsigned j=0; (n<size && j<count); ++j)
+               bool start_inside = (*i)->contains(ray.get_start());
+
+               if(!count && !start_inside)
                {
-                       SurfacePoint<T, D> &pt = buffer[base+j];
+                       if(Ops::shortcircuit(false))
+                               return 0;
+                       continue;
+               }
 
-                       bool surface = Ops::init_surface();
-                       for(typename ShapeArray::const_iterator k=shapes.begin(); k!=shapes.end(); ++k)
-                               if(k!=i)
-                                       surface = Ops::combine_surface(surface, (*k)->contains(pt.position));
+               start_nesting += start_inside;
 
-                       if(surface)
-                       {
-                               if(points && base+j!=n)
-                                       points[n] = pt;
+               if(!base)
+               {
+                       n = count;
+                       continue;
+               }
 
-                               ++n;
+               sort_points(buffer, base+count);
+
+               int nesting = start_nesting;
+               unsigned k = 0;
+               for(unsigned j=0; j<base+count; ++j)
+               {
+                       if(Ops::shortcircuit(nesting+buffer[j].entry<2))
+                       {
+                               if(j!=k)
+                                       buffer[k] = buffer[j];
+                               ++k;
                        }
+
+                       nesting += buffer[j].entry*2-1;
                }
+
+               if(!k && Ops::shortcircuit(false))
+                       return 0;
+
+               n = k;
        }
 
-       if(points)
-               sort_points(points, n);
-       else
+       if(buffer!=points)
                delete[] buffer;
 
        return n;

diff --git a/source/geometry/intersection.h b/source/geometry/intersection.h
index 7d21f75f81c081e87aeb783710a56aab7fe6207e..0e555b03f7086185076ca904512605b0ae204e08 100644 (file)
--- a/source/geometry/intersection.h
+++ b/source/geometry/intersection.h
@@ -10,11 +10,7 @@ template<typename T, unsigned D>
 struct IntersectionOps
 {
        static BoundingBox<T, D> combine_aabb(const BoundingBox<T, D> &a, const BoundingBox<T, D> &b) { return a&b; }
-       static bool init_inside() { return true; }
-       static bool combine_inside(bool a, bool b) { return a && b; }
-       static bool is_inside_decided(bool a) { return !a; }
-       static bool init_surface() { return true; }
-       static bool combine_surface(bool a, bool b) { return a && b; }
+       static bool shortcircuit(bool c) { return !c; }
 };
 
 /**

diff --git a/source/geometry/union.h b/source/geometry/union.h
index a1562cb4e6b458b55003d981b5898c0c7ded2f25..738f1f240f3de600dac9d63e1e048fe786bc3d75 100644 (file)
--- a/source/geometry/union.h
+++ b/source/geometry/union.h
@@ -10,11 +10,7 @@ template<typename T, unsigned D>
 struct UnionOps
 {
        static BoundingBox<T, D> combine_aabb(const BoundingBox<T, D> &a, const BoundingBox<T, D> &b) { return a|b; }
-       static bool init_inside() { return false; }
-       static bool combine_inside(bool a, bool b) { return a || b; }
-       static bool is_inside_decided(bool a) { return a; }
-       static bool init_surface() { return true; }
-       static bool combine_surface(bool a, bool b) { return a && !b; }
+       static bool shortcircuit(bool c) { return c; }
 };
 
 /**