Blender  V3.3
curve_decimate.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include "DNA_curve_types.h"
8 
9 #include "BLI_heap.h"
10 #include "BLI_math_vector.h"
11 #include "MEM_guardedalloc.h"
12 
13 #include "BKE_curve.h"
14 
15 #include "curve_fit_nd.h"
16 
17 #include "BLI_strict_flags.h"
18 
19 struct Knot {
20  struct Knot *next, *prev;
21  uint point_index; /* Index in point array. */
22  uint knot_index; /* Index in knot array. */
23  float tan[2][3];
24  float handles[2];
25 
29 
30 #ifndef NDEBUG
31  const float *co;
32 #endif
33 };
34 
35 struct Removal {
37  /* handles for prev/next knots */
38  float handles[2];
39 };
40 
41 static float knot_remove_error_value(const float tan_l[3],
42  const float tan_r[3],
43  const float (*points)[3],
44  const uint points_len,
45  /* avoid having to re-calculate again */
46  float r_handle_factors[2])
47 {
48  const uint dims = 3;
49  float error_sq = FLT_MAX;
50  uint error_sq_index;
51  float handle_factors[2][3];
52 
53  curve_fit_cubic_to_points_single_fl(&points[0][0],
54  points_len,
55  NULL,
56  dims,
57  0.0f,
58  tan_l,
59  tan_r,
60  handle_factors[0],
61  handle_factors[1],
62  &error_sq,
63  &error_sq_index);
64 
65  sub_v3_v3(handle_factors[0], points[0]);
66  r_handle_factors[0] = dot_v3v3(tan_l, handle_factors[0]);
67 
68  sub_v3_v3(handle_factors[1], points[points_len - 1]);
69  r_handle_factors[1] = dot_v3v3(tan_r, handle_factors[1]);
70 
71  return error_sq;
72 }
73 
75  const float (*points)[3],
76  const uint points_len,
77  struct Knot *k,
78  const float error_sq_max)
79 {
81  float handles[2];
82 
83 #ifndef NDEBUG
84  BLI_assert(equals_v3v3(points[k->prev->point_index], k->prev->co));
85  BLI_assert(equals_v3v3(points[k->next->point_index], k->next->co));
86 #endif
87 
88  const float(*points_offset)[3];
89  uint points_offset_len;
90 
91  if (k->prev->point_index < k->next->point_index) {
92  points_offset = &points[k->prev->point_index];
93  points_offset_len = (k->next->point_index - k->prev->point_index) + 1;
94  }
95  else {
96  points_offset = &points[k->prev->point_index];
97  points_offset_len = ((k->next->point_index + points_len) - k->prev->point_index) + 1;
98  }
99 
100  const float cost_sq = knot_remove_error_value(
101  k->prev->tan[1], k->next->tan[0], points_offset, points_offset_len, handles);
102 
103  if (cost_sq < error_sq_max) {
104  struct Removal *r;
105  if (k->heap_node) {
107  }
108  else {
109  r = MEM_mallocN(sizeof(*r), __func__);
110  r->knot_index = k->knot_index;
111  }
112 
113  copy_v2_v2(r->handles, handles);
114 
115  BLI_heap_insert_or_update(heap, &k->heap_node, cost_sq, r);
116  }
117  else {
118  if (k->heap_node) {
119  struct Removal *r;
121  BLI_heap_remove(heap, k->heap_node);
122 
123  MEM_freeN(r);
124 
125  k->heap_node = NULL;
126  }
127  }
128 }
129 
130 static void curve_decimate(const float (*points)[3],
131  const uint points_len,
132  struct Knot *knots,
133  const uint knots_len,
134  float error_sq_max,
135  const uint error_target_len)
136 {
137  Heap *heap = BLI_heap_new_ex(knots_len);
138  for (uint i = 0; i < knots_len; i++) {
139  struct Knot *k = &knots[i];
140  if (k->can_remove) {
141  knot_remove_error_recalculate(heap, points, points_len, k, error_sq_max);
142  }
143  }
144 
145  uint knots_len_remaining = knots_len;
146 
147  while ((knots_len_remaining > error_target_len) && (BLI_heap_is_empty(heap) == false)) {
148  struct Knot *k;
149 
150  {
151  struct Removal *r = BLI_heap_pop_min(heap);
152  k = &knots[r->knot_index];
153  k->heap_node = NULL;
154  k->prev->handles[1] = r->handles[0];
155  k->next->handles[0] = r->handles[1];
156  MEM_freeN(r);
157  }
158 
159  struct Knot *k_prev = k->prev;
160  struct Knot *k_next = k->next;
161 
162  /* remove ourselves */
163  k_next->prev = k_prev;
164  k_prev->next = k_next;
165 
166  k->next = NULL;
167  k->prev = NULL;
168  k->is_removed = true;
169 
170  if (k_prev->can_remove) {
171  knot_remove_error_recalculate(heap, points, points_len, k_prev, error_sq_max);
172  }
173 
174  if (k_next->can_remove) {
175  knot_remove_error_recalculate(heap, points, points_len, k_next, error_sq_max);
176  }
177 
178  knots_len_remaining -= 1;
179  }
180 
181  BLI_heap_free(heap, MEM_freeN);
182 }
183 
185  const uint bezt_array_len,
186  const uint resolu,
187  const bool is_cyclic,
188  const char flag_test,
189  const char flag_set,
190  const float error_sq_max,
191  const uint error_target_len)
192 {
193  const uint bezt_array_last = bezt_array_len - 1;
194  const uint points_len = BKE_curve_calc_coords_axis_len(bezt_array_len, resolu, is_cyclic, true);
195 
196  float(*points)[3] = MEM_mallocN((sizeof(float[3]) * points_len * (is_cyclic ? 2 : 1)), __func__);
197 
199  bezt_array, bezt_array_len, resolu, is_cyclic, false, 0, sizeof(float[3]), &points[0][0]);
201  bezt_array, bezt_array_len, resolu, is_cyclic, false, 1, sizeof(float[3]), &points[0][1]);
203  bezt_array, bezt_array_len, resolu, is_cyclic, false, 2, sizeof(float[3]), &points[0][2]);
204 
205  const uint knots_len = bezt_array_len;
206  struct Knot *knots = MEM_mallocN((sizeof(*knots) * bezt_array_len), __func__);
207 
208  if (is_cyclic) {
209  memcpy(points[points_len], points[0], sizeof(float[3]) * points_len);
210  }
211 
212  for (uint i = 0; i < bezt_array_len; i++) {
213  knots[i].heap_node = NULL;
214  knots[i].can_remove = (bezt_array[i].f2 & flag_test) != 0;
215  knots[i].is_removed = false;
216  knots[i].next = &knots[i + 1];
217  knots[i].prev = &knots[i - 1];
218  knots[i].point_index = i * resolu;
219  knots[i].knot_index = i;
220 
221  sub_v3_v3v3(knots[i].tan[0], bezt_array[i].vec[0], bezt_array[i].vec[1]);
222  knots[i].handles[0] = normalize_v3(knots[i].tan[0]);
223 
224  sub_v3_v3v3(knots[i].tan[1], bezt_array[i].vec[1], bezt_array[i].vec[2]);
225  knots[i].handles[1] = -normalize_v3(knots[i].tan[1]);
226 
227 #ifndef NDEBUG
228  knots[i].co = bezt_array[i].vec[1];
229  BLI_assert(equals_v3v3(knots[i].co, points[knots[i].point_index]));
230 #endif
231  }
232 
233  if (is_cyclic) {
234  knots[0].prev = &knots[bezt_array_last];
235  knots[bezt_array_last].next = &knots[0];
236  }
237  else {
238  knots[0].prev = NULL;
239  knots[bezt_array_last].next = NULL;
240 
241  /* always keep end-points */
242  knots[0].can_remove = false;
243  knots[bezt_array_last].can_remove = false;
244  }
245 
246  curve_decimate(points, points_len, knots, knots_len, error_sq_max, error_target_len);
247 
248  MEM_freeN(points);
249 
250  uint knots_len_decimated = knots_len;
251 
252  /* Update handle type on modifications. */
253 #define HANDLE_UPDATE(a, b) \
254  { \
255  if (a == HD_VECT) { \
256  a = HD_FREE; \
257  } \
258  else if (ELEM(a, HD_AUTO, HD_AUTO_ANIM)) { \
259  a = HD_ALIGN; \
260  } \
261  /* opposite handle */ \
262  if (ELEM(b, HD_AUTO, HD_AUTO_ANIM)) { \
263  b = HD_ALIGN; \
264  } \
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) {
280  bezt_array[i].vec[0], bezt_array[i].vec[1], knots[i].tan[0], knots[i].handles[0]);
281  HANDLE_UPDATE(bezt_array[i].h1, bezt_array[i].h2);
282  }
283  }
284  if (is_cyclic || i != bezt_array_last) {
285  uint i_next = (i != bezt_array_last) ? i + 1 : 0;
286  if (knots[i_next].is_removed) {
288  bezt_array[i].vec[2], bezt_array[i].vec[1], knots[i].tan[1], knots[i].handles[1]);
289  HANDLE_UPDATE(bezt_array[i].h2, bezt_array[i].h1);
290  }
291  }
292  }
293  }
294 
295 #undef HANDLE_UPDATE
296 
297  MEM_freeN(knots);
298 
299  return knots_len_decimated;
300 }
301 #define SELECT 1
302 
304  const uint resolu,
305  const float error_sq_max,
306  const uint error_target_len)
307 {
308  const char flag_test = BEZT_FLAG_TEMP_TAG;
309 
310  const uint pntsu_dst = BKE_curve_decimate_bezt_array(nu->bezt,
311  (uint)nu->pntsu,
312  resolu,
313  (nu->flagu & CU_NURB_CYCLIC) != 0,
314  SELECT,
315  flag_test,
316  error_sq_max,
317  error_target_len);
318 
319  if (pntsu_dst == (uint)nu->pntsu) {
320  return;
321  }
322 
323  BezTriple *bezt_src = nu->bezt;
324  BezTriple *bezt_dst = MEM_mallocN(sizeof(BezTriple) * pntsu_dst, __func__);
325 
326  int i_src = 0, i_dst = 0;
327 
328  while (i_src < nu->pntsu) {
329  if ((bezt_src[i_src].f2 & flag_test) == 0) {
330  bezt_dst[i_dst] = bezt_src[i_src];
331  i_dst++;
332  }
333  i_src++;
334  }
335 
336  MEM_freeN(bezt_src);
337 
338  nu->bezt = bezt_dst;
339  nu->pntsu = i_dst;
340 }
typedef float(TangentPoint)[2]
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:1650
void BKE_curve_calc_coords_axis(const struct 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)
#define BLI_assert(a)
Definition: BLI_assert.h:46
A min-heap / priority queue ADT.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:202
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:279
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:301
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:182
void * BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:362
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
MINLINE float normalize_v3(float r[3])
MINLINE void sub_v3_v3(float r[3], const float a[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v2_v2(float r[2], const float a[2])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE bool equals_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
@ CU_NURB_CYCLIC
@ BEZT_FLAG_TEMP_TAG
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
Read Guarded memory(de)allocation.
#define HANDLE_UPDATE(a, b)
#define SELECT
void BKE_curve_decimate_nurb(Nurb *nu, const uint resolu, const float error_sq_max, const uint error_target_len)
uint 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)
static void knot_remove_error_recalculate(Heap *heap, const float(*points)[3], const uint points_len, struct Knot *k, const float error_sq_max)
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])
static void 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)
static bool is_cyclic(const Nurb *nu)
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
INLINE Rall1d< T, V, S > tan(const Rall1d< T, V, S > &arg)
Definition: rall1d.h:327
float vec[3][3]
uint8_t f2
Definition: BLI_heap.c:43
struct Knot * next
uint knot_index
const float * co
uint is_removed
struct Knot * prev
float handles[2]
uint can_remove
uint point_index
float tan[2][3]
HeapNode * heap_node
short flagu
BezTriple * bezt
float handles[2]
uint knot_index
ParamHandle ** handles