The medial axis transform (MAT), as an intrinsic shape representation, plays an important role in shape approximation, recognition and retrieval. Q-MAT is a state-of-the-art algorithm driven by ...quadratic error minimization to compute a geometrically precise, structurally concise, and compact representation of the MAT for 3D shapes. In this work we extend the technique to make it more robust, controllable, and name it Q-MAT+. Combining shape diameter function (SDF) and other mesh information, Q-MAT+ gets a more complete and accurate initial MAT than Q-MAT, even for extreme thin features, such as wires and sheets. Q-MAT+ could quickly remove insignificant branches while preserving significant ones to get a simple and faithful piecewise linear approximation of the MAT. Moreover, it performs the medial axis simplification with explicit maintenance and the control of Hausdorff error, which is not originally supported in Q-MAT. We further demonstrate the outstanding efficiency and accuracy of our method compared with other existing approaches for MAT generation and simplification.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
2.
Shape-Based Measures Improve Scene Categorization Rezanejad, Morteza; Wilder, John; Walther, Dirk B. ...
IEEE transactions on pattern analysis and machine intelligence,
04/2024, Volume:
46, Issue:
4
Journal Article
Peer reviewed
Converging evidence indicates that deep neural network models that are trained on large datasets are biased toward color and texture information. Humans, on the other hand, can easily recognize ...objects and scenes from images as well as from bounding contours. Mid-level vision is characterized by the recombination and organization of simple primary features into more complex ones by a set of so-called Gestalt grouping rules. While described qualitatively in the human literature, a computational implementation of these perceptual grouping rules is so far missing. In this article, we contribute a novel set of algorithms for the detection of contour-based cues in complex scenes. We use the medial axis transform (MAT) to locally score contours according to these grouping rules. We demonstrate the benefit of these cues for scene categorization in two ways: (i) Both human observers and CNN models categorize scenes most accurately when perceptual grouping information is emphasized. (ii) Weighting the contours with these measures boosts performance of a CNN model significantly compared to the use of unweighted contours. Our work suggests that, even though these measures are computed directly from contours in the image, current CNN models do not appear to extract or utilize these grouping cues.
We propose a framework for the interactive simulation of nonlinear deformable objects. The primary feature of our system is the seamless integration of deformable simulation and collision culling, ...which are often independently handled in existing animation systems. The bridge connecting them is the medial axis transform (MAT), a high-fidelity volumetric approximation of complex 3D shapes. From the physics simulation perspective, MAT leads to an expressive and compact reduced nonlinear model. We employ a semireduced projective dynamics formulation, which well captures high-frequency local deformations of high-resolution models while retaining a low computation cost. Our key observation is that the most compelling (nonlinear) deformable effects are enabled by the local constraints projection, which should not be aggressively reduced, and only apply model reduction at the global stage. From the collision detection (CD)/collision culling (CC) perspective, MAT is geometrically versatile using linear-interpolated spheres (i.e., the so-called medial primitives (MPs)) to approximate the boundary of the input model. The intersection test between two MPs is formulated as a quadratically constrained quadratic program problem. We give an algorithm to solve this problem exactly, which returns the deepest penetration between a pair of intersecting MPs. When coupled with spatial hashing, collision (including self-collision) can be efficiently identified on the GPU within a few milliseconds even for massive simulations. We have tested our system on a variety of geometrically complex and high-resolution deformable objects, and our system produces convincing animations with all of the collisions/self-collisions well handled at an interactive rate.
•Automatic building outline extraction, required by various spatial modeling applications and mapping, remains challenging due to object and data complexities.•Skeletonization encodes topological ...information of point cloud data that can be used to extract object boundaries but it has traditional drawback due to its instability to small perturbations.•We proposed a robust medial axis transform (MAT) based skeletonization method and designed a novel segmentation procedure for MAT points that allows to efficiently identify building corner points.
Automatic building extraction and delineation from airborne LiDAR point cloud data of urban environments is still a challenging task due to the variety and complexity at which buildings appear. The Medial Axis Transform (MAT) is able to describe the geometric shape and topology of an object, but has never been applied for building roof outline extraction. It represents the shape of an object by its centerline, or skeleton structure instead of its boundary. Notably, end points of the MAT in principle coincide with corner points of building outlines. However, the MAT is sensitive to small boundary irregularities, which makes shape detection in airborne point clouds challenging. We propose a robust MAT-based method for detecting building corner points, which are then connected to form a building boundary polygon. First, we approximate the 2D MAT of a set of building edge points acquired by the alpha-shape algorithm to derive a so-called building roof skeleton. We then propose a hierarchical corner-aware segmentation to cluster skeleton points based on their properties which are the so-called separation angle, radius of the maximally inscribe circle, and defining edge point indices. From each segment, a corner point is then estimated by extrapolating the position of the zero radius inscribed circle based on the skeleton point positions within the segment. Our experiment uses point cloud datasets of Makassar, Indonesia and EYE-Amsterdam, The Netherlands. The average positional accuracy of the building outline results for Makassar and EYE-Amsterdam is 65 cm and 70 cm, respectively, which meet one-meter base map accuracy criteria. The results imply that skeletonization is a promising tool to extract relevant geometric information on e.g. building outlines even from far from perfect geographical point cloud data.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
This paper presents a novel methodology to generate deposition paths for wire and arc additive manufacturing (WAAM). The medial axis transformation (MAT), which represents the skeleton of a given ...geometry, is firstly extracted to understand the geometry. Then a deposition path that is based on the MAT is efficiently generated. The resulting MAT-based path is able to entirely fill any given cross-sectional geometry without gaps. With the variation of step-over distance, material efficiency alters accordingly for both solid and thin-walled structures. It is found that thin-walled structures are more sensitive to step-over distance in terms of material efficiency. The optimal step-over distance corresponding to the maximum material efficiency can be achieved for various geometries, allowing the optimization of the deposition parameters. Five case studies of complex models including solid and thin-walled structures are used to test the developed methodology. Experimental comparison between the proposed MAT-based path patterns and the traditional contour path patterns demonstrate significant improved performance in terms of gap-free cross-sections. The proposed path planning strategy is shown to be particularly beneficial for WAAM of thin-walled structures.
•A novel path planning methodology based on the Medial Axis Transformation (MAT) of the geometry is proposed.•Gap-free paths can be obtained for any arbitrarily shaped geometry.•Relationships between step-over distance and material efficiency are analysed.•Optimal step-over distances for different Additive Manufacturing (AM) systems are discussed.•The proposed path planning strategy is particularly useful for wire and arc additive manufacturing of thin-walled structures.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
Segmenting arbitrary 3D objects into constituent parts that are structurally meaningful is a fundamental problem encountered in a wide range of computer graphics applications. Existing methods for 3D ...shape segmentation suffer from complex geometry processing and heavy computation caused by using low-level features and fragmented segmentation results due to the lack of global consideration. We present an efficient method, called SEG-MAT , based on the medial axis transform (MAT) of the input shape. Specifically, with the rich geometrical and structural information encoded in the MAT, we are able to develop a simple and principled approach to effectively identify the various types of junctions between different parts of a 3D shape. Extensive evaluations and comparisons show that our method outperforms the state-of-the-art methods in terms of segmentation quality and is also one order of magnitude faster.
Voxel cores Yan, Yajie; Letscher, David; Ju, Tao
ACM transactions on graphics,
08/2018, Volume:
37, Issue:
4
Journal Article
Peer reviewed
We present a novel algorithm for computing the medial axes of 3D shapes. We make the observation that the medial axis of a voxel shape can be simply yet faithfully approximated by the interior ...Voronoi diagram of the boundary vertices, which we call the
voxel core.
We further show that voxel cores can approximate the medial axes of any smooth shape with homotopy equivalence and geometric convergence. These insights motivate an algorithm that is simple, efficient, numerically stable, and equipped with theoretical guarantees. Compared with existing voxel-based methods, our method inherits their simplicity but is more scalable and can process significantly larger inputs. Compared with sampling-based methods that offer similar theoretical guarantees, our method produces visually comparable results but more robustly captures the topology of the input shape.
The molecular-scale morphology and topology of polyamide composite membranes determine the performance characteristics of these materials. However, molecular-scale simulations are computationally ...expensive and morphological and topological characterization of molecular structures are not well developed. Molecular dynamics simulation and analysis methods for the polymerization, hydration, and quantification of polyamide membrane structures were developed and compared to elucidate efficient approaches for producing and analyzing the polyamide structure. Polymerization simulations that omitted the reaction-phase solvent did not change the observed hydration, pore-size distribution, or water permeability, while improving the simulation efficiency. Pre-insertion of water into the aggregate pores (radius ≈ 4 Å) of dry domains enabled shorter hydration simulations and improved simulation scaling, without altering pore structure, properties, or performance. Medial axis and Minkowski functional methods were implemented to identify permeation pathways and quantify the polyamide morphology and topology, respectively. Better agreement between simulations and experimentally observed systems was accomplished by increasing the domain size rather than increasing the number of ensemble realizations of smaller systems. The largest domain hydrated was an order of magnitude larger by volume than the largest domain previously reported. This work identifies methods that can enable more efficient and meaningful fundamental modeling of membrane materials.
Display omitted
•Molecular dynamics simulations of polyamide synthesis and hydration were performed.•More computationally efficient, but less realistic synthesis did not affect results.•Water insertion into large polymer pores sped hydration without affecting results.•The morphology and topology of the molecular potential field was analyzed.•Simulation results depended on scale; larger scales approached experimental values.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
9.
Medial IPC Lan, Lei; Yang, Yin; Kaufman, Danny ...
ACM transactions on graphics,
08/2021, Volume:
40, Issue:
4
Journal Article
Peer reviewed
Open access
We propose a framework of efficient nonlinear deformable simulation with both fast continuous collision detection and robust collision resolution. We name this new framework Medial IPC as it ...integrates the merits from medial elastics, for an efficient and versatile reduced simulation, as well as incremental potential contact, for a robust collision and contact resolution. We leverage medial axis transform to construct a kinematic subspace. Instead of resorting to projective dynamics, we use classic hyperelastics to embrace real-world nonlinear materials. A novel reduced continuous collision detection algorithm is presented based on the medial mesh. Thanks to unique geometric properties of medial axis and medial primitives, we derive closed-form formulations for identifying between-primitive collision within the reduced medial space. In the meantime, the implicit barrier energy that generates necessary repulsion forces for collision resolution is also formulated with the medial coordinate. In other words, Medial IPC exploits a universal reduced coordinate for simulation, continuous self-/collision detection, and IPC-based collision resolution. Continuous collision detection also allows more aggressive time stepping. In addition, we carefully implement our system with a heterogeneous CPU-GPU deployment such that massively parallelizable computations are carried out on the GPU while few sequential computations are on the CPU. Such implementation also frees us from generating training poses for selecting Cubature points and pre-computing their weights. We have tested our method on complicated deformable models and collision-rich simulation scenarios. Due to the reduced nature of our system, the computation is faster than fullspace IPC or other fullspace methods using continuous collision detection by at least one order. The simulation remains high-quality as the medial subspace captures intriguing and local deformations with sufficient realism.
Wire-feed additive manufacturing technologies have made it possible to significantly reduce material waste and energy consumption for fabricating large aerospace metal components that feature high ...buy-to-fly ratios. This paper presents an innovative path planning strategy using medial axis transformation for the wire-feed additive manufacturing process. The proposed path planning strategy is able to improve geometrical accuracy and produce void-free deposition by continuously altering the deposition width of the wire-feed process to accommodate the component geometry, while simultaneously minimising the number of interruptions to the deposition process at the component boundary. As a result, both buy-to-fly ratio and energy consumption are improved through reducing material waste. The algorithm for generating the adaptive path is described and validated through application to various typical geometries. Buy-to-fly ratios are calculated for a number of thin-walled complex structures. Savings of more than 27% in material usage are achieved using adaptive path planning, when compared with non-adaptive methods. The proposed method is tested experimentally through deposition of two metal components. The results demonstrate that the adaptive strategy is capable of generating void-free deposition with improved accuracy at the component boundary using the wire-feed additive manufacturing process.
•An innovative path planning strategy is presented.•High quality (void-free) components can be achieved.•Component geometrical accuracy and buy-to-fly ratio are improved.•Material waste and energy consumption are reduced by the proposed deposition path.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
PDF
