Adventures in 3D: Part VI - Faster Pussycat! Cull! Cull!

Oh look, the return of the Adventures in 3D series - you might want to start at the beginning

Last time out, we had a nice shaded sphere spinning around. First things first, a sphere is very boring to rotate - if it weren't for the polygons, you wouldn't even notice. So lets jam a little bit of maths in there so that it's a bit more obvious. In the createScene() method, add a factor to the calculation of each Point position to modify the rotundness. Note the 0.8 and 0.4. This will give you something akin to a Trebor Softmint.

points[phi][theta] = new Point(radius * Math.cos(stp * phi)
   * Math.sin(stp * theta), radius * 0.8 * Math.sin(stp * phi)
   * Math.sin(stp * theta), radius * 0.4 * Math.cos(stp * theta));

If you have any sense of adventure, you will probably already have played around with the line

int STP = 60;

in the createScene() method. This line determines how many latitude/longtitude sections the sphere is divided into, and therefore, the higher this number, the more polygons that make up the sphere, and the smoother it will appear. With a value of 10, the sphere has a total of 100 polygons and will appear very obviously made up of triangles, much like the 3D graphics of yore. A value of 100 will give you something much better looking, using 10000 polygons. Of course, this is all a trade-off - the time to render 10000 polygons is not insignificant, and you'll find that the rotation is much less responsive.

Polygon count is the rawest measure of 3D graphics performance. More polygons, in theory, equals better graphics. But you can't just up the numbers, because it all takes time. So you can try to find a way to render polygons on the screen quicker, or you can reduce the number of polygons you have to render. If you want to take the latter, you can either make your graphics less detailed, or you can just plain cheat. Guess which option we're going for?

In any given frame in our 3D scene, there are a bunch of polygons that we're just not going to see, which are those on the other side of the shape, facing away from us. In the case of a sphere, that's fully half of all the polygons we're drawing every frame which we don't need to draw. So there's a simple conclusion - let's not draw them. This is Backface Culling.

Working out which faces you don't have to draw turns out to be very simple. You'll remember that in Part IV we discussed normals, which are vectors telling us which way a polygon is facing, and the dot product, which tells us something about whether two vectors are pointing the same way or not. To check for a backwards facing polygon, we'll compare it's vector normal to a vector that represents the direction we're looking in. In the Triangle class:

 private Vector viewer = new Vector(0,0,-1);
 
 public void draw(Graphics2D graphics) {
    Vector normal = getNormal().normalise();
  
    //backface culling
    double cull = normal.dotProduct(viewer);
    if(cull > 0) return;

    ...rest of the method...
 }

Quite simply, get the vector normal for this polygon, normalise it (not strictly necessary here, but we'll reuse it later), and then find the dot product with the view vector. Remember that a result of zero means that one vector is orthogonal (i.e. at 90 degrees) to the other. A result of greater than zero means that they form an angle less than 90 degrees, and so if the view vector is pointing away from the viewer, so is the vector normal, to some extent. If that's the case here, we return from the method, so this polygon is not drawn at all on screen.

There's one gotcha here - for the normal to point in the expected direction, the points in your polygons must be defined in a clockwise direction. If you define the points anti-clockwise, things can still work, but the vector normal for polygons facing away from you will point towards you, so the check becomes if(cull < 0) instead.

Let's do some unscientific testing. I added some code (the static getAndResetDrawnCount() method) to the Triangle class so we can keep count of how many polygons have actually been drawn, and retrieve that to display at the end of each frame render. I also added some very simple timing code to time how long each frame takes to display.

Without backface culling present (and using an STP value of 100), the output shows that all 10000 polygons were rendered, and the time varies but a quick eye grep suggests it averages (on my machine) around 27-30ms. When the two lines of culling code are added, the average number of objects actually drawn to the screen drops to around 5080, and the average time is somewhere around 15ms - as you might expect if it's doing half the work.

By now you must surely be taking your seat in the pantheon of the 3D gods. If not, cheat by downloading the source. In either case, we'll be coming back to earth with a bump next time when we look at introducing a camera. Warning: contains matrix maths.