Merge branch 'master' into blender2.8
authorSergey Sharybin <sergey.vfx@gmail.com>
Thu, 8 Feb 2018 15:27:28 +0000 (16:27 +0100)
committerSergey Sharybin <sergey.vfx@gmail.com>
Thu, 8 Feb 2018 15:27:28 +0000 (16:27 +0100)
151 files changed:
CMakeLists.txt
build_files/cmake/config/blender_full.cmake
build_files/cmake/config/blender_lite.cmake
build_files/cmake/config/blender_release.cmake
build_files/cmake/macros.cmake
extern/CMakeLists.txt
extern/carve/CMakeLists.txt [deleted file]
extern/carve/LICENSE.GPL2 [deleted file]
extern/carve/LICENSE.GPL3 [deleted file]
extern/carve/README.blender [deleted file]
extern/carve/bundle.sh [deleted file]
extern/carve/carve-capi.cc [deleted file]
extern/carve/carve-capi.h [deleted file]
extern/carve/carve-util.cc [deleted file]
extern/carve/carve-util.h [deleted file]
extern/carve/files.txt [deleted file]
extern/carve/include/carve/aabb.hpp [deleted file]
extern/carve/include/carve/aabb_impl.hpp [deleted file]
extern/carve/include/carve/carve.hpp [deleted file]
extern/carve/include/carve/cbrt.h [deleted file]
extern/carve/include/carve/classification.hpp [deleted file]
extern/carve/include/carve/collection.hpp [deleted file]
extern/carve/include/carve/collection/unordered.hpp [deleted file]
extern/carve/include/carve/collection/unordered/boost_impl.hpp [deleted file]
extern/carve/include/carve/collection/unordered/fallback_impl.hpp [deleted file]
extern/carve/include/carve/collection/unordered/libstdcpp_impl.hpp [deleted file]
extern/carve/include/carve/collection/unordered/std_impl.hpp [deleted file]
extern/carve/include/carve/collection/unordered/tr1_impl.hpp [deleted file]
extern/carve/include/carve/collection/unordered/vcpp_impl.hpp [deleted file]
extern/carve/include/carve/collection_types.hpp [deleted file]
extern/carve/include/carve/colour.hpp [deleted file]
extern/carve/include/carve/config.h [deleted file]
extern/carve/include/carve/convex_hull.hpp [deleted file]
extern/carve/include/carve/csg.hpp [deleted file]
extern/carve/include/carve/csg_triangulator.hpp [deleted file]
extern/carve/include/carve/debug_hooks.hpp [deleted file]
extern/carve/include/carve/djset.hpp [deleted file]
extern/carve/include/carve/edge_decl.hpp [deleted file]
extern/carve/include/carve/edge_impl.hpp [deleted file]
extern/carve/include/carve/exact.hpp [deleted file]
extern/carve/include/carve/face_decl.hpp [deleted file]
extern/carve/include/carve/face_impl.hpp [deleted file]
extern/carve/include/carve/faceloop.hpp [deleted file]
extern/carve/include/carve/geom.hpp [deleted file]
extern/carve/include/carve/geom2d.hpp [deleted file]
extern/carve/include/carve/geom3d.hpp [deleted file]
extern/carve/include/carve/geom_impl.hpp [deleted file]
extern/carve/include/carve/gnu_cxx.h [deleted file]
extern/carve/include/carve/heap.hpp [deleted file]
extern/carve/include/carve/input.hpp [deleted file]
extern/carve/include/carve/interpolator.hpp [deleted file]
extern/carve/include/carve/intersection.hpp [deleted file]
extern/carve/include/carve/iobj.hpp [deleted file]
extern/carve/include/carve/kd_node.hpp [deleted file]
extern/carve/include/carve/math.hpp [deleted file]
extern/carve/include/carve/math_constants.hpp [deleted file]
extern/carve/include/carve/matrix.hpp [deleted file]
extern/carve/include/carve/mesh.hpp [deleted file]
extern/carve/include/carve/mesh_impl.hpp [deleted file]
extern/carve/include/carve/mesh_ops.hpp [deleted file]
extern/carve/include/carve/mesh_simplify.hpp [deleted file]
extern/carve/include/carve/octree_decl.hpp [deleted file]
extern/carve/include/carve/octree_impl.hpp [deleted file]
extern/carve/include/carve/pointset.hpp [deleted file]
extern/carve/include/carve/pointset_decl.hpp [deleted file]
extern/carve/include/carve/pointset_impl.hpp [deleted file]
extern/carve/include/carve/pointset_iter.hpp [deleted file]
extern/carve/include/carve/poly.hpp [deleted file]
extern/carve/include/carve/poly_decl.hpp [deleted file]
extern/carve/include/carve/poly_impl.hpp [deleted file]
extern/carve/include/carve/polyhedron_base.hpp [deleted file]
extern/carve/include/carve/polyhedron_decl.hpp [deleted file]
extern/carve/include/carve/polyhedron_impl.hpp [deleted file]
extern/carve/include/carve/polyline.hpp [deleted file]
extern/carve/include/carve/polyline_decl.hpp [deleted file]
extern/carve/include/carve/polyline_impl.hpp [deleted file]
extern/carve/include/carve/polyline_iter.hpp [deleted file]
extern/carve/include/carve/random/random.h [deleted file]
extern/carve/include/carve/rescale.hpp [deleted file]
extern/carve/include/carve/rtree.hpp [deleted file]
extern/carve/include/carve/spacetree.hpp [deleted file]
extern/carve/include/carve/tag.hpp [deleted file]
extern/carve/include/carve/timing.hpp [deleted file]
extern/carve/include/carve/tree.hpp [deleted file]
extern/carve/include/carve/triangle_intersection.hpp [deleted file]
extern/carve/include/carve/triangulator.hpp [deleted file]
extern/carve/include/carve/triangulator_impl.hpp [deleted file]
extern/carve/include/carve/util.hpp [deleted file]
extern/carve/include/carve/vcpp_config.h [deleted file]
extern/carve/include/carve/vector.hpp [deleted file]
extern/carve/include/carve/vertex_decl.hpp [deleted file]
extern/carve/include/carve/vertex_impl.hpp [deleted file]
extern/carve/include/carve/win32.h [deleted file]
extern/carve/lib/carve.cpp [deleted file]
extern/carve/lib/convex_hull.cpp [deleted file]
extern/carve/lib/csg.cpp [deleted file]
extern/carve/lib/csg_collector.cpp [deleted file]
extern/carve/lib/csg_collector.hpp [deleted file]
extern/carve/lib/csg_data.hpp [deleted file]
extern/carve/lib/csg_detail.hpp [deleted file]
extern/carve/lib/face.cpp [deleted file]
extern/carve/lib/geom2d.cpp [deleted file]
extern/carve/lib/geom3d.cpp [deleted file]
extern/carve/lib/intersect.cpp [deleted file]
extern/carve/lib/intersect_classify_common.hpp [deleted file]
extern/carve/lib/intersect_classify_common_impl.hpp [deleted file]
extern/carve/lib/intersect_classify_edge.cpp [deleted file]
extern/carve/lib/intersect_classify_group.cpp [deleted file]
extern/carve/lib/intersect_common.hpp [deleted file]
extern/carve/lib/intersect_debug.cpp [deleted file]
extern/carve/lib/intersect_debug.hpp [deleted file]
extern/carve/lib/intersect_face_division.cpp [deleted file]
extern/carve/lib/intersect_group.cpp [deleted file]
extern/carve/lib/intersect_half_classify_group.cpp [deleted file]
extern/carve/lib/intersection.cpp [deleted file]
extern/carve/lib/math.cpp [deleted file]
extern/carve/lib/mesh.cpp [deleted file]
extern/carve/lib/octree.cpp [deleted file]
extern/carve/lib/pointset.cpp [deleted file]
extern/carve/lib/polyhedron.cpp [deleted file]
extern/carve/lib/polyline.cpp [deleted file]
extern/carve/lib/tag.cpp [deleted file]
extern/carve/lib/timing.cpp [deleted file]
extern/carve/lib/triangulator.cpp [deleted file]
extern/carve/mkfiles.sh [deleted file]
extern/carve/patches/clang_is_heap_fix.patch [deleted file]
extern/carve/patches/face_hole_merge_workaround.patch [deleted file]
extern/carve/patches/files/config.h [deleted file]
extern/carve/patches/files/random.h [deleted file]
extern/carve/patches/gcc46.patch [deleted file]
extern/carve/patches/includes.patch [deleted file]
extern/carve/patches/interpolator_reorder.patch [deleted file]
extern/carve/patches/memory_leak_fix.patch [deleted file]
extern/carve/patches/mesh_iterator.patch [deleted file]
extern/carve/patches/mesh_simplify_dissolve_edges.patch [deleted file]
extern/carve/patches/mesh_simplify_uninitialized_var.patch [deleted file]
extern/carve/patches/msvc_fix.patch [deleted file]
extern/carve/patches/random.patch [deleted file]
extern/carve/patches/series [deleted file]
extern/carve/patches/strict_flags.patch [deleted file]
extern/carve/patches/win32.patch [deleted file]
release/scripts/startup/bl_ui/properties_data_modifier.py
source/blender/makesdna/DNA_modifier_types.h
source/blender/makesrna/intern/rna_modifier.c
source/blender/modifiers/CMakeLists.txt
source/blender/modifiers/intern/MOD_boolean.c
source/blender/modifiers/intern/MOD_boolean_util.c [deleted file]
source/blender/modifiers/intern/MOD_boolean_util.h [deleted file]
source/blender/python/intern/CMakeLists.txt
source/blender/python/intern/bpy_app_build_options.c
source/blenderplayer/CMakeLists.txt

index 650f5ec4ff2d6b0a3cd3078f9a50ff726b58d949..0ce35da95f1306742932b75cd0d7afd0d8aa7238 100644 (file)
@@ -312,7 +312,6 @@ endif()
 # Modifiers
 option(WITH_MOD_FLUID           "Enable Elbeem Modifier (Fluid Simulation)" ON)
 option(WITH_MOD_SMOKE           "Enable Smoke Modifier (Smoke Simulation)" ON)
-option(WITH_MOD_BOOLEAN         "Enable Boolean Modifier" ON)
 option(WITH_MOD_REMESH          "Enable Remesh Modifier" ON)
 # option(WITH_MOD_CLOTH_ELTOPO    "Enable Experimental cloth solver" OFF)  # this is now only available in a branch
 # mark_as_advanced(WITH_MOD_CLOTH_ELTOPO)
@@ -639,9 +638,8 @@ if(NOT WITH_BOOST)
        set_and_warn(WITH_INTERNATIONAL  OFF)
        set_and_warn(WITH_OPENVDB        OFF)
        set_and_warn(WITH_OPENCOLORIO    OFF)
-       set_and_warn(WITH_MOD_BOOLEAN    OFF)
 elseif(WITH_CYCLES OR WITH_OPENIMAGEIO OR WITH_INTERNATIONAL OR
-       WITH_OPENVDB OR WITH_OPENCOLORIO OR WITH_MOD_BOOLEAN)
+       WITH_OPENVDB OR WITH_OPENCOLORIO)
        # Keep enabled
 else()
        # New dependency graph needs either Boost or C++11 for function bindings.
@@ -1710,7 +1708,6 @@ if(FIRST_RUN)
        endif()
 
        info_cfg_text("Modifiers:")
-       info_cfg_option(WITH_MOD_BOOLEAN)
        info_cfg_option(WITH_MOD_REMESH)
        info_cfg_option(WITH_MOD_FLUID)
        info_cfg_option(WITH_MOD_OCEANSIM)
index 35eba1e6a41b84559bb97bb9a2ddd7d48cca78b5..c896c0452b34fe97a509d83933c654f7f06eb716 100644 (file)
@@ -34,7 +34,6 @@ set(WITH_INTERNATIONAL       ON  CACHE BOOL "" FORCE)
 set(WITH_JACK                ON  CACHE BOOL "" FORCE)
 set(WITH_LZMA                ON  CACHE BOOL "" FORCE)
 set(WITH_LZO                 ON  CACHE BOOL "" FORCE)
-set(WITH_MOD_BOOLEAN         ON  CACHE BOOL "" FORCE)
 set(WITH_MOD_FLUID           ON  CACHE BOOL "" FORCE)
 set(WITH_MOD_REMESH          ON  CACHE BOOL "" FORCE)
 set(WITH_MOD_SMOKE           ON  CACHE BOOL "" FORCE)
index 98818d4ab501b4a048a49a0fff0aa19d788b7562..7db26c3f7c0d6c99b8d1051606c24a087980279f 100644 (file)
@@ -38,7 +38,6 @@ set(WITH_INTERNATIONAL       OFF CACHE BOOL "" FORCE)
 set(WITH_JACK                OFF CACHE BOOL "" FORCE)
 set(WITH_LZMA                OFF CACHE BOOL "" FORCE)
 set(WITH_LZO                 OFF CACHE BOOL "" FORCE)
-set(WITH_MOD_BOOLEAN         OFF CACHE BOOL "" FORCE)
 set(WITH_MOD_FLUID           OFF CACHE BOOL "" FORCE)
 set(WITH_MOD_REMESH          OFF CACHE BOOL "" FORCE)
 set(WITH_MOD_SMOKE           OFF CACHE BOOL "" FORCE)
index 3cdbfdfcf3bd74e26fc21455f16c98c338c55c82..1d1793e0aba964891fcba332cad1d05fc59191ae 100644 (file)
@@ -34,7 +34,6 @@ set(WITH_INTERNATIONAL       ON  CACHE BOOL "" FORCE)
 set(WITH_JACK                ON  CACHE BOOL "" FORCE)
 set(WITH_LZMA                ON  CACHE BOOL "" FORCE)
 set(WITH_LZO                 ON  CACHE BOOL "" FORCE)
-set(WITH_MOD_BOOLEAN         ON  CACHE BOOL "" FORCE)
 set(WITH_MOD_FLUID           ON  CACHE BOOL "" FORCE)
 set(WITH_MOD_REMESH          ON  CACHE BOOL "" FORCE)
 set(WITH_MOD_SMOKE           ON  CACHE BOOL "" FORCE)
index 6f014d7eb3b08696ebd50cea47c8563684239f37..09bc01fcae33010d57767a34977b88779d121c63 100644 (file)
@@ -736,10 +736,6 @@ function(SETUP_BLENDER_SORTED_LIBS)
                list(APPEND BLENDER_SORTED_LIBS bf_intern_itasc)
        endif()
 
-       if(WITH_MOD_BOOLEAN)
-               list(APPEND BLENDER_SORTED_LIBS extern_carve)
-       endif()
-
        if(WITH_GHOST_XDND)
                list(APPEND BLENDER_SORTED_LIBS extern_xdnd)
        endif()
index 65958eee6f72448a50f5edf0dad63446804f5aa8..54d3275b760ac2f369f5a66162768b496cbfc15b 100644 (file)
@@ -86,10 +86,6 @@ if(WITH_CYCLES OR WITH_COMPOSITOR OR WITH_OPENSUBDIV)
        endif()
 endif()
 
-if(WITH_MOD_BOOLEAN)
-       add_subdirectory(carve)
-endif()
-
 if(WITH_X11 AND WITH_GHOST_XDND)
        add_subdirectory(xdnd)
 endif()
