In metal 3D printing, and in particular in the production of dental implants and prosthodontics, a careful geometric analysis of the parts is key to maximize the overall throughput and minimize fabrication costs. Herewith we describe the main results obtained within the European Project DIGITBrain/ProMED, whose objective is to optimize the production of customized metal medical devices. ProMED delivers a digital twin of an existing production pipeline and allows for the quick simulation of a large number of fabrication scenarios. This is achieved thanks to a clever geometric analysis driving the optimal orientation of the part in the platform combined with a geometry-based process simulator that makes it possible to estimate fabrication time, material consumption, human labour, and other useful information that greatly supports users in the task of optimizing the overall fabrication performances from many meaningful points of view. Compared to standard simulation software provided by printer vendors, our approach can be orders of magnitude faster: this makes it possible to analyze and compare a great number of scenarios to support companies in their day-by-day decisions for real productions.

Boolean operations are among the most used paradigms to create and edit digital shapes. Despite being conceptually simple, the computation of mesh Booleans is notoriously challenging. Main issues come from numerical approximations that make the detection and processing of intersection points inconsistent and unreliable, exposing implementations based on floating point arithmetic to many kinds of degeneracy and failure. Numerical methods based on rational numbers or exact geometric predicates have the needed robustness guarantees, that are achieved at the cost of increased computation times that, as of today, has always restricted the use of robust mesh Booleans to offline applications.We introduce the first algorithm for Boolean operations with robustness guarantees that is capable of operating at interactive frame rates on meshes with up to 200K triangles. We evaluate our tool thoroughly, considering not only interactive applications but also batch processing of large collections of meshes, processing of huge meshes containing millions of elements and variadic Booleans of hundreds of shapes altogether. In all these experiments, we consistently outperform prior art by at least one order of magnitude.

We introduce the first exact root parity counter for continuous collision detection (CCD). That is, our algorithm computes the parity (even or odd) of the number of roots of the cubic polynomial arising from a CCD query. We note that the parity is unable to differentiate between zero (no collisions) and the rare case of two roots (collisions). Our method does not have numerical parameters to tune, has a performance comparable to efficient approximate algorithms, and is exact. We test our approach on a large collection of synthetic tests and real simulations, and we demonstrate that it can be easily integrated into existing simulators.

We introduce a new technique to create a mesh of convex polyhedra representing the interior volume of a triangulated input surface. Our approach is particularly tolerant to defects in the input, which is allowed to self-intersect, to be non-manifold, disconnected, and to contain surface holes and gaps. We guarantee that the input surface is exactly represented as the union of polygonal facets of the output volume mesh. Thanks to our algorithm, traditionally difficult solid modeling operations such as mesh booleans and Minkowski sums become surprisingly robust and easy to implement, even if the input has defects. Our technique leverages on the recent concept of indirect geometric predicate to provide an unprecedented combination of guaranteed robustness and speed, thus enabling the practical implementation of robust though flexible solid modeling systems. We have extensively tested our method on all the 10000 models of the Thingi10k dataset, and concluded that no existing method provides comparable robustness, precision and performances.

Triangulation algorithms that conform to a set of non-intersecting input segments typically proceed in an incremental fashion, by inserting points first, and then segments. Inserting a segment amounts to: (1) deleting all the triangles it intersects; (2) filling the so generated hole with two polygons that have the wanted segment as shared edge; (3) triangulate each polygon separately. In this paper we prove that these polygons are such that all their convex vertices but two can be used to form triangles in an earcut fashion, without the need to check whether other polygon points are located within each ear. The fact that any simple polygon contains at least three convex vertices guarantees the existence of a valid ear to cut, ensuring convergence. Not only this translates to an optimal deterministic linear time triangulation algorithm, but such algorithm is also trivial to implement. We formally prove the correctness of our approach, also validating it in practical applications and comparing it with prior art.

We introduce a large-scale benchmark for continuous collision detection (CCD) algorithms, composed of queries manually constructed to highlight challenging degenerate cases and automatically generated using existing simulators to cover common cases. We use the benchmark to evaluate the accuracy, correctness, and efficiency of state-of-the-art continuous collision detection algorithms, both with and without minimal separation. We discover that, despite the widespread use of CCD algorithms, existing algorithms are (1) correct but impractically slow; (2) efficient but incorrect, introducing false negatives that will lead to interpenetration; or (3) correct but over conservative, reporting a large number of false positives that might lead to inaccuracies when integrated in a simulator. By combining the seminal interval root finding algorithm introduced by Snyder in 1992 with modern predicate design techniques, we propose a simple and efficient CCD algorithm. This algorithm is competitive with state-of-the-art methods in terms of runtime while conservatively reporting the time of impact and allowing explicit tradeoff between runtime efficiency and number of false positives reported.

