blender
/
blender
128
396
Fork 568
Code Issues 6.2k Pull Requests 754 Projects 19 Wiki Activity

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.
This commit is contained in:
Sergey Sharybin 2014-03-04 20:01:58 +06:00
parent 58bd0e53f1
commit 34c7fd1a11
Notes: blender-bot 2023-02-14 11:05:05 +01:00 
Referenced by issue #38918, Boolean modifers crashes when using specific topology
4 changed files with 539 additions and 186 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

440
extern/carve/carve-capi.cc vendored
View File

@ -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)
{
MeshSet<3>::edge_t *cur_edge = cur_face->edge,
*forward_edge = face->edge,
*backward_edge = face->edge;
bool forward_matches = true, backward_matches = true;
for (int a = 0; a < cur_face->nEdges(); ++a) {
if (forward_edge->vert != cur_edge->vert) {
forward_matches = false;
if (backward_matches == false) {
break;
}
}
if (backward_edge->vert != cur_edge->vert) {
backward_matches = false;
if (forward_matches == false) {
break;
}
}
cur_edge = cur_edge->next;
forward_edge = forward_edge->next;
backward_edge = backward_edge->prev;
}
if (forward_matches || backward_matches) {
found = true;
break;
}
}
}
if (found) {
duplicated_faces.push_back(face);
}
else {
out_faces.push_back(face);
}
}
for (int i = 0; i < duplicated_faces.size(); ++i) {
delete duplicated_faces[i];
}
std::swap(faces, out_faces);
}
public:
virtual ~HoleResolver() {
}
virtual void processOutputFace(std::vector<MeshSet<3>::face_t *> &faces,
const MeshSet<3>::face_t *orig,
bool flipped) {
carve::csg::CarveHoleResolver::processOutputFace(faces, orig, flipped);
if (faces.size() > 1) {
removeDuplicatedFaces(faces);
}
}
};
} // namespace
CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
@ -348,8 +554,8 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
int num_tessellated_polys = 0;
std::vector<int> face_indices;
face_indices.reserve(num_loops);
mesh_descr->orig_loop_index_map.reserve(num_polys);
mesh_descr->orig_poly_index_map.reserve(num_polys);
TrianglesStorage triangles_storage;
for (int i = 0; i < num_polys; i++) {
int verts_per_poly =
mesh_importer->getNumPolyVerts(import_data, i);
@ -376,32 +582,35 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
verts_per_poly,
verts_of_poly,
&axis_matrix)) {
int num_triangles;
int num_triangles = carve_triangulatePoly(import_data,
mesh_importer,
vertices,
verts_per_poly,
verts_of_poly,
axis_matrix,
&face_indices,
&triangles_storage);
num_triangles = carve_triangulatePoly(import_data,
mesh_importer,
i,
loop_index,
vertices,
verts_per_poly,
verts_of_poly,
axis_matrix,
&face_indices,
&mesh_descr->orig_loop_index_map,
&mesh_descr->orig_poly_index_map);
for (int j = 0; j < num_triangles; ++j) {
mesh_descr->orig_poly_index_map.push_back(i);
}
num_tessellated_polys += num_triangles;
loop_index += verts_per_poly;
}
else {
face_indices.push_back(verts_per_poly);
for (int j = 0; j < verts_per_poly; ++j) {
mesh_descr->orig_loop_index_map.push_back(loop_index++);
face_indices.push_back(verts_of_poly[j]);
}
mesh_descr->orig_poly_index_map.push_back(i);
num_tessellated_polys++;
}
for (int j = 0; j < verts_per_poly; ++j) {
int v1 = verts_of_poly[j];
int v2 = verts_of_poly[(j + 1) % verts_per_poly];
edgeIndexMap_put(&mesh_descr->orig_loop_index_map, v1, v2, loop_index++);
}
}
if (verts_of_poly_dynamic != NULL) {
@ -471,7 +680,10 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
carve::csg::CSG csg;
csg.hooks.registerHook(new carve::csg::CarveHoleResolver,
csg.hooks.registerHook(new HoleResolver,
carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
csg.hooks.registerHook(new EarClipper,
carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
output_descr->orig_vert_mapping.installHooks(csg);
@ -504,10 +716,11 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
op,
NULL,
carve::csg::CSG::CLASSIFY_EDGE);
if (output_descr->poly) {
output_descr->poly->transform(rev_r);
dissolveTriangulatedEdges(output_descr);
//dissolveTriangulatedEdges(output_descr);
}
}
catch (carve::exception e) {
@ -522,33 +735,32 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
return output_descr->poly != NULL;
}
static void exportMesh_handle_edges_list(MeshSet<3> *poly,
const std::vector<MeshSet<3>::edge_t*> &edges,
int start_edge_index,
CarveMeshExporter *mesh_exporter,
struct ExportMeshData *export_data,
const std::unordered_map<VertexPair, OrigIndex> &edge_origindex_map,
std::unordered_map<VertexPair, int> *edge_map)
static int exportMesh_handle_edges_list(MeshSet<3> *poly,
const std::vector<MeshSet<3>::edge_t*> &edges,
int start_edge_index,
CarveMeshExporter *mesh_exporter,
struct ExportMeshData *export_data,
std::unordered_map<VertexPair, OrigIndex> &edge_origindex_map,
std::unordered_map<VertexPair, int> *edge_map)
{
int num_exported_edges = 0;
for (int i = 0, edge_index = start_edge_index;
i < edges.size();
++i, ++edge_index)
++i)
{
MeshSet<3>::edge_t *edge = edges.at(i);
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;
if (!edgeIndexMap_get_if_exists(edge_origindex_map,
v1,
v2,
&orig_edge_index))
{
orig_edge_index.first = CARVE_MESH_NONE;
orig_edge_index.second = -1;
if (edgeIndexMap_exists(*edge_map, v1, v2)) {
continue;
}
const OrigIndex &orig_edge_index = edgeIndexMap_get(edge_origindex_map,
v1,
v2);
mesh_exporter->setEdge(export_data,
edge_index,
indexOf(v1, poly->vertex_storage),
@ -557,7 +769,11 @@ static void exportMesh_handle_edges_list(MeshSet<3> *poly,
orig_edge_index.second);
edgeIndexMap_put(edge_map, v1, v2, edge_index);
++edge_index;
++num_exported_edges;
}
return num_exported_edges;
}
void carve_exportMesh(CarveMeshDescr *mesh_descr,
@ -569,28 +785,6 @@ void carve_exportMesh(CarveMeshDescr *mesh_descr,
int num_vertices = poly->vertex_storage.size();
int num_edges = 0, num_loops = 0, num_polys = 0;
// Count edges from all manifolds.
for (int i = 0; i < poly->meshes.size(); ++i) {
carve::mesh::Mesh<3> *mesh = poly->meshes[i];
num_edges += mesh->closed_edges.size() + mesh->open_edges.size();
}
// Count polys and loops from all manifolds.
for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
face_iter != poly->faceEnd();
++face_iter, ++num_polys)
{
MeshSet<3>::face_t *face = *face_iter;
num_loops += face->n_edges;
}
// Initialize arrays for geometry in exported mesh.
mesh_exporter->initGeomArrays(export_data,
num_vertices,
num_edges,
num_loops,
num_polys);
// Get mapping from edge denoted by vertex pair to original edge index,
//
// This is needed because internally Carve interpolates data for per-face
@ -613,23 +807,45 @@ void carve_exportMesh(CarveMeshDescr *mesh_descr,
edge_iter_index,
origindex_none);
if (orig_loop_index.first != CARVE_MESH_NONE) {
OrigIndex orig_edge_index;
OrigIndex orig_edge_index;
if (orig_loop_index.first != CARVE_MESH_NONE) {
orig_edge_index.first = orig_loop_index.first;
orig_edge_index.second =
mesh_exporter->mapLoopToEdge(export_data,
orig_loop_index.first,
orig_loop_index.second);
MeshSet<3>::vertex_t *v1 = edge.vert;
MeshSet<3>::vertex_t *v2 = edge.next->vert;
edgeIndexMap_put(&edge_origindex_map, v1, v2, orig_edge_index);
}
else {
orig_edge_index.first = CARVE_MESH_NONE;
orig_edge_index.second = -1;
}
MeshSet<3>::vertex_t *v1 = edge.v1();
MeshSet<3>::vertex_t *v2 = edge.v2();
edgeIndexMap_put(&edge_origindex_map, v1, v2, orig_edge_index);
}
}
num_edges = edge_origindex_map.size();
// Count polys and loops from all manifolds.
for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
face_iter != poly->faceEnd();
++face_iter, ++num_polys)
{
MeshSet<3>::face_t *face = *face_iter;
num_loops += face->nEdges();
}
// Initialize arrays for geometry in exported mesh.
mesh_exporter->initGeomArrays(export_data,
num_vertices,
num_edges,
num_loops,
num_polys);
// Export all the vertices.
std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter = poly->vertex_storage.begin();
for (int i = 0; vertex_iter != poly->vertex_storage.end(); ++i, ++vertex_iter) {
@ -652,24 +868,22 @@ void carve_exportMesh(CarveMeshDescr *mesh_descr,
for (int i = 0, edge_index = 0; i < poly->meshes.size(); ++i) {
carve::mesh::Mesh<3> *mesh = poly->meshes[i];
// Export closed edges.
exportMesh_handle_edges_list(poly,
mesh->closed_edges,
edge_index,
mesh_exporter,
export_data,
edge_origindex_map,
&edge_map);
edge_index += mesh->closed_edges.size();
edge_index += exportMesh_handle_edges_list(poly,
mesh->closed_edges,
edge_index,
mesh_exporter,
export_data,
edge_origindex_map,
&edge_map);
// Export open edges.
exportMesh_handle_edges_list(poly,
mesh->open_edges,
edge_index,
mesh_exporter,
export_data,
edge_origindex_map,
&edge_map);
edge_index += mesh->open_edges.size();
edge_index += exportMesh_handle_edges_list(poly,
mesh->open_edges,
edge_index,
mesh_exporter,
export_data,
edge_origindex_map,
&edge_map);
}
// Export all the loops and polys.
@ -694,15 +908,15 @@ void carve_exportMesh(CarveMeshDescr *mesh_descr,
origindex_none);
mesh_exporter->setLoop(export_data,
loop_index,
indexOf(edge.vert, poly->vertex_storage),
edgeIndexMap_get(edge_map, edge.vert, edge.next->vert),
orig_loop_index.first,
orig_loop_index.second);
loop_index,
indexOf(edge.vert, poly->vertex_storage),
edgeIndexMap_get(edge_map, edge.v1(), edge.v2()),
orig_loop_index.first,
orig_loop_index.second);
}
mesh_exporter->setPoly(export_data,
poly_index, start_loop_index, face->n_edges,
poly_index, start_loop_index, face->nEdges(),
orig_face_index.first, orig_face_index.second);
}
}

