Jump to content
  • Advertisement
recp

3D Best way to get center of scene or model which contains multiple primitives

Recommended Posts

Posted (edited)

Hello,

How can I get center of scene or node or model? What is best way to do this? Scene structure:

Scene
  |
  o - Node[s]
           |
           o - Model[s] // Mesh
                      |
                      o - Primitive[s] // Sub-Mesh
                                   |
                                   o local AABB and world AABB

I'm using AABB's center as center of primitive and I'm combining all AABB boxes to build an AABB for scene. When I visualized the boxes it seems work as expected. 

But I need to get center of scene, node or model for apply rotation around center. Because I'm using a trackball for rotating attached node or model. Currently I'm using scene's AABB's center as rotation point (pivot), for single object it is working. After rotation is completed center of primitive remains same which it should be, I think. But if I load a scene which contains multiple models or primitives, after rotation is completed center of scene's AABB is moving (I'm using that as center of scene). Because every time rotation is completed, new AABB is calculated for scene by combining all sub AABB boxes. I think this may be a normal because there is no balance between AABB boxes while rotating. For instance if I use two same CUBE without rotations center of new scene's AABB remains same.

My solution (it seems work for now):

I created new center member (vec3) in scene struct:

scene->center    = vec3(0);
scene->primCount = 0;

for prim in primitivesInFrustum
   scene->center += prim->aabb->center;
   scene->primCount++;

scene->center = scene->center / scene->primCount

Now I'm using this center as center of scene instead of scene->aabb->center and it seems work.

My question is that what is best way to get center of scene, node or model? How do you get the center for rotation? Any suggestions? Am I doing right? 

Thanks

Edited by recp

Share this post


Link to post
Share on other sites
Advertisement

If I understand you correctly I think you want to use an algorithm for finding the smallest bounding sphere of a set of points, in your case the points in your model.  Then you can just use the center.  I remember there was Welzl's algorithm for circles.  I forget if you can extend it to spheres.  You could also project all your points to a plane and use the circle algorithm if you just need to spin stuff around an axis. Also a quick google gave me the link below.  Hopefully you can make some use of it.

https://github.com/hbf/miniball

Share this post


Link to post
Share on other sites
17 minutes ago, Gnollrunner said:

I think you want to use an algorithm for finding the smallest bounding sphere of a set of points

No I already have bounding box which is Axis Aligned Bounding Box (AABB). Thanks for sharing that algorithm, I'll take a look at it later.

I want to rotate scene or a node around its center, this is all I wanted :) To do this I need center point of scene or node. All primitives already have Axis Aligned Bounding Box (AABB). So I'm calculating center of primitive like this:

center of primitive = (aabb->min + aabb->max) * 0.5

But I don't know center of scene or center of node. A node or model may have multiple primitives. I need average center of all of them to make rotation work correctly.

You can think primitive as sub-mesh, and model as mesh. 

Using spheres instead of AABB could also help I don't know. I wonder how current engines calculate center point for model and for scene. 

AABB is changing after transform so center point of two AABB is also changing. 
 

Share this post


Link to post
Share on other sites

