Public Group

# Spacial Partitioning Woes...

This topic is 4252 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am working on my 3D level geometry right now which I want to partition using a KD tree. Simply put, it divides the space into partitions using various XY/YZ/XZ planes (the 3 types rotate each iteration). I find the best plane to parition a given set of polygons simply by averaging their vertexes (i.e. I find the plane that is exactly in the middle of my polygons, thus ensuring the most efficient division). Of course, if a plane happens to cut cross a polygon, it simply cuts it into two new polygons. However, I forgot to take into account the importance of dividing a single polygon into two... and now, my simple 72 polygon scene, when divided into partitions of no more than 10 polygons, is now made of 1998 polygons ;_; *sigh* Did I make a booboo somewhere..?

##### Share on other sites
Well, fortunately you likely didn't make any booboos, unfortunately the situation that you describe is completely unavoidable if you're going to be dividing polygons. It doesn't take a lot of polygons being divided to explode into a huge amount of polygon saw-dust [especially if you have some sort of number-of-polygons-under-X criteria for stopping your division, you're going to pulverize your entire geometry into sand, since the polygons in each sector actually would likely be increasing with each pass.

So, what are you options.

Well you can just continue to split them, and grit your teeth and put up with the geometry exploding. This method works if you pay close attention to capping the depth that you allow your partitioning scheme to go, but it's nasty, and you've already witnessed the problems with just going along business as usual.

A rather popular method is actually a bit lazy sounding, don't split any polygons. The idea would be to include whole polygons into each tree branch, and allow overlapping in the tree. If a polygon is sitting on the line between two tree nodes, just include the polygon into the tree node that 'most' of the polygon resides in, and extend the tree node's border to completely surround the newly added poly. The structure that this describes is refered to as a 'loose KD tree' [or loose octree, loose quadtree, or loose whatever. 'loose' just describing the allowance of overlapping in the tree nodes]. That way your 72 poly figure STAYS 72 polys, even regardless of how far down you go. You're going to be drawing a bit of extra geometry per frame, but it'll actually be fewer polygons, and thus likely faster.

In any case, the choice is yours, but the loose tree design is certainly something to consider, and certainly solves the problem you're describing in a rather efficient way.

##### Share on other sites

The loose tree is exactly what I was thinking about. I can still see the loose tree getting inefficient. The primary use of the tree will be for collision detection and I can see having to check a lot of unnecesary polygons just because they were stretching out of a tree border... I guess I won't really know until I actually get to working with the full level with a reasonable amount of polies (considerably more than 72) and try to tweak it then.

Quote:
 If a polygon is sitting on the line between two tree nodes, just include the polygon into the tree node that 'most' of the polygon resides in, and extend the tree node's border to completely surround the newly added poly.

Are you saying I should move my dividing plane so that the poly is completly on one side? Lets say I move my plane so that it encompasses my entire poly... but suddenly it starts cutting another poly in half, so I move it again... and again... and I either end up with all polygons being only on one side of the plane (so if I do it again, I will get the same result and thus end in an infinite loop) or going back and forth between two polies, unable to encompass either one of them without cutting the other.

##### Share on other sites
Quote:
 Original post by KoobazaurAre you saying I should move my dividing plane so that the poly is completly on one side? Lets say I move my plane so that it encompasses my entire poly... but suddenly it starts cutting another poly in half, so I move it again... and again... and I either end up with all polygons being only on one side of the plane (so if I do it again, I will get the same result and thus end in an infinite loop) or going back and forth between two polies, unable to encompass either one of them without cutting the other.
Sorry, I should have been a bit more clear on this.

For the sake of explaining things easily, lets consider everything is only being divided along a single axis [for example, we're just using the z/y plane, and slicing up the x axis]. We'll use the x-axis for example. The idea is this :

1: Drop a line somewhere near the middle of our axis, so that the same amount of stuff is on one side as is on the other. Our dividing line sits on x=K.

2: Define two regions, one zone extending from the minimum value of x to K [region 1], and one extending from K to the maximum value of x [region 2].

3: If the plane x = K intersects a polygon, determine which side of K the polygon *mostly* lays on. If it *mostly* lays to the left of K [x-value < K], add the polygon to region 1, and extend region 1's right border to include the entire polygon. If it *mostly* lays to the right of K [x-value > K], add the polygon to region 2, and extend region 2's left border to include the entire polygon. Do this for all polygons intersected by the plane x = K. Note that you're not doing this for the new moved region borders, but instead still only that which is intersected by K. This yeilds a region of overlap that deals with all the poly's that would have otherwise been cut.

4: Repeat this process back from step one for region 1 and region 2 seperately. [you'll find you never have to extend the border that does not wedge up against the plane you're dividing along, and thus never have to worry about propogating the extension back up the tree].

Honestly though, this method is mainly used for graphics, and determining visibility. Depending on what kind of data you're working with, there are other models that work pretty well for physics, that likely outrun this method. There are better ways of representing data specificly for collision detection. Either way though, the problem of shredding poly's is solved.

##### Share on other sites
I see that makes sense... It will require a bit of redesigning, as currently my tree is made of a single plane and a * pFront and *pBack pointers to further nodes. Easy fix though.

What other model would be better for collision detection, though? I only know about spacial parititoning with trees...

*bump*

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633724
• Total Posts
3013552
×