1fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul/************************************************************************** 2fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * 3877128505431adaf817dc8069172ebe4a1cdf5d8José Fonseca * Copyright 2008 VMware, Inc. 4fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * All Rights Reserved. 5fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * 6fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * Permission is hereby granted, free of charge, to any person obtaining a 7fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * copy of this software and associated documentation files (the 8fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * "Software"), to deal in the Software without restriction, including 9fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * without limitation the rights to use, copy, modify, merge, publish, 10fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * distribute, sub license, and/or sell copies of the Software, and to 11fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * permit persons to whom the Software is furnished to do so, subject to 12fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * the following conditions: 13fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * 14fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * The above copyright notice and this permission notice (including the 15fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * next paragraph) shall be included in all copies or substantial portions 16fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * of the Software. 17fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * 18fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 19fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 21877128505431adaf817dc8069172ebe4a1cdf5d8José Fonseca * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR 22fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 23fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 24fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul * 26fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul **************************************************************************/ 27fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul 28fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul 294cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell#ifndef U_RECT_H 304cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell#define U_RECT_H 314cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell 324cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell#include "pipe/p_compiler.h" 337d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller#include "util/u_math.h" 344cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell 355d12c7b755cd405c41d44ef9102e826a366323e3José Fonseca#ifdef __cplusplus 365d12c7b755cd405c41d44ef9102e826a366323e3José Fonsecaextern "C" { 375d12c7b755cd405c41d44ef9102e826a366323e3José Fonseca#endif 385d12c7b755cd405c41d44ef9102e826a366323e3José Fonseca 394cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwellstruct u_rect { 404cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell int x0, x1; 414cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell int y0, y1; 424cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell}; 434cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell 444cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell/* Do two rectangles intersect? 45fec4f5de67b22a7048266fb7e57f49fe6fc3744aRoland Scheidegger * Note: empty rectangles are valid as inputs (and never intersect). 46fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul */ 47a2a1a5805fd617e7f3cc8be44dd79b50da07ebb9Ilia Mirkinstatic inline boolean 484cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwellu_rect_test_intersection(const struct u_rect *a, 494cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell const struct u_rect *b) 504cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell{ 514cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell return (!(a->x1 < b->x0 || 524cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell b->x1 < a->x0 || 534cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell a->y1 < b->y0 || 54fec4f5de67b22a7048266fb7e57f49fe6fc3744aRoland Scheidegger b->y1 < a->y0 || 55fec4f5de67b22a7048266fb7e57f49fe6fc3744aRoland Scheidegger a->x1 < a->x0 || 56fec4f5de67b22a7048266fb7e57f49fe6fc3744aRoland Scheidegger a->y1 < a->y0 || 57fec4f5de67b22a7048266fb7e57f49fe6fc3744aRoland Scheidegger b->x1 < b->x0 || 58fec4f5de67b22a7048266fb7e57f49fe6fc3744aRoland Scheidegger b->y1 < b->y0)); 594cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell} 60fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul 614cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell/* Find the intersection of two rectangles known to intersect. 624cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell */ 63a2a1a5805fd617e7f3cc8be44dd79b50da07ebb9Ilia Mirkinstatic inline void 644cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwellu_rect_find_intersection(const struct u_rect *a, 654cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell struct u_rect *b) 664cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell{ 674cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell /* Caller should verify intersection exists before calling. 684cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell */ 694cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell if (b->x0 < a->x0) b->x0 = a->x0; 704cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell if (b->x1 > a->x1) b->x1 = a->x1; 714cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell if (b->y0 < a->y0) b->y0 = a->y0; 724cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell if (b->y1 > a->y1) b->y1 = a->y1; 734cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell} 74fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul 75fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul 76a2a1a5805fd617e7f3cc8be44dd79b50da07ebb9Ilia Mirkinstatic inline int 777d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumilleru_rect_area(const struct u_rect *r) 787d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller{ 797d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller return (r->x1 - r->x0) * (r->y1 - r->y0); 807d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller} 817d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller 82a2a1a5805fd617e7f3cc8be44dd79b50da07ebb9Ilia Mirkinstatic inline void 834cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwellu_rect_possible_intersection(const struct u_rect *a, 844cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell struct u_rect *b) 854cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell{ 864cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell if (u_rect_test_intersection(a,b)) { 874cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell u_rect_find_intersection(a,b); 884cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell } 894cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell else { 9017542086174ed1c2ea47f3b9b5917ce478442819Roland Scheidegger /* 9117542086174ed1c2ea47f3b9b5917ce478442819Roland Scheidegger * Note the u_rect_xx tests deal with inclusive coordinates 9217542086174ed1c2ea47f3b9b5917ce478442819Roland Scheidegger * hence all-zero would not be an empty box. 9317542086174ed1c2ea47f3b9b5917ce478442819Roland Scheidegger */ 9417542086174ed1c2ea47f3b9b5917ce478442819Roland Scheidegger b->x0 = b->y0 = 0; 9517542086174ed1c2ea47f3b9b5917ce478442819Roland Scheidegger b->x1 = b->y1 = -1; 964cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell } 974cef3087261317f04e4a06cc645c895d31f6e06bKeith Whitwell} 98fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul 997d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller/* Set @d to a rectangle that covers both @a and @b. 1007d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller */ 101a2a1a5805fd617e7f3cc8be44dd79b50da07ebb9Ilia Mirkinstatic inline void 1027d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumilleru_rect_union(struct u_rect *d, const struct u_rect *a, const struct u_rect *b) 1037d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller{ 1047d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller d->x0 = MIN2(a->x0, b->x0); 1057d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller d->y0 = MIN2(a->y0, b->y0); 1067d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller d->x1 = MAX2(a->x1, b->x1); 1077d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller d->y1 = MAX2(a->y1, b->y1); 1087d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller} 1097d2573b5376bb4f9ce9a50e0b965e06032b135a9Christoph Bumiller 1105d12c7b755cd405c41d44ef9102e826a366323e3José Fonseca#ifdef __cplusplus 1115d12c7b755cd405c41d44ef9102e826a366323e3José Fonseca} 1125d12c7b755cd405c41d44ef9102e826a366323e3José Fonseca#endif 1135d12c7b755cd405c41d44ef9102e826a366323e3José Fonseca 114fe1e39afbb147deab60ecc932c24f921b46f1364Brian Paul#endif /* U_RECT_H */ 115