Jump to content

  • Log In with Google      Sign In   
  • Create Account

disk octree

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
1 reply to this topic

#1 rouncer   Members   -  Reputation: 290


Posted 23 April 2011 - 01:28 PM

Jon Olick stores a node with 8 bits only, 1 for on, 0 for off... but thats not enough information to actually GET to the child and access its data, how the hell does that work with such little information?!?


#2 IvicaKolic   Members   -  Reputation: 282


Posted 08 August 2011 - 08:30 AM

I know that this is an old topic, but it hasn't been answered so I'll give it a try.

8 bit per atom for placement data is all you need. From that you can very quickly generate all the remaining data - all the ID-s of children and brother nodes.
If this is stored in a PNG file, it will be compressed even more and that is how you can get 1.5 bit like Jon Olic states.
The only thing you need to know to reconstruct all the data is the maximal octree level.

If you assume that traversal of data goes like this:
|   |
B   F--+
|   |  |
C-+ G  I
| | |  |
D E H  J

... you can easily determine all the ID-s of child nodes, store that in separate texture and send it to graphic card...
Note that if child node exists, its nodeID is always curNodeID+1. For the next child you just continue from where you've stopped.
You don't really need child node, but nextNodeID for every node and relative position within parent node...
This is what I would choose for my final node structure that can easily be derived from that simplest 8bit disk data structure:
struct NODE
   unsigned char curNodeLocationMask; // relative position within parent - only 3 bits are important
   int nextNodeID;
  // I don't need first childNodeID because I know it is curNodeID+1

So this is how traversal would look:
void Travese(RAY ray, int curNodeID, int level, BOX parentBox, BEST_RESULT& bestResult)
  BOX myBox = GetSubBox( octreeNodes[curNodeID].curNodeLocationMask ); // To get box of the current node
  if( rayIntersect(myBox, ray) )
	if( level == maxLevelForCurrentDistance ) // if no children or we don't want to go further...
   	// find result:
   	if( curResult > bestResult ) bestResult = curResult;
	else Traverse( ray, curNodeID+1, level+1, myBox, bestResult); // Let's do children...
  if( VALID(octreeNodes[curNodeID].nextNodeID) ) Traverse( ray, octreeNodes[curNodeID].nextNodeID, level, parentBox, bestResult);
So, from that 1 byte structure stored in a PNG file we've ended up with more suitable 5 byte structure used for traversal which is also stored in a texture and send to the graphic card.
Color and other info can be in seperate textures and packed even stronger with DX compression - once you know curNodeID and resolution of the octree texture, you can determine point in color/normal/spec/emissive texture and sample that data, but you only need that at the very end of traversal (level == maxLevelforCurrentDistance).

So to store entire geometry you need:
* one 8bit PNG texture for octree branching (preferably PNG format)
* one 24 bit texture for atom's color (32 bit if you want transparency)
* one 32 bit texture for atom's plane (normal + D constant of a plane)
* one 24 bit texture with emissive amout, specular amount and specular power.
But those other 3 textures you have to have even with regular triangular mesh, so adding one single channel PNG texture that can be well compressed is nothing much. In fact, in most cases this will take much less space than triangle mesh.

NOTE: I don't use this structure because it isn't suitable for GPU traversal - too much dynamic branching, stack required etc....
I use something else, also 5 byte, but much better for GPU traversal - no branching - no stack - no hassle and very fast.

Problem with this is that you can't order traversal to visit those subcubes that are closer to the ray origin first. Then if you get a hit, you don't even have to go through the rest of the nodes, and you don't need BEST_RESULT variable.

Storing geometry in octree isn't memory expensive at all.

That is all.

EDIT: Small modifications

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.