Henri Verbeet : d2d1: Split overlapping bezier control triangles.
Alexandre Julliard
julliard at winehq.org
Thu Aug 17 18:55:07 CDT 2017
Module: wine
Branch: master
Commit: 2187a1edb394dac7cfbb0f23b6b7d58d59c49333
URL: http://source.winehq.org/git/wine.git/?a=commit;h=2187a1edb394dac7cfbb0f23b6b7d58d59c49333
Author: Henri Verbeet <hverbeet at codeweavers.com>
Date: Wed Aug 16 21:58:26 2017 +0200
d2d1: Split overlapping bezier control triangles.
Signed-off-by: Henri Verbeet <hverbeet at codeweavers.com>
Signed-off-by: Alexandre Julliard <julliard at winehq.org>
---
dlls/d2d1/geometry.c | 160 ++++++++++++++++++++++++++++++++++++++++++++++++-
dlls/d2d1/tests/d2d1.c | 2 +-
2 files changed, 160 insertions(+), 2 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 8796323..8c66881 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -2641,9 +2641,138 @@ static BOOL d2d_geometry_get_next_bezier_segment_idx(struct d2d_geometry *geomet
return d2d_geometry_get_bezier_segment_idx(geometry, idx, TRUE);
}
+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)
+{
+ const D2D1_POINT_2F *a[3], *b[3], *p[2], *q;
+ const struct d2d_figure *figure;
+ 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];
+ 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];
+ 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;
+
+ d2d_point_subtract(&v_q[0], b[1], b[0]);
+ d2d_point_subtract(&v_q[1], b[2], b[0]);
+ d2d_point_subtract(&v_q[2], b[1], b[2]);
+
+ /* Check for intersections between the edges. Strictly speaking we'd only
+ * need to check 8 of the 9 possible intersections, since if there's any
+ * intersection there has to be a second intersection as well. */
+ for (i = 0; i < 3; ++i)
+ {
+ d2d_point_subtract(&v_p, a[(i & 1) + 1], a[i & 2]);
+ for (j = 0; j < 3; ++j)
+ {
+ det = v_p.x * v_q[j].y - v_p.y * v_q[j].x;
+ if (det == 0.0f)
+ continue;
+
+ d2d_point_subtract(&v_qp, a[i & 2], b[j & 2]);
+ t = (v_q[j].x * v_qp.y - v_q[j].y * v_qp.x) / det;
+ if (t <= 0.0f || t >= 1.0f)
+ continue;
+
+ t = (v_p.x * v_qp.y - v_p.y * v_qp.x) / det;
+ if (t <= 0.0f || t >= 1.0f)
+ continue;
+
+ return TRUE;
+ }
+ }
+
+ /* Check if one triangle is contained within the other. */
+ for (j = 0, score = 0, q = a[1], p[0] = b[2]; j < 3; ++j)
+ {
+ p[1] = b[j];
+ d2d_point_subtract(&v_p, p[1], p[0]);
+ d2d_point_subtract(&v_qp, q, p[0]);
+
+ if ((q->y < p[0]->y) != (q->y < p[1]->y) && v_qp.x < v_p.x * (v_qp.y / v_p.y))
+ ++score;
+
+ p[0] = p[1];
+ }
+
+ if (score & 1)
+ return TRUE;
+
+ for (j = 0, score = 0, q = b[1], p[0] = a[2]; j < 3; ++j)
+ {
+ p[1] = a[j];
+ d2d_point_subtract(&v_p, p[1], p[0]);
+ d2d_point_subtract(&v_qp, q, p[0]);
+
+ if ((q->y < p[0]->y) != (q->y < p[1]->y) && v_qp.x < v_p.x * (v_qp.y / v_p.y))
+ ++score;
+
+ p[0] = p[1];
+ }
+
+ return score & 1;
+}
+
+static float d2d_geometry_bezier_ccw(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx)
+{
+ const struct d2d_figure *figure = &geometry->u.path.figures[idx->figure_idx];
+ size_t next = idx->vertex_idx + 1;
+
+ if (next == figure->vertex_count)
+ next = 0;
+
+ return d2d_point_ccw(&figure->vertices[idx->vertex_idx],
+ &figure->bezier_controls[idx->control_idx], &figure->vertices[next]);
+}
+
+static BOOL d2d_geometry_split_bezier(struct d2d_geometry *geometry, const struct d2d_segment_idx *idx)
+{
+ const D2D1_POINT_2F *p[3];
+ struct d2d_figure *figure;
+ D2D1_POINT_2F q[3];
+ size_t next;
+
+ figure = &geometry->u.path.figures[idx->figure_idx];
+ p[0] = &figure->vertices[idx->vertex_idx];
+ p[1] = &figure->bezier_controls[idx->control_idx];
+ next = idx->vertex_idx + 1;
+ if (next == figure->vertex_count)
+ next = 0;
+ p[2] = &figure->vertices[next];
+
+ 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);
+
+ figure->bezier_controls[idx->control_idx] = q[0];
+ if (!(d2d_figure_insert_bezier_control(figure, idx->control_idx + 1, &q[1])))
+ return FALSE;
+ if (!(d2d_figure_insert_vertex(figure, idx->vertex_idx + 1, q[2])))
+ return FALSE;
+ figure->vertex_types[idx->vertex_idx + 1] = D2D_VERTEX_TYPE_SPLIT_BEZIER;
+
+ return TRUE;
+}
+
static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
{
- struct d2d_segment_idx idx_p;
+ struct d2d_segment_idx idx_p, idx_q;
struct d2d_bezier_vertex *b;
const D2D1_POINT_2F *p[3];
struct d2d_figure *figure;
@@ -2652,6 +2781,34 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
if (!d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p))
return S_OK;
+ /* Split overlapping bezier control triangles. */
+ while (d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_p))
+ {
+ 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))
+ {
+ if (fabsf(d2d_geometry_bezier_ccw(geometry, &idx_q)) > fabsf(d2d_geometry_bezier_ccw(geometry, &idx_p)))
+ {
+ if (!d2d_geometry_split_bezier(geometry, &idx_q))
+ return E_OUTOFMEMORY;
+ if (idx_p.figure_idx == idx_q.figure_idx)
+ {
+ ++idx_p.vertex_idx;
+ ++idx_p.control_idx;
+ }
+ }
+ else
+ {
+ if (!d2d_geometry_split_bezier(geometry, &idx_p))
+ return E_OUTOFMEMORY;
+ }
+ }
+ d2d_geometry_get_next_bezier_segment_idx(geometry, &idx_q);
+ }
+ }
+
for (i = 0; i < geometry->u.path.figure_count; ++i)
{
geometry->fill.bezier_vertex_count += 3 * geometry->u.path.figures[i].bezier_control_count;
@@ -2666,6 +2823,7 @@ static HRESULT d2d_geometry_resolve_beziers(struct d2d_geometry *geometry)
}
bezier_idx = 0;
+ d2d_geometry_get_first_bezier_segment_idx(geometry, &idx_p);
for (;;)
{
float sign = -1.0f;
diff --git a/dlls/d2d1/tests/d2d1.c b/dlls/d2d1/tests/d2d1.c
index ade5743..c1ca98d 100644
--- a/dlls/d2d1/tests/d2d1.c
+++ b/dlls/d2d1/tests/d2d1.c
@@ -5696,7 +5696,7 @@ static void test_bezier_intersect(void)
"sQGRAbEBkAGyAZABsgGPAbMBjwG0AY4BtAGNAbUBjQG2AYwBtgGLAbgBigG4AYoBuQGJAboBhwG7"
"AYcBvAGGAb0BhQG+AYQBvwGDAcABggHBAYIBwgGAAcMBf8QBfsYBfMgBe8gBesoBeMwBd80BddAB"
"c9EBcdQBb9YBbNkBatsBaN0BZeEBYuQBX+gBW+0BVvEBUvUBTvwBR4QCQIoCOZgCK6oCGQIA");
- todo_wine ok(match, "Figure does not match.\n");
+ ok(match, "Figure does not match.\n");
ID2D1SolidColorBrush_Release(brush);
ID2D1RenderTarget_Release(rt);
More information about the wine-cvs
mailing list