Update the current bezier control triangle overlap functions to handle cubic beziers.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- dlls/d2d1/geometry.c | 168 +++++++++++++++++++++++++++++++------------ 1 file changed, 123 insertions(+), 45 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c index c78664488d..c740f232cd 100644 --- a/dlls/d2d1/geometry.c +++ b/dlls/d2d1/geometry.c @@ -3273,31 +3273,13 @@ static void d2d_geometry_get_figure_orientation(struct d2d_geometry *geometry, ID2D1Factory_Release((ID2D1Factory *)geometry->factory); }
-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) +static BOOL d2d_check_bezier_triangle_overlap(const D2D1_POINT_2F **a, const D2D1_POINT_2F **b) { - const D2D1_POINT_2F *a[3], *b[3], *p[2], *q; - const struct d2d_figure *figure; + const D2D1_POINT_2F *p[2], *q; D2D1_POINT_2F v_q[3], v_p, v_qp; unsigned int i, j, score; float det, t;
- figure = &geometry->u.path.figures[idx_p->figure_idx]; - a[0] = &figure->vertices[idx_p->vertex_idx]; - a[1] = &figure->bezier_controls[idx_p->control_idx].cq0; - if (idx_p->vertex_idx == figure->vertex_count - 1) - a[2] = &figure->vertices[0]; - else - a[2] = &figure->vertices[idx_p->vertex_idx + 1]; - - figure = &geometry->u.path.figures[idx_q->figure_idx]; - b[0] = &figure->vertices[idx_q->vertex_idx]; - b[1] = &figure->bezier_controls[idx_q->control_idx].cq0; - if (idx_q->vertex_idx == figure->vertex_count - 1) - b[2] = &figure->vertices[0]; - else - b[2] = &figure->vertices[idx_q->vertex_idx + 1]; - if (d2d_point_ccw(a[0], a[1], a[2]) == 0.0f || d2d_point_ccw(b[0], b[1], b[2]) == 0.0f) return FALSE;
@@ -3361,48 +3343,144 @@ static BOOL d2d_geometry_check_bezier_overlap(struct d2d_geometry *geometry, return score & 1; }
-static float d2d_geometry_bezier_ccw(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx) +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, + struct d2d_cubic_triangulation *triangles) { - const struct d2d_figure *figure = &geometry->u.path.figures[idx->figure_idx]; - size_t next = idx->vertex_idx + 1; + const D2D1_POINT_2F *p[4], *q[4], *a[3], *b[3]; + struct d2d_cubic_triangles *tri_p, *tri_q; + const struct d2d_figure *figure; + unsigned int i, j; + size_t next;
+ figure = &geometry->u.path.figures[idx_p->figure_idx]; + p[0] = &figure->vertices[idx_p->vertex_idx]; + p[1] = &figure->bezier_controls[idx_p->control_idx].c0; + p[2] = &figure->bezier_controls[idx_p->control_idx].c1; + next = idx_p->vertex_idx + 1; + if (next == figure->vertex_count) + next = 0; + p[3] = &figure->vertices[next]; + + figure = &geometry->u.path.figures[idx_q->figure_idx]; + q[0] = &figure->vertices[idx_q->vertex_idx]; + q[1] = &figure->bezier_controls[idx_q->control_idx].c0; + q[2] = &figure->bezier_controls[idx_q->control_idx].c1; + next = idx_q->vertex_idx + 1; if (next == figure->vertex_count) next = 0; + q[3] = &figure->vertices[next]; + + /* Get the triangle structure for each. */ + tri_p = &triangles[idx_p->figure_idx].cubic_tri[idx_p->control_idx]; + tri_q = &triangles[idx_q->figure_idx].cubic_tri[idx_q->control_idx];
- return d2d_point_ccw(&figure->vertices[idx->vertex_idx], - &figure->bezier_controls[idx->control_idx].cq0, &figure->vertices[next]); + for (i = 0; i < tri_p->tri_count; i++) + { + a[0] = p[tri_p->triangles[i][0]]; + a[1] = p[tri_p->triangles[i][1]]; + a[2] = p[tri_p->triangles[i][2]]; + for (j = 0; j < tri_q->tri_count; j++) + { + b[0] = q[tri_q->triangles[j][0]]; + b[1] = q[tri_q->triangles[j][1]]; + b[2] = q[tri_q->triangles[j][2]]; + if (d2d_check_bezier_triangle_overlap(a, b)) + return TRUE; + } + } + + return FALSE; }
-static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx) +static float d2d_geometry_bezier_ccw(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx, + struct d2d_cubic_triangulation *triangles) { - const D2D1_POINT_2F *p[3]; - struct d2d_figure *figure; - D2D1_POINT_2F q[3], c[2]; + struct d2d_cubic_triangles *tri = &triangles[idx->figure_idx].cubic_tri[idx->control_idx]; + const struct d2d_figure *figure; + const D2D1_POINT_2F *p[4]; + float total_size; size_t next; + unsigned int i;
figure = &geometry->u.path.figures[idx->figure_idx]; p[0] = &figure->vertices[idx->vertex_idx]; - p[1] = &figure->bezier_controls[idx->control_idx].cq0; + p[1] = &figure->bezier_controls[idx->control_idx].c0; + p[2] = &figure->bezier_controls[idx->control_idx].c1; next = idx->vertex_idx + 1; if (next == figure->vertex_count) next = 0; - p[2] = &figure->vertices[next]; + p[3] = &figure->vertices[next]; + + for (i = 0, total_size = 0.0f; i < tri->tri_count; i++) + total_size += fabsf(d2d_point_ccw(p[tri->triangles[i][0]], p[tri->triangles[i][1]], p[tri->triangles[i][2]])); + + return total_size; +} + +static BOOL d2d_geometry_insert_bezier_triangulation(struct d2d_cubic_triangulation *triangles, size_t idx, + struct d2d_cubic_triangles *tri) +{ + if (!d2d_array_reserve((void **)&triangles->cubic_tri, &triangles->cubic_tri_size, + triangles->cubic_tri_count + 1, sizeof(*triangles->cubic_tri))) + { + ERR("Failed to grow bezier triangles array.\n"); + return FALSE; + }
- d2d_point_lerp(&q[0], p[0], p[1], 0.5f); - d2d_point_lerp(&q[1], p[1], p[2], 0.5f); - d2d_point_lerp(&q[2], &q[0], &q[1], 0.5f); + memmove(&triangles->cubic_tri[idx + 1], &triangles->cubic_tri[idx], + (triangles->cubic_tri_count - idx) * sizeof(*triangles->cubic_tri)); + triangles->cubic_tri[idx] = *tri; + ++triangles->cubic_tri_count;
- d2d_bezier_quad_to_cubic(p[0], &q[0], &q[2], &c[0], &c[1]); + return TRUE; +}
- figure->bezier_controls[idx->control_idx].cq0 = q[0]; - figure->bezier_controls[idx->control_idx].c0 = c[0]; - figure->bezier_controls[idx->control_idx].c1 = c[1]; +static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx, + struct d2d_cubic_triangulation *triangles) +{ + const D2D1_POINT_2F *p[4], *q[4]; + D2D1_POINT_2F cq[2]; + struct d2d_cubic_triangulation *tri_fig = &triangles[idx->figure_idx]; + struct d2d_cubic_triangles new_triangle; + struct d2d_figure *figure; + D2D1_BEZIER_SEGMENT b[2]; + size_t next;
- d2d_bezier_quad_to_cubic(&q[0], &q[1], p[2], &c[0], &c[1]); + 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; + next = idx->vertex_idx + 1; + if (next == figure->vertex_count) + next = 0; + p[3] = &figure->vertices[next];
- if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &c[0], &c[1], &q[1]))) + d2d_cubic_bezier_split(p[0], p[1], p[2], p[3], 0.5f, &b[0], &b[1], NULL); + + q[0] = p[0]; + q[1] = &b[0].point1; + q[2] = &b[0].point2; + q[3] = &b[0].point3; + d2d_bezier_cubic_to_quad(q[0], q[1], q[2], q[3], &cq[0]); + d2d_geometry_triangulate_bezier(&tri_fig->cubic_tri[idx->control_idx], q); + + q[0] = &b[0].point3; + q[1] = &b[1].point1; + q[2] = &b[1].point2; + q[3] = &b[1].point3; + d2d_bezier_cubic_to_quad(q[0], q[1], q[2], q[3], &cq[1]); + d2d_geometry_triangulate_bezier(&new_triangle, q); + new_triangle.inside = tri_fig->cubic_tri[idx->control_idx].inside; + + figure->bezier_controls[idx->control_idx].c0 = b[0].point1; + figure->bezier_controls[idx->control_idx].c1 = b[0].point2; + figure->bezier_controls[idx->control_idx].cq0 = cq[0]; + if (!(d2d_geometry_insert_bezier_triangulation(tri_fig, idx->control_idx + 1, &new_triangle))) + return FALSE; + if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &b[1].point1, &b[1].point2, &cq[1]))) return FALSE; - if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2]))) + if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, b[0].point3))) return FALSE; figure->vertex_types[idx->vertex_idx + 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER;
@@ -3437,11 +3515,11 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_q); while (idx_q.figure_idx < idx_p.figure_idx || idx_q.vertex_idx < idx_p.vertex_idx) { - while (d2d_geometry_check_bezier_overlap(geometry, &idx_p, &idx_q)) + while (d2d_geometry_check_bezier_overlap(geometry, &idx_p, &idx_q, triangles)) { - if (fabsf(d2d_geometry_bezier_ccw(geometry, &idx_q)) > fabsf(d2d_geometry_bezier_ccw(geometry, &idx_p))) + if (d2d_geometry_bezier_ccw(geometry, &idx_q, triangles) > d2d_geometry_bezier_ccw(geometry, &idx_p, triangles)) { - if (!d2d_geometry_split_bezier(geometry, &idx_q)) + if (!d2d_geometry_split_bezier(geometry, &idx_q, triangles)) return E_OUTOFMEMORY; if (idx_p.figure_idx == idx_q.figure_idx) { @@ -3451,7 +3529,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry) } else { - if (!d2d_geometry_split_bezier(geometry, &idx_p)) + if (!d2d_geometry_split_bezier(geometry, &idx_p, triangles)) return E_OUTOFMEMORY; } }