Octree help
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.
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.
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.
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.
Thanks very much.
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).
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).
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?
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?
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.
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.
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?
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.
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.
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?
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?
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!
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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement