Jump to content


Photo

Center Of Mass Of A 3d Model


  • Please log in to reply
16 replies to this topic

#1 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 13 September 2008 - 03:24 AM

Question at end of post.

I'm working on a model editor and I have a set center function to reset the center of a model. I can do this a few ways which I have implemented.

method 1) add vertices and average them and move the model

pseudocode
for each point
dx += point.x
dy += point.y
dz += point.z
count ++

dx/=count
dy/=count
dz/=count

for each point
point.x-=dx
point.y-=dy
point.z-=dz

the problem: If the model has many points in one area, the deviation favors that area. Which is not always good because some models have many many points like at the tip of a gun or the cone of a ship.

method 2) find min max of vertices, average the min max into a deviation and moved the model
for each point
mindx = min(point.x,mindx)
maxdx = max(point.x,maxdx)
same for y and z
count ++

dx = (mindx+maxdx)/2
same for dy,dz;
for each point
point.x-=dx
same for y and z

That works OK.



QUESTION
For my 3rd method, I would really like to center the model on its estimated center mass.

I have a series of 3 points defining the planes/faces. I figure I could plug either the plane area or perimeter into the deviation calculation. That way many points defining a tiny area would not affect the calculation that much. But I cant figure out the right math for this.

Edited by icuurd12b42, 24 September 2008 - 11:52 PM.

  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#2 xshortguy

xshortguy

    GMC Member

  • Global Moderators
  • 4355 posts
  • Version:GM:Studio

Posted 13 September 2008 - 03:58 AM

Can you determine the surface areas of each face? If so, you may be able to add up the surface areas divided by the center of that surface. Then sum up these points in relation to the model using the center of mass formula.

Let's start with the basic center of mass formula:
r_com = sum( m_i * r_i, i = 0..N) / sum( m_i, i = 0..N ); r_i = (x_i, y_i, z_i).

We'll let m_i be the sum of each vertex divided by the area of the face and let r_i be the center of each face. This should give a fair approximation.

Edited by xshortguy, 13 September 2008 - 04:01 AM.

  • 0
Check out my Profile's About Me Page for some useful links.

#3 Yourself

Yourself

    The Ultimate Pronoun

  • GMC Elder
  • 7352 posts
  • Version:Unknown

Posted 13 September 2008 - 05:07 AM

Can you determine the surface areas of each face?


