Calculating the centroid of a msurface_t

Discuss programming topics for the various GPL'd game engine sources.
Post Reply
mankrip
Posts: 924
Joined: Fri Jul 04, 2008 3:02 am

Calculating the centroid of a msurface_t

Post by mankrip »

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.
Ph'nglui mglw'nafh mankrip Hell's end wgah'nagl fhtagn.
==-=-=-=-=-=-=-=-=-=-==
Dev blog / Twitter / YouTube
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: Calculating the centroid of a msurface_t

Post by Spike »

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.
mankrip
Posts: 924
Joined: Fri Jul 04, 2008 3:02 am

Re: Calculating the centroid of a msurface_t

Post by mankrip »

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.
Ph'nglui mglw'nafh mankrip Hell's end wgah'nagl fhtagn.
==-=-=-=-=-=-=-=-=-=-==
Dev blog / Twitter / YouTube
Post Reply