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