bdca1bb51bd7080a3dff126724d285f36ca53a6d
[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 int BLI_rcti_is_empty(const rcti *rect)
52 {
53         return ((rect->xmax <= rect->xmin) || (rect->ymax <= rect->ymin));
54 }
55
56 int BLI_rctf_is_empty(const rctf *rect)
57 {
58         return ((rect->xmax <= rect->xmin) || (rect->ymax <= rect->ymin));
59 }
60
61 int BLI_in_rcti(const rcti *rect, const int x, const int y)
62 {
63         if (x < rect->xmin) return 0;
64         if (x > rect->xmax) return 0;
65         if (y < rect->ymin) return 0;
66         if (y > rect->ymax) return 0;
67         return 1;
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 int BLI_in_rcti_v(const rcti *rect, const int xy[2])
78 {
79         if (xy[0] < rect->xmin) return 0;
80         if (xy[0] > rect->xmax) return 0;
81         if (xy[1] < rect->ymin) return 0;
82         if (xy[1] > rect->ymax) return 0;
83         return 1;
84 }
85
86 int BLI_in_rctf(const rctf *rect, const float x, const float y)
87 {
88         if (x < rect->xmin) return 0;
89         if (x > rect->xmax) return 0;
90         if (y < rect->ymin) return 0;
91         if (y > rect->ymax) return 0;
92         return 1;
93 }
94
95 int BLI_in_rctf_v(const rctf *rect, const float xy[2])
96 {
97         if (xy[0] < rect->xmin) return 0;
98         if (xy[0] > rect->xmax) return 0;
99         if (xy[1] < rect->ymin) return 0;
100         if (xy[1] > rect->ymax) return 0;
101         return 1;
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(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.0f) {
109                 return 1; /* co-linear */
110         }
111         else {
112                 const double labda = (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 (labda >= 0.0f && labda <= 1.0f && mu >= 0.0f && mu <= 1.0f);
115         }
116 }
117
118 int BLI_segment_in_rcti(const rcti *rect, const int s1[2], const int s2[2])
119 {
120         /* first do outside-bounds check for both points of the segment */
121         if (s1[0] < rect->xmin && s2[0] < rect->xmin) return 0;
122         if (s1[0] > rect->xmax && s2[0] > rect->xmax) return 0;
123         if (s1[1] < rect->ymin && s2[1] < rect->ymin) return 0;
124         if (s1[1] > rect->ymax && s2[1] > rect->ymax) return 0;
125
126         /* if either points intersect then we definetly intersect */
127         if (BLI_in_rcti_v(rect, s1) || BLI_in_rcti_v(rect, s2)) {
128                 return 1;
129         }
130         else {
131                 /* both points are outside but may insersect the rect */
132                 int tvec1[2];
133                 int tvec2[2];
134                 /* diagonal: [/] */
135                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymin;
136                 tvec2[0] = rect->xmin; tvec2[1] = rect->ymax;
137                 if (isect_segments(s1, s2, tvec1, tvec2)) {
138                         return 1;
139                 }
140
141                 /* diagonal: [\] */
142                 tvec1[0] = rect->xmin; tvec1[1] = rect->ymax;
143                 tvec2[0] = rect->xmax; tvec2[1] = rect->ymin;
144                 if (isect_segments(s1, s2, tvec1, tvec2)) {
145                         return 1;
146                 }
147
148                 /* no intersection */
149                 return 0;
150         }
151 }
152
153 void BLI_union_rctf(rctf *rct1, const rctf *rct2)
154 {
155         if (rct1->xmin > rct2->xmin) rct1->xmin = rct2->xmin;
156         if (rct1->xmax < rct2->xmax) rct1->xmax = rct2->xmax;
157         if (rct1->ymin > rct2->ymin) rct1->ymin = rct2->ymin;
158         if (rct1->ymax < rct2->ymax) rct1->ymax = rct2->ymax;
159 }
160
161 void BLI_union_rcti(rcti *rct1, const rcti *rct2)
162 {
163         if (rct1->xmin > rct2->xmin) rct1->xmin = rct2->xmin;
164         if (rct1->xmax < rct2->xmax) rct1->xmax = rct2->xmax;
165         if (rct1->ymin > rct2->ymin) rct1->ymin = rct2->ymin;
166         if (rct1->ymax < rct2->ymax) rct1->ymax = rct2->ymax;
167 }
168
169 void BLI_rctf_init(rctf *rect, float xmin, float xmax, float ymin, float ymax)
170 {
171         if (xmin <= xmax) {
172                 rect->xmin = xmin;
173                 rect->xmax = xmax;
174         }
175         else {
176                 rect->xmax = xmin;
177                 rect->xmin = xmax;
178         }
179         if (ymin <= ymax) {
180                 rect->ymin = ymin;
181                 rect->ymax = ymax;
182         }
183         else {
184                 rect->ymax = ymin;
185                 rect->ymin = ymax;
186         }
187 }
188
189 void BLI_rcti_init(rcti *rect, int xmin, int xmax, int ymin, int ymax)
190 {
191         if (xmin <= xmax) {
192                 rect->xmin = xmin;
193                 rect->xmax = xmax;
194         }
195         else {
196                 rect->xmax = xmin;
197                 rect->xmin = xmax;
198         }
199         if (ymin <= ymax) {
200                 rect->ymin = ymin;
201                 rect->ymax = ymax;
202         }
203         else {
204                 rect->ymax = ymin;
205                 rect->ymin = ymax;
206         }
207 }
208
209 void BLI_rcti_init_minmax(struct rcti *rect)
210 {
211         rect->xmin = rect->ymin = INT_MAX;
212         rect->xmax = rect->ymax = INT_MIN;
213 }
214
215 void BLI_rctf_init_minmax(struct rctf *rect)
216 {
217         rect->xmin = rect->ymin = FLT_MAX;
218         rect->xmax = rect->ymax = FLT_MIN;
219 }
220
221 void BLI_rcti_do_minmax_v(struct rcti *rect, const int xy[2])
222 {
223         if (xy[0] < rect->xmin) rect->xmin = xy[0];
224         if (xy[0] > rect->xmax) rect->xmax = xy[0];
225         if (xy[1] < rect->ymin) rect->ymin = xy[1];
226         if (xy[1] > rect->ymax) rect->ymax = xy[1];
227 }
228
229 void BLI_rctf_do_minmax_v(struct rctf *rect, const float xy[2])
230 {
231         if (xy[0] < rect->xmin) rect->xmin = xy[0];
232         if (xy[0] > rect->xmax) rect->xmax = xy[0];
233         if (xy[1] < rect->ymin) rect->ymin = xy[1];
234         if (xy[1] > rect->ymax) rect->ymax = xy[1];
235 }
236
237 void BLI_translate_rcti(rcti *rect, int x, int y)
238 {
239         rect->xmin += x;
240         rect->ymin += y;
241         rect->xmax += x;
242         rect->ymax += y;
243 }
244 void BLI_translate_rctf(rctf *rect, float x, float y)
245 {
246         rect->xmin += x;
247         rect->ymin += y;
248         rect->xmax += x;
249         rect->ymax += y;
250 }
251
252 /* change width & height around the central location */
253 void BLI_resize_rcti(rcti *rect, int x, int y)
254 {
255         rect->xmin = rect->xmax = (rect->xmax + rect->xmin) / 2;
256         rect->ymin = rect->ymax = (rect->ymax + rect->ymin) / 2;
257         rect->xmin -= x / 2;
258         rect->ymin -= y / 2;
259         rect->xmax = rect->xmin + x;
260         rect->ymax = rect->ymin + y;
261 }
262
263 void BLI_resize_rctf(rctf *rect, float x, float y)
264 {
265         rect->xmin = rect->xmax = (rect->xmax + rect->xmin) * 0.5f;
266         rect->ymin = rect->ymax = (rect->ymax + rect->ymin) * 0.5f;
267         rect->xmin -= x * 0.5f;
268         rect->ymin -= y * 0.5f;
269         rect->xmax = rect->xmin + x;
270         rect->ymax = rect->ymin + y;
271 }
272
273 int BLI_isect_rctf(const rctf *src1, const rctf *src2, rctf *dest)
274 {
275         float xmin, xmax;
276         float ymin, ymax;
277
278         xmin = (src1->xmin) > (src2->xmin) ? (src1->xmin) : (src2->xmin);
279         xmax = (src1->xmax) < (src2->xmax) ? (src1->xmax) : (src2->xmax);
280         ymin = (src1->ymin) > (src2->ymin) ? (src1->ymin) : (src2->ymin);
281         ymax = (src1->ymax) < (src2->ymax) ? (src1->ymax) : (src2->ymax);
282
283         if (xmax >= xmin && ymax >= ymin) {
284                 if (dest) {
285                         dest->xmin = xmin;
286                         dest->xmax = xmax;
287                         dest->ymin = ymin;
288                         dest->ymax = ymax;
289                 }
290                 return 1;
291         }
292         else {
293                 if (dest) {
294                         dest->xmin = 0;
295                         dest->xmax = 0;
296                         dest->ymin = 0;
297                         dest->ymax = 0;
298                 }
299                 return 0;
300         }
301 }
302
303 int BLI_isect_rcti(const rcti *src1, const rcti *src2, rcti *dest)
304 {
305         int xmin, xmax;
306         int ymin, ymax;
307
308         xmin = (src1->xmin) > (src2->xmin) ? (src1->xmin) : (src2->xmin);
309         xmax = (src1->xmax) < (src2->xmax) ? (src1->xmax) : (src2->xmax);
310         ymin = (src1->ymin) > (src2->ymin) ? (src1->ymin) : (src2->ymin);
311         ymax = (src1->ymax) < (src2->ymax) ? (src1->ymax) : (src2->ymax);
312
313         if (xmax >= xmin && ymax >= ymin) {
314                 if (dest) {
315                         dest->xmin = xmin;
316                         dest->xmax = xmax;
317                         dest->ymin = ymin;
318                         dest->ymax = ymax;
319                 }
320                 return 1;
321         }
322         else {
323                 if (dest) {
324                         dest->xmin = 0;
325                         dest->xmax = 0;
326                         dest->ymin = 0;
327                         dest->ymax = 0;
328                 }
329                 return 0;
330         }
331 }
332
333 void BLI_copy_rcti_rctf(rcti *tar, const rctf *src)
334 {
335         tar->xmin = floorf(src->xmin + 0.5f);
336         tar->xmax = floorf((src->xmax - src->xmin) + 0.5f);
337         tar->ymin = floorf(src->ymin + 0.5f);
338         tar->ymax = floorf((src->ymax - src->ymin) + 0.5f);
339 }
340
341 void print_rctf(const char *str, const rctf *rect)
342 {
343         printf("%s: xmin %.3f, xmax %.3f, ymin %.3f, ymax %.3f (%.3fx%.3f)\n", str,
344                rect->xmin, rect->xmax, rect->ymin, rect->ymax, rect->xmax - rect->xmin, rect->ymax - rect->ymin);
345 }
346
347 void print_rcti(const char *str, const rcti *rect)
348 {
349         printf("%s: xmin %d, xmax %d, ymin %d, ymax %d (%dx%d)\n", str,
350                rect->xmin, rect->xmax, rect->ymin, rect->ymax, rect->xmax - rect->xmin, rect->ymax - rect->ymin);
351 }