Started by Aug 17 2011 03:33 PM

,
8 replies to this topic

Posted 17 August 2011 - 03:33 PM

Hey all,

I thought that if one has a minimum OBB it is then possible to get a minimum sphere from the OBB. I believe I can just reuse the center points and then for the spheres radius I make use of the axes/extents. I thought that it would be the length of the vector formed by the three extents, i.e.

radius = Vec3(extent[0], extent[1], extent[2]).length()

but this doesn't seem to be the case. I think that this only works for axes of the from (1, 0, 0), (0, 1, 0), (0, 0, 1).

I know that I could just take the center and find the distance to the furthest vertex for my radius, but if it is possible to get the radius essentially free from the OBB that would be nice.

Any suggestions on how to do this is appreciated!

I thought that if one has a minimum OBB it is then possible to get a minimum sphere from the OBB. I believe I can just reuse the center points and then for the spheres radius I make use of the axes/extents. I thought that it would be the length of the vector formed by the three extents, i.e.

radius = Vec3(extent[0], extent[1], extent[2]).length()

but this doesn't seem to be the case. I think that this only works for axes of the from (1, 0, 0), (0, 1, 0), (0, 0, 1).

I know that I could just take the center and find the distance to the furthest vertex for my radius, but if it is possible to get the radius essentially free from the OBB that would be nice.

Any suggestions on how to do this is appreciated!

Posted 17 August 2011 - 03:41 PM

By definition, the vertices are equidistant from the center. You should be able to use what you're using, if I'm thinking straight; show some code maybe?

Posted 17 August 2011 - 04:41 PM

For my radius I have the following python code

For rendering the sphere in 2D I have the following javascript code

The data for my OBB is the following:

Center: -0.59886017446 -0.0983405452277 3.41642282281

Axis[0]: -0.528170568862 -0.025137618422 -0.848766134061

Axis[1]: -0.849138298623 0.0156357924773 0.527939079635

Axis[2]: 0.0 0.99956171502 -0.0296036799456

Extent[0]: 2.97967211026

Extent[1]: 2.95378776944

Extent[2]: 0.783827040213

The data for my sphere is the following:

Center: : -0.59886017446, -0.0983405452277, 3.41642282281

Radius: 4.26821893775

The OBB is the shape of a slightly rotated diamond. The sphere does actually seem to be reaching the extents of the diamond shape, however the sphere has tons of empty space and is far from minimum.

Is it a property that a minimum sphere can be constructed from a minimum OBB? If so, and you say I am computing the radius correctly, then perhaps I have a bug in my OBB that makes it not quite minimum?

radius = math.pow((mMinBox.Extent[0]*mMinBox.Extent[0]) + (mMinBox.Extent[1]*mMinBox.Extent[1]) + (mMinBox.Extent[2]*mMinBox.Extent[2]), .5);

For rendering the sphere in 2D I have the following javascript code

for (var angle=0; angle < 365; angle+=5) { var angle_radians = angle * Math.PI / 180; var x = center[0] + radius * Math.cos(angle_radians); var y = center[1] + radius * Math.sin(angle_radians); var vertex = [x, y, center[2]]; points.push(vertex); }

The data for my OBB is the following:

Center: -0.59886017446 -0.0983405452277 3.41642282281

Axis[0]: -0.528170568862 -0.025137618422 -0.848766134061

Axis[1]: -0.849138298623 0.0156357924773 0.527939079635

Axis[2]: 0.0 0.99956171502 -0.0296036799456

Extent[0]: 2.97967211026

Extent[1]: 2.95378776944

Extent[2]: 0.783827040213

The data for my sphere is the following:

Center: : -0.59886017446, -0.0983405452277, 3.41642282281

Radius: 4.26821893775

The OBB is the shape of a slightly rotated diamond. The sphere does actually seem to be reaching the extents of the diamond shape, however the sphere has tons of empty space and is far from minimum.

Is it a property that a minimum sphere can be constructed from a minimum OBB? If so, and you say I am computing the radius correctly, then perhaps I have a bug in my OBB that makes it not quite minimum?

Posted 18 August 2011 - 04:23 PM

I have taken a variety of screen shots to help visualize the problem I am trying to solve.

I am basically down to two questions.

1) Does my OBB appear to be minimum?

2) Am I guaranteed to get a minimum bounding sphere from the minimum OBB?

The model with an OBB BV is here:

http://postimage.org/image/25hlvways/

The convex hull of the model is here:

http://postimage.org/image/baeww3hg/

With this image

http://postimage.org/image/balj1hgk/

we can see that the OBB shares an edge with the convex hull, which is a requirement for a minimum OBB.

With these two images it is clear that the sphere formed form the minimum OBB is not minimum:

http://postimage.org/image/bayrc9es/

http://postimage.org/image/bb710zvo/

So either one of two propositions must be true.

1) I may have some bug and the OBB is not truly minimum.

2) We are not guaranteed to get a minimum bounding sphere from a minimum orient bounding box.

I am basically down to two questions.

1) Does my OBB appear to be minimum?

2) Am I guaranteed to get a minimum bounding sphere from the minimum OBB?

The model with an OBB BV is here:

http://postimage.org/image/25hlvways/

The convex hull of the model is here:

http://postimage.org/image/baeww3hg/

With this image

http://postimage.org/image/balj1hgk/

we can see that the OBB shares an edge with the convex hull, which is a requirement for a minimum OBB.

With these two images it is clear that the sphere formed form the minimum OBB is not minimum:

http://postimage.org/image/bayrc9es/

http://postimage.org/image/bb710zvo/

So either one of two propositions must be true.

