[PATCH 10/12] d2d1: Update bezier overlap checking for cubics.
Connor McAdams
conmanx360 at gmail.com
Mon Feb 24 20:32:21 CST 2020
Update the current bezier control triangle overlap functions to handle
cubic beziers.
Signed-off-by: Connor McAdams <conmanx360 at 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;
}
}
--
2.20.1
More information about the wine-devel
mailing list