Mercurial > sdl-ios-xcode

comparison src/video/SDL_rect.c @ 3541:0c429a5fda8a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added an automated test for rectangle routines, currently only testing line clipping. Use the Cohen-Sutherland algorithm for line clipping which uses integer math and preserves ordering of clipped points. Removed getopt() support in testsdl.c, replaced with simple argv scanning.
author Sam Lantinga <slouken@libsdl.org>
date Fri, 11 Dec 2009 09:22:34 +0000
parents 0267b8b1595c
children 97eae5a705f9
comparison
equal deleted inserted replaced
3540:3ad09fdbfcb0 3541:0c429a5fda8a
194 result->h = (maxy-miny)+1; 194 result->h = (maxy-miny)+1;
195 } 195 }
196 return SDL_TRUE; 196 return SDL_TRUE;
197 } 197 }
198 198
199 /* Use the Cohen-Sutherland algorithm for line clipping */
200 #define CODE_BOTTOM 1
201 #define CODE_TOP 2
202 #define CODE_LEFT 4
203 #define CODE_RIGHT 8
204
205 static int ComputeOutCode(const SDL_Rect * rect, int x, int y)
206 {
207 int code = 0;
208 if (y < 0) {
209 code |= CODE_TOP;
210 } else if (y >= rect->y + rect->h) {
211 code |= CODE_BOTTOM;
212 }
213 if (x < 0) {
214 code |= CODE_LEFT;
215 } else if (x >= rect->x + rect->w) {
216 code |= CODE_RIGHT;
217 }
218 return code;
219 }
220
199 SDL_bool 221 SDL_bool
200 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2, 222 SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2,
201 int *Y2) 223 int *Y2)
202 { 224 {
225 int x, y;
203 int x1, y1; 226 int x1, y1;
204 int x2, y2; 227 int x2, y2;
205 int rectx1; 228 int rectx1;
206 int recty1; 229 int recty1;
207 int rectx2; 230 int rectx2;
208 int recty2; 231 int recty2;
232 int outcode1, outcode2;
209 233
210 if (!rect || !X1 || !Y1 || !X2 || !Y2) { 234 if (!rect || !X1 || !Y1 || !X2 || !Y2) {
211 return SDL_FALSE; 235 return SDL_FALSE;
212 } 236 }
213 237
260 *Y2 = recty2; 284 *Y2 = recty2;
261 } 285 }
262 return SDL_TRUE; 286 return SDL_TRUE;
263 } 287 }
264 288
265 else { 289 /* More complicated Cohen-Sutherland algorithm */
266 /* The task of clipping a line with finite slope ratios in a fixed- 290 outcode1 = ComputeOutCode(rect, x1, y1);
267 * precision coordinate space is not as immediately simple as it is 291 outcode2 = ComputeOutCode(rect, x2, y2);
268 * with coordinates of arbitrary precision. If the ratio of slopes 292 while (outcode1 || outcode2) {
269 * between the input line segment and the result line segment is not 293 if (outcode1 & outcode2) {
270 * a whole number, you have in fact *moved* the line segment a bit, 294 return SDL_FALSE;
271 * and there can be no avoiding it without more precision 295 }
272 */ 296
273 int *x_result_[] = { X1, X2, NULL }, **x_result = x_result_; 297 if (outcode1) {
274 int *y_result_[] = { Y1, Y2, NULL }, **y_result = y_result_; 298 if (outcode1 & CODE_TOP) {
275 SDL_bool intersection = SDL_FALSE; 299 y = recty1;
276 double b, m, left, right, bottom, top; 300 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
277 int xl, xh, yl, yh; 301 } else if (outcode1 & CODE_BOTTOM) {
278 302 y = recty2;
279 /* solve mx+b line formula */ 303 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
280 m = (double) (y1 - y2) / (double) (x1 - x2); 304 } else if (outcode1 & CODE_LEFT) {
281 b = y2 - m * (double) x2; 305 x = rectx1;
282 306 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
283 /* find some linear intersections */ 307 } else if (outcode1 & CODE_RIGHT) {
284 left = (m * (double) rectx1) + b; 308 x = rectx2;
285 right = (m * (double) rectx2) + b; 309 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
286 top = (recty1 - b) / m; 310 }
287 bottom = (recty2 - b) / m; 311 x1 = x;
288 312 y1 = y;
289 /* sort end-points' x and y components individually */ 313 outcode1 = ComputeOutCode(rect, x, y);
290 if (x1 < x2) { 314 }
291 xl = x1; 315
292 xh = x2; 316 if (outcode2) {
293 } else { 317 if (outcode2 & CODE_TOP) {
294 xl = x2; 318 y = recty1;
295 xh = x1; 319 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
296 } 320 } else if (outcode2 & CODE_BOTTOM) {
297 if (y1 < y2) { 321 y = recty2;
298 yl = y1; 322 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1);
299 yh = y2; 323 } else if (outcode2 & CODE_LEFT) {
300 } else { 324 x = rectx1;
301 yl = y2; 325 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
302 yh = y1; 326 } else if (outcode2 & CODE_RIGHT) {
303 } 327 x = rectx2;
304 328 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1);
305 #define RISING(a, b, c) (((a)<=(b))&&((b)<=(c))) 329 }
306 330 x2 = x;
307 /* check for a point that's entirely inside the rect */ 331 y2 = y;
308 if (RISING(rectx1, x1, rectx2) && RISING(recty1, y1, recty2)) { 332 outcode2 = ComputeOutCode(rect, x, y);
309 x_result++; 333 }
310 y_result++; 334 }
311 intersection = SDL_TRUE; 335 *X1 = x1;
312 } else 336 *Y1 = y1;
313 /* it was determined earlier that *both* end-points are not contained */ 337 *X2 = x2;
314 if (RISING(rectx1, x2, rectx2) && RISING(recty1, y2, recty2)) { 338 *Y2 = y2;
315 **(x_result++) = x2; 339 return SDL_TRUE;
316 **(y_result++) = y2;
317 intersection = SDL_TRUE;
318 }
319
320 if (RISING(recty1, left, recty2) && RISING(xl, rectx1, xh)) {
321 **(x_result++) = rectx1;
322 **(y_result++) = (int) left;
323 intersection = SDL_TRUE;
324 }
325
326 if (*x_result == NULL)
327 return intersection;
328 if (RISING(recty1, right, recty2) && RISING(xl, rectx2, xh)) {
329 **(x_result++) = rectx2;
330 **(y_result++) = (int) right;
331 intersection = SDL_TRUE;
332 }
333
334 if (*x_result == NULL)
335 return intersection;
336 if (RISING(rectx1, top, rectx2) && RISING(yl, recty1, yh)) {
337 **(x_result++) = (int) top;
338 **(y_result++) = recty1;
339 intersection = SDL_TRUE;
340 }
341
342 if (*x_result == NULL)
343 return intersection;
344 if (RISING(rectx1, bottom, rectx2) && RISING(yl, recty2, yh)) {
345 **(x_result++) = (int) bottom;
346 **(y_result++) = recty2;
347 intersection = SDL_TRUE;
348 }
349
350 return intersection;
351 }
352
353 return SDL_FALSE;
354 } 340 }
355 341
356 void 342 void
357 SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect) 343 SDL_AddDirtyRect(SDL_DirtyRectList * list, const SDL_Rect * rect)
358 { 344 {