Remove old boolean operation module
authorSergey Sharybin <sergey.vfx@gmail.com>
Thu, 2 Aug 2012 16:42:30 +0000 (16:42 +0000)
committerSergey Sharybin <sergey.vfx@gmail.com>
Thu, 2 Aug 2012 16:42:30 +0000 (16:42 +0000)
Carve proved it's a way to go, so the time have came to get rid of old
boolean operation module which isn't used anymore.

Still kept BOP interface but move it to BSP module. At some point it
could be cleaned up further (like perhaps removed extra abstraction
level or so) but would be nice to combine such a refactor with making
BSP aware of NGons.

Tested on linux using both cmake and scons, possible regressions on
windows/osx. Would check windoes build just after commit.

50 files changed:
CMakeLists.txt
build_files/cmake/config/blender_lite.cmake
build_files/scons/tools/btools.py
extern/CMakeLists.txt
extern/SConscript
intern/CMakeLists.txt
intern/SConscript
intern/boolop/CMakeLists.txt [deleted file]
intern/boolop/SConscript [deleted file]
intern/boolop/intern/BOP_BBox.cpp [deleted file]
intern/boolop/intern/BOP_BBox.h [deleted file]
intern/boolop/intern/BOP_BSPNode.cpp [deleted file]
intern/boolop/intern/BOP_BSPNode.h [deleted file]
intern/boolop/intern/BOP_BSPTree.cpp [deleted file]
intern/boolop/intern/BOP_BSPTree.h [deleted file]
intern/boolop/intern/BOP_Chrono.h [deleted file]
intern/boolop/intern/BOP_Edge.cpp [deleted file]
intern/boolop/intern/BOP_Edge.h [deleted file]
intern/boolop/intern/BOP_Face.cpp [deleted file]
intern/boolop/intern/BOP_Face.h [deleted file]
intern/boolop/intern/BOP_Face2Face.cpp [deleted file]
intern/boolop/intern/BOP_Face2Face.h [deleted file]
intern/boolop/intern/BOP_Indexs.h [deleted file]
intern/boolop/intern/BOP_Interface.cpp [deleted file]
intern/boolop/intern/BOP_MathUtils.cpp [deleted file]
intern/boolop/intern/BOP_MathUtils.h [deleted file]
intern/boolop/intern/BOP_Merge.cpp [deleted file]
intern/boolop/intern/BOP_Merge.h [deleted file]
intern/boolop/intern/BOP_Merge2.cpp [deleted file]
intern/boolop/intern/BOP_Merge2.h [deleted file]
intern/boolop/intern/BOP_Mesh.cpp [deleted file]
intern/boolop/intern/BOP_Mesh.h [deleted file]
intern/boolop/intern/BOP_Misc.h [deleted file]
intern/boolop/intern/BOP_Segment.cpp [deleted file]
intern/boolop/intern/BOP_Segment.h [deleted file]
intern/boolop/intern/BOP_Splitter.cpp [deleted file]
intern/boolop/intern/BOP_Splitter.h [deleted file]
intern/boolop/intern/BOP_Tag.cpp [deleted file]
intern/boolop/intern/BOP_Tag.h [deleted file]
intern/boolop/intern/BOP_Triangulator.cpp [deleted file]
intern/boolop/intern/BOP_Triangulator.h [deleted file]
intern/boolop/intern/BOP_Vertex.cpp [deleted file]
intern/boolop/intern/BOP_Vertex.h [deleted file]
intern/bsp/CMakeLists.txt
intern/bsp/SConscript
intern/bsp/intern/BOP_CarveInterface.cpp [moved from intern/boolop/intern/BOP_CarveInterface.cpp with 99% similarity]
intern/bsp/intern/BOP_Interface.h [moved from intern/boolop/extern/BOP_Interface.h with 96% similarity]
intern/bsp/intern/CSG_BooleanOps.cpp
source/blenderplayer/CMakeLists.txt
source/creator/CMakeLists.txt

index a3411176b1ec968f055af18c8bd334b1f96d6b98..299244b119e90d29201d1c8f5e993e05b31b1f73 100644 (file)
@@ -226,9 +226,6 @@ option(WITH_LZMA          "Enable best LZMA compression, (used for pointcache)"
 # Camera/motion tracking
 option(WITH_LIBMV         "Enable libmv structure from motion library" ON)
 
-# Mesh boolean lib
-option(WITH_CARVE         "Enable Carve library to handle mesh boolean operations" ON)
-
 # Misc
 option(WITH_INPUT_NDOF "Enable NDOF input devices (SpaceNavigator and friends)" ON)
 option(WITH_RAYOPTIMIZATION    "Enable use of SIMD (SSE) optimizations for the raytracer" ON)
@@ -364,8 +361,8 @@ if(WITH_CYCLES)
        set(WITH_OPENIMAGEIO ON)
 endif()
 
-# auto enable boost for cycles and carve
-if(WITH_CYCLES OR WITH_CARVE)
+# auto enable boost for cycles and booleans
+if(WITH_CYCLES OR WITH_MOD_BOOLEAN)
        set(WITH_BOOST ON)
 endif()
 
index 777fbbf0dba400498872fc7a49f4188dd7045e34..06a822617958bf8a54488d4cd252c487329c7b71 100644 (file)
@@ -15,7 +15,6 @@ set(WITH_CODEC_SNDFILE       OFF CACHE FORCE BOOL)
 set(WITH_CYCLES              OFF CACHE FORCE BOOL)
 set(WITH_FFTW3               OFF CACHE FORCE BOOL)
 set(WITH_LIBMV               OFF CACHE FORCE BOOL)
-set(WITH_CARVE               OFF CACHE FORCE BOOL)
 set(WITH_GAMEENGINE          OFF CACHE FORCE BOOL)
 set(WITH_COMPOSITOR          OFF CACHE FORCE BOOL)
 set(WITH_GHOST_XDND          OFF CACHE FORCE BOOL)
index e08a013d081b148ea042c4800a5825c7eabc9f79..034d261e7cdb7e52f64a2adb9b7fefef1e5f4270 100644 (file)
@@ -164,7 +164,7 @@ def validate_arguments(args, bc):
             'WITH_BF_CYCLES', 'WITH_BF_CYCLES_CUDA_BINARIES', 'BF_CYCLES_CUDA_NVCC', 'BF_CYCLES_CUDA_NVCC', 'WITH_BF_CYCLES_CUDA_THREADED_COMPILE',
             'WITH_BF_OIIO', 'WITH_BF_STATICOIIO', 'BF_OIIO', 'BF_OIIO_INC', 'BF_OIIO_LIB', 'BF_OIIO_LIB_STATIC', 'BF_OIIO_LIBPATH',
             'WITH_BF_BOOST', 'WITH_BF_STATICBOOST', 'BF_BOOST', 'BF_BOOST_INC', 'BF_BOOST_LIB', 'BF_BOOST_LIB_STATIC', 'BF_BOOST_LIBPATH',
-            'WITH_BF_LIBMV', 'WITH_BF_CARVE'
+            'WITH_BF_LIBMV'
             ]
     
     # Have options here that scons expects to be lists
@@ -530,7 +530,6 @@ def read_opts(env, cfg, args):
         
         (BoolVariable('WITH_BF_LZO', 'Enable fast LZO pointcache compression', True)),
         (BoolVariable('WITH_BF_LZMA', 'Enable best LZMA pointcache compression', True)),
-        (BoolVariable('WITH_BF_CARVE', 'Enable carve library for mesh boolean operations', True)),
         
         (BoolVariable('WITH_BF_LIBMV', 'Enable libmv structure from motion library', True)),
         
index b5f94c06d4c25d9eb0c14f88d85654eec22e1005..151df493062112f8e2d4092af7e7818bb7cb113e 100644 (file)
@@ -68,7 +68,7 @@ if(WITH_LIBMV)
        add_subdirectory(libmv)
 endif()
 
-if(WITH_CARVE)
+if(WITH_MOD_BOOLEAN)
        add_subdirectory(carve)
 endif()
 
index 67b74e9ee91facc601afc7a76c129eebcc1da39e..ce366deb38a713ff0a3793ea2e3b7ffc71156cc3 100644 (file)
@@ -32,7 +32,7 @@ if env['WITH_BF_LZMA']:
 if env['WITH_BF_LIBMV']:
     SConscript(['libmv/SConscript'])
 
-if env['WITH_BF_CARVE']:
+if env['WITH_BF_BOOLEAN']:
     SConscript(['carve/SConscript'])
 
 if env['WITH_GHOST_XDND']:
index 71d2ef5e410f45f79533ef017b55353b943d2782..2b4a84d6b39682705a2de698df6e6aaa230830df 100644 (file)
@@ -55,7 +55,6 @@ if(WITH_MOD_DECIMATE)
 endif()
 
 if(WITH_MOD_BOOLEAN)
-       add_subdirectory(boolop)
        add_subdirectory(bsp)
 endif()
 
