Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Octree problem  (Read 5481 times) 0 Members and 1 Guest are viewing this topic.
Captain-Goatse

Junior Devvie

I suck at teh 2D. XBOX IS BIG LOL!111

 « Posted 2003-02-11 16:07:26 »

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.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107 `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:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154 `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).
princec

« JGO Spiffy Duke »

Medals: 1012
Projects: 3
Exp: 20 years

Eh? Who? What? ... Me?

 « Reply #1 - Posted 2003-02-11 20:39:03 »

I've got a working octree in java at http://sourceforge.net/projects/spgl (com.powersolve.jglib.geometry.storage.OctTree)

Have a look at that.

It doesn't split polys if they cross childnode boundaries though; it shoves them up at the top (so my octree has in effect 8 leaves plus a list of polys which didn't fit). This isn't particularly optimal. Nor is it the fastest way to build it but it was only for an experiment.

Cas

Captain-Goatse

Junior Devvie

I suck at teh 2D. XBOX IS BIG LOL!111

 « Reply #2 - Posted 2003-02-12 04:59:28 »

I'll take a look at that. Thanks.

I hate when I have everything clear on paper and when I turn it into code it funks up.

I bet the mistake is very trivial....
Captain-Goatse

Junior Devvie

I suck at teh 2D. XBOX IS BIG LOL!111

 « Reply #3 - Posted 2003-02-12 12:13:17 »

I still can't get it right... Looks like the problem is with recursion. I swiched to quadtree for simplicity purposes and I end up having most of the data divided into two very small nodes.
debug out put:
LeafNode created: 20038.787, 20038.787, -40.12438 Width: 10.4375 VERTEXCOUNT: 20046

and I have set my max triangle count to be 2000, if over 2000 triangles, it should subdivide, but even if take I set my max subdivision to 50 the width gets smaller and smaller but the thing still holds as many vertices as before.

LeafNode created: 20033.568, 20033.568, -40.12438 Width: 2.82909E-19 VERTEXCOUNT: 20034

This is how I start my QuadTree
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 `            if(nodeTriangles > QuadTree.MAX_TRIANGLES && subDivisionLevel < QuadTree.MAX_SUBDIVISION){                  //Subdivide!!!                  subDivisionLevel++;                  System.out.println("SUBDIVISIONLEVEL: " + subDivisionLevel);                  this.subDivide(verticeData);                              subDivisionLevel--;                                                } else{                  //This is leaf node!!!                  this.makeLeafNode(verticeData);                              }            `

Now here is where I think the problem is, but I can't find it:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67 `      private final void subDivide(Vector3f[] vertexData){            nodeIsSubDivided = true;                        boolean[] list0 = new boolean[nodeTriangles];            boolean[] list1 = new boolean[nodeTriangles];            boolean[] list2 = new boolean[nodeTriangles];            boolean[] list3 = new boolean[nodeTriangles];            //Create list of vertices in quads            for(int i = 0; i=nodeCenter.y){                        list0[i/3]=true;                  } else if(checkPoint.x >=nodeCenter.x && checkPoint.y >=nodeCenter.y){                        list1[i/3]=true;                  } else if(checkPoint.x <=nodeCenter.x && checkPoint.y <=nodeCenter.y){                        list2[i/3]=true;                  } else if(checkPoint.x >=nodeCenter.x && checkPoint.y <=nodeCenter.y){                        list3[i/3]=true;                                                            }            }                        //Divide vertices into smaller quads                        // Here we create a variable for each list that holds how many triangles            // were found for each of the 8 subdivided nodes.            int triCount0 = 0; int triCount1 = 0;      int triCount2 = 0;      int triCount3 = 0;                                    // Go through each of the lists and increase the triangle count for each node.            for(int i = 0; i < nodeTriangles; 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(triCount0 > 0){                  subNode0 = createNewSubNode(vertexData, list0, triCount0, nodeCenter, nodeWidth, TOP_LEFT);            } else {                  subNode0 = null;                                    }                        if(triCount1 > 0){                  subNode1 = createNewSubNode(vertexData, list1, triCount1, nodeCenter, nodeWidth, TOP_RIGHT);            } else {                  subNode1 = null;                                    }                        if(triCount2 > 0){                  subNode2 = createNewSubNode(vertexData, list2, triCount2, nodeCenter, nodeWidth, BOTTOM_LEFT);            } else {                  subNode2 = null;                                    }                                                if(triCount3 > 0){                  subNode3 = createNewSubNode(vertexData, list3, triCount3, nodeCenter, nodeWidth, BOTTOM_RIGHT);            } else {                  subNode3 = null;                                    }                              }`

