[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [43760] trunk/blender/extern/carve: Fix #29993: Boolean modifier crashes Blender

Sergey Sharybin sergey.vfx at gmail.com
Mon Jan 30 09:45:19 CET 2012


Revision: 43760
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=43760
Author:   nazgul
Date:     2012-01-30 08:45:12 +0000 (Mon, 30 Jan 2012)
Log Message:
-----------
Fix #29993: Boolean modifier crashes Blender

Crash was caused by error in Carve triangulator. Fixed by upgrading Carve library.

Modified Paths:
--------------
    trunk/blender/extern/carve/bundle.sh
    trunk/blender/extern/carve/lib/intersect_face_division.cpp
    trunk/blender/extern/carve/lib/triangulator.cpp

Modified: trunk/blender/extern/carve/bundle.sh
===================================================================
--- trunk/blender/extern/carve/bundle.sh	2012-01-30 06:47:01 UTC (rev 43759)
+++ trunk/blender/extern/carve/bundle.sh	2012-01-30 08:45:12 UTC (rev 43760)
@@ -17,7 +17,7 @@
 rm -rf include
 rm -rf lib
 
-cat "files.txt" | while f=`line`; do
+cat "files.txt" | while read f; do
   mkdir -p `dirname $f`
   cp $tmp/carve/$f $f
 done

Modified: trunk/blender/extern/carve/lib/intersect_face_division.cpp
===================================================================
--- trunk/blender/extern/carve/lib/intersect_face_division.cpp	2012-01-30 06:47:01 UTC (rev 43759)
+++ trunk/blender/extern/carve/lib/intersect_face_division.cpp	2012-01-30 08:45:12 UTC (rev 43760)
@@ -48,6 +48,63 @@
 
 
 
+#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
+  template<typename iter_t>
+  void dumpFacesAndHoles(iter_t f_begin, iter_t f_end,
+                         iter_t h_begin, iter_t h_end,
+                         const std::string &fname) {
+    std::cerr << "dumping " << std::distance(f_begin, f_end) << " faces, " << std::distance(h_begin, h_end) << " holes." << std::endl;
+    std::map<carve::mesh::MeshSet<3>::vertex_t *, size_t> v_included;
+
+    for (iter_t i = f_begin; i != f_end; ++i) {
+      for (size_t j = 0; j < (*i).size(); ++j) {
+        if (v_included.find((*i)[j]) == v_included.end()) {
+          size_t &p = v_included[(*i)[j]];
+          p = v_included.size() - 1;
+        }
+      }
+    }
+
+    for (iter_t i = h_begin; i != h_end; ++i) {
+      for (size_t j = 0; j < (*i).size(); ++j) {
+        if (v_included.find((*i)[j]) == v_included.end()) {
+          size_t &p = v_included[(*i)[j]];
+          p = v_included.size() - 1;
+        }
+      }
+    }
+
+    carve::line::PolylineSet fh;
+    fh.vertices.resize(v_included.size());
+    for (std::map<carve::mesh::MeshSet<3>::vertex_t *, size_t>::const_iterator
+           i = v_included.begin(); i != v_included.end(); ++i) {
+      fh.vertices[(*i).second].v = (*i).first->v;
+    }
+
+    {
+      std::vector<size_t> connected;
+      for (iter_t i = f_begin; i != f_end; ++i) {
+        connected.clear();
+        for (size_t j = 0; j < (*i).size(); ++j) {
+          connected.push_back(v_included[(*i)[j]]);
+        }
+        fh.addPolyline(true, connected.begin(), connected.end());
+      }
+      for (iter_t i = h_begin; i != h_end; ++i) {
+        connected.clear();
+        for (size_t j = 0; j < (*i).size(); ++j) {
+          connected.push_back(v_included[(*i)[j]]);
+        }
+        fh.addPolyline(true, connected.begin(), connected.end());
+      }
+    }
+
+    ::writePLY(fname, &fh, true);
+  }
+#endif
+
+
+
   template<typename T>
   void populateVectorFromList(std::list<T> &l, std::vector<T> &v) {
     v.clear();
@@ -433,6 +490,7 @@
         face_loops_sorted[m].push_back(n);
       }
       face_loop_areas.push_back(carve::geom2d::signedArea(face_loops_projected[m]));
+
       std::sort(face_loops_sorted[m].begin(), face_loops_sorted[m].end(), 
                 carve::make_index_sort(face_loops[m].begin()));
       face_loop_aabb[m].fit(face_loops_projected[m].begin(), face_loops_projected[m].end());
@@ -449,6 +507,7 @@
         hole_loops_sorted[m].push_back(n);
       }
       hole_loop_areas.push_back(carve::geom2d::signedArea(hole_loops_projected[m]));