diff --git a/extern/carve/CMakeLists.txt b/extern/carve/CMakeLists.txt
deleted file mode 100644 (file)
index bb81332..0000000
+++ /dev/null
@@ -1,170 +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 Beaurai, Erwin Coumans
-#
-# ***** END GPL LICENSE BLOCK *****
-
-# NOTE: This file is automatically generated by bundle.sh script
-#       If you're doing changes in this file, please update template
-#       in that script too
-
-set(INC
-       include
-)
-
-set(INC_SYS
-)
-
-set(SRC
-       carve-capi.cc
-       carve-util.cc
-       lib/carve.cpp
-       lib/convex_hull.cpp
-       lib/csg_collector.cpp
-       lib/csg.cpp
-       lib/face.cpp
-       lib/geom2d.cpp
-       lib/geom3d.cpp
-       lib/intersect_classify_edge.cpp
-       lib/intersect_classify_group.cpp
-       lib/intersect.cpp
-       lib/intersect_debug.cpp
-       lib/intersect_face_division.cpp
-       lib/intersect_group.cpp
-       lib/intersect_half_classify_group.cpp
-       lib/intersection.cpp
-       lib/math.cpp
-       lib/mesh.cpp
-       lib/octree.cpp
-       lib/pointset.cpp
-       lib/polyhedron.cpp
-       lib/polyline.cpp
-       lib/tag.cpp
-       lib/timing.cpp
-       lib/triangulator.cpp
-
-       carve-capi.h
-       carve-util.h
-       lib/csg_collector.hpp
-       lib/csg_data.hpp
-       lib/csg_detail.hpp
-       lib/intersect_classify_common.hpp
-       lib/intersect_classify_common_impl.hpp
-       lib/intersect_common.hpp
-       lib/intersect_debug.hpp
-
-       include/carve/aabb.hpp
-       include/carve/aabb_impl.hpp
-       include/carve/carve.hpp
-       include/carve/cbrt.h
-       include/carve/classification.hpp
-       include/carve/collection.hpp
-       include/carve/collection_types.hpp
-       include/carve/collection/unordered/boost_impl.hpp
-       include/carve/collection/unordered/fallback_impl.hpp
-       include/carve/collection/unordered.hpp
-       include/carve/collection/unordered/libstdcpp_impl.hpp
-       include/carve/collection/unordered/std_impl.hpp
-       include/carve/collection/unordered/tr1_impl.hpp
-       include/carve/collection/unordered/vcpp_impl.hpp
-       include/carve/colour.hpp
-       include/carve/convex_hull.hpp
-       include/carve/csg.hpp
-       include/carve/csg_triangulator.hpp
-       include/carve/debug_hooks.hpp
-       include/carve/djset.hpp
-       include/carve/edge_decl.hpp
-       include/carve/edge_impl.hpp
-       include/carve/exact.hpp
-       include/carve/face_decl.hpp
-       include/carve/face_impl.hpp
-       include/carve/faceloop.hpp
-       include/carve/geom2d.hpp
-       include/carve/geom3d.hpp
-       include/carve/geom.hpp
-       include/carve/geom_impl.hpp
-       include/carve/gnu_cxx.h
-       include/carve/heap.hpp
-       include/carve/input.hpp
-       include/carve/interpolator.hpp
-       include/carve/intersection.hpp
-       include/carve/iobj.hpp
-       include/carve/kd_node.hpp
-       include/carve/math_constants.hpp
-       include/carve/math.hpp
-       include/carve/matrix.hpp
-       include/carve/mesh.hpp
-       include/carve/mesh_impl.hpp
-       include/carve/mesh_ops.hpp
-       include/carve/mesh_simplify.hpp
-       include/carve/octree_decl.hpp
-       include/carve/octree_impl.hpp
-       include/carve/pointset_decl.hpp
-       include/carve/pointset.hpp
-       include/carve/pointset_impl.hpp
-       include/carve/pointset_iter.hpp
-       include/carve/poly_decl.hpp
-       include/carve/polyhedron_base.hpp
-       include/carve/polyhedron_decl.hpp
-       include/carve/polyhedron_impl.hpp
-       include/carve/poly.hpp
-       include/carve/poly_impl.hpp
-       include/carve/polyline_decl.hpp
-       include/carve/polyline.hpp
-       include/carve/polyline_impl.hpp
-       include/carve/polyline_iter.hpp
-       include/carve/rescale.hpp
-       include/carve/rtree.hpp
-       include/carve/spacetree.hpp
-       include/carve/tag.hpp
-       include/carve/timing.hpp
-       include/carve/tree.hpp
-       include/carve/triangle_intersection.hpp
-       include/carve/triangulator.hpp
-       include/carve/triangulator_impl.hpp
-       include/carve/util.hpp
-       include/carve/vcpp_config.h
-       include/carve/vector.hpp
-       include/carve/vertex_decl.hpp
-       include/carve/vertex_impl.hpp
-       include/carve/win32.h
-)
-
-if(WITH_BOOST)
-       if(NOT MSVC)
-               # Boost is setting as preferred collections library in the Carve code when using MSVC compiler
-               add_definitions(
-                       -DHAVE_BOOST_UNORDERED_COLLECTIONS
-               )
-       endif()
-
-       add_definitions(
-               -DCARVE_SYSTEM_BOOST
-               -DHAVE_BOOST_LIBRARY
-       )
-
-       list(APPEND INC_SYS
-               ${BOOST_INCLUDE_DIR}
-       )
-endif()
-
-blender_add_lib(extern_carve "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/extern/carve/LICENSE.GPL2 b/extern/carve/LICENSE.GPL2
deleted file mode 100644 (file)
index 792acb9..0000000
+++ /dev/null
@@ -1,361 +0,0 @@
-                    GNU GENERAL PUBLIC LICENSE
-
- The Qt GUI Toolkit is Copyright (C) 1994-2008 Trolltech ASA.
-
- You may use, distribute and copy the Qt GUI Toolkit under the terms of
- GNU General Public License version 2, which is displayed below.
-
--------------------------------------------------------------------------
-
-                   GNU GENERAL PUBLIC LICENSE
-                      Version 2, June 1991
-
- Copyright (C) 1989, 1991 Free Software Foundation, Inc.
- 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
- Everyone is permitted to copy and distribute verbatim copies
- of this license document, but changing it is not allowed.
-
-                           Preamble
-
-  The licenses for most software are designed to take away your
-freedom to share and change it.  By contrast, the GNU General Public
-License is intended to guarantee your freedom to share and change free
-software--to make sure the software is free for all its users.  This
-General Public License applies to most of the Free Software
-Foundation's software and to any other program whose authors commit to
-using it.  (Some other Free Software Foundation software is covered by
-the GNU Library General Public License instead.)  You can apply it to
-your programs, too.
-
-  When we speak of free software, we are referring to freedom, not
-price.  Our General Public Licenses are designed to make sure that you
-have the freedom to distribute copies of free software (and charge for
-this service if you wish), that you receive source code or can get it
-if you want it, that you can change the software or use pieces of it
-in new free programs; and that you know you can do these things.
-
-  To protect your rights, we need to make restrictions that forbid
-anyone to deny you these rights or to ask you to surrender the rights.
-These restrictions translate to certain responsibilities for you if you
-distribute copies of the software, or if you modify it.
-
-  For example, if you distribute copies of such a program, whether
-gratis or for a fee, you must give the recipients all the rights that
-you have.  You must make sure that they, too, receive or can get the
-source code.  And you must show them these terms so they know their
-rights.
-
-  We protect your rights with two steps: (1) copyright the software, and
-(2) offer you this license which gives you legal permission to copy,
-distribute and/or modify the software.
-
-  Also, for each author's protection and ours, we want to make certain
-that everyone understands that there is no warranty for this free
-software.  If the software is modified by someone else and passed on, we
-want its recipients to know that what they have is not the original, so
-that any problems introduced by others will not reflect on the original
-authors' reputations.
-
-  Finally, any free program is threatened constantly by software
-patents.  We wish to avoid the danger that redistributors of a free
-program will individually obtain patent licenses, in effect making the
-program proprietary.  To prevent this, we have made it clear that any
-patent must be licensed for everyone's free use or not licensed at all.
-
-  The precise terms and conditions for copying, distribution and
-modification follow.
-\f
-                   GNU GENERAL PUBLIC LICENSE
-   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
-
-  0. This License applies to any program or other work which contains
-a notice placed by the copyright holder saying it may be distributed
-under the terms of this General Public License.  The "Program", below,
-refers to any such program or work, and a "work based on the Program"
-means either the Program or any derivative work under copyright law:
-that is to say, a work containing the Program or a portion of it,
-either verbatim or with modifications and/or translated into another
-language.  (Hereinafter, translation is included without limitation in
-the term "modification".)  Each licensee is addressed as "you".
-
-Activities other than copying, distribution and modification are not
-covered by this License; they are outside its scope.  The act of
-running the Program is not restricted, and the output from the Program
-is covered only if its contents constitute a work based on the
-Program (independent of having been made by running the Program).
-Whether that is true depends on what the Program does.
-
-  1. You may copy and distribute verbatim copies of the Program's
-source code as you receive it, in any medium, provided that you
-conspicuously and appropriately publish on each copy an appropriate
-copyright notice and disclaimer of warranty; keep intact all the
-notices that refer to this License and to the absence of any warranty;
-and give any other recipients of the Program a copy of this License
-along with the Program.
-
-You may charge a fee for the physical act of transferring a copy, and
-you may at your option offer warranty protection in exchange for a fee.
-
-  2. You may modify your copy or copies of the Program or any portion
-of it, thus forming a work based on the Program, and copy and
-distribute such modifications or work under the terms of Section 1
-above, provided that you also meet all of these conditions:
-
-    a) You must cause the modified files to carry prominent notices
-    stating that you changed the files and the date of any change.
-
-    b) You must cause any work that you distribute or publish, that in
-    whole or in part contains or is derived from the Program or any
-    part thereof, to be licensed as a whole at no charge to all third
-    parties under the terms of this License.
-
-    c) If the modified program normally reads commands interactively
-    when run, you must cause it, when started running for such
-    interactive use in the most ordinary way, to print or display an
-    announcement including an appropriate copyright notice and a
-    notice that there is no warranty (or else, saying that you provide
-    a warranty) and that users may redistribute the program under
-    these conditions, and telling the user how to view a copy of this
-    License.  (Exception: if the Program itself is interactive but
-    does not normally print such an announcement, your work based on
-    the Program is not required to print an announcement.)
-\f
-These requirements apply to the modified work as a whole.  If
-identifiable sections of that work are not derived from the Program,
-and can be reasonably considered independent and separate works in
-themselves, then this License, and its terms, do not apply to those
-sections when you distribute them as separate works.  But when you
-distribute the same sections as part of a whole which is a work based
-on the Program, the distribution of the whole must be on the terms of
-this License, whose permissions for other licensees extend to the
-entire whole, and thus to each and every part regardless of who wrote it.
-
-Thus, it is not the intent of this section to claim rights or contest
-your rights to work written entirely by you; rather, the intent is to
-exercise the right to control the distribution of derivative or
-collective works based on the Program.
-
-In addition, mere aggregation of another work not based on the Program
-with the Program (or with a work based on the Program) on a volume of
-a storage or distribution medium does not bring the other work under
-the scope of this License.
-
-  3. You may copy and distribute the Program (or a work based on it,
-under Section 2) in object code or executable form under the terms of
-Sections 1 and 2 above provided that you also do one of the following:
-
-    a) Accompany it with the complete corresponding machine-readable
-    source code, which must be distributed under the terms of Sections
-    1 and 2 above on a medium customarily used for software interchange; or,
-
-    b) Accompany it with a written offer, valid for at least three
-    years, to give any third party, for a charge no more than your
-    cost of physically performing source distribution, a complete
-    machine-readable copy of the corresponding source code, to be
-    distributed under the terms of Sections 1 and 2 above on a medium
-    customarily used for software interchange; or,
-
-    c) Accompany it with the information you received as to the offer
-    to distribute corresponding source code.  (This alternative is
-    allowed only for noncommercial distribution and only if you
-    received the program in object code or executable form with such
-    an offer, in accord with Subsection b above.)
-
-The source code for a work means the preferred form of the work for
-making modifications to it.  For an executable work, complete source
-code means all the source code for all modules it contains, plus any
-associated interface definition files, plus the scripts used to
-control compilation and installation of the executable.  However, as a
-special exception, the source code distributed need not include
-anything that is normally distributed (in either source or binary
-form) with the major components (compiler, kernel, and so on) of the
-operating system on which the executable runs, unless that component
-itself accompanies the executable.
-
-If distribution of executable or object code is made by offering
-access to copy from a designated place, then offering equivalent
-access to copy the source code from the same place counts as
-distribution of the source code, even though third parties are not
-compelled to copy the source along with the object code.
-\f
-  4. You may not copy, modify, sublicense, or distribute the Program
-except as expressly provided under this License.  Any attempt
-otherwise to copy, modify, sublicense or distribute the Program is
-void, and will automatically terminate your rights under this License.
-However, parties who have received copies, or rights, from you under
-this License will not have their licenses terminated so long as such
-parties remain in full compliance.
-
-  5. You are not required to accept this License, since you have not
-signed it.  However, nothing else grants you permission to modify or
-distribute the Program or its derivative works.  These actions are
-prohibited by law if you do not accept this License.  Therefore, by
-modifying or distributing the Program (or any work based on the
-Program), you indicate your acceptance of this License to do so, and
-all its terms and conditions for copying, distributing or modifying
-the Program or works based on it.
-
-  6. Each time you redistribute the Program (or any work based on the
-Program), the recipient automatically receives a license from the
-original licensor to copy, distribute or modify the Program subject to
-these terms and conditions.  You may not impose any further
-restrictions on the recipients' exercise of the rights granted herein.
-You are not responsible for enforcing compliance by third parties to
-this License.
-
-  7. If, as a consequence of a court judgment or allegation of patent
-infringement or for any other reason (not limited to patent issues),
-conditions are imposed on you (whether by court order, agreement or
-otherwise) that contradict the conditions of this License, they do not
-excuse you from the conditions of this License.  If you cannot
-distribute so as to satisfy simultaneously your obligations under this
-License and any other pertinent obligations, then as a consequence you
-may not distribute the Program at all.  For example, if a patent
-license would not permit royalty-free redistribution of the Program by
-all those who receive copies directly or indirectly through you, then
-the only way you could satisfy both it and this License would be to
-refrain entirely from distribution of the Program.
-
-If any portion of this section is held invalid or unenforceable under
-any particular circumstance, the balance of the section is intended to
-apply and the section as a whole is intended to apply in other
-circumstances.
-
-It is not the purpose of this section to induce you to infringe any
-patents or other property right claims or to contest validity of any
-such claims; this section has the sole purpose of protecting the
-integrity of the free software distribution system, which is
-implemented by public license practices.  Many people have made
-generous contributions to the wide range of software distributed
-through that system in reliance on consistent application of that
-system; it is up to the author/donor to decide if he or she is willing
-to distribute software through any other system and a licensee cannot
-impose that choice.
-
-This section is intended to make thoroughly clear what is believed to
-be a consequence of the rest of this License.
-\f
-  8. If the distribution and/or use of the Program is restricted in
-certain countries either by patents or by copyrighted interfaces, the
-original copyright holder who places the Program under this License
-may add an explicit geographical distribution limitation excluding
-those countries, so that distribution is permitted only in or among
-countries not thus excluded.  In such case, this License incorporates
-the limitation as if written in the body of this License.
-
-  9. The Free Software Foundation may publish revised and/or new versions
-of the General Public License from time to time.  Such new versions will
-be similar in spirit to the present version, but may differ in detail to
-address new problems or concerns.
-
-Each version is given a distinguishing version number.  If the Program
-specifies a version number of this License which applies to it and "any
-later version", you have the option of following the terms and conditions
-either of that version or of any later version published by the Free
-Software Foundation.  If the Program does not specify a version number of
-this License, you may choose any version ever published by the Free Software
-Foundation.
-
-  10. If you wish to incorporate parts of the Program into other free
-programs whose distribution conditions are different, write to the author
-to ask for permission.  For software which is copyrighted by the Free
-Software Foundation, write to the Free Software Foundation; we sometimes
-make exceptions for this.  Our decision will be guided by the two goals
-of preserving the free status of all derivatives of our free software and
-of promoting the sharing and reuse of software generally.
-
-                           NO WARRANTY
-
-  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
-FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
-OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
-PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
-OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
-MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
-TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
-PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
-REPAIR OR CORRECTION.
-
-  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
-WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
-REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
-INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
-OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
-TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
-YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
-PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
-POSSIBILITY OF SUCH DAMAGES.
-
-                    END OF TERMS AND CONDITIONS
-\f
-           How to Apply These Terms to Your New Programs
-
-  If you develop a new program, and you want it to be of the greatest
-possible use to the public, the best way to achieve this is to make it
-free software which everyone can redistribute and change under these terms.
-
-  To do so, attach the following notices to the program.  It is safest
-to attach them to the start of each source file to most effectively
-convey the exclusion of warranty; and each file should have at least
-the "copyright" line and a pointer to where the full notice is found.
-
-    <one line to give the program's name and a brief idea of what it does.>
-    Copyright (C) <year>  <name of author>
-
-    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 St, Fifth Floor, Boston, MA  02110-1301  USA
-
-
-Also add information on how to contact you by electronic and paper mail.
-
-If the program is interactive, make it output a short notice like this
-when it starts in an interactive mode:
-
-    Gnomovision version 69, Copyright (C) year name of author
-    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
-    This is free software, and you are welcome to redistribute it
-    under certain conditions; type `show c' for details.
-
-The hypothetical commands `show w' and `show c' should show the appropriate
-parts of the General Public License.  Of course, the commands you use may
-be called something other than `show w' and `show c'; they could even be
-mouse-clicks or menu items--whatever suits your program.
-
-You should also get your employer (if you work as a programmer) or your
-school, if any, to sign a "copyright disclaimer" for the program, if
-necessary.  Here is a sample; alter the names:
-
-  Yoyodyne, Inc., hereby disclaims all copyright interest in the program
-  `Gnomovision' (which makes passes at compilers) written by James Hacker.
-
-  <signature of Ty Coon>, 1 April 1989
-  Ty Coon, President of Vice
-
-This General Public License does not permit incorporating your program into
-proprietary programs.  If your program is a subroutine library, you may
-consider it more useful to permit linking proprietary applications with the
-library.  If this is what you want to do, use the GNU Library General
-Public License instead of this License.
-
--------------------------------------------------------------------------
-
-In addition, as a special exception, Trolltech gives permission to link the
-code of its release of Qt with the OpenSSL project's "OpenSSL" library (or
-modified versions of it that use the same license as the "OpenSSL"
-library), and distribute the linked executables. You must comply with the GNU
-General Public License version 2 or the GNU General Public License version 3
-in all respects for all of the code used other than the "OpenSSL" code.  If
-you modify this file, you may extend this exception to your version of the
-file, but you are not obligated to do so.  If you do not wish to do so,
-delete this exception statement from your version of this file.
diff --git a/extern/carve/LICENSE.GPL3 b/extern/carve/LICENSE.GPL3
deleted file mode 100644 (file)
index 94a9ed0..0000000
+++ /dev/null
@@ -1,674 +0,0 @@
-                    GNU GENERAL PUBLIC LICENSE
-                       Version 3, 29 June 2007
-
- Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>
- Everyone is permitted to copy and distribute verbatim copies
- of this license document, but changing it is not allowed.
-
-                            Preamble
-
-  The GNU General Public License is a free, copyleft license for
-software and other kinds of works.
-
-  The licenses for most software and other practical works are designed
-to take away your freedom to share and change the works.  By contrast,
-the GNU General Public License is intended to guarantee your freedom to
-share and change all versions of a program--to make sure it remains free
-software for all its users.  We, the Free Software Foundation, use the
-GNU General Public License for most of our software; it applies also to
-any other work released this way by its authors.  You can apply it to
-your programs, too.
-
-  When we speak of free software, we are referring to freedom, not
-price.  Our General Public Licenses are designed to make sure that you
-have the freedom to distribute copies of free software (and charge for
-them if you wish), that you receive source code or can get it if you
-want it, that you can change the software or use pieces of it in new
-free programs, and that you know you can do these things.
-
-  To protect your rights, we need to prevent others from denying you
-these rights or asking you to surrender the rights.  Therefore, you have
-certain responsibilities if you distribute copies of the software, or if
-you modify it: responsibilities to respect the freedom of others.
-
-  For example, if you distribute copies of such a program, whether
-gratis or for a fee, you must pass on to the recipients the same
-freedoms that you received.  You must make sure that they, too, receive
-or can get the source code.  And you must show them these terms so they
-know their rights.
-
-  Developers that use the GNU GPL protect your rights with two steps:
-(1) assert copyright on the software, and (2) offer you this License
-giving you legal permission to copy, distribute and/or modify it.
-
-  For the developers' and authors' protection, the GPL clearly explains
-that there is no warranty for this free software.  For both users' and
-authors' sake, the GPL requires that modified versions be marked as
-changed, so that their problems will not be attributed erroneously to
-authors of previous versions.
-
-  Some devices are designed to deny users access to install or run
-modified versions of the software inside them, although the manufacturer
-can do so.  This is fundamentally incompatible with the aim of
-protecting users' freedom to change the software.  The systematic
-pattern of such abuse occurs in the area of products for individuals to
-use, which is precisely where it is most unacceptable.  Therefore, we
-have designed this version of the GPL to prohibit the practice for those
-products.  If such problems arise substantially in other domains, we
-stand ready to extend this provision to those domains in future versions
-of the GPL, as needed to protect the freedom of users.
-
-  Finally, every program is threatened constantly by software patents.
-States should not allow patents to restrict development and use of
-software on general-purpose computers, but in those that do, we wish to
-avoid the special danger that patents applied to a free program could
-make it effectively proprietary.  To prevent this, the GPL assures that
-patents cannot be used to render the program non-free.
-
-  The precise terms and conditions for copying, distribution and
-modification follow.
-
-                       TERMS AND CONDITIONS
-
-  0. Definitions.
-
-  "This License" refers to version 3 of the GNU General Public License.
-
-  "Copyright" also means copyright-like laws that apply to other kinds of
-works, such as semiconductor masks.
-
-  "The Program" refers to any copyrightable work licensed under this
-License.  Each licensee is addressed as "you".  "Licensees" and
-"recipients" may be individuals or organizations.
-
-  To "modify" a work means to copy from or adapt all or part of the work
-in a fashion requiring copyright permission, other than the making of an
-exact copy.  The resulting work is called a "modified version" of the
-earlier work or a work "based on" the earlier work.
-
-  A "covered work" means either the unmodified Program or a work based
-on the Program.
-
-  To "propagate" a work means to do anything with it that, without
-permission, would make you directly or secondarily liable for
-infringement under applicable copyright law, except executing it on a
-computer or modifying a private copy.  Propagation includes copying,
-distribution (with or without modification), making available to the
-public, and in some countries other activities as well.
-
-  To "convey" a work means any kind of propagation that enables other
-parties to make or receive copies.  Mere interaction with a user through
-a computer network, with no transfer of a copy, is not conveying.
-
-  An interactive user interface displays "Appropriate Legal Notices"
-to the extent that it includes a convenient and prominently visible
-feature that (1) displays an appropriate copyright notice, and (2)
-tells the user that there is no warranty for the work (except to the
-extent that warranties are provided), that licensees may convey the
-work under this License, and how to view a copy of this License.  If
-the interface presents a list of user commands or options, such as a
-menu, a prominent item in the list meets this criterion.
-
-  1. Source Code.
-
-  The "source code" for a work means the preferred form of the work
-for making modifications to it.  "Object code" means any non-source
-form of a work.
-
-  A "Standard Interface" means an interface that either is an official
-standard defined by a recognized standards body, or, in the case of
-interfaces specified for a particular programming language, one that
-is widely used among developers working in that language.
-
-  The "System Libraries" of an executable work include anything, other
-than the work as a whole, that (a) is included in the normal form of
-packaging a Major Component, but which is not part of that Major
-Component, and (b) serves only to enable use of the work with that
-Major Component, or to implement a Standard Interface for which an
-implementation is available to the public in source code form.  A
-"Major Component", in this context, means a major essential component
-(kernel, window system, and so on) of the specific operating system
-(if any) on which the executable work runs, or a compiler used to
-produce the work, or an object code interpreter used to run it.
-
-  The "Corresponding Source" for a work in object code form means all
-the source code needed to generate, install, and (for an executable
-work) run the object code and to modify the work, including scripts to
-control those activities.  However, it does not include the work's
-System Libraries, or general-purpose tools or generally available free
-programs which are used unmodified in performing those activities but
-which are not part of the work.  For example, Corresponding Source
-includes interface definition files associated with source files for
-the work, and the source code for shared libraries and dynamically
-linked subprograms that the work is specifically designed to require,
-such as by intimate data communication or control flow between those
-subprograms and other parts of the work.
-
-  The Corresponding Source need not include anything that users
-can regenerate automatically from other parts of the Corresponding
-Source.
-
-  The Corresponding Source for a work in source code form is that
-same work.
-
-  2. Basic Permissions.
-
-  All rights granted under this License are granted for the term of
-copyright on the Program, and are irrevocable provided the stated
-conditions are met.  This License explicitly affirms your unlimited
-permission to run the unmodified Program.  The output from running a
-covered work is covered by this License only if the output, given its
-content, constitutes a covered work.  This License acknowledges your
-rights of fair use or other equivalent, as provided by copyright law.
-
-  You may make, run and propagate covered works that you do not
-convey, without conditions so long as your license otherwise remains
-in force.  You may convey covered works to others for the sole purpose
-of having them make modifications exclusively for you, or provide you
-with facilities for running those works, provided that you comply with
-the terms of this License in conveying all material for which you do
-not control copyright.  Those thus making or running the covered works
-for you must do so exclusively on your behalf, under your direction
-and control, on terms that prohibit them from making any copies of
-your copyrighted material outside their relationship with you.
-
-  Conveying under any other circumstances is permitted solely under
-the conditions stated below.  Sublicensing is not allowed; section 10
-makes it unnecessary.
-
-  3. Protecting Users' Legal Rights From Anti-Circumvention Law.
-
-  No covered work shall be deemed part of an effective technological
-measure under any applicable law fulfilling obligations under article
-11 of the WIPO copyright treaty adopted on 20 December 1996, or
-similar laws prohibiting or restricting circumvention of such
-measures.
-
-  When you convey a covered work, you waive any legal power to forbid
-circumvention of technological measures to the extent such circumvention
-is effected by exercising rights under this License with respect to
-the covered work, and you disclaim any intention to limit operation or
-modification of the work as a means of enforcing, against the work's
-users, your or third parties' legal rights to forbid circumvention of
-technological measures.
-
-  4. Conveying Verbatim Copies.
-
-  You may convey verbatim copies of the Program's source code as you
-receive it, in any medium, provided that you conspicuously and
-appropriately publish on each copy an appropriate copyright notice;
-keep intact all notices stating that this License and any
-non-permissive terms added in accord with section 7 apply to the code;
-keep intact all notices of the absence of any warranty; and give all
-recipients a copy of this License along with the Program.
-
-  You may charge any price or no price for each copy that you convey,
-and you may offer support or warranty protection for a fee.
-
-  5. Conveying Modified Source Versions.
-
-  You may convey a work based on the Program, or the modifications to
-produce it from the Program, in the form of source code under the
-terms of section 4, provided that you also meet all of these conditions:
-
-    a) The work must carry prominent notices stating that you modified
-    it, and giving a relevant date.
-
-    b) The work must carry prominent notices stating that it is
-    released under this License and any conditions added under section
-    7.  This requirement modifies the requirement in section 4 to
-    "keep intact all notices".
-
-    c) You must license the entire work, as a whole, under this
-    License to anyone who comes into possession of a copy.  This
-    License will therefore apply, along with any applicable section 7
-    additional terms, to the whole of the work, and all its parts,
-    regardless of how they are packaged.  This License gives no
-    permission to license the work in any other way, but it does not
-    invalidate such permission if you have separately received it.
-
-    d) If the work has interactive user interfaces, each must display
-    Appropriate Legal Notices; however, if the Program has interactive
-    interfaces that do not display Appropriate Legal Notices, your
-    work need not make them do so.
-
-  A compilation of a covered work with other separate and independent
-works, which are not by their nature extensions of the covered work,
-and which are not combined with it such as to form a larger program,
-in or on a volume of a storage or distribution medium, is called an
-"aggregate" if the compilation and its resulting copyright are not
-used to limit the access or legal rights of the compilation's users
-beyond what the individual works permit.  Inclusion of a covered work
-in an aggregate does not cause this License to apply to the other
-parts of the aggregate.
-
-  6. Conveying Non-Source Forms.
-
-  You may convey a covered work in object code form under the terms
-of sections 4 and 5, provided that you also convey the
-machine-readable Corresponding Source under the terms of this License,
-in one of these ways:
-
-    a) Convey the object code in, or embodied in, a physical product
-    (including a physical distribution medium), accompanied by the
-    Corresponding Source fixed on a durable physical medium
-    customarily used for software interchange.
-
-    b) Convey the object code in, or embodied in, a physical product
-    (including a physical distribution medium), accompanied by a
-    written offer, valid for at least three years and valid for as
-    long as you offer spare parts or customer support for that product
-    model, to give anyone who possesses the object code either (1) a
-    copy of the Corresponding Source for all the software in the
-    product that is covered by this License, on a durable physical
-    medium customarily used for software interchange, for a price no
-    more than your reasonable cost of physically performing this
-    conveying of source, or (2) access to copy the
-    Corresponding Source from a network server at no charge.
-
-    c) Convey individual copies of the object code with a copy of the
-    written offer to provide the Corresponding Source.  This
-    alternative is allowed only occasionally and noncommercially, and
-    only if you received the object code with such an offer, in accord
-    with subsection 6b.
-
-    d) Convey the object code by offering access from a designated
-    place (gratis or for a charge), and offer equivalent access to the
-    Corresponding Source in the same way through the same place at no
-    further charge.  You need not require recipients to copy the
-    Corresponding Source along with the object code.  If the place to
-    copy the object code is a network server, the Corresponding Source
-    may be on a different server (operated by you or a third party)
-    that supports equivalent copying facilities, provided you maintain
-    clear directions next to the object code saying where to find the
-    Corresponding Source.  Regardless of what server hosts the
-    Corresponding Source, you remain obligated to ensure that it is
-    available for as long as needed to satisfy these requirements.
-
-    e) Convey the object code using peer-to-peer transmission, provided
-    you inform other peers where the object code and Corresponding
-    Source of the work are being offered to the general public at no
-    charge under subsection 6d.
-
-  A separable portion of the object code, whose source code is excluded
-from the Corresponding Source as a System Library, need not be
-included in conveying the object code work.
-
-  A "User Product" is either (1) a "consumer product", which means any
-tangible personal property which is normally used for personal, family,
-or household purposes, or (2) anything designed or sold for incorporation
-into a dwelling.  In determining whether a product is a consumer product,
-doubtful cases shall be resolved in favor of coverage.  For a particular
-product received by a particular user, "normally used" refers to a
-typical or common use of that class of product, regardless of the status
-of the particular user or of the way in which the particular user
-actually uses, or expects or is expected to use, the product.  A product
-is a consumer product regardless of whether the product has substantial
-commercial, industrial or non-consumer uses, unless such uses represent
-the only significant mode of use of the product.
-
-  "Installation Information" for a User Product means any methods,
-procedures, authorization keys, or other information required to install
-and execute modified versions of a covered work in that User Product from
-a modified version of its Corresponding Source.  The information must
-suffice to ensure that the continued functioning of the modified object
-code is in no case prevented or interfered with solely because
-modification has been made.
-
-  If you convey an object code work under this section in, or with, or
-specifically for use in, a User Product, and the conveying occurs as
-part of a transaction in which the right of possession and use of the
-User Product is transferred to the recipient in perpetuity or for a
-fixed term (regardless of how the transaction is characterized), the
-Corresponding Source conveyed under this section must be accompanied
-by the Installation Information.  But this requirement does not apply
-if neither you nor any third party retains the ability to install
-modified object code on the User Product (for example, the work has
-been installed in ROM).
-
-  The requirement to provide Installation Information does not include a
-requirement to continue to provide support service, warranty, or updates
-for a work that has been modified or installed by the recipient, or for
-the User Product in which it has been modified or installed.  Access to a
-network may be denied when the modification itself materially and
-adversely affects the operation of the network or violates the rules and
-protocols for communication across the network.
-
-  Corresponding Source conveyed, and Installation Information provided,
-in accord with this section must be in a format that is publicly
-documented (and with an implementation available to the public in
-source code form), and must require no special password or key for
-unpacking, reading or copying.
-
-  7. Additional Terms.
-
-  "Additional permissions" are terms that supplement the terms of this
-License by making exceptions from one or more of its conditions.
-Additional permissions that are applicable to the entire Program shall
-be treated as though they were included in this License, to the extent
-that they are valid under applicable law.  If additional permissions
-apply only to part of the Program, that part may be used separately
-under those permissions, but the entire Program remains governed by
-this License without regard to the additional permissions.
-
-  When you convey a copy of a covered work, you may at your option
-remove any additional permissions from that copy, or from any part of
-it.  (Additional permissions may be written to require their own
-removal in certain cases when you modify the work.)  You may place
-additional permissions on material, added by you to a covered work,
-for which you have or can give appropriate copyright permission.
-
-  Notwithstanding any other provision of this License, for material you
-add to a covered work, you may (if authorized by the copyright holders of
-that material) supplement the terms of this License with terms:
-
-    a) Disclaiming warranty or limiting liability differently from the
-    terms of sections 15 and 16 of this License; or
-
-    b) Requiring preservation of specified reasonable legal notices or
-    author attributions in that material or in the Appropriate Legal
-    Notices displayed by works containing it; or
-
-    c) Prohibiting misrepresentation of the origin of that material, or
-    requiring that modified versions of such material be marked in
-    reasonable ways as different from the original version; or
-
-    d) Limiting the use for publicity purposes of names of licensors or
-    authors of the material; or
-
-    e) Declining to grant rights under trademark law for use of some
-    trade names, trademarks, or service marks; or
-
-    f) Requiring indemnification of licensors and authors of that
-    material by anyone who conveys the material (or modified versions of
-    it) with contractual assumptions of liability to the recipient, for
-    any liability that these contractual assumptions directly impose on
-    those licensors and authors.
-
-  All other non-permissive additional terms are considered "further
-restrictions" within the meaning of section 10.  If the Program as you
-received it, or any part of it, contains a notice stating that it is
-governed by this License along with a term that is a further
-restriction, you may remove that term.  If a license document contains
-a further restriction but permits relicensing or conveying under this
-License, you may add to a covered work material governed by the terms
-of that license document, provided that the further restriction does
-not survive such relicensing or conveying.
-
-  If you add terms to a covered work in accord with this section, you
-must place, in the relevant source files, a statement of the
-additional terms that apply to those files, or a notice indicating
-where to find the applicable terms.
-
-  Additional terms, permissive or non-permissive, may be stated in the
-form of a separately written license, or stated as exceptions;
-the above requirements apply either way.
-
-  8. Termination.
-
-  You may not propagate or modify a covered work except as expressly
-provided under this License.  Any attempt otherwise to propagate or
-modify it is void, and will automatically terminate your rights under
-this License (including any patent licenses granted under the third
-paragraph of section 11).
-
-  However, if you cease all violation of this License, then your
-license from a particular copyright holder is reinstated (a)
-provisionally, unless and until the copyright holder explicitly and
-finally terminates your license, and (b) permanently, if the copyright
-holder fails to notify you of the violation by some reasonable means
-prior to 60 days after the cessation.
-
-  Moreover, your license from a particular copyright holder is
-reinstated permanently if the copyright holder notifies you of the
-violation by some reasonable means, this is the first time you have
-received notice of violation of this License (for any work) from that
-copyright holder, and you cure the violation prior to 30 days after
-your receipt of the notice.
-
-  Termination of your rights under this section does not terminate the
-licenses of parties who have received copies or rights from you under
-this License.  If your rights have been terminated and not permanently
-reinstated, you do not qualify to receive new licenses for the same
-material under section 10.
-
-  9. Acceptance Not Required for Having Copies.
-
-  You are not required to accept this License in order to receive or
-run a copy of the Program.  Ancillary propagation of a covered work
-occurring solely as a consequence of using peer-to-peer transmission
-to receive a copy likewise does not require acceptance.  However,
-nothing other than this License grants you permission to propagate or
-modify any covered work.  These actions infringe copyright if you do
-not accept this License.  Therefore, by modifying or propagating a
-covered work, you indicate your acceptance of this License to do so.
-
-  10. Automatic Licensing of Downstream Recipients.
-
-  Each time you convey a covered work, the recipient automatically
-receives a license from the original licensors, to run, modify and
-propagate that work, subject to this License.  You are not responsible
-for enforcing compliance by third parties with this License.
-
-  An "entity transaction" is a transaction transferring control of an
-organization, or substantially all assets of one, or subdividing an
-organization, or merging organizations.  If propagation of a covered
-work results from an entity transaction, each party to that
-transaction who receives a copy of the work also receives whatever
-licenses to the work the party's predecessor in interest had or could
-give under the previous paragraph, plus a right to possession of the
-Corresponding Source of the work from the predecessor in interest, if
-the predecessor has it or can get it with reasonable efforts.
-
-  You may not impose any further restrictions on the exercise of the
-rights granted or affirmed under this License.  For example, you may
-not impose a license fee, royalty, or other charge for exercise of
-rights granted under this License, and you may not initiate litigation
-(including a cross-claim or counterclaim in a lawsuit) alleging that
-any patent claim is infringed by making, using, selling, offering for
-sale, or importing the Program or any portion of it.
-
-  11. Patents.
-
-  A "contributor" is a copyright holder who authorizes use under this
-License of the Program or a work on which the Program is based.  The
-work thus licensed is called the contributor's "contributor version".
-
-  A contributor's "essential patent claims" are all patent claims
-owned or controlled by the contributor, whether already acquired or
-hereafter acquired, that would be infringed by some manner, permitted
-by this License, of making, using, or selling its contributor version,
-but do not include claims that would be infringed only as a
-consequence of further modification of the contributor version.  For
-purposes of this definition, "control" includes the right to grant
-patent sublicenses in a manner consistent with the requirements of
-this License.
-
-  Each contributor grants you a non-exclusive, worldwide, royalty-free
-patent license under the contributor's essential patent claims, to
-make, use, sell, offer for sale, import and otherwise run, modify and
-propagate the contents of its contributor version.
-
-  In the following three paragraphs, a "patent license" is any express
-agreement or commitment, however denominated, not to enforce a patent
-(such as an express permission to practice a patent or covenant not to
-sue for patent infringement).  To "grant" such a patent license to a
-party means to make such an agreement or commitment not to enforce a
-patent against the party.
-
-  If you convey a covered work, knowingly relying on a patent license,
-and the Corresponding Source of the work is not available for anyone
-to copy, free of charge and under the terms of this License, through a
-publicly available network server or other readily accessible means,
-then you must either (1) cause the Corresponding Source to be so
-available, or (2) arrange to deprive yourself of the benefit of the
-patent license for this particular work, or (3) arrange, in a manner
-consistent with the requirements of this License, to extend the patent
-license to downstream recipients.  "Knowingly relying" means you have
-actual knowledge that, but for the patent license, your conveying the
-covered work in a country, or your recipient's use of the covered work
-in a country, would infringe one or more identifiable patents in that
-country that you have reason to believe are valid.
-
-  If, pursuant to or in connection with a single transaction or
-arrangement, you convey, or propagate by procuring conveyance of, a
-covered work, and grant a patent license to some of the parties
-receiving the covered work authorizing them to use, propagate, modify
-or convey a specific copy of the covered work, then the patent license
-you grant is automatically extended to all recipients of the covered
-work and works based on it.
-
-  A patent license is "discriminatory" if it does not include within
-the scope of its coverage, prohibits the exercise of, or is
-conditioned on the non-exercise of one or more of the rights that are
-specifically granted under this License.  You may not convey a covered
-work if you are a party to an arrangement with a third party that is
-in the business of distributing software, under which you make payment
-to the third party based on the extent of your activity of conveying
-the work, and under which the third party grants, to any of the
-parties who would receive the covered work from you, a discriminatory
-patent license (a) in connection with copies of the covered work
-conveyed by you (or copies made from those copies), or (b) primarily
-for and in connection with specific products or compilations that
-contain the covered work, unless you entered into that arrangement,
-or that patent license was granted, prior to 28 March 2007.
-
-  Nothing in this License shall be construed as excluding or limiting
-any implied license or other defenses to infringement that may
-otherwise be available to you under applicable patent law.
-
-  12. No Surrender of Others' Freedom.
-
-  If conditions are imposed on you (whether by court order, agreement or
-otherwise) that contradict the conditions of this License, they do not
-excuse you from the conditions of this License.  If you cannot convey a
-covered work so as to satisfy simultaneously your obligations under this
-License and any other pertinent obligations, then as a consequence you may
-not convey it at all.  For example, if you agree to terms that obligate you
-to collect a royalty for further conveying from those to whom you convey
-the Program, the only way you could satisfy both those terms and this
-License would be to refrain entirely from conveying the Program.
-
-  13. Use with the GNU Affero General Public License.
-
-  Notwithstanding any other provision of this License, you have
-permission to link or combine any covered work with a work licensed
-under version 3 of the GNU Affero General Public License into a single
-combined work, and to convey the resulting work.  The terms of this
-License will continue to apply to the part which is the covered work,
-but the special requirements of the GNU Affero General Public License,
-section 13, concerning interaction through a network will apply to the
-combination as such.
-
-  14. Revised Versions of this License.
-
-  The Free Software Foundation may publish revised and/or new versions of
-the GNU General Public License from time to time.  Such new versions will
-be similar in spirit to the present version, but may differ in detail to
-address new problems or concerns.
-
-  Each version is given a distinguishing version number.  If the
-Program specifies that a certain numbered version of the GNU General
-Public License "or any later version" applies to it, you have the
-option of following the terms and conditions either of that numbered
-version or of any later version published by the Free Software
-Foundation.  If the Program does not specify a version number of the
-GNU General Public License, you may choose any version ever published
-by the Free Software Foundation.
-
-  If the Program specifies that a proxy can decide which future
-versions of the GNU General Public License can be used, that proxy's
-public statement of acceptance of a version permanently authorizes you
-to choose that version for the Program.
-
-  Later license versions may give you additional or different
-permissions.  However, no additional obligations are imposed on any
-author or copyright holder as a result of your choosing to follow a
-later version.
-
-  15. Disclaimer of Warranty.
-
-  THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY
-APPLICABLE LAW.  EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT
-HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY
-OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,
-THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
-PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM
-IS WITH YOU.  SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF
-ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
-
-  16. Limitation of Liability.
-
-  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
-WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS
-THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY
-GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
-USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF
-DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD
-PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS),
-EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF
-SUCH DAMAGES.
-
-  17. Interpretation of Sections 15 and 16.
-
-  If the disclaimer of warranty and limitation of liability provided
-above cannot be given local legal effect according to their terms,
-reviewing courts shall apply local law that most closely approximates
-an absolute waiver of all civil liability in connection with the
-Program, unless a warranty or assumption of liability accompanies a
-copy of the Program in return for a fee.
-
-                     END OF TERMS AND CONDITIONS
-
-            How to Apply These Terms to Your New Programs
-
-  If you develop a new program, and you want it to be of the greatest
-possible use to the public, the best way to achieve this is to make it
-free software which everyone can redistribute and change under these terms.
-
-  To do so, attach the following notices to the program.  It is safest
-to attach them to the start of each source file to most effectively
-state the exclusion of warranty; and each file should have at least
-the "copyright" line and a pointer to where the full notice is found.
-
-    <one line to give the program's name and a brief idea of what it does.>
-    Copyright (C) <year>  <name of author>
-
-    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 3 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, see <http://www.gnu.org/licenses/>.
-
-Also add information on how to contact you by electronic and paper mail.
-
-  If the program does terminal interaction, make it output a short
-notice like this when it starts in an interactive mode:
-
-    <program>  Copyright (C) <year>  <name of author>
-    This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
-    This is free software, and you are welcome to redistribute it
-    under certain conditions; type `show c' for details.
-
-The hypothetical commands `show w' and `show c' should show the appropriate
-parts of the General Public License.  Of course, your program's commands
-might be different; for a GUI interface, you would use an "about box".
-
-  You should also get your employer (if you work as a programmer) or school,
-if any, to sign a "copyright disclaimer" for the program, if necessary.
-For more information on this, and how to apply and follow the GNU GPL, see
-<http://www.gnu.org/licenses/>.
-
-  The GNU General Public License does not permit incorporating your program
-into proprietary programs.  If your program is a subroutine library, you
-may consider it more useful to permit linking proprietary applications with
-the library.  If this is what you want to do, use the GNU Lesser General
-Public License instead of this License.  But first, please read
-<http://www.gnu.org/philosophy/why-not-lgpl.html>.
diff --git a/extern/carve/README.blender b/extern/carve/README.blender
deleted file mode 100644 (file)
index 80be40a..0000000
+++ /dev/null
@@ -1,4 +0,0 @@
-Project: Carve, CSG library
-URL: https://code.google.com/archive/p/carve/
-Upstream version 9a85d733a43d
-Local modifications: See patches/ folder
diff --git a/extern/carve/bundle.sh b/extern/carve/bundle.sh
deleted file mode 100755 (executable)
index 00de08e..0000000
+++ /dev/null
@@ -1,105 +0,0 @@
-#!/bin/sh
-
-if [ "x$1" = "x--i-really-know-what-im-doing" ] ; then
-  echo Proceeding as requested by command line ...
-else
-  echo "*** Please run again with --i-really-know-what-im-doing ..."
-  exit 1
-fi
-
-tmp=`mktemp -d`
-
-hg clone https://code.google.com/p/carve/ $tmp/carve
-
-for p in `cat ./patches/series`; do
-  echo "Applying patch $p..."
-  cat ./patches/$p | patch -d $tmp/carve -p1
-done
-
-find include -type f -not -iwholename '*.svn*' -exec rm -rf {} \;
-find lib -type f -not -iwholename '*.svn*' -exec rm -rf {} \;
-
-cat "files.txt" | while read f; do
-  mkdir -p `dirname $f`
-  cp $tmp/carve/$f $f
-done
-
-rm -rf $tmp
-
-sources=`find ./lib -type f -iname '*.cc' -or -iname '*.cpp' -or -iname '*.c' | sed -r 's/^\.\//\t/' | sort -d`
-headers=`find ./lib -type f -iname '*.h' -or -iname '*.hpp' | sed -r 's/^\.\//\t/' | sort -d`
-includes=`find ./include -type f -iname '*.h' -or -iname '*.hpp' | sed -r 's/^\.\//\t/' | sort -d`
-
-cp patches/files/config.h include/carve/config.h
-mkdir -p include/carve/random
-cp patches/files/random.h include/carve/random/random.h
-
-cat > CMakeLists.txt << EOF
-# ***** 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 Beaurai, Erwin Coumans
-#
-# ***** END GPL LICENSE BLOCK *****
-
-# NOTE: This file is automatically generated by bundle.sh script
-#       If you're doing changes in this file, please update template
-#       in that script too
-
-set(INC
-       include
-)
-
-set(INC_SYS
-)
-
-set(SRC
-       carve-capi.cc
-       carve-util.cc
-${sources}
-
-       carve-capi.h
-       carve-util.h
-${headers}
-
-${includes}
-)
-
-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
-               -DHAVE_BOOST_LIBRARY
-       )
-
-       list(APPEND INC_SYS
-               \${BOOST_INCLUDE_DIR}
-       )
-endif()
-
-blender_add_lib(extern_carve "\${SRC}" "\${INC}" "\${INC_SYS}")
-EOF
diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc
deleted file mode 100644 (file)
index d6666a5..0000000
+++ /dev/null
@@ -1,994 +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) 2014 Blender Foundation.
- * All rights reserved.
- *
- * Contributor(s): Blender Foundation,
- *                 Sergey Sharybin
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-#include "carve-capi.h"
-#include "carve-util.h"
-
-#include <carve/interpolator.hpp>
-#include <carve/rescale.hpp>
-#include <carve/csg_triangulator.hpp>
-#include <carve/mesh_simplify.hpp>
-
-using carve::mesh::MeshSet;
-
-typedef std::pair<int, int> OrigIndex;
-typedef std::pair<MeshSet<3>::vertex_t *, MeshSet<3>::vertex_t *> VertexPair;
-typedef carve::interpolate::VertexAttr<OrigIndex> OrigVertMapping;
-typedef carve::interpolate::FaceAttr<OrigIndex> OrigFaceMapping;
-typedef carve::interpolate::SwapableFaceEdgeAttr<OrigIndex> OrigFaceEdgeMapping;
-typedef carve::interpolate::SimpleFaceEdgeAttr<bool> FaceEdgeTriangulatedFlag;
-
-typedef struct CarveMeshDescr {
-       // Stores mesh data itself.
-       MeshSet<3> *poly;
-
-       // N-th element of the vector indicates index of an original mesh loop.
-       std::unordered_map<std::pair<int, int>, int> orig_loop_index_map;
-
-       // Mapping from carve face to an original face index in DM.
-       std::unordered_map<const MeshSet<3>::face_t *, int> orig_poly_index_map;
-
-       // The folloving mapping is only filled in for output mesh.
-
-       // Mapping from the face verts back to original vert index.
-       OrigVertMapping orig_vert_mapping;
-
-       // Mapping from the face edges back to (original edge index, original loop index).
-       OrigFaceEdgeMapping orig_face_edge_mapping;
-
-       FaceEdgeTriangulatedFlag face_edge_triangulated_flag;
-
-       // Mapping from the faces back to original poly index.
-       OrigFaceMapping orig_face_mapping;
-} CarveMeshDescr;
-
-namespace {
-
-template <typename T1, typename T2>
-void edgeIndexMap_put(std::unordered_map<std::pair<T1, T1>, T2> *edge_map,
-                      const T1 &v1,
-                      const T1 &v2,
-                      const T2 &index)
-{
-       if (v1 < v2) {
-               (*edge_map)[std::make_pair(v1, v2)] = index;
-       }
-       else {
-               (*edge_map)[std::make_pair(v2, v1)] = index;
-       }
-}
-
-template <typename T1, typename T2>
-const T2 &edgeIndexMap_get(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
-                           const T1 &v1,
-                           const T1 &v2)
-{
-       typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
-       typename Map::const_iterator found;
-
-       if (v1 < v2) {
-               found = edge_map.find(std::make_pair(v1, v2));
-       }
-       else {
-               found = edge_map.find(std::make_pair(v2, v1));
-       }
-
-       assert(found != edge_map.end());
-       return found->second;
-}
-
-template <typename T1, typename T2>
-bool edgeIndexMap_get_if_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
-                                const T1 &v1,
-                                const T1 &v2,
-                                T2 *out)
-{
-       typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
-       typename Map::const_iterator found;
-
-       if (v1 < v2) {
-               found = edge_map.find(std::make_pair(v1, v2));
-       }
-       else {
-               found = edge_map.find(std::make_pair(v2, v1));
-       }
-
-       if (found == edge_map.end()) {
-               return false;
-       }
-       *out = found->second;
-       return true;
-}
-
-template <typename T1, typename T2>
-bool edgeIndexMap_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
-                         const T1 &v1,
-                         const T1 &v2)
-{
-       typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
-       typename Map::const_iterator found;
-
-       if (v1 < v2) {
-               found = edge_map.find(std::make_pair(v1, v2));
-       }
-       else {
-               found = edge_map.find(std::make_pair(v2, v1));
-       }
-
-       return found != edge_map.end();
-}
-
-template <typename T>
-inline int indexOf(const T *element, const std::vector<T> &vector_from)
-{
-       return element - &vector_from.at(0);
-}
-
-void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
-                                  int which_mesh,
-                                  std::unordered_map<std::pair<int, int>, int> &orig_loop_index_map,
-                                  std::unordered_map<const MeshSet<3>::face_t*, int> &orig_poly_index_map,
-                                  OrigVertMapping *orig_vert_mapping,
-                                  OrigFaceEdgeMapping *orig_face_edge_mapping,
-                                  FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
-                                  OrigFaceMapping *orig_face_attr)
-{
-       MeshSet<3> *poly = mesh->poly;
-
-       std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter =
-               poly->vertex_storage.begin();
-       for (int i = 0;
-            vertex_iter != poly->vertex_storage.end();
-            ++i, ++vertex_iter)
-       {
-               MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
-               orig_vert_mapping->setAttribute(vertex,
-                                               std::make_pair(which_mesh, i));
-       }
-
-       MeshSet<3>::face_iter face_iter = poly->faceBegin();
-       for (int i = 0, loop_map_index = 0;
-            face_iter != poly->faceEnd();
-            ++face_iter, ++i)
-       {
-               const MeshSet<3>::face_t *face = *face_iter;
-
-               // Mapping from carve face back to original poly index.
-               int orig_poly_index = orig_poly_index_map[face];
-               orig_face_attr->setAttribute(face, std::make_pair(which_mesh, orig_poly_index));
-
-               for (MeshSet<3>::face_t::const_edge_iter_t edge_iter = face->begin();
-                    edge_iter != face->end();
-                    ++edge_iter, ++loop_map_index)
-               {
-                       int v1 = indexOf(edge_iter->v1(), poly->vertex_storage);
-                       int v2 = indexOf(edge_iter->v2(), poly->vertex_storage);
-
-                       int orig_loop_index;
-                       if (!edgeIndexMap_get_if_exists(orig_loop_index_map,
-                                                       v1, v2,
-                                                       &orig_loop_index))
-                       {
-                               orig_loop_index = -1;
-                       }
-
-                       if (orig_loop_index != -1) {
-                               // Mapping from carve face edge back to original loop index.
-                               orig_face_edge_mapping->setAttribute(face,
-                                                                    edge_iter.idx(),
-                                                                    std::make_pair(which_mesh,
-                                                                                   orig_loop_index));
-                       }
-                       else {
-                               face_edge_triangulated_flag->setAttribute(face,
-                                                                         edge_iter.idx(),
-                                                                         true);
-                       }
-               }
-       }
-}
-
-void initOrigIndexMapping(CarveMeshDescr *left_mesh,
-                          CarveMeshDescr *right_mesh,
-                          OrigVertMapping *orig_vert_mapping,
-                          OrigFaceEdgeMapping *orig_face_edge_mapping,
-                          FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
-                          OrigFaceMapping *orig_face_mapping)
-{
-       initOrigIndexMeshFaceMapping(left_mesh,
-                                    CARVE_MESH_LEFT,
-                                    left_mesh->orig_loop_index_map,
-                                    left_mesh->orig_poly_index_map,
-                                    orig_vert_mapping,
-                                    orig_face_edge_mapping,
-                                    face_edge_triangulated_flag,
-                                    orig_face_mapping);
-
-       initOrigIndexMeshFaceMapping(right_mesh,
-                                    CARVE_MESH_RIGHT,
-                                    right_mesh->orig_loop_index_map,
-                                    right_mesh->orig_poly_index_map,
-                                    orig_vert_mapping,
-                                    orig_face_edge_mapping,
-                                    face_edge_triangulated_flag,
-                                    orig_face_mapping);
-}
-
-void origEdgeMappingForFace(MeshSet<3>::face_t *face,
-                            OrigFaceEdgeMapping *orig_face_edge_mapping,
-                            std::unordered_map<VertexPair, OrigIndex> *edge_origindex_map)
-{
-       OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
-
-       MeshSet<3>::edge_t *edge = face->edge;
-       for (int i = 0;
-            i < face->nEdges();
-            ++i, edge = edge->next)
-       {
-               MeshSet<3>::vertex_t *v1 = edge->v1();
-               MeshSet<3>::vertex_t *v2 = edge->v2();
-
-               OrigIndex orig_edge_index =
-                       orig_face_edge_mapping->getAttribute(edge->face, i, origindex_none);
-
-               edgeIndexMap_put(edge_origindex_map, v1, v2, orig_edge_index);
-       }
-}
-
-void dissolveTriangulatedEdges(MeshSet<3>::mesh_t *mesh,
-                               const std::set< std::pair<int, int> > &open_edges,
-                               FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
-                               OrigFaceEdgeMapping *orig_face_edge_mapping)
-{
-       typedef std::unordered_set<MeshSet<3>::edge_t *> edge_set_t;
-       typedef std::unordered_set<MeshSet<3>::face_t *> face_set_t;
-       edge_set_t triangulated_face_edges;
-
-       for (int face_index = 0; face_index < mesh->faces.size(); ++face_index) {
-               MeshSet<3>::face_t *face = mesh->faces[face_index];
-               MeshSet<3>::edge_t *edge = face->edge;
-               for (int edge_index = 0;
-                    edge_index < face->nEdges();
-                    ++edge_index, edge = edge->next)
-               {
-                       if (edge->rev) {
-                               const bool is_triangulated_edge =
-                                       face_edge_triangulated_flag->getAttribute(face,
-                                                                                 edge_index,
-                                                                                 false);
-                               if (is_triangulated_edge) {
-                                       MeshSet<3>::edge_t *e1 = std::min(edge, edge->rev);
-                                       int v1 = indexOf(e1->v1(), mesh->meshset->vertex_storage),
-                                           v2 = indexOf(e1->v2(), mesh->meshset->vertex_storage);
-
-                                       bool is_open = false;
-                                       if (v1 < v2) {
-                                               is_open = open_edges.find(std::make_pair(v1, v2)) != open_edges.end();
-                                       }
-                                       else {
-                                               is_open = open_edges.find(std::make_pair(v2, v1)) != open_edges.end();
-                                       }
-
-                                       if (is_open == false) {
-                                               triangulated_face_edges.insert(e1);
-                                       }
-                               }
-                       }
-               }
-       }
-
-       if (triangulated_face_edges.size()) {
-               face_set_t triangulated_faces;
-               std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
-
-               for (edge_set_t::iterator it = triangulated_face_edges.begin();
-                    it != triangulated_face_edges.end();
-                    ++it)
-               {
-                       MeshSet<3>::edge_t *edge = *it;
-
-                       origEdgeMappingForFace(edge->face,
-                                              orig_face_edge_mapping,
-                                              &edge_origindex_map);
-                       triangulated_faces.insert(edge->face);
-
-                       origEdgeMappingForFace(edge->rev->face,
-                                              orig_face_edge_mapping,
-                                              &edge_origindex_map);
-                       triangulated_faces.insert(edge->rev->face);
-               }
-
-               carve::mesh::MeshSimplifier simplifier;
-               simplifier.dissolveMeshEdges(mesh, triangulated_face_edges);
-
-               for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
-                       MeshSet<3>::face_t *face = mesh->faces[face_index];
-
-                       if (triangulated_faces.find(face) != triangulated_faces.end()) {
-                               MeshSet<3>::edge_t *edge = face->edge;
-                               for (int edge_index = 0;
-                                    edge_index < face->nEdges();
-                                    ++edge_index, edge = edge->next)
-                               {
-                                       MeshSet<3>::vertex_t *v1 = edge->v1();
-                                       MeshSet<3>::vertex_t *v2 = edge->v2();
-
-                                       OrigIndex orig_edge_index =
-                                               edgeIndexMap_get(edge_origindex_map,
-                                                                v1,
-                                                                v2);
-
-                                       orig_face_edge_mapping->setAttribute(face, edge_index, orig_edge_index);
-                               }
-                       }
-               }
-       }
-}
-
-void dissolveTriangulatedEdges(CarveMeshDescr *mesh_descr)
-{
-       MeshSet<3> *poly = mesh_descr->poly;
-       FaceEdgeTriangulatedFlag *face_edge_triangulated_flag =
-               &mesh_descr->face_edge_triangulated_flag;
-
-       std::set< std::pair<int, int> > open_edges;
-       for (int mesh_index = 0;
-            mesh_index < poly->meshes.size();
-            ++mesh_index)
-       {
-               const MeshSet<3>::mesh_t *mesh = poly->meshes[mesh_index];
-               for (int edge_index = 0;
-                    edge_index < mesh->open_edges.size();
-                    ++edge_index)
-               {
-                       const MeshSet<3>::edge_t *edge = mesh->open_edges[edge_index];
-                       int v1 = indexOf(edge->v1(), poly->vertex_storage),
-                           v2 = indexOf(edge->v2(), poly->vertex_storage);
-                       if (v1 < v2) {
-                               open_edges.insert(std::make_pair(v1, v2));
-                       }
-                       else {
-                               open_edges.insert(std::make_pair(v2, v1));
-                       }
-               }
-       }
-
-       for (int mesh_index = 0; mesh_index < poly->meshes.size(); ++mesh_index) {
-               MeshSet<3>::mesh_t *mesh = poly->meshes[mesh_index];
-               dissolveTriangulatedEdges(mesh,
-                                         open_edges,
-                                         face_edge_triangulated_flag,
-                                         &mesh_descr->orig_face_edge_mapping);
-       }
-}
-
-void clipEar(MeshSet<3>::edge_t *ear)
-{
-       MeshSet<3>::edge_t *p_edge = ear->prev;
-       MeshSet<3>::edge_t *n_edge = ear->next;
-
-       p_edge->next = n_edge;
-       n_edge->prev = p_edge;
-
-       if (ear->face->edge == ear) {
-               ear->face->edge = n_edge;
-       }
-       ear->face->n_edges--;
-
-       delete ear;
-}
-
-MeshSet<3>::edge_t *findDegenerateEar(MeshSet<3>::face_t *face)
-{
-       for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
-            edge_iter != face->end();
-            ++edge_iter)
-       {
-               MeshSet<3>::edge_t &edge = *edge_iter;
-               if (edge.vert == edge.next->next->vert) {
-                       return edge.next->next;
-               }
-       }
-       return NULL;
-}
-
-class EarClipper : public carve::csg::CSG::Hook {
-public:
-       virtual ~EarClipper() {
-       }
-
-       virtual void processOutputFace(std::vector<MeshSet<3>::face_t *> &faces,
-                                      const MeshSet<3>::face_t *orig,
-                                      bool flipped) {
-               for (size_t face_index = 0; face_index < faces.size(); ++face_index) {
-                       carve::mesh::MeshSet<3>::face_t *face = faces[face_index];
-
-                       // There's no ears in quads and tris.
-                       if (face->nVertices() <= 4) {
-                               continue;
-                       }
-
-                       MeshSet<3>::edge_t *ear;
-                       while ((ear = findDegenerateEar(face)) != NULL) {
-                               clipEar(ear);
-                       }
-
-               }
-       }
-};
-
-class HoleResolver : public carve::csg::CarveHoleResolver {
-
-       void removeDuplicatedFaces(std::vector<MeshSet<3>::face_t *> &faces) {
-               std::vector<MeshSet<3>::face_t *> out_faces;
-               std::vector<MeshSet<3>::face_t *> duplicated_faces;
-
-               for (size_t face_index = 0; face_index < faces.size(); ++face_index) {
-                       carve::mesh::MeshSet<3>::face_t *face = faces[face_index];
-                       face->canonicalize();
-               }
-
-               for (size_t i = 0; i < faces.size(); ++i) {
-                       carve::mesh::MeshSet<3>::face_t *face = faces[i];
-
-                       bool found = false;
-                       for (size_t j = i + 1; j < faces.size() && found == false; ++j) {
-                               MeshSet<3>::face_t *cur_face = faces[j];
-                               if (cur_face->nEdges() == face->nEdges() &&
-                                   cur_face->edge->vert == face->edge->vert)
-                               {
-
-                                       MeshSet<3>::edge_t *cur_edge = cur_face->edge,
-                                                          *forward_edge = face->edge,
-                                                          *backward_edge = face->edge;
-                                       bool forward_matches = true, backward_matches = true;
-
-                                       for (int a = 0; a < cur_face->nEdges(); ++a) {
-                                               if (forward_edge->vert != cur_edge->vert) {
-                                                       forward_matches = false;
-                                                       if (backward_matches == false) {
-                                                               break;
-                                                       }
-                                               }
-
-                                               if (backward_edge->vert != cur_edge->vert) {
-                                                       backward_matches = false;
-                                                       if (forward_matches == false) {
-                                                               break;
-                                                       }
-                                               }
-
-                                               cur_edge = cur_edge->next;
-                                               forward_edge = forward_edge->next;
-                                               backward_edge = backward_edge->prev;
-                                       }
-
-                                       if (forward_matches || backward_matches) {
-                                               found = true;
-                                               break;
-                                       }
-                               }
-                       }
-
-                       if (found) {
-                               duplicated_faces.push_back(face);
-                       }
-                       else {
-                               out_faces.push_back(face);
-                       }
-               }
-
-               for (int i = 0; i < duplicated_faces.size(); ++i) {
-                       delete duplicated_faces[i];
-               }
-
-               std::swap(faces, out_faces);
-       }
-
-public:
-       virtual ~HoleResolver() {
-       }
-
-       virtual void processOutputFace(std::vector<MeshSet<3>::face_t *> &faces,
-                                      const MeshSet<3>::face_t *orig,
-                                      bool flipped) {
-               carve::csg::CarveHoleResolver::processOutputFace(faces, orig, flipped);
-               if (faces.size() > 1) {
-                       removeDuplicatedFaces(faces);
-               }
-       }
-};
-
-template <typename Interpolator>
-void copyFaceEdgeAttrs(const MeshSet<3> *poly,
-                       Interpolator *old_interpolator,
-                       Interpolator *new_interpolator)
-{
-       for (MeshSet<3>::const_face_iter face_iter = poly->faceBegin();
-            face_iter != poly->faceEnd();
-            ++face_iter)
-       {
-               const MeshSet<3>::face_t *face = *face_iter;
-
-               for (int edge_index = 0;
-                    edge_index < face->nEdges();
-                    ++edge_index)
-               {
-                       new_interpolator->copyAttribute(face,
-                                                       edge_index,
-                                                       old_interpolator);
-               }
-       }
-}
-
-template <typename Interpolator>
-void cleanupFaceEdgeAttrs(const MeshSet<3> *left,
-                          const MeshSet<3> *right,
-                          Interpolator *interpolator)
-{
-       Interpolator new_interpolator;
-       copyFaceEdgeAttrs(left, interpolator, &new_interpolator);
-       copyFaceEdgeAttrs(right, interpolator, &new_interpolator);
-       interpolator->swapAttributes(&new_interpolator);
-}
-
-void cleanupFaceEdgeAttrsCallback(const MeshSet<3> *left,
-                                  const MeshSet<3> *right,
-                                  void *descr_v)
-{
-       CarveMeshDescr *descr = (CarveMeshDescr *) descr_v;
-       cleanupFaceEdgeAttrs(left,
-                            right,
-                            &descr->face_edge_triangulated_flag);
-       cleanupFaceEdgeAttrs(left,
-                            right,
-                            &descr->orig_face_edge_mapping);
-}
-
-void copyVertexAttrsCallback(const carve::mesh::MeshSet<3>::vertex_t *orig_vert,
-                             const carve::mesh::MeshSet<3>::vertex_t *new_vert,
-                             void *descr_v)
-{
-       CarveMeshDescr *descr = (CarveMeshDescr *) descr_v;
-       if (!descr->orig_vert_mapping.hasAttribute(orig_vert)) {
-               return;
-       }
-       if (descr->orig_vert_mapping.hasAttribute(new_vert)) {
-               return;
-       }
-       OrigIndex attr = descr->orig_vert_mapping.getAttribute(orig_vert);
-       descr->orig_vert_mapping.setAttribute(new_vert, attr);
-       descr->orig_vert_mapping.removeAttribute(orig_vert);
-}
-
-}  // namespace
-
-CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
-                              CarveMeshImporter *mesh_importer)
-{
-#define MAX_STATIC_VERTS 64
-
-       CarveMeshDescr *mesh_descr = new CarveMeshDescr;
-
-       // Import verices from external mesh to Carve.
-       int num_verts = mesh_importer->getNumVerts(import_data);
-       std::vector<MeshSet<3>::vertex_t> vertex_storage;
-       vertex_storage.reserve(num_verts);
-       for (int i = 0; i < num_verts; i++) {
-               float position[3];
-               mesh_importer->getVertCoord(import_data, i, position);
-               vertex_storage.push_back(carve::geom::VECTOR(position[0],
-                                                            position[1],
-                                                            position[2]));
-       }
-
-       // Import polys from external mesh to Carve.
-       int verts_of_poly_static[MAX_STATIC_VERTS];
-       int *verts_of_poly_dynamic = NULL;
-       int verts_of_poly_dynamic_size = 0;
-
-       int num_polys = mesh_importer->getNumPolys(import_data);
-       int loop_index = 0;
-       std::vector<int> face_indices;
-       TrianglesStorage triangles_storage;
-       std::vector<MeshSet<3>::face_t *> faces;
-       std::vector<MeshSet<3>::vertex_t *> face_vertices;
-       faces.reserve(num_polys);
-       for (int i = 0; i < num_polys; i++) {
-               int verts_per_poly =
-                       mesh_importer->getNumPolyVerts(import_data, i);
-               int *verts_of_poly;
-
-               if (verts_per_poly <= MAX_STATIC_VERTS) {
-                       verts_of_poly = verts_of_poly_static;
-               }
-               else {
-                       if (verts_of_poly_dynamic_size < verts_per_poly) {
-                               if (verts_of_poly_dynamic != NULL) {
-                                       delete [] verts_of_poly_dynamic;
-                               }
-                               verts_of_poly_dynamic = new int[verts_per_poly];
-                               verts_of_poly_dynamic_size = verts_per_poly;
-                       }
-                       verts_of_poly = verts_of_poly_dynamic;
-               }
-
-               mesh_importer->getPolyVerts(import_data, i, verts_of_poly);
-
-               carve::math::Matrix3 axis_matrix;
-               if (!carve_checkPolyPlanarAndGetNormal(vertex_storage,
-                                                      verts_per_poly,
-                                                      verts_of_poly,
-                                                      &axis_matrix)) {
-                       face_indices.clear();
-                       int num_triangles = carve_triangulatePoly(import_data,
-                                                                 mesh_importer,
-                                                                 vertex_storage,
-                                                                 verts_per_poly,
-                                                                 verts_of_poly,
-                                                                 axis_matrix,
-                                                                 &face_indices,
-                                                                 &triangles_storage);
-                       for (int j = 0; j < num_triangles; ++j) {
-                               MeshSet<3>::face_t *face = new MeshSet<3>::face_t(
-                                       &vertex_storage[face_indices[j * 3]],
-                                       &vertex_storage[face_indices[j * 3 + 1]],
-                                       &vertex_storage[face_indices[j * 3 + 2]]);
-                               mesh_descr->orig_poly_index_map[face] = i;
-                               faces.push_back(face);
-                       }
-               }
-               else {
-                       face_vertices.clear();
-                       face_vertices.reserve(verts_per_poly);
-                       for (int j = 0; j < verts_per_poly; ++j) {
-                               face_vertices.push_back(&vertex_storage[verts_of_poly[j]]);
-                       }
-                       MeshSet<3>::face_t *face =
-                               new MeshSet<3>::face_t(face_vertices.begin(),
-                                                      face_vertices.end());
-                       mesh_descr->orig_poly_index_map[face] = i;
-                       faces.push_back(face);
-               }
-
-               for (int j = 0; j < verts_per_poly; ++j) {
-                       int v1 = verts_of_poly[j];
-                       int v2 = verts_of_poly[(j + 1) % verts_per_poly];
-                       edgeIndexMap_put(&mesh_descr->orig_loop_index_map, v1, v2, loop_index++);
-               }
-       }
-
-       if (verts_of_poly_dynamic != NULL) {
-               delete [] verts_of_poly_dynamic;
-       }
-
-       std::vector<MeshSet<3>::mesh_t *> meshes;
-       MeshSet<3>::mesh_t::create(faces.begin(), faces.end(), meshes, carve::mesh::MeshOptions());
-       mesh_descr->poly = new MeshSet<3> (vertex_storage, meshes);
-
-       return mesh_descr;
-
-#undef MAX_STATIC_VERTS
-}
-
-void carve_deleteMesh(CarveMeshDescr *mesh_descr)
-{
-       delete mesh_descr->poly;
-       delete mesh_descr;
-}
-
-bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
-                                   CarveMeshDescr *right_mesh,
-                                   int operation,
-                                   CarveMeshDescr **output_mesh)
-{
-       *output_mesh = NULL;
-
-       carve::csg::CSG::OP op;
-       switch (operation) {
-#define OP_CONVERT(the_op) \
-               case CARVE_OP_ ## the_op: \
-                       op = carve::csg::CSG::the_op; \
-                       break;
-               OP_CONVERT(UNION)
-               OP_CONVERT(INTERSECTION)
-               OP_CONVERT(A_MINUS_B)
-               default:
-                       return false;
-#undef OP_CONVERT
-       }
-
-       CarveMeshDescr *output_descr = new CarveMeshDescr;
-       output_descr->poly = NULL;
-       try {
-               MeshSet<3> *left = left_mesh->poly, *right = right_mesh->poly;
-               carve::geom3d::Vector min, max;
-
-               // TODO(sergey): Make importer/exporter to care about re-scale
-               // to save extra mesh iteration here.
-               carve_getRescaleMinMax(left, right, &min, &max);
-
-               carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z);
-               carve::rescale::fwd fwd_r(scaler);
-               carve::rescale::rev rev_r(scaler);
-
-               left->transform(fwd_r);
-               right->transform(fwd_r);
-
-               // Initialize attributes for maping from boolean result mesh back to
-               // original geometry indices.
-               initOrigIndexMapping(left_mesh, right_mesh,
-                                    &output_descr->orig_vert_mapping,
-                                    &output_descr->orig_face_edge_mapping,
-                                    &output_descr->face_edge_triangulated_flag,
-                                    &output_descr->orig_face_mapping);
-
-               carve::csg::CSG csg;
-
-               csg.hooks.registerHook(new HoleResolver,
-                                      carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
-
-               csg.hooks.registerHook(new EarClipper,
-                                      carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
-
-               output_descr->orig_vert_mapping.installHooks(csg);
-               output_descr->orig_face_edge_mapping.installHooks(csg);
-               output_descr->face_edge_triangulated_flag.installHooks(csg);
-               output_descr->orig_face_mapping.installHooks(csg);
-
-               // Prepare operands for actual boolean operation.
-               //
-               // It's needed because operands might consist of several intersecting
-               // meshes and in case of another operands intersect an edge loop of
-               // intersecting that meshes tessellation of operation result can't be
-               // done properly. The only way to make such situations working is to
-               // union intersecting meshes of the same operand.
-               carve_unionIntersections(&csg, &left, &right,
-                                        copyVertexAttrsCallback,
-                                        cleanupFaceEdgeAttrsCallback,
-                                        (void *) output_descr);
-
-               left_mesh->poly = left;
-               right_mesh->poly = right;
-
-               if (left->meshes.size() == 0 || right->meshes.size() == 0) {
-                       // Normally shouldn't happen (zero-faces objects are handled by
-                       // modifier itself), but unioning intersecting meshes which doesn't
-                       // have consistent normals might lead to empty result which
-                       // wouldn't work here.
-
-                       return false;
-               }
-
-               output_descr->poly = csg.compute(left,
-                                                right,
-                                                op,
-                                                NULL,
-                                                carve::csg::CSG::CLASSIFY_EDGE);
-
-               if (output_descr->poly) {
-                       output_descr->poly->transform(rev_r);
-
-                       dissolveTriangulatedEdges(output_descr);
-               }
-       }
-       catch (carve::exception e) {
-               std::cerr << "CSG failed, exception " << e.str() << std::endl;
-       }
-       catch (...) {
-               std::cerr << "Unknown error in Carve library" << std::endl;
-       }
-
-       *output_mesh = output_descr;
-
-       return output_descr->poly != NULL;
-}
-
-static int exportMesh_handle_edges_list(MeshSet<3> *poly,
-                                        const std::vector<MeshSet<3>::edge_t*> &edges,
-                                        int start_edge_index,
-                                        CarveMeshExporter *mesh_exporter,
-                                        struct ExportMeshData *export_data,
-                                        std::unordered_map<VertexPair, OrigIndex> &edge_origindex_map,
-                                        std::unordered_map<VertexPair, int> *edge_map)
-{
-       int num_exported_edges = 0;
-
-       for (int i = 0, edge_index = start_edge_index;
-            i < edges.size();
-            ++i)
-       {
-               MeshSet<3>::edge_t *edge = edges.at(i);
-               MeshSet<3>::vertex_t *v1 = edge->v1();
-               MeshSet<3>::vertex_t *v2 = edge->v2();
-
-               if (edgeIndexMap_exists(*edge_map, v1, v2)) {
-                       continue;
-               }
-
-               const OrigIndex &orig_edge_index = edgeIndexMap_get(edge_origindex_map,
-                                                                       v1,
-                                                                       v2);
-
-               mesh_exporter->setEdge(export_data,
-                                      edge_index,
-                                      indexOf(v1, poly->vertex_storage),
-                                      indexOf(v2, poly->vertex_storage),
-                                      orig_edge_index.first,
-                                      orig_edge_index.second);
-
-               edgeIndexMap_put(edge_map, v1, v2, edge_index);
-               ++edge_index;
-               ++num_exported_edges;
-       }
-
-       return num_exported_edges;
-}
-
-void carve_exportMesh(CarveMeshDescr *mesh_descr,
-                      CarveMeshExporter *mesh_exporter,
-                      struct ExportMeshData *export_data)
-{
-       OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
-       MeshSet<3> *poly = mesh_descr->poly;
-       int num_vertices = poly->vertex_storage.size();
-       int num_edges = 0, num_loops = 0, num_polys = 0;
-
-       // Get mapping from edge denoted by vertex pair to original edge index,
-       //
-       // This is needed because internally Carve interpolates data for per-face
-       // edges rather then having some global edge storage.
-       std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
-       for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
-            face_iter != poly->faceEnd();
-            ++face_iter)
-       {
-               MeshSet<3>::face_t *face = *face_iter;
-               for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
-                    edge_iter != face->end();
-                    ++edge_iter)
-               {
-                       MeshSet<3>::edge_t &edge = *edge_iter;
-                       int edge_iter_index = edge_iter.idx();
-
-                       const OrigIndex &orig_loop_index =
-                               mesh_descr->orig_face_edge_mapping.getAttribute(face,
-                                                                               edge_iter_index,
-                                                                               origindex_none);
-
-                       OrigIndex orig_edge_index;
-
-                       if (orig_loop_index.first != CARVE_MESH_NONE) {
-                               orig_edge_index.first = orig_loop_index.first;
-                               orig_edge_index.second =
-                                       mesh_exporter->mapLoopToEdge(export_data,
-                                                                    orig_loop_index.first,
-                                                                    orig_loop_index.second);
-                       }
-                       else {
-                               orig_edge_index.first = CARVE_MESH_NONE;
-                               orig_edge_index.second = -1;
-                       }
-
-                       MeshSet<3>::vertex_t *v1 = edge.v1();
-                       MeshSet<3>::vertex_t *v2 = edge.v2();
-
-                       edgeIndexMap_put(&edge_origindex_map, v1, v2, orig_edge_index);
-               }
-       }
-
-       num_edges = edge_origindex_map.size();
-
-       // Count polys and loops from all manifolds.
-       for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
-            face_iter != poly->faceEnd();
-            ++face_iter, ++num_polys)
-       {
-               MeshSet<3>::face_t *face = *face_iter;
-               num_loops += face->nEdges();
-       }
-
-       // Initialize arrays for geometry in exported mesh.
-       mesh_exporter->initGeomArrays(export_data,
-                                     num_vertices,
-                                     num_edges,
-                                     num_loops,
-                                     num_polys);
-
-       // Export all the vertices.
-       std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter = poly->vertex_storage.begin();
-       for (int i = 0; vertex_iter != poly->vertex_storage.end(); ++i, ++vertex_iter) {
-               MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
-
-               OrigIndex orig_vert_index =
-                       mesh_descr->orig_vert_mapping.getAttribute(vertex, origindex_none);
-
-               float coord[3];
-               coord[0] = vertex->v[0];
-               coord[1] = vertex->v[1];
-               coord[2] = vertex->v[2];
-               mesh_exporter->setVert(export_data, i, coord,
-                                      orig_vert_index.first,
-                                      orig_vert_index.second);
-       }
-
-       // Export all the edges.
-       std::unordered_map<VertexPair, int> edge_map;
-       for (int i = 0, edge_index = 0; i < poly->meshes.size(); ++i) {
-               carve::mesh::Mesh<3> *mesh = poly->meshes[i];
-               // Export closed edges.
-               edge_index += exportMesh_handle_edges_list(poly,
-                                                          mesh->closed_edges,
-                                                          edge_index,
-                                                          mesh_exporter,
-                                                          export_data,
-                                                          edge_origindex_map,
-                                                          &edge_map);
-
-               // Export open edges.
-               edge_index += exportMesh_handle_edges_list(poly,
-                                                          mesh->open_edges,
-                                                          edge_index,
-                                                          mesh_exporter,
-                                                          export_data,
-                                                          edge_origindex_map,
-                                                          &edge_map);
-       }
-
-       // Export all the loops and polys.
-       MeshSet<3>::face_iter face_iter = poly->faceBegin();
-       for (int loop_index = 0, poly_index = 0;
-            face_iter != poly->faceEnd();
-            ++face_iter, ++poly_index)
-       {
-               int start_loop_index = loop_index;
-               MeshSet<3>::face_t *face = *face_iter;
-               const OrigIndex &orig_face_index =
-                       mesh_descr->orig_face_mapping.getAttribute(face, origindex_none);
-
-               for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
-                    edge_iter != face->end();
-                    ++edge_iter, ++loop_index)
-               {
-                       MeshSet<3>::edge_t &edge = *edge_iter;
-                       const OrigIndex &orig_loop_index =
-                               mesh_descr->orig_face_edge_mapping.getAttribute(face,
-                                                                               edge_iter.idx(),
-                                                                               origindex_none);
-
-                       mesh_exporter->setLoop(export_data,
-                                              loop_index,
-                                              indexOf(edge.vert, poly->vertex_storage),
-                                              edgeIndexMap_get(edge_map, edge.v1(), edge.v2()),
-                                              orig_loop_index.first,
-                                              orig_loop_index.second);
-               }
-
-               mesh_exporter->setPoly(export_data,
-                                      poly_index, start_loop_index, face->nEdges(),
-                                      orig_face_index.first, orig_face_index.second);
-       }
-}
diff --git a/extern/carve/carve-capi.h b/extern/carve/carve-capi.h
deleted file mode 100644 (file)
index f08ce41..0000000
+++ /dev/null
@@ -1,164 +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) 2014 Blender Foundation.
- * All rights reserved.
- *
- * Contributor(s): Blender Foundation,
- *                 Sergey Sharybin
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-#ifndef __CARVE_CAPI_H__
-#define __CARVE_CAPI_H__
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-struct CarveMeshDescr;
-
-//
-// Importer from external storage to Carve module
-//
-
-struct ImportMeshData;
-
-// Get number of vertices.
-typedef int (*CarveImporter_GetNumVerts) (struct ImportMeshData *import_data);
-
-// Get number of edges.
-typedef int (*CarveImporter_GetNumEdges) (struct ImportMeshData *import_data);
-
-// Get number of loops.
-typedef int (*CarveImporter_GetNumLoops) (struct ImportMeshData *import_data);
-
-// Get number of polys.
-typedef int (*CarveImporter_GetNumPolys) (struct ImportMeshData *import_data);
-
-// Get 3D coordinate of vertex with given index.
-typedef void (*CarveImporter_GetVertCoord) (struct ImportMeshData *import_data, int vert_index, float coord[3]);
-
-// Get index of vertices which are adjacent to edge specified by its index.
-typedef void (*CarveImporter_GetEdgeVerts) (struct ImportMeshData *import_data, int edge_index, int *v1, int *v2);
-
-// Get number of adjacent vertices to the poly specified by its index.
-typedef int (*CarveImporter_GetPolyNumVerts) (struct ImportMeshData *import_data, int poly_index);
-
-// Get list of adjacent vertices to the poly specified by its index.
-typedef void (*CarveImporter_GetPolyVerts) (struct ImportMeshData *import_data, int poly_index, int *verts);
-
-// Triangulate 2D polygon.
-typedef int (*CarveImporter_Triangulate2DPoly) (struct ImportMeshData *import_data,
-                                                const float (*vertices)[2], int num_vertices,
-                                                unsigned int (*triangles)[3]);
-
-typedef struct CarveMeshImporter {
-       CarveImporter_GetNumVerts getNumVerts;
-       CarveImporter_GetNumEdges getNumEdges;
-       CarveImporter_GetNumLoops getNumLoops;
-       CarveImporter_GetNumPolys getNumPolys;
-       CarveImporter_GetVertCoord getVertCoord;
-       CarveImporter_GetEdgeVerts getEdgeVerts;
-       CarveImporter_GetPolyNumVerts getNumPolyVerts;
-       CarveImporter_GetPolyVerts getPolyVerts;
-       CarveImporter_Triangulate2DPoly triangulate2DPoly;
-} CarveMeshImporter;
-
-//
-// Exporter from Carve module to external storage
-//
-
-struct ExportMeshData;
-
-// Initialize arrays for geometry.
-typedef void (*CarveExporter_InitGeomArrays) (struct ExportMeshData *export_data,
-                                              int num_verts, int num_edges,
-                                              int num_loops, int num_polys);
-
-// Set coordinate of vertex with given index.
-typedef void (*CarveExporter_SetVert) (struct ExportMeshData *export_data,
-                                       int vert_index, float coord[3],
-                                       int which_orig_mesh, int orig_vert_index);
-
-// Set vertices which are adjacent to the edge specified by its index.
-typedef void (*CarveExporter_SetEdge) (struct ExportMeshData *export_data,
-                                       int edge_index, int v1, int v2,
-                                       int which_orig_mesh, int orig_edge_index);
-
-// Set adjacent loops to the poly specified by its index.
-typedef void (*CarveExporter_SetPoly) (struct ExportMeshData *export_data,
-                                       int poly_index, int start_loop, int num_loops,
-                                       int which_orig_mesh, int orig_poly_index);
-
-// Set list vertex and edge which are adjacent to loop with given index.
-typedef void (*CarveExporter_SetLoop) (struct ExportMeshData *export_data,
-                                       int loop_index, int vertex, int edge,
-                                       int which_orig_mesh, int orig_loop_index);
-
-// Get edge index from a loop index for a given original mesh.
-//
-// A bit of a bummer to access original operands data on export stage,
-// but Blender side still does have this information in derived meshes
-// and we use API to get this data instead of duplicating it in Carve
-// API side. This is because of optimizations reasons.
-typedef int (*CarveExporter_MapLoopToEdge) (struct ExportMeshData *export_data,
-                                            int which_mesh, int loop_index);
-
-typedef struct CarveMeshExporter {
-       CarveExporter_InitGeomArrays initGeomArrays;
-       CarveExporter_SetVert setVert;
-       CarveExporter_SetEdge setEdge;
-       CarveExporter_SetPoly setPoly;
-       CarveExporter_SetLoop setLoop;
-       CarveExporter_MapLoopToEdge mapLoopToEdge;
-} CarveMeshExporter;
-
-enum {
-       CARVE_OP_UNION,
-       CARVE_OP_INTERSECTION,
-       CARVE_OP_A_MINUS_B,
-};
-
-enum {
-       CARVE_MESH_NONE,
-       CARVE_MESH_LEFT,
-       CARVE_MESH_RIGHT
-};
-
-struct CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
-                                     CarveMeshImporter *mesh_importer);
-
-void carve_deleteMesh(struct CarveMeshDescr *mesh_descr);
-
-bool carve_performBooleanOperation(struct CarveMeshDescr *left_mesh,
-                                   struct CarveMeshDescr *right_mesh,
-                                   int operation,
-                                   struct CarveMeshDescr **output_mesh);
-
-void carve_exportMesh(struct CarveMeshDescr *mesh_descr,
-                      CarveMeshExporter *mesh_exporter,
-                      struct ExportMeshData *export_data);
-
-void carve_unionIntersections(struct CarveMeshDescr **left_mesh_r, struct CarveMeshDescr **right_mesh_r);
-
-#ifdef __cplusplus
-}  // extern "C"
-#endif
-
-#endif  // __CARVE_CAPI_H__
diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc
deleted file mode 100644 (file)
index 78997c7..0000000
+++ /dev/null
@@ -1,838 +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) 2014 Blender Foundation.
- * All rights reserved.
- *
- * Contributor(s): Blender Foundation,
- *                 Sergey Sharybin
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-#include "carve-util.h"
-#include "carve-capi.h"
-
-#include <cfloat>
-#include <carve/csg.hpp>
-#include <carve/csg_triangulator.hpp>
-#include <carve/rtree.hpp>
-
-using carve::csg::Intersections;
-using carve::geom::aabb;
-using carve::geom::RTreeNode;
-using carve::geom3d::Vector;
-using carve::math::Matrix3;
-using carve::mesh::Face;
-using carve::mesh::MeshSet;
-using carve::triangulate::tri_idx;
-using carve::triangulate::triangulate;
-
-typedef std::map< MeshSet<3>::mesh_t*, RTreeNode<3, Face<3> *> * > RTreeCache;
-typedef std::map< MeshSet<3>::mesh_t*, bool > IntersectCache;
-
-namespace {
-
-// Functions adopted from BLI_math.h to use Carve Vector and Matrix.
-
-void transpose_m3__bli(double mat[3][3])
-{
-       double t;
-
-       t = mat[0][1];
-       mat[0][1] = mat[1][0];
-       mat[1][0] = t;
-       t = mat[0][2];
-       mat[0][2] = mat[2][0];
-       mat[2][0] = t;
-       t = mat[1][2];
-       mat[1][2] = mat[2][1];
-       mat[2][1] = t;
-}
-
-void ortho_basis_v3v3_v3__bli(double r_n1[3], double r_n2[3], const double n[3])
-{
-       const double eps = FLT_EPSILON;
-       const double f = (n[0] * n[0]) + (n[1] * n[1]);
-
-       if (f > eps) {
-               const double d = 1.0f / sqrt(f);
-
-               r_n1[0] =  n[1] * d;
-               r_n1[1] = -n[0] * d;
-               r_n1[2] =  0.0f;
-               r_n2[0] = -n[2] * r_n1[1];
-               r_n2[1] =  n[2] * r_n1[0];
-               r_n2[2] =  n[0] * r_n1[1] - n[1] * r_n1[0];
-       }
-       else {
-               /* degenerate case */
-               r_n1[0] = (n[2] < 0.0f) ? -1.0f : 1.0f;
-               r_n1[1] = r_n1[2] = r_n2[0] = r_n2[2] = 0.0f;
-               r_n2[1] = 1.0f;
-       }
-}
-
-void axis_dominant_v3_to_m3__bli(Matrix3 *r_mat, const Vector &normal)
-{
-       memcpy(r_mat->m[2], normal.v, sizeof(double[3]));
-       ortho_basis_v3v3_v3__bli(r_mat->m[0], r_mat->m[1], r_mat->m[2]);
-
-       transpose_m3__bli(r_mat->m);
-}
-
-
-void meshset_minmax(const MeshSet<3> *mesh,
-                    Vector *min,
-                    Vector *max)
-{
-       for (size_t i = 0; i < mesh->vertex_storage.size(); ++i) {
-               min->x = std::min(min->x, mesh->vertex_storage[i].v.x);
-               min->y = std::min(min->y, mesh->vertex_storage[i].v.y);
-               min->z = std::min(min->z, mesh->vertex_storage[i].v.z);
-               max->x = std::max(max->x, mesh->vertex_storage[i].v.x);
-               max->y = std::max(max->y, mesh->vertex_storage[i].v.y);
-               max->z = std::max(max->z, mesh->vertex_storage[i].v.z);
-       }
-}
-
-}  // namespace
-
-void carve_getRescaleMinMax(const MeshSet<3> *left,
-                            const MeshSet<3> *right,
-                            Vector *min,
-                            Vector *max)
-{
-       min->x = max->x = left->vertex_storage[0].v.x;
-       min->y = max->y = left->vertex_storage[0].v.y;
-       min->z = max->z = left->vertex_storage[0].v.z;
-
-       meshset_minmax(left, min, max);
-       meshset_minmax(right, min, max);
-
-       // Make sure we don't scale object with zero scale.
-       if (std::abs(min->x - max->x) < carve::EPSILON) {
-               min->x = -1.0;
-               max->x = 1.0;
-       }
-       if (std::abs(min->y - max->y) < carve::EPSILON) {
-               min->y = -1.0;
-               max->y = 1.0;
-       }
-       if (std::abs(min->z - max->z) < carve::EPSILON) {
-               min->z = -1.0;
-               max->z = 1.0;
-       }
-}
-
-namespace {
-
-struct UnionIntersectionContext {
-       VertexAttrsCallback vertex_attr_callback;
-       void *user_data;
-};
-
-void copyMeshes(const std::vector<MeshSet<3>::mesh_t*> &meshes,
-                std::vector<MeshSet<3>::mesh_t*> *new_meshes)
-{
-       std::vector<MeshSet<3>::mesh_t*>::const_iterator it = meshes.begin();
-       new_meshes->reserve(meshes.size());
-       for (; it != meshes.end(); it++) {
-               MeshSet<3>::mesh_t *mesh = *it;
-               MeshSet<3>::mesh_t *new_mesh = new MeshSet<3>::mesh_t(mesh->faces);
-
-               new_meshes->push_back(new_mesh);
-       }
-}
-
-struct NewMeshMapping {
-       std::map<const MeshSet<3>::edge_t*, MeshSet<3>::vertex_t*> orig_edge_vert;
-};
-
-void prepareNewMeshMapping(const std::vector<MeshSet<3>::mesh_t*> &meshes,
-                           NewMeshMapping *mapping)
-{
-       for (size_t m = 0; m < meshes.size(); ++m) {
-               MeshSet<3>::mesh_t *mesh = meshes[m];
-               for (size_t f = 0; f < mesh->faces.size(); ++f) {
-                       MeshSet<3>::face_t *face = mesh->faces[f];
-                       MeshSet<3>::edge_t *edge = face->edge;
-                       do {
-                               mapping->orig_edge_vert[edge] = edge->vert;
-                               edge = edge->next;
-                       } while (edge != face->edge);
-               }
-       }
-}
-
-void runNewMeshSetHooks(UnionIntersectionContext *ctx,
-                        NewMeshMapping *mapping,
-                        MeshSet<3> *mesh_set)
-{
-       for (size_t m = 0; m < mesh_set->meshes.size(); ++m) {
-               MeshSet<3>::mesh_t *mesh = mesh_set->meshes[m];
-               for (size_t f = 0; f < mesh->faces.size(); ++f) {
-                       MeshSet<3>::face_t *face = mesh->faces[f];
-                       MeshSet<3>::edge_t *edge = face->edge;
-                       do {
-                               const MeshSet<3>::vertex_t *orig_vert = mapping->orig_edge_vert[edge];
-                               const MeshSet<3>::vertex_t *new_vert = edge->vert;
-                               ctx->vertex_attr_callback(orig_vert, new_vert, ctx->user_data);
-                               edge = edge->next;
-                       } while (edge != face->edge);
-               }
-       }
-}
-
-MeshSet<3> *newMeshSetFromMeshesWithAttrs(
-    UnionIntersectionContext *ctx,
-    std::vector<MeshSet<3>::mesh_t*> &meshes)
-{
-       NewMeshMapping mapping;
-       prepareNewMeshMapping(meshes, &mapping);
-       MeshSet<3> *mesh_set = new MeshSet<3>(meshes);
-       runNewMeshSetHooks(ctx, &mapping, mesh_set);
-       return mesh_set;
-}
-
-
-MeshSet<3> *meshSetFromMeshes(UnionIntersectionContext *ctx,
-                              const std::vector<MeshSet<3>::mesh_t*> &meshes)
-{
-       std::vector<MeshSet<3>::mesh_t*> new_meshes;
-       copyMeshes(meshes, &new_meshes);
-       return newMeshSetFromMeshesWithAttrs(ctx, new_meshes);
-}
-
-MeshSet<3> *meshSetFromTwoMeshes(UnionIntersectionContext *ctx,
-                                 const std::vector<MeshSet<3>::mesh_t*> &left_meshes,
-                                 const std::vector<MeshSet<3>::mesh_t*> &right_meshes)
-{
-       std::vector<MeshSet<3>::mesh_t*> new_meshes;
-       copyMeshes(left_meshes, &new_meshes);
-       copyMeshes(right_meshes, &new_meshes);
-       return newMeshSetFromMeshesWithAttrs(ctx, new_meshes);
-}
-
-bool checkEdgeFaceIntersections_do(Intersections &intersections,
-                                   MeshSet<3>::face_t *face_a,
-                                   MeshSet<3>::edge_t *edge_b)
-{
-       if (intersections.intersects(edge_b, face_a))
-               return true;
-
-       carve::mesh::MeshSet<3>::vertex_t::vector_t _p;
-       if (face_a->simpleLineSegmentIntersection(carve::geom3d::LineSegment(edge_b->v1()->v, edge_b->v2()->v), _p))
-               return true;
-
-       return false;
-}
-
-bool checkEdgeFaceIntersections(Intersections &intersections,
-                                MeshSet<3>::face_t *face_a,
-                                MeshSet<3>::face_t *face_b)
-{
-       MeshSet<3>::edge_t *edge_b;
-
-       edge_b = face_b->edge;
-       do {
-               if (checkEdgeFaceIntersections_do(intersections, face_a, edge_b))
-                       return true;
-               edge_b = edge_b->next;
-       } while (edge_b != face_b->edge);
-
-       return false;
-}
-
-inline bool facesAreCoplanar(const MeshSet<3>::face_t *a, const MeshSet<3>::face_t *b)
-{
-       carve::geom3d::Ray temp;
-       // XXX: Find a better definition. This may be a source of problems
-       // if floating point inaccuracies cause an incorrect answer.
-       return !carve::geom3d::planeIntersection(a->plane, b->plane, temp);
-}
-
-bool checkMeshSetInterseciton_do(Intersections &intersections,
-                                 const RTreeNode<3, Face<3> *> *a_node,
-                                 const RTreeNode<3, Face<3> *> *b_node,
-                                 bool descend_a = true)
-{
-       if (!a_node->bbox.intersects(b_node->bbox)) {
-               return false;
-       }
-
-       if (a_node->child && (descend_a || !b_node->child)) {
-               for (RTreeNode<3, Face<3> *> *node = a_node->child; node; node = node->sibling) {
-                       if (checkMeshSetInterseciton_do(intersections, node, b_node, false)) {
-                               return true;
-                       }
-               }
-       }
-       else if (b_node->child) {
-               for (RTreeNode<3, Face<3> *> *node = b_node->child; node; node = node->sibling) {
-                       if (checkMeshSetInterseciton_do(intersections, a_node, node, true)) {
-                               return true;
-                       }
-               }
-       }
-       else {
-               for (size_t i = 0; i < a_node->data.size(); ++i) {
-                       MeshSet<3>::face_t *fa = a_node->data[i];
-                       aabb<3> aabb_a = fa->getAABB();
-                       if (aabb_a.maxAxisSeparation(b_node->bbox) > carve::EPSILON) {
-                               continue;
-                       }
-
-                       for (size_t j = 0; j < b_node->data.size(); ++j) {
-                               MeshSet<3>::face_t *fb = b_node->data[j];
-                               aabb<3> aabb_b = fb->getAABB();
-                               if (aabb_b.maxAxisSeparation(aabb_a) > carve::EPSILON) {
-                                       continue;
-                               }
-
-                               std::pair<double, double> a_ra = fa->rangeInDirection(fa->plane.N, fa->edge->vert->v);
-                               std::pair<double, double> b_ra = fb->rangeInDirection(fa->plane.N, fa->edge->vert->v);
-                               if (carve::rangeSeparation(a_ra, b_ra) > carve::EPSILON) {
-                                       continue;
-                               }
-
-                               std::pair<double, double> a_rb = fa->rangeInDirection(fb->plane.N, fb->edge->vert->v);
-                               std::pair<double, double> b_rb = fb->rangeInDirection(fb->plane.N, fb->edge->vert->v);
-                               if (carve::rangeSeparation(a_rb, b_rb) > carve::EPSILON) {
-                                       continue;
-                               }
-
-                               if (!facesAreCoplanar(fa, fb)) {
-                                       if (checkEdgeFaceIntersections(intersections, fa, fb)) {
-                                               return true;
-                                       }
-                               }
-                       }
-               }
-       }
-
-       return false;
-}
-
-bool checkMeshSetInterseciton(RTreeNode<3, Face<3> *> *rtree_a, RTreeNode<3, Face<3> *> *rtree_b)
-{
-       Intersections intersections;
-       return checkMeshSetInterseciton_do(intersections, rtree_a, rtree_b);
-}
-
-void getIntersectedOperandMeshes(std::vector<MeshSet<3>::mesh_t*> *meshes,
-                                 const MeshSet<3>::aabb_t &otherAABB,
-                                 std::vector<MeshSet<3>::mesh_t*> *operandMeshes,
-                                 RTreeCache *rtree_cache,
-                                 IntersectCache *intersect_cache)
-{
-       std::vector<MeshSet<3>::mesh_t*>::iterator it = meshes->begin();
-       std::vector< RTreeNode<3, Face<3> *> *> meshRTree;
-
-       while (it != meshes->end()) {
-               MeshSet<3>::mesh_t *mesh = *it;
-               bool isAdded = false;
-
-               RTreeNode<3, Face<3> *> *rtree;
-               bool intersects;
-
-               RTreeCache::iterator rtree_found = rtree_cache->find(mesh);
-               if (rtree_found != rtree_cache->end()) {
-                       rtree = rtree_found->second;
-               }
-               else {
-                       rtree = RTreeNode<3, Face<3> *>::construct_STR(mesh->faces.begin(), mesh->faces.end(), 4, 4);
-                       (*rtree_cache)[mesh] = rtree;
-               }
-
-               IntersectCache::iterator intersect_found = intersect_cache->find(mesh);
-               if (intersect_found != intersect_cache->end()) {
-                       intersects = intersect_found->second;
-               }
-               else {
-                       intersects = rtree->bbox.intersects(otherAABB);
-                       (*intersect_cache)[mesh] = intersects;
-               }
-
-               if (intersects) {
-                       bool isIntersect = false;
-
-                       std::vector<MeshSet<3>::mesh_t*>::iterator operand_it = operandMeshes->begin();
-                       std::vector<RTreeNode<3, Face<3> *> *>::iterator tree_it = meshRTree.begin();
-                       for (; operand_it!=operandMeshes->end(); operand_it++, tree_it++) {
-                               RTreeNode<3, Face<3> *> *operandRTree = *tree_it;
-
-                               if (checkMeshSetInterseciton(rtree, operandRTree)) {
-                                       isIntersect = true;
-                                       break;
-                               }
-                       }
-
-                       if (!isIntersect) {
-                               operandMeshes->push_back(mesh);
-                               meshRTree.push_back(rtree);
-
-                               it = meshes->erase(it);
-                               isAdded = true;
-                       }
-               }
-
-               if (!isAdded) {
-                       //delete rtree;
-                       it++;
-               }
-       }
-
-       std::vector<RTreeNode<3, Face<3> *> *>::iterator tree_it = meshRTree.begin();
-       for (; tree_it != meshRTree.end(); tree_it++) {
-               //delete *tree_it;
-       }
-}
-
-MeshSet<3> *getIntersectedOperand(UnionIntersectionContext *ctx,
-                                  std::vector<MeshSet<3>::mesh_t*> *meshes,
-                                  const MeshSet<3>::aabb_t &otherAABB,
-                                  RTreeCache *rtree_cache,
-                                  IntersectCache *intersect_cache)
-{
-       std::vector<MeshSet<3>::mesh_t*> operandMeshes;
-       getIntersectedOperandMeshes(meshes, otherAABB, &operandMeshes, rtree_cache, intersect_cache);
-
-       if (operandMeshes.size() == 0)
-               return NULL;
-
-       return meshSetFromMeshes(ctx, operandMeshes);
-}
-
-MeshSet<3> *unionIntersectingMeshes(carve::csg::CSG *csg,
-                                    MeshSet<3> *poly,
-                                    const MeshSet<3> *other_poly,
-                                    const MeshSet<3>::aabb_t &otherAABB,
-                                    VertexAttrsCallback vertex_attr_callback,
-                                    UnionIntersectionsCallback callback,
-                                    void *user_data)
-{
-       if (poly->meshes.size() <= 1) {
-               return poly;
-       }
-
-       std::vector<MeshSet<3>::mesh_t*> orig_meshes =
-                       std::vector<MeshSet<3>::mesh_t*>(poly->meshes.begin(), poly->meshes.end());
-
-       RTreeCache rtree_cache;
-       IntersectCache intersect_cache;
-
-       UnionIntersectionContext ctx;
-       ctx.vertex_attr_callback = vertex_attr_callback;
-       ctx.user_data = user_data;
-
-       MeshSet<3> *left = getIntersectedOperand(&ctx,
-                                                &orig_meshes,
-                                                otherAABB,
-                                                &rtree_cache,
-                                                &intersect_cache);
-
-       if (!left) {
-               // No maniforlds which intersects another object at all.
-               return poly;
-       }
-
-       while (orig_meshes.size()) {
-               MeshSet<3> *right = getIntersectedOperand(&ctx,
-                                                         &orig_meshes,
-                                                         otherAABB,
-                                                         &rtree_cache,
-                                                         &intersect_cache);
-
-               if (!right) {
-                       // No more intersecting manifolds which intersects other object
-                       break;
-               }
-
-               try {
-                       if (left->meshes.size()==0) {
-                               delete left;
-
-                               left = right;
-                       }
-                       else {
-                               MeshSet<3> *result = csg->compute(left, right,
-                                                                 carve::csg::CSG::UNION,
-                                                                 NULL, carve::csg::CSG::CLASSIFY_EDGE);
-
-                               callback(result, other_poly, user_data);
-                               delete left;
-                               delete right;
-
-                               left = result;
-                       }
-               }
-               catch (carve::exception e) {
-                       std::cerr << "CSG failed, exception " << e.str() << std::endl;
-
-                       MeshSet<3> *result = meshSetFromTwoMeshes(&ctx,
-                                                                 left->meshes,
-                                                                 right->meshes);
-
-                       callback(result, other_poly, user_data);
-
-                       delete left;
-                       delete right;
-
-                       left = result;
-               }
-               catch (...) {
-                       delete left;
-                       delete right;
-
-                       throw "Unknown error in Carve library";
-               }
-       }
-
-       for (RTreeCache::iterator it = rtree_cache.begin();
-            it != rtree_cache.end();
-            it++)
-       {
-               delete it->second;
-       }
-
-       // Append all meshes which doesn't have intersection with another operand as-is.
-       if (orig_meshes.size()) {
-               MeshSet<3> *result = meshSetFromTwoMeshes(&ctx,
-                                                         left->meshes,
-                                                         orig_meshes);
-
-               delete left;
-               left = result;
-       }
-
-       return left;
-}
-
-}  // namespace
-
-// TODO(sergey): This function is to be totally re-implemented to make it
-// more clear what's going on and hopefully optimize it as well.
-void carve_unionIntersections(carve::csg::CSG *csg,
-                              MeshSet<3> **left_r,
-                              MeshSet<3> **right_r,
-                              VertexAttrsCallback vertex_attr_callback,
-                              UnionIntersectionsCallback callback,
-                              void *user_data)
-{
-       MeshSet<3> *left = *left_r, *right = *right_r;
-
-       if (left->meshes.size() == 1 && right->meshes.size() == 0) {
-               return;
-       }
-
-       MeshSet<3>::aabb_t leftAABB = left->getAABB();
-       MeshSet<3>::aabb_t rightAABB = right->getAABB();;
-
-       left = unionIntersectingMeshes(csg, left, right, rightAABB,
-                                      vertex_attr_callback, callback, user_data);
-       right = unionIntersectingMeshes(csg, right, left, leftAABB,
-                                       vertex_attr_callback, callback, user_data);
-
-       if (left != *left_r) {
-               delete *left_r;
-       }
-
-       if (right != *right_r) {
-               delete *right_r;
-       }
-
-       *left_r = left;
-       *right_r = right;
-}
-
-static inline void add_newell_cross_v3_v3v3(const Vector &v_prev,
-                                            const Vector &v_curr,
-                                            Vector *n)
-{
-       (*n)[0] += (v_prev[1] - v_curr[1]) * (v_prev[2] + v_curr[2]);
-       (*n)[1] += (v_prev[2] - v_curr[2]) * (v_prev[0] + v_curr[0]);
-       (*n)[2] += (v_prev[0] - v_curr[0]) * (v_prev[1] + v_curr[1]);
-}
-
-// Axis matrix is being set for non-flat ngons only.
-bool carve_checkPolyPlanarAndGetNormal(const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
-                                       const int verts_per_poly,
-                                       const int *verts_of_poly,
-                                       Matrix3 *axis_matrix_r)
-{
-       if (verts_per_poly == 3) {
-               // Triangles are always planar.
-               return true;
-       }
-       else if (verts_per_poly == 4) {
-               // Presumably faster than using generig n-gon check for quads.
-
-               const Vector &v1 = vertex_storage[verts_of_poly[0]].v,
-                            &v2 = vertex_storage[verts_of_poly[1]].v,
-                            &v3 = vertex_storage[verts_of_poly[2]].v,
-                            &v4 = vertex_storage[verts_of_poly[3]].v;
-
-               Vector vec1, vec2, vec3, cross;
-
-               vec1 = v2 - v1;
-               vec2 = v4 - v1;
-               vec3 = v3 - v1;
-
-               cross = carve::geom::cross(vec1, vec2);
-
-               double production = carve::geom::dot(cross, vec3);
-
-               // TODO(sergey): Check on whether we could have length-independent
-               // magnitude here.
-               double magnitude = 1e-3 * cross.length2();
-
-               return fabs(production) < magnitude;
-       }
-       else {
-               const Vector *vert_prev = &vertex_storage[verts_of_poly[verts_per_poly - 1]].v;
-               const Vector *vert_curr = &vertex_storage[verts_of_poly[0]].v;
-
-               Vector normal = carve::geom::VECTOR(0.0, 0.0, 0.0);
-               for (int i = 0; i < verts_per_poly; i++) {
-                       add_newell_cross_v3_v3v3(*vert_prev, *vert_curr, &normal);
-                       vert_prev = vert_curr;
-                       vert_curr = &vertex_storage[verts_of_poly[(i + 1) % verts_per_poly]].v;
-               }
-
-               if (normal.length2() < FLT_EPSILON) {
-                       // Degenerated face, couldn't triangulate properly anyway.
-                       return true;
-               }
-               else {
-                       double magnitude = normal.length2();
-
-                       normal.normalize();
-                       axis_dominant_v3_to_m3__bli(axis_matrix_r, normal);
-
-                       Vector first_projected = *axis_matrix_r * vertex_storage[verts_of_poly[0]].v;
-                       double min_z = first_projected[2], max_z = first_projected[2];
-
-                       for (int i = 1; i < verts_per_poly; i++) {
-                               const Vector &vertex = vertex_storage[verts_of_poly[i]].v;
-                               Vector projected = *axis_matrix_r * vertex;
-                               if (projected[2] < min_z) {
-                                       min_z = projected[2];
-                               }
-                               if (projected[2] > max_z) {
-                                       max_z = projected[2];
-                               }
-                       }
-
-                       if (std::abs(min_z - max_z) > FLT_EPSILON * magnitude) {
-                               return false;
-                       }
-               }
-
-               return true;
-       }
-
-       return false;
-}
-
-namespace {
-
-int triangulateNGon_carveTriangulator(const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
-                                      const int verts_per_poly,
-                                      const int *verts_of_poly,
-                                      const Matrix3 &axis_matrix,
-                                      std::vector<tri_idx> *triangles)
-{
-       // Project vertices to 2D plane.
-       Vector projected;
-       std::vector<carve::geom::vector<2> > poly_2d;
-       poly_2d.reserve(verts_per_poly);
-       for (int i = 0; i < verts_per_poly; ++i) {
-               projected = axis_matrix * vertex_storage[verts_of_poly[i]].v;
-               poly_2d.push_back(carve::geom::VECTOR(projected[0], projected[1]));
-       }
-
-       carve::triangulate::triangulate(poly_2d, *triangles);
-       carve::triangulate::improve(poly_2d, *triangles);
-
-       return triangles->size();
-}
-
-int triangulateNGon_importerTriangulator(struct ImportMeshData *import_data,
-                                         CarveMeshImporter *mesh_importer,
-                                         const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
-                                         const int verts_per_poly,
-                                         const int *verts_of_poly,
-                                         const Matrix3 &axis_matrix,
-                                         std::vector<tri_idx> *triangles)
-{
-       typedef float Vector2D[2];
-       typedef unsigned int Triangle[3];
-
-       // Project vertices to 2D plane.
-       Vector2D *poly_2d = new Vector2D[verts_per_poly];
-       Vector projected;
-       for (int i = 0; i < verts_per_poly; ++i) {
-               projected = axis_matrix * vertex_storage[verts_of_poly[i]].v;
-               poly_2d[i][0] = projected[0];
-               poly_2d[i][1] = projected[1];
-       }
-
-       Triangle *api_triangles = new Triangle[verts_per_poly - 2];
-       int num_triangles =
-               mesh_importer->triangulate2DPoly(import_data,
-                                                poly_2d,
-                                                verts_per_poly,
-                                                api_triangles);
-
-       triangles->reserve(num_triangles);
-       for (int i = 0; i < num_triangles; ++i) {
-               triangles->push_back(tri_idx(api_triangles[i][0],
-                                                api_triangles[i][1],
-                                                api_triangles[i][2]));
-       }
-
-       delete [] poly_2d;
-       delete [] api_triangles;
-
-       return num_triangles;
-}
-
-template <typename T>
-void sortThreeNumbers(T &a, T &b, T &c)
-{
-       if (a > b)
-               std::swap(a, b);
-       if (b > c)
-               std::swap(b, c);
-       if (a > b)
-               std::swap(a, b);
-}
-
-bool pushTriangle(int v1, int v2, int v3,
-                  std::vector<int> *face_indices,
-                  TrianglesStorage *triangles_storage)
-{
-
-       tri_idx triangle(v1, v2, v3);
-       sortThreeNumbers(triangle.a, triangle.b, triangle.c);
-
-       assert(triangle.a < triangle.b);
-       assert(triangle.b < triangle.c);
-
-       if (triangles_storage->find(triangle) == triangles_storage->end()) {
-               face_indices->push_back(v1);
-               face_indices->push_back(v2);
-               face_indices->push_back(v3);
-
-               triangles_storage->insert(triangle);
-               return true;
-       }
-       else {
-               return false;
-       }
-}
-
-}  // namespace
-
-int carve_triangulatePoly(struct ImportMeshData *import_data,
-                          CarveMeshImporter *mesh_importer,
-                          const std::vector<MeshSet<3>::vertex_t> &vertex_storage,
-                          const int verts_per_poly,
-                          const int *verts_of_poly,
-                          const Matrix3 &axis_matrix,
-                          std::vector<int> *face_indices,
-                          TrianglesStorage *triangles_storage)
-{
-       int num_triangles = 0;
-
-       assert(verts_per_poly > 3);
-
-       if (verts_per_poly == 4) {
-               // Quads we triangulate by 1-3 diagonal, it is an original behavior
-               // of boolean modifier.
-               //
-               // TODO(sergey): Consider using shortest diagonal here. However
-               // display code in Blende use static 1-3 split, so some experiments
-               // are needed here.
-               if (pushTriangle(verts_of_poly[0],
-                                verts_of_poly[1],
-                                verts_of_poly[2],
-                                face_indices,
-                                triangles_storage))
-               {
-                       num_triangles++;
-               }
-
-               if (pushTriangle(verts_of_poly[0],
-                                verts_of_poly[2],
-                                verts_of_poly[3],
-                                face_indices,
-                                triangles_storage))
-               {
-                       num_triangles++;
-               }
-       }
-       else {
-               std::vector<tri_idx> triangles;
-               triangles.reserve(verts_per_poly - 2);
-
-               // Make triangulator callback optional so we could do some tests
-               // in the future.
-               if (mesh_importer->triangulate2DPoly) {
-                       triangulateNGon_importerTriangulator(import_data,
-                                                            mesh_importer,
-                                                            vertex_storage,
-                                                            verts_per_poly,
-                                                            verts_of_poly,
-                                                            axis_matrix,
-                                                            &triangles);
-               }
-               else {
-                       triangulateNGon_carveTriangulator(vertex_storage,
-                                                         verts_per_poly,
-                                                         verts_of_poly,
-                                                         axis_matrix,
-                                                         &triangles);
-               }
-
-               for (int i = 0; i < triangles.size(); ++i) {
-                       int v1 = triangles[i].a,
-                           v2 = triangles[i].b,
-                           v3 = triangles[i].c;
-
-                       // Sanity check of the triangle.
-                       assert(v1 != v2);
-                       assert(v1 != v3);
-                       assert(v2 != v3);
-                       assert(v1 < verts_per_poly);
-                       assert(v2 < verts_per_poly);
-                       assert(v3 < verts_per_poly);
-
-                       if (pushTriangle(verts_of_poly[v1],
-                                        verts_of_poly[v2],
-                                        verts_of_poly[v3],
-                                        face_indices,
-                                        triangles_storage))
-                       {
-                               num_triangles++;
-                       }
-               }
-       }
-
-       return num_triangles;
-}
diff --git a/extern/carve/carve-util.h b/extern/carve/carve-util.h
deleted file mode 100644 (file)
index e8f62cd..0000000
+++ /dev/null
@@ -1,300 +0,0 @@
-/*
- * ***** BEGIN GPL LICENSE BLOCK *****
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2014 Blender Foundation.
- * All rights reserved.
- *
- * Contributor(s): Blender Foundation,
- *                 Sergey Sharybin
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-#ifndef __CARVE_UTIL_H__
-#define __CARVE_UTIL_H__
-
-#include <carve/csg.hpp>
-#include <carve/geom3d.hpp>
-#include <carve/interpolator.hpp>
-#include <carve/mesh.hpp>
-#include <carve/triangulator.hpp>
-
-#include "carve-capi.h"
-
-struct TriIdxCompare {
-       bool operator() (const carve::triangulate::tri_idx &left,
-                        const carve::triangulate::tri_idx &right) const {
-               if (left.a < right.a) {
-                       return true;
-               }
-               else if (left.a > right.a) {
-                       return false;
-               }
-
-               if (left.b < right.b) {
-                       return true;
-               }
-               else if (left.b > right.b) {
-                       return false;
-               }
-
-               if (left.c < right.c) {
-                       return true;
-               }
-               else if (left.c > right.c) {
-                       return false;
-               }
-
-               return false;
-       }
-};
-
-typedef std::set<carve::triangulate::tri_idx, TriIdxCompare> TrianglesStorage;
-
-void carve_getRescaleMinMax(const carve::mesh::MeshSet<3> *left,
-                            const carve::mesh::MeshSet<3> *right,
-                            carve::geom3d::Vector *min,
-                            carve::geom3d::Vector *max);
-
-typedef void (*VertexAttrsCallback) (const carve::mesh::MeshSet<3>::vertex_t *orig_vert,
-                                     const carve::mesh::MeshSet<3>::vertex_t *new_vert,
-                                     void *userdata);
-
-typedef void (*UnionIntersectionsCallback) (const carve::mesh::MeshSet<3> *left,
-                                            const carve::mesh::MeshSet<3> *right,
-                                            void *userdata);
-
-void carve_unionIntersections(carve::csg::CSG *csg,
-                              carve::mesh::MeshSet<3> **left_r,
-                              carve::mesh::MeshSet<3> **right_r,
-                              VertexAttrsCallback vertex_attr_callback,
-                              UnionIntersectionsCallback callback,
-                              void *user_data);
-
-bool carve_checkPolyPlanarAndGetNormal(const std::vector<carve::mesh::MeshSet<3>::vertex_t> &vertex_storage,
-                                       const int verts_per_poly,
-                                       const int *verts_of_poly,
-                                       carve::math::Matrix3 *axis_matrix_r);
-
-int carve_triangulatePoly(struct ImportMeshData *import_data,
-                          CarveMeshImporter *mesh_importer,
-                          const std::vector<carve::mesh::MeshSet<3>::vertex_t> &vertex_storage,
-                          const int verts_per_poly,
-                          const int *verts_of_poly,
-                          const carve::math::Matrix3 &axis_matrix,
-                          std::vector<int> *face_indices,
-                          TrianglesStorage *triangles_storage);
-
-namespace carve {
-       namespace interpolate {
-
-               template<typename attr_t>
-               class VertexAttr : public Interpolator {
-               public:
-                       typedef const meshset_t::vertex_t *key_t;
-
-               protected:
-                       typedef std::unordered_map<key_t, attr_t> attrmap_t;
-
-                       attrmap_t attrs;
-
-                       virtual void resultFace(const carve::csg::CSG &csg,
-                                               const meshset_t::face_t *new_face,
-                                               const meshset_t::face_t *orig_face,
-                                               bool flipped)
-                       {
-                               typedef meshset_t::face_t::const_edge_iter_t const_edge_iter_t;
-                               for (const_edge_iter_t new_edge_iter = new_face->begin();
-                                        new_edge_iter != new_face->end();
-                                        ++new_edge_iter)
-                               {
-                                       typename attrmap_t::const_iterator found =
-                                               attrs.find(new_edge_iter->vert);
-                                       if (found == attrs.end()) {
-                                               for (const_edge_iter_t orig_edge_iter = orig_face->begin();
-                                                    orig_edge_iter != orig_face->end();
-                                                    ++orig_edge_iter)
-                                               {
-                                                       if ((orig_edge_iter->vert->v - new_edge_iter->vert->v).length2() < 1e-5) {
-                                                               attrs[new_edge_iter->vert] = attrs[orig_edge_iter->vert];
-                                                       }
-                                               }
-                                       }
-                               }
-                       }
-
-               public:
-                       bool hasAttribute(const meshset_t::vertex_t *v) {
-                               return attrs.find(v) != attrs.end();
-                       }
-
-                       const attr_t &getAttribute(const meshset_t::vertex_t *v, const attr_t &def = attr_t()) {
-                               typename attrmap_t::const_iterator found = attrs.find(v);
-                               if (found != attrs.end()) {
-                                       return found->second;
-                               }
-                               return def;
-                       }
-
-                       void setAttribute(const meshset_t::vertex_t *v, const attr_t &attr) {
-                               attrs[v] = attr;
-                       }
-
-                       void removeAttribute(const meshset_t::vertex_t *v) {
-                               typename attrmap_t::iterator it = attrs.find(v);
-                               if (it != attrs.end()) {
-                                       attrs.erase(it);
-                               }
-                       }
-               };
-
-               template<typename attr_t>
-               class SimpleFaceEdgeAttr : public Interpolator {
-               public:
-                       typedef std::pair<const meshset_t::face_t *, unsigned> key_t;
-
-               protected:
-                       typedef std::pair<const meshset_t::vertex_t *, const meshset_t::vertex_t *> vpair_t;
-
-                       struct key_hash {
-                               size_t operator()(const key_t &v) const {
-                                       return size_t(v.first) ^ size_t(v.second);
-                               }
-                       };
-                       struct vpair_hash {
-                               size_t operator()(const vpair_t &v) const {
-                                       return size_t(v.first) ^ size_t(v.second);
-                               }
-                       };
-
-                       typedef std::unordered_map<key_t, attr_t, key_hash> attrmap_t;
-                       typedef std::unordered_map<vpair_t, key_t, vpair_hash> edgedivmap_t;
-
-                       attrmap_t attrs;
-
-                       struct Hook : public Interpolator::Hook {
-                       public:
-                               virtual unsigned hookBits() const {
-                                       return carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT;
-                               }
-                               Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : Interpolator::Hook(_interpolator, _csg) {
-                               }
-                               virtual ~Hook() {
-                               }
-                       };
-
-                       virtual Interpolator::Hook *makeHook(carve::csg::CSG &csg) {
-                               return new Hook(this, csg);
-                       }
-
-                       virtual void processOutputFace(const carve::csg::CSG &csg,
-                                                      std::vector<carve::mesh::MeshSet<3>::face_t *> &new_faces,
-                                                      const meshset_t::face_t *orig_face,
-                                                      bool flipped) {
-                               edgedivmap_t undiv;
-
-                               for (meshset_t::face_t::const_edge_iter_t e = orig_face->begin(); e != orig_face->end(); ++e) {
-                                       key_t k(orig_face, e.idx());
-                                       typename attrmap_t::const_iterator attr_i = attrs.find(k);
-                                       if (attr_i == attrs.end()) {
-                                               continue;
-                                       } else {
-                                               undiv[vpair_t(e->v1(), e->v2())] = k;
-                                       }
-                               }
-
-                               for (size_t fnum = 0; fnum < new_faces.size(); ++fnum) {
-                                       const carve::mesh::MeshSet<3>::face_t *new_face = new_faces[fnum];
-                                       for (meshset_t::face_t::const_edge_iter_t e = new_face->begin(); e != new_face->end(); ++e) {
-                                               key_t k(new_face, e.idx());
-
-                                               vpair_t vp;
-                                               if (!flipped) {
-                                                       vp = vpair_t(e->v1(), e->v2());
-                                               } else {
-                                                       vp = vpair_t(e->v2(), e->v1());
-                                               }
-                                               typename edgedivmap_t::const_iterator vp_i;
-                                               if ((vp_i = undiv.find(vp)) != undiv.end()) {
-                                                       attrs[k] = attrs[vp_i->second];
-                                               }
-                                       }
-                               }
-                       }
-
-               public:
-
-                       bool hasAttribute(const meshset_t::face_t *f, unsigned e) {
-                               return attrs.find(std::make_pair(f, e)) != attrs.end();
-                       }
-
-                       attr_t getAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &def = attr_t()) {
-                               typename attrmap_t::const_iterator fv = attrs.find(std::make_pair(f, e));
-                               if (fv != attrs.end()) {
-                                       return (*fv).second;
-                               }
-                               return def;
-                       }
-
-                       void setAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &attr) {
-                               attrs[std::make_pair(f, e)] = attr;
-                       }
-
-                       void copyAttribute(const meshset_t::face_t *face,
-                                          unsigned edge,
-                                          SimpleFaceEdgeAttr<attr_t> *interpolator) {
-                               key_t key(face, edge);
-                               typename attrmap_t::const_iterator fv = interpolator->attrs.find(key);
-                               if (fv != interpolator->attrs.end()) {
-                                       attrs[key] = (*fv).second;
-                               }
-                       }
-
-                       void swapAttributes(SimpleFaceEdgeAttr<attr_t> *interpolator) {
-                               attrs.swap(interpolator->attrs);
-                       }
-
-                       SimpleFaceEdgeAttr() : Interpolator() {
-                       }
-
-                       virtual ~SimpleFaceEdgeAttr() {
-                       }
-               };
-
-               template<typename attr_t>
-               class SwapableFaceEdgeAttr : public FaceEdgeAttr<attr_t> {
-               public:
-                       typedef carve::mesh::MeshSet<3> meshset_t;
-
-                       void copyAttribute(const meshset_t::face_t *face,
-                                          unsigned edge,
-                                          SwapableFaceEdgeAttr<attr_t> *interpolator) {
-                               typename FaceEdgeAttr<attr_t>::key_t key(face, edge);
-                               typename FaceEdgeAttr<attr_t>::attrmap_t::const_iterator fv = interpolator->attrs.find(key);
-                               if (fv != interpolator->attrs.end()) {
-                                       this->attrs[key] = (*fv).second;
-                               }
-                       }
-
-                       void swapAttributes(SwapableFaceEdgeAttr<attr_t> *interpolator) {
-                               this->attrs.swap(interpolator->attrs);
-                       }
-               };
-       }  // namespace interpolate
-}  // namespace carve
-
-#endif  // __CARVE_UTIL_H__
diff --git a/extern/carve/files.txt b/extern/carve/files.txt
deleted file mode 100644 (file)
index 9598d07..0000000
+++ /dev/null
@@ -1,107 +0,0 @@
-include/carve/edge_impl.hpp
-include/carve/tag.hpp
-include/carve/colour.hpp
-include/carve/math_constants.hpp
-include/carve/csg.hpp
-include/carve/heap.hpp
-include/carve/vector.hpp
-include/carve/djset.hpp
-include/carve/mesh_impl.hpp
-include/carve/polyline_iter.hpp
-include/carve/input.hpp
-include/carve/geom2d.hpp
-include/carve/aabb_impl.hpp
-include/carve/geom.hpp
-include/carve/triangulator.hpp
-include/carve/pointset_iter.hpp
-include/carve/spacetree.hpp
-include/carve/vertex_impl.hpp
-include/carve/vcpp_config.h
-include/carve/octree_decl.hpp
-include/carve/rescale.hpp
-include/carve/collection_types.hpp
-include/carve/faceloop.hpp
-include/carve/polyhedron_base.hpp
-include/carve/vertex_decl.hpp
-include/carve/cbrt.h
-include/carve/matrix.hpp
-include/carve/tree.hpp
-include/carve/debug_hooks.hpp
-include/carve/rtree.hpp
-include/carve/math.hpp
-include/carve/convex_hull.hpp
-include/carve/polyline.hpp
-include/carve/geom3d.hpp
-include/carve/aabb.hpp
-include/carve/pointset_decl.hpp
-include/carve/intersection.hpp
-include/carve/face_impl.hpp
-include/carve/collection.hpp
-include/carve/poly_impl.hpp
-include/carve/exact.hpp
-include/carve/timing.hpp
-include/carve/poly.hpp
-include/carve/mesh.hpp
-include/carve/win32.h
-include/carve/mesh_simplify.hpp
-include/carve/classification.hpp
-include/carve/collection/unordered/fallback_impl.hpp
-include/carve/collection/unordered/std_impl.hpp
-include/carve/collection/unordered/vcpp_impl.hpp
-include/carve/collection/unordered/boost_impl.hpp
-include/carve/collection/unordered/libstdcpp_impl.hpp
-include/carve/collection/unordered/tr1_impl.hpp
-include/carve/collection/unordered.hpp
-include/carve/pointset.hpp
-include/carve/mesh_ops.hpp
-include/carve/triangle_intersection.hpp
-include/carve/octree_impl.hpp
-include/carve/pointset_impl.hpp
-include/carve/carve.hpp
-include/carve/kd_node.hpp
-include/carve/polyhedron_impl.hpp
-include/carve/interpolator.hpp
-include/carve/edge_decl.hpp
-include/carve/face_decl.hpp
-include/carve/geom_impl.hpp
-include/carve/util.hpp
-include/carve/random/random.h
-include/carve/gnu_cxx.h
-include/carve/polyline_decl.hpp
-include/carve/triangulator_impl.hpp
-include/carve/iobj.hpp
-include/carve/csg_triangulator.hpp
-include/carve/polyline_impl.hpp
-include/carve/poly_decl.hpp
-include/carve/polyhedron_decl.hpp
-lib/math.cpp
-lib/intersect_classify_edge.cpp
-lib/csg_detail.hpp
-lib/polyhedron.cpp
-lib/csg.cpp
-lib/intersect.cpp
-lib/csg_data.hpp
-lib/intersection.cpp
-lib/timing.cpp
-lib/intersect_classify_common_impl.hpp
-lib/geom2d.cpp
-lib/csg_collector.hpp
-lib/mesh.cpp
-lib/intersect_half_classify_group.cpp
-lib/octree.cpp
-lib/csg_collector.cpp
-lib/intersect_debug.hpp
-lib/intersect_classify_common.hpp
-lib/geom3d.cpp
-lib/intersect_face_division.cpp
-lib/face.cpp
-lib/triangulator.cpp
-lib/tag.cpp
-lib/intersect_classify_group.cpp
-lib/polyline.cpp
-lib/intersect_common.hpp
-lib/convex_hull.cpp
-lib/intersect_group.cpp
-lib/carve.cpp
-lib/pointset.cpp
-lib/intersect_debug.cpp
diff --git a/extern/carve/include/carve/aabb.hpp b/extern/carve/include/carve/aabb.hpp
deleted file mode 100644 (file)
index 9677358..0000000
+++ /dev/null
@@ -1,156 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-#pragma once
-
-#include <carve/carve.hpp>
-
-#include <carve/geom.hpp>
-
-#include <vector>
-
-namespace carve {
-  namespace geom {
-
-
-
-    // n-dimensional AABB
-    template<unsigned ndim>
-    struct aabb {
-      typedef vector<ndim> vector_t;
-      typedef aabb<ndim> aabb_t;
-
-      vector_t pos;     // the centre of the AABB
-      vector_t extent;  // the extent of the AABB - the vector from the centre to the maximal vertex.
-
-      void empty();
-
-      bool isEmpty() const;
-
-      void fit(const vector_t &v1);
-      void fit(const vector_t &v1, const vector_t &v2);
-      void fit(const vector_t &v1, const vector_t &v2, const vector_t &v3);
-
-      template<typename iter_t, typename value_type>
-      void _fit(iter_t begin, iter_t end, value_type);
-
-      template<typename iter_t>
-      void _fit(iter_t begin, iter_t end, vector_t);
-
-      template<typename iter_t>
-      void _fit(iter_t begin, iter_t end, aabb_t);
-
-      template<typename iter_t>
-      void fit(iter_t begin, iter_t end);
-
-      template<typename iter_t, typename adapt_t>
-      void fit(iter_t begin, iter_t end, adapt_t adapt);
-
-      void unionAABB(const aabb<ndim> &a);
-
-      void expand(double pad);
-
-      bool completelyContains(const aabb<ndim> &other) const;
-
-      bool containsPoint(const vector_t &v) const;
-
-      bool intersectsLineSegment(const vector_t &v1, const vector_t &v2) const;
-
-      double axisSeparation(const aabb<ndim> &other, unsigned axis) const;
-
-      double maxAxisSeparation(const aabb<ndim> &other) const;
-
-      bool intersects(const aabb<ndim> &other) const;
-      bool intersects(const sphere<ndim> &s) const;
-      bool intersects(const plane<ndim> &plane) const;
-      bool intersects(const ray<ndim> &ray) const;
-      bool intersects(tri<ndim> tri) const;
-      bool intersects(const linesegment<ndim> &ls) const;
-
-      std::pair<double, double> rangeInDirection(const carve::geom::vector<ndim> &v) const;
-
-      vector_t min() const;
-      vector_t mid() const;
-      vector_t max() const;
-
-      double min(unsigned dim) const;
-      double mid(unsigned dim) const;
-      double max(unsigned dim) const;
-
-      double volume() const;
-
-      int compareAxis(const axis_pos &ap) const;
-
-      void constrainMax(const axis_pos &ap);
-      void constrainMin(const axis_pos &ap);
-
-      aabb getAABB() const;
-
-      aabb(const vector_t &_pos = vector_t::ZERO(),
-           const vector_t &_extent = vector_t::ZERO());
-
-      template<typename iter_t, typename adapt_t>
-      aabb(iter_t begin, iter_t end, adapt_t adapt);
-
-      template<typename iter_t>
-      aabb(iter_t begin, iter_t end);
-
-      aabb(const aabb<ndim> &a, const aabb<ndim> &b);
-    };
-
-    template<unsigned ndim>
-    bool operator==(const aabb<ndim> &a, const aabb<ndim> &b);
-
-    template<unsigned ndim>
-    bool operator!=(const aabb<ndim> &a, const aabb<ndim> &b);
-
-    template<unsigned ndim>
-    std::ostream &operator<<(std::ostream &o, const aabb<ndim> &a);
-
-    template<unsigned ndim>
-    double distance2(const aabb<3> &a, const vector<ndim> &v);
-
-    template<unsigned ndim>
-    double distance(const aabb<3> &a, const vector<ndim> &v);
-
-
-
-    template<unsigned ndim, typename obj_t>
-    struct get_aabb {
-      aabb<ndim> operator()(const obj_t &obj) const {
-        return obj.getAABB();
-      }
-    };
-
-    template<unsigned ndim, typename obj_t>
-    struct get_aabb<ndim, obj_t *> {
-      aabb<ndim> operator()(const obj_t *obj) const {
-        return obj->getAABB();
-      }
-    };
-
-
-
-  }
-}
-
-namespace carve {
-  namespace geom3d {
-    typedef carve::geom::aabb<3> AABB;
-  }
-}
-
-#include <carve/aabb_impl.hpp>
diff --git a/extern/carve/include/carve/aabb_impl.hpp b/extern/carve/include/carve/aabb_impl.hpp
deleted file mode 100644 (file)
index c9028b7..0000000
+++ /dev/null
@@ -1,440 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-#pragma once
-
-#include <carve/carve.hpp>
-
-#include <carve/vector.hpp>
-#include <carve/geom3d.hpp>
-
-#include <carve/geom.hpp>
-
-#include <vector>
-
-namespace carve {
-  namespace geom {
-
-    template<unsigned ndim>
-    void aabb<ndim>::empty() {
-      pos.setZero();
-      extent.setZero();
-    }
-
-    template<unsigned ndim>
-    bool aabb<ndim>::isEmpty() const {
-      return extent.exactlyZero();
-    }
-
-    template<unsigned ndim>
-    template<typename iter_t, typename value_type>
-    void aabb<ndim>::_fit(iter_t begin, iter_t end, value_type) {
-      if (begin == end) {
-        empty();
-        return;
-      }
-
-      vector_t min, max;
-      aabb<ndim> a = get_aabb<ndim, value_type>()(*begin); ++begin;
-      min = a.min();
-      max = a.max();
-      while (begin != end) {
-        aabb<ndim> a = get_aabb<ndim, value_type>()(*begin); ++begin;
-        assign_op(min, min, a.min(), carve::util::min_functor());
-        assign_op(max, max, a.max(), carve::util::max_functor());
-      }
-
-      pos = (min + max) / 2.0;
-      assign_op(extent, max - pos, pos - min, carve::util::max_functor());
-    }
-
-    template<unsigned ndim>
-    template<typename iter_t>
-    void aabb<ndim>::_fit(iter_t begin, iter_t end, vector_t) {
-      if (begin == end) {
-        empty();
-        return;
-      }
-
-      vector_t min, max;
-      bounds(begin, end, min, max);
-      pos = (min + max) / 2.0;
-      assign_op(extent, max - pos, pos - min, carve::util::max_functor());
-    }
-
-    template<unsigned ndim>
-    template<typename iter_t>
-    void aabb<ndim>::_fit(iter_t begin, iter_t end, aabb_t) {
-      if (begin == end) {
-        empty();
-        return;
-      }
-
-      vector_t min, max;
-      aabb<ndim> a = *begin++;
-      min = a.min();
-      max = a.max();
-      while (begin != end) {
-        aabb<ndim> a = *begin; ++begin;
-        assign_op(min, min, a.min(), carve::util::min_functor());
-        assign_op(max, max, a.max(), carve::util::max_functor());
-      }
-
-      pos = (min + max) / 2.0;
-      assign_op(extent, max - pos, pos - min, carve::util::max_functor());
-    }
-
-    template<unsigned ndim>
-    void aabb<ndim>::fit(const vector_t &v1) {
-      pos = v1;
-      extent.setZero();
-    }
-
-    template<unsigned ndim>
-    void aabb<ndim>::fit(const vector_t &v1, const vector_t &v2) {
-      vector_t min, max;
-      assign_op(min, v1, v2, carve::util::min_functor());
-      assign_op(max, v1, v2, carve::util::max_functor());
-
-      pos = (min + max) / 2.0;
-      assign_op(extent, max - pos, pos - min, carve::util::max_functor());
-    }
-
-    template<unsigned ndim>
-    void aabb<ndim>::fit(const vector_t &v1, const vector_t &v2, const vector_t &v3) {
-      vector_t min, max;
-      min = max = v1;
-
-      assign_op(min, min, v2, carve::util::min_functor());
-      assign_op(max, max, v2, carve::util::max_functor());
-      assign_op(min, min, v3, carve::util::min_functor());
-      assign_op(max, max, v3, carve::util::max_functor());
-
-      pos = (min + max) / 2.0;
-      assign_op(extent, max - pos, pos - min, carve::util::max_functor());
-    }
-
-    template<unsigned ndim>
-    template<typename iter_t, typename adapt_t>
-    void aabb<ndim>::fit(iter_t begin, iter_t end, adapt_t adapt) {
-      vector_t min, max;
-
-      bounds(begin, end, adapt, min, max);
-      pos = (min + max) / 2.0;
-      assign_op(extent, max - pos, pos - min, carve::util::max_functor());
-    }
-
-    template<unsigned ndim>
-    template<typename iter_t>
-    void aabb<ndim>::fit(iter_t begin, iter_t end) {
-      _fit(begin, end, typename std::iterator_traits<iter_t>::value_type());
-    }
-
-    template<unsigned ndim>
-    void aabb<ndim>::expand(double pad) {
-      extent += pad;
-    }
-
-    template<unsigned ndim>
-    void aabb<ndim>::unionAABB(const aabb<ndim> &a) {
-      vector_t vmin, vmax;
-
-      assign_op(vmin, min(), a.min(), carve::util::min_functor());
-      assign_op(vmax, max(), a.max(), carve::util::max_functor());
-      pos = (vmin + vmax) / 2.0;
-      assign_op(extent, vmax - pos, pos - vmin, carve::util::max_functor());
-    }
-
-    template<unsigned ndim>
-    bool aabb<ndim>::completelyContains(const aabb<ndim> &other) const {
-      for (unsigned i = 0; i < ndim; ++i) {
-        if (fabs(other.pos.v[i] - pos.v[i]) + other.extent.v[i] > extent.v[i]) return false;
-      }
-      return true;
-    }
-
-    template<unsigned ndim>
-    bool aabb<ndim>::containsPoint(const vector_t &v) const {
-      for (unsigned i = 0; i < ndim; ++i) {
-        if (fabs(v.v[i] - pos.v[i]) > extent.v[i]) return false;
-      }
-      return true;
-    }
-
-    template<unsigned ndim>
-    double aabb<ndim>::axisSeparation(const aabb<ndim> &other, unsigned axis) const {
-      return fabs(other.pos.v[axis] - pos.v[axis]) - extent.v[axis] - other.extent.v[axis];
-    }
-
-    template<unsigned ndim>
-    double aabb<ndim>::maxAxisSeparation(const aabb<ndim> &other) const {
-      double m = axisSeparation(other, 0);
-      for (unsigned i = 1; i < ndim; ++i) {
-        m = std::max(m, axisSeparation(other, i));
-      }
-      return m;
-    }
-
-    template<unsigned ndim>
-    bool aabb<ndim>::intersects(const aabb<ndim> &other) const {
-      return maxAxisSeparation(other) <= 0.0;
-    }
-    template<unsigned ndim>
-    bool aabb<ndim>::intersects(const sphere<ndim> &s) const {
-      double r = 0.0;
-      for (unsigned i = 0; i < ndim; ++i) {
-        double t = fabs(s.C[i] - pos[i]) - extent[i]; if (t > 0.0) r += t*t;
-      }
-      return r <= s.r*s.r;
-    }
-
-    template<unsigned ndim>
-    bool aabb<ndim>::intersects(const plane<ndim> &plane) const {
-      double d1 = fabs(distance(plane, pos));
-      double d2 = dot(abs(plane.N), extent);
-      return d1 <= d2;
-    }
-
-    template<unsigned ndim>
-    bool aabb<ndim>::intersects(const linesegment<ndim> &ls) const {
-      return intersectsLineSegment(ls.v1, ls.v2);
-    }
-
-    template<unsigned ndim>
-    std::pair<double, double> aabb<ndim>::rangeInDirection(const carve::geom::vector<ndim> &v) const {
-      double d1 = dot(v, pos);
-      double d2 = dot(abs(v), extent);
-
-      return std::make_pair(d1 - d2, d1 + d2);
-    }
-
-    template<unsigned ndim>
-    typename aabb<ndim>::vector_t aabb<ndim>::min() const { return pos - extent; }
-
-    template<unsigned ndim>
-    typename aabb<ndim>::vector_t aabb<ndim>::mid() const { return pos; }
-
-    template<unsigned ndim>
-    typename aabb<ndim>::vector_t aabb<ndim>::max() const { return pos + extent; }
-
-    template<unsigned ndim>
-    double aabb<ndim>::min(unsigned dim) const { return pos.v[dim] - extent.v[dim]; }
-
-    template<unsigned ndim>
-    double aabb<ndim>::mid(unsigned dim) const { return pos.v[dim]; }
-
-    template<unsigned ndim>
-    double aabb<ndim>::max(unsigned dim) const { return pos.v[dim] + extent.v[dim]; }
-
-    template<unsigned ndim>
-    double aabb<ndim>::volume() const {
-      double v = 1.0;
-      for (size_t dim = 0; dim < ndim; ++dim) { v *= 2.0 * extent.v[dim]; }
-      return v;
-    }
-
-    template<unsigned ndim>
-    int aabb<ndim>::compareAxis(const axis_pos &ap) const {
-      double p = ap.pos - pos[ap.axis];
-      if (p > extent[ap.axis]) return -1;
-      if (p < -extent[ap.axis]) return +1;
-      return 0;
-    }
-
-    template<unsigned ndim>
-    void aabb<ndim>::constrainMax(const axis_pos &ap) {
-      if (pos[ap.axis] + extent[ap.axis] > ap.pos) {
-        double min = std::min(ap.pos, pos[ap.axis] - extent[ap.axis]);
-        pos[ap.axis] = (min + ap.pos) / 2.0;
-        extent[ap.axis] = ap.pos - pos[ap.axis];
-      }
-    }
-
-    template<unsigned ndim>
-    void aabb<ndim>::constrainMin(const axis_pos &ap) {
-      if (pos[ap.axis] - extent[ap.axis] < ap.pos) {
-        double max = std::max(ap.pos, pos[ap.axis] + extent[ap.axis]);
-        pos[ap.axis] = (ap.pos + max) / 2.0;
-        extent[ap.axis] = pos[ap.axis] - ap.pos;
-      }
-    }
-
-    template<unsigned ndim>
-    aabb<ndim> aabb<ndim>::getAABB() const {
-      return *this;
-    }
-
-    template<unsigned ndim>
-    aabb<ndim>::aabb(const vector_t &_pos,
-                     const vector_t &_extent) : pos(_pos), extent(_extent) {
-    }
-
-    template<unsigned ndim>
-    template<typename iter_t, typename adapt_t>
-    aabb<ndim>::aabb(iter_t begin, iter_t end, adapt_t adapt) {
-      fit(begin, end, adapt);
-    }
-
-    template<unsigned ndim>
-    template<typename iter_t>
-    aabb<ndim>::aabb(iter_t begin, iter_t end) {
-      fit(begin, end);
-    }
-
-    template<unsigned ndim>
-    aabb<ndim>::aabb(const aabb<ndim> &a, const aabb<ndim> &b) {
-      fit(a, b);
-    }
-
-    template<unsigned ndim>
-    bool operator==(const aabb<ndim> &a, const aabb<ndim> &b) {
-      return a.pos == b.pos && a.extent == b.extent;
-    }
-
-    template<unsigned ndim>
-    bool operator!=(const aabb<ndim> &a, const aabb<ndim> &b) {
-      return a.pos != b.pos || a.extent != b.extent;
-    }
-
-    template<unsigned ndim>
-    std::ostream &operator<<(std::ostream &o, const aabb<ndim> &a) {
-      o << (a.pos - a.extent) << "--" << (a.pos + a.extent);
-      return o;
-    }
-
-    template<unsigned ndim>
-    double distance2(const aabb<3> &a, const vector<ndim> &v) {
-      double d2 = 0.0;
-      for (unsigned i = 0; i < ndim; ++i) {
-        double d = ::fabs(v.v[i] - a.pos.v[i]) - a.extent.v[i];
-        if (d > 0.0) {
-          d2 += d * d;
-        }
-      }
-      return d2;
-    }
-
-    template<unsigned ndim>
-    double distance(const aabb<3> &a, const vector<ndim> &v) {
-      return ::sqrt(distance2(a, v));
-    }
-
-    template<>
-    inline bool aabb<3>::intersects(const ray<3> &ray) const {
-      vector<3> t = pos - ray.v;
-      double r;
-
-      //l.cross(x-axis)?
-      r = extent.y * fabs(ray.D.z) + extent.z * fabs(ray.D.y);
-      if (fabs(t.y * ray.D.z - t.z * ray.D.y) > r) return false;
-
-      //ray.D.cross(y-axis)?
-      r = extent.x * fabs(ray.D.z) + extent.z * fabs(ray.D.x);
-      if (fabs(t.z * ray.D.x - t.x * ray.D.z) > r) return false;
-
-      //ray.D.cross(z-axis)?
-      r = extent.x*fabs(ray.D.y) + extent.y*fabs(ray.D.x);
-      if (fabs(t.x * ray.D.y - t.y * ray.D.x) > r) return false;
-
-      return true;
-    }
-
-    template<>
-    inline bool aabb<3>::intersectsLineSegment(const vector<3> &v1, const vector<3> &v2) const {
-      vector<3> half_length = 0.5 * (v2 - v1);
-      vector<3> t = pos - half_length - v1;
-      double r;
-
-      //do any of the principal axes form a separating axis?
-      if(fabs(t.x) > extent.x + fabs(half_length.x)) return false;
-      if(fabs(t.y) > extent.y + fabs(half_length.y)) return false;
-      if(fabs(t.z) > extent.z + fabs(half_length.z)) return false;
-
-      // NOTE: Since the separating axis is perpendicular to the line in
-      // these last four cases, the line does not contribute to the
-      // projection.
-
-      //line.cross(x-axis)?
-      r = extent.y * fabs(half_length.z) + extent.z * fabs(half_length.y);
-      if (fabs(t.y * half_length.z - t.z * half_length.y) > r) return false;
-
-      //half_length.cross(y-axis)?
-      r = extent.x * fabs(half_length.z) + extent.z * fabs(half_length.x);
-      if (fabs(t.z * half_length.x - t.x * half_length.z) > r) return false;
-
-      //half_length.cross(z-axis)?
-      r = extent.x*fabs(half_length.y) + extent.y*fabs(half_length.x);
-      if (fabs(t.x * half_length.y - t.y * half_length.x) > r) return false;
-
-      return true;
-    }
-
-    template<int Ax, int Ay, int Az, int c>
-    static inline bool intersectsTriangle_axisTest_3(const aabb<3> &aabb, const tri<3> &tri) {
-      const int d = (c+1) % 3, e = (c+2) % 3;
-      const vector<3> a = cross(VECTOR(Ax, Ay, Az), tri.v[d] - tri.v[c]);
-      double p1 = dot(a, tri.v[c]), p2 = dot(a, tri.v[e]);
-      if (p1 > p2) std::swap(p1, p2);
-      const double r = dot(abs(a), aabb.extent);
-      return !(p1 > r || p2 < -r);
-    }
-
-    template<int c>
-    static inline bool intersectsTriangle_axisTest_2(const aabb<3> &aabb, const tri<3> &tri) {
-      double vmin = std::min(std::min(tri.v[0][c], tri.v[1][c]), tri.v[2][c]),
-             vmax = std::max(std::max(tri.v[0][c], tri.v[1][c]), tri.v[2][c]);
-      return !(vmin > aabb.extent[c] || vmax < -aabb.extent[c]);
-    }
-
-    static inline bool intersectsTriangle_axisTest_1(const aabb<3> &aabb, const tri<3> &tri) {
-      vector<3> n = cross(tri.v[1] - tri.v[0], tri.v[2] - tri.v[0]);
-      double d1 = fabs(dot(n, tri.v[0]));
-      double d2 = dot(abs(n), aabb.extent);
-      return d1 <= d2;
-    }
-
-    template<>
-    inline bool aabb<3>::intersects(tri<3> tri) const {
-      tri.v[0] -= pos;
-      tri.v[1] -= pos;
-      tri.v[2] -= pos;
-
-      if (!intersectsTriangle_axisTest_2<0>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_2<1>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_2<2>(*this, tri)) return false;
-
-      if (!intersectsTriangle_axisTest_3<1,0,0,0>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_3<1,0,0,1>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_3<1,0,0,2>(*this, tri)) return false;
-                                                          
-      if (!intersectsTriangle_axisTest_3<0,1,0,0>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_3<0,1,0,1>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_3<0,1,0,2>(*this, tri)) return false;
-                                                          
-      if (!intersectsTriangle_axisTest_3<0,0,1,0>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_3<0,0,1,1>(*this, tri)) return false;
-      if (!intersectsTriangle_axisTest_3<0,0,1,2>(*this, tri)) return false;
-
-      if (!intersectsTriangle_axisTest_1(*this, tri)) return false;
-
-      return true;
-    }
-
-
-
-  }
-}
diff --git a/extern/carve/include/carve/carve.hpp b/extern/carve/include/carve/carve.hpp
deleted file mode 100644 (file)
index 5f8d76e..0000000
+++ /dev/null
@@ -1,238 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-#pragma once
-
-#if defined(CMAKE_BUILD)
-#  include <carve/config.h>
-#elif defined(XCODE_BUILD)
-#  include <carve/xcode_config.h>
-#elif defined(_MSC_VER)
-#  include <carve/vcpp_config.h>
-#else
-#  include <carve/config.h>
-#endif
-
-#if defined(WIN32)
-#  include <carve/win32.h>
-#elif defined(__GNUC__)
-#  include <carve/gnu_cxx.h>
-#endif
-
-#if defined(CARVE_SYSTEM_BOOST)
-#  define BOOST_INCLUDE(x) <boost/x>
-#else
-#  define BOOST_INCLUDE(x) <carve/external/boost/x>
-#endif
-
-#include <math.h>
-
-#include <string>
-#include <set>
-#include <map>
-#include <vector>
-#include <list>
-#include <sstream>
-#include <iomanip>
-
-#include <carve/collection.hpp>
-
-#include <carve/util.hpp>
-
-#include <stdarg.h>
-
-#define STR(x) #x
-#define XSTR(x) STR(x)
-
-/**
- * \brief Top level Carve namespace.
- */
-namespace carve {
-  static struct noinit_t {} NOINIT;
-
-  inline std::string fmtstring(const char *fmt, ...);
-
-  /**
-   * \brief Base class for all Carve exceptions.
-   */
-  struct exception {
-  private:
-    mutable std::string err;
-    mutable std::ostringstream accum;
-
-  public:
-    exception(const std::string &e) : err(e), accum() { }
-    exception() : err(), accum() { }
-    exception(const exception &e) : err(e.str()), accum() { }
-    exception &operator=(const exception &e) {
-      if (this != &e) {
-        err = e.str();
-        accum.str("");
-      }
-      return *this;
-    }
-
-    const std::string &str() const {
-      if (accum.str().size() > 0) {
-        err += accum.str();
-        accum.str("");
-      }
-      return err;
-    }
-
-    template<typename T>
-    exception &operator<<(const T &t) {
-      accum << t;
-      return *this;
-    }
-  };
-
-  template<typename iter_t, typename order_t = std::less<typename std::iterator_traits<iter_t>::value_type > >
-  struct index_sort {
-    iter_t base;
-    order_t order;
-    index_sort(const iter_t &_base) : base(_base), order() { }
-    index_sort(const iter_t &_base, const order_t &_order) : base(_base), order(_order) { }
-    template<typename U>
-    bool operator()(const U &a, const U &b) {
-      return order(*(base + a), *(base + b));
-    }
-  };
-
-  template<typename iter_t, typename order_t>
-  index_sort<iter_t, order_t> make_index_sort(const iter_t &base, const order_t &order) {
-    return index_sort<iter_t, order_t>(base, order);
-  }
-
-  template<typename iter_t>
-  index_sort<iter_t> make_index_sort(const iter_t &base) {
-    return index_sort<iter_t>(base);
-  }
-
-
-  enum RayIntersectionClass {
-    RR_DEGENERATE = -2,
-    RR_PARALLEL = -1,
-    RR_NO_INTERSECTION = 0,
-    RR_INTERSECTION = 1
-  };
-
-  enum LineIntersectionClass {
-    COLINEAR        = -1,
-    NO_INTERSECTION = 0,
-    INTERSECTION_LL = 1,
-    INTERSECTION_PL = 2,
-    INTERSECTION_LP = 3,
-    INTERSECTION_PP = 4
-  };
-
-  enum PointClass {
-    POINT_UNK = -2,
-    POINT_OUT = -1,
-    POINT_ON = 0,
-    POINT_IN = 1,
-    POINT_VERTEX = 2,
-    POINT_EDGE = 3
-  };
-
-  enum IntersectionClass {
-    INTERSECT_BAD = -1,
-    INTERSECT_NONE = 0,
-    INTERSECT_FACE = 1,
-    INTERSECT_VERTEX = 2,
-    INTERSECT_EDGE = 3,
-    INTERSECT_PLANE = 4,
-  };
-
-
-
-  extern double EPSILON;
-  extern double EPSILON2;
-
-  static inline void setEpsilon(double ep) { EPSILON = ep; EPSILON2 = ep * ep; }
-
-
-
-  template<typename T>
-  struct identity_t {
-    typedef T argument_type;
-    typedef T result_type;
-    const T &operator()(const T &t) const { return t; }
-  };
-
-
-
-  template<typename iter_t>
-  inline bool is_sorted(iter_t first, iter_t last) {
-    if (first == last) return true;
-
-    iter_t iter = first;
-    iter_t next = first; ++next;
-    for (; next != last; iter = next, ++next) {
-      if (*next < *iter) {
-        return false;
-      }
-    }
-    return true;
-  }
-
-
-
-  template<typename iter_t,
-           typename pred_t>
-  inline bool is_sorted(iter_t first, iter_t last, pred_t pred) {
-    if (first == last) return true;
-
-    iter_t iter = first;
-    iter_t next = first; ++next;
-    for (; next != last; iter = next, ++next) {
-      if (pred(*next, *iter)) {
-        return false;
-      }
-    }
-    return true;
-  }
-
-
-
-  inline double rangeSeparation(const std::pair<double, double> &a,
-                                const std::pair<double, double> &b) {
-    if (a.second < b.first) {
-      return b.first - a.second;
-    } else if (b.second < a.first) {
-      return a.first - b.second;
-    } else {
-      return 0.0;
-    }
-  }
-}
-
-
-#if defined(_MSC_VER)
-#  define MACRO_BEGIN do {
-#  define MACRO_END   __pragma(warning(push)) __pragma(warning(disable:4127)) } while(0) __pragma(warning(pop))
-#else
-#  define MACRO_BEGIN do {
-#  define MACRO_END   } while(0)
-#endif
-
-#if !defined(CARVE_NODEBUG)
-#  define CARVE_ASSERT(x) MACRO_BEGIN if (!(x)) throw carve::exception() << __FILE__ << ":" << __LINE__ << "  " << #x; MACRO_END
-#else
-#  define CARVE_ASSERT(X)
-#endif
-
-#define CARVE_FAIL(x) MACRO_BEGIN throw carve::exception() << __FILE__ << ":" << __LINE__ << "  " << #x; MACRO_END
diff --git a/extern/carve/include/carve/cbrt.h b/extern/carve/include/carve/cbrt.h
deleted file mode 100644 (file)
index aeceab0..0000000
+++ /dev/null
@@ -1,93 +0,0 @@
-// N.B. only appropriate for IEEE doubles.
-// Cube root implementation obtained from code with the following notice:
-
-/* @(#)s_cbrt.c 1.3 95/01/18 */
-/*
- * ====================================================
- * Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
- *
- * Developed at SunSoft, a Sun Microsystems, Inc. business.
- * Permission to use, copy, modify, and distribute this
- * software is freely granted, provided that this notice 
- * is preserved.
- * ====================================================
- *
- */
-
-/* Sometimes it's necessary to define __LITTLE_ENDIAN explicitly
-   but these catch some common cases. */
-
-#if defined(i386) || defined(i486) || \
-       defined(intel) || defined(x86) || defined(i86pc) || \
-       defined(__alpha) || defined(__osf__)
-#define __LITTLE_ENDIAN
-#endif
-
-#ifdef __LITTLE_ENDIAN
-#define __HI(x) *(1+(int*)&x)
-#define __LO(x) *(int*)&x
-#define __HIp(x) *(1+(int*)x)
-#define __LOp(x) *(int*)x
-#else
-#define __HI(x) *(int*)&x
-#define __LO(x) *(1+(int*)&x)
-#define __HIp(x) *(int*)x
-#define __LOp(x) *(1+(int*)x)
-#endif
-
-/* cbrt(x)
- * Return cube root of x
- */
-
-inline double cbrt(double x) {
-
-  static const unsigned 
-    B1 = 715094163, /* B1 = (682-0.03306235651)*2**20 */
-    B2 = 696219795; /* B2 = (664-0.03306235651)*2**20 */
-  static const double
-    C =  5.42857142857142815906e-01, /* 19/35     = 0x3FE15F15, 0xF15F15F1 */
-    D = -7.05306122448979611050e-01, /* -864/1225 = 0xBFE691DE, 0x2532C834 */
-    E =  1.41428571428571436819e+00, /* 99/70     = 0x3FF6A0EA, 0x0EA0EA0F */
-    F =  1.60714285714285720630e+00, /* 45/28     = 0x3FF9B6DB, 0x6DB6DB6E */
-    G =  3.57142857142857150787e-01; /* 5/14      = 0x3FD6DB6D, 0xB6DB6DB7 */
-
-  int  hx;
-  double r,s,t=0.0,w;
-  unsigned sign;
-
-  hx = __HI(x);                /* high word of x */
-  sign=hx&0x80000000;          /* sign= sign(x) */
-  hx  ^=sign;
-  if(hx>=0x7ff00000) return(x+x); /* cbrt(NaN,INF) is itself */
-  if((hx|__LO(x))==0) 
-    return(x);         /* cbrt(0) is itself */
-
-  __HI(x) = hx;        /* x <- |x| */
-  /* rough cbrt to 5 bits */
-  if(hx<0x00100000)            /* subnormal number */
-    {__HI(t)=0x43500000;               /* set t= 2**54 */
-    t*=x; __HI(t)=__HI(t)/3+B2;
-    }
-  else
-    __HI(t)=hx/3+B1;   
-  
-
-  /* new cbrt to 23 bits, may be implemented in single precision */
-  r=t*t/x;
-  s=C+r*t;
-  t*=G+F/(s+E+D/s);    
-
-  /* chopped to 20 bits and make it larger than cbrt(x) */ 
-  __LO(t)=0; __HI(t)+=0x00000001;
-
-  /* one step newton iteration to 53 bits with error less than 0.667 ulps */
-  s=t*t;               /* t*t is exact */
-  r=x/s;
-  w=t+t;
-  r=(r-t)/(w+r);       /* r-s is exact */
-  t=t+t*r;
-
-  /* retore the sign bit */
-  __HI(t) |= sign;
-  return(t);
-}
diff --git a/extern/carve/include/carve/classification.hpp b/extern/carve/include/carve/classification.hpp
deleted file mode 100644 (file)
index ebda48e..0000000
+++ /dev/null
@@ -1,115 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/carve.hpp>
-#include <carve/collection_types.hpp>
-
-namespace carve {
-  namespace csg {
-
-    enum FaceClass {
-      FACE_UNCLASSIFIED = -3,
-      FACE_ON_ORIENT_OUT = -2,
-      FACE_OUT = -1,
-      FACE_ON = 0,
-      FACE_IN = +1,
-      FACE_ON_ORIENT_IN = +2
-    };
-
-    enum FaceClassBit {
-      FACE_ON_ORIENT_OUT_BIT = 0x01,
-      FACE_OUT_BIT           = 0x02,
-      FACE_IN_BIT            = 0x04,
-      FACE_ON_ORIENT_IN_BIT  = 0x08,
-
-      FACE_ANY_BIT           = 0x0f,
-      FACE_ON_BIT            = 0x09,
-      FACE_NOT_ON_BIT        = 0x06
-    };
-
-    static inline FaceClass class_bit_to_class(unsigned i) {
-      if (i & FACE_ON_ORIENT_OUT_BIT) return FACE_ON_ORIENT_OUT;
-      if (i & FACE_OUT_BIT) return FACE_OUT;
-      if (i & FACE_IN_BIT) return FACE_IN;
-      if (i & FACE_ON_ORIENT_IN_BIT) return FACE_ON_ORIENT_IN;
-      return FACE_UNCLASSIFIED;
-    }
-
-    static inline unsigned class_to_class_bit(FaceClass f) {
-      switch (f) {
-      case FACE_ON_ORIENT_OUT: return FACE_ON_ORIENT_OUT_BIT;
-      case FACE_OUT: return FACE_OUT_BIT;
-      case FACE_ON: return FACE_ON_BIT;
-      case FACE_IN: return FACE_IN_BIT;
-      case FACE_ON_ORIENT_IN: return FACE_ON_ORIENT_IN_BIT;
-      case FACE_UNCLASSIFIED: return FACE_ANY_BIT;
-      default: return 0;
-      }
-    }
-
-    enum EdgeClass {
-      EDGE_UNK = -2,
-      EDGE_OUT = -1,
-      EDGE_ON = 0,
-      EDGE_IN = 1
-    };
-
-
-
-    const char *ENUM(FaceClass f);
-    const char *ENUM(PointClass p);
-
-
-
-    struct ClassificationInfo {
-      const carve::mesh::Mesh<3> *intersected_mesh;
-      FaceClass classification;
-
-      ClassificationInfo() : intersected_mesh(NULL), classification(FACE_UNCLASSIFIED) { }
-      ClassificationInfo(const carve::mesh::Mesh<3> *_intersected_mesh,
-                         FaceClass _classification) :
-          intersected_mesh(_intersected_mesh),
-          classification(_classification) {
-      }
-      bool intersectedMeshIsClosed() const {
-        return intersected_mesh->isClosed();
-      }
-    };
-
-
-
-    struct EC2 {
-      EdgeClass cls[2];
-      EC2() { cls[0] = cls[1] = EDGE_UNK; }
-      EC2(EdgeClass a, EdgeClass b) { cls[0] = a; cls[1] = b; }
-    };
-
-    struct PC2 {
-      PointClass cls[2];
-      PC2() { cls[0] = cls[1] = POINT_UNK; }
-      PC2(PointClass a, PointClass b) { cls[0] = a; cls[1] = b; }
-    };
-
-    typedef std::unordered_map<std::pair<const carve::mesh::MeshSet<3>::vertex_t *, const carve::mesh::MeshSet<3>::vertex_t *>,
-                               EC2> EdgeClassification;
-
-    typedef std::unordered_map<const carve::mesh::Vertex<3> *, PC2> VertexClassification;
-
-  }
-}
diff --git a/extern/carve/include/carve/collection.hpp b/extern/carve/include/carve/collection.hpp
deleted file mode 100644 (file)
index 8104d20..0000000
+++ /dev/null
@@ -1,51 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/collection/unordered.hpp>
-
-namespace carve {
-
-  template<typename set_t>
-  class set_insert_iterator : public std::iterator<std::output_iterator_tag, void, void, void, void> {
-
-  protected:
-    set_t *set;
-  public:
-
-    set_insert_iterator(set_t &s) : set(&s) {
-    }
-
-    set_insert_iterator &
-    operator=(typename set_t::const_reference value) {
-      set->insert(value);
-      return *this;
-    }
-
-    set_insert_iterator &operator*() { return *this; }
-    set_insert_iterator &operator++() { return *this; }
-    set_insert_iterator &operator++(int) { return *this; }
-  };
-
-  template<typename set_t>
-  inline set_insert_iterator<set_t>
-  set_inserter(set_t &s) {
-    return set_insert_iterator<set_t>(s);
-  }
-
-}
diff --git a/extern/carve/include/carve/collection/unordered.hpp b/extern/carve/include/carve/collection/unordered.hpp
deleted file mode 100644 (file)
index e89022b..0000000
+++ /dev/null
@@ -1,43 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-#pragma once
-
-#if defined(HAVE_STD_UNORDERED_COLLECTIONS)
-
-#  include <carve/collection/unordered/std_impl.hpp>
-
-#elif defined(HAVE_TR1_UNORDERED_COLLECTIONS)
-
-#  include <carve/collection/unordered/tr1_impl.hpp>
-
-#elif defined(HAVE_BOOST_UNORDERED_COLLECTIONS)
-
-#  include <carve/collection/unordered/boost_impl.hpp>
-
-#elif defined(HAVE_LIBSTDCPP_UNORDERED_COLLECTIONS)
-
-#  include <carve/collection/unordered/libstdcpp_impl.hpp>
-
-#elif defined(_MSC_VER) && _MSC_VER >= 1300
-
-#  include <carve/collection/unordered/vcpp_impl.hpp>
-
-#else
-
-#  include <carve/collection/unordered/fallback_impl.hpp>
-
-#endif
diff --git a/extern/carve/include/carve/collection/unordered/boost_impl.hpp b/extern/carve/include/carve/collection/unordered/boost_impl.hpp
deleted file mode 100644 (file)
index 7247dce..0000000
+++ /dev/null
@@ -1,45 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include BOOST_INCLUDE(unordered_set.hpp)
-#include BOOST_INCLUDE(unordered_map.hpp)
-
-#include <functional>
-
-namespace std {
-  template <typename Key, typename T, typename Hash = boost::hash<Key>,
-            typename Pred = std::equal_to<Key> >
-  class unordered_map : public boost::unordered_map<Key, T, Hash, Pred> {
-
-  public:
-    typedef T data_type;
-  };
-
-  template <typename Key, typename T, typename Hash = boost::hash<Key>,
-            typename Pred = std::equal_to<Key> >
-  class unordered_multimap : public boost::unordered_multimap<Key, T, Hash, Pred> {
-  };
-
-  template <typename Value, typename Hash = boost::hash<Value>,
-            typename Pred = std::equal_to<Value> >
-  class unordered_set : public boost::unordered_set<Value, Hash, Pred> {
-  };
-}
-
-#undef UNORDERED_COLLECTIONS_SUPPORT_RESIZE
diff --git a/extern/carve/include/carve/collection/unordered/fallback_impl.hpp b/extern/carve/include/carve/collection/unordered/fallback_impl.hpp
deleted file mode 100644 (file)
index 98dd19f..0000000
+++ /dev/null
@@ -1,40 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <set>
-#include <map>
-
-namespace std {
-
-  template<typename K, typename T, typename H = int>
-  class unordered_map : public std::map<K, T> {
-    typedef std::map<K, T> super;
-  public:
-    typedef T data_type;
-  };
-
-  template<typename K, typename H = int>
-  class unordered_set : public std::set<K> {
-    typedef std::set<K> super;
-  public:
-  };
-
-}
-
-#undef UNORDERED_COLLECTIONS_SUPPORT_RESIZE
diff --git a/extern/carve/include/carve/collection/unordered/libstdcpp_impl.hpp b/extern/carve/include/carve/collection/unordered/libstdcpp_impl.hpp
deleted file mode 100644 (file)
index 6a61abb..0000000
+++ /dev/null
@@ -1,61 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-#pragma once
-
-#include <ext/hash_map>
-#include <ext/hash_set>
-
-namespace __gnu_cxx {
-  template <typename T>
-  struct hash<T *> : public std::unary_function<T *, size_t> {
-    size_t operator()(T *v) const {
-      size_t x = (size_t)(v);
-      return x + (x>>3);
-    }
-  };
-
-  template <typename A, typename B>
-  struct hash<std::pair<A, B> > : public std::unary_function<std::pair<A, B>, size_t> {
-    size_t operator()(const std::pair<A, B> &v) const {
-      std::size_t seed = 0;
-
-      seed ^= hash<A>()(v.first);
-      seed ^= hash<B>()(v.second) + (seed<<6) + (seed>>2);
-
-      return seed;
-    }
-  };
-}
-
-namespace std {
-
-  template<typename K, typename V, typename H = __gnu_cxx::hash<K> >
-  class unordered_map : public __gnu_cxx::hash_map<K, V, H> {
-    typedef __gnu_cxx::hash_map<K, V, H> super;
-  public:
-    typedef typename super::mapped_type data_type;
-  };
-
-  template<typename K, typename H = __gnu_cxx::hash<K> >
-  class unordered_set : public __gnu_cxx::hash_set<K, H> {
-    typedef __gnu_cxx::hash_set<K, H> super;
-  public:
-  };
-
-}
-
-#define UNORDERED_COLLECTIONS_SUPPORT_RESIZE 1
diff --git a/extern/carve/include/carve/collection/unordered/std_impl.hpp b/extern/carve/include/carve/collection/unordered/std_impl.hpp
deleted file mode 100644 (file)
index 1d3d4f8..0000000
+++ /dev/null
@@ -1,23 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <unordered_map>
-#include <unordered_set>
-
-#undef UNORDERED_COLLECTIONS_SUPPORT_RESIZE
diff --git a/extern/carve/include/carve/collection/unordered/tr1_impl.hpp b/extern/carve/include/carve/collection/unordered/tr1_impl.hpp
deleted file mode 100644 (file)
index 64789d2..0000000
+++ /dev/null
@@ -1,58 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <tr1/unordered_map>
-#include <tr1/unordered_set>
-#include <tr1/functional>
-
-namespace std {
-  namespace tr1 {
-    template <typename A, typename B>
-    struct hash<std::pair<A, B> > : public std::unary_function<std::pair<A, B>, size_t> {
-      size_t operator()(const std::pair<A, B> &v) const {
-        std::size_t seed = 0;
-
-        seed ^= hash<A>()(v.first);
-        seed ^= hash<B>()(v.second) + (seed<<6) + (seed>>2);
-
-        return seed;
-      }
-    };
-  }
-
-
-
-  template <typename Key, typename T,
-            typename Hash = tr1::hash<Key>,
-            typename Pred = std::equal_to<Key> >
-  class unordered_map : public std::tr1::unordered_map<Key, T, Hash, Pred> {
-  public:
-    typedef T data_type;
-  };
-
-  template <typename Value,
-            typename Hash = tr1::hash<Value>,
-            typename Pred = std::equal_to<Value> >
-  class unordered_set : public std::tr1::unordered_set<Value, Hash, Pred> {
-  public:
-  };
-
-}
-
-#undef UNORDERED_COLLECTIONS_SUPPORT_RESIZE
diff --git a/extern/carve/include/carve/collection/unordered/vcpp_impl.hpp b/extern/carve/include/carve/collection/unordered/vcpp_impl.hpp
deleted file mode 100644 (file)
index eaa1f75..0000000
+++ /dev/null
@@ -1,65 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <hash_map>
-#include <hash_set>
-
-namespace std {
-
-  namespace {
-
-    template<class Value, class Hash> class hash_traits {
-      Hash hash_value;
-      std::less<Value> comp;
-    public:
-      enum {
-        bucket_size = 4,
-        min_buckets = 8
-      };
-      // hash _Keyval to size_t value
-      size_t operator()(const Value& v) const {
-        return ((size_t)hash_value(v));
-      }
-      // test if _Keyval1 ordered before _Keyval2
-      bool operator()(const Value& v1, const Value& v2) const {
-        return (comp(v1, v2));
-      }
-    };
-
-  }
-
-  template <typename Key, typename T, typename Hash = stdext::hash_compare<Key, less<Key> >, typename Pred = std::equal_to<Key> >
-  class unordered_map 
-    : public stdext::hash_map<Key, T, hash_traits<Key, Hash> > {
-    typedef stdext::hash_map<Key, T, hash_traits<Key, Hash> > super;
-  public:
-    unordered_map() : super() {}
-  };
-
-  template <typename Value, typename Hash = stdext::hash_compare<Key, less<Key> >, typename Pred = std::equal_to<Value> >
-  class unordered_set
-    : public stdext::hash_set<Value, hash_traits<Value, Hash> > {
-    typedef stdext::hash_set<Value, hash_traits<Value, Hash> > super;
-  public:
-    unordered_set() : super() {}
-  };
-
-}
-
-#undef UNORDERED_COLLECTIONS_SUPPORT_RESIZE
diff --git a/extern/carve/include/carve/collection_types.hpp b/extern/carve/include/carve/collection_types.hpp
deleted file mode 100644 (file)
index 8c81737..0000000
+++ /dev/null
@@ -1,63 +0,0 @@
-
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/carve.hpp>
-
-#include <carve/mesh.hpp>
-
-namespace carve {
-  namespace csg {
-
-    typedef std::pair<
-      carve::mesh::MeshSet<3>::vertex_t *,
-      carve::mesh::MeshSet<3>::vertex_t *> V2;
-
-    typedef std::pair<
-      carve::mesh::MeshSet<3>::face_t *,
-      carve::mesh::MeshSet<3>::face_t *> F2;
-
-    static inline V2 ordered_edge(
-      carve::mesh::MeshSet<3>::vertex_t *a,
-      carve::mesh::MeshSet<3>::vertex_t *b) {
-      return V2(std::min(a, b), std::max(a, b));
-    }
-
-    static inline V2 flip(const V2 &v) {
-      return V2(v.second, v.first);
-    }
-
-    // include/carve/csg.hpp include/carve/faceloop.hpp
-    // lib/intersect.cpp lib/intersect_classify_common_impl.hpp
-    // lib/intersect_classify_edge.cpp
-    // lib/intersect_classify_group.cpp
-    // lib/intersect_classify_simple.cpp
-    // lib/intersect_face_division.cpp lib/intersect_group.cpp
-    // lib/intersect_half_classify_group.cpp
-    typedef std::unordered_set<V2> V2Set;
-
-    // include/carve/csg.hpp include/carve/polyhedron_decl.hpp
-    // lib/csg_collector.cpp lib/intersect.cpp
-    // lib/intersect_common.hpp lib/intersect_face_division.cpp
-    // lib/polyhedron.cpp
-    typedef std::unordered_map<
-      carve::mesh::MeshSet<3>::vertex_t *,
-      carve::mesh::MeshSet<3>::vertex_t *> VVMap;
-  }
-}
diff --git a/extern/carve/include/carve/colour.hpp b/extern/carve/include/carve/colour.hpp
deleted file mode 100644 (file)
index e21b8f4..0000000
+++ /dev/null
@@ -1,47 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/carve.hpp>
-#include <carve/geom.hpp>
-
-namespace carve {
-  namespace colour {
-    static inline void HSV2RGB(float H, float S, float V, float &r, float &g, float &b) {
-      H = 6.0f * H;
-      if (S < 5.0e-6) {
-        r = g = b = V; return;
-      } else {
-        int i = (int)H;
-        float f = H - i;
-        float p1 = V * (1.0f - S);
-        float p2 = V * (1.0f - S * f);
-        float p3 = V * (1.0f - S * (1.0f - f));
-        switch (i) {
-        case 0:  r = V;  g = p3; b = p1; return;
-        case 1:  r = p2; g = V;  b = p1; return;
-        case 2:  r = p1; g = V;  b = p3; return;
-        case 3:  r = p1; g = p2; b = V;  return;
-        case 4:  r = p3; g = p1; b = V;  return;
-        case 5:  r = V;  g = p1; b = p2; return;
-        }
-      }
-      r = g = b = 0.0;
-    }
-  }
-}
diff --git a/extern/carve/include/carve/config.h b/extern/carve/include/carve/config.h
deleted file mode 100644 (file)
index 3533c1a..0000000
+++ /dev/null
@@ -1,30 +0,0 @@
-#define CARVE_VERSION "2.0.0a"
-
-#undef CARVE_DEBUG
-#undef CARVE_DEBUG_WRITE_PLY_DATA
-
-#if defined(__GNUC__)
-#  if !defined(HAVE_BOOST_UNORDERED_COLLECTIONS)
-#    define HAVE_TR1_UNORDERED_COLLECTIONS
-#  endif
-
-#  define HAVE_STDINT_H
-#endif
-
-// Support for latest Clang/LLVM on FreeBSD which does have different libcxx.
-//
-// TODO(sergey): Move it some some more generic header with platform-specific
-//               declarations.
-
-// Indicates whether __is_heap is available
-#undef HAVE_IS_HEAP
-
-#ifdef __GNUC__
-// NeyBSD doesn't have __is_heap
-#  ifndef __NetBSD__
-#    define HAVE_IS_HEAP
-#    ifdef _LIBCPP_VERSION
-#      define __is_heap is_heap
-#    endif  // _LIBCPP_VERSION
-#  endif  // !__NetBSD__
-#endif  // __GNUC__
diff --git a/extern/carve/include/carve/convex_hull.hpp b/extern/carve/include/carve/convex_hull.hpp
deleted file mode 100644 (file)
index b7296ca..0000000
+++ /dev/null
@@ -1,52 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <list>
-#include <vector>
-#include <algorithm>
-
-#include <carve/carve.hpp>
-
-#include <carve/geom2d.hpp>
-
-namespace carve {
-  namespace geom {
-    std::vector<int> convexHull(const std::vector<carve::geom2d::P2> &points);
-
-    template<typename project_t, typename polygon_container_t>
-    std::vector<int> convexHull(const project_t &project, const polygon_container_t &points) {
-      std::vector<carve::geom2d::P2> proj;
-      proj.reserve(points.size());
-      for (typename polygon_container_t::const_iterator i = points.begin(); i != points.end(); ++i) {
-        proj.push_back(project(*i));
-      }
-      return convexHull(proj);
-    }
-
-    template<typename project_t, typename iter_t>
-    std::vector<int> convexHull(const project_t &project, iter_t beg, iter_t end, size_t size_hint = 0) {
-      std::vector<carve::geom2d::P2> proj;
-      if (size_hint) proj.reserve(size_hint);
-      for (; beg != end; ++beg) {
-        proj.push_back(project(*beg));
-      }
-      return convexHull(proj);
-    }
-  }
-}
diff --git a/extern/carve/include/carve/csg.hpp b/extern/carve/include/carve/csg.hpp
deleted file mode 100644 (file)
index 6ecfca0..0000000
+++ /dev/null
@@ -1,510 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <list>
-#include <vector>
-#include <algorithm>
-
-#include <carve/carve.hpp>
-
-#include <carve/geom3d.hpp>
-
-#include <carve/mesh.hpp>
-
-#include <carve/collection_types.hpp>
-#include <carve/classification.hpp>
-#include <carve/iobj.hpp>
-#include <carve/faceloop.hpp>
-#include <carve/intersection.hpp>
-#include <carve/rtree.hpp>
-
-namespace carve {
-  namespace csg {
-
-    class VertexPool {
-      typedef carve::mesh::MeshSet<3>::vertex_t vertex_t;
-
-      const static unsigned blocksize = 1024;
-      typedef std::list<std::vector<vertex_t> > pool_t;
-      pool_t pool;
-    public:
-      void reset();
-      vertex_t *get(const vertex_t::vector_t &v = vertex_t::vector_t::ZERO());
-      bool inPool(vertex_t *v) const;
-
-      VertexPool();
-      ~VertexPool();
-    };
-
-
-
-    namespace detail {
-      struct Data;
-      class LoopEdges;
-    }
-
-    /** 
-     * \class CSG
-     * \brief The class responsible for the computation of CSG operations.
-     * 
-     */
-    class CSG {
-    private:
-
-    public:
-      typedef carve::mesh::MeshSet<3> meshset_t;
-
-      struct Hook {
-        /** 
-         * \class Hook
-         * \brief Provides API access to intermediate steps in CSG calculation.
-         * 
-         */
-        virtual void intersectionVertex(const meshset_t::vertex_t * /* vertex */,
-                                        const IObjPairSet & /* intersections */) {
-        }
-        virtual void processOutputFace(std::vector<meshset_t::face_t *> & /* faces */,
-                                       const meshset_t::face_t * /* orig_face */,
-                                       bool /* flipped */) {
-        }
-        virtual void resultFace(const meshset_t::face_t * /* new_face */,
-                                const meshset_t::face_t * /* orig_face */,
-                                bool /* flipped */) {
-        }
-        virtual void edgeDivision(const meshset_t::edge_t * /* orig_edge */,
-                                  size_t /* orig_edge_idx */,
-                                  const meshset_t::vertex_t * /* v1 */,
-                                  const meshset_t::vertex_t * /* v2 */) {
-        }
-
-        virtual ~Hook() {
-        }
-      };
-
-        /** 
-         * \class Hooks
-         * \brief Management of API hooks.
-         * 
-         */
-      class Hooks {
-      public:
-        enum {
-          RESULT_FACE_HOOK         = 0,
-          PROCESS_OUTPUT_FACE_HOOK = 1,
-          INTERSECTION_VERTEX_HOOK = 2,
-          EDGE_DIVISION_HOOK       = 3,
-          HOOK_MAX                 = 4,
-
-          RESULT_FACE_BIT          = 0x0001,
-          PROCESS_OUTPUT_FACE_BIT  = 0x0002, 
-          INTERSECTION_VERTEX_BIT  = 0x0004,
-          EDGE_DIVISION_BIT        = 0x0008
-       };
-
-        std::vector<std::list<Hook *> > hooks;
-
-        bool hasHook(unsigned hook_num);
-
-        void intersectionVertex(const meshset_t::vertex_t *vertex,
-                                const IObjPairSet &intersections);
-
-        void processOutputFace(std::vector<meshset_t::face_t *> &faces,
-                               const meshset_t::face_t *orig_face,
-                               bool flipped);
-
-        void resultFace(const meshset_t::face_t *new_face,
-                        const meshset_t::face_t *orig_face,
-                        bool flipped);
-
-        void edgeDivision(const meshset_t::edge_t *orig_edge,
-                          size_t orig_edge_idx,
-                          const meshset_t::vertex_t *v1,
-                          const meshset_t::vertex_t *v2);
-
-        void registerHook(Hook *hook, unsigned hook_bits);
-        void unregisterHook(Hook *hook);
-
-        void reset();
-
-        Hooks();
-        ~Hooks();
-      };
-
-        /** 
-         * \class Collector
-         * \brief Base class for objects responsible for selecting result from which form the result polyhedron.
-         * 
-         */
-      class Collector {
-        Collector(const Collector &);
-        Collector &operator=(const Collector &);
-
-      protected:
-
-      public:
-        virtual void collect(FaceLoopGroup *group, CSG::Hooks &) =0;
-        virtual meshset_t *done(CSG::Hooks &) =0;
-
-        Collector() {}
-        virtual ~Collector() {}
-      };
-
-    private:
-      typedef carve::geom::RTreeNode<3, carve::mesh::Face<3> *> face_rtree_t;
-      typedef std::unordered_map<carve::mesh::Face<3> *, std::vector<carve::mesh::Face<3> *> > face_pairs_t;
-
-      /// The computed intersection data.
-      Intersections intersections;
-
-      /// A map from intersection point to a set of intersections
-      /// represented by pairs of intersection objects.
-      VertexIntersections vertex_intersections;
-
-      /// A pool from which temporary vertices are allocated. Also
-      /// provides testing for pool membership.
-      VertexPool vertex_pool;
-
-      void init();
-
-      void makeVertexIntersections();
-
-      void groupIntersections();
-
-      void _generateVertexVertexIntersections(meshset_t::vertex_t *va,
-                                              meshset_t::edge_t *eb);
-      void generateVertexVertexIntersections(meshset_t::face_t *a,
-                                             const std::vector<meshset_t::face_t *> &b);
-
-      void _generateVertexEdgeIntersections(meshset_t::vertex_t *va,
-                                            meshset_t::edge_t *eb);
-      void generateVertexEdgeIntersections(meshset_t::face_t *a,
-                                           const std::vector<meshset_t::face_t *> &b);
-
-      void _generateEdgeEdgeIntersections(meshset_t::edge_t *ea,
-                                          meshset_t::edge_t *eb);
-      void generateEdgeEdgeIntersections(meshset_t::face_t *a,
-                                         const std::vector<meshset_t::face_t *> &b);
-
-      void _generateVertexFaceIntersections(meshset_t::face_t *fa,
-                                            meshset_t::edge_t *eb);
-      void generateVertexFaceIntersections(meshset_t::face_t *a,
-                                           const std::vector<meshset_t::face_t *> &b);
-
-      void _generateEdgeFaceIntersections(meshset_t::face_t *fa,
-                                          meshset_t::edge_t *eb);
-      void generateEdgeFaceIntersections(meshset_t::face_t *a,
-                                         const std::vector<meshset_t::face_t *> &b);
-
-      void generateIntersectionCandidates(meshset_t *a,
-                                          const face_rtree_t *a_node,
-                                          meshset_t *b,
-                                          const face_rtree_t *b_node,
-                                          face_pairs_t &face_pairs,
-                                          bool descend_a = true);
-      /** 
-       * \brief Compute all points of intersection between poly \a a and poly \a b
-       * 
-       * @param a Polyhedron a.
-       * @param b Polyhedron b.
-       */
-      void generateIntersections(meshset_t *a,
-                                 const face_rtree_t *a_node,
-                                 meshset_t *b,
-                                 const face_rtree_t *b_node,
-                                 detail::Data &data);
-
-      /** 
-       * \brief Generate tables of intersecting pairs of faces.
-       *
-       * @param[out] data Internal data-structure holding intersection info.
-       */
-      void intersectingFacePairs(detail::Data &data);
-
-      /** 
-       * \brief Divide edges in \a edges that are intersected by polyhedron \a poly
-       * 
-       * @param edges The edges to divide.
-       * @param[in] poly The polyhedron to divide against.
-       * @param[in,out] data Intersection information.
-       */
-      void divideEdges(
-        const std::vector<meshset_t::edge_t> &edges,
-        meshset_t *poly,
-        detail::Data &data);
-
-      void divideIntersectedEdges(detail::Data &data);
-
-      /** 
-       * \brief From the intersection points of pairs of intersecting faces, compute intersection edges.
-       * 
-       * @param[out] eclass Classification information about created edges.
-       * @param[in,out] data Intersection information.
-       */
-      void makeFaceEdges(
-        EdgeClassification &eclass,
-        detail::Data &data);
-
-      friend void classifyEasyFaces(
-        FaceLoopList &face_loops,
-        VertexClassification &vclass,
-        meshset_t *other_poly,
-        int other_poly_num,
-        CSG &csg,
-        CSG::Collector &collector);
-
-      size_t generateFaceLoops(
-        meshset_t *poly,
-        const detail::Data &data,
-        FaceLoopList &face_loops_out);
-
-
-
-      // intersect_group.cpp
-
-      /** 
-       * \brief Build a loop edge mapping from a list of face loops.
-       * 
-       * @param[in] loops A list of face loops.
-       * @param[in] edge_count A hint as to the number of edges in \a loops.
-       * @param[out] edge_map The calculated map of edges to loops.
-       */
-      void makeEdgeMap(
-        const FaceLoopList &loops,
-        size_t edge_count,
-        detail::LoopEdges &edge_map);
-
-      /** 
-       * \brief Divide a list of face loops into groups that are connected by at least one edge not present in \a no_cross.
-       * 
-       * @param[in] src The source mesh from which these loops derive.
-       * @param[in,out] face_loops The list of loops (will be emptied as a side effect)
-       * @param[in] loop_edges A loop edge map used for traversing connected loops.
-       * @param[in] no_cross A set of edges not to cross.
-       * @param[out] out_loops A list of grouped face loops.
-       */
-      void groupFaceLoops(
-        meshset_t *src,
-        FaceLoopList &face_loops,
-        const detail::LoopEdges &loop_edges,
-        const V2Set &no_cross,
-        FLGroupList &out_loops);
-
-      /** 
-       * \brief Find the set of edges shared between two edge maps.
-       * 
-       * @param[in] edge_map_a The first edge map.
-       * @param[in] edge_map_b The second edge map.
-       * @param[out] shared_edges The resulting set of common edges.
-       */
-      void findSharedEdges(
-        const detail::LoopEdges &edge_map_a,
-        const detail::LoopEdges &edge_map_b,
-        V2Set &shared_edges);
-
-
-      // intersect_classify_edge.cpp
-
-      /** 
-       * 
-       * 
-       * @param shared_edges 
-       * @param vclass 
-       * @param poly_a 
-       * @param a_loops_grouped 
-       * @param a_edge_map 
-       * @param poly_b 
-       * @param b_loops_grouped 
-       * @param b_edge_map 
-       * @param collector 
-       */
-      void classifyFaceGroupsEdge(
-        const V2Set &shared_edges,
-        VertexClassification &vclass,
-        meshset_t *poly_a,
-        const face_rtree_t *poly_a_rtree,
-        FLGroupList &a_loops_grouped,
-        const detail::LoopEdges &a_edge_map,
-        meshset_t *poly_b,
-        const face_rtree_t *poly_b_rtree,
-        FLGroupList &b_loops_grouped,
-        const detail::LoopEdges &b_edge_map,
-        CSG::Collector &collector);
-
-      // intersect_classify_group.cpp
-
-      /** 
-       * 
-       * 
-       * @param shared_edges 
-       * @param vclass 
-       * @param poly_a 
-       * @param a_loops_grouped 
-       * @param a_edge_map 
-       * @param poly_b 
-       * @param b_loops_grouped 
-       * @param b_edge_map 
-       * @param collector 
-       */
-      void classifyFaceGroups(
-        const V2Set &shared_edges,
-        VertexClassification &vclass,
-        meshset_t *poly_a, 
-        const face_rtree_t *poly_a_rtree,
-        FLGroupList &a_loops_grouped,
-        const detail::LoopEdges &a_edge_map,
-        meshset_t *poly_b,
-        const face_rtree_t *poly_b_rtree,
-        FLGroupList &b_loops_grouped,
-        const detail::LoopEdges &b_edge_map,
-        CSG::Collector &collector);
-
-      // intersect_half_classify_group.cpp
-
-      /** 
-       * 
-       * 
-       * @param shared_edges 
-       * @param vclass 
-       * @param poly_a 
-       * @param a_loops_grouped 
-       * @param a_edge_map 
-       * @param poly_b 
-       * @param b_loops_grouped 
-       * @param b_edge_map 
-       * @param FaceClass 
-       * @param b_out 
-       */
-      void halfClassifyFaceGroups(
-        const V2Set &shared_edges,
-        VertexClassification &vclass,
-        meshset_t *poly_a, 
-        const face_rtree_t *poly_a_rtree,
-        FLGroupList &a_loops_grouped,
-        const detail::LoopEdges &a_edge_map,
-        meshset_t *poly_b,
-        const face_rtree_t *poly_b_rtree,
-        FLGroupList &b_loops_grouped,
-        const detail::LoopEdges &b_edge_map,
-        std::list<std::pair<FaceClass, meshset_t  *> > &b_out);
-
-      // intersect.cpp
-
-      /** 
-       * \brief The main calculation method for CSG.
-       * 
-       * @param[in] a Polyhedron a
-       * @param[in] b Polyhedron b
-       * @param[out] vclass 
-       * @param[out] eclass 
-       * @param[out] a_face_loops 
-       * @param[out] b_face_loops 
-       * @param[out] a_edge_count 
-       * @param[out] b_edge_count 
-       */
-      void calc(
-        meshset_t  *a,
-        const face_rtree_t *a_rtree,
-        meshset_t  *b,
-        const face_rtree_t *b_rtree,
-        VertexClassification &vclass,
-        EdgeClassification &eclass,
-        FaceLoopList &a_face_loops,
-        FaceLoopList &b_face_loops,
-        size_t &a_edge_count,
-        size_t &b_edge_count);
-
-    public:
-      /**
-       * \enum OP
-       * \brief Enumeration of the supported CSG operations.
-       */
-      enum OP {
-        UNION,                  /**< in a or b. */
-        INTERSECTION,           /**< in a and b. */
-        A_MINUS_B,              /**< in a, but not b. */
-        B_MINUS_A,              /**< in b, but not a. */
-        SYMMETRIC_DIFFERENCE,   /**< in a or b, but not both. */
-        ALL                     /**< all split faces from a and b */
-      };
-
-      /**
-       * \enum CLASSIFY_TYPE
-       * \brief The type of classification algorithm to use.
-       */
-      enum CLASSIFY_TYPE {
-        CLASSIFY_NORMAL,        /**< Normal (group) classifier. */
-        CLASSIFY_EDGE           /**< Edge classifier. */
-      };
-
-      CSG::Hooks hooks;         /**< The manager for calculation hooks. */
-
-      CSG();
-      ~CSG();
-
-      /** 
-       * \brief Compute a CSG operation between two polyhedra, \a a and \a b.
-       * 
-       * @param a Polyhedron a
-       * @param b Polyhedron b
-       * @param collector The collector (determines the CSG operation performed)
-       * @param shared_edges A pointer to a set that will be populated with shared edges (if not NULL).
-       * @param classify_type The type of classifier to use.
-       * 
-       * @return 
-       */
-      meshset_t *compute(
-        meshset_t *a,
-        meshset_t *b,
-        CSG::Collector &collector,
-        V2Set *shared_edges = NULL,
-        CLASSIFY_TYPE classify_type = CLASSIFY_NORMAL);
-
-      /** 
-       * \brief Compute a CSG operation between two closed polyhedra, \a a and \a b.
-       * 
-       * @param a Polyhedron a
-       * @param b Polyhedron b
-       * @param op The CSG operation (A collector is created automatically).
-       * @param shared_edges A pointer to a set that will be populated with shared edges (if not NULL).
-       * @param classify_type The type of classifier to use.
-       * 
-       * @return 
-       */
-      meshset_t *compute(
-        meshset_t *a,
-        meshset_t *b,
-        OP op,
-        V2Set *shared_edges = NULL,
-        CLASSIFY_TYPE classify_type = CLASSIFY_NORMAL);
-
-      void slice(
-        meshset_t *a,
-        meshset_t *b,
-        std::list<meshset_t  *> &a_sliced,
-        std::list<meshset_t  *> &b_sliced,
-        V2Set *shared_edges = NULL);
-
-      bool sliceAndClassify(
-        meshset_t *closed,
-        meshset_t *open,
-        std::list<std::pair<FaceClass, meshset_t *> > &result,
-        V2Set *shared_edges = NULL);
-    };
-  }
-}
diff --git a/extern/carve/include/carve/csg_triangulator.hpp b/extern/carve/include/carve/csg_triangulator.hpp
deleted file mode 100644 (file)
index 4765d0b..0000000
+++ /dev/null
@@ -1,435 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-#include <carve/csg.hpp>
-#include <carve/tag.hpp>
-#include <carve/poly.hpp>
-#include <carve/triangulator.hpp>
-#include <deque>
-
-namespace carve {
-  namespace csg {
-
-    namespace detail {
-      template<bool with_improvement>
-      class CarveTriangulator : public csg::CSG::Hook {
-
-      public:
-        CarveTriangulator() {
-        }
-
-        virtual ~CarveTriangulator() {
-        }
-
-        virtual void processOutputFace(std::vector<carve::mesh::MeshSet<3>::face_t *> &faces,
-                                       const carve::mesh::MeshSet<3>::face_t *orig,
-                                       bool flipped) {
-          std::vector<carve::mesh::MeshSet<3>::face_t *> out_faces;
-
-          size_t n_tris = 0;
-          for (size_t f = 0; f < faces.size(); ++f) {
-            CARVE_ASSERT(faces[f]->nVertices() >= 3);
-            n_tris += faces[f]->nVertices() - 2;
-          }
-
-          out_faces.reserve(n_tris);
-
-          for (size_t f = 0; f < faces.size(); ++f) {
-            carve::mesh::MeshSet<3>::face_t *face = faces[f];
-
-            if (face->nVertices() == 3) {
-              out_faces.push_back(face);
-              continue;
-            }
-
-            std::vector<triangulate::tri_idx> result;
-
-            std::vector<carve::mesh::MeshSet<3>::vertex_t *> vloop;
-            face->getVertices(vloop);
-
-            triangulate::triangulate(
-                carve::mesh::MeshSet<3>::face_t::projection_mapping(face->project),
-                vloop,
-                result);
-
-            if (with_improvement) {
-              triangulate::improve(
-                  carve::mesh::MeshSet<3>::face_t::projection_mapping(face->project),
-                  vloop,
-                  carve::mesh::vertex_distance(),
-                  result);
-            }
-
-            std::vector<carve::mesh::MeshSet<3>::vertex_t *> fv;
-            fv.resize(3);
-            for (size_t i = 0; i < result.size(); ++i) {
-              fv[0] = vloop[result[i].a];
-              fv[1] = vloop[result[i].b];
-              fv[2] = vloop[result[i].c];
-              out_faces.push_back(face->create(fv.begin(), fv.end(), false));
-            }
-            delete face;
-          }
-          std::swap(faces, out_faces);
-        }
-      };
-    }
-
-    typedef detail::CarveTriangulator<false> CarveTriangulator;
-    typedef detail::CarveTriangulator<true> CarveTriangulatorWithImprovement;
-
-    class CarveTriangulationImprover : public csg::CSG::Hook {
-    public:
-      CarveTriangulationImprover() {
-      }
-
-      virtual ~CarveTriangulationImprover() {
-      }
-
-      virtual void processOutputFace(std::vector<carve::mesh::MeshSet<3>::face_t *> &faces,
-                                     const carve::mesh::MeshSet<3>::face_t *orig,
-                                     bool flipped) {
-        if (faces.size() == 1) return;
-
-        // doing improvement as a separate hook is much messier than
-        // just incorporating it into the triangulation hook.
-
-        typedef std::map<carve::mesh::MeshSet<3>::vertex_t *, size_t> vert_map_t;
-        std::vector<carve::mesh::MeshSet<3>::face_t *> out_faces;
-        vert_map_t vert_map;
-
-        out_faces.reserve(faces.size());
-
-
-        carve::mesh::MeshSet<3>::face_t::projection_mapping projector(faces[0]->project);
-
-        std::vector<triangulate::tri_idx> result;
-
-        for (size_t f = 0; f < faces.size(); ++f) {
-          carve::mesh::MeshSet<3>::face_t *face = faces[f];
-          if (face->nVertices() != 3) {
-            out_faces.push_back(face);
-          } else {
-            triangulate::tri_idx tri;
-            for (carve::mesh::MeshSet<3>::face_t::edge_iter_t i = face->begin(); i != face->end(); ++i) {
-              size_t v = 0;
-              vert_map_t::iterator j = vert_map.find(i->vert);
-              if (j == vert_map.end()) {
-                v = vert_map.size();
-                vert_map[i->vert] = v;
-              } else {
-                v = (*j).second;
-              }
-              tri.v[i.idx()] = v;
-            }
-            result.push_back(tri);
-            delete face;
-          }
-        }
-
-        std::vector<carve::mesh::MeshSet<3>::vertex_t *> verts;
-        verts.resize(vert_map.size());
-        for (vert_map_t::iterator i = vert_map.begin(); i != vert_map.end(); ++i) {
-          verts[(*i).second] = (*i).first;
-        }
-        triangulate::improve(projector, verts, carve::mesh::vertex_distance(), result);
-
-        std::vector<carve::mesh::MeshSet<3>::vertex_t *> fv;
-        fv.resize(3);
-        for (size_t i = 0; i < result.size(); ++i) {
-          fv[0] = verts[result[i].a];
-          fv[1] = verts[result[i].b];
-          fv[2] = verts[result[i].c];
-          out_faces.push_back(orig->create(fv.begin(), fv.end(), false));
-        }
-
-        std::swap(faces, out_faces);
-      }
-    };
-
-    class CarveTriangulationQuadMerger : public csg::CSG::Hook {
-      // this code is incomplete.
-      typedef std::map<V2, F2> edge_map_t;
-
-    public:
-      CarveTriangulationQuadMerger() {
-      }
-
-      virtual ~CarveTriangulationQuadMerger() {
-      }
-
-      double scoreQuad(edge_map_t::iterator i, edge_map_t &edge_map) {
-        if (!(*i).second.first || !(*i).second.second) return -1;
-        return -1;
-      }
-
-      carve::mesh::MeshSet<3>::face_t *mergeQuad(edge_map_t::iterator i, edge_map_t &edge_map) {
-        return NULL;
-      }
-
-      void recordEdge(carve::mesh::MeshSet<3>::vertex_t *v1,
-                      carve::mesh::MeshSet<3>::vertex_t *v2,
-                      carve::mesh::MeshSet<3>::face_t *f,
-                      edge_map_t &edge_map) {
-        if (v1 < v2) {
-          edge_map[V2(v1, v2)].first = f;
-        } else {
-          edge_map[V2(v2, v1)].second = f;
-        }
-      }
-
-      virtual void processOutputFace(std::vector<carve::mesh::MeshSet<3>::face_t *> &faces,
-                                     const carve::mesh::MeshSet<3>::face_t *orig,
-                                     bool flipped) {
-        if (faces.size() == 1) return;
-
-        std::vector<carve::mesh::MeshSet<3>::face_t *> out_faces;
-        edge_map_t edge_map;
-
-        out_faces.reserve(faces.size());
-
-        poly::p2_adapt_project<3> projector(faces[0]->project);
-
-        for (size_t f = 0; f < faces.size(); ++f) {
-          carve::mesh::MeshSet<3>::face_t *face = faces[f];
-          if (face->nVertices() != 3) {
-            out_faces.push_back(face);
-          } else {
-            carve::mesh::MeshSet<3>::face_t::vertex_t *v1, *v2, *v3;
-            v1 = face->edge->vert;
-            v2 = face->edge->next->vert;
-            v3 = face->edge->next->next->vert;
-            recordEdge(v1, v2, face, edge_map);
-            recordEdge(v2, v3, face, edge_map);
-            recordEdge(v3, v1, face, edge_map);
-          }
-        }
-
-        for (edge_map_t::iterator i = edge_map.begin(); i != edge_map.end();) {
-          if ((*i).second.first && (*i).second.second) {
-            ++i;
-          } else {
-            edge_map.erase(i++);
-          }
-        }
-
-        while (edge_map.size()) {
-          edge_map_t::iterator i = edge_map.begin();
-          edge_map_t::iterator best = i;
-          double best_score = scoreQuad(i, edge_map);
-          for (++i; i != edge_map.end(); ++i) {
-            double score = scoreQuad(i, edge_map);
-            if (score > best_score) best = i;
-          }
-          if (best_score < 0) break;
-          out_faces.push_back(mergeQuad(best, edge_map));
-        }
-
-        if (edge_map.size()) {
-          tagable::tag_begin();
-          for (edge_map_t::iterator i = edge_map.begin(); i != edge_map.end(); ++i) {
-            carve::mesh::MeshSet<3>::face_t *a = const_cast<carve::mesh::MeshSet<3>::face_t *>((*i).second.first);
-            carve::mesh::MeshSet<3>::face_t *b = const_cast<carve::mesh::MeshSet<3>::face_t *>((*i).second.first);
-            if (a && a->tag_once()) out_faces.push_back(a);
-            if (b && b->tag_once()) out_faces.push_back(b);
-          }
-        }
-
-        std::swap(faces, out_faces);
-      }
-    };
-
-    class CarveHoleResolver : public csg::CSG::Hook {
-
-    public:
-      CarveHoleResolver() {
-      }
-
-      virtual ~CarveHoleResolver() {
-      }
-
-      bool findRepeatedEdges(const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &vertices,
-                             std::list<std::pair<size_t, size_t> > &edge_pos) {
-        std::map<V2, size_t> edges;
-        for (size_t i = 0; i < vertices.size() - 1; ++i) {
-          edges[std::make_pair(vertices[i], vertices[i+1])] = i;
-        }
-        edges[std::make_pair(vertices[vertices.size()-1], vertices[0])] = vertices.size() - 1;
-
-        for (std::map<V2, size_t>::iterator i = edges.begin(); i != edges.end(); ++i) {
-          V2 rev = V2((*i).first.second, (*i).first.first);
-          std::map<V2, size_t>::iterator j = edges.find(rev);
-          if (j != edges.end()) {
-            edge_pos.push_back(std::make_pair((*i).second, (*j).second));
-          }
-        }
-        return edge_pos.size() > 0;
-      }
-
-      void flood(size_t t1,
-                 size_t t2,
-                 size_t old_grp,
-                 size_t new_grp_1,
-                 size_t new_grp_2,
-                 std::vector<size_t> &grp,
-                 const std::vector<triangulate::tri_idx> &tris,
-                 const std::map<std::pair<size_t, size_t>, size_t> &tri_edge) {
-        grp[t1] = new_grp_1;
-        grp[t2] = new_grp_2;
-
-        std::deque<size_t> to_visit;
-        to_visit.push_back(t1);
-        to_visit.push_back(t2);
-        std::vector<std::pair<size_t, size_t> > rev;
-        rev.resize(3);
-        while (to_visit.size()) {
-          size_t curr = to_visit.front();
-          to_visit.pop_front();
-          triangulate::tri_idx ct = tris[curr];
-          rev[0] = std::make_pair(ct.b, ct.a);
-          rev[1] = std::make_pair(ct.c, ct.b);
-          rev[2] = std::make_pair(ct.a, ct.c);
-
-          for (size_t i = 0; i < 3; ++i) {
-            std::map<std::pair<size_t, size_t>, size_t>::const_iterator adj = tri_edge.find(rev[i]);
-            if (adj == tri_edge.end()) continue;
-            size_t next = (*adj).second;
-            if (grp[next] != old_grp) continue;
-            grp[next] = grp[curr];
-            to_visit.push_back(next);
-          }
-        }
-      }
-
-      void findPerimeter(const std::vector<triangulate::tri_idx> &tris,
-                         const std::vector<carve::mesh::MeshSet<3>::vertex_t *> &verts,
-                         std::vector<carve::mesh::MeshSet<3>::vertex_t *> &out) {
-        std::map<std::pair<size_t, size_t>, size_t> edges;
-        for (size_t i = 0; i < tris.size(); ++i) {
-          edges[std::make_pair(tris[i].a, tris[i].b)] = i;
-          edges[std::make_pair(tris[i].b, tris[i].c)] = i;
-          edges[std::make_pair(tris[i].c, tris[i].a)] = i;
-        }
-        std::map<size_t, size_t> unpaired;
-        for (std::map<std::pair<size_t, size_t>, size_t>::iterator i = edges.begin(); i != edges.end(); ++i) {
-          if (edges.find(std::make_pair((*i).first.second, (*i).first.first)) == edges.end()) {
-            CARVE_ASSERT(unpaired.find((*i).first.first) == unpaired.end());
-            unpaired[(*i).first.first] = (*i).first.second;
-          }
-        }
-        out.clear();
-        out.reserve(unpaired.size());
-        size_t start = (*unpaired.begin()).first;
-        size_t vert = start;
-        do {
-          out.push_back(verts[vert]);
-          CARVE_ASSERT(unpaired.find(vert) != unpaired.end());
-          vert = unpaired[vert];
-        } while (vert != start);
-      }
-
-      virtual void processOutputFace(std::vector<carve::mesh::MeshSet<3>::face_t *> &faces,
-                                     const carve::mesh::MeshSet<3>::face_t *orig,
-                                     bool flipped) {
-        std::vector<carve::mesh::MeshSet<3>::face_t *> out_faces;
-
-        for (size_t f = 0; f < faces.size(); ++f) {
-          carve::mesh::MeshSet<3>::face_t *face = faces[f];
-
-          if (face->nVertices() == 3) {
-            out_faces.push_back(face);
-            continue;
-          }
-
-          std::vector<carve::mesh::MeshSet<3>::vertex_t *> vloop;
-          face->getVertices(vloop);
-
-          std::list<std::pair<size_t, size_t> > rep_edges;
-          if (!findRepeatedEdges(vloop, rep_edges)) {
-            out_faces.push_back(face);
-            continue;
-          }
-
-          std::vector<triangulate::tri_idx> result;
-          triangulate::triangulate(
-              carve::mesh::MeshSet<3>::face_t::projection_mapping(face->project),
-              vloop,
-              result);
-
-          std::map<std::pair<size_t, size_t>, size_t> tri_edge;
-          for (size_t i = 0; i < result.size(); ++i) {
-            tri_edge[std::make_pair(result[i].a, result[i].b)] = i;
-            tri_edge[std::make_pair(result[i].b, result[i].c)] = i;
-            tri_edge[std::make_pair(result[i].c, result[i].a)] = i;
-          }
-
-          std::vector<size_t> grp;
-          grp.resize(result.size(), 0);
-
-          size_t grp_max = 0;
-
-          while (rep_edges.size()) {
-            std::pair<size_t, size_t> e1, e2;
-
-            e1.first = rep_edges.front().first;
-            e1.second = (e1.first + 1) % vloop.size();
-
-            e2.first = rep_edges.front().second;
-            e2.second = (e2.first + 1) % vloop.size();
-
-            rep_edges.pop_front();
-
-            CARVE_ASSERT(tri_edge.find(e1) != tri_edge.end());
-            size_t t1 = tri_edge[e1];
-            CARVE_ASSERT(tri_edge.find(e2) != tri_edge.end());
-            size_t t2 = tri_edge[e2];
-
-            if (grp[t1] != grp[t2]) {
-              continue;
-            }
-
-            size_t t1g = ++grp_max;
-            size_t t2g = ++grp_max;
-
-            flood(t1, t2, grp[t1], t1g, t2g, grp, result, tri_edge);
-          }
-
-          std::set<size_t> groups;
-          std::copy(grp.begin(), grp.end(), std::inserter(groups, groups.begin()));
-
-          // now construct perimeters for each group.
-          std::vector<triangulate::tri_idx> grp_tris;
-          grp_tris.reserve(result.size());
-          for (std::set<size_t>::iterator i = groups.begin(); i != groups.end(); ++i) {
-            size_t grp_id = *i;
-            grp_tris.clear();
-            for (size_t j = 0; j < grp.size(); ++j) {
-              if (grp[j] == grp_id) {
-                grp_tris.push_back(result[j]);
-              }
-            }
-            std::vector<carve::mesh::MeshSet<3>::vertex_t *> grp_perim;
-            findPerimeter(grp_tris, vloop, grp_perim);
-            out_faces.push_back(face->create(grp_perim.begin(), grp_perim.end(), false));
-          }
-          delete face;
-        }
-        std::swap(faces, out_faces);
-      }
-    };
-  }
-}
diff --git a/extern/carve/include/carve/debug_hooks.hpp b/extern/carve/include/carve/debug_hooks.hpp
deleted file mode 100644 (file)
index 53de863..0000000
+++ /dev/null
@@ -1,97 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/carve.hpp>
-
-#include <carve/vector.hpp>
-#include <carve/geom3d.hpp>
-#include <carve/csg.hpp>
-
-#include <iomanip>
-
-template<typename MAP>
-void map_histogram(std::ostream &out, const MAP &map) {
-  std::vector<int> hist;
-  for (typename MAP::const_iterator i = map.begin(); i != map.end(); ++i) {
-    size_t n = (*i).second.size();
-    if (hist.size() <= n) {
-      hist.resize(n + 1);
-    }
-    hist[n]++;
-  }
-  int total = (int)map.size();
-  std::string bar(50, '*');
-  for (size_t i = 0; i < hist.size(); i++) {
-    if (hist[i] > 0) {
-      out << std::setw(5) << i << " : " << std::setw(5) << hist[i] << " " << bar.substr((size_t)(50 - hist[i] * 50 / total)) << std::endl;
-    }
-  }
-}
-
-namespace carve {
-  namespace csg {
-    class IntersectDebugHooks {
-    public:
-      virtual void drawIntersections(const VertexIntersections & /* vint */) {
-      }
-
-      virtual void drawPoint(const carve::mesh::MeshSet<3>::vertex_t * /* v */,
-                             float /* r */,
-                             float /* g */,
-                             float /* b */,
-                             float /* a */,
-                             float /* rad */) {
-      }
-      virtual void drawEdge(const carve::mesh::MeshSet<3>::vertex_t * /* v1 */,
-                            const carve::mesh::MeshSet<3>::vertex_t * /* v2 */,
-                            float /* rA */, float /* gA */, float /* bA */, float /* aA */,
-                            float /* rB */, float /* gB */, float /* bB */, float /* aB */,
-                            float /* thickness */ = 1.0) {
-      }
-
-      virtual void drawFaceLoopWireframe(const std::vector<carve::mesh::MeshSet<3>::vertex_t *> & /* face_loop */,
-                                         const carve::mesh::MeshSet<3>::vertex_t & /* normal */,
-                                         float /* r */, float /* g */, float /* b */, float /* a */,
-                                         bool /* inset */ = true) {
-      }
-
-      virtual void drawFaceLoop(const std::vector<carve::mesh::MeshSet<3>::vertex_t *> & /* face_loop */,
-                                const carve::mesh::MeshSet<3>::vertex_t & /* normal */,
-                                float /* r */, float /* g */, float /* b */, float /* a */,
-                                bool /* offset */ = true,
-                                bool /* lit */ = true) {
-      }
-
-      virtual void drawFaceLoop2(const std::vector<carve::mesh::MeshSet<3>::vertex_t *> & /* face_loop */,
-                                 const carve::mesh::MeshSet<3>::vertex_t & /* normal */,
-                                 float /* rF */, float /* gF */, float /* bF */, float /* aF */,
-                                 float /* rB */, float /* gB */, float /* bB */, float /* aB */,
-                                 bool /* offset */ = true,
-                                 bool /* lit */ = true) {
-      }
-
-      virtual ~IntersectDebugHooks() {
-      }
-    };
-
-    IntersectDebugHooks *intersect_installDebugHooks(IntersectDebugHooks *hooks);
-    bool intersect_debugEnabled();
-
-  }
-}
diff --git a/extern/carve/include/carve/djset.hpp b/extern/carve/include/carve/djset.hpp
deleted file mode 100644 (file)
index 90f5092..0000000
+++ /dev/null
@@ -1,134 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/carve.hpp>
-#include <vector>
-
-
-
-namespace carve {
-namespace djset {
-
-
-
-  class djset {
-
-  protected:
-    struct elem {
-      size_t parent, rank;
-      elem(size_t p, size_t r) : parent(p), rank(r) {}
-      elem() {}
-    };
-
-    std::vector<elem> set;
-    size_t n_sets;
-
-  public:
-    djset() : set(), n_sets(0) {
-    }
-
-    djset(size_t N) {
-      n_sets = N;
-      set.reserve(N);
-      for (size_t i = 0; i < N; ++i) {
-        set.push_back(elem(i,0));
-      }
-    }
-
-    void init(size_t N) {
-      if (N == set.size()) {
-        for (size_t i = 0; i < N; ++i) {
-          set[i] = elem(i,0);
-        }
-        n_sets = N;
-      } else {
-        djset temp(N);
-        std::swap(set, temp.set);
-        std::swap(n_sets, temp.n_sets);
-      }
-    }
-
-    size_t count() const {
-      return n_sets;
-    }
-
-    size_t find_set_head(size_t a) {
-      if (a == set[a].parent) return a;
-    
-      size_t a_head = a;
-      while (set[a_head].parent != a_head) a_head = set[a_head].parent;
-      set[a].parent = a_head;
-      return a_head;
-    }
-
-    bool same_set(size_t a, size_t b) {
-      return find_set_head(a) == find_set_head(b);
-    }
-
-    void merge_sets(size_t a, size_t b) {
-      a = find_set_head(a);
-      b = find_set_head(b);
-      if (a != b) {
-        n_sets--;
-        if (set[a].rank < set[b].rank) {
-          set[a].parent = b;
-        } else if (set[b].rank < set[a].rank) {
-          set[b].parent = a;
-        } else {
-          set[a].rank++;
-          set[b].parent = a;
-        }
-      }
-    }
-
-    void get_index_to_set(std::vector<size_t> &index_set, std::vector<size_t> &set_size) {
-      index_set.clear();
-      index_set.resize(set.size(), n_sets);
-      set_size.clear();
-      set_size.resize(n_sets, 0);
-
-      size_t c = 0;
-      for (size_t i = 0; i < set.size(); ++i) {
-        size_t s = find_set_head(i);
-        if (index_set[s] == n_sets) index_set[s] = c++;
-        index_set[i] = index_set[s];
-        set_size[index_set[s]]++;
-      }
-    }
-
-    template<typename in_iter_t, typename out_collection_t>
-    void collate(in_iter_t in, out_collection_t &out) {
-      std::vector<size_t> set_id(set.size(), n_sets);
-      out.clear();
-      out.resize(n_sets);
-      size_t c = 0;
-      for (size_t i = 0; i < set.size(); ++i) {
-        size_t s = find_set_head(i);
-        if (set_id[s] == n_sets) set_id[s] = c++;
-        s = set_id[s];
-        std::insert_iterator<typename out_collection_t::value_type> j(out[s], out[s].end());
-        *j = *in++;
-      }
-    }
-  };
-
-
-
-}
-}
diff --git a/extern/carve/include/carve/edge_decl.hpp b/extern/carve/include/carve/edge_decl.hpp
deleted file mode 100644 (file)
index 1fde265..0000000
+++ /dev/null
@@ -1,68 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/carve.hpp>
-
-#include <carve/vector.hpp>
-#include <carve/tag.hpp>
-
-#include <vector>
-#include <list>
-
-namespace carve {
-  namespace poly {
-
-
-
-    struct Object;
-
-
-
-    template<unsigned ndim>
-    class Edge : public tagable {
-    public:
-      typedef Vertex<ndim> vertex_t;
-      typedef typename Vertex<ndim>::vector_t vector_t;
-      typedef Object obj_t;
-
-      const vertex_t *v1, *v2;
-      const obj_t *owner;
-
-      Edge(const vertex_t *_v1, const vertex_t *_v2, const obj_t *_owner) :
-        tagable(), v1(_v1), v2(_v2), owner(_owner) {
-      }
-
-      ~Edge() {
-      }
-    };
-
-
-
-    struct hash_edge_ptr {
-      template<unsigned ndim>
-      size_t operator()(const Edge<ndim> * const &e) const {
-        return (size_t)e;
-      }
-    };
-
-
-
-  }
-}
-
diff --git a/extern/carve/include/carve/edge_impl.hpp b/extern/carve/include/carve/edge_impl.hpp
deleted file mode 100644 (file)
index ff00615..0000000
+++ /dev/null
@@ -1,23 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-namespace carve {
-  namespace poly {
-  }
-}
diff --git a/extern/carve/include/carve/exact.hpp b/extern/carve/include/carve/exact.hpp
deleted file mode 100644 (file)
index a74fb77..0000000
+++ /dev/null
@@ -1,704 +0,0 @@
-// Begin License:
-// Copyright (C) 2006-2014 Tobias Sargeant (tobias.sargeant@gmail.com).
-// All rights reserved.
-//
-// This file is part of the Carve CSG Library (http://carve-csg.com/)
-//
-// This file may be used under the terms of either the GNU General
-// Public License version 2 or 3 (at your option) as published by the
-// Free Software Foundation and appearing in the files LICENSE.GPL2
-// and LICENSE.GPL3 included in the packaging of this file.
-//
-// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
-// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE.
-// End:
-
-
-#pragma once
-
-#include <carve/carve.hpp>
-
-#include <vector>
-#include <numeric>
-#include <algorithm>
-
-
-namespace carve {
-  namespace exact {
-
-    class exact_t : public std::vector<double> {
-      typedef std::vector<double> super;
-
-    public:
-      exact_t() : super() {
-      }
-
-      exact_t(double v, size_t sz = 1) : super(sz, v) {
-      }
-
-      template<typename iter_t>
-      exact_t(iter_t a, iter_t b) : super(a, b) {
-      }
-
-      exact_t(double a, double b) : super() {
-        reserve(2);
-        push_back(a);
-        push_back(b);
-      }
-
-      exact_t(double a, double b, double c) : super() {
-        reserve(3);
-        push_back(a);
-        push_back(b);
-        push_back(c);
-      }
-
-      exact_t(double a, double b, double c, double d) : super() {
-        reserve(4);
-        push_back(a);
-        push_back(b);
-        push_back(c);
-        push_back(d);
-      }
-
-      exact_t(double a, double b, double c, double d, double e) : super() {
-        reserve(5);
-        push_back(a);
-        push_back(b);
-        push_back(c);
-        push_back(d);
-        push_back(e);
-      }
-
-      exact_t(double a, double b, double c, double d, double e, double f) : super() {
-        reserve(6);
-        push_back(a);
-        push_back(b);
-        push_back(c);
-        push_back(d);
-        push_back(e);
-        push_back(f);
-      }
-
-      exact_t(double a, double b, double c, double d, double e, double f, double g) : super() {
-        reserve(7);
-        push_back(a);
-        push_back(b);
-        push_back(c);
-        push_back(d);
-        push_back(e);
-        push_back(f);
-        push_back(g);
-      }
-
-      exact_t(double a, double b, double c, double d, double e, double f, double g, double h) : super() {
-        reserve(8);
-        push_back(a);
-        push_back(b);
-        push_back(c);
-        push_back(d);
-        push_back(e);
-        push_back(f);
-        push_back(g);
-        push_back(h);
-      }
-
-      void compress();
-
-      exact_t compressed() const {
-        exact_t result(*this);
-        result.compress();
-        return result;
-      }
-
-      operator double() const {
-        return std::accumulate(begin(), end(), 0.0);
-      }
-
-      void removeZeroes() {
-        erase(std::remove(begin(), end(), 0.0), end());
-      }
-    };
-
-    inline std::ostream &operator<<(std::ostream &out, const exact_t &p) {
-      out << '{';
-      out << p[0];
-      for (size_t i = 1; i < p.size(); ++i) out << ';' << p[i];
-      out << '}';
-      return out;
-    }
-
-
-
-    namespace detail {
-      const struct constants_t {
-        double splitter;     /* = 2^ceiling(p / 2) + 1.  Used to split floats in half. */
-        double epsilon;                /* = 2^(-p).  Used to estimate roundoff errors. */
-        /* A set of coefficients used to calculate maximum roundoff errors.          */
-        double resulterrbound;
-        double ccwerrboundA, ccwerrboundB, ccwerrboundC;
-        double o3derrboundA, o3derrboundB, o3derrboundC;
-        double iccerrboundA, iccerrboundB, iccerrboundC;
-        double isperrboundA, isperrboundB, isperrboundC;
-
-        constants_t() {
-          double half;
-          double check, lastcheck;
-          int every_other;
-  
-          every_other = 1;
-          half = 0.5;
-          epsilon = 1.0;
-          splitter = 1.0;
-          check = 1.0;
-          /* Repeatedly divide `epsilon' by two until it is too small to add to    */
-          /*   one without causing roundoff.  (Also check if the sum is equal to   */
-          /*   the previous sum, for machines that round up instead of using exact */
-          /*   rounding.  Not that this library will work on such machines anyway. */
-          do {
-            lastcheck = check;
-            epsilon *= half;
-            if (every_other) {
-              splitter *= 2.0;
-            }
-            every_other = !every_other;
-            check = 1.0 + epsilon;
-          } while ((check != 1.0) && (check != lastcheck));
-          splitter += 1.0;
-  
-          /* Error bounds for orientation and incircle tests. */
-          resulterrbound = (3.0 + 8.0 * epsilon) * epsilon;
-          ccwerrboundA = (3.0 + 16.0 * epsilon) * epsilon;
-          ccwerrboundB = (2.0 + 12.0 * epsilon) * epsilon;
-          ccwerrboundC = (9.0 + 64.0 * epsilon) * epsilon * epsilon;
-          o3derrboundA = (7.0 + 56.0 * epsilon) * epsilon;
-          o3derrboundB = (3.0 + 28.0 * epsilon) * epsilon;
-          o3derrboundC = (26.0 + 288.0 * epsilon) * epsilon * epsilon;
-          iccerrboundA = (10.0 + 96.0 * epsilon) * epsilon;
-          iccerrboundB = (4.0 + 48.0 * epsilon) * epsilon;
-          iccerrboundC = (44.0 + 576.0 * epsilon) * epsilon * epsilon;
-          isperrboundA = (16.0 + 224.0 * epsilon) * epsilon;
-          isperrboundB = (5.0 + 72.0 * epsilon) * epsilon;
-          isperrboundC = (71.0 + 1408.0 * epsilon) * epsilon * epsilon;
-        }
-      } constants;
-
-      template<unsigned U, unsigned V>
-      struct op {
-        enum {
-          Vlo = V / 2,
-          Vhi = V - Vlo
-        };
-
-        static inline void add(const double *a, const double *b, double *r) {
-          double t[U + Vlo];
-          op<U, Vlo>::add(a, b, t);
-          for (size_t i = 0; i < Vlo; ++i) r[i] = t[i];
-          op<U, Vhi>::add(t + Vlo, b + Vlo, r + Vlo);
-        }
-
-        static inline void sub(const double *a, const double *b, double *r) {
-          double t[U + Vlo];
-          op<U, Vlo>::sub(a, b, t);
-          for (size_t i = 0; i < Vlo; ++i) r[i] = t[i];
-          op<U, Vhi>::sub(t + Vlo, b + Vlo, r + Vlo);
-        }
-      };
-
-      template<unsigned U>
-      struct op<U, 1> {
-        enum {
-          Ulo = U / 2,
-          Uhi = U - Ulo
-        };
-        static void add(const double *a, const double *b, double *r) {
-          double t[Ulo + 1];
-          op<Ulo, 1>::add(a, b, t);
-          for (size_t i = 0; i < Ulo; ++i) r[i] = t[i];
-          op<Uhi, 1>::add(a + Ulo, t + Ulo, r + Ulo);
-        }
-
-        static void sub(const double *a, const double *b, double *r) {
-          double t[Ulo + 1];
-          op<Ulo, 1>::sub(a, b, t);
-          for (size_t i = 0; i < Ulo; ++i) r[i] = t[i];
-          op<Uhi, 1>::add(a + Ulo, t + Ulo, r + Ulo);
-        }
-      };
-
-      template<>
-      struct op<1, 1> {
-        static void add_fast(const double *a, const double *b, double *r) {
-          assert(fabs(a[0]) >= fabs(b[0]));
-          volatile double sum = a[0] + b[0];
-          volatile double bvirt = sum - a[0];
-          r[0] = b[0] - bvirt;
-          r[1] = sum;
-        }
-
-        static void sub_fast(const double *a, const double *b, double *r) {
-          assert(fabs(a[0]) >= fabs(b[0]));
-          volatile double diff = a[0] - b[0];
-          volatile double bvirt = a[0] - diff;
-          r[0] = bvirt - b[0];
-          r[1] = diff;
-        }
-
-        static void add(const double *a, const double *b, double *r) {
-          volatile double sum = a[0] + b[0];
-          volatile double bvirt = sum - a[0];
-          double avirt = sum - bvirt;
-          double bround = b[0] - bvirt;
-          double around = a[0] - avirt;
-          r[0] = around + bround;
-          r[1] = sum;
-        }
-
-        static void sub(const double *a, const double *b, double *r) {
-          volatile double diff = a[0] - b[0];
-          volatile double bvirt = a[0] - diff;
-          double avirt = diff + bvirt;
-          double bround = bvirt - b[0];
-          double around = a[0] - avirt;
-          r[0] = around + bround;
-          r[1] = diff;
-        }
-      };
-
-
-      template<unsigned U, unsigned V>
-      static exact_t add(const double *a, const double *b) {
-        exact_t result;
-        result.resize(U + V);
-        op<U,V>::add(a, b, &result[0]);
-        return result;
-      }
-
-
-      template<unsigned U, unsigned V>
-      static exact_t sub(const double *a, const double *b) {
-        exact_t result;
-        result.resize(U + V);
-        op<U,V>::sub(a, b, &result[0]);
-        return result;
-      }
-
-
-      template<unsigned U, unsigned V>
-      static exact_t add(const exact_t &a, const exact_t &b) {
-        assert(a.size() == U);
-        assert(b.size() == V);
-        exact_t result;
-        result.resize(U + V);
-        std::fill(result.begin(), result.end(), std::numeric_limits<double>::quiet_NaN());
-        op<U,V>::add(&a[0], &b[0], &result[0]);
-        return result;
-      }
-
-
-      template<unsigned U, unsigned V>
-      static exact_t add(const exact_t &a, const double *b) {
-        assert(a.size() == U);
-        exact_t result;
-        result.resize(U + V);
-        std::fill(result.begin(), result.end(), std::numeric_limits<double>::quiet_NaN());
-        op<U,V>::add(&a[0], b, &result[0]);
-        return result;
-      }
-
-
-      template<unsigned U, unsigned V>
-      static exact_t sub(const exact_t &a, const exact_t &b) {
-        assert(a.size() == U);
-        assert(b.size() == V);
-        exact_t result;
-        result.resize(U + V);
-        std::fill(result.begin(), result.end(), std::numeric_limits<double>::quiet_NaN());
-        op<U,V>::sub(&a[0], &b[0], &result[0]);
-        return result;
-      }
-
-
-      template<unsigned U, unsigned V>
-      static exact_t sub(const exact_t &a, const double *b) {
-        assert(a.size() == U);
-        exact_t result;
-        result.resize(U + V);
-        std::fill(result.begin(), result.end(), std::numeric_limits<double>::quiet_NaN());
-        op<U,V>::sub(&a[0], &b[0], &result[0]);
-        return result;
-      }
-
-
-      static inline void split(const double a, double *r) {
-        volatile double c = constants.splitter * a;
-        volatile double abig = c - a;
-        r[1] = c - abig;
-        r[0] = a - r[1];
-      }
-
-      static inline void prod_1_1(const double *a, const double *b, double *r) {
-        r[1] = a[0] * b[0];
-        double a_sp[2]; split(a[0], a_sp);
-        double b_sp[2]; split(b[0], b_sp);
-        double err1 = r[1] - a_sp[1] * b_sp[1];
-        double err2 = err1 - a_sp[0] * b_sp[1];
-        double err3 = err2 - a_sp[1] * b_sp[0];
-        r[0] = a_sp[0] * b_sp[0] - err3;
-      }
-
-      static inline void prod_1_1s(const double *a, const double *b, const double *b_sp, double *r) {
-        r[1] = a[0] * b[0];
-        double a_sp[2]; split(a[0], a_sp);
-        double err1 = r[1] - a_sp[1] * b_sp[1];
-        double err2 = err1 - a_sp[0] * b_sp[1];
-        double err3 = err2 - a_sp[1] * b_sp[0];
-        r[0] = a_sp[0] * b_sp[0] - err3;
-      }
-
-      static inline void prod_1s_1s(const double *a, const double *a_sp, const double *b, const double *b_sp, double *r) {
-        r[1] = a[0] * b[0];
-        double err1 = r[1] - a_sp[1] * b_sp[1];
-        double err2 = err1 - a_sp[0] * b_sp[1];
-        double err3 = err2 - a_sp[1] * b_sp[0];
-        r[0] = a_sp[0] * b_sp[0] - err3;
-      }
-
-      static inline void prod_2_1(const double *a, const double *b, double *r) {
-        double b_sp[2]; split(b[0], b_sp);
-        double t1[2]; prod_1_1s(a+0, b, b_sp, t1);
-        r[0] = t1[0];
-        double t2[2]; prod_1_1s(a+1, b, b_sp, t2);
-        double t3[2]; op<1,1>::add(t1+1, t2, t3);
-        r[1] = t3[0];
-        double t4[2]; op<1,1>::add_fast(t2+1, t3+1, r + 2);
-      }
-
-      static inline void prod_1_2(const double *a, const double *b, double *r) {
-        prod_2_1(b, a, r);
-      }
-
-      static inline void prod_4_1(const double *a, const double *b, double *r) {
-        double b_sp[2]; split(b[0], b_sp);
-        double t1[2]; prod_1_1s(a+0, b, b_sp, t1);
-        r[0] = t1[0];
-        double t2[2]; prod_1_1s(a+1, b, b_sp, t2);
-        double t3[2]; op<1,1>::add(t1+1, t2, t3);
-        r[1] = t3[0];
-        double t4[2]; op<1,1>::add_fast(t2+1, t3+1, t4);
-        r[2] = t4[0];
-        double t5[2]; prod_1_1s(a+2, b, b_sp, t5);
-        double t6[2]; op<1,1>::add(t4+1, t5, t6);
-        r[3] = t6[0];
-        double t7[2]; op<1,1>::add_fast(t5+1, t6+1, t7);
-        r[4] = t7[0];
-        double t8[2]; prod_1_1s(a+3, b, b_sp, t8);
-        double t9[2]; op<1,1>::add(t7+1, t8, t9);
-        r[5] = t9[0];
-        op<1,1>::add_fast(t8+1, t9+1, r + 6);
-      }
-
-      static inline void prod_1_4(const double *a, const double *b, double *r) {
-        prod_4_1(b, a, r);
-      }
-
-      static inline void prod_2_2(const double *a, const double *b, double *r) {
-        double a1_sp[2]; split(a[1], a1_sp);
-        double a0_sp[2]; split(a[0], a0_sp);
-        double b1_sp[2]; split(b[1], b1_sp);
-        double b0_sp[2]; split(b[0], b0_sp);
-
-        double t1[2]; prod_1s_1s(a+0, a0_sp, b+0, b0_sp, t1);
-        r[0] = t1[0];
-        double t2[2]; prod_1s_1s(a+1, a1_sp, b+0, b0_sp, t2);
-
-        double t3[2]; op<1,1>::add(t1+1, t2, t3);
-        double t4[2]; op<1,1>::add_fast(t2+1, t3+1, t4);
-
-        double t5[2]; prod_1s_1s(a+0, a0_sp, b+1, b1_sp, t5);
-
-        double t6[2]; op<1,1>::add(t3, t5, t6);
-        r[1] = t6[0];
-        double t7[2]; op<1,1>::add(t4, t6+1, t7);
-        double t8[2]; op<1,1>::add(t4+1, t7+1, t8);
-
-        double t9[2]; prod_1s_1s(a+1, a1_sp, b+1, b1_sp, t9);
-
-        double t10[2]; op<1,1>::add(t5+1, t9, t10);
-        double t11[2]; op<1,1>::add(t7, t10, t11);
-        r[2] = t11[0];
-        double t12[2]; op<1,1>::add(t8, t11+1, t12);
-        double t13[2]; op<1,1>::add(t8+1, t12+1, t13);
-        double t14[2]; op<1,1>::add(t9+1, t10+1, t14);
-        double t15[2]; op<1,1>::add(t12, t14, t15);
-        r[3] = t15[0];
-        double t16[2]; op<1,1>::add(t13, t15+1, t16);
-        double t17[2]; op<1,1>::add(t13+1, t16+1, t17);
-        double t18[2]; op<1,1>::add(t16, t14+1, t18);
-        r[4] = t18[0];
-        double t19[2]; op<1,1>::add(t17, t18+1, t19);
-        r[5] = t19[0];
-        double t20[2]; op<1,1>::add(t17+1, t19+1, t20);
-        r[6] = t20[0];
-        r[7] = t20[1];
-      }
-
-
-
-      static inline void square(const double a, double *r) {
-        r[1] = a * a;
-        double a_sp[2]; split(a, a_sp);
-        double err1 = r[1] - (a_sp[1] * a_sp[1]);
-        double err3 = err1 - ((a_sp[1] + a_sp[1]) * a_sp[0]);
-        r[0] = a_sp[0] * a_sp[