Friday, October 02, 2015

High-performance Visualization of Neurons, Molecules, and Other Graph-Like Models Using Quadric Imposters

 In my day job in scientific visualization, I am sometimes called upon to display models of neurons or molecules. Both types of models are "graph-like", in the computer science data structure sense, in that they consist of a collecion of Nodes, connected by Edges.

General Graph data structure. This graph consists of six edges and seven nodes.

In the case of molecules, the Nodes are Atoms, and the Edges are Bonds. Molecules and atoms make up all of the air and earth and animals and tacos and all the other stuff of the world.

This serotonin molecule contains 24 atoms and 26 bonds. This representation uses spheres and cylinders to represent atoms and bonds.
In the case of neurons, the Edges are piecewise linear segments of neurites, and the Nodes are branch points, tips, and bends of those segments. In both molecules and neurons, the Nodes have an XYZ location in space, and a size. These Nodes are usually well represented by spheres of a particular size.

This neuron has many branch points, tips and bends. Neurons are the cells that animals use to think and to control movement.
In the past few years, I have been very interested in using Quadric Imposters to represent scientific models. I have been able to achieve very high-performance rendering, while attaining flawless image quality. By high-performance, I mean that I am now able to display models containing hundreds of thousands of nodes, with flawless performance, compared to perhaps only thousands of nodes using traditional mesh-based rendering methods.

Imposter models look better and run faster. What's not to like? The only downside is that it requires a lot of tricky work on the part of the programmer. Me.

You probably learned the quadratic formula in high school:

In any case, the quadratic formula can be used to solve for \(x\) in polynomial equations of the form:

So the trick for imposter rendering is to derive a quadratic polynomial for each analytic shape you want to display. I have already done this and have it working for the following shapes:
  • Sphere (easiest)
  • Cylinder
  • Cone
I wrote a little about sphere imposters in the past.

I plan to eventually do the same treatment for
  • Ellipsoid
  • Ellipsoid cylinder
  • Ellipsoid cone
  • Single sheet hyperboloid
  • Dual sheet hyperboloid
By the way, I just now started using  MathJax for displaying equations. The equations look nice, right?