Hit detection on graphics primitives: Speeding up the Parallel Coordinates Plot

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…

  1. 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.

  2. 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.

  3. 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:

  1. The first bitmap contains a line for every item, regardless of selected or rolled over status.
  2. 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.
  3. The third bitmap shows only the selected items.  Similarly, this is rendered on top of the second bitmap to achieve the same effect.
  4. 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.

This entry was posted in BirdEye, Flex, Information Visualization. Bookmark the permalink. Both comments and trackbacks are currently closed.

7 Comments

  1. Posted February 20, 2009 at 12:07 am | Permalink

    what a brilliant idea 🙂

  2. Posted February 20, 2009 at 12:52 am | Permalink

    @Tom I actually saw Krist do something similar to this a while back, so I knew it could be pulled off. I’m glad this worked out as a proof of concept. Let’s hope we see it in Degrafa some day soon.

  3. iq
    Posted February 21, 2009 at 10:01 am | Permalink

    Excellent component..With the changes in performance, it’s good for any major application. We appreciate the time you spend and the idea for this.

    Have you ever thought of making the node of the links bigger so when multiple lines intercept the size can be made bigger..

    see the second diagram in the “sample pictures” in the below link
    http://secviz.org/content/applied-security-visualization/

    thanks
    .iq

  4. pp
    Posted February 26, 2009 at 7:59 am | Permalink

    > Tom

    This technique is quite common and used often in game programmings.
    I see many flex/flash apps using this tech.

  5. Posted May 19, 2009 at 3:14 pm | Permalink

    Thank you for this great article.

    To summarize my understanding: you are using 4 screens of bitmaps and you are mapping clicks/mouse positions to offscreen bitmap intersections.

    Does this scale with large display areas?
    Why not map onscreen positions to the data model directly? And have one offscreen bitmap for difference rendering only?

  6. Posted May 22, 2009 at 11:48 pm | Permalink

    @Thomas The Flash Player is really good at bitmap operations. Mapping screen positions to data values in either a hash or an array would most likely be much slower than relying on bitmap methods, and it would be tedious to correctly populate such a data structure. At 2880 x 2880, this method still performs very quickly.

  7. Posted December 11, 2009 at 1:49 pm | Permalink

    Parallel Coordinates – This book is about visualization, systematically incorporating the fantastic human pattern recognition into the problem-solving …
    http://www.springer.com/math/cse/book/978-0-387-21507-5