src/borast/borast-traps.c

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /*
   3  * Copyright © 2002 Keith Packard
   4  * Copyright © 2007 Red Hat, Inc.
   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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 Keith Packard
  32  *
  33  * Contributor(s):
  34  *      Keith R. Packard <keithp@keithp.com>
  35  *      Carl D. Worth <cworth@cworth.org>
  36  *
  37  * 2002-07-15: Converted from XRenderCompositeDoublePoly to #cairo_trap_t. Carl D. Worth
  38  */
  39
  40 #include "borastint-minimal.h"
  41 #include "borast-malloc-private.h"
  42 #include "borast-traps-private.h"
  43 #include "borast-fixed-private.h"
  44
  45 #define _borast_error(x) (x)
  46
  47 /* private functions */
  48
  49 void
  50 _borast_traps_init (borast_traps_t *traps)
  51 {
  52     VG (VALGRIND_MAKE_MEM_UNDEFINED (traps, sizeof (borast_traps_t)));
  53
  54     traps->status = BORAST_STATUS_SUCCESS;
  55
  56     traps->maybe_region = 1;
  57     traps->is_rectilinear = 0;
  58     traps->is_rectangular = 0;
  59
  60     traps->num_traps = 0;
  61
  62     traps->traps_size = ARRAY_LENGTH (traps->traps_embedded);
  63     traps->traps = traps->traps_embedded;
  64
  65     traps->num_limits = 0;
  66     traps->has_intersections = FALSE;
  67 }
  68
  69 void
  70 _borast_traps_limit (borast_traps_t     *traps,
  71                     const borast_box_t  *limits,
  72                     int                  num_limits)
  73 {
  74     traps->limits = limits;
  75     traps->num_limits = num_limits;
  76 }
  77
  78 void
  79 _borast_traps_clear (borast_traps_t *traps)
  80 {
  81     traps->status = BORAST_STATUS_SUCCESS;
  82
  83     traps->maybe_region = 1;
  84     traps->is_rectilinear = 0;
  85     traps->is_rectangular = 0;
  86
  87     traps->num_traps = 0;
  88     traps->has_intersections = FALSE;
  89 }
  90
  91 void
  92 _borast_traps_fini (borast_traps_t *traps)
  93 {
  94     if (traps->traps != traps->traps_embedded)
  95         free (traps->traps);
  96
  97     VG (VALGRIND_MAKE_MEM_NOACCESS (traps, sizeof (borast_traps_t)));
  98 }
  99
 100 /* make room for at least one more trap */
 101 static borast_bool_t
 102 _borast_traps_grow (borast_traps_t *traps)
 103 {
 104     borast_trapezoid_t *new_traps;
 105     int new_size = 4 * traps->traps_size;
 106
 107     if (traps->traps == traps->traps_embedded) {
 108         new_traps = _borast_malloc_ab (new_size, sizeof (borast_trapezoid_t));
 109         if (new_traps != NULL)
 110             memcpy (new_traps, traps->traps, sizeof (traps->traps_embedded));
 111     } else {
 112         new_traps = _borast_realloc_ab (traps->traps,
 113                                        new_size, sizeof (borast_trapezoid_t));
 114     }
 115
 116     if (unlikely (new_traps == NULL)) {
 117         traps->status = _borast_error (BORAST_STATUS_NO_MEMORY);
 118         return FALSE;
 119     }
 120
 121     traps->traps = new_traps;
 122     traps->traps_size = new_size;
 123     return TRUE;
 124 }
 125
 126 void
 127 _borast_traps_add_trap (borast_traps_t *traps,
 128                        borast_fixed_t top, borast_fixed_t bottom,
 129                        borast_line_t *left, borast_line_t *right)
 130 {
 131     borast_trapezoid_t *trap;
 132
 133     if (unlikely (traps->num_traps == traps->traps_size)) {
 134         if (unlikely (! _borast_traps_grow (traps)))
 135             return;
 136     }
 137
 138     trap = &traps->traps[traps->num_traps++];
 139     trap->top = top;
 140     trap->bottom = bottom;
 141     trap->left = *left;
 142     trap->right = *right;
 143 }
 144
 145 /**
 146  * _borast_traps_init_box:
 147  * @traps: a #borast_traps_t
 148  * @box: an array box that will each be converted to a single trapezoid
 149  *       to store in @traps.
 150  *
 151  * Initializes a #borast_traps_t to contain an array of rectangular
 152  * trapezoids.
 153  **/
 154 borast_status_t
 155 _borast_traps_init_boxes (borast_traps_t            *traps,
 156                          const borast_box_t  *boxes,
 157                          int                 num_boxes)
 158 {
 159     borast_trapezoid_t *trap;
 160
 161     _borast_traps_init (traps);
 162
 163     while (traps->traps_size < num_boxes) {
 164         if (unlikely (! _borast_traps_grow (traps))) {
 165             _borast_traps_fini (traps);
 166             return _borast_error (BORAST_STATUS_NO_MEMORY);
 167         }
 168     }
 169
 170     traps->num_traps = num_boxes;
 171     traps->is_rectilinear = TRUE;
 172     traps->is_rectangular = TRUE;
 173
 174     trap = &traps->traps[0];
 175     while (num_boxes--) {
 176         trap->top    = boxes->p1.y;
 177         trap->bottom = boxes->p2.y;
 178
 179         trap->left.p1   = boxes->p1;
 180         trap->left.p2.x = boxes->p1.x;
 181         trap->left.p2.y = boxes->p2.y;
 182
 183         trap->right.p1.x = boxes->p2.x;
 184         trap->right.p1.y = boxes->p1.y;
 185         trap->right.p2   = boxes->p2;
 186
 187         if (traps->maybe_region) {
 188             traps->maybe_region  = _borast_fixed_is_integer (boxes->p1.x) &&
 189                                    _borast_fixed_is_integer (boxes->p1.y) &&
 190                                    _borast_fixed_is_integer (boxes->p2.x) &&
 191                                    _borast_fixed_is_integer (boxes->p2.y);
 192         }
 193
 194         trap++, boxes++;
 195     }
 196
 197     return BORAST_STATUS_SUCCESS;
 198 }
 199
 200 borast_status_t
 201 _borast_traps_tessellate_rectangle (borast_traps_t *traps,
 202                                    const borast_point_t *top_left,
 203                                    const borast_point_t *bottom_right)
 204 {
 205     borast_line_t left;
 206     borast_line_t right;
 207     borast_fixed_t top, bottom;
 208
 209     if (top_left->y == bottom_right->y)
 210         return BORAST_STATUS_SUCCESS;
 211
 212     if (top_left->x == bottom_right->x)
 213         return BORAST_STATUS_SUCCESS;
 214
 215      left.p1.x =  left.p2.x = top_left->x;
 216      left.p1.y = right.p1.y = top_left->y;
 217     right.p1.x = right.p2.x = bottom_right->x;
 218      left.p2.y = right.p2.y = bottom_right->y;
 219
 220      top = top_left->y;
 221      bottom = bottom_right->y;
 222
 223     if (traps->num_limits) {
 224         borast_bool_t reversed;
 225         int n;
 226
 227         /* support counter-clockwise winding for rectangular tessellation */
 228         reversed = top_left->x > bottom_right->x;
 229         if (reversed) {
 230             right.p1.x = right.p2.x = top_left->x;
 231             left.p1.x = left.p2.x = bottom_right->x;
 232         }
 233
 234         for (n = 0; n < traps->num_limits; n++) {
 235             const borast_box_t *limits = &traps->limits[n];
 236             borast_line_t _left, _right;
 237             borast_fixed_t _top, _bottom;
 238
 239             if (top >= limits->p2.y)
 240                 continue;
 241             if (bottom <= limits->p1.y)
 242                 continue;
 243
 244             /* Trivially reject if trapezoid is entirely to the right or
 245              * to the left of the limits. */
 246             if (left.p1.x >= limits->p2.x)
 247                 continue;
 248             if (right.p1.x <= limits->p1.x)
 249                 continue;
 250
 251             /* Otherwise, clip the trapezoid to the limits. */
 252             _top = top;
 253             if (_top < limits->p1.y)
 254                 _top = limits->p1.y;
 255
 256             _bottom = bottom;
 257             if (_bottom > limits->p2.y)
 258                 _bottom = limits->p2.y;
 259
 260             if (_bottom <= _top)
 261                 continue;
 262
 263             _left = left;
 264             if (_left.p1.x < limits->p1.x) {
 265                 _left.p1.x = limits->p1.x;
 266                 _left.p1.y = limits->p1.y;
 267                 _left.p2.x = limits->p1.x;
 268                 _left.p2.y = limits->p2.y;
 269             }
 270
 271             _right = right;
 272             if (_right.p1.x > limits->p2.x) {
 273                 _right.p1.x = limits->p2.x;
 274                 _right.p1.y = limits->p1.y;
 275                 _right.p2.x = limits->p2.x;
 276                 _right.p2.y = limits->p2.y;
 277             }
 278
 279             if (left.p1.x >= right.p1.x)
 280                 continue;
 281
 282             if (reversed)
 283                 _borast_traps_add_trap (traps, _top, _bottom, &_right, &_left);
 284             else
 285                 _borast_traps_add_trap (traps, _top, _bottom, &_left, &_right);
 286         }
 287     } else {
 288         _borast_traps_add_trap (traps, top, bottom, &left, &right);
 289     }
 290
 291     return traps->status;
 292 }
 293
 294 void
 295 _borast_traps_translate (borast_traps_t *traps, int x, int y)
 296 {
 297     borast_fixed_t xoff, yoff;
 298     borast_trapezoid_t *t;
 299     int i;
 300
 301     /* Ugh. The borast_composite/(Render) interface doesn't allow
 302        an offset for the trapezoids. Need to manually shift all
 303        the coordinates to align with the offset origin of the
 304        intermediate surface. */
 305
 306     xoff = _borast_fixed_from_int (x);
 307     yoff = _borast_fixed_from_int (y);
 308
 309     for (i = 0, t = traps->traps; i < traps->num_traps; i++, t++) {
 310         t->top += yoff;
 311         t->bottom += yoff;
 312         t->left.p1.x += xoff;
 313         t->left.p1.y += yoff;
 314         t->left.p2.x += xoff;
 315         t->left.p2.y += yoff;
 316         t->right.p1.x += xoff;
 317         t->right.p1.y += yoff;
 318         t->right.p2.x += xoff;
 319         t->right.p2.y += yoff;
 320     }
 321 }
 322
 323 void
 324 _borast_trapezoid_array_translate_and_scale (borast_trapezoid_t *offset_traps,
 325                                             borast_trapezoid_t *src_traps,
 326                                             int num_traps,
 327                                             double tx, double ty,
 328                                             double sx, double sy)
 329 {
 330     int i;
 331     borast_fixed_t xoff = _borast_fixed_from_double (tx);
 332     borast_fixed_t yoff = _borast_fixed_from_double (ty);
 333
 334     if (sx == 1.0 && sy == 1.0) {
 335         for (i = 0; i < num_traps; i++) {
 336             offset_traps[i].top = src_traps[i].top + yoff;
 337             offset_traps[i].bottom = src_traps[i].bottom + yoff;
 338             offset_traps[i].left.p1.x = src_traps[i].left.p1.x + xoff;
 339             offset_traps[i].left.p1.y = src_traps[i].left.p1.y + yoff;
 340             offset_traps[i].left.p2.x = src_traps[i].left.p2.x + xoff;
 341             offset_traps[i].left.p2.y = src_traps[i].left.p2.y + yoff;
 342             offset_traps[i].right.p1.x = src_traps[i].right.p1.x + xoff;
 343             offset_traps[i].right.p1.y = src_traps[i].right.p1.y + yoff;
 344             offset_traps[i].right.p2.x = src_traps[i].right.p2.x + xoff;
 345             offset_traps[i].right.p2.y = src_traps[i].right.p2.y + yoff;
 346         }
 347     } else {
 348         borast_fixed_t xsc = _borast_fixed_from_double (sx);
 349         borast_fixed_t ysc = _borast_fixed_from_double (sy);
 350
 351         for (i = 0; i < num_traps; i++) {
 352             offset_traps[i].top = _borast_fixed_mul (src_traps[i].top + yoff, ysc);
 353             offset_traps[i].bottom = _borast_fixed_mul (src_traps[i].bottom + yoff, ysc);
 354             offset_traps[i].left.p1.x = _borast_fixed_mul (src_traps[i].left.p1.x + xoff, xsc);
 355             offset_traps[i].left.p1.y = _borast_fixed_mul (src_traps[i].left.p1.y + yoff, ysc);
 356             offset_traps[i].left.p2.x = _borast_fixed_mul (src_traps[i].left.p2.x + xoff, xsc);
 357             offset_traps[i].left.p2.y = _borast_fixed_mul (src_traps[i].left.p2.y + yoff, ysc);
 358             offset_traps[i].right.p1.x = _borast_fixed_mul (src_traps[i].right.p1.x + xoff, xsc);
 359             offset_traps[i].right.p1.y = _borast_fixed_mul (src_traps[i].right.p1.y + yoff, ysc);
 360             offset_traps[i].right.p2.x = _borast_fixed_mul (src_traps[i].right.p2.x + xoff, xsc);
 361             offset_traps[i].right.p2.y = _borast_fixed_mul (src_traps[i].right.p2.y + yoff, ysc);
 362         }
 363     }
 364 }
 365
 366 static borast_fixed_t
 367 _line_compute_intersection_x_for_y (const borast_line_t *line,
 368                                     borast_fixed_t y)
 369 {
 370     return _borast_edge_compute_intersection_x_for_y (&line->p1, &line->p2, y);
 371 }
 372
 373 void
 374 _borast_traps_extents (const borast_traps_t *traps,
 375                       borast_box_t *extents)
 376 {
 377     int i;
 378
 379     if (traps->num_traps == 0) {
 380         extents->p1.x = extents->p1.y = 0;
 381         extents->p2.x = extents->p2.y = 0;
 382         return;
 383     }
 384
 385     extents->p1.x = extents->p1.y = INT32_MAX;
 386     extents->p2.x = extents->p2.y = INT32_MIN;
 387
 388     for (i = 0; i < traps->num_traps; i++) {
 389         const borast_trapezoid_t *trap =  &traps->traps[i];
 390
 391         if (trap->top < extents->p1.y)
 392             extents->p1.y = trap->top;
 393         if (trap->bottom > extents->p2.y)
 394             extents->p2.y = trap->bottom;
 395
 396         if (trap->left.p1.x < extents->p1.x) {
 397             borast_fixed_t x = trap->left.p1.x;
 398             if (trap->top != trap->left.p1.y) {
 399                 x = _line_compute_intersection_x_for_y (&trap->left,
 400                                                         trap->top);
 401                 if (x < extents->p1.x)
 402                     extents->p1.x = x;
 403             } else
 404                 extents->p1.x = x;
 405         }
 406         if (trap->left.p2.x < extents->p1.x) {
 407             borast_fixed_t x = trap->left.p2.x;
 408             if (trap->bottom != trap->left.p2.y) {
 409                 x = _line_compute_intersection_x_for_y (&trap->left,
 410                                                         trap->bottom);
 411                 if (x < extents->p1.x)
 412                     extents->p1.x = x;
 413             } else
 414                 extents->p1.x = x;
 415         }
 416
 417         if (trap->right.p1.x > extents->p2.x) {
 418             borast_fixed_t x = trap->right.p1.x;
 419             if (trap->top != trap->right.p1.y) {
 420                 x = _line_compute_intersection_x_for_y (&trap->right,
 421                                                         trap->top);
 422                 if (x > extents->p2.x)
 423                     extents->p2.x = x;
 424             } else
 425                 extents->p2.x = x;
 426         }
 427         if (trap->right.p2.x > extents->p2.x) {
 428             borast_fixed_t x = trap->right.p2.x;
 429             if (trap->bottom != trap->right.p2.y) {
 430                 x = _line_compute_intersection_x_for_y (&trap->right,
 431                                                         trap->bottom);
 432                 if (x > extents->p2.x)
 433                     extents->p2.x = x;
 434             } else
 435                 extents->p2.x = x;
 436         }
 437     }
 438 }