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