Search

Noise barrier tunnels (NBTs) are road facilities installed to reduce road traffic noise. Although building information modeling (BIM) has been widely used in civil engineering, alignment problems m...

Eurographics Symposium on Geometry Processing 2020, ; Computer graphics forum 39(5), 163-172 (2020). doi:10.1111/cgf.14076, Published by Wiley-Blackwell, Oxford

In this paper, a boundary element-based approach is proposed for partitioning a planar domain automatically into a set of 4-sided regions, which is suitable for semi-structured quad mesh generation. The basic idea is to generate a smooth cross-field via solving PDEs with the boundary element method and then partition the input domain by extracting singular structures of the cross-field. Firstly, a cross is configured at each boundary vertex of the input domain. Then, two Laplacian equations are selected as the governing equation to smoothly propagate the crosses defined on the boundary into the interior of the domain. To obtain an accurate cross-field, the boundary element method is used to solve the governing equations. Then the singular vertices are identified by analyzing the structure of the cross-field, and the streamlines emanating from these points are traced and simplified as segmentation curves to partition the domain. Finally, to demonstrate the efficiency and effectiveness of the proposed approach, some quad mesh generation examples and comparison with previous approaches are presented.

We introduce an algorithm for computing the two-sided Hausdorff distance between a triangle mesh and a quad mesh, guaranteed to be within the given error bound, which can be machine precision-level small. The algorithm expands upon a recent breakthrough that only calculates the one-sided Hausdorff distance from the triangle mesh to the quad mesh using what is called “matching” and “upper bounding” of candidate pieces. We complete the algorithm by accomplishing the computation of the one-sided Hausdorff distance in the opposite direction: from the quad mesh to the triangle mesh. We split each quad into two triangular pieces to simplify the breakdown of matching cases and provide additional matching methods for new cases. By fusing the two one-sided computation algorithms, one can compute the two-sided Hausdorff distance that, for instance, can properly evaluate a quad mesh approximation of a triangle mesh. Experimental results show that our algorithm can handle near-zero Hausdorff distance, which has always been known to be a much difficult task, in an interactive time. Moreover, the improvement in efficiency of the two-sided Hausdorff distance computation over the successive execution of the two one-sided computations is addressed.

This paper presents a semi-global method to simplify the structure of an all-quad mesh. The simplification aims to reduce the number of singularities, while preserving boundary features. The simplification operations of our method are based on the separatrices connecting adjacent singularities. The proposed semi-global method can handle quad-meshes with complex structures (e.g., quad-meshes obtained via Catmull-Clark subdivision of the triangle meshes) and produce quad meshes with much simpler structures.

We propose a method for extracting auxetic patterns from meshes for fabrication by modifying the existing mesh primitives directly and fully automatically. This direct approach is novel in the sense that most of the fabricationoriented surface tiling methods introduce additional primitives, such as curve networks in an interactive semiautomatic framework. Our method is based on a remeshing procedure that converts a given quad mesh with arbitrary topology into our desired structure that is ready to be fabricated. The main advantages of establishing auxetic patterns on meshes are the achieved flexibility using cheap inflexible materials as well as less material usage and fabrication time, as demonstrated in our results.

In an augmented reality project dealing with complex objects with a large scale, it is necessary to minimize the number of polygons of a mesh. The challenge is trying to find a compromise between accuracy, details and fluidity of the representation. Starting from two different surveys (Laser Scanner and Photogrammetry) with high resolution, two paths have been identified: the first one consists on the retopology of the mesh obtained from the point cloud with the help of software like Instant Mesh; the second one relies on the complete re-modelling of the artefact, trying to simplify its structure in macro-elements using Retopoflow tool in Blender. The level of detail is preserved in both cases: in the first, the “quad mesh” keeps complex geometries minimizing the number of polygons; in the other an accurate management of texture of PBR materials returns realism with simple shapes, with a lower number of polygons. These methods have been applied to the reconstruction of San Lorenzo Bridge, one of the ancient monuments of the Roman Padova no longer visible, examined by the research project PD-Invisible. Results validate that the second method is more effective, ensuring an excellent realism in the rendering phases, minimizing the size of the file.

