74 if( fabs( p1.
norm[0] - p2.
norm[0] ) > 1e-6 || fabs( p1.
norm[1] - p2.
norm[1] ) > 1e-6 ||
77 printf(
"Equality Test Failed: %s == %s\n", exp1, exp2 );
78 printf(
" at line %d of '%s'\n", line, file );
79 printf(
" Expected: %f x + %f y + %f z + %f = 0\n", p1.
norm[0], p1.
norm[1], p1.
norm[2], p1.
coeff );
80 printf(
" Actual : %f x + %f y + %f z + %f = 0\n", p2.
norm[0], p2.
norm[1], p2.
norm[2], p2.
coeff );
89 const double points[3][3] = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
90 p.
set( points[0], points[1], points[2] );
181 bool compare_hexes(
const double expected[8][3],
const double actual[8][3],
double epsilon )
184 const int rotation_maps[3][8] = {
185 { 0, 1, 2, 3, 4, 5, 6, 7 }, { 3, 2, 6, 7, 0, 1, 5, 4 }, { 7, 3, 2, 6, 4, 0, 1, 5 } };
186 for(
int i = 0; i < 3; ++i )
189 for(
int j = 0; j < 4; ++j )
193 for(
int k = 0; k < 4 && match; ++k )
196 for(
int d = 0; d < 3; ++d )
198 if( fabs( expected[( j + k ) % 4][d] - actual[rotation_maps[i][k]][d] ) > epsilon ||
199 fabs( expected[( j + k ) % 4 + 4][d] - actual[rotation_maps[i][k + 4]][d] ) > epsilon )
207 if( match )
return true;
211 printf(
"Hex vertex copmarison failed.\n" );
212 printf(
" Exected Actual\n" );
213 for(
int v = 0; v < 8; ++v )
215 printf(
"% 9f % 9f % 9f % 9f % 9f % 9f\n", expected[v][0], expected[v][1], expected[v][2], actual[v][0],
216 actual[v][1], actual[v][2] );
222 static void aabox_corners(
const double min[3],
const double max[3],
double corners[8][3] )
224 const double expt[8][3] = { { min[0], min[1], min[2] }, { max[0], min[1], min[2] }, { max[0], max[1], min[2] },
225 { min[0], max[1], min[2] }, { min[0], min[1], max[2] }, { max[0], min[1], max[2] },
226 { max[0], max[1], max[2] }, { min[0], max[1], max[2] } };
227 memcpy( corners, expt,
sizeof( expt ) );
236 double corners[8][3] )
238 double min[] = { min_x, min_y, min_z };
239 double max[] = { max_x, max_y, max_z };
250 const double min[3] = { -1, -2, -3 };
251 const double max[3] = { 3, 2, 1 };
263 double corners[8][3], expt[8][3];
305 for(
int i = 0; i < 8; ++i )
306 if( expt[i][0] > 0 ) expt[i][0] = 0;
323 for(
int i = 0; i < 8; ++i )
324 if( expt[i][0] < 0 ) expt[i][0] = 0;
337 for(
int i = 0; i < 8; ++i )
338 if( expt[i][0] > 0 ) expt[i][0] = 0;
387 const double r = 0.5 * sqrt( 2.0 );
443 const double min[3] = { -2, -2, -2 };
444 const double max[3] = { 2, 2, 2 };
456 double corners[8][3], expt[8][3];
570 for(
unsigned i = 0; i < 8; ++i )
571 if( expt[i][2] > 0.0 ) expt[i][2] = 0.0;
578 for(
unsigned i = 0; i < 8; ++i )
579 if( expt[i][2] < -1.0 ) expt[i][2] = -1.0;
587 for(
unsigned i = 0; i < 8; ++i )
588 if( expt[i][2] > -1.0 ) expt[i][2] = -1.0;
716 double expected[8][3], corners[8][3];
737 const double min[3] = { 0, 0, 0 };
738 const double max[3] = { 1, 1, 1 };
759 const double A_point[] = { 0.1, 0.8, 0.5 };
772 const double B_point[] = { 0.3, 0.1, 0.6 };
785 const double C_point[] = { 0.9, 0.9, 0.1 };
798 const double D_point[] = { 0.5, 0.2, 0.9 };
813 const double above_pt[] = { 0.5, 0.5, 2.0 };
817 const double left_pt[] = { -1.0, 0.5, 0.5 };
872 const double A_point[] = { -1000, -1000, -1000 };
880 const double B_point[] = { -3, 1, 100 };
888 const double C_point[] = { -10, 500, 0 };
896 const double D_point[] = { 10, 500, 0 };
913 double expected[8][3], corners[8][3];
934 const double min[3] = { 0, 0, 0 };
935 const double max[3] = { 1, 1, 1 };
977 std::vector< BSPTreeBoxIter > list;
980 std::vector< int > results;
981 for(
size_t i = 0; i < list.size(); ++i )
982 results.push_back( std::find( leaves, leaves + 8, list[i].handle() ) - leaves );
983 std::sort( results.begin(), results.end() );
998 const double corners[8][3] = { { 0, 0, 0 }, { 8, 0, 0 }, { 8, 2, 0 }, { 0, 2, 0 },
999 { 0, 0, 1 }, { 8, 0, 1 }, { 8, 2, 1 }, { 0, 2, 1 } };
1037 leaves[0] = iter.
handle();
1039 leaves[1] = iter.
handle();
1057 leaves[2] = iter.
handle();
1059 leaves[3] = iter.
handle();
1086 leaves[4] = iter.
handle();
1088 leaves[5] = iter.
handle();
1106 leaves[6] = iter.
handle();
1108 leaves[7] = iter.
handle();
1126 std::vector< int > expected;
1132 expected.push_back( 3 );
1134 expected.insert( expected.begin(), 2 );
1137 expected.push_back( 1 );
1142 expected.push_back( 4 );
1144 expected.push_back( 7 );
1154 expected.push_back( 2 );
1156 expected.push_back( 3 );
1159 expected.push_back( 0 );
1164 expected.push_back( 7 );
1166 expected.insert( expected.begin(), 4 );
1183 expected.push_back( 3 );
1188 expected.push_back( 1 );
1190 expected.insert( expected.begin(), 0 );
1201 expected.push_back( 2 );
1206 expected.push_back( 0 );
1208 expected.push_back( 1 );
1224 expected.push_back( 0 );
1226 expected.push_back( 1 );
1229 expected.push_back( 7 );
1231 expected.insert( expected.begin(), 6 );
1235 expected.push_back( 5 );
1248 expected.push_back( 4 );
1253 expected.push_back( 6 );
1255 expected.push_back( 7 );
1272 expected.push_back( 7 );
1277 expected.push_back( 5 );
1279 expected.insert( expected.begin(), 4 );
1289 expected.push_back( 1 );
1291 expected.insert( expected.begin(), 0 );
1294 expected.push_back( 4 );
1297 expected.push_back( 5 );
1300 expected.push_back( 6 );
1333 const double min[3] = { 0, 0, 0 };
1334 const double max[3] = { 1, 1, 1 };
1418 const double min[3] = { 0, 0, 0 };
1419 const double max[3] = { 1, 1, 1 };
1450 const double min[3] = { 0, 0, 0 };
1451 const double max[3] = { 1, 2, 3 };
1455 p.
set( 1, 0, 0, 1 );
1462 p.
set( 1, 0, 0, 0 );
1467 p.
set( 1, 0, 0, -0.5 );
1474 p.
set( 1, 0, 0, -1 );
1479 p.
set( 1, 0, 0, -2 );
1486 double pt1[3] = { 0, 0, 1.5 };
1487 double pt2[3] = { 1, 0, 1.5 };
1488 double pt3[3] = { 0, 1, 3.0 };
1489 p.
set( pt1, pt2, pt3 );
1496 double pt4[3] = { 0, 2, 2.8 };
1497 p.
set( pt1, pt2, pt4 );
1504 double pta[3] = { 0.8, 0, 0 };
1505 double ptb[3] = { 0, 0.2, 3 };
1506 double ptc[3] = { 0.8, 2, 3 };
1507 p.
set( pta, ptb, ptc );
1515 #define CHECK_RAY_XSECTS( PT, DIR, T_IN, T_OUT ) \
1518 CHECK( iter.intersect_ray( ( PT ), ( DIR ), t_in, t_out ) ); \
1519 CHECK_REAL_EQUAL( ( T_IN ), t_in, 1e-6 ); \
1520 CHECK_REAL_EQUAL( ( T_OUT ), t_out, 1e-6 ); \
1549 const double corners[][3] = { { 1, 1, -3 }, { 6, 1, -3 }, { 2, 5, -3 }, { 1, 5, -3 },
1550 { 1, 1, -1 }, { 6, 1, -1 }, { 2, 5, -1 }, { 1, 5, -1 } };
1559 const double pt1[] = { 3.5, 3, -2 };
1560 const double dir1[] = { 0.1, 0.1, 0.1 };
1562 const double dir2[] = { 5, 5, 5 };
1564 const double pxdir[] = { 1, 0, 0 };
1566 const double nxdir[] = { -1, 0, 0 };
1568 const double pydir[] = { 0, 1, 0 };
1570 const double nydir[] = { 0, -1, 0 };
1572 const double pzdir[] = { 0, 0, 1 };
1574 const double nzdir[] = { 0, 0, -1 };
1578 const double pt2[] = { 3.5, 3, -4 };
1589 const double pt3[] = { 7, 3, -2 };
1600 const double dira[] = { -2, -2, 0 };
1602 const double dirb[] = { -1, -2.1, 0 };
1627 const double pt4[] = { 4, 2, -2 };
1638 const double pt5[] = { 4, 2, -4 };
1649 const double pt6[] = { 7, 2, -2 };
1660 const double dird[] = { -2, -2, 0 };
1662 const double dire[] = { -3, -2, 0 };
1664 const double dirf[] = { -2, -2.1, 0 };
1668 static void box(
const double pts[],
int num_pts,
double minpt[3],
double maxpt[3] )
1670 minpt[0] = maxpt[0] = pts[0];
1671 minpt[1] = maxpt[1] = pts[1];
1672 minpt[2] = maxpt[2] = pts[2];
1673 for(
int i = 1; i < num_pts; ++i )
1675 for(
int d = 0; d < 3; ++d )
1677 if( pts[3 * i + d] < minpt[d] ) minpt[d] = pts[3 * i + d];
1678 if( pts[3 * i + d] > maxpt[d] ) maxpt[d] = pts[3 * i + d];
1687 std::vector< EntityHandle > pts( num_points );
1688 for(
int i = 0; i < num_points; ++i )
1694 double minpt[3], maxpt[3];
1695 box( points, num_points, minpt, maxpt );
1707 std::vector< EntityHandle > left_pts, right_pts;
1708 std::vector< CartVect > coords( num_points ), tmp_coords;
1713 while( pts.size() > 1 )
1716 coords.resize( pts.size() );
1720 std::vector< CartVect >* ptr;
1721 if( coords.size() < 10 )
1725 tmp_coords.resize( 16 );
1727 box( coords[0].array(), coords.size(), pn.
array(), px.
array() );
1729 tmp_coords[9] =
CartVect( px[0], pn[1], pn[2] );
1730 tmp_coords[10] =
CartVect( px[0], px[1], pn[2] );
1731 tmp_coords[11] =
CartVect( pn[0], px[1], pn[2] );
1732 tmp_coords[12] =
CartVect( pn[0], pn[1], px[2] );
1733 tmp_coords[13] =
CartVect( px[0], pn[1], px[2] );
1734 tmp_coords[14] = px;
1735 tmp_coords[15] =
CartVect( pn[0], px[1], px[2] );
1736 for(
int i = 0; i < 8; ++i )
1738 tmp_coords[i] = coords[0];
1739 for(
size_t j = 1; j < coords.size(); ++j )
1742 tmp_coords[i] = coords[j];
1744 tmp_coords.resize( 8 );
1748 size_t pt1 = 0, pt2 = 0;
1750 for(
size_t i = 0; i < ptr->size(); ++i )
1752 for(
size_t j = 0; j < ptr->size(); ++j )
1765 if( lsqr <= 1e-12 )
break;
1768 CartVect norm = ( *ptr )[pt1] - ( *ptr )[pt2];
1773 for(
size_t i = 0; i < coords.size(); ++i )
1774 coeff -= norm % coords[i];
1775 coeff /= coords.size();
1780 for(
size_t i = 0; i < coords.size(); ++i )
1782 double d = -( norm % coords[i] );
1784 left_pts.push_back( pts[i] );
1786 right_pts.push_back( pts[i] );
1790 CHECK( !left_pts.empty() && !right_pts.empty() );
1791 pts.swap( left_pts );
1804 for(
int i = 0; i < num_points; ++i )
1827 static const double points[] = { 7, 6, 3, 5, 3, 5, 9, 2, 6, 7, 2, 1, 3, 9, 0, 6, 0, 6, 1, 6,
1828 2, 9, 7, 8, 2, 0, 2, 5, 7, 3, 2, 2, 9, 7, 9, 8, 1, 6, 3, 3,
1829 9, 2, 4, 9, 1, 4, 8, 7, 3, 0, 5, 0, 1, 6, 2, 3, 6, 1, 6, 0 };
1830 const int num_pts =
sizeof( points ) / ( 3 *
sizeof(
double ) );
1840 std::vector< EntityHandle > pts;
1841 std::vector< CartVect > coords;
1853 CHECK( !pts.empty() );
1854 coords.resize( pts.size() );
1857 for(
size_t i = 0; i < pts.size(); ++i )