## object centers

### object centers

Hi there,

I have been using the following method to come up with a (a... not the)
center for an object. Simply add all components of all vertices and divide
the components of the resulting vertice by the total number of vertices.
Then I use this center to move/scale/rotate etc. For cubes and simple
primitives, this works fine but for more detailed objects things start to
get messy. For example, imagine a cube of which one polygon has been divided
into 4 seperate polygons. That side of the cube will then contain more
vertices, so the center moves a little bit to that side. That's not what I
want. My questions are:

1. what types of "centers" are there? (i've read somewhere there are more
types)
2. how can they be computed?
3. what use can they have? (examples)

Futhermore, I imagine the same questions (and their answers) are valid for
polygon centers. Is that correct?

Thanks,
Jeroen

### object centers

> 1. what types of "centers" are there? (i've read somewhere there are more
> types)

Almost an infinity.  An exhaustive list would be impossible.

The classic definition of a "center" would be the center-of-gravity concept
from physics.  The idea is you treat your objects as actual solid objects,
and compute their center-of-gravity, i.e. the point in which their gravity
"appears" to sit, as looked from the outside.

Yours is essentially a fault attempt at computing such a COG.

Quote:> 2. how can they be computed?

Each in a different way.

COG is computed by splitting up objects into smaller ones you know COG
formulae for (typically triangles or tetrahedrons, for which they're
just the average of their vertices), and form a mass-weighted average
of those to find the overall COG.

Quote:> 3. what use can they have? (examples)

Lots.  Essentially, you can't ever apply mechanical simulation to a
solid body without knowing its COG (and some other properties, too,
typically).  If any, only a body's total mass is needed more regularly
for simulation than its COG.
--

Even if all the snow were burnt, ashes would remain.

### object centers

You have to decide which points belong to your object and continue to use
the formula you used. With one exception. It may be necessary to replace sum
with integral. If your object has planes, then every point of a plane
belongs to the object.
Try google for "calculation of center of mass".
To get rid of integral, you may hack it with randomization. You may put
uniformly distributed points on every plane of object. The number of points
in a plain to be proportional to the area of the plane. After that use your
formula with sum.

Quote:> Hi there,

> I have been using the following method to come up with a (a... not the)
> center for an object. Simply add all components of all vertices and divide
> the components of the resulting vertice by the total number of vertices.
> Then I use this center to move/scale/rotate etc. For cubes and simple
> primitives, this works fine but for more detailed objects things start to
> get messy. For example, imagine a cube of which one polygon has been
divided
> into 4 seperate polygons. That side of the cube will then contain more
> vertices, so the center moves a little bit to that side. That's not what I
> want. My questions are:

> 1. what types of "centers" are there? (i've read somewhere there are more
> types)
> 2. how can they be computed?
> 3. what use can they have? (examples)

> Futhermore, I imagine the same questions (and their answers) are valid for
> polygon centers. Is that correct?

> Thanks,
> Jeroen

### object centers

On Sun, 29 Jun 2003 10:29:46 -0700, Ron Levine

> For computational techniques in the special case of polyhedra see B.
>Mirtich, "Fast and Accurate Computation of Polyhedral Mass
>Properties", Journal of Graphics Tools, volume 1, number 2, 1996.

Code and article can be found online.

<http://www.cs.berkeley.edu/~jfc/mirtich/massProps.html>

I expect the article will be difficult for OP to digest. Thus, with
some trepidation, I shall attempt to condense a key insight.

To find the center of mass of a uniform body, we sum the positions of
all the points and divide by the number of points. But that's all the
infinitely many interior points, not just vertices. The infinite sum
is, in fact, an integral; counting the number of points is also.

