For simulation in computer aided surgical interventions the detection of impingement between parts of the patient's anatomy and/or implants is often of key importance. Impingement (collision) detection methods used in the existing literature seem to be unsuitable for two reasons. First, a polyhedral approximation of an anatomical model is not appropriate, since medical images are quite irregular and are essentially non-linear. Secondly, geometric and temporal coherences are not always available, since just final results may be of interest.

A method for performing surgery on a body portion with the steps of loading previously established surgical plan data into a computer, registering a three-dimensional computer model of the body portion stored in the surgical plan data to the body portion of the patient, providing at least one surgical tool, positioning the surgical tool relative to the body portion and performing the surgery is known from US 5,682,886 DELP. Before the surgical procedure may be effected image data of the body portion must be gathered by means of applying a radiant energy means e. g. magnetic resonance imaging, X-ray devices or computed tomography imaging devices. The so gathered image data is then stored in a memory means for storing image data and the stored image data read into a computer interfaced to the memory means, whereby the computer has a visual display means for displaying images generated in at least one process step.

The surgery plan data comprises the three-dimensional computer model of the body portion and data relating to at least one prosthesis of defined size and position relative to the body. Before performing the surgery the three-dimensional computer model of the body portion is registered on-site to the actual body-portion by means of suitable magnetic devices, acoustic devices or optical devices such as a wand with LED's that are sensed by external cameras. Furthermore, this known surgical procedure subsystem allows the surgeon to implement the preoperative plan by accurately guiding the placement of the prosthesis on the patient's bone. Thereby, the position measurement device reports to the computer the three-dimensional position of a movable probe, surgical instrument or component of a prosthesis. In case a MR imaging machine (Magnetic Resonance) is used data points are automatically collected in order to register the body portion and the instruments to the three-dimensional computer model. The use of such a MR imaging machine provides the surgeon a real-time image of the body portion and the instruments. Instead of a MR imaging machine a intraoperative CT device (computer tomography) could be used.

This known method shows the disadvantage that the impingement of two bodies e. g. the body portion and a surgical instrument may only be detected in real-time by using an imaging device, e. g. a MR imaging machine intraoperatively.

The object of the invention is palliation. It addresses the creation of a method to detect impingement between two bodies in real-time by using registration devices without the need of intraoperative imaging as MR, CT or X-ray devices.

The goal of collision detection (also known as interference detection, contact determination, or impingement detection) is to automatically report a geometric contact when it is about to occur, or has actually occurred [5]. The problem is encountered in computer-aided design and machining (CAD/CAM), robotics and automation, manufacturing, computer graphics, animation, and computer simulated environments. In many of these application areas, collision detection is a major computational bottleneck.

There are two kinds of collision detection methods. The first kind determines whether the surfaces of objects intersect [6], while the second one is based on the calculation of distances of objects, since two objects are separate if they have a positive distance from each other [4]. These methods always suppose that objects are represented or approximated as polyhedrons [8], which is not always feasible in anatomic-related applications, where the objects are some anatomical parts and are essentially non- linear. These methods need to perform a search for closest feature pairs, or a calculation of dot products of vectors of all polygons and edges, which is quite time consuming when models are non-linear. In addition, these methods suppose that objects move only slightly between successive time steps or simulation frames, so that temporal and geometric coherences [5] play a crucial role to speed up the calculation.

This assumption is not always true in computer aided surgery, if for example, the range of motion of the femur with respect to pelvis [2] should be calculated.

The collision detection problem in computer aided surgery can be better described by applying a relative transformation to an anatomical object and checking if collision occurs, since the status of intermediate positions may be considered clinically irrelevant.

In addition, the more general term'collision'is referred to as impingement in medically related applications [2], and the research effort so far has been quite limited. Unlike in other applications, where the geometric models are explicitly given in the form of polygonal objects, splines, or algebraic surfaces, the anatomical medical image is rather irregular, and implicit geometric models are preferred. Physically, bony objects cannot penetrate one another. Therefore it is not necessary to compute the exact volume of penetration, rather it will suffice to report if and where impingement between the objects occurs.

