🔒 Locked

Implementing octrees

Started by Arcibald Wearlot Jun 18, 2004 at 10:49 AM 12 replies 1.8k views

Original Post

Jun 18, 2004 at 10:49 AM

I'm thinking of implementing octrees in my engine. I know the concepts, but I have never seen an actual implementation, so I'll show you my ideas, so you can tell me where it can get better. -I build the level in 3d studio max -in the exporter, I create an array of triangles and fill it with all the useful info (including the texture they use); i create a big array of vertices, too. -I recursively subdivide the level, working with the triangles --if a triangle intersects the bounding box of a node, the node stores a pointer of it --if there are too many triangles in the node, it is splitted, and the polygons are passed to the children nodes; this way only the leaf nodes contain triangles. -In my engine I load the level. I get two arrays (one of triangles, the other of vertices) and the nodes information -I create a vertex buffer and fill it with the vertex array, and create some dynamic index buffers, as many as the textures used. [Every Frame] -I set the big vertex buffer -I cull the nodes with the frustum planes, so I know what nodes need to be drawn -loop trough every node that has to be drawn --loop trough every triangle of the node ---(only if it is not flagged) write the indices of the triangle to the corresponding index buffer (depending on the triangle texture) ---flag the triangle as drawn -for every index buffer --set it --set the corresponding texture --draw -remove all the flags from the triangle list.. what do you think? is it going to work well/run fast? especially since I already get high framerates (180FPS) drawing the entire level (but it is still far from being complete, so the triangle count is still low) thank you for you help!

xg0blin

Jun 18, 2004 at 11:10 AM

Everything sounds good. Only thing I would change is what you do when a triangle intersects a bounding box. Use a clipping algorithm to split the triangle into two triangles and store each within their respective bounding boxes. Sure you'll have more triangles, but then you don't have overdraw, nor do you have to find a decent solution for dealing with the pointers to all the overlapping triangles.

Pipo DeClown

Jun 18, 2004 at 11:14 AM

How people do it is they have a frame-time with their triangles, and if the frame-time == this-frame, DON'T render, otherwise render and update this triangles frame-time.

Another approach is to use loose octrees. Never used them, only heard of them, sorry. :)

Arcibald Wearlot

Jun 18, 2004 at 11:31 AM

I heard about loose octrees, but they don't seem a very good solution to me. I like the frame-time idea anyway, and I think I'm going to use it, since it seems much easier than triangle splitting..

Etnu

Jun 18, 2004 at 11:35 AM

You're either going to have to split triangles, or else you'll have to use a loose structure. Either triangles go into higher nodes, or they're split. If you don't do one of those two, you wind up with triangles that extend beyond the boundries of the node they're in, which has the potential to create a lot of messed up artifacts as well as making things like collision detection a pain in the butt.

Pipo DeClown

Jun 18, 2004 at 11:38 AM

Keep in mind that the frame-time approach is meant to be a solution on the rendering part. If you do collision detection, maybe you SHOULD follow the other posters advice and split polygons.

Arcibald Wearlot

Jun 18, 2004 at 1:26 PM

Hmm, ok, I'll go for splitting, since I was thinking of using octrees for collision detection too, and you're right, I'm gonna have a lot of problems with collisions if I don't split the polygons.
Thanks guys!

imDivineLight

Jun 18, 2004 at 8:10 PM

Nice discussion on Octrees, i have also tried to implement them a time ago but they seem to hard for me at that time, and again i never found any good commented implementation which matches theory and educate me, so from what resources you are implementing those? books or tutorials or what?

Pipo DeClown

Jun 19, 2004 at 5:07 AM

I first read of them was in a book. But there are enough tutorials on the web to learn from. GameTutorials has some, IIRC, and of course there are more to be found with google.

Etnu

Jun 19, 2004 at 6:37 AM

You shouldn't need a book. It's a very, very simple procedure.

All you're doing is making a series of nested boxes. For a quadtree, it's 4 boxes per box, and for an octree, it's 8.

Really simple when you think about it.

imDivineLight

Jun 22, 2004 at 8:54 PM

you're right, when we have learnt something it seems to easy, but for the one who don't know it's hard, btw theory is very easy and nice i have read it more than 10 times, but when i come to implementing i am stuck, do i need a new vertexbuffer per node? How to check if this triangle is in which node?
etc.

Pipo DeClown

Jun 23, 2004 at 4:05 AM

Quote:
Original post by imDivineLight
you're right, when we have learnt something it seems to easy, but for the one who don't know it's hard, btw theory is very easy and nice i have read it more than 10 times, but when i come to implementing i am stuck, do i need a new vertexbuffer per node? How to check if this triangle is in which node?
etc.

At the beginning of the game/level, you scan through the level's vertexbuffer and store the vertices and indices AND triangles inside each node. So you NEED some structures like these:

struct vertex{};
struct index{};
struct triangle{};

struct texturegroup{ /*WILL contains the above*/ };
struct node{ /*contains neverchanging triangle information*/ };

Now you would have a nodeTREE, that tree would each frame, scan through visible nodes, and add triangle information in each texturegroup.
You'll end up rendering texturegroups instead of nodes.

Promit

Jun 23, 2004 at 9:53 AM

I want to strongly, strongly recommend against the splitting solution.

Don't store the actual polys in the tree. Keep them elsewhere, seperate from your tree. When a poly tests positive against more than one node, simply send it down all of the branches of the tree that it intersects.

Then, when rendering, don't render the polys during recursion. Determine which polys are visible and mark them as visible. Then sort the visible ones by texture/shader and render them that way.

This will be a far more effective way to handle things, all in all. It's a little more costly memory-wise, but far more efficient and flexible.

imDivineLight

Jun 26, 2004 at 11:46 AM

I'm pretty busy implementing GUI system for my engine these days after it i will fix collision system, after it, i will see those ghost trees.

Ppl say Real time terrain engines book explains them, i'll get it :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.