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. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