We present an algorithm that computes the one-sided Hausdorff distance from a triangle mesh to a quad mesh. Our algorithm is much more robust than previous ones in the sense that memory requirement is vastly reduced, by avoiding storing combinatorial pairs of each two input model's parts. Meanwhile, point projection via uniform grid greatly accelerates the algorithm. Experimental results show that even for cases where the Hausdorff distance is near zero, its precise computation is done in an interactive speed, while memory consumption is easily manageable.

We propose a novel sampling algorithm for quad mesh generation. The nodes are considered as (positive and negative) charged particles that interact and evolve in space. The mesh connectivity, which is built after the particle evolution, naturally corresponds to the ionic bonds. This meshing process is inspired by NaCl crystallization and the result mimics its natural structure. Experiments demonstrate the effectiveness of this new sampling and meshing model for tessellating 2D regions.

Maritime Theatre is one of the most iconic buildings of Hadrian's Villa (UNESCO site since 1999). This circular-shaped “domus” is characterized by one of the most obvious aspects of Hadrianic architectural production, namely the alternation of curved and straight lines applied to designing both plans and elevations. Mixtilinear features caught the interest of architects from the Renaissance to present day, becoming inspiration as well as a sort of “quarry” for noble families and antiquarians. Complex entablatures designed by Hadrian's architects have been systematically removed and reused starting from Middle Ages with the consequence of having several fragments scattered in private and public collections all over Europe. Through a systematic digital survey of remaining structures as well as of removed elements, a 3D analytical model was exploited in order to include all the “digitally gathered” elements and for deepening the knowledge of this emblematic mixtilinear architecture.

Convolution surfaces with 1D skeletons have been limited to close-to-circular normal sections. The new formalism presented here allows for ellipsoidal normal sections. Anisotropy is prescribed on G 1 skeletal curves, chosen as circular splines, by a rotation angle and the three radii of an ellipsoid at each extremity. This lightweight model creates smooth shapes that previously required tweaking the skeleton or supplementing it with 2D pieces. The scale invariance of our formalism achieves excellent radii control and thus lends itself to approximate a variety of shapes. The construction of a scaffold is extended to skeletons with G 1 branches. It projects onto the convolution surface as a quad mesh with skeleton bound edge-flow.

Quad meshes can be interpreted as tensor-product spline control meshes as long as they form a regular grid, locally. We present a new option for complementing bi-3 splines by bi-4 splines near irregularities in the mesh layout, where less or more than four quadrilaterals join. These new generalized surface and IGA (isogeometric?analysis) elements have as their degrees of freedom the vertices of the irregular quad mesh. From a geometric design point of view, the new construction distinguishes itself from earlier work by a notably better distribution of highlight lines. From the IGA point of view, increased smoothness and reproduction at the irregular point?yield fast convergence. Bi-3 tensor-product splines are complemented by bi-4 splines near irregular points.The vertices of the irregular quad mesh serve as spline-like control points.The resulting surfaces have a good distribution of highlight lines.The resulting surfaces have a increased smoothness and reproduction at irregular points.

We develop a structured quad meshing algorithm for large-scale 2D geometric regions based on solving a low-distorted poly-square map. The poly-square map is constructed through a divide-and-conquer strategy in a distributed way. First, a geometry-aware partitioning is performed to decompose the geometric region into solvable subparts. Then, parameterizations and meshing are computed on subregions under certain boundary constraints. The local results are merged and refined through a multi-pass optimization until the global convergence of the polysquare map is achieved. We demonstrate that our algorithm can process huge geometric model effectively on high performance clusters.

