0000000000114770
AUTHOR
Nicola Wolpert
showing 13 related works from this author
Voxel-based General Voronoi Diagram for Complex Data with Application on Motion Planning
2020
One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find appropriate disassembly paths for all assembled parts. Such a path places demands on its length and clearance. In the past, it became apparent that planning the disassembly path based on the (approximate) General Voronoi Diagram (GVD) is a good approach to achieve these requirements. But for complex real-world data, every known solution for computing the GVD is either too slow or very memory consuming, even if only approximating the GVD.We present a new approach for computing the approximate GVD and demonstrate its practicability using a representative vehicle data set. We can calculate a…
Completely randomized RRT-connect: A case study on 3D rigid body motion planning
2015
Nowadays sampling-based motion planners use the power of randomization to compute multidimensional motions at high performance. Nevertheless the performance is based on problem-dependent parameters like the weighting of translation versus rotation and the planning range of the algorithm. Former work uses constant user-adjusted values for these parameters which are defined a priori. Our new approach extends the power of randomization by varying the parameters randomly during runtime. This avoids a preprocessing step to adjust parameters and moreover improves the performance in comparison to existing methods in the majority of the benchmarks. Our method is simple to understand and implement. …
An exact and efficient approach for computing a cell in an arrangement of quadrics
2006
AbstractWe present an approach for the exact and efficient computation of a cell in an arrangement of quadric surfaces. All calculations are based on exact rational algebraic methods and provide the correct mathematical results in all, even degenerate, cases. By projection, the spatial problem is reduced to the one of computing planar arrangements of algebraic curves. We succeed in locating all event points in these arrangements, including tangential intersections and singular points. By introducing an additional curve, which we call the Jacobi curve, we are able to find non-singular tangential intersections. We show that the coordinates of the singular points in our special projected plana…
Saliency Features for 3D CAD-Data in the Context of Sampling-Based Motion Planning
2021
In this paper, we consider disassembly scenarios for real-world 3D CAD-data, where each component is defined by a triangle mesh. For a fast construction of collision-free disassembly paths, common approaches use sampling-based rigid body motion planning which is well studied in the literature. One fact that has so far received little attention is that in industrial disassembly scenarios components are often attached to each other with flexible fastening elements like clips. In the planning process, the fastening elements show the following characteristics: 1) They can cause complex non-linear disassembly paths. 2) They are often deformable. 3) They are usually modeled in a relaxed state and…
Collision detection for 3D rigid body motion planning with narrow passages
2017
In sampling-based 3D rigid body motion planning one of the major subroutines is collision detection. Especially for problems with narrow passages many samples have to be checked by a collision detection algorithm. In this application, the runtime of the motion planning algorithm is dominated by collision detection and the samples have the very specific characteristic that many of them are in collision and have small penetration volumes. In our work, we introduce a data structure and an algorithm that makes use of this characteristic by combining well-known data structures like a distance field and an octree with the swap algorithm by Llanas et al. For 3D rigid body motion planning with narr…
Expansive Voronoi Tree: A Motion Planner for Assembly Sequence Planning
2021
One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find an appropriate disassembly path for each assembled part. Complex real-world scenes are characterized by a large installation space. There each part has many different possible disassembly paths that differ in length and clearance. However, due to tight packing in the installation space, these paths can contain narrow passages. Therefore a motion planner is needed that is able to globally search for a reasonable path and to locally overcome narrow passages. Moreover, since motion planning requests are executed in the ASP context over and over again for many parts, both for those that can b…
Parallel Collision Queries on the GPU
2013
We present parallel algorithms to accelerate collision tests of rigid body objects for a high number of independent transformations as they occur in sampling-based motion planning and path validation problems. We compare various GPU approaches with a different level of parallelism against each other and against a parallel CPU implementation. Our algorithms require no sophisticated load balancing schemes. They make no assumption on the distribution of the input transformations and require no pre-processing. Yet, we can perform up to 1 million collision tests per second with our best GPU implementation in our benchmarks. This is about 2.5X faster than our reference multi-core CPU implementati…
Exacus: Efficient and Exact Algorithms for Curves and Surfaces
2005
We present the first release of the Exacus C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness, clarity of the design, modularity, flexibility, and ease of use. We present the generic design and structure of the libraries, which currently compute arrangements of curves and curve segments of low algebraic degree, and boolean operations on polygons bounded by such segments.
Complete, exact, and efficient computations with cubic curves
2004
The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quart…
An exact, complete and efficient implementation for computing planar maps of quadric intersection curves
2005
We present the first exact, complete and efficient implementation that computes for a given set P=p1,...,pn of quadric surfaces the planar map induced by all intersection curves p1∩ pi, 2 ≤ i ≤ n, running on the surface of p1. The vertices in this graph are the singular and x-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in [20] and [9].Our implementation is complete in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pa…
A motion planning algorithm for the invalid initial state disassembly problem
2015
Sampling-based motion planners are able to plan disassembly paths at high performance. They are limited by the fact that the input triangle sets of the static and dynamic object need to be free of collision in the initial and all following states. In real world applications, like the disassembly planning in car industry, this often does not hold true. Beside data inaccuracy, this is mainly caused by the modeling of flexible parts as rigid bodies, especially fixture elements like clips. They cause the invalid initial state disassembly problem. In the literature there exists no algorithm that is able to calculate a reasonable disassembly path for an invalid initial state. Our novel algorithm …
Exact, efficient, and complete arrangement computation for cubic curves
2006
AbstractThe Bentley–Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and Bézier curves.The algorithm is complete in that it handles all possible degeneracies such as tangential intersections and singularities. It is exact in t…
Local-Area-Learning Network: Meaningful Local Areas for Efficient Point Cloud Analysis
2020
Research in point cloud analysis with deep neural networks has made rapid progress in recent years. The pioneering work PointNet offered a direct analysis of point clouds. However, due to its architecture PointNet is not able to capture local structures. To overcome this drawback, the same authors have developed PointNet++ by applying PointNet to local areas. The local areas are defined by center points and their neighbors. In PointNet++ and its further developments the center points are determined with a Farthest Point Sampling (FPS) algorithm. This has the disadvantage that the center points in general do not have meaningful local areas. In this paper, we introduce the neural Local-Area-L…