Logo 3.5Cats_AndHalfAFish

3.5Cats_AndHalfAFish

Pixel-perfect touch with polygons.

January 05, 2019 SeaRose
Hack.

Shortly after I started working on SeaRose, I noticed a big problem with the Starling framework I was using:


Somehow, mouseOver and mouseClick events happened even when the mouse was over transparent pixels ! Obviously, that's not what I wanted.

This behvior puzzled me because it is not what I had seen before, with ActionScript and OpenFL ...

As it turns out, it has something to do with hardware acceleration and the GPU.
I'm not going to pretend I completely understand all of this, but it seems that in de Olden Days, images were handled by the CPU. Since the CPU has access to the individual pixels of an image, it knows if a pixel is transparent or opaque. Because collisions and touch (mouse) events can only happen over opaque pixels, you get automatic pixel-perfect touch and collision.
Nowadays, more and more game development libraries let the GPU handle the graphics. Most of the time, this will result in a much better performance for the game. A side effect however, seems to be that once an image has been loaded into the GPU memory, one can no longer access the individual pixels of the image (in the Starling library ; I don't know about other hardware accelerated libraries). Therefore, one has no way of knowing if an individual pixel is opaque or transparent. So, touch and collision events have to be calculated based on the width and height of the image (the bounding box). Most of the time, and for most types of games, this isn't a problem. But for hidden object games it obviously is.

As a game developer, you now have several options :

  • use a game dev library that's not hardware accelerated.
    This may not be a good idea for mobile games, or for games with lots of textures.
  • use an optimized physics library to do the collision checks.
    This may be overkill, or slow down your game, or make the game file size too big.
  • use a game dev library that's hardware accelerated, but store all textures on the CPU as well, so you can do pixel-perfect touch / collision.
    This may not be a good idea since you have to store every texture 2x in memory.
    However, I've come across some nice hacks to reduce the CPU memory needed :


My own solution is a bit different.
Since I have a lot of images on screen at the same time, I wanted something simple. I also realized that I didn't need 'pixel perfect' touch events, but something in between pixel-perfect and bounding box : polygons !
Let me show you what I mean :

Bounding box & polygon.
Bounding box vs. polygon.

As you can see, the polygon is much closer to the real shape of the whale, but still, it only consists of fourteen lines (or fourteen vertices). You can make the polygon more (or less) complex, depending on the needs of your game. Just remember that 'less is more' in this case !
Here you can see the effect of the polygon (as opposed to the bounding box in the first clip) :


Perfect for a hidden object game ! =)

This is how I implemented the polygon idea (sorry, it's a rather long read).

First, I create the art for the game (any software). Whales, in this case.
Next, I import the art (file.png) in a drawing program that can create SVG images (eg/ Inkscape). I add a new layer with the same size as the original image, and draw the polygon for each whale. I try to make sure that the width and height of the polygon and whale are as similar as possible. This way, the midpoints of the polygon and the whale will also be the same (makes it easier to code).
When you're happy with everything, save ONLY the polygon layer as an SVG image. If everything goes well, you should be able to open the file with eg/ Notepad++ (it's basically an XML-file).

Spritesheet & polygon layer. SVG data opened in Notepad++.

The SVG data may look a bit intimidating at first, but don't worry, it's not that complicated. Honest. =)
We're only interested in the stuff inside <path id='name' d='vertices'/> : the name of the image (or subtexture) and a list of the vertices (points that make up the polygon).
The info inside the 'd' attribute has two parts. The first part ('M' : move to) defines the starting point of the polygon, and the second part ('L': line to -> 'Z' : close path) defines the path (the sides of the polygon).
The <g transform='matrix'> elements at the bottom of the file have information about the x, y, rotation, and scale of the polygons. We don't need it.

Since I don't want to process the SVG file when someone is playing the game, I wrote a tiny program to extract the info from the SVG file and store it as a byteArray that will be read when the game starts.
This is the pseudo-code :


/* -- store all information from the SVG file in one array -- */
var info_all_polygons= []; //will contain name + array(vertices)

/* -- read SVG -file -- */
var xml= readXml(SVG file);   (1)
var all_path_nodes= xml.defs[0].path; //first 'defs' element, all 'path' elements

