Game Development Reference
In-Depth Information
of new types of tetrahedrons. In the same manner, Veltkamp uses γ -indicators
(a function to classify triangles vis-à-vis a sphere) and eliminates the triangles by
decreasing γ -indicators. This technique adjusts very well with the differences in den-
sity of scatter plots, but like in Boissonnat's approach, it cannot be used to reconstruct
surfaces containing holes.
14.4.2.2 Distance function methods
A distance function in algorithmic geometry is a function whose absolute value is
the shortest distance between a point in the space and a point of the surface. The
value is negative when the point is inside the volume demarcated by the surface, else
positive. The key element in this type of approach is the calculation of the distance
function.
Hoppe and colleagues (1992) suggest the following: An estimated tangent plane
is associated to each point p i
P . This estimation is obtained by taking k points of
P close to p i and by calculating the best approximating plane in the least-squares
sense. The distance is calculated by determining the tangent plane closest to the point
whose distance from the surface is to be calculated. Thus, the problem lies in finding an
orientation coherent with tangent planes to determine the sign of the distance function.
A Riemann graph 2 is used for this purpose.
How to use a distance function defined in this manner? The method presented by
Hoppe et al. is a cell selection method that uses a distance function: First, a regular
voxel division is carried out. The voxels selected are those with vertices having opposite
signs. Then the surface is obtained by using the Marching Cubes algorithm (refer to
section 14.4.1).
14.4.2.3 Deformation methods
In this case, an initial surface is deformed until it gives a good approximation of the
shape, i.e. till it forms a good approximation of the points of P . These methods are
particularly useful when an initial rough approximation of the surface is available.
We can present three different types of methods here:
A purely geometric method: It involves deforming the entire space (and thus the
object in it) by providing source points and destination points (typically the points
of the surface), and by interpolating between these points;
Physics approach: It is simply a spring-mass approach; the points of the mesh are
connected by springs to the points of P ;
Computer approach: This approach uses a network of neurons (Kohonen feature
map) which is driven to make the surface stick to the control points. However,
connecting the weights to the points of the surface is a difficult task. Being able to
model any type of surface is the important question here.
2 A Riemann graph is a graph whose vertices are the o i centres of the tangent planes defined
as centroids of k points used to estimate them. Two planes are connected if the centre of one
of them is the neighbouring k of the other. A value equal to 1 minus the absolute value of
the scalar product between the perpendiculars to the planes is assigned as weight to the arcs. The
orientation is then determined by propagating a reference orientation by a minimum spanning
tree.

Search Nedrilad ::

Custom Search