Tree idea

I love innovation !

Hmmm... I don''t know if this comment was meant to have a sense of sarcasm or not...

I''m aware that this could/should have been implemented by someone already but I would like to get some feedback about this. It sounds like a promising way to handle world storage and I wonder why it hasn''t been used by now.

hey,

I was wondering how do you handle these: "Each sector has a AABB which can be adjusted dependent by the objects stored in the sector." because did that mean you create the sectors depend on the terrain, add the "objects" and if a "object" didnt fit exactly into the sector, the sector will expand till the object fits?! Whats about the terrain data, is that also stored within these Sectors?! How do you handle the terrain data within such an expanding?! Do you swap some terrain data into the neighbouring sectors?!

Ahh and what did you mean with objects, static objects like trees, stones, whatever..?! How do you handle dynamic objects like the Player, some car, ...?!

Questions over questions..hehe i''m realy interested in your solution because they sounds realy cool

Mfg Impz0r

Hi,

thanks for your interest.

@ImpzOr :

In fact the sectors aren''t bound to anything. You can bind and fit them to what you want. To handle your terrain example, you could do this :

a) You certainly have some type of terrain data storage that is already cut into more or less small pieces (ie. geomipmaps, vim or some other method) unless you use the roam approach (which in my opinion is not quite hardware friendly).

b) If you handle the terrain rendering differnet from the standard object rendering, you might consider wrapping it into one of you standard objects (so that the terrain culling fits into your object culling methods).

c) You create sectors that contain your terrain pieces (means a fit AABB around your terrain data + a top offset for the objects placed on the terrain).

d) you add all your objects to the sector.

Once an object does not fit into the sector it is stored in, the sector has to expand it''s size. The terrain data within the sector stays the way it is. It does not change. This is the principle of overlapping bounding boxes.

The sector changement is done until the half of the object bounding box extends. It''s then put into the sector where he fits better to. The new sector is expanded to normal size + half the object''s bounding box extends. The old sector just flips back into the original bounding box size.

By objects I define all kind of objects : Static and non static. In my experience it doesn''t make sense anymore to make a difference between the two. It''s quite simple to implement a static object behaviour to an object by just adding a flag that hinders the object movement and that controls the transformation path.

So, a player or car or whatever will change the sector bounding box. BUT this is quite fast since it''s quite simple to do with AABBs.

I hope this makes it a little bit more clear.

BTW : I''ve roughly described the transformation/rendering pass of my system within the "octree from gound up" (or so) thread...

Kind regards,
Metron

Heya,

Thanks for the fast answer

Hmm never heard of "loose" boundingboxes..did you get a tutorial or something about this subject?! I''ll be glad if you could share it with me

Anyway.. about the inserting of these "objects" so far i got the idea, you insert an object, check how close the BB of the object fits the Sectors BB, expand the Sector BB about the half of the Objects BB and check again how close it fits?! Hmm and if the object fits fine, you add it to these Sector and expand the Sectors BB about the half..ok and whats about the neighbours do you shrink them about the half?!
But what happens if an object has already been added to one of the neighbouring sectors and dosent fit any longer after the expandation, do you swap the object to the other Sector or whats going on there ?!

Hope you understand what i mean

Thanks alot..

Mfg Impz0r

No I think he means the sector can only extend over half the size of the original sector, and if the object is partly past this point, it tries to fit the object into the other sector.

But what if the object is too long to fit in sector 1 even when extending half sector 1''s width and too long to fit in sector 2 even when extending back half sector 2''s width?

Know what I mean?

Hi,

in fact it's a bit easier than that You should really try to get a hand on the "Loose Octrees" article by Thatcher Ulrich in "Game Programming Gems 1". It really explains it much better than I could do it. The "loose octree" scheme is easy to adapt to the bounding boxes (since a AABB isn't anything else than a cell in an octree)

You have 2 bounding boxes :

- the objects AABB (formerly known as OAB)
- the sectors AABB (formerly known as SAB)

The SAB will be expanded when the OAB touches the SAB boundary until new SAB > original SAB + 1/2OAB. The object then gets out of the old sector and is placed in the new sector which expands with the above mentioned scheme if needed. The old sector snaps back into the original size.

Why 1/2OAB ? Because if an objects is more than 50% in sector A than in sector B it makes more sense to put the object into sector A (and thus have an SAB smaller than if it where in sector B).

@neXius : This is a quite interesting problem. But it's quite possible to solve

If you have objects that are too long for a single sector to fit in, you should reconsider your initial sector size (if a quad/octree like scheme is adopted) or you could do this :

a) if it's a static object (means never moves) consider packing it into a seperate sector and link that sector to all sectors it passes through. Nothing hinders you to stick one sector into another (making it look even more like a quad/octtree; wow... didn't think of this... my scheme is cool ).

