Biarc Interpolation

Interpolating between two points comes up all the time in game development. Most of the time, only a simple linear interpolation is needed. Linear interpolations are great because you can't really get them wrong. There is only one possible line connecting the points. Just follow it. When a curved interpolation is required, the solution gets far more complicated. There are an infinite number of curves to choose from and many methods for generating them: NURBS, Catmull-Rom, Bézier, Hermite, etc. I want to discuss a less common method that will generate circular shaped arcs.

Continue reading...

Printing Floating-Point Numbers - Part 4: Results

I knew this was going to be a difficult problem from the start, and it has lived up to the challenge. One of my initial concerns was how complicated the code would get to make it run at an acceptable speed. It started off terribly slow, but I'm happy to say it has arrived in a good place. Let's discuss the accuracy, performance and any considerations that should be made before using this implementation. You can also find a link to a simple demo project at the bottom of the page.

Continue reading...

Printing Floating-Point Numbers - Part 3: Formatting

We have written an implementation of the Dragon4 algorithm that can be used with both 32-bit and 64-bit floating-point numbers. However, the inputs and output to Dragon4 are not as user friendly as we need. Thus, we're going to create two user facing functions. One will print a supplied 32-bit float to a buffer and the other will print a supplied 64-bit float to a buffer.

Continue reading...

Printing Floating-Point Numbers - Part 2: Dragon4

So far, we've covered enough background to start diving into the real code. To get started, we need to write some high-precision arithmetic. Luckily we only require a subset of operations: comparison, addition, multiplication, exponentiation, division, and a bitwise shift.

The performance of what we write here will have a large impact on the overall algorithm. When I first got Dragon4 up and running, I was using a very C++ friendly public-domain big integer class that I found online. After everything was functional, I rewrote my own big integer code specifically tuned to the task at hand and performance increased over one hundred fold. That's not to say this is as optimized as possible, but it should be fast enough for production use.

Continue reading...

Printing Floating-Point Numbers

As far as I could find (as of today - March 5, 2014), there are only two open source implementations of floating-point to string conversion that are efficient, accurate and output "pretty" results. The code can be hard to follow and the licenses are a little more restrictive than I prefer. As an everyday tool that is often taken for granted, it might be surprising that it is so rarely implemented, but it's actually nontrivial to solve. It's also one of those problems complex enough where a wise engineer might recommend that "you never write your own", but I like a challenge and have been interested in it for a while. After spending a couple weeks investigating and experimenting, hopefully I can make it a bit more digestible for the curious.

Continue reading...