The invention solves this problem using a method with the steps of claim 1 and a device with the features of claim 12.

The method of fast impingement detection between at least two bodies according to the invention comprises the steps of A) acquisition of three-dimensional image data of the at least two bodies as a first set of binary data with reference to at least one three-dimensional system of coordinates by means of image acquisition means; B) obtaining a second set of binary data of points on the three-dimensional surface of each of the bodies with reference to at least one three-dimensional system of coordinates using the first set of binary data acquired under A) by means of a computer; C) attaching at each of the bodies a reference element comprising at least three markers; . D) establishing a mathematical relationship between the at least one three-dimensional system of coordinates and the position of the markers rendering possible a relationship between the points on the surface of the bodies and the markers; E) displacing at least one body relative to the other; F) measuring the three-dimensional coordinates of the markers with respect to an on- site three-dimensional system of coordinates by means of a position measurement device; and G) transforming the three-dimensional coordinates of the markers into three- dimensional coordinates of the surface points of the bodies with respect to the on-site three-dimensional system of coordinates by means of the computer; characterized in that the method further comprises the step of H) computing if and where two surface points being each on the surface of a separate body and being closest to each other coincide within the on-site three-dimensional system of coordinates by means of the computer.

A detailed description of methods for generating a medical image data set as a three dimensional array of binary voxels (bitvolumes) through segmentation and reconstruction of a medical image received e. g. via a radiant energy means can be found in [12]. Known methods in medical imaging technology are X-ray, Magnetic Resonance Imaging (MR), Computed Tomography, Positron Emission Tomography (PET), Single Photon Emission Computing Tomography (SPECT) and Ultrasonography.

Another method of gathering three-dimensional image data of the two bodies as a first set of binary data comprises the use of Computer Aided Design Software on a computer.

For computing if and where two surface points being each on the surface of separate body and being closest to each other coincide within the on-site three-dimensional system of coordinates is preferably performed through a fast impingement detection algorithm allowing the performance of the method according to the invention in real time.

The preferred algorithm of the method according to the invention takes implicit object models from reconstruction of anatomical CT data that represent complicated anatomical structures. To speed up the detection procedure, a lookup table and a linear transformation are introduced. Searching for impingement between any two objects thus becomes a problem of calculating spatial indices and checking the lookup table.

Thereby it is assumed that all objects are rigid bodies, i. e. they do not undergo any deformations.

Since searching for impingement among multiple objects can be represented as impingement detection between groups of two objects, only the impingement detection between two objects will be discussed.

The basic idea of the preferred method is that if two objects collide, they must share at least one common point in space. Both objects are free to move in space, but in fact, the problem can be modeled as the relative movement of one object with respect to the other one. When two objects change their relative positions in a way that contact occurs, the first contact point is located on the surfaces of both objects. Except for one special case, which is discussed later in this section, two objects must have at least one common surface point when they impinge. Since the number of surface points of an object is much smaller than the number of voxels making up the object, it is more efficient to search for impingement only among the surface points. The proposed algorithm can be broken into the following steps: (a) obtaining the surface representations of objects, (b) defining a linear transform to calculate the spatial indices, (c) building up a lookup table to confine the free space where impingement may occur, and (d) searching the confined space to locate possible impingement. These steps are discussed in detail in the following.

(a) Suppose two objects A and B are given as three dimensional arrays of binary voxels, so-called bitvolumes. Without losing generality, it can be assumed that A is static, and B may move with respect to A. This assumption is valid since only relative movement needs to be considered. Surface representations of both objects can be obtained by segmentation and reconstruction of the associated CT data. This creates only the bitvolumes, not the surfaces. The process of segmentation is not covered here.

