Dr Dave

I previously described an approach to implementing inertia processing by averaging positions to extract velocity from manipulation. However, this approach could result in discontinuous velocities when transitioning from manipulation to inertia.

While implementing multitouch manipulation processing for this project, I "smoothed-out" manipulations using a basic dampened-spring algorithm. Rather than extracting velocity from position, this approach conversely relies on calculating velocities to extrapolate positions. This neatly solves the problem of discontinuous velocities since I always know the correct velocity at the point at which manipulation ends, and is also a much simpler approach.

Using "stiff" springs ensures gestures such as flicks lead to rapidly increasing velocity.

Internet Explorer 9 Beta enables some specific integration features for Windows 7, such as "Site Pinning" to the Taskbar, Start Menu, and desktop (effectively Site Specific Browsers), customising the navigation button colours, and providing Jump Lists. I'll discuss how I've supported each of these features for my Blog Engine.

Icons

A site can be "Pinned" to the Windows 7 Taskbar, Start Menu, and Desktop, for example by dragging the IE9 tab or the address bar icon to the relevant target. The icons used for pinning are defined in the favicon.ico file in the root of the web site. This file contains a number of images at different resolutions which are used for the address bar, tab, browser "Home" button, Taskbar, Start Menu, and pinning the site by dragging the address bar icon.

The icon file is specified in the site.master View using the following tags:

<link rel="shortcut icon" type="image/x-icon" href="/blog/favicon.ico" />
<link rel="icon" type="image/ico" href="/blog/favicon.ico" />

Figure 1. IE9 Beta Taskbar Site Pinning

Navigation Buttons

I set the colour of the back and forward navigation buttons (see Figure 2) to match the color of my current site header with the following tag:

<meta name="msapplication-navbutton-color" content="#303030" />

Figure 2. IE9 Beta header

Jump Lists

I was already passing a ViewModel containing the categories and item counts to the master page, so adding links to each category in a Jump List (see Figure 3) using the following tag structure was trivial.

<meta name="msapplication-task" content="name=Category name (item count);action-uri=/blog/archive/category/Random-Stuff;icon-uri=/blog/favicon.ico" />

Figure 3. IE9 Beta Jump List

Pinning the site to the Start Menu also gives access to the Jump List, as shown below in Figure 4.

Figure 4. IE9 Beta Start Menu Site Pinning with Jump List

In addition to indexing stars and deep sky objects by position, as described in Spatial Indexing Part 1 and Part 2, I added an additional index for magnitude to allow objects to be rendered by brightness.

I wanted to provide a way of automatically adjusting the faintest object visible as the field-of-view is changed, so that a sensible number of objects are drawn, particularly for rendering an appropriate number of labels. In order to consider which algorithm to use, I thought it would be useful to analyse the datasets for stars and deep-sky objects. Figure 1 shows the distribution of magnitude values in the Hipparcos catalog, the majority of which (87%) are in the range from 6-10.

Figure 1. Hipparcos magnitude histogram

In order to automatically select the magnitude for a given field-of-view, I chose first to calculate its fraction of the maximum field-of-view (1), then square this to give the fraction of area of the maximum field-of-view (2).

fov_fraction = current_fov(1)
                 max_fov

area_fraction = fov_fraction2(2)

I assume that the change in brightness is directly proportional to the change in area (3).

brightness_fraction = area_fraction(3)

Apparent magnitude is a logarithmic scale, with magnitude 6 stars defined as being one hundred times brighter than magnitude 1 stars. Hence each order of magnitude is ⁵√100 (approximately 2.512, known as Pogson's Ratio) times brighter (4). I then convert this difference in brightness to a difference in magnitude (5).

brightness_fraction = 2.512magnitude_delta(4)

magnitude_delta = log(brightness_fraction)(5)
                        log(2.512)

Finally I subtract the magnitude difference from the magntiude used at the maximum field-of-view (6). The maximum magnitude for labels can be set slightly below this figure (e.g. by some order of magnitude) so that items appear before their labels.

max_magnitude = 5.0 - magnitude_delta(6)

The maximum magnitude calculated in this manner is shown in Figure 2. Note that the graph tends to the magnitude at maximum field-of-view (magntide 5.00 at 100° in this case). For example, at a field-of-view of 10°, the area fraction of the maximum field of view is 0.01, hence the magnitude difference is -5.00, giving a calculated value of 5.00 + 5.00 = 10.00.

Figure 2. Automatic magnitude by field-of-view

In part 1 I discussed a basic approach to indexing stars and their corresponding labels. I extended this approach further to include deep-sky objects from the NGC catalog. I'll also add the IC catalog, and cross-references to other designations such as Messier number.

In order to cater for orientations of galaxies, I used a textured, indexed quad instead of a point sprite. This enabled me to scale and rotate the texture appropriately. You can see this in Figure 2 with NGC 224 (The Andromeda Galaxy, M31). For the time-being I will use a simple sprite to represent the size, shape and orientation, and will extend this to images in the future.

Figures 1-2. Spatial indexing of stars and deep-sky objects

Strictly speaking, since the deep-sky objects are not point-sources, I should be using an alternative spatial indexing approach, since it is possible for an object to span cells in my simple grid. However, the maximum object size is relatively small in comparison with the grid size so this shouldn't be a practical issue.

I previously described the use of XNA's automatic content deserialization for loading my background stars from the Hipparcos catalog. This catalog contains approximately 120,000 entries, and this step was taking a significant proportion of my start-up time (over 3,000ms on a typical machine).

Shawn Hargreaves recently posted an article on efficiently loading large arrays or lists, which described the use of custom ContentTypeWriter and ContentTypeReader classes to avoid the performance hit caused by reflection.

I implemented these simple classes for my BackgroundStar type, and reduced the load time of this piece of content to approximately 100ms, an improvement of over 95%, which was nice :)

As the number of potentially visible items increases, it becomes less feasible to simply draw all items, and more important to select which items are actually drawn.

In order to avoid checking every object to determine if it should be drawn, an O(n) operation, it is necessary to assign each object with some type of spatial index. In this way, it is possible to determine only which indexes should be drawn and therefore eliminate large "buckets" of objects at once.

Many approaches for spatial indexing exist, and I initially set up a simple project to give me a test framework for different methods. The first approach was to use a simple regular grid based on right-asension and declination. I used an established algorithm¹ for determining which grid cells are visible in a given field-of-view, and used labels for star names as the objects to index (Bayer and Common names are used, with Hipparcos designations added for other bright stars).

Some initial screenshots are shown below in Figures 1-3. The centered circle indicates the reduced field-of-view which is used to calculate which cells to draw (since using the entire viewport would not demonstrate that surrounding objects are culled). The green area indicates the grid cells which are calculated as overlapping the reduced field-of-view, and only labels within this area are drawn.

Figures 1-3. Spatial indexing using a right-ascension/declination grid

One of the drawbacks of using a regular grid based on right-ascension and declination (or any projection involving a singularity at the poles) is that the number of grid cells increases dramatcally around the poles. Other spatial indexing approaches such as a Hierarchical Triangular Mesh² give more consistent areas per cell, and will be explored at a later date now that I have a test framework in place.

¹ "The Zones Algorithm for Finding Points-Near-a-Point or Cross-Matching Spatial Datasets", Jim Gray, María A. Nieto-Santisteban, Alexander S. Szalay, April 2006
² "Indexing the Sphere with the Hierarchical Triangular Mesh", Alexander S. Szalay, Jim Gray, George Fekete, Peter Z. Kunszt, Peter Kukol, and Ani Thakar, August 2005