and this is how I derive my vectorData

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19 `      private Vector3f[] getVertexData(Vector3f[] vertexData, boolean[] list, int triCount){            Vector3f[] newVertexData = new Vector3f[triCount*3];                        int index = 0;            // Go through all the vertices and assign the vertices to the node's list            for(int i = 0; i < nodeVertices; i++)            {                  // If this current triangle is in the node, assign it's vertices to it                  if(list[i / 3])                        {                        newVertexData[index] = vertexData[i];                        index++;                  }            }                                    return newVertexData;      }`
Captain-Goatse

Junior Devvie

I suck at teh 2D. XBOX IS BIG LOL!111

 « Reply #4 - Posted 2003-02-12 13:05:26 »

This is getting really strange... My quadtree only uses TOP_RIGHT and BOTTOM_LEFT nodes, which would mean that the map is cut in the middle, umm no?.
EgonOlsen
 « Reply #5 - Posted 2003-02-12 16:04:42 »

Where is the code for createNewSubNode()? Am i blind or is it missing? Maybe it would be helpfull to see this too. Looking at your code and your debug-output (smaller nodes but still the same number of triangles (almost))...my first guess is, that you are ignoring the width of the node somehow. At least you are just checking if a vertex is placed left/right and before/behind the node's center but not if it fits within the node's boundarys.
BTW.: I feel your pain. Did my own octree implementation yesterday and was on a bug-hunt for about 6 hours...just to realize that there wasn't any. I was just building a tree (holding indices into a polygon array) and then i was re-ordering the mesh for triangle-strips, so that the polygon indices changed. Don't do this...

Captain-Goatse

Junior Devvie

I suck at teh 2D. XBOX IS BIG LOL!111

 « Reply #6 - Posted 2003-02-12 16:59:55 »

Sorry for omiting it... here it is anyhow...

the center is pretty easy, it just take the center and the width of the parent and then makes new center according to ID.. the getVertexData is up there...

 1  2  3  4  5  6 `      private QuadTreeNode createNewSubNode(Vector3f[] vertexData, boolean[] list, int triCount, Vector3f parentCenter, float parentWidth, int nodeID){            if(triCount == 0) return null;            QuadTreeNode newQuadNode;            newQuadNode = new QuadTreeNode(getVertexData(vertexData, list, triCount), getNewCenter(nodeID), parentWidth/2);                                                               return newQuadNode;                                                         }`

The problem is that it doesn't even draw. It recurses now somewhat decently, except that everything is wrong.

EgonOlsen: May I ask how do you divide the vertex data for each node. In my approach the fault must be in that part.

If you'd like to take look at my code it is up on my hosting at http://suicidesolutions.com/FistfulOfSteel-LWGL.zip

EgonOlsen
 « Reply #7 - Posted 2003-02-12 19:13:19 »

Your zip-file seems to be corrupted....
Here is the recursive part of my tree. It basically starts with createChildren(rootNode) and recurses till it's done.
Note that i'm expanding the nodes if needed to make the polygons fit without splitting or maintaining an additional "doesn't-fit-list". Anyway, here you go (ignore the german comments):

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152 `    private boolean createChildren(OcTreeNode of) {        nodes++;        Vector tris=new Vector();        if (of!=null) {            for (int i=0; imaxPoly) {                         break;                     }                 }            }            // Wir haben geschaut, wieviele Polygon in diesen Knoten passen würden...            if (tris.size()<=maxPoly) {                // ok, alle Polys passen super in den Knoten...                //System.out.println("Filling node: "+of.getID()+" with "+tris.size()+" polygons!");                if (tris.size()!=0) {                    for (int ii=0; ii

Captain-Goatse

Junior Devvie

I suck at teh 2D. XBOX IS BIG LOL!111

 « Reply #8 - Posted 2003-02-13 08:48:36 »

Thanks for sharing, not much of use for me, you are using very different algorithm... I'll reupload the zip file...

This is in really bad place  since I'm leaving tomorrow for family vacation with my sister and I can't take my computer with me.

Well I got plenty of time there to figure out some method which will work 100% when implemented.
Pages: [1]
 ignore  |  Print

 ivj94 (583 views) 2018-03-24 14:47:39 ivj94 (48 views) 2018-03-24 14:46:31 ivj94 (374 views) 2018-03-24 14:43:53 Solater (61 views) 2018-03-17 05:04:08 nelsongames (109 views) 2018-03-05 17:56:34 Gornova (151 views) 2018-03-02 22:15:33 buddyBro (693 views) 2018-02-28 16:59:18 buddyBro (92 views) 2018-02-28 16:45:17 xxMrPHDxx (493 views) 2017-12-31 17:17:51 xxMrPHDxx (733 views) 2017-12-31 17:15:51
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org