for each(path in all_path_nodes) {
    var name= path.attribute('id');  //_creatures_poly_whale1_poly_0_Layer0_0_1_STROKES
    name= cleanup(name);             //whale1

    var verts_as_string= path.attribute('d');   (2) //M 0 44.55    L 57.85 0 107 ... 0 44.55 Z
    verts_as_string= cleanup(verts_as_string);      //57.85 0 107 ... 0 44.55
    var array_verts_as_string= create_array(verts_as_string);

    var verts_one_polygon= [];	//vertices for one polygon are stored in array (as numbers)			
    for(element in array_verts_as_string) {
        verts_one_polygon.push(element as number);
    }

    /* -- check if polygon is defined in clock-wise rotation -- */
    var is_cw= check_if_cw(verts_one_polygon);   (3)
    if (!is_cw) verts_one_polygon= make_cw_array(verts_one_polygon);

    /* -- store this information in the global array -- */
    info_all_polygons.push(name, verts_one_polygon);
}

/* -- finally : create a byteArray that can be used in-game -- */
create_byte_array(info_all_polygons);


  • Note (1) : the ActionScript3 XML-reader seems to stumble over the xmlns-attribute in <svg xmlns="http://www.w3.org/2000/svg">. I had to remove it manually before I tried reading the SVG file.
  • Note (2) : The Starling framework automatically connects the first vertex of a polygon to the last one. That means that I can just ignore the 'M'-part in the 'd'-attribute !
    Also, sometimes the 'd'-attribute will be missing the final 'z'. Make sure your code takes that into account, or some of your polygons will be broken or missing !
  • Note (3) : the Starling framework wants to receive the polygon vertices in clock-wise rotation only. It seems that drawing programs (at least the ones that I have tried) will define some polygons with CW rotation, and others with CCW rotation.
    If you feed CCW polygons to Starling, sometimes the polygons will be broken !
Broken polygon.
Broken polygon caused by
inconsistencies in the SVG file.

The code that I used to check if a polygon is CW or CCW, is based on information I found on StackOverflow. The method is called 'Sum over edges' : (x2 − x1)(y2 + y1), and it works even for convex shapes (like the whales). It says that if the result of the calculation is positive, the polygon is CW in a NORMAL Carthesian coord system (0,0 at bottom left). Most game code however defines (0,0) at the top left of the screen, so, the result has to be reversed (negative = CW) !
The pseudo-code for the function 'check_if_cw(verts_one_polygon)' looks like this :


/* -- check if a polygon is defined with CW rotation -- */
var area= 0;			
for (var i= 0; i < verts_one_polygon_length; i+= 2) {
    var x0= verts_one_polygon[i];
    var y0= verts_one_polygon[i+1];
    var x1= verts_one_polygon[(i+2) % verts_one_polygon_length]; //wrap
    var y1= verts_one_polygon[(i+3) % verts_one_polygon_length];

    var area+= (x1-x0)*(y1+y0);
}
			
if(area < 0) return true;   //CW (0,0 at top left)
else return false;          //CCW


It's now very easy to convert all CCW polygons to CW polygons. This is the pseudo-code :


/* -- convert a CCW polygon into a CW polygon -- */
var array_verts_cw = [];
for(var i= num_verts_ccw-1; i > -1; i--) {	
    var y= array_verts_ccw[i];
    var x= array_verts_ccw[--i];
    array_verts_cw.push(x,y);
}


When I create the byteArray from the SVG data, I add the following information for each of the polygons :
name, number of vertices, and CW polygon vertices.
The byteArray is then stored in a file that will be read when the game starts up. (Adding the number of vertices makes it easier to read the information back in.)

Once I have the SVG polygon data stored in a byteArray, it's easy to use the polygons in the game code.
I use a class 'HiddenObject' to combine each non-clickable texture (whale) with their matching, clickable polygon.


/* -- set the name of the HiddenObject -- */
this.name= name; 

/* -- set the texture of the HiddenObject -- */
var img = new Image(texture); //the whale
img.setPivot(CENTER);   (1)
img.touchable = false; //texture is non-clickable
add(img);

/* -- set the polygon of the HiddenObject -- */
var polygon = new Polygon(verts_array);
polygon.setPivot(CENTER);   (1)
polygon.alpha= 0; //polygon is not visible, but clickable
add(polygon);

/* -- set the scale and rotation of the HiddenObject -- */
this.scale = scale;   (2)
this.rotation = rotn;


  • Note (1) : Important ! This is how you position the polygon relative to the whale bounding box.
  • Note (2) : Important ! The order in which you set the pivot, scale, rotation, and position of a HiddenObject matters. Just try it out if you don't believe me. =)

I can now easily check mouseOver and mouseClick events on a HiddenObject : the texture itself is not clickable, so we no longer have the bouding box problem. The only thing that is clickable, is the polygon, and the shape of the polygon closely resembles the shape of the whale.
Problem solved. =)