Calculating the centroid of a msurface_t
Moderator: InsideQC Admins
3 posts
• Page 1 of 1
Calculating the centroid of a msurface_t
Is there any nonannoying 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 onsurface centroid calculations were correct. The problem was in my onscreen 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 onsurface centroid calculations were correct. The problem was in my onscreen projection, I was transforming the vertex twice.

mankrip  Posts: 915
 Joined: Fri Jul 04, 2008 3:02 am
Re: Calculating the centroid of a msurface_t
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 multiplyandadd (aka: the transpose) to transform back. these vectors then define your 2dwithdepth 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 rightangled 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 highschool 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 rightangled 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 highschool maths to figure out the area of the triangle from that, and the only other 3d stuff you need is basic 3d vectors. enjoy.
 Spike
 Posts: 2905
 Joined: Fri Nov 05, 2004 3:12 am
 Location: UK
Re: Calculating the centroid of a msurface_t
Spike wrote:you should be able to use highschool 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 edgecenter 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 onscreen 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.

mankrip  Posts: 915
 Joined: Fri Jul 04, 2008 3:02 am
3 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest