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

Subversion Repositories Kolibri OS

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