Lagrangian coherent structures and trajectory similarity: two important tools for scientific visualization

Chen, Mingcheng

Permalink

https://hdl.handle.net/2142/90512 Copy

Description

Title

Lagrangian coherent structures and trajectory similarity: two important tools for scientific visualization

Author(s)

Chen, Mingcheng

Issue Date

2016-04-08

Director of Research (if dissertation) or Advisor (if thesis)

Hart, John C.

Doctoral Committee Chair(s)

Hart, John C.

Committee Member(s)

• Padua, David A.
• Olson, Luke
• Shadden, Shawn C

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• unsteady flow
• unstructured mesh
• GPU
• parallel algorithms
• trajectory similarity
• trajectory clustering
• dynamic programming
• lagrangian coherent structures

Abstract

This thesis studies the computation and visualization of Lagrangian coherent structures (LCS), an emerging technique for analyzing time-varying velocity fields (e.g. blood vessels and airflows), and the measure of similarity for trajectories (e.g. hurricane paths). LCS surfaces and trajectory-based techniques (e.g. trajectory clustering) are complementary to each other for visualization, while velocity fields and trajectories are two important types of scientific data, which are more and more accessible by virtue of the technology development for both data collection and numerical simulation. A key step for LCS computation is tracing the paths of collections of particles through a flow field. When a flow field is interpolated from the nodes of an unstructured mesh, the process of advecting a particle must first find which cell in the unstructured mesh contains the particle. Since the paths of nearby particles often diverge, the parallelization of particle advection quickly leads to incoherent memory accesses of the unstructured mesh. We have developed a new block advection GPU approach that reorganizes particles into spatially coherent bundles as they follow their advection paths, which greatly improves memory coherence and thus shared-memory GPU performance. This approach works best for flows that meet the CFL criterion on unstructured meshes of uniformly sized elements, small enough to fit at least two timesteps in GPU memory. LCS surfaces provide insight into unsteady fluid flow, but their construction has posed many challenges. These structures can be characterized as ridges of a field, but their local definition utilizes an ambiguous eigenvector direction that can point in one of two directions, and its ambiguity can lead to noise and other problems. We overcome these issues with an application of a global ridge definition, applied using the hierarchical watershed transformation. We show results on a mathematical flow model and a simulated vascular flow dataset indicating the watershed method produces less noisy structures. Trajectory similarity has been shown to be a powerful tool for visualizing and analyzing trajectories. In this paper we propose a novel measure of trajectory similarity using both spatial and directional information. The similarity is asymmetric, bounded within [0,1], affine-invariant, and efficiently computed. Asymmetric mappings between a pair of trajectories can be derived from this similarity. Experimental results demonstrate that the measure is better than existing measures in both similarity scores and trajectory mappings. The measure also inspires a simple similarity-based clustering method for effectivly visualizing a large number of trajectories, which outperforms the state-of-the-art model-based clustering method (VFKM).

Graduation Semester

2016-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/90512

Copyright and License Information

2016 by Mingcheng Chen. All rights reserved.

Owning Collections