gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

DS development > Octree splitting polygons theory

#117121 - Rajveer - Thu Feb 01, 2007 1:40 pm

Hi guys, I'm implementing an octree to split collision data and it's going fairly well. I'm at the stage where I'm deciding between splitting polygons which span over/through a node into smaller polygons, or just adding these polygons to multiple nodes. Everywhere I look I find people telling me to split polygons but I've been doing some thinking and would like others to read my thoughts and criticise me where needed so I can properly decide. Ok the diagram shows the different cases:

[Images not permitted - Click here to view it]

Now firstly, there's too many cases to distinguish how many vertices should be created for a polygon, I'm sure I've missed out a few. Secondly, with each polygon split, you'll have to test collision for however many new polygons are formed, and you'll also have to render extra. Now if I were to share one polygon between two nodes, I'd render them multiple times as I render nearby nodes too (unless I use a flag to say already rendered) but I'll still only test collision for this polygon once (whichever node I'm in). So what is the advantage of splitting polygons into smaller polygons which fit a node over sharing polygons between nodes?

#117122 - kusma - Thu Feb 01, 2007 2:19 pm

First, remember that you don't need to use the same octree for colission-testing and rendering. Or you could store mulitple datasets per node.

Second, a plain, robust polygon/plane clipping routine should handle all cases more or less automatically. You don't need to check for each case.

#117157 - Balkman - Fri Feb 02, 2007 12:16 am

The way I implement collision trees is much more simple but it might not work in your case. What I do is find the center of each triangle. Since that is only a point, whereever that point falls in the node tree thats the one it belongs to. To find the center of a triangle you could do something like the following:

Code:


struct Triangle
{
   float3 vertices[3];
   float3 centeroid;
};

void CCollisionTree::FindCenteroids(vector<Triangle> tris)
{
   // Copy the triangles passed in to the member vector of triangles
   //m_Triangles.assign(tris.begin(), tris.end());
   m_root->m_Triangles = tris;

   // Calculate the center of the triangle
   for(unsigned int i = 0; i < m_root->m_Triangles.size(); i++)
   {
      // Set the centeroid components to zero
      m_root->m_Triangles[i].centeroid.x = m_root->m_Triangles[i].centeroid.y = m_root->m_Triangles[i].centeroid.z = 0.0f;

      for(unsigned int j = 0; j < 3; j++)
      {
         // Get the sum of all three vertex component
         m_root->m_Triangles[i].centeroid.x += m_root->m_Triangles[i].vertices[j].x;
         m_root->m_Triangles[i].centeroid.y += m_root->m_Triangles[i].vertices[j].y;
         m_root->m_Triangles[i].centeroid.z += m_root->m_Triangles[i].vertices[j].z;
      }

      // Get the average of the 3 points on triangle
      m_root->m_Triangles[i].centeroid.x /= 3;
      m_root->m_Triangles[i].centeroid.y /= 3;
      m_root->m_Triangles[i].centeroid.z /= 3;
   }
}


Storing the centers for each triangle might seem like a lot, but I'd figure you'd save memory from all the extra triangles you'd get from splitting. Hope this helps.

#117175 - Ant6n - Fri Feb 02, 2007 1:57 am

Maybe people tell you to split triangles to ensure that one triangle doesnt end up in front of another, i.e. that's why you split when you use bsp's. I guess when using a hardware renderer that can figure out in which order polygons have to be drawn it becomes somewhat of a moot point.

#117176 - sajiimori - Fri Feb 02, 2007 2:06 am

Balkman, how do you ensure that a collision test will hit polys whose centers are in a neighboring cell?

Ant6n, you split polys for BSP even when you're only using the tree for collision (which is what I do). But the resulting tree doesn't even have to contain polys -- just planes.

BSP collision is great. It gives you fast swept box collision, faster ray tests versus solid or empty areas, and an even faster function that reports whether a given point is solid or empty... all without testing against a single polygon!

Poly soup doesn't even make a distinction between "solid" and "empty" areas.

#117191 - Ant6n - Fri Feb 02, 2007 4:21 am

pretty cool idea, never thought about it. When using convex sectors, one does only need planes, not the polygons - pretty cool. That means the same would also hold for a portal engine (which i believe might be the way to go on gba).
So for the octree, which doesn't have the nice properties of convexities, in the end it doesnt matter to split up polygons, i.e. one could have only one instance of each worldpolygon, and every sector in which that polygon resides simply has a pointer.
like that one could reduce polycount (although bsp might reduce it more with a visible set), but one would have to collision check against polygons instead of planes...

#117192 - sajiimori - Fri Feb 02, 2007 5:18 am

Besides speed, I'd hate to live without the benefits of distinguishing "solid" from "empty".

It's great for AI navigation. You can skim a ray under the ground and ask, "When does this ray pass into empty space?" That information can be used to avoid walking off cliffs.

