Back to index

lightning-sunbird  0.9+nobinonly
cairo-traps.c
Go to the documentation of this file.
00001 /*
00002  * Copyright © 2002 Keith Packard
00003  *
00004  * This library is free software; you can redistribute it and/or
00005  * modify it either under the terms of the GNU Lesser General Public
00006  * License version 2.1 as published by the Free Software Foundation
00007  * (the "LGPL") or, at your option, under the terms of the Mozilla
00008  * Public License Version 1.1 (the "MPL"). If you do not alter this
00009  * notice, a recipient may use your version of this file under either
00010  * the MPL or the LGPL.
00011  *
00012  * You should have received a copy of the LGPL along with this library
00013  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00014  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00015  * You should have received a copy of the MPL along with this library
00016  * in the file COPYING-MPL-1.1
00017  *
00018  * The contents of this file are subject to the Mozilla Public License
00019  * Version 1.1 (the "License"); you may not use this file except in
00020  * compliance with the License. You may obtain a copy of the License at
00021  * http://www.mozilla.org/MPL/
00022  *
00023  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00024  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00025  * the specific language governing rights and limitations.
00026  *
00027  * The Original Code is the cairo graphics library.
00028  *
00029  * The Initial Developer of the Original Code is Keith Packard
00030  *
00031  * Contributor(s):
00032  *     Keith R. Packard <keithp@keithp.com>
00033  *     Carl D. Worth <cworth@cworth.org>
00034  *
00035  * 2002-07-15: Converted from XRenderCompositeDoublePoly to cairo_trap. Carl D. Worth
00036  */
00037 
00038 #include "cairoint.h"
00039 
00040 /* private functions */
00041 
00042 static cairo_status_t
00043 _cairo_traps_grow_by (cairo_traps_t *traps, int additional);
00044 
00045 static cairo_status_t
00046 _cairo_traps_add_trap (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
00047                      cairo_line_t *left, cairo_line_t *right);
00048 
00049 static cairo_status_t
00050 _cairo_traps_add_trap_from_points (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
00051                                cairo_point_t left_p1, cairo_point_t left_p2,
00052                                cairo_point_t right_p1, cairo_point_t right_p2);
00053 
00054 static int
00055 _compare_point_fixed_by_y (const void *av, const void *bv);
00056 
00057 static int
00058 _compare_cairo_edge_by_top (const void *av, const void *bv);
00059 
00060 static int
00061 _compare_cairo_edge_by_slope (const void *av, const void *bv);
00062 
00063 static cairo_fixed_16_16_t
00064 _compute_x (cairo_line_t *line, cairo_fixed_t y);
00065 
00066 static int
00067 _line_segs_intersect_ceil (cairo_line_t *left, cairo_line_t *right, cairo_fixed_t *y_ret);
00068 
00069 void
00070 _cairo_traps_init (cairo_traps_t *traps)
00071 {
00072     traps->num_traps = 0;
00073 
00074     traps->traps_size = 0;
00075     traps->traps = NULL;
00076     traps->extents.p1.x = traps->extents.p1.y = CAIRO_MAXSHORT << 16;
00077     traps->extents.p2.x = traps->extents.p2.y = CAIRO_MINSHORT << 16;
00078 }
00079 
00080 void
00081 _cairo_traps_fini (cairo_traps_t *traps)
00082 {
00083     if (traps->traps_size) {
00084        free (traps->traps);
00085        traps->traps = NULL;
00086        traps->traps_size = 0;
00087        traps->num_traps = 0;
00088     }
00089 }
00090 
00100 cairo_status_t
00101 _cairo_traps_init_box (cairo_traps_t *traps,
00102                      cairo_box_t   *box)
00103 {
00104   cairo_status_t status;
00105   
00106   _cairo_traps_init (traps);
00107   
00108   status = _cairo_traps_grow_by (traps, 1);
00109   if (status)
00110     return status;
00111   
00112   traps->num_traps = 1;
00113 
00114   traps->traps[0].top = box->p1.y;
00115   traps->traps[0].bottom = box->p2.y;
00116   traps->traps[0].left.p1 = box->p1;
00117   traps->traps[0].left.p2.x = box->p1.x;
00118   traps->traps[0].left.p2.y = box->p2.y;
00119   traps->traps[0].right.p1.x = box->p2.x;
00120   traps->traps[0].right.p1.y = box->p1.y;
00121   traps->traps[0].right.p2 = box->p2;
00122 
00123   traps->extents = *box;
00124 
00125   return CAIRO_STATUS_SUCCESS;
00126 }
00127 
00128 static cairo_status_t
00129 _cairo_traps_add_trap (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
00130                      cairo_line_t *left, cairo_line_t *right)
00131 {
00132     cairo_status_t status;
00133     cairo_trapezoid_t *trap;
00134 
00135     if (top == bottom) {
00136        return CAIRO_STATUS_SUCCESS;
00137     }
00138 
00139     if (traps->num_traps >= traps->traps_size) {
00140        int inc = traps->traps_size ? traps->traps_size : 32;
00141        status = _cairo_traps_grow_by (traps, inc);
00142        if (status)
00143            return status;
00144     }
00145 
00146     trap = &traps->traps[traps->num_traps];
00147     trap->top = top;
00148     trap->bottom = bottom;
00149     trap->left = *left;
00150     trap->right = *right;
00151 
00152     if (top < traps->extents.p1.y)
00153        traps->extents.p1.y = top;
00154     if (bottom > traps->extents.p2.y)
00155        traps->extents.p2.y = bottom;
00156     /*
00157      * This isn't generally accurate, but it is close enough for
00158      * this purpose.  Assuming that the left and right segments always
00159      * contain the trapezoid vertical extents, these compares will
00160      * yield a containing box.  Assuming that the points all come from
00161      * the same figure which will eventually be completely drawn, then
00162      * the compares will yield the correct overall extents
00163      */
00164     if (left->p1.x < traps->extents.p1.x)
00165        traps->extents.p1.x = left->p1.x;
00166     if (left->p2.x < traps->extents.p1.x)
00167        traps->extents.p1.x = left->p2.x;
00168     
00169     if (right->p1.x > traps->extents.p2.x)
00170        traps->extents.p2.x = right->p1.x;
00171     if (right->p2.x > traps->extents.p2.x)
00172        traps->extents.p2.x = right->p2.x;
00173     
00174     traps->num_traps++;
00175 
00176     return CAIRO_STATUS_SUCCESS;
00177 }
00178 
00179 static cairo_status_t
00180 _cairo_traps_add_trap_from_points (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
00181                                cairo_point_t left_p1, cairo_point_t left_p2,
00182                                cairo_point_t right_p1, cairo_point_t right_p2)
00183 {
00184     cairo_line_t left;
00185     cairo_line_t right;
00186 
00187     left.p1 = left_p1;
00188     left.p2 = left_p2;
00189 
00190     right.p1 = right_p1;
00191     right.p2 = right_p2;
00192 
00193     return _cairo_traps_add_trap (traps, top, bottom, &left, &right);
00194 }
00195 
00196 static cairo_status_t
00197 _cairo_traps_grow_by (cairo_traps_t *traps, int additional)
00198 {
00199     cairo_trapezoid_t *new_traps;
00200     int old_size = traps->traps_size;
00201     int new_size = traps->num_traps + additional;
00202 
00203     if (new_size <= traps->traps_size) {
00204        return CAIRO_STATUS_SUCCESS;
00205     }
00206 
00207     traps->traps_size = new_size;
00208     new_traps = realloc (traps->traps, traps->traps_size * sizeof (cairo_trapezoid_t));
00209 
00210     if (new_traps == NULL) {
00211        traps->traps_size = old_size;
00212        return CAIRO_STATUS_NO_MEMORY;
00213     }
00214 
00215     traps->traps = new_traps;
00216 
00217     return CAIRO_STATUS_SUCCESS;
00218 }
00219 
00220 static int
00221 _compare_point_fixed_by_y (const void *av, const void *bv)
00222 {
00223     const cairo_point_t     *a = av, *b = bv;
00224 
00225     int ret = a->y - b->y;
00226     if (ret == 0) {
00227        ret = a->x - b->x;
00228     }
00229     return ret;
00230 }
00231 
00232 void
00233 _cairo_traps_translate (cairo_traps_t *traps, int x, int y)
00234 {
00235     cairo_fixed_t xoff, yoff;
00236     cairo_trapezoid_t *t;
00237     int i;
00238 
00239     /* Ugh. The cairo_composite/(Render) interface doesn't allow
00240        an offset for the trapezoids. Need to manually shift all
00241        the coordinates to align with the offset origin of the
00242        intermediate surface. */
00243 
00244     xoff = _cairo_fixed_from_int (x);
00245     yoff = _cairo_fixed_from_int (y);
00246 
00247     for (i = 0, t = traps->traps; i < traps->num_traps; i++, t++) {
00248        t->top += yoff;
00249        t->bottom += yoff;
00250        t->left.p1.x += xoff;
00251        t->left.p1.y += yoff;
00252        t->left.p2.x += xoff;
00253        t->left.p2.y += yoff;
00254        t->right.p1.x += xoff;
00255        t->right.p1.y += yoff;
00256        t->right.p2.x += xoff;
00257        t->right.p2.y += yoff;
00258     }
00259 }
00260 
00261 cairo_status_t
00262 _cairo_traps_tessellate_triangle (cairo_traps_t *traps, cairo_point_t t[3])
00263 {
00264     cairo_status_t status;
00265     cairo_line_t line;
00266     cairo_fixed_16_16_t intersect;
00267     cairo_point_t tsort[3];
00268 
00269     memcpy (tsort, t, 3 * sizeof (cairo_point_t));
00270     qsort (tsort, 3, sizeof (cairo_point_t), _compare_point_fixed_by_y);
00271 
00272     /* horizontal top edge requires special handling */
00273     if (tsort[0].y == tsort[1].y) {
00274        if (tsort[0].x < tsort[1].x)
00275            status = _cairo_traps_add_trap_from_points (traps,
00276                                                  tsort[1].y, tsort[2].y,
00277                                                  tsort[0], tsort[2],
00278                                                  tsort[1], tsort[2]);
00279        else
00280            status = _cairo_traps_add_trap_from_points (traps,
00281                                                  tsort[1].y, tsort[2].y,
00282                                                  tsort[1], tsort[2],
00283                                                  tsort[0], tsort[2]);
00284        return status;
00285     }
00286 
00287     line.p1 = tsort[0];
00288     line.p2 = tsort[1];
00289 
00290     intersect = _compute_x (&line, tsort[2].y);
00291 
00292     if (intersect < tsort[2].x) {
00293        status = _cairo_traps_add_trap_from_points (traps,
00294                                               tsort[0].y, tsort[1].y,
00295                                               tsort[0], tsort[1],
00296                                               tsort[0], tsort[2]);
00297        if (status)
00298            return status;
00299        status = _cairo_traps_add_trap_from_points (traps,
00300                                               tsort[1].y, tsort[2].y,
00301                                               tsort[1], tsort[2],
00302                                               tsort[0], tsort[2]);
00303        if (status)
00304            return status;
00305     } else {
00306        status = _cairo_traps_add_trap_from_points (traps,
00307                                               tsort[0].y, tsort[1].y,
00308                                               tsort[0], tsort[2],
00309                                               tsort[0], tsort[1]);
00310        if (status)
00311            return status;
00312        status = _cairo_traps_add_trap_from_points (traps,
00313                                               tsort[1].y, tsort[2].y,
00314                                               tsort[0], tsort[2],
00315                                               tsort[1], tsort[2]);
00316        if (status)
00317            return status;
00318     }
00319 
00320     return CAIRO_STATUS_SUCCESS;
00321 }
00322 
00323 /* Warning: This function reorders the elements of the array provided. */
00324 cairo_status_t
00325 _cairo_traps_tessellate_rectangle (cairo_traps_t *traps, cairo_point_t q[4])
00326 {
00327     cairo_status_t status;
00328 
00329     qsort (q, 4, sizeof (cairo_point_t), _compare_point_fixed_by_y);
00330 
00331     if (q[1].x > q[2].x) {
00332        status = _cairo_traps_add_trap_from_points (traps,
00333                                               q[0].y, q[1].y, q[0], q[2], q[0], q[1]);
00334        if (status)
00335            return status;
00336        status = _cairo_traps_add_trap_from_points (traps,
00337                                               q[1].y, q[2].y, q[0], q[2], q[1], q[3]);
00338        if (status)
00339            return status;
00340        status = _cairo_traps_add_trap_from_points (traps,
00341                                               q[2].y, q[3].y, q[2], q[3], q[1], q[3]);
00342        if (status)
00343            return status;
00344     } else {
00345        status = _cairo_traps_add_trap_from_points (traps,
00346                                               q[0].y, q[1].y, q[0], q[1], q[0], q[2]);
00347        if (status)
00348            return status;
00349        status = _cairo_traps_add_trap_from_points (traps,
00350                                               q[1].y, q[2].y, q[1], q[3], q[0], q[2]);
00351        if (status)
00352            return status;
00353        status = _cairo_traps_add_trap_from_points (traps,
00354                                               q[2].y, q[3].y, q[1], q[3], q[2], q[3]);
00355        if (status)
00356            return status;
00357     }
00358 
00359     return CAIRO_STATUS_SUCCESS;
00360 }
00361 
00362 static int
00363 _compare_cairo_edge_by_top (const void *av, const void *bv)
00364 {
00365     const cairo_edge_t *a = av, *b = bv;
00366 
00367     return a->edge.p1.y - b->edge.p1.y;
00368 }
00369 
00370 /* Return value is:
00371    > 0 if a is "clockwise" from b, (in a mathematical, not a graphical sense)
00372    == 0 if slope (a) == slope (b)
00373    < 0 if a is "counter-clockwise" from b
00374 */
00375 static int
00376 _compare_cairo_edge_by_slope (const void *av, const void *bv)
00377 {
00378     const cairo_edge_t *a = av, *b = bv;
00379     cairo_fixed_32_32_t d;
00380 
00381     cairo_fixed_48_16_t a_dx = a->edge.p2.x - a->edge.p1.x;
00382     cairo_fixed_48_16_t a_dy = a->edge.p2.y - a->edge.p1.y;
00383     cairo_fixed_48_16_t b_dx = b->edge.p2.x - b->edge.p1.x;
00384     cairo_fixed_48_16_t b_dy = b->edge.p2.y - b->edge.p1.y;
00385 
00386     d = b_dy * a_dx - a_dy * b_dx;
00387 
00388     if (d > 0)
00389        return 1;
00390     else if (d == 0)
00391        return 0;
00392     else
00393        return -1;
00394 }
00395 
00396 static int
00397 _compare_cairo_edge_by_current_x_slope (const void *av, const void *bv)
00398 {
00399     const cairo_edge_t *a = av, *b = bv;
00400     int ret;
00401 
00402     ret = a->current_x - b->current_x;
00403     if (ret == 0)
00404        ret = _compare_cairo_edge_by_slope (a, b);
00405     return ret;
00406 }
00407 
00408 /* XXX: Both _compute_x and _compute_inverse_slope will divide by zero
00409    for horizontal lines. Now, we "know" that when we are tessellating
00410    polygons that the polygon data structure discards all horizontal
00411    edges, but there's nothing here to guarantee that. I suggest the
00412    following:
00413 
00414    A) Move all of the polygon tessellation code out of xrtraps.c and
00415       into xrpoly.c, (in order to be in the same module as the code
00416       discarding horizontal lines).
00417 
00418    OR
00419 
00420    B) Re-implement the line intersection in a way that avoids all
00421       division by zero. Here's one approach. The only disadvantage
00422       might be that that there are not meaningful names for all of the
00423       sub-computations -- just a bunch of determinants. I haven't
00424       looked at complexity, (both are probably similar and it probably
00425       doesn't matter much anyway).
00426  */
00427 
00428 /* XXX: Keith's new intersection code is much cleaner, and uses
00429  * sufficient precision for correctly sorting intersections according
00430  * to the analysis in Hobby's paper.
00431  *
00432  * But, when we enable this code, some things are failing, (eg. the
00433  * stars in test/fill_rule get filled wrong). This could indicate a
00434  * bug in one of tree places:
00435  *
00436  *     1) The new intersection code in this file
00437  *
00438  *     2) cairo_wideint.c (which is only exercised here)
00439  *
00440  *      3) In the current tessellator, (where the old intersection
00441  *        code, with its mystic increments could be masking the bug).
00442  *
00443  * It will likely be easier to revisit this when the new tessellation
00444  * code is in place. So, for now, we'll simply disable the new
00445  * intersection code.
00446  */
00447 
00448 #define CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE 0
00449 
00450 #if CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE
00451 static const cairo_fixed_32_32_t
00452 _det16_32 (cairo_fixed_16_16_t a,
00453           cairo_fixed_16_16_t b,
00454           cairo_fixed_16_16_t c,
00455           cairo_fixed_16_16_t d)
00456 {
00457     return _cairo_int64_sub (_cairo_int32x32_64_mul (a, d),
00458                           _cairo_int32x32_64_mul (b, c));
00459 }
00460 
00461 static const cairo_fixed_64_64_t
00462 _det32_64 (cairo_fixed_32_32_t a,
00463           cairo_fixed_32_32_t b,
00464           cairo_fixed_32_32_t c,
00465           cairo_fixed_32_32_t d)
00466 {
00467     return _cairo_int128_sub (_cairo_int64x64_128_mul (a, d),
00468                            _cairo_int64x64_128_mul (b, c));
00469 }
00470 
00471 static const cairo_fixed_32_32_t
00472 _fixed_16_16_to_fixed_32_32 (cairo_fixed_16_16_t a)
00473 {
00474     return _cairo_int64_lsl (_cairo_int32_to_int64 (a), 16);
00475 }
00476 
00477 static int
00478 _line_segs_intersect_ceil (cairo_line_t *l1, cairo_line_t *l2, cairo_fixed_t *y_intersection)
00479 {
00480     cairo_fixed_16_16_t     dx1, dx2, dy1, dy2;
00481     cairo_fixed_32_32_t     den_det;
00482     cairo_fixed_32_32_t     l1_det, l2_det;
00483     cairo_fixed_64_64_t num_det;
00484     cairo_fixed_32_32_t     intersect_32_32;
00485     cairo_fixed_48_16_t     intersect_48_16;
00486     cairo_fixed_16_16_t     intersect_16_16;
00487     cairo_quorem128_t       qr;
00488 
00489     dx1 = l1->p1.x - l1->p2.x;
00490     dy1 = l1->p1.y - l1->p2.y;
00491     dx2 = l2->p1.x - l2->p2.x;
00492     dy2 = l2->p1.y - l2->p2.y;
00493     den_det = _det16_32 (dx1, dy1,
00494                       dx2, dy2);
00495     
00496     if (_cairo_int64_eq (den_det, _cairo_int32_to_int64(0)))
00497        return 0;
00498 
00499     l1_det = _det16_32 (l1->p1.x, l1->p1.y,
00500                      l1->p2.x, l1->p2.y);
00501     l2_det = _det16_32 (l2->p1.x, l2->p1.y,
00502                      l2->p2.x, l2->p2.y);
00503 
00504     
00505     num_det = _det32_64 (l1_det, _fixed_16_16_to_fixed_32_32 (dy1),
00506                       l2_det, _fixed_16_16_to_fixed_32_32 (dy2));
00507     
00508     /*
00509      * Ok, this one is a bit tricky in fixed point, the denominator
00510      * needs to be left with 32-bits of fraction so that the
00511      * result of the divide ends up with 32-bits of fraction (64 - 32 = 32)
00512      */
00513     qr = _cairo_int128_divrem (num_det, _cairo_int64_to_int128 (den_det));
00514     
00515     intersect_32_32 = _cairo_int128_to_int64 (qr.quo);
00516     
00517     /*
00518      * Find the ceiling of the quotient -- divrem returns
00519      * the quotient truncated towards zero, so if the
00520      * quotient should be positive (num_den and den_det have same sign)
00521      * bump the quotient up by one.
00522      */
00523     
00524     if (_cairo_int128_ne (qr.rem, _cairo_int32_to_int128 (0)) &&
00525        (_cairo_int128_ge (num_det, _cairo_int32_to_int128 (0)) ==
00526         _cairo_int64_ge (den_det, _cairo_int32_to_int64 (0))))
00527     {
00528        intersect_32_32 = _cairo_int64_add (intersect_32_32,
00529                                        _cairo_int32_to_int64 (1));
00530     }
00531        
00532     /* 
00533      * Now convert from 32.32 to 48.16 and take the ceiling;
00534      * this requires adding in 15 1 bits and shifting the result
00535      */
00536 
00537     intersect_32_32 = _cairo_int64_add (intersect_32_32,
00538                                    _cairo_int32_to_int64 ((1 << 16) - 1));
00539     intersect_48_16 = _cairo_int64_rsa (intersect_32_32, 16);
00540     
00541     /*
00542      * And drop the top bits
00543      */
00544     intersect_16_16 = _cairo_int64_to_int32 (intersect_48_16);
00545     
00546     *y_intersection = intersect_16_16;
00547 
00548     return 1;
00549 }
00550 #endif /* CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE */
00551 
00552 static cairo_fixed_16_16_t
00553 _compute_x (cairo_line_t *line, cairo_fixed_t y)
00554 {
00555     cairo_fixed_16_16_t dx = line->p2.x - line->p1.x;
00556     cairo_fixed_32_32_t ex = (cairo_fixed_48_16_t) (y - line->p1.y) * (cairo_fixed_48_16_t) dx;
00557     cairo_fixed_16_16_t dy = line->p2.y - line->p1.y;
00558 
00559     return line->p1.x + (ex / dy);
00560 }
00561 
00562 #if ! CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE
00563 static double
00564 _compute_inverse_slope (cairo_line_t *l)
00565 {
00566     return (_cairo_fixed_to_double (l->p2.x - l->p1.x) / 
00567            _cairo_fixed_to_double (l->p2.y - l->p1.y));
00568 }
00569 
00570 static double
00571 _compute_x_intercept (cairo_line_t *l, double inverse_slope)
00572 {
00573     return _cairo_fixed_to_double (l->p1.x) - inverse_slope * _cairo_fixed_to_double (l->p1.y);
00574 }
00575 
00576 static int
00577 _line_segs_intersect_ceil (cairo_line_t *l1, cairo_line_t *l2, cairo_fixed_t *y_ret)
00578 {
00579     /*
00580      * x = m1y + b1
00581      * x = m2y + b2
00582      * m1y + b1 = m2y + b2
00583      * y * (m1 - m2) = b2 - b1
00584      * y = (b2 - b1) / (m1 - m2)
00585      */
00586     cairo_fixed_16_16_t y_intersect;
00587     double  m1 = _compute_inverse_slope (l1);
00588     double  b1 = _compute_x_intercept (l1, m1);
00589     double  m2 = _compute_inverse_slope (l2);
00590     double  b2 = _compute_x_intercept (l2, m2);
00591 
00592     if (m1 == m2)
00593        return 0;
00594 
00595     y_intersect = _cairo_fixed_from_double ((b2 - b1) / (m1 - m2));
00596 
00597     if (m1 < m2) {
00598        cairo_line_t *t;
00599        t = l1;
00600        l1 = l2;
00601        l2 = t;
00602     }
00603 
00604     /* Assuming 56 bits of floating point precision, the intersection
00605        is accurate within one sub-pixel coordinate. We must ensure
00606        that we return a value that is at or after the intersection. At
00607        most, we must increment once. */
00608     if (_compute_x (l2, y_intersect) > _compute_x (l1, y_intersect))
00609        y_intersect++;
00610     /* XXX: Hmm... Keith's error calculations said we'd at most be off
00611        by one sub-pixel. But, I found that the paint-fill-BE-01.svg
00612        test from the W3C SVG conformance suite definitely requires two
00613        increments.
00614 
00615        It could be that we need one to overcome the error, and another
00616        to round up.
00617 
00618        It would be nice to be sure this code is correct, (but we can't
00619        do the while loop as it will work for way to long on
00620        exceedingly distant intersections with large errors that we
00621        really don't care about anyway as they will be ignored by the
00622        calling function.
00623     */
00624     if (_compute_x (l2, y_intersect) > _compute_x (l1, y_intersect))
00625        y_intersect++;
00626     /* XXX: hmm... now I found "intersection_killer" inside xrspline.c
00627        that requires 3 increments. Clearly, we haven't characterized
00628        this completely yet. */
00629     if (_compute_x (l2, y_intersect) > _compute_x (l1, y_intersect))
00630        y_intersect++;
00631     /* I think I've found the answer to our problems. The insight is
00632        that everytime we round we are changing the slopes of the
00633        relevant lines, so we may be introducing new intersections that
00634        we miss, so everything breaks apart. John Hobby wrote a paper
00635        on how to fix this:
00636 
00637        [Hobby93c] John D. Hobby, Practical Segment Intersection with
00638        Finite Precision Output, Computation Geometry Theory and
00639        Applications, 13(4), 1999.
00640 
00641        Available online (2003-08017):
00642 
00643        http://cm.bell-labs.com/cm/cs/doc/93/2-27.ps.gz
00644 
00645        Now we just need to go off and implement that.
00646     */
00647 
00648     *y_ret = y_intersect;
00649 
00650     return 1;
00651 }
00652 #endif /* CAIRO_TRAPS_USE_NEW_INTERSECTION_CODE */
00653 
00654 /* The algorithm here is pretty simple:
00655 
00656    inactive = [edges]
00657    y = min_p1_y (inactive)
00658 
00659    while (num_active || num_inactive) {
00660        active = all edges containing y
00661 
00662        next_y = min ( min_p2_y (active), min_p1_y (inactive), min_intersection (active) )
00663 
00664        fill_traps (active, y, next_y, fill_rule)
00665 
00666        y = next_y
00667    }
00668 
00669    The invariants that hold during fill_traps are:
00670 
00671        All edges in active contain both y and next_y
00672        No edges in active intersect within y and next_y
00673 
00674    These invariants mean that fill_traps is as simple as sorting the
00675    active edges, forming a trapezoid between each adjacent pair. Then,
00676    either the even-odd or winding rule is used to determine whether to
00677    emit each of these trapezoids.
00678 
00679    Warning: This function obliterates the edges of the polygon provided.
00680 */
00681 cairo_status_t
00682 _cairo_traps_tessellate_polygon (cairo_traps_t          *traps,
00683                              cairo_polygon_t     *poly,
00684                              cairo_fill_rule_t   fill_rule)
00685 {
00686     cairo_status_t   status;
00687     int              i, active, inactive;
00688     cairo_fixed_t    y, y_next, intersect;
00689     int                     in_out, num_edges = poly->num_edges;
00690     cairo_edge_t     *edges = poly->edges;
00691 
00692     if (num_edges == 0)
00693        return CAIRO_STATUS_SUCCESS;
00694 
00695     qsort (edges, num_edges, sizeof (cairo_edge_t), _compare_cairo_edge_by_top);
00696     
00697     y = edges[0].edge.p1.y;
00698     active = 0;
00699     inactive = 0;
00700     while (active < num_edges) {
00701        while (inactive < num_edges && edges[inactive].edge.p1.y <= y)
00702            inactive++;
00703 
00704        for (i = active; i < inactive; i++)
00705            edges[i].current_x = _compute_x (&edges[i].edge, y);
00706 
00707        qsort (&edges[active], inactive - active,
00708               sizeof (cairo_edge_t), _compare_cairo_edge_by_current_x_slope);
00709 
00710        /* find next inflection point */
00711        y_next = edges[active].edge.p2.y;
00712 
00713        for (i = active; i < inactive; i++) {
00714            if (edges[i].edge.p2.y < y_next)
00715               y_next = edges[i].edge.p2.y;
00716            /* check intersect */
00717            if (i != inactive - 1 && edges[i].current_x != edges[i+1].current_x)
00718               if (_line_segs_intersect_ceil (&edges[i].edge, &edges[i+1].edge,
00719                                           &intersect))
00720                   if (intersect > y && intersect < y_next)
00721                      y_next = intersect;
00722        }
00723        /* check next inactive point */
00724        if (inactive < num_edges && edges[inactive].edge.p1.y < y_next)
00725            y_next = edges[inactive].edge.p1.y;
00726 
00727        /* walk the active edges generating trapezoids */
00728        in_out = 0;
00729        for (i = active; i < inactive - 1; i++) {
00730            if (fill_rule == CAIRO_FILL_RULE_WINDING) {
00731               if (edges[i].clockWise)
00732                   in_out++;
00733               else
00734                   in_out--;
00735               if (in_out == 0)
00736                   continue;
00737            } else {
00738               in_out++;
00739               if ((in_out & 1) == 0)
00740                   continue;
00741            }
00742            status = _cairo_traps_add_trap (traps, y, y_next, &edges[i].edge, &edges[i+1].edge);
00743            if (status)
00744               return status;
00745        }
00746 
00747        /* delete inactive edges */
00748        for (i = active; i < inactive; i++) {
00749            if (edges[i].edge.p2.y <= y_next) {
00750               memmove (&edges[active+1], &edges[active], (i - active) * sizeof (cairo_edge_t));
00751               active++;
00752            }
00753        }
00754 
00755        y = y_next;
00756     }
00757     return CAIRO_STATUS_SUCCESS;
00758 }
00759 
00760 static cairo_bool_t
00761 _cairo_trap_contains (cairo_trapezoid_t *t, cairo_point_t *pt)
00762 {
00763     cairo_slope_t slope_left, slope_pt, slope_right;
00764     
00765     if (t->top > pt->y)
00766        return FALSE;
00767     if (t->bottom < pt->y)
00768        return FALSE;
00769     
00770     _cairo_slope_init (&slope_left, &t->left.p1, &t->left.p2);
00771     _cairo_slope_init (&slope_pt, &t->left.p1, pt);
00772 
00773     if (_cairo_slope_compare (&slope_left, &slope_pt) < 0)
00774        return FALSE;
00775 
00776     _cairo_slope_init (&slope_right, &t->right.p1, &t->right.p2);
00777     _cairo_slope_init (&slope_pt, &t->right.p1, pt);
00778 
00779     if (_cairo_slope_compare (&slope_pt, &slope_right) < 0)
00780        return FALSE;
00781 
00782     return TRUE;
00783 }
00784 
00785 cairo_bool_t
00786 _cairo_traps_contain (cairo_traps_t *traps, double x, double y)
00787 {
00788     int i;
00789     cairo_point_t point;
00790 
00791     point.x = _cairo_fixed_from_double (x);
00792     point.y = _cairo_fixed_from_double (y);
00793 
00794     for (i = 0; i < traps->num_traps; i++) {
00795        if (_cairo_trap_contains (&traps->traps[i], &point))
00796            return TRUE;
00797     }
00798 
00799     return FALSE;
00800 }
00801 
00802 void
00803 _cairo_traps_extents (cairo_traps_t *traps, cairo_box_t *extents)
00804 {
00805     *extents = traps->extents;
00806 }
00807 
00821 cairo_status_t
00822 _cairo_traps_extract_region (cairo_traps_t      *traps,
00823                           pixman_region16_t **region)
00824 {
00825     int i;
00826 
00827     for (i = 0; i < traps->num_traps; i++)
00828        if (!(traps->traps[i].left.p1.x == traps->traps[i].left.p2.x
00829              && traps->traps[i].right.p1.x == traps->traps[i].right.p2.x
00830              && _cairo_fixed_is_integer(traps->traps[i].top)
00831              && _cairo_fixed_is_integer(traps->traps[i].bottom)
00832              && _cairo_fixed_is_integer(traps->traps[i].left.p1.x)
00833              && _cairo_fixed_is_integer(traps->traps[i].right.p1.x))) {
00834            *region = NULL;
00835            return CAIRO_STATUS_SUCCESS;
00836        }
00837     
00838     *region = pixman_region_create ();
00839 
00840     for (i = 0; i < traps->num_traps; i++) {
00841        int x = _cairo_fixed_integer_part(traps->traps[i].left.p1.x);
00842        int y = _cairo_fixed_integer_part(traps->traps[i].top);
00843        int width = _cairo_fixed_integer_part(traps->traps[i].right.p1.x) - x;
00844        int height = _cairo_fixed_integer_part(traps->traps[i].bottom) - y;
00845 
00846        /* XXX: Sometimes we get degenerate trapezoids from the tesellator,
00847         * if we call pixman_region_union_rect(), it bizarrly fails on such
00848         * an empty rectangle, so skip them.
00849         */
00850        if (width == 0 || height == 0)
00851          continue;
00852        
00853        if (pixman_region_union_rect (*region, *region,
00854                                   x, y, width, height) != PIXMAN_REGION_STATUS_SUCCESS) {
00855            pixman_region_destroy (*region);
00856            return CAIRO_STATUS_NO_MEMORY;
00857        }
00858     }
00859 
00860     return CAIRO_STATUS_SUCCESS;
00861 }
00862