1. Introduction - aim & objectives
2. Related Work
3. Motivation
4. Methodology
5. Input Output & Expected results
6. References
7. Online Resources

Introduction and problem description
 

 
Given the CAD models of various parts, an assembly sequence and a trajectory followed by the assembled parts for the assembly, it is important to detect any undue collision between the parts. Such collisions could occur due to various reasons such as incorrect trajectories, defective CAD models etc. Since the basic idea is to automatically simulate the real life assembly sequence, collision detection between the complex polyhedral parts is of utmost importance.

This project deals with efficient collision detection of polyhedral objects which are CAD models (described as STL files). The second phase of collision handling algorithm might be correct prediction of the dynamics of the object after the collisions, we however are not dealing with this aspect of the problem.

The main aim of the project is to load complex tesselated parts of a Light Combat Aircraft and build a framework to study the proper assembly sequences for these parts. The parts are extremely complex with thousands of surface triangles. To study assembly sequences for these complex parts, it is essential to detect collisions among them robustly.

The brute force method for collision detection is to detect intersections between two triangles. This obviously is going to be extremely computational intensive (the order of complexity being O(nm) where n, m  are the number of surface triangles in the models). A better approach is to build a simple approximation of the object and then test for collisions using this approximate model.

Back to Contents

Motivation
 

Realistic simulation of assembly sequence is of great significance in industry as it much cheaper and efficient than the real world alternative. While designing an assembly model, a number of modifications in the design take place before the actual model is conceptualised. During the design phase it would be convenient if we could test the actual assembly sequence using virtual models and look for 'imperfect fits' and other flaws in the various parts. This will give feedback for redesigning the parts or the assembly sequence. Moreover sometimes it is important to find out the exact instant at which the collision took place. This leads to the concept of time critical collision detection.

A further step might be to suggest the appropriate trajectory or the changes that might be needed in the CAD models. Next one could also find out the behaviour of the objects once the collision has taken place. This would require incorporating the material properties of the objects into the CAD models. This however is beyond the scope of this project.

Our motivation in this project is to build a framework in which the assembly sequences for complex polyhedral objects could be studied. We have defined a format in which the user  is supposed to give the assembly sequence between two polyhedral objects and the application tries to simulate the sequence in real time and find out the collision (if any) among the models in the execution of the assembly sequence.

Figure : An example of the LCA part which is used for the assembly sequence.

Back to Contents
 

---

Related Work

 

The problem of Collision Detection has been studied in detail and rich literature is available each of which suggest various methods of apporaching the problem so that the time complexity is reduced and the real time simulation can take place. The basic algorithm for collision detection has a fixed sampling time after which the detection algorithm is run. This does not give the exact time in which the collsion occured and also leads to inaccuracies and inefficiencies. The major deficiency is the absence of a proper representation which would make collision detection simpler.

Hubbard discusses in detail the pitfalls of the basic algorithm.

The approaches to rectify the above weaknesses has been the inclusion of another dimension to represent the simulation time. Canny uses numerical techniques to calculate the position and time of collision. Samet and Tamminen apply recursive subdivision to the four dimensions of space and time to finally locate the "cube" in which the collision occurs. These approaches, however, require the prior knowledge of the path taken by the object and are not suitable for interactive applications.

Other algorithms that do not focus on the time aspect are based on the subdivision of 3D space into regions and check for collision between these regions. Further approaches in this category use octrees, which are a hierarchy of grids at different resolutions. Collision detection based on octrees involve a recursive subdivision of the objects and check for collision among the subtrees. This approach essentially avoids unnecessary computation for the whole geometry of the objects and concentrates on the parts that actually suffer collision.  The various models which have been proposed to approximate the objects are Sphere hierarchies by Philip M. Hubbard, OBBs (Oriented bounding boxes) by S. Gottschalk et_al, AABs (Axis Aligned Bozes), Octrees etc. All these hierarchial models are very well suited for rejection tests when the objects are far apart. Furthermore, detecting collision among the basic building blocks of these models are very easy to reduce complexity of detecting collisions among them.
 

Back to Contents
 

Methodology

 
 Initially we had planned to implement the algorithm proposed by Philip M. Hubbard, Brown Univ, in his thesis work. His idea was to recursively subdivide the object using sphere trees. This sphere tree representation would then be used to detect collisions among the models. We, however, found out very soon that full implementation of the algorithm is impossible in a course project due to the complexity involved and we would never be able to carry out the primary motive of studying the LCA parts and testing assembly sequences for them. Furthermore, most of the hierarchial models use bounding boxes or octrees instead of sphere hierarchies. We, therefore, decided to implement the hierarchial model based on OBBs (Oriented Bounding Boxes) mainly because there were a lot of resources available on the web which would help us do the computations involved.

[2] describes the idea of Sphere hierarchies for Collision Detection in great detail.

The method that we have used was proposed by S. Gottschalk et_al [1]. The algorithm uses Oriented Bounding Boxes to approximate the model. The issues that come up are :-

Creation of OBBtrees

Collision Detection using OBBtrees

The creation of OBBtrees has two components :-
 
• Placement of tight fitting OBBs around polygons
• Grouping of OBB's to form a tree hierarchy


Placement of tight fitting OBBs

 
The polygons with more than three vertices are triangulated and a bounding box is found for each of them. The basic idea used behind finding a tight bounding box for the polygon is to find out the axes of minimum and maximum variance. The method used for finding out the axes of minimum and maximum variance is the following. The points obtained after triangulating the polygons are taken and their Covariance matrix is found out. The Covariance matrix is symmetrical and its eigenvectors are orthogonal. These eigenvectors are normalized and used as basis. The extremal vertices along these bases are found out and the bouding box is found out by aligning along the basis so as include all the extremal points. For points lying in the interior of the model, there might be problems as bounding boxes get aligned with them. To prevent this, a convex hull of the vertices of the triangles lying on the surface of the model is found out and the bounding boxes are aligned with them. The implementation of algorithms for finding convex hulls and OBBs are easily available in public domain. [1] describes the algorithm in greater detail.

