[Bf-blender-cvs] [34c7fd1] master: Fix T38918: Boolean modifier crashes when using specific topology
Sergey Sharybin
noreply at git.blender.org
Tue Mar 4 15:18:44 CET 2014
Commit: 34c7fd1a1120aee8e367bfe7336ca78e2b3e5f8b
Author: Sergey Sharybin
Date: Tue Mar 4 20:01:58 2014 +0600
https://developer.blender.org/rB34c7fd1a1120aee8e367bfe7336ca78e2b3e5f8b
Fix T38918: Boolean modifier crashes when using specific topology
There were loads of issues in the code still which are mow likely fixed:
- Hole resolver hook had memory leak -- it didn't free face with holes
when triangulating it.
- Original edge mapping didn't work correct. old code related on the fact
that loop order is not changing when constructing the MeshSet class, but
in fact it does change.
Currently used edge map for this because it was easiest way to do it now,
but after the release we're to change it. Main reason is that face mapping
is not correct as well (and it was never correct actually). So we'll need
to construct Mesh structures by our own to be sure we're using correct
original index mapping.
- Carve might produce faces with ears, which is forbidden in Blender.
it wasn't an issue in old integration because triangulation will remove
the ears. So for now simply added ears removing back as a hook.
But actual reason of the ears is to be investigated really.
This hook will only work for NGons, quads are assumed not be able to
have ears. So this additional hook shouldn't slow down things much.
- Carve's hole resolver produces duplicated faces in some cases. Still not
sure what is the reason of this. Code here is not so much straightforward,
this is to be investigated later.
For now solved the issue as own hole resolver which checks for duplicated
faces after the hole resolving.
The additional checks here will only run if the mesh actually have hole
and wouldn't introduce slowdown for faces which doesn't have holes.
- Made it so if edge user triangulation gets a split (for example, in cases
when this edge intersects with the second operand) it wouldn't be dissolved.
This prevents cases of crappy topology after dissolving in several cases.
- Edge dissolver didn't check for whether edge is a non-manifold. We couldn't
really dissolve open manifold edges.
The bad thing about this is that mesh triangulation might produce non-manifold
edges and they wouldn't be dissolved. Not worst case in the world, but would
be nice to have it solved somehow.
- Exporting mesh form Carve to Blender might have produced duplicated edges
in cases when several non-manifold faces shared the edge. This is also fixed
now.
- Mesh triangulation might have produced duplicated faces, which is really bad.
Fixed by keeping a track on which faces we've created and skipping adding new
triangle if we already have one.
This all might introduce some slowdown, but we're too close to the release now,
so would rather have it slower but robust. After the release we might look into
ways to speed things up.
===================================================================
M extern/carve/carve-capi.cc
M extern/carve/carve-util.cc
M extern/carve/carve-util.h
M extern/carve/include/carve/csg_triangulator.hpp
===================================================================
diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc
index 319a201..ef7a95e 100644
--- a/extern/carve/carve-capi.cc
+++ b/extern/carve/carve-capi.cc
@@ -39,14 +39,14 @@ typedef std::pair<MeshSet<3>::vertex_t *, MeshSet<3>::vertex_t *> VertexPair;
typedef carve::interpolate::VertexAttr<OrigIndex> OrigVertMapping;
typedef carve::interpolate::FaceAttr<OrigIndex> OrigFaceMapping;
typedef carve::interpolate::FaceEdgeAttr<OrigIndex> OrigFaceEdgeMapping;
-typedef carve::interpolate::FaceEdgeAttr<bool> FaceEdgeTriangulatedFlag;
+typedef carve::interpolate::SimpleFaceEdgeAttr<bool> FaceEdgeTriangulatedFlag;
typedef struct CarveMeshDescr {
// Stores mesh data itself.
MeshSet<3> *poly;
// N-th element of the vector indicates index of an original mesh loop.
- std::vector<int> orig_loop_index_map;
+ std::unordered_map<std::pair<int, int>, int> orig_loop_index_map;
// N-th element of the vector indicates index of an original mesh poly.
std::vector<int> orig_poly_index_map;
@@ -123,6 +123,24 @@ bool edgeIndexMap_get_if_exists(const std::unordered_map<std::pair<T1, T1>, T2>
return true;
}
+template <typename T1, typename T2>
+bool edgeIndexMap_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
+ const T1 &v1,
+ const T1 &v2)
+{
+ typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
+ typename Map::const_iterator found;
+
+ if (v1 < v2) {
+ found = edge_map.find(std::make_pair(v1, v2));
+ }
+ else {
+ found = edge_map.find(std::make_pair(v2, v1));
+ }
+
+ return found != edge_map.end();
+}
+
template <typename T>
inline int indexOf(const T *element, const std::vector<T> &vector_from)
{
@@ -131,7 +149,7 @@ inline int indexOf(const T *element, const std::vector<T> &vector_from)
void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
int which_mesh,
- const std::vector<int> &orig_loop_index_map,
+ std::unordered_map<std::pair<int, int>, int> &orig_loop_index_map,
const std::vector<int> &orig_poly_index_map,
OrigVertMapping *orig_vert_mapping,
OrigFaceEdgeMapping *orig_face_edge_mapping,
@@ -166,7 +184,17 @@ void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
edge_iter != face->end();
++edge_iter, ++loop_map_index)
{
- int orig_loop_index = orig_loop_index_map[loop_map_index];
+ int v1 = indexOf(edge_iter->v1(), poly->vertex_storage);
+ int v2 = indexOf(edge_iter->v2(), poly->vertex_storage);
+
+ int orig_loop_index;
+ if (!edgeIndexMap_get_if_exists(orig_loop_index_map,
+ v1, v2,
+ &orig_loop_index))
+ {
+ orig_loop_index = -1;
+ }
+
if (orig_loop_index != -1) {
// Mapping from carve face edge back to original loop index.
orig_face_edge_mapping->setAttribute(face,
@@ -175,7 +203,9 @@ void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
orig_loop_index));
}
else {
- face_edge_triangulated_flag->setAttribute(face, edge_iter.idx(), true);
+ face_edge_triangulated_flag->setAttribute(face,
+ edge_iter.idx(),
+ true);
}
}
}
@@ -215,11 +245,11 @@ void origEdgeMappingForFace(MeshSet<3>::face_t *face,
MeshSet<3>::edge_t *edge = face->edge;
for (int i = 0;
- i < face->n_edges;
+ i < face->nEdges();
++i, edge = edge->next)
{
- MeshSet<3>::vertex_t *v1 = edge->vert;
- MeshSet<3>::vertex_t *v2 = edge->next->vert;
+ MeshSet<3>::vertex_t *v1 = edge->v1();
+ MeshSet<3>::vertex_t *v2 = edge->v2();
OrigIndex orig_edge_index =
orig_face_edge_mapping->getAttribute(edge->face, i, origindex_none);
@@ -229,27 +259,43 @@ void origEdgeMappingForFace(MeshSet<3>::face_t *face,
}
void dissolveTriangulatedEdges(MeshSet<3>::mesh_t *mesh,
- OrigFaceEdgeMapping *orig_face_edge_mapping,
- FaceEdgeTriangulatedFlag *face_edge_triangulated_flag)
+ const std::set< std::pair<int, int> > &open_edges,
+ FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
+ OrigFaceEdgeMapping *orig_face_edge_mapping)
{
typedef std::unordered_set<MeshSet<3>::edge_t *> edge_set_t;
typedef std::unordered_set<MeshSet<3>::face_t *> face_set_t;
edge_set_t triangulated_face_edges;
- for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
+ for (int face_index = 0; face_index < mesh->faces.size(); ++face_index) {
MeshSet<3>::face_t *face = mesh->faces[face_index];
MeshSet<3>::edge_t *edge = face->edge;
for (int edge_index = 0;
- edge_index < face->n_edges;
+ edge_index < face->nEdges();
++edge_index, edge = edge->next)
{
- const bool is_triangulated_edge =
- face_edge_triangulated_flag->getAttribute(face,
- edge_index,
- false);
- if (is_triangulated_edge) {
- MeshSet<3>::edge_t *e1 = std::min(edge, edge->rev);
- triangulated_face_edges.insert(e1);
+ if (edge->rev) {
+ const bool is_triangulated_edge =
+ face_edge_triangulated_flag->getAttribute(face,
+ edge_index,
+ false);
+ if (is_triangulated_edge) {
+ MeshSet<3>::edge_t *e1 = std::min(edge, edge->rev);
+ int v1 = indexOf(e1->v1(), mesh->meshset->vertex_storage),
+ v2 = indexOf(e1->v2(), mesh->meshset->vertex_storage);
+
+ bool is_open = false;
+ if (v1 < v2) {
+ is_open = open_edges.find(std::make_pair(v1, v2)) != open_edges.end();
+ }
+ else {
+ is_open = open_edges.find(std::make_pair(v2, v1)) != open_edges.end();
+ }
+
+ if (is_open == false) {
+ triangulated_face_edges.insert(e1);
+ }
+ }
}
}
}
@@ -284,11 +330,11 @@ void dissolveTriangulatedEdges(MeshSet<3>::mesh_t *mesh,
if (triangulated_faces.find(face) != triangulated_faces.end()) {
MeshSet<3>::edge_t *edge = face->edge;
for (int edge_index = 0;
- edge_index < face->n_edges;
+ edge_index < face->nEdges();
++edge_index, edge = edge->next)
{
- MeshSet<3>::vertex_t *v1 = edge->vert;
- MeshSet<3>::vertex_t *v2 = edge->next->vert;
+ MeshSet<3>::vertex_t *v1 = edge->v1();
+ MeshSet<3>::vertex_t *v2 = edge->v2();
OrigIndex orig_edge_index =
edgeIndexMap_get(edge_origindex_map,
@@ -308,14 +354,174 @@ void dissolveTriangulatedEdges(CarveMeshDescr *mesh_descr)
FaceEdgeTriangulatedFlag *face_edge_triangulated_flag =
&mesh_descr->face_edge_triangulated_flag;
- for (int i = 0; i < poly->meshes.size(); ++i) {
- MeshSet<3>::mesh_t *mesh = poly->meshes[i];
+ std::set< std::pair<int, int> > open_edges;
+ for (int mesh_index = 0;
+ mesh_index < poly->meshes.size();
+ ++mesh_index)
+ {
+ const MeshSet<3>::mesh_t *mesh = poly->meshes[mesh_index];
+ for (int edge_index = 0;
+ edge_index < mesh->open_edges.size();
+ ++edge_index)
+ {
+ const MeshSet<3>::edge_t *edge = mesh->open_edges[edge_index];
+ int v1 = indexOf(edge->v1(), poly->vertex_storage),
+ v2 = indexOf(edge->v2(), poly->vertex_storage);
+ if (v1 < v2) {
+ open_edges.insert(std::make_pair(v1, v2));
+ }
+ else {
+ open_edges.insert(std::make_pair(v2, v1));
+ }
+ }
+ }
+
+ for (int mesh_index = 0; mesh_index < poly->meshes.size(); ++mesh_index) {
+ MeshSet<3>::mesh_t *mesh = poly->meshes[mesh_index];
dissolveTriangulatedEdges(mesh,
- &mesh_descr->orig_face_edge_mapping,
- face_edge_triangulated_flag);
+ open_edges,
+ face_edge_triangulated_flag,
+ &mesh_descr->orig_face_edge_mapping);
+ }
+}
+
+void clipEar(MeshSet<3>::edge_t *ear)
+{
+ MeshSet<3>::edge_t *p_edge = ear->prev;
+ MeshSet<3>::edge_t *n_edge = ear->next;
+
+ p_edge->next = n_edge;
+ n_edge->prev = p_edge;
+
+ if (ear->face->edge == ear) {
+ ear->face->edge = n_edge;
+ }
+ ear->face->n_edges--;
+
+ delete ear;
+}
+
+MeshSet<3>::edge_t *findDegenerateEar(MeshSet<3>::face_t *face)
+{
+ for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
+ edge_iter != face->end();
+ ++edge_iter)
+ {
+ MeshSet<3>::edge_t &edge = *edge_iter;
+ if (edge.vert == edge.next->next->vert) {
+ return edge.next->next;
+ }
}
+ return NULL;
}
+class EarClipper : public carve::csg::CSG::Hook {
+public:
+ virtual ~EarClipper() {
+ }
+
+ virtual void processOutputFace(std::vector<MeshSet<3>::face_t *> &faces,
+ const MeshSet<3>::face_t *orig,
+ bool flipped) {
+ for (size_t face_index = 0; face_index < faces.size(); ++face_index) {
+ carve::mesh::MeshSet<3>::face_t *face = faces[face_index];
+
+ // There's no ears in quads and tris.
+ if (face->nVertices() <= 4) {
+ continue;
+ }
+
+ MeshSet<3>::edge_t *ear;
+ while ((ear = findDegenerateEar(face)) != NULL) {
+ clipEar(ear);
+ }
+
+ }
+ }
+};
+
+class HoleResolver : public carve::csg::CarveHoleResolver {
+
+ void removeDuplicatedFaces(std::vector<MeshSet<3>::face_t *> &faces) {
+ std::vector<MeshSet<3>::face_t *> out_faces;
+ std::vector<MeshSet<3>::face_t *> duplicated_faces;
+
+ for (size_t face_index = 0; face_index < faces.size(); ++face_index) {
+ carve::mesh::MeshSet<3>::face_t *face = faces[face_index];
+ face->canonicalize();
+ }
+
+ for (size_t i = 0; i < faces.size(); ++i) {
+ carve::mesh::MeshSet<3>::face_t *face = faces[i];
+
+ bool found = false;
+ for (size_t j = i + 1; j < faces.size() && found == false; ++j) {
+ MeshSet<3>::face_t *cur_face = faces[j];
+ if (cur_face->nEdges() == face->nEdges() &&
+ cur_face->edge->vert == face->edge->vert)
+ {
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list