Hit Testing

I thought it was about time I gave an update on my progress with Amberfell. This week I have mostly been relearning linear algebra! I haven’t touched this kind of maths since University and its been refreshing to come back to it although it’s scary how much I have forgotten. The old adage is certainly true: if you don’t use it you lose it.

Before I embarked on reworking all the maths I implemented multiple textures for blocks. You can see in the video that the stone blocks now have green patches on top of them which is the result of my feeble art skills attempting to draw grass. Consider them placeholders for the moment.

Previously I had got block placement working and it was trivial to add block deletion too. However I soon hit a problem: I wanted to highlight the position under the mouse pointer so it was more obvious where the block was going to be placed. This is where the method of detecting the block under the mouse coordinates came unstuck. I had been using a little trick where on a mouse click you redraw the scene around the player but colour each block with a unique colour. I can then test the colour of the pixel under the mouse pointer and derive the block identifier from the colour value. This happens really quickly especially since I turned all lighting effects off and only rendered blocks close to the player and one frame out of 20 per second isn’t noticeable. However it’s not fast enough to cope with continuous mouse movement and the game ground to a halt. I needed a faster way to do it which meant digging into the maths of the 3d projection.

The basic idea is that I needed to turn a pair of coordinates on the screen into a line in the 3d model. If the model was oriented side on then a point on the screen would be mapped to a horizontal line extending into the screen. Because the game world is rotated, tilted and translated from the origin the line also needs to be transformed in the same way. In OpenGL all these transformations are specified by using 4x4 matrices that are applied to everything drawn to convert their positions to a point on the screen. To go from a point on the screen to a position in the world requires the inverse to be done. I was using the simple rotations and translation convenience methods so had to replace them with a direct matrix version. Getting that done was a bit mind-bending as I had to unpick various bits of code, often working in the dark as the world rendered off screen, upside down or at a strange angle. Once I had that all worked out I needed to write code to invert the matrix and apply it to the mouse coordinates. Amazingly that worked first time leaving me with the problem of finding out which block the line from the mouse coordinates hits and on which face. All these algorithms are well known and taught in every introductory 3D Graphics Programming course so I’ve been on a pretty rapid learning curve, made a little harder by porting them to Go as I went (not really onerous, Go is a beautiful language to use – more on that another time).

You can see the results in the video. The red square follows the mouse around whether I move the pointer myself or move the world underneath the mouse pointer. I will change that ugly red square into a nice glowing effect on the block in due course. Now I need to reimplement the block placement and removal.

Permalink: http://blog.iandavis.com/2012/04/hit-testing/


Other posts tagged as amberfell, projects

Earlier Posts