Hi all. I have started to implement using my own code an Octree system. After reading a lot of papers about this subject i have everything quite clear in my head. I know how will i start making it and where i should arrive at the end. My problem is that i have two methods when dealing with the triangles located into two nodes / cubes of the octree at the same time. 1) I split the triangle using the plane between the two nodes of the octree and i get two triangles or a triangle and a quad (which can be split into two triangles). 2) I mark the triangle as contained in both nodes / cubes and implementing a method with which i can determine the node that is in the current frustum and temporarely mark the triangle as in that node. This way, if both nodes are in the frustum, i render the triangle only once. If only one node is in the frustum, i draw the triangle anyway. In my opinion, the second method should be much more straight-forward. The question is : which one should i use ? I want to know if i am on the right track and if there are others variants which i might be able to choose from. Thank you very much for your time moromete

method 2 is bad for moving objects, since you''ll spend far too much time reorganising your pointers to the multiple nodes you''re contained within, and if you miss one and fail to clean it up the cumulative errors get insane (speaking from expereince after using an array as space partitioning).

Instead use the octtree to your advantage: if it doesn''t fit, move up the tree to the parent node and try again. Wash, rinse and repeat When I figured this out i was pretty impressed, its a remarkably elegant way of doing things (it may be formally defined as a ''loose'' octree, or i may be confusing that with something else).

Oh, and you may want to add what i call a ''world node'' which sits at the very root and has no dimensions. It can therefore always contain anything really big/awkwardly placed.

quote:

---

Original post by OrangyTang
Instead use the octtree to your advantage: if it doesn't fit, move up the tree to the parent node and try again. Wash, rinse and repeat When I figured this out i was pretty impressed, its a remarkably elegant way of doing things (it may be formally defined as a 'loose' octree, or i may be confusing that with something else).

---

What do you mean by "move up the tree" ?
What do you do if one triangle is partially contained into one node ? You are storing this triangle into the "world node" and
always render it ?

moromete


[edited by - moromete on September 11, 2002 5:32:39 PM]

An octree is ''simply'' a regular search tree but with specific constraints - that each node is split equally into 8 child nodes which are non-overlapping and totally within the parent node. This is repeated until you decide a node is small enough and so this becomes a leaf node with no children.

But remember that you can store objects in any node in the tree - not just the leaf nodes. So you progress by inserting an object into the tree until you find a node it cannot fit into (or a leaf node which it can fit into, in which case just insert there). Then you step back to the parent node and check that you can insert the object here instead.

The world node is just a catch all container that anything really huge or badly placed can be stored.

wow,
a really nice solution, never thought about it before
Thanks for this great idea.

the big problem with that solution, is that you will be including 100''s, if not 1000''s of triangles that run along the centre axis of the root node no matter what.

There is, however, a MUCH simpler method that is more logical, and works, well, perfectly.


Simply whack the triangles into each node as is, based on their rough centre position, then, for each leaf node, calculate the maximum bounds of each traingle (ie, how far they jut out from the cube) and store this data as a rectangular cube shape in each node.

Repeat this up the tree, based on the child nodes, not the data.

Then, when you traverse the tree, doing calculations, don''t use the cube''s size/position, but use the rectangular bounds of the cubes.

I''ve done this in a dynamic octree, so I can guarentee you that it works, and works very efficiently. And doesn''t have the huge problem of the previously mentioned method.

<-- smile :-)

I fail to understand how does your solution store less triangles.

If you are able to store a triangle in any node of the tree, it will still be stored only once. You wouldnt keep trying to store this triangle in the lower (or upper) levels.

Nitzan

-------------------------
www.geocities.com/nitzanw
www.scorchedearth3d.net
-------------------------

If you take any triangle that covers two nodes, and shove it upwards in the tree, you will find that anything that crosses the major divisions in the world node will be drawn every frame, unnessarly. This realy causes problems for efficiency and accuracy of the culling.

The way I designed my octree (I have never totaly implemented an octree, I don''t know why, I should one day. I have code lying around for everything, from frustrum culling to rendering to sorting to... anyway...)... So yes, the best way I have designed for an octree is to have a frameindex in the render. When you store the properties of the triangle, you need one more property, this will be the last rendered frameindex. There need only be one triangle object for each triangle, but you must point to it from every node the triangle exists in.

So when you go to render, you check if the triangle frameindex == the current frameindex. If it does, it has already been rendered. If it dosn''t then render it and make its frameindex = the current frameindex.

This adds a few instructions per triangle, however its main selling point is that it does not distroy the octree''s ability to render very small parts of very big worlds. There is no need to do a calculation for every triangle in the world, nor is there any need to make a list of triangles to render every frame and check that there are no duplicates (very slow and silly way of doing octrees). Also, the frameindex can be of any size you like. It will work with a size of 1 byte, and there will be very, very rare occurances where triangles do not get rendered ona frame (because of the wrap-around), or you could make it 4 bytes (which will align with the compile-time memory alignment probably anyway) and then you would practicly never see a triangle dissappear.

All in all, this is a good and easy method that works. It has almost 100% accuracy (that can be improved for quality/degraded for speed) and does not affect problems with world size.

Good luck.

Do not meddle in the affairs of moderators, for they are subtle and quick to anger.

---

ANDREW RUSSELL STUDIOS
Cool Links :: [ GD | TG | MS | NeHe | PA | SA | M&S | TA ]
Got Clue? :: [ Start Here! | Google | MSDN | GameDev.net Reference | OGL v D3D | File Formats | Go FAQ yourself ]

Hi all.

Andrew Russell : Your method is actually like the second method from my
original post; I also think it works but there are however some small
extra tests for every triangle potentially contained in the current frustum
(to tell if it was already rendered or not, and if it was not, then store
the current frame index).

RipTorn : i somehow fail to understand how i may be able to implement
your method...Can you please give us a small example or a more
detailed explanation ? It seems like something much more elegant
than any method i found so far but i just can''t understand it
(maybe this is the reason ) )

Thank you very much for your time
moromete

Andrew: Thats quite a neat way of doing things as well. My method is what i use for game objects (player, bullets etc.)
so theres alot of movement and reshuffling, so in this case its probably more suitable, since otherwise keeping track of
all the pointers to multiple nodes can be a real pain. For static (or mainly static) triangles your method seems better though.

I confess to not understanding Riptorn''s method at all though.