b) if it's a moving object, it's getting hard. But you'll have a similar problem in quad/octrees. There you'll have to move upwards the tree to find the node into which the object fits. In worst case this means the root.

still b) A possible solution would be to put the object into all the sectors and handle the rendering with additional flags (ie. ALREADYTRANSFORMED and ALREADYRENDERED). In the transform function of the object, you set the ALREADYTRANSFORMED flag and in the render function the ALREADYRENDERED flag (given that you first transform all your objects and then render them; 2 seperate loops). Like this you prevent the double transformation and double rendering of the object.

Edit :
c) In fact, you could create a new sector that contains all sectors in which the "long" object passes and link that new sector to the pass-through sectors. This is the inverse of a) (where you create a seperate sector for the object). The sector flags will handle the double rendering/double transformation problem...


Does this make it clear ?

Throw your questions at me

Kind regards,
Metron

[edited by - Metron on February 26, 2003 3:31:17 AM]

Hey,

I got another bunch of questions

So you said "The SAB will be expanded when the OAB touches the SAB boundary until new SAB > original SAB + 1/2OAB. The object then gets out of the old sector and is placed in the new sector which expands with the above mentioned scheme if needed. The old sector snaps back into the original size." ok but what happen if the old sector containing other objects, do you have to recalc the loose BB for the old Sector from ground up for all containing objects?!

Another thing, which size got one Sector within your implemantation?! Ah and how do you store these Secors, within a flat structure, mean Sector beside Sector without any tree hirachie or like an quad/octree?!

Thats all for now

Mfg Impz0r

Hi,

sorry that I only reply today... I was quite busy yesterday.

Here we go :

ok but what happen if the old sector containing other objects, do you have to recalc the loose BB for the old Sector from ground up for all containing objects?!

In fact, the original loose octree paper seems to indicate that the octree doesn''t snap back to it''s original size. I think that this will result in an "all boxes overlap" situation where a lot of unnecessary rendering will be done.

So, what are the possible solutions :

a) Keep it as it is and thus after some time have the above mentioned problem. *But* it is only really a problem, if you have a lot of dynamic objects (since you could easily declare your minimum AABB for the sector being the one containing all static objects such as trees rocks etc).

b) Once an object get''s removed, snap back to minimum AABB size and readd all objects. Combining with the "*But*" statement above, this should be fast, since you simply could do it only with you dynamic objects.

I would opt for b) since this will reduce the unnecessary rendering to a minimum.

Another thing, which size got one Sector within your implemantation?!

This isn''t determinated. In fact, I create a new sector and then determinate the size within my editor.

The system is such that the sector don''t have to have the same size. This wouldn''t make sense within a structure with tubes and tunnels.

Ah and how do you store these Secors, within a flat structure, mean Sector beside Sector without any tree hirachie or like an quad/octree?!

Both is possible

In fact my current implementation keeps all sectors within a linear array. The sectors themself only contain a list of connected sectors by storing the connection as the sector ID. I''ll change this into a combination of sector pointer/sector id because this will speed up the connected sector access. Only given a sector ID, I would have to iterate through the array to find the searched sector.

*But* once the sector keeps the pointer to the connected sectors, you automatically can create a tree structure like an octree.

Don''t forget that the sectors don''t have do be one beside another. You can stick one sector into another. Once you have this kind of structure, you have a quad/octree.

The neat thing about all this is that my sector implementation is just a derivate of my C3DObject. The only enhancements is the list of connected sectors that have to be checked and a supplementary world bounding box that doesn''t get affected by the transformation functions.

The objects within the sector a just children.

Kind regards,
Metron

Hey, it''s me again

I was wondering how do you create these "Sector structure", do you create it like most terrain implemantations did, with use of a heightmap?! Ah and can you please explain me how do you store the Terrain data within a Sector, did every Sector contains a VertexBuffer an IndexBuffer and the Texture/Material or did you store all these stuff somewhere else ?!

Thanks for your time

Mfg Impz0r

Hi,

why this obstination with terrain data. The tree structure has nothing to do with terrain...

A possible handling for terrain data has been described by me in post #5 (counting from the top). Terrain Data is there described as data wrapped into a standard object that is put as an object in the sector.

To make it clearer :

// Base object.
class C3DObject;

// object containing a mesh.
class C3DMeshObject : public C3DObject;

// Terrain object refering to a piece of the whole terrain.
// NOTE : ie. a VIPM or something like this.
class C3DTerrainObject : public C3DMeshObject;

// Sector derived from the base object to allow
// usage of all base object functions (ie. Child handling,
// tranformation calls, render calls, serialized file output).
class CSector : public C3DObject;

 

This is a *possible* way to include your terrain data as a simple object into your world management.

NOTE : Having two ways to manage data (1 for terrain data and 1 for all other objects) is quite inefficient.

Kind regards,
Metron