Two LLNL-led papers win Test of Time awards at 2022 IEEE VIS conference

test of time 110122 (Download Image)

Mark Miller and Peer-Timo Bremer are among the LLNL teams that won SciVis Test of Time awards.

Two Lawrence Livermore National Laboratory-led teams received SciVis Test of Time awards at the 2022 IEEE VIS conference on Oct. 18, for papers that have achieved lasting relevancy in the field of scientific visualization.

Published in 2008, an LLNL-led paper that — for the first time — allowed Digital Morse Theory to be applied to large scale and three-dimensional data, won the 14-year Test of Time award for making a lasting impact to the decades-long application of computational topology to data analysis and visualization at scale.

Based on a new theory the team developed in earlier work, the paper describes a practical framework for computing Morse-Smale complexes (MSCs) — a structure used to extract and visualize features from scalar-valued data — and demonstrated the first full computation of MSCs on large-scale data using a commodity laptop computer. Previously, computing MSCs required extensive memory and compute power, restricting their use to smaller datasets and on high-performance computers.

The algorithm the team developed uses a “divide-and-conquer” strategy to allow for memory-efficient, topology-based analysis of large-scale data of various formats and all dimensions to be done on standard, off-the-shelf computers. The SciVis awards committee noted the paper has driven deep algorithmic improvements and still receives consistent support from the Department of Energy as an approach needed for exascale analysis. It also continues to have important applications at LLNL, including potential uses at the National Ignition Facility and High Explosives Applications Facility.  

“In this paper, the authors resolved massive complexity in the existing techniques by applying a simple discrete model of gradient analysis that could readily be computed at scale,” the committee said. “Cited 231 times, this paper made multiple further developments feasible and established Morse-Smale complexes as a first-class tool in the kit of techniques we apply to data and continues to be relevant to anyone working with topological visualization.”

Co-authors included first author Attila Gyulassy, who was a student in LLNL’s Student Graduate Research Fellowship program at the time, current LLNL computer scientist Peer-Timo Bremer, Bernd Hamann of the University of California, Davis (UC Davis) and former LLNL computer scientist Valerio Pascucci, who is now the director of the Center for Extreme Data Management Analysis and Visualization at the University of Utah.

“This work selected marked a point in time where we begin to embrace discrete methods for topology computation,” said Gyulassy, who accepted the award on behalf of the team. “I was born as a graduate student into this academic family of movers and shakers combining the superpowers of UC Davis and Lawrence Livermore National Lab. They had a vision to take what had been described mathematically and see its potential for visualization and analysis. With the perspective of age, I’m amazed at their courage to entrust a graduate student with a hard problem and give them the freedom to pursue it.”

LLNL’s Bremer said the paper was the culmination of work that began with “a fundamental mathematical theory and ended in eminently practical and scalable algorithms.”

“For me, the most exciting aspect of the work is that it demonstrates the value of having a discrete equivalent of the theory that could be implemented exactly, rather than working with previous approaches that relied on numerical approximations,” Bremer said. “While it took roughly eight years to finally develop a practical 3D framework, the results have been applied to countless use cases, and we continue to extent and deploy related technologies at the Laboratory today.”

ROAM around the world with improved terrain visualization

The SciVis 25-year Test of Time award went to a paper co-authored by former LLNL senior scientist Mark Duchaineau and current LLNL computer scientist Mark Miller, who has helped develop numerous scientific database, visualization and data modeling technologies at LLNL. Several Los Alamos National Laboratory (LANL) researchers also appear as co-authors.

Published in 1997, the team’s paper describes a method for terrain visualization called Real-time Optimally Adapting Meshes (ROAM), in which triangles are split and then merged to optimally add or remove detail, allowing for meshes to be rendered at high frame rates and maintain high performance for terrain visualization. The method also added advanced optimization techniques such as incremental triangle stripping and priority-computation deferral lists, which are still in use today. The technique made it possible to produce accurate images of large datasets at high frame rates and compute more triangles with less CPU work, researchers said.

“Most of the ideas lived on,” Duchaineau said during his acceptance speech. “My colleagues and I were delighted to see how these ideas spread and were extended and adapted in so many ways.”

At the time, the team’s challenge was to help make a “holodeck,” a virtual reality environment, for an F/A-18 warplane. LANL researchers needed to hang an F/A-18 in a large anechoic chamber and operate its radar “normally,” according to LLNL’s Miller, who worked with Duchaineau as a Ph.D. student at the University of California, Davis in the 1990s. The chamber captured radar pulses and a high-performance computing application synthesized the radar returns in real time to convince the sensors that the plane was flying over real terrain.

“Hierarchical compression of the terrain database was essential and became the topic of my dissertation research,” Miller said. “The ROAM work, led by Duchaineau at LLNL and a team at LANL, substantially improved upon my earlier work, defining a better triangulation algorithm with improved continuity properties, well-defined split and merge operations and the ability to satisfy a dynamic objective function — line of sight to key terrain features, for example.”

The “ROAMing Terrain” ideas have impacted many applications in the years since the paper’s publication, especially within the gaming community. Award committee chair Kelly Gaither, who presented the team with the award, noted the paper addressed the need for effective tools to render terrains efficiently as satellite and other remote-sensing data began flooding in the 1990s.

“Cited over 1,400 times, this paper solved many of the outstanding issues by introducing split-merge operations for triangle bintrees, guaranteeing mesh consistency in a simple and elegant fashion,” Gaither said. “The work introduced in this paper profoundly influenced the state of the art for terrain rendering in films, games, flight simulation and remote sensing and continues to influence research efforts today.”

Co-authors included Murray Wolinsky, David Sigeti, Charles Aldrich and Mark Mineev-Weinstein of LANL.

The annual IEEE VIS conference, held this year in Oklahoma City, is billed as the premier forum for advances in visualization and visual analytics, bringing thousands of researchers and practitioners from universities, government and industry together to exchange recent findings on the design and use of visualization tools, according to the conference’s website. It is composed of three sub-conferences (VAST, InfoVis and SciVis). For 2022, SciVis handed out 14-, 15- and 25-year Test of Time awards.

The award recognizes articles published at previous conferences whose contents are still vibrant and useful today and have had a major impact and influence within and beyond the visualization community.

The awards committee based their decisions on number of citations, quality and longevity and influence of ideas, outreach, uptake and effect, not only in the research community but also within application domains and visualization practice.

For more on the awards, visit the Vis 2022 website.