20#include "curve_fit_nd.h"
48 const float (*points)[3],
49 const uint points_len,
51 float r_handle_factors[2])
56 float handle_factors[2][3];
58 curve_fit_cubic_to_points_single_fl(&points[0][0],
71 r_handle_factors[0] =
dot_v3v3(tan_l, handle_factors[0]);
73 sub_v3_v3(handle_factors[1], points[points_len - 1]);
74 r_handle_factors[1] =
dot_v3v3(tan_r, handle_factors[1]);
80 Heap *heap,
const float (*points)[3],
const uint points_len,
Knot *k,
const float error_sq_max)
90 const float (*points_offset)[3];
91 uint points_offset_len;
103 k->
prev->
tan[1], k->
next->
tan[0], points_offset, points_offset_len, handles);
105 if (cost_sq < error_sq_max) {
118 const uint points_len,
120 const uint knots_len,
122 const uint error_target_len)
125 for (
uint i = 0; i < knots_len; i++) {
132 uint knots_len_remaining = knots_len;
134 while ((knots_len_remaining > error_target_len) && (
BLI_heap_is_empty(heap) ==
false)) {
144 k_next->
prev = k_prev;
145 k_prev->
next = k_next;
159 knots_len_remaining -= 1;
166 const uint bezt_array_len,
168 const bool is_cyclic,
171 const float error_sq_max,
172 const uint error_target_len)
174 const uint bezt_array_last = bezt_array_len - 1;
181 bezt_array, bezt_array_len, resolu, is_cyclic,
false, 0,
sizeof(
float[3]), &points[0][0]);
183 bezt_array, bezt_array_len, resolu, is_cyclic,
false, 1,
sizeof(
float[3]), &points[0][1]);
185 bezt_array, bezt_array_len, resolu, is_cyclic,
false, 2,
sizeof(
float[3]), &points[0][2]);
187 const uint knots_len = bezt_array_len;
191 memcpy(points[points_len], points[0],
sizeof(
float[3]) * points_len);
194 for (
uint i = 0; i < bezt_array_len; i++) {
198 knots[i].
next = &knots[i + 1];
199 knots[i].
prev = &knots[i - 1];
203 sub_v3_v3v3(knots[i].
tan[0], bezt_array[i].vec[0], bezt_array[i].vec[1]);
206 sub_v3_v3v3(knots[i].
tan[1], bezt_array[i].vec[1], bezt_array[i].vec[2]);
210 knots[i].
co = bezt_array[i].
vec[1];
216 knots[0].
prev = &knots[bezt_array_last];
217 knots[bezt_array_last].
next = &knots[0];
220 knots[0].
prev =
nullptr;
221 knots[bezt_array_last].
next =
nullptr;
228 curve_decimate(points, points_len, knots, knots_len, error_sq_max, error_target_len);
232 uint knots_len_decimated = knots_len;
235#define HANDLE_UPDATE(a, b) \
237 if (a == HD_VECT) { \
240 else if (ELEM(a, HD_AUTO, HD_AUTO_ANIM)) { \
244 if (ELEM(b, HD_AUTO, HD_AUTO_ANIM)) { \
250 for (
uint i = 0; i < bezt_array_len; i++) {
251 if (knots[i].is_removed) {
253 bezt_array[i].
f2 |= flag_set;
254 knots_len_decimated--;
257 bezt_array[i].
f2 &= ~flag_set;
258 if (is_cyclic || i != 0) {
259 uint i_prev = (i != 0) ? i - 1 : bezt_array_last;
260 if (knots[i_prev].is_removed) {
262 bezt_array[i].vec[0], bezt_array[i].vec[1], knots[i].
tan[0], knots[i].handles[0]);
266 if (is_cyclic || i != bezt_array_last) {
267 uint i_next = (i != bezt_array_last) ? i + 1 : 0;
268 if (knots[i_next].is_removed) {
270 bezt_array[i].vec[2], bezt_array[i].vec[1], knots[i].
tan[1], knots[i].handles[1]);
281 return knots_len_decimated;
287 const float error_sq_max,
288 const uint error_target_len)
308 int i_src = 0, i_dst = 0;
310 while (i_src < nu->pntsu) {
311 if ((bezt_src[i_src].f2 &
flag_test) == 0) {
312 bezt_dst[i_dst] = bezt_src[i_src];
318 MEM_delete(bezt_src);
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define HANDLE_UPDATE(a, b)
bool flag_test(uint flag, uint val)
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
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])
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
MINLINE void copy_v2_v2(float r[2], const float a[2])
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
unsigned int BKE_curve_calc_coords_axis_len(unsigned int bezt_array_len, unsigned int resolu, bool is_cyclic, bool use_cyclic_duplicate_endpoint)
MINLINE void sub_v3_v3(float r[3], const float a[3])
MINLINE bool equals_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
unsigned int BKE_curve_decimate_bezt_array(BezTriple *bezt_array, unsigned int bezt_array_len, unsigned int resolu, bool is_cyclic, eBezTriple_Flag flag_test, eBezTriple_Flag flag_set, float error_sq_max, unsigned int error_target_len)
static void curve_decimate(const float(*points)[3], const uint points_len, Knot *knots, const uint knots_len, float error_sq_max, const uint error_target_len)
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
MINLINE float normalize_v3(float n[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
static void knot_remove_error_recalculate(Heap *heap, const float(*points)[3], const uint points_len, Knot *k, const float error_sq_max)
void BKE_curve_calc_coords_axis(const 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)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BKE_curve_decimate_nurb(Nurb *nu, unsigned int resolu, float error_sq_max, unsigned int error_target_len)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float