Debian Codegraph @

lib/database/src/sb/SbBox.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 /*
38 * Copyright (C) 1990,91 Silicon Graphics, Inc.
39 *
40 _______________________________________________________________________
41 ______________ S I L I C O N G R A P H I C S I N C . ____________
42 |
43 | $Revision: 1.2 $
44 |
45 | Classes:
46 | SbBox3f
47 | SbXfBox3f
48 | SbBox2f
49 | SbBox2s
50 |
51 | Author(s) : Paul S. Strauss, Nick Thompson
52 |
53 ______________ S I L I C O N G R A P H I C S I N C . ____________
54 _______________________________________________________________________
55 */
56
57 #include <Inventor/SbBox.h>
58 #include <Inventor/errors/SoDebugError.h>
59 #include <climits>
60 #include <float.h> /* For FLT_MAX */
61
62 //
63 // Return the center of a box
64 //
65
66 SbVec3f
67 SbBox3f::getCenter() const
68 {
69 return SbVec3f(0.5 * (min[0] + max[0]),
70 0.5 * (min[1] + max[1]),
71 0.5 * (min[2] + max[2]));
72 }
73
74 //
75 // Extends Box3f (if necessary) to contain given 3D point
76 //
77
78 void
79 SbBox3f::extendBy(const SbVec3f &pt)
80 {
81 if (pt[0] < min[0]) min[0] = pt[0];
82 if (pt[1] < min[1]) min[1] = pt[1];
83 if (pt[2] < min[2]) min[2] = pt[2];
84 if (pt[0] > max[0]) max[0] = pt[0];
85 if (pt[1] > max[1]) max[1] = pt[1];
86 if (pt[2] > max[2]) max[2] = pt[2];
87 }
88
89 //
90 // Extends Box3f (if necessary) to contain given Box3f
91 //
92
93 void
94 SbBox3f::extendBy(const SbBox3f &bb)
95 {
96 if (bb.min[0] < min[0]) min[0] = bb.min[0];
97 if (bb.min[1] < min[1]) min[1] = bb.min[1];
98 if (bb.min[2] < min[2]) min[2] = bb.min[2];
99 if (bb.max[0] > max[0]) max[0] = bb.max[0];
100 if (bb.max[1] > max[1]) max[1] = bb.max[1];
101 if (bb.max[2] > max[2]) max[2] = bb.max[2];
102 }
103
104 //
105 // Returns TRUE if intersection of given point and Box3f is not empty
106 //
107
108 SbBool
109 SbBox3f::intersect(const SbVec3f &pt) const
110 {
111 return ((pt[0] >= min[0]) &&
112 (pt[1] >= min[1]) &&
113 (pt[2] >= min[2]) &&
114 (pt[0] <= max[0]) &&
115 (pt[1] <= max[1]) &&
116 (pt[2] <= max[2]));
117 }
118
119 //
120 // Returns TRUE if intersection of given Box3f and Box3f is not empty
121 //
122
123 SbBool
124 SbBox3f::intersect(const SbBox3f &bb) const
125 {
126 return ((bb.max[0] >= min[0]) && (bb.min[0] <= max[0]) &&
127 (bb.max[1] >= min[1]) && (bb.min[1] <= max[1]) &&
128 (bb.max[2] >= min[2]) && (bb.min[2] <= max[2]));
129 }
130
131
132 //
133 // View-volume culling: axis-aligned bounding box against view volume,
134 // given as Model/View/Projection matrix.
135 //
136 //
137 // Inputs:
138 // MVP: Matrix from object to NDC space
139 // (model/view/projection)
140 // Inputs/Outputs:
141 // cullBits: Keeps track of which planes we need to test against.
142 // Has three bits, for X, Y and Z. If cullBits is 0,
143 // then the bounding box is completely inside the view
144 // and no further cull tests need be done for things
145 // inside the bounding box. Zero bits in cullBits mean
146 // the bounding box is completely between the
147 // left/right, top/bottom, or near/far clipping planes.
148 // Outputs:
149 // SbBool: TRUE if bbox is completely outside view volume
150 // defined by MVP.
151 //
152
153 //
154 // How:
155 //
156 // An axis-aligned bounding box is the set of all points P,
157 // Pmin < P < Pmax. We're interested in finding out whether or not
158 // any of those points P are clipped after being transformed through
159 // MVP (transformed into clip space).
160 //
161 // A transformed point P'[x,y,z,w] is inside the view if [x,y,z] are
162 // all between -w and w. Otherwise the point is outside the view.
163 //
164 // Instead of testing individual points, we want to treat the range of
165 // points P. We want to know if: All points P are clipped (in which
166 // case the cull test succeeds), all points P are NOT clipped (in
167 // which case they are completely inside the view volume and no more
168 // cull tests need be done for objects inside P), or some points are
169 // clipped and some aren't.
170 //
171 // P transformed into clip space is a 4-dimensional solid, P'. To
172 // speed things up, this algorithm finds the 4-dimensional,
173 // axis-aligned bounding box of that solid and figures out whether or
174 // not that bounding box intersects any of the sides of the view
175 // volume. In the 4D space with axes x,y,z,w, the view volume planes
176 // are the planes x=w, x=-w, y=w, y=-w, z=w, z=-w.
177 //
178 // This is all easier to think about if we think about each of the X,
179 // Y, Z axes in clip space independently; worrying only about the X
180 // axis for a moment:
181 //
182 // The idea is to find the minimum and maximum possible X,W
183 // coordinates of P'. If all of the points in the
184 // [(Xmin,Xmax),(Wmin,Wmax)] range satisfy -|W| < X < |W| (|W| is
185 // absolute value of W), then the original bounding box P is
186 // completely inside the X-axis (left/right) clipping planes of the
187 // view volume. In (x,w) space, a point (x,w) is clipped depending on
188 // which quadrant it is in:
189 //
190 // x=-w x=w
191 // \ Q0 /
192 // \ IN /
193 // \ /
194 // \ /
195 // Q1 \/ Q2
196 // CLIPPED /\ CLIPPED
197 // / \
198 // / \
199 // / Q3 \
200 // / CLIPPED\
201 //
202 // If the axis-aligned box [(Xmin,Xmax),(Wmin,Wmax)] lies entirely in
203 // Q0, then it is entirely inside the X-axis clipping planes (IN
204 // case). If it is not in Q0 at all, then it is clipped (OUT). If it
205 // straddles Q0 and some other quadrant, the bounding box intersects
206 // the clipping planes (STRADDLE). The 4 corners of the bounding box
207 // are tested first using bitwise tests on their quadrant numbers; if
208 // they determine the case is STRADDLE then a more refined test is
209 // done on the 8 points of the original bounding box.
210 // The test isn't perfect-- a bounding box that straddles both Q1 and
211 // Q2 may be incorrectly classified as STRADDLE; however, those cases
212 // are rare and the cases that are incorrectly classified will likely
213 // be culled when testing against the other clipping planes (these
214 // cases are cases where the bounding box is near the eye).
215 //
216 // Finding [(Xmin,Xmax),(Wmin,Wmax)] is easy. Consider Xmin. It is
217 // the smallest X coordinate when all of the points in the range
218 // Pmin,Pmax are transformed by MVP; written out:
219 // X = P[0]*M[0][0] + P[1]*M[1][0] + P[2]*M[2][0] + M[3][0]
220 // X will be minimized when each of the terms is minimized. If the
221 // matrix entry for the term is positive, then the term is minimized
222 // by choosing Pmin; if the matrix entry is negative, the term is
223 // minimized by choosing Pmax. Three 'if' test will let us calculate
224 // the transformed Xmin. Xmax can be calculated similarly.
225 //
226 // Testing for IN/OUT/STRADDLE for the Y and Z coordinates is done
227 // exactly the same way.
228 //
229
230 //
231 // Helper functions:
232 //
233 // Given a range in object space, find the minimum or maximum for the
234 // X,Y,Z or W coordinates in the transformed space.
235 // 3 multiplies, 3 adds, 3 comparisons/branches.
236 // Reverse min and max for the opposite test...
237 static inline float
238 minExtreme(const SbVec3f &min, const SbVec3f &max, const
239 SbMatrix &MVP, int whichCoord) {
240 return
241 (MVP[0][whichCoord]>0.0f ? min[0] : max[0])*MVP[0][whichCoord] +
242 (MVP[1][whichCoord]>0.0f ? min[1] : max[1])*MVP[1][whichCoord] +
243 (MVP[2][whichCoord]>0.0f ? min[2] : max[2])*MVP[2][whichCoord] +
244 MVP[3][whichCoord];
245 }
246
247 static inline int
248 quadrant(float x, float y) {
249 return (x < -y) | ((x > y) << 1);
250 }
251
252 static int
253 findQuadrant(float x, float y, float z,
254 int n, const SbMatrix &MVP)
255 {
256 float c = MVP[0][n]*x + MVP[1][n]*y + MVP[2][n]*z + MVP[3][n] ;
257 float w = MVP[0][3]*x + MVP[1][3]*y + MVP[2][3]*z + MVP[3][3] ;
258 return quadrant(c, w);
259 }
260
261 SbBool
262 SbBox3f::outside(const SbMatrix &MVP, int &cullBits) const
263 {
264 float Wmax = minExtreme(max, min, MVP, 3);
265 if (Wmax < 0) return TRUE;
266
267 float Wmin = minExtreme(min, max, MVP, 3);
268
269 // Do each coordinate:
270 for (int i = 0; i < 3; i++) {
271 if (cullBits & (1<<i)) { // STRADDLES:
272 float Cmin = minExtreme(min, max, MVP, i);
273
274 // The and_bits and or_bits are used to keep track of
275 // which quadrants point lie in. The cases are:
276 //
277 // All in Q0: IN
278 // (or_bits == 0) --> and_bits MUST also be 0
279 // Some/all in Q1, some/all in Q3: CULLED
280 // Some/all in Q2, some/none in Q3: CULLED
281 // (and_bits != 0, or_bits != 0)
282 // Some in Q1, some in Q2, some/none in Q3: STRADDLE
283 // (and_bits == 0, or_bits !=0)
284 //
285 int and_bits;
286 int or_bits;
287 and_bits = or_bits = quadrant(Cmin, Wmin);
288
289 int q0 = quadrant(Cmin, Wmax);
290 and_bits &= q0;
291 or_bits |= q0;
292 // Hit the STRADDLE case as soon as and_bits == 0 and
293 // or_bits != 0:
294 if (!(and_bits == 0 && or_bits != 0)) {
295 float Cmax = minExtreme(max, min, MVP, i);
296
297 q0 = quadrant(Cmax, Wmin);
298 and_bits &= q0;
299 or_bits |= q0;
300 if (!(and_bits == 0 && or_bits != 0)) {
301 q0 = quadrant(Cmax, Wmax);
302 and_bits &= q0;
303 or_bits |= q0;
304
305 // Either completely IN or completely OUT:
306 if (or_bits == 0) { // IN
307 cullBits &= ~(1<<i); // Clear bit
308 continue; // Continue for loop
309 }
310 else if (and_bits != 0) {
311 return TRUE; // CULLED
312 }
313 }
314 }
315
316 // Before we give up and just claim it straddles, do a
317 // more refined test-- check the 8 corners of the
318 // bounding box:
319
320 // Test to see if all 8 corner points of the bounding box
321 // are in the same quadrant. If so, the object is either
322 // completely in or out of the view. Otherwise, it straddles
323 // at least one of the view boundaries.
324 and_bits = or_bits = findQuadrant(min[0], min[1], min[2], i, MVP);
325 if (and_bits == 0 && or_bits != 0) continue;
326
327 q0 = findQuadrant(max[0], max[1], max[2], i, MVP);
328 and_bits &= q0;
329 or_bits |= q0;
330 if (and_bits == 0 && or_bits != 0) continue;
331
332 q0 = findQuadrant(max[0], min[1], min[2], i, MVP);
333 and_bits &= q0;
334 or_bits |= q0;
335 if (and_bits == 0 && or_bits != 0) continue;
336
337 q0 = findQuadrant(min[0], max[1], max[2], i, MVP);
338 and_bits &= q0;
339 or_bits |= q0;
340 if (and_bits == 0 && or_bits != 0) continue;
341
342 q0 = findQuadrant(min[0], max[1], min[2], i, MVP);
343 and_bits &= q0;
344 or_bits |= q0;
345 if (and_bits == 0 && or_bits != 0) continue;
346
347 q0 = findQuadrant(max[0], min[1], max[2], i, MVP);
348 and_bits &= q0;
349 or_bits |= q0;
350 if (and_bits == 0 && or_bits != 0) continue;
351
352 q0 = findQuadrant(max[0], max[1], min[2], i, MVP);
353 and_bits &= q0;
354 or_bits |= q0;
355 if (and_bits == 0 && or_bits != 0) continue;
356
357 q0 = findQuadrant(min[0], min[1], max[2], i, MVP);
358 and_bits &= q0;
359 or_bits |= q0;
360
361 // Either completely IN or completely OUT:
362 if (or_bits == 0) { // IN
363 cullBits &= ~(1<<i); // Clear bit
364 continue; // Continue for loop
365 }
366 else if (and_bits != 0) {
367 return TRUE; // CULLED
368 }
369 }
370 }
371 return FALSE; // Not culled
372 }
373
374 //
375 // Sets Box3f to contain nothing
376 //
377
378 void
379 SbBox3f::makeEmpty()
380 {
381 min.setValue(FLT_MAX, FLT_MAX, FLT_MAX);
382 max.setValue(- FLT_MAX, - FLT_MAX, - FLT_MAX);
383 }
384
385
386
387 ////////////////////////////////////////////////////////////////////////
388 //
389 // Description:
390 // Gets the closest point to the box to the given point. If the
391 // given point is dead center, returns the point centered on the
392 // positive X side.
393 //
394 // Use: public
395
396 SbVec3f
397 SbBox3f::getClosestPoint(const SbVec3f &point)
398 //
399 ////////////////////////////////////////////////////////////////////////
400 {
401 SbVec3f result;
402
403 // trivial cases first
404 if (isEmpty())
405 return point;
406 else if (point == getCenter()) {
407 // middle of z side
408 result[0] = (max[0] + min[0])/2.0;
409 result[1] = (max[1] + min[1])/2.0;
410 result[2] = max[2];
411 }
412 else {
413 // Find the closest point on a unit box (from -1 to 1),
414 // then scale up.
415
416 // Find the vector from center to the point, then scale
417 // to a unit box.
418 SbVec3f vec = point - getCenter();
419 float sizeX, sizeY, sizeZ;
420 getSize(sizeX, sizeY, sizeZ);
421 float halfX = sizeX/2.0;
422 float halfY = sizeY/2.0;
423 float halfZ = sizeZ/2.0;
424 if (halfX > 0.0)
425 vec[0] /= halfX;
426 if (halfY > 0.0)
427 vec[1] /= halfY;
428 if (halfZ > 0.0)
429 vec[2] /= halfZ;
430
431 // Side to snap side that has greatest magnitude in the vector.
432 SbVec3f mag;
433 mag[0] = fabs(vec[0]);
434 mag[1] = fabs(vec[1]);
435 mag[2] = fabs(vec[2]);
436
437 result = mag;
438
439 // Check if beyond corners
440 if (result[0] > 1.0)
441 result[0] = 1.0;
442 if (result[1] > 1.0)
443 result[1] = 1.0;
444 if (result[2] > 1.0)
445 result[2] = 1.0;
446
447 // snap to appropriate side
448 if ((mag[0] > mag[1]) && (mag[0] > mag[2])) {
449 result[0] = 1.0;
450 }
451 else if ((mag[1] > mag[0]) && (mag[1] > mag[2])) {
452 result[1] = 1.0;
453 }
454 else if ((mag[2] > mag[0]) && (mag[2] > mag[1])) {
455 result[2] = 1.0;
456 }
457 else if ((mag[0] == mag[1]) && (mag[0] == mag[2])) {
458 // corner
459 result = SbVec3f(1,1,1);
460 }
461 else if (mag[0] == mag[1]) {
462 // edge parallel with z
463 result[0] = 1.0;
464 result[1] = 1.0;
465 }
466 else if (mag[0] == mag[2]) {
467 // edge parallel with y
468 result[0] = 1.0;
469 result[2] = 1.0;
470 }
471 else if (mag[1] == mag[2]) {
472 // edge parallel with x
473 result[1] = 1.0;
474 result[2] = 1.0;
475 }
476 #ifdef DEBUG
477 else
478 SoDebugError::post("SbBox3f::getClosestPoint",
479 "Can't determine vector to point");
480 #endif
481 // Now make everything point the right way
482 for (int i=0; i < 3; i++)
483 if (vec[i] < 0.0)
484 result[i] = -result[i];
485
486 // scale back up and move to center
487 result[0] *= halfX;
488 result[1] *= halfY;
489 result[2] *= halfZ;
490
491 result += getCenter();
492 }
493
494 return result;
495 }
496
497 //
498 // Finds the span of a bounding box along a particular direction
499 //
500
501 void
502 SbBox3f::getSpan(const SbVec3f &direction, float &dMin, float &dMax) const
503 {
504 int i;
505 SbVec3f points[8];
506 SbVec3f dir = direction;
507
508 dir.normalize();
509
510 /* Set up the eight points at the corners of the extent */
511 points[0][2] = points[2][2] = points[4][2] = points[6][2] = min[2];
512 points[1][2] = points[3][2] = points[5][2] = points[7][2] = max[2];
513
514 points[0][0] = points[1][0] = points[2][0] = points[3][0] = min[0];
515 points[4][0] = points[5][0] = points[6][0] = points[7][0] = max[0];
516
517 points[0][1] = points[1][1] = points[4][1] = points[5][1] = min[1];
518 points[2][1] = points[3][1] = points[6][1] = points[7][1] = max[1];
519
520 points[0][2] = points[2][2] = points[4][2] = points[6][2] = min[2];
521 points[1][2] = points[3][2] = points[5][2] = points[7][2] = max[2];
522
523 dMin = FLT_MAX;
524 dMax = - FLT_MAX;
525
526 for (i = 0; i < 8; i++) {
527 float proj = points[i].dot(dir);
528 if (proj < dMin)
529 dMin = proj;
530 if (proj > dMax)
531 dMax = proj;
532 }
533 }
534
535 //
536 // Transforms Box3f by matrix, enlarging Box3f to contain result.
537 // Clever method courtesy of Graphics Gems, pp. 548-550
538 //
539 // This works for projection matrices as well as simple affine
540 // transformations. Coordinates of the box are rehomogenized if there
541 // is a projection matrix
542 //
543
544 void
545 SbBox3f::transform(const SbMatrix &m)
546 {
547 // a transformed empty box is still empty
548 if (isEmpty())
549 return;
550
551 SbVec3f newMin, newMax;
552 int i;
553
554 for (i = 0; i < 3; i++) {
555 newMin[i] = minExtreme(min, max, m, i);
556 newMax[i] = minExtreme(max, min, m, i);
557 }
558 float Wmin = minExtreme(min, max, m, 3);
559 float Wmax = minExtreme(max, min, m, 3);
560
561 // Division by small W's make things bigger; wacky things happen
562 // if W's are negative, but negative W's are wacky so I think
563 // that's OK:
564
565 newMin /= Wmax;
566 newMax /= Wmin;
567
568 min = newMin;
569 max = newMax;
570 }
571
572
573 //
574 // Finds the volume of the box (0 for an empty box)
575 //
576
577 float
578 SbBox3f::getVolume() const
579 {
580 if (isEmpty())
581 return 0.0;
582
583 return (max[0] - min[0]) * (max[1] - min[1]) * (max[2] - min[2]);
584 }
585
586 //////////////////////////////////////////////////////////////////////////////
587 //
588 // Equality comparison operator.
589 //
590 int
591 operator ==(const SbBox3f &b1, const SbBox3f &b2)
592 //////////////////////////////////////////////////////////////////////////////
593 {
594 return ( (b1.min == b2.min) && (b1.max == b2.max ) );
595 }
596
597 //
598 // Default constructor - leaves box totally empty
599 //
600 SbXfBox3f::SbXfBox3f()
601 {
602 xform.makeIdentity();
603 xformInv.makeIdentity();
604 makeEmpty();
605 }
606
607 //
608 // Constructor given minimum and maximum points
609 //
610 SbXfBox3f::SbXfBox3f(const SbVec3f &_min, const SbVec3f &_max)
611 {
612 xform.makeIdentity();
613 xformInv.makeIdentity();
614 setBounds(_min, _max);
615 }
616
617 //
618 // Constructor given Box3f
619 //
620 SbXfBox3f::SbXfBox3f(const SbBox3f &box)
621 {
622 xform.makeIdentity();
623 xformInv.makeIdentity();
624 *(SbBox3f *)this = box;
625 }
626
627 #define PRECISION_LIMIT (1.0e-13)
628
629 //
630 // Set the transformation on the box. This is careful about
631 // non-invertable transformations.
632 //
633 void
634 SbXfBox3f::setTransform(const SbMatrix &m)
635 {
636 xform = m;
637
638 // Check for degenerate matrix:
639 float det = m.det4();
640 if (det < PRECISION_LIMIT && det > -PRECISION_LIMIT) {
641 // We'll mark inverse[0][0] with FLT_MAX (max floating point
642 // value) as special value to indicate degenerate transform.
643 xformInv = SbMatrix(FLT_MAX,0,0,0,
644 0,0,0,0, 0,0,0,0, 0,0,0,0);
645 } else {
646 xformInv = m.inverse();
647 }
648 }
649
650 #undef PRECISION_LIMIT
651
652 //
653 // Return the center of a box
654 //
655 SbVec3f
656 SbXfBox3f::getCenter() const
657 {
658 SbVec3f p;
659
660 // transform the center before returning it
661 xform.multVecMatrix(.5 * (getMin() + getMax()), p);
662
663 return p;
664 }
665
666 //
667 // Extend (if necessary) to contain given 3D point
668 //
669 void
670 SbXfBox3f::extendBy(const SbVec3f &pt)
671 {
672 // If our transform is degenerate, project this box, which will
673 // transform min/max and get a box with identity xforms:
674 if (xformInv[0][0] == FLT_MAX) {
675 *this = SbXfBox3f(this->project());
676 }
677
678 SbVec3f p;
679 xformInv.multVecMatrix(pt, p);
680 SbBox3f::extendBy(p);
681 }
682
683 //
684 // Finds the volume of the box (0 for an empty box)
685 //
686
687 float
688 SbXfBox3f::getVolume() const
689 {
690 if (isEmpty())
691 return 0.0;
692
693 // The volume of a transformed box is just its untransformed
694 // volume times the determinant of the upper-left 3x3 of
695 // the xform matrix. Quoth Paul Strauss: "Pretty cool, indeed."
696 float objVol = SbBox3f::getVolume();
697 float factor = xform.det3();
698 return factor * objVol;
699 }
700
701 //
702 // Extends XfBox3f (if necessary) to contain given XfBox3f
703 //
704
705 void
706 SbXfBox3f::extendBy(const SbXfBox3f &bb)
707 {
708 if (bb.isEmpty()) // bb is empty, no change
709 return;
710 else if (isEmpty()) // we're empty, use bb
711 *this = bb;
712
713 else if (xformInv[0][0] != FLT_MAX && bb.xformInv[0][0] != FLT_MAX) {
714 // Neither box is empty and they are in different spaces. To
715 // get the best results, we'll perform the merge of the two
716 // boxes in each of the two spaces. Whichever merge ends up
717 // being smaller is the one we'll use.
718 // Note that we don't perform a project() as part of the test.
719 // This is because projecting almost always adds a little extra
720 // space. It also gives an unfair advantage to the
721 // box more closely aligned with world space. In the simplest
722 // case this might be preferable. However, over many objects,
723 // we are better off going with the minimum in local space,
724 // and not worrying about projecting until the very end.
725
726 SbXfBox3f xfbox1, xfbox2;
727 SbBox3f box1, box2;
728
729 // Convert bb into this's space to get box1
730 xfbox1 = bb;
731 // Rather than calling transform(), which calls inverse(),
732 // we'll do it ourselves, since we already know the inverse matrix.
733 // I.e., we could call: xfbox1.transform(xformInv);
734 xfbox1.xform *= xformInv;
735 xfbox1.xformInv.multRight(xform);
736 box1 = xfbox1.project();
737
738 // Convert this into bb's space to get box2
739 xfbox2 = *this;
740 // Same here for: xfbox2.transform(bb.xformInv);
741 xfbox2.xform *= bb.xformInv;
742 xfbox2.xformInv.multRight(bb.xform);
743 box2 = xfbox2.project();
744
745 // Extend this by box1 to get xfbox1
746 xfbox1 = *this;
747 xfbox1.SbBox3f::extendBy(box1);
748 // Use SbBox3f method; box1 is already in xfbox1's space
749 // (otherwise, we'll get an infinite loop!)
750
751 // Extend bb by box2 to get xfbox2
752 xfbox2 = bb;
753 xfbox2.SbBox3f::extendBy(box2);
754 // Use SbBox3f method; box2 is already in xfbox2's space
755 // (otherwise, we'll get an infinite loop!)
756
757 float vol1 = xfbox1.getVolume();
758 float vol2 = xfbox2.getVolume();
759
760 // Take the smaller result and extend appropriately
761 if (vol1 <= vol2) {
762 SbBox3f::extendBy(box1);
763 }
764 else {
765 *this = bb;
766 SbBox3f::extendBy(box2);
767 }
768 }
769 else if (xformInv[0][0] == FLT_MAX) {
770 if (bb.xformInv[0][0] == FLT_MAX) {
771 // Both boxes are degenerate; project them both and
772 // combine them:
773 SbBox3f box = this->project();
774 box.extendBy(bb.project());
775 *this = SbXfBox3f(box);
776 } else {
777 // this is degenerate; transform our min/max into bb's
778 // space, and combine there:
779 SbBox3f box(getMin(), getMax());
780 box.transform(xform*bb.xformInv);
781 *this = bb;
782 SbBox3f::extendBy(box);
783 }
784 } else {
785 // bb is degenerate; transform it into our space and combine:
786 SbBox3f box(bb.getMin(), bb.getMax());
787 box.transform(bb.xform*xformInv);
788 SbBox3f::extendBy(box);
789 }
790 }
791
792 //
793 // Returns TRUE if intersection of given point and Box3f is not empty
794 // (being careful about degenerate transformations...).
795 //
796 SbBool
797 SbXfBox3f::intersect(const SbVec3f &pt) const
798 {
799 if (xformInv[0][0] != FLT_MAX) {
800 SbVec3f p;
801 xformInv.multVecMatrix(pt, p);
802 return SbBox3f::intersect(p);
803 }
804 SbBox3f box = this->project(); // Degenerate; project and test:
805 return box.intersect(pt);
806 }
807
808 //
809 // Transform this box by a matrix
810 //
811 void
812 SbXfBox3f::transform(const SbMatrix &m)
813 {
814 SbMatrix new_xf = xform*m;
815 setTransform(new_xf);
816 }
817
818
819 //////////////////////////////////////////////////////////////////////////////
820 //
821 // Equality comparison operator.
822 //
823 int
824 operator ==(const SbXfBox3f &b1, const SbXfBox3f &b2)
825 //////////////////////////////////////////////////////////////////////////////
826 {
827 SbBox3f b1Proj = b1.project();
828 SbBox3f b2Proj = b2.project();
829 return (b1Proj == b2Proj);
830 }
831
832 //
833 // Projects an SbXfBox to an SbBox
834 //
835
836 SbBox3f
837 SbXfBox3f::project() const
838 {
839 SbBox3f box(getMin(), getMax());
840 box.transform(xform);
841 return box;
842 }
843
844 //
845 // Return the center of a box
846 //
847
848 SbVec2f
849 SbBox2f::getCenter() const
850 {
851 return SbVec2f(0.5 * (min[0] + max[0]),
852 0.5 * (min[1] + max[1]));
853 }
854
855 //////////////////////////////////////////////////////////////////////////////
856 //
857 // Extends Box2f (if necessary) to contain given 2D point
858 //
859 void
860 SbBox2f::extendBy(const SbVec2f &pt)
861 //
862 //////////////////////////////////////////////////////////////////////////////
863 {
864 if (pt[0] < min[0]) min[0] = pt[0];
865 if (pt[0] > max[0]) max[0] = pt[0];
866
867 if (pt[1] < min[1]) min[1] = pt[1];
868 if (pt[1] > max[1]) max[1] = pt[1];
869 }
870
871 //////////////////////////////////////////////////////////////////////////////
872 //
873 // Extends Box2f (if necessary) to contain given Box2f
874 //
875 void
876 SbBox2f::extendBy(const SbBox2f &r)
877 //
878 //////////////////////////////////////////////////////////////////////////////
879 {
880 if (r.min[0] < min[0]) min[0] = r.min[0];
881 if (r.max[0] > max[0]) max[0] = r.max[0];
882 if (r.min[1] < min[1]) min[1] = r.min[1];
883 if (r.max[1] > max[1]) max[1] = r.max[1];
884 }
885
886 //////////////////////////////////////////////////////////////////////////////
887 //
888 // Returns TRUE if intersection of given point and Box2f is not empty
889 //
890 SbBool
891 SbBox2f::intersect(const SbVec2f &pt) const
892 //
893 //////////////////////////////////////////////////////////////////////////////
894 {
895 return ((pt[0] >= min[0]) &&
896 (pt[1] >= min[1]) &&
897 (pt[0] <= max[0]) &&
898 (pt[1] <= max[1]));
899 }
900
901 //////////////////////////////////////////////////////////////////////////////
902 //
903 // Returns TRUE if intersection of given Box2f and Box2f is not empty
904 //
905 SbBool
906 SbBox2f::intersect(const SbBox2f &r) const
907 //
908 //////////////////////////////////////////////////////////////////////////////
909 {
910 return ((r.max[0] >= min[0]) && (r.min[0] <= max[0]) &&
911 (r.max[1] >= min[1]) && (r.min[1] <= max[1]));
912 }
913
914
915 //////////////////////////////////////////////////////////////////////////////
916 //
917 // Sets Box2f to contain nothing
918 //
919 void
920 SbBox2f::makeEmpty()
921 //
922 //////////////////////////////////////////////////////////////////////////////
923 {
924 min.setValue( FLT_MAX, FLT_MAX);
925 max.setValue(-FLT_MAX, -FLT_MAX);
926 }
927
928 //////////////////////////////////////////////////////////////////////////////
929 //
930 // Equality comparison operator.
931 //
932 int
933 operator ==(const SbBox2f &b1, const SbBox2f &b2)
934 //////////////////////////////////////////////////////////////////////////////
935 {
936 return ( (b1.min == b2.min) && (b1.max == b2.max ) );
937 }
938
939
940 //////////////////////////////////////////////////////////////////////////////
941 //
942 // Extends Box2s (if necessary) to contain given 2D point
943 //
944 void
945 SbBox2s::extendBy(const SbVec2s &pt)
946 //
947 //////////////////////////////////////////////////////////////////////////////
948 {
949 if (pt[0] < min[0]) min[0] = pt[0];
950 if (pt[0] > max[0]) max[0] = pt[0];
951
952 if (pt[1] < min[1]) min[1] = pt[1];
953 if (pt[1] > max[1]) max[1] = pt[1];
954 }
955
956 //////////////////////////////////////////////////////////////////////////////
957 //
958 // Extends Box2s (if necessary) to contain given Box2s
959 //
960 void
961 SbBox2s::extendBy(const SbBox2s &r)
962 //
963 //////////////////////////////////////////////////////////////////////////////
964 {
965 if (r.min[0] < min[0]) min[0] = r.min[0];
966 if (r.max[0] > max[0]) max[0] = r.max[0];
967 if (r.min[1] < min[1]) min[1] = r.min[1];
968 if (r.max[1] > max[1]) max[1] = r.max[1];
969 }
970
971 //////////////////////////////////////////////////////////////////////////////
972 //
973 // Returns TRUE if intersection of given point and Box2s is not empty
974 //
975 SbBool
976 SbBox2s::intersect(const SbVec2s &pt) const
977 //
978 //////////////////////////////////////////////////////////////////////////////
979 {
980 return ((pt[0] >= min[0]) &&
981 (pt[1] >= min[1]) &&
982 (pt[0] <= max[0]) &&
983 (pt[1] <= max[1]));
984 }
985
986 //////////////////////////////////////////////////////////////////////////////
987 //
988 // Returns TRUE if intersection of given Box2s and Box2s is not empty
989 //
990 SbBool
991 SbBox2s::intersect(const SbBox2s &r) const
992 //
993 //////////////////////////////////////////////////////////////////////////////
994 {
995 return ((r.max[0] >= min[0]) && (r.min[0] <= max[0]) &&
996 (r.max[1] >= min[1]) && (r.min[1] <= max[1]));
997 }
998
999
1000 //////////////////////////////////////////////////////////////////////////////
1001 //
1002 // Sets Box2s to contain nothing
1003 //
1004 void
1005 SbBox2s::makeEmpty()
1006 //
1007 //////////////////////////////////////////////////////////////////////////////
1008 {
1009 min.setValue(SHRT_MAX, SHRT_MAX);
1010 max.setValue(SHRT_MIN, SHRT_MIN);
1011 }
1012
1013 //////////////////////////////////////////////////////////////////////////////
1014 //
1015 // Equality comparison operator.
1016 //
1017 int
1018 operator ==(const SbBox2s &b1, const SbBox2s &b2)
1019 //////////////////////////////////////////////////////////////////////////////
1020 {
1021 return ( (b1.min == b2.min) && (b1.max == b2.max ) );
1022 }
1023
1024 ////////////////////////////////////////////////////////////////////////
1025 //
1026 // Description:
1027 // Gets the closest point to the box to the given point. If the
1028 // given point is dead center, returns the point centered on the
1029 // positive X side.
1030 //
1031 // Use: public
1032
1033 SbVec2f
1034 SbBox2f::getClosestPoint(const SbVec2f &point)
1035 //
1036 ////////////////////////////////////////////////////////////////////////
1037 {
1038 SbVec2f result;
1039
1040 // trivial cases first
1041 if (isEmpty())
1042 return point;
1043 else if (point == getCenter()) {
1044 // middle of x side
1045 result[0] = max[0];
1046 result[1] = (max[1] + min[1])/2.0;
1047 }
1048 else if (min[0] == max[0]) {
1049 result[0] = min[0];
1050 result[1] = point[1];
1051 }
1052 else if (min[1] == max[1]) {
1053 result[0] = point[0];
1054 result[1] = min[1];
1055 }
1056 else {
1057 // Find the closest point on a unit box (from -1 to 1),
1058 // then scale up.
1059
1060 // Find the vector from center to the point, then scale
1061 // to a unit box.
1062 SbVec2f vec = point - getCenter();
1063 float sizeX, sizeY;
1064 getSize(sizeX, sizeY);
1065 float halfX = sizeX/2.0;
1066 float halfY = sizeY/2.0;
1067 if (halfX > 0.0)
1068 vec[0] /= halfX;
1069 if (halfY > 0.0)
1070 vec[1] /= halfY;
1071
1072 // Side to snap to has greatest magnitude in the vector.
1073 float magX = fabs(vec[0]);
1074 float magY = fabs(vec[1]);
1075
1076 if (magX > magY) {
1077 result[0] = (vec[0] > 0) ? 1.0 : -1.0;
1078 if (magY > 1.0)
1079 magY = 1.0;
1080 result[1] = (vec[1] > 0) ? magY : -magY;
1081 }
1082 else if (magY > magX) {
1083 if (magX > 1.0)
1084 magX = 1.0;
1085 result[0] = (vec[0] > 0) ? magX : -magX;
1086 result[1] = (vec[1] > 0) ? 1.0 : -1.0;
1087 }
1088 else {
1089 // must be one of the corners
1090 result[0] = (vec[0] > 0) ? 1.0 : -1.0;
1091 result[1] = (vec[1] > 0) ? 1.0 : -1.0;
1092 }
1093
1094 // scale back the result and move it to the center of the box
1095 result[0] *= halfX;
1096 result[1] *= halfY;
1097 result += getCenter();
1098 }
1099
1100 return result;
1101 }