w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

cairo-botor-scan-converter.c File Reference
#include "cairoint.h"
#include "cairo-error-private.h"
#include "cairo-list-inline.h"
#include "cairo-freelist-private.h"
#include "cairo-combsort-inline.h"
#include <setjmp.h>
Include dependency graph for cairo-botor-scan-converter.c:

Go to the source code of this file.

Classes

struct  _cairo_bo_intersect_ordinate
 
struct  _cairo_bo_intersect_point
 
struct  quorem
 
struct  run
 
struct  edge
 
struct  _event
 
struct  _start_event
 
struct  _queue_event
 
struct  _pqueue
 
struct  cell
 
struct  _sweep_line
 
struct  _sweep_line::coverage
 
struct  _sweep_line::event_queue
 

Macros

#define STEP_X   CAIRO_FIXED_ONE
 
#define STEP_Y   CAIRO_FIXED_ONE
 
#define UNROLL3(x)   x x x
 
#define STEP_XY   (2*STEP_X*STEP_Y) /* Unit area in the step. */
 
#define AREA_TO_ALPHA(c)   (((c)*255 + STEP_XY/2) / STEP_XY)
 
#define PQ_PARENT_INDEX(i)   ((i) >> 1)
 
#define PQ_FIRST_ENTRY   1
 
#define PQ_LEFT_CHILD_INDEX(i)   ((i) << 1)
 
#define L   _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
 
#define A   _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->line.p1.y)
 
#define B   _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->line.p1.y)
 

Typedefs

typedef struct _cairo_bo_intersect_ordinate cairo_bo_intersect_ordinate_t
 
typedef struct _cairo_bo_intersect_point cairo_bo_intersect_point_t
 
typedef struct edge edge_t
 
typedef struct _event event_t
 
typedef struct _start_event start_event_t
 
typedef struct _queue_event queue_event_t
 
typedef struct _pqueue pqueue_t
 
typedef struct _sweep_line sweep_line_t
 

Enumerations

enum  { START = 0x1 , STOP = 0x2 }
 
enum  event_type_t {
  EVENT_TYPE_STOP , EVENT_TYPE_INTERSECTION , EVENT_TYPE_START , EVENT_TYPE_STOP ,
  EVENT_TYPE_INTERSECTION , EVENT_TYPE_START , EVENT_TYPE_STOP , EVENT_TYPE_INTERSECTION ,
  EVENT_TYPE_START
}
 

Functions

static struct quorem floored_divrem (int a, int b)
 
static struct quorem floored_muldivrem (int x, int a, int b)
 
static cairo_fixed_t line_compute_intersection_x_for_y (const cairo_line_t *line, cairo_fixed_t y)
 
static int edges_compare_x_for_y_general (const cairo_edge_t *a, const cairo_edge_t *b, int32_t y)
 
static int edge_compare_for_y_against_x (const cairo_edge_t *a, int32_t y, int32_t x)
 
static int edges_compare_x_for_y (const cairo_edge_t *a, const cairo_edge_t *b, int32_t y)
 
static int slope_compare (const edge_t *a, const edge_t *b)
 
static int line_equal (const cairo_line_t *a, const cairo_line_t *b)
 
static int sweep_line_compare_edges (const edge_t *a, const edge_t *b, cairo_fixed_t y)
 
static cairo_int64_t det32_64 (int32_t a, int32_t b, int32_t c, int32_t d)
 
static cairo_int128_t det64x32_128 (cairo_int64_t a, int32_t b, cairo_int64_t c, int32_t d)
 
static cairo_bool_t intersect_lines (const edge_t *a, const edge_t *b, cairo_bo_intersect_point_t *intersection)
 
static int bo_intersect_ordinate_32_compare (int32_t a, int32_t b, int exactness)
 
static cairo_bool_t bo_edge_contains_intersect_point (const edge_t *edge, cairo_bo_intersect_point_t *point)
 
static cairo_bool_t edge_intersect (const edge_t *a, const edge_t *b, cairo_point_t *intersection)
 
static int event_compare (const event_t *a, const event_t *b)
 
static void pqueue_init (pqueue_t *pq)
 
static void pqueue_fini (pqueue_t *pq)
 
static cairo_bool_t pqueue_grow (pqueue_t *pq)
 
static void pqueue_push (sweep_line_t *sweep_line, event_t *event)
 
static void pqueue_pop (pqueue_t *pq)
 
