Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSurface Multigrid via Intrinsic Prolongation
70
0
0.0
(
0
)
Added by
Hsueh-Ti Derek Liu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper introduces a novel geometric multigrid solver for unstructured curved surfaces. Multigrid methods are highly efficient iterative methods for solving systems of linear equations. Despite the success in solving problems defined on structured domains, generalizing multigrid to unstructured curved domains remains a challenging problem. The critical missing ingredient is a prolongation operator to transfer functions across different multigrid levels. We propose a novel method for computing the prolongation for triangulated surfaces based on intrinsic geometry, enabling an efficient geometric multigrid solver for curved surfaces. Our surface multigrid solver achieves better convergence than existing multigrid methods. Compared to direct solvers, our solver is orders of magnitude faster. We evaluate our method on many geometry processing applications and a wide variety of complex shapes with and without boundaries. By simply replacing the direct solver, we upgrade existing algorithms to interactive frame rates, and shift the computational bottleneck away from solving linear systems.
rate research
Read More
A merger of two optimization frameworks is introduced: SEquential Subspace OPtimization (SESOP) with the MultiGrid (MG) optimization. At each iteration of the algorithm, search directions implied by the coarse-grid correction (CGC) process of MG are added to the low dimensional search-spaces of SESOP, which include the (preconditioned) gradient and search directions involving the previous iterates (so-called history). The resulting accelerated technique is called SESOP-MG. The asymptotic convergence factor of the two-level version of SESOP-MG (dubbed SESOP-TG) is studied via Fourier mode analysis for linear problems, i.e., optimization of quadratic functionals. Numerical tests on linear and nonlinear problems demonstrate the effectiveness of the approach.
The alternating direction method of multipliers (ADMM) is a popular approach for solving optimization problems that are potentially non-smooth and with hard constraints. It has been applied to various computer graphics applications, including physical simulation, geometry processing, and image processing. However, ADMM can take a long time to converge to a solution of high accuracy. Moreover, many computer graphics tasks involve non-convex optimization, and there is often no convergence guarantee for ADMM on such problems since it was originally designed for convex optimization. In this paper, we propose a method to speed up ADMM using Anderson acceleration, an established technique for accelerating fixed-point iterations. We show that in the general case, ADMM is a fixed-point iteration of the second primal variable and the dual variable, and Anderson acceleration can be directly applied. Additionally, when the problem has a separable target function and satisfies certain conditions, ADMM becomes a fixed-point iteration of only one variable, which further reduces the computational overhead of Anderson acceleration. Moreover, we analyze a particular non-convex problem structure that is common in computer graphics, and prove the convergence of ADMM on such problems under mild assumptions. We apply our acceleration technique on a variety of optimization problems in computer graphics, with notable improvement on their convergence speed.
In this paper we provide a characterisation of rational developable surfaces in terms of the blossoms of the bounding curves and three rational functions $Lambda$, $M$, $ u$. Properties of developable surfaces are revised in this framework. In particular, a closed algebraic formula for the edge of regression of the surface is obtained in terms of the functions $Lambda$, $M$, $ u$, which are closely related to the ones that appear in the standard decomposition of the derivative of the parametrisation of one of the bounding curves in terms of the director vector of the rulings and its derivative. It is also shown that all rational developable surfaces can be described as the set of developable surfaces which can be constructed with a constant $Lambda$, $M$, $ u$ . The results are readily extended to rational spline developable surfaces.
We present a method for differentiable rendering of 3D surfaces that supports both explicit and implicit representations, provides derivatives at occlusion boundaries, and is fast and simple to implement. The method first samples the surface using non-differentiable rasterization, then applies differentiable, depth-aware point splatting to produce the final image. Our approach requires no differentiable meshing or rasterization steps, making it efficient for large 3D models and applicable to isosurfaces extracted from implicit surface definitions. We demonstrate the effectiveness of our method for implicit-, mesh-, and parametric-surface-based inverse rendering and neural-network training applications. In particular, we show for the first time efficient, differentiable rendering of an isosurface extracted from a neural radiance field (NeRF), and demonstrate surface-based, rather than volume-based, rendering of a NeRF.
Many algorithms for surface registration risk producing significant errors if surfaces are significantly nonisometric. Manifold learning has been shown to be effective at improving registration quality, using information from an entire collection of surfaces to correct issues present in pairwise registrations. These methods, however, are not robust to changes in the collection of surfaces, or do not produce accurate registrations at a resolution high enough for subsequent downstream analysis. We propose a novel algorithm for efficiently registering such collections given initial correspondences with varying degrees of accuracy. By combining the initial information with recent developments in manifold learning, we employ a simple metric condition to construct a measure on the space of correspondences between any pair of shapes in our collection, which we then use to distill soft correspondences. We demonstrate that this measure can improve correspondence accuracy between feature points compared to currently employed, less robust methods on a diverse dataset of surfaces from evolutionary biology. We then show how our methods can be used, in combination with recent sampling and interpolation methods, to compute accurate and consistent homeomorphisms between surfaces.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
