Blender V5.3
curve_decimate.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "DNA_curve_types.h"
10
11#include "BLI_heap.hh"
12#include "BLI_math_vector_c.hh"
13#include "MEM_guardedalloc.h"
14
15#include "BKE_curve.hh"
16
17namespace blender {
18
19extern "C" {
20#include "curve_fit_nd.h"
21}
22
23#include <cstring>
24
25#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
26
27struct Knot {
29 uint point_index; /* Index in point array. */
30 uint knot_index; /* Index in knot array. */
31 float tan[2][3];
32 float handles[2];
33
40
41#ifndef NDEBUG
42 const float *co;
43#endif
44};
45
46static float knot_remove_error_value(const float tan_l[3],
47 const float tan_r[3],
48 const float (*points)[3],
49 const uint points_len,
50 /* avoid having to re-calculate again */
51 float r_handle_factors[2])
52{
53 const uint dims = 3;
54 float error_sq = FLT_MAX;
55 uint error_sq_index;
56 float handle_factors[2][3];
57
58 curve_fit_cubic_to_points_single_fl(&points[0][0],
59 points_len,
60 nullptr,
61 dims,
62 0.0f,
63 tan_l,
64 tan_r,
65 handle_factors[0],
66 handle_factors[1],
67 &error_sq,
68 &error_sq_index);
69
70 sub_v3_v3(handle_factors[0], points[0]);
71 r_handle_factors[0] = dot_v3v3(tan_l, handle_factors[0]);
72
73 sub_v3_v3(handle_factors[1], points[points_len - 1]);
74 r_handle_factors[1] = dot_v3v3(tan_r, handle_factors[1]);
75
76 return error_sq;
77}
78
80 Heap *heap, const float (*points)[3], const uint points_len, Knot *k, const float error_sq_max)
81{
83 float handles[2];
84
85#ifndef NDEBUG
86 BLI_assert(equals_v3v3(points[k->prev->point_index], k->prev->co));
87 BLI_assert(equals_v3v3(points[k->next->point_index], k->next->co));
88#endif
89
90 const float (*points_offset)[3];
91 uint points_offset_len;
92
93 if (k->prev->point_index < k->next->point_index) {
94 points_offset = &points[k->prev->point_index];
95 points_offset_len = (k->next->point_index - k->prev->point_index) + 1;
96 }
97 else {
98 points_offset = &points[k->prev->point_index];
99 points_offset_len = ((k->next->point_index + points_len) - k->prev->point_index) + 1;
100 }
101
102 const float cost_sq = knot_remove_error_value(
103 k->prev->tan[1], k->next->tan[0], points_offset, points_offset_len, handles);
104
105 if (cost_sq < error_sq_max) {
106 copy_v2_v2(k->removal_handles, handles);
107 BLI_heap_insert_or_update(heap, &k->heap_node, cost_sq, k);
108 }
109 else {
110 if (k->heap_node) {
111 BLI_heap_remove(heap, k->heap_node);
112 k->heap_node = nullptr;
113 }
114 }
115}
116
117static void curve_decimate(const float (*points)[3],
118 const uint points_len,
119 Knot *knots,
120 const uint knots_len,
121 float error_sq_max,
122 const uint error_target_len)
123{
124 Heap *heap = BLI_heap_new_ex(knots_len);
125 for (uint i = 0; i < knots_len; i++) {
126 Knot *k = &knots[i];
127 if (k->can_remove) {
128 knot_remove_error_recalculate(heap, points, points_len, k, error_sq_max);
129 }
130 }
131
132 uint knots_len_remaining = knots_len;
133
134 while ((knots_len_remaining > error_target_len) && (BLI_heap_is_empty(heap) == false)) {
135 Knot *k = static_cast<Knot *>(BLI_heap_pop_min(heap));
136 k->heap_node = nullptr;
137 k->prev->handles[1] = k->removal_handles[0];
138 k->next->handles[0] = k->removal_handles[1];
139
140 Knot *k_prev = k->prev;
141 Knot *k_next = k->next;
142
143 /* remove ourselves */
144 k_next->prev = k_prev;
145 k_prev->next = k_next;
146
147 k->next = nullptr;
148 k->prev = nullptr;
149 k->is_removed = true;
150
151 if (k_prev->can_remove) {
152 knot_remove_error_recalculate(heap, points, points_len, k_prev, error_sq_max);
153 }
154
155 if (k_next->can_remove) {
156 knot_remove_error_recalculate(heap, points, points_len, k_next, error_sq_max);
157 }
158
159 knots_len_remaining -= 1;
160 }
161
162 BLI_heap_free(heap, nullptr);
163}
164
166 const uint bezt_array_len,
167 const uint resolu,
168 const bool is_cyclic,
170 const eBezTriple_Flag flag_set,
171 const float error_sq_max,
172 const uint error_target_len)
173{
174 const uint bezt_array_last = bezt_array_len - 1;
175 const uint points_len = BKE_curve_calc_coords_axis_len(bezt_array_len, resolu, is_cyclic, true);
176
177 float (*points)[3] = MEM_new_array_uninitialized<float[3]>(points_len * (is_cyclic ? 2 : 1),
178 __func__);
179
181 bezt_array, bezt_array_len, resolu, is_cyclic, false, 0, sizeof(float[3]), &points[0][0]);
183 bezt_array, bezt_array_len, resolu, is_cyclic, false, 1, sizeof(float[3]), &points[0][1]);
185 bezt_array, bezt_array_len, resolu, is_cyclic, false, 2, sizeof(float[3]), &points[0][2]);
186
187 const uint knots_len = bezt_array_len;
188 Knot *knots = MEM_new_array_uninitialized<Knot>(bezt_array_len, __func__);
189
190 if (is_cyclic) {
191 memcpy(points[points_len], points[0], sizeof(float[3]) * points_len);
192 }
193
194 for (uint i = 0; i < bezt_array_len; i++) {
195 knots[i].heap_node = nullptr;
196 knots[i].can_remove = (bezt_array[i].f2 & flag_test) != 0;
197 knots[i].is_removed = false;
198 knots[i].next = &knots[i + 1];
199 knots[i].prev = &knots[i - 1];
200 knots[i].point_index = i * resolu;
201 knots[i].knot_index = i;
202
203 sub_v3_v3v3(knots[i].tan[0], bezt_array[i].vec[0], bezt_array[i].vec[1]);
204 knots[i].handles[0] = normalize_v3(knots[i].tan[0]);
205
206 sub_v3_v3v3(knots[i].tan[1], bezt_array[i].vec[1], bezt_array[i].vec[2]);
207 knots[i].handles[1] = -normalize_v3(knots[i].tan[1]);
208
209#ifndef NDEBUG
210 knots[i].co = bezt_array[i].vec[1];
211 BLI_assert(equals_v3v3(knots[i].co, points[knots[i].point_index]));
212#endif
213 }
214
215 if (is_cyclic) {
216 knots[0].prev = &knots[bezt_array_last];
217 knots[bezt_array_last].next = &knots[0];
218 }
219 else {
220 knots[0].prev = nullptr;
221 knots[bezt_array_last].next = nullptr;
222
223 /* always keep end-points */
224 knots[0].can_remove = false;
225 knots[bezt_array_last].can_remove = false;
226 }
227
228 curve_decimate(points, points_len, knots, knots_len, error_sq_max, error_target_len);
229
230 MEM_delete(points);
231
232 uint knots_len_decimated = knots_len;
233
234/* Update handle type on modifications. */
235#define HANDLE_UPDATE(a, b) \
236 { \
237 if (a == HD_VECT) { \
238 a = HD_FREE; \
239 } \
240 else if (ELEM(a, HD_AUTO, HD_AUTO_ANIM)) { \
241 a = HD_ALIGN; \
242 } \
243 /* opposite handle */ \
244 if (ELEM(b, HD_AUTO, HD_AUTO_ANIM)) { \
245 b = HD_ALIGN; \
246 } \
247 } \
248 ((void)0)
249
250 for (uint i = 0; i < bezt_array_len; i++) {
251 if (knots[i].is_removed) {
252 /* caller must remove */
253 bezt_array[i].f2 |= flag_set;
254 knots_len_decimated--;
255 }
256 else {
257 bezt_array[i].f2 &= ~flag_set;
258 if (is_cyclic || i != 0) {
259 uint i_prev = (i != 0) ? i - 1 : bezt_array_last;
260 if (knots[i_prev].is_removed) {
262 bezt_array[i].vec[0], bezt_array[i].vec[1], knots[i].tan[0], knots[i].handles[0]);
263 HANDLE_UPDATE(bezt_array[i].h1, bezt_array[i].h2);
264 }
265 }
266 if (is_cyclic || i != bezt_array_last) {
267 uint i_next = (i != bezt_array_last) ? i + 1 : 0;
268 if (knots[i_next].is_removed) {
270 bezt_array[i].vec[2], bezt_array[i].vec[1], knots[i].tan[1], knots[i].handles[1]);
271 HANDLE_UPDATE(bezt_array[i].h2, bezt_array[i].h1);
272 }
273 }
274 }
275 }
276
277#undef HANDLE_UPDATE
278
279 MEM_delete(knots);
280
281 return knots_len_decimated;
282}
283#define SELECT 1
284
286 const uint resolu,
287 const float error_sq_max,
288 const uint error_target_len)
289{
291
292 const uint pntsu_dst = BKE_curve_decimate_bezt_array(nu->bezt,
293 uint(nu->pntsu),
294 resolu,
295 (nu->flagu & CU_NURB_CYCLIC) != 0,
297 flag_test,
298 error_sq_max,
299 error_target_len);
300
301 if (pntsu_dst == uint(nu->pntsu)) {
302 return;
303 }
304
305 BezTriple *bezt_src = nu->bezt;
306 BezTriple *bezt_dst = MEM_new_array_uninitialized<BezTriple>(pntsu_dst, __func__);
307
308 int i_src = 0, i_dst = 0;
309
310 while (i_src < nu->pntsu) {
311 if ((bezt_src[i_src].f2 & flag_test) == 0) {
312 bezt_dst[i_dst] = bezt_src[i_src];
313 i_dst++;
314 }
315 i_src++;
316 }
317
318 MEM_delete(bezt_src);
319
320 nu->bezt = bezt_dst;
321 nu->pntsu = i_dst;
322}
323
324} // namespace blender
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define HANDLE_UPDATE(a, b)
#define FLT_MAX
#define tan
bool flag_test(uint flag, uint val)
BMesh Iterators.
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:271
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static float knot_remove_error_value(const float tan_l[3], const float tan_r[3], const float(*points)[3], const uint points_len, float r_handle_factors[2])
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
Definition BLI_heap.cc:309
MINLINE void copy_v2_v2(float r[2], const float a[2])
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
unsigned int BKE_curve_calc_coords_axis_len(unsigned int bezt_array_len, unsigned int resolu, bool is_cyclic, bool use_cyclic_duplicate_endpoint)
Definition curve.cc:1629
MINLINE void sub_v3_v3(float r[3], const float a[3])
MINLINE bool equals_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
unsigned int BKE_curve_decimate_bezt_array(BezTriple *bezt_array, unsigned int bezt_array_len, unsigned int resolu, bool is_cyclic, eBezTriple_Flag flag_test, eBezTriple_Flag flag_set, float error_sq_max, unsigned int error_target_len)
static void curve_decimate(const float(*points)[3], const uint points_len, Knot *knots, const uint knots_len, float error_sq_max, const uint error_target_len)
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
Definition BLI_heap.cc:261
MINLINE float normalize_v3(float n[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
static void knot_remove_error_recalculate(Heap *heap, const float(*points)[3], const uint points_len, Knot *k, const float error_sq_max)
void BKE_curve_calc_coords_axis(const BezTriple *bezt_array, unsigned int bezt_array_len, unsigned int resolu, bool is_cyclic, bool use_cyclic_duplicate_endpoint, unsigned int axis, unsigned int stride, float *r_points)
Definition curve.cc:1639
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BKE_curve_decimate_nurb(Nurb *nu, unsigned int resolu, float error_sq_max, unsigned int error_target_len)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
eBezTriple_Flag f2
const float * co
HeapNode * heap_node
float removal_handles[2]
float tan[2][3]
BezTriple * bezt
eNurbKnotFlag flagu