1 /*
2 * bounds.c
3 *
4 * Copyright (C) 1989, 1991, Craig E. Kolb
5 * All rights reserved.
6 *
7 * This software may be freely copied, modified, and redistributed
8 * provided that this copyright notice is preserved on all copies.
9 *
10 * You may not distribute this software, in whole or in part, as part of
11 * any commercial product without the express consent of the authors.
12 *
13 * There is no warranty or other guarantee of fitness of this software
14 * for any purpose. It is provided solely "as is".
15 *
16 * $Id: bounds.c,v 4.0.1.2 91/10/05 18:17:29 cek Exp Locker: cek $
17 *
18 * $Log: bounds.c,v $
19 * Revision 4.0.1.2 91/10/05 18:17:29 cek
20 * patch1: Faster box transform, a la Jim Arvo.
21 *
22 * Revision 4.0.1.1 1991/09/29 15:42:05 cek
23 * patch1: Justified floating point compare...
24 *
25 * Revision 4.0 91/07/17 14:36:21 kolb
26 * Initial version.
27 *
28 */
29 #include "geom.h"
30
31 /*
32 * Check for intersection between bounding box and the given ray.
33 * If there is an intersection between mindist and *maxdist along
34 * the ray, *maxdist is replaced with the distance to the point of
35 * intersection, and TRUE is returned. Otherwise, FALSE is returned.
36 *
37 * If this routine is used to check for intersection with a volume
38 * rather than a "hollow" box, one should first determine if
39 * (ray->pos + mindist * ray->dir) is inside the bounding volume, and
40 * call BoundsIntersect() only if it is not.
41 */
42 int
BoundsIntersect(ray,bounds,mindist,maxdist)43 BoundsIntersect(ray, bounds, mindist, maxdist)
44 Ray *ray;
45 Float bounds[2][3], mindist, *maxdist;
46 {
47 Float t, tmin, tmax;
48 Float dir, pos;
49
50 tmax = *maxdist;
51 tmin = mindist;
52
53 dir = ray->dir.x;
54 pos = ray->pos.x;
55
56 if (dir < 0) {
57 t = (bounds[LOW][X] - pos) / dir;
58 if (t < tmin)
59 return FALSE;
60 if (t <= tmax)
61 tmax = t;
62 t = (bounds[HIGH][X] - pos) / dir;
63 if (t >= tmin) {
64 if (t > tmax)
65 return FALSE;
66 tmin = t;
67 }
68 } else if (dir > 0.) {
69 t = (bounds[HIGH][X] - pos) / dir;
70 if (t < tmin)
71 return FALSE;
72 if (t <= tmax)
73 tmax = t;
74 t = (bounds[LOW][X] - pos) / dir;
75 if (t >= tmin) {
76 if (t > tmax)
77 return FALSE;
78 tmin = t;
79 }
80 } else if (pos < bounds[LOW][X] || pos > bounds[HIGH][X])
81 return FALSE;
82
83 dir = ray->dir.y;
84 pos = ray->pos.y;
85
86 if (dir < 0) {
87 t = (bounds[LOW][Y] - pos) / dir;
88 if (t < tmin)
89 return FALSE;
90 if (t <= tmax)
91 tmax = t;
92 t = (bounds[HIGH][Y] - pos) / dir;
93 if (t >= tmin) {
94 if (t > tmax)
95 return FALSE;
96 tmin = t;
97 }
98 } else if (dir > 0.) {
99 t = (bounds[HIGH][Y] - pos) / dir;
100 if (t < tmin)
101 return FALSE;
102 if (t <= tmax)
103 tmax = t;
104 t = (bounds[LOW][Y] - pos) / dir;
105 if (t >= tmin) {
106 if (t > tmax)
107 return FALSE;
108 tmin = t;
109 }
110 } else if (pos < bounds[LOW][Y] || pos > bounds[HIGH][Y])
111 return FALSE;
112
113 dir = ray->dir.z;
114 pos = ray->pos.z;
115
116 if (dir < 0) {
117 t = (bounds[LOW][Z] - pos) / dir;
118 if (t < tmin)
119 return FALSE;
120 if (t <= tmax)
121 tmax = t;
122 t = (bounds[HIGH][Z] - pos) / dir;
123 if (t >= tmin) {
124 if (t > tmax)
125 return FALSE;
126 tmin = t;
127 }
128 } else if (dir > 0.) {
129 t = (bounds[HIGH][Z] - pos) / dir;
130 if (t < tmin)
131 return FALSE;
132 if (t <= tmax)
133 tmax = t;
134 t = (bounds[LOW][Z] - pos) / dir;
135 if (t >= tmin) {
136 if (t > tmax)
137 return FALSE;
138 tmin = t;
139 }
140 } else if (pos < bounds[LOW][Z] || pos > bounds[HIGH][Z])
141 return FALSE;
142
143 /*
144 * If tmin == mindist, then there was no "near"
145 * intersection farther than EPSILON away.
146 */
147 if (tmin == mindist) {
148 if (tmax < *maxdist) {
149 *maxdist = tmax;
150 return TRUE;
151 }
152 } else {
153 if (tmin < *maxdist) {
154 *maxdist = tmin;
155 return TRUE;
156 }
157 }
158 return FALSE; /* hit, but not closer than maxdist */
159 }
160
161 /*
162 * Transform an object's bounding box by the given transformation
163 * matrix.
164 */
165 void
BoundsTransform(trans,objbounds)166 BoundsTransform(trans, objbounds)
167 RSMatrix *trans;
168 Float objbounds[2][3];
169 {
170 Float bounds[2][3], a, b;
171 int i, j;
172
173 /*
174 * Can't (and shouldn't) do anything with unbounded objects.
175 */
176 if (objbounds[LOW][X] > objbounds[HIGH][X])
177 return;
178
179 bounds[LOW][X] = bounds[HIGH][X] = trans->translate.x;
180 bounds[LOW][Y] = bounds[HIGH][Y] = trans->translate.y;
181 bounds[LOW][Z] = bounds[HIGH][Z] = trans->translate.z;
182
183 for (i = 0; i < 3; i++) {
184 for (j = 0; j < 3; j++) {
185 a = trans->matrix[j][i] * objbounds[LOW][j];
186 b = trans->matrix[j][i] * objbounds[HIGH][j];
187 if (a < b) {
188 bounds[LOW][i] += a;
189 bounds[HIGH][i] += b;
190 } else {
191 bounds[LOW][i] += b;
192 bounds[HIGH][i] += a;
193 }
194 }
195 }
196 BoundsCopy(bounds, objbounds);
197 }
198
199 void
BoundsInit(bounds)200 BoundsInit(bounds)
201 Float bounds[2][3];
202 {
203 bounds[LOW][X] = bounds[LOW][Y] = bounds[LOW][Z] = FAR_AWAY;
204 bounds[HIGH][X] = bounds[HIGH][Y] = bounds[HIGH][Z] = -FAR_AWAY;
205 }
206
207 void
BoundsCopy(from,into)208 BoundsCopy(from, into)
209 Float into[2][3], from[2][3];
210 {
211 into[LOW][X] = from[LOW][X];
212 into[LOW][Y] = from[LOW][Y];
213 into[LOW][Z] = from[LOW][Z];
214 into[HIGH][X] = from[HIGH][X];
215 into[HIGH][Y] = from[HIGH][Y];
216 into[HIGH][Z] = from[HIGH][Z];
217 }
218
219 #define SetIfLess(a, b) (a = ((a) < (b) ? (a) : (b)))
220 #define SetIfGreater(a, b) (a = ((a) > (b) ? (a) : (b)))
221
222 /*
223 * Find bounding box of the union of two bounding boxes.
224 */
225 void
BoundsEnlarge(old,new)226 BoundsEnlarge(old, new)
227 Float old[2][3], new[2][3];
228 {
229 SetIfLess(old[LOW][X], new[LOW][X]);
230 SetIfLess(old[LOW][Y], new[LOW][Y]);
231 SetIfLess(old[LOW][Z], new[LOW][Z]);
232 SetIfGreater(old[HIGH][X], new[HIGH][X]);
233 SetIfGreater(old[HIGH][Y], new[HIGH][Y]);
234 SetIfGreater(old[HIGH][Z], new[HIGH][Z]);
235 }
236
237 void
BoundsPrint(box,fp)238 BoundsPrint(box, fp)
239 Float box[2][3];
240 FILE *fp;
241 {
242 fprintf(fp,"\tX: %f to %f\n",box[LOW][X], box[HIGH][X]);
243 fprintf(fp,"\tY: %f to %f\n",box[LOW][Y], box[HIGH][Y]);
244 fprintf(fp,"\tZ: %f to %f\n",box[LOW][Z], box[HIGH][Z]);
245 }
246