Generating a sphere from a vertex array?

Discussion in 'Technical Discussion' started by Dude, Nov 4, 2009.

  1. Dude

    Dude

    Tech Member
    3,138
    0
    16
    Southbridge, MA
    Random VR/AR trash
    I need to write a function that returns 4 floats (center x,y, and z, and a radius) from an array of vertices. Any ideas as to how this could be done?

    I'm using c, not c++ for the record (Which will probably make it 100x harder, I know)
     
  2. Ultima

    Ultima

    Games Publisher Tech Member
    2,398
    1
    18
    London, England
    Publishing mobile games!
    How accurate does it have to be? Is it for collision detection optimisation?

    If it doesn't have to be very accurate, you can calculate the AABB of all your vertices, and set the midpoint to the centre of the AABB and the radius to the furthest point from the centre. This is going to make the sphere inaccurate though. The advantage is it's fast, easy and it is guaranteed to enclose all points, so it's useful for speeding up your collision detection.

    The more accurate way is much slower and mathematically a lot more complex. <a href="http://www.inf.ethz.ch/personal/gaertner/miniball.html" target="_blank">http://www.inf.ethz.ch/personal/gaertner/miniball.html</a> is a C++ library that will do it, and you could at least use it for some example code or as a starting point, if you don't want to use it verbatim. There's also this one, which is much slower (there's some other crap like bounding rectangles too): <a href="http://www.geometrictools.com/LibFoundation/Containment/Containment.html" target="_blank">http://www.geometrictools.com/LibFoundatio...ontainment.html</a>
     
  3. Dude

    Dude

    Tech Member
    3,138
    0
    16
    Southbridge, MA
    Random VR/AR trash
    <!--quoteo(post=369506:date=Nov 4 2009, 04:46 AM:name=Ultima)--><div class='quotetop'>QUOTE (Ultima @ Nov 4 2009, 04:46 AM) <a href="index.php?act=findpost&pid=369506">[​IMG]</a></div><div class='quotemain'><!--quotec-->How accurate does it have to be? Is it for collision detection optimisation?

    If it doesn't have to be very accurate, you can calculate the AABB of all your vertices, and set the midpoint to the centre of the AABB and the radius to the furthest point from the centre. This is going to make the sphere inaccurate though. The advantage is it's fast, easy and it is guaranteed to enclose all points, so it's useful for speeding up your collision detection.<!--QuoteEnd--></div><!--QuoteEEnd-->

    Thanks for the info, yes I am using this for collision detection. I'm writing a program that takes a text-based scene layout and copies data from it into sonic.exe for sadx. The last feature I'll need to implement is for updating collision info for each object, which is mostly a sphere. And it doesn't need to be very accurate at all, at least not for the PC version. The DC version might not like that, but I'll get to that later.

    What do you mean by "AABB" though(keep in mind I'm thinking xyz)?
    Will the (sum/count) of each coordinate result in an accurate midpoint? And how would you figure out which one was the furthest mathematically?
     
  4. Ultima

    Ultima

    Games Publisher Tech Member
    2,398
    1
    18
    London, England
    Publishing mobile games!
    Well, you've got a few options. Method 1 is fast but inaccurate, Method 2 is accurate but slow (and a little bit easier to implement), and the optional part for method 1 is an idea I had to improve method 1's accuracy without needing all the processing power of method 2. I mentioned a mathematical way too - that's about as accurate as method 2, and a little bit faster, but it's too complex.

    METHOD 1: AABB = Axis-Aligned Bounding Box. <a href="http://devmaster.net/wiki/AABB" target="_blank">http://devmaster.net/wiki/AABB</a>. This page contains info for calculating the AABB from vertices :P

    If the centre that you need is the exact mathematical centre of all the vertices (ie you don't have any moment of inertia or anything which I'm assuming you don't) then you just take the centre of the AABB (min.x + max.x / 2, min.y + max.y /2, min.z + max.z / 2).

    Calculating the furthest point from the midpoint is easy. Use pythagoras for each point of the AABB - ((point.x - centre.x) * (point.x - centre.x)) + ((point.y - centre.y) * (point.y - centre.y)) + ((point.z - centre.z) * (point.z - centre.z)). This gives the distance squared for that point from the centre. Compare these and whichever is biggest is your furthest point, then use the square root of your pythagoras result to get the actual distance, and thus the radius.

    METHOD 2: If it's in a program then speed isn't really that much of a concern: you could probably get away with just working out the distance of every vertex from the centre and this would be the most accurate method possible. You basically iterate through all of the vertices, working out the squared distance from the centre (see method 1), then when you've got the biggest distance you take the square root of it and that's the sphere's radius. The average of all the points,like you said, will get your midpoint.

    OPTIONAL FOR METHOD 1:

    I was thinking that if you did want it to be more accurate, you could improve the accuracy in stages using some guesswork. You start as above to work out your starting radius: this is guaranteed to be bigger than the "real" radius, so all you have to do is keep making it slightly smaller until one of the vertices is outside of your sphere. So pick an accuracy value - something like 0.25.

    Code (Text):
    1. PSEUDOCODE:
    2.  
    3. FUNCTION(sphere sphere1)
    4. {
    5. &nbsp;&nbsp;&nbsp;&nbsp;radius = sphere1.radius
    6. &nbsp;&nbsp;&nbsp;&nbsp;while(true)&nbsp;&nbsp;&nbsp;&nbsp;//loop forever, or maybe set a limited amount of "runs"
    7. &nbsp;&nbsp;&nbsp;&nbsp;{
    8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sphere2.pos = sphere1.pos
    9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sphere2.radius = radius
    10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(all points)
    12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
    13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(point is outside sphere2)
    14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
    15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;&nbsp;&nbsp;&nbsp;&nbsp;//this is our final radius
    16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
    17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
    18.  
    19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;radius -= 0.25
    20. &nbsp;&nbsp;&nbsp;&nbsp;}
    21. }
    To test if a point is outside a sphere, just do pythagoras, similar to before: ((point.x - sphere.pos.x) * (point.x - sphere.pos.x)) + ((point.y - sphere.pos.y) * (point.y - sphere.pos.y)) + ((point.z - sphere.pos.z) * (point.z - sphere.pos.z)) - this gives the squared distance from the centre of the sphere - compare this to the squared radius and if it's greater then the point is outside the sphere.
     
  5. Ultima

    Ultima

    Games Publisher Tech Member
    2,398
    1
    18
    London, England
    Publishing mobile games!
    Any luck?