The automatic generation of (dis)assembly sequences for complex technical products is a challenging field. Complex products like vehicles consist of numerous different components. Determining the sequence using a brute-force-approach by testing all components for disassembly one after another in a loop until all components are disassembled is laborious and costly. In industrial scenarios, a large proportion of the components are fasteners. In this paper, we propose a new framework which improves the disassembly sequencing generation by prioritizing fasteners during planning. Our proposed framework comprises a preprocessing in which fasteners are identified with a convolutional neural network within a dataset and a procedure that preferentially and automatically checks fasteners for disassembly. The algorithm takes initial and unavoidable collisions of the fasteners into account. We show the effectiveness of our approach on real-world data from the automotive industry. A new synthetic dataset of fasteners for training neural networks is available.

We present the first realization of an assembly sequence planning framework for large-scale and complex 3D real-world CAD scenarios. Other than in academic benchmark data sets, in our scenario each assembled part is allowed to contain flexible fastening elements and the number of assembled parts is quite high. With our framework we are able to derive a meaningful assembly priority graph for the parts. Our framework divides the disassembly motion of each part into a NEAR- and a subsequent FAR planning phase and uses existing specialized motion planners for each phase. To reduce the number of unsuccessful motion planning requests we use a general Voronoi diagram graph and a novel collision perceiving method which significantly speed up our framework. At the end, we create an assembly priority graph to indicate which parts must be disassembled before others. In our experiments, we show that our framework is the first one which is able to generate a priority graph for a representative data set from the automotive industry. Moreover, the reported disassembly motions for the individual parts are shorter and can be computed faster than with other state-of-the-art frameworks.

Automatic disassembly planning for complex industrial products like vehicles checks the expandability of components already at early stages of design. For a fast computation of collision-free disassembly paths, sampling-based rigid body motion planning is used in the literature. However, in real-world scenarios there are circumstances that prevent the finding of plausible collision-free disassembly paths with these conventional motion planners. The most difficult problem is that many components have deformable fastening elements that are modeled in a relaxed state and often as a part of the rigid object. The fastening elements cause unavoidable collisions of the component with its environment along the actual disassembly path. In this paper, we present Iterative Mesh Modification Planning (IMMP). Given the information about fastening elements in advance, our method applies a controlled iterative process of geometric deformations and planning attempts to the component to be disassembled. With this process, we are able to disassemble the component from its installed position with a conventional rigid body motion planner taking fastening elements and also overpressure into account. We demonstrate the effectiveness of our method on real-world planning scenarios from the automotive industry.

Infrared thermography is increasingly applied in sports science due to promising observations regarding changes in skin’s surface radiation temperature ($T_{sr}$) before, during, and after exercise. The common manual thermogram analysis limits an objective and reproducible measurement of$T_{sr}$. Previous analysis approaches depend on expert knowledge and have not been applied during movement. We aimed to develop a deep neural network (DNN) capable of automatically and objectively segmenting body parts, recognizing blood vessel-associated$T_{sr}$distributions, and continuously measuring$T_{sr}$during exercise. We conducted 38 cardiopulmonary exercise tests on a treadmill. We developed two DNNs: body part network and vessel network, to perform semantic segmentation of 1 107 855 thermal images. Both DNNs were trained with 263 training and 75 validation images. Additionally, we compare the results of a common manual thermogram analysis with these of the DNNs. Performance analysis identified a mean IoU of 0.8 for body part network and 0.6 for vessel network. There is a high agreement between manual and automatic analysis (r = 0.999; p$< $0.001; T-test: p = 0.116), with a mean difference of 0.01$^\circ$C (0.08). Non-parametric Bland Altman’s analysis showed that the 95% agreement ranges between - 0.086$^\circ$C and 0.228$^\circ$C. The developed DNNs enable automatic, objective, and continuous measurement of$T_{sr}$and recognition of blood vessel-associated$T_{sr}$distributions in resting and moving legs. Hence, the DNNs surpass previous algorithms by eliminating manual region of interest selection and form the currently needed foundation to extensively investigate$T_{sr}$distributions related to non-invasive diagnostics of (patho-)physiological traits in means of exercise radiomics.

