Browsing by Author "Smid, Michiel"

Now showing 1 - 8 of 8
  • Thumbnail Image
    Item
    A Decomposition-Based Approach to Layered Manufacturing
    (2000-10-10) Ilinkin, Ivaylo; Janardan, Ravi; Majhi, Jayanth; Schwerdt, Jörg; Smid, Michiel; Sriram, Ram
    This 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.
  • Thumbnail Image
    Item
    Approximating Contact-Area of Supports in Layered Manufacturing
    (2004-01-05) Ilinkin, Ivaylo; Janardan, Ravi; Smid, Michiel; Johnson, Eric; Castillo, Paul; Schwerdt, Jörg
    Layered Manufacturing is a technology that allows physicalprototypes of three-dimensional models to be built directlyfrom their digital representation, as a stack of two-dimensional layers. A key design problem here is the choice of a suitable direction in which the digital model should be oriented and built so as to minimize the area of contact between the prototype and temporary support structures that are generated during the build. Devising an efficient algorithm for computing such a direction has remained a difficult problem for quite some time. In this paper, a suite of efficient and practical heuristics is presented for approximating the minimum contact-area. Also given is a technique for evaluating the quality of the approximation of any heuristic, which doesnot require knowledge of the (unknown and hard-to-compute) optimal solution; instead, it provides an indirect upper bound on the quality of the approximation via two relatively easy-to-compute quantities. The algorithms are based on various techniques from computational geometry, such as ray-shooting, convex hulls, boolean operations on polygons, and spherical arrangements, and have been implemented and tested. Experimental results on a wide range of real-world models show that the heuristics perform quite well in practice.
  • Thumbnail Image
    Item
    Computing an optimal hatching direction in Layered Manufacturing
    (2001-02-01) Schwerdt, Jörg; Smid, Michiel; HonChung, Man; Janardan, Ravi
    In Layered manufacturing (LM), a prototype of a virtual polyhedral object is built by slicing the object into polygonal layers, and then building the layers one after another. In StereoLithography, a specific LM-technology, a layer is built using a laser which follows paths along equally-spaced parallel lines and hatches all segments on these lines that are contained in the layer. We consider the problem of computing a direction of these lines for which the number of segments to be hatched is minimum, and present an algorithm that solves this problem exactly. The algorithm has been implemented and experimental results are reported for real-world polyhedral models obtained from industry.
  • Thumbnail Image
    Item
    Computing the Width of a Three-Dimensional Point Set: An Experimental Study
    (1999-02-09) Schwerdt, Jörg; Smid, Michiel; Majhi, Jayanth; Janardan, Ravi
    We 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 two-dimensional plane. The implementation is based on LEDA, and the geometric objects are represented using exact rational arithmetic.
  • Thumbnail Image
    Item
    Minimizing support structures and trapped area in two-dimensional layered manufacturing
    (1997) Majhi, Jayanth; Janardan, Ravi; Smid, Michiel; Schwerdt, Jorg; Gupta, Prosenjit
    Efficient geometric algorithms are given for the two-dimensional versions of optimization problems arising in layered manufacturing, where a polygonal object is built by slicing its CAD model and manufacturing the slices successively. The problems considered are minimizing (i) the contact-length between the supports and the manufactured object, (ii) the area of the support structures used, and (iii) the area of the so-called trapped regions- factors that affect the cost and quality of the process.
  • Thumbnail Image
    Item
    Minimizing the total projection of a set of vectors, with applications to Layered Manufacturing
    (2001-02-01) HonChung, Man; Janardan, Ravi; Schwerdt, Jörg; Smid, Michiel
    In Layered manufacturing, a three-dimensional polyhedral solid is built as a stack of two-dimensional slices. Each slice (a polygon) is built by filling its interior with a sequence of parallel line segments (of some small non-zero width), in a process called hatching. A critical step in hatching is choosing a direction which minimizes the number of segments. In this paper, this problem is approximated as the problem of finding a direction which minimizes the total projected length of a certain set of vectors. Efficient algorithms are proposed for the latter problem, using techniques from computational geometry. Experimental and theoretical analyses show that this approach yields results that approximate closely the optimal solution to the hatching problem of finding a direction which minimizes the total projected length of a certain set of vectors. Efficient algorithms are proposed for the latter problem, using techniques from computational geometry. Experimental and theoretical analyses show that this approach yields results that approximate closely the optimal solution to the hatching problem. Extensions of these results to several related problems are also discussed.
  • Thumbnail Image
    Item
    Multi-criteria geometric optimization problems in Layered Manufacturing
    (1997) Majhi, Jayanth; Janardan, Ravi; Smid, Michiel; Schwerdt, Jorg
    In 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 searching of certain arrangements on the unit-sphere, 3-dimensional convex hulls, Voronoi diagrams, point location, and hierarchical representations. Additionally, solutions are also provided, for the first time, for the constrained versions of two fundamental geometric problems, namely polyhedron width and largest empty disk on the unit-sphere.
  • Thumbnail Image
    Item
    Protecting Facets in Layered Manufacturing
    (1999-04-21) Schwerdt, Jörg; Smid, Michiel; Janardan, Ravi; Johnson, Eric; Majhi, Jayanth
    In 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.