[PATCH 07/12] d2d1: Add functions for cubic bezier triangulation.
Connor McAdams
conmanx360 at gmail.com
Mon Feb 24 20:32:18 CST 2020
Add functions for the triangulation of a cubic bezier with it's control
points.
Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
dlls/d2d1/geometry.c | 260 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 260 insertions(+)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 0e2ceb1875..c9ea108484 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -2907,6 +2907,250 @@ static BOOL d2d_geometry_get_next_bezier_segment_idx(struct d2d_geometry *geomet
return d2d_geometry_get_bezier_segment_idx(geometry, idx, TRUE);
}
+struct d2d_cubic_triangles
+{
+ unsigned int triangles[3][3];
+ unsigned int tri_count;
+
+ D2D1_POINT_2F p[4];
+};
+
+struct d2d_cubic_triangulation
+{
+ struct d2d_cubic_triangles *cubic_tri;
+ size_t cubic_tri_count;
+ size_t cubic_tri_size;
+};
+
+static BOOL d2d_point_approximately_equal(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
+{
+ D2D1_POINT_2F length;
+
+ d2d_point_subtract(&length, a, b);
+
+ return (length.x * length.x + length.y * length.y) <
+ (D2D1_CUBIC_BEZIER_EPSILON * D2D1_CUBIC_BEZIER_EPSILON);
+}
+/*
+ * Second function found on
+ * https://blackpawn.com/texts/pointinpoly/default.html page. Uses barycentric
+ * coordinates to see whether or not the point *p is within the triangle
+ * plane defined by points a, b, and c.
+ */
+static BOOL d2d_point_within_triangle(const D2D1_POINT_2F *p, const D2D1_POINT_2F *a, const D2D1_POINT_2F *b,
+ const D2D1_POINT_2F *c)
+{
+ float dot00, dot01, dot02, dot11, dot12, u, v, inverted_denom;
+ D2D1_POINT_2F v0, v1, v2;
+
+ d2d_point_subtract(&v0, c, a);
+ d2d_point_subtract(&v1, b, a);
+ d2d_point_subtract(&v2, p, a);
+
+ dot00 = d2d_point_dot(&v0, &v0);
+ dot01 = d2d_point_dot(&v0, &v1);
+ dot02 = d2d_point_dot(&v0, &v2);
+ dot11 = d2d_point_dot(&v1, &v1);
+ dot12 = d2d_point_dot(&v1, &v2);
+
+ inverted_denom = 1.0f / (dot00 * dot11 - dot01 * dot01);
+ u = (dot11 * dot02 - dot01 * dot12) * inverted_denom;
+ v = (dot00 * dot12 - dot01 * dot02) * inverted_denom;
+
+ return (u >= 0.0f) && (v >= 0.0f) && (u + v < 1.0f);
+}
+
+/* Reusing portions of d2d_geometry_intersect_line_line */
+static BOOL d2d_line_intersect_test(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b, const D2D1_POINT_2F *c,
+ const D2D1_POINT_2F *d)
+{
+ D2D1_POINT_2F v_p, v_q, v_qp;
+ float det, s, t;
+
+ d2d_point_subtract(&v_p, b, a);
+ d2d_point_subtract(&v_q, d, c);
+ d2d_point_subtract(&v_qp, a, c);
+
+ det = v_p.x * v_q.y - v_p.y * v_q.x;
+ if (det == 0.0f)
+ return FALSE;
+
+ s = (v_q.x * v_qp.y - v_q.y * v_qp.x) / det;
+ t = (v_p.x * v_qp.y - v_p.y * v_qp.x) / det;
+
+ if (s < 0.0f || s > 1.0f || t < 0.0f || t > 1.0f)
+ return FALSE;
+
+ return TRUE;
+}
+
+static float d2d_line_length_squared(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
+{
+ return (b->x - a->x) * (b->x - a->x) + (b->y - a->y) * (b->y - a->y);
+}
+
+static void d2d_geometry_set_bezier_triangle(struct d2d_cubic_triangles *tri,
+ unsigned int tri_index, unsigned int i0, unsigned int i1, unsigned int i2)
+{
+ tri->triangles[tri_index][0] = i0;
+ tri->triangles[tri_index][1] = i1;
+ tri->triangles[tri_index][2] = i2;
+}
+
+static void d2d_geometry_triangulate_bezier(struct d2d_cubic_triangles *tri, const D2D1_POINT_2F **p)
+{
+ unsigned int i, j, k, l, tri_point[3];
+
+ for (i = 0; i < 4; i++)
+ tri->p[i] = *p[i];
+
+ /* Check to see if any of the control points are the same. If they are,
+ * we're only going to need one triangle. */
+ for (i = 0; i < 4; i++)
+ {
+ for (j = i + 1; j < 4; j++)
+ {
+ if (d2d_point_approximately_equal(p[i], p[j]))
+ {
+ for (k = 0, l = 0; k < 4; k++)
+ {
+ if (k == j)
+ continue;
+ tri->triangles[0][l++] = k;
+ }
+
+ tri->tri_count = 1;
+ return;
+ }
+
+ }
+ }
+
+ /* Next, check to see if any control points are within the triangles
+ * generated by other control points. If this happens, we're going to end
+ * up needing 3 triangles. For example:
+ * /------------------\
+ * | |
+ * | * p1 |
+ * | |
+ * | * * |
+ * | p0 p3 |
+ * | * p2 |
+ * \------------------/
+ * p3 would be contained within the triangle generated by p0->p1->p2, so
+ * we'll need to create 3 triangles, each with p3 as a common vertex.
+ */
+ for (i = 0; i < 4; i++)
+ {
+ for (j = 0, k = 0; j < 4; j++)
+ {
+ if (i == j)
+ continue;
+ tri_point[k++] = j;
+ }
+
+ if (d2d_point_within_triangle(p[i], p[tri_point[0]], p[tri_point[1]], p[tri_point[2]]))
+ {
+ for (k = 0; k < 3; k++)
+ d2d_geometry_set_bezier_triangle(tri, k, tri_point[k % 3],
+ tri_point[(k + 1) % 3], i);
+
+ tri->tri_count = 3;
+ return;
+ }
+ }
+
+ /* Now, with those two possibilities out of the way, we are down to the
+ * common case: Two triangles, a quad with a line splitting it down the
+ * middle. There are three possible triangles, and we check for which one
+ * to use by checking to see if the lines that split the quad intersect
+ * one another. Once we've found a suitable triangulation, we also find
+ * the shortest line to split the quad.
+ */
+ if (d2d_line_intersect_test(p[0], p[2], p[1], p[3]))
+ {
+ if (d2d_line_length_squared(p[0], p[2]) < d2d_line_length_squared(p[1], p[3]))
+ {
+ d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 2);
+ d2d_geometry_set_bezier_triangle(tri, 1, 0, 2, 3);
+ }
+ else
+ {
+ d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 3);
+ d2d_geometry_set_bezier_triangle(tri, 1, 1, 2, 3);
+ }
+ }
+ else if (d2d_line_intersect_test(p[0], p[3], p[1], p[2]))
+ {
+ if (d2d_line_length_squared(p[0], p[3]) < d2d_line_length_squared(p[1], p[2]))
+ {
+ d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 3);
+ d2d_geometry_set_bezier_triangle(tri, 1, 0, 3, 2);
+ }
+ else
+ {
+ d2d_geometry_set_bezier_triangle(tri, 0, 0, 1, 2);
+ d2d_geometry_set_bezier_triangle(tri, 1, 2, 1, 3);
+ }
+ }
+ else
+ {
+ if (d2d_line_length_squared(p[0], p[1]) < d2d_line_length_squared(p[2], p[3]))
+ {
+ d2d_geometry_set_bezier_triangle(tri, 0, 0, 2, 1);
+ d2d_geometry_set_bezier_triangle(tri, 1, 0, 1, 3);
+ }
+ else
+ {
+ d2d_geometry_set_bezier_triangle(tri, 0, 0, 2, 3);
+ d2d_geometry_set_bezier_triangle(tri, 1, 3, 2, 1);
+ }
+ }
+
+ tri->tri_count = 2;
+}
+
+static HRESULT d2d_geometry_triangulate_beziers(struct d2d_geometry *geometry,
+ struct d2d_cubic_triangulation *triangles)
+{
+ struct d2d_segment_idx idx;
+ struct d2d_figure *figure;
+ struct d2d_cubic_triangles *tri;
+ const D2D1_POINT_2F *p[4];
+ unsigned int i;
+
+ for (i = 0; i < geometry->u.path.figure_count; ++i)
+ {
+ triangles[i].cubic_tri_count = geometry->u.path.figures[i].bezier_control_count;
+ if (!(triangles[i].cubic_tri = heap_calloc(triangles[i].cubic_tri_count, sizeof(*triangles[i].cubic_tri))))
+ {
+ ERR("Failed to allocate bezier triangles array.\n");
+ return E_OUTOFMEMORY;
+ }
+ }
+
+ d2d_geometry_get_first_bezier_segment_idx(geometry, &idx);
+ for(;;)
+ {
+ tri = &triangles[idx.figure_idx].cubic_tri[idx.control_idx];
+ figure = &geometry->u.path.figures[idx.figure_idx];
+ p[0] = &figure->vertices[idx.vertex_idx];
+ p[1] = &figure->bezier_controls[idx.control_idx].c0;
+ p[2] = &figure->bezier_controls[idx.control_idx].c1;
+ if (idx.vertex_idx == figure->vertex_count - 1)
+ p[3] = &figure->vertices[0];
+ else
+ p[3] = &figure->vertices[idx.vertex_idx + 1];
+
+ d2d_geometry_triangulate_bezier(tri, p);
+
+ if (!d2d_geometry_get_next_bezier_segment_idx(geometry, &idx))
+ break;
+ }
+
+ return S_OK;
+}
+
static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry,
const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
{
@@ -3045,15 +3289,26 @@ static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struc
static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
{
+ struct d2d_cubic_triangulation *triangles;
struct d2d_segment_idx idx_p, idx_q;
struct d2d_bezier_vertex *b;
const D2D1_POINT_2F *p[3];
struct d2d_figure *figure;
size_t bezier_idx, i;
+ HRESULT hr;
if (!d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p))
return S_OK;
+ if (!(triangles = heap_calloc(geometry->u.path.figure_count, sizeof(*triangles))))
+ {
+ ERR("Failed to allocate bezier triangulation data.\n");
+ return E_OUTOFMEMORY;
+ }
+
+ if (FAILED(hr = d2d_geometry_triangulate_beziers(geometry, triangles)))
+ return hr;
+
/* Split overlapping bezier control triangles. */
while (d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p))
{
@@ -3131,6 +3386,11 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
++bezier_idx;
}
+ for (i = 0; i < geometry->u.path.figure_count; i++)
+ heap_free(triangles[i].cubic_tri);
+
+ heap_free(triangles);
+
return S_OK;
}
--
2.20.1
More information about the wine-devel
mailing list