An official website of the United States government
Functionals that penalize bending or stretching of a surface play a key role in geometric and scientific computing, but to date have ignored a very basic requirement: in many situations, surfaces must not pass through themselves or each other. This paper develops a numerical framework for optimization of surface geometry while avoiding (self-)collision. The starting point is thetangent-point energy, which effectively pushes apart pairs of points that are close in space but distant along the surface. We develop a discretization of this energy for triangle meshes, and introduce a novel acceleration scheme based on a fractional Sobolev inner product. In contrast to similar schemes developed for curves, we avoid the complexity of building a multiresolution mesh hierarchy by decomposing our preconditioner into two ordinary Poisson equations, plus forward application of a fractional differential operator. We further accelerate this scheme via hierarchical approximation, and describe how to incorporate a variety of constraints (on area, volume,etc.). Finally, we explore how this machinery might be applied to problems in mathematical visualization, geometric modeling, and geometry processing.
more »
« less
Repulsive Curves
Curves play a fundamental role across computer graphics, physical simulation, and mathematical visualization, yet most tools for curve design do nothing to prevent crossings or self-intersections. This paper develops efficient algorithms for (self-)repulsion of plane and space curves that are well-suited to problems in computational design. Our starting point is the so-called tangent-point energy, which provides an infinite barrier to self-intersection. In contrast to local collision detection strategies used in, e.g., physical simulation, this energy considers interactions between all pairs of points, and is hence useful for global shape optimization: local minima tend to be aesthetically pleasing, physically valid, and nicely distributed in space. A reformulation of gradient descent, based on a Sobolev-Slobodeckij inner product enables us to make rapid progress toward local minima---independent of curve resolution. We also develop a hierarchical multigrid scheme that significantly reduces the per-step cost of optimization. The energy is easily integrated with a variety of constraints and penalties (e.g., inextensibility, or obstacle avoidance), which we use for applications including curve packing, knot untangling, graph embedding, non-crossing spline interpolation, flow visualization, and robotic path planning.
more »
« less
- Award ID(s):
- 1717320
- PAR ID:
- 10203182
- Date Published:
- Journal Name:
- ACM transactions on graphics
- ISSN:
- 0730-0301
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Kinematic synthesis to meet an approximate motion specification naturally forms a constrained optimization problem. Instead of using local methods, we conduct global design searches by direct computation of all critical points. The idea is not new, but performed at scale is only possible through modern polynomial homotopy continuation solvers. Such a complete computation finds all minima, including the global, which allows for a full exploration of the design space, whereas local solvers can only find the minimum nearest to an initial guess. We form equality-constrained objective functions that pertain to the synthesis of spherical four-bar linkages for approximate function generation. We consider the general case where all mechanism dimensions may vary and a more specific case that enables the placement of ground pivots. The former optimization problem is shown to permit 268 sets of critical points, and the latter permits 61 sets. Critical points are classified as saddles or minima through a post-process eigenanalysis of the projected Hessian. The discretization points are contained within the coefficients of the stationarity polynomials, so the algebraic structure of the synthesis equations remains invariant to the number of points. The results of our computational work were used to design a mechanism that coordinates the folding wings. We also use this method to parameterize mechanism dimensions for a family of hyperbolic curves.more » « less
-
In this article, we define Vassiliev measures of complexity for open curves in 3-space. These are related to the coefficients of the enhanced Jones polynomial of open curves in 3-space. These Vassiliev measures are continuous functions of the curve coordinates; as the ends of the curve tend to coincide, they converge to the corresponding Vassiliev invariants of the resulting knot. We focus on the second Vassiliev measure from the enhanced Jones polynomial for closed and open curves in 3-space. For closed curves, this second Vassiliev measure can be computed by a Gauss code diagram and it has an integral formulation, the double alternating self-linking integral. The double alternating self-linking integral is a topological invariant of closed curves and a continuous function of the curve coordinates for open curves in 3-space. For polygonal curves, the double alternating self-linking integral obtains a simpler expression in terms of geometric probabilities.more » « less
-
Topology optimization problems are typically non-convex, and as such, multiple local minima exist. Depending on the initial design, the type of optimization algorithm and the optimization parameters, gradient-based optimizers converge to one of those minima. Unfortunately, these minima can be highly suboptimal, particularly when the structural response is very non-linear or when multiple constraints are present. This issue is more pronounced in the topology optimization of geometric primitives, because the design representation is more compact and restricted than in free-form topology optimization. In this paper, we investigate the use of tunneling in topology optimization to move from a poor local minimum to a better one. The tunneling method used in this work is a gradient-based deterministic method that finds a better minimum than the previous one in a sequential manner. We demonstrate this approach via numerical examples and show that the coupling of the tunneling method with topology optimization leads to better designs.more » « less
-
We study a deep learning inspired formulation for the blind demodulation problem, which is the task of recovering two unknown vectors from their entrywise multiplication. We consider the case where the unknown vectors are in the range of known deep generative models, G(1):R^n→R^l and G(2):R^p→R^l. In the case when the networks corresponding to the generative models are expansive, the weight matrices are random and the dimension of the unknown vectors satisfy l=Omega(n^2+p^2), up to log factors, we show that the empirical risk objective has a favorable landscape for optimization. That is, the objective function has a descent direction at every point outside of a small neighborhood around four hyperbolic curves. We also characterize the local maximizers of the empirical risk objective and, hence, show that there does not exist any other stationary points outside of these neighborhood around four hyperbolic curves and the set of local maximizers. We also implement a gradient descent scheme inspired by the geometry of the landscape of the objective function. In order to converge to a global minimizer, this gradient descent scheme exploits the fact that exactly one of the hyperbolic curve corresponds to the global minimizer, and thus points near this hyperbolic curve have a lower objective value than points close to the other spurious hyperbolic curves. We show that this gradient descent scheme can effectively remove distortions synthetically introduced to the MNIST dataset.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