Developing neural networks for supervised multi-class classification has become important for theory and practice. An essential point is the design of the underlying network. Beside single-network approaches there are several multi-class patterns which decompose a classification problem into multiple sub-problems and derive systems of neural networks. We show that existing multi-class patterns can be improved by a new and simple labeling scheme for the training of the sub-problems. We efficiently derive a class hierarchy which is optimized for our labeling scheme and, unlike most of existing works, has no schematic restrictions. Based on that we introduce a hierarchical multi-class pattern, called ConfusionTree-pattern, which is able to reach high classification accuracies. Our experiments show that our multi-class ConfusionTree-pattern reaches state-of-the-art results regarding performance and efficiency.

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 be disassembled in the next step and for those that cannot be yet, the motion planner has to be reliably fast.We present a new rigid body motion planner, called Expansive Voronoi Tree (EVT), which is optimized for complex ASP scenarios. The EVT estimates a globally reasonable path using a General Voronoi Diagram of the complete scene. With a novel EST-based sampling strategy, which is the contribution of this paper, it then locally explores the environment along the estimated path. The EVT automatically adapts to different clearance situations. It passes wide environments quickly and samples densely at narrow passages.We compare our EVT to state of the art motion planners which use different sampling strategies on a real-world data set consisting of a large subset of a car. The experiments show that the EVT is reliably many times faster and delivers shorter paths.

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 as an unknown part of the rigid mesh. That leads to the problem that unavoidable collisions occur during the planning process. Hence, the localization of the fastening elements and the integration of this information into the motion planning process is crucial for an automatic disassembly.We present a new geometric solution to extract salient features of 3D meshes which is specialized to find the fastening elements within the otherwise rigid mesh. Our approach measures a vertex-based surface feature using a local Gauss map in combination with a local thickness computation of the mesh. We compare our surface feature to state-of-the-art mesh saliency methods on various examples. Further, we integrate this measure of per-vertex saliency into a motion planning process and demonstrate the effectiveness of our result on real-world planning scenarios from the automotive industry.

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 an approximation of the GVD within minutes and meet the accuracy requirement of some few millimeters for the subsequent path planning. This is achieved by voxelizing the surface with a common error-bounded GPU render approach. We then use an error-bounded wavefront propagation technique and combine it with a novel hash table-based data structure, the so-called Voronoi Voxel History (VVH). On top of the GVD, we present a novel approach for the creation of a General Voronoi Diagram Graph (GVDG) that leads to an extensive roadmap. For the later motion planning task this roadmap can be used to suggest appropriate disassembly paths.

Recent advances in digitization of geometry and radiometry generate in routine massive amounts of surface meshes with texture or color attributes. This large amount of data can be compressed using a progressive approach which provides at decoding low complexity levels of details (LoDs) that are continuously refined until retrieving the original model. The goal of such a progressive mesh compression algorithm is to improve the overall quality of the transmission for the user, by optimizing the rate-distortion trade-off. In this paper, we introduce a novel meaningful measure for the cost of a progressive transmission of a textured mesh by observing that the rate-distortion curve is in fact a staircase, which enables an effective comparison and optimization of progressive transmissions in the first place. We contribute a novel generic framework which utilizes the cost function to encode triangle surface meshes via multiplexing several geometry reduction steps (mesh decimation via half-edge or full-edge collapse operators, xyz quantization reduction and uv quantization reduction). This framework can also deal with textures by multiplexing an additional texture reduction step. We also design a texture atlas that enables us to preserve texture seams during decimation while not impairing the quality of resulting LODs. For encoding the inverse mesh decimation steps we further contribute a significant improvement over the state-of-the-art in terms of rate-distortion performance and yields a compression-rate of 22:1, on average. Finally, we propose a unique single-rate alternative solution using a selection scheme of a subset among LODs, optimized for our cost function, and provided with our atlas that enables interleaved progressive texture refinements.

