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