Add functions for the triangulation of a cubic bezier with it's control points.
Signed-off-by: Connor McAdams conmanx360@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; }