An official website of the United States government
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
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:
- 10606805
- Publisher / Repository:
- Association for Computing Machinery (ACM)
- Date Published:
- Journal Name:
- ACM Transactions on Graphics
- Volume:
- 43
- Issue:
- 4
- ISSN:
- 0730-0301
- Format(s):
- Medium: X Size: p. 1-18
- Size(s):
- p. 1-18
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
We describe a novel meshless Galerkin method for numerically solving semilinear parabolic equations on spheres. The new approximation method is based upon a discretization in space using spherical basis functions in a Galerkin approximation. As our spatial approximation spaces are built with spherical basis functions, they can be of arbitrary order and do not require the construction of an underlying mesh. We will establish convergence of the meshless method by adapting, to the sphere, a convergence result due to Thom\'ee and Wahlbin. To do this requires proving new approximation results, including a novel inverse or Nikolskii inequality for spherical basis functions. We also discuss how the integrals in the Galerkin method can accurately and more efficiently be computed using a recently developed quadrature rule. These new quadrature formulas also apply to Galerkin approximations of elliptic partial differential equations on the sphere. Finally, we provide several numerical examples, including the Allen-Cahn for the sphere.more » « less
-
null (Ed.)Flat surfaces captured by 3D point clouds are often used for localization, mapping, and modeling. Dense point cloud processing has high computation and memory costs making low-dimensional representations of flat surfaces such as polygons desirable. We present Polylidar3D, a non-convex polygon extraction algorithm which takes as input unorganized 3D point clouds (e.g., LiDAR data), organized point clouds (e.g., range images), or user-provided meshes. Non-convex polygons represent flat surfaces in an environment with interior cutouts representing obstacles or holes. The Polylidar3D front-end transforms input data into a half-edge triangular mesh. This representation provides a common level of abstraction for subsequent back-end processing. The Polylidar3D back-end is composed of four core algorithms: mesh smoothing, dominant plane normal estimation, planar segment extraction, and finally polygon extraction. Polylidar3D is shown to be quite fast, making use of CPU multi-threading and GPU acceleration when available. We demonstrate Polylidar3D’s versatility and speed with real-world datasets including aerial LiDAR point clouds for rooftop mapping, autonomous driving LiDAR point clouds for road surface detection, and RGBD cameras for indoor floor/wall detection. We also evaluate Polylidar3D on a challenging planar segmentation benchmark dataset. Results consistently show excellent speed and accuracy.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
