Re: Mesh Fitting

<artifice_1@xxxxxxxxxxx> wrote in message
news:1138339658.860732.220420@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

> I am curious about your second suggestion though. Please excuse me if
> I'm misunderstanding, but I was under the impression that marching
> cubes was used for generating a hull. Is it actually feasible to
> generate a hull that is, face connectivity wise, identical to an input
> mesh of some sort?

Given a continuous function w = F(x,y,z), the zero-level set is
the set of points for which F(x,y,z) = 0. For most applications,
you expect this equation to implicitly define surfaces, although
in general it is possible to get isolated points or curves. For
example, F(x,y,z) = x^2 + y^2 + z^2 - 1 is a function whose
zero-level set is a sphere centered at the origin and having
radius 1.

Assuming that F(x,y,z) = 0 defines a surface, the problem is
to approximate the surface by a triangle mesh in some region
of space, say in the rectangular solid xmin <= x <= xmax,
ymin <= y <= ymax, zmin <= z <= zmax. One method to
construct such a mesh is to sample the function on the
rectangular solid on a regular lattice of points. Let the
samples be G[i][j][k] = F(x[i],y[j],z[k]), where
0 <= i <= imax, x[i] = xmin + (xmax-xmin)*i/imax
0 <= j <= jmax, y[j] = ymin + (ymax-ymin)*j/jmax
0 <= k <= kmax, z[k] = zmin + (zmax-zmin)*k/kmax
A surface extraction algorithm analyzes the signs of collections
of eight samples: G[i][j][k], G[i+1][j][k], G[i+1][j+1][k],
G[i][j+1][k], G[i][j][k+1],G[i+1][j][k+1], G[i+1][j+1][k+1],
and G[i][j+1][k+1]. For example, suppose G[i][j][k] < 0 and
G[i+1][j][k] > 0; then F(x',y[j],z[k]) = 0 must be zero for
some x' value where x[i] < x' < x[i+1]. Linear interpolation
is typically used to approximate x' by a value
x" = G[i][j][k]/(G[i][j][k] - G[i+1][j][k]. Compute all such
points for this collection of eight samples and "connect the
dots" by triangles. Do this for all collections of eight
samples. The end result is a triangle mesh that approximates
the level surface defined by F(x,y,z) = 0.

Roughly, the larger you choose imax, jmax, and kmax for the
selected rectangular solid, the better the triangle mesh
approximates the true level surface.

How to connect the dots? The Marching Cubes is one famous
(or infamous) algorithm for doing this. It uses a lookup
table for generating the triangles. Works great for
2-manifold surfaces, particularly in the realm of extracting
surfaces from medical images, but has a topological problem
in some cases in correctly selecting triangles in two
adjacent collections of eight samples. To resolve this
problem, you have to be a bit more careful about selecting
the triangles.

Now back to your problem. You already have a triangle
mesh M0, so you can think of this as the *exact* level
surface for the Euclidean distance transform F(x,y,z)
corresponding to the mesh. That is, F(x,y,z) is zero
when (x,y,z) is a point on the mesh. If (x,y,z) is
not on the mesh, F(x,y,z) is chosen to be the distance
from (x,y,z) to the mesh. To get sign changes in F, though,
you need to identify which side of the surface a point is on.
If your original surface is closed, this is easy enough to do
by using the distance if (x,y,z) is in the region bounded by
the surface, but using the negative of the distance if
(x,y,z) is outside the bounded region. Generally, for a
nonintersecting 2-manifold triangle mesh, you can define
a consistent set of triangle normals (the surface is
orientable) and use their direction to apply a sign to the
point-to-triangle distances.

Apply the method I described above to sample F and build
a regular lattice of samples, then extract a triangle mesh
from this, call it M1. The mesh M1 is an approximation
to the mesh M0. The larger you choose imax, jmax, and kmax,
the better M1 approximates M0, but the price you pay for
the better approximation is an increase in the triangle
count for M1. If I understand the problem you posted
originally, you want M1 to be a reasonable approximation
to M0, but with fewer triangles. So you will need to
experiment with various values of imax, jmax, kmax.

> I am looking to preserve more than just pure face count.

Your original post does not appear to have this requirement.
In fact, I do not understand this statement. If you want
M1 to have the same number of faces as M0, and preserve
the mesh topology, choose M1 to be M0 :)

--
Dave Eberly
http://www.geometrictools.com


.

Relevant Pages

  • Re: Finding closest Triangle to a point
    ... a convex mesh is such that all its polygons are contained in the boundary of the convex hull formed by the vertices of the mesh. ... This also simplifies the evaluation of the potential function to a simple distance calculation between points. ... the answer to the question "which is the closest triangle to a point?" ...
    (comp.graphics.algorithms)
  • Re: IntersectInformation Problem
    ... If you have a triangle v0, v1, v2 then u and v are barycentric coordinates ... > two questions - both to do with the age old question of picking a mesh ... > determine whether a specified mesh intersects with this ray or not). ... Then with the second problem I want to do the ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: .x Object Not Showing Light
    ... If the mesh contains a triangle strip then my ... In DirectX the normals are at the ... "ZMan" wrote in message ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: Retrieving faces (verts) from an Mesh.FromFile object
    ... Your assumption about meshes being triangle lists is correct. ... My guess is that the mesh you're loading from the ... > objects Index- and Vertexbuffer and using a for-loop I run through the ...
    (microsoft.public.win32.programmer.directx.graphics)
  • Re: Finding closest Triangle to a point
    ... i am working on a Triangle Mesh, ... To deform this geometry i have to find the closest triangle to a given ... (The Mesh can be called convex, so i thought this should work so far) ...
    (comp.graphics.algorithms)