Basic level partitioning
Author
Hi there.
I wanted to divide up my levels into smaller groups of polygons to make the collision detection more efficient. I did some code to split the level into boxes and assign all the polys to the box that they collide with. Then after I position the player object I run a function that determines which box the object is in. From there I just use the min/max xyz of the current box and the player position to determine which box the player is in on each loop.
This all works well. The collision code works much faster as it is only colliding with the polygons in the current box. The problem is that when the collision sphere crosses the boundary of the current box the collision code operates on the polygons from the current box and the ones from the adjacent box or boxes depending on how many boxes the sphere intersects with. The maximum number of boxes to collide with is eight if there is more than one level of boxes which is where it all falls down. I realise that it will be a rare situation for a player to find the exact location where eight boxes can be intersected by the collision sphere but it does happen and it’s very slow.
So I thought I might set up a smaller box at these points and collide with the polys in it but that makes the whole process of determining the current box much slower.
Then I thought I might have levels of smaller and smaller boxes so that if there is an intersection with more than one box at a lower level I could go up a level and test again, repeating until I find a level where the collision sphere is contained in a single box. Then I realised that this is the same as colliding with polys from several boxes only with a bit more faffing about.
Can anyone give me any tips for improving this or perhaps tell me if I’m going about it all wrong. I don’t want to go bananas with partitioning but it needs to be better.
As usual I must apologise for the lengthy and slightly incoherent rambling.
elnebulso it sounds like you have a type of division but you missed the main point.
IT has to be a tree, where the Main Parent contains all the polygons in the world.
Thus you first test the main parent, if it is not inside the main parent it doesnt collide any boxes, otherwise if it is in the main parent it goes down a level with 8 smaller boxes.
So if you have a tree of depth 5 the process of finding the polygons for a point will be simple like this
lets see if i still have my uber elite source code:
And yes it does mean that the MainParent will have a list of all the polygons in the world. In Quake3 it means the the parent will have 12 000 boolens (simple true if it is in the child) and then on a rational map each of its children will have 12 000/8 booleans and so on.
It is left to note that thise can also be used for frustum culling and rather accurately
----------
This code is not mine, but a tutorial's
IT has to be a tree, where the Main Parent contains all the polygons in the world.
Thus you first test the main parent, if it is not inside the main parent it doesnt collide any boxes, otherwise if it is in the main parent it goes down a level with 8 smaller boxes.
So if you have a tree of depth 5 the process of finding the polygons for a point will be simple like this
Once it is found to be inside the parent traverse down the children, checking each child. MainParent /-------/----------/-------/----|------\----------\-------- Node Node Node Node Node Node Node Node[/Source]lets see if i still have my uber elite source code:
And yes it does mean that the MainParent will have a list of all the polygons in the world. In Quake3 it means the the parent will have 12 000 boolens (simple true if it is in the child) and then on a rational map each of its children will have 12 000/8 booleans and so on.
It is left to note that thise can also be used for frustum culling and rather accurately
----------
This code is not mine, but a tutorial's
[Source]///////////////////////////////// CREATE NEW NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*////////// This figures out the new node information and then passes it into CreateNode()////////////////////////////////////// CREATE NEW NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*void COctree::CreateNewNode(CVector3 *pVertices, vector<bool> pList, int numberOfVerts, CVector3 vCenter, float width, int triangleCount, int nodeID){ // This function helps us set up the new node that is being created. We only // want to create a new node if it found triangles in it's area. If there were // no triangle found in this node's cube, then we ignore it and don't create a node. // Check if the first node found some triangles in it if(triangleCount) { // Allocate memory for the triangles found in this node (tri's * 3 for vertices) CVector3 *pNodeVertices = new CVector3 [triangleCount * 3]; // Create an counter to count the current index of the new node vertices int index = 0; // Go through all the vertices and assign the vertices to the node's list for(int i = 0; i < numberOfVerts; i++) { // If this current triangle is in the node, assign it's vertices to it if(pList) <br> {<br> pNodeVertices[index] = pVertices<span style="font-weight:bold;">;<br> index++;<br> }<br> }<br><br> <span class="cpp-comment">// Now comes the initialization of the node. First we allocate memory for</span><br> <span class="cpp-comment">// our node and then get it's center point. Depending on the nodeID, </span><br> <span class="cpp-comment">// GetNewNodeCenter() knows which center point to pass back (TOP_LEFT_FRONT, etc..)</span><br><br> <span class="cpp-comment">// Allocate a new node for this octree</span><br> m_pOctreeNodes[nodeID] = <span class="cpp-keyword">new</span> COctree;<br><br> <span class="cpp-comment">// Get the new node's center point depending on the nodexIndex (which of the 8 subdivided cubes).</span><br> CVector3 vNodeCenter = GetNewNodeCenter(vCenter, width, nodeID);<br> <br> <span class="cpp-comment">// Below, before and after we recurse further down into the tree, we keep track</span><br> <span class="cpp-comment">// of the level of subdivision that we are in. This way we can restrict it.</span><br><br> <span class="cpp-comment">// Increase the current level of subdivision</span><br> g_CurrentSubdivision++;<br><br> <span class="cpp-comment">// Recurse through this node and subdivide it if necessary</span><br> m_pOctreeNodes[nodeID]->CreateNode(pNodeVertices, triangleCount * <span class="cpp-number">3</span>, vNodeCenter, width / <span class="cpp-number">2</span>);<br><br> <span class="cpp-comment">// Decrease the current level of subdivision</span><br> g_CurrentSubdivision–;<br><br> <span class="cpp-comment">// Free the allocated vertices for the triangles found in this node</span><br> <span class="cpp-keyword">delete</span> [] pNodeVertices;<br> }<br>}<br><br><br><span class="cpp-comment">///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*</span><br><span class="cpp-comment">/////</span><br><span class="cpp-comment">///// This is our recursive function that goes through and subdivides our nodes</span><br><span class="cpp-comment">/////</span><br><span class="cpp-comment">///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*</span><br><br><span class="cpp-keyword">void</span> COctree::CreateNode(CVector3 *pVertices, <span class="cpp-keyword">int</span> numberOfVerts, CVector3 vCenter, <span class="cpp-keyword">float</span> width)<br>{<br> <span class="cpp-comment">// This is our main function that creates the octree. We will recurse through</span><br> <span class="cpp-comment">// this function until we finish subdividing. Either this will be because we</span><br> <span class="cpp-comment">// subdivided too many levels or we divided all of the triangles up.</span><br><br> <span class="cpp-comment">// Create a variable to hold the number of triangles</span><br> <span class="cpp-keyword">int</span> numberOfTriangles = numberOfVerts / <span class="cpp-number">3</span>;<br><br> <span class="cpp-comment">// Initialize this node's center point. Now we know the center of this node.</span><br> m_vCenter = vCenter;<br><br> <span class="cpp-comment">// Initialize this nodes cube width. Now we know the width of this current node.</span><br> m_Width = width;<br><br> <span class="cpp-comment">// Add the current node to our debug rectangle list so we can visualize it.</span><br> <span class="cpp-comment">// We can now see this node visually as a cube when we render the rectangles.</span><br> <span class="cpp-comment">// Since it's a cube we pass in the width for width, height and depth.</span><br> g_Debug.AddDebugRectangle(vCenter, width, width, width);<br><br> <span class="cpp-comment">// Check if we have too many triangles in this node and we haven't subdivided</span><br> <span class="cpp-comment">// above our max subdivisions. If so, then we need to break this node into</span><br> <span class="cpp-comment">// 8 more nodes (hence the word OCTree). Both must be true to divide this node.</span><br> <span class="cpp-keyword">if</span>( (numberOfTriangles > g_MaxTriangles) && (g_CurrentSubdivision < g_MaxSubdivisions) )<br> {<br> <span class="cpp-comment">// Since we need to subdivide more we set the divided flag to true.</span><br> <span class="cpp-comment">// This let's us know that this node does NOT have any vertices assigned to it,</span><br> <span class="cpp-comment">// but nodes that perhaps have vertices stored in them (Or their nodes, etc….)</span><br> <span class="cpp-comment">// We will querey this variable when we are drawing the octree.</span><br> m_bSubDivided = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Create a list for each new node to store if a triangle should be stored in it's</span><br> <span class="cpp-comment">// triangle list. For each index it will be a true or false to tell us if that triangle</span><br> <span class="cpp-comment">// is in the cube of that node. Below we check every point to see where it's</span><br> <span class="cpp-comment">// position is from the center (I.E. if it's above the center, to the left and </span><br> <span class="cpp-comment">// back it's the TOP_LEFT_BACK node). Depending on the node we set the pList </span><br> <span class="cpp-comment">// index to true. This will tell us later which triangles go to which node.</span><br> <span class="cpp-comment">// You might catch that this way will produce doubles in some nodes. Some</span><br> <span class="cpp-comment">// triangles will intersect more than 1 node right? We won't split the triangles</span><br> <span class="cpp-comment">// in this tutorial just to keep it simple, but the next tutorial we will.</span><br><br> <span class="cpp-comment">// Create the list of booleans for each triangle index</span><br> vector<<span class="cpp-keyword">bool</span>> pList1(numberOfTriangles); <span class="cpp-comment">// TOP_LEFT_FRONT node list</span><br> vector<<span class="cpp-keyword">bool</span>> pList2(numberOfTriangles); <span class="cpp-comment">// TOP_LEFT_BACK node list</span><br> vector<<span class="cpp-keyword">bool</span>> pList3(numberOfTriangles); <span class="cpp-comment">// TOP_RIGHT_BACK node list</span><br> vector<<span class="cpp-keyword">bool</span>> pList4(numberOfTriangles); <span class="cpp-comment">// TOP_RIGHT_FRONT node list</span><br> vector<<span class="cpp-keyword">bool</span>> pList5(numberOfTriangles); <span class="cpp-comment">// BOTTOM_LEFT_FRONT node list</span><br> vector<<span class="cpp-keyword">bool</span>> pList6(numberOfTriangles); <span class="cpp-comment">// BOTTOM_LEFT_BACK node list</span><br> vector<<span class="cpp-keyword">bool</span>> pList7(numberOfTriangles); <span class="cpp-comment">// BOTTOM_RIGHT_BACK node list</span><br> vector<<span class="cpp-keyword">bool</span>> pList8(numberOfTriangles); <span class="cpp-comment">// BOTTOM_RIGHT_FRONT node list</span><br> <br> <span class="cpp-comment">// Create this variable to cut down the thickness of the code below (easier to read)</span><br> CVector3 vCtr = vCenter;<br><br> <span class="cpp-comment">// Go through all of the vertices and check which node they belong too. The way</span><br> <span class="cpp-comment">// we do this is use the center of our current node and check where the point</span><br> <span class="cpp-comment">// lies in relationship to the center. For instance, if the point is </span><br> <span class="cpp-comment">// above, left and back from the center point it's the TOP_LEFT_BACK node.</span><br> <span class="cpp-comment">// You'll see we divide by 3 because there are 3 points in a triangle.</span><br> <span class="cpp-comment">// If the vertex index 0 and 1 are in a node, 0 / 3 and 1 / 3 is 0 so it will</span><br> <span class="cpp-comment">// just set the 0'th index to TRUE twice, which doesn't hurt anything. When</span><br> <span class="cpp-comment">// we get to the 3rd vertex index of pVertices[] it will then be checking the</span><br> <span class="cpp-comment">// 1st index of the pList*[] array. We do this because we want a list of the</span><br> <span class="cpp-comment">// triangles in the node, not the vertices.</span><br> <span class="cpp-keyword">for</span>(<span class="cpp-keyword">int</span> i = <span class="cpp-number">0</span>; i < numberOfVerts; i++)<br> {<br> <span class="cpp-comment">// Create some variables to cut down the thickness of the code (easier to read)</span><br> CVector3 vPoint = pVertices<span style="font-weight:bold;">;<br><br> <span class="cpp-comment">// Check if the point lines within the TOP LEFT FRONT node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z) ) <br> pList1 = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Check if the point lines within the TOP LEFT BACK node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z) ) <br> pList2 = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Check if the point lines within the TOP RIGHT BACK node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z) ) <br> pList3 = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Check if the point lines within the TOP RIGHT FRONT node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z) ) <br> pList4 = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Check if the point lines within the BOTTOM LEFT FRONT node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z) ) <br> pList5 = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Check if the point lines within the BOTTOM LEFT BACK node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z) ) <br> pList6 = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Check if the point lines within the BOTTOM RIGHT BACK node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z) ) <br> pList7 = <span class="cpp-keyword">true</span>;<br><br> <span class="cpp-comment">// Check if the point lines within the BOTTOM RIGHT FRONT node</span><br> <span class="cpp-keyword">if</span>( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z) ) <br> pList8 = <span class="cpp-keyword">true</span>;<br> } <br><br> <span class="cpp-comment">// Here we create a variable for each list that holds how many triangles</span><br> <span class="cpp-comment">// were found for each of the 8 subdivided nodes.</span><br> <span class="cpp-keyword">int</span> triCount1 = <span class="cpp-number">0</span>; <span class="cpp-keyword">int</span> triCount2 = <span class="cpp-number">0</span>; <span class="cpp-keyword">int</span> triCount3 = <span class="cpp-number">0</span>; <span class="cpp-keyword">int</span> triCount4 = <span class="cpp-number">0</span>;<br> <span class="cpp-keyword">int</span> triCount5 = <span class="cpp-number">0</span>; <span class="cpp-keyword">int</span> triCount6 = <span class="cpp-number">0</span>; <span class="cpp-keyword">int</span> triCount7 = <span class="cpp-number">0</span>; <span class="cpp-keyword">int</span> triCount8 = <span class="cpp-number">0</span>;<br> <br> <span class="cpp-comment">// Go through each of the lists and increase the triangle count for each node.</span><br> <span class="cpp-keyword">for</span>(i = <span class="cpp-number">0</span>; i < numberOfTriangles; i++) <br> {<br> <span class="cpp-comment">// Increase the triangle count for each node that has a "true" for the index i.</span><br> <span class="cpp-keyword">if</span>(pList1<span style="font-weight:bold;">) triCount1++; <span class="cpp-keyword">if</span>(pList2<span style="font-weight:bold;">) triCount2++;<br> <span class="cpp-keyword">if</span>(pList3<span style="font-weight:bold;">) triCount3++; <span class="cpp-keyword">if</span>(pList4<span style="font-weight:bold;">) triCount4++;<br> <span class="cpp-keyword">if</span>(pList5<span style="font-weight:bold;">) triCount5++; <span class="cpp-keyword">if</span>(pList6<span style="font-weight:bold;">) triCount6++;<br> <span class="cpp-keyword">if</span>(pList7<span style="font-weight:bold;">) triCount7++; <span class="cpp-keyword">if</span>(pList8<span style="font-weight:bold;">) triCount8++;<br> }<br> <br> <span class="cpp-comment">// Next we do the dirty work. We need to set up the new nodes with the triangles</span><br> <span class="cpp-comment">// that are assigned to each node, along with the new center point of the node.</span><br> <span class="cpp-comment">// Through recursion we subdivide this node into 8 more nodes.</span><br><br> <span class="cpp-comment">// Create the subdivided nodes if necessary and then recurse through them.</span><br> <span class="cpp-comment">// The information passed into CreateNewNode() are essential for creating the</span><br> <span class="cpp-comment">// new nodes. We pass the 8 ID's in so it knows how to calculate it's new center.</span><br> CreateNewNode(pVertices, pList1, numberOfVerts, vCenter, width, triCount1, TOP_LEFT_FRONT);<br> CreateNewNode(pVertices, pList2, numberOfVerts, vCenter, width, triCount2, TOP_LEFT_BACK);<br> CreateNewNode(pVertices, pList3, numberOfVerts, vCenter, width, triCount3, TOP_RIGHT_BACK);<br> CreateNewNode(pVertices, pList4, numberOfVerts, vCenter, width, triCount4, TOP_RIGHT_FRONT);<br> CreateNewNode(pVertices, pList5, numberOfVerts, vCenter, width, triCount5, BOTTOM_LEFT_FRONT);<br> CreateNewNode(pVertices, pList6, numberOfVerts, vCenter, width, triCount6, BOTTOM_LEFT_BACK);<br> CreateNewNode(pVertices, pList7, numberOfVerts, vCenter, width, triCount7, BOTTOM_RIGHT_BACK);<br> CreateNewNode(pVertices, pList8, numberOfVerts, vCenter, width, triCount8, BOTTOM_RIGHT_FRONT);<br> }<br> <span class="cpp-keyword">else</span><br> {<br> <span class="cpp-comment">// If we get here we must either be subdivided past our max level, or our triangle</span><br> <span class="cpp-comment">// count went below the minimum amount of triangles so we need to store them.</span><br> <br> <span class="cpp-comment">// Assign the vertices to this node since we reached the end node.</span><br> <span class="cpp-comment">// This will be the end node that actually gets called to be drawn.</span><br> <span class="cpp-comment">// We just pass in the vertices and vertex count to be assigned to this node.</span><br> AssignVerticesToNode(pVertices, numberOfVerts);<br> }<br>}<br><br><br><span class="cpp-comment">//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\*</span><br><span class="cpp-comment">/////</span><br><span class="cpp-comment">///// This allocates memory for the vertices to assign to the current end node</span><br><span class="cpp-comment">/////</span><br><span class="cpp-comment">//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\*</span><br><br><span class="cpp-keyword">void</span> COctree::AssignVerticesToNode(CVector3 *pVertices, <span class="cpp-keyword">int</span> numberOfVerts)<br>{<br> <span class="cpp-comment">// Since we did not subdivide this node we want to set our flag to false</span><br> m_bSubDivided = <span class="cpp-keyword">false</span>;<br><br> <span class="cpp-comment">// Initialize the triangle count of this end node (total verts / 3 = total triangles)</span><br> m_TriangleCount = numberOfVerts / <span class="cpp-number">3</span>;<br><br> <span class="cpp-comment">// Allocate enough memory to hold the needed vertices for the triangles</span><br> m_pVertices = <span class="cpp-keyword">new</span> CVector3 [numberOfVerts];<br><br> <span class="cpp-comment">// Initialize the vertices to 0 before we copy the data over to them</span><br> memset(m_pVertices, <span class="cpp-number">0</span>, <span class="cpp-keyword">sizeof</span>(CVector3) * numberOfVerts);<br><br> <span class="cpp-comment">// Copy the passed in vertex data over to our node vertice data</span><br> memcpy(m_pVertices, pVertices, <span class="cpp-keyword">sizeof</span>(CVector3) * numberOfVerts);<br><br> <span class="cpp-comment">// Increase the amount of end nodes created (Nodes with vertices stored)</span><br> g_EndNodeCount++;<br>}<br><br></pre></div><!–ENDSCRIPT–>
Author
Thanks for all that info mate.
I think what I have done so far will be quite easy to develop into the type of system you are describing.
Plenty of work to do this weekend by the look of it.
Thanks again for the help.
I think what I have done so far will be quite easy to develop into the type of system you are describing.
Plenty of work to do this weekend by the look of it.
Thanks again for the help.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
