Sign in to follow this  
Bejan0303

Octree help

Recommended Posts

I am trying to create an octree that can be saved to a map file. Then loaded, and a ray representing position and velocity can be passed in as a query. A list of triangle indices is returned and those would be the only ones need for a more in depth collision check. My question is, is this a good way to do this? I have googled and researched trees, there uses, and other related stuff over the passed month. I just havent found anything like what I am considering yet and want some opinions or better(faster, simpler) alternitives. If it matters, to build the octree I use the SAT method to test if the triangle intersects a child node, making a list for each. Then the list is passed on child creation, and it recurses till a heuristic limit is reach. My query is just a simple ray to cube collision check. I have some source code, but it doesnt seem to be working properly. So I won't bother posting now. Thank you for your time and responses! P.S. Also I'm not sure if this is the right place for this question, I just saw some other tree questions here. I apologize in advance if not.

Share this post


Link to post
Share on other sites
It really depends on what kind of data and how much data you're storing in the octree, and how that data is clustered. Are you storing meshes, whole models, heightmap data, is the geometry static (which I assume it is), etc?

Personally, I find octrees very easy to use, but they're not at all optimal in most situations. If it's heightmap data you're storing, you might consider an even simpler quadtree where each node optionally has bounding height values or if your scene is dynamic/has a lot of objects that are organized in a non-uniform manner, consider researching icoseptrees (essentially a fancy extension of octree). If your scene is static and you're building the spatial partitioning layout offline (eg in an editor), BSP trees are still a good bet, although for ray-casting - as far as I've read (eg especially raytracing) - a well-balanced kD-tree is the way to go. If you're going for maximum simplicity and don't mind calculating spatial partitioning information at run-time, a simple axis-aligned grid might be your best bet.

So, in the end it really depends on what you're trying to do.

Share this post


Link to post
Share on other sites
Ok Thank you so much for the response! To be more specific. I have a static mesh. And wanted to load it into data structure so I could pass my player position and his velocity in and only hae to test those specific nodes, or lists of triangles, whatever. I was going to use a bsp tree first but I kept reading that octrees we more efficient. So I went with that, I haven't head of the icoseptrees, or kD-Trees what and i considered the grid but i wasnt sure if that was as fast and such.

Thanks very much.

Share this post


Link to post
Share on other sites
Unless you're building an editor, I'd go with octrees for now - building a BSP tree is far more expensive and less trivial than an octree (however the queries can be assumed to be faster in most cases - especially assuming you have geometry that is in a variety of size scales).

PS - you probably won't want to do polygon-accurate collision detection at all on meshes unless the mesh has relatively low poly count and is sufficiently large. What you might want to consider is breaking up your more complex meshes into smaller bounding volumes, storing polygon references with those bounding volumes and adding the bounding volumes to your octree (together with a parent bounding volume, which you might prefer to test prior to trying out the child volumes). Using spheres instead of boxes might be a good idea unless your meshes have very odd shapes (eg using a bounding sphere for a flagpole is probably a bad idea whereas it be a really good choice for a small shack).

Share this post


Link to post
Share on other sites
My mesh will have seveal thousand triangles and be static, it's just a terrain file. I was hoping to just store indices to the triangles in the structure. I'm doing a sphere to polygon method of collision if that's what you mean by polygon-accurate and went I tried implementing the bsp tree it seemed just as simple though I might have been doing it wrong. I am making an editor for the file so build time isn't a problem.
Sorry for my ignorance but I thought the tree structure seperated the triangles, I don't follow what you mean by seperating by volumes (let's say spheres) added to octree? Like a "BVH" I read something about that. Again sorry if I'm just missing something simple.
I looked up kd trees and this is very similar to the bsp tree I tried to do at first would this be a more beneficial approach? Thanks for the quick responses and the information.

P.s. Would a grid be better than a tree?

Share this post


Link to post
Share on other sites
I can't comment on kd-trees myself since I've never used them.

However, now that you're mentioning a terrain, unless your terrain can have actual 3D properties (eg it can fold back onto iself, eg it has caves and negative cliffs and all that), you'll be far better off with a simple quadtree or a regular 2D grid with each cell having minheight and maxheight (or height + centerpoint) properties to quickly test AABB-AABB intersections.

When you mentioned meshes I was assuming you were talking about stuff that you can find lying around the house/in the streets.

Something to consider: if you want to stream your terrain from the disk or procedrually calculate it, you cannot really use a quadtree (or any other non-trivial method) and should stick to a regular 2D grid.

Mind you that a heightmap is by definition a 2D concept and for that reason it is by far easiest to treat it as such.

Share this post


Link to post
Share on other sites
sorry for not specifying I didn't even thonk of making that distinction.I wasn't planning on having any caves etc mostly just hilly land. So a would there be any pros or cons to using either a quadtree or grid?or is it basically the same. Also I wasn't planning on using a height map to generate It although if that would simply things. I don't think it would be to difficult to do so. What do you mean a min max height if its a 2d grid or quadtree height is disregarded right?