Well, one would assume that we'd want to count the inside of the model into the mass calculation as well, in which case you want to find the volume of the model. This actually isn't too difficult to compute assuming that the model is closed (no holes; otherwise it wouldn't really have a well-defined volume; in which case you'll have to go with xshortguy's method) and that it's simple (in the mathematical sense; that means it doesn't intersect with itself). Each triangular face contributes a tetrahedron's worth of volume to the whole model. To find this volume given the three vertices of the face v1, v2, and v3, you need only compute v1·(v2×v3)/6. The following is very important. The vertices of every face must be oriented the same way. This means that if you look at a face from the outside of a model, its vertices should be oriented in a clockwise fashion (counterclockwise is valid too as long as you're consistent).

So, now we essentially have a way to compute a weighting factor for every face in the model. The coordinates we have to weight by this are the centroids of each tetrahedron which is given by: (v1 + v2 + v3)/4. This is because one of the vertices of every tetrahedron is the origin so it's 0, so there's no reason to include it here. So, the centroid of the model is given by the following:

Sum[v1·(v2×v3)*(v1 + v2 + v3)/4]/Sum[v1·(v2×v3)]

The sum is performed over each face. Also, the factor of 6 in the volume is left out because it cancels out because of the division. So, loop over each face, compute the volume contribution and add that onto a total volume counter and also multiply it by that average position (you can move the division by 4 outside of the sum to make the loop faster; that way only one division needs to be performed instead of one for each face) of the tetrahedron (i.e. multiply it by the sum of the vertices). Then, outside of the loop, divide by the total volume times 4 (assuming you moved that division by 4 outside of the loop). You now have the centroid assuming constant density.
  • 0

#4 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 13 September 2008 - 08:30 AM

when you say v1, do I have to use the entire vertex, or can I get away with using x,y,z values repectively so to only move on the specified axis?

Can you verify this representation of your equation? I don't think I have it figured out.

This is for my center on the x axis based on mass.
var dx,i;
			dx = 0;
			i = 0;
			var v1,v2,v3,sum1,sum2;
			sum1 = 0;
			sum2 = 0;
			if(opt = 120 or opt = 123)
			{
			repeat(ds_list_size(m_x)/3)
			{
				v1 = ds_list_find_value(m_x,i);
				v2 = ds_list_find_value(m_x,i+1);
				v3 = ds_list_find_value(m_x,i+2)
				sum1 += v1*(v2*v3)*(v1 + v2 + v3)/4;
				sum2 += v1*(v2*v3)
				 i+=3;
			}
			if(sum2) dx=sum1/sum2;
			}

Edited by icuurd12b42, 13 September 2008 - 08:32 AM.

  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#5 Yourself

Yourself

    The Ultimate Pronoun

  • GMC Elder
  • 7352 posts
  • Version:Unknown

Posted 13 September 2008 - 08:42 AM

when you say v1, do I have to use the entire vertex, or can I get away with using x,y,z values repectively so to only move on the specified axis?


I bolded the variable names because they're all vectors. I guess that may not have been obvious even with the different multiplication operators. The product of the three vectors is a triple scalar product. It's the dot product with the cross product (and also the determinant of the matrix of these vectors). It's equal to this:

x1*(y2*z3 - y3*z2) + y1*(z2*x3 - z3*x2) + z1*(x2*y3 - x3*y2)
  • 0

#6 Toni12

Toni12

    Designer

  • New Member
  • 851 posts
  • Version:GM8

Posted 13 September 2008 - 04:55 PM

Posted Image

p = point
cp = center point

In Figure 1:

Cube: p1, p2, p3, p4, p5, p6, p7, p8

(p1.x + p7.x)/2 = cp.x
(p1.y + p7.y)/2 = cp.y
(p1.z + p7.z)/2 = cp.z

It quick and dirty but it works.

Future Reference - Midpoint Formula:
mp = midpoint

(X1 + X2)/2 = mpX
(Y1 + Y2)/2 = mpY
(Z1 + Z2)/2 = mpZ
  • 0

#7 Yourself

Yourself

    The Ultimate Pronoun

  • GMC Elder
  • 7352 posts
  • Version:Unknown

Posted 13 September 2008 - 05:09 PM

His model isn't a cube and simply averaging point locations is exactly what he said he didn't want (since it doesn't find the actually centroid of a model since its highly influenced by what parts of the model contain more detail). Please make it look like you read more than just the topic title when you try to answer a question.
  • 0

#8 mechanikos

mechanikos

    GMC Member

  • New Member
  • 453 posts

Posted 13 September 2008 - 06:03 PM

This is because one of the vertices of every tetrahedron is the origin


You are assuming the model is.. what's the word, convex? So that all the tetrahedrons are entirely contained inside the model.
  • 0

#9 Yourself

Yourself

    The Ultimate Pronoun

  • GMC Elder
  • 7352 posts
  • Version:Unknown

Posted 13 September 2008 - 06:28 PM

You are assuming the model is.. what's the word, convex? So that all the tetrahedrons are entirely contained inside the model.


No, I'm not. I assume that the model is closed and simple. Any tetrahedrons outside the model will have their area computed to be negative. They'll subtract off their contributions. The origin of the system can be anywhere as well. It doesn't have to be inside the model.
  • 0

#10 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 13 September 2008 - 10:47 PM

OK, this got a little too complex with the 3d vectors (points) and all for my little non mathematical head.

Unless someone is willing to translate that to code I can use (I'm not asking for it, but if you are interested in the brain exercise, you're welcome).

Meanwhile, I decide to use a simpler approach (I can code), derived from xshortguy.

I have a 3d point distance function.


point_distance_3d(x,y,z,x,y,z)

I use is to calculate the perimeter of a face, simply

plane_perimeter(x,y,z,x,y,z,x,y,z)

returns point_dstance(v1,v2) + point_dstance(v2,v3) + point_dstance(v3,v1)

now my loop is like so;

example for x deviation
var dx,dy,dz;
			dx = 0;
			dy = 0;
			dz = 0;
			ct = 0;
			i = 0;
			sum1 = 0;
			sum2 = 0;
			if(opt = 120 or opt = 123)
			{
			repeat(ds_list_size(m_x)/3)
			{
				
				p= plane_perimeter(
				ds_list_find_value(m_x,i),ds_list_find_value(m_y,i),ds_list_find_value(m_z,i),
				ds_list_find_value(m_x,i+1),ds_list_find_value(m_y,i+1),ds_list_find_value(m_z,i+1),
				ds_list_find_value(m_x,i+2),ds_list_find_value(m_y,i+2),ds_list_find_value(m_z,i+2)) 
				ct += p;
				dx+=p * (((ds_list_find_value(m_x,i) + ds_list_find_value(m_x,i+1)+ ds_list_find_value(m_x,i+2))/3))
				
				i+=3;
			}
			if (ct) dx/=ct;
.
.
.
			i = 0;
			repeat(ds_list_size(m_x))
			{
				ds_list_replace(m_x,i,ds_list_find_value(m_x,i)-dx)
				i+=1
			}

I dont know if I was using area instead of perimeter if the function would be more accurate. I assume area or perimeter would give me the same ratio anyway.

So, I get the perimeter, multiply by the center position (on that axis) of the triangle (x1+x2+x3)/3.

Assume I was using area, for a second, the code would act like it's getting x for each "pixel" of the face, add each pixel deviation to the model sum (approx). Then the whole thing is averaged using the model total "fake pixel" count.

Looks like it does the job fairly well in most cases (not all). If other cases, I have the 2 other moves + other manual move the user can use.


Soon I'll post the gmk in the WIP. If anyone would like to tweak this for me then, you'll be welcome.

Edited by icuurd12b42, 13 September 2008 - 10:48 PM.

  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#11 xshortguy

xshortguy

    GMC Member

  • Global Moderators
  • 4355 posts
  • Version:GM:Studio

Posted 13 September 2008 - 11:10 PM

Perimeter and area usually won't give you the same ratio. This can be easily illustrated by comparing a 4x1 rectangle by a 2x2 rectangle. Both have an area of 4, but the the perimeters differ.
  • 0
Check out my Profile's About Me Page for some useful links.

#12 Yourself

Yourself

    The Ultimate Pronoun

  • GMC Elder
  • 7352 posts
  • Version:Unknown

Posted 13 September 2008 - 11:21 PM

OK, this got a little too complex with the 3d vectors (points) and all for my little non mathematical head.


I gave you the formula for the volume above:

x1*(y2*z3 - y3*z2) + y1*(z2*x3 - z3*x2) + z1*(x2*y3 - x3*y2)


var cx, cy, cz, volume, v, i, x1, y1, z1, x2, y2, z2, x3, y3, z3;
volume = 0;
cx = 0; cy = 0; cz = 0;
// Assuming vertices are in vertX[i], vertY[i], and vertZ[i]
// and faces are faces[i, j] where the first index indicates the 
// face and the second index indicates the vertex of that face
// The value in the faces array is an index into the vertex array
i = 0;
repeat (numFaces) {
	x1 = vertX[faces[i, 0]]; y1 = vertY[faces[i, 0]]; z1 = vertZ[faces[i, 0]];
	x2 = vertX[faces[i, 1]]; y2 = vertY[faces[i, 1]]; z2 = vertZ[faces[i, 1]];
	x3 = vertX[faces[i, 2]]; y3 = vertY[faces[i, 2]]; z3 = vertZ[faces[i, 2]];
	v = x1*(y2*z3 - y3*z2) + y1*(z2*x3 - z3*x2) + z1*(x2*y3 - x3*y2);
	volume += v;
	cx += (x1 + x2 + x3)*v;
	cy += (y1 + y2 + y3)*v;
	cz += (z1 + z2 + z3)*v;
	i += 1;
}
// Set centroid coordinates to their final value
cx /= 4 * volume;
cy /= 4 * volume;
cz /= 4 * volume;
// And, just in case you want to know the total volume of the model:
volume /= 6;

Remember that the vertices of each face must be oriented in the same way (one way to see if they are is to turn on back face culling; if the model appears normally then they're all oriented properly--the model could also appear inside-out which would also be a valid orientation).
  • 0

#13 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 14 September 2008 - 10:02 AM

OK, Thanks yourself for going the extra mile. I'll plug this in tomorow or monday. Sorry for missing the converted function. I thought that equation was the exploded form of v1+v2+v3. So I still had no clue how to plug it in.

I cant guaranty all the models will have faces oriented the same way. I trust the model will be valid as I trust to model editor used to create it and export it to obj made sure.

But the result of flipping axis may turn all the points inside out (I have a fix button for that). They would still be all oriented the same way.

What would happen if some faces are inward and some outward? Would it cause the model to be moved 10000 units away?


OK xshortguy. I only did a quick estimation for the area vs perimeter... I just did not want to go into the trouble of adding an extra step to find the area. There must be a function to calculate an area of a triangle without having to figure out the angles... Simply using the 3 distance. I did not find any (yes I found (1/2)*(b*h) but could not figure what b and h are... which vector lenghts). And this stuff is 30 years stale in my head.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#14 xshortguy

xshortguy

    GMC Member

  • Global Moderators
  • 4355 posts
  • Version:GM:Studio

Posted 14 September 2008 - 12:02 PM

There must be a function to calculate an area of a triangle without having to figure out the angles... Simply using the 3 distance.


Heron's Formula.

A = sqrt(s * (s - a) * (s - b) * (s - c) ), where a, b, c are the lengths of each side and s is the semi-perimeter, s = (a + b + c) / 2.

Edited by xshortguy, 14 September 2008 - 12:03 PM.

  • 0
Check out my Profile's About Me Page for some useful links.

#15 Toni12

Toni12

    Designer

  • New Member
  • 851 posts
  • Version:GM8

Posted 14 September 2008 - 04:36 PM

You could use my box method in combination with a bounding box of a model. Yet, if you want it to be at the center of gravity you should implement a physics engine. Otherwise a normal origin point should suffice for most games.
  • 0

#16 Yourself

Yourself

    The Ultimate Pronoun

  • GMC Elder
  • 7352 posts
  • Version:Unknown

Posted 14 September 2008 - 06:04 PM

Heron's Formula.


Or you could just take the magnitude of the cross product of two edge vectors of the face and divide it by 2. That is you can find the area of the face when you're looking for its normal vector.

What would happen if some faces are inward and some outward? Would it cause the model to be moved 10000 units away?


I don't think anything quite that severe would happen, but the result you'd get would definitely be wrong. One way to check orientation (from a program) is to start from some face and assume it's oriented properly (no loss of generality here). Then find its three neighboring faces (those faces that share an edge with it). These faces are oriented properly if the shared edges are directed opposite one another (so, say, face 1 has vertices (1, 2, 3) in that order; face 2 is oriented properly if it has vertices (3, 2, 4) or something similar--it has to have a pair of the same vertices as the first face, but they must appear in reversed order).

You could use my box method in combination with a bounding box of a model. Yet, if you want it to be at the center of gravity you should implement a physics engine.


Do you even read what others have done in this topic? I've provided a method for finding exactly the center of mass and I didn't need to implement a physics engine to do it. He wanted the center of mass, I gave him the center of mass. Why keep trying to convince him that he wants something else? Besides, the second method he proposed in the original post is a bounding box center and he said that worked okay, but he still wanted the center of mass.
  • 0

#17 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 15 September 2008 - 12:48 AM

OK. It's all in!!! Both yourself volume version and xshortguy's area version (yes better than perimiter). I just could not decide which had the better outcome.

Both very similar results from the models I have tired. The exception is this particular model where yourself's code simply blows the ship somewhere off to lala land (Got my previous question answered here). So the area version wins in this case.

I now have 16 move center (4 methods * (3 axis + all axis) and 6 move aling and 6 move relative methods. So if one of the codes looses the model it's just a matter of clicking one of the other buttons.

It's soo cool. Thank you both.


Here, I would appreciate a code review to see if I had a brain fart somewhere
var dx,dy,dz;
			dx = 0;
			dy = 0;
			dz = 0;
			ct = 0;
			i = 0;
			var volume, i, x1, y1, z1, x2, y2, z2, x3, y3, z3;
			volume = 0;
			if(opt <= 123)
			{
				repeat(ds_list_size(m_x)/3)
				{
					x1 = ds_list_find_value(m_x,i); y1 = ds_list_find_value(m_y,i); z1 = ds_list_find_value(m_z,i);
					x2 = ds_list_find_value(m_x,i+1); y2 = ds_list_find_value(m_y,i+1); z2 = ds_list_find_value(m_z,i+1);
					x3 = ds_list_find_value(m_x,i+2); y3 = ds_list_find_value(m_y,i+2); z3 = ds_list_find_value(m_z,i+2);

					p= plane_area(
						x1,y1,z1,
						x2,y2,z2,
						x3,y3,z3) 
					ct += p;
					dx+=p * (((x1 + x2 + x3)/3))
					dy+=p * (((y1 + y2 + y3)/3))
					dz+=p * (((z1 + z2 + z3)/3))
					i+=3;
				}
				if (ct) dx/=ct;
				if (ct) dy/=ct;
				if (ct) dz/=ct;
			}
			else if(opt <= 133)
			{
				repeat(ds_list_size(m_x)/3)
				{
					x1 = ds_list_find_value(m_x,i); y1 = ds_list_find_value(m_y,i); z1 = ds_list_find_value(m_z,i);
					x2 = ds_list_find_value(m_x,i+1); y2 = ds_list_find_value(m_y,i+1); z2 = ds_list_find_value(m_z,i+1);
					x3 = ds_list_find_value(m_x,i+2); y3 = ds_list_find_value(m_y,i+2); z3 = ds_list_find_value(m_z,i+2);
					v = x1*(y2*z3 - y3*z2) + y1*(z2*x3 - z3*x2) + z1*(x2*y3 - x3*y2);
					volume += v;
					dx += (x1 + x2 + x3)*v;
					dy += (y1 + y2 + y3)*v;
					dz += (z1 + z2 + z3)*v;
					i += 3;
				}
				// Set centroid coordinates to their final value
				if(volume) dx /= 4 * volume;
				if(volume) dy /= 4 * volume;
				if(volume) dz /= 4 * volume;
			}
			
			if(opt = 120 or opt = 130)
			{
				dy = 0; dz = 0;
			}
			if(opt = 121 or opt = 131)
			{
				dx = 0; dz = 0;
			}
			if(opt = 122 or opt = 132)
			{
				dy = 0; dx = 0;
			}
			i = 0;
			repeat(ds_list_size(m_x))
			{
				ds_list_replace(m_x,i,ds_list_find_value(m_x,i)-dx)
				ds_list_replace(m_y,i,ds_list_find_value(m_y,i)-dy)
				ds_list_replace(m_z,i,ds_list_find_value(m_z,i)-dz)
				i+=1
			}


The result:
http://gmc.yoyogames...howtopic=397461

Edited by icuurd12b42, 15 September 2008 - 11:24 AM.

  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button