1,721,039 research outputs found
PolyCut: Monotone Graph-Cuts for PolyCube Base-Complex Construction
No full textPolyCubes, or orthogonal polyhedra, are useful as parameterization base-complexes for various operations in computer graphics. However, computing quality PolyCube base-complexes for general shapes, providing a good trade-off between mapping distortion and singularity counts, remains a challenge. Our work improves on the state-of-the-art in PolyCube computation by adopting a graph-cut inspired approach. We observe that, given an arbitrary input mesh, the computation of a suitable PolyCube base-complex can be formulated as associating, or labeling, each input mesh triangle with one of six signed principal axis directions. Most of the criteria for a desirable PolyCube labeling can be satisfied using a multi-label graph-cut optimization with suitable local unary and pairwise terms. However, the highly constrained nature of PolyCubes, imposed by the need to align each chart with one of the principal axes, enforces additional global constraints that the labeling must satisfy. To enforce these constraints, we develop a constrained discrete optimization technique, PolyCut, which embeds a graph-cut multi-label optimization within a hill-climbing local search framework that looks for solutions that minimize the cut energy while satisfying the global constraints. We further optimize our generated PolyCube base-complexes through a combination of distortion-minimizing deformation, followed by a labeling update and a final PolyCube parameterization step. Our PolyCut formulation captures the desired properties of a PolyCube base-complex, balancing parameterization distortion against singularity count, and produces demonstrably better PolyCube base-complexes then previous work
Practical Hex-Mesh optimization via edge-cone rectification
No full textThe usability of hexahedral meshes depends on the degree to which the shape of their elements deviates from a perfect cube; a single concave, or inverted element makes a mesh unusable. While a range of methods exist for discretizing 3D objects with an initial topologically suitable hex mesh, their output meshes frequently contain poorly shaped and even inverted elements, requiring a further quality optimization step. We introduce a novel framework for optimizing hex-mesh quality capable of generating inversion-free high-quality meshes from such poor initial inputs. We recast hex quality improvement as an optimization of the shape of overlapping cones, or unions, of tetrahedra surrounding every directed edge in the hex mesh, and show the two to be equivalent. We then formulate cone shape optimization as a sequence of convex quadratic optimization problems, where hex convexity is encoded via simple linear inequality constraints. As this solution space may be empty, we therefore present an alternate formulation which allows the solver to proceed even when constraints cannot be satisfied exactly. We iteratively improve mesh element quality by solving at each step a set of local, per-cone, convex constrained optimization problems, followed by a global energy minimization step which reconciles these local solutions. This latter method provides no theoretical guarantees on the solution but produces inversion-free, high quality meshes in practice. We demonstrate the robustness of our framework by optimizing numerous poor quality input meshes generated using a variety of initial meshing methods and producing high-quality inversion-free meshes in each case. We further validate our algorithm by comparing it against previous work, and demonstrate a significant improvement in both worst and average element quality
A Quadratic Bending Model for Inextensible Surfaces
No full textRelating the intrinsic Laplacian to the mean curvature normal, we arrive at a model for bending of inextensible surfaces. Due to its constant Hessian, our isometric bending model reduces cloth simulation times up to three-fold
Procedural Cloudscapes
No full textWe present a phenomenological approach for modeling and animating cloudscapes. We propose a compact procedural model for representing the different types of cloud over a range of altitudes. We define primitive-based field functions that allow the user to control and author the cloud cover over large distances easily. Our approach allows us to animate cloudscapes by morphing: instead of simulating the evolution of clouds using a physically-based simulation, we compute the movement of clouds using key-frame interpolation and tackle the morphing problem as an Optimal Transport problem. The trajectories of the cloud cover primitives are generated by solving an Anisotropic Shortest Path problem with a cost function that takes into account the elevation of the terrain and the parameters of the wind field.Computer Graphics ForumProcedural Modeling37
Discrete optimization problems in geometric mesh processing
No full textMany geometry processing tasks in computer graphics reduce geometric problems to numerical optimization problems by minimizing an energy that captures the geometric properties we seek. These methods often encounter challenges in the presence of complex global geometric constraints that cannot be easily expressed as numerical optimizations. In this work, we augment these approaches with a different class of algorithmic techniques - discrete and combinatorial optimization algorithms - to solve diverse, challenging problems in geometry processing and computer graphics.
We first show how generating PolyCube base-complexes for meshes can be expressed
as a labeling problem, and how embedding a graph-cut multi-label optimization within a classical hill-climbing local search framework can find suitable labelings that both minimize a local cut energy and satisfy complex geometric constraints. We demonstrate the applicability of this method, PolyCut, to hexahedral meshing, and include a local-global optimization approach for untangling deformed hexahedral elements with minimal or negative scaled Jacobian.
We then consider the problem of generating video game levels from a graph description of the level and a set of candidate building blocks, and show how another numerical optimization technique, simulated annealing, can be embedded within a combinatorial backtracking framework to generate valid game level layouts satisfying design requirements.
Finally, we consider the problem of texture-space shading, which enables decoupled shading on existing GPU hardware, facilitating amortization of shading over space and time. Existing texture-space shading methods segment input meshes into fixed charts, and generate atlases spanning all or some of these charts; this introduces visible texture seams and perspective distortion, and wastes texture space. We introduce ViewParam, which solves these problems by generating per-frame atlases in real time. We achieve real-time performance entirely on the GPU by formulating chart finding and packing as discrete and combinatorial problems. We compute seamless charts by employing a GPU-based implementation of the classical union-find algorithm, and find approximate solutions to the NP-hard box packing problem by employing a relaxation strategy based on prefix sums and exploiting GPU parallelism. We validate the quality and robustness of ViewParam by shading and rendering challenging scenes with significantly better shading quality than prior methods.Science, Faculty ofComputer Science, Department ofGraduat
Algorithms for geometry partitioning and reshaping
No full textVirtual digital content, including 2D vector clip art and 3D meshes, has experienced a significant surge in popularity in recent years. The increasing availability of these digital assets on virtual platforms enables professionals and amateurs to find and repurpose existing content to suit their specific needs. Whether it involves customizing assets to align with creative preferences or satisfying the constraints of downstream applications, such as those imposed by digital manufacturing technologies, editing digital assets remains a highly complex and time-consuming task. This complexity poses a significant barrier to the widespread adoption of virtual platforms and digital manufacturing technologies. In this thesis, we investigate novel and easy-to-use approaches for critical operations in digital content editing: reshaping and volumetric partitioning.
First, we address the challenges of 2D/3D reshaping. When editing digital content, users often desire to customize existing assets to generate new looks and styles while preserving their original structure. However, the lack of automatic tools suitable for reshaping tasks leads users to rely on labor-intensive and complex modeling tasks. We introduce novel user-centric algorithmic solutions for reshaping 2D vector clip art and 3D meshes, enabling users to effortlessly produce outputs that align with their expectations of reshaping operations. We rigorously validate our methods across various inputs and by comparing our outputs to those produced by alternative approaches and professional artists.
The second part of this thesis focuses on 3D geometry partitioning. When producing physical replicas of 3D digital content, users often desire to fabricate objects with multi-attribute surface regions (e.g. distinct colors or materials). However, manufacturing these objects as single pieces can be challenging or even impossible. An alternative solution is to partition such objects into single-attribute parts that allow per-part fabrication and subsequent assembly. To overcome the complexity of performing this operation manually, we introduce a novel easy-to-use algorithm for surface-segmentation conforming and assemblable volumetric partitioning. The robustness of our method is demonstrated on a variety of complex models, and it is validated via comparisons with alternative approaches.
The algorithmic solutions presented in this thesis enable end-users to effortlessly customize digital content to meet their reshaping goals or to comply with the constraints of multi-attribute 3D fabrication.Science, Faculty ofComputer Science, Department ofGraduat
Using dual height fields for the parametrization of signed distance fields
No full textRay-tracing has become an important technique used to generate photorealistic images in video games and movies. It is a technique in which straight rays of light traveling in a scene are simulated to produce realistic images. Signed Distance Fields are a class of mathematical functions used to describe 3D geometry. They allow for fast ray-object collision detection. While they are very well suited for simulating the trajectory a ray of light travels through in a scene, they lack explicit surface connectivity information. This makes it challenging to use existing methods that map the surface of the model into an image, also known as texture mapping. Thus, many applications either resort to hybrid approaches where both Signed Distance Fields and triangle meshes are used for different purposes, or texture mapping is not used. In these cases, it is assumed that objects have uniform material properties across large portions of their surface. We propose an algorithm that is capable of computing parametrizations (one of the most popular techniques for texture mapping) of Signed Distance Field data, that leverages an approach based on Dual Height Fields. We leverage the properties of Dual Height Fields, for efficient and effective texture mapping. We achieve this by meshing the model along the DHF direction, parametrizing the result, and then, at render time, using the DHF's natural parametrization to a plane to sample from a texture atlas. We show how our method suitably parametrizes surfaces with minimum distortion in many complex models and how it can be used for texture mapping.Science, Faculty ofComputer Science, Department ofGraduat
Detecting viewer-perceived intended vector sketch connectivity
No full textMany sketch processing applications target precise vector drawings with accurately specified stroke intersections, yet free-form artist drawn sketches are typically inexact: strokes that are intended to intersect often stop short of doing so. While human observers easily perceive the artist intended stroke connectivity, manually or even semi-manually correcting drawings to generate correctly-connected outputs is tedious and highly time consuming. We propose a novel, robust algorithm that extracts viewer-perceived stroke connectivity from inexact free-form vector drawings by leveraging observations about local and global factors that impact human perception of inter-stroke connectivity. We employ the identified local cues to train classifiers that assess the likelihood that pairs of strokes are perceived as forming end-to-end or T-junctions based on local context. We then use these classifiers within an incremental framework that combines classifier-provided likelihoods with a more global, contextual, and closure-based analysis. We demonstrate our method on over 95 diversely sourced inputs, and validate it via a series of perceptual studies; participants prefer our outputs over the closest alternative by a factor of 9 to 1.Science, Faculty ofComputer Science, Department ofGraduat
Ribbon drawing in VR : brushes and applications
No full textVirtual reality drawing applications let users draw 3D shapes using brushes that form ribbon-shaped, or ruled-surface, strokes. Each ribbon is uniquely defined by its user-specified ruling length, path, and the ruling directions at each point along this path. A collection of these virtual ribbons with proper normal orientations can communicate complex surfaces; thus, artists frequently describe their envisioned 3D surfaces by drawing dense brush strokes that cover the surface of the intended shapes. In this thesis, we analyze these ribbon brushes, and propose ways to expand the scope of their applications and improve their usability. Currently, the practical use of these drawings is limited since most geometry processing algorithms and downstream applications such as 3D printing require manifold meshes. Furthermore, existing brushes use the trajectory of a handheld controller in 3D space as the ribbon path, and compute the ruling directions using a fixed mapping from a specific controller coordinate-frame axis. This fixed mapping requires users to rotate the controller and thus their wrists to change ribbon normal or ruling directions, which requires substantial physical effort to draw even medium complexity ribbons. As people have limited ability to rotate their wrists continuously, the range of ribbon geometries they can comfortably draw with these brushes is limited. We solve these problems by first developing SurfaceBrush, a surfacing method that converts such VR drawings into user-intended manifold free-form 3D surfaces. We then present AdaptiBrush, a ribbon brush system that dramatically extends the space of ribbon geometries users can comfortably draw while enabling them to accurately predict the ribbon shape that a given hand motion produces. Our work expands the range of applications of VR drawing and makes VR drawing a viable alternative to 3D modeling for inexperienced users.Science, Faculty ofComputer Science, Department ofGraduat
Processing freehand vector sketches
No full textFreehand sketching is a fast and intuitive way for artists to communicate visual ideas, and is often the first step of creating visual content, ranging from industrial design to cartoon production. As drawing tablets and touch displays become increasingly common among professionals, a growing number of sketches are created and stored digitally in vector graphics format. This trend motivates a series of downstream sketch-based applications, performing tasks including drawing colorization, 3D model creation, editing, and posing. Even when stored digitally in vector format, hand-drawn sketches, often containing overdrawn strokes and inaccurate junctions, are different from the clean vector sketches required by these applications, which results in tedious and time-consuming manual cleanup tasks. In this thesis, we analyze the human perceptual cues that influence these two tasks: grouping overdrawn strokes that depict a single intended curve and connecting unintended gaps between strokes. Guided by these cues, we develop three methods for these two tasks. We first introduce StrokeAggregator, a method that automatically groups strokes in the input vector sketch and then replaces each group by the best corresponding fitting curve—a procedure we call sketch consolidation. We then present a method that detects and resolves unintended gaps in a consolidated vector line drawing using learned local classifiers and global cues. Finally, we propose StripMaker, a consolidation method that jointly considers local perception cues from the first method and connectivities detected by the second method. We further integrate observations about temporal and contextual information present in drawing, resulting in a method with superior consolidation performance and potential for better user interactivity. Together, this work identifies important factors in humans’ perception of freehand sketches and provides automatic tools that narrow the gap between the raw freehand vector sketches directly created by artists and the requirements of downstream computational applications.Science, Faculty ofComputer Science, Department ofGraduat
- …
