From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: Simplicial Complexes and Barycentric Coordinates?
Date: 19 Jan 1999 15:42:06 GMT
Newsgroups: sci.math
Keywords: Barycentric coordinates in complexes

In article <77h5if$opd$1@nnrp1.dejanews.com>,
 <richard_harding@playstation.sony.com> wrote:
>I have a triangulated mesh in R3 (3 should be superscripted) space. The mesh
>M is denoted as the tuple M(K,V) where K is the simplicial complex
>representing the mesh face, edge and vertex connectivity and V contains the
>geometric locations of each vertex in the mesh. Assuming there are m vertices
>in the mesh, V would contain m coordinates values.
>
>I need to calculate the barycentric coordinate vector for the point p (on the
>mesh) that is closest to some arbitrary point x (not necessarily on the mesh).
>
>In the literature I'm reading, it suggests that one could project x onto
>each of the faces in M and find the projection with the minimal distance.

Well, each face is contained in some plane, which you may write in the form
ax+by+cz=d where  (a,b,c) is a unit vector. The distance from (x0,y0,z0) to
this plane is then  |ax0+by0+cz0-d|. So yes, you can easily enumerate
all these distances and choose the minimal one. Unfortunately this isn't
quite what you want: what you have calculated for each face is the distance
to the ambient plane; if the perpendicular projection of your initial
point lies somewhere else on the plane rather than in the interior of the
simplex, then you haven't found the closest point.

So what you'd really have to do for each face is
    1. compute the perpendicular projection to the ambient plane
    2. If that point is in the face, stop. Otherwise, for each edge
        2a. compute the perpendicular projection to the ambient line
        2b. If that point is in the edge, stop. Otherwise
    	2c. Compute the distance to each of the two endpoints; choose min.
	2d. This is the distance to that edge
    3. Min over all three edges is the distance to that face
Examine all faces and choose the minimum point-to-face distance.

Note that this isn't the most efficient procedure. For example, an edge where
two or more faces meet would likely be multiply tested as step 2 is performed
for each face.

>I could interpret that to mean that for each face I need to calculate the
>barycentric coordinate of x relative to that face and then take the distance
>between...???? And that's where I get confused. I'm not sure what to calculate
>the distance between when I have the barycentric coordinate of x relative to
>some face. Does this even make sense? Can a point not on a face have a
>barycentric coordinate relative to that face?

No: barycentric coordinates only make sense for point in the affine span of
the vertices. You can compute barycentric coordinates for points in this span
which are outside the face; one or more of them will lie outside the interval
[0,1]. But note that barycentric coordinates are not particularly well
suited to distance computations (unless you incorporate the distances
between the vertices into your calculations).

>Another source of confusion for me has arisen from the definition of the
>topological realization of K.  Is it correct for me to assume that the
>topological realization of K exists in an Rm (m should be superscripted)
>space with each of the m geometric vertices corresponding one-to-one with the
>basis vectors (which would be barycentric?) of that space? For example, if my
>mesh has 4 vertices in it, then the basis vectors in the topological
>realization would be (1,0,0,0), (0,1,0,0), (0,0,1,0) and (0,0,0,1). Thus,
>each barycentric coordinate vector in K would be composed of 4 elements with
>at most 3 of those elements non-zero. There would be 3 non-zero elements for
>a point on a face, 2 for a point on an edge, and 1 for a point on a vertex.
>Is this correct?

Yes, any complex may be embedded into  R^m  in the way you describe. More
appropriately, you can take this embedding as the _definition_ of the 
topology on the complex; then the question is whether or not the given map
into R^3 is a homeomorphism. You need to check that none of the 1-cells
pierce any of the 2-cells, for example, something which will occur with
the correct topology on  K  (and something which is not entirely trivial
to check given the proposed coordinates of the vertices). 
Again I suppose I should point out that the two embeddings into  R^m  and  R^3
give different metrics on this space.

dave

PS -- If this is for a Playstation product, let me just mention that I 
have a 14-year-old son who wouldn't mind collecting free samples...