# 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.

## 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 on other sites
Have you looked into octrees?

##### 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.                                 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[i / 3])				{				pNodeVertices[index] = pVertices;				index++;			}		}		// 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		g_CurrentSubdivision++;		// 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		g_CurrentSubdivision--;		// 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);	}	else	{		// 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)	g_EndNodeCount++;}

##### 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 11
• 28
• 15
• 39
• ### Forum Statistics

• Total Topics
634835
• Total Posts
3019539
×