Integral calculus hands us a tool we quickly take for granted, that
the definite integral of f(t) = F'(t) from a to b is simply the
difference F(b) - F(a). Generalized, this tells us we can integrate
over the interior by looking at the boundary. (Depending on context,
we call this the Fundamental Theorem of Calculus, Green's Theorem,
Gauss' (Divergence) Theorem, or Stokes' Theorem. It's popular!)

For a line segment, we look at its end points. For a polygon, we look
at the bounding line segments. And for a polyhedron, we look at its
polygonal faces.

Mirtich makes this precise, formal, and efficient, simultaneously
computing many different quantities, not just center of mass.

### object centers

Quote:> [...]
> Code and article can be found online.

>   <http://www.cs.berkeley.edu/~jfc/mirtich/massProps.html>

> I expect the article will be difficult for OP to digest. Thus, with
> some trepidation, I shall attempt to condense a key insight.
> [...]
> Mirtich makes this precise, formal, and efficient, simultaneously
> computing many different quantities, not just center of mass.

Dave Eberly revisits the topic in:

http://www.magic-software.com/Documentation/PolyhedralMassProperties.pdf

giving a formulation that is cheaper to compute than Mirtich's.

Christer Ericson
Sony Computer Entertainment, Santa Monica

### object centers

On Mon, 30 Jun 2003 05:38:33 GMT, Christer Ericson

>Dave Eberly revisits the topic in:
>http://www.magic-software.com/Documentation/PolyhedralMassProperties.pdf
>giving a formulation that is cheaper to compute than Mirtich's.

Yes, but Eberly's method only works for triangular faces. Although he
speculates that improvements can be made for general polyhedra, he
does not present any. I doubt it's worth triangulating all the faces
just to use Eberly's code.

### object centers

Quote:> Yes, but Eberly's method only works for triangular faces.

No, it works for general faces.  I parameterize the triangle
faces directly without using projection onto some coordinate
plane.  If the face has more vertices, it can just as easily be
parameterized in the plane of that face.

Quote:> I doubt it's worth triangulating all the faces just to use
> Eberly's code.

This complaint has some merit, but only from an academic
perspective.  In a game environment, the rigid bodies typically
are chosen to be convex polyhedra, so the faces are convex
polygons.  No need to apply a general triangulation algorithm
since triangle fans work just fine (code requires only a few extra
lines).  I doubt that you would encounter faces with so many
vertices that the cost of Mirtich's general approach makes
it a faster option.  For bodies that are not convex you will
also typically find that the model data is used both for display
and for physics.  Since most renderers like being fed triangles,
meshs, so no need to triangulate.

Quote:> Although he speculates that improvements can be made
> for general polyhedra, he does not present any.

And because I do not present any, the idea is useless?

to generalize to the n-th degree just for the sake of publication.
I wrote the document because the result has practical value in
a real programming environment.  If I encounter a need to deal
with the more general case, I will revisit the algorithm at that time.
If you find my approach not sufficient for your programming
needs, sorry I could not help.  The approach certainly meets my
needs.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

### object centers

On Mon, 30 Jun 2003 12:42:37 GMT, "Dave Eberly"

>> Yes, but Eberly's method only works for triangular faces.

>No, it works for general faces.  I parameterize the triangle
>faces directly without using projection onto some coordinate
>plane.  If the face has more vertices, it can just as easily be
>parameterized in the plane of that face.

| A simpler construction is provided here when the polyhedron faces
| are triangles. A consequence of the formulas as derived in this
| document is that they require significantly less computational time
| than does Mirtichs formulas. I suspect that for nontriangular
| faces, Mirtichs formulas are reducible to simpler expressions.

Quote:>> I doubt it's worth triangulating all the faces just to use
>> Eberly's code.

>This complaint has some merit, but only from an academic
>perspective.  In a game environment, the rigid bodies typically
>are chosen to be convex polyhedra, so the faces are convex
>polygons.  No need to apply a general triangulation algorithm
>since triangle fans work just fine (code requires only a few extra
>lines).  I doubt that you would encounter faces with so many
>vertices that the cost of Mirtich's general approach makes
>it a faster option.  For bodies that are not convex you will
>also typically find that the model data is used both for display
>and for physics.  Since most renderers like being fed triangles,
>meshs, so no need to triangulate.

Agreed, triangle meshes predominate. But OP did not restrict to that,
experienced, may not be so for OP.

Quote:>> Although he speculates that improvements can be made
>> for general polyhedra, he does not present any.

>And because I do not present any, the idea is useless?

No, not useless, just unrealized. I did not plan to derive improved
formulae myself, and did not expect that of OP.

>to generalize to the n-th degree just for the sake of publication.
>I wrote the document because the result has practical value in
>a real programming environment.  If I encounter a need to deal
>with the more general case, I will revisit the algorithm at that time.
>If you find my approach not sufficient for your programming
>needs, sorry I could not help.  The approach certainly meets my
>needs.

I have no complaint. In fact, it bothered me that Mirtich thought it
necessary to project the faces. (And for the record, I don't see the
Graphics Gems books nor their successor journal (jgt) as a model of
academic excellence. But they are useful.) Perhaps I triggered this by
saying his code was efficient (his claim, with numbers). It could be
ten times slower and still suffice for OP I wager. What really worries
me here is not the relative merits of your code versus Mirtich, but
the sense that we're killing a fly with a cannon.

To remind us all of the original request, OP was merely trying to find
some kind of "center" for a body, specifically mentioning a cube as a
simple example. :)

