Ok here is the new CSG library that implements boolean operations for blender through...
authorFrancis Laurence <laurencebourn@hotmail.com>
Tue, 10 Feb 2004 20:16:44 +0000 (20:16 +0000)
committerFrancis Laurence <laurencebourn@hotmail.com>
Tue, 10 Feb 2004 20:16:44 +0000 (20:16 +0000)
As mentioned earlier on bf-commiters mailing list, there is no current *nix make file only an msvc60 project file. I only have a linux box at work and to be honest I want to avoid doing any commits from there! So if some kind soul could sort it out that would be great.

Dependencies:
This code only depends on other stuff in the intern library, moto and memutils the CSG lib needs to have their include paths to compile. Other than that its completely self contained.

Acknowledgements:
To speed up the polygon-polygon intersection queries I've used some code (under the GPL) from freesolid2.0 this clearly marked in the appropriate files and Gino van den Bergen still owns the copyright to that material. The algorithm I used in based on one from Paul Nettle described on flipcode (www.flipcode.com) and I think his work was a derivative of the "Laidlaw algorithm"

There is also some basic 'ear clipping' triangulation code that unfortunately remains unatributable. I have no right to publish this code under the GPL nor BPL for that matter as I have no idea who the original authors are. Its just one of those random bits of internet code.

Warning!
The stuff used a lot of C++ template features, which on one hand makes it very generic but on the other means that some work will need to be done to get working with other compilters. The msvc60 compiler is not very compliant to the C++ standards with respect to templates so its very difficult to say if this code will compile out of the box on other platforms.

I still haven't committed modifications to booleanops.c in the blender code as without a working library to link to it will break the current build. This needs to be done first!

Improvements
This code is much simpler than the previous bsp implementation see intern/bsp and this old code should be deprectated/removed. However, whilst this implementation produces less triangles in the output than the bps algo, its still not an optimal solution. This is just hard to do and beyond my humble skills.

License:
Just to make it clear this stuff for the reasons mentioned above and for the fact I'm to mean to give the copyright away to BF is licensed under the GPL only.

Cheers,
Laurence.

39 files changed:
intern/csg/extern/CSG_Interface.h [new file with mode: 0644]
intern/csg/intern/CSG_BBox.h [new file with mode: 0644]
intern/csg/intern/CSG_BBoxTree.cpp [new file with mode: 0644]
intern/csg/intern/CSG_BBoxTree.h [new file with mode: 0644]
intern/csg/intern/CSG_BlenderVProp.h [new file with mode: 0644]
intern/csg/intern/CSG_BooleanOp.h [new file with mode: 0644]
intern/csg/intern/CSG_BooleanOp.inl [new file with mode: 0644]
intern/csg/intern/CSG_CVertex.h [new file with mode: 0644]
intern/csg/intern/CSG_ConnectedMesh.h [new file with mode: 0644]
intern/csg/intern/CSG_ConnectedMeshWrapper.inl [new file with mode: 0644]
intern/csg/intern/CSG_GeometryBinder.h [new file with mode: 0644]
intern/csg/intern/CSG_IndexDefs.h [new file with mode: 0644]
intern/csg/intern/CSG_Math.h [new file with mode: 0644]
intern/csg/intern/CSG_Math.inl [new file with mode: 0644]
intern/csg/intern/CSG_Mesh.h [new file with mode: 0644]
intern/csg/intern/CSG_MeshCopier.h [new file with mode: 0644]
intern/csg/intern/CSG_MeshWrapper.h [new file with mode: 0644]
intern/csg/intern/CSG_MeshWrapper.inl [new file with mode: 0644]
intern/csg/intern/CSG_Polygon.h [new file with mode: 0644]
intern/csg/intern/CSG_SplitFunction.h [new file with mode: 0644]
intern/csg/intern/CSG_TreeQueries.h [new file with mode: 0644]
intern/csg/intern/CSG_Triangulate.h [new file with mode: 0644]
intern/csg/intern/CSG_Triangulate.inl [new file with mode: 0644]
intern/csg/intern/CSG_Vertex.h [new file with mode: 0644]
intern/csg/intern/MT_Line3.cpp [new file with mode: 0644]
intern/csg/intern/MT_Line3.h [new file with mode: 0644]
intern/csg/intern/blender/CSG_BlenderMesh.h [new file with mode: 0644]
intern/csg/intern/blender/CSG_BlenderVProp.cpp [new file with mode: 0644]
intern/csg/intern/blender/CSG_CsgOp.cpp [new file with mode: 0644]
intern/csg/intern/blender/CSG_CsgOp.h [new file with mode: 0644]
intern/csg/intern/blender/CSG_IndexDefs.h [new file with mode: 0644]
intern/csg/intern/blender/CSG_Interface.cpp [new file with mode: 0644]
intern/csg/intern/blender/CSG_Iterator.h [new file with mode: 0644]
intern/csg/intern/blender/CSG_MeshBuilder.h [new file with mode: 0644]
intern/csg/intern/blender/CSG_PropArray.h [new file with mode: 0644]
intern/csg/intern/blender/CSG_SimpleProp.cpp [new file with mode: 0644]
intern/csg/intern/blender/CSG_SimpleProp.h [new file with mode: 0644]
intern/csg/make/msvc60/csg.dsp [new file with mode: 0644]
intern/csg/make/msvc60/csg.dsw [new file with mode: 0644]

