Sabbatical Log: November 3rd

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

It’s the weekend, so I’m doing mostly social stuff and not coding. However, I have gotten started on a rough implementation of the Separating-Axis-Theorem with some tweaks to handle polygons in motion. I’m thinking I’ll avoid, at least in the final implementation, floating point and instead do a poor man’s fixed point by scaling everything by a large constant multiple.

I went down something of a rabbit hole on the fixed point representation, as I realized that a lot of the code I’d written for collision detection was using integers… that rapidly rounding to 0, causing explosions.

The most interesting bit on the fixed point representation (which is just a struct wrapped around a long, where the “raw value” is multiplied by 2^20 before storage) has been working out how to implement all the operations:

• Addition (c = a + b) is straight forward
  • c * 2^20 = a * 2^20 + b * 2^20
• Ditto for subtraction (c = a – b)
  • c * 2^20 = a * 2^20 – b * 2^20
• Multiplication (c = a * b) is trickier because
  • a * 2^20 * b * 2^20 = (a * b) * (2^20)^2
  • So I divided by 2^20 at the end to correctly calculate c
• Division (c = a / b) is likewise tricky, as
  • (a * 2^20) / (b * 2^20) = a / b
  • Even worse, this loses precision
  • So I multiply by 2^20 before dividing, correctly calculating c
  • This can still lose precision at the high end, but I’m expecting most numbers to be much less than int.MaxValue. Perhaps I’ll throw on that case in the future.
• Square root (c = a^(1/2)) is also rather tricky
  • First, I’ve got to actually implement a square root algorithm without using built-in floating point
  • I stole the iterative algorithm from Wikipedia
  • Using it, I calculate ((2^20) * a)^(1/2) = 2^10 * (a^(1/2))
  • I then multiply by 2^10 to get the desired result.

My implementation seems good to about 3 decimal places, and while I’m sure I’ll have to do some performance work (probably using lookup tables for common square roots) I’m pretty happy with it – I’ve got a small test verifying the above operations.

Continue onto November 4th