Browsing by Author "Janardan, Ravi"

Now showing 1 - 12 of 12
  • 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
    A new optimization criterion for generalized discriminant analysis on undersampled problems
    (2003-06-10) Ye, Jieping; Janardan, Ravi; Park, Cheonghee; Park, Haesun
    We present a new optimization criterion for discriminant analysis. The new criterion extends the optimization criteria of the classical linear discriminant analysis (LDA) by introducing the pseudo-inverse when the scatter matrices are singular. It is applicable regardless of the relative sizes of the data dimension and sample size,overcoming a limitation of the classical LDA. Recently, a new algorithm called LDA/GSVD for structure-preserving dimension reduction has been introduced, which extends the classical LDA to very high-dimensional undersampled problems by using the generalized singular value decomposition (GSVD). The solution from the LDA/GSVD algorithm is a special case of the solution for our generalized criterion in this paper, which is also based on GSVD. We also present an approximate solution for our GSVD-based solution, which reduces computational complexity by finding sub-clusters of each cluster, and using their centroids to capture the structure of each cluster. This reduced problem yields much smaller matrices of which the GSVD can be applied efficiently. Experiments on text data, with up to 7000 dimensions, show that the approximation algorithm produces results that are close to those produced by the exact algorithm.
  • Thumbnail Image
    Item
    Approximate Multiple Protein Structure Alignment Using the Sum-of-Pairs Distance
    (2003-03-31) Ye, Jieping; Janardan, Ravi
    An algorithm is presented to compute a multiple structure alignment for a set of proteins and to generate a consensus (pseudo) protein for the set. The algorithm is a heuristic in that it computes an approximation to the optimal multiple structure alignment that minimizes the sum of thepairwise distances between the protein structures. The algorithm chooses an input protein as the initial consensus and computes a correspondence between the protein structures (which are represented as sets of unitvectors) using an approach analogous to the center-star method for multiple sequence alignment. From this correspondence, a set of rotation matrices (optimal for the given correspondence) is derived to align the structures and derive the new consensus. The process is iterated until the sum of pairwise distances converges. The computation of the optimal rotations is itself an iterative process that both makes use of the current consensus and generates simultaneously a new one. This approach is based on an interesting result that allows the sum of all pairwisedistances to be represented compactly as distances to the consensus. Experimental results on several protein families are presented, showing that the algorithm converges quite rapidly.
  • 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
    Pairwise Protein Structure Alignment Based on an Orientation-Independent Representation of the Backbone Geometry
    (2003-01-14) Ye, Jieping; Janardan, Ravi; Liu, Songtao
    Determining structural similarities between proteins is animportant problem since it can help identify functional and evolutionary relationships. In this paper, an algorithm is proposed to align two protein structures. Given the protein backbones, the algorithm finds a rigid motion of one backbone onto the other such that large substructures are matched. The algorithm uses a representation of the backbone that is independent of their relative orientations in space and applies dynamic programming to this representation to compute an initial alignment, which is then refined iteratively. Experiments indicate that the algorithm is competitive with two well-known algorithms, namely DALI [12] and LOCK [19].
  • 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.
  • Thumbnail Image
    Item
    Real-Time Collision Warning and Avoidance at Intersections
    (Minnesota Department of Transportation, 2004-11-01) Atev, Stefan; Masoud, Osama; Janardan, Ravi; Papanikolopoulos, Nikolaos P.
    Monitoring traffic intersections in real-time as well as predicting possible collisions is an important first step towards building an early collision warning system. We present the general vision methods used in a system addressing this problem and describe the practical adaptations necessary to achieve real-time performance. A novel method for three dimensional vehicle size estimation is presented. We also describe a method for target localization in real-world coordinates, which allows for sequential incorporation of measurements from multiple cameras into a single target's state vector. Additionally, a fast implementation of a false-positive reduction method for the foreground pixel masks is developed. Finally, a low-overhead collision prediction algorithm using the time-as-axis paradigm is presented. The proposed system was able to perform in real-time on videos of quarter-VGA ($320\times240$) resolution. The errors in target position and dimension estimates in a test video sequence are quantified.