Back to index

lightning-sunbird  0.9+nobinonly
Classes | Typedefs | Functions
cairo-hull.c File Reference
#include "cairoint.h"

Go to the source code of this file.

Classes

struct  cairo_hull

Typedefs

typedef struct cairo_hull cairo_hull_t

Functions

static cairo_hull_t_cairo_hull_create (cairo_pen_vertex_t *vertices, int num_vertices)
static int _cairo_hull_vertex_compare (const void *av, const void *bv)
static int _cairo_hull_prev_valid (cairo_hull_t *hull, int num_hull, int index)
static int _cairo_hull_next_valid (cairo_hull_t *hull, int num_hull, int index)
static cairo_status_t _cairo_hull_eliminate_concave (cairo_hull_t *hull, int num_hull)
static cairo_status_t _cairo_hull_to_pen (cairo_hull_t *hull, cairo_pen_vertex_t *vertices, int *num_vertices)
cairo_status_t _cairo_hull_compute (cairo_pen_vertex_t *vertices, int *num_vertices)

Class Documentation

struct cairo_hull

Definition at line 39 of file cairo-hull.c.

Collaboration diagram for cairo_hull:
Class Members
int discard
int id
cairo_point_t point
cairo_slope_t slope

Typedef Documentation

typedef struct cairo_hull cairo_hull_t

Function Documentation

cairo_status_t _cairo_hull_compute ( cairo_pen_vertex_t vertices,
int num_vertices 
)

Definition at line 193 of file cairo-hull.c.

{
    cairo_hull_t *hull;
    int num_hull = *num_vertices;

    hull = _cairo_hull_create (vertices, num_hull);
    if (hull == NULL)
       return CAIRO_STATUS_NO_MEMORY;

    qsort (hull + 1, num_hull - 1,
          sizeof (cairo_hull_t), _cairo_hull_vertex_compare);

    _cairo_hull_eliminate_concave (hull, num_hull);

    _cairo_hull_to_pen (hull, vertices, num_vertices);

    free (hull);

    return CAIRO_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static cairo_hull_t* _cairo_hull_create ( cairo_pen_vertex_t vertices,
int  num_vertices 
) [static]

Definition at line 48 of file cairo-hull.c.

{
    int i;
    cairo_hull_t *hull;
    cairo_point_t *p, *extremum, tmp;

    extremum = &vertices[0].point;
    for (i = 1; i < num_vertices; i++) {
       p = &vertices[i].point;
       if (p->y < extremum->y || (p->y == extremum->y && p->x < extremum->x))
           extremum = p;
    }
    /* Put the extremal point at the beginning of the array */
    tmp = *extremum;
    *extremum = vertices[0].point;
    vertices[0].point = tmp;

    hull = malloc (num_vertices * sizeof (cairo_hull_t));
    if (hull == NULL)
       return NULL;

    for (i = 0; i < num_vertices; i++) {
       hull[i].point = vertices[i].point;
       _cairo_slope_init (&hull[i].slope, &hull[0].point, &hull[i].point);

        /* give each point a unique id for later comparison */
        hull[i].id = i;

        /* Don't discard by default */
        hull[i].discard = 0;

       /* Discard all points coincident with the extremal point */
       if (i != 0 && hull[i].slope.dx == 0 && hull[i].slope.dy == 0)
           hull[i].discard = 1;
    }

    return hull;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static cairo_status_t _cairo_hull_eliminate_concave ( cairo_hull_t hull,
int  num_hull 
) [static]

Definition at line 144 of file cairo-hull.c.

{
    int i, j, k;
    cairo_slope_t slope_ij, slope_jk;

    i = 0;
    j = _cairo_hull_next_valid (hull, num_hull, i);
    k = _cairo_hull_next_valid (hull, num_hull, j);

    do {
       _cairo_slope_init (&slope_ij, &hull[i].point, &hull[j].point);
       _cairo_slope_init (&slope_jk, &hull[j].point, &hull[k].point);

       /* Is the angle formed by ij and jk concave? */
       if (_cairo_slope_compare (&slope_ij, &slope_jk) >= 0) {
           if (i == k)
              return CAIRO_STATUS_SUCCESS;
           hull[j].discard = 1;
           j = i;
           i = _cairo_hull_prev_valid (hull, num_hull, j);
       } else {
           i = j;
           j = k;
           k = _cairo_hull_next_valid (hull, num_hull, j);
       }
    } while (j != 0);

    return CAIRO_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int _cairo_hull_next_valid ( cairo_hull_t hull,
int  num_hull,
int  index 
) [static]

Definition at line 134 of file cairo-hull.c.

{
    do {
       index = (index + 1) % num_hull;
    } while (hull[index].discard);

    return index;
}

Here is the caller graph for this function:

static int _cairo_hull_prev_valid ( cairo_hull_t hull,
int  num_hull,
int  index 
) [static]

Definition at line 123 of file cairo-hull.c.

{
    do {
       /* hull[0] is always valid, so don't test and wraparound */
       index--;
    } while (hull[index].discard);

    return index;
}

Here is the caller graph for this function:

static cairo_status_t _cairo_hull_to_pen ( cairo_hull_t hull,
cairo_pen_vertex_t vertices,
int num_vertices 
) [static]

Definition at line 175 of file cairo-hull.c.

{
    int i, j = 0;

    for (i = 0; i < *num_vertices; i++) {
       if (hull[i].discard)
           continue;
       vertices[j++].point = hull[i].point;
    }

    *num_vertices = j;

    return CAIRO_STATUS_SUCCESS;
}

Here is the caller graph for this function:

static int _cairo_hull_vertex_compare ( const void av,
const void bv 
) [static]

Definition at line 88 of file cairo-hull.c.

{
    cairo_hull_t *a = (cairo_hull_t *) av;
    cairo_hull_t *b = (cairo_hull_t *) bv;
    int ret;

    ret = _cairo_slope_compare (&a->slope, &b->slope);

    /* In the case of two vertices with identical slope from the
       extremal point discard the nearer point. */

    if (ret == 0) {
       cairo_fixed_48_16_t a_dist, b_dist;
       a_dist = ((cairo_fixed_48_16_t) a->slope.dx * a->slope.dx +
                (cairo_fixed_48_16_t) a->slope.dy * a->slope.dy);
       b_dist = ((cairo_fixed_48_16_t) b->slope.dx * b->slope.dx +
                (cairo_fixed_48_16_t) b->slope.dy * b->slope.dy);
       /*
        * Use the point's ids to ensure a total ordering.
        * a well-defined ordering, and avoid setting discard on
        * both points.          
        */
       if (a_dist < b_dist || (a_dist == b_dist && a->id < b->id)) {
           a->discard = 1;
           ret = -1;
       } else {
           b->discard = 1;
           ret = 1;
       }
    }

    return ret;
}

Here is the call graph for this function:

Here is the caller graph for this function: