UI: rewrite color-ramp re-sampling

Instead of picking evenly spaced pixels color-ramp simplification
now works by removing elements with the lowest cost.

source/blender/blenkernel/intern/colorband.c

@@ -30,6 +30,7 @@
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 #include "BLI_math_color.h"
+#include "BLI_heap.h"
 
 #include "DNA_key_types.h"
 #include "DNA_texture_types.h"
@@ -112,23 +113,118 @@ static void colorband_init_from_table_rgba_simple(
 	}
 }
 
+struct ColorResampleElem {
+	struct ColorResampleElem *next, *prev;
+	HeapNode *node;
+	float rgba[4];
+	float pos;
+};
+
+static float color_sample_remove_cost(const struct ColorResampleElem *c)
+{
+	if (c->next == NULL || c->prev == NULL) {
+		return -1.0f;
+	}
+	float area = 0.0f;
+#if 0
+	float xy_prev[2], xy_curr[2], xy_next[2];
+	xy_prev[0] = c->prev->pos;
+	xy_curr[0] = c->pos;
+	xy_next[0] = c->next->pos;
+	for (int i = 0; i < 4; i++) {
+		xy_prev[1] = c->prev->rgba[i];
+		xy_curr[1] = c->rgba[i];
+		xy_next[1] = c->next->rgba[i];
+		area += fabsf(cross_tri_v2(xy_prev, xy_curr, xy_next));
+	}
+#else
+	/* Above logic, optimized (p: previous, c: current, n: next). */
+	const float xpc = c->prev->pos - c->pos;
+	const float xnc = c->next->pos - c->pos;
+	for (int i = 0; i < 4; i++) {
+		const float ycn = c->rgba[i] - c->next->rgba[i];
+		const float ypc = c->prev->rgba[i] - c->rgba[i];
+		area += fabsf((xpc * ycn) + (ypc * xnc));
+	}
+#endif
+	return area;
+}
+
 static void colorband_init_from_table_rgba_resample(
         ColorBand *coba,
         const float (*array)[4], const int array_len)
 {
-	/* TODO: more optimal method of color simplification,
-	 * for now just pick evenly spaced colors. */
 	BLI_assert(array_len >= MAXCOLORBAND);
-	float step = array_len / (float)MAXCOLORBAND;
-	float color_step = 1.0f / (MAXCOLORBAND - 1);
-	for (int i = 0; i < MAXCOLORBAND; i++) {
-		int cur_color = (int)(step * i);
-		copy_v4_v4(&coba->data[i].r, array[cur_color]);
-		coba->data[i].pos = i * color_step;
+	/* Use 2x to avoid noise having too much impact, since this is RGBA accumulated. */
+	const float eps_2x = ((1.0f / 255.0f) + 1e-6f) * 2.0f;
+	struct ColorResampleElem *c, *carr = MEM_mallocN(sizeof(*carr) * array_len, __func__);
+	float color_fac = 1.0f / (float)(array_len - 1);
+	int carr_len = array_len;
+	c = carr;
+	for (int i = 0; i < array_len; i++, c++) {
+		copy_v4_v4(carr[i].rgba, array[i]);
+		c->next = c + 1;
+		c->prev = c - 1;
+		c->pos = i * color_fac;
+	}
+	carr[0].prev = NULL;
+	carr[array_len - 1].next = NULL;
+
+	/* -2 to remove endpoints. */
+	Heap *heap = BLI_heap_new_ex(array_len - 2);
+	c = carr;
+	for (int i = 0; i < array_len; i++, c++) {
+		float cost = color_sample_remove_cost(c);
+		if (cost != -1.0f) {
+			c->node = BLI_heap_insert(heap, cost, c);
+		}
+		else {
+			c->node = NULL;
+		}
+	}
+
+	while ((carr_len > 1 && !BLI_heap_is_empty(heap)) &&
+	       ((carr_len >= MAXCOLORBAND) || (BLI_heap_node_value(BLI_heap_top(heap)) <= eps_2x)))
+	{
+		c = BLI_heap_popmin(heap);
+		struct ColorResampleElem *c_next = c->next, *c_prev = c->prev;
+		c_prev->next = c_next;
+		c_next->prev = c_prev;
+		/* Clear data (not essential, avoid confusion). */
+		c->prev = c->next = NULL;
+		c->node = NULL;
+
+		/* Update adjacent */
+		for (int i = 0; i < 2; i++) {
+			struct ColorResampleElem *c_other = i ? c_next : c_prev;
+			if (c_other->node != NULL) {
+				const float cost = color_sample_remove_cost(c_other);
+				if (cost != -1.0) {
+					BLI_heap_node_value_update(heap, c_other->node, cost);
+				}
+				else {
+					BLI_heap_remove(heap, c_other->node);
+					c_other->node = NULL;
+				}
+			}
+		}
+		carr_len -= 1;
+	}
+	BLI_heap_free(heap, NULL);
+
+	BLI_assert(carr_len < MAXCOLORBAND);
+	int i = 0;
+	/* fist member is never removed. */
+	for (c = carr; c != NULL; c = c->next, i++) {
+		copy_v4_v4(&coba->data[i].r, c->rgba);
+		coba->data[i].pos = c->pos;
 		coba->data[i].cur = i;
 	}
-	coba->tot = MAXCOLORBAND;
+	BLI_assert(i == carr_len);
+	coba->tot = i;
 	coba->cur = 0;
+
+	MEM_freeN(carr);
 }
 
 void BKE_colorband_init_from_table_rgba(