Polytopal Element Methods (PEM) allow us solving differential equations on general polygonal and polyhedral grids, potentially offering great flexibility to mesh generation algorithms. Differently from classical finite element methods, where the relation between the geometric properties of the mesh and the performances of the solver are well known, the characterization of a good polytopal element is still subject to ongoing research. Current shape regularity criteria are quite restrictive, and greatly limit the set of valid meshes. Nevertheless, numerical experiments revealed that PEM solvers can perform well on meshes that are far outside the strict boundaries imposed by the current theory, suggesting that the real capabilities of these methods are much higher. In this work, we propose a benchmark to study the correlation between general 2D polygonal meshes and PEM solvers which we test on a virtual element solver for the Poisson equation. The benchmark aims to explore the space of 2D polygonal meshes and polygonal quality metrics, in order to understand if and how shape regularity, defined according to different criteria, affects the performance of the method. The proposed tool is quite general, and can be potentially used to study any PEM solver. Besides discussing the basics of the benchmark, we demonstrate its application on a representative member of the PEM family, namely the Virtual Element Method, also discussing our findings.

We introduce a novel algorithm to transform any generic set of triangles in 3D space into a well-formed simplicial complex. Intersecting elements in the input are correctly identified, subdivided, and connected to arrange a valid configuration, leading to a topologically sound partition of the space into piece-wise linear cells. Our approach does not require the exact coordinates of intersection points to calculate the resulting complex. We represent any intersection point as an unevaluated combination of input vertices. We then extend the recently introduced concept of indirect predicates [Attene 2020] to define all the necessary geometric tests that, by construction, are both exact and efficient since they fully exploit the floating-point hardware. This design makes our method robust and guaranteed correct, while being virtually as fast as non-robust floating-point based implementations. Compared with existing robust methods, our algorithm offers a number of advantages: it is much faster, has a better memory layout, scales well on extremely challenging models, and allows fully exploiting modern multi-core hardware with a parallel implementation. We thoroughly tested our method on thousands of meshes, concluding that it consistently outperforms prior art. We also demonstrate its usefulness in various applications, such as computing efficient mesh booleans, Minkowski sums, and volume meshes.

We introduce a new technique to check containment of a triangle within an envelope built around a given triangle mesh. While existing methods conservatively check containment within a Euclidean envelope, our approach makes use of a non-Euclidean envelope where containment can be checked both exactly and efficiently. Exactness is crucial to address major robustness issues in existing geometry processing algorithms, which we demonstrate by integrating our technique in two surface triangle remeshing algorithms and a volumetric tetrahedral meshing algorithm. We provide a quantitative comparison of our method and alternative algorithms, showing that our solution, in addition to being exact, is also more efficient. Indeed, while containment within large envelopes can be checked in a comparable time, we show that our algorithm outperforms alternative methods when the envelope becomes thin.

Geometric predicates are a basic ingredient to implement a vast range of algorithms in computational geometry. Modern implementations employ floating point filtering techniques to combine efficiency and robustness, and state-of-the-art predicates are guaranteed to be always exact while being only slightly slower than corresponding (inexact) floating point implementations. Unfortunately, if the input to these predicates is an intermediate construction of an algorithm, its floating point representation may be affected by an approximation error, and correctness is no longer guaranteed. This paper introduces the concept of indirect geometric predicate: instead of taking the intermediate construction as an explicit input, an indirect predicate considers the primitive geometric elements which are combined to produce such a construction. This makes it possible to keep track of the floating point approximation, and thus to exploit efficient filters and expansion arithmetic to exactly resolve the predicate with minimal overhead with respect to a naive floating point implementation. As a representative example, we show how to extend standard predicates to the case of points of intersection of linear elements (i.e. lines and planes) and show that, on classical problems, this approach outperforms state-of-the-art solutions based on lazy exact intermediate representations.

In industrial practice, additive manufacturing (AM) processes are often followed by post-processing operations such as heat treatment, subtractive machining, milling, etc., to achieve the desired surface quality and dimensional accuracy. Hence, a given part must be 3D-printed with extra material to enable this finishing phase. This combined additive/subtractive technique can be optimized to reduce manufacturing costs by saving printing time and reducing material and energy usage. In this work, a numerical methodology based on parametric shape optimization is proposed for optimizing the thickness of the extra material, allowing for minimal machining operations while ensuring the finishing requirements. Moreover, the proposed approach is complemented by a novel algorithm for generating inner structures to reduce the part distortion and its weight. The computational effort induced by classical constrained optimization methods is alleviated by replacing both the objective and constraint functions by their sparse grid surrogates. Numerical results showcase the effectiveness of the proposed approach.

