Finding a models radius

You could centre the model in milkshape, this is probably a good idea anyway if you want to rotate the model around it''s own axes. Other than that you could write a simple algorithm to create a new origin for the sphere .

e.g. Create an axis-aligned bounding box, and use the centre of this for the centre of the sphere.

Give your bounding sphere an offset vector and a radius.

- Find the two most distant vertex in your model. This is a second order algorithm (n^2) so you will want to do it once when initialising your model.

- Radius will be half the distance between those two points.
|V1-V2| * 0.5

- Offset will be the middle between those two points.
V1 + V2 * 0.5


Using this algorithm you will find the smallest sphere possible that will contains all vertices. As a said, you will need an offset, that is, your sphere won''t be centered on model origin but rather on middle distance between the longest string in your model.

EXCELLENT! That works well, I''ll just write a plugin for Milkshape that exports the model and a second file with sphere information.

Now, later i am going to change the system to use ellipsoids with three radii: x,y,z. How should i try to do this? This one I have absolutly no idea about.

All help appreciated

I want to be rich. Some people are so rich, they lose all respect for humanity. Thats how rich I want to be.

Or you could use this somewhat better, O(n) algo:

Find the farthest vertex, instead of 2. The distance from that vertex to the center is the radius of the sphere.

____________________________________________________________
Direct3D vs. OpenGL

Promit, please read previous posts before commenting, what your suggesting doesn''t fit the requirements.



I want to be rich. Some people are so rich, they lose all respect for humanity. Thats how rich I want to be.

What are you talking about DanG, Promit made a good point.

What you do though is this: Loop through all the vertices in your model. Find the radius by keeping track of which is the greatest value of each. If you wanted an ellipse, just keep track of the largest value for each axis.

Psuedo code:

loop all vertices
find the radius // for your ellipsoid
center is sum of all vertices

center divided by num vertices is the true center


find the radius could look like this:

currentvert_x = absolutevalue(currentvertex.x - modelcenter.x);
if ( currentvert_x > radius )
radius = currentvert.x

etc...

Thats how I do it for my system. works great, very quick too.



"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com

Here''s how i would do it:

- Maintain 3 sets of xyz components... one for total, one for minimum, and one for maximum:
totalX, totalY, totalZ
minX, minY, minZ
maxX, maxY, maxZ


- Upon loading, loop through all vertices in your model. Check and update min/max for x,y, and z components against this vertex. Also add the components to their respective totals.


- Once you have completed this for all vertices, divide the components averages by the total number of vertices.
centreX = totalX / numVerts
centreY = totalY / numVerts
centreZ = totalZ / numVerts

This "centre" will be the offset from the origin of the coord system your model was created in.


- To get the radial components for the bounding ellipsoid, simply divide the distance between each component by 2
((maxX - minX) * (maxX - minX)) * 0.5
((maxY - minY) * (maxY - minY)) * 0.5
((maxZ - minZ) * (maxZ - minZ)) * 0.5

If you only want the bounding sphere, use the largest of these three radii.


Hope that actually works (I''m a tad hungover, and in need of breakfast... at 3pm on Sunday... you understand )

ah... Dirge, you bastard... pipped by less than 2 minutes... are you saying i typed all that for nothing, when I could have been out finding nourishment and a Berocca

you mean I could have been getting drunk instead of writing that!? ;-)


"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com

Hey,

I might be a bit late for this one, but a very cool (and fast) solution to this was in a Code of the Day on Flipcode. Have a look for an entry called something like: "smallest enclosing spheres" and the authors name was Nick.

T