Merge remote-tracking branch 'origin/master' into uv_unwrapping_slim_algorithm

5 files changed, 150 insertions, 63 deletions

diff --git a/extern/curve_fit_nd/curve_fit_nd.h b/extern/curve_fit_nd/curve_fit_nd.h
index 7232f802e28..18244799b0f 100644
--- a/extern/curve_fit_nd/curve_fit_nd.h
+++ b/extern/curve_fit_nd/curve_fit_nd.h
@@ -36,7 +36,7 @@
 /* curve_fit_cubic.c */
 
 /**
- * Takes a flat array of points and evalues that to calculate a bezier spline.
+ * Takes a flat array of points and evaluates that to calculate a bezier spline.
  *
  * \param points, points_len: The array of points to calculate a cubics from.
  * \param dims: The number of dimensions for for each element in \a points.
@@ -82,7 +82,7 @@ int curve_fit_cubic_to_points_fl(
         unsigned int **r_corners_index_array, unsigned int *r_corners_index_len);
 
 /**
- * Takes a flat array of points and evalues that to calculate handle lengths.
+ * Takes a flat array of points and evaluates that to calculate handle lengths.
  *
  * \param points, points_len: The array of points to calculate a cubics from.
  * \param dims: The number of dimensions for for each element in \a points.
@@ -107,7 +107,8 @@ int curve_fit_cubic_to_points_single_db(
 
         double  r_handle_l[],
         double  r_handle_r[],
-        double *r_error_sq);
+        double *r_error_sq,
+        unsigned int *r_error_index);
 
 int curve_fit_cubic_to_points_single_fl(
         const float       *points,
@@ -120,7 +121,8 @@ int curve_fit_cubic_to_points_single_fl(
 
         float   r_handle_l[],
         float   r_handle_r[],
-        float  *r_error_sq);
+        float  *r_error_sq,
+        unsigned int *r_error_index);
 
 enum {
 	CURVE_FIT_CALC_HIGH_QUALIY          = (1 << 0),
diff --git a/extern/curve_fit_nd/intern/curve_fit_cubic.c b/extern/curve_fit_nd/intern/curve_fit_cubic.c
index 0a32f1e796a..ed855d34b08 100644
--- a/extern/curve_fit_nd/intern/curve_fit_cubic.c
+++ b/extern/curve_fit_nd/intern/curve_fit_cubic.c
@@ -554,8 +554,8 @@ static void cubic_from_points_fallback(
 	r_cubic->orig_span = (points_offset_len - 1);
 #endif
 
-	/* p1 = p0 - (tan_l * alpha_l);
-	 * p2 = p3 + (tan_r * alpha_r);
+	/* p1 = p0 - (tan_l * alpha);
+	 * p2 = p3 + (tan_r * alpha);
 	 */
 	msub_vn_vnvn_fl(p1, p0, tan_l, alpha, dims);
 	madd_vn_vnvn_fl(p2, p3, tan_r, alpha, dims);
@@ -1436,12 +1436,11 @@ int curve_fit_cubic_to_points_single_db(
 
         double  r_handle_l[],
         double  r_handle_r[],
-        double  *r_error_max_sq)
+        double *r_error_max_sq,
+        uint   *r_error_index)
 {
 	Cubic *cubic = alloca(cubic_alloc_size(dims));
 
-	uint split_index;
-
 	/* in this instance theres no advantage in using length cache,
 	 * since we're not recursively calculating values. */
 #ifdef USE_LENGTH_CACHE
@@ -1462,7 +1461,7 @@ int curve_fit_cubic_to_points_single_db(
 #endif
 	        tan_l, tan_r, error_threshold, dims,
 
-	        cubic, r_error_max_sq, &split_index);
+	        cubic, r_error_max_sq, r_error_index);
 
 #ifdef USE_LENGTH_CACHE
 	if (points_length_cache_alloc) {
@@ -1487,7 +1486,8 @@ int curve_fit_cubic_to_points_single_fl(
 
         float   r_handle_l[],
         float   r_handle_r[],
-        float  *r_error_sq)
+        float  *r_error_sq,
+        uint   *r_error_index)
 {
 	const uint points_flat_len = points_len * dims;
 	double *points_db = malloc(sizeof(double) * points_flat_len);
@@ -1521,7 +1521,8 @@ int curve_fit_cubic_to_points_single_fl(
 	        (double)error_threshold,
 	        tan_l_db, tan_r_db,
 	        r_handle_l_db, r_handle_r_db,
-	        &r_error_sq_db);
+	        &r_error_sq_db,
+	        r_error_index);
 
 	free(points_db);
 