149
extern/carve/carve-util.cc vendored
View File

@ -39,6 +39,7 @@ using carve::geom3d::Vector;
using carve::math::Matrix3;
using carve::mesh::Face;
using carve::mesh::MeshSet;
using carve::triangulate::tri_idx;
using carve::triangulate::triangulate;
typedef std::map< MeshSet<3>::mesh_t*, RTreeNode<3, Face<3> *> * > RTreeCache;
@ -607,7 +608,7 @@ int triangulateNGon_carveTriangulator(const std::vector<Vector> &vertices,
const int verts_per_poly,
const int *verts_of_poly,
const Matrix3 &axis_matrix,
std::vector<carve::triangulate::tri_idx> *triangles)
std::vector<tri_idx> *triangles)
{
// Project vertices to 2D plane.
Vector projected;
@ -630,7 +631,7 @@ int triangulateNGon_importerTriangulator(struct ImportMeshData *import_data,
const int verts_per_poly,
const int *verts_of_poly,
const Matrix3 &axis_matrix,
std::vector<carve::triangulate::tri_idx> *triangles)
std::vector<tri_idx> *triangles)
{
typedef float Vector2D[2];
typedef unsigned int Triangle[3];
@ -653,10 +654,9 @@ int triangulateNGon_importerTriangulator(struct ImportMeshData *import_data,
triangles->reserve(num_triangles);
for (int i = 0; i < num_triangles; ++i) {
triangles->push_back(
carve::triangulate::tri_idx(api_triangles[i][0],
api_triangles[i][1],
api_triangles[i][2]));
triangles->push_back(tri_idx(api_triangles[i][0],
api_triangles[i][1],
api_triangles[i][2]));
}
delete [] poly_2d;
@ -665,19 +665,52 @@ int triangulateNGon_importerTriangulator(struct ImportMeshData *import_data,
return num_triangles;
}
template <typename T>
void sortThreeNumbers(T &a, T &b, T &c)
{
if (a > b)
std::swap(a, b);
if (b > c)
std::swap(b, c);
if (a > b)
std::swap(a, b);
}
bool pushTriangle(int v1, int v2, int v3,
std::vector<int> *face_indices,
TrianglesStorage *triangles_storage)
{
tri_idx triangle(v1, v2, v3);
sortThreeNumbers(triangle.a, triangle.b, triangle.c);
assert(triangle.a < triangle.b);
assert(triangle.b < triangle.c);
if (triangles_storage->find(triangle) == triangles_storage->end()) {
face_indices->push_back(3);
face_indices->push_back(v1);
face_indices->push_back(v2);
face_indices->push_back(v3);
triangles_storage->insert(triangle);
return true;
}
else {
return false;
}
}
} // namespace
int carve_triangulatePoly(struct ImportMeshData *import_data,
CarveMeshImporter *mesh_importer,
int poly_index,
int start_loop_index,
const std::vector<Vector> &vertices,
const int verts_per_poly,
const int *verts_of_poly,
const Matrix3 &axis_matrix,
std::vector<int> *face_indices,
std::vector<int> *orig_loop_index_map,
std::vector<int> *orig_poly_index_map)
TrianglesStorage *triangles_storage)
{
int num_triangles = 0;
@ -690,51 +723,45 @@ int carve_triangulatePoly(struct ImportMeshData *import_data,
// TODO(sergey): Consider using shortest diagonal here. However
// display code in Blende use static 1-3 split, so some experiments
// are needed here.
face_indices->push_back(3);
face_indices->push_back(verts_of_poly[0]);
face_indices->push_back(verts_of_poly[1]);
face_indices->push_back(verts_of_poly[2]);
if (pushTriangle(verts_of_poly[0],
verts_of_poly[1],
verts_of_poly[2],
face_indices,
triangles_storage))
{
num_triangles++;
}
orig_loop_index_map->push_back(start_loop_index);
orig_loop_index_map->push_back(start_loop_index + 1);
orig_loop_index_map->push_back(-1);
orig_poly_index_map->push_back(poly_index);
face_indices->push_back(3);
face_indices->push_back(verts_of_poly[0]);
face_indices->push_back(verts_of_poly[2]);
face_indices->push_back(verts_of_poly[3]);
orig_loop_index_map->push_back(-1);
orig_loop_index_map->push_back(start_loop_index + 2);
orig_loop_index_map->push_back(start_loop_index + 3);
orig_poly_index_map->push_back(poly_index);
num_triangles = 2;
if (pushTriangle(verts_of_poly[0],
verts_of_poly[2],
verts_of_poly[3],
face_indices,
triangles_storage))
{
num_triangles++;
}
}
else {
std::vector<carve::triangulate::tri_idx> triangles;
std::vector<tri_idx> triangles;
triangles.reserve(verts_per_poly - 2);
// Make triangulator callback optional so we could do some tests
// in the future.
if (mesh_importer->triangulate2DPoly) {
num_triangles =
triangulateNGon_importerTriangulator(import_data,
mesh_importer,
vertices,
verts_per_poly,
verts_of_poly,
axis_matrix,
&triangles);
triangulateNGon_importerTriangulator(import_data,
mesh_importer,
vertices,
verts_per_poly,
verts_of_poly,
axis_matrix,
&triangles);
}
else {
num_triangles =
triangulateNGon_carveTriangulator(vertices,
verts_per_poly,
verts_of_poly,
axis_matrix,
&triangles);
triangulateNGon_carveTriangulator(vertices,
verts_per_poly,
verts_of_poly,
axis_matrix,
&triangles);
}
for (int i = 0; i < triangles.size(); ++i) {
@ -750,30 +777,14 @@ int carve_triangulatePoly(struct ImportMeshData *import_data,
assert(v2 < verts_per_poly);
assert(v3 < verts_per_poly);
face_indices->push_back(3);
face_indices->push_back(verts_of_poly[v1]);
face_indices->push_back(verts_of_poly[v2]);
face_indices->push_back(verts_of_poly[v3]);
#define CHECK_TRIANGLE_LOOP_INDEX(v1, v2) \
{ \
int v1_ = std::min(v1, v2), \
v2_ = std::max(v1, v2); \
if (v1_ + 1 == v2_ || v1_ + verts_per_poly == v2_ + 1) { \
orig_loop_index_map->push_back(start_loop_index + v1); \
} \
else { \
orig_loop_index_map->push_back(-1); \
} \
} (void) 0
CHECK_TRIANGLE_LOOP_INDEX(v1, v2);
CHECK_TRIANGLE_LOOP_INDEX(v2, v3);
CHECK_TRIANGLE_LOOP_INDEX(v3, v1);
#undef CHECK_TRIANGLE_LOOP_INDEX
orig_poly_index_map->push_back(poly_index);
if (pushTriangle(verts_of_poly[v1],
verts_of_poly[v2],
verts_of_poly[v3],
face_indices,
triangles_storage))
{
num_triangles++;
}
}
}

135
extern/carve/carve-util.h vendored
View File

@ -31,9 +31,40 @@
#include <carve/geom3d.hpp>
#include <carve/interpolator.hpp>
#include <carve/mesh.hpp>
#include <carve/triangulator.hpp>
#include "carve-capi.h"
struct TriIdxCompare {
bool operator() (const carve::triangulate::tri_idx &left,
const carve::triangulate::tri_idx &right) {
if (left.a < right.a) {
return true;
}
else if (left.a > right.a) {
return false;
}
if (left.b < right.b) {
return true;
}
else if (left.b > right.b) {
return false;
}
if (left.c < right.c) {
return true;
}
else if (left.c > right.c) {
return false;
}
return false;
}
};
typedef std::set<carve::triangulate::tri_idx, TriIdxCompare> TrianglesStorage;
void carve_getRescaleMinMax(const carve::mesh::MeshSet<3> *left,
const carve::mesh::MeshSet<3> *right,
carve::geom3d::Vector *min,
@ -50,15 +81,12 @@ bool carve_checkPolyPlanarAndGetNormal(const std::vector<carve::geom3d::Vector>
int carve_triangulatePoly(struct ImportMeshData *import_data,
CarveMeshImporter *mesh_importer,
int poly_index,
int start_loop_index,
const std::vector<carve::geom3d::Vector> &vertices,
const int verts_per_poly,
const int *verts_of_poly,
const carve::math::Matrix3 &axis_matrix,
std::vector<int> *face_indices,
std::vector<int> *orig_loop_index_map,
std::vector<int> *orig_poly_index_map);
TrianglesStorage *triangles_storage);
namespace carve {
namespace interpolate {
@ -116,6 +144,105 @@ namespace carve {
}
};
template<typename attr_t>
class SimpleFaceEdgeAttr : public Interpolator {
public:
typedef std::pair<const meshset_t::face_t *, unsigned> key_t;
protected:
typedef std::pair<const meshset_t::vertex_t *, const meshset_t::vertex_t *> vpair_t;
struct key_hash {
size_t operator()(const key_t &v) const {
return size_t(v.first) ^ size_t(v.second);
}
};
struct vpair_hash {
size_t operator()(const vpair_t &v) const {
return size_t(v.first) ^ size_t(v.second);
}
};
typedef std::unordered_map<key_t, attr_t, key_hash> attrmap_t;
typedef std::unordered_map<vpair_t, key_t, vpair_hash> edgedivmap_t;
attrmap_t attrs;
struct Hook : public Interpolator::Hook {
public:
virtual unsigned hookBits() const {
return carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT;
}
Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : Interpolator::Hook(_interpolator, _csg) {
}
virtual ~Hook() {
}
};
virtual Interpolator::Hook *makeHook(carve::csg::CSG &csg) {
return new Hook(this, csg);
}
virtual void processOutputFace(const carve::csg::CSG &csg,
std::vector<carve::mesh::MeshSet<3>::face_t *> &new_faces,
const meshset_t::face_t *orig_face,
bool flipped) {
edgedivmap_t undiv;
for (meshset_t::face_t::const_edge_iter_t e = orig_face->begin(); e != orig_face->end(); ++e) {
key_t k(orig_face, e.idx());
typename attrmap_t::const_iterator attr_i = attrs.find(k);
if (attr_i == attrs.end()) {
continue;
} else {
undiv[vpair_t(e->v1(), e->v2())] = k;
}
}
for (size_t fnum = 0; fnum < new_faces.size(); ++fnum) {
const carve::mesh::MeshSet<3>::face_t *new_face = new_faces[fnum];
for (meshset_t::face_t::const_edge_iter_t e = new_face->begin(); e != new_face->end(); ++e) {
key_t k(new_face, e.idx());
vpair_t vp;
if (!flipped) {
vp = vpair_t(e->v1(), e->v2());
} else {
vp = vpair_t(e->v2(), e->v1());
}
typename edgedivmap_t::const_iterator vp_i;
if ((vp_i = undiv.find(vp)) != undiv.end()) {
attrs[k] = attrs[vp_i->second];
}
}
}
}
public:
bool hasAttribute(const meshset_t::face_t *f, unsigned e) {
return attrs.find(std::make_pair(f, e)) != attrs.end();
}
attr_t getAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &def = attr_t()) {
typename attrmap_t::const_iterator fv = attrs.find(std::make_pair(f, e));
if (fv != attrs.end()) {
return (*fv).second;
}
return def;
}
void setAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &attr) {
attrs[std::make_pair(f, e)] = attr;
}
SimpleFaceEdgeAttr() : Interpolator() {
}
virtual ~SimpleFaceEdgeAttr() {
}
};
} // namespace interpolate
} // namespace carve

1
extern/carve/include/carve/csg_triangulator.hpp vendored
View File

@ -426,6 +426,7 @@ namespace carve {
findPerimeter(grp_tris, vloop, grp_perim);
out_faces.push_back(face->create(grp_perim.begin(), grp_perim.end(), false));
}
delete face;
}
std::swap(faces, out_faces);
}