Jump to content
  • Advertisement
Sign in to follow this  

Basic level partitioning

This topic is 4861 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post

Link to post
Share on other sites
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

Once it is found to be inside the parent traverse down the children, checking each child.
/-------/----------/-------/----|------\----------\-------- Node Node Node Node Node Node Node Node


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
///////////////////////////////// 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
// 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[i / 3])
pNodeVertices[index] = pVertices;

// Now comes the initialization of the node. First we allocate memory for
// our node and then get it's center point. Depending on the nodeID,
// GetNewNodeCenter() knows which center point to pass back (TOP_LEFT_FRONT, etc..)

// Allocate a new node for this octree
m_pOctreeNodes[nodeID] = new COctree;

// Get the new node's center point depending on the nodexIndex (which of the 8 subdivided cubes).
CVector3 vNodeCenter = GetNewNodeCenter(vCenter, width, nodeID);

// Below, before and after we recurse further down into the tree, we keep track
// of the level of subdivision that we are in. This way we can restrict it.

// Increase the current level of subdivision

// Recurse through this node and subdivide it if necessary
m_pOctreeNodes[nodeID]->CreateNode(pNodeVertices, triangleCount * 3, vNodeCenter, width / 2);

// Decrease the current level of subdivision

// Free the allocated vertices for the triangles found in this node
delete [] pNodeVertices;

///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
///// This is our recursive function that goes through and subdivides our nodes
///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::CreateNode(CVector3 *pVertices, int numberOfVerts, CVector3 vCenter, float width)
// This is our main function that creates the octree. We will recurse through
// this function until we finish subdividing. Either this will be because we
// subdivided too many levels or we divided all of the triangles up.

// Create a variable to hold the number of triangles
int numberOfTriangles = numberOfVerts / 3;

// Initialize this node's center point. Now we know the center of this node.
m_vCenter = vCenter;

// Initialize this nodes cube width. Now we know the width of this current node.
m_Width = width;

// Add the current node to our debug rectangle list so we can visualize it.
// We can now see this node visually as a cube when we render the rectangles.
// Since it's a cube we pass in the width for width, height and depth.
g_Debug.AddDebugRectangle(vCenter, width, width, width);

// Check if we have too many triangles in this node and we haven't subdivided
// above our max subdivisions. If so, then we need to break this node into
// 8 more nodes (hence the word OCTree). Both must be true to divide this node.
if( (numberOfTriangles > g_MaxTriangles) && (g_CurrentSubdivision < g_MaxSubdivisions) )
// Since we need to subdivide more we set the divided flag to true.
// This let's us know that this node does NOT have any vertices assigned to it,
// but nodes that perhaps have vertices stored in them (Or their nodes, etc....)
// We will querey this variable when we are drawing the octree.
m_bSubDivided = true;

// Create a list for each new node to store if a triangle should be stored in it's
// triangle list. For each index it will be a true or false to tell us if that triangle
// is in the cube of that node. Below we check every point to see where it's
// position is from the center (I.E. if it's above the center, to the left and
// back it's the TOP_LEFT_BACK node). Depending on the node we set the pList
// index to true. This will tell us later which triangles go to which node.
// You might catch that this way will produce doubles in some nodes. Some
// triangles will intersect more than 1 node right? We won't split the triangles
// in this tutorial just to keep it simple, but the next tutorial we will.

// Create the list of booleans for each triangle index
vector<bool> pList1(numberOfTriangles); // TOP_LEFT_FRONT node list
vector<bool> pList2(numberOfTriangles); // TOP_LEFT_BACK node list
vector<bool> pList3(numberOfTriangles); // TOP_RIGHT_BACK node list
vector<bool> pList4(numberOfTriangles); // TOP_RIGHT_FRONT node list
vector<bool> pList5(numberOfTriangles); // BOTTOM_LEFT_FRONT node list
vector<bool> pList6(numberOfTriangles); // BOTTOM_LEFT_BACK node list
vector<bool> pList7(numberOfTriangles); // BOTTOM_RIGHT_BACK node list
vector<bool> pList8(numberOfTriangles); // BOTTOM_RIGHT_FRONT node list

// Create this variable to cut down the thickness of the code below (easier to read)
CVector3 vCtr = vCenter;

// Go through all of the vertices and check which node they belong too. The way
// we do this is use the center of our current node and check where the point
// lies in relationship to the center. For instance, if the point is
// above, left and back from the center point it's the TOP_LEFT_BACK node.
// You'll see we divide by 3 because there are 3 points in a triangle.
// If the vertex index 0 and 1 are in a node, 0 / 3 and 1 / 3 is 0 so it will
// just set the 0'th index to TRUE twice, which doesn't hurt anything. When
// we get to the 3rd vertex index of pVertices[] it will then be checking the
// 1st index of the pList*[] array. We do this because we want a list of the
// triangles in the node, not the vertices.
for(int i = 0; i < numberOfVerts; i++)
// Create some variables to cut down the thickness of the code (easier to read)
CVector3 vPoint = pVertices;

