An official website of the United States government
Abstract This paper presents a fast and robust numerical method for reconstructing point-like sources in the time-harmonic Maxwell’s equations given Cauchy data at a fixed frequency. This is an electromagnetic inverse source problem with broad applications, such as antenna synthesis and design, medical imaging, and pollution source tracing. We introduce new imaging functions and a computational algorithm to determine the number of point sources, their locations, and associated moment vectors, even when these vectors have notably different magnitudes. The number of sources and locations are estimated using significant peaks of the imaging functions, and the moment vectors are computed via explicitly simple formulas. The theoretical analysis and stability of the imaging functions are investigated, where the main challenge lies in analyzing the behavior of the dot products between the columns of the imaginary part of the Green’s tensor and the unknown moment vectors. Additionally, we extend our method to reconstruct small-volume sources using an asymptotic expansion of their radiated electric field. We provide numerical examples in three dimensions to demonstrate the performance of our method.
more »
« less
Ray Tracing Harmonic Functions
Sphere tracingis a fast and high-quality method for visualizing surfaces encoded by signed distance functions (SDFs). We introduce a similar method for a completely different class of surfaces encoded byharmonic functions, opening up rich new possibilities for visual computing. Our starting point is similar in spirit to sphere tracing: using conservativeHarnack boundson the growth of harmonic functions, we develop aHarnack tracingalgorithm for visualizing level sets of harmonic functions, including those that are angle-valued and exhibit singularities. The method takes much larger steps than naïve ray marching, avoids numerical issues common to generic root finding methods and, like sphere tracing, needs only perform pointwise evaluation of the function at each step. For many use cases, the method is fast enough to run real time in a shader program. We use it to visualize smooth surfaces directly from point clouds (via Poisson surface reconstruction) or polygon soup (via generalized winding numbers) without linear solves or mesh extraction. We also use it to visualize nonplanar polygons (possibly with holes), surfaces from architectural geometry, mesh exoskeletons, and key mathematical objects including knots, links, spherical harmonics, and Riemann surfaces. Finally we show that, at least in theory, Harnack tracing provides an alternative mechanism for visualizing arbitrary implicit surfaces.
more »
« less
- Award ID(s):
- 2212290
- PAR ID:
- 10553556
- Publisher / Repository:
- Association for Computing Machinery
- Date Published:
- Journal Name:
- ACM Transactions on Graphics
- Volume:
- 43
- Issue:
- 4
- ISSN:
- 0730-0301
- Page Range / eLocation ID:
- 1 to 18
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In the plane, thewinding numberis the number of times a curve wraps around a given point. Winding numbers are a basic component of geometric algorithms such as point-in-polygon tests, and their generalization to data with noise or topological errors has proven valuable for geometry processing tasks ranging from surface reconstruction to mesh booleans. However, standard definitions do not immediately apply on surfaces, where not all curves bound regions. We develop a meaningful generalization, starting with the well-known relationship between winding numbers and harmonic functions. By processing the derivatives of such functions, we can robustly filter out components of the input that do not bound any region. Ultimately, our algorithm yields (i) a closed, completed version of the input curves, (ii) integer labels for regions that are meaningfully bounded by these curves, and (iii) the complementary curves that do not bound any region. The main computational cost is solving a standard Poisson equation, or for surfaces with nontrivial topology, a sparse linear program. We also introduce special basis functions to represent singularities that naturally occur at endpoints of open curves.more » « less
-
Many geometry processing techniques require the solution of partial differential equations (PDEs) on manifolds embedded in\(\mathbb {R}^2 \)or\(\mathbb {R}^3 \), such as curves or surfaces. Suchmanifold PDEsoften involve boundary conditions (e.g., Dirichlet or Neumann) prescribed at points or curves on the manifold’s interior or along the geometric (exterior) boundary of an open manifold. However, input manifolds can take many forms (e.g., triangle meshes, parametrizations, point clouds, implicit functions, etc.). Typically, one must generate a mesh to apply finite element-type techniques or derive specialized discretization procedures for each distinct manifold representation. We propose instead to address such problems in a unified manner through a novel extension of theclosest point method(CPM) to handle interior boundary conditions. CPM solves the manifold PDE by solving a volumetric PDE defined over the Cartesian embedding space containing the manifold, and requires only a closest point representation of the manifold. Hence, CPM supports objects that are open or closed, orientable or not, and of any codimension. To enable support for interior boundary conditions we derive a method that implicitly partitions the embedding space across interior boundaries. CPM’s finite difference and interpolation stencils are adapted to respect this partition while preserving second-order accuracy. Additionally, we develop an efficient sparse-grid implementation and numerical solver that can scale to tens of millions of degrees of freedom, allowing PDEs to be solved on more complex manifolds. We demonstrate our method’s convergence behaviour on selected model PDEs and explore several geometry processing problems: diffusion curves on surfaces, geodesic distance, tangent vector field design, harmonic map construction, and reaction-diffusion textures. Our proposed approach thus offers a powerful and flexible new tool for a range of geometry processing tasks on general manifold representations.more » « less
-
In some applications, it is reasonable to assume that geodesics (rays) have a consistent orientation so that a time-harmonic elastic wave equation may be viewed as an evolution equation in one of the spatial directions. With such applications in mind, motivated by our recent work [Hadamard- Babich ansatz for point-source elastic wave equations in variable media at high frequencies, Multiscale Model Simul. 19/1 (2021) 46–86], we propose a new truncated Hadamard-Babich ansatz based globally valid asymptotic method, dubbed the fast Huygens sweeping method, for computing Green’s functions of frequency-domain point-source elastic wave equations in inhomogeneous media in the high-frequency asymptotic regime and in the presence of caustics. The first novelty of the fast Huygens sweeping method is that the Huygens-Kirchhoff secondary-source principle is used to integrate many locally valid asymptotic solutions to yield a globally valid asymptotic solution so that caustics can be treated automatically. This yields uniformly accurate solutions both near the source and away from it. The second novelty is that a butterfly algorithm is adapted to accelerate matrix-vector products induced by the Huygens-Kirchhoff integral. The new method enjoys the following desired features: (1) it treats caustics automatically; (2) precomputed asymptotic ingredients can be used to construct Green’s functions of elastic wave equations for many different point sources and for arbitrary frequencies; (3) given a specified number of points per wavelength, it constructs Green’s functions in nearly optimal complexity O(N logN) in terms of the total number of mesh points N, where the prefactor of the complexity depends only on the specified accuracy and is independent of the frequency parameter. Three-dimensional numerical examples are presented to demonstrate the performance and accuracy of the new method.more » « less
-
Spatial population genetic data often exhibits ‘isolation-by-distance,’ where genetic similarity tends to decrease as individuals become more geographically distant. The rate at which genetic similarity decays with distance is often spatially heterogeneous due to variable population processes like genetic drift, gene flow, and natural selection. Petkova et al., 2016 developed a statistical method called Estimating Effective Migration Surfaces (EEMS) for visualizing spatially heterogeneous isolation-by-distance on a geographic map. While EEMS is a powerful tool for depicting spatial population structure, it can suffer from slow runtimes. Here, we develop a related method called Fast Estimation of Effective Migration Surfaces (FEEMS). FEEMS uses a Gaussian Markov Random Field model in a penalized likelihood framework that allows for efficient optimization and output of effective migration surfaces. Further, the efficient optimization facilitates the inference of migration parameters per edge in the graph, rather than per node (as in EEMS). With simulations, we show conditions under which FEEMS can accurately recover effective migration surfaces with complex gene-flow histories, including those with anisotropy. We apply FEEMS to population genetic data from North American gray wolves and show it performs favorably in comparison to EEMS, with solutions obtained orders of magnitude faster. Overall, FEEMS expands the ability of users to quickly visualize and interpret spatial structure in their data.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1145/3658201