| My questions are:
| 1. what types of "centers" are there? (i've read somewhere there
|    are more types)
| 2. how can they be computed?
| 3. what use can they have? (examples)
| Futhermore, I imagine the same questions (and their answers) are
| valid for polygon centers. Is that correct?

### object centers

>  | A simpler construction is provided here when the polyhedron faces
>  | are triangles. A consequence of the formulas as derived in this
>  | document is that they require significantly less computational time
>  | than does Mirtich's formulas. I suspect that for nontriangular
>  | faces, Mirtich's formulas are reducible to simpler expressions.

A paper does not consist solely of its introduction.  Clearly
your background is such that you can see the idea as discussed
in the remainder of the document applies to simple polygon
faces.  But my purpose for the paper is to stress the case of
triangle faces.

You can argue that for simple polygon cases my approach
requires you to construct planar coordinates for each vertex
of the face, whereas Mirtich's construction does not.  I have
not investigated if the coordinate construction plus mass/inertia
calculations are more/less than Mirtich's.  Even if you had the
face triangulation available so that coordinate construction is
not necessary, the operation count is significantly large enough
in Mirtich's approach that you would want to find the
break-even point where the number of triangles finally causes
my method to use more cycles; that point is dependent on
which case you arrive at in Mirtich's formulas.

For rigid bodies, it is quite irrelevant which formula you use
since you compute the mass and inertia tensor (in body
coordinates) just once.  For deformable bodies where you
have to compute the inertia tensor each time step, using
simple polygon faces is problematic.  At one time step
you have a simple polygon face.  At the next time step
the vertices of that face are most likely not coplanar.  What
are you going to do?  No problem when you use triangle
faces.

Quote:> Agreed, triangle meshes predominate. But OP did not restrict to that,
> and otherwise your code needs adaptation which, while simple for the
> experienced, may not be so for OP.

Neither did the OP restrict his problem to rigid bodies.
If his faces are not triangular, he has to modify Mirtich's
code as well.  Maybe the OP has deformable bodies with
trimmed surface patches.  In that case, neither Mirtich's nor
my approach will help.  I am not the one who posted the
reference to Mirtich's paper :)

Quote:> I have no complaint. In fact, it bothered me that Mirtich thought it
> necessary to project the faces.

I have no complaint about Mirtich's paper.  Since the "area of
a 3D polygon" problem is solved by projecting to the appropriate
coordinate plane, it is only natural you would try the same idea
for mass/inertia.  Neither did I like the projection of faces.  That
is why I investigated the alternative.   Regardless, none of this is
rocket science.  The application of Green's theorem is a topic in
an undergraduate calculus class.  I suspect Green himself investigated
all these applications that folks seem to "discover" nowadays (more
appropriate might be to say "rediscover").

Quote:> ...Perhaps I triggered this by saying his code was efficient (his claim,
> with numbers). It could be ten times slower and still suffice for OP
> I wager. What really worries me here is not the relative merits of

Yes, this is how it was triggered, but your response to Christer's
post *was* about the relative merits :)

Quote:>... but the sense that we're killing a fly with a cannon.

> To remind us all of the original request, OP was merely trying to find
> some kind of "center" for a body, specifically mentioning a cube as a
> simple example. :)

The OP did mention some faces of the cube might be subdivided to
have more triangles than other faces.  If he plans on computing the
center of mass using the triangle face information, our discussion is
quite relevant.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

### object centers

On Mon, 30 Jun 2003 22:17:17 GMT, "Dave Eberly"

>I am not the one who posted the reference to Mirtich's paper :)

Ron Levine is the one who brought it up; I merely added a link and
tried to summarize the Stokes/Green/Gauss idea.

But I'm still interested to hear other proposals for "centers", along
with relative merits and when to use them. For example, I think there
is something to be said for choosing the center of the smallest sphere
containing the body.

### object centers

Quote:> But I'm still interested to hear other proposals for "centers", along
> with relative merits and when to use them. For example, I think there
> is something to be said for choosing the center of the smallest sphere
> containing the body.

If one's planning to do scene culling: definitely so.

Or, for that matter, one could look at the "generalized median"
vertex, i.e. the vertex for which the sum of distances (in some
measure, e.g. L_1, L_2, L_infinity, or L_2 squared) to all others is
minimal.  Further along this road lies graph theory county.

Or maybe you could extend that definition to include edges and faces
as eligible candidates (returning their centroid, respectively, if
they win the optimization).  Or just add their centroids into the list
of vertices and use the earlier definition on that extended set.

