# Collision using Octree - when to check a node

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

## Recommended Posts

Hey alltogether... I implemented a collision detection system into my engine, combined with an octree. Before I am going to check my vertices for collision, I want to know which nodes I have to check. Since I know the center of each Node / ChildNode and its diameter / radius I should easily be able to check if my boundingsphere is within a node. So is the theory... Practically I did it the following way: If the distance between the centers of my boundingsphere and the node (I check all nodes/childnodes) is smaller then the radius boundingsphere + radius node, the boundingsphere has clearly entered the node and therefore need to be checked for collision. Since the boundingsphere is moving with a certain speed it might happen that, between the frames, my boundingpshere enters a node and "collides" with an object without knowing it. To prevent that, I just "extended" the radius value of the boundingsphere I use for this check. So the node is being checked before the boundingsphere enters the node. Another possibility I thought of is just to add velocity to the actual position of the bounding sphere to find out, which nodes lie on its movement vector (where the boundingsphere will be shortly). Both possibilities sound good to me, but somehow it still doesnt work out. If I use one of these methods to check my nodes, I miss parts of the node (even if there is only one) and I fall through the ground... Are there other, better ways to define when a boundingsphere enters a node or do I just miss an essential part while checking it? As far as I can tell my octree is being created correctly. (If I just run through all nodes without checking if I am in one of the nodes it works fine, but slow, since this is like working without my octree...) //edit: The way I get the center of the Node: loop through all vertices of node { center.x = Center.x + Vertices.x center.y = Center.y + Vertices.y center.z = Center.z + Vertices.z } Center.x = Center.x / NumberofVertices Center.y = Center.y / NumberofVertices Center.z = Center.z / NumberofVertices et voila, the center of the node... The way I get the radius of the Node: again loop through all vertices of node { - find the distances of all vertices to the center - remember the biggest distance to the center } the biggest distance to the center is the radius... [Edited by - darkwolf79 on March 29, 2006 8:06:23 AM]

##### Share on other sites
You're finding the centre of your octree node incorrectly.

You're supposed to store bounding box definitions for each end-node when you create the octree. Only store triangles in end nodes.

CVector3 COctree::GetNewNodeCenter(CVector3 vCenter, float width, int nodeID){	CVector3 vNodeCenter(0, 0, 0);	CVector3 vCtr = vCenter;	switch(nodeID)								{		case TOP_LEFT_FRONT:			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y + width/4, vCtr.z + width/4);			break;		case TOP_LEFT_BACK:			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y + width/4, vCtr.z - width/4);			break;		case TOP_RIGHT_BACK:			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y + width/4, vCtr.z - width/4);			break;		case TOP_RIGHT_FRONT:			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y + width/4, vCtr.z + width/4);			break;		case BOTTOM_LEFT_FRONT:			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y - width/4, vCtr.z + width/4);			break;		case BOTTOM_LEFT_BACK:			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y - width/4, vCtr.z - width/4);			break;		case BOTTOM_RIGHT_BACK:			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y - width/4, vCtr.z - width/4);			break;		case BOTTOM_RIGHT_FRONT:			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y - width/4, vCtr.z + width/4);			break;	}	return vNodeCenter;}

Then when you wish to check whether a sphere intersects the node,

int ClassifySphere(CVector3 &vCenter, 				   CVector3 &vNormal, CVector3 &vPoint, float radius, float &distance){	// First we need to find the distance our polygon plane is from the origin.	float d = (float)PlaneDistance(vNormal, vPoint);	// Here we use the famous distance formula to find the distance the center point	// of the sphere is from the polygon's plane.  	distance = (vNormal.x * vCenter.x + vNormal.y * vCenter.y + vNormal.z * vCenter.z + d);	// If the absolute value of the distance we just found is less than the radius, 	// the sphere intersected the plane.	if(Absolute(distance) < radius)		return INTERSECTS;	// Else, if the distance is greater than or equal to the radius, the sphere is	// completely in FRONT of the plane.	else if(distance > radius)		return INFRONT;		// If the sphere isn't intersecting or in FRONT of the plane, it must be BEHIND	return BEHIND;}

If you call thebove function for each side of your bounding box, and they all return BEHIND or INTERSECTS, then you have to check collision against that node.

For a complicated scene, you could probably speed this up a bit by checking whether points (origins of you objects) are in the bounding-boxes of each octree node - before you run the above sphere check.

##### Share on other sites
First of all, thanks for the answer... ;) helped me finding my mistake...

Right, I only have the diameter / radius of the parent node, holding the 8 child nodes which contain the vertices. In that case my whole check routine is only checking for that parent node.

But it should work when there is only one node, shouldnt it? anyway...

Since the radius is only valid vor the parent node holding the child nodes with the vertices, what would be the best way to find out which of those child nodes is affected?

I can use the routine I was using to find out which parent nodes are affected, but once I know that, how could I determine which of the 8 child nodes need to be checked (in a fast way :) ) ?

my check routine looks like that:

TestOctree(octree node)
{
if( node->holding_triangles )
{
// here i can check if the boundingsphere is within this node
}
else // not holding triangles, check the 8 child nodes
{
TestOctree(node->TOP_FRONT_LEFT]);
TestOctree(node->TOP_FRONT_RIGHT]);
TestOctree(node->TOP_BACK_LEFT]);
TestOctree(node->TOP_BACK_RIGHT]);
TestOctree(node->BOTTOM_FRONT_LEFT]);
TestOctree(node->BOTTOM_FRONT_RIGHT]);
TestOctree(node->BOTTOM_BACK_LEFT]);
TestOctree(node->BOTTOM_BACK_RIGHT]);
}
}

i can skip that process when i know that the parent node is not affected (no need to go through the child nodes then), but how finding the affected child nodes, since i only have triangle informations in those nodes...

thx in any way, brought me a bit further...

//edit:
I know the child nodes containing the vertices are only supposed to be an array holding the vertex data, but wouldnt the easiest way to find out which child nod e is affected not just be to store the center and radius of each of those child nodes? Then the check routine could be quite fast, just checking the distance of the boundingsphere to each of those nodes...

//edit²:
Ok, I was running into a wrong direction here... The diameter/radius I get back is of a bounding box. Assuming that it is a bounding sphere ruined everything... Now this is humiliating. *g*

That makes the whole checking process a lot more difficult.
How would an approach look like to find out if a sphere is within or enters a bounding box?

[Edited by - darkwolf79 on March 29, 2006 2:44:12 PM]

##### Share on other sites
I've posted the function for determining whether a sphere is intersecting, or within a bounding cube... just check against it 6 times...

##### Share on other sites
jepp, and once more you are right...
After working on this for hours now I start to be blind...

##### Share on other sites
one more question about feeding that function, then i have enough for the day...
(math at that time of the day get seriously difficult *arr*)

If I am right, then there is no need to generate the normals of the 6 planes of the bounding cube, since I know them anyway (since the box is axis aligned).

And for vPoint I should be able to use one of the corner points of the according plane.

thx alot ;)

##### Share on other sites
Problem solved, thanks alot for help, it finally looks like it works now.

Now I can tweak the whole thing...
This is my first collision detection/response system, using an octree. I will include torque, friction and bouncing to create a simple physics simulation, when I am completely done with the whole project, I will upload it for criticism. :)

• 19
• 10
• 19
• 14
• 19