We introduce a new algorithm for computing the distance from a point to an arbitrary polygonal mesh. Our algorithm uses a multiresolution hierarchy of bounding volumes generated by geometric simplification. Our algorithm is dynamic, exploiting coherence between subsequent queries using a priority process and achieving constant time queries in some cases. It can be applied to meshes that transform rigidly or deform nonrigidly. We illustrate our algorithm with a simulation of particle dynamics and collisions with a deformable mesh, the computation of distance maps and offset surfaces, the computation of an approximation to the expensive Hausdorff distance between two shapes, and the detection of self-intersections. We also report comparison results between our algorithm and an alternative algorithm using an octree, upon which our method permits an order-of-magnitude speed-up.

Many real-world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, and smoothing. We present an algorithm that removes singularities from nonmanifold sets of polygons to create manifold (optionally oriented) polygonal surfaces. We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching operation, we maintain the surface as a manifold while joining boundary edges. We present two different edge stitching strategies, called pinching and snapping. Our algorithm manipulates the surface topology and ignores physical coordinates. Except for the optional stitching, the algorithm has a linear complexity and requires no floating point operations. In addition to introducing new algorithms, we expose the complexity (and pitfalls) associated with stitching. Finally, several real-world examples are studied.

We present a method for compressing non-manifold polygonal meshes, i.e. polygonal meshes with singularities, which occur very frequently in the real-world. Most efficient polygonal compression methods currently available are restricted to a manifold mesh: they require a conversion process, and fail to retrieve the original model connectivity after decompression. The present method works by converting the original model to a manifold model, encoding the manifold model using an existing mesh compression technique, and clustering, or stitching together during the decompression process vertices that were duplicated earlier to faithfully recover the original connectivity. This paper focuses on efficiently encoding and decoding the stitching information. By separating connectivity from geometry and properties, the method avoids encoding vertices (and properties bound to vertices) multiple times; thus a reduction of the size of the bit-stream of about 10% is obtained compared with encoding the model as a manifold.

This paper describes an ongoing project to develop a computer-integrated system to assist surgeons in revision total hip replacement (RTHR) surgery. In RTHR surgery, a failing orthopedic hip implant, typically cemented, is replaced with a new one by removing the old implant, removing the cement and fitting a new implant into an enlarged canal broached in the femur. RTHR surgery is a difficult procedure fraught with technical challenges and a high incidence of complications. The goals of the computer-based system are the significant reduction of cement removal labor and time, the elimination of cortical wall penetration and femur fracture, the improved positioning and fit of the new implant resulting from precise, high-quality canal milling and the reduction of bone sacrificed to fit the new implant. Our starting points are the ROBODOC system for primary hip replacement surgery and the manual RTHR surgical protocol. We first discuss the main difficulties of computer-integrated RTHR surgery and identify key issues and possible solutions. We then describe possible system architectures and protocols for preoperative planning and intraoperative execution. We present a summary of methods and preliminary results in CT image metal artifact removal, interactive cement cut-volume definition and cement machining, anatomy-based registration using fluoroscopic X-ray images and clinical trials using an extended RTHR version of ROBODOC. We conclude with a summary of lessons learned and a discussion of current and future work.

We present a technique for simplifying a triangulated surface. Simplifying consists of approximating the surface with another surface of lower triangle count. Our algorithm can preserve the volume of a solid to within machine accuracy; it favors the creation of near-equilateral triangles. We develop novel methods for reporting and representing a bound to the approximation error between a simplified surface and the original, and respecting a variable tolerance across the surface. A different positive error value is reported at each vertex. By linearly blending the error values in between vertices, we define a volume of space, called the error volume, as the union of balls of linearly varying radii. The error volume is built dynamically as the simplification progresses, on top of preexisting error volumes that it contains. We also build a tolerance volume to forbid simplification errors exceeding a local tolerance. The information necessary to compute error values is local to the star of a vertex; accordingly, the complexity of the algorithm is either linear or in O(n log n) in the original number of surface edges, depending on the variant. We extend the mechanisms of error and tolerance volumes to preserve during simplification scalar and vector attributes associated with surface vertices. Assuming a linear variation across triangles, error and tolerance volumes are defined in the same fashion as for positional error. For normals, a corrective term is applied to the error measured at the vertices to compensate for nonlinearities.

In this paper we introduce the Progressive Forest Split (PFS) representation, a new adaptive refinement scheme for storing and transmitting manifold triangular meshes in progressive and highly compressed form. As in the Progressive Mesh (PM) method of Hoppe, a triangular mesh is represented as a low resolution polygonal model followed by a sequence of refinement operations, each one specifying how to add triangles and vertices to the previous level of detail to obtain a new level. The PFS format shares with PM and other refinement schemes the ability to smoothly interpolate between consecutive levels of detail. However, it achieves much higher compression ratios than PM by using a more complex refinement operation which can, at the expense of reduced granularity, be encoded more efficiently. A forest split operation doubling the number n of triangles of a mesh requires a maximum of approximately 3:5n bits to represent the connectivity changes, as opposed to approximately #5 + log 2 #n## n bits in PM. We describe

