A collisions evaluation method in virtual environment for collaborativeassembly

https://doi.org/10.1016/j.jnca.2013.01.003Get rights and content

Abstract

Collision detection is critical for collaborative assembly simulation to assist design processing. However, collisions between polygonal models may not reflect collisions between real objects in reality because of polygonal approximation and designed tolerance. This problem reduces the reliability of simulation in collaborative assembly and sometimes even results in wrong conclusions. To solve the problem, we propose a novel collision evaluation algorithm based on generalized penetration depth, approximation information, and tolerance information. Given two interfered polygonal models, generalized penetration depth is calculated using relative motion information. Then two thresholds, which are based on approximation information and tolerance information, are integrated to evaluate collisions between polygonal models. In order to distinguish the status of collisions for further analysis, the collisions between polygonal models are categorized into three types by evaluation algorithm, namely real collision, potential collision, and fake collision. Computational efficiency and accuracy of the evaluation algorithm are verified in a virtual collaborative assembly environment.

Introduction

Collaborative technologies enable individuals to work together in assembly simulation. To perform the simulation in collaborative environment effectively, fast and accurate collision detection is one of fundamental techniques. Detecting collision is supposed to help designers check out potential problems in early stages or find a collision-free assembly path, however incorrect outcome resulted from detecting algorithms may make the simulation unreliable. Typically collision detection algorithms will check intersection between objects. To be effective in collision detection process, models of polygonal mesh are commonly used to represent objects and static environment. Although computational efficiency could be achieved using polygonal models, this kind of models introduces approximation errors. Due to this approximation, not all the collisions between polygonal models exist in reality, which may cause wrong results in some accurate applications such as assembly simulation. Therefore it is significant to evaluate collisions between polygonal models.

Although it has been implemented successfully in video games, motion planning, and physically-based animation, collision detection in assembly simulation is still a big bottleneck which limits the application. One of the main reasons is that collision detection in virtual collaborative assembly environment must accurately reflect collision state between physical models rather than digital models. If not, the result of collision detection is useless and the simulation is unrealistic. Some work has been done to perform collision detection in virtual collaborative environment. Yang et al. (2001)) present a dynamic grid based method to reduce the pairs of objects to detect collision in a large-scale virtual world simulation. Ma uses the method based on bounding volume hierarchy (BVH) model of axis align bounding box AABB trees to achieve high efficiency (Ma et al., 2011). Though effective the methods are, when it comes to the level of polygonal models, few works have been done to eliminate the approximation errors, which may lead to wrong detecting results. In some applications (Seth, 2007, Wang et al., 2003), geometric constraints such as concentricity, coplanar surfaces, etc. are applied between parts to reduce the degree-of-freedom and complete the assembly task. Liu et al. (2004) combine geometric constraints and collision detection to assist assembly by using a multi-layer exact collision detection in which collisions between marched pairs are eliminated. Assisted by geometric constraints, these approaches make it possible to move objects precisely; however, most of them lose the collision information, which would be needed in further analysis. In our methods, we pre-calculate the approximation errors and transfer them into thresholds to eliminate the inaccurateness lead by polygonal approximation. Besides approximation errors, tolerance information is usually assigned for some features during design stage of mechanical products. Both approximation errors and tolerance information need to be taken into account to determine collisions between real objects based on polygonal models. Consider the following two situations as shown in Fig. 1, in situation (a), a peg is inserted into a hole, which is with the same diameter as the peg. The peg and the hole are always approximated by prism in simulation. It is definitely that collisions would occur in this process, but this collision may not exist in reality if the peg and the hole are in clearance fit. In situation (b) part A is approaching part B in direction D. The intersection between them would be different when calculated in different direction, which should be evaluated to determine the actual collision state between real objects.

To achieve this goal effectively, the collision information, including penetration depth, colliding time and positions should be detected fast and accurately. Collision detection algorithms have been well studied and the methods could be generally categorized into discrete collision detection and continuous collision detection (Kim et al., 2008). Discrete-collision detection checks for collisions between static objects at each discrete time instance. These methods are easy to implement but fail to calculate the exact colliding configuration. Continuous collision detection takes the motion of objects into consideration and report the first time of intersection if a collision occurs. There are many approaches to implement continuous collision detection such as algebraic equation solving (Canny, 1986, Redon et al., 2000), swept volumes (Abdel-Malek et al., 2006), and adaptive bisection (Redon et al., 2001, Redon et al., 2002, Schwarzer et al., 2004). However most of these approaches could not run at interactive rate. In application of virtual collaborative assembly it is difficult to balance these two aspects. On one hand collision detection algorithm should run at interactive rate, on the other hand the collision results should be as accurate as possible because the collision results directly affect the reliability of assembly simulation. Until now few collision detection algorithm could be implemented effectively in this field. A simplified continuous collision detection method is presented in this paper to overcome this shortcoming. To reflect collision information correctly, the method of quantifying intersection is important. There are three main approaches to quantify collisions, namely volume of the intersection, penetration depth, and generalized penetration depth, as shown in Fig. 2. The methods using volume of intersections as measurement encounter problems when dealing with objects which vary in size. The volume of intersection between two big objects may be irrationally large even when there is only a tiny penetration. Penetration depth is the most widely used method. Most of the prior researches have been restricted on the translational penetration depth. The translational penetration depth between two objects is defined as minimum translational distance which is required to separate two interfered objects (Cameron and Culley, 1986, Dobkin et al., 1993). Many of the prior works are related to translational penetration depth. For the situation that the motion of objects is unknown, Minkowski sum is widely used to calculate translational penetration depth. But it is computational expensive to calculate Minkowski sum and the worst case computational complexity of computing Minkowski sum would be O(n6), where n is the number of features (Dobkin et al., 1993). Because rotational motion is not taken into consideration in translational penetration depth computation, it is insufficient to quantify collisions. For example, in Fig. 2, the part A could be more easily separated through both translational and rotational motion compared with only using the translation motion. Methods which combine both translational and rotational motion are proposed to quantify the extent of intersection by computing generalized penetration depth (Young et al., 2002). Because of the rotation’s nonlinear nature, the generalized penetration depth is much more complicated to calculate, but when thinking of accuracy need and motion’s translational and rotational nature, it is necessary to quantify collision using generalized penetration depth in order to yield more accurate result.

