I can't find this anywhere. Can someone point me to detect hitting a "wall"?(QUAD) I can't find it, and I'm making my first "world" in OpenGL. I just need this to detect the wall collision. If you can help me thanks!
Printable View
I can't find this anywhere. Can someone point me to detect hitting a "wall"?(QUAD) I can't find it, and I'm making my first "world" in OpenGL. I just need this to detect the wall collision. If you can help me thanks!
search at GDNet for articles about collision detection, also at Gamasutra.
Both have articles discussing collision detection thouroughly.
Try these :
Simple intersection tests for games : 9 collision tests are discussed here (as far as I recall)
A list of articles
GDNet's collision detection article list
I couldn't find anything. Can someone just post a small code using collisions with quads please?
You should've found something on bounding boxes (Axis aligned bounding boxes) as well as bounding spheres. You can surround your model with one of these, and then perform your collision detection.
This works as an introductory test, which will determine whether the object's near the quad enough to do plane-collision checking or not.
Plane collision checking depends on the following :
*Create a plane for your quad (which should be planar).
Assuming the object you're checking has a bounding sphere, you substitute in the plane equation (Ax + By + Cz + D = 0, A,B,C & D are constants) with the centre of the sphere *, this will give you the distance between the sphere and the quad plane.
If the distance is greater than the radius of the sphere, then there's no collision, if equal then they're touching, otherwise they're colliding.
Creating a plane
Given 3 points, you construct 2 vectors out of them. You take the cross product between the 2 vectors, this gives you a vector normal to their plane, normalize the vector and use its x,y,z components as the plane's A, B & C members of the plane.
Now, you need the D. Substitue in the eqn :
Ax + By + Cz + D = 0
This equation is satisfied by any of the 3 points, so assuming the first points is (x1,y1,z1) :
Ax1 + By1 + Cz1 + D = 0
(A,B,C) Dot (x1,y1,z1) + D = 0
D = - (A,B,C) Dot (x1,y1,z1)
That means, that you just take the negative the value of the dot product of any of the 3 points with the normal vector you just got. Now you have the plane.
Checking the distance between a point and a plane
You just substitute with the points coordinates in the plane equation :
Point P(x0,y0,z0)
Plane (A,B,C,D)
Distance = Ax0 + By0 + Cz0 + D
You can read about this type of collision detection at GDNet :
Paul Nettle's article : This is one fine articles discussing sphere-plane & ellipsoid-plane checks (as far as I recall. you might find some additional stuff)
David Bull's article : Read this article first if you know nothing about vectors & planes.
Those didn't help really. I did read the one about vectors and planes, though. I really understand them now. I still can't find anything on this. My "world" is a first-person view, if that helps you any, and I want to stop when the person hits the walls.
Wall collision detection
As far as I see, you expect to find some tutorial named “Wall collision detection in OpenGL”; this rarely happens.
Engineering simply is applying stuff; an engineer applies stuff, he learns concepts & facts and makes something useful out of them.
John carmack - after Wolfenstein - found a paper on BSP trees, the paper was just discussing BSP trees. He invested this knowledge and made his DOOM engine (which was and is a bit famous). The paper wasn't entitled “Using BSP trees to sort geometry in an advanced raycasting engine as well as doing collision detection checks”, because this is his job - as a software engineer. The paper only introduced the concepts.
Now, those tutorials I pointed you to should've given you the following info (as well as some more, but let's just limit ourselves to these) :
1 - AABB - AABB (Axis-aligned bounding box) collision detection.
2 - Sphere - AABB collision detection.
3 - Plane - Sphere collision detection.
4 - Plane - AABB collision detection (I'm not sure whether this was in one of the tutorials, yet it can be easily deduced from the plane-sphere collision detection).
Using 1 & 2, you can do collision detection between your objects.
Using 3 & 4, you can do collision detection between objects & walls.
How?
We'll examine 4 as an example of the approach to solving such a problem. Please note that the following is definitely not the best/correct way to do it. It's the solution from my point of view based on my current knowledge of the subject. Experienced programmers will have better solutions (i.e This is not the standard solution). Additionally, there might be bugs :
Notes :Code:Requirement specification (Problem description)
Detecting whether an object and a wall are colliding or not in a 3D world.
Given some walls and a player, we have to detect whether the player's colliding with any of the walls.
Analysis
Input(s) :
1 - A pool of vertices defining the world. Each 4 consecutive vertices define a wall.
2 - A player
Output(s) :
1 - Result of collision check
Design
// For each wall, we want to create a plane for that wall to
// be used in collision detection as well as a bounding
// volume.
// The reason we need a bounding volume (sphere or box) is
// that a plane collision
// check checks the collision between an object & the plane of
// the wall (thus it acts as if your wall is infinitely long
// in all directions, while it definitely isn't).
// Bounding volumes act as a first line-of-defense, they
// prevent false collision detections with planes. See the
// attached image)
// We need the following info for a wall:
Wall_t
Plane
Sphere
FirstVertexIndex
End Wall_t
Procedure : Init
Input(s) : A vertex pool
// We first have to create a wall pool. The number of elements
// in this pool is the number of vertices we have divided by
// 4.
Create wall array of NumVertices/4 elements
// Now, we need to the fill each wall with proper info
for each 4 vertices in vertex pool
CorrespondingWall.Plane = CreatePlane v1,v2,v3
CorrespondingWall.Sphere = CalculateSphere v1,v2,v3,v4
CorrespondingWall.FirstVertexIndex = IndexOf v1
end for
End Procedure
Procedure : Destroy
Destroy wall pool
End Procedure
Procedure : CheckPlayerCollision
Input(s) : PlayerSphere
Output(s) : Result
// Now you have an array of properly filled Wall_t's. You
// need to have a bounding sphere around your player. On any
// frame update, you check the player's position in
// some heirarchial organization of your map (BSP/OCT/QUAD
// tree) in order to know which walls are close enough to do
// collision checking with (you won't check all the walls,
// otherwise the engine would be slow)
WallList = GetNearWallsFromTree(PlayerSphere)
// Assume no collision
Result = false
// Loop through walls
for each wall in WallList
if true == SphereSphereCheck(PlayerSphere,Wall.Sphere)
if true == SpherePlaneCheck(PlayerSphere,Wall.Plane)
Result = true
End if
End if
End for
End Procedure
Detailed design
Procedure : CreatePlane
Input(s) : v1,v2,v3
Output(s) : Plane
Vector Plane.Normal = (v3 - v1) Cross (v2 - v1)
Normalize Plane.Normal
Plane.D = - (v1) Dot (Plane.Normal)
End Procedure
Procedure : CalculateSphere
Input(s) : v1,v2,v3,v4
Output(s) : Sphere
Sphere.Center = (v1 + v2 + v3 + v4)/4;
Vector FarthestPoint = FarthestVectorFromCenter(Center,v1,v2,v3,v4)
Sphere.Radius = VectorLength( FarthestPoint - Center )
End Procedure
Procedure : FarthestVectorFromCenter
Input(s) : Center,v1,v2,v3,v4
Output(s) : vOut
Vector vOut = v1
Distance = VectorLength(v1 - Center)
if Distance < VectorLength(v2 - Center)
Distance = VectorLength(v2 - Center)
vOut = v2
End if
if Distance < VectorLength(v3 - Center)
Distance = VectorLength(v3 - Center)
vOut = v3
End if
if Distance < VectorLength(v4 - Center)
Distance = VectorLength(v4 - Center)
vOut = v4
End if
End Procedure
Procedure : SphereSphereCheck
Input(s) : Sphere1,Sphere2
Output(s) : Result
Distance = VectorLength(Sphere1.Center - Sphere2.Center)
If Distance >= Sphere1.Radius + Sphere2.Radius
Result = false
Else
Result = true
End Procedure
Procedure : SpherePlaneCheck
Input(s) : Sphere, Plane
Output(s) : Result
Distance = Sphere.Center Dot Plane.Normal + Plane.D
if Distance >= Sphere.Radius
Result = false
Else
Result = true
// Now we know it's a collision, you can either
// stop your object (thus preventing it from penetrating
// the wall), or
// make it slide along the wall (read Paul Nettle's
// article to know how. If you still can't figure out
// how, tell me)
End Procedure
Implementation
// Code everything
.
.
.
Testing & debugging
When you do this, you're done.
1 - You'll need to make your player slide along a wall when he hits it, otherwise he won't be able to walk on any inclined ground.
2 - This test won't work for fast objects. If an object moves a great distance in one frame, such that it penetrates a wall and becomes on the other side, collision won't be reported. That's why you'll need to perform sweep tests (discussed in the 9 simple intersection tests for games article on Gamasutra).
Sorry for any bugs in the design.
Hope this helps :D
See you
That must be the best thing I've heard on this forum :)Quote:
Originally posted by Coder
John carmack - after Wolfenstein - found a paper on BSP trees, the paper was just discussing BSP trees. He invested this knowledge and made his DOOM engine (which was and is a bit famous). The paper wasn't entitled “Using BSP trees to sort geometry in an advanced raycasting engine as well as doing collision detection checks”, because this is his job - as a software engineer. The paper only introduced the concepts.