API tools faq
paste
Advertisement
Guest User

Welzl's Sphere

a guest
Nov 4th, 2011
157
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.14 KB | None | 0 0
raw download clone embed print report
  1. Sphere UpdateSphereOne( std::vector< Vector >& pointSet, Vector& newPoint )
  2. {
  3.     pointSet.push_back( newPoint );
  4.  
  5.     return Sphere( pointSet[0], pointSet[1] );
  6. }
  7.  
  8. Sphere UpdateSphereTwo( std::vector< Vector >& pointSet, Vector& newPoint )
  9. {
  10.     Sphere minimumSphere;
  11.  
  12.     // have a circle currently consisting of p0 and p1
  13.     Vector p0 = pointSet[0];
  14.     Vector p1 = pointSet[1];
  15.  
  16.     // need to test a circle of p0 and newpoint & one of p1 and newpoint
  17.     Sphere possibleSpheres[2];
  18.     float minRadius = RAND_MAX;
  19.     int index = -1;
  20.  
  21.     // means I can have two possible spheres
  22.     possibleSpheres[0] = Sphere( p0, newPoint );
  23.     possibleSpheres[1] = Sphere( p1, newPoint );
  24.  
  25.     if( possibleSpheres[0].Contains( p1 ) )
  26.     {
  27.         minRadius = possibleSpheres[0].radius;
  28.         index = 0;
  29.     }
  30.     else if( possibleSpheres[1].Contains( p0 ) && possibleSpheres[1].radius < minRadius )
  31.     {
  32.         minRadius = possibleSpheres[1].radius;
  33.         index = 1;
  34.     }
  35.  
  36.     if( index != -1 ) // meaning we found a valid sphere
  37.     {
  38.         minimumSphere = possibleSpheres[index];
  39.         pointSet[1-index] = newPoint; // replace unecessary point with the new point
  40.     }
  41.     else
  42.     {
  43.         minimumSphere = Sphere( p0, p1, newPoint );
  44.         pointSet.push_back( newPoint ); // add point to set because all three are now required
  45.     }
  46.  
  47.     return minimumSphere;
  48. }
  49.  
  50. Sphere UpdateSphereThree( std::vector< Vector >& pointSet, Vector& newPoint )
  51. {
  52.     Sphere minimumSphere;
  53.    
  54.     Sphere possibleSpheres[6]; // 6 possible spheres
  55.  
  56.     // test points
  57.     Vector p0 = pointSet[0];
  58.     Vector p1 = pointSet[1];
  59.     Vector p2 = pointSet[2];
  60.  
  61.     int sphereIndex = 0; // all possible 2 pairs of spheres
  62.  
  63.     // initialize all possible spheres
  64.     for( size_t k1 = 0; k1 < pointSet.size(); ++k1 )
  65.     {
  66.         possibleSpheres[sphereIndex++] = Sphere( pointSet[k1], newPoint );
  67.     }
  68.     possibleSpheres[3] = Sphere( p0, p1, newPoint );
  69.     possibleSpheres[4] = Sphere( p0, p2, newPoint );
  70.     possibleSpheres[5] = Sphere( p1, p2, newPoint );
  71.  
  72.     int chosenSphere = -1;
  73.     float minRadius = RAND_MAX;
  74.  
  75.     if( possibleSpheres[0].Contains( p1 ) && possibleSpheres[0].Contains( p2 ) )
  76.     {
  77.         chosenSphere = 0;
  78.         minRadius = possibleSpheres[0].radius;
  79.     }
  80.     if( possibleSpheres[1].radius < minRadius && possibleSpheres[1].Contains( p0 ) && possibleSpheres[1].Contains( p2 ) )
  81.     {
  82.         chosenSphere = 1;
  83.         minRadius = possibleSpheres[1].radius;
  84.     }
  85.     if( possibleSpheres[2].radius < minRadius && possibleSpheres[2].Contains( p0 ) && possibleSpheres[2].Contains( p1 ) )
  86.     {
  87.         chosenSphere = 2;
  88.         minRadius = possibleSpheres[2].radius;
  89.     }
  90.     if( possibleSpheres[3].radius < minRadius && possibleSpheres[3].Contains( p2 ) )
  91.     {
  92.         chosenSphere = 3;
  93.         minRadius = possibleSpheres[3].radius;
  94.     }
  95.     if( possibleSpheres[4].radius < minRadius && possibleSpheres[4].Contains( p1 ) )
  96.     {
  97.         chosenSphere = 4;
  98.         minRadius = possibleSpheres[4].radius;
  99.     }
  100.     if( possibleSpheres[5].radius < minRadius && possibleSpheres[5].Contains( p0 ) )
  101.     {
  102.         chosenSphere = 5;
  103.         minRadius = possibleSpheres[5].radius;
  104.     }
  105.  
  106.     if( chosenSphere == -1 )
  107.     {
  108.         minimumSphere = Sphere( pointSet[0], pointSet[1], pointSet[2], newPoint );
  109.         pointSet.push_back( newPoint );
  110.     }
  111.     else
  112.     {
  113.         minimumSphere = possibleSpheres[chosenSphere];
  114.  
  115.         switch( chosenSphere )
  116.         {
  117.         case 0: pointSet.resize( 2 );
  118.             pointSet[1] = newPoint;
  119.             break;
  120.         case 1: pointSet.resize( 2 );
  121.             pointSet[0] = newPoint;
  122.             break;
  123.         case 2: pointSet[0] = pointSet[3];
  124.             pointSet.resize( 2 );
  125.             pointSet[1] = newPoint;
  126.             break;
  127.         case 3: pointSet.resize( 3 );
  128.             pointSet[2] = newPoint;
  129.             break;
  130.         case 4: pointSet.resize( 3 );
  131.             pointSet[1] = newPoint;
  132.             break;
  133.         case 5: pointSet.resize( 3 );
  134.             pointSet[0] = newPoint;
  135.             break;
  136.         }
  137.     }
  138.  
  139.     return minimumSphere;
  140. }
  141.  
  142. Sphere UpdateSphereFour( std::vector< Vector >& pointSet, Vector& newPoint )
  143. {
  144.     Sphere updatedSphere;
  145.  
  146.     Sphere possibleSpheres[14]; // 14 possible spheres
  147.  
  148.     // test points
  149.     Vector p0 = pointSet[0];
  150.     Vector p1 = pointSet[1];
  151.     Vector p2 = pointSet[2];
  152.     Vector p3 = pointSet[3];
  153.  
  154.     int sphereIndex = -1;
  155.     float minRadius = RAND_MAX;
  156.  
  157.     possibleSpheres[0] = Sphere( p0, newPoint );
  158.     possibleSpheres[1] = Sphere( p1, newPoint );
  159.     possibleSpheres[2] = Sphere( p2, newPoint );
  160.     possibleSpheres[3] = Sphere( p3, newPoint );
  161.     possibleSpheres[4] = Sphere( p0, p1, newPoint );
  162.     possibleSpheres[5] = Sphere( p0, p2, newPoint );
  163.     possibleSpheres[6] = Sphere( p0, p3, newPoint );
  164.     possibleSpheres[7] = Sphere( p1, p2, newPoint );
  165.     possibleSpheres[8] = Sphere( p1, p3, newPoint );
  166.     possibleSpheres[9] = Sphere( p2, p3, newPoint );
  167.     possibleSpheres[10] = Sphere( p0, p1, p2, newPoint );
  168.     possibleSpheres[11] = Sphere( p0, p1, p3, newPoint );
  169.     possibleSpheres[12] = Sphere( p1, p2, p3, newPoint );
  170.     possibleSpheres[13] = Sphere( p2, p3, p0, newPoint );
  171.  
  172.     // test all two spheres
  173.     if( possibleSpheres[0].Contains( p1 ) && possibleSpheres[0].Contains( p2 ) && possibleSpheres[0].Contains( p3 ) )
  174.     {
  175.         sphereIndex = 0;
  176.         minRadius = possibleSpheres[0].radius;
  177.     }
  178.     if( possibleSpheres[1].radius < minRadius && possibleSpheres[1].Contains( p0 ) && possibleSpheres[1].Contains( p2 ) && possibleSpheres[1].Contains( p3 ) )
  179.     {
  180.         sphereIndex = 1;
  181.         minRadius = possibleSpheres[1].radius;
  182.     }
  183.     if( possibleSpheres[2].radius < minRadius && possibleSpheres[2].Contains( p0 ) && possibleSpheres[2].Contains( p1 ) && possibleSpheres[2].Contains( p3 ) )
  184.     {
  185.         sphereIndex = 2;
  186.         minRadius = possibleSpheres[2].radius;
  187.     }
  188.     if( possibleSpheres[3].radius < minRadius && possibleSpheres[3].Contains( p0 ) && possibleSpheres[3].Contains( p1 ) && possibleSpheres[3].Contains( p2 ) )
  189.     {
  190.         sphereIndex = 3;
  191.         minRadius = possibleSpheres[3].radius;
  192.     }
  193.  
  194.     // test all three spheres
  195.     if( possibleSpheres[4].radius < minRadius && possibleSpheres[4].Contains( p2 ) && possibleSpheres[4].Contains( p3 ) )
  196.     {
  197.         sphereIndex = 4;
  198.         minRadius = possibleSpheres[4].radius;
  199.     }
  200.     if( possibleSpheres[5].radius < minRadius && possibleSpheres[5].Contains( p1 ) && possibleSpheres[5].Contains( p3 ) )
  201.     {
  202.         sphereIndex = 5;
  203.         minRadius = possibleSpheres[5].radius;
  204.     }
  205.     if( possibleSpheres[6].radius < minRadius && possibleSpheres[6].Contains( p1 ) && possibleSpheres[6].Contains( p2 ) )
  206.     {
  207.         sphereIndex = 6;
  208.         minRadius = possibleSpheres[6].radius;
  209.     }
  210.     if( possibleSpheres[7].radius < minRadius && possibleSpheres[7].Contains( p0 ) && possibleSpheres[7].Contains( p3 ) )
  211.     {
  212.         sphereIndex = 7;
  213.         minRadius = possibleSpheres[7].radius;
  214.     }
  215.     if( possibleSpheres[8].radius < minRadius && possibleSpheres[8].Contains( p0 ) && possibleSpheres[8].Contains( p2 ) )
  216.     {
  217.         sphereIndex = 8;
  218.         minRadius = possibleSpheres[8].radius;
  219.     }
  220.     if( possibleSpheres[9].radius < minRadius && possibleSpheres[9].Contains( p0 ) && possibleSpheres[9].Contains( p1 ) )
  221.     {
  222.         sphereIndex = 9;
  223.         minRadius = possibleSpheres[9].radius;
  224.     }
  225.  
  226.     // test all four spheres
  227.     if( possibleSpheres[10].radius < minRadius && possibleSpheres[10].Contains( p3 ) )
  228.     {
  229.         sphereIndex = 10;
  230.         minRadius = possibleSpheres[10].radius;
  231.     }
  232.     if( possibleSpheres[11].radius < minRadius && possibleSpheres[11].Contains( p2 ) )
  233.     {
  234.         sphereIndex = 11;
  235.         minRadius = possibleSpheres[11].radius;
  236.     }
  237.     if( possibleSpheres[12].radius < minRadius && possibleSpheres[12].Contains( p0 ) )
  238.     {
  239.         sphereIndex = 12;
  240.         minRadius = possibleSpheres[12].radius;
  241.     }
  242.     if( possibleSpheres[13].radius < minRadius && possibleSpheres[13].Contains( p1 ) )
  243.     {
  244.         sphereIndex = 13;
  245.         minRadius = possibleSpheres[13].radius;
  246.     }
  247.  
  248.     if( sphereIndex == -1 )
  249.     {
  250.         _ASSERT( false );
  251.     }
  252.  
  253.     updatedSphere = possibleSpheres[sphereIndex];
  254.  
  255.     switch( sphereIndex )
  256.     {
  257.     case 0:
  258.         pointSet.resize( 2 );
  259.         pointSet[1] = newPoint;
  260.         break;
  261.     case 1:
  262.         pointSet.resize( 2 );
  263.         pointSet[0] = newPoint;
  264.         break;
  265.     case 2:
  266.         pointSet[0] = p2;
  267.         pointSet.resize( 2 );
  268.         pointSet[1] = newPoint;
  269.         break;
  270.     case 3:
  271.         pointSet[0] = p3;
  272.         pointSet.resize( 2 );
  273.         pointSet[1] = newPoint;
  274.         break;
  275.     case 4:
  276.         pointSet.resize( 3 );
  277.         pointSet[2] = newPoint;
  278.         break;
  279.     case 5:
  280.         pointSet.resize( 3 );
  281.         pointSet[1] = newPoint;
  282.         break;
  283.     case 6:
  284.         pointSet[1] = p3;
  285.         pointSet.resize( 3 );
  286.         pointSet[2] = newPoint;
  287.         break;
  288.     case 7:
  289.         pointSet[0] = p2;
  290.         pointSet.resize( 3 );
  291.         pointSet[2] = newPoint;
  292.         break;
  293.     case 8:
  294.         pointSet[0] = p3;
  295.         pointSet.resize( 3 );
  296.         pointSet[2] = newPoint;
  297.         break;
  298.     case 9:
  299.         pointSet[0] = p3;
  300.         pointSet[1] = newPoint;
  301.         pointSet.resize( 3 );
  302.         break;
  303.     case 10:
  304.         pointSet.resize( 4 );
  305.         pointSet[3] = newPoint;
  306.         break;
  307.     case 11:
  308.         pointSet[2] = newPoint;
  309.         pointSet.resize( 4 );
  310.         break;
  311.     case 12:
  312.         pointSet[0] = newPoint;
  313.         pointSet.resize( 4 );
  314.         break;
  315.     case 13:
  316.         pointSet[1] = newPoint;
  317.         pointSet.resize( 4 );
  318.         break;
  319.     }
  320.  
  321.     return updatedSphere;
  322. }
  323.  
  324. Sphere UpdateSphere( std::vector< Vector >& pointSet, Vector& newPoint )
  325. {
  326.     Sphere updatedSphere;
  327.  
  328.     switch( pointSet.size() )
  329.     {
  330.     case 1:
  331.         updatedSphere = UpdateSphereOne( pointSet, newPoint );
  332.         break;
  333.     case 2:
  334.         updatedSphere = UpdateSphereTwo( pointSet, newPoint );
  335.         break;
  336.     case 3:
  337.         updatedSphere = UpdateSphereThree( pointSet, newPoint );
  338.         break;
  339.     case 4:
  340.         updatedSphere = UpdateSphereFour( pointSet, newPoint );
  341.         break;
  342.     }
  343.     return updatedSphere;
  344. }
  345.  
  346. Sphere MyExporter::CalculateBoundingSphere( std::vector< MyVertex >& vertices )
  347. {
  348.     std::vector< Vector > pointSet;
  349.  
  350.     pointSet.push_back( Vector( vertices[0].pos.x, vertices[0].pos.y, vertices[0].pos.z ) );
  351.     Sphere boundingSphere = Sphere( Vector( vertices[0].pos.x, vertices[0].pos.y, vertices[0].pos.z ) );
  352.  
  353.     int index = 0;
  354.    
  355.     while( index < vertices.size() )
  356.     {
  357.         Vector vPos = Vector( vertices[index].pos.x, vertices[index].pos.y, vertices[index].pos.z );
  358.         bool supportSetContains = false;
  359.         for( size_t k1 = 0; k1 < pointSet.size(); ++k1 )
  360.         {
  361.             if( pointSet[k1] == vPos )
  362.                 supportSetContains = true;
  363.         }
  364.        
  365.         if( !supportSetContains ) // if the current vertex is not in the pointset
  366.         {
  367.             if( !boundingSphere.Contains( vPos ) ) // if the current vertex is not in the bounding sphere
  368.             {
  369.                 Sphere newCircle = UpdateSphere( pointSet, vPos );
  370.                 if( newCircle.radius > boundingSphere.radius )
  371.                 {
  372.                     boundingSphere = newCircle;
  373.                     index = 0;
  374.                     continue;
  375.                 }
  376.             }
  377.         }
  378.  
  379.         ++index;
  380.     }
  381.  
  382.     return boundingSphere;
  383. }
  384.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!