In this paper, we propose a novel formulation of generalized penetration depth computation between polygonal models. This formulation combines the current configuration of environment and the motion of parts. Then the generalized penetration depth is utilized to evaluate collisions between polygonal models in virtual collaborative assembly application by combining with two different thresholds, which are yielded from approximation errors and tolerance information. The main idea of this step is to compare these two different thresholds with the generalized penetration depth, and then based on the comparison results these collisions are categorized into three types: real collision, potential collision, and fake collision. A statistic of all collisions is provided to engineers for analysis of products. These works are based on our CSCWD conference paper (Shi et al., 2012). We use the method to a virtual collaborative assembly environment and add more detailed instruction about potential collision and determination of concave–convex in 3Dcase.

Section snippets

Scheme for evaluating collision

Collisions between polygonal models may not exist between real world objects. Depending on the realistic existence of collisions, collisions between polygonal models could be categorized into three types: real collision, potential collision, and fake collision. If a collision definitely exists between real objects, this collision is a real collision. If the existence of a collision is not determined, this collision is a potential collision. If a collision between polygonal models does not

Continuous collision detection

An efficient continuous collision detection algorithm is implemented to detect the detailed collision information. During virtual assembly simulation, users manipulate the grabbed objects through hardwares such as keyboard, mouse, haptic device and so on. Usually the input information of devices is mapped as increment transform of part ΔT. Then the new transform of object is calculated as (1).Xnew=ΔTXcurrent

Usually the transform is represented by a 4×4 matrix, but this kind of representation

Computation of generalized penetration depth

Continuous collision detection yields the incremental transform ΔTcontacttarget to quantify collisions. However, ΔTcontacttarget is not enough to evaluate collisions because of its deficiency in handling both translation and rotation. Generalized penetration depth is introduced to solve this problem. Generalized penetration depth computation depends on concave–convex determination. Before computing generalized penetration depth, it is essential to determine whether the intersection region is

Evaluation algorithm of collisions

Tolerance information affects the real world assembly significantly. To this end, it needs to take tolerance information into consideration when simulating assembly process. In this section we present the evaluation algorithm of collisions in virtual collaborative assembly environment, in which tolerance information is used to set thresholds, and approximation error is adopted to revise these thresholds. This evaluation algorithm determines the collision statues by comparing the generalized

Implement and results

A prototype system is developed to verify the evaluation algorithm. From a collision detection algorithm’s viewpoint, a virtual collaborative assembly environment is composed of S arbitrarily moving and M stationary parts. Each of the S parts could possibly collide with the other S-1 part as well as with the M stationary parts. Fig. 10 presents the architecture of system. For each time step, polygonal collision detection is implemented to find potentially colliding pairs among parts, and the

Conclusion and future work

We present and demonstrate the method that evaluates collisions between polygonal models in virtual collaborative assembly environment. This method puts more emphasis on accuracy in order to eliminate the incorrectness during assembly simulation. The motion state of objects, tolerance information and approximation errors are taken into consideration to evaluate collision during assembly simulation, which results that computation complexity increases in this method. To implement the method in

Acknowledgements

This work was supported by the National Natural Science Foundation, China, No. 50805009, the Specialized Research Fund for Doctoral Program of Higher Education, China, No. 20091101110010. The authors gratefully acknowledge this support.

References (16)

  • K Abdel-Malek et al.

    Swept volumes: foundations, perspectives, and applications

    International. Journal ofShape Modeling

    (2006)
  • Cameron S A and Culley R K. Determining the minimum translational distance between two convex polyhedra. In:...
  • J. Canny

    Collision detection for moving polyhedra

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (1986)
  • D Dobkin et al.

    Computing the intersection-depth of polyhedra

    Algorithmica

    (1993)
  • S Kim et al.

    Continuous collision detection for adaptive simulation of articulated bodies

    The Visual Computer

    (2008)
  • J Liu et al.

    Research and realization of collision detection algorithm in virtual assembly environment

    Journal of System Simulation

    (2004)
  • D Ma et al.

    Collaborative virtual assembly operation simulation and its application

  • Redon S, Kheddar A, Coquillart S. An algebraic solution to the problem of collision detection for rigid polyhedral...
There are more references available in the full text version of this article.

Cited by (12)

  • Development of a gap searching program for automotive body assemblies based on a decomposition model representation

    2015, Advances in Engineering Software
    Citation Excerpt :

    Song et al. [5] suggested a web-based interference verification system for mold design processes. Shi et al. [6] suggested a collisions evaluation method in virtual environment for collaborative assembly. Chen [7] also developed a new system for virtual assembly of parts and real time collision detection between parts.

  • Collaboration technologies and applications

    2013, Journal of Network and Computer Applications
  • Voxel-based recognition and visualization of water leakage gaps for automobile assembly

    2020, Zhejiang Daxue Xuebao (Gongxue Ban)/Journal of Zhejiang University (Engineering Science)
  • An approach to partition workpiece CAD model towards 5-axis support-free 3D printing

    2020, International Journal of Advanced Manufacturing Technology
View all citing articles on Scopus
View full text