diff options
39 files changed, 5122 insertions, 0 deletions
diff --git a/intern/csg/extern/CSG_Interface.h b/intern/csg/extern/CSG_Interface.h new file mode 100644 index 00000000000..44b01c6f500 --- /dev/null +++ b/intern/csg/extern/CSG_Interface.h @@ -0,0 +1,434 @@ +/** + * $Id$ + * ***** BEGIN GPL/BL DUAL 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. The Blender + * Foundation also sells licenses for use in proprietary software under + * the Blender License. See http://www.blender.org/BL/ for information + * about this. + * + * 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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/BL DUAL LICENSE BLOCK ***** + */ + +#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 + +#if 0 +typedef struct { + int vertex_index[4]; + int vertex_number; + + void *user_face_vertex_data[4]; + void *user_face_data; +} CSG_IFace; +#else + +/** + * The following structs are much better to use than the crazy + * abstract type above. It's a value type an allows the CSG + * module to directly access mesh properties which is very useful + * for debugging etc. + */ + +typedef struct +{ + int m_vertexIndex; + float m_uv[2]; + float m_color[4]; + short m_normal[3]; +} CSG_IFaceVertexData; + +typedef struct +{ + struct Material *m_material; + + /* assorted tface flags */ + void *m_tpage; + char m_flag, m_transp; + short m_mode, m_tile; +} CSG_IFaceData; + +typedef struct +{ + CSG_IFaceVertexData m_vertexData[4]; + int m_vertexNumber; + + CSG_IFaceData m_faceData; + +} CSG_IFace; + +#endif + +/** + * CSG_IVertex -- an interface vertex structure. + * position is the location of the vertex in 3d space. + */ + +typedef struct { + float position[3]; +} CSG_IVertex; + + +/** + * @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 + * } + * + * // Describe each mesh operand to the module. + * // NOTE: example properties! + * CSG_MeshPropertyDescriptor propA,propB; + * propA.user_data_size = 0; + * propA.user_face_vertex_data = 0; + * propB.user_face_vertex_data = 0; + * propB.user_data_size = 0; + * + * // Get the output properties of the mesh. + * CSG_MeshPropertyDescriptor output_properties; + * output_properties = CSG_DescibeOperands( + * operation, + * propA, + * propB + * ); + * + * // 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 +); + +/** + * The user data is handled by the BSP modules through + * the following function which is called whenever the + * module needs new face vertex properties (when a face is split). + * d1,d2 are pointers to existing vertex face data. dnew is + * a pointer to an allocated but unfilled area of user data of + * size user_face_vertex_data_size in the CSG_MeshPropertyDescriptor + * returned by a call to the above function. Epsilon is the relative + * distance (between [0,1]) of the new vertex and the vertex associated + * with d1. Use epsilon to interpolate the face vertex data in d1 and d2 + * and fill dnew + */ + +typedef int (*CSG_InterpolateUserFaceVertexDataFunc)( + const CSG_IFaceVertexData *d1, + const CSG_IFaceVertexData * d2, + CSG_IFaceVertexData *dnew, + double epsilon +); + + +/** + * 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, + CSG_InterpolateUserFaceVertexDataFunc interp_func +); + +/** + * 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/csg/intern/CSG_BBox.h b/intern/csg/intern/CSG_BBox.h new file mode 100644 index 00000000000..4d17b935a80 --- /dev/null +++ b/intern/csg/intern/CSG_BBox.h @@ -0,0 +1,206 @@ +/* +The following BBox class is a lightly modfied version of what +is found in Free Solid 2.0 +*/ + +/* + SOLID - Software Library for Interference Detection + Copyright (C) 1997-1998 Gino van den Bergen + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to gino@win.tue.nl, + or write to: + Gino van den Bergen + Department of Mathematics and Computing Science + Eindhoven University of Technology + P.O. Box 513, 5600 MB Eindhoven, The Netherlands +*/ + +#ifndef _BBOX_H_ +#define _BBOX_H_ + +#include "MT_Point3.h" +#include "MT_Vector3.h" +#include "MT_MinMax.h" + +class BBox { +public: + BBox() {} + + BBox( + const MT_Point3& mini, + const MT_Point3& maxi + ) { SetValue(mini,maxi); } + + const MT_Point3& + Center( + ) const { + return m_center; + } + + const MT_Vector3& + Extent( + ) const { + return m_extent; + } + + MT_Point3& + Center( + ) { + return m_center; + } + + MT_Vector3& + Extent( + ) { + return m_extent; + } + + void + SetValue( + const MT_Point3& mini, + const MT_Point3& maxi + ) { + m_extent = (maxi-mini)/2; + m_center = mini+m_extent; + } + + void + Enclose( + const BBox& a, + const BBox& b + ) { + MT_Point3 lower( + MT_min(a.Lower(0), b.Lower(0)), + MT_min(a.Lower(1), b.Lower(1)), + MT_min(a.Lower(2), b.Lower(2)) + ); + MT_Point3 upper( + MT_max(a.Upper(0), b.Upper(0)), + MT_max(a.Upper(1), b.Upper(1)), + MT_max(a.Upper(2), b.Upper(2)) + ); + SetValue(lower, upper); + } + + void + SetEmpty() { + m_center.setValue(0, 0, 0); + m_extent.setValue(-MT_INFINITY,-MT_INFINITY,-MT_INFINITY); + } + + void + Include ( + const MT_Point3& p + ) { + MT_Point3 lower( + MT_min(Lower(0), p[0]), + MT_min(Lower(1), p[1]), + MT_min(Lower(2), p[2]) + ); + MT_Point3 upper( + MT_max(Upper(0), p[0]), + MT_max(Upper(1), p[1]), + MT_max(Upper(2), p[2]) + ); + SetValue(lower, upper); + } + + void + Include ( + const BBox& b + ) { + Enclose(*this, b); + } + + MT_Scalar + Lower( + int i + ) const { + return m_center[i] - m_extent[i]; + } + MT_Scalar + Upper( + int i + ) const { + return m_center[i] + m_extent[i]; + } + + MT_Point3 + Lower( + ) const { + return m_center - m_extent; + } + MT_Point3 + Upper( + ) const { + return m_center + m_extent; + } + + MT_Scalar + Size( + ) const { + return MT_max(MT_max(m_extent[0], m_extent[1]), m_extent[2]); + } + + int + LongestAxis( + ) const { + return m_extent.closestAxis(); + } + + bool + IntersectXRay( + const MT_Point3& xBase + ) const { + if (xBase[0] <= Upper(0)) + { + if (xBase[1] <= Upper(1) && xBase[1] >= Lower(1)) + { + if (xBase[2] <= Upper(2) && xBase[2] >= Lower(2)) + { + return true; + } + } + } + return false; + } + + + + + friend bool intersect(const BBox& a, const BBox& b); + +private: + MT_Point3 m_center; + MT_Vector3 m_extent; +}; + +inline + bool +intersect( + const BBox& a, + const BBox& b +) { + return + MT_abs(a.m_center[0] - b.m_center[0]) <= a.m_extent[0] + b.m_extent[0] && + MT_abs(a.m_center[1] - b.m_center[1]) <= a.m_extent[1] + b.m_extent[1] && + MT_abs(a.m_center[2] - b.m_center[2]) <= a.m_extent[2] + b.m_extent[2]; +} + +#endif + + diff --git a/intern/csg/intern/CSG_BBoxTree.cpp b/intern/csg/intern/CSG_BBoxTree.cpp new file mode 100644 index 00000000000..37ff9651359 --- /dev/null +++ b/intern/csg/intern/CSG_BBoxTree.cpp @@ -0,0 +1,125 @@ +/* + SOLID - Software Library for Interference Detection + Copyright (C) 1997-1998 Gino van den Bergen + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to gino@win.tue.nl, + or write to: + Gino van den Bergen + Department of Mathematics and Computing Science + Eindhoven University of Technology + P.O. Box 513, 5600 MB Eindhoven, The Netherlands +*/ + +#include "CSG_BBoxTree.h" +#include <algorithm> + + +using namespace std; + + +BBoxInternal:: +BBoxInternal( + int n, LeafPtr leafIt +) +{ + m_tag = INTERNAL; + m_bbox.SetEmpty(); + + int i; + for (i=0;i<n;i++) { + m_bbox.Include(leafIt[i].m_bbox); + } +} +// Construct a BBoxInternal from a list of BBoxLeaf nodes. +// Recursive function that does the longest axis median point +// fit. + +void BBoxTree:: +BuildTree( + LeafPtr leaves, int numLeaves +) { + m_branch = 0; + m_leaves = leaves; + m_numLeaves = numLeaves; + m_internals = new BBoxInternal[numLeaves]; + + RecursiveTreeBuild(m_numLeaves,m_leaves); +} + + void +BBoxTree:: +RecursiveTreeBuild( + int n, LeafPtr leafIt +){ + m_internals[m_branch] = BBoxInternal(n,leafIt); + BBoxInternal& aBBox = m_internals[m_branch]; + + m_branch++; + + int axis = aBBox.m_bbox.LongestAxis(); + int i = 0, mid = n; + + // split the leaves into two groups those that are < bbox.getCenter()[axis] + // and those that are >= + // smart bit about this code is it does the grouping in place. + while (i < mid) + { + if (leafIt[i].m_bbox.Center()[axis] < aBBox.m_bbox.Center()[axis]) + { + ++i; + } else { + --mid; + swap(leafIt[i], leafIt[mid]); + } + } + + // all of the nodes were on one side of the box centre + // I'm not sure if this case ever gets reached? + if (mid == 0 || mid == n) + { + mid = n / 2; + } + + if (mid >= 2) + { + aBBox.rson = m_internals + m_branch; + RecursiveTreeBuild(mid,leafIt); + } else { + aBBox.rson = leafIt; + } + if (n - mid >= 2) { + aBBox.lson = m_internals + m_branch; + RecursiveTreeBuild(n - mid, leafIt + mid); + } else { + aBBox.lson = leafIt + mid; + } +} + + + + + + + + + + + + + + + diff --git a/intern/csg/intern/CSG_BBoxTree.h b/intern/csg/intern/CSG_BBoxTree.h new file mode 100644 index 00000000000..a9013ccf329 --- /dev/null +++ b/intern/csg/intern/CSG_BBoxTree.h @@ -0,0 +1,135 @@ +/** + * I've modified some very nice bounding box tree code from + * Gino van der Bergen's Free Solid Library below. It's basically + * the same code - but I've hacked out the transformation stuff as + * I didn't understand it. I've also made it far less elegant! + * + */ + +/* + SOLID - Software Library for Interference Detection + Copyright (C) 1997-1998 Gino van den Bergen + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to gino@win.tue.nl, + or write to: + Gino van den Bergen + Department of Mathematics and Computing Science + Eindhoven University of Technology + P.O. Box 513, 5600 MB Eindhoven, The Netherlands +*/ + +#ifndef _BBOXTREE_H_ +#define _BBOXTREE_H_ + +#include "CSG_BBox.h" +#include "MT_Line3.h" +#include "CSG_IndexDefs.h" + +#include <vector> + +/** + * Tree structure + */ + +class BBoxNode +{ +public: + enum TagType { LEAF, INTERNAL }; + + BBox m_bbox; + TagType m_tag; +}; + + +class BBoxLeaf : public BBoxNode +{ +public: + int m_polyIndex; + + BBoxLeaf() {} + + BBoxLeaf(int polyIndex, const BBox& bbox) + : m_polyIndex(polyIndex) + { + m_bbox = bbox; + m_tag = LEAF; + } + +}; + + +typedef BBoxLeaf* LeafPtr; +typedef BBoxNode* NodePtr; + + +class BBoxInternal : public BBoxNode +{ +public: + NodePtr lson; + NodePtr rson; + + BBoxInternal() {} + BBoxInternal( + int n, LeafPtr leafIt + ); + +}; + +typedef BBoxInternal* InternalPtr; + + +class BBoxTree +{ +public : + BBoxTree() {}; + + const NodePtr RootNode() const { + return m_internals; + } + + ~BBoxTree() { + delete[] m_leaves; + delete[] m_internals; + } + + // tree takes ownership of the leaves. + void BuildTree(LeafPtr leaves, int numLeaves); + +private : + + void RecursiveTreeBuild( + int n, LeafPtr leafIt + ); + + int m_branch; + + LeafPtr m_leaves; + InternalPtr m_internals; + int m_numLeaves; +}; + + + + + +#endif + + + + + + diff --git a/intern/csg/intern/CSG_BlenderVProp.h b/intern/csg/intern/CSG_BlenderVProp.h new file mode 100644 index 00000000000..72cad752c31 --- /dev/null +++ b/intern/csg/intern/CSG_BlenderVProp.h @@ -0,0 +1,94 @@ +#ifndef CSG_BlenderVProp_H +#define CSG_BlenderVProp_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +// A vertex property that stores a CSG_IFaceVertexData structure defined +// in the interface between the CSG module and blender CSG_Interface.h! + +#include "CSG_Interface.h" +#include "MT_Scalar.h" + +class BlenderVProp +{ +public : + // You must set the interpolation function ptr + // before using this class. + + static CSG_InterpolateUserFaceVertexDataFunc InterpFunc; + +private : + + CSG_IFaceVertexData m_data; + +public : + + BlenderVProp(const int& vIndex) + { + m_data.m_vertexIndex = vIndex; + } + + BlenderVProp( + const int& vIndex, + const BlenderVProp& p1, + const BlenderVProp& p2, + const MT_Scalar& epsilon + ){ + m_data.m_vertexIndex = vIndex; + InterpFunc(&(p1.m_data),&(p2.m_data),&m_data,epsilon); + } + + + BlenderVProp( + ) {}; + + // Default copy constructor and assignment operator are fine. + + // Support conversion to an integer + /////////////////////////////////// + operator int( + ) const { + return m_data.m_vertexIndex; + } + + // and assignment from an integer. + ////////////////////////////////// + BlenderVProp& + operator = ( + int i + ) { + m_data.m_vertexIndex = i; + return *this; + } + + // return a reference to our data + const CSG_IFaceVertexData& Data() const { + return m_data; + } + + CSG_IFaceVertexData& Data() { + return m_data; + } + + +}; + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/CSG_BooleanOp.h b/intern/csg/intern/CSG_BooleanOp.h new file mode 100644 index 00000000000..ff293799286 --- /dev/null +++ b/intern/csg/intern/CSG_BooleanOp.h @@ -0,0 +1,88 @@ +#ifndef CSG_BOOLEANOP_H +#define CSG_BOOLEANOP_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "CSG_IndexDefs.h" +#include "CSG_BBoxTree.h" + +template <typename CMesh, typename TMesh> class BooleanOp +{ +public : + + // unimplemented + //////////////// + BooleanOp(); + BooleanOp(const BooleanOp&); + BooleanOp& operator = (const BooleanOp&); + + //helpers + ///////// + + static + void + BuildSplitGroup( + const TMesh& meshA, + const TMesh& meshB, + const BBoxTree& treeA, + const BBoxTree& treeB, + OverlapTable& aOverlapsB, + OverlapTable& bOverlapsA + ); + + // Split mesh with mesh2, table is an OverlapTable containing the polygons + // of mesh2 that intersect with polygons of mesh. + // if preserve is true this function will aim to reduce the number of + // T-junctions created. + + static + void + PartitionMesh( + CMesh & mesh, + const TMesh & mesh2, + const OverlapTable& table + ); + + // Classify meshB with respect to meshA, uses a BBox tree of meshA + // to drastically improve speed! + static + void + ClassifyMesh( + const TMesh& meshA, + const BBoxTree& aTree, + CMesh& meshB + ); + + static + void + ExtractClassification( + CMesh& meshA, + TMesh& newMesh, + int classification, + bool reverse + ); + + +}; + +#include "CSG_BooleanOp.inl" + +#endif diff --git a/intern/csg/intern/CSG_BooleanOp.inl b/intern/csg/intern/CSG_BooleanOp.inl new file mode 100644 index 00000000000..9309d4ffbb5 --- /dev/null +++ b/intern/csg/intern/CSG_BooleanOp.inl @@ -0,0 +1,235 @@ +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ +#include "CSG_Math.h" +#include "CSG_BBoxTree.h" +#include "CSG_TreeQueries.h" + +using namespace std; + +template <typename CMesh, typename TMesh> + void +BooleanOp<CMesh,TMesh>:: +BuildSplitGroup( + const TMesh& meshA, + const TMesh& meshB, + const BBoxTree& treeA, + const BBoxTree& treeB, + OverlapTable& aOverlapsB, + OverlapTable& bOverlapsA +) { + + aOverlapsB = OverlapTable(meshB.Polys().size()); + bOverlapsA = OverlapTable(meshA.Polys().size()); + + // iterate through the polygons of A and then B + // and mark each + TreeIntersector<TMesh>(treeA,treeB,&aOverlapsB,&bOverlapsA,&meshA,&meshB); + +} + +template <typename CMesh, typename TMesh> + void +BooleanOp<CMesh,TMesh>:: +PartitionMesh( + CMesh & mesh, + const TMesh & mesh2, + const OverlapTable& table +) { + + // iterate through the overlap table. + int i; + + MT_Scalar onEpsilon(1e-4); + + for (i = 0; i < table.size(); i++) + { + if (table[i].size()) + { + // current list of fragments - initially contains + // just the to-be-split polygon index + PIndexList fragments; + fragments.push_back(i); + + // iterate through the splitting polygons. + int j; + for (j =0 ; j <table[i].size(); ++j) + { + PIndexList newFragments; + + // find the splitting plane + MT_Plane3 splitPlane = mesh2.Polys()[table[i][j]].Plane(); + + // iterate through the current fragments and split them + // with the new plane, adding the resulting fragments to + // the newFragments list. + int k; + for (k = 0; k < fragments.size(); ++k) + { + int newInFragment; + int newOutFragment; + + CMesh::TGBinder pg1(mesh,fragments[k]); + TMesh::TGBinder pg2(mesh2,table[i][j]); + + const MT_Plane3& fragPlane = mesh.Polys()[fragments[k]].Plane(); + + if (CSG_PolygonIntersector<CMesh::TGBinder,TMesh::TGBinder >:: + IntersectPolygons(pg1,pg2,fragPlane,splitPlane)) + { + mesh.SplitPolygon(fragments[k],splitPlane,newInFragment,newOutFragment,onEpsilon); + + if (-1 != newInFragment) newFragments.push_back(newInFragment); + if (-1 != newOutFragment) newFragments.push_back(newOutFragment); + } else { + // this fragment was not split by this polygon but it may be split by a subsequent + // polygon in the list + newFragments.push_back(fragments[k]); + } + + } + + fragments = newFragments; + } + } + } +} + +template <typename CMesh, typename TMesh> + void +BooleanOp<CMesh,TMesh>:: +ClassifyMesh( + const TMesh& meshA, + const BBoxTree& aTree, + CMesh& meshB +) { + + // walk through all of the polygons of meshB. Create a + // ray in the direction of the polygons normal emintaing from the + // mid point of the polygon + + // Do a ray test with all of the polygons of MeshA + // Find the nearest intersection point and record the polygon index + + // If there were no intersections then the ray is outside. + // If there was an intersection and the dot product of the ray and normal + // of the intersected polygon from meshA is +ve then we are on the inside + // else outside. + + int i; + for (i = 0; i < meshB.Polys().size(); i++) + { + CMesh::TGBinder pg(meshB,i); + + MT_Line3 midPointRay = CSG_Math<CMesh::TGBinder >::PolygonMidPointRay(pg,meshB.Polys()[i].Plane()); + + MT_Line3 midPointXRay(midPointRay.Origin(),MT_Vector3(1,0,0)); + + int aPolyIndex(-1); + + RayTreeIntersector<TMesh>(aTree,&meshA,midPointXRay,aPolyIndex); + + if (-1 != aPolyIndex) + { + if (meshA.Polys()[aPolyIndex].Plane().signedDistance(midPointXRay.Origin()) < 0) + { + meshB.Polys()[i].Classification()= 1; + } else { + meshB.Polys()[i].Classification()= 2; + } + } else { + meshB.Polys()[i].Classification()= 2; + } + } +} + + +template <typename CMesh, typename TMesh> + void +BooleanOp<CMesh,TMesh>:: +ExtractClassification( + CMesh& meshA, + TMesh& newMesh, + int classification, + bool reverse +){ + + int i; + for (i = 0; i < meshA.Polys().size(); ++i) + { + CMesh::Polygon& meshAPolygon = meshA.Polys()[i]; + if (meshAPolygon.Classification() == classification) + { + newMesh.Polys().push_back(meshAPolygon); + TMesh::Polygon& newPolygon = newMesh.Polys().back(); + + if (reverse) newPolygon.Reverse(); + + // iterate through the vertices of the new polygon + // and find a new place for them in the new mesh (if they arent already there) + + int j; + for (j=0; j< newPolygon.Size(); j++) + { + if (meshA.Verts()[newPolygon[j]].VertexMap() == -1) + { + // this is the first time we have visited this vertex + // copy it over to the new mesh. + newMesh.Verts().push_back(meshA.Verts()[newPolygon[j]]); + // and record it's position in the new mesh for the next time we visit it. + meshA.Verts()[newPolygon[j]].VertexMap() = newMesh.Verts().size() -1; + } + newPolygon.VertexProps(j) = meshA.Verts()[newPolygon[j]].VertexMap(); + } + } + } +} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/intern/csg/intern/CSG_CVertex.h b/intern/csg/intern/CSG_CVertex.h new file mode 100644 index 00000000000..fd0a7b098b5 --- /dev/null +++ b/intern/csg/intern/CSG_CVertex.h @@ -0,0 +1,104 @@ +#ifndef CSG_CVertex_H +#define CSG_CVertex_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include <algorithm> +#include "CSG_IndexDefs.h" +#include "CSG_Vertex.h" +// This class extends an existing vertex by connecting +// them with their polygons through the PIndexList member. +// +// This extra information allows us to perform local +// mesh topology queries +// +// These queries are availble through the ConnectedMesh class. + +class CVertex : public VertexBase +{ +private : + + // polygons using this vertex + PIndexList m_polygons; + +public : + + CVertex() + :VertexBase(),m_polygons() + { + }; + + // have to change VertexBase and all functions to + // use Pos() rather than m_pos; + + CVertex(const VertexBase& vertex) + :VertexBase(vertex),m_polygons() + {} + + // Value type model + /////////////////// + CVertex(const CVertex& other) + : VertexBase(other), m_polygons(other.m_polygons) + {} + + CVertex& operator = (const CVertex& other) + { + m_pos = other.Pos(); + m_vertexMap = other.m_vertexMap; + m_polygons = other.m_polygons; + + return *this; + } + + + CVertex& operator = (const VertexBase& other) + { + m_pos= other.Pos(); + return *this; + } + + + ~CVertex(){}; + + // Our special connected vertex functions. + ////////////////////////////////////////// + + const PIndexList& Polys() const { return m_polygons;} + PIndexList& Polys() { return m_polygons;} + + int & operator[] (const int & i) { return m_polygons[i];} + + const int & operator[] (const int& i) const { return m_polygons[i];} + + void AddPoly(int polyIndex) {m_polygons.push_back(polyIndex);} + + void RemovePolygon(int polyIndex) + { + PIndexIt foundIt = std::find(m_polygons.begin(),m_polygons.end(),polyIndex); + if (foundIt != m_polygons.end()) { + std::swap(m_polygons.back(), *foundIt); + m_polygons.pop_back(); + } + } +}; + + +#endif diff --git a/intern/csg/intern/CSG_ConnectedMesh.h b/intern/csg/intern/CSG_ConnectedMesh.h new file mode 100644 index 00000000000..6cf73ef2240 --- /dev/null +++ b/intern/csg/intern/CSG_ConnectedMesh.h @@ -0,0 +1,95 @@ +#ifndef CSG_ConnectedMesh_H +#define CSG_ConnectedMesh_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "CSG_GeometryBinder.h" +#include "MT_Plane3.h" + +template <typename TMesh> class ConnectedMeshWrapper +{ +public : + + typedef TMesh::Polygon Polygon; + typedef TMesh::Vertex Vertex; + + typedef TMesh::Polygon::TVProp VProp; + + typedef TMesh::VLIST VLIST; + typedef TMesh::PLIST PLIST; + + typedef PolygonGeometry<ConnectedMeshWrapper> TGBinder; + + typedef ConnectedMeshWrapper<TMesh> MyType; + +private : + TMesh& m_mesh; + + unsigned int m_uniqueEdgeTestId; + +public : + + // Mesh Template interface + ////////////////////////// + VLIST& Verts() {return m_mesh.Verts();} + const VLIST& Verts() const {return m_mesh.Verts();} + + PLIST& Polys() {return m_mesh.Polys();} + const PLIST& Polys() const {return m_mesh.Polys();} + + // Mesh Wrapper functions + ///////////////////////// + + ConnectedMeshWrapper(TMesh& mesh): + m_mesh(mesh),m_uniqueEdgeTestId(0) {}; + + void BuildVertexPolyLists(); + + void DisconnectPolygon(int polyIndex); + + void ConnectPolygon(int polyIndex); + + //return the polygons neibouring the given edge. + void EdgePolygons(int v1, int v2, PIndexList& polys); + + void InsertVertexAlongEdge(int v1,int v2, const VProp& prop); + + void + SplitPolygon( + const int p1Index, + const MT_Plane3& plane, + int& inPiece, + int& outPiece, + const MT_Scalar onEpsilon + ); + + ~ConnectedMeshWrapper(){}; +}; + +#include "CSG_ConnectedMeshWrapper.inl" + +#endif + + + + + + diff --git a/intern/csg/intern/CSG_ConnectedMeshWrapper.inl b/intern/csg/intern/CSG_ConnectedMeshWrapper.inl new file mode 100644 index 00000000000..5d6cc11cc48 --- /dev/null +++ b/intern/csg/intern/CSG_ConnectedMeshWrapper.inl @@ -0,0 +1,210 @@ +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ +#include <algorithm> +#include <iterator> +#include "CSG_SplitFunction.h" + +// Define functors things that bind a function to an object, +// for the templated split polygon code. + +template <typename CMesh> class SplitFunctionBindor +{ +private : + CMesh& m_mesh; + +public : + + SplitFunctionBindor(CMesh& mesh):m_mesh(mesh) {}; + + void DisconnectPolygon(int polyIndex){ + m_mesh.DisconnectPolygon(polyIndex); + } + + void ConnectPolygon(int polygonIndex) { + m_mesh.ConnectPolygon(polygonIndex); + } + + void InsertVertexAlongEdge(int lastIndex,int newIndex,const CMesh::VProp& prop) { + m_mesh.InsertVertexAlongEdge(lastIndex,newIndex,prop); + } + + ~SplitFunctionBindor(){}; +}; + + +template <typename TMesh> + void +ConnectedMeshWrapper<TMesh>:: +BuildVertexPolyLists( +) { + int i; + for (i=0; i < Polys().size(); i++) + { + ConnectPolygon(i); + } +} + +template <typename TMesh> + void +ConnectedMeshWrapper<TMesh>:: +DisconnectPolygon( + int polyIndex +){ + const Polygon& poly = Polys()[polyIndex]; + + int j; + for (j=0;j<poly.Verts().size(); j++) + { + Verts()[poly[j]].RemovePolygon(polyIndex); + } +} + +template <typename TMesh> + void +ConnectedMeshWrapper<TMesh>:: +ConnectPolygon( + int polyIndex +){ + const Polygon& poly = Polys()[polyIndex]; + + int j; + for (j=0;j<poly.Verts().size(); j++) + { + Verts()[poly[j]].AddPoly(polyIndex); + } +} + +template <typename TMesh> + void +ConnectedMeshWrapper<TMesh>:: +EdgePolygons( + int v1, + int v2, + PIndexList& polys +) { + ++m_uniqueEdgeTestId; + + Vertex& vb1 = Verts()[v1]; + int i; + for (i=0;i < vb1.Polys().size(); ++i) + { + Polys()[vb1[i]].Classification() = m_uniqueEdgeTestId; + } + + Vertex& vb2 = Verts()[v2]; + int j; + for (j=0;j < vb2.Polys().size(); ++j) + { + if (Polys()[vb2[j]].Classification() == m_uniqueEdgeTestId) + { + polys.push_back(vb2[j]); + } + } +} + +template <typename TMesh> + void +ConnectedMeshWrapper<TMesh>:: +InsertVertexAlongEdge( + int v1, + int v2, + const VProp& prop +) { + + PIndexList npolys; + EdgePolygons(v1,v2,npolys); + + // iterate through the neighbouting polygons of + // this edge and insert the vertex into the polygon + + int newVertex = int(prop); + + int i; + for (i=0;i < npolys.size(); i++) + { + // find the first vertex index in this polygon + Polygon::TVPropList& polyVerts = Polys()[npolys[i]].Verts(); + + Polygon::TVPropIt v1pos = std::find(polyVerts.begin(),polyVerts.end(),v1); + + // this should never be false! + if (v1pos != polyVerts.end()) + { + // v2 must be either side of this pos + Polygon::TVPropIt prevPos = (v1pos == polyVerts.begin()) ? polyVerts.end()-1 : v1pos-1; + Polygon::TVPropIt nextPos = (v1pos == polyVerts.end()-1) ? polyVerts.begin() : v1pos+1; + + if (*prevPos == v2) { + polyVerts.insert(v1pos,prop); + } else + if (*nextPos == v2) { + polyVerts.insert(nextPos,prop); + } else { + //assert(false); + } + + Verts()[newVertex].AddPoly(npolys[i]); + } else { + assert(false); + } + } +} + + +template <typename TMesh> + void +ConnectedMeshWrapper<TMesh>:: +SplitPolygon( + const int p1Index, + const MT_Plane3& plane, + int& inPiece, + int& outPiece, + const MT_Scalar onEpsilon +){ + + SplitFunctionBindor<MyType> functionBindor(*this); + + SplitFunction<MyType,SplitFunctionBindor<MyType> > splitFunction(*this,functionBindor); + splitFunction.SplitPolygon(p1Index,plane,inPiece,outPiece,onEpsilon); +} + +#if 0 +template <class TPolygon, class TVertex> + void +Mesh:: +printMesh( + std::ostream& stream +) { + + int i; + for (i =0; i < m_polys.size(); i++) + { + std::ostream_iterator<int> streamIt(stream," "); + std::copy(m_polys[i].Verts().begin(),m_polys[i].Verts().end(),streamIt); + stream << "\n"; + } +} + +#endif + + + + diff --git a/intern/csg/intern/CSG_GeometryBinder.h b/intern/csg/intern/CSG_GeometryBinder.h new file mode 100644 index 00000000000..2977ac65971 --- /dev/null +++ b/intern/csg/intern/CSG_GeometryBinder.h @@ -0,0 +1,72 @@ +#ifndef CSG_GEOMETRY_BINDER_H +#define CSG_GEOMETRY_BINDER_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +// This class binds the geometry of a polygon +// to the polygon itself it provides just one +// operator [int i] that returns the vertex position +// of the ith vertex in the polygon. + +// Its a model of a geometry binder primarily used by the CSG_Math +// template class to compute geometric information about a mesh. + +#include "MT_Point3.h" + + +template <typename TMesh> class PolygonGeometry +{ +public : + + typedef typename TMesh::Polygon TPolygon; + + PolygonGeometry(const TMesh& mesh, int pIndex) + : m_poly(mesh.Polys()[pIndex]),m_mesh(mesh) + {}; + + PolygonGeometry(const TMesh& mesh,const TPolygon& poly) + : m_poly(poly),m_mesh(mesh) + {}; + + const MT_Point3& operator[] (int i) const { + return m_mesh.Verts()[m_poly[i]].Pos(); + }; + + int Size() const { return m_poly.Size();} + + ~PolygonGeometry(){}; + +private : + + PolygonGeometry(const PolygonGeometry& other) {}; + PolygonGeometry& operator = (PolygonGeometry& other) { return *this;} + + const TMesh& m_mesh; + const TPolygon& m_poly; + +}; + +#endif + + + + + diff --git a/intern/csg/intern/CSG_IndexDefs.h b/intern/csg/intern/CSG_IndexDefs.h new file mode 100644 index 00000000000..2e1e05a5eb4 --- /dev/null +++ b/intern/csg/intern/CSG_IndexDefs.h @@ -0,0 +1,42 @@ +#ifndef CSG_INDEXDEFS_H +#define CSG_INDEXDEFS_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +//typdefs for lists and things in the CSG library + +#include <vector> + +typedef std::vector<int> PIndexList; +typedef PIndexList::iterator PIndexIt; +typedef PIndexList::const_iterator const_PIndexIt; + +typedef std::vector<int> VIndexList; +typedef VIndexList::iterator VIndexIt; +typedef VIndexList::const_iterator const_VIndexIt; + +typedef std::vector< PIndexList > OverlapTable; + + + +#endif + + diff --git a/intern/csg/intern/CSG_Math.h b/intern/csg/intern/CSG_Math.h new file mode 100644 index 00000000000..0c41e3d63ae --- /dev/null +++ b/intern/csg/intern/CSG_Math.h @@ -0,0 +1,152 @@ +#ifndef __CSG_MATH_H +#define __CSG_MATH_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "MT_Plane3.h" +#include "MT_Matrix3x3.h" +#include "MT_Line3.h" +#include "CSG_BBox.h" + +// useful geometry functions. +///////////////////////////// + +const int cofacTable[3][2] = {{1,2},{0,2},{0,1}}; + +class CSG_Geometry +{ +public : + + static bool Intersect( + const MT_Plane3& p1, + const MT_Plane3& p2, + MT_Line3& output + ); + + // Return intersection of line1 and line 2 in the plane formed by the given + // standard axis. Intersection l1Param is the intersection parameter of line1. + static bool Intersect2D( + const MT_Line3& l1, + const MT_Line3& l2, + int majAxis, + MT_Scalar& l1Param + ); + + static bool Intersect2DBoundsCheck( + const MT_Line3& l1, + const MT_Line3& l2, + int majAxis, + MT_Scalar& l1Param, + MT_Scalar& l2Param + ); + + static bool Intersect2DNoBoundsCheck( + const MT_Line3& l1, + const MT_Line3& l2, + int majAxis, + MT_Scalar& l1Param, + MT_Scalar& l2Param + ); + + static int ComputeClassification( + const MT_Scalar& distance, + const MT_Scalar& epsilon + ); +}; + +// The template parameter TGBinder is a model of a Geometry Binder concept +// see CSG_GeometryBinder.h for an example. + +template <typename TGBinder> class CSG_Math +{ +public : + + static bool IntersectPolyWithLine2D( + const MT_Line3& l, + const TGBinder& p1, + const MT_Plane3& plane, + MT_Scalar& a, + MT_Scalar& b + ); + + static bool InstersectPolyWithLine3D( + const MT_Line3& l, + const TGBinder& p1, + const MT_Plane3& plane, + MT_Scalar& a + ); + + static bool PointInPolygonTest3D( + const TGBinder& p1, + const MT_Plane3& plane, + const MT_Point3& origin, + const MT_Point3& pointOnPlane + ); + + // Return the mid-point of the given polygon index. + static MT_Point3 PolygonMidPoint( + const TGBinder& p1 + ); + + static MT_Line3 PolygonMidPointRay( + const TGBinder& p1, + const MT_Plane3& plane + ); + + static MT_Plane3 ComputePlane( + const TGBinder &p1 + ); + + // Return a bounding box of the given polygon index. + static BBox FitBBox( + const TGBinder& p1 + ); + + // Return which side of the polygon the plane is on. + // 0 == 0n + // 1 == in + // 2 == out + // 3 == Straddle + static int WhichSide( + const TGBinder& p1, + const MT_Plane3& plane1 + ); + +}; + +template <class TGBinderA, class TGBinderB> class CSG_PolygonIntersector +{ +public : + + static bool IntersectPolygons ( + const TGBinderA& p1, + const TGBinderB& p2, + const MT_Plane3& plane1, + const MT_Plane3& plane2 + ); + +}; + + +#include "CSG_Math.inl" + +#endif + diff --git a/intern/csg/intern/CSG_Math.inl b/intern/csg/intern/CSG_Math.inl new file mode 100644 index 00000000000..73483ea41d6 --- /dev/null +++ b/intern/csg/intern/CSG_Math.inl @@ -0,0 +1,362 @@ +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ +#include "CSG_Math.h" +#include "MT_minmax.h" +#include "MT_Point2.h" +#include "MT_Vector2.h" +#include "MT_Plane3.h" + +#include <vector> + +using namespace std; + +inline bool CSG_Geometry::Intersect( + const MT_Plane3& p1, + const MT_Plane3& p2, + MT_Line3& output +) { + MT_Matrix3x3 mat; + mat[0] = p1.Normal(); + mat[1] = p2.Normal(); + mat[2] = mat[0].cross(mat[1]); + + if (mat[2].fuzzyZero()) + { + return false; + } + + MT_Vector3 aPoint(-p1.Scalar(),-p2.Scalar(),0); + + output = MT_Line3(MT_Point3(0,0,0) + mat.inverse()*aPoint ,mat[2]); + + assert(MT_fuzzyZero(p1.signedDistance(output.Origin()))); + assert(MT_fuzzyZero(p2.signedDistance(output.Origin()))); + + + return true; +} + +inline bool CSG_Geometry::Intersect2DNoBoundsCheck( + const MT_Line3& l1, + const MT_Line3& l2, + int majAxis, + MT_Scalar& l1Param, + MT_Scalar& l2Param +){ + int ind1 = cofacTable[majAxis][0]; + int ind2 = cofacTable[majAxis][1]; + + MT_Scalar Zx = l2.Origin()[ind1] - l1.Origin()[ind1]; + MT_Scalar Zy = l2.Origin()[ind2] - l1.Origin()[ind2]; + + MT_Scalar det = l1.Direction()[ind1]*l2.Direction()[ind2] - + l2.Direction()[ind1]*l1.Direction()[ind2]; + + if (MT_fuzzyZero(det)) + { + return false; + } + + l1Param = (l2.Direction()[ind2]*Zx - l2.Direction()[ind1]*Zy)/det; + l2Param = -(-l1.Direction()[ind2]*Zx + l1.Direction()[ind1]*Zy)/det; + + return true; +} + + +inline bool CSG_Geometry::Intersect2DBoundsCheck( + const MT_Line3& l1, + const MT_Line3& l2, + int majAxis, + MT_Scalar& l1Param, + MT_Scalar& l2Param +) { + + bool isect = Intersect2DNoBoundsCheck(l1,l2,majAxis,l1Param,l2Param); + if (!isect) return false; + + return l1.IsParameterOnLine(l1Param) && l2.IsParameterOnLine(l2Param); +} + + +//IMplementation of CSG_Math +//////////////////////////// + +template<typename TGBinder> +inline bool CSG_Math<TGBinder>::IntersectPolyWithLine2D( + const MT_Line3& l, + const TGBinder& p1, + const MT_Plane3& plane, + MT_Scalar& a, + MT_Scalar& b +){ + int majAxis = plane.Normal().closestAxis(); + int lastInd = p1.Size()-1; + + b = (-MT_INFINITY); + a = (MT_INFINITY); + + MT_Scalar isectParam(0); + MT_Scalar isectParam2(0); + + int i; + int j = lastInd; + int isectsFound(0); + for (i=0;i<=lastInd; j=i,i++ ) + { + MT_Line3 testLine(p1[j],p1[i]); + if ( CSG_Geometry::Intersect2DBoundsCheck(l,testLine,majAxis,isectParam,isectParam2)) + { + ++isectsFound; + b = MT_max(isectParam,b); + a = MT_min(isectParam,a); + } + } + + return (isectsFound > 0); +} + +template<typename TGBinder> +inline bool CSG_Math<TGBinder>::InstersectPolyWithLine3D( + const MT_Line3& l, + const TGBinder& p1, + const MT_Plane3& plane, + MT_Scalar& a +){ + // First compute intersection parameter t + MT_Scalar determinant = l.Direction().dot(plane.Normal()); + + // they are coplanar but we're not interested in that right? + if (MT_fuzzyZero(determinant)) return false; + + a = -plane.Scalar() - plane.Normal().dot(l.Origin()); + a /= determinant; + + // intersection point is behind the ray. + if (a <= 0 ) return false; + + + // check if line is bounded and if t lies in bounds. + if (!l.IsParameterOnLine(a)) return false; + + // calculate the point on the plane + MT_Point3 pointOnPlane = l.Origin() + l.Direction()*a; + + assert(MT_fuzzyZero(plane.signedDistance(pointOnPlane))); + + // make sure the intersection point is within the polygon + return PointInPolygonTest3D(p1,plane,l.Origin(),pointOnPlane); +} + + + +template<typename TGBinder> +inline bool CSG_Math<TGBinder>::PointInPolygonTest3D( + const TGBinder& p1, + const MT_Plane3& plane, + const MT_Point3& origin, + const MT_Point3& pointOnPlane +) { + // Form planes with the edges of the polygon and the origin. + // make sure that origin is inside all these planes. + + // ONe small detail we have to first workout which side the origin + // is wrt the plane of the polygon. + + bool discardSign = plane.signedDistance(origin) < 0 ? true : false; + + const int polySize = p1.Size(); + + MT_Point3 lastPoint = p1[polySize-1]; + + int i; + for (i=0;i<polySize; ++i) + { + const MT_Point3& aPoint = p1[i]; + + MT_Plane3 testPlane(origin,lastPoint,aPoint); + if ((testPlane.signedDistance(pointOnPlane) <= 0) == discardSign) + { + return false; + } + lastPoint = aPoint; + } + return true; +} + +// return 0 = on +// return 1 = in +// return 2 = out + +inline int CSG_Geometry::ComputeClassification( + const MT_Scalar& distance, + const MT_Scalar& epsilon +) { + if (MT_abs(distance) < epsilon) + { + return 0; + } else { + return distance < 0 ? 1 : 2; + } +} + +// Return the mid-point of the given polygon index. +template <typename TGBinder> +inline MT_Point3 CSG_Math<TGBinder>::PolygonMidPoint( + const TGBinder& p1 +){ + + MT_Point3 midPoint(0,0,0); + + int i; + for (i=0; i < p1.Size(); i++) + { + midPoint += p1[i]; + } + + return MT_Point3(midPoint[0]/i,midPoint[1]/i,midPoint[2]/i); +} + +template <typename TGBinder> +int CSG_Math<TGBinder>::WhichSide( + const TGBinder& p1, + const MT_Plane3& plane1 +){ + + int output = 0; + int i; + for (i=0; i<p1.Size(); i++) + { + MT_Scalar signedDistance = plane1.signedDistance(p1[i]); + if (!MT_fuzzyZero(signedDistance)) + { + signedDistance < 0 ? (output |= 1) : (output |=2); + } + } + return output; + +} + + +template <typename TGBinder> +inline MT_Line3 CSG_Math<TGBinder>::PolygonMidPointRay( + const TGBinder& p1, + const MT_Plane3& plane +){ + return MT_Line3(PolygonMidPoint(p1),plane.Normal(),true,false); +} + +template <typename TGBinder> +inline MT_Plane3 CSG_Math<TGBinder>::ComputePlane( + const TGBinder &poly +){ + assert(poly.Size() >= 3); + MT_Point3 plast(poly[poly.Size()-1]); + MT_Point3 pivot; + MT_Vector3 edge; + int j; + for (j=0; j < poly.Size(); j++) + { + pivot = poly[j]; + edge = pivot - plast; + if (!edge.fuzzyZero()) break; + } + + for (; j < poly.Size(); j++) + { + MT_Vector3 v2 = poly[j] - pivot; + MT_Vector3 v3 = edge.cross(v2); + if (!v3.fuzzyZero()) + { + return MT_Plane3(v3,pivot); + } + } + + return MT_Plane3(); + +} + +template <typename TGBinder> +inline BBox CSG_Math<TGBinder>::FitBBox( + const TGBinder& p1 +) { + BBox bbox; + bbox.SetEmpty(); + + for (int i = 0; i < p1.Size(); ++i) { + bbox.Include(p1[i]); + } + return bbox; +} + +// we now have enough machinary to intersect 3d polygons +// Compute line of intersect +// Intersect line with each edge in PolygonB record min and max intersection parameters +// Do same for PolygonB. If range of intersections overlap then polys overlap. + +// Does not yet deal with 2d case. + +template<typename TGBinderA, typename TGBinderB> +inline bool CSG_PolygonIntersector<TGBinderA,TGBinderB>::IntersectPolygons ( + const TGBinderA& p1, + const TGBinderB& p2, + const MT_Plane3& plane1, + const MT_Plane3& plane2 +){ + MT_Line3 intersectLine; + if (!CSG_Geometry::Intersect(plane1,plane2,intersectLine)) + { + // parrallel planes + return false; + } + // check intersection of polygons with intersectLine + MT_Scalar p1A,p1B; + MT_Scalar p2A,p2B; + if ( + !CSG_Math<TGBinderA>::IntersectPolyWithLine2D(intersectLine,p1,plane1,p1A,p1B) || + !CSG_Math<TGBinderB>::IntersectPolyWithLine2D(intersectLine,p2,plane2,p2A,p2B) + ) { + return false; + } + + // see if intersections overlap. + + MT_Scalar maxOMin = MT_max(p1A,p2A); + MT_Scalar minOMax = MT_min(p1B,p2B); + + return (maxOMin <= minOMax); +} + + + + + + + + + + + + + + + + diff --git a/intern/csg/intern/CSG_Mesh.h b/intern/csg/intern/CSG_Mesh.h new file mode 100644 index 00000000000..bd687824484 --- /dev/null +++ b/intern/csg/intern/CSG_Mesh.h @@ -0,0 +1,66 @@ +#ifndef __MESH_H +#define __MESH_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "CSG_GeometryBinder.h" +#include <vector> + +// Simple vertex polygon container class +//-------------------------------------- + +template <typename TPolygon, typename TVertex> class Mesh +{ +public : + typedef std::vector<TVertex> VLIST; + typedef std::vector<TPolygon> PLIST; + + typedef TPolygon Polygon; + typedef TVertex Vertex; + + typedef PolygonGeometry<Mesh> TGBinder; + +private : + + VLIST m_verts; + PLIST m_polys; + + MT_Point3 m_bBoxMin; + MT_Point3 m_bBoxMax; + + +public : + + Mesh(): + m_verts(), + m_polys() + {}; + + VLIST& Verts() {return m_verts;} + const VLIST& Verts() const {return m_verts;} + + PLIST& Polys() {return m_polys;} + const PLIST& Polys() const {return m_polys;} + + ~Mesh() {} +}; + +#endif diff --git a/intern/csg/intern/CSG_MeshCopier.h b/intern/csg/intern/CSG_MeshCopier.h new file mode 100644 index 00000000000..4acf4440df6 --- /dev/null +++ b/intern/csg/intern/CSG_MeshCopier.h @@ -0,0 +1,45 @@ +#ifndef CSG_MeshCopier_H +#define CSG_MeshCopier_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + + +template <typename MeshA, typename MeshB> class MeshCopier +{ +public : + + static void Copy(const MeshA& source, MeshB& output) + { + int vertexNum = source.Verts().size(); + int polyNum = source.Polys().size(); + + output.Verts() = MeshB::VLIST(vertexNum); + output.Polys() = MeshB::PLIST(polyNum); + + std::copy(source.Verts().begin(),source.Verts().end(),output.Verts().begin()); + std::copy(source.Polys().begin(),source.Polys().end(),output.Polys().begin()); + + } + +}; + +#endif + diff --git a/intern/csg/intern/CSG_MeshWrapper.h b/intern/csg/intern/CSG_MeshWrapper.h new file mode 100644 index 00000000000..b557dde37c9 --- /dev/null +++ b/intern/csg/intern/CSG_MeshWrapper.h @@ -0,0 +1,110 @@ +#ifndef CSG_MESH_WRAPPER_H +#define CSG_MESH_WRAPPER_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +// This class wraps a mesh providing +// simple mesh functions required by the CSG library. +// TMesh is a model of a mesh and as such should have the +// following public typedefs and functions +// +// TMesh::Vertex the vertex type +// TMesh::Polygon the polygon type. +// TMesh::VLIST an stl container of Vertex objects +// TMesh::PLIST an stl container of Polygon objects +// +// VLIST& Verts(); +// const VLIST& Verts(); +// +// PLIST& Polys(); +// const PLIST& Polys(); + +#include "CSG_GeometryBinder.h" +#include "MT_Transform.h" +#include "CSG_BBox.h" + +#include <vector> + +template <typename TMesh> class MeshWrapper +{ +public : + + typedef TMesh::Polygon Polygon; + typedef TMesh::Vertex Vertex; + + typedef TMesh::VLIST VLIST; + typedef TMesh::PLIST PLIST; + + typedef PolygonGeometry<MeshWrapper> TGBinder; + + typedef MeshWrapper<TMesh> MyType; + +private : + TMesh& m_mesh; + +public : + + // Mesh Template interface + ////////////////////////// + + VLIST& Verts() {return m_mesh.Verts();} + const VLIST& Verts() const {return m_mesh.Verts();} + + PLIST& Polys() {return m_mesh.Polys();} + const PLIST& Polys() const {return m_mesh.Polys();} + + // Mesh Wrapper functions + ///////////////////////// + + MeshWrapper(TMesh& mesh) + : m_mesh(mesh) + {} + + void ComputePlanes(); + + void BurnTransform(const MT_Transform& t); + + BBox ComputeBBox() const; + + // Triangulate this mesh - does not preserve vertex->polygon information. + void Triangulate(); + + // Split the polygon at position p1Index in the mesh mesh1 into 2 pieces. + // Remove the polygon p1 and add the 2 pieces (along with the 2 new vertices) + // to the mesh. Returns the index of the 2 new pieces in the mesh.(either of [but never both] which can be + // -1 if there was nothing to split. + + void SplitPolygon( + const int p1Index, + const MT_Plane3& plane, + int& inPiece, + int& outPiece, + const MT_Scalar onEpsilon + ); + + + ~MeshWrapper(){}; + +}; + +#include "CSG_MeshWrapper.inl" + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/CSG_MeshWrapper.inl b/intern/csg/intern/CSG_MeshWrapper.inl new file mode 100644 index 00000000000..7a9a141e92a --- /dev/null +++ b/intern/csg/intern/CSG_MeshWrapper.inl @@ -0,0 +1,150 @@ +// Implementation of MeshWrapper template class. +//////////////////////////////////////////////// +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ +#include "CSG_Math.h" +#include "CSG_Triangulate.h" +#include "CSG_SplitFunction.h" + +template <typename TMesh> +void MeshWrapper<TMesh>::ComputePlanes() +{ + PLIST& polyList = Polys(); + + int i; + for (i=0;i < polyList.size(); i++) + { + TGBinder binder(m_mesh,i); + polyList[i].SetPlane(CSG_Math<TGBinder>::ComputePlane(binder)); + } +} + +template <typename TMesh> +void MeshWrapper<TMesh>::BurnTransform(const MT_Transform& t) +{ + VLIST& vertexList = Verts(); + + int i; + for (i=0;i<vertexList.size(); i++) + { + vertexList[i].Pos() = t * vertexList[i].Pos(); + } + ComputePlanes(); + +} + +template <typename TMesh> +BBox MeshWrapper<TMesh>::ComputeBBox() const +{ + const VLIST& vertexList = Verts(); + + BBox bbox; + bbox.SetEmpty(); + + int i; + for (i=0;i<vertexList.size(); i++) + { + bbox.Include(vertexList[i].Pos()); + } + return bbox; + +} + + +template <typename TMesh> +void MeshWrapper<TMesh>::Triangulate() +{ + vector<Polygon> newPolys; + + CSG_Triangulate<TGBinder> triangulator; + int i; + for (i=0; i< Polys().size(); ++i) + { + TGBinder pg(m_mesh,i); + const Polygon& poly = Polys()[i]; + + if (pg.Size() >= 4) + { + VIndexList triangleList; + + if (triangulator.Process(pg,poly.Plane(),triangleList)) + { + + // translate the triangle list into the real vertex properties + int tSize = triangleList.size(); + Polygon::TVPropList triangleProps(tSize); + + int j; + for (j=0; j < tSize; j++) + { + triangleProps[j] = poly.VertexProps(triangleList[j]); + } + + // iterate through the new triangles + for (j=0; j < tSize; j+=3) + { + // copy the polygon + newPolys.push_back(poly); + newPolys.back().Verts().clear(); + + // copy the relevant triangle indices + newPolys.back().Verts().assign(triangleProps.begin() + j,triangleProps.begin() + j +3); + } + + } + } else { + if (pg.Size() >= 3) { + newPolys.push_back(poly); + } + } + } + + // replace our polygons with the new ones. + Polys() = newPolys; +}; + +template<typename TMesh> +void MeshWrapper<TMesh>::SplitPolygon( + const int p1Index, + const MT_Plane3& plane, + int& inPiece, + int& outPiece, + const MT_Scalar onEpsilon +){ + + DefaultSplitFunctionBindor<TMesh::Polygon::TVProp> defaultSplitFunction; + + SplitFunction<MyType,DefaultSplitFunctionBindor<TMesh::Polygon::TVProp> > splitFunction(*this,defaultSplitFunction); + splitFunction.SplitPolygon(p1Index,plane,inPiece,outPiece,onEpsilon); + +} + + + + + + + + + + + + diff --git a/intern/csg/intern/CSG_Polygon.h b/intern/csg/intern/CSG_Polygon.h new file mode 100644 index 00000000000..8332977da71 --- /dev/null +++ b/intern/csg/intern/CSG_Polygon.h @@ -0,0 +1,93 @@ +#ifndef __POLYGON_H +#define __POLYGON_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "CSG_IndexDefs.h" + +#include <algorithm> +#include "MT_Plane3.h" +#include "MT_Point3.h" + +template <typename AVProp, typename AFProp> class PolygonBase +{ +public : + + // The per vertex properties + typedef AVProp TVProp; + + // The per face properties + typedef AFProp TFProp; + + typedef std::vector<TVProp> TVPropList; + typedef TVPropList::iterator TVPropIt; + + // Functions required by the CSG library + //////////////////////////////////////// + + PolygonBase():m_fProp(){} + + const TVPropList& Verts() const { return m_verts;} + TVPropList& Verts() { return m_verts;} + + int Size() const { return m_verts.size();} + + int operator[](int i) const {return m_verts[i];} + + const TVProp& VertexProps(int i) const { return m_verts[i];} + TVProp& VertexProps(int i) { return m_verts[i];} + + void SetPlane(const MT_Plane3& plane) { m_plane = plane;} + + const MT_Plane3& Plane() const { return m_plane;} + MT_Vector3 Normal() const { return m_plane.Normal();} + + int & Classification() { return m_classification;} + const int& Classification() const { return m_classification;} + + // Reverse this polygon. + void Reverse() + { + std::reverse(m_verts.begin(),m_verts.end()); + m_plane.Invert(); + } + + // Our functions + //////////////// + + TFProp& FProp(){ return m_fProp;} + const TFProp& FProp() const { return m_fProp;} + + ~PolygonBase() {} + +private : + + TVPropList m_verts; + MT_Plane3 m_plane; + + TFProp m_fProp; + + // gross waste of bits! 1 = in, 2 = out; + int m_classification; + +}; + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/CSG_SplitFunction.h b/intern/csg/intern/CSG_SplitFunction.h new file mode 100644 index 00000000000..70929a3d4ec --- /dev/null +++ b/intern/csg/intern/CSG_SplitFunction.h @@ -0,0 +1,188 @@ +#ifndef CCG_SplitFunction_H +#define CCG_SplitFunction_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +// This class contains the all important split function. +// It's a bit of weird definition but doing it like this +// means we don't have to copy any code between implementations +// that preserve mesh connectivity and those that introduce T junctions. + +template <typename TMesh, typename TSplitFunctionBindor> class SplitFunction +{ +private : + + TMesh& m_mesh; + TSplitFunctionBindor& m_functionBindor; + +public : + + SplitFunction( TMesh& mesh, TSplitFunctionBindor& functionBindor) + : m_mesh(mesh), m_functionBindor(functionBindor) + {}; + + void + SplitPolygon( + const int p1Index, + const MT_Plane3& plane, + int& inPiece, + int& outPiece, + const MT_Scalar onEpsilon + ){ + + const TMesh::Polygon& p = m_mesh.Polys()[p1Index]; + TMesh::Polygon inP(p),outP(p); + + inP.Verts().clear(); + outP.Verts().clear(); + + // Disconnect the polygon from the mesh. + m_functionBindor.DisconnectPolygon(p1Index); + + int lastIndex = p.Verts().back(); + MT_Point3 lastVertex = m_mesh.Verts()[lastIndex].Pos(); + + int lastClassification = CSG_Geometry::ComputeClassification(plane.signedDistance(lastVertex),onEpsilon); + int totalClassification(lastClassification); + + // iterate through the vertex indices of the to-be-split polygon + + int i; + int j=p.Size()-1; + for (i = 0; i < p.Size(); j = i, ++i) + { + int newIndex = p[i]; + MT_Point3 aVertex = m_mesh.Verts()[newIndex].Pos(); + int newClassification = CSG_Geometry::ComputeClassification(plane.signedDistance(aVertex),onEpsilon); + + // if neither the new vertex nor the old vertex were on and they differ + if ((newClassification != lastClassification) && newClassification && lastClassification) + { + // create new vertex + int newVertexIndex = m_mesh.Verts().size(); + m_mesh.Verts().push_back(TMesh::Vertex()); + + // work out new vertex position. + MT_Vector3 v = aVertex - lastVertex; + MT_Scalar sideA = plane.signedDistance(lastVertex); + + MT_Scalar epsilon = -sideA/plane.Normal().dot(v); + m_mesh.Verts().back().Pos() = lastVertex + (v * epsilon); + + // Make a new VertexProp + TMesh::Polygon::TVProp splitProp(newVertexIndex,p.VertexProps(j),p.VertexProps(i),epsilon); + + + // add new index to both polygons. + inP.Verts().push_back( splitProp ); + outP.Verts().push_back( splitProp ); + + // insert vertex into any neighbouring polygons of this edge + m_functionBindor.InsertVertexAlongEdge(lastIndex,newIndex,splitProp); + + } + + Classify(inP.Verts(),outP.Verts(),newClassification,p.VertexProps(i)); + lastClassification = newClassification; + totalClassification |= newClassification; + lastVertex = aVertex; + lastIndex = newIndex; + } + + if (totalClassification == 3) + { + // replace polygon p with the inpiece and add the outPiece to the back + // of the mesh. we just replace the vertices as the normal will be the same. + + inPiece = p1Index; + outPiece = m_mesh.Polys().size(); + + m_mesh.Polys()[p1Index] = inP; + m_mesh.Polys().push_back( outP ); + + m_functionBindor.ConnectPolygon(inPiece); + m_functionBindor.ConnectPolygon(outPiece); + + } else { + + // remember to connect back the original polygon! + m_functionBindor.ConnectPolygon(p1Index); + + // dont touch the mesh but just return the index of the original polygon + if (totalClassification == 1) + { + inPiece = p1Index; + outPiece = -1; + } else { + outPiece = p1Index; + inPiece = -1; + } + } + } + + + void Classify( + TMesh::Polygon::TVPropList &inGroup, + TMesh::Polygon::TVPropList &outGroup, + int classification, + TMesh::Polygon::TVProp prop + ) { + switch (classification) + { + case 0 : + inGroup.push_back(prop); + outGroup.push_back(prop); + break; + case 1 : + inGroup.push_back(prop); + break; + case 2 : + outGroup.push_back(prop); + break; + default : + break; + } + } + + ~SplitFunction() {}; +}; + + +template <typename PROP> class DefaultSplitFunctionBindor +{ +public : + + DefaultSplitFunctionBindor() {}; + + void DisconnectPolygon(int){ + } + + void ConnectPolygon(int) { + } + + void InsertVertexAlongEdge(int,int,const PROP& ) { + } + + ~DefaultSplitFunctionBindor(){}; +}; + + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/CSG_TreeQueries.h b/intern/csg/intern/CSG_TreeQueries.h new file mode 100644 index 00000000000..1b79d2ca36d --- /dev/null +++ b/intern/csg/intern/CSG_TreeQueries.h @@ -0,0 +1,158 @@ +#ifndef CSG_TREEQUERIES_H +#define CSG_TREEQUERIES_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "CSG_IndexDefs.h" +#include "CSG_BBoxTree.h" +#include "CSG_Math.h" + +template <typename TMesh> class TreeIntersector +{ +public : + + TreeIntersector( + const BBoxTree& a, + const BBoxTree& b, + OverlapTable *aOverlapsB, + OverlapTable *bOverlapsA, + const TMesh* meshA, + const TMesh* meshB + ) { + m_aOverlapsB = aOverlapsB; + m_bOverlapsA = bOverlapsA; + m_meshA = meshA; + m_meshB = meshB; + + MarkIntersectingPolygons(a.RootNode(),b.RootNode()); + } + +private : + + void MarkIntersectingPolygons(const BBoxNode*a,const BBoxNode *b) + { + if (!intersect(a->m_bbox, b->m_bbox)) return; + if (a->m_tag == BBoxNode::LEAF && b->m_tag == BBoxNode::LEAF) + { + const BBoxLeaf *la = (const BBoxLeaf *)a; + const BBoxLeaf *lb = (const BBoxLeaf *)b; + + PolygonGeometry<TMesh> pg1(*m_meshA,la->m_polyIndex); + PolygonGeometry<TMesh> pg2(*m_meshB,lb->m_polyIndex); + + if (CSG_PolygonIntersector<PolygonGeometry<TMesh>,PolygonGeometry<TMesh> >:: + IntersectPolygons(pg1,pg2, + m_meshA->Polys()[la->m_polyIndex].Plane(), + m_meshB->Polys()[lb->m_polyIndex].Plane() + ) + ) { + (*m_aOverlapsB)[lb->m_polyIndex].push_back(la->m_polyIndex); + (*m_bOverlapsA)[la->m_polyIndex].push_back(lb->m_polyIndex); + } + } else + if ( a->m_tag == BBoxNode::LEAF || + (b->m_tag != BBoxNode::LEAF && a->m_bbox.Size() < b->m_bbox.Size()) + ) { + MarkIntersectingPolygons(a,((const BBoxInternal *)b)->lson); + MarkIntersectingPolygons(a,((const BBoxInternal *)b)->rson); + } else { + MarkIntersectingPolygons(((const BBoxInternal *)a)->lson,b); + MarkIntersectingPolygons(((const BBoxInternal *)a)->rson,b); + } + } + + // Temporaries held through recursive intersection + OverlapTable* m_aOverlapsB; + OverlapTable* m_bOverlapsA; + const TMesh* m_meshA; + const TMesh* m_meshB; + +}; + +template<typename TMesh> class RayTreeIntersector +{ +public: + + RayTreeIntersector( + const BBoxTree& a, + const TMesh* meshA, + const MT_Line3& xRay, + int& polyIndex + ): + m_meshA(meshA), + m_polyIndex(-1), + m_lastIntersectValue(MT_INFINITY) + { + FindIntersectingPolygons(a.RootNode(),xRay); + polyIndex = m_polyIndex; + } + + +private : + + void FindIntersectingPolygons(const BBoxNode*a,const MT_Line3& xRay) + { + if ((xRay.Origin().x() + m_lastIntersectValue < a->m_bbox.Lower(0)) || + !a->m_bbox.IntersectXRay(xRay.Origin()) + ) { + // ray does not intersect this box. + return; + } + + if (a->m_tag == BBoxNode::LEAF) + { + const BBoxLeaf *la = (const BBoxLeaf *)a; + MT_Scalar testParameter(0); + + PolygonGeometry<TMesh> pg(*m_meshA,la->m_polyIndex); + + if ( + CSG_Math<PolygonGeometry<TMesh> >::InstersectPolyWithLine3D( + xRay,pg,m_meshA->Polys()[la->m_polyIndex].Plane(),testParameter + ) + ) { + if (testParameter < m_lastIntersectValue) + { + m_lastIntersectValue = testParameter; + m_polyIndex = la->m_polyIndex; + } + } + } else { + FindIntersectingPolygons(((const BBoxInternal*)a)->lson,xRay); + FindIntersectingPolygons(((const BBoxInternal*)a)->rson,xRay); + } + } + + const TMesh* m_meshA; + + MT_Scalar m_lastIntersectValue; + int m_polyIndex; +}; + + + + + + + + + +#endif diff --git a/intern/csg/intern/CSG_Triangulate.h b/intern/csg/intern/CSG_Triangulate.h new file mode 100644 index 00000000000..95c0b602ddf --- /dev/null +++ b/intern/csg/intern/CSG_Triangulate.h @@ -0,0 +1,96 @@ +#ifndef TRIANGULATE_H +#define TRIANGULATE_H + +/*****************************************************************/ +/** Static class to triangulate any contour/polygon efficiently **/ +/** You should replace Vector2d with whatever your own Vector **/ +/** class might be. Does not support polygons with holes. **/ +/** Uses STL vectors to represent a dynamic array of vertices. **/ +/** This code snippet was submitted to FlipCode.com by **/ +/** John W. Ratcliff (jratcliff@verant.com) on July 22, 2000 **/ +/** I did not write the original code/algorithm for this **/ +/** this triangulator, in fact, I can't even remember where I **/ +/** found it in the first place. However, I did rework it into **/ +/** the following black-box static class so you can make easy **/ +/** use of it in your own code. Simply replace Vector2d with **/ +/** whatever your own Vector implementation might be. **/ +/*****************************************************************/ + +#include "CSG_IndexDefs.h" +#include <vector> // Include STL vector class. +class MT_Plane3; + +template <typename PGBinder> class CSG_Triangulate +{ +public: + + CSG_Triangulate( + ); + + // triangulate a contour/polygon, places results in STL vector + // as series of triangles. IT uses the major axis of the normal + // to turn it into a 2d problem. + + // Should chaange this to accept a point array and a list of + // indices into that point array. Result should be indices of those + // indices. + // + // MT_Point3 global_array + // vector<BSP_VertexInd> polygon + // result is vector<int> into polygon. + + bool + Process( + const PGBinder& contour, + const MT_Plane3 &normal, + VIndexList &result + ); + + ~CSG_Triangulate( + ); + +private: + + // compute area of a contour/polygon + MT_Scalar + Area( + const PGBinder& contour + ); + + // decide if point Px/Py is inside triangle defined by + // (Ax,Ay) (Bx,By) (Cx,Cy) + + bool + InsideTriangle( + MT_Scalar Ax, MT_Scalar Ay, + MT_Scalar Bx, MT_Scalar By, + MT_Scalar Cx, MT_Scalar Cy, + MT_Scalar Px, MT_Scalar Py + ); + + + bool + Snip( + const PGBinder& contour, + int u, + int v, + int w, + int n, + int *V + ); + + int m_xi; + int m_yi; + int m_zi; + + // Temporary storage + + VIndexList m_V; + +}; + +#include "CSG_Triangulate.inl" + +#endif + + diff --git a/intern/csg/intern/CSG_Triangulate.inl b/intern/csg/intern/CSG_Triangulate.inl new file mode 100644 index 00000000000..d7f12201af3 --- /dev/null +++ b/intern/csg/intern/CSG_Triangulate.inl @@ -0,0 +1,232 @@ +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ +#include "MT_Plane3.h" +#include "MT_Point3.h" + +static const MT_Scalar EPSILON = MT_Scalar(1e-10); + +template <typename PGBinder> +CSG_Triangulate<PGBinder>:: +CSG_Triangulate( +): + m_xi(0), + m_yi(1) +{ +} + +template <typename PGBinder> +CSG_Triangulate<PGBinder>:: +~CSG_Triangulate( +){ +} + + +template <typename PGBinder> + MT_Scalar +CSG_Triangulate<PGBinder>:: +Area( + const PGBinder& contour +){ + + int n = contour.Size(); + MT_Scalar A(0.0); + + for(int p=n-1,q=0; q<n; p=q++) + { + A+= contour[p][m_xi]*contour[q][m_yi] - + contour[q][m_xi]*contour[p][m_yi]; + } + return A*MT_Scalar(0.5); +} + +/* + InsideTriangle decides if a point P is Inside of the triangle + defined by A, B, C. + Or within an epsilon of it. +*/ + +template <typename PGBinder> + bool +CSG_Triangulate<PGBinder>:: +InsideTriangle( + MT_Scalar Ax, MT_Scalar Ay, + MT_Scalar Bx, MT_Scalar By, + MT_Scalar Cx, MT_Scalar Cy, + MT_Scalar Px, MT_Scalar Py +){ + MT_Scalar ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy; + MT_Scalar cCROSSap, bCROSScp, aCROSSbp; + + ax = Cx - Bx; ay = Cy - By; + bx = Ax - Cx; by = Ay - Cy; + cx = Bx - Ax; cy = By - Ay; + apx= Px - Ax; apy= Py - Ay; + bpx= Px - Bx; bpy= Py - By; + cpx= Px - Cx; cpy= Py - Cy; + + aCROSSbp = ax*bpy - ay*bpx; + cCROSSap = cx*apy - cy*apx; + bCROSScp = bx*cpy - by*cpx; + + return ((aCROSSbp >= -EPSILON) && (bCROSScp >= -EPSILON) && (cCROSSap >= -EPSILON)); +}; + +template <typename PGBinder> + bool +CSG_Triangulate<PGBinder>:: +Snip( + const PGBinder& contour, + int u,int v, + int w,int n, + int *V +){ + MT_Scalar Ax, Ay, Bx, By, Cx, Cy; + + Ax = contour[V[u]][m_xi]; + Ay = contour[V[u]][m_yi]; + + Bx = contour[V[v]][m_xi]; + By = contour[V[v]][m_yi]; + + Cx = contour[V[w]][m_xi]; + Cy = contour[V[w]][m_yi]; + + // Snip is passes if the area of the candidate triangle is + // greater than 2*epsilon + // And if none of the remaining vertices are inside the polygon + // or within an epsilon of the boundary, + + if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false; +#if 1 + // this check is only needed for non-convex polygons + // well yeah but convex to me and you is not necessarily convex to opengl. + int p; + MT_Scalar Px,Py; + + for (p=0;p<n;p++) + { + if( (p == u) || (p == v) || (p == w) ) continue; + Px = contour[V[p]][m_xi]; + Py = contour[V[p]][m_yi]; + if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false; + } +#endif + return true; +} + +template <typename PGBinder> + bool +CSG_Triangulate<PGBinder>:: +Process( + const PGBinder& contour, + const MT_Plane3 &normal, + VIndexList &result +){ + + // Choose major axis of normal and assign + // 'projection' indices m_xi,m_yi; + + int maj_axis = normal.Normal().closestAxis(); + + if (maj_axis == 0) { + m_xi = 1; m_yi = 2; + } else + if (maj_axis == 1) { + m_xi = 0; m_yi = 2; + } else { + m_xi = 0; m_yi = 1; + } + m_zi = maj_axis; + + /* initialize list of Vertices in polygon */ + + int n = contour.Size(); + if ( n < 3 ) return false; + + /* we want a counter-clockwise polygon in V */ + /* to true but we also nead to preserve the winding order + of polygons going into the routine. We keep track of what + we did with a little bool */ + bool is_flipped = false; + + if ( 0.0f < Area(contour) ) { + for (int v=0; v<n; v++) m_V.push_back(v); + } else { + for(int v=0; v<n; v++) m_V.push_back((n-1)-v); + is_flipped = true; + } + + int nv = n; + + /* remove nv-2 Vertices, creating 1 triangle every time */ + int count = 2*nv; /* error detection */ + + for(int m=0, v=nv-1; nv>2; ) + { + /* if we loop, it is probably a non-simple polygon */ + if (0 >= (count--)) + { + //** Triangulate: ERROR - probable bad polygon! + m_V.clear(); + return false; + } + + /* three consecutive vertices in current polygon, <u,v,w> */ + int u = v ; if (nv <= u) u = 0; /* previous */ + v = u+1; if (nv <= v) v = 0; /* new v */ + int w = v+1; if (nv <= w) w = 0; /* next */ + + /* Try and snip this triangle off from the + current polygon.*/ + + if ( Snip(contour,u,v,w,nv,m_V.begin()) ) + { + int a,b,c,s,t; + + /* true names of the vertices */ + a = m_V[u]; b = m_V[v]; c = m_V[w]; + + /* output Triangle indices*/ + if (is_flipped) { + result.push_back( c ); + result.push_back( b ); + result.push_back( a ); + } else { + result.push_back( a ); + result.push_back( b ); + result.push_back( c ); + } + + m++; + + /* remove v from remaining polygon */ + for(s=v,t=v+1;t<nv;s++,t++) m_V[s] = m_V[t]; nv--; + + /* resest error detection counter */ + count = 2*nv; + } + } + + m_V.clear(); + return true; +} + + diff --git a/intern/csg/intern/CSG_Vertex.h b/intern/csg/intern/CSG_Vertex.h new file mode 100644 index 00000000000..bb39dbceab5 --- /dev/null +++ b/intern/csg/intern/CSG_Vertex.h @@ -0,0 +1,56 @@ +#ifndef __VERTEX_H +#define __VERTEX_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "MT_Point3.h" +#include <algorithm> +#include "CSG_IndexDefs.h" + + +class VertexBase +{ +protected: + + // Map to this vertex position in the classified Mesh + // or -1 if this vertex has not yet been used. + int m_vertexMap; + + MT_Point3 m_pos; + +public : + + VertexBase():m_vertexMap(-1) {}; + + // Regular vertex model + ////////////////////// + const MT_Point3& Pos() const { return m_pos;} + MT_Point3& Pos() {return m_pos;} + + int & VertexMap() { return m_vertexMap;} + const int & VertexMap() const { return m_vertexMap;} + + ~VertexBase(){}; +}; + +#endif + + diff --git a/intern/csg/intern/MT_Line3.cpp b/intern/csg/intern/MT_Line3.cpp new file mode 100644 index 00000000000..199eaea3390 --- /dev/null +++ b/intern/csg/intern/MT_Line3.cpp @@ -0,0 +1,81 @@ +//implementation of MT_Line3 +///////////////////////////// +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "MT_Line3.h" + +MT_Line3::MT_Line3() +: + m_origin(0,0,0), + m_dir(1,0,0) +{ + m_bounds[0] = false; + m_bounds[1] = false; + + m_params[0] = 0; + m_params[1] = 1; +} + + +MT_Line3::MT_Line3( + const MT_Point3& p1, + const MT_Point3& p2 +): + m_origin(p1), + m_dir(p2-p1) +{ + m_bounds[0] = true; + m_bounds[1] = true; + m_params[0] = 0; + m_params[1] = 1; +} + +// construct infinite line from p1 in direction v +MT_Line3::MT_Line3( + const MT_Point3& p1, + const MT_Vector3& v +): + m_origin(p1), + m_dir(v) +{ + m_bounds[0] = false; + m_bounds[1] = false; + m_params[0] = 0; + m_params[1] = 1; +} + +MT_Line3::MT_Line3( + const MT_Point3& p1, + const MT_Vector3& v, + bool bound1, + bool bound2 +): + m_origin(p1), + m_dir(v) +{ + m_bounds[0] = bound1; + m_bounds[1] = bound2; + m_params[0] = 0; + m_params[1] = 1; +} + + diff --git a/intern/csg/intern/MT_Line3.h b/intern/csg/intern/MT_Line3.h new file mode 100644 index 00000000000..e36f3995b91 --- /dev/null +++ b/intern/csg/intern/MT_Line3.h @@ -0,0 +1,109 @@ +#ifndef __CGS_LINE_H +#define __CGS_LINE_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "MT_Point3.h" +#include "MT_Vector3.h" + +class MT_Line3 +{ +public : + + MT_Line3(); + + // construct closed line segment from p1 -> p2 + MT_Line3(const MT_Point3& p1, const MT_Point3& p2); + + // construct infinite line from p1 in direction v + MT_Line3(const MT_Point3& p1, const MT_Vector3& v); + + MT_Line3(const MT_Point3& p1, const MT_Vector3& v, bool bound1, bool bound2); + + // return an infinite ray from the point p1 in the direction v + static MT_Line3 InfiniteRay(const MT_Point3& p1, const MT_Vector3& v); + + // return direction of line + const MT_Vector3& Direction() const { return m_dir;} + + // return a point on the line + const MT_Point3& Origin() const { return m_origin;} + + bool Bounds(int i) const { + return (i == 0 ? m_bounds[0] : m_bounds[1]); + } + + bool & Bounds(int i) { + return (i == 0 ? m_bounds[0] : m_bounds[1]); + } + + const MT_Scalar& Param(int i) const { + return (i == 0 ? m_params[0] : m_params[1]); + } + + MT_Scalar& Param(int i){ + return (i == 0 ? m_params[0] : m_params[1]); + } + + // Return the smallest Vector from the point to the line + // does not take into account bounds of line. + MT_Vector3 UnboundSmallestVector(const MT_Point3& point) const + { + MT_Vector3 diff(m_origin-point); + return diff - m_dir * diff.dot(m_dir); + } + + // Return the closest parameter of the line to the + // point. + MT_Scalar UnboundClosestParameter(const MT_Point3& point) const + { + MT_Vector3 diff(m_origin-point); + return diff.dot(m_dir); + } + + MT_Scalar UnboundDistance(const MT_Point3& point) const + { + return UnboundSmallestVector(point).length(); + } + + // Return true if the line parameter t is actually within the line bounds. + bool IsParameterOnLine(const MT_Scalar &t) const + { + return ((m_params[0]-MT_EPSILON < t) || (!m_bounds[0])) && ((m_params[1] > t+MT_EPSILON) || (!m_bounds[1])); +// return ((m_params[0] < t) || (!m_bounds[0])) && ((m_params[1] > t ) || (!m_bounds[1])); + } + + +private : + + bool m_bounds[2]; + + MT_Scalar m_params[2]; + MT_Point3 m_origin; + MT_Vector3 m_dir; + +}; + + + + + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/blender/CSG_BlenderMesh.h b/intern/csg/intern/blender/CSG_BlenderMesh.h new file mode 100644 index 00000000000..1f7a841d1e2 --- /dev/null +++ b/intern/csg/intern/blender/CSG_BlenderMesh.h @@ -0,0 +1,45 @@ +#ifndef CSG_BlenderMesh_H +#define CSG_BlenderMesh_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +//typedefs for types used to represent blender meshes in the CSG library + +#include "CSG_IndexDefs.h" +#include "CSG_ConnectedMesh.h" + +#include "CSG_Vertex.h" +#include "CSG_CVertex.h" +#include "CSG_Polygon.h" +#include "CSG_Mesh.h" +#include "CSG_MeshWrapper.h" +#include "CSG_Interface.h" +#include "CSG_BlenderVProp.h" + +typedef PolygonBase<BlenderVProp,CSG_IFaceData> TestPolygon; + +typedef Mesh<TestPolygon,VertexBase> AMesh; +typedef Mesh<TestPolygon,CVertex > AConnectedMesh; + +typedef MeshWrapper<AMesh> AMeshWrapper; +typedef ConnectedMeshWrapper<AConnectedMesh> AConnectedMeshWrapper; + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/blender/CSG_BlenderVProp.cpp b/intern/csg/intern/blender/CSG_BlenderVProp.cpp new file mode 100644 index 00000000000..6acbdf25e6f --- /dev/null +++ b/intern/csg/intern/blender/CSG_BlenderVProp.cpp @@ -0,0 +1,35 @@ +#include "CSG_Interface.h" +#include "CSG_BlenderVProp.h" +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ +#pragma warning( disable : 4786 ) + +int NoFunc( + const CSG_IFaceVertexData*, + const CSG_IFaceVertexData*, + CSG_IFaceVertexData*, + double +){ + return 0; +} + + +CSG_InterpolateUserFaceVertexDataFunc BlenderVProp::InterpFunc = &NoFunc;
\ No newline at end of file diff --git a/intern/csg/intern/blender/CSG_CsgOp.cpp b/intern/csg/intern/blender/CSG_CsgOp.cpp new file mode 100644 index 00000000000..1ff84ab0f3b --- /dev/null +++ b/intern/csg/intern/blender/CSG_CsgOp.cpp @@ -0,0 +1,257 @@ +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ +#pragma warning( disable : 4786 ) + +#include "CSG_CsgOp.h" +#include "CSG_BooleanOp.h" +#include "CSG_BBoxTree.h" +#include "CSG_Math.h" +#include "CSG_GeometryBinder.h" +#include "CSG_MeshCopier.h" + +#include "MEM_SmartPtr.h" + +using namespace std; + + void +BuildTree( + const AMesh& mesh, + BBoxTree& tree +) { + int numLeaves = mesh.Polys().size(); + + BBoxLeaf *aLeaves = new BBoxLeaf[numLeaves]; + + int i; + for (i=0;i< mesh.Polys().size(); i++) + { + PolygonGeometry<AMesh> pg(mesh,i); + aLeaves[i] = BBoxLeaf(i,CSG_Math<PolygonGeometry<AMesh> >::FitBBox(pg) ); + } + + tree.BuildTree(aLeaves,numLeaves); +} + + + void +ExtractClassificationPreserve( + const AMesh& meshA, + const AMesh& meshB, + const BBoxTree& aTree, + const BBoxTree& bTree, + const OverlapTable& aOverlapsB, + const OverlapTable& bOverlapsA, + int aClassification, + int bClassification, + bool reverseA, + bool reverseB, + AMesh& output +){ + + // Now we need to make a copy of each mesh and then partition each of those + // copies with respect to the original meshes. + AConnectedMesh meshAPartitioned; + AConnectedMesh meshBPartitioned; + + MeshCopier<AMesh,AConnectedMesh>::Copy(meshA,meshAPartitioned); + MeshCopier<AMesh,AConnectedMesh>::Copy(meshB,meshBPartitioned); + + AConnectedMeshWrapper meshAWrapper(meshAPartitioned); + AConnectedMeshWrapper meshBWrapper(meshBPartitioned); + + meshAWrapper.BuildVertexPolyLists(); + meshBWrapper.BuildVertexPolyLists(); + // Partition meshA wrt to meshB + BooleanOp<AConnectedMeshWrapper,AMesh>::PartitionMesh(meshAWrapper,meshB,bOverlapsA); + // and now meshB wrt meshA + BooleanOp<AConnectedMeshWrapper,AMesh>::PartitionMesh(meshBWrapper,meshA,aOverlapsB); + + // Classify the partioned meshes wrt to the originals. + BooleanOp<AConnectedMesh,AMesh>::ClassifyMesh(meshB,bTree,meshAPartitioned); + BooleanOp<AConnectedMesh,AMesh>::ClassifyMesh(meshA,aTree,meshBPartitioned); + + // Extract the classification we want from both meshes + BooleanOp<AConnectedMesh,AMesh>::ExtractClassification(meshAPartitioned, output,aClassification,reverseA); + BooleanOp<AConnectedMesh,AMesh>::ExtractClassification(meshBPartitioned, output,bClassification,reverseB); +} + + void +ExtractClassification( + const AMesh& meshA, + const AMesh& meshB, + const BBoxTree& aTree, + const BBoxTree& bTree, + const OverlapTable& aOverlapsB, + const OverlapTable& bOverlapsA, + int aClassification, + int bClassification, + bool reverseA, + bool reverseB, + AMesh& output +){ + // Now we need to make a copy of each mesh and then partition each of those + // copies with respect to the original meshes. + AMesh meshAPartitioned(meshA); + AMesh meshBPartitioned(meshB); + + AMeshWrapper meshAWrapper(meshAPartitioned); + AMeshWrapper meshBWrapper(meshBPartitioned); + + // Partition meshA wrt to meshB + BooleanOp<AMeshWrapper,AMesh>::PartitionMesh(meshAWrapper,meshB,bOverlapsA); + // and now meshB wrt meshA + BooleanOp<AMeshWrapper,AMesh>::PartitionMesh(meshBWrapper,meshA,aOverlapsB); + + // Classify the partioned meshes wrt to the originals. + BooleanOp<AMesh,AMesh>::ClassifyMesh(meshB,bTree,meshAPartitioned); + BooleanOp<AMesh,AMesh>::ClassifyMesh(meshA,aTree,meshBPartitioned); + + // Extract the classification we want from both meshes + BooleanOp<AMesh,AMesh>::ExtractClassification(meshAPartitioned, output,aClassification,reverseA); + BooleanOp<AMesh,AMesh>::ExtractClassification(meshBPartitioned, output,bClassification,reverseB); +} + + AMesh * +CsgOp:: +Intersect( + const AMesh& meshA, + const AMesh& meshB, + bool preserve +){ + // assumes they occups the same space and their planes have + // been computed. + + // First thing is to build a BBoxTree for each mesh. + BBoxTree aTree,bTree; + BuildTree(meshA,aTree); + BuildTree(meshB,bTree); + + // Build the overlap tables - they tell us which polygons from + // meshA overlap with those of meshB and vice versa + OverlapTable bOverlapsA(meshA.Polys().size()); + OverlapTable aOverlapsB(meshB.Polys().size()); + + BooleanOp<AMesh,AMesh>::BuildSplitGroup(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA); + + // Create a new mesh for the output + MEM_SmartPtr<AMesh> output = new AMesh; + if (output == NULL) return NULL; + + if (preserve) + { + ExtractClassificationPreserve(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA,1,1,false,false,output.Ref()); + } else { + ExtractClassification(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA,1,1,false,false,output.Ref()); + } + +#if 1 + // Triangulate the result + AMeshWrapper outputWrapper(output.Ref()); + outputWrapper.Triangulate(); +#endif + return output.Release(); +} + + + AMesh * +CsgOp:: +Union( + const AMesh& meshA, + const AMesh& meshB, + bool preserve +){ + // assumes they occups the same space and their planes have + // been computed. + + // First thing is to build a BBoxTree for each mesh. + BBoxTree aTree,bTree; + BuildTree(meshA,aTree); + BuildTree(meshB,bTree); + + // Build the overlap tables - they tell us which polygons from + // meshA overlap with those of meshB and vice versa + OverlapTable bOverlapsA(meshA.Polys().size()); + OverlapTable aOverlapsB(meshB.Polys().size()); + + BooleanOp<AMesh,AMesh>::BuildSplitGroup(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA); + + // Create a new mesh for the output + MEM_SmartPtr<AMesh> output = new AMesh; + if (output == NULL) return NULL; + + if (preserve) + { + ExtractClassificationPreserve(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA,2,2,false,false,output.Ref()); + } else { + ExtractClassification(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA,2,2,false,false,output.Ref()); + } + +#if 1 + // Triangulate the result + AMeshWrapper outputWrapper(output.Ref()); + outputWrapper.Triangulate(); +#endif + return output.Release(); +} + + AMesh * +CsgOp:: +Difference( + const AMesh& meshA, + const AMesh& meshB, + bool preserve +){ + + // assumes they occups the same space and their planes have + // been computed. + + // First thing is to build a BBoxTree for each mesh. + BBoxTree aTree,bTree; + BuildTree(meshA,aTree); + BuildTree(meshB,bTree); + + // Build the overlap tables - they tell us which polygons from + // meshA overlap with those of meshB and vice versa + OverlapTable bOverlapsA(meshA.Polys().size()); + OverlapTable aOverlapsB(meshB.Polys().size()); + + BooleanOp<AMesh,AMesh>::BuildSplitGroup(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA); + + // Create a new mesh for the output + MEM_SmartPtr<AMesh> output = new AMesh; + if (output == NULL) return NULL; + + if (preserve) + { + ExtractClassificationPreserve(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA,2,1,false,true,output.Ref()); + } else { + ExtractClassification(meshA,meshB,aTree,bTree,aOverlapsB,bOverlapsA,2,1,false,true,output.Ref()); + } + +#if 1 + // Triangulate the result + AMeshWrapper outputWrapper(output.Ref()); + outputWrapper.Triangulate(); +#endif + return output.Release(); +} + + diff --git a/intern/csg/intern/blender/CSG_CsgOp.h b/intern/csg/intern/blender/CSG_CsgOp.h new file mode 100644 index 00000000000..3b0e8b33766 --- /dev/null +++ b/intern/csg/intern/blender/CSG_CsgOp.h @@ -0,0 +1,59 @@ +#ifndef CSG_CsgOp_h +#define CSG_CsgOp_h +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "CSG_BlenderMesh.h" + + +class CsgOp +{ +public : + + static + AMesh * + Intersect( + const AMesh& meshA, + const AMesh& meshB, + bool preserve + ); + + static + AMesh * + Union( + const AMesh& meshA, + const AMesh& meshB, + bool preserve + ); + + static + AMesh * + Difference( + const AMesh& meshA, + const AMesh& meshB, + bool preserve + ); + + +}; + + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/blender/CSG_IndexDefs.h b/intern/csg/intern/blender/CSG_IndexDefs.h new file mode 100644 index 00000000000..f385537d0ac --- /dev/null +++ b/intern/csg/intern/blender/CSG_IndexDefs.h @@ -0,0 +1,22 @@ +#ifndef CSG_INDEXDEFS_H +#define CSG_INDEXDEFS_H + +//typdefs for lists and things in the CSG library + +#include <vector> + +typedef std::vector<int> PIndexList; +typedef PIndexList::iterator PIndexIt; +typedef PIndexList::const_iterator const_PIndexIt; + +typedef std::vector<int> VIndexList; +typedef VIndexList::iterator VIndexIt; +typedef VIndexList::const_iterator const_VIndexIt; + +typedef std::vector< PIndexList > OverlapTable; + + + +#endif + + diff --git a/intern/csg/intern/blender/CSG_Interface.cpp b/intern/csg/intern/blender/CSG_Interface.cpp new file mode 100644 index 00000000000..8b6415f1b3a --- /dev/null +++ b/intern/csg/intern/blender/CSG_Interface.cpp @@ -0,0 +1,193 @@ +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +/** + * Implementation of external C api for CSG lib . + */ +#pragma warning( disable : 4786 ) + +#include "CSG_Interface.h" +#include "CSG_Iterator.h" +#include "CSG_BlenderMesh.h" +#include "CSG_MeshBuilder.h" +#include "CSG_CsgOp.h" + +#include "MEM_SmartPtr.h" + +struct CSG_MeshInfo { + MEM_SmartPtr<AMesh> output_mesh; +}; + + CSG_BooleanOperation * +CSG_NewBooleanFunction( + void +){ + CSG_MeshInfo * mesh_info = new CSG_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; +} + + int +CSG_PerformBooleanOperation( + CSG_BooleanOperation * operation, + CSG_OperationType op_type, + CSG_FaceIteratorDescriptor obAFaces, + CSG_VertexIteratorDescriptor obAVertices, + CSG_FaceIteratorDescriptor obBFaces, + CSG_VertexIteratorDescriptor obBVertices, + CSG_InterpolateUserFaceVertexDataFunc interp_func +){ + + if (operation == NULL) return 0; + + CSG_MeshInfo * mesh_info = static_cast<CSG_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); + + MEM_SmartPtr<AMesh> outputMesh; + + try { + // Build the individual meshes + // set the face data size + BlenderVProp::InterpFunc = interp_func; + + MEM_SmartPtr<AMesh> obA = MeshBuilder::NewMesh(obAFaces,obAVertices); + + MEM_SmartPtr<AMesh> obB = MeshBuilder::NewMesh(obBFaces,obBVertices); + + if ( + obA == NULL || + obB == NULL + ) { + return 0; + } + + // build normals + AMeshWrapper aMeshWrap(obA.Ref()), bMeshWrap(obB.Ref()); + aMeshWrap.ComputePlanes(); + bMeshWrap.ComputePlanes(); + + // translate enums! + + switch(op_type) { + case e_csg_union : + case e_csg_classify : + outputMesh = CsgOp::Union(obA.Ref(),obB.Ref(),true); + break; + case e_csg_intersection : + outputMesh = CsgOp::Intersect(obA.Ref(),obB.Ref(),true); + break; + case e_csg_difference : + outputMesh = CsgOp::Difference(obA.Ref(),obB.Ref(),true); + break; + default : + return 0; + } + } + catch(...) { + return 0; + } + + // set the output mesh + mesh_info->output_mesh = outputMesh; + + return 1; +} + + int +CSG_OutputFaceDescriptor( + CSG_BooleanOperation * operation, + CSG_FaceIteratorDescriptor * output +){ + if (operation == NULL) return 0; + CSG_MeshInfo * mesh_info = static_cast<CSG_MeshInfo *>(operation->CSG_info); + + if (mesh_info == NULL) return 0; + if (mesh_info->output_mesh == NULL) return 0; + + AMesh_FaceIt_Construct(mesh_info->output_mesh,output); + return 1; +} + + + int +CSG_OutputVertexDescriptor( + CSG_BooleanOperation * operation, + CSG_VertexIteratorDescriptor *output +){ + if (operation == NULL) return 0; + CSG_MeshInfo * mesh_info = static_cast<CSG_MeshInfo *>(operation->CSG_info); + + if (mesh_info == NULL) return 0; + if (mesh_info->output_mesh == NULL) return 0; + + AMesh_VertexIt_Construct(mesh_info->output_mesh,output); + return 1; +} + + void +CSG_FreeVertexDescriptor( + CSG_VertexIteratorDescriptor * v_descriptor +){ + AMesh_VertexIt_Destruct(v_descriptor); +} + + + void +CSG_FreeFaceDescriptor( + CSG_FaceIteratorDescriptor * f_descriptor +){ + AMesh_FaceIt_Destruct(f_descriptor); +} + + + void +CSG_FreeBooleanOperation( + CSG_BooleanOperation *operation +){ + if (operation != NULL) { + CSG_MeshInfo * mesh_info = static_cast<CSG_MeshInfo *>(operation->CSG_info); + delete(mesh_info); + delete(operation); + } +} + + + + + + + + + + + + diff --git a/intern/csg/intern/blender/CSG_Iterator.h b/intern/csg/intern/blender/CSG_Iterator.h new file mode 100644 index 00000000000..e349229be9e --- /dev/null +++ b/intern/csg/intern/blender/CSG_Iterator.h @@ -0,0 +1,199 @@ + +#ifndef CSG_Iterator_H +#define CSG_Iterator_H + +#include "CSG_BlenderMesh.h" +#include "CSG_Interface.h" + +#include "MEM_SmartPtr.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 AMesh_VertexIt { + AMesh* mesh; + AMesh::VLIST::const_iterator pos; +}; + + +static + void +AMesh_VertexIt_Destruct( + CSG_VertexIteratorDescriptor * vIterator +) { + delete ((AMesh_VertexIt *)(vIterator->it)); + vIterator->it = NULL; + vIterator->Done = NULL; + vIterator->Fill = NULL; + vIterator->Reset = NULL; + vIterator->Step = NULL; + vIterator->num_elements = 0; +}; + + +static + int +AMesh_VertexIt_Done( + CSG_IteratorPtr it +) { + // assume CSG_IteratorPtr is of the correct type. + AMesh_VertexIt * vertex_it = (AMesh_VertexIt *)it; + + if (vertex_it->pos < vertex_it->mesh->Verts().end() ) return 0; + return 1; +}; + +static + void +AMesh_VertexIt_Fill( + CSG_IteratorPtr it, + CSG_IVertex *vert +) { + // assume CSG_IteratorPtr is of the correct type. + AMesh_VertexIt * vertex_it = (AMesh_VertexIt *)it; + + vertex_it->pos->Pos().getValue(vert->position); +}; + +static + void +AMesh_VertexIt_Step( + CSG_IteratorPtr it +) { + // assume CSG_IteratorPtr is of the correct type. + AMesh_VertexIt * vertex_it = (AMesh_VertexIt *)it; + + ++(vertex_it->pos); +}; + +static + void +AMesh_VertexIt_Reset( + CSG_IteratorPtr it +) { + // assume CSG_IteratorPtr is of the correct type. + AMesh_VertexIt * vertex_it = (AMesh_VertexIt *)it; + vertex_it->pos = vertex_it->mesh->Verts().begin(); +}; + +static + void +AMesh_VertexIt_Construct( + AMesh *mesh, + CSG_VertexIteratorDescriptor *output +){ + // user should have insured mesh is not equal to NULL. + + output->Done = AMesh_VertexIt_Done; + output->Fill = AMesh_VertexIt_Fill; + output->Step = AMesh_VertexIt_Step; + output->Reset = AMesh_VertexIt_Reset; + output->num_elements = mesh->Verts().size(); + + AMesh_VertexIt * v_it = new AMesh_VertexIt; + v_it->mesh = mesh; + v_it->pos = mesh->Verts().begin(); + output->it = v_it; +}; + + +/** + * Face iterator. + */ + +struct AMesh_FaceIt { + AMesh* mesh; + AMesh::PLIST::const_iterator pos; +}; + + +static + void +AMesh_FaceIt_Destruct( + CSG_FaceIteratorDescriptor *fIterator +) { + delete ((AMesh_FaceIt *)(fIterator->it)); + fIterator->it = NULL; + fIterator->Done = NULL; + fIterator->Fill = NULL; + fIterator->Reset = NULL; + fIterator->Step = NULL; + fIterator->num_elements = 0; +}; + + +static + int +AMesh_FaceIt_Done( + CSG_IteratorPtr it +) { + // assume CSG_IteratorPtr is of the correct type. + AMesh_FaceIt * face_it = (AMesh_FaceIt *)it; + + return face_it->pos >= face_it->mesh->Polys().end(); +}; + +static + void +AMesh_FaceIt_Fill( + CSG_IteratorPtr it, + CSG_IFace *face +){ + // assume CSG_IteratorPtr is of the correct type. + AMesh_FaceIt * face_it = (AMesh_FaceIt *)it; + + face->m_vertexData[0] = face_it->pos->VertexProps(0).Data(); + face->m_vertexData[1] = face_it->pos->VertexProps(1).Data(); + face->m_vertexData[2] = face_it->pos->VertexProps(2).Data(); + + face->m_vertexNumber =3; + face->m_faceData = face_it->pos->FProp(); +}; + +static + void +AMesh_FaceIt_Step( + CSG_IteratorPtr it +) { + // assume CSG_IteratorPtr is of the correct type. + AMesh_FaceIt * face_it = (AMesh_FaceIt *)it; + face_it->pos++; +}; + +static + void +AMesh_FaceIt_Reset( + CSG_IteratorPtr it +) { + // assume CSG_IteratorPtr is of the correct type. + AMesh_FaceIt * f_it = (AMesh_FaceIt *)it; + f_it->pos = f_it->mesh->Polys().begin(); +}; + +static + void +AMesh_FaceIt_Construct( + AMesh * mesh, + CSG_FaceIteratorDescriptor *output +) { + + output->Done = AMesh_FaceIt_Done; + output->Fill = AMesh_FaceIt_Fill; + output->Step = AMesh_FaceIt_Step; + output->Reset = AMesh_FaceIt_Reset; + + output->num_elements = mesh->Polys().size(); + + AMesh_FaceIt * f_it = new AMesh_FaceIt; + f_it->mesh = mesh; + f_it->pos = mesh->Polys().begin(); + + output->it = f_it; + +}; + + +#endif + diff --git a/intern/csg/intern/blender/CSG_MeshBuilder.h b/intern/csg/intern/blender/CSG_MeshBuilder.h new file mode 100644 index 00000000000..5d65acdab50 --- /dev/null +++ b/intern/csg/intern/blender/CSG_MeshBuilder.h @@ -0,0 +1,123 @@ +#ifndef CSG_MeshBuilder_H +#define CSG_MeshBuilder_H +/* + CSGLib - Software Library for Constructive Solid Geometry + Copyright (C) 2003-2004 Laurence Bourn + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + Please send remarks, questions and bug reports to laurencebourn@hotmail.com +*/ + +#include "CSG_IndexDefs.h" +#include "CSG_Vertex.h" +#include "CSG_Polygon.h" +#include "CSG_Interface.h" +#include "CSG_BlenderMesh.h" + +// build a mesh from external c interface to this module +//////////////////////////////////////////////////////// + +class MeshBuilder +{ + +public : + + // You must have set the size of the SimpleProps data ptr size + // before calling this function. + + static AMesh* NewMesh( + CSG_FaceIteratorDescriptor obBFaces, + CSG_VertexIteratorDescriptor obBVertices + ) { + + AMesh *output = new AMesh(); + + // first get the vertices. + AMesh::VLIST& verts = output->Verts(); + + verts.reserve(obBVertices.num_elements); + + obBVertices.Reset(obBFaces.it); + + CSG_IVertex iVert; + + while (!obBVertices.Done(obBVertices.it)) + { + obBVertices.Fill(obBVertices.it,&iVert); + + AMesh::Vertex aVertex; + aVertex.Pos().setValue(iVert.position); + verts.push_back(aVertex); + + obBVertices.Step(obBVertices.it); + } + + // now for the faces + //////////////////// + + AMesh::PLIST &faces = output->Polys(); + faces.reserve(obBFaces.num_elements); + + CSG_IFace iFace; + + while (!obBFaces.Done(obBFaces.it)) + { + obBFaces.Fill(obBFaces.it,&iFace); + + AMesh::Polygon aPolygon; + aPolygon.FProp() = iFace.m_faceData; + + int i; + for (i=0;i < 3; i++) + { + AMesh::Polygon::TVProp vProp; + vProp.Data() = iFace.m_vertexData[i]; + aPolygon.Verts().push_back(vProp); + } + faces.push_back(aPolygon); + + if (iFace.m_vertexNumber == 4) + { + AMesh::Polygon::TVProp vProp[3]; + vProp[0].Data() = iFace.m_vertexData[2]; + vProp[1].Data() = iFace.m_vertexData[3]; + vProp[2].Data() = iFace.m_vertexData[0]; + + aPolygon.VertexProps(0) = vProp[0]; + aPolygon.VertexProps(1) = vProp[1]; + aPolygon.VertexProps(2) = vProp[2]; + + faces.push_back(aPolygon); + } + + obBFaces.Step(obBFaces.it); + } + + return output; + } +}; + + +#endif + + + + + + + + +
\ No newline at end of file diff --git a/intern/csg/intern/blender/CSG_PropArray.h b/intern/csg/intern/blender/CSG_PropArray.h new file mode 100644 index 00000000000..7e28a2a417e --- /dev/null +++ b/intern/csg/intern/blender/CSG_PropArray.h @@ -0,0 +1,126 @@ +#ifndef CSG_IndexProp_H +#define CSG_IndexProp_H + +#include <vector> +#include <memory.h> +// Face and vertex props that are contained in a seperate array +// (PropArray) and indexed through a VProp compliant thing. + +typedef int (*CSG_InterpFunc)(const void *d1, const void * d2, void *dnew, float epsilon); + +class IndexProp +{ +private : + + int m_vIndex; + int m_size; + unsigned char *m_data; + mutable CSG_InterpFunc m_interpFunc; + +public : + + IndexProp(const int& vIndex) + : m_vIndex(vIndex), + m_size(0), + m_data(0) + {}; + + IndexProp( + const int& vIndex, + const IndexProp& p1, + const IndexProp& p2, + const MT_Scalar& epsilon + ): + m_vIndex(vIndex), + m_data(0) + { + SetInterpFunc(p1.m_interpFunc); + SetSize(p1.m_size); + m_interpFunc(p1.m_data,p2.m_data,m_data,(float)epsilon); + } + + IndexProp(const IndexProp& other) + : m_vIndex(other.m_vIndex), + m_data(0), + m_interpFunc(other.m_interpFunc) + { + SetInterpFunc(other.m_interpFunc); + SetSize(other.m_size); + memcpy(m_data,other.m_data,m_size); + } + + IndexProp( + ): m_vIndex(-1), + m_size(0), + m_data(0) + {}; + + // Support conversion to an integer + /////////////////////////////////// + operator int( + ) const { + return m_vIndex; + } + + // and assignment from an integer. + ////////////////////////////////// + IndexProp& + operator = ( + int i + ) { + m_vIndex = i; + return *this; + } + + IndexProp& + operator = ( + const IndexProp& other + ) { + m_vIndex = other.m_vIndex; + m_data = 0; + SetSize(other.m_size); + SetInterpFunc(other.m_interpFunc); + memcpy(m_data,other.m_data,m_size); + return *this; + } + + // Our local functions + ////////////////////// + + void SetInterpFunc(CSG_InterpFunc interpFunc) + { + m_interpFunc = interpFunc; + } + + void SetSize(int size) + { + delete[] m_data; + m_data = new unsigned char[size]; + m_size = size; + } + + int Size() const { + return m_size; + } + + void CopyData(const void * userData) + { + memcpy(m_data,userData,m_size); + } + + void Create(int size, const void * userData, CSG_InterpFunc interpFunc) + { + SetInterpFunc(interpFunc); + SetSize(size); + CopyData(userData); + } + + const unsigned char * GetData() const { return m_data;} + + ~IndexProp() { + delete[] m_data; + }; +}; + + +#endif
\ No newline at end of file diff --git a/intern/csg/intern/blender/CSG_SimpleProp.cpp b/intern/csg/intern/blender/CSG_SimpleProp.cpp new file mode 100644 index 00000000000..2c8f0eedae9 --- /dev/null +++ b/intern/csg/intern/blender/CSG_SimpleProp.cpp @@ -0,0 +1,4 @@ +#include "CSG_SimpleProp.h" + + +int SimpleProp::s_size = 4;
\ No newline at end of file diff --git a/intern/csg/intern/blender/CSG_SimpleProp.h b/intern/csg/intern/blender/CSG_SimpleProp.h new file mode 100644 index 00000000000..dc8ab45c6d8 --- /dev/null +++ b/intern/csg/intern/blender/CSG_SimpleProp.h @@ -0,0 +1,58 @@ +#ifndef CSG_SIMPLEPROP_H +#define CSG_SIMPLEPROP_H + +// Simple face prop contains a fixed size piece of memory +// initiated by the client and copied round through this +// value type by the CSG library. +#include <memory.h> + +class SimpleProp +{ +private : + + static int s_size; + unsigned char * m_data; + +public : + + static void SetSize(int size) { + s_size = size; + } + + static int Size() { + return s_size; + } + + SimpleProp() + : m_data(new unsigned char[s_size]) + {} + + SimpleProp(const SimpleProp& other) + : m_data(new unsigned char[s_size]) + { + memcpy(m_data,other.m_data,s_size); + } + + SimpleProp& operator = (const SimpleProp& other) + { + memcpy(m_data,other.m_data,s_size); + return *this; + } + + void SetData(const void * data) + { + memcpy(m_data,data,s_size); + } + + const unsigned char * Data() const { + return m_data; + } + + + ~SimpleProp() + { + delete[] m_data; + } +}; + +#endif
\ No newline at end of file diff --git a/intern/csg/make/msvc60/csg.dsp b/intern/csg/make/msvc60/csg.dsp new file mode 100644 index 00000000000..39c3895fb00 --- /dev/null +++ b/intern/csg/make/msvc60/csg.dsp @@ -0,0 +1,234 @@ +# Microsoft Developer Studio Project File - Name="csg" - Package Owner=<4> +# Microsoft Developer Studio Generated Build File, Format Version 6.00 +# ** DO NOT EDIT ** + +# TARGTYPE "Win32 (x86) Static Library" 0x0104 + +CFG=csg - Win32 Debug +!MESSAGE This is not a valid makefile. To build this project using NMAKE, +!MESSAGE use the Export Makefile command and run +!MESSAGE +!MESSAGE NMAKE /f "csg.mak". +!MESSAGE +!MESSAGE You can specify a configuration when running NMAKE +!MESSAGE by defining the macro CFG on the command line. For example: +!MESSAGE +!MESSAGE NMAKE /f "csg.mak" CFG="csg - Win32 Debug" +!MESSAGE +!MESSAGE Possible choices for configuration are: +!MESSAGE +!MESSAGE "csg - Win32 Release" (based on "Win32 (x86) Static Library") +!MESSAGE "csg - Win32 Debug" (based on "Win32 (x86) Static Library") +!MESSAGE + +# Begin Project +# PROP AllowPerConfigDependencies 0 +# PROP Scc_ProjName "" +# PROP Scc_LocalPath "" +CPP=cl.exe +RSC=rc.exe + +!IF "$(CFG)" == "csg - Win32 Release" + +# PROP BASE Use_MFC 0 +# PROP BASE Use_Debug_Libraries 0 +# PROP BASE Output_Dir "Release" +# PROP BASE Intermediate_Dir "Release" +# PROP BASE Target_Dir "" +# PROP Use_MFC 0 +# PROP Use_Debug_Libraries 0 +# PROP Output_Dir "..\..\..\..\obj\windows\intern\bsp\" +# PROP Intermediate_Dir "..\..\..\..\obj\windows\intern\bsp\" +# PROP Target_Dir "" +# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_MBCS" /D "_LIB" /YX /FD /c +# ADD CPP /nologo /G6 /MT /W3 /GX /Oy- /Ob0 /I "../../intern/blender" /I "../../extern" /I "../../intern" /I "../../../../lib/windows/memutil/include" /I "../.." /I "../../../../lib/windows/moto/include" /D "WIN32" /D "NDEBUG" /D "_MBCS" /D "_LIB" /FD /c +# SUBTRACT CPP /Ox /Ot /Og /YX +# ADD BASE RSC /l 0x413 /d "NDEBUG" +# ADD RSC /l 0x413 /d "NDEBUG" +BSC32=bscmake.exe +# ADD BASE BSC32 /nologo +# ADD BSC32 /nologo +LIB32=link.exe -lib +# ADD BASE LIB32 /nologo +# ADD LIB32 /nologo /out:"..\..\..\..\obj\windows\intern\bsp\libbsp.lib" +# Begin Special Build Tool +SOURCE="$(InputPath)" +PostBuild_Cmds=ECHO Copying header files XCOPY /E /Y ..\..\extern\*.h ..\..\..\..\lib\windows\bsp\include\ ECHO Copying lib XCOPY /E /Y ..\..\..\..\obj\windows\intern\bsp\*.lib ..\..\..\..\lib\windows\bsp\lib\*.a ECHO Done +# End Special Build Tool + +!ELSEIF "$(CFG)" == "csg - Win32 Debug" + +# PROP BASE Use_MFC 0 +# PROP BASE Use_Debug_Libraries 1 +# PROP BASE Output_Dir "Debug" +# PROP BASE Intermediate_Dir "Debug" +# PROP BASE Target_Dir "" +# PROP Use_MFC 0 +# PROP Use_Debug_Libraries 1 +# PROP Output_Dir "..\..\..\..\obj\windows\intern\bsp\debug\" +# PROP Intermediate_Dir "..\..\..\..\obj\windows\intern\bsp\debug\" +# PROP Target_Dir "" +# ADD BASE CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_MBCS" /D "_LIB" /YX /FD /GZ /c +# ADD CPP /nologo /MTd /W3 /Gm /GX /ZI /Od /I "../../intern/blender" /I "../../extern" /I "../../intern" /I "../../../../lib/windows/memutil/include" /I "../.." /I "../../../../lib/windows/moto/include" /D "WIN32" /D "_DEBUG" /D "_MBCS" /D "_LIB" /FD /GZ /c +# SUBTRACT CPP /X /YX +# ADD BASE RSC /l 0x413 /d "_DEBUG" +# ADD RSC /l 0x413 /d "_DEBUG" +BSC32=bscmake.exe +# ADD BASE BSC32 /nologo +# ADD BSC32 /nologo +LIB32=link.exe -lib +# ADD BASE LIB32 /nologo +# ADD LIB32 /nologo /out:"..\..\..\..\obj\windows\intern\bsp\debug\libbsp.lib" +# Begin Special Build Tool +SOURCE="$(InputPath)" +PostBuild_Cmds=ECHO Copying header files XCOPY /E /Y ..\..\extern\*.h ..\..\..\..\lib\windows\bsp\include\ ECHO Copying lib XCOPY /E /Y ..\..\..\..\obj\windows\intern\bsp\debug\*.lib ..\..\..\..\lib\windows\bsp\lib\debug\*.a ECHO Copying Debug info. XCOPY /E /Y ..\..\..\..\obj\windows\intern\bsp\debug\vc60.* ..\..\..\..\lib\windows\bsp\lib\debug\ ECHO Done +# End Special Build Tool + +!ENDIF + +# Begin Target + +# Name "csg - Win32 Release" +# Name "csg - Win32 Debug" +# Begin Group "AABBTree" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=..\..\intern\CSG_BBox.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_BBoxTree.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_BBoxTree.h +# End Source File +# End Group +# Begin Group "inlines" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=..\..\intern\CSG_ConnectedMeshWrapper.inl +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_Math.inl +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_Triangulate.inl +# End Source File +# End Group +# Begin Group "blender" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=..\..\intern\blender\CSG_BlenderMesh.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\blender\CSG_BlenderVProp.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_BlenderVProp.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\blender\CSG_CsgOp.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\blender\CSG_CsgOp.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\blender\CSG_Interface.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\extern\CSG_Interface.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\blender\CSG_MeshBuilder.h +# End Source File +# End Group +# Begin Source File + +SOURCE=..\..\intern\CSG_BooleanOp.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_BooleanOp.inl +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_ConnectedMesh.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_CVertex.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_GeometryBinder.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_IndexDefs.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_Math.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_Mesh.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_MeshCopier.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_MeshWrapper.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_MeshWrapper.inl +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_Polygon.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_SplitFunction.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_TreeQueries.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_Triangulate.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\CSG_Vertex.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\MT_Line3.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\MT_Line3.h +# End Source File +# End Target +# End Project diff --git a/intern/csg/make/msvc60/csg.dsw b/intern/csg/make/msvc60/csg.dsw new file mode 100644 index 00000000000..7f9bd29b97a --- /dev/null +++ b/intern/csg/make/msvc60/csg.dsw @@ -0,0 +1,29 @@ +Microsoft Developer Studio Workspace File, Format Version 6.00 +# WARNING: DO NOT EDIT OR DELETE THIS WORKSPACE FILE! + +############################################################################### + +Project: "csg"=.\csg.dsp - Package Owner=<4> + +Package=<5> +{{{ +}}} + +Package=<4> +{{{ +}}} + +############################################################################### + +Global: + +Package=<5> +{{{ +}}} + +Package=<3> +{{{ +}}} + +############################################################################### + |