Hello everyone. I'm working on a project now called Doom.Net, a remake of Doom with C# and unfortunately I'm having some trouble implementing frustum culling. Now I only need 2D culling, because while Doom levels look 3D, their structure is actually 2D. Basically the level is made up of vertices, 2D X and Z points, and line segments(two vertices connected). I can walk through the BSP tree and get the nearest lines fine, but part of the problem is that it draws all the lines in view, so when looking at a whole level it draws everything. My angle system looks like this:

       90
        |
        |
180-----------0
        |
        |
       270

My idea for culling was just to test whether any one of a lines vertices where in view, then find the angles between the camera and its vertices. I would then send those angles to some kind of clipping function, which would check if the screen was "full". The first problem is if I have the camera looking "east" any of the retrieved angles could be between 0 and 90, while the other is between 270 and 360. I have no idea how to translate this into useable values. Plus if the player is right in-front of a line that won't work.

      \    /
*------\--/--------* Wall
        \/
         *Camera

Any ideas? I've been struggling with this for a while and would appreciate any help.

Forget angles. Just test the line segment for intersection with the frustum using the separating axis test; this will solve the problems you mention, including the 'wall directly in front of player' problem.

Let me know if you need any additional info.

Thanks jyk, that appears to be a much better way of doing things. However I've having some trouble understanding how I'm supposed to implement it. Everything online seems to be focused on polygons and vectors, not simple shapes like just a point and line.

Quote:Original post by Scet
Thanks jyk, that appears to be a much better way of doing things. However I've having some trouble understanding how I'm supposed to implement it. Everything online seems to be focused on polygons and vectors, not simple shapes like just a point and line.

Is your frustum bounded (a triangle) or unbounded (an infinite wedge)?

Infinite wedge, although I could make it into a triangle if it had to be.

(in Doom there's no far clipping plane, which is why I went with infinite)

The first step will be to test the line segment against each of the two hyperplanes making up the frustum. If it's in the negative halfspace of either, it's culled.

If after these tests the segment is still not culled, the next step is to see if the 'infinite wedge' of the frustum lies entirely in either half-space of the hyperplane associated with the line segment. The conditions for this case are that the camera is 'pointing away from' the wall, and that the angle between the wall and the camera direction vector is greater than half the field of view. (This is off the top of my head, but I think it's right.)

If this is unclear, you might draw a few diagrams, which should help clarify things. All of the above tests should reduce to just a few dot products and a little vector arithmetic, and so should be quite efficient.

How do I create the hyperplanes? After looking on Google, 2D hyperplanes are just lines right? So do I just create a vector at the cameras position with the direction set to the cameras angle +- half the FOV?

Quote:Original post by Scet
How do I create the hyperplanes? After looking on Google, 2D hyperplanes are just lines right? So do I just create a vector at the cameras position with the direction set to the cameras angle +- half the FOV?

Right, a hyperplane in 2D is a line (in 3D it's a plane).

For the purpose of culling it's most useful to represent the line as a unit-length normal and a distance along that normal from the origin. If v is the vector you describe above, then the corresponding normal-distance representation is:

vector2 normal(-v.y,v.x);float distance = dot(camera_position,normal);

You then need to flip the normals of one of the frustum lines (the left one, I think) in order for them both to point to the inside of the frustum.

This will set you up for the tests I described earlier. If you're unsure of how to perform the tests, I'd start by googling 'point plane distance'. Aside from the dimensions of the vectors involved, the equations are the same in both 2D and 3D.

Post back if you get stuck on anything.