Users frequently seek to fabricate objects whose outer surfaces consist ofregions with different surface attributes, such as color or material. Manufac-turing such objects in a single piece is often challenging or even impossible.The alternative is to partition them into single-attribute volumetric partsthat can be fabricated separately and then assembled to form the targetobject. Facilitating this approach requires partitioning the input model intoparts thatconformto the surface segmentation and that can be moved apartwith no collisions. We proposeSurface2Volume, a partition algorithm capableof producing suchassemblableparts, each of which is affiliated with a singleattribute, the outer surface of whose assembly conforms to the input surfacegeometry and segmentation. In computing the partition we strictly enforceconformity with surface segmentation and assemblability, and optimize forease of fabrication by minimizing part count, promoting part simplicity,and simplifying assembly sequencing. We note that computing the desiredpartition requires solving for three types of variables: per-part assemblytrajectories, partition topology, i.e. the connectivity of the interface surfacesseparating the different parts, and the geometry, or location, of these inter-faces. We efficiently produce the desired partitions by addressing one type of ariables at a time: first computing the assembly trajectories, then determin-ing interface topology, and finally computing interface locations that allowparts assemblability. We algorithmically identify inputs that necessitatesequential assembly, and partition these inputs gradually by computing anddisassembling a subset of assemblable parts at a time. We demonstrate ourmethod's robustness and versatility by employing it to partition a rangeof models with complex surface segmentations into assemblable parts. Wefurther validate our framework via output fabrication and comparisons toalternative partition techniques.

Accurately simulating additive manufacturing (AM) processes is useful to predict printing failures and test 3D printing without wasting precious resources, both in terms of time and material. In AM the object to be fabricated is first cut into a set of slices aligned with the build direction, and then printed, depositing or solidifying material one layer on top of the other. To guarantee accurate simulations, it is therefore necessary to encode the temporal evolution of the shape to be printed within the simulation domain. We introduce slice2mesh, to the best of our knowledge the first software capable of turning a sliced object directly into a volumetric mesh. Our tool inputs a set of slices and produces a tetrahedral mesh that endows each slice in its connectivity. An accurate representation of the simulation domain at any time during the print can therefore be easily obtained by filtering out the slices yet to be processed. slice2mesh also features a flexible mesh generation system for external supports, and allows the user to trade accuracy for simplicity by producing approximate simulation domains obtained by filtering the object in slice space.

Accurately simulating Additive Manufacturing (AM) processes is useful to predict printing failures and test 3D printing without wasting precious resources, both in terms of time ad material. In AM the object to be fabricated is first cut into a set of slices aligned with the build direction, and then printed, depositing or solidifying material one layer on top of the other. To guarantee accurate simulations, it is therefore necessary to encode the temporal evolution of the shape to be printed within the simulation domain. We introduce slice2mesh, to the best of our knowledge the first software capable of turning a sliced object directly into a volumetric mesh. Our tool inputs a set of slices and produces a tetrahedral mesh that endows each slice in its connectivity. An accurate representation of the simulation domain at any time during the print can therefore be easily obtained by filtering out the slices yet to be processed. slice2mesh also features a flexible mesh generation system for external supports, and allows the user to trade accuracy for simplicity by producing approximate simulation domains obtained by filtering the object in slice space.

The wide diffusion of 3D printing technologies continuously calls for effective solutions for designing and fabricating objects of increasing complexity. The so called "computational fabrication" pipeline comprises all the steps necessary to turn a design idea into a physical object, and this book describes the most recent advancements in the two fundamental phases along this pipeline: design and process planning. We examine recent systems in the computer graphics community that allow us to take a design idea from conception to a digital model, and classify algorithms that are necessary to turn such a digital model into an appropriate sequence of machining instructions.