Of course you can rotate around any point but I was thinking to wanted to keep the same point.  If you recalculate bounding boxes at different rotations the center will change.  If you used the smallest bounding sphere for the whole model then the center will stay the same (assuming stuff doesn't move). I mean how important is it that you have an exact center?  Averaging centers doesn't work so well. If you have a lot of stuff on one side and one thing on the other your "center" will be way off.

Share this post


Link to post
Share on other sites

If you want an approximation, you can take all the corners of your leaf AABB boxes at some standard rotation and then feed those into the smallest bounding sphere algorithm. It wont be exact but it will be a lot better than an average of bounding box centers and a bit better than the center of the top level one. It will also be a lot faster than finding the smallest bounding sphere of all points in all meshes.

Share this post


Link to post
Share on other sites
Posted (edited)

Exactly! I want to keep same point as center after rotations are done. Do you suggest to drop AABB completely and switch to sphere or keep both? 

When trackball is attached to a model, a node or a scene; it must use exact and same center. You may rotate object using trackball, then drop mouse then rotate it again, this is why it must use same center. Trackball is just one case. For instance rotating scene/node around its center can be animated. If center will move, it will also move scene/node. After a while, all scene will be moved :( there will be nothing to render 

9 minutes ago, Gnollrunner said:

If you want an approximation, you can take all the corners of your leaf AABB boxes at some standard rotation and then feed those into the smallest bounding sphere algorithm. It wont be exact but it will be a lot better than an average of bounding box centers and a bit better than the center of the top level one. It will also be a lot faster than finding the smallest bounding sphere of all points in all meshes.

Thank you ver much, I will give a try later.

Edited by recp

Share this post


Link to post
Share on other sites
14 minutes ago, recp said:

Exactly! I want to keep same point as center after rotations are done. Do you suggest to drop AABB completely and switch to sphere or keep both? 

 

Depends on what else you are doing. I mean is there any collision detection involved?  That's what AABB is often used for. In any case if you use spheres (even if they are only an aproximiaton of the smallest enclosing sphere) you won't have to recalculate them.  I often use spheres for this reason. For instance when placing trees on my planet the trees will be at different orientations, because the planet is spherical itself. However I can reference the same tree many times and just orient it around it's center point and it's bounding sphere is still valid. 

Share this post


Link to post
Share on other sites
Posted (edited)

Finding the smallest enclosing bounding sphere is not a simple problem:

https://en.wikipedia.org/wiki/Bounding_sphere

One solution commonly used in tools is to decide on a centre (by a variety of methods), then use it, and not recalculate unless requested by the user, or something changes in the scene.

If you really do need to recalculate constantly (it is not clear if this is really needed?), you are going to have a job finding a value that does not change. You could for instance find the average vertex position and use that as the centre. That could work but not be a very good fit in some circumstances. Anything using AABBs is going to change with orientation. I'm guessing many of the algorithms for finding bounding sphere will be approximations and may not produce the same results in different orientations.

/Edit Incidentally it may be better just to refer to an origin rather than centre. Typically objects in 3d are expressed in terms of their origin (offset from a parent), rotation and scale.

It is also unclear what problem you are trying to solve. Are you trying to have a user visualize and rotate a view around a model? Or are you trying to rotate a model in relation to other models in a scene graph?

Edited by lawnjelly

Share this post


Link to post
Share on other sites
Posted (edited)
1 hour ago, Gnollrunner said:

I mean is there any collision detection involved?

Currently I'm working on animation system, after that yes it will be involved. It is next TODO so I can't say much for now. I thought that I can use same AABB boxes for that purpose.

53 minutes ago, lawnjelly said:

If you really do need to recalculate constantly (it is not clear if this is really needed?)

I'm only re-calculating center if parent transform changed. Because if object may move, then I have to re-calculate it, right?

53 minutes ago, lawnjelly said:

It is also unclear what problem you are trying to solve. Are you trying to have a user visualize and rotate a view around a model? Or are you trying to rotate a model in relation to other models in a scene graph?

I want to rotate object using trackball, since it is trackball it must rotate around object's center, not origin, if origin could be (0,0,0) in object space. Also I want to animate object around its center. Not related to other models just around its center. But a model may have multiple primitives so center must be center of all primitives of model/mesh and center of scene must be center of all models, I think

As @Gnollrunner mentioned maybe sphere can fix this issue, because after transforming AABB, the shape of AABB is changing, so center of model/scene/node also changing. This means that the scene is moving by time just because of this.

I used average center (sum of all AABBs centers / AABB count), it seems work. There is rounding errors e.g. center1 = (100.234, 10.095, 78.356), center2 = (100.201, 10.101, 78.4), but better then nothing.

Edited by recp

Share this post


Link to post
Share on other sites
Quote

I used average center (sum of all AABBs centers / AABB count), it seems work. There is rounding errors e.g. center1 = (100.234, 10.095, 78.356), center2 = (100.201, 10.101, 78.4), but better then nothing.

Keep in mind though that depending on your layout, your center may be WAY far from a good rotation point. It may seem to work now because your have stuff somewhat evenly laid out.  I wouldn't use it as a general solution.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!