We propose an algorithm for real-time 6DOF pose tracking of rigid 3D objects using a monocular RGB camera. The key idea is to derive a region-based cost function using temporally consistent local color histograms. While such region-based cost functions are commonly optimized using first-order gradient descent techniques, we systematically derive a Gauss-Newton optimization scheme which gives rise to drastically faster convergence and highly accurate and robust tracking performance. We furthermore propose a novel complex dataset dedicated for the task of monocular object pose tracking and make it publicly available to the community. To our knowledge, it is the first to address the common and important scenario in which both the camera as well as the objects are moving simultaneously in cluttered scenes. In numerous experiments-including our own proposed dataset-we demonstrate that the proposed Gauss-Newton approach outperforms existing approaches, in particular in the presence of cluttered backgrounds, heterogeneous objects and partial occlusions.

We present a novel approach to 6DOF pose estimation and segmentation of rigid 3D objects using a single monocular RGB camera based on temporally consistent, local color histograms. We show that this approach outperforms previous methods in cases of cluttered backgrounds, heterogenous objects, and occlusions. The proposed histograms can be used as statistical object descriptors within a template matching strategy for pose recovery after temporary tracking loss e.g. caused by massive occlusion or if the object leaves the camera's field of view. The descriptors can be trained online within a couple of seconds moving a handheld object in front of a camera. During the training stage, our approach is already capable to recover from accidental tracking loss. We demonstrate the performance of our method in comparison to the state of the art in different challenging experiments including a popular public data set.

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 narrow passages, our approach achieves a speedup of up to 5.0 compared to well-established collision detection libraries like the Proximity Query Package (PQP) and the Flexible Collision Library (FCL).

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. In order to compare our approach we present a comprehensive experimental analysis about the parameters and the resulting performance. The algorithms and data structures were implemented in our own library RASAND, but we also compare the results of our work with OMPL [12] and the commercial software Kineo™ Kite Lab [15].

We present a novel, efficient, and flexible scheme to generate a high-quality mesh that approximates the outer boundary of a swept volume. Our approach comes with two guarantees. First, the approximation is conservative, i.e., the swept volume is enclosed by the generated mesh. Second, the one-sided Hausdorff distance of the generated mesh to the swept volume is upper bounded by a user defined tolerance. Exploiting this tolerance the algorithm generates a mesh that is adapted to the local complexity of the swept volume boundary, keeping the overall output complexity remarkably low. The algorithm is two-phased: the actual sweep and the mesh generation. In the sweeping phase, we introduce a general framework to compute a compressed voxelization. The phase is tailored for an easy application of parallelization techniques. We show this for our exemplary implementation and provide a multicore solution, as well as a GPU-based solution using CUDA. For the meshing phase we utilize and extend the well known Delaunay refinement such that it generates an adaptive conservative approximation that obeys the user defined upper bound on the one-sided Hausdorff distance to the swept volume. The approach is able to handle inputs of high complexity and compute an approximation with a very high precision, which we demonstrate on real industrial data sets.

Euclidean Distance (ED) and Dynamic Time Warping (DTW) are cornerstones in the field of time series data mining. Many high-level algorithms like kNN-classification, clustering or anomaly detection make excessive use of these distance measures as subroutines. Furthermore, the vast growth of recorded data produced by automated monitoring systems or integrated sensors establishes the need for efficient implementations. In this paper, we introduce linear memory parallelization schemes for the alignment of a given query Q in a stream of time series data S for both ED and DTW using CUDA-enabled accelerators. The ED parallelization features a log-linear calculation scheme in contrast to the naive implementation with quadratic time complexity which allows for more efficient processing of long queries. The DTW implementation makes extensive use of a lower-bound cascade to avoid expensive calculations for unpromising candidates. Our CUDA-parallelizations for both ED and DTW outperform state-of-the-art algorithms, namely the UCR-Suite. The gained speedups range from one to two orders-of-magnitude which allows for significantly faster processing of exceedingly bigger data streams.

