[Bf-blender-cvs] [e56e7bd] master: Add lib for n-dimensional cubic curve fitting

Campbell Barton noreply at git.blender.org
Fri Apr 15 12:36:44 CEST 2016


Commit: e56e7bd1ec3081a13e44319a1b2793f4043d07dd
Author: Campbell Barton
Date:   Fri Apr 15 18:02:17 2016 +1000
Branches: master
https://developer.blender.org/rBe56e7bd1ec3081a13e44319a1b2793f4043d07dd

Add lib for n-dimensional cubic curve fitting

This will be used for calculating bezier curves from freehand drawing,
may be used for other areas too.

Original code from GraphicsGems, 1990 (FitCurve.c),
with updates from OpenToonz, under 3 clause BSD license.
with own minor modifications for integration with Blender:
- support adding extra custom-data.
- improved handle clamping.

===================================================================

M	build_files/cmake/macros.cmake
M	doc/doxygen/doxygen.extern.h
M	extern/CMakeLists.txt
A	extern/curve_fit_nd/CMakeLists.txt
A	extern/curve_fit_nd/curve_fit_nd.h
A	extern/curve_fit_nd/intern/curve_fit_corners_detect.c
A	extern/curve_fit_nd/intern/curve_fit_cubic.c
A	extern/curve_fit_nd/intern/curve_fit_inline.h

===================================================================

diff --git a/build_files/cmake/macros.cmake b/build_files/cmake/macros.cmake
index 2b7a43b..85bc400 100644
--- a/build_files/cmake/macros.cmake
+++ b/build_files/cmake/macros.cmake
@@ -578,6 +578,7 @@ function(SETUP_BLENDER_SORTED_LIBS)
 		ge_phys_bullet
 		bf_intern_smoke
 		extern_lzma
+		extern_curve_fit_nd
 		ge_logic_ketsji
 		extern_recastnavigation
 		ge_logic
diff --git a/doc/doxygen/doxygen.extern.h b/doc/doxygen/doxygen.extern.h
index 6c6872f..27b53ad 100644
--- a/doc/doxygen/doxygen.extern.h
+++ b/doc/doxygen/doxygen.extern.h
@@ -11,6 +11,10 @@
  *
  */
 
