CreateOctree help?
BlitzMax Forums/MiniB3D Module/CreateOctree help?
| ||
| I've got a level mesh which I make an octree for which speeds up my collision detection considerably. However I noticed that when the player model is in one area of the level where there are a few angles that arn't strait along the x,y or z axis that my frame rate drops considerably. I have a feeling that tweaking the octree numbers would help a lot if I had any clue as to what they actualy do. is max_polys the number of faces that can fit in one octcube? and is max_level how many times those octcubes will be subdivided into individual collision cubes? Playing around with random numbers changes very little besides making the game really slow if I put in stupid values... Little help? |
| ||
| From the readme.txt provided with miniB3D : Octree Notes ------------ * MiniB3D uses octrees to speed-up ellipsoid-to-mesh collisions. * Octrees are not created automatically for meshes. They must be created manually using CreateOctree(mesh:TMesh,max_polys,max_levels). * 'max_polys' denotes the maximum no. of polygons per octcube, and 'max_level' denotes the maximum no. of octcube 'levels', or sub-divisions. * If both are set to greater than 0, then whatever is reached first will be used as the exit condition. * If 'max_polys' is set to 0, then the octree will be sub-divided 'max_levels' times. * If 'max_levels' is set to 0, then the octree will be sub-divided until the no. of polys per octcube is less than 'max_polys'. * Experiment with both values for best results. A couple of suggested values are 200,5 for large meshes and 0,1 for small meshes. |
| ||
| Yea, I've read that many times, but it doesn't make sense to me. primarily because it says "... polygons per octcube" and I don't know what it means by pollys... is that faces? or spacial units? or what? if I have say a rectangular cube shape, that is 60 units along the Z axis and 5 units along the x and Y, what's a reasonable setting for something like that... if it were on an angle (not rotated, but created as a mesh that was already rotated) would that make a difference? i.e. would it need more subdivisions to get better accuracy since it wouldn't be straight along an axis... I'm sure I'm missing something obvious. Is there a tutorial on how to properly use octrees somewhere? |
| ||
| 1. Polys are faces,yes. 2. As far as I know it make no difference if a mesh is rotated before or after creation time. 3 The usage of the Octree depends of the size of your mesh. eg a mesh which is small will need less subdivision (very small: 0,1) a very large mesh needs a lot more subdivison (eg: 200,5) . these values are just examples. to get values of your needs the only way is to test different values. try things like 20,3 or 100,4 etc. there are no limits, but keep in mind the calculation time raises exponential to the subdivisions. |
| ||
| Thanks for the help! if I can get a handle on this I think I'll write up a doc or atleast post some instructions. So if I understand this so far, the max_polys value is how many cubes will be used per face (or in simpler terms, how many pieces each side of each thing you can hit will be seperated into) and then max_levels is how many pieces each one of those sub-face slices are further seperated into... I think... So if I'm right about that 1 max_poly and 1 max_level will make 1 octcube per face... 10 max_polys and 1 max_level would make 1 octcube with a maximum of 10 faces inside it. 10 max_polys and 100 max_levels would make an octcube with a maximum of 10 faces in it and then subdivide that octcube 100 times for greater acuracy in the collision... (which would be crazy slow in most instances since that's 1000 collisions tests per 10 or less faces...) so to simplify it down to a speed vs. acuracy thing. more max_polys means faster and potentialy less acurate. more max_levels means much more accurate but exponentialy slower. Especialy since it's MAX pollys, so setting it to 200 is going to grab 1-200 faces depending on geometry in a given area, but each one of those generated octcubes will be split by max_levels, so if an area has complicated geometry and generates 1 octcube per face, and then subdivides each one by 5, then it could really slow things down. So really it comes down to how complicated is geometry in a given area, and how big an object are you testing with the collision. If you have a bigger object it might be overlaping 2 or 3 or 10 areas with many single faces that are divided many many times causing a lot of slow down. but if it's a small object and it's testing say 2 or more faces and those are only subdivided once or twice then theres a lot less testing to do. are octcubes always perfect cubes or can they be stretched? I'm guessing I'll find out if I test some more. Also by pre rotated I mean if you make in a modeling program a mesh of a cube and turn it 45 degrees and make an octtree for it, would you need more octcubes because the octcubes would be 45 degrees off of the sides of the mesh, or will the octcubes always be along the same orientation as the faces they're attached to... I have a fealing the angle thing is a factor simply because the areas where I have slow down as a result of my bad octree values in my level are areas where there are faces that are not straight along the x, y or z axis. It could also be because there are a few more faces in those areas though but I think I can trial and error it out now. |
| ||
| Clearly I'm not understanding something... I just changed my values from 200, 5 to 100, 1000. with the new settings areas that were getting 50-60 fps (open areas like the middle of the room) are now getting 60-65 and areas that were getting 25-45 (tight areas and places with lots of angles) are getting 75-90... I love the FPS increase but I'll be buggered if I can figure out why it's doing what it's doing... maybe it is just play with the numbers till you get values that work... or maybe my defenition of a "large mesh" is way off... by large mesh does it mean something with say tens of thousands of faces? or does it mean something that is large on a unit scale, like the mesh size is 1000x 1000y 1000z? |
| ||
| Welp, I still don't really get it, but playing around with lots of random numbers got my frame rate up. However if I put an octree on more than one thing (i.e. my level mesh and say a landing pad) certain spots on the level drop to 3 fps... no idea why but I'm guessing that making a second ocrtee somehow combines values of both trees... I really only need it on my level mesh though so not a problem for me... |
| ||
| The current octree.bmx splits polygons in half if they're on a dividing plan which sometimes leads to more polys than is desirable (especially in small tight areas with many polys). I've since changed this so polys are no longer split and it's generally a lot faster - will be in the next version. |
| ||
| aaaaah that would totaly explain a lot of the things I was encountering. Any kind of estimate (weeks/months/etc.) till we might get a new version? |
   |