1) I may have some bug and the OBB is not truly minimum.

2) We are not guaranteed to get a minimum bounding sphere from a minimum orient bounding box.

Posted 18 August 2011 - 04:41 PM

The second proposition is right. You would always get the radius of the box. Your formular don't knows about the shape of the model only the shape of the box. Why would you use a sphere as bounding box when it is clear that it would be more free space?

Posted 18 August 2011 - 05:28 PM

The sphere is simply for a quick check before moving on to the more accurate OBB/OBB collision checks.

So you are saying that with any minimum OBB, taking the length of the vector formed by the 3 extents will give a minimum bounding sphere? If this is true then my OBB is not minimum? It must be one or the other as it is clear from the pictures that the sphere is not minimum.

I know that for an OBB with 0 empty space this is true, but I question if it is true for a model with empty space, such as the model in the pictures.

Thanks for the help. I really appreciate it =)

So you are saying that with any minimum OBB, taking the length of the vector formed by the 3 extents will give a minimum bounding sphere? If this is true then my OBB is not minimum? It must be one or the other as it is clear from the pictures that the sphere is not minimum.

I know that for an OBB with 0 empty space this is true, but I question if it is true for a model with empty space, such as the model in the pictures.

Thanks for the help. I really appreciate it =)

Posted 20 August 2011 - 02:26 AM

Problem with a sphere is that it only haves 1 degree of freedom. You can only xhoose one size for every axe. So if one bounding box axe is slightly bigger the sphere would have more free space because the biggest axe would make the sphere. But on the picture is looks like the box is not in centre of sphere, that's maybe the problem.

And also you are generatimg the sphere wrong. The radius is the biggest axe extent.

And also you are generatimg the sphere wrong. The radius is the biggest axe extent.

Posted 20 August 2011 - 04:47 AM

This statement is slightly ambiguous, and wrong or right depending on how you interpret it. If you have an object M (such like the character mesh in your picture), and the minimal enclosing OBB O for the object M, then the following statements hold:So you are saying that with any minimum OBB, taking the length of the vector formed by the 3 extents will give a minimum bounding sphere?

1) The sphere S which minimally encloses O is computed by taking the center of O as the center of sphere, and using as the radius half the length of the diagonal of O.

2) Even if S computed like above minimally encloses O, it most often is not the minimal enclosing sphere for the object M. (It can be quite bad, as you noticed)

So you see that the "minimally enclosing" property is not transitive. If S minimally encloses O, and O minimally encloses M, then it does not follow that S also minimally encloses M.

To produce a minimal enclosing sphere, see for example the Miniball code, or Welzl's algorithm. For a fast and very good approximation, see the Ritter's algorithm.

Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

Posted 20 August 2011 - 05:27 PM

Thanks for all of the help guys. I feel like I have solved this problem and I want to wrap things up and convey what I have learned for future people who may be facing the same problem.

For an OBB with 0 empty space (i.e. the object is rectangular and the OBB perfectly fits it) forming a sphere from the center and extents of the OBB will give you a minimum sphere. For any OBB that is not perfectly fitting you are not guaranteed to (And most likely will not) get a minimum sphere from the OBB. As clb states, a minimum sphere can be obtain from Welzl's algorithm and eberly has code for this at geometrictools.com.

If you do not care that the sphere is minimum and just want a quick sphere from an OBB it can be calculated by using the same center as the OBB and then the radius equals the length of the vector formed by the 3 extents of the OBB.

This is wrong. Not that I don't appreciate the post, I just do not want others to spend time heading in the wrong direction.

Here is the data for the object above. The minimum sphere is generated using Welzl's algorithm and as you can see the minimum radius is larger than all 3 extents.

OBB:

Center: -0.59886017446 -0.0983405452277 3.41642282281

Axis[0]: -0.528170568862 -0.025137618422 -0.848766134061

Axis[1]: -0.849138298623 0.0156357924773 0.527939079635

Axis[2]: 0.0 0.99956171502 -0.0296036799456

Extent[0]: 2.97967211026

Extent[1]: 2.95378776944

Extent[2]: 0.783827040213

Sphere:

Center: 5.55111512313e-17 0.0716081026349 3.43848969457

Radius: 3.60353099695

For an OBB with 0 empty space (i.e. the object is rectangular and the OBB perfectly fits it) forming a sphere from the center and extents of the OBB will give you a minimum sphere. For any OBB that is not perfectly fitting you are not guaranteed to (And most likely will not) get a minimum sphere from the OBB. As clb states, a minimum sphere can be obtain from Welzl's algorithm and eberly has code for this at geometrictools.com.

If you do not care that the sphere is minimum and just want a quick sphere from an OBB it can be calculated by using the same center as the OBB and then the radius equals the length of the vector formed by the 3 extents of the OBB.

And also you are generatimg the sphere wrong. The radius is the biggest axe extent.

This is wrong. Not that I don't appreciate the post, I just do not want others to spend time heading in the wrong direction.

Here is the data for the object above. The minimum sphere is generated using Welzl's algorithm and as you can see the minimum radius is larger than all 3 extents.

OBB:

Center: -0.59886017446 -0.0983405452277 3.41642282281

Axis[0]: -0.528170568862 -0.025137618422 -0.848766134061

Axis[1]: -0.849138298623 0.0156357924773 0.527939079635

Axis[2]: 0.0 0.99956171502 -0.0296036799456

Extent[0]: 2.97967211026

Extent[1]: 2.95378776944

Extent[2]: 0.783827040213

Sphere:

Center: 5.55111512313e-17 0.0716081026349 3.43848969457

Radius: 3.60353099695