aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/linden/indra/test/math.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--linden/indra/test/math.cpp442
1 files changed, 441 insertions, 1 deletions
diff --git a/linden/indra/test/math.cpp b/linden/indra/test/math.cpp
index 9cab3fe..405b8a3 100644
--- a/linden/indra/test/math.cpp
+++ b/linden/indra/test/math.cpp
@@ -34,9 +34,13 @@
34#include "linden_common.h" 34#include "linden_common.h"
35#include "lltut.h" 35#include "lltut.h"
36 36
37#include "llcrc.h"
38#include "llline.h"
37#include "llmath.h" 39#include "llmath.h"
40#include "llrand.h"
41#include "llsphere.h"
38#include "lluuid.h" 42#include "lluuid.h"
39#include "llcrc.h" 43#include "v3math.h"
40 44
41namespace tut 45namespace tut
42{ 46{
@@ -277,3 +281,439 @@ namespace tut
277 ensure_equals("crc update 2", c1.getCRC(), c2.getCRC()); 281 ensure_equals("crc update 2", c1.getCRC(), c2.getCRC());
278 } 282 }
279} 283}
284
285namespace tut
286{
287 struct sphere_data
288 {
289 };
290 typedef test_group<sphere_data> sphere_test;
291 typedef sphere_test::object sphere_object;
292 tut::sphere_test tsphere("LLSphere");
293
294 template<> template<>
295 void sphere_object::test<1>()
296 {
297 // test LLSphere::contains() and ::overlaps()
298 S32 number_of_tests = 10;
299 for (S32 test = 0; test < number_of_tests; ++test)
300 {
301 LLVector3 first_center(1.f, 1.f, 1.f);
302 F32 first_radius = 3.f;
303 LLSphere first_sphere( first_center, first_radius );
304
305 F32 half_millimeter = 0.0005f;
306 LLVector3 direction( ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
307 direction.normalize();
308
309 F32 distance = ll_frand(first_radius - 2.f * half_millimeter);
310 LLVector3 second_center = first_center + distance * direction;
311 F32 second_radius = first_radius - distance - half_millimeter;
312 LLSphere second_sphere( second_center, second_radius );
313 ensure("first sphere should contain the second", first_sphere.contains(second_sphere));
314 ensure("first sphere should overlap the second", first_sphere.overlaps(second_sphere));
315
316 distance = first_radius + ll_frand(first_radius);
317 second_center = first_center + distance * direction;
318 second_radius = distance - first_radius + half_millimeter;
319 second_sphere.set( second_center, second_radius );
320 ensure("first sphere should NOT contain the second", !first_sphere.contains(second_sphere));
321 ensure("first sphere should overlap the second", first_sphere.overlaps(second_sphere));
322
323 distance = first_radius + ll_frand(first_radius) + half_millimeter;
324 second_center = first_center + distance * direction;
325 second_radius = distance - first_radius - half_millimeter;
326 second_sphere.set( second_center, second_radius );
327 ensure("first sphere should NOT contain the second", !first_sphere.contains(second_sphere));
328 ensure("first sphere should NOT overlap the second", !first_sphere.overlaps(second_sphere));
329 }
330 }
331
332 template<> template<>
333 void sphere_object::test<2>()
334 {
335 // test LLSphere::getBoundingSphere()
336 S32 number_of_tests = 100;
337 S32 number_of_spheres = 10;
338 F32 sphere_center_range = 32.f;
339 F32 sphere_radius_range = 5.f;
340
341 for (S32 test = 0; test < number_of_tests; ++test)
342 {
343 // gegnerate a bunch of random sphere
344 std::vector< LLSphere > sphere_list;
345 for (S32 sphere_count=0; sphere_count < number_of_spheres; ++sphere_count)
346 {
347 LLVector3 direction( ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
348 direction.normalize();
349 F32 distance = ll_frand(sphere_center_range);
350 LLVector3 center = distance * direction;
351 F32 radius = ll_frand(sphere_radius_range);
352 LLSphere sphere( center, radius );
353 sphere_list.push_back(sphere);
354 }
355
356 // compute the bounding sphere
357 LLSphere bounding_sphere = LLSphere::getBoundingSphere(sphere_list);
358
359 // make sure all spheres are inside the bounding sphere
360 {
361 std::vector< LLSphere >::const_iterator sphere_itr;
362 for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
363 {
364 ensure("sphere should be contained by the bounding sphere", bounding_sphere.contains(*sphere_itr));
365 }
366 }
367
368 // TODO -- improve LLSphere::getBoundingSphere() to the point where
369 // we can reduce the 'expansion' in the two tests below to about
370 // 2 mm or less
371
372 F32 expansion = 0.005f;
373 // move all spheres out a little bit
374 // and count how many are NOT contained
375 {
376 std::vector< LLVector3 > uncontained_directions;
377 std::vector< LLSphere >::iterator sphere_itr;
378 for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
379 {
380 LLVector3 direction = sphere_itr->getCenter() - bounding_sphere.getCenter();
381 direction.normalize();
382
383 sphere_itr->setCenter( sphere_itr->getCenter() + expansion * direction );
384 if (! bounding_sphere.contains( *sphere_itr ) )
385 {
386 uncontained_directions.push_back(direction);
387 }
388 }
389 ensure("when moving spheres out there should be at least two uncontained spheres",
390 uncontained_directions.size() > 1);
391
392 /* TODO -- when the bounding sphere algorithm is improved we can open up this test
393 * at the moment it occasionally fails when the sphere collection is tight and small
394 * (2 meters or less)
395 if (2 == uncontained_directions.size() )
396 {
397 // if there were only two uncontained spheres then
398 // the two directions should be nearly opposite
399 F32 dir_dot = uncontained_directions[0] * uncontained_directions[1];
400 ensure("two uncontained spheres should lie opposite the bounding center", dir_dot < -0.95f);
401 }
402 */
403 }
404
405 // compute the new bounding sphere
406 bounding_sphere = LLSphere::getBoundingSphere(sphere_list);
407
408 // increase the size of all spheres a little bit
409 // and count how many are NOT contained
410 {
411 std::vector< LLVector3 > uncontained_directions;
412 std::vector< LLSphere >::iterator sphere_itr;
413 for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
414 {
415 LLVector3 direction = sphere_itr->getCenter() - bounding_sphere.getCenter();
416 direction.normalize();
417
418 sphere_itr->setRadius( sphere_itr->getRadius() + expansion );
419 if (! bounding_sphere.contains( *sphere_itr ) )
420 {
421 uncontained_directions.push_back(direction);
422 }
423 }
424 ensure("when boosting sphere radii there should be at least two uncontained spheres",
425 uncontained_directions.size() > 1);
426
427 /* TODO -- when the bounding sphere algorithm is improved we can open up this test
428 * at the moment it occasionally fails when the sphere collection is tight and small
429 * (2 meters or less)
430 if (2 == uncontained_directions.size() )
431 {
432 // if there were only two uncontained spheres then
433 // the two directions should be nearly opposite
434 F32 dir_dot = uncontained_directions[0] * uncontained_directions[1];
435 ensure("two uncontained spheres should lie opposite the bounding center", dir_dot < -0.95f);
436 }
437 */
438 }
439 }
440 }
441}
442
443namespace tut
444{
445 F32 SMALL_RADIUS = 1.0f;
446 F32 MEDIUM_RADIUS = 5.0f;
447 F32 LARGE_RADIUS = 10.0f;
448
449 struct line_data
450 {
451 };
452 typedef test_group<line_data> line_test;
453 typedef line_test::object line_object;
454 tut::line_test tline("LLLine");
455
456 template<> template<>
457 void line_object::test<1>()
458 {
459 // this is a test for LLLine::intersects(point) which returns TRUE
460 // if the line passes within some tolerance of point
461
462 // these tests will have some floating point error,
463 // so we need to specify how much error is ok
464 F32 allowable_relative_error = 0.00001f;
465 S32 number_of_tests = 100;
466 for (S32 test = 0; test < number_of_tests; ++test)
467 {
468 // generate some random point to be on the line
469 LLVector3 point_on_line( ll_frand(2.f) - 1.f,
470 ll_frand(2.f) - 1.f,
471 ll_frand(2.f) - 1.f);
472 point_on_line.normalize();
473 point_on_line *= ll_frand(LARGE_RADIUS);
474
475 // generate some random point to "intersect"
476 LLVector3 random_direction ( ll_frand(2.f) - 1.f,
477 ll_frand(2.f) - 1.f,
478 ll_frand(2.f) - 1.f);
479 random_direction.normalize();
480
481 LLVector3 random_offset( ll_frand(2.f) - 1.f,
482 ll_frand(2.f) - 1.f,
483 ll_frand(2.f) - 1.f);
484 random_offset.normalize();
485 random_offset *= ll_frand(SMALL_RADIUS);
486
487 LLVector3 point = point_on_line + MEDIUM_RADIUS * random_direction
488 + random_offset;
489
490 // compute the axis of approach (a unit vector between the points)
491 LLVector3 axis_of_approach = point - point_on_line;
492 axis_of_approach.normalize();
493
494 // compute the direction of the the first line (perp to axis_of_approach)
495 LLVector3 first_dir( ll_frand(2.f) - 1.f,
496 ll_frand(2.f) - 1.f,
497 ll_frand(2.f) - 1.f);
498 first_dir.normalize();
499 F32 dot = first_dir * axis_of_approach;
500 first_dir -= dot * axis_of_approach; // subtract component parallel to axis
501 first_dir.normalize();
502
503 // construct the line
504 LLVector3 another_point_on_line = point_on_line + ll_frand(LARGE_RADIUS) * first_dir;
505 LLLine line(another_point_on_line, point_on_line);
506
507 // test that the intersection point is within MEDIUM_RADIUS + SMALL_RADIUS
508 F32 test_radius = MEDIUM_RADIUS + SMALL_RADIUS;
509 test_radius += (LARGE_RADIUS * allowable_relative_error);
510 ensure("line should pass near intersection point", line.intersects(point, test_radius));
511
512 test_radius = allowable_relative_error * (point - point_on_line).length();
513 ensure("line should intersect point used to define it", line.intersects(point_on_line, test_radius));
514 }
515 }
516
517 template<> template<>
518 void line_object::test<2>()
519 {
520 // this is a test for LLLine::nearestApproach(LLLIne) method
521 // which computes the point on a line nearest another line
522
523 // these tests will have some floating point error,
524 // so we need to specify how much error is ok
525 // TODO -- make nearestApproach() algorithm more accurate so
526 // we can tighten the allowable_error. Most tests are tighter
527 // than one milimeter, however when doing randomized testing
528 // you can walk into inaccurate cases.
529 F32 allowable_relative_error = 0.001f;
530 S32 number_of_tests = 100;
531 for (S32 test = 0; test < number_of_tests; ++test)
532 {
533 // generate two points to be our known nearest approaches
534 LLVector3 some_point( ll_frand(2.f) - 1.f,
535 ll_frand(2.f) - 1.f,
536 ll_frand(2.f) - 1.f);
537 some_point.normalize();
538 some_point *= ll_frand(LARGE_RADIUS);
539
540 LLVector3 another_point( ll_frand(2.f) - 1.f,
541 ll_frand(2.f) - 1.f,
542 ll_frand(2.f) - 1.f);
543 another_point.normalize();
544 another_point *= ll_frand(LARGE_RADIUS);
545
546 // compute the axis of approach (a unit vector between the points)
547 LLVector3 axis_of_approach = another_point - some_point;
548 axis_of_approach.normalize();
549
550 // compute the direction of the the first line (perp to axis_of_approach)
551 LLVector3 first_dir( ll_frand(2.f) - 1.f,
552 ll_frand(2.f) - 1.f,
553 ll_frand(2.f) - 1.f);
554 F32 dot = first_dir * axis_of_approach;
555 first_dir -= dot * axis_of_approach; // subtract component parallel to axis
556 first_dir.normalize(); // normalize
557
558 // compute the direction of the the second line
559 LLVector3 second_dir( ll_frand(2.f) - 1.f,
560 ll_frand(2.f) - 1.f,
561 ll_frand(2.f) - 1.f);
562 dot = second_dir * axis_of_approach;
563 second_dir -= dot * axis_of_approach;
564 second_dir.normalize();
565
566 // make sure the lines aren't too parallel,
567 dot = fabsf(first_dir * second_dir);
568 if (dot > 0.99f)
569 {
570 // skip this test, we're not interested in testing
571 // the intractible cases
572 continue;
573 }
574
575 // construct the lines
576 LLVector3 first_point = some_point + ll_frand(LARGE_RADIUS) * first_dir;
577 LLLine first_line(first_point, some_point);
578
579 LLVector3 second_point = another_point + ll_frand(LARGE_RADIUS) * second_dir;
580 LLLine second_line(second_point, another_point);
581
582 // compute the points of nearest approach
583 LLVector3 some_computed_point = first_line.nearestApproach(second_line);
584 LLVector3 another_computed_point = second_line.nearestApproach(first_line);
585
586 // compute the error
587 F32 first_error = (some_point - some_computed_point).length();
588 F32 scale = llmax((some_point - another_point).length(), some_point.length());
589 scale = llmax(scale, another_point.length());
590 scale = llmax(scale, 1.f);
591 F32 first_relative_error = first_error / scale;
592
593 F32 second_error = (another_point - another_computed_point).length();
594 F32 second_relative_error = second_error / scale;
595
596 //if (first_relative_error > allowable_relative_error)
597 //{
598 // std::cout << "first_error = " << first_error
599 // << " first_relative_error = " << first_relative_error
600 // << " scale = " << scale
601 // << " dir_dot = " << (first_dir * second_dir)
602 // << std::endl;
603 //}
604 //if (second_relative_error > allowable_relative_error)
605 //{
606 // std::cout << "second_error = " << second_error
607 // << " second_relative_error = " << second_relative_error
608 // << " scale = " << scale
609 // << " dist = " << (some_point - another_point).length()
610 // << " dir_dot = " << (first_dir * second_dir)
611 // << std::endl;
612 //}
613
614 // test that the errors are small
615 ensure("first line should accurately compute its closest approach",
616 first_relative_error <= allowable_relative_error);
617 ensure("second line should accurately compute its closest approach",
618 second_relative_error <= allowable_relative_error);
619 }
620 }
621
622 F32 ALMOST_PARALLEL = 0.99f;
623 template<> template<>
624 void line_object::test<3>()
625 {
626 // this is a test for LLLine::getIntersectionBetweenTwoPlanes() method
627
628 // first some known tests
629 LLLine xy_plane(LLVector3(0.f, 0.f, 2.f), LLVector3(0.f, 0.f, 3.f));
630 LLLine yz_plane(LLVector3(2.f, 0.f, 0.f), LLVector3(3.f, 0.f, 0.f));
631 LLLine zx_plane(LLVector3(0.f, 2.f, 0.f), LLVector3(0.f, 3.f, 0.f));
632
633 LLLine x_line;
634 LLLine y_line;
635 LLLine z_line;
636
637 bool x_success = LLLine::getIntersectionBetweenTwoPlanes(x_line, xy_plane, zx_plane);
638 bool y_success = LLLine::getIntersectionBetweenTwoPlanes(y_line, yz_plane, xy_plane);
639 bool z_success = LLLine::getIntersectionBetweenTwoPlanes(z_line, zx_plane, yz_plane);
640
641 ensure("xy and zx planes should intersect", x_success);
642 ensure("yz and xy planes should intersect", y_success);
643 ensure("zx and yz planes should intersect", z_success);
644
645 LLVector3 direction = x_line.getDirection();
646 ensure("x_line should be parallel to x_axis", fabs(direction.mV[VX]) == 1.f
647 && 0.f == direction.mV[VY]
648 && 0.f == direction.mV[VZ] );
649 direction = y_line.getDirection();
650 ensure("y_line should be parallel to y_axis", 0.f == direction.mV[VX]
651 && fabs(direction.mV[VY]) == 1.f
652 && 0.f == direction.mV[VZ] );
653 direction = z_line.getDirection();
654 ensure("z_line should be parallel to z_axis", 0.f == direction.mV[VX]
655 && 0.f == direction.mV[VY]
656 && fabs(direction.mV[VZ]) == 1.f );
657
658 // next some random tests
659 F32 allowable_relative_error = 0.0001f;
660 S32 number_of_tests = 20;
661 for (S32 test = 0; test < number_of_tests; ++test)
662 {
663 // generate the known line
664 LLVector3 some_point( ll_frand(2.f) - 1.f,
665 ll_frand(2.f) - 1.f,
666 ll_frand(2.f) - 1.f);
667 some_point.normalize();
668 some_point *= ll_frand(LARGE_RADIUS);
669 LLVector3 another_point( ll_frand(2.f) - 1.f,
670 ll_frand(2.f) - 1.f,
671 ll_frand(2.f) - 1.f);
672 another_point.normalize();
673 another_point *= ll_frand(LARGE_RADIUS);
674 LLLine known_intersection(some_point, another_point);
675
676 // compute a plane that intersect the line
677 LLVector3 point_on_plane( ll_frand(2.f) - 1.f,
678 ll_frand(2.f) - 1.f,
679 ll_frand(2.f) - 1.f);
680 point_on_plane.normalize();
681 point_on_plane *= ll_frand(LARGE_RADIUS);
682 LLVector3 plane_normal = (point_on_plane - some_point) % known_intersection.getDirection();
683 plane_normal.normalize();
684 LLLine first_plane(point_on_plane, point_on_plane + plane_normal);
685
686 // compute a different plane that intersect the line
687 LLVector3 point_on_different_plane( ll_frand(2.f) - 1.f,
688 ll_frand(2.f) - 1.f,
689 ll_frand(2.f) - 1.f);
690 point_on_different_plane.normalize();
691 point_on_different_plane *= ll_frand(LARGE_RADIUS);
692 LLVector3 different_plane_normal = (point_on_different_plane - another_point) % known_intersection.getDirection();
693 different_plane_normal.normalize();
694 LLLine second_plane(point_on_different_plane, point_on_different_plane + different_plane_normal);
695
696 if (fabs(plane_normal * different_plane_normal) > ALMOST_PARALLEL)
697 {
698 // the two planes are approximately parallel, so we won't test this case
699 continue;
700 }
701
702 LLLine measured_intersection;
703 bool success = LLLine::getIntersectionBetweenTwoPlanes(
704 measured_intersection,
705 first_plane,
706 second_plane);
707
708 ensure("plane intersection should succeed", success);
709
710 F32 dot = fabs(known_intersection.getDirection() * measured_intersection.getDirection());
711 ensure("measured intersection should be parallel to known intersection",
712 dot > ALMOST_PARALLEL);
713
714 ensure("measured intersection should pass near known point",
715 measured_intersection.intersects(some_point, LARGE_RADIUS * allowable_relative_error));
716 }
717 }
718}
719
generated by cgit v1.1 at 2024-12-29 07:03:20 +0000