Improvements in Path Tracing in VTK

Given vector fields, or time-varying vector fields (flow fields), a common visualization approach is to “release” a set of particles into the vector field, move them according to the vectors, and observe their paths of travel. Specifically,
•  Streamlines are paths taken by particles in a vector field.
•  Pathlines are paths taken by particles in a flow field.
•  Streaklines are curves created by releasing particles
continuously into a flow field at fixed seed positions and connecting the particles released from common
seed positions.

We have improved path tracing support in VTK:
•  Created a faster parallel algorithm for streamline tracing.
•  Improved usability of particle tracing filters for flow fields.
•  Added a new filter to create streaklines.

Faster Parallel Streamlines
The previous parallel algorithm for stream tracing is very simple and has the same asymptotic running time as the sequential algorithm. We have replaced it with a more sophisticated algorithm that scales reasonably well according to the number of processors. The algorithm starts by dividing the seed particles between the processes according to the data; each process then traces the streamlines one by one, and, in between, sends and receives particles that travel between processes. For AMR data, by using the metadata information, the particles can be sent to exactly the right processes; for other types of data, the particles are iteratively forwarded to the process next in MPI rank until they arrive at the right processes.

The algorithm is implemented by the class vtkPStreamTracer, which previously existed as an abstract super class. The child class vtkDistributedStreamTracer is depreciated. Conveniently, thanks to the VTK modular changes, the user does not have to decide whether to use vtkStreamTracer or vtkPStreamTracer depending on the presence of MPI; the object factory will instantiate a vtkPStreamTracer object whenever MPI is enabled.

In experiments, we observed that the algorithm scales reasonably well by the number of processes. Figure 1 shows the output of the parallel stream tracer, with an AMR Flash input dataset from an astrophysics simulation. The data set is 24G and distributed over eight machines with eight cores each. The colors of the trace lines are mapped to the processor ids.

Figure 1: Parallel Stream Tracer with AMR Flash Input Dataset

Easier-to-Use Particle Tracing
Previously, the main algorithm for performing particle tracing for flow field data was implemented in the class vtkTemporalStreamTracer [1]. This algorithm moves a set of particles one time step at a time according to a linearly-interpolated velocity field. It also supports parallel execution using MPI. In this work, we kept the algorithm mostly intact but focused on resolving a set of usability issues. Because the algorithm always takes one time step, the user has to manually step through the time steps by incrementing the time step parameter starting from zero and calling update(). Not starting from zero, skipping time steps, or decreasing time steps all result in errors. If particle paths are desired then the user has to connect an additional filter, vtkTemporalPathLineFilter, to run in tandem. The parallel support for vtkTemporalPathLineFilter is incomplete; it leaves gaps from particles hopping between processes. There is no streak line support.

We refactored the original vtkTemporalStreamTracer into two new classes, vtkParticleTracerBase and vtkPParticleTracerBase, for the serial and parallel version. We also augmented the original algorithm to internally step through the time steps from the user-defined starting time until the termination time. To be efficient, the new algorithm caches output so that if the only parameter and input change is the increased termination time, then a new run can start from the previous termination time instead of all the way from the starting time. Changing any upstream pipeline or any other parameters would invalidate the cache.

We created three new particle tracing filters that all can be used on their own. These filters are derived from the base class previously described and essentially do the same thing; they move a set of seed particles from the starting to termination time, but the outputs are different:

vtkParticleTracer/vtkPParticleTracer: The outputs are the particles at the termination time. In ParaView, we expect the user to use this filter to animate the moving particles. Therefore, the termination time is not exposed on the GUI. Rather, it is updated according to the pipeline time (vtkStreamingDemandDrivenPipeline::UPDATE_TIME()), which can be changed using the animation controls.

vtkParticlePathFilter/vtkPParticlePathFilter: The outputs are a set of polygonal lines representing the paths particles took.
vtkStreaklineFilter/vtkPStreaklineFilter: The outputs are a set of polygonal lines representing the streaklines.
Figure 2 shows the three particle tracers running on a dataset of ten time steps.

Figure 2: From left-to-right: a snapshot of particle tracing; pathlines; and streaklines. The colors are mapped to the magnitude of the velocity vectors.

Acknowledgement
We would like to thank Paul Sutter and Mohamad M.
Nasr-Azadani for providing the data used to produce the images used in this article.

References
[1] John Biddiscombe, Berk Geveci, Ken Martin, Kenneth Moreland, David Thompson: Time Dependent Processing in a Parallel Pipeline Architecture. IEEE Trans. Vis. Comput. Graph. 13(6): 1376-1383 (2007)

Yuanxin “Leo” Liu joined the Kitware team in January, 2012 as an R&D engineer. Prior to joining Kitware, he was a senior R&D software engineer at Geomagic Inc. and developed algorithms to process point clouds and polygonal meshes.