New techniques are presented for using the medial axis to generate high quality decompositions for generating block-structured meshes with well-placed mesh singularities away from the surface boundaries. Established medial axis based meshing algorithms are highly effective for some geometries, but in general, they do not produce the most favourable decompositions, particularly when there are geometry concavities. This new approach uses both the topological and geometric information in the medial axis to establish a valid and effective arrangement of mesh singularities for any 2-D surface. It deals with concavities effectively and finds solutions that are most appropriate to the geometric shapes. Methods for directly constructing the corresponding decompositions are also put forward.

In this paper, we present a new interpolation subdivision scheme for mixed triangle/quad meshes that is C^1 continuous. The new scheme is capable of reproducing the well-known four-point based interpolation subdivision in the quad region but does not reproduce Butterfly subdivision in the triangular part. The new scheme defines rules that produce surfaces both at the regular quad/triangle vertices and isolated, extraordinary points. We demonstrate the visually satisfying of our surfaces through several examples.

A new indirect way of producing all-quad meshes is presented. The method takes advantage of a well known algorithm of the graph theory, namely the Blossom algorithm that computes the minimum cost perfect matching in a graph in polynomial time. Then, the triangulation itself is taylored with the aim of producing right triangles in the domain. This is done using the infinity norm to compute distances in the meshing process. The alignement of the triangles is controlled by a cross field that is defined on the domain. Meshes constructed this way have their points aligned with the cross field direction and their triangles are almost right everywhere. Then, recombination with our Blossom-based approach yields quadrilateral meshes of excellent quality.

Displacement mapping refers to a technique for rendering a high-frequency surface by adding geometric details encoded in a displacement map to a low-frequency base surface. This paper proposes a method for indirectly accessing the base surface using a special displacement map and then carrying out scalar displacement. Given a high-frequency triangle mesh, a coarse PN (point-normal) quad mesh is computed as the base surface. The parameters used to evaluate the base surface are precomputed such that scalar displacement from the evaluated points reaches the features of the original surface. The parameters are stored in the displacement map together with the displacement scalars. The run-time algorithm uses the hardware tessellation capability of GPU and reconstructs the high-frequency surface. Using the proposed method, surface features are accurately preserved, surface deformation is well supported, LOD control becomes quite flexible, and the base surface can be extremely simplified.

Detailed analysis of brain structures is essential in identifying anatomical biomarkers in Alzheimer's disease (AD). In this paper, we develop a new radial distance model to compare different hippocampal shapes and measure their atrophies over time. Using harmonic mappings, we project hippocampal surfaces onto cylinders to obtain evenly-spaced quadrilateral meshes. Surface radial distances estimated via the quad-meshes are invariant to global shifts in the surrounding tissues, leading to a powerful way to detect localized anatomical progressions. The novel quad-meshing method also provides an efficient means to align anatomical surfaces across subjects. Through regions of interest (ROI) analysis, we extract discriminative patches of radial distance and atrophy, and utilize them as anatomical features for patient classification. The effectiveness of the proposed surface modeling and feature extraction strategies in identifying shape biomarkers for AD/MCI is evaluated using the ADNI dataset.

New techniques are presented for using the medial axis to generate decompositions on which high quality block-structured meshes with well-placed mesh singularities can be generated. Established medial-axis-based meshing algorithms are effective for some geometries, but in general, they do not produce the most favourable decompositions, particularly when there are geometric concavities. This new approach uses both the topological and geometric information in the medial axis to establish a valid and effective arrangement of mesh singularities for any 2-D surface. It deals with concavities effectively and finds solutions that are most appropriate to the geometric shapes. Resulting meshes are shown for a number of example models. A novel method is described for using the medial axis for block-structured meshing.The hitherto neglected angular information in the medial axis is shown to be useful.Geometry concavities are dealt with effectively.The surface is decomposed into m-sided and submappable subregions.The final meshes are of high quality for all types of 2-D geometry.

