Search

In this article, we investigate geometric properties and modeling capabilities of quad meshes with planar faces whose mesh polylines enjoy the additional property of being contained in a single plane. This planarity is a major benefit in architectural design and building construction: If a structural element is contained in a plane, it can be manufactured on the ground without scaffolding and put into place as a whole. Further, the plane it is contained in serves as part of a so-called support structure. We discuss design of meshes under the requirement that one half of mesh polylines are planar ("P meshes"), and we also investigate the geometry and design of meshes where all polylines enjoy this property ("PP meshes"). We work in the space of planes and with appropriate transformations of that space. We also incorporate further properties relevant for architectural design, such as near-rectangular panels and repetitive nodes. We provide geometric insights, give explicit constructions, and show an approach to geometric modeling of both P meshes and PP meshes, in particular, the case of nearly rectangular panels. [ABSTRACT FROM AUTHOR]

Edge detection is a common image‐processing technique that has numerous applications. In this article, we propose an algorithm for detecting edges based on the color of a mesh surface. We name the edges the color boundaries. Our approach is based on the data structure of a quad mesh, which makes the data structure of 3D meshes resemble the data structure of images. As a result, image‐processing methods can be applied on the 3D meshes. In this article, six classical edge detection filters are implemented on the 3D meshes. The experimental results demonstrate that our method can identify areas of high color gradient on 3D meshes. A comparison with two other methods for detecting color boundaries on 3D meshes reveals that our method is more effective at detecting boundaries. Lastly, we propose two novel applications that utilize the information of color boundaries on a 3D mesh surface. [ABSTRACT FROM AUTHOR]

In this paper, we present a structure simplification framework for planar all-quad meshes with open boundaries. Our simplification framework can handle quad meshes with complex structures (e.g., quad meshes obtained via Catmull–Clark subdivision of the triangle meshes) to produce simpler meshes while preserving the boundary features. To achieve that, we introduce a set of separatrix-based semi-global operations and combine them with existing local operations to develop a new simplification framework. Additionally, we organize and order the individual simplification operations into groups and employ ranking strategies for each group to sort these operations to produce quad meshes with better quality and simpler structure. We provide a comprehensive evaluation of our framework using different input parameters on a number of representative planar quad meshes with various boundary configurations. To demonstrate the advantages of our method, we compare it with a few existing frameworks. Our comparison shows that our simplification framework usually produces simpler structure with faster computation than the state-of-the-art methods. [Display omitted] • Structure simplification used to optimize structural complexity of planar quad meshes. • Existing local and global simplification may produce sub-optimal results. • Semi-global simplification utilizes separatrices to perform simplification. • A new framework combines, organizes, and ranks semi-global and local operations. • Results show that the new framework outperforms existing simplification methods. [ABSTRACT FROM AUTHOR]

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 must first be addressed for BIM to be applied in transportation infrastructure; this is because unlike buildings, roads are linear. The array of tunnel frames based on the centerlines of individual roads cause the discontinuity of components at junctions of two NBTs. This leads to structural instabilities and poor airtightness, which in turn cause vulnerabilities such as noise and water leakage. To address these issues, this study proposes an optimization design method for NBT junctions using quad meshes. We created a Y-branch topology of NBTs using quad meshes, performed data arrangement using mesh segmentation and mesh reorder, and used the results to optimize the design via performance analysis. During mesh segmentation and mesh reorder, an interface in which the user directly enters curves to improve the efficiency of the algorithm was also developed. In addition, a case study of a main road with eight lanes that merged with a sub road with one lane was conducted, data arrangement was performed successfully, and a BIM-compliant model that used various geometric data was generated through optimization.

We describe a method for the generation of seamless surface parametrizations with guaranteed local injectivity and full control over holonomy. Previous methods guarantee only one of the two. Local injectivity is required to enable these parametrizations' use in applications such as surface quadrangulation and spline construction. Holonomy control is crucial to enable guidance or prescription of the parametrization's isocurves based on directional information, in particular from cross-fields or feature curves, and more generally to constrain the parametrization topologically. To this end we investigate the relation between cross-field topology and seamless parametrization topology. Leveraging previous results on locally injective parametrization and combining them with insights on this relation in terms of holonomy, we propose an algorithm that meets these requirements. A key component relies on the insight that arbitrary surface cut graphs, as required for global parametrization, can be homeomorphically modified to assume almost any set of turning numbers with respect to a given target cross-field. [ABSTRACT FROM AUTHOR]

Isogeometric Analysis (IGA) necessitates quadrilateral meshing owing to the utilization of NURBS or other locally tensor-product spline functions as the foundation for its analysis. It is a widely held misconception that the generation of cross fields over the surface domain – a common precursor to quad-mesh construction – establishes equivalence between cross fields and quad-meshes. In this study, we dispel this notion by presenting theorems that distinctly delineate the singularity configurations of both cross fields and quad-meshes. It is posited that these can be viewed as characteristic classes of different fiber bundles, where cross field singularity aligns with the cross fiber bundle and structured mesh singularity corresponds to holomorphic line bundles. As a result, the conditions necessitating quad-mesh singularities are decidedly more stringent than those for cross field singularities. This explains a notable query in the field: the absence of a 3-5 quad-mesh (a quad-mesh with two singularities with topological valence 3 and 5 respectively) on a torus. Additionally, the theoretical framework is broadened to incorporate other types of structured meshes. The formulated theorems give rise to practical algorithms for cross field construction and structured mesh generation. The efficacy and applicability of these algorithms are corroborated through numerical examples that not only validate the theoretical findings but also underscore their practical usability. [ABSTRACT FROM AUTHOR]

