1/*
2 Simple DirectMedia Layer
3 Copyright (C) 1997-2025 Sam Lantinga <slouken@libsdl.org>
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
22// This file is #included twice to support int and float versions with the same code.
23
24static bool SDL_RECT_CAN_OVERFLOW(const RECTTYPE *rect)
25{
26 if (rect->x <= (SCALARTYPE)(SDL_MIN_SINT32 / 2) ||
27 rect->x >= (SCALARTYPE)(SDL_MAX_SINT32 / 2) ||
28 rect->y <= (SCALARTYPE)(SDL_MIN_SINT32 / 2) ||
29 rect->y >= (SCALARTYPE)(SDL_MAX_SINT32 / 2) ||
30 rect->w >= (SCALARTYPE)(SDL_MAX_SINT32 / 2) ||
31 rect->h >= (SCALARTYPE)(SDL_MAX_SINT32 / 2)) {
32 return true;
33 }
34 return false;
35}
36
37bool SDL_HASINTERSECTION(const RECTTYPE *A, const RECTTYPE *B)
38{
39 SCALARTYPE Amin, Amax, Bmin, Bmax;
40
41 if (!A) {
42 SDL_InvalidParamError("A");
43 return false;
44 } else if (!B) {
45 SDL_InvalidParamError("B");
46 return false;
47 } else if (SDL_RECT_CAN_OVERFLOW(A) ||
48 SDL_RECT_CAN_OVERFLOW(B)) {
49 SDL_SetError("Potential rect math overflow");
50 return false;
51 } else if (SDL_RECTEMPTY(A) || SDL_RECTEMPTY(B)) {
52 return false; // Special cases for empty rects
53 }
54
55 // Horizontal intersection
56 Amin = A->x;
57 Amax = Amin + A->w;
58 Bmin = B->x;
59 Bmax = Bmin + B->w;
60 if (Bmin > Amin) {
61 Amin = Bmin;
62 }
63 if (Bmax < Amax) {
64 Amax = Bmax;
65 }
66 if ((Amax - ENCLOSEPOINTS_EPSILON) < Amin) {
67 return false;
68 }
69 // Vertical intersection
70 Amin = A->y;
71 Amax = Amin + A->h;
72 Bmin = B->y;
73 Bmax = Bmin + B->h;
74 if (Bmin > Amin) {
75 Amin = Bmin;
76 }
77 if (Bmax < Amax) {
78 Amax = Bmax;
79 }
80 if ((Amax - ENCLOSEPOINTS_EPSILON) < Amin) {
81 return false;
82 }
83 return true;
84}
85
86bool SDL_INTERSECTRECT(const RECTTYPE *A, const RECTTYPE *B, RECTTYPE *result)
87{
88 SCALARTYPE Amin, Amax, Bmin, Bmax;
89
90 if (!A) {
91 SDL_InvalidParamError("A");
92 return false;
93 } else if (!B) {
94 SDL_InvalidParamError("B");
95 return false;
96 } else if (SDL_RECT_CAN_OVERFLOW(A) ||
97 SDL_RECT_CAN_OVERFLOW(B)) {
98 SDL_SetError("Potential rect math overflow");
99 return false;
100 } else if (!result) {
101 SDL_InvalidParamError("result");
102 return false;
103 } else if (SDL_RECTEMPTY(A) || SDL_RECTEMPTY(B)) { // Special cases for empty rects
104 result->w = 0;
105 result->h = 0;
106 return false;
107 }
108
109 // Horizontal intersection
110 Amin = A->x;
111 Amax = Amin + A->w;
112 Bmin = B->x;
113 Bmax = Bmin + B->w;
114 if (Bmin > Amin) {
115 Amin = Bmin;
116 }
117 result->x = Amin;
118 if (Bmax < Amax) {
119 Amax = Bmax;
120 }
121 result->w = Amax - Amin;
122
123 // Vertical intersection
124 Amin = A->y;
125 Amax = Amin + A->h;
126 Bmin = B->y;
127 Bmax = Bmin + B->h;
128 if (Bmin > Amin) {
129 Amin = Bmin;
130 }
131 result->y = Amin;
132 if (Bmax < Amax) {
133 Amax = Bmax;
134 }
135 result->h = Amax - Amin;
136
137 return !SDL_RECTEMPTY(result);
138}
139
140bool SDL_UNIONRECT(const RECTTYPE *A, const RECTTYPE *B, RECTTYPE *result)
141{
142 SCALARTYPE Amin, Amax, Bmin, Bmax;
143
144 if (!A) {
145 return SDL_InvalidParamError("A");
146 } else if (!B) {
147 return SDL_InvalidParamError("B");
148 } else if (SDL_RECT_CAN_OVERFLOW(A) ||
149 SDL_RECT_CAN_OVERFLOW(B)) {
150 return SDL_SetError("Potential rect math overflow");
151 } else if (!result) {
152 return SDL_InvalidParamError("result");
153 } else if (SDL_RECTEMPTY(A)) { // Special cases for empty Rects
154 if (SDL_RECTEMPTY(B)) { // A and B empty
155 SDL_zerop(result);
156 } else { // A empty, B not empty
157 *result = *B;
158 }
159 return true;
160 } else if (SDL_RECTEMPTY(B)) { // A not empty, B empty
161 *result = *A;
162 return true;
163 }
164
165 // Horizontal union
166 Amin = A->x;
167 Amax = Amin + A->w;
168 Bmin = B->x;
169 Bmax = Bmin + B->w;
170 if (Bmin < Amin) {
171 Amin = Bmin;
172 }
173 result->x = Amin;
174 if (Bmax > Amax) {
175 Amax = Bmax;
176 }
177 result->w = Amax - Amin;
178
179 // Vertical union
180 Amin = A->y;
181 Amax = Amin + A->h;
182 Bmin = B->y;
183 Bmax = Bmin + B->h;
184 if (Bmin < Amin) {
185 Amin = Bmin;
186 }
187 result->y = Amin;
188 if (Bmax > Amax) {
189 Amax = Bmax;
190 }
191 result->h = Amax - Amin;
192 return true;
193}
194
195bool SDL_ENCLOSEPOINTS(const POINTTYPE *points, int count, const RECTTYPE *clip, RECTTYPE *result)
196{
197 SCALARTYPE minx = 0;
198 SCALARTYPE miny = 0;
199 SCALARTYPE maxx = 0;
200 SCALARTYPE maxy = 0;
201 SCALARTYPE x, y;
202 int i;
203
204 if (!points) {
205 SDL_InvalidParamError("points");
206 return false;
207 } else if (count < 1) {
208 SDL_InvalidParamError("count");
209 return false;
210 }
211
212 if (clip) {
213 bool added = false;
214 const SCALARTYPE clip_minx = clip->x;
215 const SCALARTYPE clip_miny = clip->y;
216 const SCALARTYPE clip_maxx = clip->x + clip->w - ENCLOSEPOINTS_EPSILON;
217 const SCALARTYPE clip_maxy = clip->y + clip->h - ENCLOSEPOINTS_EPSILON;
218
219 // Special case for empty rectangle
220 if (SDL_RECTEMPTY(clip)) {
221 return false;
222 }
223
224 for (i = 0; i < count; ++i) {
225 x = points[i].x;
226 y = points[i].y;
227
228 if (x < clip_minx || x > clip_maxx ||
229 y < clip_miny || y > clip_maxy) {
230 continue;
231 }
232 if (!added) {
233 // Special case: if no result was requested, we are done
234 if (!result) {
235 return true;
236 }
237
238 // First point added
239 minx = maxx = x;
240 miny = maxy = y;
241 added = true;
242 continue;
243 }
244 if (x < minx) {
245 minx = x;
246 } else if (x > maxx) {
247 maxx = x;
248 }
249 if (y < miny) {
250 miny = y;
251 } else if (y > maxy) {
252 maxy = y;
253 }
254 }
255 if (!added) {
256 return false;
257 }
258 } else {
259 // Special case: if no result was requested, we are done
260 if (!result) {
261 return true;
262 }
263
264 // No clipping, always add the first point
265 minx = maxx = points[0].x;
266 miny = maxy = points[0].y;
267
268 for (i = 1; i < count; ++i) {
269 x = points[i].x;
270 y = points[i].y;
271
272 if (x < minx) {
273 minx = x;
274 } else if (x > maxx) {
275 maxx = x;
276 }
277 if (y < miny) {
278 miny = y;
279 } else if (y > maxy) {
280 maxy = y;
281 }
282 }
283 }
284
285 if (result) {
286 result->x = minx;
287 result->y = miny;
288 result->w = (maxx - minx) + ENCLOSEPOINTS_EPSILON;
289 result->h = (maxy - miny) + ENCLOSEPOINTS_EPSILON;
290 }
291 return true;
292}
293
294// Use the Cohen-Sutherland algorithm for line clipping
295static int COMPUTEOUTCODE(const RECTTYPE *rect, SCALARTYPE x, SCALARTYPE y)
296{
297 int code = 0;
298 if (y < rect->y) {
299 code |= CODE_TOP;
300 } else if (y > (rect->y + rect->h - ENCLOSEPOINTS_EPSILON)) {
301 code |= CODE_BOTTOM;
302 }
303 if (x < rect->x) {
304 code |= CODE_LEFT;
305 } else if (x > (rect->x + rect->w - ENCLOSEPOINTS_EPSILON)) {
306 code |= CODE_RIGHT;
307 }
308 return code;
309}
310
311bool SDL_INTERSECTRECTANDLINE(const RECTTYPE *rect, SCALARTYPE *X1, SCALARTYPE *Y1, SCALARTYPE *X2, SCALARTYPE *Y2)
312{
313 SCALARTYPE x = 0;
314 SCALARTYPE y = 0;
315 SCALARTYPE x1, y1;
316 SCALARTYPE x2, y2;
317 SCALARTYPE rectx1;
318 SCALARTYPE recty1;
319 SCALARTYPE rectx2;
320 SCALARTYPE recty2;
321 int outcode1, outcode2;
322
323 if (!rect) {
324 SDL_InvalidParamError("rect");
325 return false;
326 } else if (SDL_RECT_CAN_OVERFLOW(rect)) {
327 SDL_SetError("Potential rect math overflow");
328 return false;
329 } else if (!X1) {
330 SDL_InvalidParamError("X1");
331 return false;
332 } else if (!Y1) {
333 SDL_InvalidParamError("Y1");
334 return false;
335 } else if (!X2) {
336 SDL_InvalidParamError("X2");
337 return false;
338 } else if (!Y2) {
339 SDL_InvalidParamError("Y2");
340 return false;
341 } else if (SDL_RECTEMPTY(rect)) {
342 return false; // Special case for empty rect
343 }
344
345 x1 = *X1;
346 y1 = *Y1;
347 x2 = *X2;
348 y2 = *Y2;
349 rectx1 = rect->x;
350 recty1 = rect->y;
351 rectx2 = rect->x + rect->w - ENCLOSEPOINTS_EPSILON;
352 recty2 = rect->y + rect->h - ENCLOSEPOINTS_EPSILON;
353
354 // Check to see if entire line is inside rect
355 if (x1 >= rectx1 && x1 <= rectx2 && x2 >= rectx1 && x2 <= rectx2 &&
356 y1 >= recty1 && y1 <= recty2 && y2 >= recty1 && y2 <= recty2) {
357 return true;
358 }
359
360 // Check to see if entire line is to one side of rect
361 if ((x1 < rectx1 && x2 < rectx1) || (x1 > rectx2 && x2 > rectx2) ||
362 (y1 < recty1 && y2 < recty1) || (y1 > recty2 && y2 > recty2)) {
363 return false;
364 }
365
366 if (y1 == y2) { // Horizontal line, easy to clip
367 if (x1 < rectx1) {
368 *X1 = rectx1;
369 } else if (x1 > rectx2) {
370 *X1 = rectx2;
371 }
372 if (x2 < rectx1) {
373 *X2 = rectx1;
374 } else if (x2 > rectx2) {
375 *X2 = rectx2;
376 }
377 return true;
378 }
379
380 if (x1 == x2) { // Vertical line, easy to clip
381 if (y1 < recty1) {
382 *Y1 = recty1;
383 } else if (y1 > recty2) {
384 *Y1 = recty2;
385 }
386 if (y2 < recty1) {
387 *Y2 = recty1;
388 } else if (y2 > recty2) {
389 *Y2 = recty2;
390 }
391 return true;
392 }
393
394 // More complicated Cohen-Sutherland algorithm
395 outcode1 = COMPUTEOUTCODE(rect, x1, y1);
396 outcode2 = COMPUTEOUTCODE(rect, x2, y2);
397 while (outcode1 || outcode2) {
398 if (outcode1 & outcode2) {
399 return false;
400 }
401
402 if (outcode1) {
403 if (outcode1 & CODE_TOP) {
404 y = recty1;
405 x = (SCALARTYPE) (x1 + ((BIGSCALARTYPE)(x2 - x1) * (y - y1)) / (y2 - y1));
406 } else if (outcode1 & CODE_BOTTOM) {
407 y = recty2;
408 x = (SCALARTYPE) (x1 + ((BIGSCALARTYPE)(x2 - x1) * (y - y1)) / (y2 - y1));
409 } else if (outcode1 & CODE_LEFT) {
410 x = rectx1;
411 y = (SCALARTYPE) (y1 + ((BIGSCALARTYPE)(y2 - y1) * (x - x1)) / (x2 - x1));
412 } else if (outcode1 & CODE_RIGHT) {
413 x = rectx2;
414 y = (SCALARTYPE) (y1 + ((BIGSCALARTYPE)(y2 - y1) * (x - x1)) / (x2 - x1));
415 }
416 x1 = x;
417 y1 = y;
418 outcode1 = COMPUTEOUTCODE(rect, x, y);
419 } else {
420 if (outcode2 & CODE_TOP) {
421 SDL_assert(y2 != y1); // if equal: division by zero.
422 y = recty1;
423 x = (SCALARTYPE) (x1 + ((BIGSCALARTYPE)(x2 - x1) * (y - y1)) / (y2 - y1));
424 } else if (outcode2 & CODE_BOTTOM) {
425 SDL_assert(y2 != y1); // if equal: division by zero.
426 y = recty2;
427 x = (SCALARTYPE) (x1 + ((BIGSCALARTYPE)(x2 - x1) * (y - y1)) / (y2 - y1));
428 } else if (outcode2 & CODE_LEFT) {
429 /* If this assertion ever fires, here's the static analysis that warned about it:
430 http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-b0d01a.html#EndPath */
431 SDL_assert(x2 != x1); // if equal: division by zero.
432 x = rectx1;
433 y = (SCALARTYPE) (y1 + ((BIGSCALARTYPE)(y2 - y1) * (x - x1)) / (x2 - x1));
434 } else if (outcode2 & CODE_RIGHT) {
435 /* If this assertion ever fires, here's the static analysis that warned about it:
436 http://buildbot.libsdl.org/sdl-static-analysis/sdl-macosx-static-analysis/sdl-macosx-static-analysis-1101/report-39b114.html#EndPath */
437 SDL_assert(x2 != x1); // if equal: division by zero.
438 x = rectx2;
439 y = (SCALARTYPE) (y1 + ((BIGSCALARTYPE)(y2 - y1) * (x - x1)) / (x2 - x1));
440 }
441 x2 = x;
442 y2 = y;
443 outcode2 = COMPUTEOUTCODE(rect, x, y);
444 }
445 }
446 *X1 = x1;
447 *Y1 = y1;
448 *X2 = x2;
449 *Y2 = y2;
450 return true;
451}
452
453#undef RECTTYPE
454#undef POINTTYPE
455#undef SCALARTYPE
456#undef BIGSCALARTYPE
457#undef COMPUTEOUTCODE
458#undef ENCLOSEPOINTS_EPSILON
459#undef SDL_RECT_CAN_OVERFLOW
460#undef SDL_HASINTERSECTION
461#undef SDL_INTERSECTRECT
462#undef SDL_RECTEMPTY
463#undef SDL_UNIONRECT
464#undef SDL_ENCLOSEPOINTS
465#undef SDL_INTERSECTRECTANDLINE
466