Page

**1**of**1**### Calculating the centroid of a msurface_t

Posted:

**Sat Oct 22, 2016 9:42 pm**Is there any non-annoying way to do it? I'm trying to calculate the centroid in Mod_LoadFaces.

First, there's no direct list of vertices for msurface_t, so the vertices must be read from the vertices of the surface's edges... which results in duplicated vertices. To work around this I've calculated a unique vertex for the center of each edge.

Now, I've got to calculate the centroid, but all the algorithms I'm finding are for 2D vertices, not for 3D vertices. And I suck at 3D math, so I don't know how to convert those 2D algorithms to 3D.

It's been frustrating.

[edit] Nevermind, my on-surface centroid calculations were correct. The problem was in my on-screen projection, I was transforming the vertex twice.

First, there's no direct list of vertices for msurface_t, so the vertices must be read from the vertices of the surface's edges... which results in duplicated vertices. To work around this I've calculated a unique vertex for the center of each edge.

Now, I've got to calculate the centroid, but all the algorithms I'm finding are for 2D vertices, not for 3D vertices. And I suck at 3D math, so I don't know how to convert those 2D algorithms to 3D.

It's been frustrating.

[edit] Nevermind, my on-surface centroid calculations were correct. The problem was in my on-screen projection, I was transforming the vertex twice.

### Re: Calculating the centroid of a msurface_t

Posted:

**Sun Oct 23, 2016 1:02 am**its easy enough to transform worldspace coords into some other coordinate system, you just need forward/right/up vectors, with some dotproducts to transform to, and multiply-and-add (aka: the transpose) to transform back. these vectors then define your 2d-with-depth axes. the rest is just rewriting your 2d maths to deal with depth. eg adding z*z to the whole x*x+y*y=len*len thing, where without depth the z axis is always 0. Oh, and avoiding the use of cos+sin...

but yeah, its basically all dotproducts. when in doubt, look for a missing dotproduct... or three.

that said, if you just want to find the centre of a 3d polygon/trisoup, one way is to subdivide into triangles, average the three points of each triangle, and then weight(ie: multiply) each center by the area of said triangle. add them together, then divide by the total area and you have the centre.

or something.

here's a dotproduct formula I just pulled off wikipedia

dot(a,b) == vlen(a)*vlen(b)*cos(theta)

where theta is the angle between vectors a and b, which define two sides of the triangle.

rearange that and you have

cos(theta) == dot(a,b)/(vlen(a)*vlen(b))

for completeness hypotenuse*hypotenuse == width*width+height*height+depth*depth of a 3d right-angled triangle, hey look! that's a dotproduct

and for the luls if you didn't realise that, vlen(a) == sqrt(dot(a,a)), which is true whether the vector is 2d or 3d, but I'm sure you already knew that.

you should be able to use high-school maths to figure out the area of the triangle from that, and the only other 3d stuff you need is basic 3d vectors. enjoy.

but yeah, its basically all dotproducts. when in doubt, look for a missing dotproduct... or three.

that said, if you just want to find the centre of a 3d polygon/trisoup, one way is to subdivide into triangles, average the three points of each triangle, and then weight(ie: multiply) each center by the area of said triangle. add them together, then divide by the total area and you have the centre.

or something.

here's a dotproduct formula I just pulled off wikipedia

dot(a,b) == vlen(a)*vlen(b)*cos(theta)

where theta is the angle between vectors a and b, which define two sides of the triangle.

rearange that and you have

cos(theta) == dot(a,b)/(vlen(a)*vlen(b))

for completeness hypotenuse*hypotenuse == width*width+height*height+depth*depth of a 3d right-angled triangle, hey look! that's a dotproduct

and for the luls if you didn't realise that, vlen(a) == sqrt(dot(a,a)), which is true whether the vector is 2d or 3d, but I'm sure you already knew that.

you should be able to use high-school maths to figure out the area of the triangle from that, and the only other 3d stuff you need is basic 3d vectors. enjoy.

### Re: Calculating the centroid of a msurface_t

Posted:

**Sun Oct 23, 2016 2:20 am**Spike wrote:you should be able to use high-school maths to figure out the area of the triangle from that

High school in Brazil is... disappointing, to say the least.

Anyway, I feel that I can simply sum all edge-center vertices and divide by numedges to get the centroid in Mod_LoadFaces. Would this be innacurate? Since all surfaces are convex, I don't see how it wouldn't work.

I'm storing this precomputed centroid in an extra msurface_t field to simplify calculations. Afterwards, I'm using a variation of the particle projection code to get the on-screen position, and now I just have to write the other stuff... once my cat leaves the laptop keyboard.

Of course, I'm forgetting to take model rotation into account during projection. Time for a "//todo" comment.