• Efficient algorithm for computing the two-sided Hausdorff distance between a triangle mesh and a quad mesh. • Specialized algorithm for handling the cases of near-zero Hausdorff distance in an interactive speed. • Guarantee on the approximation error of the Hausdorff distance to be within an arbitrarily given error bound, which can be machine precision-level small. Two-sided Hausdorff Distance Computation Progress 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We present a novel method to generate quad meshes for non-rigid objects. Our method takes into account the geometry of a collection of key poses in one-to-one correspondence or even an entire animation sequence. From this input, on a common computational domain, an extremal metric is computed that captures the local worst case behavior in terms of distortion as the object undergoes deformation. An anisotropic, non-uniformly sized quad mesh is then generated based on this metric. This mesh avoids undersampling when deformed into any of the poses specified in the input and thus reduces artifacts. Hence, in contrast to previous approaches which target static geometry, our method aims to optimize the mesh's adaptation to the shape for every pose expected during animation or deformation rather than for one specific reference state. [ABSTRACT FROM AUTHOR]

We compute the shortest sequence of local connectivity modifications that transform a genus 0 quad mesh to a polycube. The modification operations are (dual) loop preserving and thus, we are restricted to quad meshes where loops don't self-intersect and two loops intersect at most twice. The intersection patterns of the loops are encoded in a simplicial complex, which we call loop complex. To formulate the modification search over the loop complex, we characterise polycubes combinatorially and determine dependencies between modifications. We show that the full task can be encoded as a mixed-integer problem that is solved by a commodity MIP-solver. We demonstrate the practical feasibility by a number of examples with varying complexity. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper presents a method that takes a collection of 3D surface shapes, and produces a consistent and individually feature preserving quadrangulation of each shape. By exploring the correspondence among shapes within a collection, we coherently extract a set of representative feature lines as the key characteristics for the given shapes. Then we compute a smooth cross-field interpolating sparsely distributed directional constraints induced from the feature lines and apply the mixed-integer quadrangulation to generate the quad meshes. We develop a greedy algorithm to extract aligned cut graphs across the shape collection so that the meshes can be aligned in a common parametric domain. Computational results demonstrate that our approach not only produces consistent quad meshes across the entire collection with significant geometry variation but also achieves a trade-off between global structural simplicity for the collection and local geometry fidelity for each shape. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

SUMMARY We present a fully automatic procedure for the mesh generation of tubular geometries such as blood vessels or airways. The procedure is implemented in the open-source Gmsh software and relies on a centerline description of the input geometry. The presented method can generate different type of meshes: isotropic tetrahedral meshes, anisotropic tetrahedral meshes, and mixed hexahedral/tetrahedral meshes. Additionally, a multiple layered arterial wall can be generated with a variable thickness. All the generated meshes rely on a mesh size field and a mesh metric that is based on centerline descriptions, namely the distance to the centerlines and a local reference system based on the tangent and the normal directions to the centerlines. Different examples show that the proposed method is very efficient and robust and leads to high quality computational meshes. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of approximate topological matching for quadrilateral meshes, that is, the problem of finding as large a set as possible of matching portions of two quadrilateral meshes. This study is motivated by applications in graphics that involve the modeling of different shapes that have results needing to be merged in order to produce a final unified representation of an object. We show that the problem of producing a maximum approximate topological match of two quad meshes is NP-hard and that its decision version is NP-complete. Given these results, which make an exact solution extremely unlikely, we show that the natural greedy algorithm derived from polynomial-time graph isomorphism can produce poor results, even when it is possible to find matches with only a few nonmatching quads. Nevertheless, we provide a “lazy-greedy” algorithm that is guaranteed to find good matches when mismatching portions of mesh are localized. Finally, we provide empirical evidence that this approach produces good matches between similar quad meshes. [ABSTRACT FROM AUTHOR]

In architectural freeform design, the relation between shape and fabrication poses new challenges and requires more sophistication from the underlying geometry. The new concept of conical meshes satisfies central requirements for this application: They are quadrilateral meshes with planar faces, and therefore particularly suitable for the design of freeform glass structures. Moreover, they possess a natural offsetting operation and provide a support structure orthogonal to the mesh. Being a discrete analogue of the network of principal curvature lines, they represent fundamental shape characteristics. We show how to optimize a quad mesh such that its faces become planar, or the mesh becomes even conical. Combining this perturbation with subdivision yields a powerful new modeling tool for all types of quad meshes with planar faces, making subdivision attractive for architecture design and providing an elegant way of modeling developable surfaces. [ABSTRACT FROM AUTHOR]