Sign in to follow this  
Kalie

Octree and world geometry

Recommended Posts

Hello everyone, I hope someone can help me. I've been sort of struggling with this problem for a little while, and can't seem to phrase the question well enough to get it answered with searches.

I am creating a relatively simple game using Microsoft's XNA that involves 3d environment similar to a lot of FPS games out there. The map is mostly a building interior with clearly defined rooms containing numerous objects. Judging by the scene complexity I expect, I'm tackling the problem using a combination of octrees and portals. The idea is that the Octrees will handle the objects in the room and the room geometry (visibility and broad collision), while the portals are used to separate the rooms into a basic potentially visible set.

At this stage, I'm working through the spacial partitioning and scene management code. I have built a working loose octree manager that stores discrete meshes in the leaves, which seems to be working well. The problem I'm having now is how to fit 'world geometry' into the scheme. By world geometry I mean the walls/floors/counters, etc that aren't movable and serve primarily as room boundaries (although columns in the middle of the room are possible too). The more complex and movable objects (couches, tv's, vampires) are all mesh objects that are handled by octree nodes.

Currently, the world geometry is being loaded from a custom map file. I sort all of the various polygons based on a material (shader, texture, etc) and render all of the polygons with the same material basically at the same time to help with effect switching. This works perfectly fine for rendering the world, and I can easily just draw these world polygons before trying to march through my octree for visible objects.. and the world geo is simple enough that working any harder to partition it for visibility isn't going to give me much in return.

Now to the problem I'm having (finally! sorry!). I also want to be able to perform collision checking on this world geometry (nothing super fancy just ray and bounding volume collision for now). It would also be nice to not render parts that aren't in the frustum. So, I think it should also be put into the Octree so pieces of the world can be detected in the same pass as when I'm detecting a mesh. Since the polygons are sorted by material and not by location, simply drawing a bounding box around them will mean they're always in collision results.

So, how is this kind of thing best handled? What strategies are wise for taking room boundary data like this and keeping track of it in a loose octree? I admit I might be asking the wrong question here -- it seems that for every one else this is easily handled! I really hope someone has some insight or can point me to something I'm missing, because i'm pretty stumped here.

Thanks!
Kalie

Share this post


Link to post
Share on other sites
If your world scenarios usually have well defined rooms you hit the nail on the head by implementing portals, Octrees however, may not be the best solution for you in such environment, for interior rendering usually BSP is the way to go, this structure is to be pre-processed and saved into your map format, BSP will help you with both collisions and occlusion.

Piece of advice, collision detection, space partitioning and rendering, while they do work best combined, are very different systems and I would recommend you to implement them separated and provide interfaces for them to communicate, the rendering system does not need to know about which space partitioning structure you are using, it just needs to know what that structure has decided should be rendered. In this way you could create one game with BSP, another game with OctTree and use the same renderer for both while changing only the space partitioning structure to best fit the needs of each game.

Share this post


Link to post
Share on other sites
Thanks, Nexus for the reply!

To address your second advice first: Thank you, and I agree... I am currently doing so already. Rendering is taken care of in a batch of objects that implement a 'renderable' interface. These objects are attached to a generic node structure that manages their world position/orientation etc. The nodes and bounding boxes are stored in the loose octree. Each frame, a rendering queue is generated by querying the octree against the camera's frustum. Ray queries are also implemented and return an ordered list of all nodes that collide with the ray. The octree management can be turned off at will or swapped for something completely different, and there'd be no difference in appearance (except for performance)

A BSP tree is a replacement for the octree, as you suggested. As I understand it, the disadvantages of BSP are that it's harder to generate well, doesn't nicely seem to handle movable objects, and organizes geometry in a manner optimized for a painter's algorithm. Since graphics hardware does so much better when you minimize swapping of shaders and textures, I've been lead to believe that the performance is usually better when you batch rendering by material and use the zbuffer to handle overdraw.

In general, I'm pleased with the octree structure for my spacial partitioning, visibility determination, and collision detection for the mesh based objects in my game. These make up the bulk of the rendering load anyway ... a room might have 100s of tris, but the objects inside have 1000s each. I'm mostly trying to figure out a good way to get the static walls and floors into the octree for nice collision detection. I'm pretty sure I've seen people using octrees for this, but I've been unable to find specific information on how they handle enclosure geometry, any further hints? :)

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