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