For characters that can grab onto ledges, I check two points near their hands, one above the other. If the bottom point is solid and the top point is empty, there might be a ledge.

#117223 - Rajveer - Fri Feb 02, 2007 2:52 pm

Cheers for the replies guys. I'd rather not use the centre of polygons, as even though the centre of a polygon may be in one node, it may still occupy some space in another node, and when the player is in the second node it would not test for collision where the polygon occupies it.

I think I may do both cases, and see which gives more favorable results. Kusma, you said a good polygon clipper would take care of all the cases I drew, could you point me in the direction of a good algorithm to use? Would Sutherland-Hodgman's method using divide and conquer on edges of polygons work well for an octree with 6 planes to test per node?

#117226 - Sunray - Fri Feb 02, 2007 3:27 pm

BSP trees for collision detection is a good choice. You don't have to split anything unless you need to render the polygons back to front (which you don't in collision detection :).

#117293 - bsder - Sat Feb 03, 2007 10:58 am

What you are doing is a subclass of a bunch of algorithms called computational geometry. I heartily recommend:

Computational Geometry in C (Second Edition)
by Joseph O'Rourke

Make sure to get the second edition. It's *much* more complete than the first.

First, splitting space in 2D--you probably want to look into something called an R-tree. You don't have to be perfect on your polygons as the space partitioning can overlap (you don't have to split the polygon). It has good characteristics and doesn't require a lot of special casing.

http://en.wikipedia.org/wiki/R-tree

Be aware that almost all "linear" algorithms I have seen for R-trees are broken. Use the "quadratic" ones. If you find that the "quadratic" insert algorithms are taking too long, you probably need to prepack the tree (which can be done in n log n).

Second, polygon intersection algorithms are ... annoying. The class of algorithms to to polygon clipping and intersection are called line sweep algorithms. Here is a page that has a bunch of polygon operation libraries:

http://www.complex-a5.ru/polyboolean/comp.html

Hope this helps.

#117408 - kusma - Sun Feb 04, 2007 6:45 pm

Rajveer wrote:
Kusma, you said a good polygon clipper would take care of all the cases I drew, could you point me in the direction of a good algorithm to use? Would Sutherland-Hodgman's method using divide and conquer on edges of polygons work well for an octree with 6 planes to test per node?


Yep

#117559 - sajiimori - Mon Feb 05, 2007 7:13 pm

Sunray, you do have to split polys as usual even just for collision -- it's just that for autopartitioning schemes, you don't have to store the resulting polys in the tree.

But if you want to collide versus anything other than rays and axis-aligned boxes (which I do in my current game), it becomes important to store the vertices in the tree.

#117561 - Sunray - Mon Feb 05, 2007 7:32 pm

You don't have to split polygons. What difference would it make if you perform collision detection against a clipped and a non-clipped polygon? When you're building the BSP tree and a polygon overlaps the clipping plane, simply put a pointer to that polygon in both the back and front node.

Try my demo to see it working (press F2 to fly around): http://sunray.cplusplus.se/?p=proj&pid=11

#117562 - sajiimori - Mon Feb 05, 2007 8:00 pm

Okay, you must be talking about a different kind of BSP tree. =)

Am I correct in assuming that you test versus polygons in-game, and the purpose of the BSP tree is to reduce the number of tests, and you don't distinguish between solid and empty areas?

My data structure does not contain polygons -- only planes (and recently verts to do SATs vs rotated boxes). The planes that the polygons lie on are used as the splitting planes. This is called "autopartitioning", and the result is a tree whose leaves are either solid or empty convex volumes. After you determine that an object is behind all the planes of a solid leaf, it is considered to be colliding with that leaf.

While building a BSP tree using autopartitioning, you choose a plane and then split all the polys that cross that plane. If you don't, you get a bad tree.

#117564 - Sunray - Mon Feb 05, 2007 8:12 pm

Quote:
Am I correct in assuming that you test versus polygons in-game, and the purpose of the BSP tree is to reduce the number of tests, and you don't distinguish between solid and empty areas?

Correct.

So, you store a convex set in each leaf (like quake). But I don't think thats the most efficient method for only collision detection. Never mind.

#117569 - sajiimori - Mon Feb 05, 2007 8:56 pm

It may not be the fastest, but it's much faster than testing versus polys. =)

The first version of my BSP tree format didn't store anything in solid leaves. If all you want to do is test for collisions, there is no leaf data. All the data I store now is for "extra" features: in particular, surface tags (like "wood" or "metal") and support for collision versus rotated boxes.

Edit: To clarify, for tests against points, rays, and swept or stationary axis-aligned boxes, no additional work is needed upon arriving at a solid leaf. For rotated boxes, extra SATs are needed along the box axes.