diff options
Diffstat (limited to 'intern')
| -rw-r--r-- | intern/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | intern/bsp/CMakeLists.txt | 69 | ||||
| -rw-r--r-- | intern/bsp/SConscript | 49 | ||||
| -rw-r--r-- | intern/bsp/extern/CSG_BooleanOps.h | 361 | ||||
| -rw-r--r-- | intern/bsp/intern/BOP_CarveInterface.cpp | 852 | ||||
| -rw-r--r-- | intern/bsp/intern/BOP_Interface.h | 47 | ||||
| -rw-r--r-- | intern/bsp/intern/BSP_CSGException.h | 59 | ||||
| -rw-r--r-- | intern/bsp/intern/BSP_CSGMesh.cpp | 659 | ||||
| -rw-r--r-- | intern/bsp/intern/BSP_CSGMesh.h | 249 | ||||
| -rw-r--r-- | intern/bsp/intern/BSP_CSGMesh_CFIterator.h | 272 | ||||
| -rw-r--r-- | intern/bsp/intern/BSP_MeshPrimitives.cpp | 298 | ||||
| -rw-r--r-- | intern/bsp/intern/BSP_MeshPrimitives.h | 280 | ||||
| -rw-r--r-- | intern/bsp/intern/CSG_BooleanOps.cpp | 180 | ||||
| -rw-r--r-- | intern/container/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | intern/container/CTR_TaggedIndex.h | 210 | ||||
| -rw-r--r-- | intern/container/CTR_TaggedSetOps.h | 300 |
16 files changed, 0 insertions, 3891 deletions
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__ */ |