In my last post I mentioned that I had rewritten the Parallel Coordinates Plot to achieve a pretty drastic speed up. Before I get into the graphics hit detection trick at the heart of the performance boost, I’d like to explain the problem with the original implementation. The main thing that dragged down the first version was the fact that each line drawn on the plot was handled by a separate UIComponent. I knew that that was bad idea going in, but I went with it anyway. My reasons for subclassing UIComponent were pretty weak…
- I wanted to take advantage of invalidation.In most cases Parallel Coordinates Plots contain hundreds, if not thousands, of lines. The overhead involved in instantiating and validating thousands of UIComponents outweighs the programming convenience provided by invalidation, especially when all you really want to do is draw a line.
- I wanted the lines to have tool tips.It’s great that UIComponents have tool tip functionality built right in, but again, it’s foolish to take advantage of the niceties of UIComponent at the cost of performance. The ToolTipManager exists for a reason.
- I wanted to allow the user to draw anything they wanted between the axes.Honestly, Parallel Coordinates Plots are crowded enough by default. I can’t think of a single thing a user would want to do aside from changing the color and thickness of the lines.
So for the most part I made the decision out of laziness. When I started cleaning up the code to migrate it into BirdEye, I realized that I would have to rewrite the Parallel Coordinates Plot altogether if it was going to be useful to anyone.
Cutting out the bloat
With the overhead of UIComponent mind, it might seem reasonable to just make each line a Sprite and manage rendering manually. Unfortunately, that probably wouldn’t scale nicely either. Sprites are lighter than UIComponents, but adding thousands of Sprites to the display list and running graphics operations on them is still a tall order.
Drawing all of the lines to a single Sprite’s graphics property is straightforward enough, but all those graphics operations wear noticeably on performance. This is the option I ultimately went with, so to get around the performance problem I store the results of the graphics operations to a BitmapData using the BitmapData.draw method and then render the BitmapData to the screen using Graphics.beginBitmapFill.
Unfortunately, this leaves the lines completely non-interactive. They’re not DisplayObjects anymore, so they can’t dispatch the mouse events needed to support roll over and selection. But wait…
Supporting bitmap interactivity using picking techniques
3D engines have to deal with this problem all the time. When you click on the screen in an OpenGL application, the app knows the coordinates of the cursor, but the developer still has to do some leg work to figure out which 3D object those coordinates refer to. There are a number of techniques used to solve this “picking” problem. One technique is to render the 3D scene twice: once normally and once with each 3D object colored with a unique color. The first rendering is presented to the user, while the second is kept invisible. When the user clicks on a pixel in the first rendering, the program looks up the color at the cooresponding coordinates in the second rendering. Since the colors are uniquely mapped to the 3D objects, this program can determine which object was clicked based on that color.
This is the same technique that the new Parallel Coordinates Plot uses to determine what the user is interacting with. Each line segment is uniquely identified by two fields and the values in those fields; the fields determine the x coordinates of the line segment’s endpoints and the values determine the y coordinates.
The Parallel Coordinates Plot maintains a hash mapping those four properties to unique colors. When the user clicks on the component, the color under the pointer is extracted, the hash is queried, and the items that match the field-value pairs are returned. In the full implementation there are four bitmaps used in all:
- The first bitmap contains a line for every item, regardless of selected or rolled over status.
- The second bitmap only shows lines for rolled over items. This bitmap is rendered on top of the first bitmap, masking the fact that every item is actually rendered in the first one.
- The third bitmap shows only the selected items. Similarly, this is rendered on top of the second bitmap to achieve the same effect.
- The invisible fourth bitmap used for picking.
It may seem redundant to render lines more times than absolutely necessary, but the extra steps let the Parallel Coordinates Plot save in the long run. It only needs to redraw the lines that have changed from one moment to the next. If the contents of the data provider and the width and height remain constant, the first bitmap only needs to be drawn once.
When it all comes together, the Parallel Coordinates Plot looks like this under the hood:
but the user sees this:
I’ve put together an example that demonstrates the new and improved Parallel Coordinates Plot. I didn’t run any metrics to try and compare the performance with the older sample I put together, but in terms of responsiveness, the new version blows the old one out of the water. The source for the new sample is available here. The color hashing occurs within the internal FieldValuePairColorHash class at the bottom of the ParallelCoordinatePlot class.
