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>, 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...