index 3bfdc2c4ca7d5e0976ee6b219653906a3ed19a9a..53fc80b0317988560caabcd310f84287df410b80 100644 (file)
@@ -11,7 +11,6 @@ SConscript(['audaspace/SConscript',
             'decimation/SConscript',
             'iksolver/SConscript',
             'itasc/SConscript',
-            'boolop/SConscript',
             'opennl/SConscript',
             'mikktspace/SConscript',
             'smoke/SConscript',
@@ -26,7 +25,8 @@ if env['WITH_BF_FLUID']:
 if env['WITH_BF_CYCLES']:
     SConscript(['cycles/SConscript'])
 
-SConscript(['bsp/SConscript'])
+if env['WITH_BF_BOOLEAN']:
+    SConscript(['bsp/SConscript'])
 
 if env['OURPLATFORM'] in ('win32-vc', 'win32-mingw', 'win64-mingw', 'linuxcross', 'win64-vc'):
     SConscript(['utfconv/SConscript'])
diff --git a/intern/boolop/CMakeLists.txt b/intern/boolop/CMakeLists.txt
deleted file mode 100644 (file)
index d8e9c0c..0000000
+++ /dev/null
@@ -1,111 +0,0 @@
-# ***** BEGIN GPL LICENSE BLOCK *****
-#
-# This program is free software; you can redistribute it and/or
-# modify it under the terms of the GNU General Public License
-# as published by the Free Software Foundation; either version 2
-# of the License, or (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software Foundation,
-# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
-#
-# The Original Code is Copyright (C) 2006, Blender Foundation
-# All rights reserved.
-#
-# The Original Code is: all of this file.
-#
-# Contributor(s): Jacques Beaurain.
-#
-# ***** END GPL LICENSE BLOCK *****
-
-remove_strict_flags()
-
-set(INC        
-       .
-       extern
-       intern
-       ../container
-       ../guardedalloc
-       ../memutil
-       ../moto/include
-       ../../source/blender/blenlib
-       ../../source/blender/makesdna
-)
-
-set(INC_SYS
-
-)
-
-if(NOT WITH_CARVE)
-       set(SRC
-               intern/BOP_BBox.cpp
-               intern/BOP_BSPNode.cpp
-               intern/BOP_BSPTree.cpp
-               intern/BOP_Edge.cpp
-               intern/BOP_Face.cpp
-               intern/BOP_Face2Face.cpp
-               intern/BOP_Interface.cpp
-               intern/BOP_MathUtils.cpp
-               intern/BOP_Merge.cpp
-               intern/BOP_Merge2.cpp
-               intern/BOP_Mesh.cpp
-               intern/BOP_Segment.cpp
-               intern/BOP_Splitter.cpp
-               intern/BOP_Tag.cpp
-               intern/BOP_Triangulator.cpp
-               intern/BOP_Vertex.cpp
-
-               extern/BOP_Interface.h
-               intern/BOP_BBox.h
-               intern/BOP_BSPNode.h
-               intern/BOP_BSPTree.h
-               intern/BOP_Chrono.h
-               intern/BOP_Edge.h
-               intern/BOP_Face.h
-               intern/BOP_Face2Face.h
-               intern/BOP_Indexs.h
-               intern/BOP_MathUtils.h
-               intern/BOP_Merge.h
-               intern/BOP_Merge2.h
-               intern/BOP_Mesh.h
-               intern/BOP_Misc.h
-               intern/BOP_Segment.h
-               intern/BOP_Splitter.h
-               intern/BOP_Tag.h
-               intern/BOP_Triangulator.h
-               intern/BOP_Vertex.h
-       )
-else()
-       set(SRC
-               intern/BOP_CarveInterface.cpp
-               extern/BOP_Interface.h
-       )
-
-       list(APPEND INC
-               ../../extern/carve/include
-       )
-
-       if(WITH_BOOST)
-               if(NOT MSVC)
-                       # Boost is setting as preferred collections library in the Carve code when using MSVC compiler
-                       add_definitions(
-                               -DHAVE_BOOST_UNORDERED_COLLECTIONS
-                       )
-               endif()
-
-               add_definitions(
-                       -DCARVE_SYSTEM_BOOST
-               )
-
-               list(APPEND INC
-                       ${BOOST_INCLUDE_DIR}
-               )
-       endif()
-endif()
-
-blender_add_lib(bf_intern_bop "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/intern/boolop/SConscript b/intern/boolop/SConscript
deleted file mode 100644 (file)
index f630d1d..0000000
+++ /dev/null
@@ -1,31 +0,0 @@
-#!/usr/bin/python
-Import ('env')
-
-incs = '. intern extern ../moto/include ../container ../memutil'
-incs += ' ../../source/blender/makesdna ../../intern/guardedalloc'
-incs += ' ../../source/blender/blenlib'
-
-defs = []
-
-if not env['WITH_BF_CARVE']:
-    import os
-    sources = env.Glob('intern/*.cpp')
-    sources.remove('intern' + os.sep + 'BOP_CarveInterface.cpp')
-else:
-    sources = env.Glob('intern/BOP_CarveInterface.cpp')
-    incs += ' ../../extern/carve/include'
-
-    if env['WITH_BF_BOOST']:
-        if env['OURPLATFORM'] not in ('win32-vc', 'win64-vc'):
-            # Boost is setting as preferred collections library in the Carve code when using MSVC compiler
-            if env['OURPLATFORM'] not in ('win32-mingw', 'win64-mingw'):
-                defs.append('HAVE_BOOST_UNORDERED_COLLECTIONS')
-
-        defs.append('CARVE_SYSTEM_BOOST')
-        incs +=  ' ' + env['BF_BOOST_INC']
-
-if (env['OURPLATFORM'] in ('win32-mingw', 'win64-mingw')):
-    env.BlenderLib ('bf_intern_bop', sources, Split(incs) , [], libtype='intern', priority = 5 )
-else:
-    env.BlenderLib ('bf_intern_bop', sources, Split(incs) , defs, libtype='intern', priority = 5 )
-
diff --git a/intern/boolop/intern/BOP_BBox.cpp b/intern/boolop/intern/BOP_BBox.cpp
deleted file mode 100644 (file)
index a42c7d9..0000000
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_BBox.cpp
- *  \ingroup boolopintern
- */
-
-
-#include "BOP_BBox.h"
-
-#include "MT_Scalar.h"
-
-/**
- * Constructs a nwe bounding box.
- */
-BOP_BBox::BOP_BBox()
-{
-       m_minX = MT_INFINITY;
-       m_minY = MT_INFINITY;
-       m_minZ = MT_INFINITY;
-       m_maxX = -MT_INFINITY;
-       m_maxY = -MT_INFINITY;
-       m_maxZ = -MT_INFINITY;
-}
-
-/**
- * Constructs a new bounding box using three points.
- * @param p1 first point
- * @param p2 second point
- * @param p3 third point
- */
-BOP_BBox::BOP_BBox(const MT_Point3& p1,const MT_Point3& p2,const MT_Point3& p3)
-{
-  m_minX = BOP_MIN(BOP_MIN(p1[0],p2[0]),p3[0]);
-  m_minY = BOP_MIN(BOP_MIN(p1[1],p2[1]),p3[1]);
-  m_minZ = BOP_MIN(BOP_MIN(p1[2],p2[2]),p3[2]);
-  m_maxX = BOP_MAX(BOP_MAX(p1[0],p2[0]),p3[0]);
-  m_maxY = BOP_MAX(BOP_MAX(p1[1],p2[1]),p3[1]);
-  m_maxZ = BOP_MAX(BOP_MAX(p1[2],p2[2]),p3[2]);
-}
diff --git a/intern/boolop/intern/BOP_BBox.h b/intern/boolop/intern/BOP_BBox.h
deleted file mode 100644 (file)
index c58bb70..0000000
+++ /dev/null
@@ -1,98 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_BBox.h
- *  \ingroup boolopintern
- */
-
-
-#ifndef __BOP_BBOX_H__
-#define __BOP_BBOX_H__
-
-#include "MT_Point3.h"
-#include "BOP_MathUtils.h"
-
-#define BOP_MAX(a, b) ((a > b) ? a : b)
-#define BOP_MIN(a, b) ((a < b) ? a : b)
-#define BOP_ABS(a) ((a < 0) ? -(a) : a)
-
-class BOP_BBox
-{
-public:
-       MT_Scalar m_minX;
-       MT_Scalar m_minY;
-       MT_Scalar m_minZ;
-       MT_Scalar m_maxX;
-       MT_Scalar m_maxY;
-       MT_Scalar m_maxZ;
-       MT_Scalar m_centerX;
-       MT_Scalar m_centerY;
-       MT_Scalar m_centerZ;
-       MT_Scalar m_extentX;
-       MT_Scalar m_extentY;
-       MT_Scalar m_extentZ;
-       
-public:
-       BOP_BBox();
-       BOP_BBox(const MT_Point3& p1,const MT_Point3& p2,const MT_Point3& p3);
-       inline void add(const MT_Point3& p)
-       {
-               m_minX = BOP_MIN(m_minX,p[0]);
-               m_minY = BOP_MIN(m_minY,p[1]);
-               m_minZ = BOP_MIN(m_minZ,p[2]);
-               m_maxX = BOP_MAX(m_maxX,p[0]);
-               m_maxY = BOP_MAX(m_maxY,p[1]);
-               m_maxZ = BOP_MAX(m_maxZ,p[2]);
-       };
-
-       inline const MT_Scalar getCenterX() const {return m_centerX;};
-       inline const MT_Scalar getCenterY() const {return m_centerY;};
-       inline const MT_Scalar getCenterZ() const {return m_centerZ;};
-
-       inline const MT_Scalar getExtentX() const {return m_extentX;};
-       inline const MT_Scalar getExtentY() const {return m_extentY;};
-       inline const MT_Scalar getExtentZ() const {return m_extentZ;};
-       
-       inline void compute() {
-               m_extentX = (m_maxX-m_minX)/2.0f;
-               m_extentY = (m_maxY-m_minY)/2.0f;
-               m_extentZ = (m_maxZ-m_minZ)/2.0f;
-               m_centerX = m_minX+m_extentX;
-               m_centerY = m_minY+m_extentY;
-               m_centerZ = m_minZ+m_extentZ;
-       };
-
-       inline const bool intersect(const BOP_BBox& b) const {
-         return (!((BOP_comp(m_maxX,b.m_minX)<0) || (BOP_comp(b.m_maxX,m_minX)<0) ||
-                   (BOP_comp(m_maxY,b.m_minY)<0) || (BOP_comp(b.m_maxY,m_minY)<0) ||
-                   (BOP_comp(m_maxZ,b.m_minZ)<0) || (BOP_comp(b.m_maxZ,m_minZ)<0)));
-       };
-       
-       
-};
-
-#endif
diff --git a/intern/boolop/intern/BOP_BSPNode.cpp b/intern/boolop/intern/BOP_BSPNode.cpp
deleted file mode 100644 (file)
index 3588e80..0000000
+++ /dev/null
@@ -1,718 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_BSPNode.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_MathUtils.h"
-#include "BOP_BSPNode.h"
-#include "MT_assert.h"
-#include "MT_MinMax.h"
-#include <iostream>
-
-/**
- * Constructs a new BSP node.
- * @param plane split plane.
- */
-BOP_BSPNode::BOP_BSPNode(const MT_Plane3& plane)
-{
-       m_plane      = plane;
-       m_inChild    = NULL;
-       m_outChild   = NULL;
-       m_deep       = 1;
-}
-
-/**
- * Destroys a BSP tree.
- */
-BOP_BSPNode::~BOP_BSPNode()
-{
-       if (m_inChild!=NULL) delete m_inChild;
-       if (m_outChild!=NULL) delete m_outChild;
-}
-
-/**
- * Adds a new face to this BSP tree.
- * @param pts vector containing face points
- * @param plane face plane.
- */
-
-unsigned int BOP_BSPNode::addFace(const BOP_BSPPoints& pts,
-                                                                 const MT_Plane3& plane )
-{
-       unsigned int newDeep = 0;
-       BOP_TAG tag = ON;
-
-       // find out if any points on the "face" lie in either half-space
-       BOP_IT_BSPPoints ptsEnd = pts.end();
-       for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
-               tag = (BOP_TAG) ((int) tag | (int)testPoint(*itp));
-       }
-       if (tag == ON) { }              // face lies on hyperplane: do nothing
-       else if ((tag & IN) != 0 && (tag & OUT) == 0) { // face is entirely on inside
-               if (m_inChild != NULL)
-                       newDeep = m_inChild->addFace(pts, plane) + 1;
-               else {
-                       m_inChild = new BOP_BSPNode(plane);
-                       newDeep = 2;
-               }    
-       } else if ((tag & OUT) != 0 && (tag & IN) == 0) { // face is entirely on outside
-               if (m_outChild != NULL)
-                       newDeep = m_outChild->addFace(pts, plane) + 1;
-               else {
-                       m_outChild = new BOP_BSPNode(plane);
-                       newDeep = 2;
-               }
-       } else { // face lies in both half-spaces: split it
-               BOP_BSPPoints inside, outside;
-               MT_Point3 lpoint= pts[pts.size()-1];
-               BOP_TAG ltag = testPoint(lpoint);
-               BOP_TAG tstate = ltag;
-
-               // classify each line segment, looking for endpoints which lie on different
-               // sides of the hyperplane.
-
-               ptsEnd = pts.end();
-               for(BOP_IT_BSPPoints itp=pts.begin();itp!=ptsEnd;itp++){
-                       MT_Point3 npoint= *itp;
-                       BOP_TAG ntag = testPoint(npoint);
-
-                       if(ltag != ON) {        // last point not on hyperplane
-                               if(tstate == IN) {
-                                       if (m_inChild != NULL) inside.push_back(lpoint);
-                               } else {
-                                       if (m_outChild != NULL) outside.push_back(lpoint);
-                               }
-                               if(ntag != ON && ntag != tstate) {      // last, self in different half-spaces 
-                                       MT_Point3 mpoint = BOP_intersectPlane( m_plane, lpoint, npoint );
-                                       if (m_inChild != NULL) inside.push_back(mpoint);
-                                       if (m_outChild != NULL) outside.push_back(mpoint);
-                                       tstate = ntag;
-                               }
-                       } else {                        // last point on hyperplane, so we're switching
-                                                               // half-spaces
-                                                               // boundary point belong to both faces
-                               if (m_inChild != NULL) inside.push_back(lpoint);        
-                               if (m_outChild != NULL) outside.push_back(lpoint);
-                               tstate = ntag;  // state changes to new point tag
-                       }
-                       lpoint = npoint;        // save point, tag for next iteration
-                       ltag = ntag;
-               }
-
-               if (m_inChild != NULL)
-                       newDeep = m_inChild->addFace(inside, plane) + 1;
-               else {
-                       m_inChild = new BOP_BSPNode(plane);
-                       newDeep = 2;
-               }    
-               if (m_outChild != NULL)
-                       newDeep = MT_max(newDeep, m_outChild->addFace(outside, plane) + 1);
-               else {
-                       m_outChild = new BOP_BSPNode(plane);
-                       newDeep = MT_max(newDeep,(unsigned int)2);
-               }      
-       }
-       
-       // update the deep attribute
-       m_deep = MT_max(m_deep,newDeep);
-       
-       return m_deep;
-}
-
-/**
- * Tests the point situation respect the node plane.
- * @param p point to test.
- * @return TAG result: IN, OUT or ON.
- */
-BOP_TAG BOP_BSPNode::testPoint(const MT_Point3& p) const
-{
-  return BOP_createTAG(BOP_classify(p,m_plane));
-
-}
-
-/**
- * Classifies a face using its coordinates and plane.
- * @param p1 first point.
- * @param p2 second point.
- * @param p3 third point.
- * @param plane face plane.
- * @return TAG result: IN, OUT or IN&OUT.
- */
-BOP_TAG BOP_BSPNode::classifyFace(const MT_Point3& p1, 
-                                                                 const MT_Point3& p2, 
-                                                                 const MT_Point3& p3, 
-                                                                 const MT_Plane3& plane) const
-{
-       // local variables
-       MT_Point3 auxp1, auxp2;
-       BOP_TAG auxtag1, auxtag2, auxtag3;
-
-       switch(BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3))) {
-               // Classify the face on the IN side
-               case IN_IN_IN : 
-                       return classifyFaceIN(p1, p2, p3, plane);
-               case IN_IN_ON :
-               case IN_ON_IN :
-               case ON_IN_IN :
-               case IN_ON_ON :
-               case ON_IN_ON :
-               case ON_ON_IN :
-                       return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
-       
-               // Classify the face on the OUT side
-               case OUT_OUT_OUT :
-                       return classifyFaceOUT(p1, p2, p3, plane);
-               case OUT_OUT_ON :
-               case OUT_ON_OUT :
-               case ON_OUT_OUT :
-               case ON_ON_OUT :
-               case ON_OUT_ON :
-               case OUT_ON_ON :
-                       return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
-       
-               // Classify the ON face depending on it plane normal
-               case ON_ON_ON :
-                       if (hasSameOrientation(plane))
-                               return BOP_addON(classifyFaceIN(p1, p2, p3, plane));
-                       else
-                               return BOP_addON(classifyFaceOUT(p1, p2, p3, plane));
-
-               // Classify the face IN/OUT and one vertex ON
-               // becouse only one ON, only one way to subdivide the face
-               case IN_OUT_ON :
-                       auxp1 = BOP_intersectPlane(m_plane, p1, p2);
-                       auxtag1 = classifyFaceIN( p1,    auxp1 , p3, plane);
-                       auxtag2 = classifyFaceOUT(auxp1, p2,     p3, plane);
-                       return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
-
-               case OUT_IN_ON :
-                       auxp1 = BOP_intersectPlane(m_plane, p1, p2);
-                       auxtag1 = classifyFaceOUT(p1,    auxp1, p3, plane);
-                       auxtag2 = classifyFaceIN( auxp1, p2,    p3, plane);
-                       return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
-
-               case IN_ON_OUT :
-                       auxp1 = BOP_intersectPlane(m_plane, p1, p3);
-                       auxtag1 = classifyFaceIN( p1, p2, auxp1, plane);
-                       auxtag2 = classifyFaceOUT(p2, p3, auxp1, plane);
-                       return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
-
-               case OUT_ON_IN :
-                       auxp1 = BOP_intersectPlane(m_plane, p1, p3);
-                       auxtag1 = classifyFaceOUT(p1, p2, auxp1, plane);
-                       auxtag2 = classifyFaceIN( p2, p3, auxp1, plane);
-                       return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
-
-               case ON_IN_OUT :
-                       auxp1 = BOP_intersectPlane(m_plane, p2, p3);
-                       auxtag1 = classifyFaceIN( p1,    p2, auxp1, plane);
-                       auxtag2 = classifyFaceOUT(auxp1, p3, p1,    plane);
-                       return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
-
-               case ON_OUT_IN :
-                       auxp1 = BOP_intersectPlane(m_plane, p2, p3);
-                       auxtag1 = classifyFaceOUT(p1,    p2, auxp1, plane);
-                       auxtag2 = classifyFaceIN( auxp1, p3, p1,    plane);
-                       return (BOP_compTAG(auxtag1,auxtag2)?BOP_addON(auxtag1):INOUT);
-
-               // Classify IN/OUT face without ON vertices.
-               // Two ways to divide the triangle, 
-               // will chose the least degenerated sub-triangles.
-               case IN_OUT_OUT :
-                       auxp1 = BOP_intersectPlane(m_plane, p1, p2);
-                       auxp2 = BOP_intersectPlane(m_plane, p1, p3);
-       
-                       // f1: p1 auxp1 , auxp1 auxp2
-                       auxtag1 = classifyFaceIN(p1, auxp1, auxp2, plane);
-       
-                       // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||  
-                       // f2: auxp1 p3, p3 auxp2;   f3: p2 p3 , p3 auxp1
-                       if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
-                               auxtag2 = classifyFaceOUT(auxp1, p2, auxp2, plane);
-                               auxtag3 = classifyFaceOUT(p2,    p3, auxp2, plane);
-                       }
-                       else {
-                               auxtag2 = classifyFaceOUT(auxp1, p3, auxp2, plane);
-                               auxtag3 = classifyFaceOUT(p2,    p3, auxp1, plane);
-                       }
-                       return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
-
-               case OUT_IN_IN :
-                       auxp1 = BOP_intersectPlane(m_plane, p1, p2);
-                       auxp2 = BOP_intersectPlane(m_plane, p1, p3);
-       
-                       // f1: p1 auxp1 , auxp1 auxp2
-                       auxtag1 = classifyFaceOUT(p1, auxp1, auxp2, plane);
-       
-                       // f2: auxp1 p2 , p2 auxp2;  f3: p2 p3 , p3 auxp2  ||
-                       // f2: auxp1 p3, p3 auxp2;  f3: p2 p3 , p3 auxp1
-                       if (BOP_isInsideCircle(p2, p3, auxp1, auxp2)) {
-                               auxtag2 = classifyFaceIN(auxp1, p2, auxp2, plane);
-                               auxtag3 = classifyFaceIN(p2, p3, auxp2, plane);
-                       }
-                       else {
-                               auxtag2 = classifyFaceIN(auxp1, p3, auxp2, plane);
-                               auxtag3 = classifyFaceIN(p2,    p3, auxp1, plane);
-                       }
-                       return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
-
-               case OUT_IN_OUT :
-                       auxp1 = BOP_intersectPlane(m_plane, p2, p1);
-                       auxp2 = BOP_intersectPlane(m_plane, p2, p3);
-       
-                       // f1: auxp1 p2 , p2 auxp2
-                       auxtag1 = classifyFaceIN(auxp1, p2, auxp2, plane);
-       
-                       // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
-                       // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
-                       if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
-                               auxtag2 = classifyFaceOUT(p1, auxp1, auxp2, plane);
-                               auxtag3 = classifyFaceOUT(p1, auxp2, p3,    plane);
-                       }
-                       else {
-                               auxtag2 = classifyFaceOUT(p3, auxp1, auxp2, plane);
-                               auxtag3 = classifyFaceOUT(p1, auxp1, p3,    plane);
-                       }
-                       return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
-    
-               case IN_OUT_IN :
-                       auxp1 = BOP_intersectPlane(m_plane, p2, p1);
-                       auxp2 = BOP_intersectPlane(m_plane, p2, p3);
-       
-                       // f1: auxp1 p2 , p2 auxp2
-                       auxtag1 = classifyFaceOUT(auxp1, p2, auxp2, plane);
-       
-                       // f2: p1 auxp1 , auxp1 auxp2;  f3: p1 auxp2 , auxp2 p3  ||  
-                       // f2: p3 auxp1, auxp1 auxp2  f3:p1 auxp1, auxp1 p3
-                       if (BOP_isInsideCircle(p1, p3, auxp1, auxp2)) {
-                               auxtag2 = classifyFaceIN(p1, auxp1, auxp2, plane);
-                               auxtag3 = classifyFaceIN(p1, auxp2, p3,    plane);
-                       }
-                       else {
-                               auxtag2 = classifyFaceIN(p3, auxp1, auxp2, plane);
-                               auxtag3 = classifyFaceIN(p1, auxp1, p3,    plane);
-                       }
-                       return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
-       
-               case OUT_OUT_IN :
-                       auxp1 = BOP_intersectPlane(m_plane, p3, p1);
-                       auxp2 = BOP_intersectPlane(m_plane, p3, p2);
-       
-                       // f1: auxp1 auxp2 , auxp2 p3
-                       auxtag1 = classifyFaceIN(auxp1, auxp2, p3, plane);
-       
-                       // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
-                       // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
-                       if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
-                               auxtag2 = classifyFaceOUT(p1, p2,    auxp2, plane);
-                               auxtag3 = classifyFaceOUT(p1, auxp2, auxp1, plane);
-                       }
-                       else {
-                               auxtag2 = classifyFaceOUT(p1, p2,    auxp1, plane);
-                               auxtag3 = classifyFaceOUT(p2, auxp2, auxp1, plane);
-                       }
-                       return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
-
-               case IN_IN_OUT :
-                       auxp1 = BOP_intersectPlane(m_plane, p3, p1);
-                       auxp2 = BOP_intersectPlane(m_plane, p3, p2);
-       
-                       // f1: auxp1 auxp2 , auxp2 p3
-                       auxtag1 = classifyFaceOUT(auxp1, auxp2, p3, plane);
-       
-                       // f2: p1 p2 , p2 auxp2;   f3:p1 auxp2 , auxp2 auxp1  ||
-                       // f2: p1 p2, p2 auxp1;  f3:p2 auxp2, auxp2 auxp1
-                       if (BOP_isInsideCircle(p1, p2, auxp1, auxp2)) {
-                               auxtag2 = classifyFaceIN(p1, p2,    auxp2, plane);
-                               auxtag3 = classifyFaceIN(p1, auxp2, auxp1, plane);
-                       }
-                       else {
-                               auxtag2 = classifyFaceIN(p1, p2,    auxp1, plane);
-                               auxtag3 = classifyFaceIN(p2, auxp2, auxp1, plane);
-                       }
-                       return (BOP_compTAG(auxtag1,auxtag2)&&BOP_compTAG(auxtag2,auxtag3)?auxtag1:INOUT);
-
-               default:
-                       return UNCLASSIFIED;
-       }
-}
-
-/**
- * Classifies a face through IN subtree.
- * @param p1 firts face vertex.
- * @param p2 second face vertex.
- * @param p3 third face vertex.
- * @param plane face plane.
- */
-BOP_TAG BOP_BSPNode::classifyFaceIN(const MT_Point3& p1, 
-                                                                       const MT_Point3& p2, 
-                                                                       const MT_Point3& p3, 
-                                                                       const MT_Plane3& plane) const
-{
-       if (m_inChild != NULL)
-               return m_inChild->classifyFace(p1, p2, p3, plane);
-       else
-               return IN;
-}
-
-/**
- * Classifies a face through OUT subtree.
- * @param p1 firts face vertex.
- * @param p2 second face vertex.
- * @param p3 third face vertex.
- * @param plane face plane.
- */
-BOP_TAG BOP_BSPNode::classifyFaceOUT(const MT_Point3& p1, 
-                                                                        const MT_Point3& p2, 
-                                                                        const MT_Point3& p3, 
-                                                                        const MT_Plane3& plane) const
-{
-       if (m_outChild != NULL)
-               return m_outChild->classifyFace(p1, p2, p3, plane);
-       else
-               return OUT;
-}
-
-/**
- * Simplified classification (optimized but requires that the face is not 
- * INOUT; only works correctly with faces completely IN or OUT).
- * @param p1 firts face vertex.
- * @param p2 second face vertex.
- * @param p3 third face vertex.
- * @param plane face plane.
- * @return TAG result: IN or OUT.
- */
-BOP_TAG BOP_BSPNode::simplifiedClassifyFace(const MT_Point3& p1, 
-                                                                                       const MT_Point3& p2, 
-                                                                                       const MT_Point3& p3, 
-                                                                                       const MT_Plane3& plane) const
-{
-       MT_Point3 ret[3];
-
-       BOP_TAG tag = BOP_createTAG(testPoint(p1),testPoint(p2),testPoint(p3));
-
-       if ((tag & IN_IN_IN) != 0) {
-               if ((tag & OUT_OUT_OUT) != 0) {     
-                 if (splitTriangle(ret,m_plane,p1,p2,p3,tag)<0)
-                   return simplifiedClassifyFaceIN(ret[0],ret[1],ret[2],plane);
-                 else
-                   return simplifiedClassifyFaceOUT(ret[0],ret[1],ret[2],plane);
-               }
-               else {
-                       return simplifiedClassifyFaceIN(p1,p2,p3,plane);
-               }
-       }
-       else {
-               if ((tag & OUT_OUT_OUT) != 0) {
-                       return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
-               }
-               else {
-                       if (hasSameOrientation(plane)) {
-                               return simplifiedClassifyFaceIN(p1,p2,p3,plane);
-                       }
-                       else {
-                               return simplifiedClassifyFaceOUT(p1,p2,p3,plane);
-                       }
-               }
-       }
-       
-       return IN;
-}
-
-/**
- * Simplified classify through IN subtree.
- * @param p1 firts face vertex.
- * @param p2 second face vertex.
- * @param p3 third face vertex.
- * @param plane face plane.
- */
-BOP_TAG BOP_BSPNode::simplifiedClassifyFaceIN(const MT_Point3& p1, 
-                                                                                         const MT_Point3& p2, 
-                                                                                         const MT_Point3& p3, 
-                                                                                         const MT_Plane3& plane) const
-{
-       if (m_inChild != NULL)
-               return m_inChild->simplifiedClassifyFace(p1, p2, p3, plane);
-       else
-               return IN;
-}
-
-/**
- * Simplified classify through OUT subtree.
- * @param p1 firts face vertex.
- * @param p2 second face vertex.
- * @param p3 third face vertex.
- * @param plane face plane.
- */
-BOP_TAG BOP_BSPNode::simplifiedClassifyFaceOUT(const MT_Point3& p1, 
-                                                                                          const MT_Point3& p2, 
-                                                                                          const MT_Point3& p3, 
-                                                                                          const MT_Plane3& plane) const
-{
-       if (m_outChild != NULL)
-               return m_outChild->simplifiedClassifyFace(p1, p2, p3, plane);
-       else
-               return OUT;
-}
-
-/**
- * Determine if the input plane have the same orientation of the node plane.
- * @param plane plane to test.
- * @return TRUE if have the same orientation, FALSE otherwise.
- */
-bool BOP_BSPNode::hasSameOrientation(const MT_Plane3& plane) const
-{
-       return (BOP_orientation(m_plane,plane)>0);
-}
-
-/**
- * Comparation between both childrens.
- * @return 0 equal deep, 1 inChild more deep than outChild and -1 otherwise.
- */
-int BOP_BSPNode::compChildren() const
-{
-       unsigned int deep1 = (m_inChild == NULL?0:m_inChild->getDeep());
-       unsigned int deep2 = (m_outChild == NULL?0:m_outChild->getDeep());
-       
-       if (deep1 == deep2)
-               return 0;
-       else if (deep1 < deep2)
-               return -1;
-       else
-               return 1;
-}
-
-/**
- * Extract a subtriangle from input triangle, is used for simplified classification.
- * The subtriangle is obtained spliting the input triangle by input plane.
- * @param res output subtriangle result.
- * @param plane spliter plane.
- * @param p1 first triangle point.
- * @param p2 second triangle point.
- * @param p3 third triangle point.
- * @param tag triangle orientation respect the plane.
- */
-int BOP_BSPNode::splitTriangle(MT_Point3* res, 
-                                                          const MT_Plane3& plane, 
-                                                          const MT_Point3& p1, 
-                                                          const MT_Point3& p2, 
-                                                          const MT_Point3& p3, 
-                                                          const BOP_TAG tag) const
-{
-       switch (tag) {
-               case IN_OUT_ON :
-                 if (compChildren()<0) {
-                   // f1: p1 new p3 || new = splitedge(p1,p2)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p1, p2 );
-                   res[2] = p3;
-                   return -1;
-                 }else{
-                   // f1: p2 new p3 || new = splitedge(p1,p2)
-                   res[0] = p2;
-                   res[1] = p3;
-                   res[2] = BOP_intersectPlane( plane, p1, p2 );
-                   return 1;
-                 }
-               case OUT_IN_ON :
-                 if (compChildren()<0) {
-                   // f1: p2 new p3 || new = splitedge(p1,p2)
-                   res[0] = p2;
-                   res[1] = p3;
-                   res[2] = BOP_intersectPlane( plane, p1, p2 );
-                   return -1;
-                 }else{
-                   // f1: p1 new p3 || new = splitedge(p1,p2)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p1, p2 );
-                   res[2] = p3;
-                   return 1;
-                 }
-               case IN_ON_OUT :
-                 if (compChildren()<0) {
-                   // f1: p1 p2 new || new = splitedge(p1,p3)
-                   res[0] = p1;
-                   res[1] = p2;
-                   res[2] = BOP_intersectPlane( plane, p1, p3 );
-                   return -1;
-                 }else{
-                   // f1: p2 p3 new || new = splitedge(p1,p3)
-                   res[0] = p2;
-                   res[1] = p3;
-                   res[2] = BOP_intersectPlane( plane, p1, p3 );
-                   return 1;
-                 }
-               case OUT_ON_IN :
-                 if (compChildren()<0) {
-                   // f1: p2 p3 new || new = splitedge(p1,p3)
-                   res[0] = p2;
-                   res[1] = p3;
-                   res[2] = BOP_intersectPlane( plane, p1, p3 );
-                   return -1;
-                 }else{
-                   // f1: p1 p2 new || new = splitedge(p1,p3)
-                   res[0] = p1;
-                   res[1] = p2;
-                   res[2] = BOP_intersectPlane( plane, p1, p3 );
-                   return 1;
-                 }
-               case ON_IN_OUT :
-                 if (compChildren()<0) {
-                   // f1: p1 p2 new || new = splitedge(p2,p3)
-                   res[0] = p1;
-                   res[1] = p2;
-                   res[2] = BOP_intersectPlane( plane, p2, p3 );
-                   return -1;
-                 }else{
-                   // f1: p1 p3 new || new = splitedge(p2,p3)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p2, p3 );
-                   res[2] = p3;
-                   return 1;
-                 }
-               case ON_OUT_IN :
-                 if (compChildren()<0) {
-                   // f1: p1 p2 new || new = splitedge(p2,p3)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p2, p3 );
-                   res[2] = p3;
-                   return -1;
-                 }else{
-                   // f1: p1 p2 new || new = splitedge(p2,p3)
-                   res[0] = p1;
-                   res[1] = p2;
-                   res[2] = BOP_intersectPlane( plane, p2, p3 );
-                   return 1;
-                 }
-               case IN_OUT_OUT :
-                 if (compChildren()<=0) {
-                   // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p1, p2 );
-                   res[2] = BOP_intersectPlane( plane, p1, p3 );
-                   return -1;
-                 }else{
-                   // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
-                   res[0] = BOP_intersectPlane( plane, p1, p2 );
-                   res[1] = p2;
-                   res[2] = p3;
-                   return 1;
-                 }
-               case OUT_IN_IN :
-                 if (compChildren()<0) {
-                   // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
-                   res[0] = BOP_intersectPlane( plane, p1, p2 );
-                   res[1] = p2;
-                   res[2] = p3;
-                   return -1;
-                 }else {
-                   // f1: p1 new1 new2 || new1 = splitedge(p1,p2) new2 = splitedge(p1,p3)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p1, p2 );
-                   res[2] = BOP_intersectPlane( plane, p1, p3 );
-                   return 1;
-                 }
-               case OUT_IN_OUT :
-                 if (compChildren()<=0) {
-                   // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
-                   res[0] = BOP_intersectPlane( plane, p2, p1 );
-                   res[1] = p2;
-                   res[2] = BOP_intersectPlane( plane, p2, p3 );
-                   return -1;
-                 }else {
-                   // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p2, p1 );
-                   res[2] = BOP_intersectPlane( plane, p2, p3 );
-                   return 1;
-                 }
-               case IN_OUT_IN :
-                 if (compChildren()<0) {
-                   // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
-                   res[0] = p1;
-                   res[1] = BOP_intersectPlane( plane, p2, p1 );
-                   res[2] = BOP_intersectPlane( plane, p2, p3 );
-                   return -1;
-                 }else{
-                   // f1: new1 p2 new2 || new1 = splitedge(p2,p1) new2 = splitedge(p2,p3)
-                   res[0] = BOP_intersectPlane( plane, p2, p1 );
-                   res[1] = p2;
-                   res[2] = BOP_intersectPlane( plane, p2, p3 );
-                   return 1;
-                 }
-               case OUT_OUT_IN :
-                 if (compChildren()<=0) {
-                   // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
-                   res[0] = BOP_intersectPlane( plane, p3, p1 );
-                   res[1] = BOP_intersectPlane( plane, p3, p2 );
-                   res[2] = p3;
-                   return -1;
-                 }else{
-                   // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
-                   res[0] = BOP_intersectPlane( plane, p3, p1 );
-                   res[1] = p1;
-                   res[2] = p2;
-                   return 1;
-                 }
-               case IN_IN_OUT :
-                 if (compChildren()<0) {
-                   // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
-                   res[0] = BOP_intersectPlane( plane, p3, p1 );
-                   res[1] = p1;
-                   res[2] = p2;
-                   return -1;
-                 }else{
-                   // f1: new1 new2 p2 || new1 = splitedge(p3,p1) new2 = splitedge(p3,p2)
-                   res[0] = BOP_intersectPlane( plane, p3, p1 );
-                   res[1] = BOP_intersectPlane( plane, p3, p2 );
-                   res[2] = p3;
-                   return 1;
-                 }
-       default:
-         return 0;
-       }
-}
-
-/**
- * Debug info.
- */
-void BOP_BSPNode::print(unsigned int deep)
-{
-       std::cout << "(" << deep << "," << m_plane << ")," << std::endl;
-       if (m_inChild != NULL)
-               m_inChild->print(deep + 1);
-       else
-               std::cout << "(" << deep+1 << ",None)," << std::endl;
-       if (m_outChild != NULL)
-               m_outChild->print(deep + 1);
-       else
-               std::cout << "(" << deep+1 << ",None)," << std::endl;
-}
diff --git a/intern/boolop/intern/BOP_BSPNode.h b/intern/boolop/intern/BOP_BSPNode.h
deleted file mode 100644 (file)
index 6c11041..0000000
+++ /dev/null
@@ -1,107 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_BSPNode.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_BSPNODE_H__
-#define __BOP_BSPNODE_H__
-
-#include "MT_Plane3.h"
-#include "BOP_Tag.h"
-#include "BOP_Face.h"
-
-typedef std::vector<MT_Point3> BOP_BSPPoints;
-typedef std::vector<MT_Point3>::const_iterator BOP_IT_BSPPoints;
-
-class BOP_BSPNode
-{
-protected:
-       BOP_BSPNode* m_inChild;
-       BOP_BSPNode* m_outChild;
-       MT_Plane3    m_plane;
-       unsigned int m_deep;
-
-public:
-       // Construction methods
-       BOP_BSPNode(const MT_Plane3& plane);
-       ~BOP_BSPNode();
-       unsigned int addFace(const BOP_BSPPoints& pts,
-                            const MT_Plane3& plane);
-       BOP_TAG classifyFace(const MT_Point3& p1,
-                            const MT_Point3& p2,
-                            const MT_Point3& p3,
-                            const MT_Plane3& plane) const;
-       BOP_TAG simplifiedClassifyFace(const MT_Point3& p1,
-                                      const MT_Point3& p2,
-                                      const MT_Point3& p3,
-                                      const MT_Plane3& plane) const;
-       
-protected:
-       BOP_TAG testPoint(const MT_Point3& p) const;
-       BOP_TAG classifyFaceIN(const MT_Point3& p1,
-                              const MT_Point3& p2,
-                              const MT_Point3& p3,
-                              const MT_Plane3& plane) const;
-       BOP_TAG classifyFaceOUT(const MT_Point3& p1,
-                               const MT_Point3& p2,
-                               const MT_Point3& p3,
-                               const MT_Plane3& plane) const;
-       BOP_TAG simplifiedClassifyFaceIN(const MT_Point3& p1,
-                                        const MT_Point3& p2,
-                                        const MT_Point3& p3,
-                                        const MT_Plane3& plane) const;
-       BOP_TAG simplifiedClassifyFaceOUT(const MT_Point3& p1,
-                                         const MT_Point3& p2,
-                                         const MT_Point3& p3,
-                                         const MT_Plane3& plane) const;
-       bool hasSameOrientation(const MT_Plane3& plane) const;
-       int compChildren() const;
-       int splitTriangle(MT_Point3* res,
-                         const MT_Plane3& plane,
-                         const MT_Point3& p1,
-                         const MT_Point3& p2,
-                         const MT_Point3& p3,
-                         const BOP_TAG tag) const;
-
-public:
-       // Inline acces methods
-       inline void setInChild(BOP_BSPNode* inChild) { m_inChild=inChild; };
-       inline void setOutChild(BOP_BSPNode* outChild) { m_outChild=outChild; };
-       inline BOP_BSPNode* getInChild() { return m_inChild; };
-       inline BOP_BSPNode* getOutChild() { return m_outChild; };
-       inline bool isLeaf() const { return !m_inChild && !m_outChild; };
-       inline void setPlane(const MT_Plane3& plane) {m_plane=plane;};
-       inline MT_Plane3& getPlane() { return m_plane; };
-
-       inline unsigned int getDeep() const {return m_deep;};
-       void print(unsigned int deep);
-};
-
-#endif
diff --git a/intern/boolop/intern/BOP_BSPTree.cpp b/intern/boolop/intern/BOP_BSPTree.cpp
deleted file mode 100644 (file)
index 7a8ed41..0000000
+++ /dev/null
@@ -1,190 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_BSPTree.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_BSPTree.h"
-#include <vector>
-#include <iostream>
-
-/**
- * Constructs a new BSP tree.
- */
-BOP_BSPTree::BOP_BSPTree()
-{
-       m_root = NULL;
-       m_bspBB = NULL;
-}
-
-/**
- * Destroys a BSP tree.
- */
-BOP_BSPTree::~BOP_BSPTree()
-{
-       if (m_root!=NULL) delete m_root;
-       if (m_bspBB!=NULL) delete m_bspBB;
-}
-
-/**
- * Adds all mesh faces to BSP tree.
- * @param mesh mesh to add.
- * @param facesList face list to add.
- */
-void BOP_BSPTree::addMesh(BOP_Mesh* mesh, BOP_Faces& facesList)
-{
-       for (BOP_IT_Faces it = facesList.begin(); it != facesList.end(); ++it) {
-               addFace( mesh, *it );
-       }
-       
-}
-
-/**
- * Adds a new face into bsp tree.
- * @param mesh Input data for BSP tree.
- * @param face index to mesh face.
- */
-
-void BOP_BSPTree::addFace(BOP_Mesh* mesh, BOP_Face* face)
-{
-       addFace(mesh->getVertex(face->getVertex(0))->getPoint(),
-                       mesh->getVertex(face->getVertex(1))->getPoint(),
-                       mesh->getVertex(face->getVertex(2))->getPoint(),
-                       face->getPlane());
-}
-
-/**
- * Adds new facee to the bsp-tree.
- * @param p1 first face point.
- * @param p2 second face point.
- * @param p3 third face point.
- * @param plane face plane.
- */
-void BOP_BSPTree::addFace(const MT_Point3& p1, 
-                                                 const MT_Point3& p2, 
-                                                 const MT_Point3& p3, 
-                                                 const MT_Plane3& plane)
-{
-       if (m_root == NULL)
-               m_root = new BOP_BSPNode(plane);
-       else {
-               BOP_BSPPoints pts;
-
-               pts.push_back(p1);
-               pts.push_back(p2);
-               pts.push_back(p3);
-
-               m_root->addFace(pts,plane);
-       }
-
-       // update bounding box
-       m_bbox.add(p1);
-       m_bbox.add(p2);
-       m_bbox.add(p3);
-}
-
-/**
- * Tests face vs bsp-tree (returns where is the face respect bsp planes).
- * @param p1 first face triangle point.
- * @param p2 secons face triangle point.
- * @param p3 third face triangle point.
- * @param plane face plane.
- * @return BSP_IN, BSP_OUT or BSP_IN_OUT
- */
-BOP_TAG BOP_BSPTree::classifyFace(const MT_Point3& p1, 
-                                                                 const MT_Point3& p2, 
-                                                                 const MT_Point3& p3, 
-                                                                 const MT_Plane3& plane) const
-{
-       if ( m_root != NULL )
-         return m_root->classifyFace(p1, p2, p3, plane);
-       else
-         return OUT;
-}
-
-/**
- * Filters a face using the BSP bounding infomation.
- * @param p1 first face triangle point.
- * @param p2 secons face triangle point.
- * @param p3 third face triangle point.
- * @param face face to test.
- * @return UNCLASSIFIED, BSP_IN, BSP_OUT or BSP_IN_OUT
- */
-BOP_TAG BOP_BSPTree::filterFace(const MT_Point3& p1, 
-                                                               const MT_Point3& p2, 
-                                                               const MT_Point3& p3, 
-                                                               BOP_Face* face)
-{
-       if ( m_bspBB != NULL ) {
-               return m_bspBB->classifyFace(p1,p2,p3,face->getPlane());
-       }
-       else
-               return UNCLASSIFIED;
-}
-
-/**
- * Tests face vs bsp-tree (returns where is the face respect bsp planes).
- * @param p1 first face triangle point.
- * @param p2 secons face triangle point.
- * @param p3 third face triangle point.
- * @param plane face plane.
- * @return BSP_IN, BSP_OUT or BSP_IN_OUT
- */
-BOP_TAG BOP_BSPTree::simplifiedClassifyFace(const MT_Point3& p1, 
-                                                                                       const MT_Point3& p2, 
-                                                                                       const MT_Point3& p3, 
-                                                                                       const MT_Plane3& plane) const
-{
-       if ( m_root != NULL )
-         return m_root->simplifiedClassifyFace(p1, p2, p3, plane);
-       else
-         return OUT;
-}
-
-/**
- * Returns the deep of this BSP tree.
- * @return tree deep
- */
-unsigned int BOP_BSPTree::getDeep() const
-{
-       if ( m_root != NULL )
-         return m_root->getDeep();
-       else
-         return 0;
-}
-
-/**
- * Prints debug information.
- */
-void BOP_BSPTree::print()
-{
-       if ( m_root != NULL )
-               m_root->print( 0 );
-}
-
diff --git a/intern/boolop/intern/BOP_BSPTree.h b/intern/boolop/intern/BOP_BSPTree.h
deleted file mode 100644 (file)
index 5dc55e4..0000000
+++ /dev/null
@@ -1,76 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_BSPTree.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_BSPTREE_H__
-#define __BOP_BSPTREE_H__
-
-#include "BOP_BSPNode.h"
-#include "BOP_Mesh.h"
-#include "BOP_Tag.h"
-#include "BOP_BBox.h"
-
-class BOP_BSPTree
-{
-protected:
-       BOP_BSPNode* m_root;
-       BOP_BSPNode* m_bspBB;
-       BOP_BBox     m_bbox;
-public:
-       // Construction methods
-       BOP_BSPTree();
-       virtual ~BOP_BSPTree();
-       void addMesh(BOP_Mesh* mesh, BOP_Faces& facesList);
-       void addFace(BOP_Mesh* mesh, BOP_Face* face);
-       virtual void addFace(const MT_Point3& p1,
-                            const MT_Point3& p2,
-                            const MT_Point3& p3,
-                            const MT_Plane3& plane);
-       BOP_TAG classifyFace(const MT_Point3& p1,
-                            const MT_Point3& p2,
-                            const MT_Point3& p3,
-                            const MT_Plane3& plane) const;
-       BOP_TAG filterFace(const MT_Point3& p1,
-                          const MT_Point3& p2,
-                          const MT_Point3& p3,
-                          BOP_Face* face);
-       BOP_TAG simplifiedClassifyFace(const MT_Point3& p1,
-                                      const MT_Point3& p2,
-                                      const MT_Point3& p3,
-                                      const MT_Plane3& plane) const;
-       unsigned int getDeep() const;
-       void print();
-       inline void setRoot(BOP_BSPNode* root) {m_root=root;};
-       inline BOP_BSPNode* getRoot() const {return m_root;};
-};
-
-#endif
-
diff --git a/intern/boolop/intern/BOP_Chrono.h b/intern/boolop/intern/BOP_Chrono.h
deleted file mode 100644 (file)
index 8f09eea..0000000
+++ /dev/null
@@ -1,54 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Chrono.h
- *  \ingroup boolopintern
- */
-
-
-#ifndef __BOP_CHRONO_H__
-#define __BOP_CHRONO_H__
-
-#include <time.h>
-
-class BOP_Chrono
-{
-private:
-       clock_t m_begin;
-public:
-       BOP_Chrono(){};
-       void start() {m_begin = clock();};
-       float stamp() {
-               clock_t c = clock();
-               clock_t stmp = c - m_begin;
-               m_begin = c;
-               float t = ((float) stmp / (float) CLOCKS_PER_SEC)*1000.0f;
-               return t;
-       };
-};
-
-#endif
diff --git a/intern/boolop/intern/BOP_Edge.cpp b/intern/boolop/intern/BOP_Edge.cpp
deleted file mode 100644 (file)
index fc03dd8..0000000
+++ /dev/null
@@ -1,125 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Edge.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_Edge.h"
-
-/**
- * Constructs a new edge.
- * @param v1 vertex index
- * @param v2 vertex index
- */
-BOP_Edge::BOP_Edge(BOP_Index v1, BOP_Index v2) 
-{
-       m_vertexs[0] = v1;
-       m_vertexs[1] = v2;
-}
-
-/**
- * Adds a new face index to this edge.
- * @param i face index
- */
-void BOP_Edge::addFace(BOP_Index i) 
-{
-       if (!containsFace(i))
-               m_faces.push_back(i);
-}
-
-/**
- * Returns if this edge contains the specified face index.
- * @param i face index
- * @return true if this edge contains the specified face index, false otherwise
- */
-bool BOP_Edge::containsFace(BOP_Index i)
-{
-       int pos=0;
-       for(BOP_IT_Indexs it = m_faces.begin();it!=m_faces.end();pos++,it++) {
-               if ((*it) == i)
-               return true;
-       }
-       
-       return false;
-}
-
-/**
- * Replaces an edge vertex index.
- * @param oldIndex old vertex index
- * @param newIndex new vertex index
- */
-void BOP_Edge::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex) 
-{
-       if (m_vertexs[0] == oldIndex) m_vertexs[0] = newIndex;
-       else if (m_vertexs[1] == oldIndex) m_vertexs[1] = newIndex;
-}
-
-#ifdef BOP_NEW_MERGE
-
-/**
- * Returns if this edge contains the specified face index.
- * @param i face index
- * @return true if this edge contains the specified face index, false otherwise
- */
-bool BOP_Edge::removeFace(BOP_Index i)
-{
-       int pos=0;
-       for(BOP_IT_Indexs it = m_faces.begin();it!=m_faces.end();pos++,it++) {
-               if ((*it) == i) {
-                       m_faces.erase(it);
-                       return true;
-               }
-       }
-       
-       return false;
-}
-
-#endif
-
-#ifdef BOP_DEBUG
-
-#include <iostream>
-
-/**
- * Implements operator <<.
- */
-ostream &operator<<(ostream &stream, BOP_Edge *e)
-{
-       stream << "Edge[" << e->getVertex1() << "," << e->getVertex2();
-#ifdef BOP_NEW_MERGE
-       if(e->m_used)
-               stream << "] (used)";
-       else
-               stream << "] (unused)";
-#endif
-       return stream;
-}
-#endif
-
-
diff --git a/intern/boolop/intern/BOP_Edge.h b/intern/boolop/intern/BOP_Edge.h
deleted file mode 100644 (file)
index fd2f53b..0000000
+++ /dev/null
@@ -1,70 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Edge.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_EDGE_H__
-#define __BOP_EDGE_H__
-
-#include "BOP_Indexs.h"
-#include "BOP_Misc.h"
-
-class BOP_Edge
-{
-private:
-       BOP_Index  m_vertexs[2];
-       BOP_Indexs m_faces;
-#ifdef BOP_NEW_MERGE
-       bool m_used;
-#endif
-
-       bool containsFace(BOP_Index i);
-
-public:
-       BOP_Edge(BOP_Index v1, BOP_Index v2);
-       inline BOP_Index getVertex1() { return m_vertexs[0];};
-       inline BOP_Index getVertex2() { return m_vertexs[1];};
-       void replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex);
-       inline BOP_Index getFace(unsigned int i){return m_faces[i];};
-       inline unsigned int getNumFaces(){return m_faces.size();};
-       inline BOP_Indexs &getFaces(){return m_faces;};
-       void addFace(BOP_Index face);
-#ifdef BOP_NEW_MERGE
-       bool removeFace(BOP_Index i);
-       bool getUsed() { return m_used;};
-       void setUsed(bool setting) { m_used=setting;};
-#endif
-#ifdef BOP_DEBUG
-       friend ostream &operator<<(ostream &stream, BOP_Edge *e);
-#endif
-
-};
-
-#endif
diff --git a/intern/boolop/intern/BOP_Face.cpp b/intern/boolop/intern/BOP_Face.cpp
deleted file mode 100644 (file)
index 651964f..0000000
+++ /dev/null
@@ -1,430 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Face.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_Face.h"
-
-/******************************************************************************/
-/*** BOP_Face                                                               ***/
-/******************************************************************************/
-
-/**
- * Constructs a new face.
- * @param plane face plane
- * @param originalFace index of the original face
- */
-BOP_Face::BOP_Face(MT_Plane3 plane, BOP_Index originalFace)
-{
-       m_plane        = plane;
-       m_tag          = UNCLASSIFIED;
-       m_originalFace = originalFace;
-       m_split        = 0;
-       m_bbox         = NULL;
-}
-
-/**
- * Inverts this face.
- */
-void BOP_Face::invert()
-{
-       getPlane().Invert();
-       BOP_Index aux = m_indexs[0];
-       m_indexs[0] = m_indexs[2];
-       m_indexs[2] = aux;
-}
-
-/******************************************************************************/
-/*** BOP_Face                                                              ***/
-/******************************************************************************/
-
-/**
- * Constructs a new triangle face.
- * @param v1 vertex index
- * @param v2 vertex index
- * @param v3 vertex index
- * @param plane face plane
- * @param originalFace index of the original face
- */
-BOP_Face3::BOP_Face3(BOP_Index v1, BOP_Index v2, BOP_Index v3, MT_Plane3 plane, BOP_Index originalFace): BOP_Face(plane,originalFace) 
-{
-       m_indexs[0] = v1;
-       m_indexs[1] = v2;
-       m_indexs[2] = v3;       
-       m_size = 3;
-}
-
-/**
- * Returns the relative edge index (1,2,3) for the specified vertex indexs.
- * @param v1 vertex index
- * @param v2 vertex index
- * @param e relative edge index (1,2,3)
- * @return true if (v1,v2) is an edge of this face, false otherwise
- */
-bool BOP_Face3::getEdgeIndex(BOP_Index v1, BOP_Index v2, unsigned int &e)
-{
-       if (m_indexs[0] == v1) {
-               if (m_indexs[1] == v2) {
-                       e = 1;
-               }
-               else if (m_indexs[2] == v2) {
-                       e = 3;
-               }
-               else
-                 return false;
-       }
-       else if (m_indexs[1] == v1) {
-               if (m_indexs[0] == v2) {
-                       e = 1;
-               }
-               else if (m_indexs[2] == v2) {
-                       e = 2;
-               }
-               else
-                 return false;
-       }
-       else if (m_indexs[2] == v1) {
-               if (m_indexs[0] == v2) {
-                       e = 3;
-               }
-               else if (m_indexs[1] == v2) {
-                       e = 2;
-               }
-               else
-                 return false;
-       }else {
-         return false;
-       }
-       
-       return  true;
-} 
-
-/**
- * Returns if this face contains the specified vertex index.
- * @param v vertex index
- * @return true if this face contains the specified vertex index, false otherwise
- */
-bool BOP_Face3::containsVertex(BOP_Index v) 
-{
-       return (m_indexs[0] == v || m_indexs[1] == v || m_indexs[2] == v);
-}
-
-/**
- * Returns the neighbours of the specified vertex index.
- * @param v vertex index
- * @param prev previous vertex index
- * @param next next vertex index
- * @return true if this face contains the vertex index v, false otherwise
- */
-bool BOP_Face3::getNeighbours(BOP_Index v, BOP_Index &prev, BOP_Index &next) 
-{
-       if (m_indexs[0] == v) {
-         prev = m_indexs[2];
-         next = m_indexs[1];
-       }
-       else if (m_indexs[1] == v) {
-         prev = m_indexs[0];
-         next = m_indexs[2];
-       }
-        else if (m_indexs[2] == v) {
-         prev = m_indexs[1];
-         next = m_indexs[0];
-       }
-       else return false;
-       
-       return true;
-}
-
-/**
- * Returns the previous neighbour of the specified vertex index.
- * @param v vertex index
- * @param w previous vertex index
- * @return true if this face contains the specified vertex index, false otherwise
- */
-bool BOP_Face3::getPreviousVertex(BOP_Index v, BOP_Index &w) 
-{
-       if (m_indexs[0] == v) w = m_indexs[2];
-       else if (m_indexs[1] == v) w = m_indexs[0];
-       else if (m_indexs[2] == v) w = m_indexs[1];
-       else return false;
-       
-       return true;
-}
-
-/**
- * Returns the next neighbour of the specified vertex index.
- * @param v vertex index
- * @param w vertex index
- * @return true if this face contains the specified vertex index, false otherwise
- */
-bool BOP_Face3::getNextVertex(BOP_Index v, BOP_Index &w) 
-{
-       if (m_indexs[0] == v) w = m_indexs[1];
-       else if (m_indexs[1] == v) w = m_indexs[2];
-       else if (m_indexs[2] == v) w = m_indexs[0];
-       else return false;
-       
-       return true;
-} 
-
-/**
- * Replaces a face vertex index.
- * @param oldIndex old vertex index
- * @param newIndex new vertex index
- */
-void BOP_Face3::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex)
-{
-       /* if the old index really exists, and new index also exists already,
-        * don't create an edge with both vertices == newIndex */
-
-       if( (m_indexs[0] == oldIndex || m_indexs[1] == oldIndex || m_indexs[2] == oldIndex) &&
-                       (m_indexs[0] == newIndex || m_indexs[1] == newIndex || m_indexs[2] == newIndex) ) {
-               setTAG(BROKEN);
-       }
-
-       if (m_indexs[0] == oldIndex) m_indexs[0] = newIndex;
-       else if (m_indexs[1] == oldIndex) m_indexs[1] = newIndex;
-       else if (m_indexs[2] == oldIndex) m_indexs[2] = newIndex;
-}
-
-/******************************************************************************/
-/*** BOP_Face4                                                              ***/
-/******************************************************************************/
-
-/**
- * Constructs a new quad face.
- * @param v1 vertex index
- * @param v2 vertex index
- * @param v3 vertex index
- * @param v4 vertex index
- * @param plane face plane
- * @param originalFace index of the original face
- */
-BOP_Face4::BOP_Face4(BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index v4, MT_Plane3 plane, 
-                                        BOP_Index originalFace): 
-                                        BOP_Face(plane,originalFace) 
-{
-       m_indexs[0] = v1;
-       m_indexs[1] = v2;
-       m_indexs[2] = v3;
-       m_indexs[3] = v4;
-       
-       m_size = 4;
-}
-
-/**
- * Returns if this face contains the specified vertex index.
- * @param v vertex index
- * @return true if this face contains the specified vertex index, false otherwise
- */
-bool BOP_Face4::containsVertex(BOP_Index v) 
-{
-       return (m_indexs[0] == v || m_indexs[1] == v || m_indexs[2] == v || m_indexs[3]==v);
-}
-
-/**
- * Returns the neighbours of the specified vertex index.
- * @param v vertex index
- * @param prev previous vertex index
- * @param next next vertex index
- * @param opp opposite vertex index
- * @return true if this face contains the vertex index v, false otherwise
- */
-bool BOP_Face4::getNeighbours(BOP_Index v, BOP_Index &prev, BOP_Index &next, BOP_Index &opp) 
-{
-       if (m_indexs[0] == v) {
-         prev = m_indexs[3];
-         next = m_indexs[1];
-         opp = m_indexs[2];
-       }
-       else if (m_indexs[1] == v) {
-         prev = m_indexs[0];
-         next = m_indexs[2];
-         opp = m_indexs[3];
-       }
-       else if (m_indexs[2] == v) {
-         prev = m_indexs[1];
-         next = m_indexs[3];
-         opp = m_indexs[0];
-       }
-       else if (m_indexs[3] == v) {
-         prev = m_indexs[2];
-         next = m_indexs[0];
-         opp = m_indexs[1];
-       }
-       else return false;
-
-       return true;
-}
-
-/**
- * Returns the previous neighbour of the specified vertex index.
- * @param v vertex index
- * @param w previous vertex index
- * @return true if this face contains the specified vertex index, false otherwise
- */
-bool BOP_Face4::getPreviousVertex(BOP_Index v, BOP_Index &w) 
-{
-       if (m_indexs[0] == v) w = m_indexs[3];
-       else if (m_indexs[1] == v) w = m_indexs[0];
-       else if (m_indexs[2] == v) w = m_indexs[1];
-       else if (m_indexs[3] == v) w = m_indexs[2];
-       else return false;
-
-       return true;
-}
-
-/**
- * Returns the next neighbour of the specified vertex index.
- * @param v vertex index
- * @param w next vertex index
- * @return true if this face contains the specified vertex index, false otherwise
- */
-bool BOP_Face4::getNextVertex(BOP_Index v, BOP_Index &w) 
-{
-       if (m_indexs[0] == v) w = m_indexs[1];
-       else if (m_indexs[1] == v) w = m_indexs[2];
-       else if (m_indexs[2] == v) w = m_indexs[3];
-       else if (m_indexs[3] == v) w = m_indexs[0];
-       else return false;
-
-       return true;
-} 
-
-/**
- * Returns the opposite  neighbour of the specified vertex index.
- * @param v vertex index
- * @param w opposite vertex index
- * @return true if this face contains the specified vertex index, false otherwise
- */
-bool BOP_Face4::getOppositeVertex(BOP_Index v, BOP_Index &w)
-{
-       if (m_indexs[0] == v) 
-               w = m_indexs[2];
-       else if (m_indexs[1] == v) 
-               w = m_indexs[3];
-       else if (m_indexs[2] == v) 
-               w = m_indexs[0];
-       else if (m_indexs[3] == v) 
-               w = m_indexs[1];
-       else
-         return false;
-
-       return true;
-}
-
-/**
- * Replaces a face vertex index.
- * @param oldIndex old vertex index
- * @param newIndex new vertex index
- */
-void BOP_Face4::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex)
-{
-       if (m_indexs[0] == oldIndex) m_indexs[0] = newIndex;
-       else if (m_indexs[1] == oldIndex) m_indexs[1] = newIndex;
-       else if (m_indexs[2] == oldIndex) m_indexs[2] = newIndex;
-       else if (m_indexs[3] == oldIndex) m_indexs[3] = newIndex;
-}
-
-/**
- * Returns the relative edge index (1,2,3,4) for the specified vertex indexs.
- * @param v1 vertex index
- * @param v2 vertex index
- * @param e relative edge index (1,2,3,4)
- * @return true if (v1,v2) is an edge of this face, false otherwise
- */
-bool BOP_Face4::getEdgeIndex(BOP_Index v1, BOP_Index v2, unsigned int &e)
-{
-       if (m_indexs[0] == v1) {
-               if (m_indexs[1] == v2) {
-                       e = 1;
-               }
-               else if (m_indexs[3] == v2) {
-                       e = 4;
-               }
-               else
-                 return false;
-       }
-       else if (m_indexs[1] == v1) {
-               if (m_indexs[0] == v2) {
-                       e = 1;
-               }
-               else if (m_indexs[2] == v2) {
-                       e = 2;
-               }
-               else
-                 return false;
-       }
-       else if (m_indexs[2] == v1) {
-               if (m_indexs[1] == v2) {
-                       e = 2;
-               }
-               else if (m_indexs[3] == v2) {
-                       e = 3;
-               }
-               else
-                 return false;
-       }
-       else if (m_indexs[3] == v1) {
-               if (m_indexs[2] == v2) {
-                       e = 3;
-               }
-               else if (m_indexs[0] == v2) {
-                       e = 4;
-               }
-               else
-                 return false;
-       }
-       else return false;
-       
-       return  true;
-}  
-
-#ifdef BOP_DEBUG
-/**
- * Implements operator <<.
- */
-ostream &operator<<(ostream &stream, BOP_Face *f)
-{
-       char aux[20];
-       BOP_stringTAG(f->m_tag,aux);
-       if (f->size()==3) {
-               stream << "Face[" << f->getVertex(0) << "," << f->getVertex(1) << ",";
-               stream << f->getVertex(2) << "] ("  <<  aux  <<  ") <-- " << f->m_originalFace;
-       }
-       else {
-               stream << "Face[" << f->getVertex(0) << "," << f->getVertex(1) << ",";
-               stream << f->getVertex(2) << "," << f->getVertex(3) << "] ("  <<  aux;
-               stream <<  ") <-- " << f->m_originalFace;
-       }
-
-       return stream;
-}
-#endif
diff --git a/intern/boolop/intern/BOP_Face.h b/intern/boolop/intern/BOP_Face.h
deleted file mode 100644 (file)
index 4f09618..0000000
+++ /dev/null
@@ -1,120 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Face.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_FACE_H__
-#define __BOP_FACE_H__
-
-#include "BOP_Tag.h"
-#include "MT_Plane3.h"
-#include "BOP_Indexs.h"
-#include "BOP_BBox.h"
-#include "BOP_Misc.h"
-#include <iostream>
-#include <vector>
-
-class BOP_Face;
-
-typedef std::vector<BOP_Face *> BOP_Faces;
-typedef std::vector<BOP_Face *>::iterator BOP_IT_Faces;
-
-class BOP_Face
-{
-private:
-       BOP_TAG      m_tag;
-       MT_Plane3    m_plane;
-       BOP_Index    m_originalFace;
-
-protected:
-       BOP_Index    m_indexs[4];
-       unsigned int m_size;
-       unsigned int m_split;
-       BOP_BBox     *m_bbox;
-
-public:
-       BOP_Face(MT_Plane3 plane, BOP_Index originalFace);
-       virtual ~BOP_Face(){if (m_bbox) delete m_bbox;};
-       inline MT_Plane3 getPlane() const {return m_plane;};
-       inline void setPlane(const MT_Plane3 plane) {m_plane = plane;};
-       inline BOP_TAG getTAG() const {return m_tag;};
-       inline void setTAG(const BOP_TAG t) {m_tag = t;};
-       inline BOP_Index getOriginalFace() const {return m_originalFace;};
-       inline void setOriginalFace(const BOP_Index originalFace) {m_originalFace=originalFace;};
-       inline BOP_Index getVertex(unsigned int i) const {return m_indexs[i];};
-       inline void setVertex(const BOP_Index idx, const BOP_Index i) {m_indexs[idx]=i;};
-       inline unsigned int getSplit() const {return m_split;};
-       inline void setSplit(const unsigned int i) {m_split=i;};
-
-       void invert();
-       inline void setBBox(const MT_Point3& p1,const MT_Point3& p2,const MT_Point3& p3) {
-    m_bbox = new BOP_BBox(p1, p2, p3);};
-       inline BOP_BBox *getBBox() {return m_bbox;};
-       inline void freeBBox(){if (m_bbox!=NULL) {delete m_bbox; m_bbox=NULL;} };
-
-       inline unsigned int size() const {return m_size;};
-       
-       virtual bool getEdgeIndex(BOP_Index v1, BOP_Index v2, unsigned int &e) = 0;
-       virtual void replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex) = 0;
-       virtual bool containsVertex(BOP_Index v) = 0;
-               
-#ifdef BOP_DEBUG
-       friend ostream &operator<<(ostream &stream, BOP_Face *f);
-#endif
-};
-
-class BOP_Face3: public BOP_Face 
-{
-public:
-       BOP_Face3(BOP_Index i, BOP_Index j, BOP_Index k, MT_Plane3 p, BOP_Index originalFace);
-       bool getEdgeIndex(BOP_Index v1, BOP_Index v2, unsigned int &e);
-       void replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex);
-       bool containsVertex(BOP_Index v);
-
-       bool getNeighbours(BOP_Index v, BOP_Index &prev, BOP_Index &next);
-       bool getPreviousVertex(BOP_Index v, BOP_Index &w);
-       bool getNextVertex(BOP_Index v, BOP_Index &w);
-};
-
-class BOP_Face4: public BOP_Face 
-{
-public:
-       BOP_Face4(BOP_Index i, BOP_Index j, BOP_Index k, BOP_Index l, MT_Plane3 p, BOP_Index originalFace);
-       bool getEdgeIndex(BOP_Index v1, BOP_Index v2, unsigned int &e);
-       void replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex);
-       bool containsVertex(BOP_Index v);
-
-       bool getNeighbours(BOP_Index v, BOP_Index &prev, BOP_Index &next, BOP_Index &opp);
-       bool getPreviousVertex(BOP_Index v, BOP_Index &w);
-       bool getNextVertex(BOP_Index v, BOP_Index &w);
-       bool getOppositeVertex(BOP_Index v, BOP_Index &w);
-};
-
-#endif
diff --git a/intern/boolop/intern/BOP_Face2Face.cpp b/intern/boolop/intern/BOP_Face2Face.cpp
deleted file mode 100644 (file)
index 905d23f..0000000
+++ /dev/null
@@ -1,1250 +0,0 @@
-/*
- *
- *
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Marc Freixas, Ken Hughes
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Face2Face.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_Face2Face.h"
-#include "BOP_BBox.h"
-
-// TAGS for segment classification in x-segment creation
-// sA -> point of sA
-// sB -> point of sB
-// sX -> point of sA and SB
-#define sA_sB 12
-#define sB_sA 21
-#define sX_sA 31
-#define sA_sX 13
-#define sX_sB 32
-#define sB_sX 23
-#define sX_sX 33
-    
-#define sA_sA_sB 112
-#define sB_sB_sA 221
-#define sB_sA_sA 211
-#define sA_sB_sB 122
-#define sA_sB_sA 121
-#define sB_sA_sB 212
-#define sA_sX_sB 132
-#define sB_sX_sA 231
-#define sX_sA_sB 312
-#define sX_sB_sA 321
-#define sA_sB_sX 123
-#define sB_sA_sX 213
-
-#define sA_sA_sB_sB 1122
-#define sB_sB_sA_sA 2211
-#define sA_sB_sA_sB 1212
-#define sB_sA_sB_sA 2121
-#define sA_sB_sB_sA 1221
-#define sB_sA_sA_sB 2112
-
-void BOP_intersectCoplanarFaces(BOP_Mesh*  mesh, 
-                                                               BOP_Faces* facesB, 
-                                                               BOP_Face*  faceA, 
-                                                               BOP_Face*  faceB, 
-                                                               bool       invert);
-
-void BOP_intersectCoplanarFaces(BOP_Mesh*   mesh, 
-                                                               BOP_Faces*  facesB, 
-                                                               BOP_Face*   faceB, 
-                                                               BOP_Segment sA, 
-                                                               MT_Plane3   planeA, 
-                                                               bool        invert);
-
-void BOP_intersectNonCoplanarFaces(BOP_Mesh*  mesh, 
-                                                                  BOP_Faces* facesA,  
-                                                                  BOP_Faces* facesB, 
-                                                                  BOP_Face*  faceA, 
-                                                                  BOP_Face*  faceB);
-
-void BOP_getPoints(BOP_Mesh*    mesh, 
-                                  BOP_Face*    faceA, 
-                                  BOP_Segment& sA, 
-                                  MT_Plane3    planeB, 
-                                  MT_Point3*   points, 
-                                  unsigned int*         faces, 
-                                  unsigned int&         size, 
-                                  unsigned int         faceValue);
-
-void BOP_mergeSort(MT_Point3 *points, unsigned int *face, unsigned int &size, bool &invertA, bool &invertB);
-
-void BOP_createXS(BOP_Mesh*    mesh, 
-                                 BOP_Face*    faceA, 
-                                 BOP_Face*    faceB, 
-                                 BOP_Segment  sA, 
-                                 BOP_Segment  sB, 
-                                 bool         invert, 
-                                 BOP_Segment* segments);    
-
-void BOP_createXS(BOP_Mesh*    mesh, 
-                                 BOP_Face*    faceA, 
-                                 BOP_Face*    faceB, 
-                                 MT_Plane3    planeA, 
-                                 MT_Plane3    planeB, 
-                                 BOP_Segment  sA, 
-                                 BOP_Segment  sB, 
-                                 bool         invert, 
-                                 BOP_Segment* segments);    
-
-BOP_Index BOP_getVertexIndex(BOP_Mesh* mesh, 
-                                          MT_Point3 point, 
-                                          unsigned int       cfgA, 
-                                          unsigned int       cfgB, 
-                                          BOP_Index       vA, 
-                                          BOP_Index       vB, 
-                                          bool      invert);
-
-BOP_Index BOP_getVertexIndex(BOP_Mesh *mesh, MT_Point3 point, unsigned int cfg, BOP_Index v);
-
-void triangulate(BOP_Mesh *mesh,  BOP_Faces *faces, BOP_Face *face, BOP_Segment s);
-
-BOP_Face *BOP_getOppositeFace(BOP_Mesh*  mesh, 
-                                                         BOP_Faces* faces, 
-                                                         BOP_Face*  face, 
-                                                         BOP_Edge*  edge);
-
-bool BOP_overlap(MT_Vector3 normal, 
-                                MT_Point3  p1, 
-                                MT_Point3  p2, 
-                                MT_Point3  p3, 
-                                MT_Point3  q1, 
-                                MT_Point3  q2, 
-                                MT_Point3  q3);
-
-void BOP_mergeVertexs(BOP_Mesh *mesh, unsigned int firstFace);
-
-
-/**
- * Computes intersections between faces of both lists.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param facesA set of faces from object A
- * @param facesB set of faces from object B
- *
- * Two optimizations were added here:
- *   1) keep the bounding box for a face once it's created; this is
- *      especially important for B faces, since they were being created and
- *      recreated over and over
- *   2) associate a "split" index in the faceB vector with each A face; when
- *      an A face is split, we will not need to recheck any B faces have
- *      already been checked against that original A face
- */
-
-void BOP_Face2Face(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB)
-{
-       for(unsigned int idxFaceA=0;idxFaceA<facesA->size();idxFaceA++) {
-               BOP_Face *faceA = (*facesA)[idxFaceA];
-               MT_Plane3 planeA = faceA->getPlane();
-               MT_Point3 p1 = mesh->getVertex(faceA->getVertex(0))->getPoint();
-               MT_Point3 p2 = mesh->getVertex(faceA->getVertex(1))->getPoint();
-               MT_Point3 p3 = mesh->getVertex(faceA->getVertex(2))->getPoint();
-
-               /* get (or create) bounding box for face A */
-               if( faceA->getBBox() == NULL )
-                       faceA->setBBox(p1,p2,p3);
-               BOP_BBox *boxA = faceA->getBBox();
-
-       /* start checking B faces with the previously stored split index */
-
-               for(unsigned int idxFaceB=faceA->getSplit();
-                   idxFaceB<facesB->size() && (faceA->getTAG() != BROKEN) && (faceA->getTAG() != PHANTOM);) {
-                       BOP_Face *faceB = (*facesB)[idxFaceB];
-                       faceA->setSplit(idxFaceB);
-                       if ((faceB->getTAG() != BROKEN) && (faceB->getTAG() != PHANTOM)) {
-
-                               /* get (or create) bounding box for face B */
-                               if( faceB->getBBox() == NULL ) {
-                                       faceB->setBBox(mesh->getVertex(faceB->getVertex(0))->getPoint(),
-                                                      mesh->getVertex(faceB->getVertex(1))->getPoint(),
-                                                      mesh->getVertex(faceB->getVertex(2))->getPoint());
-                               }
-                               BOP_BBox *boxB = faceB->getBBox();
-
-                               if (boxA->intersect(*boxB)) {
-                                       MT_Plane3 planeB = faceB->getPlane();
-                                       if (BOP_containsPoint(planeB,p1) &&
-                                               BOP_containsPoint(planeB,p2) &&
-                                               BOP_containsPoint(planeB,p3))
-                                       {
-                                               if (BOP_orientation(planeB,planeA)>0) {
-                                                       BOP_intersectCoplanarFaces(mesh,facesB,faceA,faceB,false);
-                                               }
-                                       }
-                                       else {
-                                               BOP_intersectNonCoplanarFaces(mesh,facesA,facesB,faceA,faceB);
-                                       }
-                               }
-                       }
-                       idxFaceB++;
-               }
-       }
-       
-       
-       // Clean broken faces from facesA
-       BOP_IT_Faces it;
-       it = facesA->begin();
-       while (it != facesA->end()) {
-               BOP_Face *face = *it;
-               if (face->getTAG() == BROKEN) it = facesA->erase(it);
-               else it++;
-       }
-       /*
-       it = facesB->begin();
-       while (it != facesB->end()) {
-               BOP_Face *face = *it;
-               if (face->getTAG() == BROKEN) it = facesB->erase(it);
-               else it++;
-       }
-       */
-}
-
-/**
- * Computes intesections of coplanars faces from object A with faces from object B.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param facesA set of faces from object A
- * @param facesB set of faces from object B
- */
-void BOP_sew(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB)
-{
-       for(unsigned int idxFaceB = 0; idxFaceB < facesB->size(); idxFaceB++) {
-               BOP_Face *faceB = (*facesB)[idxFaceB];
-               MT_Plane3 planeB = faceB->getPlane();
-               MT_Point3 p1 = mesh->getVertex(faceB->getVertex(0))->getPoint();
-               MT_Point3 p2 = mesh->getVertex(faceB->getVertex(1))->getPoint();
-               MT_Point3 p3 = mesh->getVertex(faceB->getVertex(2))->getPoint();
-               
-               for(unsigned int idxFaceA = 0;
-                       idxFaceA < facesA->size() &&
-                       faceB->getTAG() != BROKEN &&
-                       faceB->getTAG() != PHANTOM;
-                       idxFaceA++) {
-                       BOP_Face *faceA = (*facesA)[idxFaceA];
-                       if ((faceA->getTAG() != BROKEN)&&(faceA->getTAG() != PHANTOM)) {
-                               MT_Plane3 planeA = faceA->getPlane();
-                               if (BOP_containsPoint(planeA,p1) && 
-                                       BOP_containsPoint(planeA,p2) && 
-                                       BOP_containsPoint(planeA,p3)) {
-                                       if (BOP_orientation(planeA,planeB) > 0) {
-                                               BOP_intersectCoplanarFaces(mesh,facesA,faceB,faceA,true);
-                                       }
-                               }
-                       }
-               }
-       }
-}
-
-/**
- * Triangulates faceB using edges of faceA that both are complanars.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param facesB set of faces from object B
- * @param faceA face from object A
- * @param faceB face from object B
- * @param invert indicates if faceA has priority over faceB
- */
-void BOP_intersectCoplanarFaces(BOP_Mesh*  mesh,
-                                                               BOP_Faces* facesB, 
-                                                               BOP_Face*  faceA, 
-                                                               BOP_Face*  faceB, 
-                                                               bool       invert)
-{
-       unsigned int oldSize = facesB->size();
-       unsigned int originalFaceB = faceB->getOriginalFace();    
-       
-       MT_Point3 p1 = mesh->getVertex(faceA->getVertex(0))->getPoint();
-       MT_Point3 p2 = mesh->getVertex(faceA->getVertex(1))->getPoint();
-       MT_Point3 p3 = mesh->getVertex(faceA->getVertex(2))->getPoint();
-       
-       MT_Vector3 normal(faceA->getPlane().x(),faceA->getPlane().y(),faceA->getPlane().z());
-       
-       MT_Vector3 p1p2 = p2-p1;
-       
-       MT_Plane3 plane1((p1p2.cross(normal).normalized()),p1);
-       
-       BOP_Segment sA;
-       sA.m_cfg1 = BOP_Segment::createVertexCfg(1);
-       sA.m_v1 = faceA->getVertex(0);
-       sA.m_cfg2 = BOP_Segment::createVertexCfg(2);
-       sA.m_v2 = faceA->getVertex(1);
-       
-       BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane1,invert);
-       
-       MT_Vector3 p2p3 = p3-p2;
-       MT_Plane3 plane2((p2p3.cross(normal).normalized()),p2);
-       
-       sA.m_cfg1 = BOP_Segment::createVertexCfg(2);
-       sA.m_v1 = faceA->getVertex(1);
-       sA.m_cfg2 = BOP_Segment::createVertexCfg(3);
-       sA.m_v2 = faceA->getVertex(2);
-  
-       if (faceB->getTAG() == BROKEN) {
-               for(unsigned int idxFace = oldSize; idxFace < facesB->size(); idxFace++) {
-                       BOP_Face *face = (*facesB)[idxFace];
-                       if (face->getTAG() != BROKEN && originalFaceB == face->getOriginalFace())
-                               BOP_intersectCoplanarFaces(mesh,facesB,face,sA,plane2,invert);
-               }
-       }
-       else {
-               BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane2,invert);
-       }
-  
-       MT_Vector3 p3p1 = p1-p3;
-       MT_Plane3 plane3((p3p1.cross(normal).safe_normalized()),p3);
-       
-       sA.m_cfg1 = BOP_Segment::createVertexCfg(3);
-       sA.m_v1 = faceA->getVertex(2);
-       sA.m_cfg2 = BOP_Segment::createVertexCfg(1);
-       sA.m_v2 = faceA->getVertex(0);
-  
-       if (faceB->getTAG() == BROKEN) {
-               for(unsigned int idxFace = oldSize; idxFace < facesB->size(); idxFace++) {
-                       BOP_Face *face = (*facesB)[idxFace];
-                       if (face->getTAG() != BROKEN && originalFaceB == face->getOriginalFace())
-                               BOP_intersectCoplanarFaces(mesh,facesB,face,sA,plane3,invert);
-               }
-       }
-       else {
-               BOP_intersectCoplanarFaces(mesh,facesB,faceB,sA,plane3,invert);
-       } 
-}
-
-/**
- * Triangulates faceB using segment sA and planeA.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param facesB set of faces from object B
- * @param faceB face from object B
- * @param sA segment to intersect with faceB
- * @param planeA plane to intersect with faceB
- * @param invert indicates if sA has priority over faceB
- */
-void BOP_intersectCoplanarFaces(BOP_Mesh*   mesh, 
-                                                               BOP_Faces*  facesB, 
-                                                               BOP_Face*   faceB, 
-                                                               BOP_Segment sA, 
-                                                               MT_Plane3   planeA, 
-                                                               bool        invert)
-{
-       BOP_Segment sB = BOP_splitFace(planeA,mesh,faceB);
-
-       if (BOP_Segment::isDefined(sB.m_cfg1)) {
-               BOP_Segment xSegment[2];
-               BOP_createXS(mesh,NULL,faceB,planeA,MT_Plane3(),sA,sB,invert,xSegment);
-               if (BOP_Segment::isDefined(xSegment[1].m_cfg1)) {
-                       unsigned int sizefaces = mesh->getNumFaces();
-                       triangulate(mesh,facesB,faceB,xSegment[1]);
-                       BOP_mergeVertexs(mesh,sizefaces);
-               }
-       }
-}
-
-/**
- * Triangulates faceB using edges of faceA that both are not complanars.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param facesB set of faces from object B
- * @param faceA face from object A
- * @param faceB face from object B
- */
-void BOP_intersectNonCoplanarFaces(BOP_Mesh *mesh, 
-                                                                  BOP_Faces *facesA, 
-                                                                  BOP_Faces *facesB, 
-                                                                  BOP_Face *faceA, 
-                                                                  BOP_Face *faceB)
-{
-       // Obtain segments of faces A and B from the intersection with their planes
-       BOP_Segment sA = BOP_splitFace(faceB->getPlane(),mesh,faceA);
-       BOP_Segment sB = BOP_splitFace(faceA->getPlane(),mesh,faceB);
-       
-       if (BOP_Segment::isDefined(sA.m_cfg1) && BOP_Segment::isDefined(sB.m_cfg1)) {    
-               // There is an intesection, build the X-segment
-               BOP_Segment xSegment[2];
-               BOP_createXS(mesh,faceA,faceB,sA,sB,false,xSegment);
-               
-               unsigned int sizefaces = mesh->getNumFaces();
-               triangulate(mesh,facesA,faceA,xSegment[0]);
-               BOP_mergeVertexs(mesh,sizefaces);
-       
-               sizefaces = mesh->getNumFaces();
-               triangulate(mesh,facesB,faceB,xSegment[1]);
-               BOP_mergeVertexs(mesh,sizefaces);
-       }
-}
-
-/**
- * Tests if faces since firstFace have all vertexs non-coincident of colinear, otherwise repairs the mesh.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param firstFace first face index to be tested
- */
-void BOP_mergeVertexs(BOP_Mesh *mesh, unsigned int firstFace)
-{
-       unsigned int numFaces = mesh->getNumFaces();
-       for(unsigned int idxFace = firstFace; idxFace < numFaces; idxFace++) {
-               BOP_Face *face = mesh->getFace(idxFace);
-               if ((face->getTAG() != BROKEN) && (face->getTAG() != PHANTOM)) {
-                       MT_Point3 vertex1 = mesh->getVertex(face->getVertex(0))->getPoint();
-                       MT_Point3 vertex2 = mesh->getVertex(face->getVertex(1))->getPoint();
-                       MT_Point3 vertex3 = mesh->getVertex(face->getVertex(2))->getPoint();
-                       if (BOP_collinear(vertex1,vertex2,vertex3)) // collinear triangle 
-                               face->setTAG(PHANTOM);
-               }
-       }
-}
-
-/**
- * Obtains the points of the segment created from the intersection between faceA and planeB.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param faceA intersected face
- * @param sA segment of the intersection between  faceA and planeB
- * @param planeB intersected plane
- * @param points array of points where the new points are saved
- * @param faces array of relative face index to the points
- * @param size size of arrays points and faces
- * @param faceValue relative face index of new points
- */
-void BOP_getPoints(BOP_Mesh*    mesh, 
-                                  BOP_Face*    faceA, 
-                                  BOP_Segment& sA, 
-                                  MT_Plane3    planeB, 
-                                  MT_Point3*   points, 
-                                  unsigned int*         faces, 
-                                  unsigned int&         size, 
-                                  unsigned int          faceValue) 
-{
-       MT_Point3 p1,p2;  
-  
-       if (BOP_Segment::isDefined(sA.m_cfg1)) {
-               if (BOP_Segment::isEdge(sA.m_cfg1)) {
-                       // the new point becomes of split faceA edge 
-                       p1 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg1));
-               }
-               else if (BOP_Segment::isVertex(sA.m_cfg1)) {
-                       // the new point becomes of vertex faceA
-                       p1 =  mesh->getVertex(BOP_Segment::getVertex(sA.m_v1))->getPoint();
-               }
-
-               if (BOP_Segment::isDefined(sA.m_cfg2)) {
-                       if (BOP_Segment::isEdge(sA.m_cfg2)) {
-                               p2 = BOP_splitEdge(planeB,mesh,faceA,BOP_Segment::getEdge(sA.m_cfg2));
-                       }
-                       else if (BOP_Segment::isVertex(sA.m_cfg2)) { 
-                               p2 =  mesh->getVertex(BOP_Segment::getVertex(sA.m_v2))->getPoint();
-                       }
-                       points[size] = p1;
-                       points[size+1] = p2;
-                       faces[size] = faceValue;
-                       faces[size+1] = faceValue;
-                       size += 2;
-               }
-       
-               else {
-                       points[size] = p1;
-                       faces[size] = faceValue;
-                       size++;
-               }
-       }
-}
-
-/**
- * Sorts the colinear points and relative face indices.
- * @param points array of points where the new points are saved
- * @param faces array of relative face index to the points
- * @param size size of arrays points and faces
- * @param invertA indicates if points of same relative face had been exchanged
- */
-void BOP_mergeSort(MT_Point3 *points, unsigned int *face, unsigned int &size, bool &invertA, bool &invertB) {
-       MT_Point3 sortedPoints[4];
-       unsigned int sortedFaces[4], position[4];
-       unsigned int i;
-       if (size == 2) {
-
-               // Trivial case, only test the merge ...
-               if (BOP_fuzzyZero(points[0].distance(points[1]))) {
-                       face[0] = 3;
-                       size--;
-               }
-       }
-       else {
-               // size is 3 or 4
-               // Get segment extreme points
-               MT_Scalar maxDistance = -1;
-               for(i=0;i<size-1;i++){
-                       for(unsigned int j=i+1;j<size;j++){
-                               MT_Scalar distance = points[i].distance(points[j]);
-                               if (distance > maxDistance){
-                                       maxDistance = distance;
-                                       position[0] = i;
-                                       position[size-1] = j;
-                               }
-                       }
-               }
-
-               // Get segment inner points
-               position[1] = position[2] = size;
-               for(i=0;i<size;i++){
-                       if ((i != position[0]) && (i != position[size-1])){
-                               if (position[1] == size) position[1] = i;
-                               else position[2] = i;
-                       }
-               }
-
-               // Get inner points
-               if (position[2] < size) {
-                       MT_Scalar d1 = points[position[1]].distance(points[position[0]]);
-                       MT_Scalar d2 = points[position[2]].distance(points[position[0]]);
-                       if (d1 > d2) {
-                               unsigned int aux = position[1];
-                               position[1] = position[2];
-                               position[2] = aux;
-                       }
-               }
-
-               // Sort data
-               for(i=0;i<size;i++) {
-                       sortedPoints[i] = points[position[i]];
-                       sortedFaces[i] = face[position[i]];
-               }
-
-               invertA = false;
-               invertB = false;
-               if (face[1] == 1) {
-
-                       // invertA?
-                       for(i=0;i<size;i++) {
-                               if (position[i] == 1) {
-                                       invertA = true;
-                                       break;
-                               }
-                               else if (position[i] == 0) break;
-                       }
-
-                       // invertB?
-                       if (size == 4) {
-                               for(i=0;i<size;i++) {
-                                       if (position[i] == 3) {
-                                               invertB = true;
-                                               break;
-                                       }
-                                       else if (position[i] == 2) break;
-                               }
-                       }
-               }
-               else if (face[1] == 2) {
-                       // invertB?
-                       for(i=0;i<size;i++) {
-                               if (position[i] == 2) {
-                                       invertB = true;
-                                       break;
-                               }
-                               else if (position[i] == 1) break;
-                       }
-               }
-
-
-               // Merge data
-               MT_Scalar d1 = sortedPoints[1].distance(sortedPoints[0]);
-               MT_Scalar d2 = sortedPoints[1].distance(sortedPoints[2]);
-               if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[0]) {
-                       if (BOP_fuzzyZero(d2) && sortedFaces[1] != sortedFaces[2])  {
-                               if (d1 < d2) {
-                                       // merge 0 and 1
-                                       sortedFaces[0] = 3;
-                                       for(i = 1; i<size-1;i++) {
-                                               sortedPoints[i] = sortedPoints[i+1];
-                                               sortedFaces[i] = sortedFaces[i+1];
-                                       }
-                                       size--;
-                                       if (size == 3) {
-                                               // merge 1 and 2 ???
-                                               d1 = sortedPoints[1].distance(sortedPoints[2]);
-                                               if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[2])  {
-                                                       // merge!
-                                                       sortedFaces[1] = 3;
-                                                       size--;
-                                               }
-                                       }
-                               }
-                               else {
-                                       // merge 1 and 2
-                                       sortedFaces[1] = 3;
-                                       for(i = 2; i<size-1;i++) {
-                                               sortedPoints[i] = sortedPoints[i+1];
-                                               sortedFaces[i] = sortedFaces[i+1];
-                                       }
-                                       size--;
-                               }
-                       }
-                       else {
-                               // merge 0 and 1
-                               sortedFaces[0] = 3;
-                               for(i = 1; i<size-1;i++) {
-                                       sortedPoints[i] = sortedPoints[i+1];
-                                       sortedFaces[i] = sortedFaces[i+1];
-                               }
-                               size--;
-                               if (size == 3) {
-                                       // merge 1 i 2 ???
-                                       d1 = sortedPoints[1].distance(sortedPoints[2]);
-                                       if (BOP_fuzzyZero(d1) && sortedFaces[1] != sortedFaces[2])  {
-                                               // merge!
-                                               sortedFaces[1] = 3;
-                                               size--;
-                                       }
-                               }
-                       }
-               }
-               else {
-                       if (BOP_fuzzyZero(d2) && sortedFaces[1] != sortedFaces[2])  {
-                               // merge 1 and 2
-                               sortedFaces[1] = 3;
-                               for(i = 2; i<size-1;i++) {
-                                       sortedPoints[i] = sortedPoints[i+1];
-                                       sortedFaces[i] = sortedFaces[i+1];
-                               }
-                               size--;
-                       }
-                       else if (size == 4) {
-                               d1 = sortedPoints[2].distance(sortedPoints[3]);
-                               if (BOP_fuzzyZero(d1) && sortedFaces[2] != sortedFaces[3])  {
-                                       // merge 2 and 3
-                                       sortedFaces[2] = 3;
-                                       size--;
-                               }
-                       }
-               }
-
-               // Merge initial points ...
-               for(i=0;i<size;i++) {
-                       points[i] = sortedPoints[i];
-                       face[i] = sortedFaces[i];
-               }
-
-       }
-}
-
-
-/**
- * Computes the x-segment of two segments (the shared interval). The segments needs to have sA.m_cfg1 > 0 && sB.m_cfg1 > 0 .
- * @param mesh mesh that contains the faces, edges and vertices
- * @param faceA face of object A
- * @param faceB face of object B
- * @param sA segment of intersection between faceA and planeB
- * @param sB segment of intersection between faceB and planeA
- * @param invert indicates if faceA has priority over faceB
- * @param segmemts array of the output x-segments
- */
-void BOP_createXS(BOP_Mesh*    mesh,
-                  BOP_Face*    faceA,
-                  BOP_Face*    faceB,
-                  BOP_Segment  sA,
-                  BOP_Segment  sB,
-                  bool         invert,
-                  BOP_Segment* segments) {
-       BOP_createXS(mesh, faceA, faceB, faceA->getPlane(), faceB->getPlane(),
-                    sA, sB, invert, segments);
-}
-
-/**
- * Computes the x-segment of two segments (the shared interval). The segments needs to have sA.m_cfg1 > 0 && sB.m_cfg1 > 0 .
- * @param mesh mesh that contains the faces, edges and vertices
- * @param faceA face of object A
- * @param faceB face of object B
- * @param planeA plane of faceA
- * @param planeB plane of faceB
- * @param sA segment of intersection between faceA and planeB
- * @param sB segment of intersection between faceB and planeA
- * @param invert indicates if faceA has priority over faceB
- * @param segmemts array of the output x-segments
- */
-void BOP_createXS(BOP_Mesh*    mesh, 
-                                 BOP_Face*    faceA, 
-                                 BOP_Face*    faceB, 
-                                 MT_Plane3    planeA, 
-                                 MT_Plane3    planeB, 
-                                 BOP_Segment  sA, 
-                                 BOP_Segment  sB, 
-                                 bool         invert, 
-                                 BOP_Segment* segments)
-{    
-       MT_Point3 points[4];  // points of the segments
-       unsigned int face[4]; // relative face indexs (1 => faceA, 2 => faceB)
-       unsigned int size = 0;  // size of points and relative face indexs
-  
-       BOP_getPoints(mesh, faceA, sA, planeB, points, face, size, 1);
-       BOP_getPoints(mesh, faceB, sB, planeA, points, face, size, 2);
-
-       bool invertA = false;
-       bool invertB = false;
-       BOP_mergeSort(points,face,size,invertA,invertB);
-
-       if (invertA) sA.invert();
-       if (invertB) sB.invert();
-       
-       // Compute the configuration label
-       unsigned int label = 0;
-       for(unsigned int i =0; i < size; i++) {
-               label = face[i]+label*10;    
-       }
-
-       if (size == 1) {
-               // Two coincident points
-               segments[0].m_cfg1 = sA.m_cfg1;
-               segments[1].m_cfg1 = sB.m_cfg1;
-               
-               segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
-                                                                                         sA.m_v1, sB.m_v1, invert);
-               segments[1].m_v1 = segments[0].m_v1;
-               segments[0].m_cfg2 = segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-       }
-       else if (size == 2) {
-               switch(label) {
-               // Two non-coincident points
-               case sA_sB:
-               case sB_sA:
-                       segments[0].m_cfg1 = 
-                       segments[1].m_cfg1 = 
-                       segments[0].m_cfg2 = 
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-      
-               // Two coincident points and one non-coincident of sA
-               case sA_sX:
-                       segments[0].m_cfg1 = sA.m_cfg2;
-                       segments[1].m_cfg1 = sB.m_cfg1;
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1,
-                                                                                                 sA.m_v2, sB.m_v1, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-               case sX_sA:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.m_cfg1;
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
-                                                                                                 sA.m_v1, sB.m_v1, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-      
-               // Two coincident points and one non-coincident of sB
-               case sB_sX:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.m_cfg2;
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 
-                                                                                                 sA.m_v1, sB.m_v2, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-               case sX_sB:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.m_cfg1;
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 
-                                                                                                 sA.m_v1, sB.m_v1, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-               
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-      
-               // coincident points 2-2
-               case sX_sX:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.m_cfg1;          
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1, 
-                                                                                                 sA.m_v1, sB.m_v1, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.m_cfg2;
-                       segments[1].m_cfg2 = sB.m_cfg2;          
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg2, 
-                                                                                                 sA.m_v2, sB.m_v2, invert);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;
-               
-               default:
-                       break; 
-               }
-       }
-       else if (size == 3) {
-               switch(label) {
-               case sA_sA_sB:
-               case sB_sA_sA:
-               case sA_sB_sB:
-               case sB_sB_sA:
-                       segments[0].m_cfg1 = 
-                       segments[1].m_cfg1 = 
-                       segments[0].m_cfg2 = 
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-      
-               case sA_sB_sA:
-                       segments[1].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
-                       segments[1].m_cfg1 = sB.m_cfg1;
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[0].m_cfg1 = sA.getConfig();
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[0].m_v1 = segments[1].m_v1;
-                       break;
-      
-               case sB_sA_sB:
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_cfg1 = sB.getConfig();
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_v1 = segments[0].m_v1;
-                       break;
-      
-               case sA_sX_sB:
-                       segments[0].m_cfg1 = sA.m_cfg2;
-                       segments[1].m_cfg1 = sB.m_cfg1;          
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sB.m_cfg1, 
-                                                                                                 sA.m_v2, sB.m_v1, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-    
-               case sB_sX_sA:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.m_cfg2;          
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg1, sB.m_cfg2, 
-                                                                                                 sA.m_v1, sB.m_v2, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       segments[0].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-      
-               case sX_sA_sB:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.m_cfg1;          
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
-                                                                                                 sA.m_v1, sB.m_v1, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.m_cfg2;
-                       segments[1].m_cfg2 = sB.getConfig();
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh, points[1], sA.m_cfg2, sA.m_v2);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;
-      
-               case sX_sB_sA:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.m_cfg1;          
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh, points[0], sA.m_cfg1, sB.m_cfg1,
-                                                                                                 sA.m_v1, sB.m_v1, invert);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.getConfig();
-                       segments[1].m_cfg2 = sB.m_cfg2;
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg2,sB.m_v2);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;
-      
-               case sA_sB_sX:
-                       segments[0].m_cfg1 = sA.getConfig();
-                       segments[1].m_cfg1 = sB.m_cfg1;
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.m_cfg2;
-                       segments[1].m_cfg2 = sB.m_cfg2;          
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2, 
-                                                                                                 sA.m_v2, sB.m_v2, invert);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;
-
-               case sB_sA_sX:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.getConfig();
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.m_cfg2;
-                       segments[1].m_cfg2 = sB.m_cfg2;          
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh, points[2], sA.m_cfg2, sB.m_cfg2,
-                                                                                                 sA.m_v2, sB.m_v2, invert);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;
-      
-               default:
-                       break; 
-               }
-       }
-       else {
-               // 4!
-               switch(label) {
-               case sA_sA_sB_sB:
-               case sB_sB_sA_sA:
-                       segments[0].m_cfg1 = 
-                       segments[1].m_cfg1 = 
-                       segments[0].m_cfg2 = 
-                       segments[1].m_cfg2 = BOP_Segment::createUndefinedCfg();
-                       break;
-      
-               case sA_sB_sA_sB:
-                       segments[0].m_cfg1 = sA.getConfig();
-                       segments[1].m_cfg1 = sB.m_cfg1;
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.m_cfg2;
-                       segments[1].m_cfg2 = sB.getConfig();
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;          
-      
-               case sB_sA_sB_sA:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.getConfig();
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.getConfig();
-                       segments[1].m_cfg2 = sB.m_cfg2;
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;          
-      
-               case sA_sB_sB_sA:
-                       segments[0].m_cfg1 = sA.getConfig();
-                       segments[1].m_cfg1 = sB.m_cfg1;
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sB.m_cfg1,sB.m_v1);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = segments[0].m_cfg1;
-                       segments[1].m_cfg2 = sB.m_cfg2;
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sB.m_cfg2,sB.m_v2);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;
-      
-               case sB_sA_sA_sB:
-                       segments[0].m_cfg1 = sA.m_cfg1;
-                       segments[1].m_cfg1 = sB.getConfig();
-                       segments[0].m_v1 = BOP_getVertexIndex(mesh,points[1],sA.m_cfg1,sA.m_v1);
-                       segments[1].m_v1 = segments[0].m_v1;
-                       
-                       segments[0].m_cfg2 = sA.m_cfg2;
-                       segments[1].m_cfg2 = segments[1].m_cfg1;
-                       segments[0].m_v2 = BOP_getVertexIndex(mesh,points[2],sA.m_cfg2,sA.m_v2);
-                       segments[1].m_v2 = segments[0].m_v2;
-                       break;
-      
-               default:
-                       break; 
-               }
-       }
-       
-       segments[0].sort();
-       segments[1].sort();
-}
-
-/**
- * Computes the vertex index of a point.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param point input point
- * @param cfgA configuration of point on faceA
- * @param cfgB configuration of point on faceB
- * @param vA vertex index of point on faceA
- * @param vB vertex index of point on faceB
- * @param invert indicates if vA has priority over vB
- * @return final vertex index in the mesh
- */
-BOP_Index BOP_getVertexIndex(BOP_Mesh* mesh, 
-                                          MT_Point3 point, 
-                                          unsigned int       cfgA, 
-                                          unsigned int       cfgB, 
-                                          BOP_Index       vA, 
-                                          BOP_Index       vB, 
-                                          bool      invert)
-{
-       if (BOP_Segment::isVertex(cfgA)) { // exists vertex index on A
-               if (BOP_Segment::isVertex(cfgB)) { // exists vertex index on B
-                       // unify vertex indexs
-                       if (invert)
-                               return mesh->replaceVertexIndex(vA,vB);
-                       else 
-                               return mesh->replaceVertexIndex(vB,vA);
-               }
-               else
-                       return vA;
-       }
-       else {// does not exist vertex index on A
-               if (BOP_Segment::isVertex(cfgB)) // exists vertex index on B
-                       return vB;      
-               else {// does not exist vertex index on B
-                       return mesh->addVertex(point);
-               }
-       } 
-}
-
-/**
- * Computes the vertex index of a point.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param cfg configuration of point
- * @param v vertex index of point
- * @return final vertex index in the mesh
- */
-BOP_Index BOP_getVertexIndex(BOP_Mesh *mesh, MT_Point3 point, unsigned int cfg, BOP_Index v)
-{
-       if (BOP_Segment::isVertex(cfg)) // vertex existent
-               return v;       
-       else {
-               return mesh->addVertex(point);
-       }
-}
-
-/******************************************************************************/
-/*** TRIANGULATE                                                            ***/
-/******************************************************************************/
-
-/**
- * Triangulates the input face according to the specified segment.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param faces set of faces that contains the original face and the new triangulated faces
- * @param face face to be triangulated
- * @param s segment used to triangulate face
- */
-void triangulate(BOP_Mesh *mesh, BOP_Faces *faces, BOP_Face *face, BOP_Segment s)
-{
-       if (BOP_Segment::isUndefined(s.m_cfg1)) {
-               // Nothing to do
-       }
-       else if (BOP_Segment::isVertex(s.m_cfg1)) {
-               // VERTEX(v1) + VERTEX(v2) => nothing to do
-       }
-       else if (BOP_Segment::isEdge(s.m_cfg1)) {
-               if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) {
-                       // EDGE(v1) + VERTEX(v2)
-                       BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
-                       BOP_triangulateA(mesh,faces,face,s.m_v1,BOP_Segment::getEdge(s.m_cfg1));
-                       BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
-                       if (opposite != NULL) {
-                         unsigned int e;
-                         opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
-                         BOP_triangulateA(mesh, faces, opposite, s.m_v1, e);
-                       }
-               }
-               else {
-                       //  EDGE(v1) + EDGE(v2)
-                       if (BOP_Segment::getEdge(s.m_cfg1) == BOP_Segment::getEdge(s.m_cfg2)) {
-                               // EDGE(v1) == EDGE(v2)
-                               BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
-                               BOP_triangulateD(mesh, faces, face, s.m_v1, s.m_v2,
-                                                BOP_Segment::getEdge(s.m_cfg1));
-                               BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
-                               if (opposite != NULL) {
-                                       unsigned int e;
-                                       opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
-                                       BOP_triangulateD(mesh, faces, opposite, s.m_v1, s.m_v2, e);
-                               }
-                       }
-                       else { // EDGE(v1) != EDGE(v2)
-                               BOP_Edge *edge1 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg1));
-                               BOP_Edge *edge2 = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2));
-                               BOP_triangulateE(mesh, faces, face, s.m_v1, s.m_v2,
-                                                                BOP_Segment::getEdge(s.m_cfg1),
-                                                                BOP_Segment::getEdge(s.m_cfg2));
-                               BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge1);
-                               if (opposite != NULL) {
-                                 unsigned int e;
-                                 opposite->getEdgeIndex(edge1->getVertex1(), edge1->getVertex2(),e);
-                                 BOP_triangulateA(mesh, faces, opposite, s.m_v1, e);
-                               }
-                               opposite = BOP_getOppositeFace(mesh,faces,face,edge2);
-                               if (opposite != NULL) {
-                                 unsigned int e;
-                                 opposite->getEdgeIndex(edge2->getVertex1(), edge2->getVertex2(),e);
-                                 BOP_triangulateA(mesh, faces, opposite, s.m_v2, e);
-                               }
-                       }
-               }
-       }
-       else if (BOP_Segment::isIn(s.m_cfg1)) {
-               if (BOP_Segment::isVertex(s.m_cfg2) || BOP_Segment::isUndefined(s.m_cfg2)) {
-                       // IN(v1) + VERTEX(v2)
-                       BOP_triangulateB(mesh,faces,face,s.m_v1);
-               }
-               else if (BOP_Segment::isEdge(s.m_cfg2)) {
-                       // IN(v1) + EDGE(v2)
-                       BOP_Edge *edge = mesh->getEdge(face,BOP_Segment::getEdge(s.m_cfg2));
-                       BOP_triangulateF(mesh,faces,face,s.m_v1,s.m_v2,BOP_Segment::getEdge(s.m_cfg2));
-                       BOP_Face *opposite = BOP_getOppositeFace(mesh,faces,face,edge);
-                       if (opposite != NULL) {
-                         unsigned int e;
-                         opposite->getEdgeIndex(edge->getVertex1(), edge->getVertex2(),e);
-                         BOP_triangulateA(mesh, faces, opposite, s.m_v2, e);
-                       }
-               }
-               else // IN(v1) + IN(v2)
-                       BOP_triangulateC(mesh,faces,face,s.m_v1,s.m_v2);
-       }
-}
-
-/**
- * Returns if a face is in the set of faces.
- * @param faces set of faces
- * @param face face to be searched
- * @return if the face is inside faces
- */
-bool BOP_containsFace(BOP_Faces *faces, BOP_Face *face)
-{
-  const BOP_IT_Faces facesEnd = faces->end();
-       for(BOP_IT_Faces it=faces->begin();it!=facesEnd;it++)
-       {
-               if (*it == face)
-               return true;
-       }
-       
-       return false;
-}
-
-/**
- * Returns the first face of faces that shares the input edge of face.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param faces set of faces
- * @param face input face
- * @param edge face's edge
- * @return first face that shares the edge of input face
- */
-BOP_Face *BOP_getOppositeFace(BOP_Mesh*  mesh, 
-                                                         BOP_Faces* faces, 
-                                                         BOP_Face*  face,
-                                                         BOP_Edge*  edge)
-{
-       if (edge == NULL)
-         return NULL;
-  
-       BOP_Indexs auxfaces = edge->getFaces();
-       const BOP_IT_Indexs auxfacesEnd = auxfaces.end();
-       for(BOP_IT_Indexs it = auxfaces.begin(); it != auxfacesEnd; it++) {
-               BOP_Face *auxface = mesh->getFace(*it);
-               if ((auxface != face) && (auxface->getTAG()!=BROKEN) && 
-                       BOP_containsFace(faces,auxface)) {
-                       return auxface;
-               }
-       }        
-  
-       return NULL;
-}
-
-/******************************************************************************/ 
-/***  OVERLAPPING                                                           ***/
-/******************************************************************************/ 
-
-/**
- * Removes faces from facesB that are overlapped with anyone from facesA.
- * @param mesh mesh that contains the faces, edges and vertices
- * @param facesA set of faces from object A
- * @param facesB set of faces from object B
- */
-void BOP_removeOverlappedFaces(BOP_Mesh *mesh,  BOP_Faces *facesA,  BOP_Faces *facesB)
-{
-       for(unsigned int i=0;i<facesA->size();i++) {
-               BOP_Face *faceI = (*facesA)[i];
-               if (faceI->getTAG()==BROKEN) continue;
-               bool overlapped = false;
-               MT_Point3 p1 = mesh->getVertex(faceI->getVertex(0))->getPoint();
-               MT_Point3 p2 = mesh->getVertex(faceI->getVertex(1))->getPoint();
-               MT_Point3 p3 = mesh->getVertex(faceI->getVertex(2))->getPoint();
-               for(unsigned int j=0;j<facesB->size();) {
-                       BOP_Face *faceJ = (*facesB)[j];
-                       if (faceJ->getTAG()!=BROKEN) {
-                               MT_Plane3 planeJ = faceJ->getPlane();
-                               if (BOP_containsPoint(planeJ,p1) && BOP_containsPoint(planeJ,p2)
-                                       && BOP_containsPoint(planeJ,p3))
-                               {
-                                       MT_Point3 q1 = mesh->getVertex(faceJ->getVertex(0))->getPoint();
-                                       MT_Point3 q2 = mesh->getVertex(faceJ->getVertex(1))->getPoint();
-                                       MT_Point3 q3 = mesh->getVertex(faceJ->getVertex(2))->getPoint();
-                                       if (BOP_overlap(MT_Vector3(planeJ.x(),planeJ.y(),planeJ.z()),
-                                                       p1,p2,p3,q1,q2,q3))
-                                       {
-                                               facesB->erase(facesB->begin()+j,facesB->begin()+(j+1));
-                                               faceJ->setTAG(BROKEN);
-                                               overlapped = true;
-                                       }
-                                       else j++;
-                               }
-                               else j++;
-                       }else j++;
-               }
-               if (overlapped) faceI->setTAG(OVERLAPPED);
-       }
-}
-
-/**
- * Computes if triangle p1,p2,p3 is overlapped with triangle q1,q2,q3.
- * @param normal normal of the triangle p1,p2,p3
- * @param p1 point of first triangle
- * @param p2 point of first triangle
- * @param p3 point of first triangle
- * @param q1 point of second triangle
- * @param q2 point of second triangle
- * @param q3 point of second triangle
- * @return if there is overlapping between both triangles
- */
-bool BOP_overlap(MT_Vector3 normal, MT_Point3 p1, MT_Point3 p2, MT_Point3 p3, 
-                                 MT_Point3 q1, MT_Point3 q2, MT_Point3 q3)
-{
-       MT_Vector3 p1p2 = p2-p1;    
-       MT_Plane3 plane1(p1p2.cross(normal),p1);
-       
-       MT_Vector3 p2p3 = p3-p2;
-       MT_Plane3 plane2(p2p3.cross(normal),p2);
-       
-       MT_Vector3 p3p1 = p1-p3;    
-       MT_Plane3 plane3(p3p1.cross(normal),p3);
-  
-       BOP_TAG tag1 = BOP_createTAG(BOP_classify(q1,plane1));
-       BOP_TAG tag2 = BOP_createTAG(BOP_classify(q1,plane2));
-       BOP_TAG tag3 = BOP_createTAG(BOP_classify(q1,plane3));
-       BOP_TAG tagQ1 = BOP_createTAG(tag1,tag2,tag3);   
-       if (tagQ1 == IN_IN_IN) return true;    
-  
-       tag1 = BOP_createTAG(BOP_classify(q2,plane1));
-       tag2 = BOP_createTAG(BOP_classify(q2,plane2));
-       tag3 = BOP_createTAG(BOP_classify(q2,plane3));
-       BOP_TAG tagQ2 = BOP_createTAG(tag1,tag2,tag3);
-       if (tagQ2 == IN_IN_IN) return true;    
-       
-       tag1 = BOP_createTAG(BOP_classify(q3,plane1));
-       tag2 = BOP_createTAG(BOP_classify(q3,plane2));
-       tag3 = BOP_createTAG(BOP_classify(q3,plane3));
-       BOP_TAG tagQ3 = BOP_createTAG(tag1,tag2,tag3);
-       if (tagQ3 == IN_IN_IN) return true;    
-  
-       if ((tagQ1 & OUT_OUT_OUT) == 0 && (tagQ2 & OUT_OUT_OUT) == 0 && 
-               (tagQ3 & OUT_OUT_OUT) == 0) return true;
-       else return false;
-}
diff --git a/intern/boolop/intern/BOP_Face2Face.h b/intern/boolop/intern/BOP_Face2Face.h
deleted file mode 100644 (file)
index 9809084..0000000
+++ /dev/null
@@ -1,46 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Face2Face.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_FACE2FACE_H__
-#define __BOP_FACE2FACE_H__
-
-#include "BOP_Mesh.h"
-#include "BOP_Segment.h"
-#include "BOP_Triangulator.h"
-#include "BOP_Splitter.h"
-#include "BOP_BSPTree.h"
-
-void BOP_Face2Face(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB);
-void BOP_sew(BOP_Mesh *mesh, BOP_Faces *facesA, BOP_Faces *facesB);
-void BOP_removeOverlappedFaces(BOP_Mesh *mesh,  BOP_Faces *facesA,  BOP_Faces *facesB);
-
-#endif
diff --git a/intern/boolop/intern/BOP_Indexs.h b/intern/boolop/intern/BOP_Indexs.h
deleted file mode 100644 (file)
index e001f41..0000000
+++ /dev/null
@@ -1,42 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Indexs.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_INDEXS_H__
-#define __BOP_INDEXS_H__
-
-#include <vector>
-
-typedef unsigned int BOP_Index;
-typedef std::vector<BOP_Index> BOP_Indexs;
-typedef std::vector<BOP_Index>::iterator BOP_IT_Indexs;
-
-#endif
diff --git a/intern/boolop/intern/BOP_Interface.cpp b/intern/boolop/intern/BOP_Interface.cpp
deleted file mode 100644 (file)
index b18a433..0000000
+++ /dev/null
@@ -1,535 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Interface.cpp
- *  \ingroup boolopintern
- */
-
-#include <iostream>
-#include <map>
-#include "../extern/BOP_Interface.h"
-#include "../../bsp/intern/BSP_CSGMesh_CFIterator.h"
-#include "BOP_BSPTree.h"
-#include "BOP_Mesh.h"
-#include "BOP_Face2Face.h"
-#include "BOP_Merge.h"
-#include "BOP_Merge2.h"
-#include "BOP_Chrono.h"
-
-#if defined(BOP_ORIG_MERGE) && defined(BOP_NEW_MERGE) 
-#include "../../../source/blender/blenkernel/BKE_global.h"
-#endif
-
-BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
-                                   BOP_Faces* facesA,
-                                   BOP_Faces* facesB,
-                                   bool       invertMeshA,
-                                   bool       invertMeshB);
-BOP_Face3* BOP_createFace(BOP_Mesh* mesh, 
-                          BOP_Index vertex1,
-                          BOP_Index vertex2,
-                          BOP_Index vertex3,
-                          BOP_Index origFace);
-void BOP_addMesh(BOP_Mesh*                     mesh,
-                 BOP_Faces*                    meshFacesId,
-                 CSG_FaceIteratorDescriptor&   face_it,
-                 CSG_VertexIteratorDescriptor& vertex_it,
-                 bool                          invert);
-BSP_CSGMesh* BOP_newEmptyMesh();
-BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  inputMesh, 
-                            bool                       invert);
-void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp);
-void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted);
-void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp);
-
-/**
- * Performs a generic booleam operation, the entry point for external modules.
- * @param opType Boolean operation type BOP_INTERSECTION, BOP_UNION, BOP_DIFFERENCE
- * @param outputMesh Output mesh, the final result (the object C)
- * @param obAFaces Object A faces list
- * @param obAVertices Object A vertices list
- * @param obBFaces Object B faces list
- * @param obBVertices Object B vertices list
- * @param interpFunc Interpolating function
- * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR
- */
-BoolOpState BOP_performBooleanOperation(BoolOpType                    opType,
-                                                                               BSP_CSGMesh**                 outputMesh,
-                                                                               CSG_FaceIteratorDescriptor    obAFaces,
-                                                                               CSG_VertexIteratorDescriptor  obAVertices,
-                                                                               CSG_FaceIteratorDescriptor    obBFaces,
-                                                                               CSG_VertexIteratorDescriptor  obBVertices)
-{
-       #ifdef BOP_DEBUG
-       std::cout << "BEGIN BOP_performBooleanOperation" << std::endl;
-       #endif
-
-       // Set invert flags depending on boolean operation type:
-       // INTERSECTION: A^B = and(A,B)
-       // UNION:        A|B = not(and(not(A),not(B)))
-       // DIFFERENCE:   A-B = and(A,not(B))
-       bool invertMeshA = (opType == BOP_UNION);
-       bool invertMeshB = (opType != BOP_INTERSECTION);
-       bool invertMeshC = (opType == BOP_UNION);
-       
-       // Faces list for both objects, used by boolean op.
-       BOP_Faces meshAFacesId;
-       BOP_Faces meshBFacesId;
-       
-       // Build C-mesh, the output mesh
-       BOP_Mesh meshC;
-
-       // Add A-mesh into C-mesh
-       BOP_addMesh(&meshC, &meshAFacesId, obAFaces, obAVertices, invertMeshA);
-
-       // Add B-mesh into C-mesh
-       BOP_addMesh(&meshC, &meshBFacesId, obBFaces, obBVertices, invertMeshB);
-
-       // for now, allow operations on non-manifold (non-solid) meshes
-#if 0
-       if (!meshC.isClosedMesh())
-               return BOP_NO_SOLID;
-#endif
-
-       // Perform the intersection boolean operation.
-       BoolOpState result = BOP_intersectionBoolOp(&meshC, &meshAFacesId, &meshBFacesId, 
-                                                                                               invertMeshA, invertMeshB);
-
-       // Invert the output mesh if is required
-       *outputMesh = BOP_exportMesh(&meshC, invertMeshC);
-
-       #ifdef BOP_DEBUG
-       std::cout << "END BOP_performBooleanOperation" << std::endl;
-       #endif
-       
-       return result;
-}
-
-/**
- * Computes the intersection boolean operation. Creates a new mesh resulting from 
- * an intersection of two meshes.
- * @param meshC Input & Output mesh
- * @param facesA Mesh A faces list
- * @param facesB Mesh B faces list
- * @param invertMeshA determines if object A is inverted
- * @param invertMeshB determines if object B is inverted
- * @return operation state: BOP_OK, BOP_NO_SOLID, BOP_ERROR
- */
-BoolOpState BOP_intersectionBoolOp(BOP_Mesh*  meshC,
-                                                                  BOP_Faces* facesA,
-                                                                  BOP_Faces* facesB,
-                                                                  bool       invertMeshA,
-                                                                  bool       invertMeshB)
-{
-       #ifdef BOP_DEBUG
-       BOP_Chrono chrono;
-       float t = 0.0f;
-       float c = 0.0f;
-       chrono.start();  
-       std::cout << "---" << std::endl;
-       #endif
-
-       // Create BSPs trees for mesh A & B
-       BOP_BSPTree bspA;
-       bspA.addMesh(meshC, *facesA);
-
-       BOP_BSPTree bspB;
-       bspB.addMesh(meshC, *facesB);
-
-       #ifdef BOP_DEBUG
-       c = chrono.stamp(); t += c;
-       std::cout << "Create BSP     " << c << std::endl;       
-       #endif
-
-       unsigned int numVertices = meshC->getNumVertexs();
-       
-       // mesh pre-filter
-       BOP_simplifiedMeshFilter(meshC, facesA, &bspB, invertMeshB);
-       if ((0.25*facesA->size()) > bspB.getDeep())
-         BOP_meshFilter(meshC, facesA, &bspB);
-
-       BOP_simplifiedMeshFilter(meshC, facesB, &bspA, invertMeshA);
-       if ((0.25*facesB->size()) > bspA.getDeep())
-         BOP_meshFilter(meshC, facesB, &bspA);
-       
-       #ifdef BOP_DEBUG
-       c = chrono.stamp(); t += c;
-       std::cout << "mesh Filter    " << c << std::endl;       
-       #endif
-
-       // Face 2 Face
-       BOP_Face2Face(meshC,facesA,facesB);
-
-       #ifdef BOP_DEBUG
-       c = chrono.stamp(); t += c;
-       std::cout << "Face2Face      " << c << std::endl;
-       #endif
-
-       // BSP classification
-       BOP_meshClassify(meshC,facesA,&bspB);
-       BOP_meshClassify(meshC,facesB,&bspA);
-       
-       #ifdef BOP_DEBUG
-       c = chrono.stamp(); t += c;
-       std::cout << "Classification " << c << std::endl;
-       #endif
-       
-       // Process overlapped faces
-       BOP_removeOverlappedFaces(meshC,facesA,facesB);
-       
-       #ifdef BOP_DEBUG
-       c = chrono.stamp(); t += c;
-       std::cout << "Remove overlap " << c << std::endl;
-       #endif
-
-       // Sew two meshes
-       BOP_sew(meshC,facesA,facesB);
-
-       #ifdef BOP_DEBUG
-       c = chrono.stamp(); t += c;
-       std::cout << "Sew            " << c << std::endl;
-       #endif
-
-       // Merge faces
-#ifdef BOP_ORIG_MERGE
-#ifndef BOP_NEW_MERGE
-       BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
-#endif
-#endif
-
-#ifdef BOP_NEW_MERGE
-#ifndef BOP_ORIG_MERGE
-       BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
-#else
-       static int state = -1;
-       if (G.rt == 100) {
-               if( state != 1 ) {
-                       std::cout << "Boolean code using old merge technique." << std::endl;
-                       state = 1;
-               }
-               BOP_Merge::getInstance().mergeFaces(meshC,numVertices);
-       } else {
-               if( state != 0 ) {
-                       std::cout << "Boolean code using new merge technique." << std::endl;
-                       state = 0;
-               }
-               BOP_Merge2::getInstance().mergeFaces(meshC,numVertices);
-       }
-#endif
-#endif
-
-       #ifdef BOP_DEBUG
-       c = chrono.stamp(); t += c;
-       std::cout << "Merge faces    " << c << std::endl;
-       std::cout << "Total          " << t << std::endl;
-       // Test integrity
-       meshC->testMesh();
-       #endif
-       
-       return BOP_OK;
-}
-
-/**
- * Preprocess to filter no collisioned faces.
- * @param meshC Input & Output mesh data
- * @param faces Faces list to test
- * @param bsp BSP tree used to filter
- */
-void BOP_meshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
-{
-       BOP_IT_Faces it;
-       BOP_TAG tag;
-       
-       it = faces->begin();
-       while (it!=faces->end()) {
-               BOP_Face *face = *it;
-               MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
-               MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
-               MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
-               if ((tag = bsp->classifyFace(p1,p2,p3,face->getPlane()))==OUT||tag==OUTON) {
-                       face->setTAG(BROKEN);
-                       it = faces->erase(it);
-               }
-               else if (tag == IN) {
-                       it = faces->erase(it);
-               }else{
-                 it++;
-               }
-       }
-}
-
-/**
- * Pre-process to filter no collisioned faces.
- * @param meshC Input & Output mesh data
- * @param faces Faces list to test
- * @param bsp BSP tree used to filter
- * @param inverted determines if the object is inverted
- */
-void BOP_simplifiedMeshFilter(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp, bool inverted)
-{
-       BOP_IT_Faces it;
-       
-       it = faces->begin();
-       while (it!=faces->end()) {
-               BOP_Face *face = *it;
-               MT_Point3 p1 = meshC->getVertex(face->getVertex(0))->getPoint();
-               MT_Point3 p2 = meshC->getVertex(face->getVertex(1))->getPoint();
-               MT_Point3 p3 = meshC->getVertex(face->getVertex(2))->getPoint();
-               if (bsp->filterFace(p1,p2,p3,face)==OUT) {
-                       if (!inverted) face->setTAG(BROKEN);
-                       it = faces->erase(it);
-               }
-               else {
-                       it++;
-               }
-       }
-}
-
-/**
- * Process to classify the mesh faces using a bsp tree.
- * @param meshC Input & Output mesh data
- * @param faces Faces list to classify
- * @param bsp BSP tree used to face classify
- */
-void BOP_meshClassify(BOP_Mesh* meshC, BOP_Faces* faces, BOP_BSPTree* bsp)
-{
-       for(BOP_IT_Faces face=faces->begin();face!=faces->end();face++) {
-               if ((*face)->getTAG()!=BROKEN) {
-                       MT_Point3 p1 = meshC->getVertex((*face)->getVertex(0))->getPoint();
-                       MT_Point3 p2 = meshC->getVertex((*face)->getVertex(1))->getPoint();
-                       MT_Point3 p3 = meshC->getVertex((*face)->getVertex(2))->getPoint();
-                       if (bsp->simplifiedClassifyFace(p1,p2,p3,(*face)->getPlane())!=IN) {
-                               (*face)->setTAG(BROKEN);
-                       }
-               }
-       }
-}
-
-/**
- * Returns a new mesh triangle.
- * @param meshC Input & Output mesh data
- * @param vertex1 first vertex of the new face
- * @param vertex2 second vertex of the new face
- * @param vertex3 third vertex of the new face
- * @param origFace identifier of the new face
- * @return new the new face
- */
-BOP_Face3 *BOP_createFace3(BOP_Mesh* mesh, 
-                                                  BOP_Index       vertex1, 
-                                                  BOP_Index       vertex2, 
-                                                  BOP_Index       vertex3, 
-                                                  BOP_Index       origFace)
-{
-       MT_Point3 p1 = mesh->getVertex(vertex1)->getPoint();
-       MT_Point3 p2 = mesh->getVertex(vertex2)->getPoint();
-       MT_Point3 p3 = mesh->getVertex(vertex3)->getPoint();
-       MT_Plane3 plane(p1,p2,p3);
-
-       return new BOP_Face3(vertex1, vertex2, vertex3, plane, origFace);
-}
-
-/**
- * Adds mesh information into destination mesh.
- * @param mesh input/output mesh, destination for the new mesh data
- * @param meshFacesId output mesh faces, contains an added faces list
- * @param face_it faces iterator
- * @param vertex_it vertices iterator
- * @param inverted if TRUE adding inverted faces, non-inverted otherwise
- */
-void BOP_addMesh(BOP_Mesh*                     mesh,
-                                BOP_Faces*                    meshFacesId,
-                                CSG_FaceIteratorDescriptor&   face_it,
-                                CSG_VertexIteratorDescriptor& vertex_it,
-                                bool                          invert)
-{
-       unsigned int vtxIndexOffset = mesh->getNumVertexs();
-
-       // The size of the vertex data array will be at least the number of faces.
-       CSG_IVertex vertex;
-       while (!vertex_it.Done(vertex_it.it)) {
-               vertex_it.Fill(vertex_it.it,&vertex);
-               MT_Point3 pos(vertex.position);
-               mesh->addVertex(pos);
-               vertex_it.Step(vertex_it.it);
-       }
-
-       CSG_IFace face;
-       
-       // now for the polygons.
-       // we may need to decalare some memory for user defined face properties.
-
-       BOP_Face3 *newface;
-       
-       while (!face_it.Done(face_it.it)) {
-               face_it.Fill(face_it.it,&face);
-
-               // Let's not rely on quads being coplanar - especially if they 
-               // are coming out of that soup of code from blender...
-               if (face.vertex_number == 4){
-                       // QUAD
-                       if (invert) {
-                               newface = BOP_createFace3(mesh,
-                                                                                 face.vertex_index[2] + vtxIndexOffset,
-                                                                                 face.vertex_index[0] + vtxIndexOffset,
-                                                                                 face.vertex_index[3] + vtxIndexOffset,
-                                                                                 face.orig_face);
-                               meshFacesId->push_back(newface);
-                               mesh->addFace(newface);
-                               newface = BOP_createFace3(mesh,
-                                                                                 face.vertex_index[2] + vtxIndexOffset,
-                                                                                 face.vertex_index[1] + vtxIndexOffset,
-                                                                                 face.vertex_index[0] + vtxIndexOffset,
-                                                                                 face.orig_face);
-                               meshFacesId->push_back(newface);
-                               mesh->addFace(newface);
-                       }
-                       else {
-                               newface = BOP_createFace3(mesh,
-                                                                                face.vertex_index[0] + vtxIndexOffset,
-                                                                                face.vertex_index[2] + vtxIndexOffset,
-                                                                                face.vertex_index[3] + vtxIndexOffset,
-                                                                                face.orig_face);
-                               meshFacesId->push_back(newface);
-                               mesh->addFace(newface);
-                               newface = BOP_createFace3(mesh,
-                                                                                face.vertex_index[0] + vtxIndexOffset,
-                                                                                face.vertex_index[1] + vtxIndexOffset,
-                                                                                face.vertex_index[2] + vtxIndexOffset,
-                                                                                face.orig_face);
-                               meshFacesId->push_back(newface);
-                               mesh->addFace(newface);
-                       }
-               }
-               else {
-                       // TRIANGLES
-                       if (invert) {
-                               newface = BOP_createFace3(mesh,
-                                                                                 face.vertex_index[2] + vtxIndexOffset,
-                                                                                 face.vertex_index[1] + vtxIndexOffset,
-                                                                                 face.vertex_index[0] + vtxIndexOffset,
-                                                                                 face.orig_face);
-                               meshFacesId->push_back(newface);
-                               mesh->addFace(newface);
-                       }
-                       else {
-                               newface = BOP_createFace3(mesh,
-                                                                                 face.vertex_index[0] + vtxIndexOffset,
-                                                                                 face.vertex_index[1] + vtxIndexOffset,
-                                                                                 face.vertex_index[2] + vtxIndexOffset,
-                                                                                 face.orig_face);
-                               meshFacesId->push_back(newface);
-                               mesh->addFace(newface);
-                       }
-               }
-               
-               face_it.Step(face_it.it);
-       }
-}
-
-/**
- * Returns an empty mesh with the specified properties.
- * @return a new empty mesh
- */
-BSP_CSGMesh* BOP_newEmptyMesh()
-{
-       BSP_CSGMesh* mesh = BSP_CSGMesh::New();
-       if (mesh == NULL) return mesh;
-
-       std::vector<BSP_MVertex>* vertices = new std::vector<BSP_MVertex>;
-       
-       mesh->SetVertices(vertices);
-
-       return mesh;
-}
-
-/**
- * Exports a BOP_Mesh to a BSP_CSGMesh.
- * @param mesh Input mesh
- * @param invert if TRUE export with inverted faces, no inverted otherwise
- * @return the corresponding new BSP_CSGMesh
- */
-BSP_CSGMesh* BOP_exportMesh(BOP_Mesh*                  mesh, 
-                                                       bool                       invert)
-{
-       BSP_CSGMesh* outputMesh = BOP_newEmptyMesh();
-
-       if (outputMesh == NULL) return NULL;
-
-       // vtx index dictionary, to translate indeces from input to output.
-       std::map<int,unsigned int> dic;
-       std::map<int,unsigned int>::iterator itDic;
-
-       unsigned int count = 0;
-
-       // Add a new face for each face in the input list
-       BOP_Faces faces = mesh->getFaces();
-       BOP_Vertexs vertexs = mesh->getVertexs();
-
-       for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) {
-               if ((*face)->getTAG()!=BROKEN){    
-                       // Add output face
-                       outputMesh->FaceSet().push_back(BSP_MFace());
-                       BSP_MFace& outFace = outputMesh->FaceSet().back();
-
-                       // Copy face
-                       outFace.m_verts.clear();
-                       outFace.m_plane = (*face)->getPlane();
-                       outFace.m_orig_face = (*face)->getOriginalFace();
-
-                       // invert face if is required
-                       if (invert) (*face)->invert();
-                       
-                       // Add the face vertex if not added yet
-                       for (unsigned int pos=0;pos<(*face)->size();pos++) {
-                               BSP_VertexInd outVtxId;
-                               BOP_Index idVertex = (*face)->getVertex(pos);
-                               itDic = dic.find(idVertex);
-                               if (itDic == dic.end()) {
-                                       // The vertex isn't added yet
-                                       outVtxId = BSP_VertexInd(outputMesh->VertexSet().size());
-                                       BSP_MVertex outVtx((mesh->getVertex(idVertex))->getPoint());
-                                       outVtx.m_edges.clear();
-                                       outputMesh->VertexSet().push_back(outVtx);
-                                       dic[idVertex] = outVtxId;
-                                       count++;
-                               }
-                               else {
-                                       // The vertex is added
-                                       outVtxId = BSP_VertexInd(itDic->second);
-                               }
-
-                               outFace.m_verts.push_back(outVtxId);
-                       }
-               }
-       }
-       
-       // Build the mesh edges using topological informtion
-       outputMesh->BuildEdges();
-       
-       return outputMesh;
-}
diff --git a/intern/boolop/intern/BOP_MathUtils.cpp b/intern/boolop/intern/BOP_MathUtils.cpp
deleted file mode 100644 (file)
index 020de21..0000000
+++ /dev/null
@@ -1,471 +0,0 @@
-/*
- *
- *
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Marc Freixas, Ken Hughes
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_MathUtils.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_MathUtils.h"
-#include <iostream>
-
-/**
- * Compares two scalars with EPSILON accuracy.
- * @param A scalar
- * @param B scalar
- * @return 1 if A > B, -1 if A < B, 0 otherwise
- */
-int BOP_comp(const MT_Scalar A, const MT_Scalar B)
-{
-#ifndef VAR_EPSILON
-       if (A >= B + BOP_EPSILON) return 1;
-       else if (B >= A + BOP_EPSILON) return -1;
-       else return 0; 
-#else
-       int expA, expB;
-       float mant;
-       frexp(A, &expA);        /* get exponents of each number */
-       frexp(B, &expB);
-
-       if(expA < expB)         /* find the larger exponent */
-               expA = expB;
-       mant = frexp((A-B), &expB);     /* get exponent of the difference */
-       /* mantissa will only be zero is (A-B) is really zero; otherwise, also
-        * also allow a "reasonably" small exponent or "reasonably large"
-        * difference in exponents to be considers "close to zero" */
-       if( mant == 0 || expB < -30 || expA - expB > 31) return 0;
-       else if( mant > 0) return 1;
-       else return -1;
-#endif
-}
-
-/**
- * Compares a scalar with EPSILON accuracy.
- * @param A scalar
- * @return 1 if A > 0, -1 if A < 0, 0 otherwise
- */
-int BOP_comp0(const MT_Scalar A)
-{
-       if (A >= BOP_EPSILON) return 1;
-       else if (0 >= A + BOP_EPSILON) return -1;
-       else return 0; 
-}
-
-/**
- * Compares two scalar triplets with EPSILON accuracy.
- * @param A scalar triplet
- * @param B scalar triplet
- * @return 1 if A > B, -1 if A < B, 0 otherwise
- */
-int BOP_comp(const MT_Tuple3& A, const MT_Tuple3& B)
-{
-#ifndef VAR_EPSILON
-       if (A.x() >= (B.x() + BOP_EPSILON)) return 1;
-       else if (B.x() >= (A.x() + BOP_EPSILON)) return -1;
-       else if (A.y() >= (B.y() + BOP_EPSILON)) return 1;
-       else if (B.y() >= (A.y() + BOP_EPSILON)) return -1;
-       else if (A.z() >= (B.z() + BOP_EPSILON)) return 1;
-       else if (B.z() >= (A.z() + BOP_EPSILON)) return -1;
-       else return 0;
-#else
-       int result = BOP_comp(A.x(), B.x());
-       if (result != 0) return result;
-       result = BOP_comp(A.y(), B.y());
-       if (result != 0) return result;
-       return BOP_comp(A.z(), B.z());
-#endif
-}
-
-/**
- * Compares two scalars strictly.
- * @param A scalar
- * @param B scalar
- * @return 1 if A > B, -1 if A < B, 0 otherwise
- */
-int BOP_exactComp(const MT_Scalar A, const MT_Scalar B)
-{
-       if (A > B) return 1;
-       else if (B > A) return -1;
-       else return 0; 
-}
-/**
- * Compares two scalar strictly.
- * @param A scalar triplet
- * @param B scalar triplet
- * @return 1 if A > B, -1 if A < B, 0 otherwise
- */
-int BOP_exactComp(const MT_Tuple3& A, const MT_Tuple3& B)
-{
-       if (A.x() > B.x()) return 1;
-       else if (B.x() > A.x()) return -1;
-       else if (A.y() > B.y()) return 1;
-       else if (B.y() > A.y()) return -1;
-       else if (A.z() > B.z()) return 1;
-       else if (B.z() > A.z()) return -1;
-       else return 0;
-}
-
-/**
- * Returns if p1 is between p2 and p3 and lay on the same line (are collinears).
- * @param p1 point
- * @param p2 point
- * @param p3 point
- * @return true if p1 is between p2 and p3 and lay on the same line, false otherwise
- */
-bool BOP_between(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3)
-{
-       MT_Scalar distance = p2.distance(p3);
-       return (p1.distance(p2) < distance && p1.distance(p3) < distance) && BOP_collinear(p1,p2,p3);
-}
-
-/**
- * Returns if three points lay on the same line (are collinears).
- * @param p1 point
- * @param p2 point
- * @param p3 point
- * @return true if the three points lay on the same line, false otherwise
- */
-bool BOP_collinear(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3)
-{
-       if( BOP_comp(p1,p2) == 0 || BOP_comp(p2,p3) == 0 ) return true;
-
-       MT_Vector3 v1 = p2 - p1;
-       MT_Vector3 v2 = p3 - p2;
-
-       /* normalize vectors before taking their cross product, so its length 
-     * has some actual meaning */
-       // if(MT_fuzzyZero(v1.length()) || MT_fuzzyZero(v2.length())) return true;
-       v1.normalize(); 
-       v2.normalize();
-
-       MT_Vector3 w = v1.cross(v2);
-       
-       return (BOP_fuzzyZero(w.x()) && BOP_fuzzyZero(w.y()) && BOP_fuzzyZero(w.z()));
-}
-
-/**
- * Returns if a quad (coplanar) is convex.
- * @return true if the quad is convex, false otherwise
- */
-bool BOP_convex(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, const MT_Point3& p4)
-{
-       MT_Vector3 v1 = p3 - p1;
-       MT_Vector3 v2 = p4 - p2;
-       MT_Vector3 quadPlane = v1.cross(v2);
-       // plane1 is the perpendicular plane that contains the quad diagonal (p2,p4)
-       MT_Plane3 plane1(quadPlane.cross(v2),p2);
-       // if p1 and p3 are classified in the same region, the quad is not convex 
-       if (BOP_classify(p1,plane1) == BOP_classify(p3,plane1)) return false;
-       else {
-               // Test the other quad diagonal (p1,p3) and perpendicular plane
-               MT_Plane3 plane2(quadPlane.cross(v1),p1);
-               // if p2 and p4 are classified in the same region, the quad is not convex
-               return (BOP_classify(p2,plane2) != BOP_classify(p4,plane2));
-       }
-}
-
-/**
- * Returns if a quad (coplanar) is concave and where is the split edge.
- * @return 0 if is convex, 1 if is concave and split edge is p1-p3 and -1 if is
- * cancave and split edge is p2-p4.
- */
-int BOP_concave(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, const MT_Point3& p4)
-{
-       MT_Vector3 v1 = p3 - p1;
-       MT_Vector3 v2 = p4 - p2;
-       MT_Vector3 quadPlane = v1.cross(v2);
-       // plane1 is the perpendicular plane that contains the quad diagonal (p2,p4)
-       MT_Plane3 plane1(quadPlane.cross(v2),p2);
-       // if p1 and p3 are classified in the same region, the quad is not convex 
-       if (BOP_classify(p1,plane1) == BOP_classify(p3,plane1)) return 1;
-       else {
-               // Test the other quad diagonal (p1,p3) and perpendicular plane
-               MT_Plane3 plane2(quadPlane.cross(v1),p1);
-               // if p2 and p4 are classified in the same region, the quad is not convex
-               if (BOP_classify(p2,plane2) == BOP_classify(p4,plane2)) return -1;
-               else return 0;
-       }
-}
-
-/**
- * Computes the intersection between two lines (on the same plane).
- * @param vL1 first line vector
- * @param pL1 first line point
- * @param vL2 second line vector
- * @param pL2 second line point
- * @param intersection intersection point (if exists)
- * @return false if lines are parallels, true otherwise
- */
-bool BOP_intersect(const MT_Vector3& vL1, const MT_Point3& pL1, const MT_Vector3& vL2, 
-                                  const MT_Point3& pL2, MT_Point3 &intersection)
-{
-       // NOTE: 
-    // If the lines aren't on the same plane, the intersection point will not be valid. 
-       // So be careful !!
-
-       MT_Scalar t = -1;
-       MT_Scalar den = (vL1.y()*vL2.x() - vL1.x() * vL2.y());
-       
-       if (!BOP_fuzzyZero(den)) {
-               t =  (pL2.y()*vL1.x() - vL1.y()*pL2.x() + pL1.x()*vL1.y() - pL1.y()*vL1.x()) / den;
-       }
-       else {
-               den = (vL1.y()*vL2.z() - vL1.z() * vL2.y());
-               if (!BOP_fuzzyZero(den)) {
-                       t =  (pL2.y()*vL1.z() - vL1.y()*pL2.z() + pL1.z()*vL1.y() - pL1.y()*vL1.z()) / den;
-               }
-               else {
-                       den = (vL1.x()*vL2.z() - vL1.z() * vL2.x());
-                       if (!BOP_fuzzyZero(den)) {
-                               t =  (pL2.x()*vL1.z() - vL1.x()*pL2.z() + pL1.z()*vL1.x() - pL1.x()*vL1.z()) / den;
-                       }
-                       else {
-                               return false;
-                       }
-               }
-       }
-       
-       intersection.setValue(vL2.x()*t + pL2.x(), vL2.y()*t + pL2.y(), vL2.z()*t + pL2.z());
-       return true;
-}
-
-/**
- * Returns the center of the circle defined by three points.
- * @param p1 point
- * @param p2 point
- * @param p3 point
- * @param center circle center
- * @return false if points are collinears, true otherwise
- */
-bool BOP_getCircleCenter(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, 
-                                                MT_Point3& center)
-{
-       // Compute quad plane
-       MT_Vector3 p1p2 = p2-p1;
-       MT_Vector3 p1p3 = p3-p1;
-       MT_Plane3 plane1(p1,p2,p3);
-       MT_Vector3 plane = plane1.Normal();
-       
-       // Compute first line vector, perpendicular to plane vector and edge (p1,p2)
-       MT_Vector3 vL1 = p1p2.cross(plane);
-       if( MT_fuzzyZero(vL1.length() ) )
-                       return false;
-       vL1.normalize();
-       
-       // Compute first line point, middle point of edge (p1,p2)
-       MT_Point3 pL1 = p1.lerp(p2, 0.5);
-
-       // Compute second line vector, perpendicular to plane vector and edge (p1,p3)
-       MT_Vector3 vL2 = p1p3.cross(plane);
-       if( MT_fuzzyZero(vL2.length() ) )
-                       return false;
-       vL2.normalize();
-       
-       // Compute second line point, middle point of edge (p1,p3)
-       MT_Point3 pL2 = p1.lerp(p3, 0.5);
-
-       // Compute intersection (the lines lay on the same plane, so the intersection exists
-    // only if they are not parallel!!)
-       return BOP_intersect(vL1,pL1,vL2,pL2,center);
-}
-
-/**
- * Returns if points q is inside the circle defined by p1, p2 and p3.
- * @param p1 point
- * @param p2 point
- * @param p3 point
- * @param q point
- * @return true if p4 or p5 are inside the circle, false otherwise. If 
- * the circle does not exist (p1, p2 and p3 are collinears) returns true
- */
-bool BOP_isInsideCircle(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, 
-                                               const MT_Point3& q)
-{
-       MT_Point3 center;
-
-       // Compute circle center
-       bool ok = BOP_getCircleCenter(p1,p2,p3,center);
-       
-       if (!ok) return true; // p1,p2 and p3 are collinears
-
-       // Check if q is inside the circle
-       MT_Scalar r = p1.distance(center);
-       MT_Scalar d = q.distance(center);    
-       return (BOP_comp(d,r) <= 0);
-}
-
-/**
- * Returns if points p4 or p5 is inside the circle defined by p1, p2 and p3.
- * @param p1 point
- * @param p2 point
- * @param p3 point
- * @param p4 point
- * @param p5 point
- * @return true if p4 or p5 is inside the circle, false otherwise. If 
- * the circle does not exist (p1, p2 and p3 are collinears) returns true
- */
-bool BOP_isInsideCircle(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, 
-                                               const MT_Point3& p4, const MT_Point3& p5)
-{
-       MT_Point3 center;
-       bool ok = BOP_getCircleCenter(p1,p2,p3,center);
-
-       if (!ok) return true; // Collinear points!
-
-       // Check if p4 or p5 is inside the circle
-       MT_Scalar r = p1.distance(center);
-       MT_Scalar d1 = p4.distance(center);
-       MT_Scalar d2 = p5.distance(center);
-       return (BOP_comp(d1,r) <= 0 || BOP_comp(d2,r) <= 0);
-}
-
-/**
- * Returns if two planes share the same orientation.
- * @return >0 if planes share the same orientation
- */
-MT_Scalar BOP_orientation(const MT_Plane3& p1, const MT_Plane3& p2)
-{
-       // Dot product between plane normals
-       return (p1.x()*p2.x() + p1.y()*p2.y() + p1.z()*p2.z());
-}
-
-/**
- * Classifies a point according to the specified plane with EPSILON accuracy.
- * @param p point
- * @param plane plane
- * @return >0 if the point is above (OUT), 
- *         =0 if the point is on (ON), 
- *         <0 if the point is below (IN)
- */
-int BOP_classify(const MT_Point3& p, const MT_Plane3& plane)
-{
-       // Compare plane - point distance with zero
-       return BOP_comp0(plane.signedDistance(p));
-}
-
-/**
- * Intersects a plane with the line that contains the specified points.
- * @param plane split plane
- * @param p1 first line point
- * @param p2 second line point
- * @return intersection between plane and line that contains p1 and p2
- */
-MT_Point3 BOP_intersectPlane(const MT_Plane3& plane, const MT_Point3& p1, const MT_Point3& p2)
-{
-       // Compute intersection between plane and line ...
-    //
-       //       L: (p2-p1)lambda + p1
-       //
-       // supposes resolve equation ...
-       //
-       //       coefA*((p2.x - p1.y)*lambda + p1.x) + ... + coefD = 0
-       
-    MT_Point3 intersection = MT_Point3(0,0,0); //never ever return anything undefined! 
-    MT_Scalar den = plane.x()*(p2.x()-p1.x()) + 
-                                       plane.y()*(p2.y()-p1.y()) + 
-                                       plane.z()*(p2.z()-p1.z());
-       if (den != 0) {
-               MT_Scalar lambda = (-plane.x()*p1.x()-plane.y()*p1.y()-plane.z()*p1.z()-plane.w()) / den;
-               intersection.setValue(p1.x() + (p2.x()-p1.x())*lambda, 
-                                                 p1.y() + (p2.y()-p1.y())*lambda, 
-                                                 p1.z() + (p2.z()-p1.z())*lambda);
-               return intersection;
-       }
-       return intersection;
-}
-
-/**
- * Returns if a plane contains a point with EPSILON accuracy.
- * @param plane plane
- * @param point point
- * @return true if the point is on the plane, false otherwise
- */
-bool BOP_containsPoint(const MT_Plane3& plane, const MT_Point3& point)
-{
-       return BOP_fuzzyZero(plane.signedDistance(point));
-}
-
-/**
- * Pre: p0, p1 and p2 is a triangle and q is an interior point.
- * @param p0 point
- * @param p1 point
- * @param p2 point
- * @param q point
- * @return intersection point I
- *                v 
- *  (p0)-----(I)----->(p1)
- *    \       ^        /
- *     \      |w      /
- *      \     |      /
- *       \   (q)    /
- *        \   |    /
- *         \  |   /
- *          \ |  /
- *           (p2)
- *
- * v = P1-P2
- * w = P3-Q
- * r0(t) = v*t+P1
- * r1(t) = w*t+P3
- * I = r0^r1
- */
-MT_Point3 BOP_4PointIntersect(const MT_Point3& p0, const MT_Point3& p1, const MT_Point3& p2, 
-                                                         const MT_Point3& q)
-{
-       MT_Vector3 v(p0.x()-p1.x(), p0.y()-p1.y(), p0.z()-p1.z());
-       MT_Vector3 w(p2.x()-q.x(), p2.y()-q.y(), p2.z()-q.z());
-       MT_Point3 I;
-       
-       BOP_intersect(v,p0,w,p2,I);
-       return I;
-}
-
-/**
- * Pre: p0, p1 and q are collinears.
- * @param p0 point
- * @param p1 point
- * @param q point
- * @return 0 if q == p0, 1 if q == p1, or a value between 0 and 1 otherwise
- *
- * (p0)-----(q)------------(p1)
- *   |<-d1-->|               |
- *   |<---------d0---------->|
- * 
- */
-MT_Scalar BOP_EpsilonDistance(const MT_Point3& p0, const MT_Point3& p1, const MT_Point3& q)
-{
-       MT_Scalar d0 = p0.distance(p1);
-       MT_Scalar d1 = p0.distance(q);
-       MT_Scalar d;
-       
-       if (BOP_fuzzyZero(d0)) d = 1.0;
-       else if (BOP_fuzzyZero(d1)) d = 0.0;
-       else d = d1 / d0;
-       return d;
-}
diff --git a/intern/boolop/intern/BOP_MathUtils.h b/intern/boolop/intern/BOP_MathUtils.h
deleted file mode 100644 (file)
index 38acd98..0000000
+++ /dev/null
@@ -1,83 +0,0 @@
-/*
- *
- *
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Marc Freixas, Ken Hughes
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_MathUtils.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_MATHUTILS_H__
-#define __BOP_MATHUTILS_H__
-
-#include <math.h>
-#include <float.h>
-#include "MT_Point3.h"
-#include "MT_Plane3.h"
-
-/* define this to give better precision comparisons */
-#define VAR_EPSILON
-
-#ifndef VAR_EPSILON
-const MT_Scalar BOP_EPSILON(1.0e-5);
-#else
-const MT_Scalar BOP_EPSILON(9.3132257461547852e-10);   /* ~= 2**-30 */
-#endif
-
-inline int BOP_sign(MT_Scalar x) {
-    return x < 0.0 ? -1 : x > 0.0 ? 1 : 0;
-}
-inline MT_Scalar BOP_abs(MT_Scalar x) { return fabs(x); }
-int BOP_comp(const MT_Scalar A, const MT_Scalar B);
-int BOP_comp(const MT_Tuple3& A, const MT_Tuple3& B);
-int BOP_comp0(const MT_Scalar A);
-inline bool BOP_fuzzyZero(MT_Scalar x) { return BOP_comp0(x) == 0; }
-int BOP_exactComp(const MT_Scalar A, const MT_Scalar B);
-int BOP_exactComp(const MT_Tuple3& A, const MT_Tuple3& B);
-bool BOP_between(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3);
-bool BOP_collinear(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3);
-bool BOP_convex(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, 
-                               const MT_Point3& p4);
-int BOP_concave(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, const MT_Point3& p4);
-bool BOP_intersect(const MT_Vector3& vL1, const MT_Point3& pL1, const MT_Vector3& vL2, 
-                                  const MT_Point3& pL2, MT_Point3& intersection);
-bool BOP_getCircleCenter(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, 
-                                                const MT_Point3& center);
-bool BOP_isInsideCircle(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, 
-                                               const MT_Point3& p4, const MT_Point3& p5);
-bool BOP_isInsideCircle(const MT_Point3& p1, const MT_Point3& p2, const MT_Point3& p3, 
-                                               const MT_Point3& q);
-MT_Scalar BOP_orientation(const MT_Plane3& p1, const MT_Plane3& p2);
-int BOP_classify(const MT_Point3& p, const MT_Plane3& plane);
-MT_Point3 BOP_intersectPlane(const MT_Plane3& plane, const MT_Point3& p1, const MT_Point3& p2);
-bool BOP_containsPoint(const MT_Plane3& plane, const MT_Point3& point);
-MT_Point3 BOP_4PointIntersect(const MT_Point3& p0, const MT_Point3& p1, const MT_Point3& p2, 
-                                                         const MT_Point3& q);
-MT_Scalar BOP_EpsilonDistance(const MT_Point3& p0, const MT_Point3& p1, const MT_Point3& q);
-
-#endif
diff --git a/intern/boolop/intern/BOP_Merge.cpp b/intern/boolop/intern/BOP_Merge.cpp
deleted file mode 100644 (file)
index 0baa6e7..0000000
+++ /dev/null
@@ -1,811 +0,0 @@
-/*
- *
- *
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Marc Freixas, Ken Hughes
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Merge.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_Merge.h"
-
-#ifdef BOP_ORIG_MERGE
-
-#ifdef _MSC_VER
-#if _MSC_VER < 1300
-#include <list>
-#endif
-#endif
-
-/**
- * SINGLETON (use method BOP_Merge.getInstance).
- */
-BOP_Merge BOP_Merge::SINGLETON;
-
-/**
- * Simplifies a mesh, merging its faces.
- * @param m mesh
- * @param v index of the first mergeable vertex (can be removed by merge) 
- */
-void BOP_Merge::mergeFaces(BOP_Mesh *m, BOP_Index v)
-{
-       m_mesh = m;
-       m_firstVertex = v;
-
-       bool cont = false;
-
-       // Merge faces
-       mergeFaces();
-
-       do {
-               // Add quads ...
-               cont = createQuads();
-               if (cont) {
-                       // ... and merge new faces
-                       cont = mergeFaces();
-               }
-               // ... until the merge is not succesful
-       } while(cont);
-}
-
-/**
- * Simplifies a mesh, merging its faces.
- */
-bool BOP_Merge::mergeFaces()
-{
-       BOP_Indexs mergeVertices;
-       BOP_Vertexs vertices = m_mesh->getVertexs();
-       BOP_IT_Vertexs v = vertices.begin();
-       const BOP_IT_Vertexs verticesEnd = vertices.end();
-
-       // Advance to first mergeable vertex
-       advance(v,m_firstVertex);
-       BOP_Index pos = m_firstVertex;
-
-       // Add unbroken vertices to the list
-       while(v!=verticesEnd) {
-               if ((*v)->getTAG() != BROKEN) mergeVertices.push_back(pos);
-               v++;pos++;
-       }
-
-       // Merge faces with that vertices
-       return mergeFaces(mergeVertices);
-}
-
-
-/**
- * Simplifies a mesh, merging the faces with the specified vertices.
- * @param mergeVertices vertices to test
- * @return true if a face merge was performed
- */
-bool BOP_Merge::mergeFaces(BOP_Indexs &mergeVertices)
-{
-       // Check size > 0!
-       if (mergeVertices.size() == 0) return false;
-
-       // New faces added by merge
-       BOP_Faces newFaces;
-
-       // Old faces removed by merge
-       BOP_Faces oldFaces;
-
-       // Get the first vertex index and add it to 
-       // the current pending vertices to merge
-       BOP_Index v = mergeVertices[0];
-       BOP_Indexs pendingVertices;
-       pendingVertices.push_back(v);
-
-       // Get faces with index v that come from the same original face
-       BOP_LFaces facesByOriginalFace;
-       getFaces(facesByOriginalFace,v);
-
-       bool merged = true;
-
-       // Check it has any unbroken face
-       if (facesByOriginalFace.size()==0) {
-               // v has not any unbroken face (so it's a new BROKEN vertex)
-               (m_mesh->getVertex(v))->setTAG(BROKEN);
-               merged = false;
-       }
-
-       // Merge vertex faces   
-       const BOP_IT_LFaces facesEnd = facesByOriginalFace.end();
-       
-       for(BOP_IT_LFaces facesByOriginalFaceX = facesByOriginalFace.begin();
-               (facesByOriginalFaceX != facesEnd)&&merged;
-               facesByOriginalFaceX++) {               
-                       merged = mergeFaces((*facesByOriginalFaceX),oldFaces,newFaces,pendingVertices,v);
-       }
-
-       // Check if the are some pendingVertices to merge
-       if (pendingVertices.size() > 1 && merged) {
-               // There are pending vertices that we need to merge in order to merge v ...
-               for(unsigned int i=1;i<pendingVertices.size() && merged;i++) 
-                       merged = mergeFaces(oldFaces,newFaces,pendingVertices,pendingVertices[i]);
-       }
-
-       // If merge was succesful ...
-       if (merged) {
-               // Set old faces to BROKEN...
-         const BOP_IT_Faces oldFacesEnd = oldFaces.end();
-               for(BOP_IT_Faces face=oldFaces.begin();face!=oldFacesEnd;face++) 
-                       (*face)->setTAG(BROKEN);
-
-               // ... and add merged faces (that are the new merged faces without pending vertices)
-               const BOP_IT_Faces newFacesEnd = newFaces.end();
-               for(BOP_IT_Faces newFace=newFaces.begin();newFace!=newFacesEnd;newFace++) {
-                       m_mesh->addFace(*newFace);
-                       // Also, add new face vertices to the queue of vertices to merge if they weren't
-                       for(BOP_Index i = 0;i<(*newFace)->size();i++) {
-                               BOP_Index vertexIndex = (*newFace)->getVertex(i);
-                               if (vertexIndex >= m_firstVertex && !containsIndex(mergeVertices,vertexIndex))
-                                       mergeVertices.push_back(vertexIndex);
-                       }
-               }
-               // Set the merged vertices to BROKEN ...
-               const BOP_IT_Indexs pendingEnd = pendingVertices.end();
-               for(BOP_IT_Indexs pendingVertex = pendingVertices.begin(); pendingVertex != pendingEnd;pendingVertex++) {
-                       BOP_Index pV = *pendingVertex;
-                       m_mesh->getVertex(pV)->setTAG(BROKEN);
-                       // ... and remove them from mergeVertices queue
-                       const BOP_IT_Indexs mergeEnd = mergeVertices.end();
-                       for(BOP_IT_Indexs mergeVertex = mergeVertices.begin(); mergeVertex != mergeEnd;mergeVertex++) {
-                               BOP_Index mV = *mergeVertex;
-                               if (mV == pV) {
-                                       mergeVertices.erase(mergeVertex);
-                                       break;
-                               }
-                       }
-               }
-       }
-       else {
-               // The merge  was not succesful, remove the vertex frome merge vertices queue
-               mergeVertices.erase(mergeVertices.begin());
-               
-               // free the not used newfaces
-               const BOP_IT_Faces newFacesEnd = newFaces.end();
-               for(BOP_IT_Faces newFace=newFaces.begin();newFace!=newFacesEnd;newFace++) {
-                       delete (*newFace);
-               }
-       }
-
-       // Invoke mergeFaces and return the merge result
-       return (mergeFaces(mergeVertices) || merged);
-}
-
-
-/**
- * Simplifies a mesh, merging the faces with vertex v that come from the same face.
- * @param oldFaces sequence of old mesh faces obtained from the merge
- * @param newFaces sequence of new mesh faces obtained from the merge
- * @param vertices sequence of indexs (v1 ... vi = v ... vn) where :
- *   v is the current vertex to test,
- *   vj (j < i) are tested vertices, 
- *   vk (k >= i) are vertices required to test to merge vj
- * (so if a vertex vk can't be merged, the merge is not possible).
- * @return true if the vertex v was 'merged' (obviously it could require to test
- * some new vertices that will be added to the vertices list)
- */
-bool BOP_Merge::mergeFaces(BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v) {
-
-       bool merged = true;
-
-       // Get faces with v that come from the same original face, (without the already 'merged' from vertices)
-       BOP_LFaces facesByOriginalFace;
-       getFaces(facesByOriginalFace,vertices,v);
-  
-       if (facesByOriginalFace.size()==0) {
-               // All the faces with this vertex were already merged!!!
-               return true;
-       }
-       else {
-               // Merge faces
-         const BOP_IT_LFaces facesEnd = facesByOriginalFace.end();
-               for(BOP_IT_LFaces facesByOriginalFaceX = facesByOriginalFace.begin();
-                       (facesByOriginalFaceX != facesEnd)&&merged;
-                       facesByOriginalFaceX++) {
-                               merged = mergeFaces((*facesByOriginalFaceX),oldFaces,newFaces,vertices,v);
-               }
-       }
-       return merged;
-}
-
-
-/**
- * Merge a set of faces removing the vertex index v.
- * @param faces set of faces
- * @param oldFaces set of old faces obtained from the merge
- * @param newFaces set of new faces obtained from the merge
- * @param vertices sequence of indexs (v1 ... vi = v ... vn) where :
- *   v is the current vertex to test,
- *   vj (j < i) are tested vertices, 
- *   vk (k >= i) are vertices required to test to merge vj
- * (so if a vertex vk can't be merged, the merge is not possible).
- * @param v vertex index
- * @return true if the merge is succesful, false otherwise
- */
-bool BOP_Merge::mergeFaces(BOP_Faces &faces, BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v)
-{
-
-       bool merged = false;
-
-       if (faces.size() == 2) {
-               // Merge a pair of faces into a new face without v
-               BOP_Face *faceI = faces[0];
-               BOP_Face *faceJ = faces[1];
-               BOP_Face *faceK = mergeFaces(faceI,faceJ,vertices,v);
-               if (faceK != NULL) {
-                       newFaces.push_back(faceK);
-                       oldFaces.push_back(faceI);
-                       oldFaces.push_back(faceJ);
-                       merged = true;
-               } 
-               else merged = false;
-       }
-       else if (faces.size() == 4) {
-               // Merge two pair of faces into a new pair without v
-               // First we try to perform a simplify merge to avoid more pending vertices
-               // (for example, if we have two triangles and two quads it will be better
-               // to do 3+4 and 3+4 than 3+3 and 4+4)
-               BOP_Face *oldFace1 = faces[0];
-               BOP_Face *oldFace2, *newFace1;
-               unsigned int indexJ = 1;
-               while (indexJ < faces.size() && !merged) {
-                       oldFace2 = faces[indexJ];
-                       newFace1 = mergeFaces(oldFace1,oldFace2,v);
-                       if (newFace1 != NULL) merged = true;
-                       else indexJ++;
-               }
-               if (merged) {
-                       // Merge the other pair of faces 
-                       unsigned int indexK, indexL;
-                       if (indexJ == 1) {indexK = 2;indexL = 3;}
-                       else if (indexJ == 2) {indexK = 1;indexL = 3;}
-                       else {indexK = 1;indexL = 2;}
-                       BOP_Face *oldFace3 = faces[indexK];
-                       BOP_Face *oldFace4 = faces[indexL];
-                       unsigned int oldSize = vertices.size();
-                       BOP_Face *newFace2 = mergeFaces(oldFace3,oldFace4,vertices,v);
-                       if (newFace2 != NULL) {
-                               newFaces.push_back(newFace1);
-                               newFaces.push_back(newFace2);
-                               oldFaces.push_back(oldFace1);
-                               oldFaces.push_back(oldFace2);
-                               oldFaces.push_back(oldFace3);
-                               oldFaces.push_back(oldFace4);
-                               merged = true;
-                       }
-                       else {
-                               // Undo all changes
-                               delete newFace1;
-                               merged = false;
-                               unsigned int count = vertices.size() - oldSize;
-                               if (count != 0)
-                                       vertices.erase(vertices.end() - count, vertices.end());
-                       }
-               }               
-               if (!merged) {
-                       // Try a complete merge
-                       merged = true;
-                       while (faces.size()>0 && merged) {
-                               indexJ = 1;
-                               BOP_Face *faceI = faces[0];
-                               merged = false;
-                               while (indexJ < faces.size()) {
-                                       BOP_Face *faceJ = faces[indexJ];
-                                       BOP_Face *faceK = mergeFaces(faceI,faceJ,vertices,v);
-                                       if (faceK != NULL) {
-                                               // faceK = faceI + faceJ and it does not include v!
-                                               faces.erase(faces.begin()+indexJ,faces.begin()+(indexJ+1));
-                                               faces.erase(faces.begin(),faces.begin()+1);
-                                               newFaces.push_back(faceK);
-                                               oldFaces.push_back(faceI);
-                                               oldFaces.push_back(faceJ);
-                                               merged = true;
-                                               break;
-                                       }
-                                       else indexJ++;
-                               }
-                       }
-               }
-       }
-       else merged = false; // there are N=1 or N=3 or N>4 faces!
-
-       // Return merge result
-       return merged;
-}
-
-/**
- * Returns a new quad from the merge of two faces (one quad and one triangle) 
- * that share the vertex v and come from the same original face.
- * @param faceI mesh face (quad or triangle) with index v
- * @param faceJ mesh face (quad or triangle) with index v
- * @param v vertex index shared by both faces
- * @return if the merge is possible, a new quad without v
- */
-BOP_Face* BOP_Merge::mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v)
-{
-       if (faceI->size() == 3) {
-               if (faceJ->size() == 4)
-                       return mergeFaces((BOP_Face4*)faceJ,(BOP_Face3*)faceI,v);
-       }
-       else if (faceI->size() == 4) {
-               if (faceJ->size() == 3)
-                       return mergeFaces((BOP_Face4*)faceI,(BOP_Face3*)faceJ,v);
-       }
-       return NULL;
-}
-
-/**
- * Returns a new face from the merge of two faces (quads or triangles) that
- * share te vertex v and come from the same original face.
- * @param faceI mesh face (quad or triangle) with index v
- * @param faceJ mesh face (quad or triangle) with index v
- * @param pending vector with pending vertices (required to merge two quads into 
- * a new quad or one quad and one triangle into a new triangle; these merges 
- * suppose to remove two vertexs, v and its neighbour, that will be a pending 
- * vertex to merge if it wasn't)
- * @param v vertex index shared by both faces
- * @return if the merge is possible, a new face without v
- */
-BOP_Face* BOP_Merge::mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Indexs &pending, BOP_Index v)
-{
-       if (faceI->size() == 3) {
-               if (faceJ->size() == 3)
-                       return mergeFaces((BOP_Face3*)faceI,(BOP_Face3*)faceJ,v);
-               else if (faceJ->size() == 4)
-                       return mergeFaces((BOP_Face4*)faceJ,(BOP_Face3*)faceI,pending,v);
-       }
-       else if (faceI->size() == 4) {
-               if (faceJ->size() == 3)
-                       return mergeFaces((BOP_Face4*)faceI,(BOP_Face3*)faceJ,pending,v);
-               else if (faceJ->size() == 4)
-                       return mergeFaces((BOP_Face4*)faceI,(BOP_Face4*)faceJ,pending,v);
-       }
-       return NULL;
-}
-
-/** 
- * Returns a new triangle from the merge of two triangles that share the vertex
- * v and come from the same original face.
- * @param faceI mesh triangle
- * @param faceJ mesh triangle
- * @param v vertex index shared by both triangles
- * @return If the merge is possible, a new triangle without v
- */
-BOP_Face* BOP_Merge::mergeFaces(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v)
-{
-       BOP_Face *faceK = NULL;
-
-       // Get faces data
-       BOP_Index prevI, nextI, prevJ, nextJ;   
-       faceI->getNeighbours(v,prevI,nextI);
-       faceJ->getNeighbours(v,prevJ,nextJ);
-       MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
-       MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
-       MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
-       MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
-       MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
-
-       // Merge test
-       if (prevI == nextJ) {
-               // Both faces share the edge (prevI,v) == (v,nextJ)
-               if (BOP_between(vertex,vNextI,vPrevJ)) {
-                       faceK = new BOP_Face3(prevI,prevJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-               }
-       }
-       else if (nextI == prevJ) {
-               // Both faces share the edge (v,nextI) == (prevJ,v)
-               if (BOP_between(vertex,vPrevI,vNextJ)) {
-                       faceK = new BOP_Face3(prevI,nextJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-               }
-       }
-       return faceK;
-}
-
-/** 
- * Returns a new quad from the merge of one quad and one triangle that share 
- * the vertex v and come from the same original face.
- * @param faceI mesh quad
- * @param faceJ mesh triangle
- * @param v vertex index shared by both faces
- * @return If the merge is possible, a new quad without v
- */
-BOP_Face* BOP_Merge::mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Index v)
-{
-       BOP_Face *faceK = NULL;
-
-       // Get faces data
-       BOP_Index prevI, nextI, opp, prevJ, nextJ;
-       faceI->getNeighbours(v,prevI,nextI,opp);
-       faceJ->getNeighbours(v,prevJ,nextJ);
-       MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
-       MT_Point3 vOpp = m_mesh->getVertex(opp)->getPoint();
-       MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
-       MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
-       MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
-       MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
-
-       // Merge test
-       if (prevI == nextJ) {
-               if (BOP_between(vertex,vNextI,vPrevJ) && !BOP_collinear(vPrevJ,vPrevI,vOpp)
-                       && BOP_convex(vOpp,vPrevI,vPrevJ,vNextI)) {
-                       faceK = new BOP_Face4(opp,prevI,prevJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-               }
-       }
-       else if (nextI == prevJ) {
-               if (BOP_between(vertex,vPrevI,vNextJ) && !BOP_collinear(vNextJ,vNextI,vOpp)
-                       && BOP_convex(vOpp,vPrevI,vNextJ,vNextI)) {
-                       faceK = new BOP_Face4(opp,prevI,nextJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-               }
-       }
-       return faceK;
-}
-
-/** 
- * Returns a new face (quad or triangle) from the merge of one quad and one 
- * triangle that share the vertex v and come from the same original face.
- * @param faceI mesh quad
- * @param faceJ mesh triangle
- * @param pending vector with pending vertices (required to merge one quad 
- * and one triangle into a new triangle; it supposes to remove two vertexs,
- * v and its neighbour, that will be a new pending vertex if it wasn't)
- * @param v vertex index shared by both faces
- * @return If the merge is possible, a new face without v
- */
-BOP_Face* BOP_Merge::mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Indexs &pending, BOP_Index v)
-{
-       BOP_Face *faceK = NULL;
-
-       // Get faces data
-       BOP_Index prevI, nextI, opp, prevJ, nextJ;
-       faceI->getNeighbours(v,prevI,nextI,opp);
-       faceJ->getNeighbours(v,prevJ,nextJ);
-       MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
-       MT_Point3 vOpp = m_mesh->getVertex(opp)->getPoint();
-       MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
-       MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
-       MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
-       MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
-
-       // Merge test
-       if (prevI == nextJ) {
-               if (BOP_between(vertex,vNextI,vPrevJ)) {
-                       if (!BOP_collinear(vPrevJ,vPrevI,vOpp) && BOP_convex(vOpp,vPrevI,vPrevJ,vNextI)) {
-                               // The result is a new quad
-                               faceK = new BOP_Face4(opp,prevI,prevJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-                       }
-                       else if (BOP_between(vPrevI,vPrevJ,vOpp)) {
-                               // The result is a triangle (only if prevI can be merged)
-                               if (prevI < m_firstVertex) return NULL; // It can't be merged
-                               faceK = new BOP_Face3(nextI,opp,prevJ,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-                               if (!containsIndex(pending, prevI)) pending.push_back(prevI);
-                       }
-               }
-       }
-       else if (nextI == prevJ) {
-               if (BOP_between(vertex,vPrevI,vNextJ)) {
-                       if (!BOP_collinear(vNextJ,vNextI,vOpp) && BOP_convex(vOpp,vPrevI,vNextJ,vNextI)) {
-                               // The result is a new quad
-                               faceK = new BOP_Face4(opp,prevI,nextJ,nextI,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-                       }
-                       else if (BOP_between(vNextI,vOpp,vNextJ)) {
-                               // The result is a triangle (only if nextI can be merged)
-                               if (nextI < m_firstVertex) return NULL;
-                               faceK = new BOP_Face3(prevI,nextJ,opp,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-                               if (!containsIndex(pending, nextI)) pending.push_back(nextI);
-                       }
-               }
-       }
-       return faceK;
-}
-
-/** 
- * Returns a new quad from the merge of two quads that share 
- * the vertex v and come from the same original face.
- * @param faceI mesh quad
- * @param faceJ mesh quad
- * @param pending vector with pending vertices (required to merge the two
- * quads supposes to remove two vertexs, v and its neighbour, 
- * that will be a new pending vertex if it wasn't)
- * @param v vertex index shared by both quads
- * @return If the merge is possible, a new quad without v
- */
-BOP_Face* BOP_Merge::mergeFaces(BOP_Face4 *faceI, BOP_Face4 *faceJ, BOP_Indexs &pending, BOP_Index v)
-{
-       BOP_Face *faceK = NULL;
-
-       // Get faces data
-       BOP_Index prevI, nextI, oppI, prevJ, nextJ, oppJ;
-       faceI->getNeighbours(v,prevI,nextI,oppI);
-       faceJ->getNeighbours(v,prevJ,nextJ,oppJ);
-       MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
-       MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
-       MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
-       MT_Point3 vOppI = m_mesh->getVertex(oppI)->getPoint();
-       MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
-       MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
-       MT_Point3 vOppJ = m_mesh->getVertex(oppJ)->getPoint();
-
-       // Merge test
-       if (prevI == nextJ) {
-               // prevI/nextJ will be a new vertex required to merge
-               if (prevI < m_firstVertex) return NULL; // It can't be merged
-               if (BOP_between(vertex,vPrevJ,vNextI) && BOP_between(vNextJ,vOppJ,vOppI)) {
-                       faceK = new BOP_Face4(oppJ,prevJ,nextI,oppI,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-                       // We add prevI to the pending list if it wasn't yet
-                       if (!containsIndex(pending, prevI)) pending.push_back(prevI);
-               }
-       }
-       else if (nextI == prevJ) {
-               // nextI/prevJ will be a new vertex required to merge
-               if (nextI < m_firstVertex) return NULL; // It can't be merged
-               if (BOP_between(vertex,vPrevI,vNextJ) && BOP_between(vNextI,vOppI,vOppJ)) {
-                       faceK = new BOP_Face4(oppI,prevI,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-                       // Add nextI to the pending list if it wasn't yet
-                       if (!containsIndex(pending, nextI)) pending.push_back(nextI);
-               }
-       }
-       return faceK;
-}
-
-
-/** 
- * Simplifies the mesh, merging the pairs of triangles that come frome the
- * same original face and define a quad.
- * @return true if a quad was added, false otherwise
- */
-bool BOP_Merge::createQuads()
-{
-  
-       BOP_Faces quads;
-       
-       // Get mesh faces
-       BOP_Faces faces = m_mesh->getFaces();
-
-       
-    // Merge mesh triangles
-       const BOP_IT_Faces facesIEnd = (faces.end()-1);
-       const BOP_IT_Faces facesJEnd = faces.end();
-       for(BOP_IT_Faces faceI=faces.begin();faceI!=facesIEnd;faceI++) {
-               if ((*faceI)->getTAG() == BROKEN || (*faceI)->size() != 3) continue;
-               for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) {
-                       if ((*faceJ)->getTAG() == BROKEN || (*faceJ)->size() != 3 ||
-                               (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue;
-
-                       // Test if both triangles share a vertex index
-                       BOP_Index v;
-                       bool found = false;
-                       for(unsigned int i=0;i<3 && !found;i++) {
-                               v = (*faceI)->getVertex(i);
-                               found = (*faceJ)->containsVertex(v);
-                               
-                       }
-                       if (!found) continue;
-
-                       BOP_Face *faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ,v);
-                       if (faceK != NULL) {
-                               // Set triangles to BROKEN
-                               (*faceI)->setTAG(BROKEN);
-                               (*faceJ)->setTAG(BROKEN);
-                               quads.push_back(faceK);
-                               break;
-                       }
-               }
-       }
-
-    // Add quads to mesh
-       const BOP_IT_Faces quadsEnd = quads.end();
-       for(BOP_IT_Faces quad=quads.begin();quad!=quadsEnd;quad++) m_mesh->addFace(*quad);
-       return (quads.size() > 0);
-}
-
-/** 
- * Returns a new quad (convex) from the merge of two triangles that share the
- * vertex index v.
- * @param faceI mesh triangle
- * @param faceJ mesh triangle
- * @param v vertex index shared by both triangles
- * @return a new convex quad if the merge is possible
- */
-BOP_Face* BOP_Merge::createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v)
-{
-       BOP_Face *faceK = NULL;
-
-       // Get faces data
-       BOP_Index prevI, nextI, prevJ, nextJ;
-       faceI->getNeighbours(v,prevI,nextI);
-       faceJ->getNeighbours(v,prevJ,nextJ);
-       MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
-       MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
-       MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
-       MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
-       MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
-
-       // Quad test
-       if (prevI == nextJ) {
-               if (!BOP_collinear(vNextI,vertex,vPrevJ) && !BOP_collinear(vNextI,vPrevI,vPrevJ) &&
-                       BOP_convex(vertex,vNextI,vPrevI,vPrevJ)) {
-                               faceK = new BOP_Face4(v,nextI,prevI,prevJ,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-               }
-       }
-       else if (nextI == prevJ) {
-               if (!BOP_collinear(vPrevI,vertex,vNextJ) && !BOP_collinear(vPrevI,vNextI,vNextJ) &&
-                       BOP_convex(vertex,vNextJ,vNextI,vPrevI)) {
-                               faceK = new BOP_Face4(v,nextJ,nextI,prevI,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-                       }
-       }
-       return faceK;
-}
-
-/**
- * Returns if a index is inside a set of indexs.
- * @param indexs set of indexs
- * @param i index
- * @return true if the index is inside the set, false otherwise
- */
-bool BOP_Merge::containsIndex(BOP_Indexs indexs, BOP_Index i)
-{
-  const BOP_IT_Indexs indexsEnd = indexs.end();
-       for(BOP_IT_Indexs it=indexs.begin();it!=indexsEnd;it++) {
-               if (*it == i) return true;
-       }
-       return false;
-}
-
-/**
- * Creates a list of lists L1, L2, ... LN where
- *   LX = mesh faces with vertex v that come from the same original face
- * @param facesByOriginalFace list of faces lists
- * @param v vertex index
- */
-void BOP_Merge::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v)
-{
-       // Get edges with vertex v
-       BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
-       const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
-       for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
-               // Foreach edge, add its no broken faces to the output list
-               BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
-               BOP_Indexs faceIndexs = edge->getFaces();
-               const BOP_IT_Indexs faceEnd = faceIndexs.end();
-               for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
-                       BOP_Face* face = m_mesh->getFace(*faceIndex);
-                       if (face->getTAG() != BROKEN) {
-                               bool found = false;
-                               // Search if we already have created a list for the 
-                               // faces that come from the same original face
-                               const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
-                               for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
-                               facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
-                                       if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
-                                               // Search that the face has not been added to the list before
-                                               for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
-                                                       if ((*facesByOriginalFaceX)[i] == face) {
-                                                               found = true;
-                                                               break;
-                                                       }
-                                               }
-                                               if (!found) {
-                                                       // Add the face to the list
-                                                 if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
-                                                 else facesByOriginalFaceX->push_back(face);
-                                                 found = true;
-                                               }
-                                               break;
-                                       }
-                               }
-                               if (!found) {
-                                       // Create a new list and add the current face
-                                       BOP_Faces facesByOriginalFaceX;
-                                       facesByOriginalFaceX.push_back(face);
-                                       facesByOriginalFace.push_back(facesByOriginalFaceX);
-                               }
-                       }
-               }
-       }
-}
-
-/**
- * Creates a list of lists L1, L2, ... LN where
- *   LX = mesh faces with vertex v that come from the same original face
- *        and without any of the vertices that appear before v in vertices
- * @param facesByOriginalFace list of faces lists
- * @param vertices vector with vertices indexs that contains v
- * @param v vertex index
- */
-void BOP_Merge::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v)
-{
-       // Get edges with vertex v
-       BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
-       const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
-       for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
-               // Foreach edge, add its no broken faces to the output list
-               BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
-               BOP_Indexs faceIndexs = edge->getFaces();
-               const BOP_IT_Indexs faceEnd = faceIndexs.end();
-               for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
-                       BOP_Face* face = m_mesh->getFace(*faceIndex);
-                       if (face->getTAG() != BROKEN) {
-                               // Search if the face contains any of the forbidden vertices
-                               bool found = false;
-                               for(BOP_IT_Indexs vertex = vertices.begin();*vertex!= v;vertex++) {
-                                       if (face->containsVertex(*vertex)) {
-                                               // face contains a forbidden vertex!
-                                               found = true;
-                                               break;
-                               }
-                       }
-                       if (!found) {
-                               // Search if we already have created a list with the 
-                               // faces that come from the same original face
-                         const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
-                               for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
-                                       facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
-                                       if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
-                                               // Search that the face has not been added to the list before
-                                               for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
-                                                       if ((*facesByOriginalFaceX)[i] == face) {
-                                                               found = true;
-                                                               break;
-                                                       }
-                                               }
-                                               if (!found) {
-                                                 // Add face to the list
-                                                 if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
-                                                 else facesByOriginalFaceX->push_back(face);
-                                                 found = true;
-                                               }
-                                               break;
-                                       }
-                               }
-                               if (!found) {
-                                       // Create a new list and add the current face
-                                       BOP_Faces facesByOriginalFaceX;
-                                       facesByOriginalFaceX.push_back(face);
-                                       facesByOriginalFace.push_back(facesByOriginalFaceX);
-                               }
-                       }
-               }
-       }
-       }
-}
-
-#endif  /* BOP_ORIG_MERGE */
diff --git a/intern/boolop/intern/BOP_Merge.h b/intern/boolop/intern/BOP_Merge.h
deleted file mode 100644 (file)
index 9d6d703..0000000
+++ /dev/null
@@ -1,81 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Merge.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_MERGE_H__
-#define __BOP_MERGE_H__
-
-#include "BOP_Misc.h"
-
-#ifdef BOP_ORIG_MERGE
-#include "BOP_Mesh.h"
-#include "BOP_Tag.h"
-#include "BOP_MathUtils.h"
-#include "MEM_SmartPtr.h"
-
-typedef std::vector< BOP_Faces > BOP_LFaces;
-typedef std::vector< BOP_Faces >::iterator BOP_IT_LFaces;
-
-class BOP_Merge {
-       private:
-               BOP_Mesh* m_mesh;
-               BOP_Index m_firstVertex;
-               static BOP_Merge SINGLETON;
-
-               BOP_Merge() {};
-               bool mergeFaces();
-               bool mergeFaces(BOP_Indexs &mergeVertices);
-               bool mergeFaces(BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v);
-               bool mergeFaces(BOP_Faces &faces, BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Indexs &pending, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Indexs &pending, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face4 *faceJ, BOP_Indexs &pending, BOP_Index v);
-               bool createQuads();
-               BOP_Face *createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v);
-               bool containsIndex(BOP_Indexs indexs, BOP_Index index);
-               void getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v);
-               void getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v);
-
-       public:
-
-               static BOP_Merge &getInstance() {
-                       return SINGLETON;
-               }
-
-               void mergeFaces(BOP_Mesh *m, BOP_Index v);
-};
-
-#endif /* BOP_ORIG_MERGE */
-
-#endif
diff --git a/intern/boolop/intern/BOP_Merge2.cpp b/intern/boolop/intern/BOP_Merge2.cpp
deleted file mode 100644 (file)
index 6bec9ba..0000000
+++ /dev/null
@@ -1,948 +0,0 @@
-/*
- *
- *
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Marc Freixas, Ken Hughes
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Merge2.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_Merge2.h"
-
-#ifdef BOP_NEW_MERGE
-
-static void deleteFace(BOP_Mesh *m, BOP_Face *face);
-
-/**
- * SINGLETON (use method BOP_Merge2.getInstance).
- */
-BOP_Merge2 BOP_Merge2::SINGLETON;
-
-#ifdef BOP_DEBUG
-void dumpmesh ( BOP_Mesh *m, bool force )
-{
-       unsigned int nonmanifold = 0;
-       {
-       BOP_Edges edges = m->getEdges();
-       int count = 0;
-    for (BOP_IT_Edges edge = edges.begin(); edge != edges.end();
-               ++count, ++edge) {
-               if (!(*edge)->getUsed() && (*edge)->getFaces().size() == 0 ) continue;
-               BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1());
-               BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2());
-
-               if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) {
-                       int fcount = 0;
-                       BOP_Indexs faces = (*edge)->getFaces();
-                       for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) {
-                               BOP_Face *f = m->getFace(*face);
-                               if(f->getTAG()== UNCLASSIFIED) ++fcount;
-                       }
-
-
-                       if(fcount !=0 && fcount !=2 ) {
-                               ++nonmanifold;
-                       }
-               }
-       }
-       if (!force && nonmanifold == 0) return;
-       }
-       if( nonmanifold )
-               cout << nonmanifold << " edges detected" << endl;
-#ifdef BOP_DEBUG
-       cout << "---------------------------" << endl;
-
-       BOP_Edges edges = m->getEdges();
-       int count = 0;
-    for (BOP_IT_Edges edge = edges.begin(); edge != edges.end();
-               ++count, ++edge) {
-               BOP_Vertex * v1 = m->getVertex((*edge)->getVertex1());
-               BOP_Vertex * v2 = m->getVertex((*edge)->getVertex2());
-
-               if(v1->getTAG()!= BROKEN || v2->getTAG()!= BROKEN ) {
-                       int fcount = 0;
-                       BOP_Indexs faces = (*edge)->getFaces();
-                       cout << count << ", " << (*edge) << ", " << faces.size() << endl;
-                       for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); face++) {
-                               BOP_Face *f = m->getFace(*face);
-                               if(f->getTAG()== UNCLASSIFIED) ++fcount;
-                               cout << "  face " << f << endl;
-                       }
-
-
-                       if(fcount !=0 && fcount !=2 )
-                               cout << "    NON-MANIFOLD" << endl;
-               }
-       }
-
-       BOP_Faces faces = m->getFaces();
-       count = 0;
-    for (BOP_IT_Faces face = faces.begin(); face != faces.end(); face++) {
-               if( count < 12*2 || (*face)->getTAG() != BROKEN ) {
-                       cout << count << ", " << *face << endl;
-               }
-               ++count;
-       }
-
-       BOP_Vertexs verts = m->getVertexs();
-       count = 0;
-    for (BOP_IT_Vertexs vert = verts.begin(); vert != verts.end(); vert++) {
-               cout << count++ << ", " << *vert << " " << (*vert)->getNumEdges() << endl;
-               BOP_Indexs edges = (*vert)->getEdges();
-           for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) {
-                       BOP_Edge *edge = m->getEdge(*it);
-                       cout << "   " << edge << endl;
-               }
-       }
-       cout << "===========================" << endl;
-#endif
-}
-#endif
-
-/**
- * Simplifies a mesh, merging its faces.
- * @param m mesh
- * @param v index of the first mergeable vertex (can be removed by merge) 
- */
-
-void BOP_Merge2::mergeFaces(BOP_Mesh *m, BOP_Index v)
-{
-       m_mesh = m;
-
-#ifdef BOP_DEBUG
-       cout << "##############################" << endl;
-#endif
-       cleanup( );
-
-       m_firstVertex = v;
-       bool cont = false;
-
-       // Merge faces
-       mergeFaces();   
-
-       do {
-               // Add quads ...
-               cont = createQuads();
-               // ... and merge new faces
-               if( cont ) cont = mergeFaces();
-
-#ifdef BOP_DEBUG
-               cout << "called mergeFaces " << cont << endl;
-#endif
-               // ... until the merge is not succesful
-       } while(cont);
-}
-
-void clean_nonmanifold( BOP_Mesh *m )
-{
-       return;
-
-       BOP_Edges nme;
-       BOP_Edges e = m->getEdges();
-       for( BOP_IT_Edges it = e.begin(); it != e.end(); ++it ) {
-               BOP_Indexs faces = (*it)->getFaces();
-               if( faces.size() & ~2 )
-                       nme.push_back(*it);
-       }
-       if (nme.size() == 0) return;
-       for( BOP_IT_Edges it = nme.begin(); it != nme.end(); ++it ) {
-               if( (*it)->getFaces().size() > 1 ) {
-                       BOP_Indexs faces = (*it)->getFaces();
-                       for( BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face ) {
-                               MT_Point3 vertex1 = m->getVertex(m->getFace(*face)->getVertex(0))->getPoint();
-                               MT_Point3 vertex2 = m->getVertex(m->getFace(*face)->getVertex(1))->getPoint();
-                               MT_Point3 vertex3 = m->getVertex(m->getFace(*face)->getVertex(2))->getPoint();
-                               if (BOP_collinear(vertex1,vertex2,vertex3)) // collinear triangle
-                                       deleteFace(m,m->getFace(*face));
-                       }
-                       continue;
-               }
-               BOP_Face *oface1 = m->getFace((*it)->getFaces().front());
-               BOP_Face *oface2, *tmpface;
-               BOP_Index first =(*it)->getVertex1();
-               BOP_Index next =(*it)->getVertex2();
-               BOP_Index last = first;
-               unsigned short facecount = 0;
-               bool found = false;
-               BOP_Indexs vertList;
-#ifdef BOP_DEBUG
-               cout << "  first edge is " << (*it) << endl;
-#endif
-               vertList.push_back(first);
-               BOP_Edge *edge;
-               while(true) {
-                       BOP_Vertex *vert = m->getVertex(next);
-                       BOP_Indexs edges = vert->getEdges();
-                       edge = NULL;
-                       for( BOP_IT_Indexs eit = edges.begin(); eit != edges.end(); ++eit) {
-                               edge = m->getEdge(*eit);
-                               if( edge->getFaces().size() > 1) {
-                                       edge = NULL;
-                                       continue;
-                               }
-                               if( edge->getVertex1() == next && edge->getVertex2() != last ) {
-                                       last = next;
-                                       next = edge->getVertex2();
-                                       break;
-                               }
-                               if( edge->getVertex2() == next && edge->getVertex1() != last ) {
-                                       last = next;
-                                       next = edge->getVertex1();
-                                       break;
-                               }
-                               edge = NULL;
-                       }
-                       if( !edge ) break;
-#ifdef BOP_DEBUG
-                       cout << "   next edge is " << edge << endl;
-#endif
-                       tmpface = m->getFace(edge->getFaces().front());
-                       if( oface1->getOriginalFace() != tmpface->getOriginalFace() )
-                               oface2 = tmpface;
-                       else
-                               ++facecount;
-                       vertList.push_back(last);
-                       if( vertList.size() > 3 ) break;
-                       if( next == first ) {
-                               found = true;
-                               break;
-                       }
-               }
-               if(found) {
-                       edge = *it;
-#ifdef BOP_DEBUG
-                       cout << "   --> found a loop" << endl;
-#endif
-                       if( vertList.size() == 3 ) {
-                               BOP_Face3 *face = (BOP_Face3 *)m->getFace(edge->getFaces().front());
-                               face->getNeighbours(first,last,next);
-                       } else if( vertList.size() == 4 ) {
-                               BOP_Face4 *face = (BOP_Face4 *)m->getFace(edge->getFaces().front());
-                               face->getNeighbours(first,last,next,last);
-                       } else {
-#ifdef BOP_DEBUG
-                               cout << "loop has " << vertList.size() << "verts"; 
-#endif
-                               continue;
-                       }
-                       if(facecount == 1) oface1 = oface2;
-                       next = vertList[1];
-                       last = vertList[2];
-                       if( edge->getVertex2() == next ) { 
-                               BOP_Face3 *f = new BOP_Face3(next,first,last,
-                                       oface1->getPlane(),oface1->getOriginalFace());
-                               m->addFace( f );
-#ifdef BOP_DEBUG
-                               cout << "   face is backward: " << f << endl;
-#endif
-                               
-                       } else {
-                               BOP_Face3 *f = new BOP_Face3(last,first,next,
-                                       oface1->getPlane(),oface1->getOriginalFace());
-                               m->addFace( f );
-#ifdef BOP_DEBUG
-                               cout << "   face is forward: " << f << endl;
-#endif
-                       }
-               }
-       }
-}
-
-/**
- * Runs through mesh and makes sure vert/face/edge data is consistent.  Most
- * importantly:
- * (1) mark edges which are no longer used
- * (2) remove broken faces from edges
- * (3) remove faces from mesh which have a single edge belonging to no other
- *     face (non-manifold edges)
- */
-
-void BOP_Merge2::cleanup( void )
-{
-       BOP_Edges edges = m_mesh->getEdges();
-       for (BOP_IT_Edges edge = edges.begin(); edge != edges.end(); ++edge) {
-               BOP_Indexs faces = (*edge)->getFaces();
-               for (BOP_IT_Indexs face = faces.begin(); face != faces.end(); ++face) {
-                       BOP_Face *f = m_mesh->getFace(*face);
-                       if (f->getTAG()== UNCLASSIFIED);
-                       else (*edge)->removeFace(*face);
-               }
-               if( (*edge)->getFaces().size() == 0) (*edge)->setUsed(false);
-       }
-
-       BOP_Vertexs v = m_mesh->getVertexs();
-       for( BOP_IT_Vertexs it = v.begin(); it != v.end(); ++it ) {
-               if( (*it)->getTAG() != BROKEN) {
-                       BOP_Indexs iedges = (*it)->getEdges();
-                       for(BOP_IT_Indexs i = iedges.begin();i!=iedges.end();i++)
-                               if( m_mesh->getEdge((*i))->getUsed( ) == false) (*it)->removeEdge( *i );
-                       if( (*it)->getEdges().size() == 0 ) (*it)->setTAG(BROKEN);
-               }
-       }
-       // clean_nonmanifold( m_mesh );
-}
-
-/**
- * Simplifies a mesh, merging its faces.
- */
-bool BOP_Merge2::mergeFaces()
-{
-       BOP_Indexs mergeVertices;
-       BOP_Vertexs vertices = m_mesh->getVertexs();
-       BOP_IT_Vertexs v = vertices.begin();
-       const BOP_IT_Vertexs verticesEnd = vertices.end();
-
-       // Advance to first mergeable vertex
-       advance(v,m_firstVertex);
-       BOP_Index pos = m_firstVertex;
-
-       // Add unbroken vertices to the list
-       while(v!=verticesEnd) {
-               if ((*v)->getTAG() != BROKEN) {
-                       mergeVertices.push_back(pos);
-               }
-
-               v++;
-               pos++;
-       }
-
-       // Merge faces with that vertices
-       return mergeFaces(mergeVertices);
-}
-
-/**
- * remove edges from vertices when the vertex is removed
- */
-void BOP_Merge2::freeVerts(BOP_Index v, BOP_Vertex *vert)
-{
-       BOP_Indexs edges = vert->getEdges();
-       BOP_Vertex *other;
-
-       for( BOP_IT_Indexs it = edges.begin(); it != edges.end(); ++it) {
-               BOP_Edge *edge = m_mesh->getEdge(*it);
-               BOP_Indexs edges2;
-               if( edge->getVertex1() != v )
-                       other = m_mesh->getVertex( edge->getVertex1() );
-               else
-                       other = m_mesh->getVertex( edge->getVertex2() );
-               other->removeEdge(*it);
-               vert->removeEdge(*it);
-       }
-}
-
-/**
- * Simplifies a mesh, merging the faces with the specified vertices.
- * @param mergeVertices vertices to test
- * @return true if a face merge was performed
- */
-bool BOP_Merge2::mergeFaces(BOP_Indexs &mergeVertices)
-{
-       // Check size > 0!
-       if (mergeVertices.size() == 0) return false;
-       bool didMerge = false;
-
-       for( BOP_Index i = 0; i < mergeVertices.size(); ++i ) {
-               BOP_LFaces facesByOriginalFace;
-               BOP_Index v = mergeVertices[i];
-               BOP_Vertex *vert = m_mesh->getVertex(v);
-#ifdef BOP_DEBUG
-               cout << "i = " << i << ", v = " << v << ", vert = " << vert << endl;
-               if (v==48)
-                       cout << "found vert 48" << endl;
-#endif
-               if ( vert->getTAG() != BROKEN ) {
-                       getFaces(facesByOriginalFace,v);
-
-                       switch (facesByOriginalFace.size()) {
-                       case 0:
-                               // v has no unbroken faces (so it's a new BROKEN vertex)
-                               freeVerts( v, vert );
-                               vert->setTAG(BROKEN);
-                               break;
-                       case 2: {
-#ifdef BOP_DEBUG
-                               cout << "size of fBOF = " << facesByOriginalFace.size() << endl;
-#endif
-                               BOP_Faces ff = facesByOriginalFace.front();
-                               BOP_Faces fb = facesByOriginalFace.back();
-                               BOP_Index eindexs[2];
-                               int ecount = 0;
-
-                               // look for two edges adjacent to v which contain both ofaces
-                               BOP_Indexs edges = vert->getEdges();
-#ifdef BOP_DEBUG
-                               cout << "   ff has " << ff.size() << " faces" << endl;
-                               cout << "   fb has " << fb.size() << " faces" << endl;
-                               cout << "   v  has " << edges.size() << " edges" << endl;
-#endif
-                               for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); 
-                                               ++it ) {
-                                       BOP_Edge *edge = m_mesh->getEdge(*it);
-                                       BOP_Indexs faces = edge->getFaces();
-#ifdef BOP_DEBUG
-                                       cout << "  " << edge << " has " << edge->getFaces().size() << " faces" << endl;
-#endif
-                                       if( faces.size() == 2 ) {
-                                               BOP_Face *f0 = m_mesh->getFace(faces[0]);
-                                               BOP_Face *f1 = m_mesh->getFace(faces[1]);
-                                               if( f0->getOriginalFace() != f1->getOriginalFace() ) {
-#ifdef BOP_DEBUG
-                                                       cout << "   " << f0 << endl;
-                                                       cout << "   " << f1 << endl;
-#endif
-                                                       eindexs[ecount++] = (*it);
-                                               }
-                                       }
-                               }
-                               if(ecount == 2) {
-#ifdef BOP_DEBUG
-                                       cout << "   edge indexes are " << eindexs[0];
-                                       cout << " and " << eindexs[1] << endl;
-#endif
-                                       BOP_Edge *edge = m_mesh->getEdge(eindexs[0]);
-                                       BOP_Index N = edge->getVertex1();
-                                       if(N == v) N = edge->getVertex2();
-#ifdef BOP_DEBUG
-                                       cout << "    ## OK, replace "<<v<<" with "<<N << endl;
-#endif
-                                       mergeVertex(ff , v, N );
-                                       mergeVertex(fb , v, N );
-// now remove v and its edges
-                                       vert->setTAG(BROKEN);
-                                       for(BOP_IT_Indexs it = edges.begin(); it != edges.end(); 
-                                                       ++it ) {
-                                               BOP_Edge *tedge = m_mesh->getEdge(*it);
-                                               tedge->setUsed(false);
-                                       }
-                                       didMerge = true;
-                               }       
-#ifdef BOP_DEBUG
-                               else {
-                                       cout << "   HUH: ecount was " << ecount << endl;
-                               }
-#endif
-                               }
-                               break;
-                       default:
-                               break;
-                       }
-               }
-       }
-
-       return didMerge;
-}
-
-void BOP_Merge2::mergeVertex(BOP_Faces &faces, BOP_Index v1, BOP_Index v2)
-{
-       for(BOP_IT_Faces face=faces.begin();face!=faces.end();face++) {
-               if( (*face)->size() == 3)
-                       mergeVertex((BOP_Face3 *) *face, v1, v2);
-               else
-                       mergeVertex((BOP_Face4 *) *face, v1, v2);
-               (*face)->setTAG(BROKEN);
-#ifdef BOP_DEBUG
-               cout << "  breaking " << (*face) << endl;
-#endif
-       }
-}
-
-/*
- * Remove a face from the mesh and from each edges's face list
- */
-
-static void deleteFace(BOP_Mesh *m, BOP_Face *face)
-{
-       BOP_Index l2 = face->getVertex(0);
-       BOP_Faces faces = m->getFaces();
-       for(int i = face->size(); i-- ; ) {
-               BOP_Indexs edges = m->getVertex(l2)->getEdges();
-               BOP_Index l1 = face->getVertex(i);
-               for(BOP_IT_Indexs it1 = edges.begin(); it1 != edges.end(); ++it1 ) {
-                       BOP_Edge *edge = m->getEdge(*it1);
-                       if( ( edge->getVertex1() == l1 && edge->getVertex2() == l2 ) ||
-                               ( edge->getVertex1() == l2 && edge->getVertex2() == l1 ) ) {
-                               BOP_Indexs ef = edge->getFaces();
-                               for(BOP_IT_Indexs it = ef.begin(); it != ef.end(); ++it ) {
-                                       if( m->getFace(*it) == face) {
-                                               edge->removeFace(*it);
-                                               break;
-                                       }
-                               }
-                               break;
-                       }
-               }
-               l2 = l1;
-       }
-       face->setTAG(BROKEN);
-}
-
-void BOP_Merge2::mergeVertex(BOP_Face3 *face, BOP_Index v1, BOP_Index v2)
-{
-       BOP_Index next, prev;
-       face->getNeighbours(v1,prev,next);
-
-       // if new vertex is not already in the tri, make a new tri
-       if( prev != v2 && next != v2 ) {
-               m_mesh->addFace( new BOP_Face3(prev,v2,next,
-                                       face->getPlane(),face->getOriginalFace()) );
-#ifdef BOP_DEBUG
-               cout << "mv3: add " << prev << "," << v2 << "," << next << endl;
-       } else {
-               cout << "mv3: vertex already in tri: doing nothing" << endl;
-#endif
-       }
-       deleteFace(m_mesh, face);
-}
-
-void BOP_Merge2::mergeVertex(BOP_Face4 *face, BOP_Index v1, BOP_Index v2)
-{
-       BOP_Index next, prev, opp;
-       face->getNeighbours(v1,prev,next,opp);
-
-       // if new vertex is already in the quad, replace quad with new tri
-       if( prev == v2 || next == v2 ) {
-               m_mesh->addFace( new BOP_Face3(prev,next,opp,
-                                       face->getPlane(),face->getOriginalFace()) );
-#ifdef BOP_DEBUG
-               cout << "mv4a: add " << prev << "," << next << "," << opp << endl;
-#endif
-       }
-       // otherwise make a new quad
-       else {
-               m_mesh->addFace( new BOP_Face4(prev,v2,next,opp,
-                                       face->getPlane(),face->getOriginalFace()) );
-#ifdef BOP_DEBUG
-               cout << "mv4b: add "<<prev<<","<<v2<<","<<next<<","<<opp<<endl;
-#endif
-       }
-       deleteFace(m_mesh, face);
-}
-
-// #define OLD_QUAD
-
-/** 
- * Simplifies the mesh, merging the pairs of triangles that come frome the
- * same original face and define a quad.
- * @return true if a quad was added, false otherwise
- */
-bool BOP_Merge2::createQuads()
-{
-  
-       BOP_Faces quads;
-       
-       // Get mesh faces
-       BOP_Faces faces = m_mesh->getFaces();
-       
-    // Merge mesh triangles
-       const BOP_IT_Faces facesIEnd = (faces.end()-1);
-       const BOP_IT_Faces facesJEnd = faces.end();
-       for(BOP_IT_Faces faceI=faces.begin();faceI!=facesIEnd;faceI++) {
-#ifdef OLD_QUAD
-               if ((*faceI)->getTAG() == BROKEN || (*faceI)->size() != 3) continue;
-               for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) {
-                       if ((*faceJ)->getTAG() == BROKEN || (*faceJ)->size() != 3 ||
-                               (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue;
-
-
-                       BOP_Face *faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ);
-                       if (faceK != NULL) {
-                               // Set triangles to BROKEN
-                               deleteFace(m_mesh, *faceI);
-                               deleteFace(m_mesh, *faceJ);
-#ifdef BOP_DEBUG
-                       cout << "createQuad: del " << *faceI << endl;
-                       cout << "createQuad: del " << *faceJ << endl;
-                       cout << "createQuad: add " << faceK << endl;
-#endif
-                               quads.push_back(faceK);
-                               break;
-                       }
-               }
-#else
-               if ((*faceI)->getTAG() == BROKEN ) continue;
-               for(BOP_IT_Faces faceJ=(faceI+1);faceJ!=facesJEnd;faceJ++) {
-                       if ((*faceJ)->getTAG() == BROKEN ||
-                               (*faceJ)->getOriginalFace() != (*faceI)->getOriginalFace()) continue;
-
-                       BOP_Face *faceK = NULL;
-                       if((*faceI)->size() == 3) {
-                               if((*faceJ)->size() == 3)
-                                       faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face3*)*faceJ);
-                               else
-                                       faceK = createQuad((BOP_Face3*)*faceI,(BOP_Face4*)*faceJ);
-                       } else {
-                               if((*faceJ)->size() == 3)
-                                       faceK = createQuad((BOP_Face3*)*faceJ,(BOP_Face4*)*faceI);
-                               else
-                                       faceK = createQuad((BOP_Face4*)*faceI,(BOP_Face4*)*faceJ);
-                       }
-
-                       if (faceK != NULL) {
-                               // Set triangles to BROKEN
-                               deleteFace(m_mesh, *faceI);
-                               deleteFace(m_mesh, *faceJ);
-#ifdef BOP_DEBUG
-                       cout << "createQuad: del " << *faceI << endl;
-                       cout << "createQuad: del " << *faceJ << endl;
-                       cout << "createQuad: add " << faceK << endl;
-#endif
-                               quads.push_back(faceK);
-                               break;
-                       }
-               }
-#endif
-       }
-
-    // Add quads to mesh
-       const BOP_IT_Faces quadsEnd = quads.end();
-       for(BOP_IT_Faces quad=quads.begin();quad!=quadsEnd;quad++) m_mesh->addFace(*quad);
-       return (quads.size() > 0);
-}
-
-/** 
- * Returns a new quad (convex) from the merge of two triangles that share the
- * vertex index v.
- * @param faceI mesh triangle
- * @param faceJ mesh triangle
- * @param v vertex index shared by both triangles
- * @return a new convex quad if the merge is possible
- */
-BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ)
-{
-       // Test if both triangles share a vertex index
-       BOP_Index v;
-       unsigned int i;
-       for(i=0;i<3 ;i++) {
-               v = faceI->getVertex(i);
-               if( faceJ->containsVertex(v) ) break;
-       }
-       if (i == 3) return NULL;
-
-       BOP_Face *faceK = NULL;
-
-       // Get faces data
-       BOP_Index prevI, nextI, prevJ, nextJ;
-       faceI->getNeighbours(v,prevI,nextI);
-       faceJ->getNeighbours(v,prevJ,nextJ);
-       MT_Point3 vertex = m_mesh->getVertex(v)->getPoint();
-       MT_Point3 vPrevI = m_mesh->getVertex(prevI)->getPoint();
-       MT_Point3 vNextI = m_mesh->getVertex(nextI)->getPoint();
-       MT_Point3 vPrevJ = m_mesh->getVertex(prevJ)->getPoint();
-       MT_Point3 vNextJ = m_mesh->getVertex(nextJ)->getPoint();
-
-       // Quad test
-       if (prevI == nextJ) {
-               if (!BOP_collinear(vNextI,vertex,vPrevJ) && !BOP_collinear(vNextI,vPrevI,vPrevJ) &&
-                       BOP_convex(vertex,vNextI,vPrevI,vPrevJ)) {
-                               faceK = new BOP_Face4(v,nextI,prevI,prevJ,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-                               BOP_Index edge;
-                               m_mesh->getIndexEdge(v,prevI,edge);
-                               m_mesh->getVertex(v)->removeEdge(edge);
-                               m_mesh->getVertex(prevI)->removeEdge(edge);
-               }
-       }
-       else if (nextI == prevJ) {
-               if (!BOP_collinear(vPrevI,vertex,vNextJ) && !BOP_collinear(vPrevI,vNextI,vNextJ) &&
-                       BOP_convex(vertex,vNextJ,vNextI,vPrevI)) {
-                               faceK = new BOP_Face4(v,nextJ,nextI,prevI,faceI->getPlane(),faceI->getOriginalFace());
-                               faceK->setTAG(faceI->getTAG());
-                               BOP_Index edge;
-                               m_mesh->getIndexEdge(v,nextI,edge);
-                               m_mesh->getVertex(v)->removeEdge(edge);
-                               m_mesh->getVertex(nextI)->removeEdge(edge);
-                       }
-       }
-       return faceK;
-}
-
-/** 
- * Returns a new quad (convex) from the merge of two triangles that share the
- * vertex index v.
- * @param faceI mesh triangle
- * @param faceJ mesh triangle
- * @param v vertex index shared by both triangles
- * @return a new convex quad if the merge is possible
- */
-BOP_Face* BOP_Merge2::createQuad(BOP_Face3 *faceI, BOP_Face4 *faceJ)
-{
-       // Test if triangle and quad share a vertex index
-       BOP_Index v;
-       unsigned int i;
-       for(i=0;i<3 ;i++) {
-               v = faceI->getVertex(i);
-               if( faceJ->containsVertex(v) ) break;
-       }
-       if (i == 3) return NULL;
-
-       BOP_Face *faceK = NULL;
-
-       // Get faces data
-       BOP_Index prevI, nextI, prevJ, nextJ, oppJ;
-       faceI->getNeighbours(v,prevI,nextI);
-       faceJ->getNeighbours(v,prevJ,nextJ,oppJ);
-
-       // Quad test
-       BOP_Index edge;
-       if (nextI == prevJ) {
-               if (prevI == nextJ) {   // v is in center
-                       faceK = new BOP_Face3(nextJ,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-                       m_mesh->getIndexEdge(v,prevI,edge);
-                       m_mesh->getVertex(v)->removeEdge(edge);
-                       m_mesh->getVertex(prevI)->removeEdge(edge);
-                       m_mesh->getIndexEdge(v,nextI,edge);
-                       m_mesh->getVertex(v)->removeEdge(edge);
-                       m_mesh->getVertex(nextI)->removeEdge(edge);
-                       freeVerts(v, m_mesh->getVertex(v));
-               } else if (prevI == oppJ) {     // nextI is in center
-                       faceK = new BOP_Face3(v,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-                       m_mesh->getIndexEdge(v,nextI,edge);
-                       m_mesh->getVertex(v)->removeEdge(edge);
-                       m_mesh->getVertex(nextI)->removeEdge(edge);
-                       m_mesh->getIndexEdge(prevI,nextI,edge);
-                       m_mesh->getVertex(prevI)->removeEdge(edge);
-                       m_mesh->getVertex(nextI)->removeEdge(edge);
-                       freeVerts(nextI, m_mesh->getVertex(nextI));
-               }
-       } else if (nextI == oppJ && prevI == nextJ ) { // prevI is in center
-               faceK = new BOP_Face3(prevJ,v,oppJ,faceI->getPlane(),faceI->getOriginalFace());
-               faceK->setTAG(faceI->getTAG());
-               m_mesh->getIndexEdge(v,prevI,edge);
-               m_mesh->getVertex(v)->removeEdge(edge);
-               m_mesh->getVertex(prevI)->removeEdge(edge);
-               m_mesh->getIndexEdge(nextI,prevI,edge);
-               m_mesh->getVertex(nextI)->removeEdge(edge);
-               m_mesh->getVertex(prevI)->removeEdge(edge);
-               freeVerts(prevI, m_mesh->getVertex(prevI));
-       }
-       return faceK;
-}
-
-/** 
- * Returns a new quad (convex) from the merge of two triangles that share the
- * vertex index v.
- * @param faceI mesh triangle
- * @param faceJ mesh triangle
- * @param v vertex index shared by both triangles
- * @return a new convex quad if the merge is possible
- */
-BOP_Face* BOP_Merge2::createQuad(BOP_Face4 *faceI, BOP_Face4 *faceJ)
-{
-       BOP_Face *faceK = NULL;
-       //
-       // Test if both quads share a vertex index
-       //
-       BOP_Index v;
-       unsigned int i;
-       for(i=0;i<4 ;i++) {
-               v = faceI->getVertex(i);
-               if( faceJ->containsVertex(v) ) break;
-       }
-       if (i == 3) return NULL;
-
-
-       // Get faces data
-       BOP_Index prevI, nextI, oppI, prevJ, nextJ, oppJ;
-       faceI->getNeighbours(v,prevI,nextI,oppI);
-       faceJ->getNeighbours(v,prevJ,nextJ,oppJ);
-
-       // Quad test
-       BOP_Index edge;
-       if (nextI == prevJ) {
-               if (prevI == nextJ) {   // v is in center
-                       faceK = new BOP_Face4(nextI,oppI,nextJ,oppJ,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-                       m_mesh->getIndexEdge(v,prevI,edge);
-                       m_mesh->getVertex(v)->removeEdge(edge);
-                       m_mesh->getVertex(prevI)->removeEdge(edge);
-                       m_mesh->getIndexEdge(v,nextI,edge);
-                       m_mesh->getVertex(v)->removeEdge(edge);
-                       m_mesh->getVertex(nextI)->removeEdge(edge);
-                       freeVerts(v, m_mesh->getVertex(v));
-               } else if (oppI == oppJ) {      // nextI is in center
-                       faceK = new BOP_Face4(v,nextJ,oppJ,prevI,faceI->getPlane(),faceI->getOriginalFace());
-                       faceK->setTAG(faceI->getTAG());
-                       m_mesh->getIndexEdge(v,nextI,edge);
-                       m_mesh->getVertex(v)->removeEdge(edge);
-                       m_mesh->getVertex(nextI)->removeEdge(edge);
-                       m_mesh->getIndexEdge(prevI,nextI,edge);
-                       m_mesh->getVertex(prevI)->removeEdge(edge);
-                       m_mesh->getVertex(nextI)->removeEdge(edge);
-                       freeVerts(nextI, m_mesh->getVertex(nextI));
-               }
-       } else if (prevI == nextJ && oppI == oppJ) { // prevI is in center
-               faceK = new BOP_Face4(v,nextI,oppJ,prevJ,faceI->getPlane(),faceI->getOriginalFace());
-               faceK->setTAG(faceI->getTAG());
-               m_mesh->getIndexEdge(v,prevI,edge);
-               m_mesh->getVertex(v)->removeEdge(edge);
-               m_mesh->getVertex(prevI)->removeEdge(edge);
-               m_mesh->getIndexEdge(nextI,prevI,edge);
-               m_mesh->getVertex(nextI)->removeEdge(edge);
-               m_mesh->getVertex(prevI)->removeEdge(edge);
-               freeVerts(prevI, m_mesh->getVertex(prevI));
-       }
-       return faceK;
-}
-
-/**
- * Returns if a index is inside a set of indexs.
- * @param indexs set of indexs
- * @param i index
- * @return true if the index is inside the set, false otherwise
- */
-bool BOP_Merge2::containsIndex(BOP_Indexs indexs, BOP_Index i)
-{
-  const BOP_IT_Indexs indexsEnd = indexs.end();
-       for(BOP_IT_Indexs it=indexs.begin();it!=indexsEnd;it++) {
-               if (*it == i) return true;
-       }
-       return false;
-}
-
-/**
- * Creates a list of lists L1, L2, ... LN where
- *   LX = mesh faces with vertex v that come from the same original face
- * @param facesByOriginalFace list of faces lists
- * @param v vertex index
- */
-void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v)
-{
-       // Get edges with vertex v
-
-       BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
-       const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
-       for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
-               // For each edge, add its no broken faces to the output list
-               BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
-               BOP_Indexs faceIndexs = edge->getFaces();
-               const BOP_IT_Indexs faceEnd = faceIndexs.end();
-               for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
-                       BOP_Face* face = m_mesh->getFace(*faceIndex);
-                       if (face->getTAG() != BROKEN) {
-                               bool found = false;
-                               // Search if we already have created a list for the 
-                               // faces that come from the same original face
-                               const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
-                               for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
-                               facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
-                                       if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
-                                               // Search that the face has not been added to the list before
-                                               for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
-                                                       if ((*facesByOriginalFaceX)[i] == face) {
-                                                               found = true;
-                                                               break;
-                                                       }
-                                               }
-                                               if (!found) {
-                                                       // Add the face to the list
-                                                 if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
-                                                 else facesByOriginalFaceX->push_back(face);
-                                                 found = true;
-                                               }
-                                               break;
-                                       }
-                               }
-                               if (!found) {
-                                       // Create a new list and add the current face
-                                       BOP_Faces facesByOriginalFaceX;
-                                       facesByOriginalFaceX.push_back(face);
-                                       facesByOriginalFace.push_back(facesByOriginalFaceX);
-                               }
-                       }
-               }
-       }
-}
-
-/**
- * Creates a list of lists L1, L2, ... LN where
- *   LX = mesh faces with vertex v that come from the same original face
- *        and without any of the vertices that appear before v in vertices
- * @param facesByOriginalFace list of faces lists
- * @param vertices vector with vertices indexs that contains v
- * @param v vertex index
- */
-void BOP_Merge2::getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v)
-{
-       // Get edges with vertex v
-       BOP_Indexs edgeIndexs = m_mesh->getVertex(v)->getEdges();
-       const BOP_IT_Indexs edgeEnd = edgeIndexs.end();
-       for(BOP_IT_Indexs edgeIndex = edgeIndexs.begin();edgeIndex != edgeEnd;edgeIndex++) {    
-               // Foreach edge, add its no broken faces to the output list
-               BOP_Edge* edge = m_mesh->getEdge(*edgeIndex);
-               BOP_Indexs faceIndexs = edge->getFaces();
-               const BOP_IT_Indexs faceEnd = faceIndexs.end();
-               for(BOP_IT_Indexs faceIndex=faceIndexs.begin();faceIndex!=faceEnd;faceIndex++) {
-                       BOP_Face* face = m_mesh->getFace(*faceIndex);
-                       if (face->getTAG() != BROKEN) {
-                               // Search if the face contains any of the forbidden vertices
-                               bool found = false;
-                               for(BOP_IT_Indexs vertex = vertices.begin();*vertex!= v;vertex++) {
-                                       if (face->containsVertex(*vertex)) {
-                                               // face contains a forbidden vertex!
-                                               found = true;
-                                               break;
-                               }
-                       }
-                       if (!found) {
-                               // Search if we already have created a list with the 
-                               // faces that come from the same original face
-                         const BOP_IT_LFaces lfEnd = facesByOriginalFace.end();
-                               for(BOP_IT_LFaces facesByOriginalFaceX=facesByOriginalFace.begin();
-                                       facesByOriginalFaceX!=lfEnd; facesByOriginalFaceX++) {
-                                       if (((*facesByOriginalFaceX)[0])->getOriginalFace() == face->getOriginalFace()) {
-                                               // Search that the face has not been added to the list before
-                                               for(unsigned int i = 0;i<(*facesByOriginalFaceX).size();i++) {
-                                                       if ((*facesByOriginalFaceX)[i] == face) {
-                                                               found = true;
-                                                               break;
-                                                       }
-                                               }
-                                               if (!found) {
-                                                 // Add face to the list
-                                                 if (face->getTAG()==OVERLAPPED) facesByOriginalFaceX->insert(facesByOriginalFaceX->begin(),face);
-                                                 else facesByOriginalFaceX->push_back(face);
-                                                 found = true;
-                                               }
-                                               break;
-                                       }
-                               }
-                               if (!found) {
-                                       // Create a new list and add the current face
-                                       BOP_Faces facesByOriginalFaceX;
-                                       facesByOriginalFaceX.push_back(face);
-                                       facesByOriginalFace.push_back(facesByOriginalFaceX);
-                               }
-                       }
-               }
-       }
-       }
-}
-
-#endif  /* BOP_NEW_MERGE */
diff --git a/intern/boolop/intern/BOP_Merge2.h b/intern/boolop/intern/BOP_Merge2.h
deleted file mode 100644 (file)
index 71ec070..0000000
+++ /dev/null
@@ -1,104 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Merge2.h
- *  \ingroup boolopintern
- */
-
-#ifndef __BOP_MERGE2_H__
-#define __BOP_MERGE2_H__
-
-#include "BOP_Misc.h"
-
-#ifdef BOP_NEW_MERGE
-
-#include "BOP_Mesh.h"
-#include "BOP_Tag.h"
-#include "BOP_MathUtils.h"
-#include "MEM_SmartPtr.h"
-
-typedef std::vector< BOP_Faces > BOP_LFaces;
-typedef std::vector< BOP_Faces >::iterator BOP_IT_LFaces;
-
-class BOP_Merge2 {
-       private:
-               BOP_Mesh* m_mesh;
-               BOP_Index m_firstVertex;
-               static BOP_Merge2 SINGLETON;
-
-               BOP_Merge2() {};
-               bool mergeFaces();
-               bool mergeFaces(BOP_Indexs &mergeVertices);
-               bool mergeFaces(BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v);
-               bool mergeFaces(BOP_Faces &faces, BOP_Faces &oldFaces, BOP_Faces &newFaces, BOP_Indexs &vertices, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face *faceI, BOP_Face *faceJ, BOP_Indexs &pending, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face3 *faceI, BOP_Face3 *faceJ, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face3 *faceJ, BOP_Indexs &pending, BOP_Index v);
-               BOP_Face *mergeFaces(BOP_Face4 *faceI, BOP_Face4 *faceJ, BOP_Indexs &pending, BOP_Index v);
-               bool createQuads();
-               bool containsIndex(BOP_Indexs indexs, BOP_Index index);
-               void getFaces(BOP_LFaces &facesByOriginalFace, BOP_Index v);
-               void getFaces(BOP_LFaces &facesByOriginalFace, BOP_Indexs vertices, BOP_Index v);
-               BOP_Face *createQuad(BOP_Face3 *faceI, BOP_Face3 *faceJ);
-               BOP_Face *createQuad(BOP_Face3 *faceI, BOP_Face4 *faceJ);
-               BOP_Face *createQuad(BOP_Face4 *faceI, BOP_Face4 *faceJ);
-
-               bool mergeVertex(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v,
-                               BOP_Indexs &mergeVertices);
-               bool mergeVertex(BOP_Face *faceI, BOP_Face *faceJ, BOP_Index v,
-                               BOP_Indexs &pending, BOP_Faces &oldFaces, BOP_Faces &newFaces );
-               BOP_Face *find3Neighbor(BOP_Face *faceI, BOP_Face *faceJ,
-                               BOP_Index X, BOP_Index I, BOP_Index P, BOP_Index N );
-               BOP_Face *find4Neighbor(BOP_Face *faceI, BOP_Face *faceJ,
-                               BOP_Index X, BOP_Index I, BOP_Index P, BOP_Index N,
-                               BOP_Face **faceL, BOP_Index &O);
-               BOP_Face3 *collapse(BOP_Face4 *faceC, BOP_Index X);
-               void mergeFaces(BOP_Face *A, BOP_Face *B, BOP_Index X,
-                       BOP_Index I, BOP_Index N, BOP_Index P, BOP_Faces &newFaces );
-               void freeVerts(BOP_Index v, BOP_Vertex *vert);
-
-               void mergeVertex(BOP_Faces&, BOP_Index, BOP_Index);
-               void mergeVertex(BOP_Face3 *, BOP_Index, BOP_Index);
-               void mergeVertex(BOP_Face4 *, BOP_Index, BOP_Index);
-               void cleanup( void );
-
-       public:
-
-               static BOP_Merge2 &getInstance() {
-                       return SINGLETON;
-               }
-
-               void mergeFaces(BOP_Mesh *m, BOP_Index v);
-};
-
-void dumpmesh(BOP_Mesh *, bool);
-
-#endif /* BOP_NEW_MERGE2 */
-#endif
diff --git a/intern/boolop/intern/BOP_Mesh.cpp b/intern/boolop/intern/BOP_Mesh.cpp
deleted file mode 100644 (file)
index 673caa3..0000000
+++ /dev/null
@@ -1,1090 +0,0 @@
-/*
- *
- *
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-/** \file boolop/intern/BOP_Mesh.cpp
- *  \ingroup boolopintern
- */
-
-#include "BOP_Mesh.h"
-#include "BOP_MathUtils.h"
-#include <iostream>
-#include <fstream>
-
-#include "MEM_guardedalloc.h"
-#include "BLI_blenlib.h"
-
-BOP_Mesh::BOP_Mesh()
-{
-#ifdef HASH
-#ifdef HASH_PRINTF_DEBUG
-       printf ("has hashing\n");
-#endif
-       hash = NULL;
-       hashsize = 0;
-#endif
-}
-
-/**
- * Destroys a mesh.
- */
-BOP_Mesh::~BOP_Mesh()
-{
-       const BOP_IT_Vertexs vertexsEnd = m_vertexs.end();
-       for(BOP_IT_Vertexs itv=m_vertexs.begin();itv!=vertexsEnd;itv++){
-               delete *itv;
-       }
-       m_vertexs.clear();
-  
-       const BOP_IT_Edges edgesEnd = m_edges.end();
-       for(BOP_IT_Edges ite=m_edges.begin();ite!=edgesEnd;ite++){
-               delete *ite;
-       }
-       m_edges.clear();
-  
-       const BOP_IT_Faces facesEnd = m_faces.end();
-       for(BOP_IT_Faces itf=m_faces.begin();itf!=facesEnd;itf++){
-               delete *itf;
-       }
-       m_faces.clear();
-
-#ifdef HASH
-       while( hashsize ) {
-               --hashsize;
-               BLI_freelistN( &hash[hashsize] );
-       }
-       MEM_freeN( hash );
-       hash = NULL;
-#endif
-}
-
-/**
- * Adds a new vertex.
- * @param p vertex point
- * @return mesh vertex index
- */
-BOP_Index BOP_Mesh::addVertex(MT_Point3 p)
-{
-       m_vertexs.push_back(new BOP_Vertex(p));
-       return m_vertexs.size()-1;
-}
-
-/**
- * Adds a new edge.
- * @param v1 mesh vertex index
- * @param v2 mesh vertex index
- * @return mesh edge index
- */
-BOP_Index BOP_Mesh::addEdge(BOP_Index v1, BOP_Index v2)
-{
-#ifdef HASH
-       /* prepare a new hash entry for the edge */
-       int minv;
-       EdgeEntry *h = (EdgeEntry *)MEM_callocN( sizeof( EdgeEntry ), "edgehash" );
-
-       /* store sorted, smallest vert first */
-       if( v1 < v2 ) {
-               minv = HASH(v1);
-               h->v1 = v1;
-               h->v2 = v2;
-       } else {
-            &nb