static void event_insert (sweep_line_t *sweep_line, event_type_t type, edge_t *e1, edge_t *e2, cairo_fixed_t y)
 
static void event_delete (sweep_line_t *sweep_line, event_t *event)
 
static event_tevent_next (sweep_line_t *sweep_line)
 
static void start_event_sort (event_t **base, unsigned int nmemb)
 
static void event_insert_stop (sweep_line_t *sweep_line, edge_t *edge)
 
static void event_insert_if_intersect_below_current_y (sweep_line_t *sweep_line, edge_t *left, edge_t *right)
 
static edge_tlink_to_edge (cairo_list_t *link)
 
static void sweep_line_insert (sweep_line_t *sweep_line, edge_t *edge)
 
static void coverage_rewind (struct coverage *cells)
 
static void coverage_init (struct coverage *cells)
 
static void coverage_fini (struct coverage *cells)
 
static void coverage_reset (struct coverage *cells)
 
static struct cellcoverage_alloc (sweep_line_t *sweep_line, struct cell *tail, int x)
 
static struct cellcoverage_find (sweep_line_t *sweep_line, int x)
 
static void coverage_render_cells (sweep_line_t *sweep_line, cairo_fixed_t left, cairo_fixed_t right, cairo_fixed_t y1, cairo_fixed_t y2, int sign)
 
static void full_inc_edge (edge_t *edge)
 
static void full_add_edge (sweep_line_t *sweep_line, edge_t *edge, int sign)
 
static void full_nonzero (sweep_line_t *sweep_line)
 
static void full_evenodd (sweep_line_t *sweep_line)
 
static void render_rows (cairo_botor_scan_converter_t *self, sweep_line_t *sweep_line, int y, int height, cairo_span_renderer_t *renderer)
 
static void full_repeat (sweep_line_t *sweep)
 
static void full_reset (sweep_line_t *sweep)
 
static void full_step (cairo_botor_scan_converter_t *self, sweep_line_t *sweep_line, cairo_fixed_t row, cairo_span_renderer_t *renderer)
 
static void sub_inc_edge (edge_t *edge, cairo_fixed_t height)
 
static void sub_add_run (sweep_line_t *sweep_line, edge_t *edge, int y, int sign)
 
static cairo_bool_t edges_coincident (edge_t *left, edge_t *right, cairo_fixed_t y)
 
static void sub_nonzero (sweep_line_t *sweep_line)
 
static void sub_evenodd (sweep_line_t *sweep_line)
 
static void sub_step (cairo_botor_scan_converter_t *self, sweep_line_t *sweep_line)
 
static void coverage_render_runs (sweep_line_t *sweep, edge_t *edge, cairo_fixed_t y1, cairo_fixed_t y2)
 
static void coverage_render_vertical_runs (sweep_line_t *sweep, edge_t *edge, cairo_fixed_t y2)
 
static void sub_emit (cairo_botor_scan_converter_t *self, sweep_line_t *sweep, cairo_span_renderer_t *renderer)
 
static void sweep_line_init (sweep_line_t *sweep_line, event_t **start_events, int num_events)
 
static void sweep_line_delete (sweep_line_t *sweep_line, edge_t *edge)
 
static void sweep_line_swap (sweep_line_t *sweep_line, edge_t *left, edge_t *right)
 
static void sweep_line_fini (sweep_line_t *sweep_line)
 
static cairo_status_t botor_generate (cairo_botor_scan_converter_t *self, event_t **start_events, cairo_span_renderer_t *renderer)
 
static cairo_status_t _cairo_botor_scan_converter_generate (void *converter, cairo_span_renderer_t *renderer)
 
static edge_tbotor_allocate_edge (cairo_botor_scan_converter_t *self)
 
static cairo_status_t botor_add_edge (cairo_botor_scan_converter_t *self, const cairo_edge_t *edge)
 
cairo_status_t _cairo_botor_scan_converter_add_polygon (cairo_botor_scan_converter_t *converter, const cairo_polygon_t *polygon)
 
static void _cairo_botor_scan_converter_destroy (void *converter)
 
void _cairo_botor_scan_converter_init (cairo_botor_scan_converter_t *self, const cairo_box_t *extents, cairo_fill_rule_t fill_rule)
 

Macro Definition Documentation

◆ A

◆ AREA_TO_ALPHA