Purpose: The class of models that can be represented by STL files is larger than the class of models that can be printed using additive manufacturing technologies. Stated differently, there exist well-formed STL files that cannot be printed. This paper aims to formalize such a gap and describe a fully automatic procedure to turn any such file into a printable model. Design/methodology/approach: Based on well-established concepts from combinatorial topology, this paper provide an unambiguous description of all the mathematical entities involved in the modeling-printing pipeline. Specifically, this paper formally defines the conditions that an STL file must satisfy to be printable, and, based on these, an as-exact-as-possible repairing algorithm is designed. Findings: It has been found that, to cope with all the possible triangle configurations, the algorithm must distinguish between triangles that bind solid parts and triangles that constitute zero-thickness sheets. Only the former set can be fixed without distortion. Research limitations/implications: Owing to the specific approach used that tracks the so-called "outer hull," models with inner cavities cannot be treated. Practical implications: Thanks to this new method, the shift from a 3D model to a printed prototype is faster, easier and more reliable. Social implications: The availability of this easily accessible model preparation tool has the potential to foster a wider diffusion of home-made 3D printing in non-professional communities. Originality/value: Previous methods that are guaranteed to fix all the possible configurations provide only approximate solutions with an unnecessary distortion. Conversely, this procedure is as exact as possible, meaning that no visible distortion is introduced unless it is strictly imposed by limitations of the printing device. Thanks to such unprecedented flexibility and accuracy, this algorithm is expected to significantly simplify the modeling-printing process, in particular within the continuously emerging non-professional "maker" communities.

A computational scheme to predict melting phase relations in multi-component systems at high pressure and temperature is presented and applied to the MgO-Al2O3-SiO2 (MAS) compositional system. A combined approach based on first principles calculations (hybrid DFT and Polarized Continuum Model), polymer chemistry (Hybrid Polymeric Approach, HPA) and equilibrium thermodynamics is developed to compute thermophysical and thermodynamic properties of the solid and liquid phases in the investigated system and infer the liquidus topology of binary and ternary phase diagrams in a broad range of P-T conditions (i.e. up to 25 GPa and 5000 K). The nature of ternary interactions in the liquid is discussed in terms of an excess Gibbs free energy contribution arising from the effect of polarization of charged species in the continuum. The computed phase diagrams show that pressure effects are able to change the nature of melting from congruent to incongruent and drastically reduce the number of solid phases with a primary phase field in the MAS system, thus leading to a remarkable simplication of melting phase relations at HP-HT. At pressures > 2 GPa a primary phase field of pyrope garnet opens and progressively widens from 2 to 8 GPa at the expense of those of enstatite, forsterite and spinel. Anhydrous phase B (AnhB) completely replaces forsterite on the liquidus at 9 GPa, persisting as stable liquidus phase at least up to 16-17 GPa and 2700-2750 K. At P-T conditions compatible with the mantle transition zone, the MAS phase diagram markedly simplifies, with the three pure oxides (i.e. MgO, periclase; Al2O3, corundum; SiO2, stishovite) displaying a primary phase field and majorite-pyrope garnet as the only, and most important, ternary liquidus phase in the system.

N/A

We focus on the analysis of planar shapes and solid objects having thin features and propose a new mathematical model to characterize them. Based on our model, that we call an is an element of-shape, we show how thin parts can be effectively and efficiently detected by an algorithm, and propose a novel approach to thicken these features while leaving all the other parts of the shape unchanged. When compared with state-of-the-art solutions, our proposal proves to be particularly flexible, efficient and stable, and does not require any unintuitive parameter to fine-tune the process. Furthermore, our method is able to detect thin features both in the object and in its complement, thus providing a useful tool to detect thin cavities and narrow channels. We discuss the importance of this kind of analysis in the design of robust structures and in the creation of geometry to be fabricated with modern additive manufacturing technology. (C) 2017 Elsevier Ltd. All rights reserved.

A solid cylindrical parameterization is a volumetric map between a tubular shape and a right cylinder embedded in the polar coordinate reference system. This paper introduces a novel approach to derive smooth (i.e., harmonic) cylindrical parameterizations for solids with arbitrary topology. Differently from previous approaches our mappings are both fully explicit and bi-directional, meaning that the three polar coordinates are encoded for both internal and boundary points, and that for any point within the solid we can efficiently move from the object space to the parameter space and vice-versa. To represent the discrete mapping, we calculate a tetrahedral mesh that conforms with the solid's boundary and accounts for the periodic and singular structure of the parametric domain. To deal with arbitrary topologies, we introduce a novel approach to exhaustively partition the solid into a set of tubular parts based on a curve-skeleton. Such a skeleton can be either computed by an algorithm or provided by the user. Being fully explicit, our mappings can be readily exploited by off-the-shelf algorithms (e.g., for iso-contouring). Furthermore, when the input shape is made of tubular parts, our method produces low-distortion parameterizations whose iso-surfaces fairly follow the geometry in a natural way. We show how to exploit this characteristic to produce high-quality hexahedral and shell meshes.