[Bf-blender-cvs] [2418dae] master: Curve Fitting: Add alternate 'refit' method

Campbell Barton noreply at git.blender.org
Mon Jul 25 06:59:14 CEST 2016


Commit: 2418daede5913c54bd9675eb23624487f6b0ad4c
Author: Campbell Barton
Date:   Mon Jul 25 14:12:17 2016 +1000
Branches: master
https://developer.blender.org/rB2418daede5913c54bd9675eb23624487f6b0ad4c

Curve Fitting: Add alternate 'refit' method

This is an alternative method for fitting a curve which incrementally simplifies the curve, then re-fits.

Generally gives better results, also improves corner detection.

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

M	extern/curve_fit_nd/CMakeLists.txt
M	extern/curve_fit_nd/curve_fit_nd.h
M	extern/curve_fit_nd/intern/curve_fit_cubic.c
A	extern/curve_fit_nd/intern/curve_fit_cubic_refit.c
M	extern/curve_fit_nd/intern/curve_fit_inline.h
A	extern/curve_fit_nd/intern/generic_alloc_impl.h
A	extern/curve_fit_nd/intern/generic_heap.c
A	extern/curve_fit_nd/intern/generic_heap.h
M	source/blender/editors/curve/editcurve.c
M	source/blender/editors/curve/editcurve_paint.c

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

