3D maze

This is a discussion on 3D maze within the Game Programming forums, part of the General Programming Boards category; I'm really not a touchy programmer but I dislike being questioned mid-post when the only reason behind it is simply ...

  1. #16
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    I'm really not a touchy programmer but I dislike being questioned mid-post when the only reason behind it is simply because you have a faster algo
    The reason I questioned you was because you never actually posted a full algorithm for doing a collision test, only a trivial rejection.

    Perhaps if your approach were different I would respond differently
    I'm doing an exceptionally good job as far as I'm concerned, but thanks
    See you in 13

  2. #17
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    I rarely post full code algos or even full algos on the board. It doesn't help for me to spoon feed information. Concepts are far more important than the code that implements them.

    I've posted a ray to triangle intersection snippet here before as well as several other algos relating to graphics. I couldn't tell you which of my 2069 posts involve graphic algos, but I'm sure it's quite a bit of them.

  3. #18
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    To the original poster: have you made any progress? Are you still even following the thread?
    See you in 13

  4. #19
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198
    >>To the original poster: have you made any progress? Are you still even following the thread?

    I had no time to start, but have read some of the post and have looked at some tutorials.

    My walls in the maze are constructed of polygons, so 1 polygon for each wall.

    I will try to attempt Bubba's idea, with a ray intersecting a plane.
    -MethodMan-

    Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.

    Homepage: http://www.freewebs.com/andy_moog/home.html

  5. #20
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    Okay, just remember that's only an early rejection test not a complete collision detection method.

  6. #21
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198
    I was reading on nehe

    You test whethere the ray intersects a plane, and then you know that point, and then you can check if that point is on the polygon of the wall.

    Just wanted to clarify.

    I have a lot of polygons, one for each wall in the maze, each with a normal.

    My camera is on the player, kind of like a first person view. I need to create a ray to see if it intersects the plane (wall). Would I be using values from the gluLookat in order to test whether the ray intersects the plane?

    Edit:

    I found this site:

    http://www.cs.montana.edu/~charon/th.../collision.php

    Using what they suggest, you will find out the distance to the intersection point. I would then have to test to see if the point is acutally on the plane of the polygon.

    Im a bit confused.

    How do I get any information as to which plane/polygon I will be testing on. Im not really afraid of losing some speed by testing every wall, since there wont be that many.

    Im not sure how you create a plain on the polygon to test it against.

    Thanks again
    Last edited by MethodMan; 11-23-2004 at 04:37 PM.
    -MethodMan-

    Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.

    Homepage: http://www.freewebs.com/andy_moog/home.html

  7. #22
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    You want to be using your start point and endpoint, then, you send your final calculated collision position to gluLookAt (the point where you ended up actually colliding).

    edit:
    I'm cleaning my room to pack up for thanksgiving, but I'll gladly go on AIM and walk you through this.

  8. #23
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    Any three points in 3D space are guaranteed to be coplanar. But it's even easier than that. Since your walls are already flat then you know all points on the wall are coplanar.

    Also we know that the dot product of two perpendicular vectors is always 0. Since this is true and since all your walls are planes themselves you can test whether or not any point is in the plane by a simple dot product. If the result is 0 then you know the point is on the plane. However, in 3D games this is RARELY EVER going to work out perfect since you will probably interpenetrate the plane or the wall.

    The equation for a plane is A+B+C+D=0 or A+B+C=D.

    It can be expressed in vector form as:

    N dot P=0

    Where N is the normal to the plane and P is a point on the plane.

    The graph of a plane is:


    N dot (P-P0)=0


    Essentially if PO lies on the plane then the point P also lies on the plane if the vector formed from P-P0 is orthogonal to the plane's normal vector.

    This results in the popular form: N dot P + d =0

    d=-N dot P0

    If the normal is of unit length then the above equation gives the shortest signed distance from the origin to the plane.

    Ok now a,b,c form the component's of the plane's normal vector and d is the is the value we just derived from above.

    From this proof we can see that:

    if (n dot p)+d=0 then p is coplanar with the plane
    if (n dot p)+d>0 then p is in front of the plane and in the plane's positive half space.
    if (n dot p)+d<0 then p is in back of the plane and in the plane's negative half space.

    The D3DX library provides functions to compute all of this but since you are not using Direct3D I will write the C function here.

    Code:
    typedef struct Plane
    {
      float a,b,c,d;
    }
     
    void VectorDotPlane(Plane P,Vector3 V)
    {
      return ((P.a*V.x)+(P.b*V.y)+(P.c*V.z)+(P.d))
    }

  9. #24
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    arg, I was really, really, really hoping you wouldn't post that form of the plane equation, it accomplishes the same thing but only confuses someone starting out. The d is computed with a normal vector which is anti parallel (the negative of) the actual normal, which is why I hate that form of the plane equation.
    Last edited by Darkness; 11-24-2004 at 01:07 AM.

  10. #25
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    Not if you use the A+B+C=D.

    That doesn't negate D.

    So:
    Code:
    ....
     
      return ((P.a*V.x)+(P.b*V.y)+(P.c*V.z)-(P.d));
    }

  11. #26
    Registered User
    Join Date
    Mar 2003
    Posts
    580
    A+B+C+D=0
    D must be negative in this case, because:

    d=-N dot P0

    If the normal is of unit length then the above equation gives the shortest signed distance from the origin to the plane.
    That's actually the distance from the point to the origin, and there's a crucial distinction, because if you started at the origin, then traveled d units in the Normal direction, you dont' end up at P, you end up on the other side of the origin, and that's why it was so hard for me to visualize starting off. The only reason they do this is so that they can add in the plane equation, instead of subtract (add a negative instead of subtract a positive).

    It doesn't really matter, he'll get used to both, but we might have to start drawing pictures.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 3D starfield
    By VirtualAce in forum Game Programming
    Replies: 6
    Last Post: 06-26-2003, 01:40 PM
  2. 3D SDK for C++ programmers
    By chand in forum Game Programming
    Replies: 2
    Last Post: 05-20-2003, 08:38 AM
  3. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM
  4. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-25-2002, 12:00 AM
  5. 3d engines
    By Unregistered in forum Game Programming
    Replies: 7
    Last Post: 12-17-2001, 11:19 AM

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