An official website of the United States government
We introduce a method for approximating the signed distance function (SDF) of geometry corrupted by holes, noise, or self-intersections. The method implicitly defines a completed version of the shape, rather than explicitly repairing the given input. Our starting point is a modified version of theheat methodfor geodesic distance, which diffuses normal vectors rather than a scalar distribution. This formulation provides robustness akin togeneralized winding numbers (GWN), but provides distance function rather than just an inside/outside classification. Our formulation also offers several features not common to classic distance algorithms, such as the ability to simultaneously fit multiple level sets, a notion of distance for geometry that does not topologically bound any region, and the ability to mix and match signed and unsigned distance. The method can be applied in any dimension and to any spatial discretization, including triangle meshes, tet meshes, point clouds, polygonal meshes, voxelized surfaces, and regular grids. We evaluate the method on several challenging examples, implementing normal offsets and other morphological operations directly on imperfect curve and surface data. In many cases we also obtain an inside/outside classification dramatically more robust than the one obtained provided by GWN.
more »
« less
Efficient Outside Computation
Weighted deduction systems provide a framework for describing parsing algorithms that can be used with a variety of operations for combining the values of partial derivations. For some operations, inside values can be computed efficiently, but outside values cannot. We view out-side values as functions from inside values to the total value of all derivations, and we analyze outside computation in terms of function composition. This viewpoint helps explain why efficient outside computation is possible in many settings, despite the lack of a general outside algorithm for semiring operations.
more »
« less
- Award ID(s):
- 1813823
- PAR ID:
- 10292766
- Date Published:
- Journal Name:
- Computational Linguistics
- Volume:
- 46
- Issue:
- 4
- ISSN:
- 0891-2017
- Page Range / eLocation ID:
- 745 to 762
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Processing In-Memory (PIM) is a data-centric computation paradigm that performs computations inside the memory, hence eliminating the memory wall problem in traditional computational paradigms used in Von-Neumann architectures. The associative processor, a type of PIM architecture, allows performing parallel and energy-efficient operations on vectors. This architecture is found useful in vector-based applications such as Hyper-Dimensional (HDC) Reinforcement Learning (RL). HDC is rising as a new powerful and lightweight alternative to costly traditional RL models such as Deep Q-Learning. The HDC implementation of Q-Learning relies on encoding the states in a high-dimensional representation where calculating Q-values and finding the maximum one can be done entirely in parallel. In this article, we propose to implement the main operations of a HDC RL framework on the associative processor. This acceleration achieves up to\(152.3\times\)and\(6.4\times\)energy and time savings compared to an FPGA implementation. Moreover, HDRLPIM shows that an SRAM-based AP implementation promises up to\(968.2\times\)energy-delay product gains compared to the FPGA implementation.more » « less
-
null (Ed.)Android applications rely heavily on strings for sensitive operations like reflection, access to system resources, URL connections, database access, among others. Thus, insight into application behavior can be gained through not only an analysis of what strings an application creates but also the structure of the computation used to create theses strings, and in what manner are these strings used. In this paper we introduce a static analysis of Android applications to discover strings, how they are created, and their usage. The output of our static analysis contains all of this information in the form of a graph which we call a string computation. We leverage the results to classify individual application behavior with respect to malicious or benign intent. Unlike previous work that has focused only on extraction of string values, our approach leverages the structure of the computation used to generate string values as features to perform classification of Android applications. That is, we use none of the static analysis computed string values, rather using only the graph structures of created strings to do classification of an arbitrary Android application as malware or benign. Our results show that leveraging string computation structures as features can yield precision and recall rates as high as 97% on modern malware. We also provide baseline results against other malware detection tools and techniques to classify the same corpus of applications.more » « less
-
SUMMARY In previous publications, we presented a general framework, which we called ‘box tomography’, that allows the coupling of any two different numerical seismic wave propagation solvers, respectively outside and inside a target region, or ‘box’. The goal of such hybrid wavefield computations is to reduce the cost of computations in the context of full-waveform inversion for structure within the target region, when sources and/or receivers are located at large distances from the box. Previously, we had demonstrated this approach with sources and receivers outside the target region in a 2-D acoustic spherical earth model, and demonstrated and applied this methodology in the 3-D spherical elastic Earth in a continental scale inversion in which all stations were inside the target region. Here we extend the implementation of the approach to the case of a 3-D global elastic earth model in the case where both sources and stations are outside the box. We couple a global 3-D solver, SPECFEM3D_GLOBE, for the computation of the wavefield and Green’s functions in a reference 3-D model, with a regional 3-D solver, RegSEM, for the computation of the wavefield within the box, by means of time-reversal mirrors. We briefly review key theoretical aspects, showing in particular how only the displacement is needed to be stored at the boundary of the box. We provide details of the practical implementation, including the geometrical design of the mirrors, how we deal with different sizes of meshes in the two solvers, and how we address memory-saving through the use of B-spline compression of the recorded wavefield on the mirror. The proposed approach is numerically efficient but also versatile, since adapting it to other solvers is straightforward and does not require any changes in the solver codes themselves, as long as the displacement can be recovered at any point in time and space. We present benchmarks of the hybrid computations against direct computations of the wavefield between a source and an array of stations in a realistic geometry centred in the Yellowstone region, with and without a hypothetical plume within the ‘box’, and with a 1-D or a 3-D background model, down to a period of 20 s. The ultimate goal of this development is for applications in the context of imaging of remote target regions in the deep mantle, such as, for example, Ultra Low Velocity Zones.more » « less
-
To assess thermal and kinetic influences on atomic mobility and mineral (neo)crystallization, clumped‐isotope abundances of calcite and dolomite were measured alongside dolomite cation ordering and U–Pb dates, across metamorphic grade within the c. 35–30 Ma Alta stock contact metamorphic aureole, Utah, USA. Average Δ47 values of dolomite inside the metamorphic aureole reflect the blocking temperature of dolomite (300°C–350°C) during cooling from peak temperatures. Dolomite Δ47 values outside the metamorphic aureole record a temperature of ~160°C. At the talc isograd, dolomite Δ47 values abruptly change, corresponding to a decrease of ~180°C over <50 m in the down‐temperature direction. This observed step in dolomite Δ47 values does not correlate with cation ordering in dolomite or U–Pb dates, neither of which correlate well with metamorphic grade. The short distance over which dolomite Δ47 values change indicates strong temperature sensitivity in the kinetics of dolomite clumped‐isotope reordering, and is consistent with a wide range of clumped‐isotope reequilibration modeling results. We hypothesize that clumped‐isotope reordering in dolomite precedes more extensive recrystallization or metamorphic reaction, such as the formation of talc. Dolomite U–Pb analyses from inside and outside the metamorphic aureole populate a single discordia ~60 Myr younger than depositional age (Mississippian), recording resetting in response to some older postdepositional, but premetamorphic process.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1162/coli_a_00386