We present a novel, efficient and flexible scheme to generate a high quality mesh that approximates the outer boundary of a swept volume. Our approach comes with two guarantees. First, the approximation is conservative, i.e., the swept volume is enclosed by the generated mesh. Second, the one-sided Hausdorff distance of the generated mesh to the swept volume is upper bounded by a user defined tolerance. Exploiting this tolerance the algorithm generates a mesh that is adapted to the local complexity of the swept volume boundary, keeping the overall output complexity remarkably low. The algorithm is two-phased: the actual sweep and the mesh generation. In the sweeping phase we introduce a general framework to compute a compressed voxelization. The phase is tailored for an easy application of parallelization techniques. We show this for our exemplary implementation and provide a multi-core solution as well as a GPU based solution using CUDA. The meshing phase utilizes Delaunay refinement which we carefully modified such that required guarantees are met. The approach is able to handle inputs of very high complexity at desired precision, which we demonstrate on real industrial data sets.

We present a novel technique for approximating the boundary of a swept volume. The generator given by an input triangle mesh is rendered under all rigid transformations of a discrete trajectory. We use a special shader program that creates offset geometry of each triangle on the fly, thus guaranteeing a conservative rasterization and correct depth values. Utilizing rasterization mechanisms and the depth buffer we then get a conservative voxelization of the swept volume (SV) and can extract a triangle mesh from its surface. This mesh is simplified maintaining conservativeness as well as an error bound measured in terms of the one-sided Hausdorff distance. For this we introduce a new technique for tolerance volume computation. The tolerance volume is implicitly given through six 2D-textures residing in texture memory and is evaluated in a special shader program only when needed.

Computer simulations play an ever growing role for the development of automotive products. Assembly simulation, as well as many other processes, are used systematically even before the first physical prototype of a vehicle is built in order to check whether particular components can be assembled easily or whether another part is in the way. Usually, this kind of simulation is limited to rigid bodies. However, a vehicle contains a multitude of flexible parts of various types: cables, hoses, carpets, seat surfaces, insulations, weatherstrips... Since most of the problems using these simulations concern one-dimensional components and since an intuitive tool for cable routing is still needed, we have chosen to concentrate on this category, which includes cables, hoses and wiring harnesses.This paper presents an interactive, real-time, numerically stable and physically accurate simulation tool for one-dimensional components. The modeling of bending and torsion follows the Cosserat model and is implemented with a generalized spring-mass system with a mixed coordinate system which features usual space coordinates for the positions of the points and quaternions for the orientation of the segments joining them. This structure allows us to formulate the springs based on the coordinates that are most appropriate for each type of interaction and leads to a banded system that is then solved iteratively with an energy minimizing algorithm.

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 pairs of curves intersect with high multiplicity. It is exact in that it always computes the mathematical correct result. It is efficient measured in running times.

In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure.No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constraints imposed by the chosen grid.In this paper we present a new approach which combines the grid-based combinatorial method with Simulated Annealing on a continuous model. This allows us to explore arbitrary orientations and placements of boxes, hence closing the gap even further, and - in some cases - even surpass the manual expert solution.The implemented software system allows our industrial partner to incorporate the trunk volume in a very early stage of the car design process without relying on a repeated and cumbersome manual evaluation of the volume.

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 quarter million of segmentsin the final arrangement.

Virtual prototyping and assembly planning require physically based simulation techniques. In this setting the relevant objects are mostly mechanical parts, designed in CAD-programs. When exported to the prototyping and planning systems, curved parts are approximated by large polygonal models, thus confronting the simulation algorithms with high complexity Algorithms for collision detection in particular are a bottleneck of efficiency and suffer from accuracy and robustness problems. To overcome these problems, our algorithm directly operates on the original CAD-data. This approach reduces the input complexity and avoids accuracy problems due to approximation errors. We present an efficient algorithm for computing the distance between patches of quadratic surfaces trimmed by quadratic curves. The distance calculation problem is reduced to the problem of solving univariate polynomials of a degree of at most 24. Moreover, we identify an important subclass for which the degree of the polynomials is bounded by 8.

