Cleanup: style, use braces for blenkernel
[blender.git] / source / blender / blenkernel / intern / curve_decimate.c
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 "MEM_guardedalloc.h"
24 #include "BLI_heap.h"
25 #include "BLI_math_vector.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
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
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
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
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) { \
273       a = HD_ALIGN; \
274     } \
275     /* opposite handle */ \
276     if (b == HD_AUTO) { \
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
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 }