We present a method for the global parametrization of meshes that preserves alignment to a cross field in input while obtaining a parametric domain made of few coarse axis-aligned rectangular patches, which form an abstract base complex without T-junctions. The method is based on the topological simplification of the cross field in input, followed by global smoothing.

Given an n-sided region bounded by a loop of n polylines, we present a general algorithm to fill such a region by a quad mesh suitable for a subdivision scheme. Typically, the approach consists of two phases: the topological phase and the geometrical phase. In the first part, the connectivity of the mesh is based on determining a partitioning of the region into rectangular subregions across which regular grid could be constructed. The geometrical phase generalizes discrete Coon's patches to position the vertices in the 3D space. The generated mesh could be taken as input to any quad-based subdivision scheme, such as that of Catmull–Clark or Doo–Sabin to generate the corresponding limit surface. The goal of the algorithm is to generate smooth meshes with minimum number and less valence of extraordinary vertices deemed undesirable in such subdivision schemes.

We describe algorithms for canonically partitioning semi-regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions---we prove that optimizing this number is NP-hard, but it can be efficiently approximated.

Starting from the triangle mesh of a digital shape, that is, mainly an articulated object, we produce a coarse quad layout that can be used in character modeling and animation. Our quad layout follows the intrinsic object structure described by its curve skeleton; it contains few irregular vertices of low degree; it can be immediately refined into a semiregular quad mesh; it provides a structured domain for UV mapping and parametrization. Our method is fast, one-click, and does not require any parameter setting. The user can steer and refine the process through simple interactive tools during the construction of the quad layout.

Nearly every 2D game uses sprites and tilesets, in one form or another. Games such as Phantasy Star, Zelda, Final Fantasy, Dizzy, Contra, Donkey Kong, Mario, Sonic, and others, have all used sprites and tiles. Some games use them in a conventional and obvious way while some less so. But the very fact that jargon terms exist for these two concepts is testament to their prevalence in games. The sprite is to 2D games what a mesh is to 3D games; and tilesets find their closest 3D equivalent in the static and modular geometry of the scene.

Technical Report / ETH Zurich, Department of Computer Science, 784

This chapter ranks as one of the most important in the book. Here, we’ll create a new ScriptableWizard Editor extension that’ll generate Atlas Textures. What is an Atlas Texture? And what does creating one achieve? To answer the first question, imagine this: you’ve created lots of different sprite images for your 2D game (all at different pixel dimensions)—one file for the player, one for each enemy, and one for each prop and power-up. That’s probably a lot of files! Then, you copy and paste them all into one, larger image file, consolidating them neatly into rows and columns. In doing this, you’ve just created an Atlas Texture the manual way. Now why is an Atlas Texture useful? Essentially, they offer us several benefits when we use them in Unity for our objects, as opposed to using many different textures. These benefits are listed here

The previous chapter explained how to develop a GUI editor add-in that allows users to add selected textures in the project panel to a larger atlas texture. Atlas Textures help us improve the performance of our 2D games. In generating the atlas, we also saved meta-data. This included all filenames of textures inside the atlas, and their UV positions within the atlas. In closing that chapter, we tested the add-on functionality by assigning an Atlas Texture to a procedural Quad Mesh in the scene, to see how it looked in the Viewport. The problem we faced was that the quad mesh rendered the complete atlas texture, rather than just a region of it (see Figure 7-1). The problem was not with the Atlas Texture, but with the mesh itself; with its UV mapping. By default, the UV mapping for Quad Meshes is configured to show a complete texture. To show only a region, the UV mapping must be adjusted at the vertex level. That is, we must dig deeper into the mesh construction and edit its vertices. We’ll do that in this chapter, as we create a new editor add-in to control mesh UV mapping. This add-on lets us select a textured quad in the scene and entirely customize its UV mapping to show any region within the Atlas Texture (or within any texture!). In addition, we’ll also create another class to change UV mapping over time, creating a flipbook animation effect or an animated sprite effect.

