Merge branch 'master' into blender2.8

4 files changed, 230 insertions, 12 deletions

diff --git a/source/blender/blenlib/BLI_bitmap_draw_2d.h b/source/blender/blenlib/BLI_bitmap_draw_2d.h
index fe890e94f1b..e41439e38d2 100644
--- a/source/blender/blenlib/BLI_bitmap_draw_2d.h
+++ b/source/blender/blenlib/BLI_bitmap_draw_2d.h
@@ -29,6 +29,10 @@ void BLI_bitmap_draw_2d_line_v2v2i(
         const int p1[2], const int p2[2],
         bool (*callback)(int, int, void *), void *userData);
 
+void BLI_bitmap_draw_2d_tri_v2i(
+        const int p1[2], const int p2[2], const int p3[2],
+        void (*callback)(int x, int x_end, int y, void *), void *user_data);
+
 void BLI_bitmap_draw_2d_poly_v2i_n(
         const int xmin, const int ymin, const int xmax, const int ymax,
         const int polyXY[][2], const int polyCorners,
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index ffe0ce11cef..ff80d15ea5d 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -356,12 +356,18 @@ void transform_point_by_seg_v3(
         const float l_dst_p1[3], const float l_dst_p2[3],
         const float l_src_p1[3], const float l_src_p2[3]);
 
-void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2],
-                            const float co[2], float w[3]);
-void barycentric_weights_v2_persp(const float v1[4], const float v2[4], const float v3[4],
-                                  const float co[2], float w[3]);
-void barycentric_weights_v2_quad(const float v1[2], const float v2[2], const float v3[2], const float v4[2],
-                                 const float co[2], float w[4]);
+void barycentric_weights_v2(
+        const float v1[2], const float v2[2], const float v3[2],
+        const float co[2], float w[3]);
+void barycentric_weights_v2_clamped(
+        const float v1[2], const float v2[2], const float v3[2],
+        const float co[2], float w[3]);
+void barycentric_weights_v2_persp(
+        const float v1[4], const float v2[4], const float v3[4],
+        const float co[2], float w[3]);
+void barycentric_weights_v2_quad(
+        const float v1[2], const float v2[2], const float v3[2], const float v4[2],
+        const float co[2], float w[4]);
 
 bool barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3]);
 int barycentric_inside_triangle_v2(const float w[3]);
diff --git a/source/blender/blenlib/intern/bitmap_draw_2d.c b/source/blender/blenlib/intern/bitmap_draw_2d.c
index fefd4b4587c..c6386cb3080 100644
--- a/source/blender/blenlib/intern/bitmap_draw_2d.c
+++ b/source/blender/blenlib/intern/bitmap_draw_2d.c
@@ -42,7 +42,8 @@
 #include "BLI_strict_flags.h"
 
 /* -------------------------------------------------------------------- */
-/* Draw Line */
+/** \name Draw Line
+ * \{ */
 
 /**
  * Plot a line from \a p1 to \a p2 (inclusive).
@@ -119,9 +120,186 @@ void BLI_bitmap_draw_2d_line_v2v2i(
 	}
 }
 
+/** \} */
 
 /* -------------------------------------------------------------------- */
