[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [43336] branches/carve_booleans/extern/ carve: Carve booleans: integrate new Carve library

Sergey Sharybin sergey.vfx at gmail.com
Thu Jan 12 22:47:24 CET 2012


Revision: 43336
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=43336
Author:   nazgul
Date:     2012-01-12 21:47:14 +0000 (Thu, 12 Jan 2012)
Log Message:
-----------
Carve booleans: integrate new Carve library

This resolves crash when boolean modifier is used for non-closed meshes.

It's still undefined which points are internal for such meshes, so modifier
might fail for such meshes (it'll output original mesh).

Modified Paths:
--------------
    branches/carve_booleans/extern/carve/include/carve/aabb_impl.hpp
    branches/carve_booleans/extern/carve/include/carve/carve.hpp
    branches/carve_booleans/extern/carve/include/carve/collection/unordered/libstdcpp_impl.hpp
    branches/carve_booleans/extern/carve/include/carve/geom2d.hpp
    branches/carve_booleans/extern/carve/include/carve/geom3d.hpp
    branches/carve_booleans/extern/carve/include/carve/math.hpp
    branches/carve_booleans/extern/carve/include/carve/polyline_iter.hpp
    branches/carve_booleans/extern/carve/include/carve/triangulator_impl.hpp
    branches/carve_booleans/extern/carve/include/carve/win32.h
    branches/carve_booleans/extern/carve/lib/csg_collector.cpp
    branches/carve_booleans/extern/carve/lib/geom2d.cpp
    branches/carve_booleans/extern/carve/lib/geom3d.cpp
    branches/carve_booleans/extern/carve/lib/intersect.cpp
    branches/carve_booleans/extern/carve/lib/intersect_face_division.cpp
    branches/carve_booleans/extern/carve/lib/intersect_group.cpp
    branches/carve_booleans/extern/carve/lib/polyhedron.cpp
    branches/carve_booleans/extern/carve/lib/triangulator.cpp
    branches/carve_booleans/extern/carve/patches/strict_flags.patch
    branches/carve_booleans/extern/carve/patches/win32.patch

Modified: branches/carve_booleans/extern/carve/include/carve/aabb_impl.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/aabb_impl.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/aabb_impl.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -161,7 +161,7 @@
     template<unsigned ndim>
     bool aabb<ndim>::completelyContains(const aabb<ndim> &other) const {
       for (unsigned i = 0; i < ndim; ++i) {
-        if (fabs(other.pos.v[i] - pos.v[i] + other.extent.v[i]) > extent.v[i]) return false;
+        if (fabs(other.pos.v[i] - pos.v[i]) + other.extent.v[i] > extent.v[i]) return false;
       }
       return true;
     }
@@ -319,7 +319,6 @@
     template<>
     inline bool aabb<3>::intersects(const ray<3> &ray) const {
       vector<3> t = pos - ray.v;
-      vector<3> v;
       double r;
 
       //l.cross(x-axis)?
@@ -341,7 +340,6 @@
     inline bool aabb<3>::intersectsLineSegment(const vector<3> &v1, const vector<3> &v2) const {
       vector<3> half_length = 0.5 * (v2 - v1);
       vector<3> t = pos - half_length - v1;
-      vector<3> v;
       double r;
 
       //do any of the principal axes form a separating axis?

Modified: branches/carve_booleans/extern/carve/include/carve/carve.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/carve.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/carve.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -16,7 +16,11 @@
 
 #pragma once
 
-#if defined(_MSC_VER)
+#if defined(CMAKE_BUILD)
+#  include <carve/config.h>
+#elif defined(XCODE_BUILD)
+#  include <carve/xcode_config.h>
+#elif defined(_MSC_VER)
 #  include <carve/vcpp_config.h>
 #else
 #  include <carve/config.h>
@@ -45,6 +49,7 @@
 #include <iomanip>
 
 #include <carve/collection.hpp>
+
 #include <carve/util.hpp>
 
 #include <stdarg.h>

Modified: branches/carve_booleans/extern/carve/include/carve/collection/unordered/libstdcpp_impl.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/collection/unordered/libstdcpp_impl.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/collection/unordered/libstdcpp_impl.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -47,7 +47,7 @@
   class unordered_map : public __gnu_cxx::hash_map<K, V, H> {
     typedef __gnu_cxx::hash_map<K, V, H> super;
   public:
-    typedef super::mapped_type data_type;
+    typedef typename super::mapped_type data_type;
   };
 
   template<typename K, typename H = __gnu_cxx::hash<K> >

Modified: branches/carve_booleans/extern/carve/include/carve/geom2d.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/geom2d.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/geom2d.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -228,9 +228,16 @@
       }
     };
 
-    LineIntersectionInfo lineSegmentIntersection(const P2 &l1v1, const P2 &l1v2, const P2 &l2v1, const P2 &l2v2);
-    LineIntersectionInfo lineSegmentIntersection(const LineSegment2 &l1, const LineSegment2 &l2);
+    bool lineSegmentIntersection_simple(const P2 &l1v1, const P2 &l1v2,
+                                        const P2 &l2v1, const P2 &l2v2);
+    bool lineSegmentIntersection_simple(const LineSegment2 &l1,
+                                        const LineSegment2 &l2);
 
+    LineIntersectionInfo lineSegmentIntersection(const P2 &l1v1, const P2 &l1v2,
+                                                 const P2 &l2v1, const P2 &l2v2);
+    LineIntersectionInfo lineSegmentIntersection(const LineSegment2 &l1,
+                                                 const LineSegment2 &l2);
+
     int lineSegmentPolyIntersections(const std::vector<P2> &points,
                                      LineSegment2 line,
                                      std::vector<PolyInclusionInfo> &out);

Modified: branches/carve_booleans/extern/carve/include/carve/geom3d.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/geom3d.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/geom3d.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -50,19 +50,19 @@
       iter_t i;
 
       Vector n = Vector::ZERO();
-      Vector v, z;
+      Vector v;
       Vector p1, p2, p3, c1, c2;
       if (begin == end) return false;
 
       i = begin;
-      p1 = c1 = adapt(*i++); if (i == end) return false;
-      p2 = c2 = adapt(*i++); if (i == end) return false;
+      p1 = c1 = adapt(*i); if (++i == end) return false;
+      p2 = c2 = adapt(*i); if (++i == end) return false;
 
 #if defined(CARVE_DEBUG)
       size_t N = 2;
 #endif
-      while (i != end) {
-        p3 = adapt(*i++);
+      do {
+        p3 = adapt(*i);
         v = cross(p3 - p2, p1 - p2);
         if (v.v[largestAxis(v)]) v.negate();
         n += v;
@@ -70,7 +70,7 @@
 #if defined(CARVE_DEBUG)
         ++N;
 #endif
-      }
+      } while (++i != end);
 
       p1 = p2; p2 = p3; p3 = c1;
       v = cross(p3 - p2, p1 - p2);
@@ -206,9 +206,9 @@
      *         * +1, if a is ordered after b around, rotating about direction.
      */
     inline int compareAngles(const Vector &direction, const Vector &base, const Vector &a, const Vector &b) {
-      double d1 = carve::geom3d::orient3d(carve::geom::VECTOR(0,0,0), direction, a, b);
-      double d2 = carve::geom3d::orient3d(carve::geom::VECTOR(0,0,0), direction, base, a);
-      double d3 = carve::geom3d::orient3d(carve::geom::VECTOR(0,0,0), direction, base, b);
+      const double d1 = carve::geom3d::orient3d(carve::geom::VECTOR(0,0,0), direction, a, b);
+      const double d2 = carve::geom3d::orient3d(carve::geom::VECTOR(0,0,0), direction, base, a);
+      const double d3 = carve::geom3d::orient3d(carve::geom::VECTOR(0,0,0), direction, base, b);
 
       // CASE: a and b are coplanar wrt. direction.
       if (d1 == 0.0) {
@@ -219,7 +219,6 @@
         }
 
         // a and b point in opposite directions.
-        double d2 = carve::geom3d::orient3d(carve::geom::VECTOR(0,0,0), direction, base, a);
         // * if d2 < 0.0, a is above plane(direction, base) and is less
         //   than b.
         // * if d2 == 0.0 a is coplanar with plane(direction, base) and is

Modified: branches/carve_booleans/extern/carve/include/carve/math.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/math.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/math.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -25,7 +25,7 @@
 
 namespace carve {
   namespace geom {
-    template<unsigned ndim> class vector;
+    template<unsigned ndim> struct vector;
   }
 }
 

Modified: branches/carve_booleans/extern/carve/include/carve/polyline_iter.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/polyline_iter.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/polyline_iter.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -51,7 +51,7 @@
 
 
 
-    static inline int operator-(const polyline_vertex_iter&a, const polyline_vertex_iter &b) { return a.idx - b.idx; }
+    static inline ptrdiff_t operator-(const polyline_vertex_iter &a, const polyline_vertex_iter &b) { return a.idx - b.idx; }
                 
     static inline bool operator==(const polyline_vertex_iter&a, const polyline_vertex_iter &b) { return a.idx == b.idx; }
     static inline bool operator!=(const polyline_vertex_iter&a, const polyline_vertex_iter &b) { return a.idx != b.idx; }
@@ -87,7 +87,7 @@
 
 
 
-    static inline int operator-(const polyline_vertex_const_iter&a, const polyline_vertex_const_iter &b) { return a.idx - b.idx; }
+    static inline ptrdiff_t operator-(const polyline_vertex_const_iter &a, const polyline_vertex_const_iter &b) { return a.idx - b.idx; }
                 
     static inline bool operator==(const polyline_vertex_const_iter&a, const polyline_vertex_const_iter &b) { return a.idx == b.idx; }
     static inline bool operator!=(const polyline_vertex_const_iter&a, const polyline_vertex_const_iter &b) { return a.idx != b.idx; }

Modified: branches/carve_booleans/extern/carve/include/carve/triangulator_impl.hpp
===================================================================
--- branches/carve_booleans/extern/carve/include/carve/triangulator_impl.hpp	2012-01-12 21:10:46 UTC (rev 43335)
+++ branches/carve_booleans/extern/carve/include/carve/triangulator_impl.hpp	2012-01-12 21:47:14 UTC (rev 43336)
@@ -513,6 +513,70 @@
           return fwd;
         }
       };
+
+
+
+      template<typename project_t, typename vert_t>
+      static bool
+      testCandidateAttachment(const project_t &project,
+                              std::vector<vert_t> &current_f_loop,
+                              size_t curr,
+                              carve::geom2d::P2 hole_min) {
+        const size_t SZ = current_f_loop.size();
+
+        size_t prev, next;
+
+        if (curr == 0) {
+          prev = SZ - 1; next = 1;
+        } else if (curr == SZ - 1) {
+          prev = curr - 1; next = 0;
+        } else {
+          prev = curr - 1; next = curr + 1;
+        }
+
+        if (!carve::geom2d::internalToAngle(project(current_f_loop[next]),
+                                            project(current_f_loop[curr]),
+                                            project(current_f_loop[prev]),
+                                            hole_min)) {
+          return false;
+        }
+
+        if (hole_min == project(current_f_loop[curr])) {
+          return true;
+        }
+
+        carve::geom2d::LineSegment2 test(hole_min, project(current_f_loop[curr]));
+
+        size_t v1 = current_f_loop.size() - 1;
+        size_t v2 = 0;
+        double v1_side = carve::geom2d::orient2d(test.v1, test.v2, project(current_f_loop[v1]));
+        double v2_side = 0;
+
+        while (v2 != current_f_loop.size()) {
+          v2_side = carve::geom2d::orient2d(test.v1, test.v2, project(current_f_loop[v2]));
+
+          if (v1_side != v2_side) {

@@ Diff output truncated at 10240 characters. @@


More information about the Bf-blender-cvs mailing list