Suppose that the number of surface points of A is LA and that of B is LB. The coordinates of the i-th surface boundary point of A and B are given by (XA YA(i), YA (i), (i=1, 2, ..., LA), (XB (i), YB (i) M ZB (i)) (i=1,2, ..., LB).

Let us denote the maximum and minimum values of XA (i), YA (i), ZA (i) by MaxAX and MinAX, MaxAY and MinAY, and MaxAZ and MinAZ, respectively. Mathematically these relationships are given by: MinAX < XA (i) # MaxAX (i=1, 2, --, LA) MINAY # YA(i)#MaxAY (i=1,2,..., LA) (1) MinAZ#ZA (i) # MaxAZ (i=1, 2, ..., LA) From equation (1) the three-dimensional extents of A can be calculated : DimAX = MaxAX-MinAX DimAY = MaxAY-MinAY (2) DimAZ = MaxAZ-MinAZ (b) A linear transform can be performed to define a spatial index id (x, y, z) for a given point (x, y, z): id (x, y, z) =x-MinAX + (y-MinAY)- (DimAX+1) + (z-MinAz) (DimAX+1) (DimAY+1) (3) where (x, y, z) satisfy equation (1). This index is used to quickly access elements in the LUT defined below. From a given index id (x, y, z), the spatial point (x, y, z) can also be uniquely calculated x=id-(z-MinAZ)#(DimAX+1)#(DimAY+1)-(y-MinAY)#(DimAX+1)+MinAX (6) where int [f] is a function that gives an integer value fi for a real variable f with fi # f and (fi-f) <1. From equations (3)- (6), a one-to-one relationship between spatial points and their spatial indices can be created to map equivalence. This equivalence allows to search the lookup table (LUT, defined below) in order to check if two objects share any spatial positions.

(c) A one-dimensional lookup table (LUT) is created. It is based upon the spatial information of the static object A. The size of the look-up table is given by: SIZE = (DimAZ +1)#(DimAY + 1)#(DimAX + 1) Initially, the LUT (id (x, y, z)) is initialized to 0 for all points, since no impingement initially occurs. Then, for every surface boundary point of A (XA (i), YA (i), ZA (i)), the spatial index id (XA (i), YA (i), ZA (i)) (i)) (i=1, 2, ..., LA) is calculated, and LUT (id ( XA (i), YA (i), ZA (i))) is set to a non-zero value to represent that this spatial position is occupied by object A.

(d) After any relative movement of B with respect to A, the coordinates of the i-th surface point of B are calculated or computed as (TXB (i), TYB (i), TZB (i)) (i=1, 2, ..., LB) If the relative transformation of B with respect to A can be expressed as a rotation matrix R and a translation vector T, then (TXB (i), TYB (i), TZB (i)) are calculated from (XB (i), YB (i), ZB (i)), by the following formulae, TXB (i) =R [0] [O] *XB (i) +R [0] [1] *YB (i) +R [0] [2] *ZB (i) +T [0] (7) TYB (i) =R [1] [0] *XB (i) +R [1] [1] *YB (i) +R [1] [2] *ZB (i) +T [1] (8) TZB (i) =R [2] [0] *XB (i) +R [2] [1] *YB (i) +R [2] [2]*ZB (i) +T [2] (9) for all points (TXB (i), TYB (i), TZB (i)) satisfying: MinAX # TXB (i) < MaxAX MinAY #TYB (i) S MaXAY MinAZ<TZB (i) # MaxAZ The spatial index id (TXB (i), TYB (i), TZB (i)) can be calculated according to (2). If LUT (id (TXB (i), TYB (i), TZB (i))) is zero, for all i=1, 2,..., LB, none of B's surface points is located at a position that is occupied by one of A's surface points, which means the absence of impingement. If however, for one i, LUT (id (TXB (i), TYB (i), TZB (i))) is non-zero, A and B share a common surface point at (TXB (i), TYB (i), TZB (i)), which means that impingement has occurred. All points (TXB (i), TYs (i), TZB (i)) with LUT (id (TXB (i), TYB (i), TZB (i))) non-zero are deemed to be contact points of the impingement.

Theoretically, there is one special case of impingement that needs to be mentioned, i. e. the case when object B is totally enclosed within object A. Although impingement does occur, there are no shared surface points, and hence the proposed algorithm will fail. To account for this exception, the described algorithm is slightly modified. Instead of representing the static object A by its surface, A is represented by its entire volume, and LUT is set to non-zero values for all voxels of A. When impingement occurs, the surface points of object B are checked against the modified LUT, which resolves the described pathologic case. However, since this exception can never occur physically, the basic algorithm may be used for testing and verification.

The measurement of the coordinates of the markers attached to the reference bodies with respect to the three-dimensional on-site coordinate system is performed with a position measurement device that is connected to the computer using software to evaluate the coordinates from the data received from the position measurement device.

The markers as well as the detectors of the position measurement device may be accoustic or electromagnetic effective means such as energy emitting, receiving or reflecting means. For instance as energy emitting means: -Light sources, particularly light emitting diodes (LED's); -Infrared light emitting diodes (IRED's) ; -Accoustic transmitters; or -Coils or as energy receiving means: -Photodiodes; -Microphones; or -Hall-effect components may be used.

A custom optoelectronic position measurement device may be used e. g. an OPTOTRAK 3020 System, Northern Digital, Waterloo, On., Canada. It preferably comprises -an OPTOTRAK 3020 Position Sensor consisting of three one-dimensional charge- coupled devices (CCD) paired with three lens cells and mounted on a stabilized bar.

Within each of the three lens cells, light from an infrared marker is directed onto a CCD and measured. All three measurements together determine-in real time-the three- dimensional location of the marker; -a system control unit; -a computer interface card and cables; -data collection and display software; and -a strober and marker kit.

Computer assisted surgery systems (CAS systems) that are provided with a computer and a position measurement device in order to measure the position of surgical instruments or devices which are displaceable within the operation area are disclosed e. g. in US 5,383,454 BUCHHOLZ and EP 0 359 773 SCHLONDORFF. Often these CAS-systems comprise a memory means in order to store medical images such as e. g. X-rays, Computertomographs or MR images (Magnetic Resonance images) using radiant energy means. Thereby the medical images may be gathered pre-operatively or intraoperatively.

A key issue in computer assisted surgery (CAS) is to establish a mathematical relationship between the patient's intraoperative position respectively the on-site position of the surgical implants and the three-dimensional computer model of the patient's body respectively the surgical implants that are stored e. g. as a data set in a medical imaging library. The process of computing a transformation from coordinates within an on-site coordinate system to image coordinates is referred to as"registration" or"matching". Recent developments allow the surgeon to obtain a number of points on the surface of a bone or implant with a pointer having at least three markers and measure the position of the pointer with the position measurement device whereby this "cloud of points"can be mathematically fit onto the medical image of the bone surface or implant surface through an optimisation algorithm [9 ; 10]. This process is termed "surface matching". Instead of using a pointer an ultrasound device may be used in order to gather a number of points on the surface of a bone or implant.

The device for impingement detection between at least two bodies according to the invention comprises : A) at least two reference bodies each having at least three non-linearly arranged markers attachable to two bodies, particularly to bones, bone fragments or surgical implants ; B) a position measurement device in order to determine the on-site position of the markers; C) a computer connected to the position measurement device and provided with software apt to compute the position of the markers with reference to an on-site three- dimensional coordinate system; and D) indicating means indicating the occurrence of impingement between the two bodies.

