diff options
Diffstat (limited to 'extern')
| -rw-r--r-- | extern/carve/carve-capi.cc | 440 | ||||
| -rw-r--r-- | extern/carve/carve-util.cc | 149 | ||||
| -rw-r--r-- | extern/carve/carve-util.h | 135 | ||||
| -rw-r--r-- | extern/carve/include/carve/csg_triangulator.hpp | 1 |
4 files changed, 539 insertions, 186 deletions
diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc index 319a20129d1..ef7a95e578b 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) + { + + 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; - - 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); + int num_triangles = carve_triangulatePoly(import_data, + mesh_importer, + vertices, + verts_per_poly, + verts_of_poly, + axis_matrix, + &face_indices, + &triangles_storage); + + 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); + } + else { + orig_edge_index.first = CARVE_MESH_NONE; + orig_edge_index.second = -1; + } - 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(); - edgeIndexMap_put(&edge_origindex_map, v1, v2, orig_edge_index); - } + 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); } } diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc index b1943a6dd74..ac6dcbc1a94 100644 --- a/extern/carve/carve-util.cc +++ b/extern/carve/carve-util.cc @@ -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]); - - 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); + if (pushTriangle(verts_of_poly[0], + verts_of_poly[1], + verts_of_poly[2], + face_indices, + triangles_storage)) + { + num_triangles++; + } - 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++; + } } } diff --git a/extern/carve/carve-util.h b/extern/carve/carve-util.h index 07743de2d16..324c6ae5b47 100644 --- a/extern/carve/carve-util.h +++ b/extern/carve/carve-util.h @@ -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 diff --git a/extern/carve/include/carve/csg_triangulator.hpp b/extern/carve/include/carve/csg_triangulator.hpp index 5a40439271e..513f9a145b2 100644 --- a/extern/carve/include/carve/csg_triangulator.hpp +++ b/extern/carve/include/carve/csg_triangulator.hpp @@ -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); } |