dispersing vertices in octree...
Author
Hey all, I'm attempting to split one large vertex array into several (8, really) smaller arrays for the purpose of an octree. (Each node contains a vertex array.)
Anyway, before I continue on with a horrible bug -- When I make my mesh 100x100 verts (leaving the Y axis at 0), there are 10,000 vertices. Simple enough.
However, when I'm assigning where each of those vertices need to go where, I end up with 2500 vertices in EACH of the 8 octree node vertex arrays...giving me twice as many vertices as the original 10K. I'm assuming that each time I run through the vertex assigning, it's going to double the total each time. So if I split the sucker 4 times, I'm going to have 160,000 vertices. What on earth is going on here? Is this something that I hadn't realized would happen, or a bug in my stuff? Any tips?
Thanks
EDIT: made a bit clearer
[edited by - ichor on April 13, 2004 1:56:25 AM]
Obviously you''re not writing the splitter correctly. If I understand you correctly, here''s what you want to do:
You have 10000 verices in three dimensions (such as a large model), which you want to split up by assigning each of the vertices to its respective boundary box, there being 8 of those ditributed evenly. Projected to two dimensions, it would look something like this, right?
What you''ve done, is you''ve created an octree to contain these eight cubicles (which IMO is overkill) - all you need to do is define eight boxes (since you''re not going to divide this thing dynamically any further), such as: StructBox[8]. In a sentence: you don''t need an octree here.
Then, all you need to do, is test each vertex agains each box until you find a match and store it there.
My guess as to what you''re doing wrong right now is something along the lines of not only storing vertex handles in the leaf nodes, but also each parent node.
What precisely is amiss, no one can tell, lest you post some code.
Hope this helps.
You have 10000 verices in three dimensions (such as a large model), which you want to split up by assigning each of the vertices to its respective boundary box, there being 8 of those ditributed evenly. Projected to two dimensions, it would look something like this, right?
______ ______| | || | ||______|______|| | || | ||______|______|What you''ve done, is you''ve created an octree to contain these eight cubicles (which IMO is overkill) - all you need to do is define eight boxes (since you''re not going to divide this thing dynamically any further), such as: StructBox[8]. In a sentence: you don''t need an octree here.
Then, all you need to do, is test each vertex agains each box until you find a match and store it there.
My guess as to what you''re doing wrong right now is something along the lines of not only storing vertex handles in the leaf nodes, but also each parent node.
What precisely is amiss, no one can tell, lest you post some code.
Hope this helps.
TCP - Transmission by Carrier Pigeons
Author
Well, here's what's happening down the line of creating and splitting nodes:
1. A vertex array is created. (This is what's being pushed into the octree.)
2. The main file calls octree.createNode();
createNode() is quite large, so I'll summarize here:
1. I calculate the minBounds, maxBounds, centerPoint, and longest side of the vertex array.
2. If the number of vertices in the vertex array is greater than the preset number of vertices, it needs to get split up. (hasChildren=true; )
3. I initialize an 8 element array of VertexArrays, one for each possible node that I'm splitting.
I should also say that each Octree contains:
Octree *octreeNodes[8];
All right, from there, I go through a series of checks like this:
After it gets through each of those if's, it allocates memory for the vertexarrays that each octree node has. (Which, if it's a 100x100 x,z axis array, it ends up 2500 in EACH array.)
Then, it goes through the same loop and if statements and assigns vertices from the main vertex array to each of the temp vertex arrays. I realize that having 2 loops go through each vertex may not be the most efficient, but once it works I'll figure out something better...maybe.
Anyway, so after that, I have 8 vertex arrays (local to the function) fill with vertices from the original VA.
Then I run another if check to see if the numberOfVerts in each temporary array greater than the preset amount. If so, I split the nodes. If not, I assign nodeVertexArray = tempVertArray[#].
Finally, in the splitNode() function, pretty much all that is taking place is creating the 8 new nodes:
And afterwards, I call the createNode() function again:
And that's it. I'm almost positive something is wrong with the splitNode() calling createNode(), 'cause if I run it in debug mode, I run out of stack space...so something isn't dividing right.
Would any specific code be useful to determine where the heck I went wrong?
I guess the bright side of all of this...if I don't have to split nodes, my renderOctree() function works flawlessly. =)
Sorry for the long post...
EDIT: fixed code formatting
[edited by - ichor on April 13, 2004 2:57:14 PM]
1. A vertex array is created. (This is what's being pushed into the octree.)
2. The main file calls octree.createNode();
createNode() is quite large, so I'll summarize here:
1. I calculate the minBounds, maxBounds, centerPoint, and longest side of the vertex array.
2. If the number of vertices in the vertex array is greater than the preset number of vertices, it needs to get split up. (hasChildren=true; )
3. I initialize an 8 element array of VertexArrays, one for each possible node that I'm splitting.
I should also say that each Octree contains:
Octree *octreeNodes[8];
All right, from there, I go through a series of checks like this:
//UPPER LEFT NODE if ( (vertArray.verts[mem].vx <= nodeCenter.x) && (vertArray.verts[mem].vy >= nodeCenter.y) && (vertArray.verts[mem].vz >= nodeCenter.z)){ After it gets through each of those if's, it allocates memory for the vertexarrays that each octree node has. (Which, if it's a 100x100 x,z axis array, it ends up 2500 in EACH array.)
Then, it goes through the same loop and if statements and assigns vertices from the main vertex array to each of the temp vertex arrays. I realize that having 2 loops go through each vertex may not be the most efficient, but once it works I'll figure out something better...maybe.
Anyway, so after that, I have 8 vertex arrays (local to the function) fill with vertices from the original VA.
Then I run another if check to see if the numberOfVerts in each temporary array greater than the preset amount. If so, I split the nodes. If not, I assign nodeVertexArray = tempVertArray[#].
Finally, in the splitNode() function, pretty much all that is taking place is creating the 8 new nodes:
octreeNodes[nodeID] = new Octree; And afterwards, I call the createNode() function again:
octreeNodes[nodeID]->createNode(verts, center, nodeID); And that's it. I'm almost positive something is wrong with the splitNode() calling createNode(), 'cause if I run it in debug mode, I run out of stack space...so something isn't dividing right.
Would any specific code be useful to determine where the heck I went wrong?
I guess the bright side of all of this...if I don't have to split nodes, my renderOctree() function works flawlessly. =)
Sorry for the long post...
EDIT: fixed code formatting
[edited by - ichor on April 13, 2004 2:57:14 PM]
Author
I might have figured it out, but at the same time, it might cause more problems also.
My existing code checked the upper 4 nodes (upper front/back/left/right) with:
This seems fine -- it''s logically correct (as far as I can tell.) However, my code to check the lower 4 nodes of the octree was:
So, if it''s not immediately obvious... I had said earlier that all my Y axis values are 0. Both my top and bottom nodes check for less than/greater than OR EQUAL TO. Thusly, the vertex on the Y axis was ALWAYS equal to 0, which was also the center of the mesh ((0+0)/2), so they all went into the upper AND lowernodes.
Anyway, I removed the "or equal to" operators from the lower nodes, and now when I split ''em up, I get 2500 nodes in each of the upper nodes... still not sure if it''s working, since that''s a perfect distribution of 10K vertices, and I really wasn''t expecting that, so I''ll keeping looking into it.
Does it sound like my main problem is fixed? Is a perfect distribution a coincidence...or supposed to happen...or something still screwy over here?
My existing code checked the upper 4 nodes (upper front/back/left/right) with:
if ( (vertArray.verts[mem].vx <= nodeCenter.x) && (vertArray.verts[mem].vy >= nodeCenter.y) && (vertArray.verts[mem].vz >= nodeCenter.z)) This seems fine -- it''s logically correct (as far as I can tell.) However, my code to check the lower 4 nodes of the octree was:
if ( (vertArray.verts[mem].vx <= nodeCenter.getX()) && (vertArray.verts[mem].vy <= nodeCenter.getY()) && (vertArray.verts[mem].vz >= nodeCenter.getZ())) So, if it''s not immediately obvious... I had said earlier that all my Y axis values are 0. Both my top and bottom nodes check for less than/greater than OR EQUAL TO. Thusly, the vertex on the Y axis was ALWAYS equal to 0, which was also the center of the mesh ((0+0)/2), so they all went into the upper AND lowernodes.
Anyway, I removed the "or equal to" operators from the lower nodes, and now when I split ''em up, I get 2500 nodes in each of the upper nodes... still not sure if it''s working, since that''s a perfect distribution of 10K vertices, and I really wasn''t expecting that, so I''ll keeping looking into it.
Does it sound like my main problem is fixed? Is a perfect distribution a coincidence...or supposed to happen...or something still screwy over here?
Depends on your data. If your data describes something symmetrical like a grid or a circle, then yes, it should come out even or very close to even.
If your data is something less predictable like a quake-style level of an abandoned warehouse, or a 3d model of a pig, then no, it isn''t likely to be so uniform, that''s pretty suspect.
If your data is something less predictable like a quake-style level of an abandoned warehouse, or a 3d model of a pig, then no, it isn''t likely to be so uniform, that''s pretty suspect.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
