collision inside a box

Started by diagostimo, January 22, 2013, 11:29:14 pm

Previous topic - Next topic

diagostimo

hey there guys, I have a problem figuring out the are of some triangles within a box, and thought id ask here first as you guys are pretty awesome when it comes to this sort of stuff!
so recently I have been looking into 3D game development from scratch using the LWJGL library for Java, and I am currently trying to create a collision detection system using bounding boxes around things, so the way I am currently going about it is I am testing whether a point/vector of my characters bounding box is entering another bounding box, and I will do this for all the points on my bounding box to ensure that there is no collision an the target location.

so I have managed to get it to work, well it sort of works, but at certain points of the box it doesn't work, and I cant find the problem, here is the code to my collision detection:



       public boolean collide(Cube collider, float tX, float tY, float tZ) {

boolean check;
//first check the collision of players collider vertices
check = testArea(this.collider.rotFBL, collider, tX, tY, tZ);
if (check) {
return true;
}
check = testArea(this.collider.rotFBR, collider, tX, tY, tZ);
if (check) {
return true;
}
check = testArea(this.collider.rotBBR, collider, tX, tY, tZ);
if (check) {
return true;
}
check = testArea(this.collider.rotBBL, collider, tX, tY, tZ);
if (check) {
return true;
}
//next check the targets collider vertices
//check = testArea(collider.rotFBL, this.collider, tX, tY, tZ);
//if (check) return true;
//check = testArea(collider.rotFBR, this.collider, tX, tY, tZ);
//if (check) return true;
//check = testArea(collider.rotBBR, this.collider, tX, tY, tZ);
//if (check) return true;
//check = testArea(collider.rotBBL, this.collider, tX, tY, tZ);
//if (check) return true;

//if all checks don't return true then there is no collision
return false;

}


tX ect. are the target coordinates, and what that is doing is sending the points to be individually checked to see whether they are inside the target box, also note the rotFBl etc are the rotated points named acordingly, for example rotFBL is rotatedFrontBottomLeft, next the method that checks if the point is inside the area:



private boolean testArea(Vector3f vector, Cube collider, float tX, float tY, float tZ) {

float lArea = Math.abs(collider.rotFBR.x * (collider.rotBBR.z - (vector.z + tZ)) +
collider.rotBBR.x * ((vector.z + tZ) - collider.rotFBR.z) +
(vector.x + tX) * (collider.rotFBR.z - collider.rotBBR.z)) / 2;

float rArea = Math.abs(collider.rotFBL.x * (collider.rotBBL.z - (vector.z + tZ)) +
collider.rotBBL.x * ((vector.z + tZ) - collider.rotFBL.z) +
(vector.x + tX) * (collider.rotFBL.z - collider.rotBBL.z)) / 2;

float tArea = Math.abs(collider.rotBBL.x * (collider.rotBBR.z - (vector.z + tZ)) +
collider.rotBBR.x * ((vector.z + tZ) - collider.rotBBL.z) +
(vector.x + tX) * (collider.rotBBL.z - collider.rotBBR.z)) / 2;

float bArea = Math.abs(collider.rotFBL.x * (collider.rotFBR.z - (vector.z + tZ)) +
collider.rotFBR.x * ((vector.z + tZ) - collider.rotFBL.z) +
(vector.x + tX) * (collider.rotFBL.z - collider.rotFBR.z)) / 2;

float fullArea = lArea + bArea + rArea + tArea;
float fullBoxArea = collider.xScale * collider.zScale;
//System.out.println("full area = " + fullArea);
//System.out.println("box area = " + fullBoxArea);

if (fullArea > fullBoxArea) {
return false;
}

return true;

}


now what im doing here is dividing the square into 4 triangle, where the point of the triangle is the target position, then what i do is calculate the area of my square, and the area of all the triangles, if the area of the calculated triangles is greater than the square then the position is ouside the box, if it is equal then it is is inside.

to be honest im not sure what could be wrong, as i believe i have calculated the areas properly, i seem to slightly glitch inside it if i spend a while rubbing up against it, also i tested it walking ontop of the box and there seemed to be a fall through point just around the centre next to each face, so im guessing that when the target coordinate was at that point it lets me glitch through :( any insight would be really helpful with this as its driving me crazy!

i can also provide the source code if anyone wants to look deeper into it, im using eclipse as my workspace :)

winkio

I didn't really look at your code, but just from your description I can tell you that this will be both slow and inaccurate, and is just way more complicated than it needs to be.

If you are using axis aligned bounding boxes (bounding boxes with no rotation), look up how to do collisions within the configuration space.  You can turn a box-box collision into a single point-box collision, and you can easily test for intersection with '>' and '<' and get the point of intersection.

If you are using object oriented bounding boxes (bounding boxes with rotation), use methods for polyhedra, such as V-clip.  You should be able to find a free implementation online along with an explanation.

Blizzard

I only wanted to add that it's possible that you haven't considered the borderline case of one box containing the other or the boxes touching.

Other than that, winkio is right, there are faster and simpler ways to do this. You should google stuff like this.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

fenryo

agree with the others,
don't try to check every vertice or pixel you will burn the processor and get a slow framerate. Try to see this with coordinate (x,y,z) of the more left corner of each box and with the width, lenght and depht you can easily try to create an algo more efficient (try it on paper to see)

other "optimisation stuff" is to cancel the test of collision if the "axis" of the characters are far away.

diagostimo

thanks for the input guys, ill definitely look into those methods of collision, I know I can do it very simply testing the width and the height to check if there is an intersection, I actually did it that way to begin with but the problem came when my character rotated, so I needed a more dynamic way of testing it, anyway  last night I found this v-clip Java port: http://www.cs.ubc.ca/~lloyd/java/vclip.html
so ill see if I can do anything with that, the only problem is I have no working examples with it, so I am not to sure on what methods I should be using, I also took a video last night of my issue with my current code, so I might as well upload it to show the issue a little better, although ill probably end up replacing the code, ignore the minecraft like character, I recreated the minecraft character as its a pretty easy way to build it :) if you watch the video you will see the collision works pretty well, except from when only one corner is entering a certain point of the cube, and it lets it freely enter:

http://www.youtube.com/watch?v=tlULfF8sRTI&feature=youtu.be