WebSVN – Kolibri OS – Blame – /programs/develop/libraries/cairo/src/cairo-bentley-ottmann.c

Rev	Author	Line No.	Line
1892	serge	1	/*
		2	* Copyright © 2004 Carl Worth
		3	* Copyright © 2006 Red Hat, Inc.
		4	* Copyright © 2008 Chris Wilson
		5	*
		6	* This library is free software; you can redistribute it and/or
		7	* modify it either under the terms of the GNU Lesser General Public
		8	* License version 2.1 as published by the Free Software Foundation
		9	* (the "LGPL") or, at your option, under the terms of the Mozilla
		10	* Public License Version 1.1 (the "MPL"). If you do not alter this
		11	* notice, a recipient may use your version of this file under either
		12	* the MPL or the LGPL.
		13	*
		14	* You should have received a copy of the LGPL along with this library
		15	* in the file COPYING-LGPL-2.1; if not, write to the Free Software
		16	* Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
		17	* You should have received a copy of the MPL along with this library
		18	* in the file COPYING-MPL-1.1
		19	*
		20	* The contents of this file are subject to the Mozilla Public License
		21	* Version 1.1 (the "License"); you may not use this file except in
		22	* compliance with the License. You may obtain a copy of the License at
		23	* http://www.mozilla.org/MPL/
		24	*
		25	* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
		26	* OF ANY KIND, either express or implied. See the LGPL or the MPL for
		27	* the specific language governing rights and limitations.
		28	*
		29	* The Original Code is the cairo graphics library.
		30	*
		31	* The Initial Developer of the Original Code is Carl Worth
		32	*
		33	* Contributor(s):
		34	* Carl D. Worth
		35	* Chris Wilson
		36	*/
		37
		38	/* Provide definitions for standalone compilation */
		39	#include "cairoint.h"
		40
		41	#include "cairo-error-private.h"
		42	#include "cairo-freelist-private.h"
		43	#include "cairo-combsort-private.h"
		44
		45	#define DEBUG_PRINT_STATE 0
		46	#define DEBUG_EVENTS 0
		47	#define DEBUG_TRAPS 0
		48
		49	typedef cairo_point_t cairo_bo_point32_t;
		50
		51	typedef struct _cairo_bo_intersect_ordinate {
		52	int32_t ordinate;
		53	enum { EXACT, INEXACT } exactness;
		54	} cairo_bo_intersect_ordinate_t;
		55
		56	typedef struct _cairo_bo_intersect_point {
		57	cairo_bo_intersect_ordinate_t x;
		58	cairo_bo_intersect_ordinate_t y;
		59	} cairo_bo_intersect_point_t;
		60
		61	typedef struct _cairo_bo_edge cairo_bo_edge_t;
		62	typedef struct _cairo_bo_trap cairo_bo_trap_t;
		63
		64	/* A deferred trapezoid of an edge */
		65	struct _cairo_bo_trap {
		66	cairo_bo_edge_t *right;
		67	int32_t top;
		68	};
		69
		70	struct _cairo_bo_edge {
		71	cairo_edge_t edge;
		72	cairo_bo_edge_t *prev;
		73	cairo_bo_edge_t *next;
		74	cairo_bo_trap_t deferred_trap;
		75	};
		76
		77	/* the parent is always given by index/2 */
		78	#define PQ_PARENT_INDEX(i) ((i) >> 1)
		79	#define PQ_FIRST_ENTRY 1
		80
		81	/* left and right children are index * 2 and (index * 2) +1 respectively */
		82	#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
		83
		84	typedef enum {
		85	CAIRO_BO_EVENT_TYPE_STOP,
		86	CAIRO_BO_EVENT_TYPE_INTERSECTION,
		87	CAIRO_BO_EVENT_TYPE_START
		88	} cairo_bo_event_type_t;
		89
		90	typedef struct _cairo_bo_event {
		91	cairo_bo_event_type_t type;
		92	cairo_point_t point;
		93	} cairo_bo_event_t;
		94
		95	typedef struct _cairo_bo_start_event {
		96	cairo_bo_event_type_t type;
		97	cairo_point_t point;
		98	cairo_bo_edge_t edge;
		99	} cairo_bo_start_event_t;
		100
		101	typedef struct _cairo_bo_queue_event {
		102	cairo_bo_event_type_t type;
		103	cairo_point_t point;
		104	cairo_bo_edge_t *e1;
		105	cairo_bo_edge_t *e2;
		106	} cairo_bo_queue_event_t;
		107
		108	typedef struct _pqueue {
		109	int size, max_size;
		110
		111	cairo_bo_event_t **elements;
		112	cairo_bo_event_t *elements_embedded[1024];
		113	} pqueue_t;
		114
		115	typedef struct _cairo_bo_event_queue {
		116	cairo_freepool_t pool;
		117	pqueue_t pqueue;
		118	cairo_bo_event_t **start_events;
		119	} cairo_bo_event_queue_t;
		120
		121	typedef struct _cairo_bo_sweep_line {
		122	cairo_bo_edge_t *head;
		123	cairo_bo_edge_t *stopped;
		124	int32_t current_y;
		125	cairo_bo_edge_t *current_edge;
		126	} cairo_bo_sweep_line_t;
		127
		128	#if DEBUG_TRAPS
		129	static void
		130	dump_traps (cairo_traps_t traps, const char filename)
		131	{
		132	FILE *file;
		133	cairo_box_t extents;
		134	int n;
		135
		136	if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
		137	return;
		138
		139	#if 0
		140	if (traps->has_limits) {
		141	printf ("%s: limits=(%d, %d, %d, %d)\n",
		142	filename,
		143	traps->limits.p1.x, traps->limits.p1.y,
		144	traps->limits.p2.x, traps->limits.p2.y);
		145	}
		146	#endif
		147	_cairo_traps_extents (traps, &extents);
		148	printf ("%s: extents=(%d, %d, %d, %d)\n",
		149	filename,
		150	extents.p1.x, extents.p1.y,
		151	extents.p2.x, extents.p2.y);
		152
		153	file = fopen (filename, "a");
		154	if (file != NULL) {
		155	for (n = 0; n < traps->num_traps; n++) {
		156	fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
		157	traps->traps[n].top,
		158	traps->traps[n].bottom,
		159	traps->traps[n].left.p1.x,
		160	traps->traps[n].left.p1.y,
		161	traps->traps[n].left.p2.x,
		162	traps->traps[n].left.p2.y,
		163	traps->traps[n].right.p1.x,
		164	traps->traps[n].right.p1.y,
		165	traps->traps[n].right.p2.x,
		166	traps->traps[n].right.p2.y);
		167	}
		168	fprintf (file, "\n");
		169	fclose (file);
		170	}
		171	}
		172
		173	static void
		174	dump_edges (cairo_bo_start_event_t *events,
		175	int num_edges,
		176	const char *filename)
		177	{
		178	FILE *file;
		179	int n;
		180
		181	if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
		182	return;
		183
		184	file = fopen (filename, "a");
		185	if (file != NULL) {
		186	for (n = 0; n < num_edges; n++) {
		187	fprintf (file, "(%d, %d), (%d, %d) %d %d %d\n",
		188	events[n].edge.edge.line.p1.x,
		189	events[n].edge.edge.line.p1.y,
		190	events[n].edge.edge.line.p2.x,
		191	events[n].edge.edge.line.p2.y,
		192	events[n].edge.edge.top,
		193	events[n].edge.edge.bottom,
		194	events[n].edge.edge.dir);
		195	}
		196	fprintf (file, "\n");
		197	fclose (file);
		198	}
		199	}
		200	#endif
		201
		202	static cairo_fixed_t
		203	_line_compute_intersection_x_for_y (const cairo_line_t *line,
		204	cairo_fixed_t y)
		205	{
		206	cairo_fixed_t x, dy;
		207
		208	if (y == line->p1.y)
		209	return line->p1.x;
		210	if (y == line->p2.y)
		211	return line->p2.x;
		212
		213	x = line->p1.x;
		214	dy = line->p2.y - line->p1.y;
		215	if (dy != 0) {
		216	x += _cairo_fixed_mul_div_floor (y - line->p1.y,
		217	line->p2.x - line->p1.x,
		218	dy);
		219	}
		220
		221	return x;
		222	}
		223
		224	static inline int
		225	_cairo_bo_point32_compare (cairo_bo_point32_t const *a,
		226	cairo_bo_point32_t const *b)
		227	{
		228	int cmp;
		229
		230	cmp = a->y - b->y;
		231	if (cmp)
		232	return cmp;
		233
		234	return a->x - b->x;
		235	}
		236
		237	/* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
		238	* slope a is respectively greater than, equal to, or less than the
		239	* slope of b.
		240	*
		241	* For each edge, consider the direction vector formed from:
		242	*
		243	* top -> bottom
		244	*
		245	* which is:
		246	*
		247	* (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
		248	*
		249	* We then define the slope of each edge as dx/dy, (which is the
		250	* inverse of the slope typically used in math instruction). We never
		251	* compute a slope directly as the value approaches infinity, but we
		252	* can derive a slope comparison without division as follows, (where
		253	* the ? represents our compare operator).
		254	*
		255	* 1. slope(a) ? slope(b)
		256	* 2. adx/ady ? bdx/bdy
		257	* 3. (adx * bdy) ? (bdx * ady)
		258	*
		259	* Note that from step 2 to step 3 there is no change needed in the
		260	* sign of the result since both ady and bdy are guaranteed to be
		261	* greater than or equal to 0.
		262	*
		263	* When using this slope comparison to sort edges, some care is needed
		264	* when interpreting the results. Since the slope compare operates on
		265	* distance vectors from top to bottom it gives a correct left to
		266	* right sort for edges that have a common top point, (such as two
		267	* edges with start events at the same location). On the other hand,
		268	* the sense of the result will be exactly reversed for two edges that
		269	* have a common stop point.
		270	*/
		271	static inline int
		272	_slope_compare (const cairo_bo_edge_t *a,
		273	const cairo_bo_edge_t *b)
		274	{
		275	/* XXX: We're assuming here that dx and dy will still fit in 32
		276	* bits. That's not true in general as there could be overflow. We
		277	* should prevent that before the tessellation algorithm
		278	* begins.
		279	*/
		280	int32_t adx = a->edge.line.p2.x - a->edge.line.p1.x;
		281	int32_t bdx = b->edge.line.p2.x - b->edge.line.p1.x;
		282
		283	/* Since the dy's are all positive by construction we can fast
		284	* path several common cases.
		285	*/
		286
		287	/* First check for vertical lines. */
		288	if (adx == 0)
		289	return -bdx;
		290	if (bdx == 0)
		291	return adx;
		292
		293	/* Then where the two edges point in different directions wrt x. */
		294	if ((adx ^ bdx) < 0)
		295	return adx;
		296
		297	/* Finally we actually need to do the general comparison. */
		298	{
		299	int32_t ady = a->edge.line.p2.y - a->edge.line.p1.y;
		300	int32_t bdy = b->edge.line.p2.y - b->edge.line.p1.y;
		301	cairo_int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
		302	cairo_int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
		303
		304	return _cairo_int64_cmp (adx_bdy, bdx_ady);
		305	}
		306	}
		307
		308	/*
		309	* We need to compare the x-coordinates of a pair of lines for a particular y,
		310	* without loss of precision.
		311	*
		312	* The x-coordinate along an edge for a given y is:
		313	* X = A_x + (Y - A_y) * A_dx / A_dy
		314	*
		315	* So the inequality we wish to test is:
		316	* A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
		317	* where ∘ is our inequality operator.
		318	*
		319	* By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
		320	* all positive, so we can rearrange it thus without causing a sign change:
		321	* A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
		322	* - (Y - A_y) * A_dx * B_dy
		323	*
		324	* Given the assumption that all the deltas fit within 32 bits, we can compute
		325	* this comparison directly using 128 bit arithmetic. For certain, but common,
		326	* input we can reduce this down to a single 32 bit compare by inspecting the
		327	* deltas.
		328	*
		329	* (And put the burden of the work on developing fast 128 bit ops, which are
		330	* required throughout the tessellator.)
		331	*
		332	* See the similar discussion for _slope_compare().
		333	*/
		334	static int
		335	edges_compare_x_for_y_general (const cairo_bo_edge_t *a,
		336	const cairo_bo_edge_t *b,
		337	int32_t y)
		338	{
		339	/* XXX: We're assuming here that dx and dy will still fit in 32
		340	* bits. That's not true in general as there could be overflow. We
		341	* should prevent that before the tessellation algorithm
		342	* begins.
		343	*/
		344	int32_t dx;
		345	int32_t adx, ady;
		346	int32_t bdx, bdy;
		347	enum {
		348	HAVE_NONE = 0x0,
		349	HAVE_DX = 0x1,
		350	HAVE_ADX = 0x2,
		351	HAVE_DX_ADX = HAVE_DX \| HAVE_ADX,
		352	HAVE_BDX = 0x4,
		353	HAVE_DX_BDX = HAVE_DX \| HAVE_BDX,
		354	HAVE_ADX_BDX = HAVE_ADX \| HAVE_BDX,
		355	HAVE_ALL = HAVE_DX \| HAVE_ADX \| HAVE_BDX
		356	} have_dx_adx_bdx = HAVE_ALL;
		357
		358	/* don't bother solving for abscissa if the edges' bounding boxes
		359	* can be used to order them. */
		360	{
		361	int32_t amin, amax;
		362	int32_t bmin, bmax;
		363	if (a->edge.line.p1.x < a->edge.line.p2.x) {
		364	amin = a->edge.line.p1.x;
		365	amax = a->edge.line.p2.x;
		366	} else {
		367	amin = a->edge.line.p2.x;
		368	amax = a->edge.line.p1.x;
		369	}
		370	if (b->edge.line.p1.x < b->edge.line.p2.x) {
		371	bmin = b->edge.line.p1.x;
		372	bmax = b->edge.line.p2.x;
		373	} else {
		374	bmin = b->edge.line.p2.x;
		375	bmax = b->edge.line.p1.x;
		376	}
		377	if (amax < bmin) return -1;
		378	if (amin > bmax) return +1;
		379	}
		380
		381	ady = a->edge.line.p2.y - a->edge.line.p1.y;
		382	adx = a->edge.line.p2.x - a->edge.line.p1.x;
		383	if (adx == 0)
		384	have_dx_adx_bdx &= ~HAVE_ADX;
		385
		386	bdy = b->edge.line.p2.y - b->edge.line.p1.y;
		387	bdx = b->edge.line.p2.x - b->edge.line.p1.x;
		388	if (bdx == 0)
		389	have_dx_adx_bdx &= ~HAVE_BDX;
		390
		391	dx = a->edge.line.p1.x - b->edge.line.p1.x;
		392	if (dx == 0)
		393	have_dx_adx_bdx &= ~HAVE_DX;
		394
		395	#define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
		396	#define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y)
		397	#define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y)
		398	switch (have_dx_adx_bdx) {
		399	default:
		400	case HAVE_NONE:
		401	return 0;
		402	case HAVE_DX:
		403	/* A_dy * B_dy * (A_x - B_x) ∘ 0 */
		404	return dx; /* ady * bdy is positive definite */
		405	case HAVE_ADX:
		406	/* 0 ∘ - (Y - A_y) * A_dx * B_dy */
		407	return adx; /* bdy * (y - a->top.y) is positive definite */
		408	case HAVE_BDX:
		409	/* 0 ∘ (Y - B_y) * B_dx * A_dy */
		410	return -bdx; /* ady * (y - b->top.y) is positive definite */
		411	case HAVE_ADX_BDX:
		412	/* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
		413	if ((adx ^ bdx) < 0) {
		414	return adx;
		415	} else if (a->edge.line.p1.y == b->edge.line.p1.y) { /* common origin */
		416	cairo_int64_t adx_bdy, bdx_ady;
		417
		418	/* ∴ A_dx * B_dy ∘ B_dx * A_dy */
		419
		420	adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
		421	bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
		422
		423	return _cairo_int64_cmp (adx_bdy, bdx_ady);
		424	} else
		425	return _cairo_int128_cmp (A, B);
		426	case HAVE_DX_ADX:
		427	/* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
		428	if ((-adx ^ dx) < 0) {
		429	return dx;
		430	} else {
		431	cairo_int64_t ady_dx, dy_adx;
		432
		433	ady_dx = _cairo_int32x32_64_mul (ady, dx);
		434	dy_adx = _cairo_int32x32_64_mul (a->edge.line.p1.y - y, adx);
		435
		436	return _cairo_int64_cmp (ady_dx, dy_adx);
		437	}
		438	case HAVE_DX_BDX:
		439	/* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
		440	if ((bdx ^ dx) < 0) {
		441	return dx;
		442	} else {
		443	cairo_int64_t bdy_dx, dy_bdx;
		444
		445	bdy_dx = _cairo_int32x32_64_mul (bdy, dx);
		446	dy_bdx = _cairo_int32x32_64_mul (y - b->edge.line.p1.y, bdx);
		447
		448	return _cairo_int64_cmp (bdy_dx, dy_bdx);
		449	}
		450	case HAVE_ALL:
		451	/* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */
		452	return _cairo_int128_cmp (L, _cairo_int128_sub (B, A));
		453	}
		454	#undef B
		455	#undef A
		456	#undef L
		457	}
		458
		459	/*
		460	* We need to compare the x-coordinate of a line for a particular y wrt to a
		461	* given x, without loss of precision.
		462	*
		463	* The x-coordinate along an edge for a given y is:
		464	* X = A_x + (Y - A_y) * A_dx / A_dy
		465	*
		466	* So the inequality we wish to test is:
		467	* A_x + (Y - A_y) * A_dx / A_dy ∘ X
		468	* where ∘ is our inequality operator.
		469	*
		470	* By construction, we know that A_dy (and (Y - A_y)) are
		471	* all positive, so we can rearrange it thus without causing a sign change:
		472	* (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
		473	*
		474	* Given the assumption that all the deltas fit within 32 bits, we can compute
		475	* this comparison directly using 64 bit arithmetic.
		476	*
		477	* See the similar discussion for _slope_compare() and
		478	* edges_compare_x_for_y_general().
		479	*/
		480	static int
		481	edge_compare_for_y_against_x (const cairo_bo_edge_t *a,
		482	int32_t y,
		483	int32_t x)
		484	{
		485	int32_t adx, ady;
		486	int32_t dx, dy;
		487	cairo_int64_t L, R;
		488
		489	if (x < a->edge.line.p1.x && x < a->edge.line.p2.x)
		490	return 1;
		491	if (x > a->edge.line.p1.x && x > a->edge.line.p2.x)
		492	return -1;
		493
		494	adx = a->edge.line.p2.x - a->edge.line.p1.x;
		495	dx = x - a->edge.line.p1.x;
		496
		497	if (adx == 0)
		498	return -dx;
		499	if (dx == 0 \|\| (adx ^ dx) < 0)
		500	return adx;
		501
		502	dy = y - a->edge.line.p1.y;
		503	ady = a->edge.line.p2.y - a->edge.line.p1.y;
		504
		505	L = _cairo_int32x32_64_mul (dy, adx);
		506	R = _cairo_int32x32_64_mul (dx, ady);
		507
		508	return _cairo_int64_cmp (L, R);
		509	}
		510
		511	static int
		512	edges_compare_x_for_y (const cairo_bo_edge_t *a,
		513	const cairo_bo_edge_t *b,
		514	int32_t y)
		515	{
		516	/* If the sweep-line is currently on an end-point of a line,
		517	* then we know its precise x value (and considering that we often need to
		518	* compare events at end-points, this happens frequently enough to warrant
		519	* special casing).
		520	*/
		521	enum {
		522	HAVE_NEITHER = 0x0,
		523	HAVE_AX = 0x1,
		524	HAVE_BX = 0x2,
		525	HAVE_BOTH = HAVE_AX \| HAVE_BX
		526	} have_ax_bx = HAVE_BOTH;
		527	int32_t ax, bx;
		528
		529	if (y == a->edge.line.p1.y)
		530	ax = a->edge.line.p1.x;
		531	else if (y == a->edge.line.p2.y)
		532	ax = a->edge.line.p2.x;
		533	else
		534	have_ax_bx &= ~HAVE_AX;
		535
		536	if (y == b->edge.line.p1.y)
		537	bx = b->edge.line.p1.x;
		538	else if (y == b->edge.line.p2.y)
		539	bx = b->edge.line.p2.x;
		540	else
		541	have_ax_bx &= ~HAVE_BX;
		542
		543	switch (have_ax_bx) {
		544	default:
		545	case HAVE_NEITHER:
		546	return edges_compare_x_for_y_general (a, b, y);
		547	case HAVE_AX:
		548	return -edge_compare_for_y_against_x (b, y, ax);
		549	case HAVE_BX:
		550	return edge_compare_for_y_against_x (a, y, bx);
		551	case HAVE_BOTH:
		552	return ax - bx;
		553	}
		554	}
		555
		556	static inline int
		557	_line_equal (const cairo_line_t a, const cairo_line_t b)
		558	{
		559	return a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
		560	a->p2.x == b->p2.x && a->p2.y == b->p2.y;
		561	}
		562
		563	static int
		564	_cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line,
		565	const cairo_bo_edge_t *a,
		566	const cairo_bo_edge_t *b)
		567	{
		568	int cmp;
		569
		570	/* compare the edges if not identical */
		571	if (! _line_equal (&a->edge.line, &b->edge.line)) {
		572	cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
		573	if (cmp)
		574	return cmp;
		575
		576	/* The two edges intersect exactly at y, so fall back on slope
		577	* comparison. We know that this compare_edges function will be
		578	* called only when starting a new edge, (not when stopping an
		579	* edge), so we don't have to worry about conditionally inverting
		580	* the sense of _slope_compare. */
		581	cmp = _slope_compare (a, b);
		582	if (cmp)
		583	return cmp;
		584	}
		585
		586	/* We've got two collinear edges now. */
		587	return b->edge.bottom - a->edge.bottom;
		588	}
		589
		590	static inline cairo_int64_t
		591	det32_64 (int32_t a, int32_t b,
		592	int32_t c, int32_t d)
		593	{
		594	/* det = a * d - b * c */
		595	return _cairo_int64_sub (_cairo_int32x32_64_mul (a, d),
		596	_cairo_int32x32_64_mul (b, c));
		597	}
		598
		599	static inline cairo_int128_t
		600	det64x32_128 (cairo_int64_t a, int32_t b,
		601	cairo_int64_t c, int32_t d)
		602	{
		603	/* det = a * d - b * c */
		604	return _cairo_int128_sub (_cairo_int64x32_128_mul (a, d),
		605	_cairo_int64x32_128_mul (c, b));
		606	}
		607
		608	/* Compute the intersection of two lines as defined by two edges. The
		609	* result is provided as a coordinate pair of 128-bit integers.
		610	*
		611	* Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
		612	* %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
		613	*/
		614	static cairo_bool_t
		615	intersect_lines (cairo_bo_edge_t *a,
		616	cairo_bo_edge_t *b,
		617	cairo_bo_intersect_point_t *intersection)
		618	{
		619	cairo_int64_t a_det, b_det;
		620
		621	/* XXX: We're assuming here that dx and dy will still fit in 32
		622	* bits. That's not true in general as there could be overflow. We
		623	* should prevent that before the tessellation algorithm begins.
		624	* What we're doing to mitigate this is to perform clamping in
		625	* cairo_bo_tessellate_polygon().
		626	*/
		627	int32_t dx1 = a->edge.line.p1.x - a->edge.line.p2.x;
		628	int32_t dy1 = a->edge.line.p1.y - a->edge.line.p2.y;
		629
		630	int32_t dx2 = b->edge.line.p1.x - b->edge.line.p2.x;
		631	int32_t dy2 = b->edge.line.p1.y - b->edge.line.p2.y;
		632
		633	cairo_int64_t den_det;
		634	cairo_int64_t R;
		635	cairo_quorem64_t qr;
		636
		637	den_det = det32_64 (dx1, dy1, dx2, dy2);
		638
		639	/* Q: Can we determine that the lines do not intersect (within range)
		640	* much more cheaply than computing the intersection point i.e. by
		641	* avoiding the division?
		642	*
		643	* X = ax + t * adx = bx + s * bdx;
		644	* Y = ay + t * ady = by + s * bdy;
		645	* ∴ t * (adybdx - bdyadx) = bdx * (by - ay) + bdy * (ax - bx)
		646	* => t * L = R
		647	*
		648	* Therefore we can reject any intersection (under the criteria for
		649	* valid intersection events) if:
		650	* L^R < 0 => t < 0, or
		651	* L t > 1
		652	*
		653	* (where top/bottom must at least extend to the line endpoints).
		654	*
		655	* A similar substitution can be performed for s, yielding:
		656	* s * (adybdx - bdyadx) = ady * (ax - bx) - adx * (ay - by)
		657	*/
		658	R = det32_64 (dx2, dy2,
		659	b->edge.line.p1.x - a->edge.line.p1.x,
		660	b->edge.line.p1.y - a->edge.line.p1.y);
		661	if (_cairo_int64_negative (den_det)) {
		662	if (_cairo_int64_ge (den_det, R))
		663	return FALSE;
		664	} else {
		665	if (_cairo_int64_le (den_det, R))
		666	return FALSE;
		667	}
		668
		669	R = det32_64 (dy1, dx1,
		670	a->edge.line.p1.y - b->edge.line.p1.y,
		671	a->edge.line.p1.x - b->edge.line.p1.x);
		672	if (_cairo_int64_negative (den_det)) {
		673	if (_cairo_int64_ge (den_det, R))
		674	return FALSE;
		675	} else {
		676	if (_cairo_int64_le (den_det, R))
		677	return FALSE;
		678	}
		679
		680	/* We now know that the two lines should intersect within range. */
		681
		682	a_det = det32_64 (a->edge.line.p1.x, a->edge.line.p1.y,
		683	a->edge.line.p2.x, a->edge.line.p2.y);
		684	b_det = det32_64 (b->edge.line.p1.x, b->edge.line.p1.y,
		685	b->edge.line.p2.x, b->edge.line.p2.y);
		686
		687	/* x = det (a_det, dx1, b_det, dx2) / den_det */
		688	qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dx1,
		689	b_det, dx2),
		690	den_det);
		691	if (_cairo_int64_eq (qr.rem, den_det))
		692	return FALSE;
		693	#if 0
		694	intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
		695	#else
		696	intersection->x.exactness = EXACT;
		697	if (! _cairo_int64_is_zero (qr.rem)) {
		698	if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
		699	qr.rem = _cairo_int64_negate (qr.rem);
		700	qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
		701	if (_cairo_int64_ge (qr.rem, den_det)) {
		702	qr.quo = _cairo_int64_add (qr.quo,
		703	_cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
		704	} else
		705	intersection->x.exactness = INEXACT;
		706	}
		707	#endif
		708	intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo);
		709
		710	/* y = det (a_det, dy1, b_det, dy2) / den_det */
		711	qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dy1,
		712	b_det, dy2),
		713	den_det);
		714	if (_cairo_int64_eq (qr.rem, den_det))
		715	return FALSE;
		716	#if 0
		717	intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
		718	#else
		719	intersection->y.exactness = EXACT;
		720	if (! _cairo_int64_is_zero (qr.rem)) {
		721	if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
		722	qr.rem = _cairo_int64_negate (qr.rem);
		723	qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
		724	if (_cairo_int64_ge (qr.rem, den_det)) {
		725	qr.quo = _cairo_int64_add (qr.quo,
		726	_cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
		727	} else
		728	intersection->y.exactness = INEXACT;
		729	}
		730	#endif
		731	intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo);
		732
		733	return TRUE;
		734	}
		735
		736	static int
		737	_cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t a,
		738	int32_t b)
		739	{
		740	/* First compare the quotient */
		741	if (a.ordinate > b)
		742	return +1;
		743	if (a.ordinate < b)
		744	return -1;
		745	/* With quotient identical, if remainder is 0 then compare equal */
		746	/* Otherwise, the non-zero remainder makes a > b */
		747	return INEXACT == a.exactness;
		748	}
		749
		750	/* Does the given edge contain the given point. The point must already
		751	* be known to be contained within the line determined by the edge,
		752	* (most likely the point results from an intersection of this edge
		753	* with another).
		754	*
		755	* If we had exact arithmetic, then this function would simply be a
		756	* matter of examining whether the y value of the point lies within
		757	* the range of y values of the edge. But since intersection points
		758	* are not exact due to being rounded to the nearest integer within
		759	* the available precision, we must also examine the x value of the
		760	* point.
		761	*
		762	* The definition of "contains" here is that the given intersection
		763	* point will be seen by the sweep line after the start event for the
		764	* given edge and before the stop event for the edge. See the comments
		765	* in the implementation for more details.
		766	*/
		767	static cairo_bool_t
		768	_cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t *edge,
		769	cairo_bo_intersect_point_t *point)
		770	{
		771	int cmp_top, cmp_bottom;
		772
		773	/* XXX: When running the actual algorithm, we don't actually need to
		774	* compare against edge->top at all here, since any intersection above
		775	* top is eliminated early via a slope comparison. We're leaving these
		776	* here for now only for the sake of the quadratic-time intersection
		777	* finder which needs them.
		778	*/
		779
		780	cmp_top = _cairo_bo_intersect_ordinate_32_compare (point->y,
		781	edge->edge.top);
		782	cmp_bottom = _cairo_bo_intersect_ordinate_32_compare (point->y,
		783	edge->edge.bottom);
		784
		785	if (cmp_top < 0 \|\| cmp_bottom > 0)
		786	{
		787	return FALSE;
		788	}
		789
		790	if (cmp_top > 0 && cmp_bottom < 0)
		791	{
		792	return TRUE;
		793	}
		794
		795	/* At this stage, the point lies on the same y value as either
		796	* edge->top or edge->bottom, so we have to examine the x value in
		797	* order to properly determine containment. */
		798
		799	/* If the y value of the point is the same as the y value of the
		800	* top of the edge, then the x value of the point must be greater
		801	* to be considered as inside the edge. Similarly, if the y value
		802	* of the point is the same as the y value of the bottom of the
		803	* edge, then the x value of the point must be less to be
		804	* considered as inside. */
		805
		806	if (cmp_top == 0) {
		807	cairo_fixed_t top_x;
		808
		809	top_x = _line_compute_intersection_x_for_y (&edge->edge.line,
		810	edge->edge.top);
		811	return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) > 0;
		812	} else { /* cmp_bottom == 0 */
		813	cairo_fixed_t bot_x;
		814
		815	bot_x = _line_compute_intersection_x_for_y (&edge->edge.line,
		816	edge->edge.bottom);
		817	return _cairo_bo_intersect_ordinate_32_compare (point->x, bot_x) < 0;
		818	}
		819	}
		820
		821	/* Compute the intersection of two edges. The result is provided as a
		822	* coordinate pair of 128-bit integers.
		823	*
		824	* Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection
		825	* that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the
		826	* intersection of the lines defined by the edges occurs outside of
		827	* one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges
		828	* are exactly parallel.
		829	*
		830	* Note that when determining if a candidate intersection is "inside"
		831	* an edge, we consider both the infinitesimal shortening and the
		832	* infinitesimal tilt rules described by John Hobby. Specifically, if
		833	* the intersection is exactly the same as an edge point, it is
		834	* effectively outside (no intersection is returned). Also, if the
		835	* intersection point has the same
		836	*/
		837	static cairo_bool_t
		838	_cairo_bo_edge_intersect (cairo_bo_edge_t *a,
		839	cairo_bo_edge_t *b,
		840	cairo_bo_point32_t *intersection)
		841	{
		842	cairo_bo_intersect_point_t quorem;
		843
		844	if (! intersect_lines (a, b, &quorem))
		845	return FALSE;
		846
		847	if (! _cairo_bo_edge_contains_intersect_point (a, &quorem))
		848	return FALSE;
		849
		850	if (! _cairo_bo_edge_contains_intersect_point (b, &quorem))
		851	return FALSE;
		852
		853	/* Now that we've correctly compared the intersection point and
		854	* determined that it lies within the edge, then we know that we
		855	* no longer need any more bits of storage for the intersection
		856	* than we do for our edge coordinates. We also no longer need the
		857	* remainder from the division. */
		858	intersection->x = quorem.x.ordinate;
		859	intersection->y = quorem.y.ordinate;
		860
		861	return TRUE;
		862	}
		863
		864	static inline int
		865	cairo_bo_event_compare (const cairo_bo_event_t *a,
		866	const cairo_bo_event_t *b)
		867	{
		868	int cmp;
		869
		870	cmp = _cairo_bo_point32_compare (&a->point, &b->point);
		871	if (cmp)
		872	return cmp;
		873
		874	cmp = a->type - b->type;
		875	if (cmp)
		876	return cmp;
		877
		878	return a - b;
		879	}
		880
		881	static inline void
		882	_pqueue_init (pqueue_t *pq)
		883	{
		884	pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
		885	pq->size = 0;
		886
		887	pq->elements = pq->elements_embedded;
		888	}
		889
		890	static inline void
		891	_pqueue_fini (pqueue_t *pq)
		892	{
		893	if (pq->elements != pq->elements_embedded)
		894	free (pq->elements);
		895	}
		896
		897	static cairo_status_t
		898	_pqueue_grow (pqueue_t *pq)
		899	{
		900	cairo_bo_event_t **new_elements;
		901	pq->max_size *= 2;
		902
		903	if (pq->elements == pq->elements_embedded) {
		904	new_elements = _cairo_malloc_ab (pq->max_size,
		905	sizeof (cairo_bo_event_t *));
		906	if (unlikely (new_elements == NULL))
		907	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
		908
		909	memcpy (new_elements, pq->elements_embedded,
		910	sizeof (pq->elements_embedded));
		911	} else {
		912	new_elements = _cairo_realloc_ab (pq->elements,
		913	pq->max_size,
		914	sizeof (cairo_bo_event_t *));
		915	if (unlikely (new_elements == NULL))
		916	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
		917	}
		918
		919	pq->elements = new_elements;
		920	return CAIRO_STATUS_SUCCESS;
		921	}
		922
		923	static inline cairo_status_t
		924	_pqueue_push (pqueue_t pq, cairo_bo_event_t event)
		925	{
		926	cairo_bo_event_t **elements;
		927	int i, parent;
		928
		929	if (unlikely (pq->size + 1 == pq->max_size)) {
		930	cairo_status_t status;
		931
		932	status = _pqueue_grow (pq);
		933	if (unlikely (status))
		934	return status;
		935	}
		936
		937	elements = pq->elements;
		938
		939	for (i = ++pq->size;
		940	i != PQ_FIRST_ENTRY &&
		941	cairo_bo_event_compare (event,
		942	elements[parent = PQ_PARENT_INDEX (i)]) < 0;
		943	i = parent)
		944	{
		945	elements[i] = elements[parent];
		946	}
		947
		948	elements[i] = event;
		949
		950	return CAIRO_STATUS_SUCCESS;
		951	}
		952
		953	static inline void
		954	_pqueue_pop (pqueue_t *pq)
		955	{
		956	cairo_bo_event_t **elements = pq->elements;
		957	cairo_bo_event_t *tail;
		958	int child, i;
		959
		960	tail = elements[pq->size--];
		961	if (pq->size == 0) {
		962	elements[PQ_FIRST_ENTRY] = NULL;
		963	return;
		964	}
		965
		966	for (i = PQ_FIRST_ENTRY;
		967	(child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
		968	i = child)
		969	{
		970	if (child != pq->size &&
		971	cairo_bo_event_compare (elements[child+1],
		972	elements[child]) < 0)
		973	{
		974	child++;
		975	}
		976
		977	if (cairo_bo_event_compare (elements[child], tail) >= 0)
		978	break;
		979
		980	elements[i] = elements[child];
		981	}
		982	elements[i] = tail;
		983	}
		984
		985	static inline cairo_status_t
		986	_cairo_bo_event_queue_insert (cairo_bo_event_queue_t *queue,
		987	cairo_bo_event_type_t type,
		988	cairo_bo_edge_t *e1,
		989	cairo_bo_edge_t *e2,
		990	const cairo_point_t *point)
		991	{
		992	cairo_bo_queue_event_t *event;
		993
		994	event = _cairo_freepool_alloc (&queue->pool);
		995	if (unlikely (event == NULL))
		996	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
		997
		998	event->type = type;
		999	event->e1 = e1;
		1000	event->e2 = e2;
		1001	event->point = *point;
		1002
		1003	return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event);
		1004	}
		1005
		1006	static void
		1007	_cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
		1008	cairo_bo_event_t *event)
		1009	{
		1010	_cairo_freepool_free (&queue->pool, event);
		1011	}
		1012
		1013	static cairo_bo_event_t *
		1014	_cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
		1015	{
		1016	cairo_bo_event_t event, cmp;
		1017
		1018	event = event_queue->pqueue.elements[PQ_FIRST_ENTRY];
		1019	cmp = *event_queue->start_events;
		1020	if (event == NULL \|\|
		1021	(cmp != NULL && cairo_bo_event_compare (cmp, event) < 0))
		1022	{
		1023	event = cmp;
		1024	event_queue->start_events++;
		1025	}
		1026	else
		1027	{
		1028	_pqueue_pop (&event_queue->pqueue);
		1029	}
		1030
		1031	return event;
		1032	}
		1033
		1034	CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
		1035	cairo_bo_event_t *,
		1036	cairo_bo_event_compare)
		1037
		1038	static void
		1039	_cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
		1040	cairo_bo_event_t **start_events,
		1041	int num_events)
		1042	{
		1043	_cairo_bo_event_queue_sort (start_events, num_events);
		1044	start_events[num_events] = NULL;
		1045
		1046	event_queue->start_events = start_events;
		1047
		1048	_cairo_freepool_init (&event_queue->pool,
		1049	sizeof (cairo_bo_queue_event_t));
		1050	_pqueue_init (&event_queue->pqueue);
		1051	event_queue->pqueue.elements[PQ_FIRST_ENTRY] = NULL;
		1052	}
		1053
		1054	static cairo_status_t
		1055	_cairo_bo_event_queue_insert_stop (cairo_bo_event_queue_t *event_queue,
		1056	cairo_bo_edge_t *edge)
		1057	{
		1058	cairo_bo_point32_t point;
		1059
		1060	point.y = edge->edge.bottom;
		1061	point.x = _line_compute_intersection_x_for_y (&edge->edge.line,
		1062	point.y);
		1063	return _cairo_bo_event_queue_insert (event_queue,
		1064	CAIRO_BO_EVENT_TYPE_STOP,
		1065	edge, NULL,
		1066	&point);
		1067	}
		1068
		1069	static void
		1070	_cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
		1071	{
		1072	_pqueue_fini (&event_queue->pqueue);
		1073	_cairo_freepool_fini (&event_queue->pool);
		1074	}
		1075
		1076	static inline cairo_status_t
		1077	_cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t *event_queue,
		1078	cairo_bo_edge_t *left,
		1079	cairo_bo_edge_t *right)
		1080	{
		1081	cairo_bo_point32_t intersection;
		1082
		1083	if (_line_equal (&left->edge.line, &right->edge.line))
		1084	return CAIRO_STATUS_SUCCESS;
		1085
		1086	/* The names "left" and "right" here are correct descriptions of
		1087	* the order of the two edges within the active edge list. So if a
		1088	* slope comparison also puts left less than right, then we know
		1089	* that the intersection of these two segments has already
		1090	* occurred before the current sweep line position. */
		1091	if (_slope_compare (left, right) <= 0)
		1092	return CAIRO_STATUS_SUCCESS;
		1093
		1094	if (! _cairo_bo_edge_intersect (left, right, &intersection))
		1095	return CAIRO_STATUS_SUCCESS;
		1096
		1097	return _cairo_bo_event_queue_insert (event_queue,
		1098	CAIRO_BO_EVENT_TYPE_INTERSECTION,
		1099	left, right,
		1100	&intersection);
		1101	}
		1102
		1103	static void
		1104	_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
		1105	{
		1106	sweep_line->head = NULL;
		1107	sweep_line->stopped = NULL;
		1108	sweep_line->current_y = INT32_MIN;
		1109	sweep_line->current_edge = NULL;
		1110	}
		1111
		1112	static cairo_status_t
		1113	_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line,
		1114	cairo_bo_edge_t *edge)
		1115	{
		1116	if (sweep_line->current_edge != NULL) {
		1117	cairo_bo_edge_t prev, next;
		1118	int cmp;
		1119
		1120	cmp = _cairo_bo_sweep_line_compare_edges (sweep_line,
		1121	sweep_line->current_edge,
		1122	edge);
		1123	if (cmp < 0) {
		1124	prev = sweep_line->current_edge;
		1125	next = prev->next;
		1126	while (next != NULL &&
		1127	_cairo_bo_sweep_line_compare_edges (sweep_line,
		1128	next, edge) < 0)
		1129	{
		1130	prev = next, next = prev->next;
		1131	}
		1132
		1133	prev->next = edge;
		1134	edge->prev = prev;
		1135	edge->next = next;
		1136	if (next != NULL)
		1137	next->prev = edge;
		1138	} else if (cmp > 0) {
		1139	next = sweep_line->current_edge;
		1140	prev = next->prev;
		1141	while (prev != NULL &&
		1142	_cairo_bo_sweep_line_compare_edges (sweep_line,
		1143	prev, edge) > 0)
		1144	{
		1145	next = prev, prev = next->prev;
		1146	}
		1147
		1148	next->prev = edge;
		1149	edge->next = next;
		1150	edge->prev = prev;
		1151	if (prev != NULL)
		1152	prev->next = edge;
		1153	else
		1154	sweep_line->head = edge;
		1155	} else {
		1156	prev = sweep_line->current_edge;
		1157	edge->prev = prev;
		1158	edge->next = prev->next;
		1159	if (prev->next != NULL)
		1160	prev->next->prev = edge;
		1161	prev->next = edge;
		1162	}
		1163	} else {
		1164	sweep_line->head = edge;
		1165	}
		1166
		1167	sweep_line->current_edge = edge;
		1168
		1169	return CAIRO_STATUS_SUCCESS;
		1170	}
		1171
		1172	static void
		1173	_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t *sweep_line,
		1174	cairo_bo_edge_t *edge)
		1175	{
		1176	if (edge->prev != NULL)
		1177	edge->prev->next = edge->next;
		1178	else
		1179	sweep_line->head = edge->next;
		1180
		1181	if (edge->next != NULL)
		1182	edge->next->prev = edge->prev;
		1183
		1184	if (sweep_line->current_edge == edge)
		1185	sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
		1186	}
		1187
		1188	static void
		1189	_cairo_bo_sweep_line_swap (cairo_bo_sweep_line_t *sweep_line,
		1190	cairo_bo_edge_t *left,
		1191	cairo_bo_edge_t *right)
		1192	{
		1193	if (left->prev != NULL)
		1194	left->prev->next = right;
		1195	else
		1196	sweep_line->head = right;
		1197
		1198	if (right->next != NULL)
		1199	right->next->prev = left;
		1200
		1201	left->next = right->next;
		1202	right->next = left;
		1203
		1204	right->prev = left->prev;
		1205	left->prev = right;
		1206	}
		1207
		1208	#if DEBUG_PRINT_STATE
		1209	static void
		1210	_cairo_bo_edge_print (cairo_bo_edge_t *edge)
		1211	{
		1212	printf ("(0x%x, 0x%x)-(0x%x, 0x%x)",
		1213	edge->edge.line.p1.x, edge->edge.line.p1.y,
		1214	edge->edge.line.p2.x, edge->edge.line.p2.y);
		1215	}
		1216
		1217	static void
		1218	_cairo_bo_event_print (cairo_bo_event_t *event)
		1219	{
		1220	switch (event->type) {
		1221	case CAIRO_BO_EVENT_TYPE_START:
		1222	printf ("Start: ");
		1223	break;
		1224	case CAIRO_BO_EVENT_TYPE_STOP:
		1225	printf ("Stop: ");
		1226	break;
		1227	case CAIRO_BO_EVENT_TYPE_INTERSECTION:
		1228	printf ("Intersection: ");
		1229	break;
		1230	}
		1231	printf ("(%d, %d)\t", event->point.x, event->point.y);
		1232	_cairo_bo_edge_print (event->e1);
		1233	if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION) {
		1234	printf (" X ");
		1235	_cairo_bo_edge_print (event->e2);
		1236	}
		1237	printf ("\n");
		1238	}
		1239
		1240	static void
		1241	_cairo_bo_event_queue_print (cairo_bo_event_queue_t *event_queue)
		1242	{
		1243	/* XXX: fixme to print the start/stop array too. */
		1244	printf ("Event queue:\n");
		1245	}
		1246
		1247	static void
		1248	_cairo_bo_sweep_line_print (cairo_bo_sweep_line_t *sweep_line)
		1249	{
		1250	cairo_bool_t first = TRUE;
		1251	cairo_bo_edge_t *edge;
		1252
		1253	printf ("Sweep line from edge list: ");
		1254	first = TRUE;
		1255	for (edge = sweep_line->head;
		1256	edge;
		1257	edge = edge->next)
		1258	{
		1259	if (!first)
		1260	printf (", ");
		1261	_cairo_bo_edge_print (edge);
		1262	first = FALSE;
		1263	}
		1264	printf ("\n");
		1265	}
		1266
		1267	static void
		1268	print_state (const char *msg,
		1269	cairo_bo_event_t *event,
		1270	cairo_bo_event_queue_t *event_queue,
		1271	cairo_bo_sweep_line_t *sweep_line)
		1272	{
		1273	printf ("%s ", msg);
		1274	_cairo_bo_event_print (event);
		1275	_cairo_bo_event_queue_print (event_queue);
		1276	_cairo_bo_sweep_line_print (sweep_line);
		1277	printf ("\n");
		1278	}
		1279	#endif
		1280
		1281	#if DEBUG_EVENTS
		1282	static void CAIRO_PRINTF_FORMAT (1, 2)
		1283	event_log (const char *fmt, ...)
		1284	{
		1285	FILE *file;
		1286
		1287	if (getenv ("CAIRO_DEBUG_EVENTS") == NULL)
		1288	return;
		1289
		1290	file = fopen ("bo-events.txt", "a");
		1291	if (file != NULL) {
		1292	va_list ap;
		1293
		1294	va_start (ap, fmt);
		1295	vfprintf (file, fmt, ap);
		1296	va_end (ap);
		1297
		1298	fclose (file);
		1299	}
		1300	}
		1301	#endif
		1302
		1303	static inline cairo_bool_t
		1304	edges_colinear (const cairo_bo_edge_t a, const cairo_bo_edge_t b)
		1305	{
		1306	if (_line_equal (&a->edge.line, &b->edge.line))
		1307	return TRUE;
		1308
		1309	if (_slope_compare (a, b))
		1310	return FALSE;
		1311
		1312	/* The choice of y is not truly arbitrary since we must guarantee that it
		1313	* is greater than the start of either line.
		1314	*/
		1315	if (a->edge.line.p1.y == b->edge.line.p1.y) {
		1316	return a->edge.line.p1.x == b->edge.line.p1.x;
		1317	} else if (a->edge.line.p1.y < b->edge.line.p1.y) {
		1318	return edge_compare_for_y_against_x (b,
		1319	a->edge.line.p1.y,
		1320	a->edge.line.p1.x) == 0;
		1321	} else {
		1322	return edge_compare_for_y_against_x (a,
		1323	b->edge.line.p1.y,
		1324	b->edge.line.p1.x) == 0;
		1325	}
		1326	}
		1327
		1328	/* Adds the trapezoid, if any, of the left edge to the #cairo_traps_t */
		1329	static cairo_status_t
		1330	_cairo_bo_edge_end_trap (cairo_bo_edge_t *left,
		1331	int32_t bot,
		1332	cairo_traps_t *traps)
		1333	{
		1334	cairo_bo_trap_t *trap = &left->deferred_trap;
		1335
		1336	/* Only emit (trivial) non-degenerate trapezoids with positive height. */
		1337	if (likely (trap->top < bot)) {
		1338	_cairo_traps_add_trap (traps,
		1339	trap->top, bot,
		1340	&left->edge.line, &trap->right->edge.line);
		1341
		1342	#if DEBUG_PRINT_STATE
		1343	printf ("Deferred trap: left=(%x, %x)-(%x,%x) "
		1344	"right=(%x,%x)-(%x,%x) top=%x, bot=%x\n",
		1345	left->edge.line.p1.x, left->edge.line.p1.y,
		1346	left->edge.line.p2.x, left->edge.line.p2.y,
		1347	trap->right->edge.line.p1.x, trap->right->edge.line.p1.y,
		1348	trap->right->edge.line.p2.x, trap->right->edge.line.p2.y,
		1349	trap->top, bot);
		1350	#endif
		1351	#if DEBUG_EVENTS
		1352	event_log ("end trap: %lu %lu %d %d\n",
		1353	(long) left,
		1354	(long) trap->right,
		1355	trap->top,
		1356	bot);
		1357	#endif
		1358	}
		1359
		1360	trap->right = NULL;
		1361
		1362	return _cairo_traps_status (traps);
		1363	}
		1364
		1365
		1366	/* Start a new trapezoid at the given top y coordinate, whose edges
		1367	* are `edge' and `edge->next'. If `edge' already has a trapezoid,
		1368	* then either add it to the traps in `traps', if the trapezoid's
		1369	* right edge differs from `edge->next', or do nothing if the new
		1370	* trapezoid would be a continuation of the existing one. */
		1371	static inline cairo_status_t
		1372	_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t *left,
		1373	cairo_bo_edge_t *right,
		1374	int top,
		1375	cairo_traps_t *traps)
		1376	{
		1377	cairo_status_t status;
		1378
		1379	if (left->deferred_trap.right == right)
		1380	return CAIRO_STATUS_SUCCESS;
		1381
		1382	if (left->deferred_trap.right != NULL) {
		1383	if (right != NULL && edges_colinear (left->deferred_trap.right, right))
		1384	{
		1385	/* continuation on right, so just swap edges */
		1386	left->deferred_trap.right = right;
		1387	return CAIRO_STATUS_SUCCESS;
		1388	}
		1389
		1390	status = _cairo_bo_edge_end_trap (left, top, traps);
		1391	if (unlikely (status))
		1392	return status;
		1393	}
		1394
		1395	if (right != NULL && ! edges_colinear (left, right)) {
		1396	left->deferred_trap.top = top;
		1397	left->deferred_trap.right = right;
		1398
		1399	#if DEBUG_EVENTS
		1400	event_log ("begin trap: %lu %lu %d\n",
		1401	(long) left,
		1402	(long) right,
		1403	top);
		1404	#endif
		1405	}
		1406
		1407	return CAIRO_STATUS_SUCCESS;
		1408	}
		1409
		1410	static inline cairo_status_t
		1411	_active_edges_to_traps (cairo_bo_edge_t *left,
		1412	int32_t top,
		1413	cairo_fill_rule_t fill_rule,
		1414	cairo_traps_t *traps)
		1415	{
		1416	cairo_bo_edge_t *right;
		1417	cairo_status_t status;
		1418
		1419	#if DEBUG_PRINT_STATE
		1420	printf ("Processing active edges for %x\n", top);
		1421	#endif
		1422
		1423	if (fill_rule == CAIRO_FILL_RULE_WINDING) {
		1424	while (left != NULL) {
		1425	int in_out;
		1426
		1427	/* Greedily search for the closing edge, so that we generate the
		1428	* maximal span width with the minimal number of trapezoids.
		1429	*/
		1430	in_out = left->edge.dir;
		1431
		1432	/* Check if there is a co-linear edge with an existing trap */
		1433	right = left->next;
		1434	if (left->deferred_trap.right == NULL) {
		1435	while (right != NULL && right->deferred_trap.right == NULL)
		1436	right = right->next;
		1437
		1438	if (right != NULL && edges_colinear (left, right)) {
		1439	/* continuation on left */
		1440	left->deferred_trap = right->deferred_trap;
		1441	right->deferred_trap.right = NULL;
		1442	}
		1443	}
		1444
		1445	/* End all subsumed traps */
		1446	right = left->next;
		1447	while (right != NULL) {
		1448	if (right->deferred_trap.right != NULL) {
		1449	status = _cairo_bo_edge_end_trap (right, top, traps);
		1450	if (unlikely (status))
		1451	return status;
		1452	}
		1453
		1454	in_out += right->edge.dir;
		1455	if (in_out == 0) {
		1456	cairo_bo_edge_t *next;
		1457	cairo_bool_t skip = FALSE;
		1458
		1459	/* skip co-linear edges */
		1460	next = right->next;
		1461	if (next != NULL)
		1462	skip = edges_colinear (right, next);
		1463
		1464	if (! skip)
		1465	break;
		1466	}
		1467
		1468	right = right->next;
		1469	}
		1470
		1471	status = _cairo_bo_edge_start_or_continue_trap (left, right,
		1472	top, traps);
		1473	if (unlikely (status))
		1474	return status;
		1475
		1476	left = right;
		1477	if (left != NULL)
		1478	left = left->next;
		1479	}
		1480	} else {
		1481	while (left != NULL) {
		1482	int in_out = 0;
		1483
		1484	right = left->next;
		1485	while (right != NULL) {
		1486	if (right->deferred_trap.right != NULL) {
		1487	status = _cairo_bo_edge_end_trap (right, top, traps);
		1488	if (unlikely (status))
		1489	return status;
		1490	}
		1491
		1492	if ((in_out++ & 1) == 0) {
		1493	cairo_bo_edge_t *next;
		1494	cairo_bool_t skip = FALSE;
		1495
		1496	/* skip co-linear edges */
		1497	next = right->next;
		1498	if (next != NULL)
		1499	skip = edges_colinear (right, next);
		1500
		1501	if (! skip)
		1502	break;
		1503	}
		1504
		1505	right = right->next;
		1506	}
		1507
		1508	status = _cairo_bo_edge_start_or_continue_trap (left, right,
		1509	top, traps);
		1510	if (unlikely (status))
		1511	return status;
		1512
		1513	left = right;
		1514	if (left != NULL)
		1515	left = left->next;
		1516	}
		1517	}
		1518
		1519	return CAIRO_STATUS_SUCCESS;
		1520	}
		1521
		1522
		1523	/* Execute a single pass of the Bentley-Ottmann algorithm on edges,
		1524	* generating trapezoids according to the fill_rule and appending them
		1525	* to traps. */
		1526	static cairo_status_t
		1527	_cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events,
		1528	int num_events,
		1529	cairo_fill_rule_t fill_rule,
		1530	cairo_traps_t *traps,
		1531	int *num_intersections)
		1532	{
		1533	cairo_status_t status = CAIRO_STATUS_SUCCESS; /* silence compiler */
		1534	int intersection_count = 0;
		1535	cairo_bo_event_queue_t event_queue;
		1536	cairo_bo_sweep_line_t sweep_line;
		1537	cairo_bo_event_t *event;
		1538	cairo_bo_edge_t left, right;
		1539	cairo_bo_edge_t e1, e2;
		1540
		1541	#if DEBUG_EVENTS
		1542	{
		1543	int i;
		1544
		1545	for (i = 0; i < num_events; i++) {
		1546	cairo_bo_start_event_t *event =
		1547	((cairo_bo_start_event_t **) start_events)[i];
		1548	event_log ("edge: %lu (%d, %d) (%d, %d) (%d, %d) %d\n",
		1549	(long) &events[i].edge,
		1550	event->edge.edge.line.p1.x,
		1551	event->edge.edge.line.p1.y,
		1552	event->edge.edge.line.p2.x,
		1553	event->edge.edge.line.p2.y,
		1554	event->edge.top,
		1555	event->edge.bottom,
		1556	event->edge.edge.dir);
		1557	}
		1558	}
		1559	#endif
		1560
		1561	_cairo_bo_event_queue_init (&event_queue, start_events, num_events);
		1562	_cairo_bo_sweep_line_init (&sweep_line);
		1563
		1564	while ((event = _cairo_bo_event_dequeue (&event_queue))) {
		1565	if (event->point.y != sweep_line.current_y) {
		1566	for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
		1567	if (e1->deferred_trap.right != NULL) {
		1568	status = _cairo_bo_edge_end_trap (e1,
		1569	e1->edge.bottom,
		1570	traps);
		1571	if (unlikely (status))
		1572	goto unwind;
		1573	}
		1574	}
		1575	sweep_line.stopped = NULL;
		1576
		1577	status = _active_edges_to_traps (sweep_line.head,
		1578	sweep_line.current_y,
		1579	fill_rule, traps);
		1580	if (unlikely (status))
		1581	goto unwind;
		1582
		1583	sweep_line.current_y = event->point.y;
		1584	}
		1585
		1586	#if DEBUG_EVENTS
		1587	event_log ("event: %d (%ld, %ld) %lu, %lu\n",
		1588	event->type,
		1589	(long) event->point.x,
		1590	(long) event->point.y,
		1591	(long) event->e1,
		1592	(long) event->e2);
		1593	#endif
		1594
		1595	switch (event->type) {
		1596	case CAIRO_BO_EVENT_TYPE_START:
		1597	e1 = &((cairo_bo_start_event_t *) event)->edge;
		1598
		1599	status = _cairo_bo_sweep_line_insert (&sweep_line, e1);
		1600	if (unlikely (status))
		1601	goto unwind;
		1602
		1603	status = _cairo_bo_event_queue_insert_stop (&event_queue, e1);
		1604	if (unlikely (status))
		1605	goto unwind;
		1606
		1607	/* check to see if this is a continuation of a stopped edge */
		1608	/* XXX change to an infinitesimal lengthening rule */
		1609	for (left = sweep_line.stopped; left; left = left->next) {
		1610	if (e1->edge.top <= left->edge.bottom &&
		1611	edges_colinear (e1, left))
		1612	{
		1613	e1->deferred_trap = left->deferred_trap;
		1614	if (left->prev != NULL)
		1615	left->prev = left->next;
		1616	else
		1617	sweep_line.stopped = left->next;
		1618	if (left->next != NULL)
		1619	left->next->prev = left->prev;
		1620	break;
		1621	}
		1622	}
		1623
		1624	left = e1->prev;
		1625	right = e1->next;
		1626
		1627	if (left != NULL) {
		1628	status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1);
		1629	if (unlikely (status))
		1630	goto unwind;
		1631	}
		1632
		1633	if (right != NULL) {
		1634	status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
		1635	if (unlikely (status))
		1636	goto unwind;
		1637	}
		1638
		1639	break;
		1640
		1641	case CAIRO_BO_EVENT_TYPE_STOP:
		1642	e1 = ((cairo_bo_queue_event_t *) event)->e1;
		1643	_cairo_bo_event_queue_delete (&event_queue, event);
		1644
		1645	left = e1->prev;
		1646	right = e1->next;
		1647
		1648	_cairo_bo_sweep_line_delete (&sweep_line, e1);
		1649
		1650	/* first, check to see if we have a continuation via a fresh edge */
		1651	if (e1->deferred_trap.right != NULL) {
		1652	e1->next = sweep_line.stopped;
		1653	if (sweep_line.stopped != NULL)
		1654	sweep_line.stopped->prev = e1;
		1655	sweep_line.stopped = e1;
		1656	e1->prev = NULL;
		1657	}
		1658
		1659	if (left != NULL && right != NULL) {
		1660	status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
		1661	if (unlikely (status))
		1662	goto unwind;
		1663	}
		1664
		1665	break;
		1666
		1667	case CAIRO_BO_EVENT_TYPE_INTERSECTION:
		1668	e1 = ((cairo_bo_queue_event_t *) event)->e1;
		1669	e2 = ((cairo_bo_queue_event_t *) event)->e2;
		1670	_cairo_bo_event_queue_delete (&event_queue, event);
		1671
		1672	/* skip this intersection if its edges are not adjacent */
		1673	if (e2 != e1->next)
		1674	break;
		1675
		1676	intersection_count++;
		1677
		1678	left = e1->prev;
		1679	right = e2->next;
		1680
		1681	_cairo_bo_sweep_line_swap (&sweep_line, e1, e2);
		1682
		1683	/* after the swap e2 is left of e1 */
		1684
		1685	if (left != NULL) {
		1686	status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2);
		1687	if (unlikely (status))
		1688	goto unwind;
		1689	}
		1690
		1691	if (right != NULL) {
		1692	status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
		1693	if (unlikely (status))
		1694	goto unwind;
		1695	}
		1696
		1697	break;
		1698	}
		1699	}
		1700
		1701	*num_intersections = intersection_count;
		1702	for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
		1703	if (e1->deferred_trap.right != NULL) {
		1704	status = _cairo_bo_edge_end_trap (e1, e1->edge.bottom, traps);
		1705	if (unlikely (status))
		1706	break;
		1707	}
		1708	}
		1709	unwind:
		1710	_cairo_bo_event_queue_fini (&event_queue);
		1711
		1712	#if DEBUG_EVENTS
		1713	event_log ("\n");
		1714	#endif
		1715
		1716	return status;
		1717	}
		1718
		1719	cairo_status_t
		1720	_cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps,
		1721	const cairo_polygon_t *polygon,
		1722	cairo_fill_rule_t fill_rule)
		1723	{
		1724	int intersections;
		1725	cairo_status_t status;
		1726	cairo_bo_start_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t)];
		1727	cairo_bo_start_event_t *events;
		1728	cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
		1729	cairo_bo_event_t **event_ptrs;
		1730	int num_events;
		1731	int i;
		1732
		1733	num_events = polygon->num_edges;
		1734	if (unlikely (0 == num_events))
		1735	return CAIRO_STATUS_SUCCESS;
		1736
		1737	events = stack_events;
		1738	event_ptrs = stack_event_ptrs;
		1739	if (num_events > ARRAY_LENGTH (stack_events)) {
		1740	events = _cairo_malloc_ab_plus_c (num_events,
		1741	sizeof (cairo_bo_start_event_t) +
		1742	sizeof (cairo_bo_event_t *),
		1743	sizeof (cairo_bo_event_t *));
		1744	if (unlikely (events == NULL))
		1745	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
		1746
		1747	event_ptrs = (cairo_bo_event_t **) (events + num_events);
		1748	}
		1749
		1750	for (i = 0; i < num_events; i++) {
		1751	event_ptrs[i] = (cairo_bo_event_t *) &events[i];
		1752
		1753	events[i].type = CAIRO_BO_EVENT_TYPE_START;
		1754	events[i].point.y = polygon->edges[i].top;
		1755	events[i].point.x =
		1756	_line_compute_intersection_x_for_y (&polygon->edges[i].line,
		1757	events[i].point.y);
		1758
		1759	events[i].edge.edge = polygon->edges[i];
		1760	events[i].edge.deferred_trap.right = NULL;
		1761	events[i].edge.prev = NULL;
		1762	events[i].edge.next = NULL;
		1763	}
		1764
		1765	#if DEBUG_TRAPS
		1766	dump_edges (events, num_events, "bo-polygon-edges.txt");
		1767	#endif
		1768
		1769	/* XXX: This would be the convenient place to throw in multiple
		1770	* passes of the Bentley-Ottmann algorithm. It would merely
		1771	* require storing the results of each pass into a temporary
		1772	* cairo_traps_t. */
		1773	status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs,
		1774	num_events,
		1775	fill_rule, traps,
		1776	&intersections);
		1777	#if DEBUG_TRAPS
		1778	dump_traps (traps, "bo-polygon-out.txt");
		1779	#endif
		1780
		1781	if (events != stack_events)
		1782	free (events);
		1783
		1784	return status;
		1785	}
		1786
		1787	cairo_status_t
		1788	_cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
		1789	cairo_fill_rule_t fill_rule)
		1790	{
		1791	cairo_status_t status;
		1792	cairo_polygon_t polygon;
		1793	int i;
		1794
		1795	if (unlikely (0 == traps->num_traps))
		1796	return CAIRO_STATUS_SUCCESS;
		1797
		1798	#if DEBUG_TRAPS
		1799	dump_traps (traps, "bo-traps-in.txt");
		1800	#endif
		1801
		1802	_cairo_polygon_init (&polygon);
		1803	_cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
		1804
		1805	for (i = 0; i < traps->num_traps; i++) {
		1806	status = _cairo_polygon_add_line (&polygon,
		1807	&traps->traps[i].left,
		1808	traps->traps[i].top,
		1809	traps->traps[i].bottom,
		1810	1);
		1811	if (unlikely (status))
		1812	goto CLEANUP;
		1813
		1814	status = _cairo_polygon_add_line (&polygon,
		1815	&traps->traps[i].right,
		1816	traps->traps[i].top,
		1817	traps->traps[i].bottom,
		1818	-1);
		1819	if (unlikely (status))
		1820	goto CLEANUP;
		1821	}
		1822
		1823	_cairo_traps_clear (traps);
		1824	status = _cairo_bentley_ottmann_tessellate_polygon (traps,
		1825	&polygon,
		1826	fill_rule);
		1827
		1828	#if DEBUG_TRAPS
		1829	dump_traps (traps, "bo-traps-out.txt");
		1830	#endif
		1831
		1832	CLEANUP:
		1833	_cairo_polygon_fini (&polygon);
		1834
		1835	return status;
		1836	}
		1837
		1838	#if 0
		1839	static cairo_bool_t
		1840	edges_have_an_intersection_quadratic (cairo_bo_edge_t *edges,
		1841	int num_edges)
		1842
		1843	{
		1844	int i, j;
		1845	cairo_bo_edge_t a, b;
		1846	cairo_bo_point32_t intersection;
		1847
		1848	/* We must not be given any upside-down edges. */
		1849	for (i = 0; i < num_edges; i++) {
		1850	assert (_cairo_bo_point32_compare (&edges[i].top, &edges[i].bottom) < 0);
		1851	edges[i].line.p1.x <<= CAIRO_BO_GUARD_BITS;
		1852	edges[i].line.p1.y <<= CAIRO_BO_GUARD_BITS;
		1853	edges[i].line.p2.x <<= CAIRO_BO_GUARD_BITS;
		1854	edges[i].line.p2.y <<= CAIRO_BO_GUARD_BITS;
		1855	}
		1856
		1857	for (i = 0; i < num_edges; i++) {
		1858	for (j = 0; j < num_edges; j++) {
		1859	if (i == j)
		1860	continue;
		1861
		1862	a = &edges[i];
		1863	b = &edges[j];
		1864
		1865	if (! _cairo_bo_edge_intersect (a, b, &intersection))
		1866	continue;
		1867
		1868	printf ("Found intersection (%d,%d) between (%d,%d)-(%d,%d) and (%d,%d)-(%d,%d)\n",
		1869	intersection.x,
		1870	intersection.y,
		1871	a->line.p1.x, a->line.p1.y,
		1872	a->line.p2.x, a->line.p2.y,
		1873	b->line.p1.x, b->line.p1.y,
		1874	b->line.p2.x, b->line.p2.y);
		1875
		1876	return TRUE;
		1877	}
		1878	}
		1879	return FALSE;
		1880	}
		1881
		1882	#define TEST_MAX_EDGES 10
		1883
		1884	typedef struct test {
		1885	const char *name;
		1886	const char *description;
		1887	int num_edges;
		1888	cairo_bo_edge_t edges[TEST_MAX_EDGES];
		1889	} test_t;
		1890
		1891	static test_t
		1892	tests[] = {
		1893	{
		1894	"3 near misses",
		1895	"3 edges all intersecting very close to each other",
		1896	3,
		1897	{
		1898	{ { 4, 2}, {0, 0}, { 9, 9}, NULL, NULL },
		1899	{ { 7, 2}, {0, 0}, { 2, 3}, NULL, NULL },
		1900	{ { 5, 2}, {0, 0}, { 1, 7}, NULL, NULL }
		1901	}
		1902	},
		1903	{
		1904	"inconsistent data",
		1905	"Derived from random testing---was leading to skip list and edge list disagreeing.",
		1906	2,
		1907	{
		1908	{ { 2, 3}, {0, 0}, { 8, 9}, NULL, NULL },
		1909	{ { 2, 3}, {0, 0}, { 6, 7}, NULL, NULL }
		1910	}
		1911	},
		1912	{
		1913	"failed sort",
		1914	"A test derived from random testing that leads to an inconsistent sort --- looks like we just can't attempt to validate the sweep line with edge_compare?",
		1915	3,
		1916	{
		1917	{ { 6, 2}, {0, 0}, { 6, 5}, NULL, NULL },
		1918	{ { 3, 5}, {0, 0}, { 5, 6}, NULL, NULL },
		1919	{ { 9, 2}, {0, 0}, { 5, 6}, NULL, NULL },
		1920	}
		1921	},
		1922	{
		1923	"minimal-intersection",
		1924	"Intersection of a two from among the smallest possible edges.",
		1925	2,
		1926	{
		1927	{ { 0, 0}, {0, 0}, { 1, 1}, NULL, NULL },
		1928	{ { 1, 0}, {0, 0}, { 0, 1}, NULL, NULL }
		1929	}
		1930	},
		1931	{
		1932	"simple",
		1933	"A simple intersection of two edges at an integer (2,2).",
		1934	2,
		1935	{
		1936	{ { 1, 1}, {0, 0}, { 3, 3}, NULL, NULL },
		1937	{ { 2, 1}, {0, 0}, { 2, 3}, NULL, NULL }
		1938	}
		1939	},
		1940	{
		1941	"bend-to-horizontal",
		1942	"With intersection truncation one edge bends to horizontal",
		1943	2,
		1944	{
		1945	{ { 9, 1}, {0, 0}, {3, 7}, NULL, NULL },
		1946	{ { 3, 5}, {0, 0}, {9, 9}, NULL, NULL }
		1947	}
		1948	}
		1949	};
		1950
		1951	/*
		1952	{
		1953	"endpoint",
		1954	"An intersection that occurs at the endpoint of a segment.",
		1955	{
		1956	{ { 4, 6}, { 5, 6}, NULL, { { NULL }} },
		1957	{ { 4, 5}, { 5, 7}, NULL, { { NULL }} },
		1958	{ { 0, 0}, { 0, 0}, NULL, { { NULL }} },
		1959	}
		1960	}
		1961	{
		1962	name = "overlapping",
		1963	desc = "Parallel segments that share an endpoint, with different slopes.",
		1964	edges = {
		1965	{ top = { x = 2, y = 0}, bottom = { x = 1, y = 1}},
		1966	{ top = { x = 2, y = 0}, bottom = { x = 0, y = 2}},
		1967	{ top = { x = 0, y = 3}, bottom = { x = 1, y = 3}},
		1968	{ top = { x = 0, y = 3}, bottom = { x = 2, y = 3}},
		1969	{ top = { x = 0, y = 4}, bottom = { x = 0, y = 6}},
		1970	{ top = { x = 0, y = 5}, bottom = { x = 0, y = 6}}
		1971	}
		1972	},
		1973	{
		1974	name = "hobby_stage_3",
		1975	desc = "A particularly tricky part of the 3rd stage of the 'hobby' test below.",
		1976	edges = {
		1977	{ top = { x = -1, y = -2}, bottom = { x = 4, y = 2}},
		1978	{ top = { x = 5, y = 3}, bottom = { x = 9, y = 5}},
		1979	{ top = { x = 5, y = 3}, bottom = { x = 6, y = 3}},
		1980	}
		1981	},
		1982	{
		1983	name = "hobby",
		1984	desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
		1985	edges = {
		1986	{ top = { x = 0, y = 0}, bottom = { x = 9, y = 5}},
		1987	{ top = { x = 0, y = 0}, bottom = { x = 13, y = 6}},
		1988	{ top = { x = -1, y = -2}, bottom = { x = 9, y = 5}}
		1989	}
		1990	},
		1991	{
		1992	name = "slope",
		1993	desc = "Edges with same start/stop points but different slopes",
		1994	edges = {
		1995	{ top = { x = 4, y = 1}, bottom = { x = 6, y = 3}},
		1996	{ top = { x = 4, y = 1}, bottom = { x = 2, y = 3}},
		1997	{ top = { x = 2, y = 4}, bottom = { x = 4, y = 6}},
		1998	{ top = { x = 6, y = 4}, bottom = { x = 4, y = 6}}
		1999	}
		2000	},
		2001	{
		2002	name = "horizontal",
		2003	desc = "Test of a horizontal edge",
		2004	edges = {
		2005	{ top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
		2006	{ top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
		2007	}
		2008	},
		2009	{
		2010	name = "vertical",
		2011	desc = "Test of a vertical edge",
		2012	edges = {
		2013	{ top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
		2014	{ top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
		2015	}
		2016	},
		2017	{
		2018	name = "congruent",
		2019	desc = "Two overlapping edges with the same slope",
		2020	edges = {
		2021	{ top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
		2022	{ top = { x = 5, y = 2}, bottom = { x = 5, y = 6}},
		2023	{ top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
		2024	}
		2025	},
		2026	{
		2027	name = "multi",
		2028	desc = "Several segments with a common intersection point",
		2029	edges = {
		2030	{ top = { x = 1, y = 2}, bottom = { x = 5, y = 4} },
		2031	{ top = { x = 1, y = 1}, bottom = { x = 5, y = 5} },
		2032	{ top = { x = 2, y = 1}, bottom = { x = 4, y = 5} },
		2033	{ top = { x = 4, y = 1}, bottom = { x = 2, y = 5} },
		2034	{ top = { x = 5, y = 1}, bottom = { x = 1, y = 5} },
		2035	{ top = { x = 5, y = 2}, bottom = { x = 1, y = 4} }
		2036	}
		2037	}
		2038	};
		2039	*/
		2040
		2041	static int
		2042	run_test (const char *test_name,
		2043	cairo_bo_edge_t *test_edges,
		2044	int num_edges)
		2045	{
		2046	int i, intersections, passes;
		2047	cairo_bo_edge_t *edges;
		2048	cairo_array_t intersected_edges;
		2049
		2050	printf ("Testing: %s\n", test_name);
		2051
		2052	_cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
		2053
		2054	intersections = _cairo_bentley_ottmann_intersect_edges (test_edges, num_edges, &intersected_edges);
		2055	if (intersections)
		2056	printf ("Pass 1 found %d intersections:\n", intersections);
		2057
		2058
		2059	/* XXX: Multi-pass Bentley-Ottmmann. Preferable would be to add a
		2060	* pass of Hobby's tolerance-square algorithm instead. */
		2061	passes = 1;
		2062	while (intersections) {
		2063	int num_edges = _cairo_array_num_elements (&intersected_edges);
		2064	passes++;
		2065	edges = _cairo_malloc_ab (num_edges, sizeof (cairo_bo_edge_t));
		2066	assert (edges != NULL);
		2067	memcpy (edges, _cairo_array_index (&intersected_edges, 0), num_edges * sizeof (cairo_bo_edge_t));
		2068	_cairo_array_fini (&intersected_edges);
		2069	_cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
		2070	intersections = _cairo_bentley_ottmann_intersect_edges (edges, num_edges, &intersected_edges);
		2071	free (edges);
		2072
		2073	if (intersections){
		2074	printf ("Pass %d found %d remaining intersections:\n", passes, intersections);
		2075	} else {
		2076	if (passes > 3)
		2077	for (i = 0; i < passes; i++)
		2078	printf ("*");
		2079	printf ("No remainining intersections found after pass %d\n", passes);
		2080	}
		2081	}
		2082
		2083	if (edges_have_an_intersection_quadratic (_cairo_array_index (&intersected_edges, 0),
		2084	_cairo_array_num_elements (&intersected_edges)))
		2085	printf ("* FAIL *\n");
		2086	else
		2087	printf ("PASS\n");
		2088
		2089	_cairo_array_fini (&intersected_edges);
		2090
		2091	return 0;
		2092	}
		2093
		2094	#define MAX_RANDOM 300
		2095
		2096	int
		2097	main (void)
		2098	{
		2099	char random_name[] = "random-XX";
		2100	cairo_bo_edge_t random_edges[MAX_RANDOM], *edge;
		2101	unsigned int i, num_random;
		2102	test_t *test;
		2103
		2104	for (i = 0; i < ARRAY_LENGTH (tests); i++) {
		2105	test = &tests[i];
		2106	run_test (test->name, test->edges, test->num_edges);
		2107	}
		2108
		2109	for (num_random = 0; num_random < MAX_RANDOM; num_random++) {
		2110	srand (0);
		2111	for (i = 0; i < num_random; i++) {
		2112	do {
		2113	edge = &random_edges[i];
		2114	edge->line.p1.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
		2115	edge->line.p1.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
		2116	edge->line.p2.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
		2117	edge->line.p2.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
		2118	if (edge->line.p1.y > edge->line.p2.y) {
		2119	int32_t tmp = edge->line.p1.y;
		2120	edge->line.p1.y = edge->line.p2.y;
		2121	edge->line.p2.y = tmp;
		2122	}
		2123	} while (edge->line.p1.y == edge->line.p2.y);
		2124	}
		2125
		2126	sprintf (random_name, "random-%02d", num_random);
		2127
		2128	run_test (random_name, random_edges, num_random);
		2129	}
		2130
		2131	return 0;
		2132	}
		2133	#endif

Subversion Repositories Kolibri OS

(root)/programs/develop/libraries/cairo/src/cairo-bentley-ottmann.c @ 3959 – Rev 1892