+/** \defgroup curve_fit Curve Fitting Library
+ *  \ingroup extern
+ */
+
 /** \defgroup bullet Bullet Physics Library
  *  \ingroup extern
  *  \see \ref bulletdoc
diff --git a/extern/CMakeLists.txt b/extern/CMakeLists.txt
index 1cce7dc..58e0c68 100644
--- a/extern/CMakeLists.txt
+++ b/extern/CMakeLists.txt
@@ -23,6 +23,9 @@
 #
 # ***** END GPL LICENSE BLOCK *****
 
+# Libs that adhere to strict flags
+add_subdirectory(curve_fit_nd)
+
 # Otherwise we get warnings here that we cant fix in external projects
 remove_strict_flags()
 
diff --git a/extern/curve_fit_nd/CMakeLists.txt b/extern/curve_fit_nd/CMakeLists.txt
new file mode 100644
index 0000000..6669971
--- /dev/null
+++ b/extern/curve_fit_nd/CMakeLists.txt
@@ -0,0 +1,35 @@
+# ***** 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.
+#
+# ***** END GPL LICENSE BLOCK *****
+
+set(INC
+	.
+)
+
+set(INC_SYS
+
+)
+
+set(SRC
+	intern/curve_fit_cubic.c
+	intern/curve_fit_corners_detect.c
+
+	intern/curve_fit_inline.h
+	curve_fit_nd.h
+)
+
+blender_add_lib(extern_curve_fit_nd "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/extern/curve_fit_nd/curve_fit_nd.h b/extern/curve_fit_nd/curve_fit_nd.h
new file mode 100644
index 0000000..67b0ed7
--- /dev/null
+++ b/extern/curve_fit_nd/curve_fit_nd.h
@@ -0,0 +1,125 @@
+/*
+ * Copyright (c) 2016, DWANGO Co., Ltd.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in the
+ *       documentation and/or other materials provided with the distribution.
+ *     * Neither the name of the <organization> nor the
+ *       names of its contributors may be used to endorse or promote products
+ *       derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef __SPLINE_FIT__
+#define __SPLINE_FIT__
+
+/** \file curve_fit_nd.h
+ *  \ingroup curve_fit
+ */
+
+
+/* curve_fit_cubic.c */
+
+/**
+ * Takes a flat array of points and evalues that to calculate a bezier spline.
+ *
+ * \param points, points_len: The array of points to calculate a cubics from.
+ * \param dims: The number of dimensions for for each element in \a points.
+ * \param error_threshold: the error threshold to allow for,
+ * the curve will be within this distance from \a points.
+ * \param corners, corners_len: indices for points which will not have aligned tangents (optional).
+ * This can use the output of #curve_fit_corners_detect_db which has been included
+ * to evaluate a line to detect corner indices.
+ *
+ * \param r_cubic_array, r_cubic_array_len: Resulting array of tangents and knots, formatted as follows:
+ * ``r_cubic_array[r_cubic_array_len][3][dims]``,
+ * where each point has 0 and 2 for the tangents and the middle index 1 for the knot.
+ * The size of the *flat* array will be ``r_cubic_array_len * 3 * dims``.
+ * \param r_corner_index_array, r_corner_index_len: Corner indices in in \a r_cubic_array (optional).
+ * This allows you to access corners on the resulting curve.
+ *
+ * \returns zero on success, nonzero is reserved for error values.
+ */
+int curve_fit_cubic_from_points_db(
+        const double       *points,
+        const unsigned int  points_len,
+        const unsigned int  dims,
+        const double        error_threshold,
+        const unsigned int *corners,
+        unsigned int        corners_len,
+
+        double **r_cubic_array, unsigned int *r_cubic_array_len,
+        unsigned int **r_cubic_orig_index,
+        unsigned int **r_corner_index_array, unsigned int *r_corner_index_len);
+
+int curve_fit_cubic_from_points_fl(
+        const float        *points,
+        const unsigned int  points_len,
+        const unsigned int  dims,
+        const float         error_threshold,
+        const unsigned int *corners,
+        const unsigned int  corners_len,
+
+        float **r_cubic_array, unsigned int *r_cubic_array_len,
+        unsigned int **r_cubic_orig_index,
+        unsigned int **r_corners_index_array, unsigned int *r_corners_index_len);
+
+
+/* curve_fit_corners_detect.c */
+
+/**
+ * A helper function that takes a line and outputs its corner indices.
+ *
+ * \param points, points_len: Curve to evaluate.
+ * \param dims: The number of dimensions for for each element in \a points.
+ * \param radius_min: Corners on the curve between points below this radius are ignored.
+ * \param radius_max: Corners on the curve above this radius are ignored.
+ * \param samples_max: Prevent testing corners beyond this many points
+ * (prevents a large radius taking excessive time to compute).
+ * \param angle_threshold: Angles above this value are considered corners
+ * (higher value for fewer corners).
+ *
+ * \param r_corners, r_corners_len: Resulting array of corners.
+ *
+ * \returns zero on success, nonzero is reserved for error values.
+ */
+int curve_fit_corners_detect_db(
+        const double      *points,
+        const unsigned int points_len,
+        const unsigned int dims,
+        const double       radius_min,
+        const double       radius_max,
+        const unsigned int samples_max,
+        const double       angle_threshold,
+
+        unsigned int **r_corners,
+        unsigned int  *r_corners_len);
+
+int curve_fit_corners_detect_fl(
+        const float       *points,
+        const unsigned int points_len,
+        const unsigned int dims,
+        const float        radius_min,
+        const float        radius_max,
+        const unsigned int samples_max,
+        const float        angle_threshold,
+
+        unsigned int **r_corners,
+        unsigned int  *r_corners_len);
+
+#endif  /* __SPLINE_FIT__ */
diff --git a/extern/curve_fit_nd/intern/curve_fit_corners_detect.c b/extern/curve_fit_nd/intern/curve_fit_corners_detect.c
new file mode 100644
index 0000000..c025818
--- /dev/null
+++ b/extern/curve_fit_nd/intern/curve_fit_corners_detect.c
@@ -0,0 +1,468 @@
+/*
+ * Copyright (c) 2016, Blender Foundation.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in the
+ *       documentation and/or other materials provided with the distribution.
+ *     * Neither the name of the <organization> nor the
+ *       names of its contributors may be used to endorse or promote products
+ *       derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file curve_fit_corners_detect.c
+ *  \ingroup curve_fit
+ */
+
+#include <math.h>
+#include <float.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "../curve_fit_nd.h"
+
+typedef unsigned int uint;
+
+#include "curve_fit_inline.h"
+
+#ifdef _MSC_VER
+#  define alloca(size) _alloca(size)
+#endif
+


@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list