-/* Draw Filled Polygon */
+/** \name Draw Filled Triangle
+ * \{ */
+
+/**
+ * Fill a triangle
+ *
+ * Standard algorithm,
+ * See: http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html
+ *
+ * Changes to the basic implementation:
+ *
+ * - Reuse slope calculation when drawing the second triangle.
+ * - Don't calculate the 4th point at all for the triangle split.
+ * - Order line drawing from left to right (minor detail).
+ * - 1-pixel offsets are applied so adjacent triangles don't overlap.
+ *
+ * This is not clipped, a clipped version can be added if needed.
+ */
+
+/* Macros could be moved to a shared location. */
+#define ORDERED_SWAP(ty, a, b) \
+	if (a > b) { SWAP(ty, a, b); } ((void)0)
+
+#define ORDERED_SWAP_BY(ty, a, b, by) \
+	if ((a by) > (b by)) { SWAP(ty, a, b); } ((void)0)
+
+#define ORDER_VARS2(ty, a, b) \
+	{ ORDERED_SWAP(ty, a, b); } ((void)0)
+
+#define ORDER_VARS3_BY(ty, a, b, c, by) \
+	{ \
+		ORDERED_SWAP_BY(ty, b, c, by); \
+		ORDERED_SWAP_BY(ty, a, c, by); \
+		ORDERED_SWAP_BY(ty, a, b, by); \
+	} ((void)0)
+
+static float inv_slope(const int a[2], const int b[2])
+{
+	return ((float)(a[0] - b[0]) /
+	        (float)(a[1] - b[1]));
+}
+
+/**
+ * <pre>
+ * *---*
+ *  \ /
+ *   *
+ * </pre>
+ */
+static void draw_tri_flat_max(
+        const int p[2],
+        const int max_y,
+        const float inv_slope1,
+        const float inv_slope2,
+        void (*callback)(int x, int x_end, int y, void *),
+        void *user_data)
+{
+	float cur_x1 = (float)p[0];
+	float cur_x2 = cur_x1;
+	/* start-end inclusive */
+	const int min_y = p[1];
+	const int max_y_end = max_y + 1;
+	for (int scanline_y = min_y; scanline_y != max_y_end; scanline_y += 1) {
+		callback((int)cur_x1, 1 + (int)cur_x2, scanline_y, user_data);
+		cur_x1 += inv_slope1;
+		cur_x2 += inv_slope2;
+	}
+}
+
+/**
+ * <pre>
+ *   *
+ *  / \
+ * *---*
+ * </pre>
+ */
+static void draw_tri_flat_min(
+        const int p[2],
+        const int min_y,
+        const float inv_slope1,
+        const float inv_slope2,
+        void (*callback)(int x, int x_end, int y, void *),
+        void *user_data)
+{
+	float cur_x1 = (float)p[0];
+	float cur_x2 = cur_x1;
+	/* start-end inclusive */
+	const int max_y = p[1];
+	const int min_y_end = min_y - 1;
+	for (int scanline_y = max_y; scanline_y != min_y_end; scanline_y -= 1) {
+		callback((int)cur_x1, 1 + (int)cur_x2, scanline_y, user_data);
+		cur_x1 -= inv_slope1;
+		cur_x2 -= inv_slope2;
+	}
+}
+
+/**
+ * \note Unclipped (clipped version can be added if needed).
+ */
+void BLI_bitmap_draw_2d_tri_v2i(
+        /* all 2d */
+        const int p1[2],
+        const int p2[2],
+        const int p3[2],
+        void (*callback)(int x, int x_end, int y, void *),
+        void *user_data)
+{
+	/* At first sort the three vertices by y-coordinate ascending so p1 is the top-most vertice */
+	ORDER_VARS3_BY(const int *, p1, p2, p3, [1]);
+
+	BLI_assert(p1[1] <= p2[1] && p2[1] <= p3[1]);
+
+	/* Check for trivial case of bottom-flat triangle. */
+	if (p2[1] == p3[1]) {
+		float inv_slope1 = inv_slope(p2, p1);
+		float inv_slope2 = inv_slope(p3, p1);
+		ORDER_VARS2(float, inv_slope1, inv_slope2);
+		BLI_assert(inv_slope1 <= inv_slope2);
+		draw_tri_flat_max(
+		        p1, p2[1],
+		        inv_slope1, inv_slope2,
+		        callback, user_data);
+	}
+	else if (p1[1] == p2[1]) {
+		/* Check for trivial case of top-flat triangle. */
+		float inv_slope1 = inv_slope(p3, p1);
+		float inv_slope2 = inv_slope(p3, p2);
+		ORDER_VARS2(float, inv_slope2, inv_slope1);
+		BLI_assert(inv_slope1 >= inv_slope2);
+		draw_tri_flat_min(
+		        p3, p2[1] + 1, /* avoid overlap */
+		        inv_slope1, inv_slope2,
+		        callback, user_data);
+	}
+	else {
+		/* General case - split the triangle in a top-flat and bottom-flat one. */
+		const float inv_slope_p21 = inv_slope(p2, p1);
+		const float inv_slope_p31 = inv_slope(p3, p1);
+		const float inv_slope_p32 = inv_slope(p3, p2);
+
+		float inv_slope1_max, inv_slope2_max;
+		float inv_slope2_min, inv_slope1_min;
+
+		if (inv_slope_p21 < inv_slope_p31) {
+			inv_slope1_max = inv_slope_p21;
+			inv_slope2_max = inv_slope_p31;
+			inv_slope2_min = inv_slope_p31;
+			inv_slope1_min = inv_slope_p32;
+		}
+		else {
+			inv_slope1_max = inv_slope_p31;
+			inv_slope2_max = inv_slope_p21;
+			inv_slope2_min = inv_slope_p32;
+			inv_slope1_min = inv_slope_p31;
+		}
+
+		draw_tri_flat_max(
+		        p1, p2[1],
+		        inv_slope1_max, inv_slope2_max,
+		        callback, user_data);
+		draw_tri_flat_min(
+		        p3, p2[1] + 1, /* avoid overlap */
+		        inv_slope1_min, inv_slope2_min,
+		        callback, user_data);
+	}
+}
+
+#undef ORDERED_SWAP
+#undef ORDERED_SWAP_BY
+#undef ORDER_VARS2
+#undef ORDER_VARS3_BY
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Draw Filled Polygon
+ * \{ */
 
 /* sort edge-segments on y, then x axis */
 static int draw_poly_v2i_n__span_y_sort(const void *a_p, const void *b_p, void *verts_p)
@@ -334,3 +512,5 @@ void BLI_bitmap_draw_2d_poly_v2i_n(
 	MEM_freeN(span_y);
 	MEM_freeN(node_x);
 }
+
+/** \} */
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index e179447936a..ee6a3dcc9b3 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -3021,7 +3021,9 @@ bool barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[
  * \note This is *exactly* the same calculation as #resolve_tri_uv_v2,
  * although it has double precision and is used for texture baking, so keep both.
  */
-void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
+void barycentric_weights_v2(
+        const float v1[2], const float v2[2], const float v3[2],
+        const float co[2], float w[3])
 {
 	float wtot;
 
@@ -3039,10 +3041,35 @@ void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3
 }
 
 /**
+ * A version of #barycentric_weights_v2 that doesn't allow negative weights.
+ * Useful when negative values cause problems and points are only ever slightly outside of the triangle.
+ */
+void barycentric_weights_v2_clamped(
+        const float v1[2], const float v2[2], const float v3[2],
+        const float co[2], float w[3])
+{
+	float wtot;
+
+	w[0] = max_ff(cross_tri_v2(v2, v3, co), 0.0f);
+	w[1] = max_ff(cross_tri_v2(v3, v1, co), 0.0f);
+	w[2] = max_ff(cross_tri_v2(v1, v2, co), 0.0f);
+	wtot = w[0] + w[1] + w[2];
+
+	if (wtot != 0.0f) {
+		mul_v3_fl(w, 1.0f / wtot);
+	}
+	else { /* dummy values for zero area face */
+		copy_v3_fl(w, 1.0f / 3.0f);
+	}
+}
+
+/**
  * still use 2D X,Y space but this works for verts transformed by a perspective matrix,
  * using their 4th component as a weight
  */
-void barycentric_weights_v2_persp(const float v1[4], const float v2[4], const float v3[4], const float co[2], float w[3])
+void barycentric_weights_v2_persp(
+        const float v1[4], const float v2[4], const float v3[4],
+        const float co[2], float w[3])
 {
 	float wtot;
 
@@ -3064,8 +3091,9 @@ void barycentric_weights_v2_persp(const float v1[4], const float v2[4], const fl
  * note: untested for values outside the quad's bounds
  * this is #interp_weights_poly_v2 expanded for quads only
  */
-void barycentric_weights_v2_quad(const float v1[2], const float v2[2], const float v3[2], const float v4[2],
-                                 const float co[2], float w[4])
+void barycentric_weights_v2_quad(
+        const float v1[2], const float v2[2], const float v3[2], const float v4[2],
+        const float co[2], float w[4])
 {
 	/* note: fabsf() here is not needed for convex quads (and not used in interp_weights_poly_v2).
 	 *       but in the case of concave/bow-tie quads for the mask rasterizer it gives unreliable results