Area of polygon
Author
Hi there,
does anyone know the fastest way to calculate the
area of a polygon from 3d vertices ie a quad, for use
in dynamic LOD.
Thanks
Mark.
Hi
divide your polygon to triangles, the area of triangle ABC is :
S = 1/2*a*b*Sin(C)
--Ali Seyedof
http://www.geocities.com/seyedof
divide your polygon to triangles, the area of triangle ABC is :
S = 1/2*a*b*Sin(C)
--Ali Seyedof
http://www.geocities.com/seyedof
Yes, integral form of a parametrized surface in 3d space
first write the triangle as a parametrized plane
x=x0+u*l+v*l1
y=y0+u*m+v*m1
z=z0+u*n+v*n1
where x0,y0,z0, is the first point, (l,m,n) is the vector going
form the first point to the second ,(l1,m1,n1 ) is the second vector going form the first point to the third ,u, v are parameters, write the integral form for a surface in space in which the integrating parameter go from 0 to 1 for both u and v
write the jacobian matrix for the metric switching and remember that the matrix is formed by the derivative of each component respect the parameter u and v , calculate the square of each second order determinant and do the square root of the sum of the tree determinant , calculate the double integral , and you get the surface of a trinangle in space , note that you can calculate in this way the area of a more general surface and even a function where its domain is a function itslef , but if you don''t want to deal with advanced math here is the c funtion i did for my engine
float TriangleArea ( fVect P0,fVect P1,fVect P2 )
{
fVect N,N1;
qVect P;
N[0]=P1[0]-P0[0];
N[1]=P1[1]-P0[1];
N[2]=P1[2]-P0[2];
N1[0]=P2[0]-P0[0];
N1[1]=P2[1]-P0[1];
N1[2]=P2[2]-P0[2];
P[0]=SQR( N[0] )+SQR( N[1] )+SQR( N[2] );
P[1]=SQR( N1[0] )+SQR( N1[1] )+SQR( N1[2] );
P[2]=N[0]*N1[0]+N[1]*N1[1]+N[2]*N1[2];
P[3]=(float)sqrt(P[0]*P[1]-P[2]*P[2]);
return ( P[3] );
}
first write the triangle as a parametrized plane
x=x0+u*l+v*l1
y=y0+u*m+v*m1
z=z0+u*n+v*n1
where x0,y0,z0, is the first point, (l,m,n) is the vector going
form the first point to the second ,(l1,m1,n1 ) is the second vector going form the first point to the third ,u, v are parameters, write the integral form for a surface in space in which the integrating parameter go from 0 to 1 for both u and v
write the jacobian matrix for the metric switching and remember that the matrix is formed by the derivative of each component respect the parameter u and v , calculate the square of each second order determinant and do the square root of the sum of the tree determinant , calculate the double integral , and you get the surface of a trinangle in space , note that you can calculate in this way the area of a more general surface and even a function where its domain is a function itslef , but if you don''t want to deal with advanced math here is the c funtion i did for my engine
float TriangleArea ( fVect P0,fVect P1,fVect P2 )
{
fVect N,N1;
qVect P;
N[0]=P1[0]-P0[0];
N[1]=P1[1]-P0[1];
N[2]=P1[2]-P0[2];
N1[0]=P2[0]-P0[0];
N1[1]=P2[1]-P0[1];
N1[2]=P2[2]-P0[2];
P[0]=SQR( N[0] )+SQR( N[1] )+SQR( N[2] );
P[1]=SQR( N1[0] )+SQR( N1[1] )+SQR( N1[2] );
P[2]=N[0]*N1[0]+N[1]*N1[1]+N[2]*N1[2];
P[3]=(float)sqrt(P[0]*P[1]-P[2]*P[2]);
return ( P[3] );
}
quote:Original post by Seyedof
Hi
divide your polygon to triangles, the area of triangle ABC is :
S = 1/2*a*b*Sin(C)
Almost. Just slight confusion. Don't you mean sin(theta), where theta is the angle between edges A and B? I think so. The corrected equation is:
S = 1/2*A*B*sin(theta)
Problem is, how do you get theta? Dot product to get cos(theta) then do an acos to get theta or use a trig relationship to get sin(theta) directly? Why not just use the cross product instead? Let the triangle be defined by points P1, P2, and P3:
Normal_Vec = (P3 - P1) cross (P2 - P1)
*DO NOT* make this a unit vector!
Then the area S is calculated by:
S = sqrt(Normal_Vec.x2 + Normal_Vec.y2 + Normal_Vec.z2) You could then divide Normal_Vec by S to make Normal_Vec a unit vector.
So, really, you can automatically get the area of the triangle in the process of computing per-triangle unit normal vectors!
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Edited by - grhodes_at_work on October 17, 2001 10:59:58 AM
quote:Original post by v71
Yes, integral form of a parametrized surface in 3d space
first write the triangle as a parametrized plane
x=x0+u*l+v*l1
y=y0+u*m+v*m1
z=z0+u*n+v*n1
....
That analysis may be a bit of overkill. Why not just use the cross product rule I mentioned in my other reply without bothering with the calculus at all? For a flat triangle it makes perfect sense geometrically without thinking about integrals.
quote:Original post by v71
P[0]=SQR( N[0] )+SQR( N[1] )+SQR( N[2] );
P[1]=SQR( N1[0] )+SQR( N1[1] )+SQR( N1[2] );
Okay, so P[0] is the square of the length of edge 1 and P[1] is the square of the length of edge 2.
quote:Original post by v71
P[2]=N[0]*N1[0]+N[1]*N1[1]+N[2]*N1[2];
P[2] is the dot product of edge 1 onto edge 2, or the length of the projection of edge 1 onto edge 2.
quote:Original post by v71
P[3]=(float)sqrt(P[0]*P[1]-P[2]*P[2]);
You need to multiply P[3] by 0.5 to get the area.
Effectively, you''re getting the magnitude of the cross product here, just using a different approach than I would use. Nothing wrong with that,
. Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Nope, do the calculus and you''ll see i''ve just done it again
probably you are thinking about the already differentiated function that caomes with 0.5 ahead.
probably you are thinking about the already differentiated function that caomes with 0.5 ahead.
quote:Original post by v71
Nope, do the calculus and you''ll see i''ve just done it again
probably you are thinking about the already differentiated function that caomes with 0.5 ahead.
Its entirely possible I''ve missed something here. I didn''t copy your function into a compiler and build it, but I did implement your calculations in an Excel spreadsheet. Try your function on a triangle defined by points P0 = (0,0,0), P1 = (1,0,0), P2 = (1,1,0). That triangle has half the area of the unit square, or an area of 0.5. When I run your calcs without the 0.5 multiplier, I get an area of 1, which is twice the correct area. I varied the position of the points a bit, e.g., change P1 to (1, -.25, 0), and in every case your function gave twice the correct area.... What am I missing? You do mean that SQR(N[0]) = N[0] * N[0], don''t you?
I''ve double checked my spreadsheet against your formulas and I''m fairly sure I''m doing exactly what your function does.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Graham is correct, the method v71 presented should be adjusted by a factor 0.5, after which there''s no doubt the two approaches are identical.
As Graham stated, the area of a triangle ABC is half the magnitude of of the cross product of the edges AB and AC. Or expressed differently: Area(ABC)/2 = sqrt(x), where x = Dot(Cross(AB,AC), Cross(AB,AC)).
This expression for x can be rewritten using Lagrange''s identity resulting in:
x = Dot(Cross(AB,AC), Cross(AB,AC))
= Dot(AB,AB)*Dot(AC,AC) - Dot(AB,AC)^2
which is exactly what v71 presented (except for a missing division by two at the end).
Christer Ericson
Sony Computer Entertainment, Santa Monica
As Graham stated, the area of a triangle ABC is half the magnitude of of the cross product of the edges AB and AC. Or expressed differently: Area(ABC)/2 = sqrt(x), where x = Dot(Cross(AB,AC), Cross(AB,AC)).
This expression for x can be rewritten using Lagrange''s identity resulting in:
x = Dot(Cross(AB,AC), Cross(AB,AC))
= Dot(AB,AB)*Dot(AC,AC) - Dot(AB,AC)^2
which is exactly what v71 presented (except for a missing division by two at the end).
Christer Ericson
Sony Computer Entertainment, Santa Monica
Guys, maybe i''m getting dumber as i get older , but i have done it once again and 0.5 doesn''t come from nowhere using an integral form.
I suggest you look for an error in your integration. The error must be there. Perhaps you''ve actually done the integration for a parallelogram instead of half the parallelogram?
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
