[vtkusers] Centroid of a surface

[Huntsinger, Reid]

The identity that

integral du over V = integral u over boundary(V) 

requires nothing other than some (piecewise) smoothness; to use it you have
to solve for u such that du = the form you want to integrate and that is the
hard part. It can be done easily for simple functions like x and on simple
surfaces like planes, lines, etc. 

On the other hand, you certainly can tetrahedralize the object V, but rather
than just adding up centers of mass you need the volume-weighted average. 

Note also that the center of mass of a tetrahedron is correctly given by the
formula; the "centroid" in the sense of barycenter is the center of mass of
a mass distribution concentrated on the vertices and is not the same as the
center of mass of a uniform mass distribution throughout the tetrahedron. 

Reid Huntsinger



-----Original Message-----
From: Andrew J. Dolgert [mailto:ajd27 at cornell.edu] 
Sent: Tuesday, November 16, 2004 1:50 PM
To: Huntsinger, Reid; Dr Zeto
Cc: vtkusers at vtk.org
Subject: RE: [vtkusers] Centroid of a surface


I don't believe that will work.  The integrating trick you refer to
requires a divergence-free vector.  Here the vector is (x,y,z), whose
divergence is 3.  I think you might get the correct answer for a sphere
or a cube but be only approximate for any other surface.

In order to find the centroid you have to partition the space into
tetrahedra and add up the centroids of each tetrahedron.  Breaking a 3D
simple surface into tets is called "tetrahedralization of the polytope."
I found a reference that looks likely, although I've not read it: B.
Chazelle, "Convex partitions of polyhedra: a lower bound and worst-case
optimal algorithm." SIAM J. Comput., 13:488-507, 1984.

I don't guess it will be easy, but you could make a filter that takes
vtkPolyData with normals on the way in and puts vtkUnstructuredGrid of
tets on the way out, and you'd be a star.

- Drew Dolgert

> -----Original Message-----
> From: vtkusers-bounces at vtk.org 
> [mailto:vtkusers-bounces at vtk.org] On Behalf Of Huntsinger, Reid
> Sent: Tuesday, November 16, 2004 1:05 PM
> To: Dr Zeto
> Cc: vtkusers at vtk.org
> Subject: RE: [vtkusers] Centroid of a surface
> 
> Do you mean the center of mass of the object whose boundary 
> is the surface you have triangulated? I am not sure what the 
> centroid of a _surface_ would be, unless you are thinking of 
> a mass distribution concentrated on the surface.
> 
> To compute the center of mass of the volume, you could use 
> the fact that the volume integral can be written as a surface 
> integral, and the surface integral written as a line 
> integral, and the line integral evaluated as a difference. 
> 
> For example for the x-coordinate of the center of mass, you 
> want to integrate x over the volume, ie the form x dx dy dz, 
> and divide the result by the volume. 
> 
> To get the numerator, you could instead integrate x^2/2 dy dz 
> over the surface, because d(x^2/2 dy dz) = x dx dy dz, and to 
> integrate d(something) over a set V is the same as 
> integrating 'something' over the boundary of V. 
> 
> Now use your triangulation and view this surface integral as 
> a sum over triangles of the integrals over each triangle. If 
> your surface is polyhedral, the triangles are flat and lie in 
> an affine plane described by a linear equation, say ax + by + 
> cz = d. If a = 0 then dy dz = 0 in the plane so this triangle 
> contributes 0 to the sum; otherwise you can write x = py + qz 
> + r (p = -b/a, q = -c/a, r = d/a) and you need to integrate (py + qz +
> r)^2/2 dy dz over the triangle. This is the same as 
> integrating (py + qz +
> r)^3/(3*2*p) dz over the oriented edges of the triangle. 
> 
> Now use the same argument to lower the dimension again: each 
> edge lies in a line described by another linear equation 
> relating y and z; if the coefficient of y is zero then dz = 0 
> on this line and the edge integral is 0, otherwise y = mz + n 
> say and the edge integral is the integral of
> (p(mz+n) + qz + r)^3/(3*2*p) = ((pm+q)z + pn + r)^3/(3*2*p) 
> over the interval from z0 (the z coordinate of the start of 
> the edge) to z1 (the z coordinate of the terminal point of the edge). 
> 
> This integral is ((pm+q)z + pn + r)^4/(4*3*2*p*(pm+q)) 
> evaluated from z1 to z0, from calculus. 
> 
> So for each triangle compute p,q,r; then for each edge 
> compute m,n; then accumulate the difference of the 4th degree 
> polynomial above across endpoints. 
> 
> You get the numerator for the y and z coordinates of the 
> center of mass similarly. You could just permute coordinates 
> and use the above verbatim but perhaps it's more efficient to 
> use d(yx dy dz) = y dx dy dz and follow the above recipe with 
> appropriate changes, since you use the same data p,q,r,m,n, 
> z0, z1 then.  
> 
> The denominator is the volume, and you can follow the same 
> steps (and do the computation simultaneously) with the form 
> dx dy dz. You integrate x dy dz over the boundary, view it as 
> a sum over triangles, get p, q, r, the for each oriented edge 
> get m,n and evaluate the resulting 3rd degree polynomial over 
> the start and end z coordinates of the edge.
> 
> If you mean the center of mass of a uniform mass distribution 
> concentrated on the surface, that would be the sum over triangles T of
> area(T)*centroid(T) divided by the total surface area, ie the 
> sum over T of area(T). [This is different from the center of 
> mass of the volume enclosed, for example for the tetrahedron 
> whose vertices are (0,0,0), (1,0,0),
> (0,1,0), (0,0,1).]   
> 
> Reid Huntsinger
> 
> -----Original Message-----



------------------------------------------------------------------------------
Notice:  This e-mail message, together with any attachments, contains information of Merck & Co., Inc. (One Merck Drive, Whitehouse Station, New Jersey, USA 08889), and/or its affiliates (which may be known outside the United States as Merck Frosst, Merck Sharp & Dohme or MSD and in Japan, as Banyu) that may be confidential, proprietary copyrighted and/or legally privileged. It is intended solely for the use of the individual or entity named on this message.  If you are not the intended recipient, and have received this message in error, please notify us immediately by reply e-mail and then delete it from your system.
------------------------------------------------------------------------------