[Bf-blender-cvs] [80465ba35a1] master: Curve Decimate: new tool to simplify bezier curves
Campbell Barton
noreply at git.blender.org
Mon Oct 30 12:32:33 CET 2017
Commit: 80465ba35a163c9832a4666fac74465561b7c6c5
Author: Campbell Barton
Date: Mon Oct 30 22:36:51 2017 +1100
Branches: master
https://developer.blender.org/rB80465ba35a163c9832a4666fac74465561b7c6c5
Curve Decimate: new tool to simplify bezier curves
Access from the curve clean-up menu
===================================================================
M release/scripts/startup/bl_ui/space_view3d.py
M source/blender/blenkernel/BKE_curve.h
M source/blender/blenkernel/CMakeLists.txt
A source/blender/blenkernel/intern/curve_decimate.c
M source/blender/editors/curve/curve_intern.h
M source/blender/editors/curve/curve_ops.c
M source/blender/editors/curve/editcurve.c
M source/blender/makesdna/DNA_curve_types.h
===================================================================
diff --git a/release/scripts/startup/bl_ui/space_view3d.py b/release/scripts/startup/bl_ui/space_view3d.py
index 22770230efe..c7e05a4173e 100644
--- a/release/scripts/startup/bl_ui/space_view3d.py
+++ b/release/scripts/startup/bl_ui/space_view3d.py
@@ -2789,7 +2789,7 @@ class VIEW3D_MT_edit_mesh_normals(Menu):
class VIEW3D_MT_edit_mesh_clean(Menu):
- bl_label = "Clean up"
+ bl_label = "Clean Up"
def draw(self, context):
layout = self.layout
@@ -2895,6 +2895,10 @@ def draw_curve(self, context):
layout.separator()
+ layout.menu("VIEW3D_MT_edit_curve_clean")
+
+ layout.separator()
+
layout.menu("VIEW3D_MT_edit_proportional")
layout.separator()
@@ -2943,6 +2947,14 @@ class VIEW3D_MT_edit_curve_segments(Menu):
layout.operator("curve.subdivide")
layout.operator("curve.switch_direction")
+class VIEW3D_MT_edit_curve_clean(Menu):
+ bl_label = "Clean Up"
+
+ def draw(self, context):
+ layout = self.layout
+
+ layout.operator("curve.decimate")
+
class VIEW3D_MT_edit_curve_specials(Menu):
bl_label = "Specials"
@@ -4105,6 +4117,7 @@ classes = (
VIEW3D_MT_edit_curve,
VIEW3D_MT_edit_curve_ctrlpoints,
VIEW3D_MT_edit_curve_segments,
+ VIEW3D_MT_edit_curve_clean,
VIEW3D_MT_edit_curve_specials,
VIEW3D_MT_edit_curve_delete,
VIEW3D_MT_edit_curve_showhide,
diff --git a/source/blender/blenkernel/BKE_curve.h b/source/blender/blenkernel/BKE_curve.h
index a900ba43443..30db8f45059 100644
--- a/source/blender/blenkernel/BKE_curve.h
+++ b/source/blender/blenkernel/BKE_curve.h
@@ -218,4 +218,14 @@ struct EvaluationContext;
void BKE_curve_eval_geometry(struct EvaluationContext *eval_ctx,
struct Curve *curve);
+/* curve_decimate.c */
+unsigned int BKE_curve_decimate_bezt_array(
+ struct BezTriple *bezt_array, const unsigned int bezt_array_len, const unsigned int resolu, const bool is_cyclic,
+ const char flag_test, const char flag_set,
+ const float error_sq_max, const unsigned int error_target_len);
+
+void BKE_curve_decimate_nurb(
+ struct Nurb *nu, const unsigned int resolu,
+ const float error_sq_max, const unsigned int error_target_len);
+
#endif /* __BKE_CURVE_H__ */
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 51598ede862..74c69c5aeb9 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -49,6 +49,7 @@ set(INC
../../../intern/smoke/extern
../../../intern/atomic
../../../intern/libmv
+ ../../../extern/curve_fit_nd
)
set(INC_SYS
@@ -91,6 +92,7 @@ set(SRC
intern/context.c
intern/crazyspace.c
intern/curve.c
+ intern/curve_decimate.c
intern/customdata.c
intern/customdata_file.c
intern/data_transfer.c
diff --git a/source/blender/blenkernel/intern/curve_decimate.c b/source/blender/blenkernel/intern/curve_decimate.c
new file mode 100644
index 00000000000..7983c63c99d
--- /dev/null
+++ b/source/blender/blenkernel/intern/curve_decimate.c
@@ -0,0 +1,339 @@
+/*
+ * ***** 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 *****
+ */
+
+/** \file blender/blenkernel/intern/curve_decimate.c
+ * \ingroup bke
+ */
+
+#include "DNA_curve_types.h"
+
+#include "MEM_guardedalloc.h"
+#include "BLI_heap.h"
+#include "BLI_math_vector.h"
+
+#include "BKE_curve.h"
+
+#include "curve_fit_nd.h"
+
+#include "BLI_strict_flags.h"
+
+struct Knot {
+ struct Knot *next, *prev;
+ uint point_index; /* index in point array */
+ uint knot_index; /* index in knot array*/
+ float tan[2][3];
+ float handles[2];
+
+ HeapNode *heap_node;
+ uint can_remove : 1;
+ uint is_removed : 1;
+
+#ifndef NDEBUG
+ const float *co;
+#endif
+};
+
+struct Removal {
+ uint knot_index;
+ /* handles for prev/next knots */
+ float handles[2];
+};
+
+static float knot_remove_error_value(
+ const float tan_l[3], const float tan_r[3],
+ const float (*points)[3], const uint points_len,
+ /* avoid having to re-calculate again */
+ float r_handle_factors[2])
+{
+ const uint dims = 3;
+ float error_sq = FLT_MAX;
+ uint error_sq_index;
+ float handle_factors[2][3];
+
+ curve_fit_cubic_to_points_single_fl(
+ &points[0][0], points_len, NULL, dims, 0.0f,
+ tan_l, tan_r,
+ handle_factors[0], handle_factors[1],
+ &error_sq, &error_sq_index);
+
+ sub_v3_v3(handle_factors[0], points[0]);
+ r_handle_factors[0] = dot_v3v3(tan_l, handle_factors[0]);
+
+ sub_v3_v3(handle_factors[1], points[points_len - 1]);
+ r_handle_factors[1] = dot_v3v3(tan_r, handle_factors[1]);
+
+ return error_sq;
+}
+
+static void knot_remove_error_recalculate(
+ Heap *heap, const float (*points)[3], const uint points_len,
+ struct Knot *k, const float error_sq_max)
+{
+ BLI_assert(k->can_remove);
+ float handles[2];
+
+#ifndef NDEBUG
+ BLI_assert(equals_v3v3(points[k->prev->point_index], k->prev->co));
+ BLI_assert(equals_v3v3(points[k->next->point_index], k->next->co));
+#endif
+
+ const float (*points_offset)[3];
+ uint points_offset_len;
+
+ if (k->prev->point_index < k->next->point_index) {
+ points_offset = &points[k->prev->point_index];
+ points_offset_len = (k->next->point_index - k->prev->point_index) + 1;
+ }
+ else {
+ points_offset = &points[k->prev->point_index];
+ points_offset_len = ((k->next->point_index + points_len) - k->prev->point_index) + 1;
+ }
+
+ const float cost_sq = knot_remove_error_value(
+ k->prev->tan[1], k->next->tan[0],
+ points_offset, points_offset_len,
+ handles);
+
+ if (cost_sq < error_sq_max) {
+ struct Removal *r;
+ if (k->heap_node) {
+ r = BLI_heap_node_ptr(k->heap_node);
+ }
+ else {
+ r = MEM_mallocN(sizeof(*r), __func__);
+ r->knot_index = k->knot_index;
+ }
+
+ copy_v2_v2(r->handles, handles);
+
+ BLI_heap_insert_or_update(heap, &k->heap_node, cost_sq, r);
+ }
+ else {
+ if (k->heap_node) {
+ struct Removal *r;
+ r = BLI_heap_node_ptr(k->heap_node);
+ BLI_heap_remove(heap, k->heap_node);
+
+ MEM_freeN(r);
+
+ k->heap_node = NULL;
+ }
+ }
+}
+
+static void curve_decimate(
+ const float (*points)[3], const uint points_len,
+ struct Knot *knots, const uint knots_len,
+ float error_sq_max, const uint error_target_len)
+{
+ Heap *heap = BLI_heap_new_ex(knots_len);
+ for (uint i = 0; i < knots_len; i++) {
+ struct Knot *k = &knots[i];
+ if (k->can_remove) {
+ knot_remove_error_recalculate(heap, points, points_len, k, error_sq_max);
+ }
+ }
+
+ uint knots_len_remaining = knots_len;
+
+ while ((knots_len_remaining > error_target_len) &&
+ (BLI_heap_is_empty(heap) == false))
+ {
+ struct Knot *k;
+
+ {
+ struct Removal *r = BLI_heap_popmin(heap);
+ k = &knots[r->knot_index];
+ k->heap_node = NULL;
+ k->prev->handles[1] = r->handles[0];
+ k->next->handles[0] = r->handles[1];
+ MEM_freeN(r);
+ }
+
+ struct Knot *k_prev = k->prev;
+ struct Knot *k_next = k->next;
+
+ /* remove ourselves */
+ k_next->prev = k_prev;
+ k_prev->next = k_next;
+
+ k->next = NULL;
+ k->prev = NULL;
+ k->is_removed = true;
+
+ if (k_prev->can_remove) {
+ knot_remove_error_recalculate(heap, points, points_len, k_prev, error_sq_max);
+ }
+
+ if (k_next->can_remove) {
+ knot_remove_error_recalculate(heap, points, points_len, k_next, error_sq_max);
+ }
+
+ knots_len_remaining -= 1;
+ }
+
+ BLI_heap_free(heap, MEM_freeN);
+}
+
+
+uint BKE_curve_decimate_bezt_array(
+ BezTriple *bezt_array, const uint bezt_array_len,
+ const uint resolu, const bool is_cyclic,
+ const char flag_test, const char flag_set,
+ const float error_sq_max, const uint error_target_len)
+{
+ const uint bezt_array_last = bezt_array_len - 1;
+ const uint points_len = BKE_curve_calc_coords_axis_len(bezt_array_len, resolu, is_cyclic, true);
+
+ float (*points)[3] = MEM_mallocN((sizeof(float[3]) * points_len * (is_cyclic ? 2 : 1)), __func__);
+
+ BKE_curve_calc_coords_axis(bezt_array, bezt_array_len, resolu, is_cyclic, false, 0, sizeof(float[3]), &points[0][0]);
+ BKE_curve_calc_coords_axis(bezt_array, bezt_array_len, resolu, is_cyclic, false, 1, sizeof(float[3]), &points[0][1]);
+ BKE_curve_calc_coords_axis(bezt_array, bezt_array_len, resolu, is_cyclic, false, 2, sizeof(float[3]), &points[0][2]);
+
+ const uint knots_len = bezt_array_len;
+ struct Knot *knots = MEM_mallocN((sizeof(*knots) * bezt_array_len), __func__);
+
+ if (is_cyclic) {
+ memcpy(points[points_len], points[0], sizeof(float[3]) * points_len);
+ }
+
+ for (uint i = 0; i < bezt_array_len; i++) {
+ knots[i].heap_node = NULL;
+ knots[i].can_remove = (bezt_array[i].f2 & flag_test) != 0;
+ knots[i].is_removed = false;
+ knots[i].next = &knots[i + 1];
+ knots[i].prev = &knots[i - 1];
+ knots[i].point_index = i * resolu;
+ knots[i].knot_index = i;
+
+ sub_v3_v3v3(knots[i].tan[0], bezt_array[i].vec[0], bezt_array[i].vec[1]);
+ knots[i].handles[0] = normalize_v3(knots[i].tan[0]);
+
+ sub_v3_v3v3(knots[i].tan[1], bezt_array[i].vec[1], bezt_array[i].vec[2]);
+ knots[i].handles[1] = -normalize_v3(knots[i].tan[1]);
+
+#ifndef NDEBUG
+ knots[i].co = bezt_array[i].vec[1];
+ BLI_assert(equals_v3v3(knots[i].co, points[knots[i].point_index]));
+#endif
+ }
+
+ if (is_cyclic) {
+ knots[0].prev = &knots[bezt_array_last];
+ knots[bezt_array_last].next = &knots[0];
+ }
+ else {
+ knots[0].prev = NULL;
+ knots[bezt_array_last].next = NULL;
+
+ /* always keep en
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list