Given a pair of corresponding sparse polyhedra 
and
, a local surface
parameterisation is used to interpolate a dense set of vertices
on each. The local surface parameterisation is of a single sparse
triangle, and is produced by a parameterisation of the
three surface paths corresponding to its three edges.
If the triangles of the two sparse polyhedra correspond,
then so will the interpolated vertices wtihin them.
The connectivity of these vertices is defined by the
interpolation. The interpolated vertices of this dense
corresponding pair may then be merged
by combining the geometric information from both, with the
connectivity description which is identical in each.
We now describe an algorithm which produces a parameterised path
across the surface of a densely triangulated polygon between two
vertices 
and 
of its sparsely triangulated
approximation. This surface path forms the basis of a local
parameterisation of surface patches (sparse polyhedral triangles).
The algorithm works in a similar fashion to a distance transform
algorithm. We imagine a fire started at ,
which spreads out in all directions along connected triangle edges,
burning continuously until it
reaches . The rate of burn is determined by a metric f.
Only a finite number of points
are considered on the boundary of the fire at any one time.
These are the set of edges 
connected
to the edge 
upon which the current end point 
of the surface path is located, see Figure 2.
Each of these connected
boundary edges has an identified
best point which is a possible new point on the surface path.
The edge 
with the smallest metric value is
selected to burn next, and the best surface path point
upon it becomes the new end of the surface path.
The new edge now ignites all its unburnt neighbours
(at a certain cost C) and attaches
to each the following function value:
where 
is the cost of igniting
from . The function f increases monotonically
along any given surface path. The manner in which the fire burns
(i.e. always consider the edge with minimum cost so far)
guarantees that we find the minimum cost path from to
. The algorithm is made more computationally efficient by
burning two fires simultaneously from to
and from to until the boundaries of the
two fires intersect.
Figure 3: Surfaces are made densely triangulated by the
recursive splitting of triangles into groups of
four sub-triangles.
Figure 2: Surface paths are defined on the dense triangulation
of the surface by the parameterisation of triangle edges.
We now describe the function .
The minimisation of this cost locates the best next point for the
surface path. A point 
on edge can be expressed
parametrically by:
where 
are the vertices on the mesh which
define the edge .
We consider not just the path 
which is a sparse
polyhedral edge, but also the sparse polyhedral triangles connected
to this which have vertices 
and 
,
see Figure 4.
Figure 4: The cost function used to produce surface paths is
defined in terms of a pair of sparse polyhedral triangles
connected along an edge.
We define a point 
which is the projection of
onto the sparse edge ,
again see Figure 4:
Now, we define a series of lengths:
from which the cost function of igniting an edge from
edge may be defined as:
which may be minimised in s to find . The minimisation of
expression 
forces the surface path over hills,
to follow a `straight' line between and . The
minimisation of 
constrains the surface path to
lie within the two triangles defined by 
and 
thus preventing it from
looping back around the entire surface.
The connectivity of and are identical. Therefore,
we can correspond the individual sparse triangles of the polyhedra.
A dense set of corresponded sampling points may then be generated within
each pair of triangles. First, the three surface paths corresponding to
the edges of a sparse triangle are extracted using the method of the
previous section. Next, three new
vertices are defined at the midpoints of these paths. The triangle
is now split into four new sub-triangles,
see Figure 3. This process is applied
to all the triangles of and recursively
to some depth to produce the dense triangulation
and 
.
Now a densely triangulated mean shape may be generated. The recursive
triangle-splitting algorithm is applied to all of the triangles of
and until
. The geometric information from these
is then averaged to produce a pointset 
and this is
combined with the connectivity from either
or to produce a densely
triangulated polyhedron 
. Finally,
is
decimated to the required average number of vertices
to produce our densely
triangulated mean 
, see Figure 5.
Figure 5: The mean of two synthetic shapes. (a) and (b) are
a pair of triangulated surfaces defining an ellipsoid
and a sphere 
. The upper surfaces
are the original dense
triangulation of approximately 800 vertices. The lower surfaces
are the polyhedral approximations to these used for
correspondence by the ICP algorithm, 
and 
. The approximations have
been decimated by 90%. (c) is the dense triangulated mean
shape of these two examples.