The list of possibilities is quite endless.

--

Even if all the snow were burnt, ashes would remain.

### object centers

Quote:> > But I'm still interested to hear other proposals for "centers", along
> > with relative merits and when to use them. For example, I think there
> > is something to be said for choosing the center of the smallest sphere
> > containing the body.

> If one's planning to do scene culling: definitely so.

> Or, for that matter, one could look at the "generalized median"
> vertex, i.e. the vertex for which the sum of distances (in some
> measure, e.g. L_1, L_2, L_infinity, or L_2 squared) to all others is
> minimal.  Further along this road lies graph theory county.

> Or maybe you could extend that definition to include edges and faces
> as eligible candidates (returning their centroid, respectively, if
> they win the optimization).  Or just add their centroids into the list
> of vertices and use the earlier definition on that extended set.

> The list of possibilities is quite endless.

Here's the OP again. :-) Interesting reading sofar, in particular the last
two posts in particular are quite interesting for me as they contain the
answers I've been looking for (not to say the rest of the discussion hasn't
been interesting :-)). I liked the idea of the center of the smallest sphere
containing the body as I've been thinking about something simular: using the
center of the bounding box. I have axis aligned boxes computed for each of
my objects and they are automatically updated whenever the object itself is
manipulated (e.g a vertice is moved etc). Would it be a good idea to use the
AABB's, or would it be better to transform the AABB's into orientated
bounding boxes and use those instead, or would it be better to use the
smallest sphere idea, or...? Furthermore, Hans already posted a few more
suggestions and I would definately like to see a few more, just to give me
an idea of the possibilities. I'm not asking for an exhaustive list, just a
few more suggestions. Thanks sofar!

### object centers

> manipulated (e.g a vertice is moved etc). Would it be a good idea to use the
> AABB's, or would it be better to transform the AABB's into orientated
> bounding boxes and use those instead, or would it be better to use the
> smallest sphere idea, or...?

The word "better" is the key to the problem, here.  It should be
obvious it's utterly impossible for anyone but yourself to judge what
is better for your particular application.  Unless you finally come
out and tell us what that application might be, that is.

--

Even if all the snow were burnt, ashes would remain.

### object centers

Well, take the example I mentioned earlier:

* imagine a cube of which one polygon has been divided
*into 4 seperate polygons. That side of the cube will then contain more
*vertices, so the center moves a little bit to that side. That's not what I
*want.

When looking at this cube, I would say that the center of this cube would be
exactly in the middle of the cube because it's still a cube despite of the
fact that one side contains more vertices. But if I use my old way of
computing the center, this center is not exactly in the middle. I still want
the center to be in the middle though and I thought that using the AABB
(which I have anyway) can help me here. The question thus is: can I use
AABB's, OBB's and/or bounding spheres to come up with a center that is
"more" in the "middle".

Quote:> > manipulated (e.g a vertice is moved etc). Would it be a good idea to use
the
> > AABB's, or would it be better to transform the AABB's into orientated
> > bounding boxes and use those instead, or would it be better to use the
> > smallest sphere idea, or...?

> The word "better" is the key to the problem, here.  It should be
> obvious it's utterly impossible for anyone but yourself to judge what
> is better for your particular application.  Unless you finally come
> out and tell us what that application might be, that is.

### object centers

[...]

Quote:> I still want the center to be in the middle

If that isn't a circular definition, I've never seen one... ;-)

Quote:> though and I thought that using the AABB (which I have anyway) can
> help me here. The question thus is: can I use AABB's, OBB's and/or
> bounding spheres to come up with a center that is "more" in the
> "middle".

Yes.  You can use the symmetry center of any of these objects to
define your notion of a "center" of the enclosed objects.  At the very
least, the result you get will not change just because you subdivided
some face, or did similar modifications to the data structures that
don't really modify the shape of the object being modelled.  As the
mathematicians among us would put it: this definition of "center" is
"invariant under such transformations".  This, of course, is a good
thing.

OTOH, if your object is shaped like a rather skinny donut, or a
vehicle tire, a "center" defined this way will lie outside the actual
volume of the object.  This may or may not be usable for your
application (which you _still_ haven't described...)

--

Even if all the snow were burnt, ashes would remain.

Is there a function or macro that would allow me to find either the
center coordinates of an object I've just created or it's bounding
box? I'd like to do things like create a box or a text object then
translate it so it is centered at a particular <x,y,z>.

Also, are there any tools to align multiple objects with one another?