#define AREA_TO_ALPHA (   c)    (((c)*255 + STEP_XY/2) / STEP_XY)

Definition at line 57 of file cairo-botor-scan-converter.c.

◆ B

Definition at line 249 of file gensi.hpp.

Referenced by edges_compare_x_for_y_general().

◆ L

◆ PQ_FIRST_ENTRY

#define PQ_FIRST_ENTRY   1

Definition at line 109 of file cairo-botor-scan-converter.c.

◆ PQ_LEFT_CHILD_INDEX

#define PQ_LEFT_CHILD_INDEX (   i)    ((i) << 1)

Definition at line 112 of file cairo-botor-scan-converter.c.

◆ PQ_PARENT_INDEX

#define PQ_PARENT_INDEX (   i)    ((i) >> 1)

Definition at line 108 of file cairo-botor-scan-converter.c.

◆ STEP_X

#define STEP_X   CAIRO_FIXED_ONE

Definition at line 52 of file cairo-botor-scan-converter.c.

◆ STEP_XY

#define STEP_XY   (2*STEP_X*STEP_Y) /* Unit area in the step. */

Definition at line 56 of file cairo-botor-scan-converter.c.

◆ STEP_Y

#define STEP_Y   CAIRO_FIXED_ONE

Definition at line 53 of file cairo-botor-scan-converter.c.

◆ UNROLL3

#define UNROLL3 (   x)    x x x

Definition at line 54 of file cairo-botor-scan-converter.c.

Typedef Documentation

◆ cairo_bo_intersect_ordinate_t

◆ cairo_bo_intersect_point_t

◆ edge_t

typedef struct edge edge_t

◆ event_t

typedef struct _event event_t

◆ pqueue_t

typedef struct _pqueue pqueue_t

◆ queue_event_t

typedef struct _queue_event queue_event_t

◆ start_event_t

typedef struct _start_event start_event_t

◆ sweep_line_t

typedef struct _sweep_line sweep_line_t

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
START 
STOP 

Definition at line 102 of file cairo-botor-scan-converter.c.

◆ event_type_t

Enumerator
EVENT_TYPE_STOP 
EVENT_TYPE_INTERSECTION 
EVENT_TYPE_START 
EVENT_TYPE_STOP 
EVENT_TYPE_INTERSECTION 
EVENT_TYPE_START 
EVENT_TYPE_STOP 
EVENT_TYPE_INTERSECTION 
EVENT_TYPE_START 

Definition at line 114 of file cairo-botor-scan-converter.c.

Function Documentation

◆ _cairo_botor_scan_converter_add_polygon()

cairo_status_t _cairo_botor_scan_converter_add_polygon ( cairo_botor_scan_converter_t converter,
const cairo_polygon_t polygon 
)

◆ _cairo_botor_scan_converter_destroy()

static void _cairo_botor_scan_converter_destroy ( void converter)
static

Definition at line 2170 of file cairo-botor-scan-converter.c.

References chunk(), free, chunk::next, next, and NULL.

Referenced by _cairo_botor_scan_converter_init().

◆ _cairo_botor_scan_converter_generate()

◆ _cairo_botor_scan_converter_init()

◆ bo_edge_contains_intersect_point()

◆ bo_intersect_ordinate_32_compare()

static int bo_intersect_ordinate_32_compare ( int32_t  a,
int32_t  b,
int  exactness 
)
static

Definition at line 677 of file cairo-botor-scan-converter.c.

References a, b, and cmp().

Referenced by bo_edge_contains_intersect_point().

◆ botor_add_edge()

◆ botor_allocate_edge()

static edge_t* botor_allocate_edge ( cairo_botor_scan_converter_t self)
static

Definition at line 2049 of file cairo-botor-scan-converter.c.

References _cairo_malloc_ab_plus_c, chunk(), chunk::next, NULL, size, and unlikely.

Referenced by botor_add_edge().

◆ botor_generate()

◆ coverage_alloc()

◆ coverage_find()

◆ coverage_fini()

static void coverage_fini ( struct coverage cells)
static

Definition at line 1060 of file cairo-botor-scan-converter.c.

References _cairo_freepool_fini().

Referenced by sweep_line_fini().

◆ coverage_init()

static void coverage_init ( struct coverage cells)
static

◆ coverage_render_cells()

◆ coverage_render_runs()

◆ coverage_render_vertical_runs()

◆ coverage_reset()

