diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-10-30 14:36:51 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-10-30 14:36:51 +0300 |
commit | 80465ba35a163c9832a4666fac74465561b7c6c5 (patch) | |
tree | 59c1aac8ca95dbdab195971ec808f703fc4a5249 /source/blender/blenkernel | |
parent | e8daf2e3ea17c2e9569e6fc9b49879c74d9a8c22 (diff) |
Curve Decimate: new tool to simplify bezier curves
Access from the curve clean-up menu
Diffstat (limited to 'source/blender/blenkernel')
-rw-r--r-- | source/blender/blenkernel/BKE_curve.h | 10 | ||||
-rw-r--r-- | source/blender/blenkernel/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/curve_decimate.c | 339 |
3 files changed, 351 insertions, 0 deletions
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 end-points */ + knots[0].can_remove = false; + knots[bezt_array_last].can_remove = false; + } + + curve_decimate(points, points_len, knots, knots_len, error_sq_max, error_target_len); + + MEM_freeN(points); + + uint knots_len_decimated = knots_len; + + /* Update handle type on modifications. */ +#define HANDLE_UPDATE(a, b) \ + { \ + if (a == HD_VECT) { \ + a = HD_FREE; \ + } \ + else if (a == HD_AUTO) { \ + a = HD_ALIGN; \ + } \ + /* opposite handle */ \ + if (b == HD_AUTO) { \ + b = HD_ALIGN; \ + } \ + } ((void)0) + + for (uint i = 0; i < bezt_array_len; i++) { + if (knots[i].is_removed) { + /* caller must remove */ + bezt_array[i].f2 |= flag_set; + knots_len_decimated--; + } + else { + bezt_array[i].f2 &= (char)~flag_set; + if (is_cyclic || i != 0) { + uint i_prev = (i != 0) ? i - 1 : bezt_array_last; + if (knots[i_prev].is_removed) { + madd_v3_v3v3fl(bezt_array[i].vec[0], bezt_array[i].vec[1], knots[i].tan[0], knots[i].handles[0]); + HANDLE_UPDATE(bezt_array[i].h1, bezt_array[i].h2); + } + } + if (is_cyclic || i != bezt_array_last) { + uint i_next = (i != bezt_array_last) ? i + 1 : 0; + if (knots[i_next].is_removed) { + madd_v3_v3v3fl(bezt_array[i].vec[2], bezt_array[i].vec[1], knots[i].tan[1], knots[i].handles[1]); + HANDLE_UPDATE(bezt_array[i].h2, bezt_array[i].h1); + } + } + } + } + +#undef HANDLE_UPDATE + + MEM_freeN(knots); + + return knots_len_decimated; +} +#define SELECT 1 + + +void BKE_curve_decimate_nurb( + Nurb *nu, const uint resolu, + const float error_sq_max, const uint error_target_len) +{ + const char flag_test = BEZT_FLAG_TEMP_TAG; + + const uint pntsu_dst = BKE_curve_decimate_bezt_array( + nu->bezt, (uint)nu->pntsu, resolu, (nu->flagu & CU_NURB_CYCLIC) != 0, + SELECT, flag_test, + error_sq_max, error_target_len); + + if (pntsu_dst == (uint)nu->pntsu) { + return; + } + + BezTriple *bezt_src = nu->bezt; + BezTriple *bezt_dst = MEM_mallocN(sizeof(BezTriple) * pntsu_dst, __func__); + + int i_src = 0, i_dst = 0; + + while (i_src < nu->pntsu) { + if ((bezt_src[i_src].f2 & flag_test) == 0) { + bezt_dst[i_dst] = bezt_src[i_src]; + i_dst++; + } + i_src++; + } + + MEM_freeN(bezt_src); + + nu->bezt = bezt_dst; + nu->pntsu = i_dst; +} |