diff --git a/extern/curve_fit_nd/CMakeLists.txt b/extern/curve_fit_nd/CMakeLists.txt
index 6669971..cc9efe1 100644
--- a/extern/curve_fit_nd/CMakeLists.txt
+++ b/extern/curve_fit_nd/CMakeLists.txt
@@ -26,10 +26,14 @@ set(INC_SYS
 
 set(SRC
 	intern/curve_fit_cubic.c
+	intern/curve_fit_cubic_refit.c
 	intern/curve_fit_corners_detect.c
 
-	intern/curve_fit_inline.h
 	curve_fit_nd.h
+	intern/curve_fit_inline.h
+	intern/generic_alloc_impl.h
+	intern/generic_heap.c
+	intern/generic_heap.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
index 3649802..cfb1881 100644
--- a/extern/curve_fit_nd/curve_fit_nd.h
+++ b/extern/curve_fit_nd/curve_fit_nd.h
@@ -86,6 +86,7 @@ int curve_fit_cubic_to_points_fl(
  *
  * \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 points_length_cache: Optional pre-calculated lengths between points.
  * \param error_threshold: the error threshold to allow for,
  * \param tan_l, tan_r: Normalized tangents the handles will be aligned to.
  * Note that tangents must both point along the direction of the \a points,
@@ -98,6 +99,7 @@ int curve_fit_cubic_to_points_fl(
 int curve_fit_cubic_to_points_single_db(
         const double      *points,
         const unsigned int points_len,
+        const double      *points_length_cache,
         const unsigned int dims,
         const double       error_threshold,
         const double       tan_l[],
@@ -110,6 +112,7 @@ int curve_fit_cubic_to_points_single_db(
 int curve_fit_cubic_to_points_single_fl(
         const float       *points,
         const unsigned int points_len,
+        const float       *points_length_cache,
         const unsigned int dims,
         const float        error_threshold,
         const float        tan_l[],
@@ -121,8 +124,40 @@ int curve_fit_cubic_to_points_single_fl(
 
 enum {
 	CURVE_FIT_CALC_HIGH_QUALIY          = (1 << 0),
+	CURVE_FIT_CALC_CYCLIC               = (1 << 1),
 };
 
+
+/* curve_fit_cubic_refit.c */
+
+int curve_fit_cubic_to_points_refit_db(
+        const double         *points,
+        const unsigned int    points_len,
+        const unsigned int    dims,
+        const double          error_threshold,
+        const unsigned int    calc_flag,
+        const unsigned int   *corners,
+        unsigned int          corners_len,
+        const double          corner_angle,
+
+        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_to_points_refit_fl(
+        const float          *points,
+        const unsigned int    points_len,
+        const unsigned int    dims,
+        const float           error_threshold,
+        const unsigned int    calc_flag,
+        const unsigned int   *corners,
+        unsigned int          corners_len,
+        const float           corner_angle,
+
+        float **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);
+
 /* curve_fit_corners_detect.c */
 
 /**
diff --git a/extern/curve_fit_nd/intern/curve_fit_cubic.c b/extern/curve_fit_nd/intern/curve_fit_cubic.c
index 1a0f7dc..24b216d 100644
--- a/extern/curve_fit_nd/intern/curve_fit_cubic.c
+++ b/extern/curve_fit_nd/intern/curve_fit_cubic.c
@@ -474,7 +474,7 @@ static double points_calc_circumference_factor(
 		 * We could try support this but will likely cause extreme >1 scales which could cause other issues. */
 		// assert(angle >= len_tangent);
 		double factor = (angle / len_tangent);
-		assert(factor < (M_PI / 2) + DBL_EPSILON);
+		assert(factor < (M_PI / 2) + (DBL_EPSILON * 10));
 		return factor;
 	}
 	else {
@@ -876,7 +876,6 @@ static double points_calc_coord_length(
 
 #ifdef USE_LENGTH_CACHE
 		length = points_length_cache[i];
-
 		assert(len_vnvn(pt, pt_prev, dims) == points_length_cache[i]);
 #else
 		length = len_vnvn(pt, pt_prev, dims);
@@ -1435,6 +1434,7 @@ int curve_fit_cubic_to_points_fl(
 int curve_fit_cubic_to_points_single_db(
         const double *points,
         const uint    points_len,
+        const double *points_length_cache,
         const uint    dims,
         const double  error_threshold,
         const double tan_l[],
@@ -1451,10 +1451,14 @@ int curve_fit_cubic_to_points_single_db(
 	/* in this instance theres no advantage in using length cache,
 	 * since we're not recursively calculating values. */
 #ifdef USE_LENGTH_CACHE
-	double *points_length_cache = malloc(sizeof(double) * points_len);
-	points_calc_coord_length_cache(
-	        points, points_len, dims,
-	        points_length_cache);
+	double *points_length_cache_alloc = NULL;
+	if (points_length_cache == NULL) {
+		points_length_cache_alloc = malloc(sizeof(double) * points_len);
+		points_calc_coord_length_cache(
+		        points, points_len, dims,
+		        points_length_cache_alloc);
+		points_length_cache = points_length_cache_alloc;
+	}
 #endif
 
 	fit_cubic_to_points(
@@ -1467,7 +1471,9 @@ int curve_fit_cubic_to_points_single_db(
 	        cubic, r_error_max_sq, &split_index);
 
 #ifdef USE_LENGTH_CACHE
-	free(points_length_cache);
+	if (points_length_cache_alloc) {
+		free(points_length_cache_alloc);
+	}
 #endif
 
 	copy_vnvn(r_handle_l, CUBIC_PT(cubic, 1, dims), dims);
@@ -1479,6 +1485,7 @@ int curve_fit_cubic_to_points_single_db(
 int curve_fit_cubic_to_points_single_fl(
         const float  *points,
         const uint    points_len,
+        const float  *points_length_cache,
         const uint    dims,
         const float   error_threshold,
         const float   tan_l[],
@@ -1490,9 +1497,15 @@ int curve_fit_cubic_to_points_single_fl(
 {
 	const uint points_flat_len = points_len * dims;
 	double *points_db = malloc(sizeof(double) * points_flat_len);
+	double *points_length_cache_db = NULL;
 
 	copy_vndb_vnfl(points_db, points, points_flat_len);
 
+	if (points_length_cache) {
+		points_length_cache_db = malloc(sizeof(double) * points_len);
+		copy_vndb_vnfl(points_length_cache_db, points_length_cache, points_len);
+	}
+
 #ifdef USE_VLA
 	double tan_l_db[dims];
 	double tan_r_db[dims];
@@ -1510,7 +1523,7 @@ int curve_fit_cubic_to_points_single_fl(
 	copy_vndb_vnfl(tan_r_db, tan_r, dims);
 
 	int result = curve_fit_cubic_to_points_single_db(
-	        points_db, points_len, dims,
+	        points_db, points_len, points_length_cache_db, dims,
 	        (double)error_threshold,
 	        tan_l_db, tan_r_db,
 	        r_handle_l_db, r_handle_r_db,
@@ -1518,6 +1531,10 @@ int curve_fit_cubic_to_points_single_fl(
 
 	free(points_db);
 
+	if (points_length_cache_db) {
+		free(points_length_cache_db);
+	}
+
 	copy_vnfl_vndb(r_handle_l, r_handle_l_db, dims);
 	copy_vnfl_vndb(r_handle_r, r_handle_r_db, dims);
 	*r_error_sq = (float)r_error_sq_db;
diff --git a/extern/curve_fit_nd/intern/curve_fit_cubic_refit.c b/extern/curve_fit_nd/intern/curve_fit_cubic_refit.c
new file mode 100644
index 0000000..756c093
--- /dev/null
+++ b/extern/curve_fit_nd/intern/curve_fit_cubic_refit.c
@@ -0,0 +1,1424 @@
+/*
+ * Copyright (c) 2016, Campbell Barton.
+ *
+ * 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.
+ */
+
+/**
+ * Curve Re-fitting Method
+ * =======================
+ *
+ * This is a more processor intensive method of fitting,
+ * compared to #curve_fit_cubic_to_points_db, and works as follows:
+ *
+ * - First iteratively remove all points under the error threshold.
+ * - If corner calculation is enabled:
+ *   - Find adjacent knots that exceed the angle limit
+ *   - Find a 'split' point between the knots (could include the knots)
+ *   - If copying the tangents to this split point doesn't exceed the error threshold:
+ *     - Assign the tangents of the two knots to the split point, define it as a corner.
+ *       (after this, we have many points which are too close).
+ * - Run a re-fit pass, where knots are re-positioned between their adjacent knots
+ *   when their re-fit position has a lower 'error'.
+ *   While re-fitting, remove knots that fall below the error threshold.
+ */
+
+#include <math.h>
+#include <float.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#include <string.h>
+#include <stdlib.h>
+
+
+#include <stdio.h>
+
+#include "curve_fit_inline.h"
+#include "../curve_fit_nd.h"
+
+#include "generic_heap.h"
+
+#ifdef _MSC_VER
+#  define alloca(size) _alloca(size)
+#endif
+
+#if !defined(_MSC_VER)
+#  define USE_VLA
+#endif
+
+#ifdef USE_VLA
+#  ifdef __GNUC__
+#    pragma GCC diagnostic ignored "-Wvla"
+#  e

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list