diff options
Diffstat (limited to 'extern/carve/carve-capi.cc')
| -rw-r--r-- | extern/carve/carve-capi.cc | 440 |
1 files changed, 327 insertions, 113 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); } } |