We present two approaches to the problem of calculating a cell in a 3- dimensional arrangement of quadrics. The first approach solves the problem using rational arithmetic. It works with reductions to planar arrangements of algebraic curves. Degenerate situations such as tangential intersections and self-intersections of curves are intrinsic to the planar arrangements we obtain. The coordinates of the intersection points are given by the roots of univariate polynomials. We succeed in locating all intersection points either by extended local box hit counting arguments or by globally characterizing them with simple square root expressions. The latter is realized by a clever factorization of the univariate polynomials. Only the combination of these two results facilitates a practical and implementable algorithm.

The treatment of curved algebraic surfaces becomes more and more the f ocus of attention in Computational Geometry. We present a video that illustrates the computation of the convex hull of a set of ellipsoids. The underlying algorithm is an application of our work on determining a cell in a 3-dimensional arrangement of quadrics, see \cite{ghs-ccaq-01}. In the video, the main emphasis is on a simple and comprehensible visualization of the geometric aspects of the algorithm. In addition, we give some insights into the underlying mathematical problems.

The paper discusses SiLVIA simulation library. The main purpose of SiLVIA is to supply procedures for simulating the dynamics of colliding rigid bodies and the interactive manipulation of these bodies in virtual environments. Detecting collisions between virtual objects and calculating their reaction to these collisions play an important role in VR applications such as ergonomy, studies or virtual assembly simulations.

Detecting collisions and calculating physically correct collision responses play an important role when simulating the dynamics of colliding rigid bodies. VR-applications such as virtual assembly planning and ergonomy studies can especially profit from advances in these directions, because they enable an interactive and intuitive manipulation of objects in virtual environments. This paper presents new algorithms for the calculation of contact forces in multi-body systems with unilateral contacts.

The GALILEO-system is a developmental state-of-the-art rigid body simulation tool with a strong bias to the simulation of unilateral contacts for virtual reality applications.On the one hand the system is aimed at closing the gap between the 'paradigms of impulse-based simulation' and of 'constraint-based simulation'.On the other hand the chosen simulation techniques enable a balancing of the trade-off between the real-time demands of virtual environments (i.e.15-25 visualizations per second) and the degree of physical correctness of the simulation.The focus of this paper lies on the constraint-based simulation approach to threedimensional multibody systems including a scalable friction model.This is only one of the two main components of the GALILEO-software-module.A nonlinear complementarity problem (NCP)describes the equations of motion, the contact conditions of the objects and the Coulomb friction model.Further on we show, as an interesting evaluation example from the field of 'classical mechanics', the first rigid body simulation of the tippe-top.

The interactive manipulation of rigid objects in virtual reality environments requires an object behaviour which is at least physically plausible to be useful for applications such as interactive assembly simulation and virtual training. Physically plausible behaviour implies that collisions between simulated solid objects are taken into account and that the motion of objects with obstacle contacts can be controlled without force feedback mechanisms in an intuitively correct manner. We present a real time framework which enables the simulation of interactively controlled solid objects with a dynamically changing set of contact constraints. In this paper all contact configurations are replaced by a canonical set of point contacts which is updated dynamically. The basic step to determine the contact forces and object motion consists in the solution of a non-linear complementarity problem (NCP), which results from the unilateral contact conditions together with an adequate discretization of the corresponding differential equations of motion. © 1998 John Wiley & Sons, Ltd.

No abstract available.

In this paper we consider the following problem: given two general polyhedra of complexity n, one of which is moving translationally or rotating about a fixed axis, determine the first collision (if any) between them.We present an algorithm with running time O(n8/5+') for the case of translational movements and running time qn5/3+f f ) or rotational movements, where c is an arbitrary positive constant.This is the first known algorithm with sub-quadratic running time.