Atlas - SDL_rect.c
Home / ext / SDL2 / src / video Lines: 1 | Size: 13143 bytes [Download] [Show on GitHub] [Search similar files] [Raw] [Raw (proxy)][FILE BEGIN]1/* 2 Simple DirectMedia Layer 3 Copyright (C) 1997-2018 Sam Lantinga <[email protected]> 4 5 This software is provided 'as-is', without any express or implied 6 warranty. In no event will the authors be held liable for any damages 7 arising from the use of this software. 8 9 Permission is granted to anyone to use this software for any purpose, 10 including commercial applications, and to alter it and redistribute it 11 freely, subject to the following restrictions: 12 13 1. The origin of this software must not be misrepresented; you must not 14 claim that you wrote the original software. If you use this software 15 in a product, an acknowledgment in the product documentation would be 16 appreciated but is not required. 17 2. Altered source versions must be plainly marked as such, and must not be 18 misrepresented as being the original software. 19 3. This notice may not be removed or altered from any source distribution. 20*/ 21#include "../SDL_internal.h" 22 23#include "SDL_rect.h" 24#include "SDL_rect_c.h" 25#include "SDL_assert.h" 26 27SDL_bool 28SDL_HasIntersection(const SDL_Rect * A, const SDL_Rect * B) 29{ 30 int Amin, Amax, Bmin, Bmax; 31 32 if (!A) { 33 SDL_InvalidParamError("A"); 34 return SDL_FALSE; 35 } 36 37 if (!B) { 38 SDL_InvalidParamError("B"); 39 return SDL_FALSE; 40 } 41 42 /* Special cases for empty rects */ 43 if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) { 44 return SDL_FALSE; 45 } 46 47 /* Horizontal intersection */ 48 Amin = A->x; 49 Amax = Amin + A->w; 50 Bmin = B->x; 51 Bmax = Bmin + B->w; 52 if (Bmin > Amin) 53 Amin = Bmin; 54 if (Bmax < Amax) 55 Amax = Bmax; 56 if (Amax <= Amin) 57 return SDL_FALSE; 58 59 /* Vertical intersection */ 60 Amin = A->y; 61 Amax = Amin + A->h; 62 Bmin = B->y; 63 Bmax = Bmin + B->h; 64 if (Bmin > Amin) 65 Amin = Bmin; 66 if (Bmax < Amax) 67 Amax = Bmax; 68 if (Amax <= Amin) 69 return SDL_FALSE; 70 71 return SDL_TRUE; 72} 73 74SDL_bool 75SDL_IntersectRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result) 76{ 77 int Amin, Amax, Bmin, Bmax; 78 79 if (!A) { 80 SDL_InvalidParamError("A"); 81 return SDL_FALSE; 82 } 83 84 if (!B) { 85 SDL_InvalidParamError("B"); 86 return SDL_FALSE; 87 } 88 89 if (!result) { 90 SDL_InvalidParamError("result"); 91 return SDL_FALSE; 92 } 93 94 /* Special cases for empty rects */ 95 if (SDL_RectEmpty(A) || SDL_RectEmpty(B)) { 96 result->w = 0; 97 result->h = 0; 98 return SDL_FALSE; 99 } 100 101 /* Horizontal intersection */ 102 Amin = A->x; 103 Amax = Amin + A->w; 104 Bmin = B->x; 105 Bmax = Bmin + B->w; 106 if (Bmin > Amin) 107 Amin = Bmin; 108 result->x = Amin; 109 if (Bmax < Amax) 110 Amax = Bmax; 111 result->w = Amax - Amin; 112 113 /* Vertical intersection */ 114 Amin = A->y; 115 Amax = Amin + A->h; 116 Bmin = B->y; 117 Bmax = Bmin + B->h; 118 if (Bmin > Amin) 119 Amin = Bmin; 120 result->y = Amin; 121 if (Bmax < Amax) 122 Amax = Bmax; 123 result->h = Amax - Amin; 124 125 return !SDL_RectEmpty(result); 126} 127 128void 129SDL_UnionRect(const SDL_Rect * A, const SDL_Rect * B, SDL_Rect * result) 130{ 131 int Amin, Amax, Bmin, Bmax; 132 133 if (!A) { 134 SDL_InvalidParamError("A"); 135 return; 136 } 137 138 if (!B) { 139 SDL_InvalidParamError("B"); 140 return; 141 } 142 143 if (!result) { 144 SDL_InvalidParamError("result"); 145 return; 146 } 147 148 /* Special cases for empty Rects */ 149 if (SDL_RectEmpty(A)) { 150 if (SDL_RectEmpty(B)) { 151 /* A and B empty */ 152 return; 153 } else { 154 /* A empty, B not empty */ 155 *result = *B; 156 return; 157 } 158 } else { 159 if (SDL_RectEmpty(B)) { 160 /* A not empty, B empty */ 161 *result = *A; 162 return; 163 } 164 } 165 166 /* Horizontal union */ 167 Amin = A->x; 168 Amax = Amin + A->w; 169 Bmin = B->x; 170 Bmax = Bmin + B->w; 171 if (Bmin < Amin) 172 Amin = Bmin; 173 result->x = Amin; 174 if (Bmax > Amax) 175 Amax = Bmax; 176 result->w = Amax - Amin; 177 178 /* Vertical union */ 179 Amin = A->y; 180 Amax = Amin + A->h; 181 Bmin = B->y; 182 Bmax = Bmin + B->h; 183 if (Bmin < Amin) 184 Amin = Bmin; 185 result->y = Amin; 186 if (Bmax > Amax) 187 Amax = Bmax; 188 result->h = Amax - Amin; 189} 190 191SDL_bool 192SDL_EnclosePoints(const SDL_Point * points, int count, const SDL_Rect * clip, 193 SDL_Rect * result) 194{ 195 int minx = 0; 196 int miny = 0; 197 int maxx = 0; 198 int maxy = 0; 199 int x, y, i; 200 201 if (!points) { 202 SDL_InvalidParamError("points"); 203 return SDL_FALSE; 204 } 205 206 if (count < 1) { 207 SDL_InvalidParamError("count"); 208 return SDL_FALSE; 209 } 210 211 if (clip) { 212 SDL_bool added = SDL_FALSE; 213 const int clip_minx = clip->x; 214 const int clip_miny = clip->y; 215 const int clip_maxx = clip->x+clip->w-1; 216 const int clip_maxy = clip->y+clip->h-1; 217 218 /* Special case for empty rectangle */ 219 if (SDL_RectEmpty(clip)) { 220 return SDL_FALSE; 221 } 222 223 for (i = 0; i < count; ++i) { 224 x = points[i].x; 225 y = points[i].y; 226 227 if (x < clip_minx || x > clip_maxx || 228 y < clip_miny || y > clip_maxy) { 229 continue; 230 } 231 if (!added) { 232 /* Special case: if no result was requested, we are done */ 233 if (result == NULL) { 234 return SDL_TRUE; 235 } 236 237 /* First point added */ 238 minx = maxx = x; 239 miny = maxy = y; 240 added = SDL_TRUE; 241 continue; 242 } 243 if (x < minx) { 244 minx = x; 245 } else if (x > maxx) { 246 maxx = x; 247 } 248 if (y < miny) { 249 miny = y; 250 } else if (y > maxy) { 251 maxy = y; 252 } 253 } 254 if (!added) { 255 return SDL_FALSE; 256 } 257 } else { 258 /* Special case: if no result was requested, we are done */ 259 if (result == NULL) { 260 return SDL_TRUE; 261 } 262 263 /* No clipping, always add the first point */ 264 minx = maxx = points[0].x; 265 miny = maxy = points[0].y; 266 267 for (i = 1; i < count; ++i) { 268 x = points[i].x; 269 y = points[i].y; 270 271 if (x < minx) { 272 minx = x; 273 } else if (x > maxx) { 274 maxx = x; 275 } 276 if (y < miny) { 277 miny = y; 278 } else if (y > maxy) { 279 maxy = y; 280 } 281 } 282 } 283 284 if (result) { 285 result->x = minx; 286 result->y = miny; 287 result->w = (maxx-minx)+1; 288 result->h = (maxy-miny)+1; 289 } 290 return SDL_TRUE; 291} 292 293/* Use the Cohen-Sutherland algorithm for line clipping */ 294#define CODE_BOTTOM 1 295#define CODE_TOP 2 296#define CODE_LEFT 4 297#define CODE_RIGHT 8 298 299static int 300ComputeOutCode(const SDL_Rect * rect, int x, int y) 301{ 302 int code = 0; 303 if (y < rect->y) { 304 code |= CODE_TOP; 305 } else if (y >= rect->y + rect->h) { 306 code |= CODE_BOTTOM; 307 } 308 if (x < rect->x) { 309 code |= CODE_LEFT; 310 } else if (x >= rect->x + rect->w) { 311 code |= CODE_RIGHT; 312 } 313 return code; 314} 315 316SDL_bool 317SDL_IntersectRectAndLine(const SDL_Rect * rect, int *X1, int *Y1, int *X2, 318 int *Y2) 319{ 320 int x = 0; 321 int y = 0; 322 int x1, y1; 323 int x2, y2; 324 int rectx1; 325 int recty1; 326 int rectx2; 327 int recty2; 328 int outcode1, outcode2; 329 330 if (!rect) { 331 SDL_InvalidParamError("rect"); 332 return SDL_FALSE; 333 } 334 335 if (!X1) { 336 SDL_InvalidParamError("X1"); 337 return SDL_FALSE; 338 } 339 340 if (!Y1) { 341 SDL_InvalidParamError("Y1"); 342 return SDL_FALSE; 343 } 344 345 if (!X2) { 346 SDL_InvalidParamError("X2"); 347 return SDL_FALSE; 348 } 349 350 if (!Y2) { 351 SDL_InvalidParamError("Y2"); 352 return SDL_FALSE; 353 } 354 355 /* Special case for empty rect */ 356 if (SDL_RectEmpty(rect)) { 357 return SDL_FALSE; 358 } 359 360 x1 = *X1; 361 y1 = *Y1; 362 x2 = *X2; 363 y2 = *Y2; 364 rectx1 = rect->x; 365 recty1 = rect->y; 366 rectx2 = rect->x + rect->w - 1; 367 recty2 = rect->y + rect->h - 1; 368 369 /* Check to see if entire line is inside rect */ 370 if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 && 371 y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) { 372 return SDL_TRUE; 373 } 374 375 /* Check to see if entire line is to one side of rect */ 376 if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) || 377 (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) { 378 return SDL_FALSE; 379 } 380 381 if (y1 == y2) { 382 /* Horizontal line, easy to clip */ 383 if (x1 < rectx1) { 384 *X1 = rectx1; 385 } else if (x1 > rectx2) { 386 *X1 = rectx2; 387 } 388 if (x2 < rectx1) { 389 *X2 = rectx1; 390 } else if (x2 > rectx2) { 391 *X2 = rectx2; 392 } 393 return SDL_TRUE; 394 } 395 396 if (x1 == x2) { 397 /* Vertical line, easy to clip */ 398 if (y1 < recty1) { 399 *Y1 = recty1; 400 } else if (y1 > recty2) { 401 *Y1 = recty2; 402 } 403 if (y2 < recty1) { 404 *Y2 = recty1; 405 } else if (y2 > recty2) { 406 *Y2 = recty2; 407 } 408 return SDL_TRUE; 409 } 410 411 /* More complicated Cohen-Sutherland algorithm */ 412 outcode1 = ComputeOutCode(rect, x1, y1); 413 outcode2 = ComputeOutCode(rect, x2, y2); 414 while (outcode1 || outcode2) { 415 if (outcode1 & outcode2) { 416 return SDL_FALSE; 417 } 418 419 if (outcode1) { 420 if (outcode1 & CODE_TOP) { 421 y = recty1; 422 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1); 423 } else if (outcode1 & CODE_BOTTOM) { 424 y = recty2; 425 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1); 426 } else if (outcode1 & CODE_LEFT) { 427 x = rectx1; 428 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1); 429 } else if (outcode1 & CODE_RIGHT) { 430 x = rectx2; 431 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1); 432 } 433 x1 = x; 434 y1 = y; 435 outcode1 = ComputeOutCode(rect, x, y); 436 } else { 437 if (outcode2 & CODE_TOP) { 438 y = recty1; 439 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1); 440 } else if (outcode2 & CODE_BOTTOM) { 441 y = recty2; 442 x = x1 + ((x2 - x1) * (y - y1)) / (y2 - y1); 443 } else if (outcode2 & CODE_LEFT) { 444 /* If this assertion ever fires, here's the static analysis that warned about it: 445 http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-b0d01a.html#EndPath */ 446 SDL_assert(x2 != x1); /* if equal: division by zero. */ 447 x = rectx1; 448 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1); 449 } else if (outcode2 & CODE_RIGHT) { 450 /* If this assertion ever fires, here's the static analysis that warned about it: 451 http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-39b114.html#EndPath */ 452 SDL_assert(x2 != x1); /* if equal: division by zero. */ 453 x = rectx2; 454 y = y1 + ((y2 - y1) * (x - x1)) / (x2 - x1); 455 } 456 x2 = x; 457 y2 = y; 458 outcode2 = ComputeOutCode(rect, x, y); 459 } 460 } 461 *X1 = x1; 462 *Y1 = y1; 463 *X2 = x2; 464 *Y2 = y2; 465 return SDL_TRUE; 466} 467 468SDL_bool 469SDL_GetSpanEnclosingRect(int width, int height, 470 int numrects, const SDL_Rect * rects, SDL_Rect *span) 471{ 472 int i; 473 int span_y1, span_y2; 474 int rect_y1, rect_y2; 475 476 if (width < 1) { 477 SDL_InvalidParamError("width"); 478 return SDL_FALSE; 479 } 480 481 if (height < 1) { 482 SDL_InvalidParamError("height"); 483 return SDL_FALSE; 484 } 485 486 if (!rects) { 487 SDL_InvalidParamError("rects"); 488 return SDL_FALSE; 489 } 490 491 if (!span) { 492 SDL_InvalidParamError("span"); 493 return SDL_FALSE; 494 } 495 496 if (numrects < 1) { 497 SDL_InvalidParamError("numrects"); 498 return SDL_FALSE; 499 } 500 501 /* Initialize to empty rect */ 502 span_y1 = height; 503 span_y2 = 0; 504 505 for (i = 0; i < numrects; ++i) { 506 rect_y1 = rects[i].y; 507 rect_y2 = rect_y1 + rects[i].h; 508 509 /* Clip out of bounds rectangles, and expand span rect */ 510 if (rect_y1 < 0) { 511 span_y1 = 0; 512 } else if (rect_y1 < span_y1) { 513 span_y1 = rect_y1; 514 } 515 if (rect_y2 > height) { 516 span_y2 = height; 517 } else if (rect_y2 > span_y2) { 518 span_y2 = rect_y2; 519 } 520 } 521 if (span_y2 > span_y1) { 522 span->x = 0; 523 span->y = span_y1; 524 span->w = width; 525 span->h = (span_y2 - span_y1); 526 return SDL_TRUE; 527 } 528 return SDL_FALSE; 529} 530 531/* vi: set ts=4 sw=4 expandtab: */ 532[FILE END](C) 2025 0x4248 (C) 2025 4248 Media and 4248 Systems, All part of 0x4248 See LICENCE files for more information. Not all files are by 0x4248 always check Licencing.