The
time-accurate value-scattering process (SCAP) is
the bottleneck of the UFLIC
(Unsteady Flow Line Integral Convolution) [60]
pipeline while a large amount of Euler pathline integration is computationally
expensive due to intensive temporal-spatial vector interpolation and line-segment
clamping against pixels. In order to obtain a dense scattering coverage
to exploit sufficient temporal-spatial coherence, UFLIC uses a conservative
seeding scheme by which a seed is released from each pixel center at the
first integer time step of each SCAP. Such a regular seed pattern does not
take into account flow structures and particles are too dense in converging
regions. Also, a pathline is always advected from scratch and is deleted
when the life span expires. This simplistic use of pathlines ignores intra-SCAP
and inter-SCAP correlations, which induces severe pathline redundancy. AUFLIC
(Accelerated UFLIC) adopts a flow-driven seeding strategy (Figure
1) by introducing spatial flexibility (i.e., a seed may not
necessarily be released exactly from a pixel center as long as the seed
is within the pixel) and temporal flexibility (i.e., a seed may not
necessarily be released exactly at an integer time step; instead it may
be released at a fractional time shortly after the SCAP begins). Also, AUFLIC
employs a fourth-order Runge-Kutta integrator with adaptive step size and
error control in combination with cubic Hermite polynomial curve interpolation
to achieve faster, more accurate pathline advection, and faster line convolution
(due to evenly sampling the texture) than the Euler method. |

The temporally-spatially flexible seeding
strategy used in AUFLIC allows for a flow-aligned seed distribution by which
only a few (sparsely placed) seeds need pathline integration while most
seeds are placed along the pathlines advected at earlier times by other
seeds upstream and therefore the known pathlines can be copied in the same
SCAP and reused between SCAPs, with pathline integration substantially reduced,
for fast value scattering. Pathline copying is an intra-SCAP operation
by which a seed's trace in the life span is used, with only minor corrections,
for those of other seeds successively released at several positions downstream
along the known trace at fractional times shortly after the SCAP begins
as long as they are released at the same time as the initial seed travels
through their seeding positions. Each of these seeds travels through a different-length
part of the same curve during the first time step of the SCAP, but they
synchronously run though the same trace over the remaining time steps. Pathline
reuse is an inter-SCAP operation by which the position a pathline passes
through within a fractional time into the second time step of the previous
SCAP is used to release a new seed at exactly the same global time, but
in the first time step of the current SCAP. This seed's trace is obtained
by reusing the latter part of the known pathline from the previous SCAP,
appended with integration over an additional time step. Pathline copying
applies whether a pathline is obtained by reuse or brute-force integration.
To fulfill the flow-driven seeding strategy for a dense scattering coverage
at a low computational cost and maintain a nearly constant frame rate, a
dynamic seeding controller is used in AUFLIC to decide
whether a pathline is advected from scratch, copied from that of another
seed in the current SCAP, reused from the last SCAP, saved for the next
SCAP, or finally deleted. Table 1 gives a comparison
of UFLIC and AUFLIC. |