1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bke
19 */
20
21 #include "DNA_curve_types.h"
22
23 #include "BLI_heap.h"
24 #include "BLI_math_vector.h"
25 #include "MEM_guardedalloc.h"
26
27 #include "BKE_curve.h"
28
29 #include "curve_fit_nd.h"
30
31 #include "BLI_strict_flags.h"
32
33 struct Knot {
34 struct Knot *next, *prev;
35 uint point_index; /* index in point array */
36 uint knot_index; /* index in knot array*/
37 float tan[2][3];
38 float handles[2];
39
40 HeapNode *heap_node;
41 uint can_remove : 1;
42 uint is_removed : 1;
43
44 #ifndef NDEBUG
45 const float *co;
46 #endif
47 };
48
49 struct Removal {
50 uint knot_index;
51 /* handles for prev/next knots */
52 float handles[2];
53 };
54
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])55 static float knot_remove_error_value(const float tan_l[3],
56 const float tan_r[3],
57 const float (*points)[3],
58 const uint points_len,
59 /* avoid having to re-calculate again */
60 float r_handle_factors[2])
61 {
62 const uint dims = 3;
63 float error_sq = FLT_MAX;
64 uint error_sq_index;
65 float handle_factors[2][3];
66
67 curve_fit_cubic_to_points_single_fl(&points[0][0],
68 points_len,
69 NULL,
70 dims,
71 0.0f,
72 tan_l,
73 tan_r,
74 handle_factors[0],
75 handle_factors[1],
76 &error_sq,
77 &error_sq_index);
78
79 sub_v3_v3(handle_factors[0], points[0]);
80 r_handle_factors[0] = dot_v3v3(tan_l, handle_factors[0]);
81
82 sub_v3_v3(handle_factors[1], points[points_len - 1]);
83 r_handle_factors[1] = dot_v3v3(tan_r, handle_factors[1]);
84
85 return error_sq;
86 }
87
knot_remove_error_recalculate(Heap * heap,const float (* points)[3],const uint points_len,struct Knot * k,const float error_sq_max)88 static void knot_remove_error_recalculate(Heap *heap,
89 const float (*points)[3],
90 const uint points_len,
91 struct Knot *k,
92 const float error_sq_max)
93 {
94 BLI_assert(k->can_remove);
95 float handles[2];
96
97 #ifndef NDEBUG
98 BLI_assert(equals_v3v3(points[k->prev->point_index], k->prev->co));
99 BLI_assert(equals_v3v3(points[k->next->point_index], k->next->co));
100 #endif
101
102 const float(*points_offset)[3];
103 uint points_offset_len;
104
105 if (k->prev->point_index < k->next->point_index) {
106 points_offset = &points[k->prev->point_index];
107 points_offset_len = (k->next->point_index - k->prev->point_index) + 1;
108 }
109 else {
110 points_offset = &points[k->prev->point_index];
111 points_offset_len = ((k->next->point_index + points_len) - k->prev->point_index) + 1;
112 }
113
114 const float cost_sq = knot_remove_error_value(
115 k->prev->tan[1], k->next->tan[0], points_offset, points_offset_len, handles);
116
117 if (cost_sq < error_sq_max) {
118 struct Removal *r;
119 if (k->heap_node) {
120 r = BLI_heap_node_ptr(k->heap_node);
121 }
122 else {
123 r = MEM_mallocN(sizeof(*r), __func__);
124 r->knot_index = k->knot_index;
125 }
126
127 copy_v2_v2(r->handles, handles);
128
129 BLI_heap_insert_or_update(heap, &k->heap_node, cost_sq, r);
130 }
131 else {
132 if (k->heap_node) {
133 struct Removal *r;
134 r = BLI_heap_node_ptr(k->heap_node);
135 BLI_heap_remove(heap, k->heap_node);
136
137 MEM_freeN(r);
138
139 k->heap_node = NULL;
140 }
141 }
142 }
143
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)144 static void curve_decimate(const float (*points)[3],
145 const uint points_len,
146 struct Knot *knots,
147 const uint knots_len,
148 float error_sq_max,
149 const uint error_target_len)
150 {
151 Heap *heap = BLI_heap_new_ex(knots_len);
152 for (uint i = 0; i < knots_len; i++) {
153 struct Knot *k = &knots[i];
154 if (k->can_remove) {
155 knot_remove_error_recalculate(heap, points, points_len, k, error_sq_max);
156 }
157 }
158
159 uint knots_len_remaining = knots_len;
160
161 while ((knots_len_remaining > error_target_len) && (BLI_heap_is_empty(heap) == false)) {
162 struct Knot *k;
163
164 {
165 struct Removal *r = BLI_heap_pop_min(heap);
166 k = &knots[r->knot_index];
167 k->heap_node = NULL;
168 k->prev->handles[1] = r->handles[0];
169 k->next->handles[0] = r->handles[1];
170 MEM_freeN(r);
171 }
172
173 struct Knot *k_prev = k->prev;
174 struct Knot *k_next = k->next;
175
176 /* remove ourselves */
177 k_next->prev = k_prev;
178 k_prev->next = k_next;
179
180 k->next = NULL;
181 k->prev = NULL;
182 k->is_removed = true;
183
184 if (k_prev->can_remove) {
185 knot_remove_error_recalculate(heap, points, points_len, k_prev, error_sq_max);
186 }
187
188 if (k_next->can_remove) {
189 knot_remove_error_recalculate(heap, points, points_len, k_next, error_sq_max);
190 }
191
192 knots_len_remaining -= 1;
193 }
194
195 BLI_heap_free(heap, MEM_freeN);
196 }
197
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)198 uint BKE_curve_decimate_bezt_array(BezTriple *bezt_array,
199 const uint bezt_array_len,
200 const uint resolu,
201 const bool is_cyclic,
202 const char flag_test,
203 const char flag_set,
204 const float error_sq_max,
205 const uint error_target_len)
206 {
207 const uint bezt_array_last = bezt_array_len - 1;
208 const uint points_len = BKE_curve_calc_coords_axis_len(bezt_array_len, resolu, is_cyclic, true);
209
210 float(*points)[3] = MEM_mallocN((sizeof(float[3]) * points_len * (is_cyclic ? 2 : 1)), __func__);
211
212 BKE_curve_calc_coords_axis(
213 bezt_array, bezt_array_len, resolu, is_cyclic, false, 0, sizeof(float[3]), &points[0][0]);
214 BKE_curve_calc_coords_axis(
215 bezt_array, bezt_array_len, resolu, is_cyclic, false, 1, sizeof(float[3]), &points[0][1]);
216 BKE_curve_calc_coords_axis(
217 bezt_array, bezt_array_len, resolu, is_cyclic, false, 2, sizeof(float[3]), &points[0][2]);
218
219 const uint knots_len = bezt_array_len;
220 struct Knot *knots = MEM_mallocN((sizeof(*knots) * bezt_array_len), __func__);
221
222 if (is_cyclic) {
223 memcpy(points[points_len], points[0], sizeof(float[3]) * points_len);
224 }
225
226 for (uint i = 0; i < bezt_array_len; i++) {
227 knots[i].heap_node = NULL;
228 knots[i].can_remove = (bezt_array[i].f2 & flag_test) != 0;
229 knots[i].is_removed = false;
230 knots[i].next = &knots[i + 1];
231 knots[i].prev = &knots[i - 1];
232 knots[i].point_index = i * resolu;
233 knots[i].knot_index = i;
234
235 sub_v3_v3v3(knots[i].tan[0], bezt_array[i].vec[0], bezt_array[i].vec[1]);
236 knots[i].handles[0] = normalize_v3(knots[i].tan[0]);
237
238 sub_v3_v3v3(knots[i].tan[1], bezt_array[i].vec[1], bezt_array[i].vec[2]);
239 knots[i].handles[1] = -normalize_v3(knots[i].tan[1]);
240
241 #ifndef NDEBUG
242 knots[i].co = bezt_array[i].vec[1];
243 BLI_assert(equals_v3v3(knots[i].co, points[knots[i].point_index]));
244 #endif
245 }
246
247 if (is_cyclic) {
248 knots[0].prev = &knots[bezt_array_last];
249 knots[bezt_array_last].next = &knots[0];
250 }
251 else {
252 knots[0].prev = NULL;
253 knots[bezt_array_last].next = NULL;
254
255 /* always keep end-points */
256 knots[0].can_remove = false;
257 knots[bezt_array_last].can_remove = false;
258 }
259
260 curve_decimate(points, points_len, knots, knots_len, error_sq_max, error_target_len);
261
262 MEM_freeN(points);
263
264 uint knots_len_decimated = knots_len;
265
266 /* Update handle type on modifications. */
267 #define HANDLE_UPDATE(a, b) \
268 { \
269 if (a == HD_VECT) { \
270 a = HD_FREE; \
271 } \
272 else if (a == HD_AUTO || a == HD_AUTO_ANIM) { \
273 a = HD_ALIGN; \
274 } \
275 /* opposite handle */ \
276 if (b == HD_AUTO || b == HD_AUTO_ANIM) { \
277 b = HD_ALIGN; \
278 } \
279 } \
280 ((void)0)
281
282 for (uint i = 0; i < bezt_array_len; i++) {
283 if (knots[i].is_removed) {
284 /* caller must remove */
285 bezt_array[i].f2 |= flag_set;
286 knots_len_decimated--;
287 }
288 else {
289 bezt_array[i].f2 &= (char)~flag_set;
290 if (is_cyclic || i != 0) {
291 uint i_prev = (i != 0) ? i - 1 : bezt_array_last;
292 if (knots[i_prev].is_removed) {
293 madd_v3_v3v3fl(
294 bezt_array[i].vec[0], bezt_array[i].vec[1], knots[i].tan[0], knots[i].handles[0]);
295 HANDLE_UPDATE(bezt_array[i].h1, bezt_array[i].h2);
296 }
297 }
298 if (is_cyclic || i != bezt_array_last) {
299 uint i_next = (i != bezt_array_last) ? i + 1 : 0;
300 if (knots[i_next].is_removed) {
301 madd_v3_v3v3fl(
302 bezt_array[i].vec[2], bezt_array[i].vec[1], knots[i].tan[1], knots[i].handles[1]);
303 HANDLE_UPDATE(bezt_array[i].h2, bezt_array[i].h1);
304 }
305 }
306 }
307 }
308
309 #undef HANDLE_UPDATE
310
311 MEM_freeN(knots);
312
313 return knots_len_decimated;
314 }
315 #define SELECT 1
316
BKE_curve_decimate_nurb(Nurb * nu,const uint resolu,const float error_sq_max,const uint error_target_len)317 void BKE_curve_decimate_nurb(Nurb *nu,
318 const uint resolu,
319 const float error_sq_max,
320 const uint error_target_len)
321 {
322 const char flag_test = BEZT_FLAG_TEMP_TAG;
323
324 const uint pntsu_dst = BKE_curve_decimate_bezt_array(nu->bezt,
325 (uint)nu->pntsu,
326 resolu,
327 (nu->flagu & CU_NURB_CYCLIC) != 0,
328 SELECT,
329 flag_test,
330 error_sq_max,
331 error_target_len);
332
333 if (pntsu_dst == (uint)nu->pntsu) {
334 return;
335 }
336
337 BezTriple *bezt_src = nu->bezt;
338 BezTriple *bezt_dst = MEM_mallocN(sizeof(BezTriple) * pntsu_dst, __func__);
339
340 int i_src = 0, i_dst = 0;
341
342 while (i_src < nu->pntsu) {
343 if ((bezt_src[i_src].f2 & flag_test) == 0) {
344 bezt_dst[i_dst] = bezt_src[i_src];
345 i_dst++;
346 }
347 i_src++;
348 }
349
350 MEM_freeN(bezt_src);
351
352 nu->bezt = bezt_dst;
353 nu->pntsu = i_dst;
354 }
355