// Check if the point lines within the TOP LEFT FRONT node
if( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z) )
pList1[i / 3] = true;

// Check if the point lines within the TOP LEFT BACK node
if( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z) )
pList2[i / 3] = true;

// Check if the point lines within the TOP RIGHT BACK node
if( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z) )
pList3[i / 3] = true;

// Check if the point lines within the TOP RIGHT FRONT node
if( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z) )
pList4[i / 3] = true;

// Check if the point lines within the BOTTOM LEFT FRONT node
if( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z) )
pList5[i / 3] = true;

// Check if the point lines within the BOTTOM LEFT BACK node
if( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z) )
pList6[i / 3] = true;

// Check if the point lines within the BOTTOM RIGHT BACK node
if( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z) )
pList7[i / 3] = true;

// Check if the point lines within the BOTTOM RIGHT FRONT node
if( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z) )
pList8[i / 3] = true;

// Here we create a variable for each list that holds how many triangles
// were found for each of the 8 subdivided nodes.
int triCount1 = 0; int triCount2 = 0; int triCount3 = 0; int triCount4 = 0;
int triCount5 = 0; int triCount6 = 0; int triCount7 = 0; int triCount8 = 0;

// Go through each of the lists and increase the triangle count for each node.
for(i = 0; i < numberOfTriangles; i++)
// Increase the triangle count for each node that has a "true" for the index i.
if(pList1) triCount1++; if(pList2) triCount2++;
if(pList3) triCount3++; if(pList4) triCount4++;
if(pList5) triCount5++; if(pList6) triCount6++;
if(pList7) triCount7++; if(pList8) triCount8++;

// Next we do the dirty work. We need to set up the new nodes with the triangles
// that are assigned to each node, along with the new center point of the node.
// Through recursion we subdivide this node into 8 more nodes.

// Create the subdivided nodes if necessary and then recurse through them.
// The information passed into CreateNewNode() are essential for creating the
// new nodes. We pass the 8 ID's in so it knows how to calculate it's new center.
CreateNewNode(pVertices, pList1, numberOfVerts, vCenter, width, triCount1, TOP_LEFT_FRONT);
CreateNewNode(pVertices, pList2, numberOfVerts, vCenter, width, triCount2, TOP_LEFT_BACK);
CreateNewNode(pVertices, pList3, numberOfVerts, vCenter, width, triCount3, TOP_RIGHT_BACK);
CreateNewNode(pVertices, pList4, numberOfVerts, vCenter, width, triCount4, TOP_RIGHT_FRONT);
CreateNewNode(pVertices, pList5, numberOfVerts, vCenter, width, triCount5, BOTTOM_LEFT_FRONT);
CreateNewNode(pVertices, pList6, numberOfVerts, vCenter, width, triCount6, BOTTOM_LEFT_BACK);
CreateNewNode(pVertices, pList7, numberOfVerts, vCenter, width, triCount7, BOTTOM_RIGHT_BACK);
CreateNewNode(pVertices, pList8, numberOfVerts, vCenter, width, triCount8, BOTTOM_RIGHT_FRONT);
// If we get here we must either be subdivided past our max level, or our triangle
// count went below the minimum amount of triangles so we need to store them.

// Assign the vertices to this node since we reached the end node.
// This will be the end node that actually gets called to be drawn.
// We just pass in the vertices and vertex count to be assigned to this node.
AssignVerticesToNode(pVertices, numberOfVerts);

//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\*
///// This allocates memory for the vertices to assign to the current end node
//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::AssignVerticesToNode(CVector3 *pVertices, int numberOfVerts)
// Since we did not subdivide this node we want to set our flag to false
m_bSubDivided = false;

// Initialize the triangle count of this end node (total verts / 3 = total triangles)
m_TriangleCount = numberOfVerts / 3;

// Allocate enough memory to hold the needed vertices for the triangles
m_pVertices = new CVector3 [numberOfVerts];

// Initialize the vertices to 0 before we copy the data over to them
memset(m_pVertices, 0, sizeof(CVector3) * numberOfVerts);

// Copy the passed in vertex data over to our node vertice data
memcpy(m_pVertices, pVertices, sizeof(CVector3) * numberOfVerts);

// Increase the amount of end nodes created (Nodes with vertices stored)

Share this post

Link to post
Share on other sites
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.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!