Wednesday, August 20, 2008

Asteroid Excess

We're about ready to start the final testing of the "Pro" version of SkyTools. There are just a few loose ends left to tie up, such as the new serial number code, enhancing the installer, etc.

Oh, and all those pesky asteroids.

When I first wrote the asteroid code for SkyTools there were between 8000 and 9000 known. By the time SkyTools 2 came out there were so many that I only put the first 10,000 numbered asteroids on the CD because there wasn't enough room for them all. Today there are nearly 200,000! That's so many that drawing asteroids on a chart is really bogging down.

Here's how the asteroids that are shipped with SkyTools work: asteroids use osculating elements, which are a sort of cheat. These elements would describe the orbit of the asteroid perfectly if there were no other bodies in the solar system. But with all those other asteroids and planets out there the reality is that each asteroid gets tugged around over time, changing its orbit. So the orbits we use are sort of freshness dated. They are good for about 40 days. What I do is run whats called an "n-body" program that carefully computes the position of each asteroid over many years, including all the tugging. Every 40 days a new set of orbital elements are generated. When you ask for the position of an asteroid SkyTools finds the set of elements closest to your time and uses it to compute the position.

The supplemental asteroids, which are downloaded over the web, work in much the same way. Each new set of elements you download gets added to the database. Over time you will build up a database that covers months and even years.

This all works pretty well, except for how long it can take to run through the nearly 200,000 asteroids sorting out the ones bright enough and within the bounds of your chart. Fortunately I had an idea come to me in the middle of the night a few months ago. It's one of those ideas that I would really like to claim is perfectly brilliant, yet it's so obvious I probably really ought to be ashamed I hadn't thought of it before.

The idea is to store a set of positions and magnitudes along with the orbital elements for each asteroid. Since the elements are only used for a known 40-day period we can compute a list of positions over that period (using the elements). When we want the position we interpolate to get a good idea of the position and magnitude of the asteroid. Only if the asteroid is on the chart do we go ahead and compute the accurate position. Interpolation is cheap so the end result is that the asteroids plot a lot faster. How much faster, I'm not quite sure yet. But I expect it to speed things up a lot.

Unfortunately there is a downside. The positions stored with the elements have to be pre-computed. I just tried downloading and pre-computing all the known asteroids and it took a whopping 8 minutes on my aging computer. In fact, that's why I'm writing this. I'm running another test and it's a long wait...

Fortunately I have some ideas for speeding it up!

P.S. I tested the new asteroid code and it is 12x faster!