stroke: Rely on the tessellator to remove self-intersections

As handling joins/caps between line segments shorter than
half_line_width is tricky.

Rather than also fixing the bug in traps, remove that code. The plan is
to avoiding hitting the traps code, short-circuiting several steps along
the fast rectangular paths.

Fixes line-width-overlap.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

1 files changed, 658 insertions, 0 deletions

diff --git a/src/cairo-path-stroke-boxes.c b/src/cairo-path-stroke-boxes.c
new file mode 100644
index 000000000..de3a628ae
--- /dev/null
+++ b/src/cairo-path-stroke-boxes.c
@@ -0,0 +1,658 @@
+/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2002 University of Southern California
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is University of Southern
+ * California.
+ *
+ * Contributor(s):
+ *	Carl D. Worth <cworth@cworth.org>
+ *	Chris Wilson <chris@chris-wilson.co.uk>
+ */
+
+#define _BSD_SOURCE /* for hypot() */
+#include "cairoint.h"
+
+#include "cairo-box-private.h"
+#include "cairo-boxes-private.h"
+#include "cairo-error-private.h"
+#include "cairo-path-fixed-private.h"
+#include "cairo-slope-private.h"
+#include "cairo-stroke-dash-private.h"
+
+typedef struct _segment_t {
+    cairo_point_t p1, p2;
+    cairo_bool_t is_horizontal;
+    cairo_bool_t has_join;
+} segment_t;
+
+typedef struct _cairo_rectilinear_stroker {
+    const cairo_stroke_style_t *stroke_style;
+    const cairo_matrix_t *ctm;
+    cairo_antialias_t antialias;
+
+    cairo_fixed_t half_line_width;
+    cairo_boxes_t *boxes;
+    cairo_point_t current_point;
+    cairo_point_t first_point;
+    cairo_bool_t open_sub_path;
+
+    cairo_stroker_dash_t dash;
+
+    cairo_bool_t has_bounds;
+    cairo_box_t bounds;
+
+    int num_segments;
+    int segments_size;
+    segment_t *segments;
+    segment_t segments_embedded[8]; /* common case is a single rectangle */
+} cairo_rectilinear_stroker_t;
+
+static void
+_cairo_rectilinear_stroker_limit (cairo_rectilinear_stroker_t *stroker,
+				  const cairo_box_t *boxes,
+				  int num_boxes)
+{
+    stroker->has_bounds = TRUE;
+    _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
+
+    stroker->bounds.p1.x -= stroker->half_line_width;
+    stroker->bounds.p2.x += stroker->half_line_width;
+
+    stroker->bounds.p1.y -= stroker->half_line_width;
+    stroker->bounds.p2.y += stroker->half_line_width;
+}
+
+static cairo_bool_t
+_cairo_rectilinear_stroker_init (cairo_rectilinear_stroker_t	*stroker,
+				 const cairo_stroke_style_t	*stroke_style,
+				 const cairo_matrix_t		*ctm,
+				 cairo_antialias_t		 antialias,
+				 cairo_boxes_t			*boxes)
+{
+    /* This special-case rectilinear stroker only supports
+     * miter-joined lines (not curves) and a translation-only matrix
+     * (though it could probably be extended to support a matrix with
+     * uniform, integer scaling).
+     *
+     * It also only supports horizontal and vertical line_to
+     * elements. But we don't catch that here, but instead return
+     * UNSUPPORTED from _cairo_rectilinear_stroker_line_to if any
+     * non-rectilinear line_to is encountered.
+     */
+    if (stroke_style->line_join	!= CAIRO_LINE_JOIN_MITER)
+	return FALSE;
+
+    /* If the miter limit turns right angles into bevels, then we
+     * can't use this optimization. Remember, the ratio is
+     * 1/sin(ɸ/2). So the cutoff is 1/sin(π/4.0) or ⎷2,
+     * which we round for safety. */
+    if (stroke_style->miter_limit < M_SQRT2)
+	return FALSE;
+
+    if (! (stroke_style->line_cap == CAIRO_LINE_CAP_BUTT ||
+	   stroke_style->line_cap == CAIRO_LINE_CAP_SQUARE))
+    {
+	return FALSE;
+    }
+
+    if (! _cairo_matrix_has_unity_scale (ctm))
+	return FALSE;
+
+    stroker->stroke_style = stroke_style;
+    stroker->ctm = ctm;
+    stroker->antialias = antialias;
+
+    stroker->half_line_width =
+	_cairo_fixed_from_double (stroke_style->line_width / 2.0);
+    stroker->open_sub_path = FALSE;
+    stroker->segments = stroker->segments_embedded;
+    stroker->segments_size = ARRAY_LENGTH (stroker->segments_embedded);
+    stroker->num_segments = 0;
+
+    _cairo_stroker_dash_init (&stroker->dash, stroke_style);
+
+    stroker->has_bounds = FALSE;
+
+    stroker->boxes = boxes;
+
+    return TRUE;
+}
+
+static void
+_cairo_rectilinear_stroker_fini (cairo_rectilinear_stroker_t	*stroker)
+{
+    if (stroker->segments != stroker->segments_embedded)
+	free (stroker->segments);
+}
+
+static cairo_status_t
+_cairo_rectilinear_stroker_add_segment (cairo_rectilinear_stroker_t *stroker,
+					const cairo_point_t	*p1,
+					const cairo_point_t	*p2,
+					cairo_bool_t		 is_horizontal,
+					cairo_bool_t		 has_join)
+{
+    if (CAIRO_INJECT_FAULT ())
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    if (stroker->num_segments == stroker->segments_size) {
+	int new_size = stroker->segments_size * 2;
+	segment_t *new_segments;
+
+	if (stroker->segments == stroker->segments_embedded) {
+	    new_segments = _cairo_malloc_ab (new_size, sizeof (segment_t));
+	    if (unlikely (new_segments == NULL))
+		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+	    memcpy (new_segments, stroker->segments,
+		    stroker->num_segments * sizeof (segment_t));
+	} else {
+	    new_segments = _cairo_realloc_ab (stroker->segments,
+					      new_size, sizeof (segment_t));
+	    if (unlikely (new_segments == NULL))
+		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+	}
+
+	stroker->segments_size = new_size;
+	stroker->segments = new_segments;
+    }
+
+    stroker->segments[stroker->num_segments].p1 = *p1;
+    stroker->segments[stroker->num_segments].p2 = *p2;
+    stroker->segments[stroker->num_segments].has_join = has_join;
+    stroker->segments[stroker->num_segments].is_horizontal = is_horizontal;
+    stroker->num_segments++;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_rectilinear_stroker_emit_segments (cairo_rectilinear_stroker_t *stroker)
+{
+    cairo_line_cap_t line_cap = stroker->stroke_style->line_cap;
+    cairo_fixed_t half_line_width = stroker->half_line_width;
+    cairo_status_t status;
+    int i;
+
+    /* For each segment we generate a single rectangle.
+     * This rectangle is based on a perpendicular extension (by half the
+     * line width) of the segment endpoints * after some adjustments of the
+     * endpoints to account for caps and joins.
+     */
+    for (i = 0; i < stroker->num_segments; i++) {
+	cairo_bool_t lengthen_initial, lengthen_final;
+	cairo_point_t *a, *b;
+	cairo_box_t box;
+
+	a = &stroker->segments[i].p1;
+	b = &stroker->segments[i].p2;
+
+	/* We adjust the initial point of the segment to extend the
+	 * rectangle to include the previous cap or join, (this
+	 * adjustment applies to all segments except for the first
+	 * segment of open, butt-capped paths).
+	 *
+	 * Overlapping segments will be eliminated by the tessellation.
+	 * Ideally, we would not emit these self-intersections at all,
+	 * but that is tricky with segments shorter than half_line_width.
+	 */
+	lengthen_initial = TRUE;
+	lengthen_final = TRUE;
+	if (stroker->open_sub_path && line_cap == CAIRO_LINE_CAP_BUTT) {
+	    if (i == 0)
+		lengthen_initial = FALSE;
+
+	    if (i == stroker->num_segments - 1)
+		lengthen_final = FALSE;
+	}
+
+	/* Perform the adjustments of the endpoints. */
+	if (a->y == b->y) {
+	    if (a->x < b->x) {
+		if (lengthen_initial)
+		    a->x -= half_line_width;
+		if (lengthen_final)
+		    b->x += half_line_width;
+	    } else {
+		if (lengthen_initial)
+		    a->x += half_line_width;
+		if (lengthen_final)
+		    b->x -= half_line_width;
+	    }
+	} else {
+	    if (a->y < b->y) {
+		if (lengthen_initial)
+		    a->y -= half_line_width;
+		if (lengthen_final)
+		    b->y += half_line_width;
+	    } else {
+		if (lengthen_initial)
+		    a->y += half_line_width;
+		if (lengthen_final)
+		    b->y -= half_line_width;
+	    }
+	}
+
+	/* Form the rectangle by expanding by half the line width in
+	 * either perpendicular direction. */
+	if (a->y == b->y) {
+	    a->y -= half_line_width;
+	    b->y += half_line_width;
+	} else {
+	    a->x -= half_line_width;
+	    b->x += half_line_width;
+	}
+
+	if (a->x < b->x) {
+	    box.p1.x = a->x;
+	    box.p2.x = b->x;
+	} else {
+	    box.p1.x = b->x;
+	    box.p2.x = a->x;
+	}
+	if (a->y < b->y) {
+	    box.p1.y = a->y;
+	    box.p2.y = b->y;
+	} else {
+	    box.p1.y = b->y;
+	    box.p2.y = a->y;
+	}
+
+	status = _cairo_boxes_add (stroker->boxes, stroker->antialias, &box);
+	if (unlikely (status))
+	    return status;
+    }
+
+    stroker->num_segments = 0;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_rectilinear_stroker_emit_segments_dashed (cairo_rectilinear_stroker_t *stroker)
+{
+    cairo_status_t status;
+    cairo_line_cap_t line_cap = stroker->stroke_style->line_cap;
+    cairo_fixed_t half_line_width = stroker->half_line_width;
+    int i;
+
+    for (i = 0; i < stroker->num_segments; i++) {
+	cairo_point_t *a, *b;
+	cairo_bool_t is_horizontal;
+	cairo_box_t box;
+
+	a = &stroker->segments[i].p1;
+	b = &stroker->segments[i].p2;
+
+	is_horizontal = stroker->segments[i].is_horizontal;
+
+	/* Handle the joins for a potentially degenerate segment. */
+	if (line_cap == CAIRO_LINE_CAP_BUTT &&
+	    stroker->segments[i].has_join &&
+	    (i != stroker->num_segments - 1 ||
+	     (! stroker->open_sub_path && stroker->dash.dash_starts_on)))
+	{
+	    cairo_slope_t out_slope;
+	    int j = (i + 1) % stroker->num_segments;
+
+	    box.p1 = stroker->segments[i].p1;
+	    box.p2 = stroker->segments[i].p2;
+	    _cairo_slope_init (&out_slope,
+			       &stroker->segments[j].p1,
+			       &stroker->segments[j].p2);
+
+	    if (is_horizontal) {
+		if (box.p1.x <= box.p2.x) {
+		    box.p1.x = box.p2.x;
+		    box.p2.x += half_line_width;
+		} else {
+		    box.p1.x = box.p2.x - half_line_width;
+		}
+		if (out_slope.dy >= 0)
+		    box.p1.y -= half_line_width;
+		if (out_slope.dy <= 0)
+		    box.p2.y += half_line_width;
+	    } else {
+		if (box.p1.y <= box.p2.y) {
+		    box.p1.y = box.p2.y;
+		    box.p2.y += half_line_width;
+		} else {
+		    box.p1.y = box.p2.y - half_line_width;
+		}
+		if (out_slope.dx >= 0)
+		    box.p1.x -= half_line_width;
+		if (out_slope.dx <= 0)
+		    box.p2.x += half_line_width;
+	    }
+
+	    status = _cairo_boxes_add (stroker->boxes, stroker->antialias, &box);
+	    if (unlikely (status))
+		return status;
+	}
+
+	/* Perform the adjustments of the endpoints. */
+	if (is_horizontal) {
+	    if (line_cap == CAIRO_LINE_CAP_SQUARE) {
+		if (a->x <= b->x) {
+		    a->x -= half_line_width;
+		    b->x += half_line_width;
+		} else {
+		    a->x += half_line_width;
+		    b->x -= half_line_width;
+		}
+	    }
+
+	    a->y += half_line_width;
+	    b->y -= half_line_width;
+	} else {
+	    if (line_cap == CAIRO_LINE_CAP_SQUARE) {
+		if (a->y <= b->y) {
+		    a->y -= half_line_width;
+		    b->y += half_line_width;
+		} else {
+		    a->y += half_line_width;
+		    b->y -= half_line_width;
+		}
+	    }
+
+	    a->x += half_line_width;
+	    b->x -= half_line_width;
+	}
+
+	if (a->x == b->x && a->y == b->y)
+	    continue;
+
+	if (a->x < b->x) {
+	    box.p1.x = a->x;
+	    box.p2.x = b->x;
+	} else {
+	    box.p1.x = b->x;
+	    box.p2.x = a->x;
+	}
+	if (a->y < b->y) {
+	    box.p1.y = a->y;
+	    box.p2.y = b->y;
+	} else {
+	    box.p1.y = b->y;
+	    box.p2.y = a->y;
+	}
+
+	status = _cairo_boxes_add (stroker->boxes, stroker->antialias, &box);
+	if (unlikely (status))
+	    return status;
+    }
+
+    stroker->num_segments = 0;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_rectilinear_stroker_move_to (void		*closure,
+				    const cairo_point_t	*point)
+{
+    cairo_rectilinear_stroker_t *stroker = closure;
+    cairo_status_t status;
+
+    if (stroker->dash.dashed)
+	status = _cairo_rectilinear_stroker_emit_segments_dashed (stroker);
+    else
+	status = _cairo_rectilinear_stroker_emit_segments (stroker);
+    if (unlikely (status))
+	return status;
+
+    /* reset the dash pattern for new sub paths */
+    _cairo_stroker_dash_start (&stroker->dash);
+
+    stroker->current_point = *point;
+    stroker->first_point = *point;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_rectilinear_stroker_line_to (void		*closure,
+				    const cairo_point_t	*b)
+{
+    cairo_rectilinear_stroker_t *stroker = closure;
+    cairo_point_t *a = &stroker->current_point;
+    cairo_status_t status;
+
+    /* We only support horizontal or vertical elements. */
+    assert (a->x == b->x || a->y == b->y);
+
+    /* We don't draw anything for degenerate paths. */
+    if (a->x == b->x && a->y == b->y)
+	return CAIRO_STATUS_SUCCESS;
+
+    status = _cairo_rectilinear_stroker_add_segment (stroker, a, b,
+						     a->y == b->y,
+						     TRUE);
+
+    stroker->current_point = *b;
+    stroker->open_sub_path = TRUE;
+
+    return status;
+}
+
+static cairo_status_t
+_cairo_rectilinear_stroker_line_to_dashed (void		*closure,
+					   const cairo_point_t	*point)
+{
+    cairo_rectilinear_stroker_t *stroker = closure;
+    const cairo_point_t *a = &stroker->current_point;
+    const cairo_point_t *b = point;
+    cairo_bool_t fully_in_bounds;
+    double sign, remain;
+    cairo_fixed_t mag;
+    cairo_status_t status;
+    cairo_line_t segment;
+    cairo_bool_t dash_on = FALSE;
+    cairo_bool_t is_horizontal;
+
+    /* We don't draw anything for degenerate paths. */
+    if (a->x == b->x && a->y == b->y)
+	return CAIRO_STATUS_SUCCESS;
+
+    /* We only support horizontal or vertical elements. */
+    assert (a->x == b->x || a->y == b->y);
+
+    fully_in_bounds = TRUE;
+    if (stroker->has_bounds &&
+	(! _cairo_box_contains_point (&stroker->bounds, a) ||
+	 ! _cairo_box_contains_point (&stroker->bounds, b)))
+    {
+	fully_in_bounds = FALSE;
+    }
+
+    is_horizontal = a->y == b->y;
+    if (is_horizontal)
+	mag = b->x - a->x;
+    else
+	mag = b->y - a->y;
+    if (mag < 0) {
+	remain = _cairo_fixed_to_double (-mag);
+	sign = 1.;
+    } else {
+	remain = _cairo_fixed_to_double (mag);
+	sign = -1.;
+    }
+
+    segment.p2 = segment.p1 = *a;
+    while (remain > 0.) {
+	double step_length;
+
+	step_length = MIN (stroker->dash.dash_remain, remain);
+	remain -= step_length;
+
+	mag = _cairo_fixed_from_double (sign*remain);
+	if (is_horizontal)
+	    segment.p2.x = b->x + mag;
+	else
+	    segment.p2.y = b->y + mag;
+
+	if (stroker->dash.dash_on &&
+	    (fully_in_bounds ||
+	     _cairo_box_intersects_line_segment (&stroker->bounds, &segment)))
+	{
+	    status = _cairo_rectilinear_stroker_add_segment (stroker,
+							     &segment.p1,
+							     &segment.p2,
+							     is_horizontal,
+							     remain <= 0.);
+	    if (unlikely (status))
+		return status;
+
+	    dash_on = TRUE;
+	}
+	else
+	{
+	    dash_on = FALSE;
+	}
+
+	_cairo_stroker_dash_step (&stroker->dash, step_length);
+	segment.p1 = segment.p2;
+    }
+
+    if (stroker->dash.dash_on && ! dash_on &&
+	(fully_in_bounds ||
+	 _cairo_box_intersects_line_segment (&stroker->bounds, &segment)))
+    {
+
+	/* This segment ends on a transition to dash_on, compute a new face
+	 * and add cap for the beginning of the next dash_on step.
+	 */
+
+	status = _cairo_rectilinear_stroker_add_segment (stroker,
+							 &segment.p1,
+							 &segment.p1,
+							 is_horizontal,
+							 TRUE);
+	if (unlikely (status))
+	    return status;
+    }
+
+    stroker->current_point = *point;
+    stroker->open_sub_path = TRUE;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_rectilinear_stroker_close_path (void *closure)
+{
+    cairo_rectilinear_stroker_t *stroker = closure;
+    cairo_status_t status;
+
+    /* We don't draw anything for degenerate paths. */
+    if (! stroker->open_sub_path)
+	return CAIRO_STATUS_SUCCESS;
+
+    if (stroker->dash.dashed) {
+	status = _cairo_rectilinear_stroker_line_to_dashed (stroker,
+							    &stroker->first_point);
+    } else {
+	status = _cairo_rectilinear_stroker_line_to (stroker,
+						     &stroker->first_point);
+    }
+    if (unlikely (status))
+	return status;
+
+    stroker->open_sub_path = FALSE;
+
+    if (stroker->dash.dashed)
+	status = _cairo_rectilinear_stroker_emit_segments_dashed (stroker);
+    else
+	status = _cairo_rectilinear_stroker_emit_segments (stroker);
+    if (unlikely (status))
+	return status;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_int_status_t
+_cairo_path_fixed_stroke_rectilinear_to_boxes (const cairo_path_fixed_t	*path,
+					       const cairo_stroke_style_t	*stroke_style,
+					       const cairo_matrix_t	*ctm,
+					       cairo_antialias_t	 antialias,
+					       cairo_boxes_t		*boxes)
+{
+    cairo_rectilinear_stroker_t rectilinear_stroker;
+    cairo_int_status_t status;
+
+    assert (_cairo_path_fixed_stroke_is_rectilinear (path));
+
+    if (! _cairo_rectilinear_stroker_init (&rectilinear_stroker,
+					   stroke_style, ctm, antialias,
+					   boxes))
+    {
+	return CAIRO_INT_STATUS_UNSUPPORTED;
+    }
+
+    if (boxes->num_limits) {
+	_cairo_rectilinear_stroker_limit (&rectilinear_stroker,
+					  boxes->limits,
+					  boxes->num_limits);
+    }
+
+    status = _cairo_path_fixed_interpret (path,
+					  _cairo_rectilinear_stroker_move_to,
+					  rectilinear_stroker.dash.dashed ?
+					  _cairo_rectilinear_stroker_line_to_dashed :
+					  _cairo_rectilinear_stroker_line_to,
+					  NULL,
+					  _cairo_rectilinear_stroker_close_path,
+					  &rectilinear_stroker);
+    if (unlikely (status))
+	goto BAIL;
+
+    if (rectilinear_stroker.dash.dashed)
+	status = _cairo_rectilinear_stroker_emit_segments_dashed (&rectilinear_stroker);
+    else
+	status = _cairo_rectilinear_stroker_emit_segments (&rectilinear_stroker);
+    if (unlikely (status))
+	goto BAIL;
+
+    /* As we incrementally tessellate, we do not eliminate self-intersections */
+    status = _cairo_bentley_ottmann_tessellate_boxes (boxes,
+						      CAIRO_FILL_RULE_WINDING,
+						      boxes);
+    if (unlikely (status))
+	goto BAIL;
+
+    _cairo_rectilinear_stroker_fini (&rectilinear_stroker);
+
+    return CAIRO_STATUS_SUCCESS;
+
+BAIL:
+    _cairo_rectilinear_stroker_fini (&rectilinear_stroker);
+    _cairo_boxes_clear (boxes);
+    return status;
+}