In the preferred embodiment of the device according to the invention the indicating means consist of an alarm.

In another embodiment of the device according to the invention the alarm preferably comprises loudspeakers and a voice coder connected to the computer to indicate the occurrence of impingement through speech.

Further advantageous of the invention are stated in the dependent claims.

Essentially the advantages of the method according to the invention are that due to: -A minimal invasive surgical technique may be applied e. g. during implantation of prostheses; -The algorithm provides a general-purpose impingement detection method in the sense that the objects (bodies, bone fragments) can be of any shape; and -It can be extended to any number of objects in the scene.

The preferred embodiment of the device according to the invention is elucidated below in relation to the drawing shown in partly schematic manner.

Fig. 1 shows the preferred embodiment of the device according to the invention with a femoral and acetabular components of a total hip prosthesis as first and second body.

In Fig. 1 the application of the device according to the invention is shown in its clinical use in case of a total hip replacement operation. The device comprises a) two reference elements 5 ; 6 with four LED's as markers 7 that are attached to the two bodies 1; 2 whereby body 1 is the acetabular component and body 2 the femoral component of a total hip prosthesis; b) an optoelectronic position measurement device 14 comprising a system control unit 18 and cables 20 in order to measure the position of the markers 7 within the on-site three-dimensional system of coordinates 4; c) a computer 11 with a display data storage means 13 and a computer interface card 19 to connect the computer 11 to the position measurement device 14; d) a pointer 15 with for markers 7 to perform the registration step by obtaining a number of surface points; and d) an alarm as indicating means 8 to indicate the occurrence of impingement between the two surface points 9; 10 that are each on the surface of a separate body 1 ; 2 and that are closest to each other. The computation of this impingement detection is performed by means of the computer 11.

