Frustum plane calculus

Question

I'm writing a simple JavaScript 3D engine from scratch using Canvas and box like primitives (à la Minecraft) for the hell of it. I'm implementing as much optimizations as I can and so far I have back face culling and hidden face occlusion, but I can't figure out how to do frustum culling the optimal way.

I've tried 2D culling, but that has one specific problem I can't solve: if a single vertex of a 4 point plane goes is behind the camera it is still drawn but completely distorted (x and y coordinates are reversed I think) - see image.

I'm beginning to think this hasn't got a real solution without using much more complicated math and rendering sequences.

I've tried to limit the vertices x and y coordinates inside the 2D screen as long as at least one of the 4 vertices is still inside the screen (see below), but that completely distorts the square face (although I guess I can go with more fancy math and additional triangles).

I have some experience in OpenGL and it renders stuff completely differently so this isn't even a problem there.

Do I have any chance of fixing it without pulling my hair?

---

Solution

The final solution was to test each of the 8 vertices against the near clipping plane in 3D before doing 2D projection and then screen clipping.

This is the second clipping step, the first one is to test if the box is completely behind the clipping plane using bounding sphere of radius sqrt(3/2)*boxSideLength.

Additional triangles (actually points in this case) was way too complicated and math intensive, this solution isn't perfect but quite pretty.

Answer 1

You can't project a 3d point that is behind your camera into 2d screen space and have it make any sense. so you'll need to define atleast a near plane to clip to. After you transform the points from world space into camera space, but before you project to screen space, you'll need up do some clipping. You'll want to define a near plane, something like z = 1 or something close to but in front of the camera and will define a space where points are capable of being projected into screen space.

You have three options, the first is if any point in the polygon falls behind the near plane, then don't draw the entire polygon. This is simple but usually unacceptable. Compare each point against the near plane (if polygon.points[i].z < near.z). But this will make polygons disappear and reappear seemingly randomly at the edges of the screen.

Your second option is to clip your polygon to the near plane. For triangles if all three points are behind the near plane then don't draw. If two points are behind then clip the two line segments to the near plane and draw the triangle. If one point is behind the near plane, then clip and make two new triangles and draw. If none are behind the near plane then just draw. If I wasn't posting this from my phone I would go into more detail, but hopefully that makes sense.

Lastly you can do full fustrum clipping and instead of just clipping to your near plane, clip for all 6 sides of your visible frustum.

There are optimization algorithms for each of these approaches but I would start with the basics and work forward. Each step is basically an extension of the last so I would start by going with the first and then getting more complicated, until you get the visual and performance levels you are looking for.

Answer 2

Look up clipping. Cohen-Sutherland is one fairly easy to use method. The wikipedia page linked even has some C/C++ code for implementing it.

If you introduce things like gouraud shading and texture mapping you'll find clipping post the w divide will distort things quite significantly still (ie texture and colour interpolation will look wrong). As such it i often better to do something like Cohen-Sutherland in 3D.