Sign in to follow this  

Dividing a model into a grid-like structure?

Recommended Posts

Hi! I'm currently remaking my game engine so that the level data (the static data, that is) is simply one model that gets split up at loadtime/runtime into smaller pieces. The problem is that I only got the theory down, I don't really know how to transform my paperscetches into 3d code. ;) I figure I need to create a cube-like clipping box and compare the model to each of these boxes, then create a model for each box, containing the triangles that pass the clipping-test...? I have frustum culling set up, but it's only for spherelike objects (i.e pythagoras formula) and I don't think I can reuse it for dividing triangles/lines etc... A poor-mans solution would be to manually clip the finished level in a 3d program, but that's not really nice from a professional point of view! :) I guess it's somewhat similar to performing collision checking with each plane, and if a collision occurs - get the collisionpoint. But how should I trace the next point of the triangle, etc..? So.. Can anyone help me with some pointers or directions where I can find more information about this matter? Cheers, and good night! :D

Share this post

Link to post
Share on other sites
I think you are referring to a procedure known as space partitioning. There are numerous ways to do this, including BSP (Binary Space Partitioning, used in Quake), Octree and Quadtree. In my engine, I am using a much simpler thing which works simply like this:

1. For each mesh object in the scene
2. Divide mesh object's bounding box into a specified number of smaller boxes
3. For each of the mesh object's polygons
4. Check the first of the small boxes that contains at least one of the
polygon's vertices and push the polygon into the box's polygon list

When I then draw, I simply check frustum culling against which of the smaller boxes I see, and then draw all polygons in the lists of those boxes I see.

Effective? Yes.
Optimal? May not be as optimal as one of the more acclaimed procedures.
Easy? Yes.

Share this post

Link to post
Share on other sites

This is somewhat similar to what I had in mind, except that that triangles must be clipped since I'm planing on using the same system for collision detection as well.

For instance:

If triangle A belongs to box A, but is big enough to cover a piece of Box B;
When the player walks around in box B, he won't collide with triangle A, since it belongs to Box A (which is not checked when the player is in box B)...

This could be solved by instancing so that a copy of triangle A resides in both box A and B...?

that should be reasonably effective, right?
I guess that's what I'll do, seems simple enough. :D

Problem reside thou: Some nasty z-buffer fights will occur if the same technique is applied to the rendering system... And if the triangle only exist in one box but spans several boxes - there will be holes in walls etc if the owner-box goes out of view.

Perhaps this won't be an issue, since most games&graphics nowadays don't use several-cell-sized triangles.. ;)

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

Sign in to follow this