Fix My Bugs

I enjoyed writing about Triple Pop so much, I’m going to continue straight on with the next game I coded at iomo, Sky Diver.  Sky Diver was another white label game for Nokia, this time targeted initially at the 5100, but also later the 3510i.  The 5100 is technically very similar to the 7210, it’s another Series 40 v1 device, but is aimed at the ‘outdoor sports’ type person.  It has a rugged rubber jacket that’s splash proof and the promo material at the time showed people climbing mountains using it!  A game about sky diving was ideally suited to the device.

This time, the game was entirely new, there wasn’t an existing mobile game to base things on.  However, if you look closely, you’ll notice a vague similarity to Pilot Wings for the SNES!

At the time, we created designs for games  in one or two pages, and it was Glenn Broadway, iomo founder and creative director who visualised the ideas.  Indeed, they were mostly his initially, even if they were refinements of existing ideas or games.

Technically, creating a sky diving game for a mobile device actually turned out to be fairly straightforward.  My collegue Nick Reed (an amazing programmer who later became technical director of iomo and my boss at Infospace) wrote a few lines of code that demonstrated scaling and rotation on a set of points.  By rendering lines between the points it looked like flying down from a height onto an airfield. The MIDP 1.0 specification has basic line drawing methods, but Nokia added an additional API with functions beyond the standard. The early Series 40 devices didn’t have Mode 7 hardware sprite scaling and rotation, but they did have an API with 2D polygon drawing methods.  My job was to take the simple idea and along with artist Cameron Kerr, more input from Glenn, and QA from Nokia, flesh it out into the game it became.

Polygon Clipping

You can probably stop reading now if you don’t care about technical details!  I didn’t post any code from Triple Pop because basically there wasn’t anything generally useful.  In Sky Diver however, there turned out to be an interesting problem that needed to be solved.  When the points that described the ground polygons were scaled too much, as happened at low altitudes, the large values passed to the drawLine and drawPolygon methods caused them to become really slow.  I imagine there wasn’t any internal clipping performed on the geometry, only pixel clipping to the current screen clip region when attempting to rasterise the line to pixels.  This meant if you did drawLine (0,0,10000,10000), it look a long time!

To the rescue came the seminal Computer Graphics, Principles and Practice by Foley, van Dam, Feiner and Hughes.  It goes into great detail about line and polygon clipping, and gives algorithms in Pascal or C (depending upon the edition).  I wrote these Java routines directly from the algorithms in the book:

Sutherland-Hodgman Polygon Clipping in Java

Liang-Barsky Polygon Clipping in Java

To use the routines, you call them with arrays of points, and arrays to put the clipped polygon points into.

if(land_type <= Land_Runway || land_type == Land_Ground) {

   c = SutherlandHodgmanPolygonClip(num_points,
                                    poly_x,poly_y, // input verts
                                    clip_x,clip_y, // output verts
                                    TOP
                                    );

   if(c > 0) {
      c = SutherlandHodgmanPolygonClip(c,
                                       clip_x,clip_y,   // input verts
                                       poly_x,poly_y,   // output verts
                                       LEFT
                                       );
      if(c > 0) {

         c = SutherlandHodgmanPolygonClip(c,
                                          poly_x,poly_y,   // input verts
                                          clip_x,clip_y,   // output verts
                                          BOTTOM
                                          );
         if(c > 0) {

            c = SutherlandHodgmanPolygonClip(c,
                                             clip_x,clip_y,   // input verts
                                             poly_x,poly_y,   // output verts
                                             RIGHT
                                             );
         }
      }
   }

   if(c > 2) {
      // Draw the polygon as a series of triangles.
      // Here we assume that the polygon is convex, because the triangle
      // decomposition for concave polys is much more complex and probably
      // more time consuming than the poor performance of fillPolygon!
      for(j = 1; j < c-1; j++) {
         dg.fillTriangle(poly_x[0],poly_y[0],
                         poly_x[j],poly_y[j],
                         poly_x[j+1],poly_y[j+1],
                         colour);
      }
   }

} else {

   c = LiangBarskyPolygonClip(num_points,            // count
                              poly_x,poly_y,         // input verts
                              clip_x,clip_y);        // output verts

   if(c > 2) {
      dg.drawPolygon(clip_x,0,clip_y,0,c,colour);
   }
}

The code above picks the clipping routine to use based on the land type of the current shape being drawn, the comments for the clipping routines explain the best ways to use them. The fillPolygon and fillTriangle methods come from the Nokia DirectGraphics interface, but you could replace them with drawLine calls for wireframe rendering. If you’re looking for some clipping routines and find these useful, let me know with a comment. I might even put together a standalone J2SE demo if anyone shows any interest