#115486 - Rajveer - Tue Jan 16, 2007 3:46 pm
Hi guys, I have a 3D world which I need to partition using an octtree data structure. Apparently its easy, but not for me! I'm a bit confused, and would really like a good tutorial on it WITH source code for me to read up on but cant find one. Anybody able to help?
At the moment I know the theory behind the oct-tree data structure and how it uses 8 linked lists for each node e.t.c but finding it hard to begin.
#115489 - kusma - Tue Jan 16, 2007 3:54 pm
| Rajveer wrote: |
| At the moment I know the theory behind the oct-tree data structure and how it uses 8 linked lists for each node e.t.c but finding it hard to begin. |
...But it doesn't! Each node has pointers to eight sub-nodes, not 8 linked lists in itself.
Something like this:
| Code: |
template <typename T>
class Node
{
public:
std::vector<T> data;
Node *subnodes[8];
};
|
#115490 - Lick - Tue Jan 16, 2007 3:59 pm
Try 'octree' instead of oct-tree. ;)
edit: yeah kusma is right. Each node simply has an array of 8 childnodes(ptrs).
_________________
http://licklick.wordpress.com
#115494 - tepples - Tue Jan 16, 2007 6:08 pm
A lot of "3D" games don't have a lot of height in the dimension parallel to gravity. For these, you might be better off with a quadtree than with an octree.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#115550 - Rajveer - Wed Jan 17, 2007 2:28 am
Cheers for the reply's guys :)
Ahh I see what you mean kusma, that makes sense. So I'd begin by creating a data structure for a node, which holds pointers to 8 further nodes, and pointers/variables for data. Then I'd create a function to create the octree, which would create a start node containing pointers to its children and test for each polygon where abouts in the base cube it lies, and recursively call an add function which adds 8 new nodes to existing cubes which need to be split. Or something like that :S
Think I'll have to write alot of pseudo code to get my head round it!
#115576 - Ant6n - Wed Jan 17, 2007 9:01 am
i like kd-trees
anyhoo, the best rersources about that i found at flipcode. site seems down right now, but a wayback machine should help.
http://72.14.205.104/search?q=cache:KdgcJxIo1dEJ:www.flipcode.com/articles/+flipcode&hl=en&gl=ca&ct=clnk&cd=2&client=firefox-a
#115605 - Payk - Wed Jan 17, 2007 8:10 pm
I just use something similar to a 2d tilebased system. Its enough for my project :D
#116147 - Rajveer - Mon Jan 22, 2007 3:04 pm
Ok I've been thinking about it, and just want to voice my thought so someone can check them.
At the moment my polygons and polygon data are stored in a data structure as follows:
| Code: |
typedef struct
{
f32 vertex0[3], vertex1[3], vertex2[3];
t16 tex0[2], tex1[2], tex2[2];
f32 normal[3];
f32 edgeplane0[3];
f32 edgeplane1[3];
f32 edgeplane2[3];
} polydata;
polydata Level1Poly[x]; //x is the no of polygons |
where vertex0-vertex2 are the vertices, each with x y and z components, tex0-tex2 are 2d texture coords, normal is the normal to the plane and edgeplanes are the edges of the planes previously worked out for less processing.
Now for each node of the octree I have to store this data for the polygons. First I will find the max and min x,y and z coords of all the polygons to find the two corners of the first node. Once I've found these I can create the box and workout the size of it. I'm not too confident in programming, and this is the most complex thing I've had to do, so please bear with my "newbishness" ;) I have to:
Test each polygon to see whether it fits inside the original box (which it obviously will) and then find out how many polygons lie within the box. If its greater than the preset value, split the box into 8 smaller cubes and test for each polygons if it fits within these boxes e.t.c.
So for each node, I'd have an array of polygons with the details for each, and a counter to count the total number of polygons in the node. On some sites I've read that the nodes will have a pointer to data, but it doesnt matter right? Also, I'd store 8 pointers to its nodes, which will be null if there are no nodes after it (leaf).
Also, what I'm thinking is that I'd create the first node and a "createNode" function which will create nodes within nodes (the recursion), and I'd keep calling this createNode function each time the current node has more polygons than the preset. Does this sound right?
#116188 - dannyboy - Tue Jan 23, 2007 1:29 am
A couple of comments:
1. You could make it a class instead of a struct, and thus have the data and functions for processing the data better intergrated.
2. Are you not going to keep track of the vertex normals?
3. You could also define a Vector class with respective operations to further break things down.
#116246 - silent_code - Tue Jan 23, 2007 5:35 pm
you could reduce memory usage with vertex pointers or indexing to a vertex array (aka vertex pool) instead of saving vertices per triangle. make a vertex struct (that also includes its normal) and use three indices to access vertex data (e.g. three short ints or bytes for medium size meshes - we're talking about nds programming, so meshes won't have thousands of vertices anyway). it's possible this could increase memory usage because you have those addicional indices or pointers, but most of the time it won't: you often have lot's of adjacent vertices that will get cut down to like 1.5 * triangle_count or less, instead of 3 * triangle_count.
it'll also make animation easier: you just transform one vertex, not two, three or more - depends on how much triangles include that vertex.
as far as i understand you, you're right. with trees, you can either define how deep it gets or how much data each leaf should contain. when splitting into child boxes, you'll have to check each triangle if it is (1) fully inside the boundig box (bb), (2) fully outside the bb or (3) partly in and out. cases one and two are straight forward, but case 3 needs some extra math. you'll have to cut the triangle into sevaral pieces, depending on how much other bbs contain it (a hughe tri can span sevaral nodes).
you can do that e.g. by giving each child a copy of the parent's triangles and the child will cut away (for good!) all parts that stick out of it's bb, leaving the correct data. make sure you handle texture coordinates and vertex normals right, so there's no visual difference afterwards. non leafs have no data, but the child pointers (at least when talking about level geometry).
#116253 - tepples - Tue Jan 23, 2007 6:09 pm
| silent_code wrote: |
| you could reduce memory usage with vertex pointers or indexing to a vertex array (aka vertex pool) instead of saving vertices per triangle. make a vertex struct (that also includes its normal) |
This will work for surfaces that are supposed to look curved, such as an icosahedron approximating a sphere, as the normal is identical on all triangles that share the vertex. But surfaces with actual corners, such as a cube approximating the shape of a crate on top of a pallet, need to have a separate normal for each triangle that shares the vertex. What would be the flexible way to accommodate these two scenarios?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#116256 - ikaris - Tue Jan 23, 2007 7:48 pm
#116261 - Rajveer - Tue Jan 23, 2007 9:11 pm
Cheers for all the replies everyone, I appreciate all the responses!
I wrote some pseudo-code in between lectures today and have been thinking a bit more about it, and I have some questions.
1) Why would making it a class instead of a struct make data integration for functions easier?
2) Does the code for checking if a node contains polygons exist within the function to create the node?
3) To calculate the new texture coordinates of intersecting polygons would I use some sort of linear interpolation?
4) How would I store data in the octree nodes i.e. use pointers to data or actually store it within the nodes? (I'll have to create a new data set anyways because of new polygons created from the intersecting code)
At the moment I'm seeing it this way:
* Find the max and min of all the vertices and construct a cube from them
* Create a start node which stores:
- Pointers to 8 subnodes
- Data of the node's polygons (would this not be a linked list?) including all vertices, normal info e.t.c
- Max, min and centre points of the node
- Polygon counter for the number of polygons in the node
* Use a recursion function to:
- Add a new node
- Check for the current node all of the polygons, if they are contained/not contained or intersect
- Call itself 8 times if the number of polygons exceeds a set amount, creating 8 subnodes
Does this look wrong or totally wrong?
#116320 - kusma - Wed Jan 24, 2007 12:17 pm
| tepples wrote: |
| silent_code wrote: | | you could reduce memory usage with vertex pointers or indexing to a vertex array (aka vertex pool) instead of saving vertices per triangle. make a vertex struct (that also includes its normal) |
This will work for surfaces that are supposed to look curved, such as an icosahedron approximating a sphere, as the normal is identical on all triangles that share the vertex. But surfaces with actual corners, such as a cube approximating the shape of a crate on top of a pallet, need to have a separate normal for each triangle that shares the vertex. What would be the flexible way to accommodate these two scenarios? |
This is very off-topic IMO, but what the hell ;)
Separate vertex and normal indexing is the most flexible solution IMO, but the most practical way is GPU-style explosion of a mesh and merging vertices where all attributes are identical. This way you can do efficient result-caching on computations, but re-generating normals for a given deformed surface will require extra information to avoid extra smoothing-seams.
#116450 - Rajveer - Thu Jan 25, 2007 9:35 pm
Ok guys got some (rather nasty and simple) code I have a problem with, anybody able to take a quick look at my code and help me? It will be alot better/more optimised after I get it to work which is my aim at the moment, its incomplete, also I haven't included all the variables I will need in the node struct e.t.c. so I have alot to do, but cant get this to work at the moment (basically I'm just trying to set up the head node, and check which polygons are likely to intersect it/be contained in it, then check if the number is higher than 10 which is should be):
Node structure:
| Code: |
struct node
{
f32 maxx, maxy, maxz, minx, miny, minz;
int polycount;
struct node* subnode[8];
}; |
Calculates max and min of the first node, and makes a proper cube...
| Code: |
void buildOctree()
{
//Find max and min x, y and z coords
f32 maxx = 0, maxy = 0, maxz = 0, minx = 0, miny = 0, minz = 0;
int n = 0;
for(n = 0; n < polylimit; n++)
{
if(Level1Poly[n].vertex0[0] > maxx)
{maxx = Level1Poly[n].vertex0[0];}
if(Level1Poly[n].vertex1[0] > maxx)
{maxx = Level1Poly[n].vertex1[0];}
if(Level1Poly[n].vertex2[0] > maxx)
{maxx = Level1Poly[n].vertex2[0];}
if(Level1Poly[n].vertex0[1] > maxy)
{maxy = Level1Poly[n].vertex0[1];}
if(Level1Poly[n].vertex1[1] > maxy)
{maxy = Level1Poly[n].vertex1[1];}
if(Level1Poly[n].vertex2[1] > maxy)
{maxy = Level1Poly[n].vertex2[1];}
if(Level1Poly[n].vertex0[2] > maxz)
{maxz = Level1Poly[n].vertex0[2];}
if(Level1Poly[n].vertex1[2] > maxz)
{maxz = Level1Poly[n].vertex1[2];}
if(Level1Poly[n].vertex2[2] > maxz)
{maxz = Level1Poly[n].vertex2[2];}
//
if(Level1Poly[n].vertex0[0] < minx)
{minx = Level1Poly[n].vertex0[0];}
if(Level1Poly[n].vertex1[0] < minx)
{minx = Level1Poly[n].vertex1[0];}
if(Level1Poly[n].vertex2[0] < minx)
{minx = Level1Poly[n].vertex2[0];}
if(Level1Poly[n].vertex0[1] < miny)
{miny = Level1Poly[n].vertex0[1];}
if(Level1Poly[n].vertex1[1] < miny)
{miny = Level1Poly[n].vertex1[1];}
if(Level1Poly[n].vertex2[1] < miny)
{miny = Level1Poly[n].vertex2[1];}
if(Level1Poly[n].vertex0[2] < minz)
{minz = Level1Poly[n].vertex0[2];}
if(Level1Poly[n].vertex1[2] < minz)
{minz = Level1Poly[n].vertex1[2];}
if(Level1Poly[n].vertex2[2] < minz)
{minz = Level1Poly[n].vertex2[2];}
}
//Find max lengths of x, y and z coords, and biggest length
f32 lengthx, lengthy, lengthz, lengthmax;
lengthx = maxx - minx;
lengthy = maxy - miny;
lengthz = maxz - minz;
lengthmax = 0;
if(lengthx > lengthmax)
{lengthmax = lengthx;}
if(lengthy > lengthmax)
{lengthmax = lengthy;}
if(lengthz > lengthmax)
{lengthmax = lengthz;}
//Form a cube by ammending the max and min coords with lengthmax
if(lengthx < lengthmax)
{
maxx += (lengthmax - lengthx);
lengthx = maxx - minx;
}
if(lengthy < lengthmax)
{
maxy += (lengthmax - lengthy);
lengthy = maxy - miny;
}
if(lengthz < lengthmax)
{
maxz += (lengthmax - lengthz);
lengthz = maxz - minz;
}
//Create the first node (head)
struct node* head = NULL;
head = malloc(sizeof(struct node));
head->maxx = maxx;
head->maxy = maxy;
head->maxz = maxz;
head->minx = minx;
head->miny = miny;
head->minz = minz;
//Create the head (polylist and further nodes within it)
addNode(&head);
}
|
Add node function
| Code: |
void addNode(struct node** noderef)
{
int tempintersectlist[polylimit];
int temppolycount;
int n = 0;
//Check if poly vertices are within node max/min, and if yes add to intersect list (before testing
//where polygons intersect the node e.t.c., first checking how many polygons are in the node)
for(n = 0; n < polylimit; n++)
{
if((Level1Poly[n].vertex0[0] < *noderef->maxx)&&(Level1Poly[n].vertex0[0] > *noderef->minx))
{
if((Level1Poly[n].vertex0[1] < *noderef->maxy)&&(Level1Poly[n].vertex0[1] > *noderef->miny))
{
if((Level1Poly[n].vertex0[2] < *noderef->maxz)&&(Level1Poly[n].vertex[2] > *noderef->minz))
{
temppolycount++;
templist[n] = n;
}
}
}
else if((Level1Poly[n].vertex1[0] < *noderef->maxx)&&(Level1Poly[n].vertex1[0] > *noderef->minx))
{
if((Level1Poly[n].vertex1[1] < *noderef->maxy)&&(Level1Poly[n].vertex1[1] > *noderef->miny))
{
if((Level1Poly[n].vertex1[2] < *noderef->maxz)&&(Level1Poly[n].vertex[2] > *noderef->minz))
{
temppolycount++;
templist[n] = n;
}
}
}
else if((Level1Poly[n].vertex2[0] < *noderef->maxx)&&(Level1Poly[n].vertex2[0] > *noderef->minx))
{
if((Level1Poly[n].vertex2[1] < *noderef->maxy)&&(Level1Poly[n].vertex2[1] > *noderef->miny))
{
if((Level1Poly[n].vertex2[2] < *noderef->maxz)&&(Level1Poly[n].vertex[2] > *noderef->minz))
{
temppolycount++;
templist[n] = n;
}
}
}
}//End for
if(temppolycount > 10)
{
//Split node into a further 8 nodes
}
}
|
When compiling, I get the following error in my addNode function:
error: request for member 'maxx' in something not a structure or union
(around 18 times each time either maxx, maxy e.t.c. are called) Anybody able to take a look at my code and help me?