I can’t get my octree work right. The triangles seem to increase as I subdivide more OR I tend to go into infinite regress in creating new octrees and not subdividing my vertex data. It sounds simple but it is not and I can not figure out why this happens.
What I mean by triangles increasing, I get more triangles in my subnodes altogether than I have initially in my map.
My code used to be clean and tidy, but now it is dirty as hell and this is the most working attempt I have yet to come up.
If you have time, please take short look at my code.
abstract class Node implements NodeEnum{
protected Vector3f center = new Vector3f(0f, 0f, 0f);
protected float width = 0;
protected int vertices, triangles;
protected Vector3f[] nodeVertices;
protected boolean subDivided = false;
protected boolean[] list0;
protected boolean[] list1;
protected boolean[] list2;
protected boolean[] list3;
protected boolean[] list4;
protected boolean[] list5;
protected boolean[] list6;
protected boolean[] list7;
public Node(Vector3f[] data){
setDimensions(data);
vertices = data.length;
triangles = (int)Math.ceil(data.length/3);
System.out.println("TOTAL MAX TRIANGLES: " + triangles);
System.out.println("VERTICES: " + vertices);
}
public Node(int vertexCount, Vector3f m_center, float m_width){
vertices = vertexCount;
triangles = vertexCount/3;
System.out.println("SUBNODE TRIANGLES:" + triangles);
System.out.println("SUBNODE VERTICES:" + vertices);
}
abstract void draw();
public void setDimensions(Vector3f[] mVertexData){
int mVertexCount = mVertexData.length;
// Initialize some temporary variables to hold the max dimensions found
float maxWidth = 0, maxHeight = 0, maxDepth = 0;
// Go through all of the vertices and add them up to eventually find the center
for(int i = 0; i < mVertexCount; i++)
{
// Add the current vertex to the center variable
Vector3f.add(center, mVertexData[i], center);
}
// Divide the total by the number of vertices to get the center point.
// We could have overloaded the / symbol but I chose not to because we rarely use it.
center.x /= mVertexCount;
center.y /= mVertexCount;
center.z /= mVertexCount;
// Now that we have the center point, we want to find the farthest distance from
// our center point. That will tell us how big the width of the first node is.
// Once we get the farthest height, width and depth, we then check them against each
// other. Which ever one is higher, we then use that value for the cube width.
// Go through all of the vertices and find the max dimensions
for(int i = 0; i < mVertexCount; i++){
// Get the current dimensions for this vertex. We use the abs() function
// to get the absolute value because it might return a negative number.
float currentWidth = Math.abs(mVertexData[i].x - center.x);
float currentHeight = Math.abs(mVertexData[i].y - center.y);
float currentDepth = Math.abs(mVertexData[i].z - center.z);
// Check if the current width value is greater than the max width stored.
if(currentWidth > maxWidth) maxWidth = currentWidth;
// Check if the current height value is greater than the max height stored.
if(currentHeight > maxHeight) maxHeight = currentHeight;
// Check if the current depth value is greater than the max depth stored.
if(currentDepth > maxDepth) maxDepth = currentDepth;
}
// Set the member variable dimensions to the max ones found.
// We multiply the max dimensions by 2 because this will give us the
// full width, height and depth. Otherwise, we just have half the size
// because we are calculating from the center of the scene.
maxWidth *= 2; maxHeight *= 2; maxDepth *= 2;
// Check if the width is the highest value and assign that for the cube dimension
if(maxWidth > maxHeight && maxWidth > maxDepth)
width = maxWidth;
// Check if the height is the heighest value and assign that for the cube dimension
else if(maxHeight > maxWidth && maxHeight > maxDepth)
width = maxHeight;
// Else it must be the depth or it's the same value as some of the other ones
else
width = maxDepth;
}
protected final void assignVerticesToNode(Vector3f[] data){
subDivided=false;
System.out.println("LOLOLOL OMG WTF VERTICES ASSIGNED LOLOLOL");
nodeVertices = new Vector3f[vertices];
nodeVertices = data;
}
}
This is where all the important stuff happens:
public final class OctreeNode extends Node {
public static int currentSubdivision = 0;
private OctreeNode[] subNode;
public OctreeNode(Vector3f[] data){
super(data);
if(triangles > MAX_TRIANGLES && currentSubdivision <= MAX_SUB_DIVISIONS){
subDivide(data);
} else {
assignVerticesToNode(data);
}
}
public OctreeNode(Vector3f[] data, Vector3f m_center, float m_width ){
super(data.length, m_center, m_width);
System.out.println("NEW SUBNODE CREATED");
if(triangles > MAX_TRIANGLES && currentSubdivision <= MAX_SUB_DIVISIONS){
subDivide(data);
} else {
assignVerticesToNode(data);
}
}
public void draw(){
}
private void subDivide(Vector3f[] data){
subDivided= true;
subNode = new OctreeNode[7];
//System.out.println("fagot");
list0 = new boolean[triangles];
list1 = new boolean[triangles];
list2 = new boolean[triangles];
list3 = new boolean[triangles];
list4 = new boolean[triangles];
list5 = new boolean[triangles];
list6 = new boolean[triangles];
list7 = new boolean[triangles];
for(int i = 0; i < vertices; i++)
{
// Create some variables to cut down the thickness of the code (easier to read)
Vector3f point = data[i];
// Check if the point lines within the TOP LEFT FRONT node
if( (point.x <= center.x) && (point.y >= center.y) && (point.z >= center.z) )
list0[i / 3] = true;
// Check if the point lines within the TOP LEFT BACK node
if( (point.x <= center.x) && (point.y >= center.y) && (point.z <= center.z) )
list1[i / 3] = true;
// Check if the point lines within the TOP RIGHT BACK node
if( (point.x >= center.x) && (point.y >= center.y) && (point.z <= center.z) )
list2[i / 3] = true;
// Check if the point lines within the TOP RIGHT FRONT node
if( (point.x >= center.x) && (point.y >= center.y) && (point.z >= center.z) )
list3[i / 3] = true;
// Check if the point lines within the BOTTOM LEFT FRONT node
if( (point.x <= center.x) && (point.y <= center.y) && (point.z >= center.z) )
list4[i / 3] = true;
// Check if the point lines within the BOTTOM LEFT BACK node
if( (point.x <= center.x) && (point.y <= center.y) && (point.z <= center.z) )
list5[i / 3] = true;
// Check if the point lines within the BOTTOM RIGHT BACK node
if( (point.x >= center.x) && (point.y <= center.y) && (point.z <= center.z) )
list6[i / 3] = true;
// Check if the point lines within the BOTTOM RIGHT FRONT node
if( (point.x >= center.x) && (point.y <= center.y) && (point.z >= center.z) )
list7[i / 3] = true;
}
int triCount0 = 0; int triCount1 = 0; int triCount2 = 0; int triCount3 = 0;
int triCount4 = 0; int triCount5 = 0; int triCount6 = 0; int triCount7 = 0;
// Go through each of the lists and increase the triangle count for each node.
for(int i = 0; i < triangles; i++) {
// Increase the triangle count for each node that has a "true" for the index i.
if(list0[i]) triCount0++; if(list1[i]) triCount1++;
if(list2[i]) triCount2++; if(list3[i]) triCount3++;
if(list4[i]) triCount4++; if(list5[i]) triCount5++;
if(list6[i]) triCount6++; if(list7[i]) triCount7++;
}
currentSubdivision++;
//Create new nodes according to the boolean lists and triangle count
createNewNode(data, list0, triCount0, TOP_LEFT_FRONT);
createNewNode(data, list1, triCount1, TOP_LEFT_BACK);
createNewNode(data, list2, triCount2, TOP_RIGHT_BACK);
createNewNode(data, list3, triCount3, TOP_RIGHT_FRONT);
createNewNode(data, list4, triCount4, BOTTOM_LEFT_FRONT);
createNewNode(data, list5, triCount5, BOTTOM_LEFT_BACK);
createNewNode(data, list6, triCount6, BOTTOM_RIGHT_BACK);
createNewNode(data, list7, triCount7, BOTTOM_RIGHT_FRONT);
System.out.println("CURRENT SUBDIVISION: " + currentSubdivision);
}
public void processVertices(Vector3f[] v){
if(triangles < MAX_TRIANGLES);
}
public void createNewNode(Vector3f[] data, boolean[] list, int triCount, int nodeID){
if(triCount >0){
System.out.println("tricount:" +triCount);
// Create an counter to count the current index of the new node vertices
int index = 0;
Vector3f[] newNodeVertices = new Vector3f[triCount * 3];
// Go through all the vertices and assign the vertices to the node's list
for(int i = 0; i < vertices; i++)
{
// If this current triangle is in the node, assign it's vertices to it
if(list[i / 3])
{
newNodeVertices[index] = data[i];
index++;
}
}
Vector3f nodeCenter = getNewNodeCenter(nodeID);
subNode[nodeID] = new OctreeNode(newNodeVertices, nodeCenter, width / 2);
}
}
}
The nodeEnum contains the position enum and max triangles and max subdivsions + max subnodes.
This is roughly based on the octree.cpp from gametutorials.com, but I can’t figure out good way to start porting it due the fact that it uses really worthless oop(or well, some c++ people might say good).
