Robust Parity Test for Extracting Parallel Vectors in 3D
Fundamental primitives for visualizing 3D data include line features like ridges and valleys of a scalar field, stream lines of a vector field, vortices of a velocity field, and extremal curves of a tensor field. Parallel Vectors (PV) provide a unified representation of 3D line features, forming continuous 3D curves without open ends or branching. Computing PV involves working on a 3D cellular grid and connecting seed points on a cell face to create closed curves. Various methods like analytical solutions, iterative root-finding, and boundary sampling are used for seeding PV points. The contribution highlighted is a correct test for the parity of PV points on a cell face, requiring samples only on the face border and applicable to arbitrary continuous vector fields.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
A Robust Parity Test for Extracting Parallel Vectors in 3D Tao Ju, Washington University in St. Louis Minxin Cheng, Xu Wang, Ye Duan, University of Missouri in Columbia
Line Features Fundamental primitives for visualizing 3D data Ridges and valleys of a scalar field Stream lines of a vector field Vortices of a velocity field Extremal curves of a tensor field
Parallel Vectors (PV) A unified representation of 3D line features [Peikert and Roth] Given two vector fields ?, ? A parallel vector (PV) point is where ?, ? are (anti-)parallel ? ?? = ? ? ? ? ? ? = 0}
Parallel Vectors (PV) A unified representation of 3D line features [Peikert and Roth] Given two vector fields ?, ? A parallel vector (PV) point is where ?, ? are (anti-)parallel PV points form continuous 3D curves No open ends or branching Wherever ?, ? are continuous ?? = ? ? ? ? ? = 0}
Computing PV Typically working on a 3D cellular grid Locate seed points on a cell face Connect the seeds by straight segments or curve tracing
Computing PV To create closed curves, the total number of seeds in a cell needs to be even. A sufficient condition: the number of seeds on each cell face match the parity of the number of true PV points
Seeding - Review Analytical solution of PV points Accurate, but only available for linear fields ?, ? Iterative root-finding [Roth 00, Theisel 05, Sukharev 06, Pagot 11] Could miss true PV points Requires face subdivision (more computation) Boundary sampling [Guy 97, Tang 98, Mann 02, Pollock 13] Less accurate then root-finding
Our contribution A provably correct test for the parity of PV points on a cell face Only needs samples on the face border Works for arbitrary continuous vector fields ?, ? Odd #PVs! ? ?
Observation: PV points as critical points ? (cell face) is any genus-0 surface with boundary Map ? to a spherical patch ?, so that ? maps to ? ? = ?(?) ?(?) = ?(?) ?(?) is tangent to ? at point ?(?) ? ?(?) ?(?) ? ?(?) ?(?) ?(?) ? ? is a PV point on ? if and only if ?(?) is a critical point of ? on ?
Theoretical Foundation Consider a vector field ? over a surface Index: number of 2? ccw rotations made by ? around a point 0 for a regular point 1 for a stable critical point ? Index: 0 Total indices over the surface has the same parity as the number of stable critical points Index: 1 Index: -1
Theoretical Foundation Consider two vector fields ?1, ?2 along a curve ? on the surface Turning ???1,?2: Align the surface tangent frames on ? using ?1 Total rotation angle of ?2 along ? in the aligned frames. ? ?1 ?2 ??????? ?2 ?1
Theoretical Foundation Morse Index Theorem (generalized Poincare-Hopf) ?: smooth genus-0 surface with boundary ?? ?: continuous vector field over ? =???(?,?) 2? ? Total indices of ? on ? + 1 ? (?:tangent field of ??) ?? ?
Theoretical Foundation Challenge: our spherical patch (?) may be only piece-wise smooth Some pieces are oriented outward the sphere, others inward They meet at ?0 creases ?? ? We present a variant of Morse theorem that works for piece-wise smooth spherical patches Outward Inward
Theoretical Foundation A vector field ? along a surface curve ? is parallel, if ? has zero derivative in the tangent frames of ?. Can be generated from any initial vector ?0at one end of the curve using parallel- transport parallel field ? ?0
Theoretical Foundation Gauss-Bonnet Theorem ?: smooth spherical patch ????,? = ?? 2? ? ?:tangent field of ?? ?:any parallel field on ?? ??:signed area of ? ?? ? ?
Theoretical Foundation Combining Morse and Gauss-Bonnet ?: smooth spherical patch ?: continuous vector field over ? ? ? =????,? + ?? 2? Total indices of ? on ? ?? ? ?:any parallel field on ?? ??:signed area of ?
Theoretical Foundation Relaxing smoothness condition ?: piece-wise smooth spherical patch ?: continuous vector field over ? ? ? =????,? + ?? 2? Total indices of ? on ? ?? ? ?:any parallel field on ?? ??:signed area of ?
Theoretical Foundation Using only boundary information (our Parity Test) ?: piece-wise smooth spherical patch ?: continuous vector field over ? ? ? ????,? + ?? 2? Total indices of ? on ? (??? 2) ?? ? ?:any parallel field on ?? ? :any spherical patch bounded by ?? ?
Discretization Sampling ?, ? on the boundary of ? Compute { ??= ??/ ??,??= ?? ??} Adaptive subdivision ensures slow change in ??,??. ? ?? ?? ?? ?? ??
Discretization ?0 ????,? + ?? 2? Continuous: ?? ??+1 ?? ?? ??+1 ?? ?? ?? + ?? 2? ?? Discrete: : parallel-transport of ?? ?? ?0: an arbitrarily chosen pole
Examples ? ????,? = 3.04 ????,? = 3.28 ?? = 9.53 ?? = 9.57 ?? ?? ? ????! ???!
Validation & Comparison A synthetic field with known PVs
Truth Alg. Validation & Comparison Odd Even Odd Odd Odd Even Comparison of parity tests (high-res grid) [Guy 97, Mann 02] [Tang 98, Pollock 13] Our test
Truth Alg. Validation & Comparison Odd Even Odd Odd Odd Even Comparison of parity tests (mid-res grid) [Guy 97, Mann 02] [Tang 98, Pollock 13] Our test
Truth Alg. Validation & Comparison Odd Even Odd Odd Odd Even Comparison of parity tests (low-res grid) [Guy 97, Mann 02] [Tang 98, Pollock 13] Our test
Application: Ridge/valley extraction Input: a scalar function ?: minor eigenvector of Hessian ?: gradient Seeding Create one seed for each cell face where our test reports odd PVs Resulting lines guaranteed to be closed wherever the eigenvectors are orientable
Summary A provably correct test for the parity of PV points on a cell face Utility: Ensure closed curves (when possible) in a PV extraction algorithm [Future work] Guide face subdivision in root-finding or curve tracing [Future work] Extension: Cell faces with non-zero genus PV in higher dimensions Funding sources: NSF IIS-0846072, IIS-1302200, IIS-1319573, DBI-1356388, CMMI-1039433, CC-NIE-1245795