+
       std::sort(hole_loops_sorted[m].begin(), hole_loops_sorted[m].end(), 
                 carve::make_index_sort(hole_loops[m].begin()));
       hole_loop_aabb[m].fit(hole_loops_projected[m].begin(), hole_loops_projected[m].end());
@@ -572,6 +631,10 @@
     std::vector<std::vector<int> > containing_faces;
     std::map<int, std::map<int, std::pair<unsigned, unsigned> > > hole_shared_vertices;
 
+#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
+    dumpFacesAndHoles(f_loops.begin(), f_loops.end(), h_loops.begin(), h_loops.end(), "/tmp/pre_merge.ply");
+#endif
+
     {
       // move input face and hole loops to temp vectors.
       size_t m;
@@ -720,6 +783,10 @@
       }
     }
 #endif
+#if defined(CARVE_DEBUG_WRITE_PLY_DATA)
+    dumpFacesAndHoles(f_loops.begin(), f_loops.end(), h_loops.begin(), h_loops.end(), "/tmp/post_merge.ply");
+#endif
+
   }
 
 
@@ -738,7 +805,7 @@
    *            on that edge.
    * @param[out] base_loop A vector of the vertices of the base loop.
    */
-  static void assembleBaseLoop(carve::mesh::MeshSet<3>::face_t *face,
+  static bool assembleBaseLoop(carve::mesh::MeshSet<3>::face_t *face,
                                const carve::csg::detail::Data &data,
                                std::vector<carve::mesh::MeshSet<3>::vertex_t *> &base_loop) {
     base_loop.clear();
@@ -746,6 +813,7 @@
     // XXX: assumes that face->edges is in the same order as
     // face->vertices. (Which it is)
     carve::mesh::MeshSet<3>::edge_t *e = face->edge;
+    bool face_edge_intersected = false;
     do {
       base_loop.push_back(carve::csg::map_vertex(data.vmap, e->vert));
 
@@ -757,9 +825,13 @@
         for (size_t k = 0, ke = ev_vec.size(); k < ke;) {
           base_loop.push_back(ev_vec[k++]);
         }
+
+        face_edge_intersected = true;
       }
       e = e->next;
     } while (e != face->edge);
+
+    return face_edge_intersected;
   }
 
 
@@ -789,7 +861,6 @@
                             carve::csg::CSG::Hooks &hooks,
                             std::vector<carve::mesh::MeshSet<3>::vertex_t *> &base_loop,
                             std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &paths,
-                            std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &loops,
                             std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &face_loops_out) {
     const size_t N = base_loop.size();
     std::vector<crossing_data> endpoint_indices;
@@ -800,6 +871,7 @@
       endpoint_indices.push_back(crossing_data(&paths[i], N, N));
     }
 
