# 3D Painting on Scanned Surfaces

Maneesh Agrawala <maneesh@pepper.stanford.edu>
Andrew C. Beers <beers@cs.stanford.edu>
Marc Levoy <levoy@cs.stanford.edu>

## 4. Methods

### 4.1 Object--mesh registration

When painting an object with our system, the user places the object on a table in front of the workstation. Before we can paint the mesh, we need to determine a transformation between positions reported by the tracking system in the coordinate space of the physical object and points in the coordinate space of the mesh. We would also like this transformation to ensure that relative orientations of the physical stylus and the virtual paintbrush are the same. We can accomplish this by finding an affine, shear-free transformation between the two coordinate spaces. We use a method developed by Horn [6] for obtaining such a transformation.

Horn's method determines a translation, rotation, and scaling that will align points in one coordinate system to corresponding points in another coordinate system, while minimizing the total distance between the sets of points. The two sets of points may be collected as follows. First, the mouse is used to select a point on the mesh. Then, the stylus is used to point to the corresponding point on the object, thus specifying a correspondence pair. Horn's method requires three or more of these correspondence pairs to determine the registration transformation.

There are several sources of error in collecting the two sets of points including inaccuracies in the tracking system, and inaccuracies in matching the points on the mesh to points on the object. However, as the number of correspondence pairs is increased, small alignment errors in individual pairs are averaged out and the total alignment error decreases. Unfortunately, specifying correspondence pairs is tedious and time consuming.

An algorithm developed by Besl [1] overcomes this problem. Although two sets of points are still required, it is not necessary to specify the point-to-point correspondences between them. We collect a large set of points in tracker space by sampling the position of the stylus while randomly moving it across the surface of the physical object. We use a subset of the mesh vertices as the other set of points. Besl's algorithm determines the best transformation between the two sets of points by iterating on the following steps. First an approximate correspondence between the two sets of points is computed, based on their proximity in space. Then, Horn's method is applied to these pairs of points to align them more closely. On each successive iteration of the algorithm, the proximity-based correspondence improves, which in turn improves the transformation generated by Horn's method.

Besl's algorithm is guaranteed only to find a locally optimal alignment, not a globally optimal one. Therefore, we need to ensure that the sensor samples and the mesh are initially aligned such that the globally optimal solution can be found. The initial alignment is done by hand (see figure 2) and is often a difficult and time consuming process. To speed this process, we have added the ability to easily generate a rough alignment of the sensor samples to the mesh. Once we have collected the large set of sensor samples, we ask the user to specify three or more correspondence pairs as described at the beginning of this section. From these pairs we calculate the scale factor between the sensor samples and the mesh. We also translate the centroid of the sensor correspondence points so that it is aligned with the centroid of the mesh. This produces a rough alignment of the sensor samples to the mesh which can then be hand-refined to produce the initial alignment required for Besl's algorithm.

Our registration scheme is summarized as follows:

• The user collects many samples of the physical object's surface by running the stylus over the object.
• The user selects three or more points on the mesh, and points to their corresponding locations on the physical object with the stylus. These correspondence pairs are used to compute a rough alignment of the sensor samples collected during step 1 to the mesh.
• If necessary, the user makes further hand adjustments to the rough alignment of the sensor samples to the mesh using the mouse to bring them into initial alignment.
• Besl's algorithm is run to refine the alignment of the sensor samples to the mesh.