00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #include "boundingBox.h"
00016 #include "boundingSphere.h"
00017 #include "boundingHexahedron.h"
00018 #include "boundingLine.h"
00019 #include "boundingPlane.h"
00020 #include "config_mathutil.h"
00021 #include "dcast.h"
00022
00023 #include <math.h>
00024 #include <algorithm>
00025
00026 const int BoundingBox::plane_def[6][3] = {
00027 { 0, 4, 5 },
00028 { 4, 6, 7 },
00029 { 6, 2, 3 },
00030 { 2, 0, 1 },
00031 { 1, 5, 7 },
00032 { 2, 6, 4 },
00033 };
00034
00035 TypeHandle BoundingBox::_type_handle;
00036
00037
00038
00039
00040
00041
00042 BoundingVolume *BoundingBox::
00043 make_copy() const {
00044 return new BoundingBox(*this);
00045 }
00046
00047
00048
00049
00050
00051
00052 LPoint3 BoundingBox::
00053 get_min() const {
00054 nassertr(!is_empty(), _min);
00055 nassertr(!is_infinite(), _min);
00056 return _min;
00057 }
00058
00059
00060
00061
00062
00063
00064 LPoint3 BoundingBox::
00065 get_max() const {
00066 nassertr(!is_empty(), _max);
00067 nassertr(!is_infinite(), _max);
00068 return _max;
00069 }
00070
00071
00072
00073
00074
00075
00076 PN_stdfloat BoundingBox::
00077 get_volume() const {
00078 nassertr(!is_infinite(), 0.0f);
00079 if (is_empty()) {
00080 return 0.0f;
00081 }
00082
00083
00084 return (_max[0] - _min[0]) * (_max[1] - _min[1]) * (_max[2] - _min[2]);
00085 }
00086
00087
00088
00089
00090
00091
00092 LPoint3 BoundingBox::
00093 get_approx_center() const {
00094 nassertr(!is_empty(), LPoint3::zero());
00095 nassertr(!is_infinite(), LPoint3::zero());
00096 return (_min + _max) * 0.5f;
00097 }
00098
00099
00100
00101
00102
00103
00104 void BoundingBox::
00105 xform(const LMatrix4 &mat) {
00106 nassertv(!mat.is_nan());
00107
00108 if (!is_empty() && !is_infinite()) {
00109
00110
00111 LPoint3 x = get_point(0) * mat;
00112 LPoint3 n = x;
00113 for (int i = 1; i < 8; ++i) {
00114 LPoint3 p = get_point(i) * mat;
00115 n.set(min(n[0], p[0]), min(n[1], p[1]), min(n[2], p[2]));
00116 x.set(max(x[0], p[0]), max(x[1], p[1]), max(x[2], p[2]));
00117 }
00118 _max = x;
00119 _min = n;
00120 }
00121 }
00122
00123
00124
00125
00126
00127
00128 void BoundingBox::
00129 output(ostream &out) const {
00130 if (is_empty()) {
00131 out << "bbox, empty";
00132 } else if (is_infinite()) {
00133 out << "bbox, infinite";
00134 } else {
00135 out << "bbox, (" << _min << ") to (" << _max << ")";
00136 }
00137 }
00138
00139
00140
00141
00142
00143
00144
00145
00146 const BoundingBox *BoundingBox::
00147 as_bounding_box() const {
00148 return this;
00149 }
00150
00151
00152
00153
00154
00155
00156 bool BoundingBox::
00157 extend_other(BoundingVolume *other) const {
00158 return other->extend_by_box(this);
00159 }
00160
00161
00162
00163
00164
00165
00166 bool BoundingBox::
00167 around_other(BoundingVolume *other,
00168 const BoundingVolume **first,
00169 const BoundingVolume **last) const {
00170 return other->around_boxes(first, last);
00171 }
00172
00173
00174
00175
00176
00177
00178 int BoundingBox::
00179 contains_other(const BoundingVolume *other) const {
00180 return other->contains_box(this);
00181 }
00182
00183
00184
00185
00186
00187
00188
00189 bool BoundingBox::
00190 extend_by_point(const LPoint3 &point) {
00191 nassertr(!point.is_nan(), false);
00192
00193 if (is_empty()) {
00194 _min = point;
00195 _max = point;
00196 _flags = 0;
00197
00198 } else if (!is_infinite()) {
00199 _min.set(min(_min[0], point[0]), min(_min[1], point[1]), min(_min[2], point[2]));
00200 _max.set(max(_max[0], point[0]), max(_max[1], point[1]), max(_max[2], point[2]));
00201 }
00202
00203 return true;
00204 }
00205
00206
00207
00208
00209
00210
00211 bool BoundingBox::
00212 extend_by_box(const BoundingBox *box) {
00213 nassertr(!box->is_empty() && !box->is_infinite(), false);
00214 nassertr(!is_infinite(), false);
00215
00216 if (is_empty()) {
00217 _min = box->_min;
00218 _max = box->_max;
00219 _flags = 0;
00220
00221 } else {
00222 _min.set(min(_min[0], box->_min[0]),
00223 min(_min[1], box->_min[1]),
00224 min(_min[2], box->_min[2]));
00225 _max.set(max(_max[0], box->_max[0]),
00226 max(_max[1], box->_max[1]),
00227 max(_max[2], box->_max[2]));
00228 }
00229 return true;
00230 }
00231
00232
00233
00234
00235
00236
00237 bool BoundingBox::
00238 extend_by_finite(const FiniteBoundingVolume *volume) {
00239 nassertr(!volume->is_empty() && !volume->is_infinite(), false);
00240
00241 LVector3 min1 = volume->get_min();
00242 LVector3 max1 = volume->get_max();
00243
00244 if (is_empty()) {
00245 _min = min1;
00246 _max = max1;
00247 _flags = 0;
00248
00249 } else {
00250 _min.set(min(_min[0], min1[0]),
00251 min(_min[1], min1[1]),
00252 min(_min[2], min1[2]));
00253 _max.set(max(_max[0], max1[0]),
00254 max(_max[1], max1[1]),
00255 max(_max[2], max1[2]));
00256 }
00257
00258 return true;
00259 }
00260
00261
00262
00263
00264
00265
00266 bool BoundingBox::
00267 around_points(const LPoint3 *first, const LPoint3 *last) {
00268 nassertr(first != last, false);
00269
00270
00271 const LPoint3 *p = first;
00272
00273 #ifndef NDEBUG
00274
00275 int skipped_nan = 0;
00276 while (p != last && (*p).is_nan()) {
00277 ++p;
00278 ++skipped_nan;
00279 }
00280 if (p == last) {
00281 mathutil_cat.warning()
00282 << "BoundingBox around NaN\n";
00283 return false;
00284 }
00285 #endif
00286
00287 _min = *p;
00288 _max = *p;
00289 ++p;
00290
00291 #ifndef NDEBUG
00292
00293 while (p != last && (*p).is_nan()) {
00294 ++p;
00295 ++skipped_nan;
00296 }
00297 #endif
00298
00299 while (p != last) {
00300 #ifndef NDEBUG
00301
00302 if ((*p).is_nan()) {
00303 ++skipped_nan;
00304 } else
00305 #endif
00306 {
00307 _min.set(min(_min[0], (*p)[0]),
00308 min(_min[1], (*p)[1]),
00309 min(_min[2], (*p)[2]));
00310 _max.set(max(_max[0], (*p)[0]),
00311 max(_max[1], (*p)[1]),
00312 max(_max[2], (*p)[2]));
00313 }
00314 ++p;
00315 }
00316
00317 #ifndef NDEBUG
00318 if (skipped_nan != 0) {
00319 mathutil_cat.warning()
00320 << "BoundingBox ignored " << skipped_nan << " NaN points of "
00321 << (last - first) << " total.\n";
00322 }
00323 #endif
00324
00325 _flags = 0;
00326
00327 return true;
00328 }
00329
00330
00331
00332
00333
00334
00335 bool BoundingBox::
00336 around_finite(const BoundingVolume **first,
00337 const BoundingVolume **last) {
00338 nassertr(first != last, false);
00339
00340
00341
00342
00343
00344
00345
00346 const BoundingVolume **p = first;
00347 nassertr(!(*p)->is_empty() && !(*p)->is_infinite(), false);
00348 const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p);
00349 _min = vol->get_min();
00350 _max = vol->get_max();
00351
00352 for (++p; p != last; ++p) {
00353 nassertr(!(*p)->is_infinite(), false);
00354 if (!(*p)->is_empty()) {
00355 const FiniteBoundingVolume *vol = DCAST(FiniteBoundingVolume, *p);
00356 LPoint3 min1 = vol->get_min();
00357 LPoint3 max1 = vol->get_max();
00358 _min.set(min(_min[0], min1[0]),
00359 min(_min[1], min1[1]),
00360 min(_min[2], min1[2]));
00361 _max.set(max(_max[0], max1[0]),
00362 max(_max[1], max1[1]),
00363 max(_max[2], max1[2]));
00364 }
00365 }
00366
00367 _flags = 0;
00368 return true;
00369 }
00370
00371
00372
00373
00374
00375
00376 int BoundingBox::
00377 contains_point(const LPoint3 &point) const {
00378 nassertr(!point.is_nan(), IF_no_intersection);
00379
00380 if (is_empty()) {
00381 return IF_no_intersection;
00382
00383 } else if (is_infinite()) {
00384 return IF_possible | IF_some | IF_all;
00385
00386 } else {
00387 if (point[0] >= _min[0] && point[0] <= _max[0] &&
00388 point[1] >= _min[1] && point[1] <= _max[1] &&
00389 point[2] >= _min[2] && point[2] <= _max[2]) {
00390 return IF_possible | IF_some | IF_all;
00391 } else {
00392 return IF_no_intersection;
00393 }
00394 }
00395 }
00396
00397
00398
00399
00400
00401
00402 int BoundingBox::
00403 contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
00404 nassertr(!a.is_nan() && !b.is_nan(), IF_no_intersection);
00405
00406 if (a == b) {
00407 return contains_point(a);
00408 }
00409 if (is_empty()) {
00410 return IF_no_intersection;
00411
00412 } else if (is_infinite()) {
00413 return IF_possible | IF_some | IF_all;
00414
00415 } else {
00416
00417 unsigned int a_bits = 0;
00418
00419 if (a[0] < _min[0]) {
00420 a_bits |= 0x01;
00421 } else if (a[0] > _max[0]) {
00422 a_bits |= 0x02;
00423 }
00424
00425 if (a[1] < _min[1]) {
00426 a_bits |= 0x04;
00427 } else if (a[1] > _max[1]) {
00428 a_bits |= 0x08;
00429 }
00430
00431 if (a[2] < _min[2]) {
00432 a_bits |= 0x10;
00433 } else if (a[2] > _max[2]) {
00434 a_bits |= 0x20;
00435 }
00436
00437 unsigned int b_bits = 0;
00438
00439 if (b[0] < _min[0]) {
00440 b_bits |= 0x01;
00441 } else if (b[0] > _max[0]) {
00442 b_bits |= 0x02;
00443 }
00444
00445 if (b[1] < _min[1]) {
00446 b_bits |= 0x04;
00447 } else if (b[1] > _max[1]) {
00448 b_bits |= 0x08;
00449 }
00450
00451 if (b[2] < _min[2]) {
00452 b_bits |= 0x10;
00453 } else if (b[2] > _max[2]) {
00454 b_bits |= 0x20;
00455 }
00456
00457 if ((a_bits & b_bits) != 0) {
00458
00459
00460
00461 return IF_no_intersection;
00462
00463 } else if ((a_bits | b_bits) == 0) {
00464
00465
00466 return IF_possible | IF_some | IF_all;
00467
00468 } else if (a_bits == 0 || b_bits == 0) {
00469
00470
00471 return IF_possible | IF_some;
00472
00473 } else {
00474 unsigned int differ = (a_bits ^ b_bits);
00475 if (differ == 0x03 || differ == 0x0c || differ == 0x30) {
00476
00477
00478 return IF_possible | IF_some;
00479
00480 } else {
00481
00482 return IF_possible;
00483 }
00484 }
00485 }
00486 }
00487
00488
00489
00490
00491
00492
00493
00494
00495 int BoundingBox::
00496 contains_box(const BoundingBox *box) const {
00497 nassertr(!is_empty() && !is_infinite(), 0);
00498 nassertr(!box->is_empty() && !box->is_infinite(), 0);
00499
00500 const LPoint3 &min1 = box->get_minq();
00501 const LPoint3 &max1 = box->get_maxq();
00502
00503 if (min1[0] >= _min[0] && max1[0] <= _max[0] &&
00504 min1[1] >= _min[1] && max1[1] <= _max[1] &&
00505 min1[2] >= _min[2] && max1[2] <= _max[2]) {
00506
00507 return IF_possible | IF_some | IF_all;
00508
00509 } else if (max1[0] >= _min[0] && min1[0] <= _max[0] &&
00510 max1[1] >= _min[1] && min1[1] <= _max[1] &&
00511 max1[2] >= _min[2] && min1[2] <= _max[2]) {
00512
00513 return IF_possible;
00514
00515 } else {
00516
00517 return IF_no_intersection;
00518 }
00519 }
00520
00521
00522
00523
00524
00525
00526
00527
00528 int BoundingBox::
00529 contains_hexahedron(const BoundingHexahedron *hexahedron) const {
00530
00531
00532 int result = contains_finite(hexahedron);
00533 if (result == IF_no_intersection || ((result & IF_all) != 0)) {
00534 return result;
00535 }
00536
00537
00538
00539 return hexahedron->contains_box(this) & ~IF_all;
00540 }
00541
00542
00543
00544
00545
00546
00547
00548
00549 int BoundingBox::
00550 contains_line(const BoundingLine *line) const {
00551 return line->contains_box(this) & ~IF_all;
00552 }
00553
00554
00555
00556
00557
00558
00559
00560
00561 int BoundingBox::
00562 contains_plane(const BoundingPlane *plane) const {
00563 return plane->contains_box(this) & ~IF_all;
00564 }
00565
00566
00567
00568
00569
00570
00571 int BoundingBox::
00572 contains_finite(const FiniteBoundingVolume *volume) const {
00573 nassertr(!is_empty() && !is_infinite(), 0);
00574 nassertr(!volume->is_empty() && !volume->is_infinite(), 0);
00575
00576 LPoint3 min1 = volume->get_min();
00577 LPoint3 max1 = volume->get_max();
00578
00579 if (min1[0] >= _min[0] && max1[0] <= _max[0] &&
00580 min1[1] >= _min[1] && max1[1] <= _max[1] &&
00581 min1[2] >= _min[2] && max1[2] <= _max[2]) {
00582
00583 return IF_possible | IF_some | IF_all;
00584
00585 } else if (max1[0] >= _min[0] && min1[0] <= _max[0] &&
00586 max1[1] >= _min[1] && min1[1] <= _max[1] &&
00587 max1[2] >= _min[2] && min1[2] <= _max[2]) {
00588
00589 return IF_possible;
00590
00591 } else {
00592
00593 return IF_no_intersection;
00594 }
00595 }