Collision detection with the graphics hardware

Our aim is to find a real-time collision detection method that allows us to take the whole tool into account instead of just considering its extremity. Detecting a collision between two objects basically consists in testing if the volume of the first one (ie. the tool, which has quite a simple shape), intersects the second one. This process is very close to a scene visualization process: in the latter, the user specifies a viewing volume (or frustum), characterized by the location, orientation and projection of a camera; then, the first part of the visualization process consists in clipping all the scene polygons according to this frustum, in order to render only the intersection between the scene objects and the viewing volume. Specialized graphics hardware usually performs this very efficiently.

Thus, the basic idea of our method is to specify a viewing volume corresponding to the tool shape (or alternatively to the volume covered by the tool between two consecutive time steps). We use the hardware to ``render'' the main object (the organ) relatively to this ``camera''. If nothing is visible, then there is no collision. Otherwise we can get the part of the object that the tool intersects.

Several problems occur: firstly, the tool shape is not as simple as usual viewing volumes. Secondly, we don't want to get an image, but we need meaningful information instead. More precisely, we would like to know which object faces are involves in a collision, and at which coordinates. The OpenGLgraphic library provides features that will allow us to model our problem in these terms. We review them in the next sections.

Viewing volumes

The most common frustum provided by OpenGLare those defined by an orthographic camera and by a perspective camera. In both cases, viewing volumes are hexahedra, respectively a box and a truncated pyramid, specified by six scalar values (see Figure 2).

  

Figure 2: (a) The OpenGLorthographic camera (left) and the OpenGLperspective camera (right). The viewing volumes, which are either a box or a truncated pyramid, are characterized by the distances to the far and near clipping planes and by the two intervals [left,right] and [top,bottom] which define their section in the near clipping plane.

Moreover, the user may add extra clipping planes for further restricting of the viewing volume, using glClipPlane(). All the versions of OpenGLcan treat at least six extra planes, so the viewing volume can be set to a dodecahedron. However, we must keep in mind that efficiency decreases each time an extra clipping plane is added.

Picking

The regular visualization process is divided into a geometrical part and a rasterization part. The geometrical part converts all the coordinates of the scene polygons into the camera coordinate system, clips all the faces relatively to the viewing volume, and achieves the orthographic or the perspective projection in order to get screen coordinates. The rasterization part transforms the remaining 2D triangles into pixels, taking care of the depth by using a Z-buffer in addition to the color buffer.

Computing the first part of the process is sufficient for the applications that only require meaningful informations about visible parts of the scene. A typical example is the picking feature in 3D interaction: a 3D modeler needs to know which object or face is just below the mouse, in order to operate on it when the user clicks. If several objects project on the same pixel, it can be useful to know each of them. In 3D paint systems, the program rather needs to know the texture coordinate corresponding to the pixel which is below the mouse.

OpenGLprovides two picking modes, that may be selected alternatively to the usual rendering mode GL_RENDER thanks to the function glRenderMode(). For these two modes, no rasterization is performed. Moreover, costly operations such as lighting are usually turned off. The picking modes differ from the informations they give back:

• the select mode GL_SELECT provides information about the visible groups of faces. A group name is given using glPushName() before each group of faces drawing, and OpenGLfills an array (provided by glSelectBuffer()) during the geometric pass of rendering, writing an entry per group that appears in the viewing volume. Thus one can know the faces that appear on screen. If the window has been reduced to a single pixel around the mouse, one gets the faces that appear below the mouse. If the camera geometry has been set in order to specify a given viewing volume, one gets the faces that intersect this viewing volume. Each entry contains some extra information, e.g. the z min and max inside the group, which can be used to sort or choose between multiple answers.

• the feedback mode GL_FEEDBACK provides extended information about the transformed and clipped scene. Basically, all the produced data can retrieved. The programmer indicates which kind of information he is interested in (positions, normals, colors, texture coordinates, ...), and provides an array with glFeedbackBuffer() that is filled by OpenGLduring the geometrical rendering pass. In the same way that above, the scene may be clipped to a 1 pixel size window around the mouse, in order to get the geometric data corresponding to the mouse location. A naming mechanism similar to the previous one, using glPassThrough(), allows to get in addition the information of the faces (or groups of faces) numbers appearing in the viewing volume.

Since hardware is used to compute transformations and clipping, and since no rasterization is performed (which means that almost all interpolations are suppressed), both picking processes are particularly efficient.