moving objects, bounding boxes & eye candy

[Grum]

A question for the bbox and eye candy wizards:

 

As I was working on moving and rotating objects from Pawn, I took a look at add_e3d_at_id() in 3d_objects.c to see what needs to be done to when an objects position is updated. Changing the object3d struct itself (rot_[xyz], pos_[xyz], matrix) is easy enough, but then some magic with bboxes and object obstruction is done, so:

• What's the difference between main_bbox_tree_items and main_bbox_tree. I don't suppose objects move between one and the other?
  
• What would be the best way to update the bbox tree? Simply remove the object and re-add it with the new parameters?
  
• Same for ec obstruction: simply ec_remove_obstruction_by_object3d() followed by ec_add_object_obstruction() ?
  
• Is this needed at all, or is there some magic in place that tracks the objects anyway?
  

Thanks for any help you can give me.

 

EDIT: fixed messed up list

 

EDIT2: looks like main_bbox_tree_items is for static objects, and main_bbox_tree for dynamic objects. So what if we try to move a static object? Ignore it? Move it to dynamic? How are the two handled differently?

Edited July 1, 2007 by Grum

[KarenRei]

Re, eye candy: that would do it. However, one thing that's come up concerning eye candy obstructions is that simple bounding boxes don't look quite right. Create a blowing leaves effect in a forest, for example. You'll notice that the leaves pile up great against walls, but they look unnatural when they pile up against a tree's bounding box.

 

Is there any way we could end up with more detailed bounding boxen or something? Or perhaps an "inner bounding box" instead of an "outer bounding box" (i.e., the largest box that contains no part not in the object, versus the smallest box that contains every part of the object)? I'm not sure what the right solution is.

[Xaphier]

Static objects are total static, changing them requires to rebuild the hole tree. The best solution would be to change the tree from a BSP to an octree or r*-tree. I wrote last year an implementation of a r*-tree for volumes (was planed for physic calculations). The tree is in C++, optimized for SSE/SSE2, has threading support (at the moment posix threads, but that's easy to change) etc. I also wrote lot's of test to check the functionality of the tree. If there is any interest in it, let me know.

[Grum]

Okay, for octree I at least had an idea of what they look like, but R* trees I had to look up (though Wikipedia doesn't give overly much information. If you have a link with more details handy, that'd be much appreciated). Couple of questions (bear in mind I'm a noob in this):

*) Is there any advantage of using one structure over the other?

*) Would we be able to store (references to) the actual triangles in it (probably too much information?), or would we still have to restrict ourselves to the current AABBoxes? In the latter case, Karen's problem still wouldn't be solved.

*) Do you have any idea of the impact this might have on the time to build the tree on map load?

 

If you think R* trees are the way to go, and you're really willing to donate your implementation, I'd be happy to give it a try to integrate it into the client. Unless you'd rather do it yourself, of course

[Xaphier]

Okay, for octree I at least had an idea of what they look like, but R* trees I had to look up (though Wikipedia doesn't give overly much information. If you have a link with more details handy, that'd be much appreciated). Couple of questions (bear in mind I'm a noob in this):

*) Is there any advantage of using one structure over the other?

*) Would we be able to store (references to) the actual triangles in it (probably too much information?), or would we still have to restrict ourselves to the current AABBoxes? In the latter case, Karen's problem still wouldn't be solved.

*) Do you have any idea of the impact this might have on the time to build the tree on map load?

 

If you think R* trees are the way to go, and you're really willing to donate your implementation, I'd be happy to give it a try to integrate it into the client. Unless you'd rather do it yourself, of course

Is there any advantage of using one structure over the other?

The R*-tree is optimized for a lot of remove and insert action (verry little tree degeneration). The octree on the other side should be faster if only some objects are removed and insert, because it degenerates and rebalancing is expensiv/requires a rebuild of the tree.

Would we be able to store (references to) the actual triangles in it (probably too much information?), or would we still have to restrict ourselves to the current AABBoxes? In the latter case, Karen's problem still wouldn't be solved.

That could be done with every tree, but I think the memory usage will be too high. At the moment, we need some MB's for the tree, so storing the information for the triangls in the tree, would increase this even more. (I think more than ten times, depends on how may triangles every object has).

My personal opinion is, that using effects that need the triangles itself is one of the reasons why eye candy is so slow.

Do you have any idea of the impact this might have on the time to build the tree on map load?

I think the r*-tree would be slower build than the octree, but I don't think that any them will take a noticeable amount of time. I did some profiling of the r*-tree I wrote and I think it is realy fast (thounds of insert/remove operations per second)

If you think R* trees are the way to go, and you're really willing to donate your implementation, I'd be happy to give it a try to integrate it into the client. Unless you'd rather do it yourself, of course

I have no problem with donating my r*-tree. I would never offer the imlemetation of my r*-tree if I had a problem with that.

[KarenRei]

My personal opinion is, that using effects that need the triangles itself is one of the reasons why eye candy is so slow.

 

Very few effects even check obstructions. The most significant obstruction-checkers (like blowing leaves) were just integrated a week ago, and aren't in any maps yet.