48 results
Search Results
Now showing 1 - 10 of 48
Item Fast Updates for Least-Squares Rotational Alignment(The Eurographics Association and John Wiley & Sons Ltd., 2021) Zhang, Jiayi Eris; Jacobson, Alec; Alexa, Marc; Mitra, Niloy and Viola, IvanAcross computer graphics, vision, robotics and simulation, many applications rely on determining the 3D rotation that aligns two objects or sets of points. The standard solution is to use singular value decomposition (SVD), where the optimal rotation is recovered as the product of the singular vectors. Faster computation of only the rotation is possible using suitable parameterizations of the rotations and iterative optimization. We propose such a method based on the Cayley transformations. The resulting optimization problem allows better local quadratic approximation compared to the Taylor approximation of the exponential map. This results in both faster convergence as well as more stable approximation compared to other iterative approaches. It also maps well to AVX vectorization. We compare our implementation with a wide range of alternatives on real and synthetic data. The results demonstrate up to two orders of magnitude of speedup compared to a straightforward SVD implementation and a 1.5-6 times speedup over popular optimized code.Item Hybrid Texture Synthesis(The Eurographics Association, 2003) Nealen, Andrew; Alexa, Marc; Philip Dutre and Frank Suykens and Per H. Christensen and Daniel Cohen-OrPatch-based texture synthesis algorithms produce reasonable results for a wide variety of texture classes. They preserve global structure, but often introduce unwanted visual artifacts along patch boundaries. Pixel-based synthesis algorithms, on the other hand, tend to blur out small objects while maintaining a consistent texture impression, which in return doesn t necessarily resemble the input texture. In this paper, we propose an adaptive and hybrid algorithm. Our algorithm adaptively splits patches so as to use as large as possible patches while staying within a user-defined error tolerance for the mismatch in the overlap region. Using large patches improves the reproduction of global structure. The remaining errors in the overlap regions are eliminated using pixel-based re-synthesis. We introduce an optimized ordering for the re-synthesis of these erroneous pixels using morphological operators, which ensures that every pixel has enough valid (i.e., error-free) neighboring pixels. Examples and comparisons with existing techniques demonstrate that our approach improves over previous texture synthesis algorithms, especially for textures with well-visible, possibly anisotropic structure, such as natural stone wall or scales.Item Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion(The Eurographics Association and John Wiley & Sons Ltd., 2017) Herholz, Philipp; Haase, Felix; Alexa, Marc; Loic Barthe and Bedrich BenesWe define Voronoi cells and centroids based on heat diffusion. These heat cells and heat centroids coincide with the common definitions in Euclidean spaces. On curved surfaces they compare favorably with definitions based on geodesics: they are smooth and can be computed in a stable way with a single linear solve. We analyze the numerics of this approach and can show that diffusion diagrams converge quadratically against the smooth case under mesh refinement, which is better than other common discretization of distance measures in curved spaces. By factorizing the system matrix in a preprocess, computing Voronoi diagrams or centroids amounts to just back-substitution. We show how to localize this operation so that the complexity is linear in the size of the cells and not the underlying mesh. We provide several example applications that show how to benefit from this approach.Item The Markov Pen: Online Synthesis of Free-Hand Drawing Styles(The Eurographics Association, 2015) Lang, Katrin; Alexa, Marc; David Mould and Pierre BénardLearning expressive curve styles from example is crucial for interactive or computer-based narrative illustrations. We propose a method for online synthesis of free-hand drawing styles along arbitrary base paths by means of an autoregressive Markov Model. Choice on further curve progression is made while drawing, by sampling from a series of previously learned feature distributions subject to local curvature. The algorithm requires no useradjustable parameters other than one short example style. It may be used as a custom ''random brush'' designer in any task that requires rapid placement of a large number of detail-rich shapes that are tedious to create manually.Item Efficient Computation of Smoothed Exponential Maps(© 2019 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd, 2019) Herholz, Philipp; Alexa, Marc; Chen, Min and Benes, BedrichMany applications in geometry processing require the computation of local parameterizations on a surface mesh at interactive rates. A popular approach is to compute local exponential maps, i.e. parameterizations that preserve distance and angle to the origin of the map. We extend the computation of geodesic distance by heat diffusion to also determine angular information for the geodesic curves. This approach has two important benefits compared to fast approximate as well as exact forward tracing of the distance function: First, it allows generating smoother maps, avoiding discontinuities. Second, exploiting the factorization of the global Laplace–Beltrami operator of the mesh and using recent localized solution techniques, the computation is more efficient even compared to fast approximate solutions based on Dijkstra's algorithm.Many applications in geometry processing require the computation of local parameterizations on a surface mesh at interactive rates. A popular approach is to compute local exponential maps, i.e. parameterizations that preserve distance and angle to the origin of the map. We extend the computation of geodesic distance by heat diffusion to also determine angular information for the geodesic curves. This approach has two important benefits compared to fast approximate as well as exact forward tracing of the distance function: First, it allows generating smoother maps, avoiding discontinuities. Second, exploiting the factorization of the global Laplace–Beltrami operator of the mesh and using recent localized solution techniques, the computation is more efficient even compared to fast approximate solutions based on Dijkstra's algorithm.Item The Diamond Laplace for Polygonal and Polyhedral Meshes(The Eurographics Association and John Wiley & Sons Ltd., 2021) Bunge, Astrid; Botsch, Mario; Alexa, Marc; Digne, Julie and Crane, KeenanWe introduce a construction for discrete gradient operators that can be directly applied to arbitrary polygonal surface as well as polyhedral volume meshes. The main idea is to associate the gradient of functions defined at vertices of the mesh with diamonds: the region spanned by a dual edge together with its corresponding primal element - an edge for surface meshes and a face for volumetric meshes. We call the operator resulting from taking the divergence of the gradient Diamond Laplacian. Additional vertices used for the construction are represented as affine combinations of the original vertices, so that the Laplacian operator maps from values at vertices to values at vertices, as is common in geometry processing applications. The construction is local, exactly the same for all types of meshes, and results in a symmetric negative definite operator with linear precision. We show that the accuracy of the Diamond Laplacian is similar or better compared to other discretizations. The greater versatility and generally good behavior come at the expense of an increase in the number of non-zero coefficients that depends on the degree of the mesh elements.Item crdbrd: Shape Fabrication by Sliding Planar Slices(The Eurographics Association and John Wiley and Sons Ltd., 2012) Hildebrand, Kristian; Bickel, Bernd; Alexa, Marc; P. Cignoni and T. ErtlWe introduce an algorithm and representation for fabricating 3D shape abstractions using mutually intersecting planar cut-outs. The planes have prefabricated slits at their intersections and are assembled by sliding them together. Often such abstractions are used as a sculptural art form or in architecture and are colloquially called 'cardboard sculptures'. Based on an analysis of construction rules, we propose an extended binary space partitioning tree as an efficient representation of such cardboard models which allows us to quickly evaluate the feasibility of newly added planar elements. The complexity of insertion order quickly increases with the number of planar elements and manual analysis becomes intractable. We provide tools for generating cardboard sculptures with guaranteed constructibility. In combination with a simple optimization and sampling strategy for new elements, planar shape abstraction models can be designed by iteratively adding elements. As an output, we obtain a fabrication plan that can be printed or sent to a laser cutter. We demonstrate the complete process by designing and fabricating cardboard models of various well-known 3D shapes.Item Vector Field Visualization using Markov Random Field Texture Synthesis(The Eurographics Association, 2003) Taponecco, Francesca; Alexa, Marc; G.-P. Bonneau and S. Hahmann and C. D. HansenVector field visualization aims at generating images in order to convey the information existing in the data. We use Markov Random Field (MRF) texture synthesis methods to generate the visualization from a set of sample textures. MRF texture synthesis methods allow generating images that are locally similar to a given example image. We extend this idea for vector field visualization by identifying each vector value with a representative example image, e.g. a strongly directed texture that is rotated according to a 2D vector. The visualization is synthesized pixel by pixel, where each pixel is chosen from the sample texture according to the vector values of the local pixel. The visualization locally communicates the vector information as each pixel is chosen from a sample that is representative of the vector. Furthermore it is smooth, as MRF texture synthesis searches for best fitting neighborhoods. This leads to dense and smooth visualizations with the additional freedom to use arbitrary representation textures for any vector value.Item Images from Self-Occlusion(The Eurographics Association, 2011) Alexa, Marc; Matusik, Wojciech; Douglas Cunningham and Tobias IsenbergWe propose a complete system for designing, simulating, and fabricating surfaces with shading due to selfocclusion that induce desired input images. Our work is based on a simple observation. Consider a cylindrical hole (a pit) in a planar surface. As the depth of the hole increases, the radiance emitted from the surface patch that contains the hole decreases. This is because more light is trapped and absorbed in the hole. First, we propose a measurement-based approach that derives a mapping between average albedo of the surface patch containing the hole and the hole depth. Given this mapping and an input image, we show how to produce a distribution of holes with varied depth that approximates the image well. We demonstrate that by aligning holes with image features we can obtain reproductions that look better than those resulting from regular hole patterns despite using slightly less holes. We validate this method on a variety of images and corresponding surfaces fabricated with a computer-controlled milling machine and a 3D printer.Item ARAP Revisited Discretizing the Elastic Energy using Intrinsic Voronoi Cells(© 2023 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd., 2023) Finnendahl, Ugo; Schwartz, Matthias; Alexa, Marc; Hauser, Helwig and Alliez, PierreAs‐rigid‐as‐possible (ARAP) surface modelling is widely used for interactive deformation of triangle meshes. We show that ARAP can be interpreted as minimizing a discretization of an elastic energy based on non‐conforming elements defined over dual orthogonal cells of the mesh. Using the Voronoi cells rather than an orthogonal dual of the extrinsic mesh guarantees that the energy is non‐negative over each cell. We represent the intrinsic Delaunay edges extrinsically as polylines over the mesh, encoded in barycentric coordinates relative to the mesh vertices. This modification of the original ARAP energy, which we term , remedies problems stemming from non‐Delaunay edges in the original approach. Unlike the spokes‐and‐rims version of the ARAP approach it is less susceptible to the triangulation of the surface. We provide examples of deformations generated with iARAP and contrast them with other versions of ARAP. We also discuss the properties of the Laplace‐Beltrami operator implicitly introduced with the new discretization.