Many real world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, smoothing, etc. We present an algorithm for removing such singularities, thus converting non manifold sets of polygons to manifold polygonal surfaces (orientable if necessary). We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching phase, we join surface boundary edges that were cut, or whose endpoints are sufficiently close, while guaranteeing that the surface is a manifold. We study two different stitching strategies called "edge pinching" and "edge snapping"; when snapping, special care is required to avoid re-creating singularities. The algorithm manipulates the polygon vertex indices (surface topology) and essentially ignores vertex coordinates (surface geometry). Except for the optional stitching, the algorithm has a linear complexity in the number of vertices edges and faces, and require no floating point operation.

We describe new methods for rigid registration of a preoperative computed tomography (CT)-scan image to a set of intraoperative X-ray fluoroscopic images, for guiding a surgical robot to its trajectory planned from CT. Our goal is to perform the registration, i.e., compute a rotation and translation of one data set with respect to the other to within a prescribed accuracy, based upon bony anatomy only, without external fiducial markers. With respect to previous approaches, the following aspects are new: 1) we correct the geometric distortion in fluoroscopic images and calibrate them directly with respect to the robot by affixing to it a new calibration device designed as a radiolucent rod with embedded metallic markers, and by moving the device along two planes, while radiographs are being acquired at regular intervals; 2) the registration uses an algorithm for computing the best transformation between a set of lines in three space, the (intraoperative) X-ray paths, and a set of points on the surface of the bone (imaged preoperatively), in a statistically robust fashion, using the Cayley parameterization of a rotation; and 3) to find corresponding sets of points to the X-ray paths on the surfaces, our new approach consists of extracting the surface apparent contours for a given viewpoint, as a set of closed three-dimensional nonplanar curves, before registering the apparent contours to X-ray paths. Aside from algorithms, there are a number of major technical difficulties associated with engineering a clinically viable system using anatomy and image-based registration. To detect and solve them, we have so far conducted two experiments with the surgical robot in an operating room (OR), using CT and fluoroscopic image data of a cadaver bone, and attempting to faithfully simulate clinical conditions. Such experiments indicate that intraoperative X-ray-based registration is a promising alternative to marker-based registration for clinical use with our proposed method.

Beginning with digitized volumetric data, we wish to rapidly and efficiently extract and represent surfaces defined as isosurfaces in the interpolated data. The Marching Cubes algorithm is a standard approach to this problem. We instead perform a decomposition of each 8-cell associated with a voxel into five tetrahedra. We guarantee the resulting surface representation to be closed and oriented, defined by a valid triangulation of the surface of the body, which in turn is presented as a collection of tetrahedra. The entire surface is "wrapped" by a collection of triangles, which form a graph structure, and where each triangle is contained within a single tetrahedron. The representation is similar to the homology theory that uses simplices embedded in a manifold to define a closed curve within each tetrahedron. We introduce data structures based upon a new encoding of the tetrahedra that are at least four times more compact than the standard data structures using vertices and triangles. For parallel computing and improved cache performance, the vertex information is stored local to the tetrahedra. We can distribute the vertices in such a way that no tetrahedron ever contains more than one vertex, We give methods to evaluate surface curvatures and principal directions at each vertex, whenever these quantities are defined. Finally, we outline a method for simplifying the surface, that is reducing the vertex count while preserving the geometry. We compare the characteristics of our methods with an 8-cell based method, and show results of surface extractions from CT-scans and MR-scans at full resolution.

The problem of fast rigid matching of 3D curves with subvoxel precision is addressed. More invariant parameters are used, and new hash tables are implemented in order to process larger and more complex sets of data curves. There exists a Bayesian theory of geometric hashing that explains why local minima are not really a problem. The more likely transformation always wins. It is also possible to predict the uncertainty on the match with the help of the Kalman filter, and compare it with real measures.>

The author presents new deformable spline surfaces for segmentation of 3-D medical images. He explores parametric surfaces with two different topologies, planar and cylindrical, that permit segmentation of fine anatomical structures. The surface deformation process is seen as a sequence of least squares approximations of dense data. When the deformation process stops, a smooth differentiable surface results where principle curvatures and directions are measured. An original algorithm is described that extracts lines of extremal curvature on the surface. These lines can be matched from different views with an algorithm. Experimental evidence is presented with real medical images that illustrate these points. The spherical topology for spline surfaces is outlined. Ostrogradsky's formula is used to compute the exact volume bounded by such a surface.>