diff options
32 files changed, 2253 insertions, 4308 deletions
diff --git a/extern/carve/CMakeLists.txt b/extern/carve/CMakeLists.txt index 5e917ac1e44..11a92f92abc 100644 --- a/extern/carve/CMakeLists.txt +++ b/extern/carve/CMakeLists.txt @@ -35,6 +35,8 @@ set(INC_SYS ) set(SRC + carve-capi.cc + carve-util.cc lib/aabb.cpp lib/carve.cpp lib/convex_hull.cpp @@ -62,6 +64,8 @@ set(SRC lib/timing.cpp lib/triangulator.cpp + carve-capi.h + carve-util.h lib/csg_collector.hpp lib/csg_data.hpp lib/csg_detail.hpp diff --git a/extern/carve/bundle.sh b/extern/carve/bundle.sh index 05967d6131d..91d5f44a880 100755 --- a/extern/carve/bundle.sh +++ b/extern/carve/bundle.sh @@ -70,8 +70,12 @@ set(INC_SYS ) set(SRC + carve-capi.cc + carve-util.cc ${sources} + carve-capi.h + carve-util.h ${headers} ${includes} diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc new file mode 100644 index 00000000000..7478c341663 --- /dev/null +++ b/extern/carve/carve-capi.cc @@ -0,0 +1,580 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2014 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Blender Foundation, + * Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "carve-capi.h" +#include "carve-util.h" + +#include <carve/interpolator.hpp> +#include <carve/rescale.hpp> + +using carve::mesh::MeshSet; + +typedef std::pair<int, int> OrigIndex; +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 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; + + // N-th element of the vector indicates index of an original mesh poly. + std::vector<int> orig_poly_index_map; + + // The folloving mapping is only filled in for output mesh. + + // Mapping from the face verts back to original vert index. + OrigVertMapping orig_vert_mapping; + + // Mapping from the face edges back to (original edge index, original loop index). + OrigFaceEdgeMapping orig_face_edge_mapping; + + // Mapping from the faces back to original poly index. + OrigFaceMapping orig_face_mapping; +} CarveMeshDescr; + +namespace { + +template <typename T1, typename T2> +void edgeIndexMap_put(std::unordered_map<std::pair<T1, T1>, T2> *edge_map, + const T1 &v1, + const T1 &v2, + const T2 &index) +{ + if (v1 < v2) { + (*edge_map)[std::make_pair(v1, v2)] = index; + } + else { + (*edge_map)[std::make_pair(v2, v1)] = index; + } +} + +template <typename T1, typename T2> +const T2 &edgeIndexMap_get(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)); + } + + assert(found != edge_map.end()); + return found->second; +} + +template <typename T1, typename T2> +bool edgeIndexMap_get_if_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map, + const T1 &v1, + const T1 &v2, + T2 *out) +{ + 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)); + } + + if (found == edge_map.end()) { + return false; + } + *out = found->second; + return true; +} + +template <typename T> +inline int indexOf(const T *element, const std::vector<T> &vector_from) +{ + return element - &vector_from.at(0); +} + +void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh, + int which_mesh, + const std::vector<int> &orig_loop_index_map, + const std::vector<int> &orig_poly_index_map, + OrigVertMapping *orig_vert_mapping, + OrigFaceEdgeMapping *orig_face_edge_mapping, + OrigFaceMapping *orig_face_attr) +{ + MeshSet<3> *poly = mesh->poly; + + 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) + { + MeshSet<3>::vertex_t *vertex = &(*vertex_iter); + orig_vert_mapping->setAttribute(vertex, + std::make_pair(which_mesh, i)); + } + + MeshSet<3>::face_iter face_iter = poly->faceBegin(); + for (int i = 0, loop_map_index = 0; + face_iter != poly->faceEnd(); + ++face_iter, ++i) + { + const MeshSet<3>::face_t *face = *face_iter; + + // Mapping from carve face back to original poly index. + int orig_poly_index = orig_poly_index_map[i]; + orig_face_attr->setAttribute(face, std::make_pair(which_mesh, orig_poly_index)); + + for (MeshSet<3>::face_t::const_edge_iter_t edge_iter = face->begin(); + edge_iter != face->end(); + ++edge_iter, ++loop_map_index) + { + int orig_loop_index = orig_loop_index_map[loop_map_index]; + if (orig_loop_index != -1) { + // Mapping from carve face edge back to original loop index. + orig_face_edge_mapping->setAttribute(face, + edge_iter.idx(), + std::make_pair(which_mesh, + orig_loop_index)); + } + } + } +} + +void initOrigIndexMapping(CarveMeshDescr *left_mesh, + CarveMeshDescr *right_mesh, + OrigVertMapping *orig_vert_mapping, + OrigFaceEdgeMapping *orig_face_edge_mapping, + OrigFaceMapping *orig_face_mapping) +{ + initOrigIndexMeshFaceMapping(left_mesh, + CARVE_MESH_LEFT, + left_mesh->orig_loop_index_map, + left_mesh->orig_poly_index_map, + orig_vert_mapping, + orig_face_edge_mapping, + orig_face_mapping); + + initOrigIndexMeshFaceMapping(right_mesh, + CARVE_MESH_RIGHT, + right_mesh->orig_loop_index_map, + right_mesh->orig_poly_index_map, + orig_vert_mapping, + orig_face_edge_mapping, + orig_face_mapping); +} + +} // namespace + +CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data, + CarveMeshImporter *mesh_importer) +{ +#define MAX_STATIC_VERTS 64 + + CarveMeshDescr *mesh_descr = new CarveMeshDescr; + + // Import verices from external mesh to Carve. + int num_verts = mesh_importer->getNumVerts(import_data); + std::vector<carve::geom3d::Vector> vertices; + vertices.reserve(num_verts); + for (int i = 0; i < num_verts; i++) { + float position[3]; + mesh_importer->getVertCoord(import_data, i, position); + vertices.push_back(carve::geom::VECTOR(position[0], + position[1], + position[2])); + } + + // Import polys from external mesh to Carve. + int verts_of_poly_static[MAX_STATIC_VERTS]; + int *verts_of_poly_dynamic = NULL; + int verts_of_poly_dynamic_size = 0; + + int num_loops = mesh_importer->getNumLoops(import_data); + int num_polys = mesh_importer->getNumPolys(import_data); + int loop_index = 0; + 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); + for (int i = 0; i < num_polys; i++) { + int verts_per_poly = + mesh_importer->getNumPolyVerts(import_data, i); + int *verts_of_poly; + + if (verts_per_poly <= MAX_STATIC_VERTS) { + verts_of_poly = verts_of_poly_static; + } + else { + if (verts_of_poly_dynamic_size < verts_per_poly) { + if (verts_of_poly_dynamic != NULL) { + delete [] verts_of_poly_dynamic; + } + verts_of_poly_dynamic = new int[verts_per_poly]; + verts_of_poly_dynamic_size = verts_per_poly; + } + verts_of_poly = verts_of_poly_dynamic; + } + + mesh_importer->getPolyVerts(import_data, i, verts_of_poly); + + carve::math::Matrix3 axis_matrix; + if (!carve_checkPolyPlanarAndGetNormal(vertices, + 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); + + num_tessellated_polys += num_triangles; + } + 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++; + } + } + + if (verts_of_poly_dynamic != NULL) { + delete [] verts_of_poly_dynamic; + } + + mesh_descr->poly = new MeshSet<3> (vertices, + num_tessellated_polys, + face_indices); + + return mesh_descr; + +#undef MAX_STATIC_VERTS +} + +void carve_deleteMesh(CarveMeshDescr *mesh_descr) +{ + delete mesh_descr->poly; + delete mesh_descr; +} + +bool carve_performBooleanOperation(CarveMeshDescr *left_mesh, + CarveMeshDescr *right_mesh, + int operation, + CarveMeshDescr **output_mesh) +{ + *output_mesh = NULL; + + carve::csg::CSG::OP op; + switch (operation) { +#define OP_CONVERT(the_op) \ + case CARVE_OP_ ## the_op: \ + op = carve::csg::CSG::the_op; \ + break; + OP_CONVERT(UNION) + OP_CONVERT(INTERSECTION) + OP_CONVERT(A_MINUS_B) + default: + return false; +#undef OP_CONVERT + } + + CarveMeshDescr *output_descr = new CarveMeshDescr; + output_descr->poly = NULL; + try { + MeshSet<3> *left = left_mesh->poly, *right = right_mesh->poly; + carve::geom3d::Vector min, max; + + // TODO(sergey): Make importer/exporter to care about re-scale + // to save extra mesh iteration here. + carve_getRescaleMinMax(left, right, &min, &max); + + carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z); + carve::rescale::fwd fwd_r(scaler); + carve::rescale::rev rev_r(scaler); + + left->transform(fwd_r); + right->transform(fwd_r); + + // Initialize attributes for maping from boolean result mesh back to + // original geometry indices. + initOrigIndexMapping(left_mesh, right_mesh, + &output_descr->orig_vert_mapping, + &output_descr->orig_face_edge_mapping, + &output_descr->orig_face_mapping); + + carve::csg::CSG csg; + + output_descr->orig_vert_mapping.installHooks(csg); + output_descr->orig_face_edge_mapping.installHooks(csg); + output_descr->orig_face_mapping.installHooks(csg); + + // Prepare operands for actual boolean operation. + // + // It's needed because operands might consist of several intersecting + // meshes and in case of another operands intersect an edge loop of + // intersecting that meshes tessellation of operation result can't be + // done properly. The only way to make such situations working is to + // union intersecting meshes of the same operand. + carve_unionIntersections(&csg, &left, &right); + left_mesh->poly = left; + right_mesh->poly = right; + + if (left->meshes.size() == 0 || right->meshes.size() == 0) { + // Normally shouldn't happen (zero-faces objects are handled by + // modifier itself), but unioning intersecting meshes which doesn't + // have consistent normals might lead to empty result which + // wouldn't work here. + + return false; + } + + output_descr->poly = csg.compute(left, + right, + op, + NULL, + carve::csg::CSG::CLASSIFY_EDGE); + if (output_descr->poly) { + output_descr->poly->transform(rev_r); + } + } + catch (carve::exception e) { + std::cerr << "CSG failed, exception " << e.str() << std::endl; + } + catch (...) { + std::cerr << "Unknown error in Carve library" << std::endl; + } + + *output_mesh = output_descr; + + 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) +{ + for (int i = 0, edge_index = start_edge_index; + i < edges.size(); + ++i, ++edge_index) + { + MeshSet<3>::edge_t *edge = edges.at(i); + MeshSet<3>::vertex_t *v1 = edge->vert; + MeshSet<3>::vertex_t *v2 = edge->next->vert; + + 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; + } + + mesh_exporter->setEdge(export_data, + edge_index, + indexOf(v1, poly->vertex_storage), + indexOf(v2, poly->vertex_storage), + orig_edge_index.first, + orig_edge_index.second); + + edgeIndexMap_put(edge_map, v1, v2, edge_index); + } +} + +void carve_exportMesh(CarveMeshDescr *mesh_descr, + CarveMeshExporter *mesh_exporter, + struct ExportMeshData *export_data) +{ + OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1); + MeshSet<3> *poly = mesh_descr->poly; + 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 + // edges rather then having some global edge storage. + std::unordered_map<VertexPair, OrigIndex> edge_origindex_map; + for (MeshSet<3>::face_iter face_iter = poly->faceBegin(); + face_iter != poly->faceEnd(); + ++face_iter) + { + MeshSet<3>::face_t *face = *face_iter; + 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; + int edge_iter_index = edge_iter.idx(); + + const OrigIndex &orig_loop_index = + mesh_descr->orig_face_edge_mapping.getAttribute(face, + edge_iter_index, + origindex_none); + + if (orig_loop_index.first != CARVE_MESH_NONE) { + OrigIndex orig_edge_index; + + 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); + } + } + } + + // 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) { + MeshSet<3>::vertex_t *vertex = &(*vertex_iter); + + OrigIndex orig_vert_index = + mesh_descr->orig_vert_mapping.getAttribute(vertex, origindex_none); + + float coord[3]; + coord[0] = vertex->v[0]; + coord[1] = vertex->v[1]; + coord[2] = vertex->v[2]; + mesh_exporter->setVert(export_data, i, coord, + orig_vert_index.first, + orig_vert_index.second); + } + + // Export all the edges. + std::unordered_map<VertexPair, int> edge_map; + 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); + + // 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->closed_edges.size(); + } + + // Export all the loops and polys. + MeshSet<3>::face_iter face_iter = poly->faceBegin(); + for (int loop_index = 0, poly_index = 0; + face_iter != poly->faceEnd(); + ++face_iter, ++poly_index) + { + int start_loop_index = loop_index; + MeshSet<3>::face_t *face = *face_iter; + const OrigIndex &orig_face_index = + mesh_descr->orig_face_mapping.getAttribute(face, origindex_none); + + for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin(); + edge_iter != face->end(); + ++edge_iter, ++loop_index) + { + MeshSet<3>::edge_t &edge = *edge_iter; + const OrigIndex &orig_loop_index = + mesh_descr->orig_face_edge_mapping.getAttribute(face, + edge_iter.idx(), + 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); + } + + mesh_exporter->setPoly(export_data, + poly_index, start_loop_index, face->n_edges, + orig_face_index.first, orig_face_index.second); + } +} diff --git a/extern/carve/carve-capi.h b/extern/carve/carve-capi.h new file mode 100644 index 00000000000..25704dfeb48 --- /dev/null +++ b/extern/carve/carve-capi.h @@ -0,0 +1,164 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2014 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Blender Foundation, + * Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __CARVE_CAPI_H__ +#define __CARVE_CAPI_H__ + +#ifdef __cplusplus +extern "C" { +#endif + +struct CarveMeshDescr; + +// +// Importer from external storage to Carve module +// + +struct ImportMeshData; + +// Get number of vertices. +typedef int (*CarveImporter_GetNumVerts) (struct ImportMeshData *import_data); + +// Get number of edges. +typedef int (*CarveImporter_GetNumEdges) (struct ImportMeshData *import_data); + +// Get number of loops. +typedef int (*CarveImporter_GetNumLoops) (struct ImportMeshData *import_data); + +// Get number of polys. +typedef int (*CarveImporter_GetNumPolys) (struct ImportMeshData *import_data); + +// Get 3D coordinate of vertex with given index. +typedef void (*CarveImporter_GetVertCoord) (struct ImportMeshData *import_data, int vert_index, float coord[3]); + +// Get index of vertices which are adjucent to edge specified by it's index. +typedef void (*CarveImporter_GetEdgeVerts) (struct ImportMeshData *import_data, int edge_index, int *v1, int *v2); + +// Get number of adjucent vertices to the poly specified by it's index. +typedef int (*CarveImporter_GetPolyNumVerts) (struct ImportMeshData *import_data, int poly_index); + +// Get list of adjucent vertices to the poly specified by it's index. +typedef void (*CarveImporter_GetPolyVerts) (struct ImportMeshData *import_data, int poly_index, int *verts); + +// Triangulate 2D polygon. +typedef int (*CarveImporter_Triangulate2DPoly) (struct ImportMeshData *import_data, + const float (*vertices)[2], int num_vertices, + unsigned int (*triangles)[3]); + +typedef struct CarveMeshImporter { + CarveImporter_GetNumVerts getNumVerts; + CarveImporter_GetNumEdges getNumEdges; + CarveImporter_GetNumLoops getNumLoops; + CarveImporter_GetNumPolys getNumPolys; + CarveImporter_GetVertCoord getVertCoord; + CarveImporter_GetEdgeVerts getEdgeVerts; + CarveImporter_GetPolyNumVerts getNumPolyVerts; + CarveImporter_GetPolyVerts getPolyVerts; + CarveImporter_Triangulate2DPoly triangulate2DPoly; +} CarveMeshImporter; + +// +// Exporter from Carve module to external storage +// + +struct ExportMeshData; + +// Initialize arrays for geometry. +typedef void (*CarveExporter_InitGeomArrays) (struct ExportMeshData *export_data, + int num_verts, int num_edges, + int num_polys, int num_loops); + +// Set coordinate of vertex with given index. +typedef void (*CarveExporter_SetVert) (struct ExportMeshData *export_data, + int vert_index, float coord[3], + int which_orig_mesh, int orig_edge_index); + +// Set vertices which are adjucent to the edge specified by it's index. +typedef void (*CarveExporter_SetEdge) (struct ExportMeshData *export_data, + int edge_index, int v1, int v2, + int which_orig_mesh, int orig_edge_index); + +// Set adjucent loops to the poly specified by it's index. +typedef void (*CarveExporter_SetPoly) (struct ExportMeshData *export_data, + int poly_index, int start_loop, int num_loops, + int which_orig_mesh, int orig_poly_index); + +// Set list vertex and edge which are adjucent to loop with given index. +typedef void (*CarveExporter_SetLoop) (struct ExportMeshData *export_data, + int loop_index, int vertex, int edge, + int which_orig_mesh, int orig_loop_index); + +// Get edge index from a loop index for a given original mesh. +// +// A bit of a bummer to access original operands data on export stage, +// but Blender side still does have this information in derived meshes +// and we use API to get this data instead of duplicating it in Carve +// API side. This is because of optimizations reasons. +typedef int (*CarveExporter_MapLoopToEdge) (struct ExportMeshData *export_data, + int which_mesh, int loop_index); + +typedef struct CarveMeshExporter { + CarveExporter_InitGeomArrays initGeomArrays; + CarveExporter_SetVert setVert; + CarveExporter_SetEdge setEdge; + CarveExporter_SetPoly setPoly; + CarveExporter_SetLoop setLoop; + CarveExporter_MapLoopToEdge mapLoopToEdge; +} CarveMeshExporter; + +enum { + CARVE_OP_UNION, + CARVE_OP_INTERSECTION, + CARVE_OP_A_MINUS_B, +}; + +enum { + CARVE_MESH_NONE, + CARVE_MESH_LEFT, + CARVE_MESH_RIGHT +}; + +struct CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data, + CarveMeshImporter *mesh_importer); + +void carve_deleteMesh(struct CarveMeshDescr *mesh_descr); + +bool carve_performBooleanOperation(struct CarveMeshDescr *left_mesh, + struct CarveMeshDescr *right_mesh, + int operation, + struct CarveMeshDescr **output_mesh); + +void carve_exportMesh(struct CarveMeshDescr *mesh_descr, + CarveMeshExporter *mesh_exporter, + struct ExportMeshData *export_data); + +void carve_unionIntersections(struct CarveMeshDescr **left_mesh_r, struct CarveMeshDescr **right_mesh_r); + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif // __CARVE_CAPI_H__ diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc new file mode 100644 index 00000000000..b1f9ffbb769 --- /dev/null +++ b/extern/carve/carve-util.cc @@ -0,0 +1,778 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2014 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Blender Foundation, + * Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "carve-util.h" +#include "carve-capi.h" + +#include <cfloat> +#include <carve/csg.hpp> +#include <carve/csg_triangulator.hpp> +#include <carve/rtree.hpp> + +using carve::csg::Intersections; +using carve::geom::aabb; +using carve::geom::RTreeNode; +using carve::geom3d::Vector; +using carve::math::Matrix3; +using carve::mesh::Face; +using carve::mesh::MeshSet; +using carve::triangulate::triangulate; + +typedef std::map< MeshSet<3>::mesh_t*, RTreeNode<3, Face<3> *> * > RTreeCache; +typedef std::map< MeshSet<3>::mesh_t*, bool > IntersectCache; + +namespace { + +// Functions adopted from BLI_math.h to use Carve Vector and Matrix. + +void axis_angle_normalized_to_mat3(const Vector &normal, + const double angle, + Matrix3 *matrix) +{ + double nsi[3], co, si, ico; + + /* now convert this to a 3x3 matrix */ + co = cos(angle); + si = sin(angle); + + ico = (1.0 - co); + nsi[0] = normal[0] * si; + nsi[1] = normal[1] * si; + nsi[2] = normal[2] * si; + + matrix->m[0][0] = ((normal[0] * normal[0]) * ico) + co; + matrix->m[0][1] = ((normal[0] * normal[1]) * ico) + nsi[2]; + matrix->m[0][2] = ((normal[0] * normal[2]) * ico) - nsi[1]; + matrix->m[1][0] = ((normal[0] * normal[1]) * ico) - nsi[2]; + matrix->m[1][1] = ((normal[1] * normal[1]) * ico) + co; + matrix->m[1][2] = ((normal[1] * normal[2]) * ico) + nsi[0]; + matrix->m[2][0] = ((normal[0] * normal[2]) * ico) + nsi[1]; + matrix->m[2][1] = ((normal[1] * normal[2]) * ico) - nsi[0]; + matrix->m[2][2] = ((normal[2] * normal[2]) * ico) + co; +} + +void axis_angle_to_mat3(const Vector &axis, + const double angle, + Matrix3 *matrix) +{ + if (axis.length2() < FLT_EPSILON) { + *matrix = Matrix3(); + return; + } + + Vector nor = axis; + nor.normalize(); + + axis_angle_normalized_to_mat3(nor, angle, matrix); +} + +inline double saacos(double fac) +{ + if (fac <= -1.0) return M_PI; + else if (fac >= 1.0) return 0.0; + else return acos(fac); +} + +bool axis_dominant_v3_to_m3(const Vector &normal, + Matrix3 *matrix) +{ + Vector up; + Vector axis; + double angle; + + up.x = 0.0; + up.y = 0.0; + up.z = 1.0; + + axis = carve::geom::cross(normal, up); + angle = saacos(carve::geom::dot(normal, up)); + + if (angle >= FLT_EPSILON) { + if (axis.length2() < FLT_EPSILON) { + axis[0] = 0.0; + axis[1] = 1.0; + axis[2] = 0.0; + } + + axis_angle_to_mat3(axis, angle, matrix); + return true; + } + else { + *matrix = Matrix3(); + return false; + } +} + +void meshset_minmax(const MeshSet<3> *mesh, + Vector *min, + Vector *max) +{ + for (uint i = 0; i < mesh->vertex_storage.size(); ++i) { + min->x = std::min(min->x, mesh->vertex_storage[i].v.x); + min->y = std::min(min->y, mesh->vertex_storage[i].v.y); + min->z = std::min(min->z, mesh->vertex_storage[i].v.z); + max->x = std::max(max->x, mesh->vertex_storage[i].v.x); + max->y = std::max(max->y, mesh->vertex_storage[i].v.y); + max->z = std::max(max->z, mesh->vertex_storage[i].v.z); + } +} + +} // namespace + +void carve_getRescaleMinMax(const MeshSet<3> *left, + const MeshSet<3> *right, + Vector *min, + Vector *max) +{ + min->x = max->x = left->vertex_storage[0].v.x; + min->y = max->y = left->vertex_storage[0].v.y; + min->z = max->z = left->vertex_storage[0].v.z; + + meshset_minmax(left, min, max); + meshset_minmax(right, min, max); + + // Make sure we don't scale object with zero scale. + if (std::abs(min->x - max->x) < carve::EPSILON) { + min->x = -1.0; + max->x = 1.0; + } + if (std::abs(min->y - max->y) < carve::EPSILON) { + min->y = -1.0; + max->y = 1.0; + } + if (std::abs(min->z - max->z) < carve::EPSILON) { + min->z = -1.0; + max->z = 1.0; + } +} + +namespace { + +void copyMeshes(const std::vector<MeshSet<3>::mesh_t*> &meshes, + std::vector<MeshSet<3>::mesh_t*> *new_meshes) +{ + std::vector<MeshSet<3>::mesh_t*>::const_iterator it = meshes.begin(); + new_meshes->reserve(meshes.size()); + for (; it != meshes.end(); it++) { + MeshSet<3>::mesh_t *mesh = *it; + MeshSet<3>::mesh_t *new_mesh = new MeshSet<3>::mesh_t(mesh->faces); + + new_meshes->push_back(new_mesh); + } +} + +MeshSet<3> *meshSetFromMeshes(const std::vector<MeshSet<3>::mesh_t*> &meshes) +{ + std::vector<MeshSet<3>::mesh_t*> new_meshes; + + copyMeshes(meshes, &new_meshes); + + return new MeshSet<3>(new_meshes); +} + +MeshSet<3> *meshSetFromTwoMeshes(const std::vector<MeshSet<3>::mesh_t*> &left_meshes, + const std::vector<MeshSet<3>::mesh_t*> &right_meshes) +{ + std::vector<MeshSet<3>::mesh_t*> new_meshes; + + copyMeshes(left_meshes, &new_meshes); + copyMeshes(right_meshes, &new_meshes); + + return new MeshSet<3>(new_meshes); +} + +bool checkEdgeFaceIntersections_do(Intersections &intersections, + MeshSet<3>::face_t *face_a, + MeshSet<3>::edge_t *edge_b) +{ + if (intersections.intersects(edge_b, face_a)) + return true; + + carve::mesh::MeshSet<3>::vertex_t::vector_t _p; + if (face_a->simpleLineSegmentIntersection(carve::geom3d::LineSegment(edge_b->v1()->v, edge_b->v2()->v), _p)) + return true; + + return false; +} + +bool checkEdgeFaceIntersections(Intersections &intersections, + MeshSet<3>::face_t *face_a, + MeshSet<3>::face_t *face_b) +{ + MeshSet<3>::edge_t *edge_b; + + edge_b = face_b->edge; + do { + if (checkEdgeFaceIntersections_do(intersections, face_a, edge_b)) + return true; + edge_b = edge_b->next; + } while (edge_b != face_b->edge); + + return false; +} + +inline bool facesAreCoplanar(const MeshSet<3>::face_t *a, const MeshSet<3>::face_t *b) +{ + carve::geom3d::Ray temp; + // XXX: Find a better definition. This may be a source of problems + // if floating point inaccuracies cause an incorrect answer. + return !carve::geom3d::planeIntersection(a->plane, b->plane, temp); +} + +bool checkMeshSetInterseciton_do(Intersections &intersections, + const RTreeNode<3, Face<3> *> *a_node, + const RTreeNode<3, Face<3> *> *b_node, + bool descend_a = true) +{ + if (!a_node->bbox.intersects(b_node->bbox)) { + return false; + } + + if (a_node->child && (descend_a || !b_node->child)) { + for (RTreeNode<3, Face<3> *> *node = a_node->child; node; node = node->sibling) { + if (checkMeshSetInterseciton_do(intersections, node, b_node, false)) { + return true; + } + } + } + else if (b_node->child) { + for (RTreeNode<3, Face<3> *> *node = b_node->child; node; node = node->sibling) { + if (checkMeshSetInterseciton_do(intersections, a_node, node, true)) { + return true; + } + } + } + else { + for (size_t i = 0; i < a_node->data.size(); ++i) { + MeshSet<3>::face_t *fa = a_node->data[i]; + aabb<3> aabb_a = fa->getAABB(); + if (aabb_a.maxAxisSeparation(b_node->bbox) > carve::EPSILON) { + continue; + } + + for (size_t j = 0; j < b_node->data.size(); ++j) { + MeshSet<3>::face_t *fb = b_node->data[j]; + aabb<3> aabb_b = fb->getAABB(); + if (aabb_b.maxAxisSeparation(aabb_a) > carve::EPSILON) { + continue; + } + + std::pair<double, double> a_ra = fa->rangeInDirection(fa->plane.N, fa->edge->vert->v); + std::pair<double, double> b_ra = fb->rangeInDirection(fa->plane.N, fa->edge->vert->v); + if (carve::rangeSeparation(a_ra, b_ra) > carve::EPSILON) { + continue; + } + + std::pair<double, double> a_rb = fa->rangeInDirection(fb->plane.N, fb->edge->vert->v); + std::pair<double, double> b_rb = fb->rangeInDirection(fb->plane.N, fb->edge->vert->v); + if (carve::rangeSeparation(a_rb, b_rb) > carve::EPSILON) { + continue; + } + + if (!facesAreCoplanar(fa, fb)) { + if (checkEdgeFaceIntersections(intersections, fa, fb)) { + return true; + } + } + } + } + } + + return false; +} + +bool checkMeshSetInterseciton(RTreeNode<3, Face<3> *> *rtree_a, RTreeNode<3, Face<3> *> *rtree_b) +{ + Intersections intersections; + return checkMeshSetInterseciton_do(intersections, rtree_a, rtree_b); +} + +void getIntersectedOperandMeshes(std::vector<MeshSet<3>::mesh_t*> *meshes, + const MeshSet<3>::aabb_t &otherAABB, + std::vector<MeshSet<3>::mesh_t*> *operandMeshes, + RTreeCache *rtree_cache, + IntersectCache *intersect_cache) +{ + std::vector<MeshSet<3>::mesh_t*>::iterator it = meshes->begin(); + std::vector< RTreeNode<3, Face<3> *> *> meshRTree; + + while (it != meshes->end()) { + MeshSet<3>::mesh_t *mesh = *it; + bool isAdded = false; + + RTreeNode<3, Face<3> *> *rtree; + bool intersects; + + RTreeCache::iterator rtree_found = rtree_cache->find(mesh); + if (rtree_found != rtree_cache->end()) { + rtree = rtree_found->second; + } + else { + rtree = RTreeNode<3, Face<3> *>::construct_STR(mesh->faces.begin(), mesh->faces.end(), 4, 4); + (*rtree_cache)[mesh] = rtree; + } + + IntersectCache::iterator intersect_found = intersect_cache->find(mesh); + if (intersect_found != intersect_cache->end()) { + intersects = intersect_found->second; + } + else { + intersects = rtree->bbox.intersects(otherAABB); + (*intersect_cache)[mesh] = intersects; + } + + if (intersects) { + bool isIntersect = false; + + std::vector<MeshSet<3>::mesh_t*>::iterator operand_it = operandMeshes->begin(); + std::vector<RTreeNode<3, Face<3> *> *>::iterator tree_it = meshRTree.begin(); + for (; operand_it!=operandMeshes->end(); operand_it++, tree_it++) { + RTreeNode<3, Face<3> *> *operandRTree = *tree_it; + + if (checkMeshSetInterseciton(rtree, operandRTree)) { + isIntersect = true; + break; + } + } + + if (!isIntersect) { + operandMeshes->push_back(mesh); + meshRTree.push_back(rtree); + + it = meshes->erase(it); + isAdded = true; + } + } + + if (!isAdded) { + //delete rtree; + it++; + } + } + + std::vector<RTreeNode<3, Face<3> *> *>::iterator tree_it = meshRTree.begin(); + for (; tree_it != meshRTree.end(); tree_it++) { + //delete *tree_it; + } +} + +MeshSet<3> *getIntersectedOperand(std::vector<MeshSet<3>::mesh_t*> *meshes, + const MeshSet<3>::aabb_t &otherAABB, + RTreeCache *rtree_cache, + IntersectCache *intersect_cache) +{ + std::vector<MeshSet<3>::mesh_t*> operandMeshes; + getIntersectedOperandMeshes(meshes, otherAABB, &operandMeshes, rtree_cache, intersect_cache); + + if (operandMeshes.size() == 0) + return NULL; + + return meshSetFromMeshes(operandMeshes); +} + +MeshSet<3> *unionIntersectingMeshes(carve::csg::CSG *csg, + MeshSet<3> *poly, + const MeshSet<3>::aabb_t &otherAABB) +{ + if (poly->meshes.size() <= 1) { + return poly; + } + + std::vector<MeshSet<3>::mesh_t*> orig_meshes = + std::vector<MeshSet<3>::mesh_t*>(poly->meshes.begin(), poly->meshes.end()); + + RTreeCache rtree_cache; + IntersectCache intersect_cache; + + MeshSet<3> *left = getIntersectedOperand(&orig_meshes, + otherAABB, + &rtree_cache, + &intersect_cache); + + if (!left) { + // No maniforlds which intersects another object at all. + return poly; + } + + while (orig_meshes.size()) { + MeshSet<3> *right = getIntersectedOperand(&orig_meshes, + otherAABB, + &rtree_cache, + &intersect_cache); + + if (!right) { + // No more intersecting manifolds which intersects other object + break; + } + + try { + if (left->meshes.size()==0) { + delete left; + + left = right; + } + else { + MeshSet<3> *result = csg->compute(left, right, + carve::csg::CSG::UNION, + NULL, carve::csg::CSG::CLASSIFY_EDGE); + + delete left; + delete right; + + left = result; + } + } + catch (carve::exception e) { + std::cerr << "CSG failed, exception " << e.str() << std::endl; + + MeshSet<3> *result = meshSetFromTwoMeshes(left->meshes, right->meshes); + + delete left; + delete right; + + left = result; + } + catch (...) { + delete left; + delete right; + + throw "Unknown error in Carve library"; + } + } + + for (RTreeCache::iterator it = rtree_cache.begin(); + it != rtree_cache.end(); + it++) + { + delete it->second; + } + + // Append all meshes which doesn't have intersection with another operand as-is. + if (orig_meshes.size()) { + MeshSet<3> *result = meshSetFromTwoMeshes(left->meshes, orig_meshes); + + delete left; + left = result; + } + + return left; +} + +} // namespace + +// TODO(sergey): This function is to be totally re-implemented to make it +// more clear what's going on and hopefully optimize it as well. +void carve_unionIntersections(carve::csg::CSG *csg, + MeshSet<3> **left_r, + MeshSet<3> **right_r) +{ + MeshSet<3> *left = *left_r, *right = *right_r; + + if (left->meshes.size() == 1 && right->meshes.size() == 0) { + return; + } + + MeshSet<3>::aabb_t leftAABB = left->getAABB(); + MeshSet<3>::aabb_t rightAABB = right->getAABB();; + + left = unionIntersectingMeshes(csg, left, rightAABB); + right = unionIntersectingMeshes(csg, right, leftAABB); + + if (left != *left_r) { + delete *left_r; + } + + if (right != *right_r) + delete *right_r; + + *left_r = left; + *right_r = right; +} + +static inline void add_newell_cross_v3_v3v3(const Vector &v_prev, + const Vector &v_curr, + Vector *n) +{ + (*n)[0] += (v_prev[1] - v_curr[1]) * (v_prev[2] + v_curr[2]); + (*n)[1] += (v_prev[2] - v_curr[2]) * (v_prev[0] + v_curr[0]); + (*n)[2] += (v_prev[0] - v_curr[0]) * (v_prev[1] + v_curr[1]); +} + +// Axis matrix is being set for non-flat ngons only. +bool carve_checkPolyPlanarAndGetNormal(const std::vector<Vector> &vertices, + const int verts_per_poly, + const int *verts_of_poly, + Matrix3 *axis_matrix_r) +{ + if (verts_per_poly == 3) { + // Triangles are always planar. + return true; + } + else if (verts_per_poly == 4) { + // Presumably faster than using generig n-gon check for quads. + + const Vector &v1 = vertices[verts_of_poly[0]], + &v2 = vertices[verts_of_poly[1]], + &v3 = vertices[verts_of_poly[2]], + &v4 = vertices[verts_of_poly[3]]; + + Vector vec1, vec2, vec3, cross; + + vec1 = v2 - v1; + vec2 = v4 - v1; + vec3 = v3 - v1; + + cross = carve::geom::cross(vec1, vec2); + + double production = carve::geom::dot(cross, vec3); + + // TODO(sergey): Check on whether we could have length-independent + // magnitude here. + double magnitude = 1e-3 * cross.length2(); + + return fabs(production) < magnitude; + } + else { + const Vector *vert_prev = &vertices[verts_of_poly[verts_per_poly - 1]]; + const Vector *vert_curr = &vertices[verts_of_poly[0]]; + + Vector normal = carve::geom::VECTOR(0.0, 0.0, 0.0); + for (int i = 0; i < verts_per_poly; i++) { + add_newell_cross_v3_v3v3(*vert_prev, *vert_curr, &normal); + vert_prev = vert_curr; + vert_curr = &vertices[verts_of_poly[(i + 1) % verts_per_poly]]; + } + + if (normal.length2() < FLT_EPSILON) { + // Degenerated face, couldn't triangulate properly anyway. + return true; + } + else { + double magnitude = normal.length2(); + + normal.normalize(); + axis_dominant_v3_to_m3(normal, axis_matrix_r); + + Vector first_projected = *axis_matrix_r * vertices[verts_of_poly[0]]; + double min_z = first_projected[2], max_z = first_projected[2]; + + for (int i = 1; i < verts_per_poly; i++) { + const Vector &vertex = vertices[verts_of_poly[i]]; + Vector projected = *axis_matrix_r * vertex; + if (projected[2] < min_z) { + min_z = projected[2]; + } + if (projected[2] > max_z) { + max_z = projected[2]; + } + } + + if (std::abs(min_z - max_z) > FLT_EPSILON * magnitude) { + return false; + } + } + + return true; + } + + return false; +} + +namespace { + +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) +{ + // Project vertices to 2D plane. + Vector projected; + std::vector<carve::geom::vector<2> > poly_2d; + poly_2d.reserve(verts_per_poly); + for (int i = 0; i < verts_per_poly; ++i) { + projected = axis_matrix * vertices[verts_of_poly[i]]; + poly_2d.push_back(carve::geom::VECTOR(projected[0], projected[1])); + } + + carve::triangulate::triangulate(poly_2d, *triangles); + + return triangles->size(); +} + +int triangulateNGon_importerTriangulator(struct ImportMeshData *import_data, + CarveMeshImporter *mesh_importer, + 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) +{ + typedef float Vector2D[2]; + typedef unsigned int Triangle[3]; + + // Project vertices to 2D plane. + Vector2D *poly_2d = new Vector2D[verts_per_poly]; + Vector projected; + for (int i = 0; i < verts_per_poly; ++i) { + projected = axis_matrix * vertices[verts_of_poly[i]]; + poly_2d[i][0] = projected[0]; + poly_2d[i][1] = projected[1]; + } + + Triangle *api_triangles = new Triangle[verts_per_poly - 2]; + int num_triangles = + mesh_importer->triangulate2DPoly(import_data, + poly_2d, + verts_per_poly, + api_triangles); + + 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])); + } + + delete poly_2d; + delete api_triangles; + + return num_triangles; +} + +} // 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) +{ + int num_triangles = 0; + + assert(verts_per_poly > 3); + + if (verts_per_poly == 4) { + // Quads we triangulate by 1-3 diagonal, it is an original behavior + // of boolean modifier. + // + // 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); + + num_triangles = 2; + } + else { + std::vector<carve::triangulate::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); + } + else { + num_triangles = + triangulateNGon_carveTriangulator(vertices, + verts_per_poly, + verts_of_poly, + axis_matrix, + &triangles); + } + + for (int i = 0; i < triangles.size(); ++i) { + int v1 = triangles[i].c, + v2 = triangles[i].b, + v3 = triangles[i].a; + + // Sanity check of the triangle. + assert(v1 != v2); + assert(v1 != v3); + assert(v2 != v3); + assert(v1 < verts_per_poly); + assert(v2 < verts_per_poly); + assert(v3 < verts_per_poly); + + face_indices->push_back(3); + face_indices->push_back(verts_of_poly[v3]); + face_indices->push_back(verts_of_poly[v2]); + face_indices->push_back(verts_of_poly[v1]); + +#define CHECK_TRIANGLE_LOOP_INDEX(v1, v2) \ + { \ + if (v2 == v1 + 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); + } + } + + return num_triangles; +} diff --git a/extern/carve/carve-util.h b/extern/carve/carve-util.h new file mode 100644 index 00000000000..07743de2d16 --- /dev/null +++ b/extern/carve/carve-util.h @@ -0,0 +1,122 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2014 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Blender Foundation, + * Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __CARVE_UTIL_H__ +#define __CARVE_UTIL_H__ + +#include <carve/csg.hpp> +#include <carve/geom3d.hpp> +#include <carve/interpolator.hpp> +#include <carve/mesh.hpp> + +#include "carve-capi.h" + +void carve_getRescaleMinMax(const carve::mesh::MeshSet<3> *left, + const carve::mesh::MeshSet<3> *right, + carve::geom3d::Vector *min, + carve::geom3d::Vector *max); + +void carve_unionIntersections(carve::csg::CSG *csg, + carve::mesh::MeshSet<3> **left_r, + carve::mesh::MeshSet<3> **right_r); + +bool carve_checkPolyPlanarAndGetNormal(const std::vector<carve::geom3d::Vector> &vertices, + const int verts_per_poly, + const int *verts_of_poly, + carve::math::Matrix3 *axis_matrix_r); + +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); + +namespace carve { + namespace interpolate { + + template<typename attr_t> + class VertexAttr : public Interpolator { + public: + typedef const meshset_t::vertex_t *key_t; + + protected: + typedef std::unordered_map<key_t, attr_t> attrmap_t; + + attrmap_t attrs; + + virtual void resultFace(const carve::csg::CSG &csg, + const meshset_t::face_t *new_face, + const meshset_t::face_t *orig_face, + bool flipped) + { + typedef meshset_t::face_t::const_edge_iter_t const_edge_iter_t; + for (const_edge_iter_t new_edge_iter = new_face->begin(); + new_edge_iter != new_face->end(); + ++new_edge_iter) + { + typename attrmap_t::const_iterator found = + attrs.find(new_edge_iter->vert); + if (found == attrs.end()) { + for (const_edge_iter_t orig_edge_iter = orig_face->begin(); + orig_edge_iter != orig_face->end(); + ++orig_edge_iter) + { + if ((orig_edge_iter->vert->v - new_edge_iter->vert->v).length2() < 1e-5) { + attrs[new_edge_iter->vert] = attrs[orig_edge_iter->vert]; + } + } + } + } + } + + public: + bool hasAttribute(const meshset_t::vertex_t *v) { + return attrs.find(v) != attrs.end(); + } + + const attr_t &getAttribute(const meshset_t::vertex_t *v, const attr_t &def = attr_t()) { + typename attrmap_t::const_iterator found = attrs.find(v); + if (found != attrs.end()) { + return found->second; + } + return def; + } + + void setAttribute(const meshset_t::vertex_t *v, const attr_t &attr) { + attrs[v] = attr; + } + }; + + } // namespace interpolate +} // namespace carve + +#endif // __CARVE_UTIL_H__ diff --git a/extern/carve/include/carve/interpolator.hpp b/extern/carve/include/carve/interpolator.hpp index f8162e52f39..b88a90dd18d 100644 --- a/extern/carve/include/carve/interpolator.hpp +++ b/extern/carve/include/carve/interpolator.hpp @@ -219,7 +219,7 @@ namespace carve { interpolator->edgeDivision(csg, orig_edge, orig_edge_idx, v1, v2); } - Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : interpolator(_interpolator), csg(_csg) { + Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : csg(_csg), interpolator(_interpolator) { } virtual ~Hook() { diff --git a/extern/carve/patches/interpolator_reorder.patch b/extern/carve/patches/interpolator_reorder.patch new file mode 100644 index 00000000000..867297fef7d --- /dev/null +++ b/extern/carve/patches/interpolator_reorder.patch @@ -0,0 +1,12 @@ +diff -r e82d852e4fb0 include/carve/interpolator.hpp +--- a/include/carve/interpolator.hpp Wed Jan 15 13:16:14 2014 +1100 ++++ b/include/carve/interpolator.hpp Fri Jan 31 18:55:05 2014 +0600 +@@ -219,7 +219,7 @@ + interpolator->edgeDivision(csg, orig_edge, orig_edge_idx, v1, v2); + } + +- Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : interpolator(_interpolator), csg(_csg) { ++ Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : csg(_csg), interpolator(_interpolator) { + } + + virtual ~Hook() { diff --git a/extern/carve/patches/series b/extern/carve/patches/series index d579cdaf277..30937b4b9cf 100644 --- a/extern/carve/patches/series +++ b/extern/carve/patches/series @@ -5,3 +5,4 @@ mingw.patch gcc46.patch clang_is_heap_fix.patch strict_flags.patch +interpolator_reorder.patch diff --git a/intern/CMakeLists.txt b/intern/CMakeLists.txt index b7aff03a710..42f6ca4c53e 100644 --- a/intern/CMakeLists.txt +++ b/intern/CMakeLists.txt @@ -48,10 +48,6 @@ if(WITH_MOD_SMOKE) add_subdirectory(smoke) endif() -if(WITH_MOD_BOOLEAN) - add_subdirectory(bsp) -endif() - if(WITH_IK_SOLVER) add_subdirectory(iksolver) endif() diff --git a/intern/bsp/CMakeLists.txt b/intern/bsp/CMakeLists.txt deleted file mode 100644 index 5a2e3538e0a..00000000000 --- a/intern/bsp/CMakeLists.txt +++ /dev/null @@ -1,69 +0,0 @@ -# ***** BEGIN GPL LICENSE BLOCK ***** -# -# This program is free software; you can redistribute it and/or -# modify it under the terms of the GNU General Public License -# as published by the Free Software Foundation; either version 2 -# of the License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License -# along with this program; if not, write to the Free Software Foundation, -# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. -# -# The Original Code is Copyright (C) 2006, Blender Foundation -# All rights reserved. -# -# The Original Code is: all of this file. -# -# Contributor(s): Jacques Beaurain. -# -# ***** END GPL LICENSE BLOCK ***** - -set(INC - intern - ../container - ../guardedalloc - ../memutil -) - -set(INC_SYS - ../moto/include - ../../extern/carve/include -) - -set(SRC - intern/BOP_CarveInterface.cpp - intern/BSP_CSGMesh.cpp - intern/BSP_MeshPrimitives.cpp - intern/CSG_BooleanOps.cpp - - extern/CSG_BooleanOps.h - intern/BOP_Interface.h - intern/BSP_CSGException.h - intern/BSP_CSGMesh.h - intern/BSP_CSGMesh_CFIterator.h - intern/BSP_MeshPrimitives.h -) - -if(WITH_BOOST) - if(NOT MSVC) - # Boost is setting as preferred collections library in the Carve code when using MSVC compiler - add_definitions( - -DHAVE_BOOST_UNORDERED_COLLECTIONS - ) - endif() - - add_definitions( - -DCARVE_SYSTEM_BOOST - ) - - list(APPEND INC_SYS - ${BOOST_INCLUDE_DIR} - ) -endif() - -blender_add_lib(bf_intern_bsp "${SRC}" "${INC}" "${INC_SYS}") diff --git a/intern/bsp/SConscript b/intern/bsp/SConscript deleted file mode 100644 index 92c8ee48b33..00000000000 --- a/intern/bsp/SConscript +++ /dev/null @@ -1,49 +0,0 @@ -#!/usr/bin/env python -# -# ***** BEGIN GPL LICENSE BLOCK ***** -# -# This program is free software; you can redistribute it and/or -# modify it under the terms of the GNU General Public License -# as published by the Free Software Foundation; either version 2 -# of the License, or (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License -# along with this program; if not, write to the Free Software Foundation, -# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. -# -# The Original Code is Copyright (C) 2006, Blender Foundation -# All rights reserved. -# -# The Original Code is: all of this file. -# -# Contributor(s): Nathan Letwory. -# -# ***** END GPL LICENSE BLOCK ***** - -Import ('env') - -sources = env.Glob('intern/*.cpp') - -incs = 'intern ../container ../moto/include ../memutil ../guardedalloc ../../extern/carve/include' - -defs = [] - -if env['WITH_BF_BOOST']: - isMINGW = env['OURPLATFORM'] in ('win32-mingw', 'win64-mingw') - - if env['OURPLATFORM'] not in ('win32-vc', 'win64-vc') and not isMINGW: - # Boost is setting as preferred collections library in the Carve code when using MSVC compiler - defs.append('HAVE_BOOST_UNORDERED_COLLECTIONS') - - if not isMINGW: - defs.append('CARVE_SYSTEM_BOOST') - - incs += ' ' + env['BF_BOOST_INC'] - -env.BlenderLib ('bf_intern_bsp', sources, Split(incs), defs, libtype=['core','player'], priority=[200,100] ) - diff --git a/intern/bsp/extern/CSG_BooleanOps.h b/intern/bsp/extern/CSG_BooleanOps.h deleted file mode 100644 index 5ba6e0d76a1..00000000000 --- a/intern/bsp/extern/CSG_BooleanOps.h +++ /dev/null @@ -1,361 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/extern/CSG_BooleanOps.h - * \ingroup bsp - */ - - -#ifndef __CSG_BOOLEANOPS_H__ -#define __CSG_BOOLEANOPS_H__ - - -/** - * @section Interface structures for CSG module. - * This interface falls into 2 categories. - * The first section deals with an abstract mesh description - * between blender and this module. The second deals with - * the module functions. - * The CSG module needs to know about the following entities: - */ - -/** - * CSG_IFace -- an interface polygon structure. - * vertex_index is a fixed size array of 4 elements containing indices into - * an abstract vertex container. 3 or 4 of these elements may be used to - * describe either quads or triangles. - * vertex_number is the number of vertices in this face - either 3 or 4. - * vertex_colors is an array of {r,g,b} triplets one for each vertex index. - * tex_coords is an array of {u,v} triplets one for each vertex index. - * user_data is a pointer to arbitary data of fixed width , - * this data is copied around with the face, and duplicated if a face is - * split. Contains things like material index. - */ - -#ifdef __cplusplus -extern "C" { -#endif - -typedef struct { - int vertex_index[4]; - int vertex_number; - int orig_face; -} CSG_IFace; - -/** - * CSG_IVertex -- an interface vertex structure. - * position is the location of the vertex in 3d space. - */ - -typedef struct { - float position[3]; -} CSG_IVertex; - -/** - * The actual useful data contained in a group of faces is - * described by the following struct - */ - -/** - * @section Iterator abstraction. - * - * The CSG module asks blender to fill in an instance of the above - * structure, and requests blender to move up and down (iterate) through - * it's face and vertex containers. - * - * An iterator supports the following functions. - * int IsDone(iterator *it) -- returns true if the iterator has reached - * the end of it's container. - * - * void Fill(iterator *it,DataType *data) -- Return the contents of the - * container at the current iterator position. - * - * void Step(iterator *it) -- increment the iterator to the next position - * in the container. - * - * The iterator is used in the following manner. - * - * MyIterator * iterator = ... - * DataType data; - * - * while (!IsDone(iterator)) { - * Fill(iterator,&data); - * //process information pointed to by data - * ... - * Step(iterator); - * } - * - * The CSG module does not want to know about the implementation of these - * functions so we use the c function ptr mechanism to hide them. Our - * iterator descriptor now looks like this. - */ - -typedef void* CSG_IteratorPtr; - -typedef int (*CSG_FaceItDoneFunc)(CSG_IteratorPtr it); -typedef void (*CSG_FaceItFillFunc)(CSG_IteratorPtr it,CSG_IFace *face); -typedef void (*CSG_FaceItStepFunc)(CSG_IteratorPtr it); -typedef void (*CSG_FaceItResetFunc)(CSG_IteratorPtr it); - -typedef struct CSG_FaceIteratorDescriptor { - CSG_IteratorPtr it; - CSG_FaceItDoneFunc Done; - CSG_FaceItFillFunc Fill; - CSG_FaceItStepFunc Step; - CSG_FaceItResetFunc Reset; - unsigned int num_elements; -} CSG_FaceIteratorDescriptor; - -/** - * Similarly to walk through the vertex arrays we have. - */ -typedef int (*CSG_VertexItDoneFunc)(CSG_IteratorPtr it); -typedef void (*CSG_VertexItFillFunc)(CSG_IteratorPtr it,CSG_IVertex *face); -typedef void (*CSG_VertexItStepFunc)(CSG_IteratorPtr it); -typedef void (*CSG_VertexItResetFunc)(CSG_IteratorPtr it); - -typedef struct CSG_VertexIteratorDescriptor { - CSG_IteratorPtr it; - CSG_VertexItDoneFunc Done; - CSG_VertexItFillFunc Fill; - CSG_VertexItStepFunc Step; - CSG_VertexItResetFunc Reset; - unsigned int num_elements; -} CSG_VertexIteratorDescriptor; - -/** - * The actual iterator structures are not exposed to the CSG module, they - * will contain datatypes specific to blender. - */ - -/** - * @section CSG Module interface functions. - * - * The functions below are to be used in the following way: - * - * // Create a boolean operation handle - * CSG_BooleanOperation *operation = CSG_NewBooleanFunction(); - * if (operation == NULL) { - * // deal with low memory exception - * } - * - * // Report to the user if they will loose any data! - * ... - * - * // Get some mesh iterators for your mesh data structures - * CSG_FaceIteratorDescriptor obA_faces = ... - * CSG_VertexIteratorDescriptor obA_verts = ... - * - * // same for object B - * CSG_FaceIteratorDescriptor obB_faces = ... - * CSG_VertexIteratorDescriptor obB_verts = ... - * - * // perform the operation...! - * - * int success = CSG_PerformBooleanOperation( - * operation, - * e_csg_intersection, - * obA_faces, - * obA_vertices, - * obB_faces, - * obB_vertices - * ); - * - * // if the operation failes report miserable faiulre to user - * // and clear up data structures. - * if (!success) { - * ... - * CSG_FreeBooleanOperation(operation); - * return; - * } - * - * // read the new mesh vertices back from the module - * // and assign to your own mesh structure. - * - * // First we need to create a CSG_IVertex so the module can fill it in. - * CSG_IVertex vertex; - * CSG_VertexIteratorDescriptor * verts_it = CSG_OutputVertexDescriptor(operation); - * - * // initialize your vertex container with the number of verts (verts_it->num_elements) - * - * while (!verts_it->Done(verts_it->it)) { - * verts_it->Fill(verts_it->it,&vertex); - * - * // create a new vertex of your own type and add it - * // to your mesh structure. - * verts_it->Step(verts_it->it); - * } - * // Free the vertex iterator - * CSG_FreeVertexDescriptor(verts_it); - * - * // similarly for faces. - * CSG_IFace face; - * - * // you may need to reserve some memory in face->user_data here. - * - * // initialize your face container with the number of faces (faces_it->num_elements) - * - * CSG_FaceIteratorDescriptor * faces_it = CSG_OutputFaceDescriptor(operation); - * - * while (!faces_it->Done(faces_it->it)) { - * faces_it->Fill(faces_it->it,&face); - * - * // create a new face of your own type and add it - * // to your mesh structure. - * faces_it->Step(&faces_it->it); - * } - * - * // Free the face iterator - * CSG_FreeVertexDescriptor(faces_it); - * - * // that's it free the operation. - * - * CSG_FreeBooleanOperation(operation); - * return; - * - */ - -/** - * Description of boolean operation type. - */ - -typedef enum { - e_csg_union, - e_csg_intersection, - e_csg_difference, - e_csg_classify -} CSG_OperationType; - -/** - * 'Handle' into the CSG module that identifies a particular CSG operation. - * the pointer CSG_info containers module specific data, and should not - * be touched in anyway outside of the module. - */ - -typedef struct { - void *CSG_info; -} CSG_BooleanOperation; - -/** - * Return a ptr to a CSG_BooleanOperation object allocated - * on the heap. The CSG module owns the memory associated with - * the returned ptr, use CSG_FreeBooleanOperation() to free this memory. - */ - CSG_BooleanOperation * -CSG_NewBooleanFunction( - void -); - -/** - * Attempt to perform a boolean operation between the 2 objects of the - * desired type. This may fail due to an internal error or lack of memory. - * In this case 0 is returned, otehrwise 1 is returned indicating success. - * @param operation is a 'handle' into the CSG_Module created by CSG_NewBooleanFunction() - * @param op_type is the operation to perform. - * @param obAFaces is an iterator over the faces of objectA, - * @param obAVertices is an iterator over the vertices of objectA - * @param obAFaces is an iterator over the faces of objectB, - * @param obAVertices is an iterator over the vertices of objectB - * @param interp_func the face_vertex data interpolation function.(see above) - * - * All iterators must be valid and pointing to the first element in their - * respective containers. - */ - int -CSG_PerformBooleanOperation( - CSG_BooleanOperation * operation, - CSG_OperationType op_type, - CSG_FaceIteratorDescriptor obAFaces, - CSG_VertexIteratorDescriptor obAVertices, - CSG_FaceIteratorDescriptor obBFaces, - CSG_VertexIteratorDescriptor obBVertices -); - -/** - * If the a boolean operation was successful, you may access the results - * through the following functions. - * - * CSG_OuputFaceDescriptor() returns a ptr to a CSG_FaceIteratorDesciptor - * allocated on the heap and owned by the CSG module. The iterator is - * positioned at the start of the internal face container. - * CSG_OutputVertexDescriptor() returns a ptr to a CSG_VertexIteratorDescriptor - * allocated on the heap and owned by the CSG module. The iterator is - * positioned at the start of the internal vertex container. - * There is no function to rewind an iterator but you may obtain more - * than one - * iterator at a time. Please use the function CSG_FreeFaceIterator() - * and CSG_FreeVertexIterator to free internal memory allocated for these - * iterators. - * - * If the last operation was not successful, these functions return NULL. - */ - int -CSG_OutputFaceDescriptor( - CSG_BooleanOperation * operation, - CSG_FaceIteratorDescriptor * output -); - - int -CSG_OutputVertexDescriptor( - CSG_BooleanOperation * operation, - CSG_VertexIteratorDescriptor *output -); - -/** - * Clean up functions. - * Free internal memory associated with CSG interface structures. You must - * call these functions on any structures created by the module, even if - * subsequent operations did not succeed. - */ - void -CSG_FreeVertexDescriptor( - CSG_VertexIteratorDescriptor * v_descriptor -); - - void -CSG_FreeFaceDescriptor( - CSG_FaceIteratorDescriptor * f_descriptor -); - -/** - * Free the memory associated with a boolean operation. - * NOTE any iterator descriptor describing the output will become - * invalid after this call and should be freed immediately. - */ - void -CSG_FreeBooleanOperation( - CSG_BooleanOperation *operation -); - -#ifdef __cplusplus -} -#endif - - - -#endif - diff --git a/intern/bsp/intern/BOP_CarveInterface.cpp b/intern/bsp/intern/BOP_CarveInterface.cpp deleted file mode 100644 index a96196ee8f5..00000000000 --- a/intern/bsp/intern/BOP_CarveInterface.cpp +++ /dev/null @@ -1,852 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2010 by the Blender Foundation. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): Ken Hughes, - * Sergey Sharybin. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/BOP_CarveInterface.cpp - * \ingroup bsp - */ - -#include "BOP_Interface.h" -#include "BSP_CSGMesh_CFIterator.h" - -#include <carve/csg_triangulator.hpp> -#include <carve/interpolator.hpp> -#include <carve/rescale.hpp> - -#include <iostream> - -using namespace carve::mesh; -using namespace carve::geom; -typedef unsigned int uint; - -#define MAX(x,y) ((x)>(y)?(x):(y)) -#define MIN(x,y) ((x)<(y)?(x):(y)) - -static bool isQuadPlanar(carve::geom3d::Vector &v1, carve::geom3d::Vector &v2, - carve::geom3d::Vector &v3, carve::geom3d::Vector &v4) -{ - carve::geom3d::Vector vec1, vec2, vec3, cross; - - vec1 = v2 - v1; - vec2 = v4 - v1; - vec3 = v3 - v1; - - cross = carve::geom::cross(vec1, vec2); - - float production = carve::geom::dot(cross, vec3); - float magnitude = 1e-5 * cross.length(); - - return fabsf(production) < magnitude; -} - -static bool isFacePlanar(CSG_IFace &face, std::vector<carve::geom3d::Vector> &vertices) -{ - if (face.vertex_number == 4) { - return isQuadPlanar(vertices[face.vertex_index[0]], vertices[face.vertex_index[1]], - vertices[face.vertex_index[2]], vertices[face.vertex_index[3]]); - } - - return true; -} - -static void Carve_copyMeshes(std::vector<MeshSet<3>::mesh_t*> &meshes, std::vector<MeshSet<3>::mesh_t*> &new_meshes) -{ - std::vector<MeshSet<3>::mesh_t*>::iterator it = meshes.begin(); - - for(; it!=meshes.end(); it++) { - MeshSet<3>::mesh_t *mesh = *it; - MeshSet<3>::mesh_t *new_mesh = new MeshSet<3>::mesh_t(mesh->faces); - - new_meshes.push_back(new_mesh); - } -} - -static MeshSet<3> *Carve_meshSetFromMeshes(std::vector<MeshSet<3>::mesh_t*> &meshes) -{ - std::vector<MeshSet<3>::mesh_t*> new_meshes; - - Carve_copyMeshes(meshes, new_meshes); - - return new MeshSet<3>(new_meshes); -} - -static MeshSet<3> *Carve_meshSetFromTwoMeshes(std::vector<MeshSet<3>::mesh_t*> &left_meshes, - std::vector<MeshSet<3>::mesh_t*> &right_meshes) -{ - std::vector<MeshSet<3>::mesh_t*> new_meshes; - - Carve_copyMeshes(left_meshes, new_meshes); - Carve_copyMeshes(right_meshes, new_meshes); - - return new MeshSet<3>(new_meshes); -} - -static bool Carve_checkEdgeFaceIntersections_do(carve::csg::Intersections &intersections, - MeshSet<3>::face_t *face_a, MeshSet<3>::edge_t *edge_b) -{ - if(intersections.intersects(edge_b, face_a)) - return true; - - carve::mesh::MeshSet<3>::vertex_t::vector_t _p; - if(face_a->simpleLineSegmentIntersection(carve::geom3d::LineSegment(edge_b->v1()->v, edge_b->v2()->v), _p)) - return true; - - return false; -} - -static bool Carve_checkEdgeFaceIntersections(carve::csg::Intersections &intersections, - MeshSet<3>::face_t *face_a, MeshSet<3>::face_t *face_b) -{ - MeshSet<3>::edge_t *edge_b; - - edge_b = face_b->edge; - do { - if(Carve_checkEdgeFaceIntersections_do(intersections, face_a, edge_b)) - return true; - edge_b = edge_b->next; - } while (edge_b != face_b->edge); - - return false; -} - -static inline bool Carve_facesAreCoplanar(const MeshSet<3>::face_t *a, const MeshSet<3>::face_t *b) -{ - carve::geom3d::Ray temp; - // XXX: Find a better definition. This may be a source of problems - // if floating point inaccuracies cause an incorrect answer. - return !carve::geom3d::planeIntersection(a->plane, b->plane, temp); -} - -static bool Carve_checkMeshSetInterseciton_do(carve::csg::Intersections &intersections, - const RTreeNode<3, Face<3> *> *a_node, - const RTreeNode<3, Face<3> *> *b_node, - bool descend_a = true) -{ - if(!a_node->bbox.intersects(b_node->bbox)) - return false; - - if(a_node->child && (descend_a || !b_node->child)) { - for(RTreeNode<3, Face<3> *> *node = a_node->child; node; node = node->sibling) { - if(Carve_checkMeshSetInterseciton_do(intersections, node, b_node, false)) - return true; - } - } - else if(b_node->child) { - for(RTreeNode<3, Face<3> *> *node = b_node->child; node; node = node->sibling) { - if(Carve_checkMeshSetInterseciton_do(intersections, a_node, node, true)) - return true; - } - } - else { - for(size_t i = 0; i < a_node->data.size(); ++i) { - MeshSet<3>::face_t *fa = a_node->data[i]; - aabb<3> aabb_a = fa->getAABB(); - if(aabb_a.maxAxisSeparation(b_node->bbox) > carve::EPSILON) continue; - - for(size_t j = 0; j < b_node->data.size(); ++j) { - MeshSet<3>::face_t *fb = b_node->data[j]; - aabb<3> aabb_b = fb->getAABB(); - if(aabb_b.maxAxisSeparation(aabb_a) > carve::EPSILON) continue; - - std::pair<double, double> a_ra = fa->rangeInDirection(fa->plane.N, fa->edge->vert->v); - std::pair<double, double> b_ra = fb->rangeInDirection(fa->plane.N, fa->edge->vert->v); - if(carve::rangeSeparation(a_ra, b_ra) > carve::EPSILON) continue; - - std::pair<double, double> a_rb = fa->rangeInDirection(fb->plane.N, fb->edge->vert->v); - std::pair<double, double> b_rb = fb->rangeInDirection(fb->plane.N, fb->edge->vert->v); - if(carve::rangeSeparation(a_rb, b_rb) > carve::EPSILON) continue; - - if(!Carve_facesAreCoplanar(fa, fb)) { - if(Carve_checkEdgeFaceIntersections(intersections, fa, fb)) { - return true; - } - } - } - } - } - - return false; -} - -static bool Carve_checkMeshSetInterseciton(RTreeNode<3, Face<3> *> *rtree_a, RTreeNode<3, Face<3> *> *rtree_b) -{ - carve::csg::Intersections intersections; - - return Carve_checkMeshSetInterseciton_do(intersections, rtree_a, rtree_b); -} - -static void Carve_getIntersectedOperandMeshes(std::vector<MeshSet<3>::mesh_t*> &meshes, MeshSet<3>::aabb_t &otherAABB, - std::vector<MeshSet<3>::mesh_t*> &operandMeshes) -{ - std::vector<MeshSet<3>::mesh_t*>::iterator it = meshes.begin(); - std::vector< RTreeNode<3, Face<3> *> *> meshRTree; - - while (it != meshes.end()) { - MeshSet<3>::mesh_t *mesh = *it; - bool isAdded = false; - - RTreeNode<3, Face<3> *> *rtree = RTreeNode<3, Face<3> *>::construct_STR(mesh->faces.begin(), mesh->faces.end(), 4, 4); - - if (rtree->bbox.intersects(otherAABB)) { - bool isIntersect = false; - - std::vector<MeshSet<3>::mesh_t*>::iterator operand_it = operandMeshes.begin(); - std::vector<RTreeNode<3, Face<3> *> *>::iterator tree_it = meshRTree.begin(); - for(; operand_it!=operandMeshes.end(); operand_it++, tree_it++) { - RTreeNode<3, Face<3> *> *operandRTree = *tree_it; - - if(Carve_checkMeshSetInterseciton(rtree, operandRTree)) { - isIntersect = true; - break; - } - } - - if(!isIntersect) { - operandMeshes.push_back(mesh); - meshRTree.push_back(rtree); - - it = meshes.erase(it); - isAdded = true; - } - } - - if (!isAdded) { - delete rtree; - it++; - } - } - - std::vector<RTreeNode<3, Face<3> *> *>::iterator tree_it = meshRTree.begin(); - for(; tree_it != meshRTree.end(); tree_it++) { - delete *tree_it; - } -} - -static MeshSet<3> *Carve_getIntersectedOperand(std::vector<MeshSet<3>::mesh_t*> &meshes, MeshSet<3>::aabb_t &otherAABB) -{ - std::vector<MeshSet<3>::mesh_t*> operandMeshes; - Carve_getIntersectedOperandMeshes(meshes, otherAABB, operandMeshes); - - if (operandMeshes.size() == 0) - return NULL; - - return Carve_meshSetFromMeshes(operandMeshes); -} - -static MeshSet<3> *Carve_unionIntersectingMeshes(MeshSet<3> *poly, - MeshSet<3>::aabb_t &otherAABB, - carve::interpolate::FaceAttr<uint> &oface_num) -{ - if(poly->meshes.size()<=1) - return poly; - - carve::csg::CSG csg; - - oface_num.installHooks(csg); - csg.hooks.registerHook(new carve::csg::CarveTriangulator, carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT); - - std::vector<MeshSet<3>::mesh_t*> orig_meshes = - std::vector<MeshSet<3>::mesh_t*>(poly->meshes.begin(), poly->meshes.end()); - - MeshSet<3> *left = Carve_getIntersectedOperand(orig_meshes, otherAABB); - - if (!left) { - /* no maniforlds which intersects another object at all */ - return poly; - } - - while (orig_meshes.size()) { - MeshSet<3> *right = Carve_getIntersectedOperand(orig_meshes, otherAABB); - - if (!right) { - /* no more intersecting manifolds which intersects other object */ - break; - } - - try { - if(left->meshes.size()==0) { - delete left; - - left = right; - } - else { - MeshSet<3> *result = csg.compute(left, right, carve::csg::CSG::UNION, NULL, carve::csg::CSG::CLASSIFY_EDGE); - - delete left; - delete right; - - left = result; - } - } - catch(carve::exception e) { - std::cerr << "CSG failed, exception " << e.str() << std::endl; - - MeshSet<3> *result = Carve_meshSetFromTwoMeshes(left->meshes, right->meshes); - - delete left; - delete right; - - left = result; - } - catch(...) { - delete left; - delete right; - - throw "Unknown error in Carve library"; - } - } - - /* append all meshes which doesn't have intersection with another operand as-is */ - if (orig_meshes.size()) { - MeshSet<3> *result = Carve_meshSetFromTwoMeshes(left->meshes, orig_meshes); - - delete left; - - return result; - } - - return left; -} - -static void Carve_unionIntersections(MeshSet<3> **left_r, MeshSet<3> **right_r, - carve::interpolate::FaceAttr<uint> &oface_num) -{ - MeshSet<3> *left, *right; - - MeshSet<3>::aabb_t leftAABB = (*left_r)->getAABB(); - MeshSet<3>::aabb_t rightAABB = (*right_r)->getAABB(); - - left = Carve_unionIntersectingMeshes(*left_r, rightAABB, oface_num); - right = Carve_unionIntersectingMeshes(*right_r, leftAABB, oface_num); - - if(left != *left_r) - delete *left_r; - - if(right != *right_r) - delete *right_r; - - *left_r = left; - *right_r = right; -} - -static MeshSet<3> *Carve_addMesh(CSG_FaceIteratorDescriptor &face_it, - CSG_VertexIteratorDescriptor &vertex_it, - carve::interpolate::FaceAttr<uint> &oface_num, - uint &num_origfaces) -{ - CSG_IVertex vertex; - std::vector<carve::geom3d::Vector> vertices; - - while (!vertex_it.Done(vertex_it.it)) { - vertex_it.Fill(vertex_it.it,&vertex); - vertices.push_back(VECTOR(vertex.position[0], - vertex.position[1], - vertex.position[2])); - vertex_it.Step(vertex_it.it); - } - - CSG_IFace face; - std::vector<int> f; - int numfaces = 0; - - // now for the polygons. - // we may need to decalare some memory for user defined face properties. - - std::vector<int> forig; - while (!face_it.Done(face_it.it)) { - face_it.Fill(face_it.it,&face); - - if (isFacePlanar(face, vertices)) { - f.push_back(face.vertex_number); - f.push_back(face.vertex_index[0]); - f.push_back(face.vertex_index[1]); - f.push_back(face.vertex_index[2]); - - if (face.vertex_number == 4) - f.push_back(face.vertex_index[3]); - - forig.push_back(face.orig_face); - ++numfaces; - face_it.Step(face_it.it); - ++num_origfaces; - } - else { - f.push_back(3); - f.push_back(face.vertex_index[0]); - f.push_back(face.vertex_index[1]); - f.push_back(face.vertex_index[2]); - - forig.push_back(face.orig_face); - ++numfaces; - - if (face.vertex_number == 4) { - f.push_back(3); - f.push_back(face.vertex_index[0]); - f.push_back(face.vertex_index[2]); - f.push_back(face.vertex_index[3]); - - forig.push_back(face.orig_face); - ++numfaces; - } - - face_it.Step(face_it.it); - ++num_origfaces; - } - } - - MeshSet<3> *poly = new MeshSet<3> (vertices, numfaces, f); - - uint i; - MeshSet<3>::face_iter face_iter = poly->faceBegin(); - for (i = 0; face_iter != poly->faceEnd(); ++face_iter, ++i) { - MeshSet<3>::face_t *face = *face_iter; - oface_num.setAttribute(face, forig[i]); - } - - return poly; -} - -static double triangleArea(carve::geom3d::Vector &v1, carve::geom3d::Vector &v2, carve::geom3d::Vector &v3) -{ - carve::geom3d::Vector a = v2 - v1; - carve::geom3d::Vector b = v3 - v1; - - return carve::geom::cross(a, b).length(); -} - -static bool checkValidQuad(std::vector<MeshSet<3>::vertex_t> &vertex_storage, uint quad[4]) -{ - carve::geom3d::Vector &v1 = vertex_storage[quad[0]].v; - carve::geom3d::Vector &v2 = vertex_storage[quad[1]].v; - carve::geom3d::Vector &v3 = vertex_storage[quad[2]].v; - carve::geom3d::Vector &v4 = vertex_storage[quad[3]].v; - -#if 0 - /* disabled for now to prevent initially non-planar be triangulated - * in theory this might cause some artifacts if intersections happens by non-planar - * non-concave quad, but in practice it's acceptable */ - if (!isQuadPlanar(v1, v2, v3, v4)) { - /* non-planar faces better not be merged because of possible differences in triangulation - * of non-planar faces in opengl and renderer */ - return false; - } -#endif - - carve::geom3d::Vector edges[4]; - carve::geom3d::Vector normal; - bool normal_set = false; - - edges[0] = v2 - v1; - edges[1] = v3 - v2; - edges[2] = v4 - v3; - edges[3] = v1 - v4; - - for (int i = 0; i < 4; i++) { - int n = i + 1; - - if (n == 4) - n = 0; - - carve::geom3d::Vector current_normal = carve::geom::cross(edges[i], edges[n]); - - if (current_normal.length() > DBL_EPSILON) { - if (!normal_set) { - normal = current_normal; - normal_set = true; - } - else if (carve::geom::dot(normal, current_normal) < 0) { - return false; - } - } - } - - if (!normal_set) { - /* normal wasn't set means face is degraded and better merge it in such way */ - return false; - } - - double area = triangleArea(v1, v2, v3) + triangleArea(v1, v3, v4); - if (area <= DBL_EPSILON) - return false; - - return true; -} - -// check whether two faces share an edge, and if so merge them -static uint quadMerge(std::map<MeshSet<3>::vertex_t*, uint> *vertexToIndex_map, - std::vector<MeshSet<3>::vertex_t> &vertex_storage, - MeshSet<3>::face_t *f1, MeshSet<3>::face_t *f2, - uint v, uint quad[4]) -{ - uint current, n1, p1, n2, p2; - uint v1[3]; - uint v2[3]; - - // get the vertex indices for each face - v1[0] = vertexToIndex_map->find(f1->edge->vert)->second; - v1[1] = vertexToIndex_map->find(f1->edge->next->vert)->second; - v1[2] = vertexToIndex_map->find(f1->edge->next->next->vert)->second; - - v2[0] = vertexToIndex_map->find(f2->edge->vert)->second; - v2[1] = vertexToIndex_map->find(f2->edge->next->vert)->second; - v2[2] = vertexToIndex_map->find(f2->edge->next->next->vert)->second; - - // locate the current vertex we're examining, and find the next and - // previous vertices based on the face windings - if (v1[0] == v) {current = 0; p1 = 2; n1 = 1;} - else if (v1[1] == v) {current = 1; p1 = 0; n1 = 2;} - else {current = 2; p1 = 1; n1 = 0;} - - if (v2[0] == v) {p2 = 2; n2 = 1;} - else if (v2[1] == v) {p2 = 0; n2 = 2;} - else {p2 = 1; n2 = 0;} - - // if we find a match, place indices into quad in proper order and return - // success code - if (v1[p1] == v2[n2]) { - quad[0] = v1[current]; - quad[1] = v1[n1]; - quad[2] = v1[p1]; - quad[3] = v2[p2]; - - return checkValidQuad(vertex_storage, quad); - } - else if (v1[n1] == v2[p2]) { - quad[0] = v1[current]; - quad[1] = v2[n2]; - quad[2] = v1[n1]; - quad[3] = v1[p1]; - - return checkValidQuad(vertex_storage, quad); - } - - return 0; -} - -static bool Carve_checkDegeneratedFace(std::map<MeshSet<3>::vertex_t*, uint> *vertexToIndex_map, MeshSet<3>::face_t *face) -{ - /* only tris and quads for now */ - if (face->n_edges == 3) { - uint v1, v2, v3; - - v1 = vertexToIndex_map->find(face->edge->prev->vert)->second; - v2 = vertexToIndex_map->find(face->edge->vert)->second; - v3 = vertexToIndex_map->find(face->edge->next->vert)->second; - - if (v1 == v2 || v2 == v3 || v1 == v3) - return true; - } - else if (face->n_edges == 4) { - uint v1, v2, v3, v4; - - v1 = vertexToIndex_map->find(face->edge->prev->vert)->second; - v2 = vertexToIndex_map->find(face->edge->vert)->second; - v3 = vertexToIndex_map->find(face->edge->next->vert)->second; - v4 = vertexToIndex_map->find(face->edge->next->next->vert)->second; - - if (v1 == v2 || v1 == v3 || v1 == v4 || v2 == v3 || v2 == v4 || v3 == v4) - return true; - } - - return false; -} - -static BSP_CSGMesh *Carve_exportMesh(MeshSet<3>* &poly, carve::interpolate::FaceAttr<uint> &oface_num, - uint num_origfaces) -{ - uint i; - BSP_CSGMesh *outputMesh = BSP_CSGMesh::New(); - - if (outputMesh == NULL) - return NULL; - - std::vector<BSP_MVertex> *vertices = new std::vector<BSP_MVertex>; - - outputMesh->SetVertices(vertices); - - std::map<MeshSet<3>::vertex_t*, uint> vertexToIndex_map; - std::vector<MeshSet<3>::vertex_t>::iterator it = poly->vertex_storage.begin(); - for (i = 0; it != poly->vertex_storage.end(); ++i, ++it) { - MeshSet<3>::vertex_t *vertex = &(*it); - vertexToIndex_map[vertex] = i; - } - - for (i = 0; i < poly->vertex_storage.size(); ++i ) { - BSP_MVertex outVtx(MT_Point3 (poly->vertex_storage[i].v[0], - poly->vertex_storage[i].v[1], - poly->vertex_storage[i].v[2])); - outVtx.m_edges.clear(); - outputMesh->VertexSet().push_back(outVtx); - } - - // build vectors of faces for each original face and each vertex - std::vector<std::vector<uint> > vi(poly->vertex_storage.size()); - std::vector<std::vector<uint> > ofaces(num_origfaces); - MeshSet<3>::face_iter face_iter = poly->faceBegin(); - for (i = 0; face_iter != poly->faceEnd(); ++face_iter, ++i) { - MeshSet<3>::face_t *f = *face_iter; - - if (Carve_checkDegeneratedFace(&vertexToIndex_map, f)) - continue; - - ofaces[oface_num.getAttribute(f)].push_back(i); - - MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin(); - - for (; edge_iter != f->end(); ++edge_iter) { - int index = vertexToIndex_map[edge_iter->vert]; - vi[index].push_back(i); - } - } - - uint quadverts[4] = {0, 0, 0, 0}; - // go over each set of faces which belong to an original face - std::vector< std::vector<uint> >::const_iterator fii; - uint orig = 0; - for (fii=ofaces.begin(); fii!=ofaces.end(); ++fii, ++orig) { - std::vector<uint> fl = *fii; - // go over a single set from an original face - while (fl.size() > 0) { - // remove one new face - uint findex = fl.back(); - fl.pop_back(); - - MeshSet<3>::face_t *f = *(poly->faceBegin() + findex); - - // for each vertex of this face, check other faces containing - // that vertex to see if there is a neighbor also belonging to - // the original face - uint result = 0; - - MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin(); - for (; edge_iter != f->end(); ++edge_iter) { - int v = vertexToIndex_map[edge_iter->vert]; - for (uint pos2=0; !result && pos2 < vi[v].size();pos2++) { - - // if we find the current face, ignore it - uint otherf = vi[v][pos2]; - if (findex == otherf) - continue; - - MeshSet<3>::face_t *f2 = *(poly->faceBegin() + otherf); - - // if other face doesn't have the same original face, - // ignore it also - uint other_orig = oface_num.getAttribute(f2); - if (orig != other_orig) - continue; - - // if, for some reason, we don't find the other face in - // the current set of faces, ignore it - uint other_index = 0; - while (other_index < fl.size() && fl[other_index] != otherf) ++other_index; - if (other_index == fl.size()) continue; - - // see if the faces share an edge - result = quadMerge(&vertexToIndex_map, poly->vertex_storage, f, f2, v, quadverts); - // if faces can be merged, then remove the other face - // from the current set - if (result) { - uint replace = fl.back(); - fl.pop_back(); - if(otherf != replace) - fl[other_index] = replace; - } - } - } - - // add all information except vertices to the output mesh - outputMesh->FaceSet().push_back(BSP_MFace()); - BSP_MFace& outFace = outputMesh->FaceSet().back(); - outFace.m_verts.clear(); - outFace.m_plane.setValue(f->plane.N.v); - outFace.m_orig_face = orig; - - // if we merged faces, use the list of common vertices; otherwise - // use the faces's vertices - if (result) { - // make quat using verts stored in result - outFace.m_verts.push_back(quadverts[0]); - outFace.m_verts.push_back(quadverts[1]); - outFace.m_verts.push_back(quadverts[2]); - outFace.m_verts.push_back(quadverts[3]); - } else { - MeshSet<3>::face_t::edge_iter_t edge_iter = f->begin(); - for (; edge_iter != f->end(); ++edge_iter) { - //int index = ofacevert_num.getAttribute(f, edge_iter.idx()); - int index = vertexToIndex_map[edge_iter->vert]; - outFace.m_verts.push_back( index ); - } - } - } - } - - // Build the mesh edges using topological informtion - outputMesh->BuildEdges(); - - return outputMesh; -} - -static void meshSetMinMax(const MeshSet<3> *mesh, - carve::geom3d::Vector *min, - carve::geom3d::Vector *max) -{ - for (uint i = 0; i < mesh->vertex_storage.size(); ++i) { - min->x = MIN(min->x, mesh->vertex_storage[i].v.x); - min->y = MIN(min->y, mesh->vertex_storage[i].v.y); - min->z = MIN(min->z, mesh->vertex_storage[i].v.z); - max->x = MAX(max->x, mesh->vertex_storage[i].v.x); - max->y = MAX(max->y, mesh->vertex_storage[i].v.y); - max->z = MAX(max->z, mesh->vertex_storage[i].v.z); - } -} - -static void getRescaleMinMax(const MeshSet<3> *left, - const MeshSet<3> *right, - carve::geom3d::Vector *min, - carve::geom3d::Vector *max) -{ - min->x = max->x = left->vertex_storage[0].v.x; - min->y = max->y = left->vertex_storage[0].v.y; - min->z = max->z = left->vertex_storage[0].v.z; - - meshSetMinMax(left, min, max); - meshSetMinMax(right, min, max); - - // Make sure we don't scale object with zer oscale - if ((min->x - max->x) < DBL_EPSILON) { - min->x = -1.0; - max->x = 1.0; - } - if ((min->y - max->y) < DBL_EPSILON) { - min->y = -1.0; - max->y = 1.0; - } - if ((min->z - max->z) < DBL_EPSILON) { - min->z = -1.0; - max->z = 1.0; - } -} - -/** - * Performs a generic booleam operation, the entry point for external modules. - * @param opType Boolean operation type BOP_INTERSECTION, BOP_UNION, BOP_DIFFERENCE - * @param outputMesh Output mesh, the final result (the object C) - * @param obAFaces Object A faces list - * @param obAVertices Object A vertices list - * @param obBFaces Object B faces list - * @param obBVertices Object B vertices list - * @param interpFunc Interpolating function - * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR - */ -BoolOpState BOP_performBooleanOperation(BoolOpType opType, - BSP_CSGMesh** outputMesh, - CSG_FaceIteratorDescriptor obAFaces, - CSG_VertexIteratorDescriptor obAVertices, - CSG_FaceIteratorDescriptor obBFaces, - CSG_VertexIteratorDescriptor obBVertices) -{ - carve::csg::CSG::OP op; - MeshSet<3> *left, *right, *output = NULL; - carve::csg::CSG csg; - carve::geom3d::Vector min, max; - carve::interpolate::FaceAttr<uint> oface_num; - uint num_origfaces = 0; - - switch (opType) { - case BOP_UNION: - op = carve::csg::CSG::UNION; - break; - case BOP_INTERSECTION: - op = carve::csg::CSG::INTERSECTION; - break; - case BOP_DIFFERENCE: - op = carve::csg::CSG::A_MINUS_B; - break; - default: - return BOP_ERROR; - } - - left = Carve_addMesh(obAFaces, obAVertices, oface_num, num_origfaces ); - right = Carve_addMesh(obBFaces, obBVertices, oface_num, num_origfaces ); - - getRescaleMinMax(left, right, &min, &max); - - carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z); - carve::rescale::fwd fwd_r(scaler); - carve::rescale::rev rev_r(scaler); - - left->transform(fwd_r); - right->transform(fwd_r); - - // prepare operands for actual boolean operation. it's needed because operands might consist of - // several intersecting meshes and in case if another operands intersect an edge loop of intersecting that - // meshes tessellation of operation result can't be done properly. the only way to make such situations - // working is to union intersecting meshes of the same operand - Carve_unionIntersections(&left, &right, oface_num); - - if(left->meshes.size() == 0 || right->meshes.size()==0) { - // normally sohuldn't happen (zero-faces objects are handled by modifier itself), but - // unioning intersecting meshes which doesn't have consistent normals might lead to - // empty result which wouldn't work here - - delete left; - delete right; - - return BOP_ERROR; - } - - csg.hooks.registerHook(new carve::csg::CarveTriangulator, carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT); - - oface_num.installHooks(csg); - - try { - output = csg.compute(left, right, op, NULL, carve::csg::CSG::CLASSIFY_EDGE); - } - catch(carve::exception e) { - std::cerr << "CSG failed, exception " << e.str() << std::endl; - } - catch(...) { - delete left; - delete right; - - throw "Unknown error in Carve library"; - } - - delete left; - delete right; - - if(!output) - return BOP_ERROR; - - output->transform(rev_r); - - *outputMesh = Carve_exportMesh(output, oface_num, num_origfaces); - delete output; - - return BOP_OK; -} diff --git a/intern/bsp/intern/BOP_Interface.h b/intern/bsp/intern/BOP_Interface.h deleted file mode 100644 index c7402388a29..00000000000 --- a/intern/bsp/intern/BOP_Interface.h +++ /dev/null @@ -1,47 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file BOP_Interface.h - * \ingroup bsp - */ - -#ifndef __BOP_INTERFACE_H__ -#define __BOP_INTERFACE_H__ - -#include "BSP_CSGMesh.h" - -typedef enum EnumBoolOpState {BOP_OK, BOP_NO_SOLID, BOP_ERROR} BoolOpState; -typedef enum EnumBoolOpType {BOP_INTERSECTION=e_csg_intersection, BOP_UNION=e_csg_union, BOP_DIFFERENCE=e_csg_difference} BoolOpType; - -BoolOpState BOP_performBooleanOperation(BoolOpType opType, - BSP_CSGMesh** outputMesh, - CSG_FaceIteratorDescriptor obAFaces, - CSG_VertexIteratorDescriptor obAVertices, - CSG_FaceIteratorDescriptor obBFaces, - CSG_VertexIteratorDescriptor obBVertices); - -#endif diff --git a/intern/bsp/intern/BSP_CSGException.h b/intern/bsp/intern/BSP_CSGException.h deleted file mode 100644 index 744359c1078..00000000000 --- a/intern/bsp/intern/BSP_CSGException.h +++ /dev/null @@ -1,59 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/BSP_CSGException.h - * \ingroup bsp - */ - - -#ifndef __BSP_CSGEXCEPTION_H__ -#define __BSP_CSGEXCEPTION_H__ - -// stick in more error types as you think of them - -enum BSP_ExceptionType{ - e_split_error, - e_mesh_error, - e_mesh_input_error, - e_param_error, - e_tree_build_error -}; - - -class BSP_CSGException { -public : - BSP_ExceptionType m_e_type; - - BSP_CSGException ( - BSP_ExceptionType type - ) : m_e_type (type) - { - } -}; - -#endif - diff --git a/intern/bsp/intern/BSP_CSGMesh.cpp b/intern/bsp/intern/BSP_CSGMesh.cpp deleted file mode 100644 index 4dda7741f67..00000000000 --- a/intern/bsp/intern/BSP_CSGMesh.cpp +++ /dev/null @@ -1,659 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/BSP_CSGMesh.cpp - * \ingroup bsp - */ - - - -#include "BSP_CSGMesh.h" -#include "MT_assert.h" -#include "CTR_TaggedSetOps.h" -#include "MT_Plane3.h" -#include "BSP_CSGException.h" - -// for insert_iterator -#include <iterator> - -// for vector reverse -#include <iostream> -#include <algorithm> -using namespace std; - -BSP_CSGMesh:: -BSP_CSGMesh( -) : - MEM_RefCountable() -{ - m_verts = NULL; - m_faces = NULL; - m_edges = NULL; -} - - BSP_CSGMesh * -BSP_CSGMesh:: -New( -){ - return new BSP_CSGMesh(); -} - - BSP_CSGMesh * -BSP_CSGMesh:: -NewCopy( -) const { - - BSP_CSGMesh *mesh = New(); - if (mesh == NULL) return NULL; - - mesh->m_bbox_max = m_bbox_max; - mesh->m_bbox_min = m_bbox_min; - - if (m_edges != NULL) { - mesh->m_edges = new vector<BSP_MEdge>(*m_edges); - if (mesh->m_edges == NULL) { - delete mesh; - return NULL; - } - } - if (m_verts != NULL) { - mesh->m_verts = new vector<BSP_MVertex>(*m_verts); - if (mesh->m_verts == NULL) { - if (m_edges != NULL) free(mesh->m_edges); - delete mesh; - return NULL; - } - } - if (m_faces != NULL) { - mesh->m_faces = new vector<BSP_MFace>(*m_faces); - if (mesh->m_faces == NULL) { - delete mesh; - return NULL; - } - } - - return mesh; -} - - void -BSP_CSGMesh:: -Invert( -){ - - vector<BSP_MFace> & faces = FaceSet(); - - vector<BSP_MFace>::const_iterator faces_end = faces.end(); - vector<BSP_MFace>::iterator faces_it = faces.begin(); - - for (; faces_it != faces_end; ++faces_it) { - faces_it->Invert(); - } -} - - bool -BSP_CSGMesh:: -SetVertices( - vector<BSP_MVertex> *verts -){ - if (verts == NULL) return false; - - // create polygon and edge arrays and reserve some space. - m_faces = new vector<BSP_MFace>; - if (!m_faces) return false; - - m_faces->reserve(verts->size()/2); - - // previous verts get deleted here. - m_verts = verts; - return true; -} - - void -BSP_CSGMesh:: -AddPolygon( - const int * verts, - int num_verts -){ - MT_assert(verts != NULL); - MT_assert(num_verts >=3); - - if (verts == NULL || num_verts <3) return; - - // make a polyscone from these vertex indices. - - const BSP_FaceInd fi = m_faces->size(); - m_faces->push_back(BSP_MFace()); - BSP_MFace & face = m_faces->back(); - - insert_iterator<vector<BSP_VertexInd> > insert_point(face.m_verts,face.m_verts.end()); - copy (verts,verts + num_verts,insert_point); - - // compute and store the plane equation for this face. - - MT_Plane3 face_plane = FacePlane(fi); - face.m_plane = face_plane; -}; - -// assumes that the face already has a plane equation - void -BSP_CSGMesh:: -AddPolygon( - const BSP_MFace &face -){ - m_faces->push_back(face); -}; - - - bool -BSP_CSGMesh:: -BuildEdges( -){ - - if (m_faces == NULL) return false; - - if (m_edges != NULL) { - DestroyEdges(); - } - - m_edges = new vector<BSP_MEdge>; - - if (m_edges == NULL) { - return false; - } - - - //iterate through the face set and add edges for all polygon - //edges - - vector<BSP_MFace>::const_iterator f_it_end = FaceSet().end(); - vector<BSP_MFace>::iterator f_it_begin = FaceSet().begin(); - vector<BSP_MFace>::iterator f_it = FaceSet().begin(); - - vector<BSP_EdgeInd> dummy; - - for (;f_it != f_it_end; ++f_it) { - - BSP_MFace & face = *f_it; - - int vertex_num = face.m_verts.size(); - BSP_VertexInd prev_vi(face.m_verts[vertex_num-1]); - - for (int vert = 0; vert < vertex_num; ++vert) { - - BSP_FaceInd fi(size_t (f_it - f_it_begin)); - InsertEdge(prev_vi,face.m_verts[vert],fi,dummy); - prev_vi = face.m_verts[vert]; - } - - } - dummy.clear(); - return true; -} - - void -BSP_CSGMesh:: -DestroyEdges( -){ - if ( m_edges != NULL ) { - delete m_edges; - m_edges = NULL; - } - - // Run through the vertices - // and clear their edge arrays. - - if (m_verts){ - - vector<BSP_MVertex>::const_iterator vertex_end = VertexSet().end(); - vector<BSP_MVertex>::iterator vertex_it = VertexSet().begin(); - - for (; vertex_it != vertex_end; ++vertex_it) { - vertex_it->m_edges.clear(); - } - } -} - - - BSP_EdgeInd -BSP_CSGMesh:: -FindEdge( - const BSP_VertexInd & v1, - const BSP_VertexInd & v2 -) const { - - vector<BSP_MVertex> &verts = VertexSet(); - vector<BSP_MEdge> &edges = EdgeSet(); - - BSP_MEdge e; - e.m_verts[0] = v1; - e.m_verts[1] = v2; - - vector<BSP_EdgeInd> &v1_edges = verts[v1].m_edges; - vector<BSP_EdgeInd>::const_iterator v1_end = v1_edges.end(); - vector<BSP_EdgeInd>::const_iterator v1_begin = v1_edges.begin(); - - for (; v1_begin != v1_end; ++v1_begin) { - if (edges[*v1_begin] == e) return *v1_begin; - } - - return BSP_EdgeInd::Empty(); -} - - void -BSP_CSGMesh:: -InsertEdge( - const BSP_VertexInd & v1, - const BSP_VertexInd & v2, - const BSP_FaceInd & f, - vector<BSP_EdgeInd> &new_edges -){ - - MT_assert(!v1.IsEmpty()); - MT_assert(!v2.IsEmpty()); - MT_assert(!f.IsEmpty()); - - if (v1.IsEmpty() || v2.IsEmpty() || f.IsEmpty()) { - BSP_CSGException e(e_mesh_error); - throw (e); - } - - vector<BSP_MVertex> &verts = VertexSet(); - vector<BSP_MEdge> &edges = EdgeSet(); - - BSP_EdgeInd e; - - e = FindEdge(v1,v2); - if (e.IsEmpty()) { - // This edge does not exist -- make a new one - - BSP_MEdge temp_e; - temp_e.m_verts[0] = v1; - temp_e.m_verts[1] = v2; - - e = m_edges->size(); - // set the face index from the edge back to this polygon. - temp_e.m_faces.push_back(f); - - m_edges->push_back(temp_e); - - // add the edge index to it's vertices - verts[v1].AddEdge(e); - verts[v2].AddEdge(e); - - new_edges.push_back(e); - - } else { - - // edge already exists - // insure that there is no polygon already - // attached to the other side of this edge - // swap the empty face pointer in edge with f - - BSP_MEdge &edge = edges[e]; - - // set the face index from the edge back to this polygon. - edge.m_faces.push_back(f); - } -} - - -// geometry access -////////////////// - - vector<BSP_MVertex> & -BSP_CSGMesh:: -VertexSet( -) const { - return *m_verts; -} - - vector<BSP_MFace> & -BSP_CSGMesh:: -FaceSet( -) const { - return *m_faces; -} - - vector<BSP_MEdge> & -BSP_CSGMesh:: -EdgeSet( -) const { - return *m_edges; -} - -BSP_CSGMesh:: -~BSP_CSGMesh( -){ - if ( m_verts != NULL ) delete m_verts; - if ( m_faces != NULL ) delete m_faces; - if ( m_edges != NULL ) delete m_edges; -} - -// local geometry queries. -///////////////////////// - -// face queries -/////////////// - - void -BSP_CSGMesh:: -FaceVertices( - const BSP_FaceInd & f, - vector<BSP_VertexInd> &output -){ - vector<BSP_MFace> & face_set = FaceSet(); - output.insert( - output.end(), - face_set[f].m_verts.begin(), - face_set[f].m_verts.end() - ); -} - - - void -BSP_CSGMesh:: -FaceEdges( - const BSP_FaceInd & fi, - vector<BSP_EdgeInd> &output -){ - // take intersection of the edges emminating from all the vertices - // of this polygon; - - vector<BSP_MFace> &faces = FaceSet(); - vector<BSP_MEdge> &edges = EdgeSet(); - - const BSP_MFace & f = faces[fi]; - - // collect vertex edges; - - vector<BSP_VertexInd>::const_iterator face_verts_it = f.m_verts.begin(); - vector<BSP_VertexInd>::const_iterator face_verts_end = f.m_verts.end(); - - vector< vector<BSP_EdgeInd> > vertex_edges(f.m_verts.size()); - - int vector_slot = 0; - - for (;face_verts_it != face_verts_end; ++face_verts_it, ++vector_slot) { - VertexEdges(*face_verts_it,vertex_edges[vector_slot]); - } - - int prev = vector_slot - 1; - - // intersect pairs of edge sets - - for (int i = 0; i < vector_slot;i++) { - CTR_TaggedSetOps<BSP_EdgeInd,BSP_MEdge>::IntersectPair(vertex_edges[prev],vertex_edges[i],edges,output); - prev = i; - } - - // should always have 3 or more unique edges per face. - MT_assert(output.size() >=3); - - if (output.size() < 3) { - BSP_CSGException e(e_mesh_error); - throw(e); - } -}; - -// edge queries -/////////////// - - void -BSP_CSGMesh:: -EdgeVertices( - const BSP_EdgeInd & e, - vector<BSP_VertexInd> &output -){ - const vector<BSP_MEdge> &edges = EdgeSet(); - output.push_back(edges[e].m_verts[0]); - output.push_back(edges[e].m_verts[1]); -} - - void -BSP_CSGMesh:: -EdgeFaces( - const BSP_EdgeInd & e, - vector<BSP_FaceInd> &output -){ - - vector<BSP_MEdge> & edge_set = EdgeSet(); - output.insert( - output.end(), - edge_set[e].m_faces.begin(), - edge_set[e].m_faces.end() - ); - -} - -// vertex queries -///////////////// - - void -BSP_CSGMesh:: -VertexEdges( - const BSP_VertexInd &v, - vector<BSP_EdgeInd> &output -){ - - vector<BSP_MVertex> & vertex_set = VertexSet(); - output.insert( - output.end(), - vertex_set[v].m_edges.begin(), - vertex_set[v].m_edges.end() - ); -} - - void -BSP_CSGMesh:: -VertexFaces( - const BSP_VertexInd &vi, - vector<BSP_FaceInd> &output -) { - - vector<BSP_MEdge> &edges = EdgeSet(); - vector<BSP_MFace> &faces = FaceSet(); - vector<BSP_MVertex> &verts = VertexSet(); - - const vector<BSP_EdgeInd> &v_edges = verts[vi].m_edges; - vector<BSP_EdgeInd>::const_iterator e_it = v_edges.begin(); - - for (; e_it != v_edges.end(); ++e_it) { - - BSP_MEdge &e = edges[*e_it]; - - // iterate through the faces of this edge - push unselected - // edges to output and then select the edge - - vector<BSP_FaceInd>::const_iterator e_faces_end = e.m_faces.end(); - vector<BSP_FaceInd>::iterator e_faces_it = e.m_faces.begin(); - - for (;e_faces_it != e_faces_end; ++e_faces_it) { - - if (!faces[*e_faces_it].SelectTag()) { - output.push_back(*e_faces_it); - faces[*e_faces_it].SetSelectTag(true); - } - } - } - - // deselect selected faces. - vector<BSP_FaceInd>::iterator f_it = output.begin(); - - for (; f_it != output.end(); ++f_it) { - faces[*f_it].SetSelectTag(false); - } -} - - bool -BSP_CSGMesh:: -SC_Face( - BSP_FaceInd f -){ - - - -#if 0 - { - // check area is greater than zero. - - vector<BSP_MVertex> & verts = VertexSet(); - - vector<BSP_VertexInd> f_verts; - FaceVertices(f,f_verts); - - MT_assert(f_verts.size() >= 3); - - BSP_VertexInd root = f_verts[0]; - - MT_Scalar area = 0; - - for (int i=2; i < f_verts.size(); i++) { - MT_Vector3 a = verts[root].m_pos; - MT_Vector3 b = verts[f_verts[i-1]].m_pos; - MT_Vector3 c = verts[f_verts[i]].m_pos; - - MT_Vector3 l1 = b-a; - MT_Vector3 l2 = c-b; - - area += (l1.cross(l2)).length()/2; - } - - MT_assert(!MT_fuzzyZero(area)); - } -#endif - // Check coplanarity -#if 0 - MT_Plane3 plane = FacePlane(f); - - const BSP_MFace & face = FaceSet()[f]; - vector<BSP_VertexInd>::const_iterator f_verts_it = face.m_verts.begin(); - vector<BSP_VertexInd>::const_iterator f_verts_end = face.m_verts.end(); - - for (;f_verts_it != f_verts_end; ++f_verts_it) { - MT_Scalar dist = plane.signedDistance( - VertexSet()[*f_verts_it].m_pos - ); - - MT_assert(fabs(dist) < BSP_SPLIT_EPSILON); - } -#endif - - - // Check connectivity - - vector<BSP_EdgeInd> f_edges; - FaceEdges(f,f_edges); - - MT_assert(f_edges.size() == FaceSet()[f].m_verts.size()); - - unsigned int i; - for (i = 0; i < f_edges.size(); ++i) { - - int matches = 0; - for (unsigned int j = 0; j < EdgeSet()[f_edges[i]].m_faces.size(); j++) { - - if (EdgeSet()[f_edges[i]].m_faces[j] == f) matches++; - } - - MT_assert(matches == 1); - - } - return true; -} - - MT_Plane3 -BSP_CSGMesh:: -FacePlane( - const BSP_FaceInd & fi -) const{ - - const BSP_MFace & f0 = FaceSet()[fi]; - - // Have to be a bit careful here coz the poly may have - // a lot of parallel edges. Should walk round the polygon - // and check length of cross product. - - const MT_Vector3 & p1 = VertexSet()[f0.m_verts[0]].m_pos; - const MT_Vector3 & p2 = VertexSet()[f0.m_verts[1]].m_pos; - - int face_size = f0.m_verts.size(); - MT_Vector3 n; - - for (int i = 2 ; i <face_size; i++) { - const MT_Vector3 & pi = VertexSet()[f0.m_verts[i]].m_pos; - - MT_Vector3 l1 = p2-p1; - MT_Vector3 l2 = pi-p2; - n = l1.cross(l2); - MT_Scalar length = n.length(); - - if (!MT_fuzzyZero(length)) { - n = n * (1/length); - break; - } - } - return MT_Plane3(n,p1); -} - - void -BSP_CSGMesh:: -ComputeFacePlanes( -){ - - int fsize = FaceSet().size(); - int i=0; - for (i = 0; i < fsize; i++) { - - FaceSet()[i].m_plane = FacePlane(i); - } -}; - - - int -BSP_CSGMesh:: -CountTriangles( -) const { - - // Each polygon of n sides can be partitioned into n-3 triangles. - // So we just go through and sum this function of polygon size. - - vector<BSP_MFace> & face_set = FaceSet(); - - vector<BSP_MFace>::const_iterator face_it = face_set.begin(); - vector<BSP_MFace>::const_iterator face_end = face_set.end(); - - int sum = 0; - - for (;face_it != face_end; face_it++) { - - // Should be careful about degenerate faces here. - sum += face_it->m_verts.size() - 2; - } - - return sum; -} - diff --git a/intern/bsp/intern/BSP_CSGMesh.h b/intern/bsp/intern/BSP_CSGMesh.h deleted file mode 100644 index 4754f3bdc71..00000000000 --- a/intern/bsp/intern/BSP_CSGMesh.h +++ /dev/null @@ -1,249 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/BSP_CSGMesh.h - * \ingroup bsp - */ - - -#ifndef __BSP_CSGMESH_H__ -#define __BSP_CSGMESH_H__ - -#include "BSP_MeshPrimitives.h" -#include "MEM_SmartPtr.h" -#include "MEM_RefCountPtr.h" -#include "MEM_NonCopyable.h" -#include "../extern/CSG_BooleanOps.h" - - -class MT_Plane3; - -class BSP_CSGMesh : - public MEM_NonCopyable, - public MEM_RefCountable -{ - -public : - - static - BSP_CSGMesh * - New( - ); - - bool - SetVertices( - std::vector<BSP_MVertex> *verts - ); - - void - AddPolygon( - const int * verts, - int num_verts - ); - - // assumes that the face already has a plane equation - void - AddPolygon( - const BSP_MFace &face - ); - - - // Allocate and build the mesh edges. - //////////////////////////////////// - - bool - BuildEdges( - ); - - // Clean the mesh of edges. and edge pointers - // This removes the circular connectivity information - ///////////////////////////////////////////// - - void - DestroyEdges( - ); - - // return a new separate copy of the - // mesh allocated on the heap. - - BSP_CSGMesh * - NewCopy( - ) const; - - - // Reverse the winding order of every polygon - // in the mesh and swap the planes around. - - void - Invert( - ); - - - // geometry access - ////////////////// - - std::vector<BSP_MVertex> & - VertexSet( - ) const; - std::vector<BSP_MFace> & - FaceSet( - ) const; - - std::vector<BSP_MEdge> & - EdgeSet( - ) const; - - ~BSP_CSGMesh( - ); - - // local geometry queries. - ///////////////////////// - - // face queries - /////////////// - - void - FaceVertices( - const BSP_FaceInd & f, - std::vector<BSP_VertexInd> &output - ); - - void - FaceEdges( - const BSP_FaceInd & f, - std::vector<BSP_EdgeInd> &output - ); - - // edge queries - /////////////// - - void - EdgeVertices( - const BSP_EdgeInd & e, - std::vector<BSP_VertexInd> &output - ); - - void - EdgeFaces( - const BSP_EdgeInd & e, - std::vector<BSP_FaceInd> &output - ); - - // vertex queries - ///////////////// - - void - VertexEdges( - const BSP_VertexInd & v, - std::vector<BSP_EdgeInd> &output - ); - - void - VertexFaces( - const BSP_VertexInd & v, - std::vector<BSP_FaceInd> &output - ); - - // Returns the edge index of the edge from v1 to v2. - // Does this by searching the edge sets of v1 - but not v2. - // If you are paranoid you should check both and make sure the - // indices are the same. If the edge doe not exist edgeInd is empty. - - BSP_EdgeInd - FindEdge( - const BSP_VertexInd &v1, - const BSP_VertexInd &v2 - ) const; - - - /** - * Sanity checkers - */ - - // make sure the edge faces have a pointer to f - - bool - SC_Face( - BSP_FaceInd f - ); - - /** - * Return the face plane equation - */ - - MT_Plane3 - FacePlane( - const BSP_FaceInd &fi - )const; - - - /** - * Recompute Face plane equations. - * essential if you have been messing with the object. - */ - - void - ComputeFacePlanes( - ); - - /** - * Count the number of trinagles in the mesh. - * This is not the same as the number of polygons. - */ - - int - CountTriangles( - ) const; - -private : - - void - InsertEdge( - const BSP_VertexInd &v1, - const BSP_VertexInd &v2, - const BSP_FaceInd &f, - std::vector<BSP_EdgeInd> &new_edges - ); - - - // Private to insure heap instantiation. - - BSP_CSGMesh( - ); - - std::vector<BSP_MVertex> *m_verts; - std::vector<BSP_MFace> *m_faces; - std::vector<BSP_MEdge> *m_edges; - - MT_Vector3 m_bbox_min; - MT_Vector3 m_bbox_max; - -}; - - -#endif - diff --git a/intern/bsp/intern/BSP_CSGMesh_CFIterator.h b/intern/bsp/intern/BSP_CSGMesh_CFIterator.h deleted file mode 100644 index 928d04eda20..00000000000 --- a/intern/bsp/intern/BSP_CSGMesh_CFIterator.h +++ /dev/null @@ -1,272 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/BSP_CSGMesh_CFIterator.h - * \ingroup bsp - */ - - -#ifndef __BSP_CSGMESH_CFITERATOR_H__ - -#define __BSP_CSGMESH_CFITERATOR_H__ - -#include "BSP_CSGMesh.h" -#include "../extern/CSG_BooleanOps.h" -/** - * This class defines 2 C style iterators over a CSG mesh, one for - * vertices and 1 for faces. They conform to the iterator interface - * defined in CSG_BooleanOps.h - */ - -struct BSP_CSGMesh_VertexIt { - BSP_CSGMesh *mesh; - BSP_MVertex * pos; -}; - - -inline - void -BSP_CSGMesh_VertexIt_Destruct( - CSG_VertexIteratorDescriptor * iterator -) { - delete ((BSP_CSGMesh_VertexIt *)(iterator->it)); - iterator->it = NULL; - iterator->Done = NULL; - iterator->Fill = NULL; - iterator->Reset = NULL; - iterator->Step = NULL; - iterator->num_elements = 0; -}; - - -inline - int -BSP_CSGMesh_VertexIt_Done( - CSG_IteratorPtr it -) { - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_VertexIt * vertex_it = (BSP_CSGMesh_VertexIt *)it; - - /* dereferencing iterator::end() is illegal, so we dereference 1 before it */ - /* also check that vector is not empty */ - if (vertex_it->mesh->VertexSet().size() && - vertex_it->pos <= &(*(vertex_it->mesh->VertexSet().end() -1) )) return 0; - return 1; -}; - -inline - void -BSP_CSGMesh_VertexIt_Fill( - CSG_IteratorPtr it, - CSG_IVertex *vert -) { - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_VertexIt * vertex_it = (BSP_CSGMesh_VertexIt *)it; - - vertex_it->pos->m_pos.getValue(vert->position); -}; - -inline - void -BSP_CSGMesh_VertexIt_Step( - CSG_IteratorPtr it -) { - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_VertexIt * vertex_it = (BSP_CSGMesh_VertexIt *)it; - - ++(vertex_it->pos); -}; - -inline - void -BSP_CSGMesh_VertexIt_Reset( - CSG_IteratorPtr it -) { - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_VertexIt * vertex_it = (BSP_CSGMesh_VertexIt *)it; - vertex_it->pos = &vertex_it->mesh->VertexSet()[0]; -}; - -inline - void -BSP_CSGMeshVertexIt_Construct( - BSP_CSGMesh *mesh, - CSG_VertexIteratorDescriptor *output -){ - // user should have insured mesh is not equal to NULL. - - output->Done = BSP_CSGMesh_VertexIt_Done; - output->Fill = BSP_CSGMesh_VertexIt_Fill; - output->Step = BSP_CSGMesh_VertexIt_Step; - output->Reset = BSP_CSGMesh_VertexIt_Reset; - output->num_elements = mesh->VertexSet().size(); - - BSP_CSGMesh_VertexIt * v_it = new BSP_CSGMesh_VertexIt; - v_it->mesh = mesh; - if ( output->num_elements > 0 ) - v_it->pos = &mesh->VertexSet()[0]; - output->it = v_it; -} - - -/** - * Face iterator. - */ - -struct BSP_CSGMesh_FaceIt { - BSP_CSGMesh *mesh; - BSP_MFace *pos; - int face_triangle; -}; - - -inline - void -BSP_CSGMesh_FaceIt_Destruct( - CSG_FaceIteratorDescriptor *iterator -) { - delete ((BSP_CSGMesh_FaceIt *)(iterator->it)); - iterator->it = NULL; - iterator->Done = NULL; - iterator->Fill = NULL; - iterator->Reset = NULL; - iterator->Step = NULL; - iterator->num_elements = 0; -}; - - -inline - int -BSP_CSGMesh_FaceIt_Done( - CSG_IteratorPtr it -) { - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_FaceIt * face_it = (BSP_CSGMesh_FaceIt *)it; - - /* dereferencing iterator::end() is illegal, so we dereference 1 before it */ - /* also check that vector is not empty */ - if (face_it->mesh->FaceSet().size() && - face_it->pos <= &(*(face_it->mesh->FaceSet().end() -1))) { - if (face_it->face_triangle + 3 <= (int)face_it->pos->m_verts.size()) { - return 0; - } - } - return 1; -}; - -inline - void -BSP_CSGMesh_FaceIt_Fill( - CSG_IteratorPtr it, - CSG_IFace *face -){ - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_FaceIt * face_it = (BSP_CSGMesh_FaceIt *)it; - // essentially iterating through a triangle fan here. - - if (face_it->pos->m_verts.size()>3) { - // QUAD - face->vertex_index[0] = int(face_it->pos->m_verts[0]); - face->vertex_index[1] = int(face_it->pos->m_verts[1]); - face->vertex_index[2] = int(face_it->pos->m_verts[2]); - face->vertex_index[3] = int(face_it->pos->m_verts[3]); - - face->orig_face = face_it->pos->m_orig_face; - - face->vertex_number = 4; - } - else { - // TRIANGLE - face->vertex_index[0] = int(face_it->pos->m_verts[0]); - face->vertex_index[1] = int(face_it->pos->m_verts[1]); - face->vertex_index[2] = int(face_it->pos->m_verts[2]); - - face->orig_face = face_it->pos->m_orig_face; - - face->vertex_number = 3; - } -}; - -inline - void -BSP_CSGMesh_FaceIt_Step( - CSG_IteratorPtr it -) { - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_FaceIt * face_it = (BSP_CSGMesh_FaceIt *)it; - - /* dereferencing iterator::end() is illegal, so we dereference 1 before it */ - /* also check that vector is not empty */ - if (face_it->mesh->FaceSet().size() && - face_it->pos <= &(*(face_it->mesh->FaceSet().end() -1))) { - - //if (face_it->face_triangle + 3 < face_it->pos->m_verts.size()) { - // (face_it->face_triangle)++; - //} else { - face_it->face_triangle = 0; - (face_it->pos) ++; - //} - } -}; - -inline - void -BSP_CSGMesh_FaceIt_Reset( - CSG_IteratorPtr it -) { - // assume CSG_IteratorPtr is of the correct type. - BSP_CSGMesh_FaceIt * f_it = (BSP_CSGMesh_FaceIt *)it; - f_it->pos = &f_it->mesh->FaceSet()[0]; - f_it->face_triangle = 0; -}; - -inline - void -BSP_CSGMesh_FaceIt_Construct( - BSP_CSGMesh * mesh, - CSG_FaceIteratorDescriptor *output -) { - - output->Done = BSP_CSGMesh_FaceIt_Done; - output->Fill = BSP_CSGMesh_FaceIt_Fill; - output->Step = BSP_CSGMesh_FaceIt_Step; - output->Reset = BSP_CSGMesh_FaceIt_Reset; - - output->num_elements = mesh->FaceSet().size(); - - BSP_CSGMesh_FaceIt * f_it = new BSP_CSGMesh_FaceIt; - f_it->mesh = mesh; - if( output->num_elements > 0 ) - f_it->pos = &mesh->FaceSet()[0]; - f_it->face_triangle = 0; - - output->it = f_it; -}; - - -#endif - diff --git a/intern/bsp/intern/BSP_MeshPrimitives.cpp b/intern/bsp/intern/BSP_MeshPrimitives.cpp deleted file mode 100644 index f79fcbdd1eb..00000000000 --- a/intern/bsp/intern/BSP_MeshPrimitives.cpp +++ /dev/null @@ -1,298 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/BSP_MeshPrimitives.cpp - * \ingroup bsp - */ - - -#include "BSP_MeshPrimitives.h" - -#include "MT_assert.h" -#include "BSP_CSGException.h" -#include <algorithm> - -using namespace std; - -BSP_MVertex:: -BSP_MVertex( -) : - m_pos (MT_Point3()), - m_select_tag (false), - m_open_tag (0) -{ -}; - -BSP_MVertex:: -BSP_MVertex( - const MT_Point3 & pos -) : - m_pos(pos), - m_select_tag (false), - m_open_tag (0) -{ -}; - - - bool -BSP_MVertex:: -RemoveEdge( - BSP_EdgeInd e -){ - vector<BSP_EdgeInd>::iterator result = find(m_edges.begin(),m_edges.end(),e); - if (result == m_edges.end()) { - return false; - } - BSP_EdgeInd last = m_edges.back(); - m_edges.pop_back(); - if (m_edges.empty()) return true; - - *result = last; - return true; -} - - void -BSP_MVertex:: -AddEdge( - BSP_EdgeInd e -){ - m_edges.push_back(e); -} - - void -BSP_MVertex:: -SwapEdge( - BSP_EdgeInd e_old, - BSP_EdgeInd e_new -){ - vector<BSP_EdgeInd>::iterator result = - find(m_edges.begin(),m_edges.end(),e_old); - if (result == m_edges.end()) { - BSP_CSGException e(e_mesh_error); - throw(e); - MT_assert(false); - } - - *result = e_new; -} - - bool -BSP_MVertex:: -SelectTag( -) const{ - return m_select_tag; -} - - void -BSP_MVertex:: -SetSelectTag( - bool tag -){ - m_select_tag = tag; -} - - int -BSP_MVertex:: -OpenTag( -) const { - return m_open_tag; -} - - void -BSP_MVertex:: -SetOpenTag( - int tag -){ - m_open_tag = tag; -} - - -/** - * Edge Primitive Methods. - */ - -BSP_MEdge:: -BSP_MEdge( -){ - m_verts[0] = m_verts[1] = BSP_VertexInd::Empty(); -} - - bool -BSP_MEdge:: -operator == ( - BSP_MEdge & rhs -){ - // edges are the same if their vertex indices are the - // same!!! Other properties are not checked - - int matches = 0; - - if (this->m_verts[0] == rhs.m_verts[0]) { - ++matches; - } - if (this->m_verts[1] == rhs.m_verts[0]) { - ++matches; - } - if (this->m_verts[0] == rhs.m_verts[1]) { - ++matches; - } - if (this->m_verts[1] == rhs.m_verts[1]) { - ++matches; - } - - if (matches >= 2) { - return true; - } - return false; -} - - void -BSP_MEdge:: -SwapFace( - BSP_FaceInd old_f, - BSP_FaceInd new_f -){ - vector<BSP_FaceInd>::iterator result = - find(m_faces.begin(),m_faces.end(),old_f); - if (result == m_faces.end()) { - BSP_CSGException e(e_mesh_error); - throw(e); - MT_assert(false); - } - - *result = new_f; -} - - BSP_VertexInd -BSP_MEdge:: -OpVertex( - BSP_VertexInd vi -) const { - if (vi == m_verts[0]) return m_verts[1]; - if (vi == m_verts[1]) return m_verts[0]; - MT_assert(false); - BSP_CSGException e(e_mesh_error); - throw(e); - - return BSP_VertexInd::Empty(); -} - - bool -BSP_MEdge:: -SelectTag( -) const { - return bool(m_verts[1].Tag() & 0x1); -} - void -BSP_MEdge:: -SetSelectTag( - bool tag -){ - m_verts[1].SetTag(int(tag)); -} - - int -BSP_MEdge:: -OpenTag( -) const { - return m_verts[0].Tag(); -} - - void -BSP_MEdge:: -SetOpenTag( - int tag -) { - // Note conversion from int to unsigned int!!!!! - m_verts[0].SetTag(tag); -} - - -/** - * Face primitive methods - */ - - -BSP_MFace:: -BSP_MFace( -): - m_open_tag(-1), - m_orig_face(0) -{ - // nothing to do -} - - void -BSP_MFace:: -Invert( -){ - - // TODO replace reverse as I think some compilers - // do not support the STL routines employed. - - reverse( - m_verts.begin(), - m_verts.end() - ); - - // invert the normal - m_plane.Invert(); -} - - bool -BSP_MFace:: -SelectTag( -) const { - return bool(m_verts[1].Tag() & 0x1); -} - - void -BSP_MFace:: -SetSelectTag( - bool tag -){ - m_verts[1].SetTag(int(tag)); -}; - - int -BSP_MFace:: -OpenTag( -) const { - return m_open_tag; -} - - void -BSP_MFace:: -SetOpenTag( - int tag -){ - // Note conversion from int to unsigned int!!!!! - m_open_tag = tag; -} - - - diff --git a/intern/bsp/intern/BSP_MeshPrimitives.h b/intern/bsp/intern/BSP_MeshPrimitives.h deleted file mode 100644 index f4d04d8863e..00000000000 --- a/intern/bsp/intern/BSP_MeshPrimitives.h +++ /dev/null @@ -1,280 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/BSP_MeshPrimitives.h - * \ingroup bsp - */ - - -#ifndef __BSP_MESHPRIMITIVES_H__ -#define __BSP_MESHPRIMITIVES_H__ - -#include "CTR_TaggedIndex.h" -#include "MT_Vector3.h" -#include "MT_Plane3.h" - -#include <vector> - -typedef CTR_TaggedIndex<24,0x00ffffff> BSP_VertexInd; -typedef CTR_TaggedIndex<24,0x00ffffff> BSP_EdgeInd; -typedef CTR_TaggedIndex<24,0x00ffffff> BSP_FaceInd; -typedef CTR_TaggedIndex<24,0x00ffffff> BSP_FragInd; - - -typedef std::vector<BSP_VertexInd> BSP_VertexList; -typedef std::vector<BSP_EdgeInd> BSP_EdgeList; -typedef std::vector<BSP_FaceInd> BSP_FaceList; - -/** - * Enum representing classification of primitives - * with respect to a hyperplane. - */ - -enum BSP_Classification{ - e_unclassified = 0, - e_classified_in = 1, - e_classified_out = 2, - e_classified_on = 4, - e_classified_spanning = 7 -}; - -/** - * @section Mesh linkage - * The mesh is linked in a similar way to the decimation mesh, - * although the primitives are a little more general and not - * limited to manifold meshes. - * Vertices -> (2+)Edges - * Edges -> (1+)Polygons - * Edges -> (2)Vertices. - * Polygons -> (3+)Vertices. - * - * this structure allows for arbitrary polygons (assumed to be convex). - * Edges can point to more than 2 polygons (non-manifold) - * - * We also define 2 different link types between edges and their - * neighbouring polygons. A weak link and a strong link. - * A weak link means the polygon is in a different mesh fragment - * to the other polygon. A strong link means the polygon is in the - * same fragment. - * This is not entirely consistent as it means edges have to be associated - * with fragments, in reality only polygons will be - edges and vertices - * will live in global pools. I guess we should mark edges as being on plane - * boundaries. This leaves a problem with non-manifold edges because for example - * 3 of 4 possible edges could lie in 1 fragment and the remaining edge lie in - * another, there is no way to work out then from one polygon which neighbouring - * polygons are in the same/different mesh fragment. - * - * By definition an edge will only ever lie on 1 hyperplane. We can then just - * tag neighbouring polygons with one of 3 tags to group them. - */ - -class BSP_MVertex { -public : - MT_Point3 m_pos; - BSP_EdgeList m_edges; - - /** - * TODO - * Is this boolean necessary or can we nick a few bits of m_edges[0] - * for example? - * The only problem with this is that if the vertex is degenerate then - * m_edges[0] may not exist. If the algorithm guarentees that this is - * not the case then it should be changed. - */ - - bool m_select_tag; - int m_open_tag; - - BSP_MVertex( - ); - - BSP_MVertex( - const MT_Point3 & pos - ); - - BSP_MVertex & - operator = ( - const BSP_MVertex & other - ) { - m_pos = other.m_pos; - m_edges = other.m_edges; - m_select_tag = other.m_select_tag; - m_open_tag = other.m_open_tag; - return (*this); - }; - - bool - RemoveEdge( - BSP_EdgeInd e - ); - - void - AddEdge( - BSP_EdgeInd e - ); - - void - SwapEdge( - BSP_EdgeInd e_old, - BSP_EdgeInd e_new - ); - - /** - * These operations are ONLY valid when the - * vertex has some edges associated with it. - * This is left to the user to guarentee. - * Also note that these tag's are not guarenteed - * to survive after a call to RemoveEdge(), - * because we use edges for the open tag. - */ - - int - OpenTag( - ) const; - - void - SetOpenTag( - int tag - ); - - bool - SelectTag( - ) const; - - void - SetSelectTag( - bool tag - ); -}; - -class BSP_MEdge { -public : - BSP_VertexInd m_verts[2]; - BSP_FaceList m_faces; - - BSP_MEdge( - ); - - bool operator == ( - BSP_MEdge & rhs - ); - - void - SwapFace( - BSP_FaceInd old_f, - BSP_FaceInd new_f - ); - - BSP_VertexInd - OpVertex( - BSP_VertexInd vi - ) const; - - bool - SelectTag( - ) const; - - void - SetSelectTag( - bool tag - ); - - /** - * We use one of the vertex indices for tag informtaion. - * This means these tags will not survive if you change - * the vertex indices. - */ - - int - OpenTag( - ) const; - - void - SetOpenTag( - int tag - ) ; -}; - -class BSP_MFace { -public : - - BSP_VertexList m_verts; - - // We also store the plane equation of this - // face. Generating on the fly during tree - // construction can lead to a lot of numerical errors. - // because the polygon size can get very small. - - MT_Plane3 m_plane; - - int m_open_tag; - unsigned int m_orig_face; - - BSP_MFace( - ); - - // Invert the face , done by reversing the vertex order - // and inverting the face normal. - - void - Invert( - ); - - /** - * Tagging - * We use the tag from m_verts[1] for the select tag - * and the the tag from m_verts[0] for the open tag. - * There is always a chance that the polygon contains - * no vertices but this should be checked at construction - * time. - * Also note that changing the vertex indices of this polygon - * will likely remove tagging information. - * - */ - - bool - SelectTag( - ) const; - - void - SetSelectTag( - bool tag - ); - - int - OpenTag( - ) const; - - void - SetOpenTag( - int tag - ) ; - -}; - -#endif - diff --git a/intern/bsp/intern/CSG_BooleanOps.cpp b/intern/bsp/intern/CSG_BooleanOps.cpp deleted file mode 100644 index f74dfc3c253..00000000000 --- a/intern/bsp/intern/CSG_BooleanOps.cpp +++ /dev/null @@ -1,180 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file bsp/intern/CSG_BooleanOps.cpp - * \ingroup bsp - */ - - -/** - * Implementation of external api for CSG part of BSP lib interface. - */ - -#include "../extern/CSG_BooleanOps.h" -#include "BSP_CSGMesh_CFIterator.h" -#include "MEM_RefCountPtr.h" - -#include "BOP_Interface.h" -#include <iostream> -using namespace std; - -#include "BSP_MeshPrimitives.h" - -struct BSP_MeshInfo { - BSP_CSGMesh *output_mesh; -}; - -using namespace std; - - CSG_BooleanOperation * -CSG_NewBooleanFunction( - void -){ - BSP_MeshInfo * mesh_info = new BSP_MeshInfo; - CSG_BooleanOperation * output = new CSG_BooleanOperation; - - if (mesh_info==NULL || output==NULL) return NULL; - - mesh_info->output_mesh = NULL; - output->CSG_info = mesh_info; - - return output; -} - -/** - * Compute the boolean operation, UNION, INTERSECION or DIFFERENCE - */ - int -CSG_PerformBooleanOperation( - CSG_BooleanOperation *operation, - CSG_OperationType op_type, - CSG_FaceIteratorDescriptor obAFaces, - CSG_VertexIteratorDescriptor obAVertices, - CSG_FaceIteratorDescriptor obBFaces, - CSG_VertexIteratorDescriptor obBVertices -){ - if (operation == NULL) return 0; - BSP_MeshInfo * mesh_info = static_cast<BSP_MeshInfo *>(operation->CSG_info); - if (mesh_info == NULL) return 0; - - obAFaces.Reset(obAFaces.it); - obBFaces.Reset(obBFaces.it); - obAVertices.Reset(obAVertices.it); - obBVertices.Reset(obBVertices.it); - - BoolOpType boolType; - - switch (op_type) { - case e_csg_union: - boolType = BOP_UNION; - break; - case e_csg_difference: - boolType = BOP_DIFFERENCE; - break; - default: - boolType = BOP_INTERSECTION; - break; - } - - BoolOpState boolOpResult; - try { - boolOpResult = BOP_performBooleanOperation( boolType, - (BSP_CSGMesh**) &(mesh_info->output_mesh), - obAFaces, obAVertices, obBFaces, obBVertices); - } - catch(...) { - return 0; - } - - switch (boolOpResult) { - case BOP_OK: return 1; - case BOP_NO_SOLID: return -2; - case BOP_ERROR: return 0; - default: return 1; - } -} - - int -CSG_OutputFaceDescriptor( - CSG_BooleanOperation * operation, - CSG_FaceIteratorDescriptor * output -){ - if (operation == NULL) return 0; - BSP_MeshInfo * mesh_info = static_cast<BSP_MeshInfo *>(operation->CSG_info); - - if (mesh_info == NULL) return 0; - if (mesh_info->output_mesh == NULL) return 0; - - BSP_CSGMesh_FaceIt_Construct(mesh_info->output_mesh,output); - return 1; -} - - - int -CSG_OutputVertexDescriptor( - CSG_BooleanOperation * operation, - CSG_VertexIteratorDescriptor *output -){ - if (operation == NULL) return 0; - BSP_MeshInfo * mesh_info = static_cast<BSP_MeshInfo *>(operation->CSG_info); - - if (mesh_info == NULL) return 0; - if (mesh_info->output_mesh == NULL) return 0; - - BSP_CSGMeshVertexIt_Construct(mesh_info->output_mesh,output); - return 1; -} - - void -CSG_FreeVertexDescriptor( - CSG_VertexIteratorDescriptor * v_descriptor -){ - BSP_CSGMesh_VertexIt_Destruct(v_descriptor); -} - - - void -CSG_FreeFaceDescriptor( - CSG_FaceIteratorDescriptor * f_descriptor -){ - BSP_CSGMesh_FaceIt_Destruct(f_descriptor); -} - - - void -CSG_FreeBooleanOperation( - CSG_BooleanOperation *operation -){ - if (operation != NULL) { - BSP_MeshInfo * mesh_info = static_cast<BSP_MeshInfo *>(operation->CSG_info); - - delete (mesh_info->output_mesh); - delete(mesh_info); - delete(operation); - } -} - diff --git a/intern/container/CMakeLists.txt b/intern/container/CMakeLists.txt index 8adc46a59de..4743247af26 100644 --- a/intern/container/CMakeLists.txt +++ b/intern/container/CMakeLists.txt @@ -35,8 +35,6 @@ set(INC_SYS set(SRC CTR_HashedPtr.h CTR_Map.h - CTR_TaggedIndex.h - CTR_TaggedSetOps.h ) # infact nothing to compile! diff --git a/intern/container/CTR_TaggedIndex.h b/intern/container/CTR_TaggedIndex.h deleted file mode 100644 index e03bfdea819..00000000000 --- a/intern/container/CTR_TaggedIndex.h +++ /dev/null @@ -1,210 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file container/CTR_TaggedIndex.h - * \ingroup ctr - */ - -#ifndef __CTR_TAGGEDINDEX_H__ -#define __CTR_TAGGEDINDEX_H__ - -/** - * This class is supposed to be a simple tagged index class. If these - * were indices into a mesh then we would never need 32 bits for such indices. - * It is often handy to have a few extra bits around to mark objects etc. We - * steal a few bits of CTR_TaggedIndex objects for this purpose. From the outside - * it will behave like a standard unsigned int but just carry the extra tag - * information around with it. - */ - -#include <functional> - -#include "../../source/blender/blenlib/BLI_sys_types.h" - -enum { - empty_tag = 0x0, - empty_index = 0xffffffff -}; - -template < - int tag_shift, - int index_mask -> class CTR_TaggedIndex { -public: - CTR_TaggedIndex( - ) : - m_val ((empty_tag << tag_shift) | (empty_index & index_mask)) - { - } - - CTR_TaggedIndex( - const int val - ) : - m_val ((val & index_mask) | ((empty_tag << tag_shift) & (~index_mask))) { - } - - CTR_TaggedIndex( - const unsigned int val - ) : - m_val ((val & index_mask) | ((empty_tag << tag_shift) & (~index_mask))) { - } - - CTR_TaggedIndex( - const long int val - ) : - m_val ( ((long int) val & index_mask) - | ( (empty_tag << tag_shift) - & (~index_mask)) ) { - } - - CTR_TaggedIndex( - const long unsigned int val - ) : - m_val ( ((long unsigned int)val & index_mask) - | ( (empty_tag << tag_shift) - & (~index_mask) ) ) { - } - - -#if defined(_WIN64) - CTR_TaggedIndex( - const uint64_t val - ) : - m_val ( ((uint64_t)val & index_mask) - | ( (empty_tag << tag_shift) - & (~index_mask) ) ) { - } -#endif - - CTR_TaggedIndex( - const CTR_TaggedIndex &my_index - ): - m_val(my_index.m_val) - { - } - - bool - operator == ( - const CTR_TaggedIndex& rhs - ) const { - - return ((this->m_val & index_mask) == (rhs.m_val & index_mask)); - } - - operator unsigned int () const { - return m_val & index_mask; - } - - operator unsigned long int () const { - return (unsigned long int)(m_val & index_mask); - } - - operator int () const { - return int(m_val & index_mask); - } - - operator long int () const { - return (long int)(m_val & index_mask); - } - -#if defined(_WIN64) - operator uint64_t () const { - return (uint64_t)(m_val & index_mask); - } -#endif - - bool - IsEmpty( - ) const { - return ((m_val & index_mask) == (empty_index & index_mask)); - } - - - static - CTR_TaggedIndex - Empty( - ) { - return CTR_TaggedIndex(); - } - - void - Invalidate( - ) { - m_val = (empty_tag << tag_shift) | (empty_index & index_mask); - } - - - unsigned int - Tag ( - ) const { - return m_val >> tag_shift; - } - - void - SetTag( - unsigned int tag - ) { - m_val = (m_val & index_mask) | ((tag << tag_shift) & (~index_mask)); - } - - void - EmptyTag( - ) { - m_val = (m_val & index_mask) | ((empty_tag << tag_shift) & (~index_mask)); - } - - bool - IsEmptyTag( - ) const { - return (Tag() == Empty().Tag()); - } - - /* functionals */ - - struct greater : std::binary_function<CTR_TaggedIndex, CTR_TaggedIndex, bool> - { - bool - operator()( - const CTR_TaggedIndex& a, - const CTR_TaggedIndex& b - ) const { - return (int(a) > int(b)); - } - }; - - -private : - CTR_TaggedIndex( - const CTR_TaggedIndex *index - ) {}; - - unsigned int m_val; - - -}; - -#endif /* __CTR_TAGGEDINDEX_H__ */ diff --git a/intern/container/CTR_TaggedSetOps.h b/intern/container/CTR_TaggedSetOps.h deleted file mode 100644 index 6ebf20b77bf..00000000000 --- a/intern/container/CTR_TaggedSetOps.h +++ /dev/null @@ -1,300 +0,0 @@ -/* - * ***** BEGIN GPL LICENSE BLOCK ***** - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, - * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. - * - * ***** END GPL LICENSE BLOCK ***** - */ - -/** \file container/CTR_TaggedSetOps.h - * \ingroup ctr - */ - - -#ifndef __CTR_TAGGEDSETOPS_H__ -#define __CTR_TAGGEDSETOPS_H__ - -#include "MEM_NonCopyable.h" -#include <vector> - -/** - * This class contains some utility functions for finding the intersection, - * union, and difference of a collection of stl vector of indices into - * a set of primitives. - * - * These are mainly used as helper functions in the decimation and bsp - * libraries. - * - * This template class assumes that each value of type IndexType encountered - * in the list is a valid index into an array of primitives. This is not - * checked at run-time and is left to the user to insure. Prmitives of - * type ObjectType must have the following public methods to be used by - * this template class: - * - * int - * OpenTag(void) --- return a persistent tag value for the primitive - * - * void - * SetOpenTag(int bla) --- set the persistent tag value for this primitive to bla. - * - * bool - * SelectTag() --- return a persistent boolean tag for this primitive - * - * void - * SetSelectTag(bool bla) --- set the persistent boolean tag for this primitive to bla. - * - * Here persistent means that the tag should be associated with the object for the - * entire lifetime of the primitive. Again none of this stuff is enforced you have - * to make sure that your primitives do the right thing. Often these tags can be - * cunningly stowed away inside some of the spare bits in the primitive. See - * CTR_TaggedIndex for such a class. - * - */ - -template -<class IndexType, class ObjectType> -class CTR_TaggedSetOps : public MEM_NonCopyable { - -public : - - static - void - Intersect( - const std::vector< std::vector<IndexType> > &index_list, - std::vector<ObjectType> &primitives, - std::vector<IndexType> &output, - unsigned int mask, - unsigned int shift - ) { - - /* iterate through vectors in index_list - * iterate through individual members of each vector - * mark each obejct that the index points to */ - - typename std::vector< std::vector<IndexType> >::const_iterator - last_vector = index_list.end(); - typename std::vector< std::vector<IndexType> >::const_iterator - start_vector = index_list.begin(); - - /* FIXME some temporary space */ - - std::vector<IndexType> temp_union; - temp_union.reserve(64); - - int tag_num = 0; - - for (; start_vector != last_vector; ++start_vector) { - - typename std::vector<IndexType>::const_iterator - last_index = start_vector->end(); - typename std::vector<IndexType>::const_iterator - start_index = start_vector->begin(); - - for (; start_index != last_index; ++start_index) { - - ObjectType & prim = primitives[*start_index]; - - if (!prim.OpenTag()) { - /* compute the union */ - temp_union.push_back(*start_index); - } - int tag = prim.OpenTag(); - tag = (tag & mask) >> shift; - tag += 1; - prim.SetOpenTag((prim.OpenTag() & ~mask)| ((tag << shift) & mask)); - } - - ++tag_num; - } - - /* now iterate through the union and pull out all those with the right tag */ - - typename std::vector<IndexType>::const_iterator last_index = - temp_union.end(); - typename std::vector<IndexType>::const_iterator start_index = - temp_union.begin(); - - for (; start_index != last_index; ++start_index) { - - ObjectType & prim = primitives[*start_index]; - - if (prim.OpenTag() == tag_num) { - /* it's part of the intersection! */ - - output.push_back(*start_index); - /* because we're iterating through the union - * it's safe to remove the tag at this point */ - - prim.SetOpenTag(prim.OpenTag() & ~mask); - } - } - }; - - /* note not a strict set intersection! - * if x appears twice in b and is part of the intersection - * it will appear twice in the intersection */ - - static - void - IntersectPair( - const std::vector<IndexType> &a, - const std::vector<IndexType> &b, - std::vector<ObjectType> &primitives, - std::vector<IndexType> &output - ) { - - typename std::vector<IndexType>::const_iterator last_index = - a.end(); - typename std::vector<IndexType>::const_iterator start_index = - a.begin(); - - for (; start_index != last_index; ++start_index) { - ObjectType & prim = primitives[*start_index]; - prim.SetSelectTag(true); - } - last_index = b.end(); - start_index = b.begin(); - - for (; start_index != last_index; ++start_index) { - ObjectType & prim = primitives[*start_index]; - if (prim.SelectTag()) { - output.push_back(*start_index); - } - } - /* deselect */ - last_index = a.end(); - start_index = a.begin(); - - for (; start_index != last_index; ++start_index) { - ObjectType & prim = primitives[*start_index]; - prim.SetSelectTag(false); - } - }; - - - static - void - Union( - std::vector< std::vector<IndexType> > &index_list, - std::vector<ObjectType> &primitives, - std::vector<IndexType> &output - ) { - - /* iterate through vectors in index_list - * iterate through individual members of each vector - * mark each obejct that the index points to */ - - typename std::vector< std::vector<IndexType> >::const_iterator - last_vector = index_list.end(); - typename std::vector< std::vector<IndexType> >::iterator - start_vector = index_list.begin(); - - for (; start_vector != last_vector; ++start_vector) { - - typename std::vector<IndexType>::const_iterator - last_index = start_vector->end(); - typename std::vector<IndexType>::iterator - start_index = start_vector->begin(); - - for (; start_index != last_index; ++start_index) { - - ObjectType & prim = primitives[*start_index]; - - if (!prim.SelectTag()) { - /* compute the union */ - output.push_back(*start_index); - prim.SetSelectTag(true); - } - } - } - - /* now iterate through the union and reset the tags */ - - typename std::vector<IndexType>::const_iterator last_index = - output.end(); - typename std::vector<IndexType>::iterator start_index = - output.begin(); - - for (; start_index != last_index; ++start_index) { - - ObjectType & prim = primitives[*start_index]; - prim.SetSelectTag(false); - } - } - - - static - void - Difference( - std::vector< IndexType> &a, - std::vector< IndexType> &b, - std::vector<ObjectType> &primitives, - std::vector< IndexType> &output - ) { - - /* iterate through b mark all - * iterate through a and add to output all unmarked */ - - typename std::vector<IndexType>::const_iterator last_index = - b.end(); - typename std::vector<IndexType>::iterator start_index = - b.begin(); - - for (; start_index != last_index; ++start_index) { - - ObjectType & prim = primitives[*start_index]; - prim.SetSelectTag(true); - } - - last_index = a.end(); - start_index = a.begin(); - - for (; start_index != last_index; ++start_index) { - - ObjectType & prim = primitives[*start_index]; - if (!prim.SelectTag()) { - output.push_back(*start_index); - } - } - - /* clean up the tags */ - - last_index = b.end(); - start_index = b.begin(); - - for (; start_index != last_index; ++start_index) { - - ObjectType & prim = primitives[*start_index]; - prim.SetSelectTag(false); - } - }; - -private : - - /* private constructor - this class is not meant for - * instantiation */ - - CTR_TaggedSetOps(); - -}; - -#endif /* __CTR_TAGGEDSETOPS_H__ */ diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 81dafded1da..2a0f642996d 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -384,12 +384,6 @@ if(WITH_MOD_OCEANSIM) add_definitions(-DWITH_OCEANSIM) endif() -if(WITH_MOD_BOOLEAN) - list(APPEND INC - ../../../intern/bsp/extern - ) -endif() - if(WITH_JACK) add_definitions(-DWITH_JACK) endif() diff --git a/source/blender/blenkernel/SConscript b/source/blender/blenkernel/SConscript index 5e5dea1c163..25f8422afed 100644 --- a/source/blender/blenkernel/SConscript +++ b/source/blender/blenkernel/SConscript @@ -47,7 +47,6 @@ incs = [ '#/extern/bullet2/src', '#/extern/glew/include', '#/intern/audaspace/intern', - '#/intern/bsp/extern', '#/intern/elbeem/extern', '#/intern/iksolver/extern', '#/intern/smoke/extern', diff --git a/source/blender/blenlib/BLI_polyfill2d.h b/source/blender/blenlib/BLI_polyfill2d.h index 40ac4cc0ad0..d434e1b82b9 100644 --- a/source/blender/blenlib/BLI_polyfill2d.h +++ b/source/blender/blenlib/BLI_polyfill2d.h @@ -21,6 +21,8 @@ #ifndef __BLI_POLYFILL2D_H__ #define __BLI_POLYFILL2D_H__ +struct MemArena; + void BLI_polyfill_calc_ex( const float (*coords)[2], const unsigned int count, diff --git a/source/blender/modifiers/CMakeLists.txt b/source/blender/modifiers/CMakeLists.txt index 6a8eac6ee48..7b43f9899b8 100644 --- a/source/blender/modifiers/CMakeLists.txt +++ b/source/blender/modifiers/CMakeLists.txt @@ -114,7 +114,7 @@ if(WITH_MOD_BOOLEAN) intern/MOD_boolean_util.c ) list(APPEND INC - ../../../intern/bsp/extern + ../../../extern/carve ) endif() diff --git a/source/blender/modifiers/SConscript b/source/blender/modifiers/SConscript index 86e1970ab6b..5eb62a06148 100644 --- a/source/blender/modifiers/SConscript +++ b/source/blender/modifiers/SConscript @@ -33,7 +33,6 @@ incs = [ '.', './intern', '#/intern/guardedalloc', - '#/intern/bsp/extern', '#/intern/elbeem/extern', '#/extern/glew/include', '#/intern/opennl/extern', diff --git a/source/blender/modifiers/intern/MOD_boolean.c b/source/blender/modifiers/intern/MOD_boolean.c index 71a8074c698..49c0c091dee 100644 --- a/source/blender/modifiers/intern/MOD_boolean.c +++ b/source/blender/modifiers/intern/MOD_boolean.c @@ -139,10 +139,6 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *ob, result = get_quick_derivedMesh(derivedData, dm, bmd->operation); if (result == NULL) { - - DM_ensure_tessface(dm); /* BMESH - UNTIL MODIFIER IS UPDATED FOR MPoly */ - DM_ensure_tessface(derivedData); /* BMESH - UNTIL MODIFIER IS UPDATED FOR MPoly */ - // TIMEIT_START(NewBooleanDerivedMesh) result = NewBooleanDerivedMesh(dm, bmd->object, derivedData, ob, diff --git a/source/blender/modifiers/intern/MOD_boolean_util.c b/source/blender/modifiers/intern/MOD_boolean_util.c index 9c8109c7856..3607c946be3 100644 --- a/source/blender/modifiers/intern/MOD_boolean_util.c +++ b/source/blender/modifiers/intern/MOD_boolean_util.c @@ -18,531 +18,712 @@ * The Original Code is Copyright (C) Blender Foundation * All rights reserved. * - * The Original Code is: all of this file. - * - * Contributor(s): none yet. + * Contributor(s): Sergey Sharybin. * * ***** END GPL LICENSE BLOCK ***** - * CSG operations. */ /** \file blender/modifiers/intern/MOD_boolean_util.c * \ingroup modifiers */ - #include "DNA_material_types.h" -#include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" +#include "DNA_modifier_types.h" #include "DNA_object_types.h" -#include "DNA_scene_types.h" #include "MEM_guardedalloc.h" -#include "BLI_math.h" #include "BLI_utildefines.h" -#include "BLI_listbase.h" +#include "BLI_alloca.h" #include "BLI_ghash.h" +#include "BLI_math.h" +#include "BLI_polyfill2d.h" #include "BKE_cdderivedmesh.h" -#include "BKE_depsgraph.h" -#include "BKE_global.h" #include "BKE_material.h" -#include "BKE_mesh.h" -#include "BKE_object.h" - -#include "CSG_BooleanOps.h" #include "MOD_boolean_util.h" -/** - * Here's the vertex iterator structure used to walk through - * the blender vertex structure. +#include "carve-capi.h" + +/* Adopted from BM_loop_interp_from_face(), + * + * Transform matrix is used in cases when target coordinate needs + * to be converted to source space (namely when interpolating + * boolean result loops from second operand). + * + * TODO(sergey): Consider making it a generic function in DerivedMesh.c. */ +static void DM_loop_interp_from_poly(DerivedMesh *source_dm, + MVert *source_mverts, + MLoop *source_mloops, + MPoly *source_poly, + DerivedMesh *target_dm, + MVert *target_mverts, + MLoop *target_mloop, + float transform[4][4], + int target_loop_index) +{ + float (*cos_3d)[3] = BLI_array_alloca(cos_3d, source_poly->totloop); + int *source_indices = BLI_array_alloca(source_indices, source_poly->totloop); + float *weights = BLI_array_alloca(weights, source_poly->totloop); + int i; + int target_vert_index = target_mloop[target_loop_index].v; + float coord[3]; + + for (i = 0; i < source_poly->totloop; ++i) { + MLoop *mloop = &source_mloops[source_poly->loopstart + i]; + source_indices[i] = source_poly->loopstart + i; + copy_v3_v3(cos_3d[i], source_mverts[mloop->v].co); + } -typedef struct { - DerivedMesh *dm; - Object *ob; - int pos; -} VertexIt; + if (transform) { + mul_v3_m4v3(coord, transform, target_mverts[target_vert_index].co); + } + else { + copy_v3_v3(coord, target_mverts[target_vert_index].co); + } -/** - * Implementations of local vertex iterator functions. - * These describe a blender mesh to the CSG module. - */ + interp_weights_poly_v3(weights, cos_3d, source_poly->totloop, coord); + + DM_interp_loop_data(source_dm, target_dm, source_indices, weights, + source_poly->totloop, target_loop_index); +} + +/* **** Importer from derived mesh to Carve **** */ -static void VertexIt_Destruct(CSG_VertexIteratorDescriptor *iterator) +typedef struct ImportMeshData { + DerivedMesh *dm; + float obmat[4][4]; + MVert *mvert; + MEdge *medge; + MLoop *mloop; + MPoly *mpoly; +} ImportMeshData; + +/* Get number of vertices. */ +static int importer_GetNumVerts(ImportMeshData *import_data) { - if (iterator->it) { - /* deallocate memory for iterator */ - MEM_freeN(iterator->it); - iterator->it = NULL; - } - iterator->Done = NULL; - iterator->Fill = NULL; - iterator->Reset = NULL; - iterator->Step = NULL; - iterator->num_elements = 0; + DerivedMesh *dm = import_data->dm; + return dm->getNumVerts(dm); +} -} +/* Get number of edges. */ +static int importer_GetNumEdges(ImportMeshData *import_data) +{ + DerivedMesh *dm = import_data->dm; + return dm->getNumEdges(dm); +} -static int VertexIt_Done(CSG_IteratorPtr it) +/* Get number of loops. */ +static int importer_GetNumLoops(ImportMeshData *import_data) { - VertexIt *iterator = (VertexIt *)it; - return(iterator->pos >= iterator->dm->getNumVerts(iterator->dm)); + DerivedMesh *dm = import_data->dm; + return dm->getNumLoops(dm); } -static void VertexIt_Fill(CSG_IteratorPtr it, CSG_IVertex *vert) +/* Get number of polys. */ +static int importer_GetNumPolys(ImportMeshData *import_data) { - VertexIt *iterator = (VertexIt *)it; - MVert *verts = iterator->dm->getVertArray(iterator->dm); + DerivedMesh *dm = import_data->dm; + return dm->getNumPolys(dm); +} - float global_pos[3]; +/* Get 3D coordinate of vertex with given index. */ +static void importer_GetVertCoord(ImportMeshData *import_data, int vert_index, float coord[3]) +{ + MVert *mvert = import_data->mvert; - /* boolean happens in global space, transform both with obmat */ - mul_v3_m4v3( - global_pos, - iterator->ob->obmat, - verts[iterator->pos].co - ); + BLI_assert(vert_index >= 0 && vert_index < import_data->dm->getNumVerts(import_data->dm)); - vert->position[0] = global_pos[0]; - vert->position[1] = global_pos[1]; - vert->position[2] = global_pos[2]; + mul_v3_m4v3(coord, import_data->obmat, mvert[vert_index].co); } -static void VertexIt_Step(CSG_IteratorPtr it) -{ - VertexIt *iterator = (VertexIt *)it; - iterator->pos++; -} - -static void VertexIt_Reset(CSG_IteratorPtr it) +/* Get index of vertices which are adjucent to edge specified by it's index. */ +static void importer_GetEdgeVerts(ImportMeshData *import_data, int edge_index, int *v1, int *v2) { - VertexIt *iterator = (VertexIt *)it; - iterator->pos = 0; + MEdge *medge = &import_data->medge[edge_index]; + + BLI_assert(edge_index >= 0 && edge_index < import_data->dm->getNumEdges(import_data->dm)); + + *v1 = medge->v1; + *v2 = medge->v2; } -static void VertexIt_Construct(CSG_VertexIteratorDescriptor *output, DerivedMesh *dm, Object *ob) +/* Get number of adjucent vertices to the poly specified by it's index. */ +static int importer_GetPolyNumVerts(ImportMeshData *import_data, int poly_index) { + MPoly *mpoly = import_data->mpoly; - VertexIt *it; - if (output == NULL) return; + BLI_assert(poly_index >= 0 && poly_index < import_data->dm->getNumPolys(import_data->dm)); - /* allocate some memory for blender iterator */ - it = (VertexIt *)(MEM_mallocN(sizeof(VertexIt), "Boolean_VIt")); - if (it == NULL) { - return; + return mpoly[poly_index].totloop; +} + +/* Get list of adjucent vertices to the poly specified by it's index. */ +static void importer_GetPolyVerts(ImportMeshData *import_data, int poly_index, int *verts) +{ + MPoly *mpoly = &import_data->mpoly[poly_index]; + MLoop *mloop = import_data->mloop + mpoly->loopstart; + int i; + BLI_assert(poly_index >= 0 && poly_index < import_data->dm->getNumPolys(import_data->dm)); + for (i = 0; i < mpoly->totloop; i++, mloop++) { + verts[i] = mloop->v; } - /* assign blender specific variables */ - it->dm = dm; - it->ob = ob; /* needed for obmat transformations */ - - it->pos = 0; - - /* assign iterator function pointers. */ - output->Step = VertexIt_Step; - output->Fill = VertexIt_Fill; - output->Done = VertexIt_Done; - output->Reset = VertexIt_Reset; - output->num_elements = it->dm->getNumVerts(it->dm); - output->it = it; } -/** - * Blender Face iterator - */ +// Triangulate 2D polygon. +#if 0 +static int importer_triangulate2DPoly(ImportMeshData *UNUSED(import_data), + const float (*vertices)[2], int num_vertices, + unsigned int (*triangles)[3]) +{ + // TODO(sergey): Currently import_data is unused but in the future we could + // put memory arena there which will reduce amount of allocations happening + // over the triangulation period. + // + // However that's not so much straighforward to do it right now because we + // also are tu consider threaded import/export. -typedef struct { - DerivedMesh *dm; - int pos; - int offset; - int flip; -} FaceIt; + BLI_assert(num_vertices > 3); -static void FaceIt_Destruct(CSG_FaceIteratorDescriptor *iterator) -{ - MEM_freeN(iterator->it); - iterator->Done = NULL; - iterator->Fill = NULL; - iterator->Reset = NULL; - iterator->Step = NULL; - iterator->num_elements = 0; + BLI_polyfill_calc(vertices, num_vertices, triangles); + + return num_vertices - 2; } +#endif -static int FaceIt_Done(CSG_IteratorPtr it) +static CarveMeshImporter MeshImporter = { + importer_GetNumVerts, + importer_GetNumEdges, + importer_GetNumLoops, + importer_GetNumPolys, + importer_GetVertCoord, + importer_GetEdgeVerts, + importer_GetPolyNumVerts, + importer_GetPolyVerts, + + /* TODO(sergey): We don't use BLI_polyfill_calc() because it tends + * to generate degenerated geometry which is fatal for booleans. + * + * For now we stick to Carve's triangulation. + */ + NULL, /* importer_triangulate2DPoly */ +}; + +/* **** Exporter from Carve to derived mesh **** */ + +typedef struct ExportMeshData { + DerivedMesh *dm; + float obimat[4][4]; + MVert *mvert; + MEdge *medge; + MLoop *mloop; + MPoly *mpoly; + int *vert_origindex; + int *edge_origindex; + int *poly_origindex; + int *loop_origindex; + + /* Objects and derived meshes of left and right operands. + * Used for custom data merge and interpolation. + */ + Object *ob_left; + Object *ob_right; + DerivedMesh *dm_left; + DerivedMesh *dm_right; + MVert *mvert_left; + MLoop *mloop_left; + MPoly *mpoly_left; + MVert *mvert_right; + MLoop *mloop_right; + MPoly *mpoly_right; + + float left_to_right_mat[4][4]; + + /* Hash to map materials from right object to result. */ + GHash *material_hash; +} ExportMeshData; + +BLI_INLINE Object *which_object(ExportMeshData *export_data, int which_mesh) { - /* assume CSG_IteratorPtr is of the correct type. */ - FaceIt *iterator = (FaceIt *)it; - return(iterator->pos >= iterator->dm->getNumTessFaces(iterator->dm)); + Object *object = NULL; + switch (which_mesh) { + case CARVE_MESH_LEFT: + object = export_data->ob_left; + break; + case CARVE_MESH_RIGHT: + object = export_data->ob_right; + break; + } + return object; } -static void FaceIt_Fill(CSG_IteratorPtr it, CSG_IFace *face) +BLI_INLINE DerivedMesh *which_dm(ExportMeshData *export_data, int which_mesh) { - /* assume CSG_IteratorPtr is of the correct type. */ - FaceIt *face_it = (FaceIt *)it; - MFace *mfaces = face_it->dm->getTessFaceArray(face_it->dm); - MFace *mface = &mfaces[face_it->pos]; - - /* reverse face vertices if necessary */ - face->vertex_index[1] = mface->v2; - if (face_it->flip == 0) { - face->vertex_index[0] = mface->v1; - face->vertex_index[2] = mface->v3; - } - else { - face->vertex_index[2] = mface->v1; - face->vertex_index[0] = mface->v3; + DerivedMesh *dm = NULL; + switch (which_mesh) { + case CARVE_MESH_LEFT: + dm = export_data->dm_left; + break; + case CARVE_MESH_RIGHT: + dm = export_data->dm_right; + break; } - if (mface->v4) { - face->vertex_index[3] = mface->v4; - face->vertex_number = 4; + return dm; +} + +BLI_INLINE MVert *which_mvert(ExportMeshData *export_data, int which_mesh) +{ + MVert *mvert = NULL; + switch (which_mesh) { + case CARVE_MESH_LEFT: + mvert = export_data->mvert_left; + break; + case CARVE_MESH_RIGHT: + mvert = export_data->mvert_right; + break; } - else { - face->vertex_number = 3; + return mvert; +} + +BLI_INLINE MLoop *which_mloop(ExportMeshData *export_data, int which_mesh) +{ + MLoop *mloop = NULL; + switch (which_mesh) { + case CARVE_MESH_LEFT: + mloop = export_data->mloop_left; + break; + case CARVE_MESH_RIGHT: + mloop = export_data->mloop_right; + break; } + return mloop; +} - face->orig_face = face_it->offset + face_it->pos; +BLI_INLINE MPoly *which_mpoly(ExportMeshData *export_data, int which_mesh) +{ + MPoly *mpoly = NULL; + switch (which_mesh) { + case CARVE_MESH_LEFT: + mpoly = export_data->mpoly_left; + break; + case CARVE_MESH_RIGHT: + mpoly = export_data->mpoly_right; + break; + } + return mpoly; } -static void FaceIt_Step(CSG_IteratorPtr it) +static void allocate_custom_layers(CustomData *data, int type, int num_elements, int num_layers) { - FaceIt *face_it = (FaceIt *)it; - face_it->pos++; + int i; + for (i = 0; i < num_layers; i++) { + CustomData_add_layer(data, type, CD_DEFAULT, NULL, num_elements); + } } -static void FaceIt_Reset(CSG_IteratorPtr it) +/* Create new external mesh */ +static void exporter_InitGeomArrays(ExportMeshData *export_data, + int num_verts, int num_edges, + int num_loops, int num_polys) { - FaceIt *face_it = (FaceIt *)it; - face_it->pos = 0; -} + DerivedMesh *dm = CDDM_new(num_verts, num_edges, 0, + num_loops, num_polys); + DerivedMesh *dm_left = export_data->dm_left, + *dm_right = export_data->dm_right; + + /* Mask for custom data layers to be merhed from operands. */ + CustomDataMask merge_mask = CD_MASK_DERIVEDMESH & ~CD_MASK_ORIGINDEX; + + export_data->dm = dm; + export_data->mvert = dm->getVertArray(dm); + export_data->medge = dm->getEdgeArray(dm); + export_data->mloop = dm->getLoopArray(dm); + export_data->mpoly = dm->getPolyArray(dm); + + /* Allocate layers for UV layers and vertex colors. + * Without this interpolation of those data will not happen. + */ + allocate_custom_layers(&dm->loopData, CD_MLOOPCOL, num_loops, + CustomData_number_of_layers(&dm_left->loopData, CD_MLOOPCOL)); + allocate_custom_layers(&dm->loopData, CD_MLOOPUV, num_loops, + CustomData_number_of_layers(&dm_left->loopData, CD_MLOOPUV)); + + /* Merge custom data layers from operands. + * + * Will only create custom data layers for all the layers which appears in + * the operand. Data for those layers will not be allocated or initialized. + */ + CustomData_merge(&dm_left->polyData, &dm->polyData, merge_mask, CD_DEFAULT, num_polys); + CustomData_merge(&dm_right->polyData, &dm->polyData, merge_mask, CD_DEFAULT, num_polys); + + export_data->vert_origindex = dm->getVertDataArray(dm, CD_ORIGINDEX); + export_data->edge_origindex = dm->getEdgeDataArray(dm, CD_ORIGINDEX); + export_data->poly_origindex = dm->getPolyDataArray(dm, CD_ORIGINDEX); + export_data->loop_origindex = dm->getLoopDataArray(dm, CD_ORIGINDEX); +} -static void FaceIt_Construct( - CSG_FaceIteratorDescriptor *output, DerivedMesh *dm, int offset, Object *ob) +/* Set coordinate of vertex with given index. */ +static void exporter_SetVert(ExportMeshData *export_data, + int vert_index, float coord[3], + int which_orig_mesh, int orig_vert_index) { - FaceIt *it; - if (output == NULL) return; + DerivedMesh *dm = export_data->dm; + DerivedMesh *dm_orig; + MVert *mvert = export_data->mvert; - /* allocate some memory for blender iterator */ - it = (FaceIt *)(MEM_mallocN(sizeof(FaceIt), "Boolean_FIt")); - if (it == NULL) { - return; + BLI_assert(vert_index >= 0 && vert_index <= dm->getNumVerts(dm)); + + dm_orig = which_dm(export_data, which_orig_mesh); + if (dm_orig) { + BLI_assert(orig_vert_index >= 0 && orig_vert_index < dm_orig->getNumVerts(dm_orig)); + CustomData_copy_data(&dm_orig->vertData, &dm->vertData, orig_vert_index, vert_index, 1); } - /* assign blender specific variables */ - it->dm = dm; - it->offset = offset; - it->pos = 0; - - /* determine if we will need to reverse order of face vertices */ - if (ob->size[0] < 0.0f) { - if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) { - it->flip = 1; - } - else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) { - it->flip = 1; + + /* Set original index of the vertex. */ + if (export_data->vert_origindex) { + if (which_orig_mesh == CARVE_MESH_LEFT) { + export_data->vert_origindex[vert_index] = orig_vert_index; } else { - it->flip = 0; + export_data->vert_origindex[vert_index] = ORIGINDEX_NONE; } } - else { - if (ob->size[1] < 0.0f && ob->size[2] < 0.0f) { - it->flip = 0; - } - else if (ob->size[1] >= 0.0f && ob->size[2] >= 0.0f) { - it->flip = 0; + + mul_v3_m4v3(mvert[vert_index].co, export_data->obimat, coord); +} + +/* Set vertices which are adjucent to the edge specified by it's index. */ +static void exporter_SetEdge(ExportMeshData *export_data, + int edge_index, int v1, int v2, + int which_orig_mesh, int orig_edge_index) +{ + DerivedMesh *dm = export_data->dm; + MEdge *medge = &export_data->medge[edge_index]; + DerivedMesh *dm_orig; + + BLI_assert(edge_index >= 0 && edge_index < dm->getNumEdges(dm)); + BLI_assert(v1 >= 0 && v1 < dm->getNumVerts(dm)); + BLI_assert(v2 >= 0 && v2 < dm->getNumVerts(dm)); + + dm_orig = which_dm(export_data, which_orig_mesh); + if (dm_orig) { + BLI_assert(orig_edge_index >= 0 && orig_edge_index < dm_orig->getNumEdges(dm_orig)); + + /* Copy all edge layers, including mpoly. */ + CustomData_copy_data(&dm_orig->edgeData, &dm->edgeData, orig_edge_index, edge_index, 1); + } + + /* Set original index of the edge. */ + if (export_data->edge_origindex) { + if (which_orig_mesh == CARVE_MESH_LEFT) { + export_data->edge_origindex[edge_index] = orig_edge_index; } else { - it->flip = 1; + export_data->edge_origindex[edge_index] = ORIGINDEX_NONE; } } - /* assign iterator function pointers. */ - output->Step = FaceIt_Step; - output->Fill = FaceIt_Fill; - output->Done = FaceIt_Done; - output->Reset = FaceIt_Reset; - output->num_elements = it->dm->getNumTessFaces(it->dm); - output->it = it; + medge->v1 = v1; + medge->v2 = v2; + + medge->flag |= ME_EDGEDRAW | ME_EDGERENDER; } -static void InterpCSGFace( - DerivedMesh *dm, DerivedMesh *orig_dm, int index, int orig_index, int nr, - float mapmat[4][4]) +static void setMPolyMaterial(ExportMeshData *export_data, + MPoly *mpoly, + int which_orig_mesh) { - float obco[3], *co[4], *orig_co[4], w[4][4]; - MFace *mface, *orig_mface; - int j; - - mface = CDDM_get_tessface(dm, index); - orig_mface = orig_dm->getTessFaceArray(orig_dm) + orig_index; - - /* get the vertex coordinates from the original mesh */ - orig_co[0] = (orig_dm->getVertArray(orig_dm) + orig_mface->v1)->co; - orig_co[1] = (orig_dm->getVertArray(orig_dm) + orig_mface->v2)->co; - orig_co[2] = (orig_dm->getVertArray(orig_dm) + orig_mface->v3)->co; - orig_co[3] = (orig_mface->v4) ? (orig_dm->getVertArray(orig_dm) + orig_mface->v4)->co : NULL; - - /* get the vertex coordinates from the new derivedmesh */ - co[0] = CDDM_get_vert(dm, mface->v1)->co; - co[1] = CDDM_get_vert(dm, mface->v2)->co; - co[2] = CDDM_get_vert(dm, mface->v3)->co; - co[3] = (nr == 4) ? CDDM_get_vert(dm, mface->v4)->co : NULL; - - for (j = 0; j < nr; j++) { - /* get coordinate into the space of the original mesh */ - if (mapmat) - mul_v3_m4v3(obco, mapmat, co[j]); - else - copy_v3_v3(obco, co[j]); + Object *orig_object; + GHash *material_hash; + Material *orig_mat; - interp_weights_face_v3(w[j], orig_co[0], orig_co[1], orig_co[2], orig_co[3], obco); + if (which_orig_mesh == CARVE_MESH_LEFT) { + /* No need to change materian index for faces from left operand */ + return; } - CustomData_interp(&orig_dm->faceData, &dm->faceData, &orig_index, NULL, (float *)w, 1, index); + material_hash = export_data->material_hash; + orig_object = which_object(export_data, which_orig_mesh); + + /* Set material, based on lookup in hash table. */ + orig_mat = give_current_material(orig_object, mpoly->mat_nr + 1); + + if (orig_mat) { + /* For faces from right operand check if there's requested material + * in the left operand. And if it is, use index of that material, + * otherwise fallback to first material (material with index=0). + */ + if (!BLI_ghash_haskey(material_hash, orig_mat)) { + int a, mat_nr;; + + mat_nr = 0; + for (a = 0; a < export_data->ob_left->totcol; a++) { + if (give_current_material(export_data->ob_left, a + 1) == orig_mat) { + mat_nr = a; + break; + } + } + + BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr)); + + mpoly->mat_nr = mat_nr; + } + else + mpoly->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat)); + } + else { + mpoly->mat_nr = 0; + } } -/* Iterate over the CSG Output Descriptors and create a new DerivedMesh - * from them */ -static DerivedMesh *ConvertCSGDescriptorsToDerivedMesh( - CSG_FaceIteratorDescriptor *face_it, - CSG_VertexIteratorDescriptor *vertex_it, - float parinv[4][4], - float mapmat[4][4], - Material **mat, - int *totmat, - DerivedMesh *dm1, - Object *ob1, - DerivedMesh *dm2, - Object *ob2) +/* Set list of adjucent loops to the poly specified by it's index. */ +static void exporter_SetPoly(ExportMeshData *export_data, + int poly_index, int start_loop, int num_loops, + int which_orig_mesh, int orig_poly_index) { - DerivedMesh *result, *orig_dm; - GHash *material_hash = NULL; - Mesh *me1 = (Mesh *)ob1->data; - Mesh *me2 = (Mesh *)ob2->data; - int i, *origindex_layer; - - /* create a new DerivedMesh */ - result = CDDM_new(vertex_it->num_elements, 0, face_it->num_elements, 0, 0); - CustomData_merge(&dm1->faceData, &result->faceData, CD_MASK_DERIVEDMESH & ~CD_MASK_ORIGINDEX, - CD_DEFAULT, face_it->num_elements); - CustomData_merge(&dm2->faceData, &result->faceData, CD_MASK_DERIVEDMESH & ~CD_MASK_ORIGINDEX, - CD_DEFAULT, face_it->num_elements); - - /* step through the vertex iterators: */ - for (i = 0; !vertex_it->Done(vertex_it->it); i++) { - CSG_IVertex csgvert; - MVert *mvert = CDDM_get_vert(result, i); - - /* retrieve a csg vertex from the boolean module */ - vertex_it->Fill(vertex_it->it, &csgvert); - vertex_it->Step(vertex_it->it); - - /* we have to map the vertex coordinates back in the coordinate frame - * of the resulting object, since it was computed in world space */ - mul_v3_m4v3(mvert->co, parinv, csgvert.position); + DerivedMesh *dm = export_data->dm; + MPoly *mpoly = &export_data->mpoly[poly_index]; + DerivedMesh *dm_orig; + int i; + + /* Poly is always to be either from left or right operand. */ + dm_orig = which_dm(export_data, which_orig_mesh); + + BLI_assert(poly_index >= 0 && poly_index < dm->getNumPolys(dm)); + BLI_assert(start_loop >= 0 && start_loop <= dm->getNumLoops(dm) - num_loops); + BLI_assert(num_loops >= 3); + BLI_assert(dm_orig != NULL); + BLI_assert(orig_poly_index >= 0 && orig_poly_index < dm_orig->getNumPolys(dm_orig)); + + /* Copy all poly layers, including mpoly. */ + CustomData_copy_data(&dm_orig->polyData, &dm->polyData, orig_poly_index, poly_index, 1); + + /* Set material of the curren poly. + * This would re-map materials from right operand to materials from the + * left one as well. + */ + setMPolyMaterial(export_data, mpoly, which_orig_mesh); + + /* Set original index of the poly. */ + if (export_data->poly_origindex) { + if (which_orig_mesh == CARVE_MESH_LEFT) { + export_data->poly_origindex[poly_index] = orig_poly_index; + } + else { + export_data->poly_origindex[poly_index] = ORIGINDEX_NONE; + } } - /* a hash table to remap materials to indices */ - material_hash = BLI_ghash_ptr_new("CSG_mat gh"); - - if (mat) - *totmat = 0; - - origindex_layer = result->getTessFaceDataArray(result, CD_ORIGINDEX); - - /* step through the face iterators */ - for (i = 0; !face_it->Done(face_it->it); i++) { - Mesh *orig_me; - Object *orig_ob; - Material *orig_mat; - CSG_IFace csgface; - MFace *mface; - int orig_index, mat_nr; - - /* retrieve a csg face from the boolean module */ - face_it->Fill(face_it->it, &csgface); - face_it->Step(face_it->it); - - /* find the original mesh and data */ - orig_ob = (csgface.orig_face < dm1->getNumTessFaces(dm1)) ? ob1 : ob2; - orig_dm = (csgface.orig_face < dm1->getNumTessFaces(dm1)) ? dm1 : dm2; - orig_me = (orig_ob == ob1) ? me1 : me2; - orig_index = (orig_ob == ob1) ? csgface.orig_face : csgface.orig_face - dm1->getNumTessFaces(dm1); - - /* copy all face layers, including mface */ - CustomData_copy_data(&orig_dm->faceData, &result->faceData, orig_index, i, 1); - - /* set mface */ - mface = CDDM_get_tessface(result, i); - mface->v1 = csgface.vertex_index[0]; - mface->v2 = csgface.vertex_index[1]; - mface->v3 = csgface.vertex_index[2]; - mface->v4 = (csgface.vertex_number == 4) ? csgface.vertex_index[3] : 0; - - /* set material, based on lookup in hash table */ - orig_mat = give_current_material(orig_ob, mface->mat_nr + 1); - - if (mat && orig_mat) { - if (!BLI_ghash_haskey(material_hash, orig_mat)) { - mat[*totmat] = orig_mat; - mat_nr = mface->mat_nr = (*totmat)++; - BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr)); - } - else - mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat)); + /* Set poly data itself. */ + mpoly->loopstart = start_loop; + mpoly->totloop = num_loops; + + if (which_orig_mesh == CARVE_MESH_RIGHT) { + which_orig_mesh = CARVE_MESH_RIGHT; + } + + /* Interpolate data for poly loops. */ + { + MVert *source_mverts = which_mvert(export_data, which_orig_mesh); + MLoop *source_mloops = which_mloop(export_data, which_orig_mesh); + MPoly *source_mpolys = which_mpoly(export_data, which_orig_mesh); + MPoly *source_poly = &source_mpolys[orig_poly_index]; + MVert *target_mverts = export_data->mvert; + MLoop *target_mloops = export_data->mloop; + float (*transform)[4] = NULL; + + if (which_orig_mesh == CARVE_MESH_RIGHT) { + transform = export_data->left_to_right_mat; } - else if (orig_mat) { - if (orig_ob == ob1) { - /* No need to change materian index for faces from left operand */ - } - else { - /* for faces from right operand checn if there's needed material in left operand and if it is, - * use index of that material, otherwise fallback to first material (material with index=0) */ - if (!BLI_ghash_haskey(material_hash, orig_mat)) { - int a; - - mat_nr = 0; - for (a = 0; a < ob1->totcol; a++) { - if (give_current_material(ob1, a + 1) == orig_mat) { - mat_nr = a; - break; - } - } - - BLI_ghash_insert(material_hash, orig_mat, SET_INT_IN_POINTER(mat_nr)); - - mface->mat_nr = mat_nr; - } - else - mface->mat_nr = GET_INT_FROM_POINTER(BLI_ghash_lookup(material_hash, orig_mat)); - } + + for (i = 0; i < mpoly->totloop; i++) { + DM_loop_interp_from_poly(dm_orig, + source_mverts, + source_mloops, + source_poly, + dm, + target_mverts, + target_mloops, + transform, + i + mpoly->loopstart); } - else - mface->mat_nr = 0; + } +} + +/* Set list vertex and edge which are adjucent to loop with given index. */ +static void exporter_SetLoop(ExportMeshData *export_data, + int loop_index, int vertex, int edge, + int which_orig_mesh, int orig_loop_index) +{ + DerivedMesh *dm = export_data->dm; + MLoop *mloop = &export_data->mloop[loop_index]; + DerivedMesh *dm_orig; + + BLI_assert(loop_index >= 0 && loop_index < dm->getNumLoops(dm)); + BLI_assert(vertex >= 0 && vertex < dm->getNumVerts(dm)); + BLI_assert(edge >= 0 && vertex < dm->getNumEdges(dm)); - InterpCSGFace(result, orig_dm, i, orig_index, csgface.vertex_number, - (orig_me == me2) ? mapmat : NULL); + dm_orig = which_dm(export_data, which_orig_mesh); + if (dm_orig) { + BLI_assert(orig_loop_index >= 0 && orig_loop_index < dm_orig->getNumLoops(dm_orig)); - test_index_face(mface, &result->faceData, i, csgface.vertex_number); + /* Copy all loop layers, including mpoly. */ + CustomData_copy_data(&dm_orig->loopData, &dm->loopData, orig_loop_index, loop_index, 1); + } - if (origindex_layer && orig_ob == ob2) - origindex_layer[i] = ORIGINDEX_NONE; + /* Set original index of the loop. */ + if (export_data->loop_origindex) { + if (which_orig_mesh == CARVE_MESH_LEFT) { + export_data->loop_origindex[loop_index] = orig_loop_index; + } + else { + export_data->loop_origindex[loop_index] = ORIGINDEX_NONE; + } } - if (material_hash) - BLI_ghash_free(material_hash, NULL, NULL); + mloop->v = vertex; + mloop->e = edge; +} - CDDM_calc_edges_tessface(result); +/* Edge index from a loop index for a given original mesh. */ +static int exporter_MapLoopToEdge(ExportMeshData *export_data, + int which_mesh, int loop_index) +{ + DerivedMesh *dm = which_dm(export_data, which_mesh); + MLoop *mloop = which_mloop(export_data, which_mesh); - CDDM_tessfaces_to_faces(result); /*builds ngon faces from tess (mface) faces*/ + (void) dm; /* Unused in release builds. */ - /* this fixes shading issues but SHOULD NOT. - * TODO, find out why face normals are wrong & flicker - campbell */ -#if 0 - DM_debug_print(result); + BLI_assert(dm != NULL); + BLI_assert(loop_index >= 0 && loop_index < dm->getNumLoops(dm)); - CustomData_free(&result->faceData, result->numTessFaceData); - result->numTessFaceData = 0; - DM_ensure_tessface(result); -#endif + return mloop[loop_index].e; +} + +static CarveMeshExporter MeshExporter = { + exporter_InitGeomArrays, + exporter_SetVert, + exporter_SetEdge, + exporter_SetPoly, + exporter_SetLoop, + exporter_MapLoopToEdge +}; - result->dirty |= DM_DIRTY_NORMALS; +static int operation_from_optype(int int_op_type) +{ + int operation; + + switch (int_op_type) { + case 1: + operation = CARVE_OP_INTERSECTION; + break; + case 2: + operation = CARVE_OP_UNION; + break; + case 3: + operation = CARVE_OP_A_MINUS_B; + break; + default: + BLI_assert(!"Should not happen"); + operation = -1; + break; + } - return result; + return operation; } - -static void BuildMeshDescriptors( - struct DerivedMesh *dm, - struct Object *ob, - int face_offset, - struct CSG_FaceIteratorDescriptor *face_it, - struct CSG_VertexIteratorDescriptor *vertex_it) + +static void prepare_import_data(Object *object, DerivedMesh *dm, ImportMeshData *import_data) { - VertexIt_Construct(vertex_it, dm, ob); - FaceIt_Construct(face_it, dm, face_offset, ob); + import_data->dm = dm; + copy_m4_m4(import_data->obmat, object->obmat); + import_data->mvert = dm->getVertArray(dm); + import_data->medge = dm->getEdgeArray(dm); + import_data->mloop = dm->getLoopArray(dm); + import_data->mpoly = dm->getPolyArray(dm); } - -static void FreeMeshDescriptors( - struct CSG_FaceIteratorDescriptor *face_it, - struct CSG_VertexIteratorDescriptor *vertex_it) + +static struct CarveMeshDescr *carve_mesh_from_dm(Object *object, DerivedMesh *dm) { - VertexIt_Destruct(vertex_it); - FaceIt_Destruct(face_it); + ImportMeshData import_data; + prepare_import_data(object, dm, &import_data); + return carve_addMesh(&import_data, &MeshImporter); } -DerivedMesh *NewBooleanDerivedMesh( - DerivedMesh *dm, struct Object *ob, DerivedMesh *dm_select, struct Object *ob_select, - int int_op_type) +static void prepare_export_data(Object *object_left, DerivedMesh *dm_left, + Object *object_right, DerivedMesh *dm_right, + ExportMeshData *export_data) { + float object_right_imat[4][4]; - float inv_mat[4][4]; - float map_mat[4][4]; + invert_m4_m4(export_data->obimat, object_left->obmat); - DerivedMesh *result = NULL; + export_data->ob_left = object_left; + export_data->ob_right = object_right; - if (dm == NULL || dm_select == NULL) return NULL; - if (!dm->getNumTessFaces(dm) || !dm_select->getNumTessFaces(dm_select)) return NULL; + export_data->dm_left = dm_left; + export_data->dm_right = dm_right; - /* we map the final object back into ob's local coordinate space. For this - * we need to compute the inverse transform from global to ob (inv_mat), - * and the transform from ob to ob_select for use in interpolation (map_mat) */ - invert_m4_m4(inv_mat, ob->obmat); - mul_m4_m4m4(map_mat, inv_mat, ob_select->obmat); - invert_m4_m4(inv_mat, ob_select->obmat); + export_data->mvert_left = dm_left->getVertArray(dm_left); + export_data->mloop_left = dm_left->getLoopArray(dm_left); + export_data->mpoly_left = dm_left->getPolyArray(dm_left); + export_data->mvert_right = dm_right->getVertArray(dm_right); + export_data->mloop_right = dm_right->getLoopArray(dm_right); + export_data->mpoly_right = dm_right->getPolyArray(dm_right); - { - /* interface with the boolean module: - * - * the idea is, we pass the boolean module verts and faces using the - * provided descriptors. once the boolean operation is performed, we - * get back output descriptors, from which we then build a DerivedMesh */ - - CSG_VertexIteratorDescriptor vd_1, vd_2; - CSG_FaceIteratorDescriptor fd_1, fd_2; - CSG_OperationType op_type; - CSG_BooleanOperation *bool_op; - - /* work out the operation they chose and pick the appropriate - * enum from the csg module. */ - switch (int_op_type) { - case 1: op_type = e_csg_intersection; break; - case 2: op_type = e_csg_union; break; - case 3: op_type = e_csg_difference; break; - case 4: op_type = e_csg_classify; break; - default: op_type = e_csg_intersection; - } + export_data->material_hash = BLI_ghash_ptr_new("CSG_mat gh"); - BuildMeshDescriptors(dm_select, ob_select, 0, &fd_1, &vd_1); - BuildMeshDescriptors(dm, ob, dm_select->getNumTessFaces(dm_select), &fd_2, &vd_2); + /* Matrix to convert coord from left object's loca; space to + * right object's local space. + */ + invert_m4_m4(object_right_imat, object_right->obmat); + mul_m4_m4m4(export_data->left_to_right_mat, object_left->obmat, + object_right_imat); +} - bool_op = CSG_NewBooleanFunction(); +DerivedMesh *NewBooleanDerivedMesh(DerivedMesh *dm, struct Object *ob, + DerivedMesh *dm_select, struct Object *ob_select, + int int_op_type) +{ - /* perform the operation */ - if (CSG_PerformBooleanOperation(bool_op, op_type, fd_1, vd_1, fd_2, vd_2)) { - CSG_VertexIteratorDescriptor vd_o; - CSG_FaceIteratorDescriptor fd_o; + struct CarveMeshDescr *left, *right, *output = NULL; + DerivedMesh *output_dm = NULL; + int operation; + bool result; - CSG_OutputFaceDescriptor(bool_op, &fd_o); - CSG_OutputVertexDescriptor(bool_op, &vd_o); + if (dm == NULL || dm_select == NULL) { + return NULL; + } - /* iterate through results of operation and insert - * into new object */ - result = ConvertCSGDescriptorsToDerivedMesh( - &fd_o, &vd_o, inv_mat, map_mat, NULL, NULL, dm_select, ob_select, dm, ob); + operation = operation_from_optype(int_op_type); + if (operation == -1) { + return NULL; + } - /* free up the memory */ - CSG_FreeVertexDescriptor(&vd_o); - CSG_FreeFaceDescriptor(&fd_o); - } - else - printf("Unknown internal error in boolean\n"); + left = carve_mesh_from_dm(ob_select, dm_select); + right = carve_mesh_from_dm(ob, dm); + + result = carve_performBooleanOperation(left, right, operation, &output); + + carve_deleteMesh(left); + carve_deleteMesh(right); + + if (result) { + ExportMeshData export_data; + + prepare_export_data(ob_select, dm_select, ob, dm, &export_data); + + carve_exportMesh(output, &MeshExporter, &export_data); + output_dm = export_data.dm; - CSG_FreeBooleanOperation(bool_op); + /* Free memory used by export mesh. */ + BLI_ghash_free(export_data.material_hash, NULL, NULL); - FreeMeshDescriptors(&fd_1, &vd_1); - FreeMeshDescriptors(&fd_2, &vd_2); + output_dm->dirty |= DM_DIRTY_NORMALS; + carve_deleteMesh(output); } - return result; + return output_dm; } |