An official website of the United States government
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
Polylidar3D-Fast Polygon Extraction from 3D Data
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
- Award ID(s):
- 1738714
- PAR ID:
- 10291988
- Date Published:
- Journal Name:
- Sensors
- Volume:
- 20
- Issue:
- 17
- ISSN:
- 1424-8220
- Page Range / eLocation ID:
- 4819
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this review paper, we first provide comprehensive tutorials on two classical methods of polygon-based computer-generated holography: the traditional method (also called the fast-Fourier-transform-based method) and the analytical method. Indeed, other modern polygon-based methods build on the idea of the two methods. We will then present some selective methods with recent developments and progress and compare their computational reconstructions in terms of calculation speed and image quality, among other things. Finally, we discuss and propose a fast analytical method called the fast 3D affine transformation method, and based on the method, we present a numerical reconstruction of a computer-generated hologram (CGH) of a 3D surface consisting of 49,272 processed polygons of the face of a real person without the use of graphic processing units; to the best of our knowledge, this represents a state-of-the-art numerical result in polygon-based computed-generated holography. Finally, we also show optical reconstructions of such a CGH and another CGH of the Stanford bunny of 59,996 polygons with 31,724 processed polygons after back-face culling. We hope that this paper will bring out some of the essence of polygon-based computer-generated holography and provide some insights for future research.more » « less
-
null (Ed.)Abstract The pentagram map takes a planar polygon $$P$$ to a polygon $$P^{\prime }$$ whose vertices are the intersection points of the consecutive shortest diagonals of $$P$$. The orbit of a convex polygon under this map is a sequence of polygons that converges exponentially to a point. Furthermore, as recently proved by Glick, coordinates of that limit point can be computed as an eigenvector of a certain operator associated with the polygon. In the present paper, we show that Glick’s operator can be interpreted as the infinitesimal monodromy of the polygon. Namely, there exists a certain natural infinitesimal perturbation of a polygon, which is again a polygon but in general not closed; what Glick’s operator measures is the extent to which this perturbed polygon does not close up.more » « less
-
The pentagram map takes a planar polygon $$P$$ to a polygon $P'$ whose vertices are the intersection points of consecutive shortest diagonals of $$P$$ . This map is known to interact nicely with Poncelet polygons, that is, polygons which are simultaneously inscribed in a conic and circumscribed about a conic. A theorem of Schwartz states that if $$P$$ is a Poncelet polygon, then the image of $$P$$ under the pentagram map is projectively equivalent to $$P$$ . In the present paper, we show that in the convex case this property characterizes Poncelet polygons: if a convex polygon is projectively equivalent to its pentagram image, then it is Poncelet. The proof is based on the theory of commuting difference operators, as well as on properties of real elliptic curves and theta functions.more » « less
-
null (Ed.)Emerging autonomous driving systems require reliable perception of 3D surroundings. Unfortunately, current mainstream perception modalities, i.e., camera and Lidar, are vulnerable under challenging lighting and weather conditions. On the other hand, despite their all-weather operations, today's vehicle Radars are limited to location and speed detection. In this paper, we introduce MILLIPOINT, a practical system that advances the Radar sensing capability to generate 3D point clouds. The key design principle of MILLIPOINT lies in enabling synthetic aperture radar (SAR) imaging on low-cost commodity vehicle Radars. To this end, MILLIPOINT models the relation between signal variations and Radar movement, and enables self-tracking of Radar at wavelength-scale precision, thus realize coherent spatial sampling. Furthermore, MILLIPOINT solves the unique problem of specular reflection, by properly focusing on the targets with post-imaging processing. It also exploits the Radar's built-in antenna array to estimate the height of reflecting points, and eventually generate 3D point clouds. We have implemented MILLIPOINT on a commodity vehicle Radar. Our evaluation results show that MILLIPOINT effectively combats motion errors and specular reflections, and can construct 3D point clouds with much higher density and resolution compared with the existing vehicle Radar solutions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3390/s20174819