References 1. Gong J, Bächler R, Sati M, Nolte LP (1997) Restricted surface matching: a new approach to registration in computer assisted surgery. In In Troccaz J, Grimson E, Moesges R (Eds.): First Joint Conference Computer Vision, Virtual Reality and Robotics in Medicine and Medical Robotics and Computer Assisted Surgery. Grenoble, France.

Springer 597-605 2. Jaramaz B, Nikou C, Simon DA, DiGioia AM (1997) Range of motion after total hip arthroplasty : experimental verification of the analytical simulator. In Troccaz J, Grimson E, Moesges R (Eds.): First Joint Conference Computer Vision, Virtual Reality and Robotics in Medicine and Medical Robotics and Computer Assisted Surgery. Grenoble, France. Springer 573-582 3. Lin MC, Canny JF (1991) A fast algorithm for incremental distance calculation.

Proceeding of IEEE International Conference on Robotics and Automation, California, USA, 2: 1008-1014 4. Lin MC (1993) Efficient collision detection for animation and robotics. Ph. D. thesis.

University of California, Department of Electrical Engineering and Computer Science, Berkeley, USA 5. Lin MC, Manocha D (1995) Fast interference detection between geometric models.

The Visual Computer 11 (10): 542-561 6. Moore M, Wilhelms O (1988) Collision detection and response for computer animation. Computer Graphics 22(4): 289-298 7. Nolte LP, Zamorano L, Visarius H. Berlemann U, Langlotz F, Arm E, Schwarzenbach O (1995) Clinical evaluation of a system for precision enhancement in spine surgery.

Clinical Biomechanics 10 (6): 293-303 8. Zeiller M (1994) Collision detection for complex objects in computer animation. Ph. D. thesis. Technical University of Vienna, Austria 9. Gong, J., Bächler, R., Sati, M., Nolte, L. P.

Restricted surface matching: A new approach to registration in computer assisted surgery Proc. 3 Int. Symp. Med. Robot. Comput. Assist. Surg. (MRCAS) 10. Bachoter, R., Bunke, H., Nolte, L. P.

Restricted surface matching-Numerical optimization and technical evaluation Comput. Aided Surg. 1999 12. Pommert, A., Riemer, M., Schiemann, T., Schubert, R., Tiede, U., Hohne, K. H.

Three-dimensional imaging in medicine: methods and applications Pommert et al. : 3D Imaging in Medicine