static void coverage_reset ( struct coverage cells)
inlinestatic

Definition at line 1066 of file cairo-botor-scan-converter.c.

References _cairo_freepool_reset(), and coverage_rewind().

Referenced by render_rows().

◆ coverage_rewind()

static void coverage_rewind ( struct coverage cells)
inlinestatic

Definition at line 1039 of file cairo-botor-scan-converter.c.

Referenced by coverage_init(), and coverage_reset().

◆ det32_64()

static cairo_int64_t det32_64 ( int32_t  a,
int32_t  b,
int32_t  c,
int32_t  d 
)
inlinestatic

Definition at line 536 of file cairo-botor-scan-converter.c.

References _cairo_int32x32_64_mul(), _cairo_int64_sub, a, b, c, and d.

Referenced by intersect_lines().

◆ det64x32_128()

static cairo_int128_t det64x32_128 ( cairo_int64_t  a,
int32_t  b,
cairo_int64_t  c,
int32_t  d 
)
inlinestatic

Definition at line 545 of file cairo-botor-scan-converter.c.

References _cairo_int128_sub, _cairo_int64x32_128_mul, a, b, c, and d.

Referenced by intersect_lines().

◆ edge_compare_for_y_against_x()

static int edge_compare_for_y_against_x ( const cairo_edge_t a,
int32_t  y,
int32_t  x 
)
static

Definition at line 406 of file cairo-botor-scan-converter.c.

References _cairo_int32x32_64_mul(), _cairo_int64_cmp(), a, L, R, cordic::x, and y.

Referenced by edges_compare_x_for_y().

◆ edge_intersect()

static cairo_bool_t edge_intersect ( const edge_t a,
const edge_t b,
cairo_point_t intersection 
)
static

◆ edges_coincident()

static cairo_bool_t edges_coincident ( edge_t left,
edge_t right,
cairo_fixed_t  y 
)
inlinestatic

Definition at line 1542 of file cairo-botor-scan-converter.c.

References line_equal(), and right.

Referenced by sub_evenodd(), and sub_nonzero().

◆ edges_compare_x_for_y()

static int edges_compare_x_for_y ( const cairo_edge_t a,
const cairo_edge_t b,
int32_t  y 
)
static

◆ edges_compare_x_for_y_general()

static int edges_compare_x_for_y_general ( const cairo_edge_t a,
const cairo_edge_t b,
int32_t  y 
)
static

◆ event_compare()

static int event_compare ( const event_t a,
const event_t b 
)
inlinestatic

Definition at line 794 of file cairo-botor-scan-converter.c.

References a, and b.

Referenced by event_next(), pqueue_pop(), and pqueue_push().

◆ event_delete()

static void event_delete ( sweep_line_t sweep_line,
event_t event 
)
static

Definition at line 923 of file cairo-botor-scan-converter.c.

References _cairo_freepool_free().

Referenced by botor_generate().

◆ event_insert()

static void event_insert ( sweep_line_t sweep_line,
event_type_t  type,
edge_t e1,
edge_t e2,
cairo_fixed_t  y 
)
inlinestatic

◆ event_insert_if_intersect_below_current_y()

static void event_insert_if_intersect_below_current_y ( sweep_line_t sweep_line,
edge_t left,
edge_t right 
)
inlinestatic

◆ event_insert_stop()

static void event_insert_stop ( sweep_line_t sweep_line,
edge_t edge 
)
inlinestatic

◆ event_next()

static event_t* event_next ( sweep_line_t sweep_line)
inlinestatic

Definition at line 930 of file cairo-botor-scan-converter.c.

References cmp(), event_compare(), NULL, PQ_FIRST_ENTRY, and pqueue_pop().

Referenced by botor_generate().

◆ floored_divrem()

static struct quorem floored_divrem ( int  a,
int  b 
)
inlinestatic

Definition at line 1 of file cairo-botor-scan-converter.c.

Referenced by botor_add_edge(), and coverage_render_cells().

◆ floored_muldivrem()

static struct quorem floored_muldivrem ( int  x,
int  a,
int  b 
)
static

Definition at line 1 of file cairo-botor-scan-converter.c.

Referenced by botor_add_edge().

◆ full_add_edge()

◆ full_evenodd()

static void full_evenodd ( sweep_line_t sweep_line)
static

Definition at line 1318 of file cairo-botor-scan-converter.c.

