51bd9eee0a6330509d5f0ad6e2279911cc6f1bba
[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_x(const rcti *rect, const int x)
62 {
63         if (x < rect->xmin) return false;
64         if (x > rect->xmax) return false;
65         return true;
66 }
67
68 bool BLI_rcti_isect_y(const rcti *rect, const int y)
69 {
70         if (y < rect->ymin) return false;
71         if (y > rect->ymax) return false;
72         return true;
73 }
74
75 bool BLI_rcti_isect_pt(const rcti *rect, const int x, const int y)
76 {
77         if (x < rect->xmin) return false;
78         if (x > rect->xmax) return false;
79         if (y < rect->ymin) return false;
80         if (y > rect->ymax) return false;
81         return true;
82 }
83
84 bool BLI_rcti_isect_pt_v(const rcti *rect, const int xy[2])
85 {
86         if (xy[0] < rect->xmin) return false;
87         if (xy[0] > rect->xmax) return false;
88         if (xy[1] < rect->ymin) return false;
89         if (xy[1] > rect->ymax) return false;
90         return true;
91 }
92
93 bool BLI_rctf_isect_x(const rctf *rect, const float x)
94 {
95         if (x < rect->xmin) return false;
96         if (x > rect->xmax) return false;
97         return true;
98 }
99
100 bool BLI_rctf_isect_y(const rctf *rect, const float y)
101 {
102         if (y < rect->ymin) return false;
103         if (y > rect->ymax) return false;
104         return true;
105 }
106
107 bool BLI_rctf_isect_pt(const rctf *rect, const float x, const float y)
108 {
109         if (x < rect->xmin) return false;
110         if (x > rect->xmax) return false;
111         if (y < rect->ymin) return false;
112         if (y > rect->ymax) return false;
113         return true;
114 }
115
116 bool BLI_rctf_isect_pt_v(const rctf *rect, const float xy[2])
117 {
118         if (xy[0] < rect->xmin) return false;
119         if (xy[0] > rect->xmax) return false;
120         if (xy[1] < rect->ymin) return false;
121         if (xy[1] > rect->ymax) return false;
122         return true;
123 }
124
125 /**
126  * is \a rct_b inside \a rct_a
127  */
128 bool BLI_rctf_inside_rctf(rctf *rct_a, const rctf *rct_b)
129 {
130         return ((rct_a->xmin <= rct_b->xmin) &&
131                 (rct_a->xmax >= rct_b->xmax) &&
132                 (rct_a->ymin <= rct_b->ymin) &&
133                 (rct_a->ymax >= rct_b->ymax));
134 }
135 bool BLI_rcti_inside_rcti(rcti *rct_a, const rcti *rct_b)
136 {
137         return ((rct_a->xmin <= rct_b->xmin) &&
138                 (rct_a->xmax >= rct_b->xmax) &&
139                 (rct_a->ymin <= rct_b->ymin) &&
140                 (rct_a->ymax >= rct_b->ymax));
141 }
142
143
144 /* based closely on 'isect_line_line_v2_int', but in modified so corner cases are treated as intersections */
145 static int isect_segments_i(const int v1[2], const int v2[2], const int v3[2], const int v4[2])
146 {
147         const double div = (double)((v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]));
148         if (div == 0.0) {
149                 return 1; /* co-linear */
150         }
151         else {
152                 const double lambda = (double)((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
153                 const double mu    = (double)((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
154                 return (lambda >= 0.0 && lambda <= 1.0 && mu >= 0.0 && mu <= 1.0);
155         }
156 }
157 static int isect_segments_fl(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
158 {
159         const double div = (double)((v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]));
160         if (div == 0.0) {
161                 return 1; /* co-linear */
162         }
163         else {
164                 const double lambda = (double)((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
165                 const double mu    = (double)((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
166                 return (lambda >= 0.0 && lambda <= 1.0 && mu >= 0.0 && mu <= 1.0);
167         }
168 }
169
170 bool BLI_rcti_isect_segment(const rcti *rect, const int s1[2], const int s2[2])
171 {
172         /* first do outside-bounds check for both points of the segment */
173         if (s1[0] < rect->xmin && s2[0] < rect->xmin) return false;
174         if (s1[0] > rect->xmax && s2[0] > rect->xmax) return false;
175         if (s1[1] < rect->ymin && s2[1] < rect->ymin) return false;
176         if (s1[1] > rect->ymax && s2[1] > rect->ymax) return false;
177
178         /* if either points intersect then we definetly intersect */
179         if (BLI_rcti_isect_pt_v(rect, s1) || BLI_rcti_isect_pt_v(rect, s2)) {
180                 return true;
181         }
182         else {
183                 /* both points are outside but may insersect the rect */
184                 int tvec1[2];
185                 int tvec2[2];
186                 /* diagonal: [/] */
187                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymin;
188                 tvec2[0] = rect->xmin; tvec2[1] = rect->ymax;
189                 if (isect_segments_i(s1, s2, tvec1, tvec2)) {
190                         return true;
191                 }
192
193                 /* diagonal: [\] */
194                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymax;
195                 tvec2[0] = rect->xmax; tvec2[1] = rect->ymin;
196                 if (isect_segments_i(s1, s2, tvec1, tvec2)) {
197                         return true;
198                 }
199
200                 /* no intersection */
201                 return false;
202         }
203 }
204
205 bool BLI_rctf_isect_segment(const rctf *rect, const float s1[2], const float s2[2])
206 {
207         /* first do outside-bounds check for both points of the segment */
208         if (s1[0] < rect->xmin && s2[0] < rect->xmin) return false;
209         if (s1[0] > rect->xmax && s2[0] > rect->xmax) return false;
210         if (s1[1] < rect->ymin && s2[1] < rect->ymin) return false;
211         if (s1[1] > rect->ymax && s2[1] > rect->ymax) return false;
212
213         /* if either points intersect then we definetly intersect */
214         if (BLI_rctf_isect_pt_v(rect, s1) || BLI_rctf_isect_pt_v(rect, s2)) {
215                 return true;
216         }
217         else {
218                 /* both points are outside but may insersect the rect */
219                 float tvec1[2];
220                 float tvec2[2];
221                 /* diagonal: [/] */
222                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymin;
223                 tvec2[0] = rect->xmin; tvec2[1] = rect->ymax;
224                 if (isect_segments_fl(s1, s2, tvec1, tvec2)) {
225                         return true;
226                 }
227
228                 /* diagonal: [\] */
229                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymax;
230                 tvec2[0] = rect->xmax; tvec2[1] = rect->ymin;
231                 if (isect_segments_fl(s1, s2, tvec1, tvec2)) {
232                         return true;
233                 }
234
235                 /* no intersection */
236                 return false;
237         }
238 }
239
240 bool BLI_rcti_isect_circle(const rcti *rect, const float xy[2], const float radius)
241 {
242         float dx, dy;
243
244         if (xy[0] >= rect->xmin && xy[0] <= rect->xmax) dx = 0;
245         else dx = (xy[0] < rect->xmin) ? (rect->xmin - xy[0]) : (xy[0] - rect->xmax);
246
247         if (xy[1] >= rect->ymin && xy[1] <= rect->ymax) dy = 0;
248         else dy = (xy[1] < rect->ymin) ? (rect->ymin - xy[1]) : (xy[1] - rect->ymax);
249
250         return dx * dx + dy * dy <= radius * radius;
251 }
252
253 bool BLI_rctf_isect_circle(const rctf *rect, const float xy[2], const float radius)
254 {
255         float dx, dy;
256
257         if (xy[0] >= rect->xmin && xy[0] <= rect->xmax) dx = 0;
258         else dx = (xy[0] < rect->xmin) ? (rect->xmin - xy[0]) : (xy[0] - rect->xmax);
259
260         if (xy[1] >= rect->ymin && xy[1] <= rect->ymax) dy = 0;
261         else dy = (xy[1] < rect->ymin) ? (rect->ymin - xy[1]) : (xy[1] - rect->ymax);
262
263         return dx * dx + dy * dy <= radius * radius;
264 }
265
266 void BLI_rctf_union(rctf *rct1, const rctf *rct2)
267 {
268         if (rct1->xmin > rct2->xmin) rct1->xmin = rct2->xmin;
269         if (rct1->xmax < rct2->xmax) rct1->xmax = rct2->xmax;
270         if (rct1->ymin > rct2->ymin) rct1->ymin = rct2->ymin;
271         if (rct1->ymax < rct2->ymax) rct1->ymax = rct2->ymax;
272 }
273
274 void BLI_rcti_union(rcti *rct1, const rcti *rct2)
275 {
276         if (rct1->xmin > rct2->xmin) rct1->xmin = rct2->xmin;
277         if (rct1->xmax < rct2->xmax) rct1->xmax = rct2->xmax;
278         if (rct1->ymin > rct2->ymin) rct1->ymin = rct2->ymin;
279         if (rct1->ymax < rct2->ymax) rct1->ymax = rct2->ymax;
280 }
281
282 void BLI_rctf_init(rctf *rect, float xmin, float xmax, float ymin, float ymax)
283 {
284         if (xmin <= xmax) {
285                 rect->xmin = xmin;
286                 rect->xmax = xmax;
287         }
288         else {
289                 rect->xmax = xmin;
290                 rect->xmin = xmax;
291         }
292         if (ymin <= ymax) {
293                 rect->ymin = ymin;
294                 rect->ymax = ymax;
295         }
296         else {
297                 rect->ymax = ymin;
298                 rect->ymin = ymax;
299         }
300 }
301
302 void BLI_rcti_init(rcti *rect, int xmin, int xmax, int ymin, int ymax)
303 {
304         if (xmin <= xmax) {
305                 rect->xmin = xmin;
306                 rect->xmax = xmax;
307         }
308         else {
309                 rect->xmax = xmin;
310                 rect->xmin = xmax;
311         }
312         if (ymin <= ymax) {
313                 rect->ymin = ymin;
314                 rect->ymax = ymax;
315         }
316         else {
317                 rect->ymax = ymin;
318                 rect->ymin = ymax;
319         }
320 }
321
322 void BLI_rcti_init_minmax(rcti *rect)
323 {
324         rect->xmin = rect->ymin = INT_MAX;
325         rect->xmax = rect->ymax = INT_MIN;
326 }
327
328 void BLI_rctf_init_minmax(rctf *rect)
329 {
330         rect->xmin = rect->ymin =  FLT_MAX;
331         rect->xmax = rect->ymax = -FLT_MAX;
332 }
333
334 void BLI_rcti_do_minmax_v(rcti *rect, const int xy[2])
335 {
336         if (xy[0] < rect->xmin) rect->xmin = xy[0];
337         if (xy[0] > rect->xmax) rect->xmax = xy[0];
338         if (xy[1] < rect->ymin) rect->ymin = xy[1];
339         if (xy[1] > rect->ymax) rect->ymax = xy[1];
340 }
341
342 void BLI_rctf_do_minmax_v(rctf *rect, const float xy[2])
343 {
344         if (xy[0] < rect->xmin) rect->xmin = xy[0];
345         if (xy[0] > rect->xmax) rect->xmax = xy[0];
346         if (xy[1] < rect->ymin) rect->ymin = xy[1];
347         if (xy[1] > rect->ymax) rect->ymax = xy[1];
348 }
349
350 void BLI_rcti_translate(rcti *rect, int x, int y)
351 {
352         rect->xmin += x;
353         rect->ymin += y;
354         rect->xmax += x;
355         rect->ymax += y;
356 }
357 void BLI_rctf_translate(rctf *rect, float x, float y)
358 {
359         rect->xmin += x;
360         rect->ymin += y;
361         rect->xmax += x;
362         rect->ymax += y;
363 }
364
365 void BLI_rcti_recenter(rcti *rect, int x, int y)
366 {
367         const int dx = x - BLI_rcti_cent_x(rect);
368         const int dy = y - BLI_rcti_cent_y(rect);
369         BLI_rcti_translate(rect, dx, dy);
370 }
371 void BLI_rctf_recenter(rctf *rect, float x, float y)
372 {
373         const float dx = x - BLI_rctf_cent_x(rect);
374         const float dy = y - BLI_rctf_cent_y(rect);
375         BLI_rctf_translate(rect, dx, dy);
376 }
377
378 /* change width & height around the central location */
379 void BLI_rcti_resize(rcti *rect, int x, int y)
380 {
381         rect->xmin = rect->xmax = BLI_rcti_cent_x(rect);
382         rect->ymin = rect->ymax = BLI_rcti_cent_y(rect);
383         rect->xmin -= x / 2;
384         rect->ymin -= y / 2;
385         rect->xmax = rect->xmin + x;
386         rect->ymax = rect->ymin + y;
387 }
388
389 void BLI_rctf_resize(rctf *rect, float x, float y)
390 {
391         rect->xmin = rect->xmax = BLI_rctf_cent_x(rect);
392         rect->ymin = rect->ymax = BLI_rctf_cent_y(rect);
393         rect->xmin -= x * 0.5f;
394         rect->ymin -= y * 0.5f;
395         rect->xmax = rect->xmin + x;
396         rect->ymax = rect->ymin + y;
397 }
398
399 void BLI_rcti_scale(rcti *rect, const float scale)
400 {
401         const int cent_x      = BLI_rcti_cent_x(rect);
402         const int cent_y      = BLI_rcti_cent_y(rect);
403         const int size_x_half = BLI_rcti_size_x(rect) * (scale * 0.5f);
404         const int size_y_half = BLI_rcti_size_y(rect) * (scale * 0.5f);
405         rect->xmin = cent_x - size_x_half;
406         rect->ymin = cent_y - size_y_half;
407         rect->xmax = cent_x + size_x_half;
408         rect->ymax = cent_y + size_y_half;
409 }
410
411 void BLI_rctf_scale(rctf *rect, const float scale)
412 {
413         const float cent_x      = BLI_rctf_cent_x(rect);
414         const float cent_y      = BLI_rctf_cent_y(rect);
415         const float size_x_half = BLI_rctf_size_x(rect) * (scale * 0.5f);
416         const float size_y_half = BLI_rctf_size_y(rect) * (scale * 0.5f);
417         rect->xmin = cent_x - size_x_half;
418         rect->ymin = cent_y - size_y_half;
419         rect->xmax = cent_x + size_x_half;
420         rect->ymax = cent_y + size_y_half;
421 }
422
423 void BLI_rctf_interp(rctf *rect, const rctf *rect_a, const rctf *rect_b, const float fac)
424 {
425         const float ifac = 1.0f - fac;
426         rect->xmin = (rect_a->xmin * ifac) + (rect_b->xmin * fac);
427         rect->xmax = (rect_a->xmax * ifac) + (rect_b->xmax * fac);
428         rect->ymin = (rect_a->ymin * ifac) + (rect_b->ymin * fac);
429         rect->ymax = (rect_a->ymax * ifac) + (rect_b->ymax * fac);
430 }
431
432 /* BLI_rcti_interp() not needed yet */
433
434
435 bool BLI_rctf_clamp_pt_v(const struct rctf *rect, float xy[2])
436 {
437         bool changed = false;
438         if (xy[0] < rect->xmin) { xy[0] = rect->xmin; changed = true; }
439         if (xy[0] > rect->xmax) { xy[0] = rect->xmax; changed = true; }
440         if (xy[1] < rect->ymin) { xy[1] = rect->ymin; changed = true; }
441         if (xy[1] > rect->ymax) { xy[1] = rect->ymax; changed = true; }
442         return changed;
443 }
444
445 bool BLI_rcti_clamp_pt_v(const struct rcti *rect, int xy[2])
446 {
447         bool changed = false;
448         if (xy[0] < rect->xmin) { xy[0] = rect->xmin; changed = true; }
449         if (xy[0] > rect->xmax) { xy[0] = rect->xmax; changed = true; }
450         if (xy[1] < rect->ymin) { xy[1] = rect->ymin; changed = true; }
451         if (xy[1] > rect->ymax) { xy[1] = rect->ymax; changed = true; }
452         return changed;
453 }
454
455 bool BLI_rctf_compare(const struct rctf *rect_a, const struct rctf *rect_b, const float limit)
456 {
457         if (fabsf(rect_a->xmin - rect_b->xmin) < limit)
458                 if (fabsf(rect_a->xmax - rect_b->xmax) < limit)
459                         if (fabsf(rect_a->ymin - rect_b->ymin) < limit)
460                                 if (fabsf(rect_a->ymax - rect_b->ymax) < limit)
461                                         return true;
462
463         return false;
464 }
465
466 bool BLI_rcti_compare(const struct rcti *rect_a, const struct rcti *rect_b)
467 {
468         if (rect_a->xmin == rect_b->xmin)
469                 if (rect_a->xmax == rect_b->xmax)
470                         if (rect_a->ymin == rect_b->ymin)
471                                 if (rect_a->ymax == rect_b->ymax)
472                                         return true;
473
474         return false;
475 }
476
477 bool BLI_rctf_isect(const rctf *src1, const rctf *src2, rctf *dest)
478 {
479         float xmin, xmax;
480         float ymin, ymax;
481
482         xmin = (src1->xmin) > (src2->xmin) ? (src1->xmin) : (src2->xmin);
483         xmax = (src1->xmax) < (src2->xmax) ? (src1->xmax) : (src2->xmax);
484         ymin = (src1->ymin) > (src2->ymin) ? (src1->ymin) : (src2->ymin);
485         ymax = (src1->ymax) < (src2->ymax) ? (src1->ymax) : (src2->ymax);
486
487         if (xmax >= xmin && ymax >= ymin) {
488                 if (dest) {
489                         dest->xmin = xmin;
490                         dest->xmax = xmax;
491                         dest->ymin = ymin;
492                         dest->ymax = ymax;
493                 }
494                 return true;
495         }
496         else {
497                 if (dest) {
498                         dest->xmin = 0;
499                         dest->xmax = 0;
500                         dest->ymin = 0;
501                         dest->ymax = 0;
502                 }
503                 return false;
504         }
505 }
506
507 bool BLI_rcti_isect(const rcti *src1, const rcti *src2, rcti *dest)
508 {
509         int xmin, xmax;
510         int ymin, ymax;
511
512         xmin = (src1->xmin) > (src2->xmin) ? (src1->xmin) : (src2->xmin);
513         xmax = (src1->xmax) < (src2->xmax) ? (src1->xmax) : (src2->xmax);
514         ymin = (src1->ymin) > (src2->ymin) ? (src1->ymin) : (src2->ymin);
515         ymax = (src1->ymax) < (src2->ymax) ? (src1->ymax) : (src2->ymax);
516
517         if (xmax >= xmin && ymax >= ymin) {
518                 if (dest) {
519                         dest->xmin = xmin;
520                         dest->xmax = xmax;
521                         dest->ymin = ymin;
522                         dest->ymax = ymax;
523                 }
524                 return true;
525         }
526         else {
527                 if (dest) {
528                         dest->xmin = 0;
529                         dest->xmax = 0;
530                         dest->ymin = 0;
531                         dest->ymax = 0;
532                 }
533                 return false;
534         }
535 }
536
537 void BLI_rcti_rctf_copy(rcti *dst, const rctf *src)
538 {
539         dst->xmin = floorf(src->xmin + 0.5f);
540         dst->xmax = dst->xmin + floorf(BLI_rctf_size_x(src) + 0.5f);
541         dst->ymin = floorf(src->ymin + 0.5f);
542         dst->ymax = dst->ymin + floorf(BLI_rctf_size_y(src) + 0.5f);
543 }
544
545 void BLI_rctf_rcti_copy(rctf *dst, const rcti *src)
546 {
547         dst->xmin = src->xmin;
548         dst->xmax = src->xmax;
549         dst->ymin = src->ymin;
550         dst->ymax = src->ymax;
551 }
552
553 void print_rctf(const char *str, const rctf *rect)
554 {
555         printf("%s: xmin %.8f, xmax %.8f, ymin %.8f, ymax %.8f (%.12fx%.12f)\n", str,
556                rect->xmin, rect->xmax, rect->ymin, rect->ymax, BLI_rctf_size_x(rect), BLI_rctf_size_y(rect));
557 }
558
559 void print_rcti(const char *str, const rcti *rect)
560 {
561         printf("%s: xmin %d, xmax %d, ymin %d, ymax %d (%dx%d)\n", str,
562                rect->xmin, rect->xmax, rect->ymin, rect->ymax, BLI_rcti_size_x(rect), BLI_rcti_size_y(rect));
563 }