src/vertex-clipping.c

   1 /*
   2  * Copyright © 2012 Intel Corporation
   3  *
   4  * Permission to use, copy, modify, distribute, and sell this software and
   5  * its documentation for any purpose is hereby granted without fee, provided
   6  * that the above copyright notice appear in all copies and that both that
   7  * copyright notice and this permission notice appear in supporting
   8  * documentation, and that the name of the copyright holders not be used in
   9  * advertising or publicity pertaining to distribution of the software
  10  * without specific, written prior permission.  The copyright holders make
  11  * no representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
  15  * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  16  * FITNESS, IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY
  17  * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
  18  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
  19  * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  20  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  21  */
  22 #include <assert.h>
  23 #include <float.h>
  24 #include <math.h>
  25
  26 #include "vertex-clipping.h"
  27
  28 float
  29 float_difference(float a, float b)
  30 {
  31         /* http://www.altdevblogaday.com/2012/02/22/comparing-floating-point-numbers-2012-edition/ */
  32         static const float max_diff = 4.0f * FLT_MIN;
  33         static const float max_rel_diff = 4.0e-5;
  34         float diff = a - b;
  35         float adiff = fabsf(diff);
  36
  37         if (adiff <= max_diff)
  38                 return 0.0f;
  39
  40         a = fabsf(a);
  41         b = fabsf(b);
  42         if (adiff <= (a > b ? a : b) * max_rel_diff)
  43                 return 0.0f;
  44
  45         return diff;
  46 }
  47
  48 /* A line segment (p1x, p1y)-(p2x, p2y) intersects the line x = x_arg.
  49  * Compute the y coordinate of the intersection.
  50  */
  51 static float
  52 clip_intersect_y(float p1x, float p1y, float p2x, float p2y,
  53                  float x_arg)
  54 {
  55         float a;
  56         float diff = float_difference(p1x, p2x);
  57
  58         /* Practically vertical line segment, yet the end points have already
  59          * been determined to be on different sides of the line. Therefore
  60          * the line segment is part of the line and intersects everywhere.
  61          * Return the end point, so we use the whole line segment.
  62          */
  63         if (diff == 0.0f)
  64                 return p2y;
  65
  66         a = (x_arg - p2x) / diff;
  67         return p2y + (p1y - p2y) * a;
  68 }
  69
  70 /* A line segment (p1x, p1y)-(p2x, p2y) intersects the line y = y_arg.
  71  * Compute the x coordinate of the intersection.
  72  */
  73 static float
  74 clip_intersect_x(float p1x, float p1y, float p2x, float p2y,
  75                  float y_arg)
  76 {
  77         float a;
  78         float diff = float_difference(p1y, p2y);
  79
  80         /* Practically horizontal line segment, yet the end points have already
  81          * been determined to be on different sides of the line. Therefore
  82          * the line segment is part of the line and intersects everywhere.
  83          * Return the end point, so we use the whole line segment.
  84          */
  85         if (diff == 0.0f)
  86                 return p2x;
  87
  88         a = (y_arg - p2y) / diff;
  89         return p2x + (p1x - p2x) * a;
  90 }
  91
  92 enum path_transition {
  93         PATH_TRANSITION_OUT_TO_OUT = 0,
  94         PATH_TRANSITION_OUT_TO_IN = 1,
  95         PATH_TRANSITION_IN_TO_OUT = 2,
  96         PATH_TRANSITION_IN_TO_IN = 3,
  97 };
  98
  99 static void
 100 clip_append_vertex(struct clip_context *ctx, float x, float y)
 101 {
 102         *ctx->vertices.x++ = x;
 103         *ctx->vertices.y++ = y;
 104 }
 105
 106 static enum path_transition
 107 path_transition_left_edge(struct clip_context *ctx, float x, float y)
 108 {
 109         return ((ctx->prev.x >= ctx->clip.x1) << 1) | (x >= ctx->clip.x1);
 110 }
 111
 112 static enum path_transition
 113 path_transition_right_edge(struct clip_context *ctx, float x, float y)
 114 {
 115         return ((ctx->prev.x < ctx->clip.x2) << 1) | (x < ctx->clip.x2);
 116 }
 117
 118 static enum path_transition
 119 path_transition_top_edge(struct clip_context *ctx, float x, float y)
 120 {
 121         return ((ctx->prev.y >= ctx->clip.y1) << 1) | (y >= ctx->clip.y1);
 122 }
 123
 124 static enum path_transition
 125 path_transition_bottom_edge(struct clip_context *ctx, float x, float y)
 126 {
 127         return ((ctx->prev.y < ctx->clip.y2) << 1) | (y < ctx->clip.y2);
 128 }
 129
 130 static void
 131 clip_polygon_leftright(struct clip_context *ctx,
 132                        enum path_transition transition,
 133                        float x, float y, float clip_x)
 134 {
 135         float yi;
 136
 137         switch (transition) {
 138         case PATH_TRANSITION_IN_TO_IN:
 139                 clip_append_vertex(ctx, x, y);
 140                 break;
 141         case PATH_TRANSITION_IN_TO_OUT:
 142                 yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
 143                 clip_append_vertex(ctx, clip_x, yi);
 144                 break;
 145         case PATH_TRANSITION_OUT_TO_IN:
 146                 yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
 147                 clip_append_vertex(ctx, clip_x, yi);
 148                 clip_append_vertex(ctx, x, y);
 149                 break;
 150         case PATH_TRANSITION_OUT_TO_OUT:
 151                 /* nothing */
 152                 break;
 153         default:
 154                 assert(0 && "bad enum path_transition");
 155         }
 156
 157         ctx->prev.x = x;
 158         ctx->prev.y = y;
 159 }
 160
 161 static void
 162 clip_polygon_topbottom(struct clip_context *ctx,
 163                        enum path_transition transition,
 164                        float x, float y, float clip_y)
 165 {
 166         float xi;
 167
 168         switch (transition) {
 169         case PATH_TRANSITION_IN_TO_IN:
 170                 clip_append_vertex(ctx, x, y);
 171                 break;
 172         case PATH_TRANSITION_IN_TO_OUT:
 173                 xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
 174                 clip_append_vertex(ctx, xi, clip_y);
 175                 break;
 176         case PATH_TRANSITION_OUT_TO_IN:
 177                 xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
 178                 clip_append_vertex(ctx, xi, clip_y);
 179                 clip_append_vertex(ctx, x, y);
 180                 break;
 181         case PATH_TRANSITION_OUT_TO_OUT:
 182                 /* nothing */
 183                 break;
 184         default:
 185                 assert(0 && "bad enum path_transition");
 186         }
 187
 188         ctx->prev.x = x;
 189         ctx->prev.y = y;
 190 }
 191
 192 static void
 193 clip_context_prepare(struct clip_context *ctx, const struct polygon8 *src,
 194                       float *dst_x, float *dst_y)
 195 {
 196         ctx->prev.x = src->x[src->n - 1];
 197         ctx->prev.y = src->y[src->n - 1];
 198         ctx->vertices.x = dst_x;
 199         ctx->vertices.y = dst_y;
 200 }
 201
 202 static int
 203 clip_polygon_left(struct clip_context *ctx, const struct polygon8 *src,
 204                   float *dst_x, float *dst_y)
 205 {
 206         enum path_transition trans;
 207         int i;
 208
 209         if (src->n < 2)
 210                 return 0;
 211
 212         clip_context_prepare(ctx, src, dst_x, dst_y);
 213         for (i = 0; i < src->n; i++) {
 214                 trans = path_transition_left_edge(ctx, src->x[i], src->y[i]);
 215                 clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
 216                                        ctx->clip.x1);
 217         }
 218         return ctx->vertices.x - dst_x;
 219 }
 220
 221 static int
 222 clip_polygon_right(struct clip_context *ctx, const struct polygon8 *src,
 223                    float *dst_x, float *dst_y)
 224 {
 225         enum path_transition trans;
 226         int i;
 227
 228         if (src->n < 2)
 229                 return 0;
 230
 231         clip_context_prepare(ctx, src, dst_x, dst_y);
 232         for (i = 0; i < src->n; i++) {
 233                 trans = path_transition_right_edge(ctx, src->x[i], src->y[i]);
 234                 clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
 235                                        ctx->clip.x2);
 236         }
 237         return ctx->vertices.x - dst_x;
 238 }
 239
 240 static int
 241 clip_polygon_top(struct clip_context *ctx, const struct polygon8 *src,
 242                  float *dst_x, float *dst_y)
 243 {
 244         enum path_transition trans;
 245         int i;
 246
 247         if (src->n < 2)
 248                 return 0;
 249
 250         clip_context_prepare(ctx, src, dst_x, dst_y);
 251         for (i = 0; i < src->n; i++) {
 252                 trans = path_transition_top_edge(ctx, src->x[i], src->y[i]);
 253                 clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
 254                                        ctx->clip.y1);
 255         }
 256         return ctx->vertices.x - dst_x;
 257 }
 258
 259 static int
 260 clip_polygon_bottom(struct clip_context *ctx, const struct polygon8 *src,
 261                     float *dst_x, float *dst_y)
 262 {
 263         enum path_transition trans;
 264         int i;
 265
 266         if (src->n < 2)
 267                 return 0;
 268
 269         clip_context_prepare(ctx, src, dst_x, dst_y);
 270         for (i = 0; i < src->n; i++) {
 271                 trans = path_transition_bottom_edge(ctx, src->x[i], src->y[i]);
 272                 clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
 273                                        ctx->clip.y2);
 274         }
 275         return ctx->vertices.x - dst_x;
 276 }
 277
 278 #define max(a, b) (((a) > (b)) ? (a) : (b))
 279 #define min(a, b) (((a) > (b)) ? (b) : (a))
 280 #define clip(x, a, b)  min(max(x, a), b)
 281
 282 int
 283 clip_simple(struct clip_context *ctx,
 284             struct polygon8 *surf,
 285             float *ex,
 286             float *ey)
 287 {
 288         int i;
 289         for (i = 0; i < surf->n; i++) {
 290                 ex[i] = clip(surf->x[i], ctx->clip.x1, ctx->clip.x2);
 291                 ey[i] = clip(surf->y[i], ctx->clip.y1, ctx->clip.y2);
 292         }
 293         return surf->n;
 294 }
 295
 296 int
 297 clip_transformed(struct clip_context *ctx,
 298                  struct polygon8 *surf,
 299                  float *ex,
 300                  float *ey)
 301 {
 302         struct polygon8 polygon;
 303         int i, n;
 304
 305         polygon.n = clip_polygon_left(ctx, surf, polygon.x, polygon.y);
 306         surf->n = clip_polygon_right(ctx, &polygon, surf->x, surf->y);
 307         polygon.n = clip_polygon_top(ctx, surf, polygon.x, polygon.y);
 308         surf->n = clip_polygon_bottom(ctx, &polygon, surf->x, surf->y);
 309
 310         /* Get rid of duplicate vertices */
 311         ex[0] = surf->x[0];
 312         ey[0] = surf->y[0];
 313         n = 1;
 314         for (i = 1; i < surf->n; i++) {
 315                 if (float_difference(ex[n - 1], surf->x[i]) == 0.0f &&
 316                     float_difference(ey[n - 1], surf->y[i]) == 0.0f)
 317                         continue;
 318                 ex[n] = surf->x[i];
 319                 ey[n] = surf->y[i];
 320                 n++;
 321         }
 322         if (float_difference(ex[n - 1], surf->x[0]) == 0.0f &&
 323             float_difference(ey[n - 1], surf->y[0]) == 0.0f)
 324                 n--;
 325
 326         return n;
 327 }