References full_add_edge(), full_inc_edge(), link_to_edge(), pos, right, TRUE, and cordic::x.

Referenced by full_step().

◆ full_inc_edge()

static void full_inc_edge ( edge_t edge)
inlinestatic

◆ full_nonzero()

static void full_nonzero ( sweep_line_t sweep_line)
static

Definition at line 1276 of file cairo-botor-scan-converter.c.

References full_add_edge(), full_inc_edge(), link_to_edge(), pos, right, TRUE, unlikely, and cordic::x.

Referenced by full_step().

◆ full_repeat()

static void full_repeat ( sweep_line_t sweep)
static

◆ full_reset()

static void full_reset ( sweep_line_t sweep)
static

Definition at line 1454 of file cairo-botor-scan-converter.c.

References cairo_list_foreach_entry, and edge::current_sign.

Referenced by full_step().

◆ full_step()

◆ intersect_lines()

◆ line_compute_intersection_x_for_y()

static cairo_fixed_t line_compute_intersection_x_for_y ( const cairo_line_t line,
cairo_fixed_t  y 
)
static

◆ line_equal()

static int line_equal ( const cairo_line_t a,
const cairo_line_t b 
)
inlinestatic

Definition at line 512 of file cairo-botor-scan-converter.c.

References a, and b.

Referenced by edges_coincident(), and sweep_line_compare_edges().

◆ link_to_edge()

static edge_t* link_to_edge ( cairo_list_t link)
inlinestatic

◆ pqueue_fini()

static void pqueue_fini ( pqueue_t pq)
static

Definition at line 809 of file cairo-botor-scan-converter.c.

References _pqueue::elements, _pqueue::elements_embedded, and free.

Referenced by sweep_line_fini().

◆ pqueue_grow()

◆ pqueue_init()

static void pqueue_init ( pqueue_t pq)
static

◆ pqueue_pop()

static void pqueue_pop ( pqueue_t pq)
inlinestatic

◆ pqueue_push()

static void pqueue_push ( sweep_line_t sweep_line,
event_t event 
)
inlinestatic

◆ render_rows()

◆ slope_compare()

static int slope_compare ( const edge_t a,
const edge_t b 
)
inlinestatic

◆ start_event_sort()

static void start_event_sort ( event_t **  base,
unsigned int  nmemb 
)
static

Definition at line 950 of file cairo-botor-scan-converter.c.

Referenced by sweep_line_init().

◆ sub_add_run()

static void sub_add_run ( sweep_line_t sweep_line,
edge_t edge,
int  y,
int  sign 
)
static

◆ sub_emit()

◆ sub_evenodd()

static void sub_evenodd ( sweep_line_t sweep_line)
static

◆ sub_inc_edge()

static void sub_inc_edge ( edge_t edge,
cairo_fixed_t  height 
)
inlinestatic

Definition at line 1503 of file cairo-botor-scan-converter.c.

References edge::dxdy, edge::dy, height, quorem::quo, quorem::rem, and edge::x.

Referenced by coverage_render_runs(), and sub_emit().

◆ sub_nonzero()

static void sub_nonzero ( sweep_line_t sweep_line)
static

◆ sub_step()

static void sub_step ( cairo_botor_scan_converter_t self,
sweep_line_t sweep_line 
)
inlinestatic

◆ sweep_line_compare_edges()

static int sweep_line_compare_edges ( const edge_t a,
const edge_t b,
cairo_fixed_t  y 
)
inlinestatic

Definition at line 519 of file cairo-botor-scan-converter.c.

References a, b, cmp(), edges_compare_x_for_y(), line_equal(), slope_compare(), and y.

Referenced by sweep_line_insert().

◆ sweep_line_delete()

static void sweep_line_delete ( sweep_line_t sweep_line,
edge_t edge 
)
static

◆ sweep_line_fini()

static void sweep_line_fini ( sweep_line_t sweep_line)
static

◆ sweep_line_init()

static void sweep_line_init ( sweep_line_t sweep_line,
event_t **  start_events,
int  num_events 
)
static

◆ sweep_line_insert()

static void sweep_line_insert ( sweep_line_t sweep_line,
edge_t edge 
)
static

◆ sweep_line_swap()

static void sweep_line_swap ( sweep_line_t sweep_line,
edge_t left,
edge_t right 
)
static

Definition at line 1823 of file cairo-botor-scan-converter.c.

References right.

Referenced by botor_generate().