[PATCH] Added support for float operations along int64/128, and =
Antoine Azar
cairo at antoineazar.com
Wed Jul 30 00:31:45 PDT 2008
added bounding box check in line intersection code of Bentley-Ottman=0A=
=0A=
---=0A=
src/cairo-bentley-ottmann.c | 103 =
++++++++++++++++++++++++++++++++++++++=0A=
src/cairo-wideint-private.h | 3 +=0A=
src/cairo-wideint-type-private.h | 6 ++-=0A=
src/cairo-wideint.c | 12 ++++=0A=
4 files changed, 123 insertions(+), 1 deletions(-)=0A=
=0A=
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c=0A=
index 8e97f1f..886450e 100644=0A=
--- a/src/cairo-bentley-ottmann.c=0A=
+++ b/src/cairo-bentley-ottmann.c=0A=
@@ -202,6 +202,16 @@ _slope_compare (cairo_bo_edge_t *a,=0A=
else {=0A=
int32_t ady =3D a->bottom.y - a->top.y;=0A=
int32_t bdy =3D b->bottom.y - b->top.y;=0A=
+#ifdef OPTIMIZE_FOR_FPU=0A=
+ float adx_bdy =3D (float)adx * bdy;=0A=
+ float bdx_ady =3D (float)bdx * ady;=0A=
+=0A=
+ if (adx_bdy > bdx_ady)=0A=
+ return 1;=0A=
+=0A=
+ if (adx_bdy < bdx_ady)=0A=
+ return -1;=0A=
+#else=0A=
int64_t adx_bdy =3D _cairo_int32x32_64_mul (adx, bdy);=0A=
int64_t bdx_ady =3D _cairo_int32x32_64_mul (bdx, ady);=0A=
=0A=
@@ -212,10 +222,45 @@ _slope_compare (cairo_bo_edge_t *a,=0A=
/* if (adx * bdy < bdx * ady) */=0A=
if (_cairo_int64_lt (adx_bdy, bdx_ady))=0A=
return -1;=0A=
+#endif=0A=
return 0;=0A=
}=0A=
}=0A=
=0A=
+#ifdef OPTIMIZE_FOR_FPU=0A=
+static cairo_quoremfloat_t=0A=
+edge_x_for_y (cairo_bo_edge_t *edge,=0A=
+ int32_t y)=0A=
+{=0A=
+ int32_t dx =3D edge->bottom.x - edge->top.x;=0A=
+ int32_t dy =3D edge->bottom.y - edge->top.y;=0A=
+ float numerator;=0A=
+ cairo_quoremfloat_t quorem;=0A=
+=0A=
+ if (edge->middle.y =3D=3D y) {=0A=
+ quorem.quo =3D (float)edge->middle.x;=0A=
+ quorem.rem =3D 0.f;=0A=
+ return quorem;=0A=
+ }=0A=
+ if (edge->bottom.y =3D=3D y) {=0A=
+ quorem.quo =3D (float)edge->bottom.x;=0A=
+ quorem.rem =3D 0.f;=0A=
+ return quorem;=0A=
+ }=0A=
+ if (dy =3D=3D 0) {=0A=
+ quorem.quo =3D (float)edge->top.x;=0A=
+ quorem.rem =3D 0.f;=0A=
+ return quorem;=0A=
+ }=0A=
+=0A=
+ /* edge->top.x + (y - edge->top.y) * dx / dy */=0A=
+ numerator =3D (float)(y - edge->top.y) * dx;=0A=
+ quorem =3D _cairo_float_divrem (numerator, (float)dy);=0A=
+ quorem.quo +=3D (float)edge->top.x;=0A=
+=0A=
+ return quorem;=0A=
+}=0A=
+#else=0A=
static cairo_quorem64_t=0A=
edge_x_for_y (cairo_bo_edge_t *edge,=0A=
int32_t y)=0A=
@@ -253,14 +298,21 @@ edge_x_for_y (cairo_bo_edge_t *edge,=0A=
=0A=
return quorem;=0A=
}=0A=
+#endif=0A=
=0A=
static int=0A=
_cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line,=0A=
cairo_bo_edge_t *a,=0A=
cairo_bo_edge_t *b)=0A=
{=0A=
+#ifdef OPTIMIZE_FOR_FPU=0A=
+ cairo_quoremfloat_t ax;=0A=
+ cairo_quoremfloat_t bx;=0A=
+#else=0A=
cairo_quorem64_t ax;=0A=
cairo_quorem64_t bx;=0A=
+#endif=0A=
+=0A=
int cmp;=0A=
=0A=
if (a =3D=3D b)=0A=
@@ -472,6 +524,15 @@ cairo_bo_event_compare_pointers (void const *voida,=0A=
return 0;=0A=
}=0A=
=0A=
+static inline float=0A=
+det32_float (int32_t a,=0A=
+ int32_t b,=0A=
+ int32_t c,=0A=
+ int32_t d)=0A=
+{=0A=
+ return ((float)a*d - (float)b*c);=0A=
+}=0A=
+=0A=
static inline cairo_int64_t=0A=
det32_64 (int32_t a,=0A=
int32_t b,=0A=
@@ -510,11 +571,44 @@ det64_128 (cairo_int64_t a,=0A=
* Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or=0A=
* %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.=0A=
*/=0A=
+=0A=
static cairo_bo_status_t=0A=
intersect_lines (cairo_bo_edge_t *a,=0A=
cairo_bo_edge_t *b,=0A=
cairo_bo_intersect_point_t *intersection)=0A=
{=0A=
+#ifdef OPTIMIZE_FOR_FPU=0A=
+ float a_det, b_det;=0A=
+=0A=
+ int32_t dx1 =3D a->top.x - a->bottom.x;=0A=
+ int32_t dy1 =3D a->top.y - a->bottom.y;=0A=
+=0A=
+ int32_t dx2 =3D b->top.x - b->bottom.x;=0A=
+ int32_t dy2 =3D b->top.y - b->bottom.y;=0A=
+=0A=
+ float den_det =3D det32_float(dx1, dy1, dx2, dy2);=0A=
+ float quo;=0A=
+=0A=
+ if ( den_det =3D=3D 0.f )=0A=
+ return CAIRO_BO_STATUS_PARALLEL;=0A=
+=0A=
+ a_det =3D det32_float (a->top.x, a->top.y,=0A=
+ a->bottom.x, a->bottom.y);=0A=
+ b_det =3D det32_float (b->top.x, b->top.y,=0A=
+ b->bottom.x, b->bottom.y);=0A=
+=0A=
+ quo =3D (a_det*dx2 - dx1*b_det) / den_det;=0A=
+=0A=
+ intersection->x.ordinate =3D (int32_t)quo;=0A=
+ intersection->x.exactness =3D quo-(int32_t)quo ? INEXACT : EXACT;=0A=
+=0A=
+ quo =3D (a_det*dy2 - dy1*b_det) / den_det;=0A=
+=0A=
+ intersection->y.ordinate =3D (int32_t)quo;=0A=
+ intersection->y.exactness =3D quo-(int32_t)quo ? INEXACT : EXACT;=0A=
+=0A=
+#else=0A=
+=0A=
cairo_int64_t a_det, b_det;=0A=
=0A=
/* XXX: We're assuming here that dx and dy will still fit in 32=0A=
@@ -544,6 +638,8 @@ intersect_lines (cairo_bo_edge_t *a,=0A=
qr =3D _cairo_int_96by64_32x64_divrem (det64_128 (a_det, dx1,=0A=
b_det, dx2),=0A=
den_det);=0A=
+=0A=
+ /* aazar: Why this check? isn't this impossible? */=0A=
if (_cairo_int64_eq (qr.rem,den_det))=0A=
return CAIRO_BO_STATUS_NO_INTERSECTION;=0A=
intersection->x.ordinate =3D qr.quo;=0A=
@@ -553,10 +649,13 @@ intersect_lines (cairo_bo_edge_t *a,=0A=
qr =3D _cairo_int_96by64_32x64_divrem (det64_128 (a_det, dy1,=0A=
b_det, dy2),=0A=
den_det);=0A=
+=0A=
+ /* aazar: Why this check? isn't this impossible? */=0A=
if (_cairo_int64_eq (qr.rem, den_det))=0A=
return CAIRO_BO_STATUS_NO_INTERSECTION;=0A=
intersection->y.ordinate =3D qr.quo;=0A=
intersection->y.exactness =3D qr.rem ? INEXACT : EXACT;=0A=
+#endif=0A=
=0A=
return CAIRO_BO_STATUS_INTERSECTION;=0A=
}=0A=
@@ -659,6 +758,10 @@ _cairo_bo_edge_intersect (cairo_bo_edge_t *a,=0A=
cairo_bo_status_t status;=0A=
cairo_bo_intersect_point_t quorem;=0A=
=0A=
+ /* check edge bounding box first */=0A=
+ if (MAX (a->top.x, a->bottom.x) < MIN (b->top.x, b->bottom.x))=0A=
+ return CAIRO_BO_STATUS_NO_INTERSECTION;=0A=
+=0A=
status =3D intersect_lines (a, b, &quorem);=0A=
if (status)=0A=
return status;=0A=
diff --git a/src/cairo-wideint-private.h b/src/cairo-wideint-private.h=0A=
index 412fc00..9f0def5 100644=0A=
--- a/src/cairo-wideint-private.h=0A=
+++ b/src/cairo-wideint-private.h=0A=
@@ -145,6 +145,9 @@ _cairo_uint64_divrem (cairo_uint64_t num, =
cairo_uint64_t den);=0A=
cairo_quorem64_t I=0A=
_cairo_int64_divrem (cairo_int64_t num, cairo_int64_t den);=0A=
=0A=
+cairo_quoremfloat_t=0A=
+_cairo_float_divrem (float num, float den);=0A=
+=0A=
/*=0A=
* 128-bit datatypes. Again, provide two implementations in=0A=
* case the machine has a native 128-bit datatype. GCC supports =
int128_t=0A=
diff --git a/src/cairo-wideint-type-private.h =
b/src/cairo-wideint-type-private.h=0A=
index aa76766..e40e615 100644=0A=
--- a/src/cairo-wideint-type-private.h=0A=
+++ b/src/cairo-wideint-type-private.h=0A=
@@ -118,6 +118,11 @@ typedef struct _cairo_quorem64 {=0A=
cairo_int64_t rem;=0A=
} cairo_quorem64_t;=0A=
=0A=
+typedef struct _cairo_quoremfloat {=0A=
+ float quo;=0A=
+ float rem;=0A=
+} cairo_quoremfloat_t;=0A=
+=0A=
=0A=
#if !HAVE_UINT128_T=0A=
=0A=
@@ -142,5 +147,4 @@ typedef struct _cairo_quorem128 {=0A=
cairo_int128_t rem;=0A=
} cairo_quorem128_t;=0A=
=0A=
-=0A=
#endif /* CAIRO_WIDEINT_H */=0A=
diff --git a/src/cairo-wideint.c b/src/cairo-wideint.c=0A=
index e8d3ab6..2c8b730 100644=0A=
--- a/src/cairo-wideint.c=0A=
+++ b/src/cairo-wideint.c=0A=
@@ -315,6 +315,18 @@ _cairo_int64_divrem (cairo_int64_t num, =
cairo_int64_t den)=0A=
return qr;=0A=
}=0A=
=0A=
+cairo_quoremfloat_t=0A=
+_cairo_float_divrem (float num, float den)=0A=
+{=0A=
+ cairo_quoremfloat_t qr;=0A=
+ float quo =3D num/den;=0A=
+ qr.quo =3D (int32_t)quo;=0A=
+ qr.rem =3D (quo - qr.quo)*den;=0A=
+=0A=
+ return qr;=0A=
+}=0A=
+=0A=
+=0A=
#if HAVE_UINT128_T=0A=
=0A=
cairo_uquorem128_t=0A=
-- =0A=
1.5.5.1015.g9d258=0A=
=0A=
------=_NextPart_000_002B_01C8F204.4A137800--
More information about the cairo
mailing list