Browsing by Author "Majhi, Jayanth"

Now showing 1 - 5 of 5
  • 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
    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
    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.