use 'bool' for BLI_/BKE_ functions.
[blender.git] / source / blender / blenlib / intern / rct.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  *
27  */
28
29 /** \file blender/blenlib/intern/rct.c
30  *  \ingroup bli
31  *
32  * A minimalist lib for functions doing stuff with rectangle structs.
33  */
34
35 #include <stdio.h>
36 #include <math.h>
37
38 #include <limits.h>
39 #include <float.h>
40
41 #include "DNA_vec_types.h"
42 #include "BLI_rect.h"
43
44 /**
45  * Determine if a rect is empty. An empty
46  * rect is one with a zero (or negative)
47  * width or height.
48  *
49  * \return True if \a rect is empty.
50  */
51 bool BLI_rcti_is_empty(const rcti *rect)
52 {
53         return ((rect->xmax <= rect->xmin) || (rect->ymax <= rect->ymin));
54 }
55
56 bool BLI_rctf_is_empty(const rctf *rect)
57 {
58         return ((rect->xmax <= rect->xmin) || (rect->ymax <= rect->ymin));
59 }
60
61 bool BLI_rcti_isect_pt(const rcti *rect, const int x, const int y)
62 {
63         if (x < rect->xmin) return false;
64         if (x > rect->xmax) return false;
65         if (y < rect->ymin) return false;
66         if (y > rect->ymax) return false;
67         return true;
68 }
69
70 /**
71  * Determine if a rect is empty. An empty
72  * rect is one with a zero (or negative)
73  * width or height.
74  *
75  * \return True if \a rect is empty.
76  */
77 bool BLI_rcti_isect_pt_v(const rcti *rect, const int xy[2])
78 {
79         if (xy[0] < rect->xmin) return false;
80         if (xy[0] > rect->xmax) return false;
81         if (xy[1] < rect->ymin) return false;
82         if (xy[1] > rect->ymax) return false;
83         return true;
84 }
85
86 bool BLI_rctf_isect_pt(const rctf *rect, const float x, const float y)
87 {
88         if (x < rect->xmin) return false;
89         if (x > rect->xmax) return false;
90         if (y < rect->ymin) return false;
91         if (y > rect->ymax) return false;
92         return true;
93 }
94
95 bool BLI_rctf_isect_pt_v(const rctf *rect, const float xy[2])
96 {
97         if (xy[0] < rect->xmin) return false;
98         if (xy[0] > rect->xmax) return false;
99         if (xy[1] < rect->ymin) return false;
100         if (xy[1] > rect->ymax) return false;
101         return true;
102 }
103
104 /* based closely on 'isect_line_line_v2_int', but in modified so corner cases are treated as intersections */
105 static int isect_segments_i(const int v1[2], const int v2[2], const int v3[2], const int v4[2])
106 {
107         const double div = (double)((v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]));
108         if (div == 0.0) {
109                 return 1; /* co-linear */
110         }
111         else {
112                 const double lambda = (double)((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
113                 const double mu    = (double)((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
114                 return (lambda >= 0.0 && lambda <= 1.0 && mu >= 0.0 && mu <= 1.0);
115         }
116 }
117 static int isect_segments_fl(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
118 {
119         const double div = (double)((v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]));
120         if (div == 0.0) {
121                 return 1; /* co-linear */
122         }
123         else {
124                 const double lambda = (double)((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
125                 const double mu    = (double)((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
126                 return (lambda >= 0.0 && lambda <= 1.0 && mu >= 0.0 && mu <= 1.0);
127         }
128 }
129
130 bool BLI_rcti_isect_segment(const rcti *rect, const int s1[2], const int s2[2])
131 {
132         /* first do outside-bounds check for both points of the segment */
133         if (s1[0] < rect->xmin && s2[0] < rect->xmin) return false;
134         if (s1[0] > rect->xmax && s2[0] > rect->xmax) return false;
135         if (s1[1] < rect->ymin && s2[1] < rect->ymin) return false;
136         if (s1[1] > rect->ymax && s2[1] > rect->ymax) return false;
137
138         /* if either points intersect then we definetly intersect */
139         if (BLI_rcti_isect_pt_v(rect, s1) || BLI_rcti_isect_pt_v(rect, s2)) {
140                 return true;
141         }
142         else {
143                 /* both points are outside but may insersect the rect */
144                 int tvec1[2];
145                 int tvec2[2];
146                 /* diagonal: [/] */
147                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymin;
148                 tvec2[0] = rect->xmin; tvec2[1] = rect->ymax;
149                 if (isect_segments_i(s1, s2, tvec1, tvec2)) {
150                         return true;
151                 }
152
153                 /* diagonal: [\] */
154                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymax;
155                 tvec2[0] = rect->xmax; tvec2[1] = rect->ymin;
156                 if (isect_segments_i(s1, s2, tvec1, tvec2)) {
157                         return true;
158                 }
159
160                 /* no intersection */
161                 return false;
162         }
163 }
164
165 bool BLI_rctf_isect_segment(const rctf *rect, const float s1[2], const float s2[2])
166 {
167         /* first do outside-bounds check for both points of the segment */
168         if (s1[0] < rect->xmin && s2[0] < rect->xmin) return false;
169         if (s1[0] > rect->xmax && s2[0] > rect->xmax) return false;
170         if (s1[1] < rect->ymin && s2[1] < rect->ymin) return false;
171         if (s1[1] > rect->ymax && s2[1] > rect->ymax) return false;
172
173         /* if either points intersect then we definetly intersect */
174         if (BLI_rctf_isect_pt_v(rect, s1) || BLI_rctf_isect_pt_v(rect, s2)) {
175                 return true;
176         }
177         else {
178                 /* both points are outside but may insersect the rect */
179                 float tvec1[2];
180                 float tvec2[2];
181                 /* diagonal: [/] */
182                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymin;
183                 tvec2[0] = rect->xmin; tvec2[1] = rect->ymax;
184                 if (isect_segments_fl(s1, s2, tvec1, tvec2)) {
185                         return true;
186                 }
187
188                 /* diagonal: [\] */
189                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymax;
190                 tvec2[0] = rect->xmax; tvec2[1] = rect->ymin;
191                 if (isect_segments_fl(s1, s2, tvec1, tvec2)) {
192                         return true;
193                 }
194
195                 /* no intersection */
196                 return false;
197         }
198 }
199
200 void BLI_rctf_union(rctf *rct1, const rctf *rct2)
201 {
202         if (rct1->xmin > rct2->xmin) rct1->xmin = rct2->xmin;
203         if (rct1->xmax < rct2->xmax) rct1->xmax = rct2->xmax;
204         if (rct1->ymin > rct2->ymin) rct1->ymin = rct2->ymin;
205         if (rct1->ymax < rct2->ymax) rct1->ymax = rct2->ymax;
206 }
207
208 void BLI_rcti_union(rcti *rct1, const rcti *rct2)
209 {
210         if (rct1->xmin > rct2->xmin) rct1->xmin = rct2->xmin;
211         if (rct1->xmax < rct2->xmax) rct1->xmax = rct2->xmax;
212         if (rct1->ymin > rct2->ymin) rct1->ymin = rct2->ymin;
213         if (rct1->ymax < rct2->ymax) rct1->ymax = rct2->ymax;
214 }
215
216 void BLI_rctf_init(rctf *rect, float xmin, float xmax, float ymin, float ymax)
217 {
218         if (xmin <= xmax) {
219                 rect->xmin = xmin;
220                 rect->xmax = xmax;
221         }
222         else {
223                 rect->xmax = xmin;
224                 rect->xmin = xmax;
225         }
226         if (ymin <= ymax) {
227                 rect->ymin = ymin;
228                 rect->ymax = ymax;
229         }
230         else {
231                 rect->ymax = ymin;
232                 rect->ymin = ymax;
233         }
234 }
235
236 void BLI_rcti_init(rcti *rect, int xmin, int xmax, int ymin, int ymax)
237 {
238         if (xmin <= xmax) {
239                 rect->xmin = xmin;
240                 rect->xmax = xmax;
241         }
242         else {
243                 rect->xmax = xmin;
244                 rect->xmin = xmax;
245         }
246         if (ymin <= ymax) {
247                 rect->ymin = ymin;
248                 rect->ymax = ymax;
249         }
250         else {
251                 rect->ymax = ymin;
252                 rect->ymin = ymax;
253         }
254 }
255
256 void BLI_rcti_init_minmax(rcti *rect)
257 {
258         rect->xmin = rect->ymin = INT_MAX;
259         rect->xmax = rect->ymax = INT_MIN;
260 }
261
262 void BLI_rctf_init_minmax(rctf *rect)
263 {
264         rect->xmin = rect->ymin =  FLT_MAX;
265         rect->xmax = rect->ymax = -FLT_MAX;
266 }
267
268 void BLI_rcti_do_minmax_v(rcti *rect, const int xy[2])
269 {
270         if (xy[0] < rect->xmin) rect->xmin = xy[0];
271         if (xy[0] > rect->xmax) rect->xmax = xy[0];
272         if (xy[1] < rect->ymin) rect->ymin = xy[1];
273         if (xy[1] > rect->ymax) rect->ymax = xy[1];
274 }
275
276 void BLI_rctf_do_minmax_v(rctf *rect, const float xy[2])
277 {
278         if (xy[0] < rect->xmin) rect->xmin = xy[0];
279         if (xy[0] > rect->xmax) rect->xmax = xy[0];
280         if (xy[1] < rect->ymin) rect->ymin = xy[1];
281         if (xy[1] > rect->ymax) rect->ymax = xy[1];
282 }
283
284 void BLI_rcti_translate(rcti *rect, int x, int y)
285 {
286         rect->xmin += x;
287         rect->ymin += y;
288         rect->xmax += x;
289         rect->ymax += y;
290 }
291 void BLI_rctf_translate(rctf *rect, float x, float y)
292 {
293         rect->xmin += x;
294         rect->ymin += y;
295         rect->xmax += x;
296         rect->ymax += y;
297 }
298
299 /* change width & height around the central location */
300 void BLI_rcti_resize(rcti *rect, int x, int y)
301 {
302         rect->xmin = rect->xmax = BLI_rcti_cent_x(rect);
303         rect->ymin = rect->ymax = BLI_rcti_cent_y(rect);
304         rect->xmin -= x / 2;
305         rect->ymin -= y / 2;
306         rect->xmax = rect->xmin + x;
307         rect->ymax = rect->ymin + y;
308 }
309
310 void BLI_rctf_resize(rctf *rect, float x, float y)
311 {
312         rect->xmin = rect->xmax = BLI_rctf_cent_x(rect);
313         rect->ymin = rect->ymax = BLI_rctf_cent_y(rect);
314         rect->xmin -= x * 0.5f;
315         rect->ymin -= y * 0.5f;
316         rect->xmax = rect->xmin + x;
317         rect->ymax = rect->ymin + y;
318 }
319
320 void BLI_rcti_scale(rcti *rect, const float scale)
321 {
322         const int cent_x      = BLI_rcti_cent_x(rect);
323         const int cent_y      = BLI_rcti_cent_y(rect);
324         const int size_x_half = BLI_rcti_size_x(rect) * (scale * 0.5f);
325         const int size_y_half = BLI_rcti_size_y(rect) * (scale * 0.5f);
326         rect->xmin = cent_x - size_x_half;
327         rect->ymin = cent_y - size_y_half;
328         rect->xmax = cent_x + size_x_half;
329         rect->ymax = cent_y + size_y_half;
330 }
331
332 void BLI_rctf_scale(rctf *rect, const float scale)
333 {
334         const float cent_x      = BLI_rctf_cent_x(rect);
335         const float cent_y      = BLI_rctf_cent_y(rect);
336         const float size_x_half = BLI_rctf_size_x(rect) * (scale * 0.5f);
337         const float size_y_half = BLI_rctf_size_y(rect) * (scale * 0.5f);
338         rect->xmin = cent_x - size_x_half;
339         rect->ymin = cent_y - size_y_half;
340         rect->xmax = cent_x + size_x_half;
341         rect->ymax = cent_y + size_y_half;
342 }
343
344 void BLI_rctf_interp(rctf *rect, const rctf *rect_a, const rctf *rect_b, const float fac)
345 {
346         const float ifac = 1.0f - fac;
347         rect->xmin = (rect_a->xmin * ifac) + (rect_b->xmin * fac);
348         rect->xmax = (rect_a->xmax * ifac) + (rect_b->xmax * fac);
349         rect->ymin = (rect_a->ymin * ifac) + (rect_b->ymin * fac);
350         rect->ymax = (rect_a->ymax * ifac) + (rect_b->ymax * fac);
351 }
352
353 /* BLI_rcti_interp() not needed yet */
354
355
356 bool BLI_rctf_clamp_pt_v(const struct rctf *rect, float xy[2])
357 {
358         bool change = false;
359         if (xy[0] < rect->xmin) { xy[0] = rect->xmin; change = true; }
360         if (xy[0] > rect->xmax) { xy[0] = rect->xmax; change = true; }
361         if (xy[1] < rect->ymin) { xy[1] = rect->ymin; change = true; }
362         if (xy[1] > rect->ymax) { xy[1] = rect->ymax; change = true; }
363         return change;
364 }
365
366 bool BLI_rcti_clamp_pt_v(const struct rcti *rect, int xy[2])
367 {
368         bool change = false;
369         if (xy[0] < rect->xmin) { xy[0] = rect->xmin; change = true; }
370         if (xy[0] > rect->xmax) { xy[0] = rect->xmax; change = true; }
371         if (xy[1] < rect->ymin) { xy[1] = rect->ymin; change = true; }
372         if (xy[1] > rect->ymax) { xy[1] = rect->ymax; change = true; }
373         return change;
374 }
375
376 bool BLI_rctf_compare(const struct rctf *rect_a, const struct rctf *rect_b, const float limit)
377 {
378         if (fabsf(rect_a->xmin - rect_b->xmin) < limit)
379                 if (fabsf(rect_a->xmax - rect_b->xmax) < limit)
380                         if (fabsf(rect_a->ymin - rect_b->ymin) < limit)
381                                 if (fabsf(rect_a->ymax - rect_b->ymax) < limit)
382                                         return true;
383
384         return false;
385 }
386
387 bool BLI_rcti_compare(const struct rcti *rect_a, const struct rcti *rect_b)
388 {
389         if (rect_a->xmin == rect_b->xmin)
390                 if (rect_a->xmax == rect_b->xmax)
391                         if (rect_a->ymin == rect_b->ymin)
392                                 if (rect_a->ymax == rect_b->ymax)
393                                         return true;
394
395         return false;
396 }
397
398 bool BLI_rctf_isect(const rctf *src1, const rctf *src2, rctf *dest)
399 {
400         float xmin, xmax;
401         float ymin, ymax;
402
403         xmin = (src1->xmin) > (src2->xmin) ? (src1->xmin) : (src2->xmin);
404         xmax = (src1->xmax) < (src2->xmax) ? (src1->xmax) : (src2->xmax);
405         ymin = (src1->ymin) > (src2->ymin) ? (src1->ymin) : (src2->ymin);
406         ymax = (src1->ymax) < (src2->ymax) ? (src1->ymax) : (src2->ymax);
407
408         if (xmax >= xmin && ymax >= ymin) {
409                 if (dest) {
410                         dest->xmin = xmin;
411                         dest->xmax = xmax;
412                         dest->ymin = ymin;
413                         dest->ymax = ymax;
414                 }
415                 return true;
416         }
417         else {
418                 if (dest) {
419                         dest->xmin = 0;
420                         dest->xmax = 0;
421                         dest->ymin = 0;
422                         dest->ymax = 0;
423                 }
424                 return false;
425         }
426 }
427
428 bool BLI_rcti_isect(const rcti *src1, const rcti *src2, rcti *dest)
429 {
430         int xmin, xmax;
431         int ymin, ymax;
432
433         xmin = (src1->xmin) > (src2->xmin) ? (src1->xmin) : (src2->xmin);
434         xmax = (src1->xmax) < (src2->xmax) ? (src1->xmax) : (src2->xmax);
435         ymin = (src1->ymin) > (src2->ymin) ? (src1->ymin) : (src2->ymin);
436         ymax = (src1->ymax) < (src2->ymax) ? (src1->ymax) : (src2->ymax);
437
438         if (xmax >= xmin && ymax >= ymin) {
439                 if (dest) {
440                         dest->xmin = xmin;
441                         dest->xmax = xmax;
442                         dest->ymin = ymin;
443                         dest->ymax = ymax;
444                 }
445                 return true;
446         }
447         else {
448                 if (dest) {
449                         dest->xmin = 0;
450                         dest->xmax = 0;
451                         dest->ymin = 0;
452                         dest->ymax = 0;
453                 }
454                 return false;
455         }
456 }
457
458 void BLI_rcti_rctf_copy(rcti *dst, const rctf *src)
459 {
460         dst->xmin = floorf(src->xmin + 0.5f);
461         dst->xmax = dst->xmin + floorf(BLI_rctf_size_x(src) + 0.5f);
462         dst->ymin = floorf(src->ymin + 0.5f);
463         dst->ymax = dst->ymin + floorf(BLI_rctf_size_y(src) + 0.5f);
464 }
465
466 void BLI_rctf_rcti_copy(rctf *dst, const rcti *src)
467 {
468         dst->xmin = src->xmin;
469         dst->xmax = src->xmax;
470         dst->ymin = src->ymin;
471         dst->ymax = src->ymax;
472 }
473
474 void print_rctf(const char *str, const rctf *rect)
475 {
476         printf("%s: xmin %.3f, xmax %.3f, ymin %.3f, ymax %.3f (%.3fx%.3f)\n", str,
477                rect->xmin, rect->xmax, rect->ymin, rect->ymax, BLI_rctf_size_x(rect), BLI_rctf_size_y(rect));
478 }
479
480 void print_rcti(const char *str, const rcti *rect)
481 {
482         printf("%s: xmin %d, xmax %d, ymin %d, ymax %d (%dx%d)\n", str,
483                rect->xmin, rect->xmax, rect->ymin, rect->ymax, BLI_rcti_size_x(rect), BLI_rcti_size_y(rect));
484 }