Follow this link for further insight into the algorithm. <---
 
 

Grouping of OBBs to form a tree hierarchy
 
The methods of building hierarchy can be of two types - top down and bottom up. The bottom-up algorithms, as the name suggests, merge volumes and continue till a tree hierarchy is formed. The top-down approach begin with a group of all polygons and recursively subdivide until each of the leaf nodes are indivisible. The algorithm used here is simple top-down approach.

The basic idea used for splitting the bouding box is the following. The longest axis of the bounding box is taken and the box is split along a plane which is orthogonal to one of its axes. The polygons are partitioned depending upon the which side of the plane their center lies in. If such a subdivision is not possible then the second largest axis is taken. Else the shortest one. The 2D analog of the splitting algorithm is shown in the figure below.


Figure: Splitting the Bounding Boxes : The boxes are recursively partitioned along the longest axis and bounding boxes are found for the resulting groups. (Courtesy: S. Gottschalk et_al, "OBBtrees: Hierarchial Structure for Rapid Interference detection").

The basic requirement here is to calculate the overlap between the two bounding boxes. The Bounding boxes are projected on an axis in space. This is called 'Axial Projection'. The projection of the box on the axis forms an interval. If the intervals of two boxes overlap then further tests need to be done to find out if they actually overlap. Otherwise, one may be assured that the boxes don't overlap. Moreover, it has been proved that any two disjoint convex polyhedras in 3D can always be separated by a plane which is parallel to a face of either polyhedra or parallel to the edge of each polyhedra. This fact coupled with the previous elimination test can be used to find out efficiently if the bounding boxes overlap.

Figure : L is the separating axis for the OBBs A and B as they become disjoint intervals after projection onto L.

Format of STL files
 

The STL files have a very specific format and are used by a number of CAD packages to save the models. The STL file format is based on the representation of an object using triangles in 3D. The following is a link to the html file which explains the STL file format in detail : stl_fmt.html

Assembly Sequence

The application we have built has the capability of loading multiple STL files and then running an assembly sequence on all of them. The format of the assembly sequence has been kept with the source code too. The assembly sequence is provided using a simple representation in which the user will have to enter the amount of translation in each frame. The user can also specify rotation about one of the three major axes. Initially we had kept the option of rotating around any arbitrary axis, but since specifying the rotations in that manner aren't extremely intuitive to the user, we have kept the rotation axes as the major axes.

Back to Contents

To do OBB based collision detection, its best to have the position of the objects in the world with respect to an origin denoted by the rotation and translation matrices from the initial placement in the world. Hence the assembly sequence which is an input to the program is best specified by the transformation of the models from the initial world coordinates. However, it is difficult for the user to specify the matrices himself. The best way in which the user can specify the sequence is by giving relative transformation about the last step in the sequence  in a simple, intuitive format. Hence we have written a generator program which takes as input the user specified assembly sequence and outputs the matrix transformations for the steps specified in the sequence. The format of the input and the output files is specified in the following section.

Back to Contents

Input, Output and Results

Input

• The CAD models (in STL format) which are involved in the assembly sequence are input to the system
• The assembly sequence in the format specified
• The matrix file generated by the generator. It takes the relative translations which the user specifies and generates matrices relative the original position in the world.

Output

• The collided parts of the models are rendered in red.

Results

• The program is efficient and can be run in real time with a fast display card. The major reason for this is the use of efficient algorithms for solving the sub problems involved.
• The results obtained are satisfactory. For very complex non-convex polyhedra, the program gives erratic results at times.

The following are some of the result images which we obtained by taking a screen dump of the application.
  Figure : The figures show the collision detection among the parts while they were undergoing assembly
 
 

Figure : Four parts undergoing assembly simultaneously and there is collision between the 2nd and the third part

References

1. S. Gottschalk, M.C. Lin and D. Manocha, "OBBtree: A Hierarchial Structure for Rapid Interference Detection", Proc of ACM SIGGRAPH, 1996. http://www.cs.unc.edu/~geom/OBB/OBBT.html
2. Philip M. Hubbard, "Approximating Polyhedra with Spheres for Time-Critical Collision Detection", ACM Transactions on Graphics, Volume 15, July - 1996. http://siesta.cs.wustl.edu/~pmh/
3. Philip M. Hubbard, "Real-Time Collision Detection and Time-Critical Computing", Workshop on Simulation and Interaction in Virtual Environments, July - 1995.http://siesta.cs.wustl.edu/~pmh/
4. Philip M. Hubbard, "Collision Detection for Interactive Graphics Applications", IEEE transactions on Visualization and Computer Graphics, Sept. 1995.http://siesta.cs.wustl.edu/~pmh/
5. Jonathan D. Cohen, M. C. Lin, D. Manocha, and M. K. Ponamgi, "I-COLLIDE : An interactive and Exact Collision Detection System for Large-Scale Environments", Proceedings of the 1995 Symposium on Interactive 3D Graphics, California, 1995. http://www.cs.unc.edu/~dm/

Back to Contents

• PQP : Proximity Query Package
• I-COLLIDE : A Collision Detection Library for Convex Ployhedra
• Q-COLLIDE  : Quick Collision Detection
• RAPID : Robust and Accurate Polygon Interference Detection System
• V-Clip : A low level collision detection library for polyhedral objects
• QuickCD : Software library for efficient collision detection