Share this post


Link to post
Share on other sites
If you look at your heightmap, which can be thought of as a 2D "bitmap", you'll discover that there's three bits of information encoded in it: the x and y coordinates, and a height value for each point. As soon as you interpolate this 2D field of height values, the field becomes a "pseudo-3D" geometric mesh where each height value at each point extends to its neighbours. Which is why your heightmap, when rendered, will look 3D. In other words - for all practical purposes you treat it as 2D (as such it also has all the limitations inherent in a 2D system - eg you can't have things like caves and negative cliff faces), but for some things, eg raycasting you might need to treat it as 3D.

Should you use a quadtree and not sample the heightmap down to each individual height value (eg a each quadtree leaf contains an area larger than a single cell in your heightmap), you'll be storing actual 3D data in the leaves in which case it would be beneficial to calculate AABB's (axis-aligned bounding box) for each leaf. You could use this AABB (which is a box, hence 3D) to perform initial culling/collision/raycasting tests.

As for which one to use: I would use an axis-aligned grid for a small, simple terrain and if the terrain is large (eg larger than 100x100 cells, which is 10 thousand height values), use a quadtree and allocate something like 10x10-30x30 cells in each quadtree leaf.

Share this post


Link to post
Share on other sites
Ok I think I got it. Since I'm doing more outdoor terrain and it will probably be large ill go with the quadtree, just out of curiousity why not the kd tree since you mentioned it would be more effective?

As alittle clarification would just seperate by XZ and divide. I should only have so many "cells" per leaf,by cell do you mean vertice?

Share this post


Link to post
Share on other sites
ok I just did a bunch of research on some of the keywords for your previous posts, and now i understand what your talking about, I was looking at the terrain as 3d model, and even generated from a height map, just still a 3d model. I also follow what you mean by grid/cell/AABB quadtree now.

I understand most often a buffer is stored in a lead and just drawn from there. What if I just stored a list of indices in each and then when culling/rendering just return the appropriate list of indices and glDrawElements out of one buffer to save on draw calls?

It works on my test tree now, but its a small map and I just wanted to know if it made sense before I expanded it. Also, for collision, should i just do some kind of height or is it better to stick with what i have a just check the triangles of the indexed vertices(from my leaf)?

I read some article that used an interpolated "height" (from one pixel to the next) to test for collision at your position. Basically that you cant be lower than said height, it made sense but seemed to simple and inflexible, does something like this work properly?

Thanks again!

Share this post


Link to post
Share on other sites
If you have a heightmap (each height vertex of the map is equally spaced on a plane), imo it's a pretty trivial case.

You can traverse the heightmap real quick using a DDA algorithm for your rays, and a straight forward linear mapping to detect what cells of the heightmap is underneath a particular object.

DDA example.

2D collision grid queries.

A heightmap would require no 'cooking' as well.


and here is a basic KD-tree example, just for kicks.

Share this post


Link to post
Share on other sites
I thought with a grid you would have to test through every cell individually inorder to know which cell the box or whatever was in. So I every object has to be "placed" back onto the grib with every move? I could also use thing same idea for frustum culling, just have Object Frustum?

Thanks

Share this post


Link to post
Share on other sites
Not sure I understand, but it goes like this.

Say you have a heightmap, 4 x 4, each cell 3 units across, with the corner of the first cell at (-2, -1). So the heightmap dimensions are 12 x 12, and stretches from (-2, -1) to (10, 11).

You have a point (x, y), and you want to know what cell it belongs to.

So the position of the point from the grid origin is (x + 2, y + 1) or (x, y) - (-2, -1).

the position on the heightmap, when each cell is scaled down to a unit cell, is

((x - (-2)) / 3)
((y - (-1)) / 3)

so a point (6.2, 8.3) will map to coordinates (2.73, 3.1) on the heightmap, which is cell (2, 3).

If you take the axis aligned bounding box of an object, you can map the min and max points of the box on the heightmap, to find the cells overlapped by the AABB.

If you have box (6.2, 8.3), (10.1, 9.5), the mapping of the min-max coordinates will be (2.73, 3.1), (4.03, 3.5), so the cells between (2, 3), and (4, 3) inclusive.

If you know the triangles belonging to those cells, then you can test for collisions with these triangles.

You can do the same for mobile/static objects, and assign them to the cells they cover and test pairs of objects that cover the same cells (sometimes called buckets). Mobiles objects rarely move by more than the width of one cell. By comparing the previous cell occupancy, and the new area covered by an object, you can optimise the insertion / deletion of object references in bucket lists.

you can use a similar mapping procedure and a DDA algorithm to raytrace through a grid.

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