This work deals with the parameterization of simplicial surfaces, that is, generation of a mapping between a surface and the Euclidean plane. Through this correspondence, the existing structure of the plane is transferable onto the surface. For example, the plane possesses a natural division into unit squares, and using the parameterization map one can transfer this structure onto the surface. Applications of this are, for example, remeshing and texturing of surfaces and the creation of control grids for subdivision or NURBS surfaces. Parameterization maps usually have to meet a number of quality criteria, important examples are small angle and length distortion. In addition, it is often demanded that the gradient of the parameterization function are aligned with the direction of surface features such as sharp bends and edges. Our QuadCover method, which forms the basis of this thesis, generates a parameterization automatically from a tensor field of feature directions. The method builds on the fact that such multi-dimensional direction fields can be interpreted as one-dimensional vector fields on a branched covering of the surface. In this way, known results about vector fields, such as Hodge decomposition, can be applied. On this basis, QuadCover finds a parameterization that aligns as close as possible to a given direction field. Parameterizations of highest quality additionally require that length and angle distortion are minimized. For this, the number and location of branch points of the direction field is critical. In this work, we are pursuing several approaches: First, we show with a new method that the movement and especially the creation of branch points can drastically reduce distortion. Second, the distortion that is caused by the existence of branch points is reduced significantly by using a sophisticated rounding method. The third approach opposes the different types of distortion of the two former steps, and infers the optimal number of branch points out of them. The combination of the approaches makes it possible surpass even recent algorithms in terms of distortion., Die vorliegende Arbeit befasst sich mit der Parametrisierung simplizialer Flächen. Darunter versteht man das Erzeugen einer Abbildung zwischen einer Fläche und der euklidische Ebene, um durch diese Korrespondenz die vorhandene Struktur der Ebene auf der Fläche nutzbar zu machen. Zum Beispiel besitzt die Ebene eine natürliche Rasterung in Einheitsquadrate, die mithilfe der Parametrisierungsfunktion auf die Fläche übertragen werden kann. Anwendungen hierfür sind zum Beispiel die Neuvernetzung und Texturierung von Flächen, und die Erstellung von Kontrollnetzen zur Generierung von Subdivisions- oder NURBS-Flächen. Parametrisierungsfunktionen haben meist eine Reihe von Gütekriterien zu erfüllen, wichtig ist zum Beispiel geringe Längen- und Winkelverzerrung. Oft ist zusätzlich gefordert, dass die Gradienten der Abbildung mit der Ausrichtung von Flächenmerkmalen – etwa von scharfen Kanten – übereinstimmen. Unser QuadCover-Verfahren, das die Grundlage dieser Arbeit bildet, erzeugt automatisch aus einem Tensorfeld von Merkmalsrichtungen eine Parametrisierung. Das Verfahren basiert auf der Grundlage, dass diese mehrdimensionalen Tensorfelder als eindimensionale Vektorfelder auf einer verzweigten Überlagerung der Fläche interpretiert werden können. Auf diese Weise können bekannte Resultate über Vektorfelder, zum Beispiel die Hodge- Zerlegung, angewendet werden. Auf dieser Basis findet QuadCover die Parametrisierung, die einem gegebenen Richtungsfeld am nächsten kommt. Für Parametrisierungen höchster Güte muss zusätzlich die Längen- und Winkelverzerrung minimiert werden. Hierfür ist die Anzahl und Position von Verzweigungspunkten im Richtungsfeld entscheidend. In dieser Arbeit setzen wir an drei unterschiedlichen Punkten an: Erstens, zeigen wir mit einem neuen Verfahren, dass die Verzerrung durch das Verschieben und vor allem durch das Erschaffen von Verzweigungspunkten drastisch minimiert werden kann. Zweitens wird die Verzerrung, die durch die Existenz von Verzweigungspunkten entsteht, durch ein neues Rundungsverfahren deutlich stärker verringert als mit bisherigen Methoden. Der dritte Ansatz stellt die unterschiedlichen Arten von Verzerrung der zuvor genannten Verfahren gegenüber, so dass daraus die optimale Anzahl von Verzweigungspunkten bestimmt werden kann. Die Kombination der Ansätze erlaubt es, auch neue Verfahren hinsichtlich der Verzerrung zu übertreffen.

