[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