33 research outputs found
Multi-criteria geometric optimization problems in Layered Manufacturing (Extended Abstract)
No full text) Jayanth Majhi Ravi Janardan Michiel Smid y Jorg Schwerdt y 1 Introduction Layered Manufacturing (LM) is an exciting new technology which enables complex 3D parts to be built directly from their CAD models, as a stack of 2D layers. It is revolutionizing the field of CAD/CAM because it allows the designer to create rapidly a physical version of the CAD model (literally on the desktop) and to "feel and touch" it, thereby detecting and correcting flaws in the model early on in the design cycle. Moreover, it opens up the possibility of directly building functional parts composed of multiple materials---something that is not possible via conventional manufacturing methods. Figure 1 illustrates a well-known LM process called StereoLithography [11]. The input is a surface triangulation of the CAD model in a format called STL. The STL model is oriented suitably, sliced by horizontal planes, and built vertically, as follows: The laser traces out the contour of each layer on the surfa..
Protecting Facets in Layered Manufacturing
No full textIn Layered Manufacturing, a three-dimensional polyhedral object is built by slicing its (virutal) CAD model, and maufacturing the slices successively. During this process, support structures are used to prop up overhangs. An important issue is choosing the build direction, as it affects, among other things, the location of support structures on the part, which in turn impacts process speed and part finish. Algorithms are given here that (i) compute a description of all build directions for which a prescribed facet is not in contact with supports, and (ii) compute a description of all build directions for which the total area of all facets that are not in contact with supports is minimum. The first algorithm is worst-case optimal. A simplified version of the first algorithm has been implemented, and test results on models obtained from industry are given.Schwerdt, Jörg; Smid, Michiel; Janardan, Ravi; Johnson, Eric; Majhi, Jayanth. (1999). Protecting Facets in Layered Manufacturing. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215374
A Decomposition-Based Approach to Layered Manufacturing
No full textThis paper introduces a new approach for improving the performance and versatility of Layered Manufacturing (LM), which is an emerging technology that makes it possible to build physical prototypes of 3D parts directly from their CAD models using a relatively small and inexpensive "3D printer" attached to a personal computer. LM provides the designer with an additional level of physical verification that makes it possible to detect and correct design flaws that may have, otherwise, gone unnoticed in the virtual model.Current LM processes work by viewing the CAD model as a single, monolithic unit. By contrast, the approach proposed here decomposes the model into a small number of pieces, by intersecting it with a suitably chosen plane, builds each piece separately using LM, and then glues the pieces together to obtain the physical prototype. This approach allows large models to be built quickly in parallel and also lends itself naturally to applications where the model needs to be built as several pieces, such as in the manufacture of mold halves for injection molding. Furthermore, this approach is very efficient in its use of so-called support structures that are generated by the LM process.This paper presents the first provably correct and efficient geometric algorithms to decompose polyhedral models so that the support requirements (support volume and area of contact) are minimized. Algorithms based on the plane-sweep paradigm are first given for convex polyhedra. These algorithms run in O(n log n) time for n -vertex convex polyhedra and work by generating expressions for the support volume and contact-area as a function of the height of the sweep plane, and optimizing them during the sweep. Experimental results are given for randomly-generated convex polyhedra with up to 200,000 vertices. These algorithms are then generalized to non-convex polyhedra, which are considerably more difficult due to the complex structure of the supports. It is shown that, surprisingly, non-convex polyhedra can be handled by first identifying certain critical facets using a technique called cylindrical decomposition, and then applying the algorithm for convex polyhedra to these critical facets. The resulting algorithms run in O(n2log n) time.Ilinkin, Ivaylo; Janardan, Ravi; Majhi, Jayanth; Schwerdt, Jörg; Smid, Michiel; Sriram, Ram. (2000). A Decomposition-Based Approach to Layered Manufacturing. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215427
On some geometric optimization problems in layered manufacturing
No full textAbstractEfficient geometric algorithms are given for optimization problems arising in layered manufacturing, where a 3D object is built by slicing its CAD model into layers and manufacturing the layers successively. The problems considered include minimizing the stair-step error on the surfaces of the manufactured object under various formulations, minimizing the volume of the so-called support structures used, and minimizing the contact area between the supports and the manufactured object—all of which are factors that affect the speed and accuracy of the process. The stair-step minimization algorithm is valid for any polyhedron, while the support minimization algorithms are applicable only to convex polyhedra. The techniques used to obtain these results include construction and searching of certain arrangements on the sphere, 3D convex hulls, halfplane range searching, and constrained optimization
Computing a flattest, undercut-free parting line for a convex polyhedron, with application to mold design
No full textAbstractA parting line for a polyhedron is a closed curve on its surface, which identifies the two halves of the polyhedron for which mold-boxes must be made. A parting line is undercut-free if the two halves that it generates do not contain facets that obstruct the de-molding of the polyhedron. Computing an undercut-free parting line that is as “flat” as possible is an important problem in mold design. In this paper, algorithms are presented to compute such a parting line for a convex polyhedron, based on different flatness criteria
Multi-criteria geometric optimization problems in Layered Manufacturing
No full textIn Layered Manufacturing, the choice of the build direction for the model influences several design criteria, including the number of layers, the volume and contact-area of the support structures, and the surface finish. These, in turn, impact the throughput and cost of the process. In this paper, efficient geometric algorithms are given to reconcile two or more of these criteria simultaneously, under three formulations of multi-criteria optimization: Finding a build direction which (i) optimizes the criteria sequentially, (ii) optimizes their weighted sum, or (iii) allows the criteria to meet designer-prescribed thresholds. While the algorithms involving "support volume" or "contact area" apply only to convex models, the solutions for "surface finish" and "number of layers" are applicable to any polyhedral model. Some of the latter algorithms have also been implemented and tested on real-world models obtained from industry. The geometric techniques used include construction and search..
Computing the Width of a Three-Dimensional Point Set: An Experimental Study
No full textWe describe a robust, exact, and efficient implementation of an algorithm that computes the width of a three-dimensional point set. The algorithm is based on efficient solutions to problems that are at the heart of computational geometry: three-dimensional convex hulls, point location in planar graphs, and computing intersections between line segments. The latter two problems have to be solved for planar graphs and segments on the unit sphere, rather than in the twodimensional plane. The implementation is based on LEDA, and the geometric objects are represented using exact rational arithmetic. 1. Introduction StereoLithography is a relatively new technology which is gaining importance in the manufacturing industry. (See e.g. the book by Jacobs [7].) The input to the StereoLithography process is a surface triangulation of a CAD model. The triangulated model is sliced by horizontal planes into layers, and then built layer by layer in the positive z-direction, as follows. The StereoLitho..
Conformal blocks on a 2-sphere with indistinguishable punctures and implications on black hole entropy
No full textAbstractThe dimensionality of the Hilbert space of a Chern–Simons theory on a 3-fold, in the presence of Wilson lines carrying spin representations, had been counted by using its link with the Wess–Zumino theory, with level k, on the 2-sphere with points (to be called punctures) marked by the piercing of the corresponding Wilson lines and carrying the respective spin representations. It is shown, in the weak coupling (large k) limit, the formula decouples into two characteristically distinct parts; one mimics the dimensionality of the Hilbert space of a collection of non-interacting spin systems and the other is an effective overall correction contributed by all the punctures. The exact formula yield from this counting has been shown earlier to have resulted from the consideration of the punctures to be distinguishable. We investigate the same counting problem by considering the punctures to be indistinguishable. Although the full formula remains undiscovered, nonetheless, we are able to impose the relevant statistics for indistinguishable punctures in the approximate formula resulting from the weak coupling limit. As an implication of this counting, in the context of its relation to that of black hole entropy calculation in quantum geometric approach, we are able to show that the logarithmic area correction, with a coefficient of −3/2, that results in this method of entropy calculation, in independent of whether the punctures are distinguishable or not
Computing a Flattest, Undercut-Free Parting Line for a Convex Polyhedron, With Application to Mold Design
No full textA parting line for a polyhedron is a closed curve on its surface, which identifies the two halves of the polyhedron for which mold-boxes must be made. A parting line is undercut-free if the two halves that it generates do not contain facets that obstruct the de-molding of the polyhedron. Computing an undercut-free parting line that is as "flat" as possible is an important problem in mold design. In this paper, algorithms are presented to compute such a parting line for a convex polyhedron, based on different flatness criteria. Keywords: Casting/molding, computational geometry, optimization. Additional keywords: Arrangements, shortest paths, visibility, point-set width. 1 Introduction We consider a geometric problem arising in the design of molds for casting and injection molding. Consider the construction of a sand mold for casting a polyhedral solid. First a prototype, P, of the polyhedron is made. Two halves of P are then identified and a separate mold-box is made for each. This i..