+    // Step 1:
     // locate endpoints of paths on the base loop.
     for (size_t i = 0; i < N; ++i) {
       for (size_t j = 0; j < paths.size(); ++j) {
@@ -872,6 +944,7 @@
 #endif
 
 
+    // Step 2:
     // divide paths up into those that connect to the base loop in two
     // places (cross), and those that do not (noncross).
     std::vector<crossing_data> cross, noncross;
@@ -895,7 +968,6 @@
           double area = carve::geom2d::signedArea(endpoint_indices[i].path->begin() + 1,
                                                   endpoint_indices[i].path->end(),
                                                   carve::mesh::MeshSet<3>::face_t::projection_mapping(face->project));
-          std::cerr << "HITS THIS CODE - area=" << area << std::endl;
           if (area < 0) {
             // XXX: Create test case to check that this is the correct sign for the area.
             std::reverse(endpoint_indices[i].path->begin(), endpoint_indices[i].path->end());
@@ -917,6 +989,7 @@
       }
     }
 
+    // Step 3:
     // add a temporary crossing path that connects the beginning and the
     // end of the base loop. this stops us from needing special case
     // code to handle the left over loop after all the other crossing
@@ -931,10 +1004,12 @@
     std::cerr << "### crossing edge count (with sentinel): " << cross.size() << std::endl;
 #endif
 
+    // Step 4:
     // sort paths by increasing beginning point and decreasing ending point.
     std::sort(cross.begin(), cross.end());
     std::sort(noncross.begin(), noncross.end());
 
+    // Step 5:
     // divide up the base loop based upon crossing paths.
     std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > divided_base_loop;
     divided_base_loop.reserve(cross.size());
@@ -979,6 +1054,7 @@
       }
     }
 
+    // Step 6:
     for (size_t i = 0; i < cross.size(); ++i) {
 #if defined(CARVE_DEBUG)
       std::cerr << "### i=" << i << " working on edge: " << cross[i].edge_idx[0] << " - " << cross[i].edge_idx[1] << std::endl;
@@ -1060,7 +1136,8 @@
 #endif
     }
 
-    if (!noncross.size() && !loops.size()) {
+    if (!noncross.size()) {
+      // If there are no non-crossing paths then we're done.
       populateListFromVector(divided_base_loop, face_loops_out);
       return true;
     }
@@ -1113,16 +1190,6 @@
         }
       }
 
-      // for each loop, just test with any point.
-      for (size_t j = 0; j < loops.size(); ++j) {
-        test = face->project(loops[j].front()->v);
-
-        if (proj_aabb[i].intersects(test) &&
-            carve::geom2d::pointInPoly(proj[i], test).iclass != carve::POINT_OUT) {
-          inc.push_back(&loops[j]);
-        }
-      }
-
 #if defined(CARVE_DEBUG)
       std::cerr << "### divided base loop:" << i << " inc.size()=" << inc.size() << std::endl;
       std::cerr << "### inc = [";
@@ -1172,15 +1239,18 @@
   void composeEdgesIntoPaths(const carve::csg::V2Set &edges,
                              const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &extra_endpoints,
                              std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &paths,
+                             std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &cuts,
                              std::vector<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > &loops) {
     using namespace carve::csg;
 
     detail::VVSMap vertex_graph;
     detail::VSet endpoints;
+    detail::VSet cut_endpoints;
 
-    std::vector<carve::mesh::MeshSet<3>::vertex_t *> path;
+    typedef std::vector<carve::mesh::MeshSet<3>::vertex_t *> vvec_t;
+    vvec_t path;
 
-    std::list<std::vector<carve::mesh::MeshSet<3>::vertex_t *> > temp;
+    std::list<vvec_t> path_list, cut_list, loop_list;
 
     // build graph from edges.
     for (V2Set::const_iterator i = edges.begin(); i != edges.end(); ++i) {
@@ -1199,6 +1269,9 @@
         std::cerr << "###    endpoint: " << (*i).first << std::endl;
 #endif
         endpoints.insert((*i).first);
+        if ((*i).second.size() == 1) {
+          cut_endpoints.insert((*i).first);
+        }
       }
     }
 
@@ -1209,6 +1282,7 @@
         std::cerr << "###    extra endpoint: " << extra_endpoints[i] << std::endl;
 #endif
         endpoints.insert(extra_endpoints[i]);
+        cut_endpoints.erase(extra_endpoints[i]);
       }
     }
 
@@ -1252,11 +1326,19 @@
       }
       CARVE_ASSERT(endpoints.find(path.back()) != endpoints.end());
 
-      temp.push_back(path);
+      bool is_cut =

@@ Diff output truncated at 10240 characters. @@


More information about the Bf-blender-cvs mailing list