Subversion Repositories Kolibri OS

/* -*- 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 

 *	Chris Wilson 

 */

#define _BSD_SOURCE /* for hypot() */

#include "cairoint.h"

#include "cairo-box-inline.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;

    unsigned flags;

#define HORIZONTAL 0x1

#define FORWARDS 0x2

#define JOIN 0x4

} 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_x, half_line_y;

    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_x;

    stroker->bounds.p2.x += stroker->half_line_x;

    stroker->bounds.p1.y -= stroker->half_line_y;

    stroker->bounds.p2.y += stroker->half_line_y;

}

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_is_scale (ctm))

	return FALSE;

    stroker->stroke_style = stroke_style;

    stroker->ctm = ctm;

    stroker->antialias = antialias;

    stroker->half_line_x =

	_cairo_fixed_from_double (fabs(ctm->xx) * stroke_style->line_width / 2.0);

    stroker->half_line_y =

	_cairo_fixed_from_double (fabs(ctm->yy) * 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,

					unsigned		 flags)

{

    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].flags = flags;

    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_x = stroker->half_line_x;

    cairo_fixed_t half_line_y = stroker->half_line_y;

    cairo_status_t status;

    int i, j;

    /* 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). However, we must be

	 * careful not to emit a miter join across a degenerate segment

	 * which has been elided.

	 *

	 * 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.

	 */

	j = i == 0 ? stroker->num_segments - 1 : i-1;

	lengthen_initial = (stroker->segments[i].flags ^ stroker->segments[j].flags) & HORIZONTAL;

	j = i == stroker->num_segments - 1 ? 0 : i+1;

	lengthen_final = (stroker->segments[i].flags ^ stroker->segments[j].flags) & HORIZONTAL;

	if (stroker->open_sub_path) {

	    if (i == 0)

		lengthen_initial = line_cap != CAIRO_LINE_CAP_BUTT;

	    if (i == stroker->num_segments - 1)

		lengthen_final = line_cap != CAIRO_LINE_CAP_BUTT;

	}

	/* Perform the adjustments of the endpoints. */

	if (lengthen_initial | lengthen_final) {

	    if (a->y == b->y) {

		if (a->x < b->x) {

		    if (lengthen_initial)

			a->x -= half_line_x;

		    if (lengthen_final)

			b->x += half_line_x;

		} else {

		    if (lengthen_initial)

			a->x += half_line_x;

		    if (lengthen_final)

			b->x -= half_line_x;

		}

	    } else {

		if (a->y < b->y) {

		    if (lengthen_initial)

			a->y -= half_line_y;

		    if (lengthen_final)

			b->y += half_line_y;

		} else {

		    if (lengthen_initial)

			a->y += half_line_y;

		    if (lengthen_final)

			b->y -= half_line_y;

		}

	    }

	}

	/* Form the rectangle by expanding by half the line width in

	 * either perpendicular direction. */

	if (a->y == b->y) {

	    a->y -= half_line_y;

	    b->y += half_line_y;

	} else {

	    a->x -= half_line_x;

	    b->x += half_line_x;

	}

	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_x = stroker->half_line_x;

    cairo_fixed_t half_line_y = stroker->half_line_y;

    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].flags & HORIZONTAL;

	/* Handle the joins for a potentially degenerate segment. */

	if (line_cap == CAIRO_LINE_CAP_BUTT &&

	    stroker->segments[i].flags & 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;

	    cairo_bool_t forwards = !!(stroker->segments[i].flags & FORWARDS);

	    _cairo_slope_init (&out_slope,

			       &stroker->segments[j].p1,

			       &stroker->segments[j].p2);

	    box.p2 = box.p1 = stroker->segments[i].p2;

	    if (is_horizontal) {

		if (forwards)

		    box.p2.x += half_line_x;

		else

		    box.p1.x -= half_line_x;

		if (out_slope.dy > 0)

		    box.p1.y -= half_line_y;

		else

		    box.p2.y += half_line_y;

	    } else {

		if (forwards)

		    box.p2.y += half_line_y;

		else

		    box.p1.y -= half_line_y;

		if (out_slope.dx > 0)

		    box.p1.x -= half_line_x;

		else

		    box.p2.x += half_line_x;

	    }

	    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_x;

		    b->x += half_line_x;

		} else {

		    a->x += half_line_x;

		    b->x -= half_line_x;

		}

	    }

	    a->y += half_line_y;

	    b->y -= half_line_y;

	} else {

	    if (line_cap == CAIRO_LINE_CAP_SQUARE) {

		if (a->y <= b->y) {

		    a->y -= half_line_y;

		    b->y += half_line_y;

		} else {

		    a->y += half_line_y;

		    b->y -= half_line_y;

		}

	    }

	    a->x += half_line_x;

	    b->x -= half_line_x;

	}

	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) | JOIN);

    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 sf, sign, remain;

    cairo_fixed_t mag;

    cairo_status_t status;

    cairo_line_t segment;

    cairo_bool_t dash_on = FALSE;

    unsigned 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;

	sf = fabs (stroker->ctm->xx);

    } else {

	mag = b->y - a->y;

	sf = fabs (stroker->ctm->yy);

    }

    if (mag < 0) {

	remain = _cairo_fixed_to_double (-mag);

	sign = 1.;

    } else {

	remain = _cairo_fixed_to_double (mag);

	is_horizontal |= FORWARDS;

	sign = -1.;

    }

    segment.p2 = segment.p1 = *a;

    while (remain > 0.) {

	double step_length;

	step_length = MIN (sf * stroker->dash.dash_remain, remain);

	remain -= step_length;

	mag = _cairo_fixed_from_double (sign*remain);

	if (is_horizontal & 0x1)

	    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.) << 2);

	    if (unlikely (status))

		return status;

	    dash_on = TRUE;

	}

	else

	{

	    dash_on = FALSE;

	}

	_cairo_stroker_dash_step (&stroker->dash, step_length / sf);

	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 | JOIN);

	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;

    cairo_box_t box;

    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 (! rectilinear_stroker.dash.dashed &&

	_cairo_path_fixed_is_stroke_box (path, &box) &&

	/* if the segments overlap we need to feed them into the tessellator */

	box.p2.x - box.p1.x > 2* rectilinear_stroker.half_line_x &&

	box.p2.y - box.p1.y > 2* rectilinear_stroker.half_line_y)

    {

	cairo_box_t b;

	/* top */

	b.p1.x = box.p1.x - rectilinear_stroker.half_line_x;

	b.p2.x = box.p2.x + rectilinear_stroker.half_line_x;

	b.p1.y = box.p1.y - rectilinear_stroker.half_line_y;

	b.p2.y = box.p1.y + rectilinear_stroker.half_line_y;

	status = _cairo_boxes_add (boxes, antialias, &b);

	assert (status == CAIRO_INT_STATUS_SUCCESS);

	/* left  (excluding top/bottom) */

	b.p1.x = box.p1.x - rectilinear_stroker.half_line_x;

	b.p2.x = box.p1.x + rectilinear_stroker.half_line_x;

	b.p1.y = box.p1.y + rectilinear_stroker.half_line_y;

	b.p2.y = box.p2.y - rectilinear_stroker.half_line_y;

	status = _cairo_boxes_add (boxes, antialias, &b);

	assert (status == CAIRO_INT_STATUS_SUCCESS);

	/* right  (excluding top/bottom) */

	b.p1.x = box.p2.x - rectilinear_stroker.half_line_x;

	b.p2.x = box.p2.x + rectilinear_stroker.half_line_x;

	b.p1.y = box.p1.y + rectilinear_stroker.half_line_y;

	b.p2.y = box.p2.y - rectilinear_stroker.half_line_y;

	status = _cairo_boxes_add (boxes, antialias, &b);

	assert (status == CAIRO_INT_STATUS_SUCCESS);

	/* bottom */

	b.p1.x = box.p1.x - rectilinear_stroker.half_line_x;

	b.p2.x = box.p2.x + rectilinear_stroker.half_line_x;

	b.p1.y = box.p2.y - rectilinear_stroker.half_line_y;

	b.p2.y = box.p2.y + rectilinear_stroker.half_line_y;

	status = _cairo_boxes_add (boxes, antialias, &b);

	assert (status == CAIRO_INT_STATUS_SUCCESS);

	goto done;

    }

    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;

done:

    _cairo_rectilinear_stroker_fini (&rectilinear_stroker);

    return CAIRO_STATUS_SUCCESS;

BAIL:

    _cairo_rectilinear_stroker_fini (&rectilinear_stroker);

    _cairo_boxes_clear (boxes);

    return status;

}