I started learning JavaScript and WebGL for fun in my free time on evenings and weekends. For most of my career, I’ve programmed large enterprise applications in C++ and, on occasion, I’ve written some data visualizations using desktop OpenGL. 3D content on the web is something that I’ve been waiting for a while to happen, so when the news of the upcoming WebGL specification arrived, I could not wait to try it out. The technological opportunity coincided with an idea I’ve been nurturing for a while: taking the concept of an old ’80s game that is usually played in a 2D setting and somehow translating it into the 3D world. Some ideas that I considered include: A PAC-MAN game in a maze situated on a deformed, closed surface. A Qix-like game (aka Xonix, Volfied) where the player needs to conquer as much area as possible of the surface of a 3D shape, trying to avoid enemies and obstacles. Scorched Earth, a turn-based warfare game between players on a small, 3D planet floating in space. Q*bert, which features a little creature that paints stairs as he steps on them, trying to cover an entire staircase. Instead of filling just one flight of stairs, play on a complete, 3D world made of cubes.

Direction fields, line fields and cross fields are used in a variety of computer graphics applications ranging from non-photorealistic rendering to remeshing. In many cases, it is desirable that fields adhere to symmetry, which is predominant in natural as well as man-made shapes. We present an algorithm for designing smooth N-symmetry fields on surfaces respecting generalized symmetries of the shape, while maintaining alignment with local features. Our formulation for constructing symmetry fields is based on global symmetries, which are given as input to the algorithm, with no isometry assumptions. We explore in detail the properties of generalized symmetries (reflections in particular), and we also develop an algorithm for the robust computation of such symmetry maps, based on a small number of correspondences, for surfaces of genus zero.

In this paper we present an innovative approach to incremental quad mesh simplification, i.e. the task of producing a low complexity quad mesh starting from a high complexity one. The process is based on a novel set of strictly local operations which preserve quad structure. We show how good tessellation quality (e.g. in terms of vertex valencies) can be achieved by pursuing uniform length and canonical proportions of edges and diagonals. The decimation process is interleaved with smoothing in tangent space. The latter strongly contributes to identify a suitable sequence of local modification operations. The method is naturally extended to manage preservation of feature lines (e.g. creases) and varying (e.g. adaptive) tessellation densities. We also present an original Triangle- to-Quad conversion algorithm that behaves well in terms of geometrical complexity and tessellation quality, which we use to obtain the initial quad mesh from a given triangle mesh.

The modification of hexahedral meshes is difficult to perform since their structure does not allow easy local refinement or un-refinement such that the modification does not go through the boundary. In this paper we prove that the set of hex flipping transformations of Bern et. al. [1] is the only possible local modification on a geometrical hex mesh with less than 5 edges per vertex. We propose a new basis of local transformations that can generate an infinite number of transformations on hex meshes with less than 6 edges per vertex. Those results are a continuation of a previous work [9], on topological modification of hexahedral meshes. We prove that one necessary condition for filling the enclosed volume of a surface quad mesh with compatible hexes is that the number of vertices of that quad mesh with 3 edges should be no less than 8. For quad meshes, we show the equivalence between modifying locally the number of quads on a mesh and the number of its internal vertices.

We convert any quad manifold mesh into an at least C1 surface consisting of bi-cubic tensor-product splines with localized perturbations of degree bi-5 near non-4-valent vertices. There is one polynomial piece per quad facet, regardless of the valence of the vertices. Particular care is taken to derive simple formulas so that the surfaces are computed efficiently in parallel and match up precisely when computed independently on the GPU.