diff --git a/intern/csg/extern/CSG_Interface.h b/intern/csg/extern/CSG_Interface.h
new file mode 100644 (file)
index 0000000..44b01c6
--- /dev/null
@@ -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 (file)
index 0000000..4d17b93
--- /dev/null
@@ -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 (file)
index 0000000..37ff965
--- /dev/null
@@ -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 (file)
index 0000000..a9013cc
--- /dev/null
@@ -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 (file)
index 0000000..72cad75
--- /dev/null
@@ -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 (file)
index 0000000..ff29379
--- /dev/null
@@ -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 (file)
index 0000000..9309d4f
--- /dev/null
@@ -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 (file)
index 0000000..fd0a7b0
--- /dev/null
@@ -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 (file)
index 0000000..6cf73ef
--- /dev/null
@@ -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 (file)
index 0000000..5d6cc11
--- /dev/null
@@ -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 (file)
index 0000000..2977ac6
--- /dev/null
@@ -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 (file)
index 0000000..2e1e05a
--- /dev/null
@@ -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 (file)
index 0000000..0c41e3d
--- /dev/null
@@ -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 (file)
index 0000000..73483ea
--- /dev/null
@@ -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 (file)
index 0000000..bd68782
--- /dev/null
@@ -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 (file)
index 0000000..4acf444
--- /dev/null
@@ -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 (file)
index 0000000..b557dde
--- /dev/null
@@ -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 (file)
index 0000000..7a9a141
--- /dev/null
@@ -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 (file)
index 0000000..8332977
--- /dev/null
@@ -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 (file)
index 0000000..70929a3
--- /dev/null
@@ -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 (file)
index 0000000..1b79d2c
--- /dev/null
@@ -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 (file)
index 0000000..95c0b60
--- /dev/null
@@ -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 (file)
index 0000000..d7f1220
--- /dev/null
@@ -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 (file)
index 0000000..bb39dbc
--- /dev/null
@@ -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 (file)
index 0000000..199eaea
--- /dev/null
@@ -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 (file)
index 0000000..e36f399
--- /dev/null
@@ -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 (file)
index 0000000..1f7a841
--- /dev/null
@@ -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 (file)
index 0000000..6acbdf2
--- /dev/null
@@ -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 (file)
index 0000000..1ff84ab
--- /dev/null
@@ -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 (file)
index 0000000..3b0e8b3
--- /dev/null
@@ -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 (file)
index 0000000..f385537
--- /dev/null
@@ -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 (file)
index 0000000..8b6415f
--- /dev/null
@@ -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 (file)
index 0000000..e349229
--- /dev/null
@@ -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 (file)
index 0000000..5d65acd
--- /dev/null
@@ -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 (file)
index 0000000..7e28a2a
--- /dev/null
@@ -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 (file)
index 0000000..2c8f0ee
--- /dev/null
@@ -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 (file)
index 0000000..dc8ab45
--- /dev/null
@@ -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 (file)
index 0000000..39c3895
--- /dev/null
@@ -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 (file)
index 0000000..7f9bd29
--- /dev/null
@@ -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>
+{{{
+}}}
+
+###############################################################################
+