diff --git a/extern/curve_fit_nd/intern/curve_fit_cubic_refit.c b/extern/curve_fit_nd/intern/curve_fit_cubic_refit.c
index bf1ab99995f..83b2383f58c 100644
--- a/extern/curve_fit_nd/intern/curve_fit_cubic_refit.c
+++ b/extern/curve_fit_nd/intern/curve_fit_cubic_refit.c
@@ -137,7 +137,7 @@ struct Knot {
 
 	/* Initially point to contiguous memory, however we may re-assign */
 	double *tan[2];
-} Knot;
+};
 
 
 struct KnotRemoveState {
@@ -207,7 +207,7 @@ struct KnotCornerState {
 
 /* Utility functions */
 
-#ifdef USE_KNOT_REFIT
+#if defined(USE_KNOT_REFIT) && !defined(USE_KNOT_REFIT_REMOVE)
 /**
  * Find the most distant point between the 2 knots.
  */
@@ -269,7 +269,7 @@ static uint knot_find_split_point(
 
 	return split_point;
 }
-#endif  /* USE_KNOT_REFIT */
+#endif  /* USE_KNOT_REFIT && !USE_KNOT_REFIT_REMOVE */
 
 
 #ifdef USE_CORNER_DETECT
@@ -322,9 +322,9 @@ static double knot_remove_error_value(
         const double *points_offset_length_cache,
         const uint dims,
         /* Avoid having to re-calculate again */
-        double r_handle_factors[2])
+        double r_handle_factors[2], uint *r_error_index)
 {
-	double error_sq = FLT_MAX;
+	double error_sq = DBL_MAX;
 
 #ifdef USE_VLA
 	double handle_factor_l[dims];
@@ -338,9 +338,9 @@ static double knot_remove_error_value(
 	        points_offset, points_offset_len, points_offset_length_cache, dims, 0.0,
 	        tan_l, tan_r,
 	        handle_factor_l, handle_factor_r,
-	        &error_sq);
+	        &error_sq, r_error_index);
 
-	assert(error_sq != FLT_MAX);
+	assert(error_sq != DBL_MAX);
 
 	isub_vnvn(handle_factor_l, points_offset, dims);
 	r_handle_factors[0] = dot_vnvn(tan_l, handle_factor_l, dims);
@@ -363,6 +363,7 @@ static double knot_calc_curve_error_value(
 	        ((knot_r->index + pd->points_len) - knot_l->index)) + 1;
 
 	if (points_offset_len != 2) {
+		uint error_index_dummy;
 		return knot_remove_error_value(
 		        tan_l, tan_r,
 		        &pd->points[knot_l->index * dims], points_offset_len,
@@ -372,7 +373,55 @@ static double knot_calc_curve_error_value(
 		        NULL,
 #endif
 		        dims,
-		        r_handle_factors);
+		        r_handle_factors, &error_index_dummy);
+	}
+	else {
+		/* No points between, use 1/3 handle length with no error as a fallback. */
+		assert(points_offset_len == 2);
+#ifdef USE_LENGTH_CACHE
+		r_handle_factors[0] = r_handle_factors[1] = pd->points_length_cache[knot_l->index] / 3.0;
+#else
+		r_handle_factors[0] = r_handle_factors[1] = len_vnvn(
+		        &pd->points[(knot_l->index + 0) * dims],
+		        &pd->points[(knot_l->index + 1) * dims], dims) / 3.0;
+#endif
+		return 0.0;
+	}
+}
+
+#ifdef USE_KNOT_REFIT_REMOVE
+
+static double knot_calc_curve_error_value_and_index(
+        const struct PointData *pd,
+        const struct Knot *knot_l, const struct Knot *knot_r,
+        const double *tan_l, const double *tan_r,
+        const uint dims,
+        double r_handle_factors[2],
+        uint *r_error_index)
+{
+	const uint points_offset_len = ((knot_l->index < knot_r->index) ?
+	        (knot_r->index - knot_l->index) :
+	        ((knot_r->index + pd->points_len) - knot_l->index)) + 1;
+
+	if (points_offset_len != 2) {
+		const double error_sq = knot_remove_error_value(
+		        tan_l, tan_r,
+		        &pd->points[knot_l->index * dims], points_offset_len,
+#ifdef USE_LENGTH_CACHE
+		        &pd->points_length_cache[knot_l->index],
+#else
+		        NULL,
+#endif
+		        dims,
+		        r_handle_factors, r_error_index);
+
+		/* Adjust the offset index to the global index & wrap if needed. */
+		*r_error_index += knot_l->index;
+		if (*r_error_index >= pd->points_len) {
+			*r_error_index -= pd->points_len;
+		}
+
+		return error_sq;
 	}
 	else {
 		/* No points between, use 1/3 handle length with no error as a fallback. */
@@ -384,9 +433,11 @@ static double knot_calc_curve_error_value(
 		        &pd->points[(knot_l->index + 0) * dims],
 		        &pd->points[(knot_l->index + 1) * dims], dims) / 3.0;
 #endif
+		*r_error_index = 0;
 		return 0.0;
 	}
 }
