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

- 01-11-2002SyntaxBubbleCollision with quads?
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!

- 01-12-2002Coder
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 - 01-12-2002SyntaxBubbleCan't find...
I couldn't find anything. Can someone just post a small code using collisions with quads please?

- 01-13-2002Coder
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. - 01-13-2002SyntaxBubbleThat did...
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.

- 01-16-2002Coder
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 :

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 - 01-18-2002MagosQuote:

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