Collision with quads?

This is a discussion on Collision with quads? within the Game Programming forums, part of the General Programming Boards category; I can't find this anywhere. Can someone point me to detect hitting a "wall"?(QUAD) I can't find it, and I'm ...

  1. #1
    Programming is fun, mkay?
    Join Date
    Oct 2001
    Posts
    490

    Question Collision 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!
    Website(s): http://www16.brinkster.com/trifaze/

    E-mail: trifaze_mattu@lycos.com

    ---------------------------------
    C++ Environment: MSVC++ 6.0; Dev-C++ 4.0/4.1
    DirectX Version: 9.0b
    DX SDK: DirectX 8.1 SDK

  2. #2
    Registered User Coder's Avatar
    Join Date
    Aug 2001
    Location
    Cairo, Egypt
    Posts
    128
    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
    Muhammad Haggag

  3. #3
    Programming is fun, mkay?
    Join Date
    Oct 2001
    Posts
    490

    Question Can't find...

    I couldn't find anything. Can someone just post a small code using collisions with quads please?
    Website(s): http://www16.brinkster.com/trifaze/

    E-mail: trifaze_mattu@lycos.com

    ---------------------------------
    C++ Environment: MSVC++ 6.0; Dev-C++ 4.0/4.1
    DirectX Version: 9.0b
    DX SDK: DirectX 8.1 SDK

  4. #4
    Registered User Coder's Avatar
    Join Date
    Aug 2001
    Location
    Cairo, Egypt
    Posts
    128
    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.
    Muhammad Haggag

  5. #5
    Programming is fun, mkay?
    Join Date
    Oct 2001
    Posts
    490

    Unhappy That 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.
    Website(s): http://www16.brinkster.com/trifaze/

    E-mail: trifaze_mattu@lycos.com

    ---------------------------------
    C++ Environment: MSVC++ 6.0; Dev-C++ 4.0/4.1
    DirectX Version: 9.0b
    DX SDK: DirectX 8.1 SDK

  6. #6
    Registered User Coder's Avatar
    Join Date
    Aug 2001
    Location
    Cairo, Egypt
    Posts
    128
    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.
    Notes :
    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
    See you
    Attached Images Attached Images  
    Muhammad Haggag

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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.
    That must be the best thing I've heard on this forum
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Some collision handling fun
    By DavidP in forum Game Programming
    Replies: 9
    Last Post: 04-13-2008, 09:45 AM
  2. Collision Detection Problems
    By Dark_Phoenix in forum Game Programming
    Replies: 1
    Last Post: 12-17-2006, 03:25 PM
  3. Collision Detection
    By Grantyt3 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2005, 04:21 PM
  4. collision detection
    By DavidP in forum Game Programming
    Replies: 2
    Last Post: 05-11-2002, 02:31 PM
  5. Replies: 4
    Last Post: 05-03-2002, 10:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21