+#endif  /* USE_KNOT_REFIT_REMOVE */
 
 struct KnotRemove_Params {
 	Heap *heap;
@@ -414,7 +465,6 @@ static void knot_remove_error_recalculate(
 		struct KnotRemoveState *r;
 		if (k->heap_node) {
 			r = HEAP_node_ptr(k->heap_node);
-			HEAP_remove(p->heap, k->heap_node);
 		}
 		else {
 #ifdef USE_TPOOL
@@ -422,14 +472,13 @@ static void knot_remove_error_recalculate(
 #else
 			r = malloc(sizeof(*r));
 #endif
-
 			r->index = k->index;
 		}
 
 		r->handles[0] = handles[0];
 		r->handles[1] = handles[1];
 
-		k->heap_node = HEAP_insert(p->heap, cost_sq, r);
+		HEAP_insert_or_update(p->heap, &k->heap_node, cost_sq, r);
 	}
 	else {
 		if (k->heap_node) {
@@ -556,21 +605,23 @@ static void knot_refit_error_recalculate(
 	assert(k->can_remove);
 
 #ifdef USE_KNOT_REFIT_REMOVE
+	(void)knots_len;
+
+	uint refit_index = SPLIT_POINT_INVALID;
 	{
 		double handles[2];
 
 		/* First check if we can remove, this allows to refit and remove as we go. */
-		const double cost_sq = knot_calc_curve_error_value(
+		const double cost_sq = knot_calc_curve_error_value_and_index(
 		        p->pd, k->prev, k->next,
 		        k->prev->tan[1], k->next->tan[0],
 		        dims,
-		        handles);
+		        handles, &refit_index);
 
 		if (cost_sq < error_sq_max) {
 			struct KnotRefitState *r;
 			if (k->heap_node) {
 				r = HEAP_node_ptr(k->heap_node);
-				HEAP_remove(p->heap, k->heap_node);
 			}
 			else {
 #ifdef USE_TPOOL
@@ -591,20 +642,21 @@ static void knot_refit_error_recalculate(
 			r->error_sq[0] = r->error_sq[1] = cost_sq;
 
 			/* Always perform removal before refitting, (make a negative number) */
-			k->heap_node = HEAP_insert(p->heap, cost_sq - error_sq_max, r);
+			HEAP_insert_or_update(p->heap, &k->heap_node, cost_sq - error_sq_max, r);
 
 			return;
 		}
 	}
 #else
 	(void)error_sq_max;
-#endif  /* USE_KNOT_REFIT_REMOVE */
 
 	const uint refit_index = knot_find_split_point(
 	         p->pd, k->prev, k->next,
 	         knots_len,
 	         dims);
 
+#endif  /* USE_KNOT_REFIT_REMOVE */
+
 	if ((refit_index == SPLIT_POINT_INVALID) ||
 	    (refit_index == k->index))
 	{
@@ -634,7 +686,6 @@ static void knot_refit_error_recalculate(
 			struct KnotRefitState *r;
 			if (k->heap_node) {
 				r = HEAP_node_ptr(k->heap_node);
-				HEAP_remove(p->heap, k->heap_node);
 			}
 			else {
 #ifdef USE_TPOOL
@@ -661,7 +712,7 @@ static void knot_refit_error_recalculate(
 			assert(cost_sq_dst_max < cost_sq_src_max);
 
 			/* Weight for the greatest improvement */
-			k->heap_node = HEAP_insert(p->heap, cost_sq_src_max - cost_sq_dst_max, r);
+			HEAP_insert_or_update(p->heap, &k->heap_node, cost_sq_src_max - cost_sq_dst_max, r);
 		}
 	}
 	else {
@@ -840,7 +891,6 @@ static void knot_corner_error_recalculate(
 		struct KnotCornerState *c;
 		if (k_split->heap_node) {
 			c = HEAP_node_ptr(k_split->heap_node);
-			HEAP_remove(p->heap, k_split->heap_node);
 		}
 		else {
 #ifdef USE_TPOOL
@@ -865,7 +915,7 @@ static void knot_corner_error_recalculate(
 		c->error_sq[1] = cost_sq_dst[1];
 
 		const double cost_max_sq = MAX2(cost_sq_dst[0], cost_sq_dst[1]);
-		k_split->heap_node = HEAP_insert(p->heap, cost_max_sq, c);
+		HEAP_insert_or_update(p->heap, &k_split->heap_node, cost_max_sq, c);
 	}
 	else {
 		if (k_split->heap_node) {
@@ -1047,7 +1097,7 @@ int curve_fit_cubic_to_points_refit_db(
         uint   **r_corner_index_array, uint *r_corner_index_len)
 {
 	const uint knots_len = points_len;
-	struct Knot *knots = malloc(sizeof(Knot) * knots_len);
+	struct Knot *knots = malloc(sizeof(struct Knot) * knots_len);
 
 #ifndef USE_CORNER_DETECT
 	(void)r_corner_index_array;
diff --git a/extern/curve_fit_nd/intern/generic_heap.c b/extern/curve_fit_nd/intern/generic_heap.c
index 1e2efa5b43d..09ed84bea43 100644
--- a/extern/curve_fit_nd/intern/generic_heap.c
+++ b/extern/curve_fit_nd/intern/generic_heap.c
@@ -48,13 +48,14 @@
 #  define UNLIKELY(x)     (x)
 #endif
 
+typedef unsigned int uint;
 
 /***/
 
 struct HeapNode {
-	void        *ptr;
-	double       value;
-	unsigned int index;
+	void   *ptr;
+	double  value;
+	uint    index;
 };
 
 /* heap_* pool allocator */
@@ -67,8 +68,8 @@ struct HeapNode {
 #undef TPOOL_STRUCT
 
 struct Heap {
-	unsigned int size;
-	unsigned int bufsize;
+	uint size;
+	uint bufsize;
 	HeapNode **tree;
 
 	struct HeapMemPool pool;
@@ -86,32 +87,32 @@ struct Heap {
 #define HEAP_EQUALS(a, b) ((a)->value == (b)->value)
 #endif
 
-static void heap_swap(Heap *heap, const unsigned int i, const unsigned int j)
+static void heap_swap(Heap *heap, const uint i, const uint j)
 {
 
 #if 0
-	SWAP(unsigned int,  heap->tree[i]->index, heap->tree[j]->index);
-	SWAP(HeapNode *,    heap->tree[i],        heap->tree[j]);
+	SWAP(uint,       heap->tree[i]->index, heap->tree[j]->index);
+	SWAP(HeapNode *, heap->tree[i],        heap->tree[j]);
 #else
 	HeapNode **tree = heap->tree;
 	union {
-		unsigned int  index;
-		HeapNode     *node;
+		uint      index;
+		HeapNode *node;
 	} tmp;
 	SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index);
 	SWAP_TVAL(tmp.node,  tree[i],        tree[j]);
 #endif
 }
 
-static void heap_down(Heap *heap, unsigned int i)
+static void heap_down(Heap *heap, uint i)
 {
 	/* size won't change in the loop */
-	const unsigned int size = heap->size;
+	const uint size = heap->size;
 
 	while (1) {
-		const unsigned int l = HEAP_LEFT(i);
-		const unsigned int r = HEAP_RIGHT(i);
-		unsigned int smallest;
+		const uint l = HEAP_LEFT(i);
+		const uint r = HEAP_RIGHT(i);
+		uint smallest;
 
 		smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i;
 
@@ -128,10 +129,10 @@ static void heap_down(Heap *heap, unsigned int i)
 	}
 }
 
-static void heap_up(Heap *heap, unsigned int i)
+static void heap_up(Heap *heap, uint i)
 {
 	while (i > 0) {
-		const unsigned int p = HEAP_PARENT(i);
+		const uint p = HEAP_PARENT(i);
 
 		if (HEAP_COMPARE(heap->tree[p], heap->tree[i])) {
 			break;
@@ -148,7 +149,7 @@ static void heap_up(Heap *heap, unsigned int i)
  * \{ */
 
 /* use when the size of the heap is known in advance */
-Heap *HEAP_new(unsigned int tot_reserve)
+Heap *HEAP_new(uint tot_reserve)
 {
 	Heap *heap = malloc(sizeof(Heap));
 	/* ensure we have at least one so we can keep doubling it */
@@ -164,7 +165,7 @@ Heap *HEAP_new(unsigned int tot_reserve)
 void HEAP_free(Heap *heap, HeapFreeFP ptrfreefp)
 {
 	if (ptrfreefp) {
-		unsigned int i;
+		uint i;
 
 		for (i = 0; i < heap->size; i++) {
 			ptrfreefp(heap->tree[i]->ptr);
@@ -180,7 +181,7 @@ void HEAP_free(Heap *heap, HeapFreeFP ptrfreefp)
 void HEAP_clear(Heap *heap, HeapFreeFP ptrfreefp)
 {
 	if (ptrfreefp) {
-		unsigned int i;
+		uint i;
 
 		for (i = 0; i < heap->size; i++) {
 			ptrfreefp(heap->tree[i]->ptr);
@@ -215,12 +216,22 @@ HeapNode *HEAP_insert(Heap *heap, double value, void *ptr)
 	return node;
 }
 
-bool HEAP_is_empty(Heap *heap)
+void HEAP_insert_or_update(Heap *heap, HeapNode **node_p, double value, void *ptr)
+{
+	if (*node_p == NULL) {
+		*node_p = HEAP_insert(heap, value, ptr);
+	}
+	else {
+		HEAP_node_value_update_ptr(heap, *node_p, value, ptr);
+	}
+}
+
+bool HEAP_is_empty(const Heap *heap)
 {
 	return (heap->size == 0);
 }
 
-unsigned int HEAP_size(Heap *heap)
+uint HEAP_size(const Heap *heap)
 {
 	return heap->size;
 }
@@ -230,7 +241,7 @@ HeapNode *HEAP_top(Heap *heap)
 	return heap->tree[0];
 }
 
-double HEAP_top_value(Heap *heap)
+double HEAP_top_value(const Heap *heap)
 {
 	return heap->tree[0]->value;
 }
@@ -253,12 +264,12 @@ void *HEAP_popmin(Heap *heap)
 
 void HEAP_remove(Heap *heap, HeapNode *node)
 {
-	unsigned int i = node->index;
+	uint i = node->index;
 
 	assert(heap->size != 0);
 
 	while (i > 0) {
-		unsigned int p = HEAP_PARENT(i);
+		uint p = HEAP_PARENT(i);
 
 		heap_swap(heap, p, i);
 		i = p;
@@ -267,7 +278,25 @@ void HEAP_remove(Heap *heap, HeapNode *node)
 	HEAP_popmin(heap);
 }
 
-double HEAP_node_value(HeapNode *node)
+void HEAP_node_value_update(Heap *heap, HeapNode *node, double value)
+{
+	assert(heap->size != 0);
+	if (node->value == value) {
+		return;
+	}
+	node->value = value;
+	/* Can be called in either order, makes no difference. */
+	heap_up(heap, node->index);
+	heap_down(heap, node->index);
+}
+
+void HEAP_node_value_update_ptr(Heap *heap, HeapNode *node, double value, void *ptr)
+{
+	node->ptr = ptr;
+	HEAP_node_value_update(heap, node, value);
+}
+
+double HEAP_node_value(const HeapNode *node)
 {
 	return node->value;
 }
@@ -276,3 +305,5 @@ void *HEAP_node_ptr(HeapNode *node)
 {
 	return node->ptr;
 }
+
+/** \} */
diff --git a/extern/curve_fit_nd/intern/generic_heap.h b/extern/curve_fit_nd/intern/generic_heap.h
index e39344cf076..7803542ede4 100644
--- a/extern/curve_fit_nd/intern/generic_heap.h
+++ b/extern/curve_fit_nd/intern/generic_heap.h
@@ -39,16 +39,19 @@ typedef struct HeapNode HeapNode;
 typedef void (*HeapFreeFP)(void *ptr);
 
 Heap        *HEAP_new(unsigned int tot_reserve);
-bool         HEAP_is_empty(Heap *heap);
+bool         HEAP_is_empty(const Heap *heap);
 void         HEAP_free(Heap *heap, HeapFreeFP ptrfreefp);
 void        *HEAP_node_ptr(HeapNode *node);
 void         HEAP_remove(Heap *heap, HeapNode *node);
 HeapNode    *HEAP_insert(Heap *heap, double value, void *ptr);
+void         HEAP_insert_or_update(Heap *heap, HeapNode **node_p, double value, void *ptr);
 void        *HEAP_popmin(Heap *heap);
 void         HEAP_clear(Heap *heap, HeapFreeFP ptrfreefp);
-unsigned int HEAP_size(Heap *heap);
+unsigned int HEAP_size(const Heap *heap);
 HeapNode    *HEAP_top(Heap *heap);
-double       HEAP_top_value(Heap *heap);
-double       HEAP_node_value(HeapNode *node);
+double       HEAP_top_value(const Heap *heap);
+void         HEAP_node_value_update(Heap *heap, HeapNode *node, double value);
+void         HEAP_node_value_update_ptr(Heap *heap, HeapNode *node, double value, void *ptr);
+double       HEAP_node_value(const HeapNode *node);
 
 #endif  /* __GENERIC_HEAP_IMPL_H__ */