Hey everybody! Here''s what my post is about. I am trying to make an octree (or is it octtree? ) engine. I have read up on them from various websites, and I think I know how they operate and how they subdivide, and by recursion they check each triangle and see if they are inside the bouding box, and this recursion occurs until less than a set number of polys are inside the bounding box. Herein lies my problem: How do you test if a triangle is inside the bounding box? For example: I would like to have a terrain file from 3DS max loaded, and from the vertex data, build an octree. How would I compare these vertex to see if they were in, say, a bounding box from (-1,-1,-1) to (1,1,1)? Would I use the shared vertex interlopation method, simple triangle lists, triangle stips, or something completely different? Also, from what I''ve read, you have to compare every single triangle with each and every bounding box. If you had 100,000 polys in the terrain, that would mean somewhere around 10,000 bounding boxes, meaning around 1,000,000,000 calculations! Where am I misunderstanding here? Thanks for your help! -SkyFire360

a billion calculations aint much wait until u do some raytracing eg for generation of lightmaps etc then the figures up into many trillions.

the beauty of an octree is that though the setup costs a quite high in setup time but during gameplay execution is quicker and thats where it counts.

eg u wanna test whats in the view frustum
so u check one of the octrees nodes against the frustum planes + theres 3 possible answers.
1-the node is totally within the frustum, mark it and all its children as being within the frustum
2-it starddles the border of the frustum, do this test on its immediate children
3-the nodes completely outside the frustum, go no further all the children are outside as well

compare this with a no subdivision technique

loop through every triangle in the scene
is triangle toitally outside frustum mark as outside
else mark as inside

this cost way more testing during the game play and in consequence will prolly run slower

http://members.xoom.com/myBollux

hmmn, I think that I might clarify zedzeek''s reply, to answer your question better:

you only have to calculate those billions (or trillions) of times when you setup the world. This choses which polys are where. after that, all you have to do is chose which octree nodes to render. like this:

Main/first/mother node (is it in view?) (one calc)
partialy, so do the child nodes (it could be all in view, then it would all be rendered)
do each chid node, check if it is in view (1 + 8 calcs)
if fully in view or not in view render or not render it (dont check) (9 + 8(or so) calcs)
keep doing this (17 + a lot less than 8^octree_levels calcs)

that is only a few hundred (or maybe less) calculations, not a few million. That is the advantage of Octrees.. if you can''t see the node behind you, you can''t see any of its children, thereby not having to calculate for them.

cool, huh?

ANDREW RUSSELL STUDIOS

Thanks for the information! Now I have a partially-working octtree. Boy is this exciting

One question though. What happens if a polygon is larger than the bounding box? For example (please forgive the horrendous ascii )

o------o
.\.|B|.|
..\....|
...\...|
....\..|
.....\.|
......\|
.......o

Would this produce some odd results? Should I calculate if the lines are intersecting the planes of the box, instead of the points? Or should this child simply have no polys in it?

-Thanks!

Edited by - skyfire360 on January 16, 2001 9:13:55 AM

Hi,

You have to include such a poly in the bounding box. Otherwise you may get your scene drawn incorrectly. As an example, imagine a floor made of one huge polygon. Then walk to the middle of the floor and look straight down. All the other nodes will get culled away and leave you with just the ones below you, which probably don''t contain the floor poly and it won''t get drawn.

To test for these cases, check if the plane of the poly intersects the bounding box. If it does, you need to find a point on the plane _and_ inside the bounding box (you can just use one of intersection points). If you do a point-in-poly test for this point and it is in the poly, then the poly should be included in this node.

Checking if the polys lines intersect the box isn''t enough by itself. What if the poly is especially large and the lines go around but not through the box? It should still be included.

Hope that isn''t too confusing, I can go into more detail if you like?

Dan