When doing looking for size optimization it's always a good idea to apply some basic algebra and expand expressions and try to factorize them again in a different
way to see if the same result can be expressed in less code (usually at the expense of speed of accuracy). Calculating polygon normals and areas is one of those cases
(say, for a mesh).The triangleLet's define a triangle ABC in 2 or 3D, defined by its three vertices A, B and C. We now want to compute it's normal or area. remember that the area is half the length of it's normal. The classic approach is to compute the edge vectos B-A and C-A, and cross them:normal(A,B,C) = (B-A) x (C-A) and area(A,B,C) = |normal(A,B,C)|/2 Lets expand the cross products, by distribution: (B-A) x (C-A) = BxC - BxA - AxC + AxA Since the cross product is anticommutative, BxA = -AxB. And since AxA = 0 (for it defines a zero area triangle), we have that normal(A,B,C) = AxB + BxC + CxA which is the sum of one cross product per side of the tiangle, involvig the two vertices in the side, in (cyclic) alphabetical order. Not only this is interesting as an alternative way to compute triangle normals without edge vectos, but it also insinuates some sort of generalization to polygons with more sides... |
The quadLet's define a quad ABCD by its four vertices A, B, C and D. We will compute both it's surface area and normal as the sum of the aras and normals of two of the triangles it is composed of. This will work just fine for the surface areas, and for the normals too as long as the two triangles are coplanar and do define a real quad. In case they don't, the addition of the two normals will be nothing but the average normal of the quad. In any case, we have that:normal(A,B,C,D) = normal(A,B,D) + normal(B,C,D) = AxB + BxD + DxA + BxC + CxD + DxB. Again, due to the anticommutativity of the cross product (BxD = -DxB) we get that normal(A,B,C,D) = AxB + BxC + CxD + DxA which is again a cyclic alphabetically sorted summatory of one cross product per side of the polygon. Da-daaaaaa! Of course area(A,B,C,D) = |normal(A,B,C,D)|/2 Interestingly, the normal/area of the quad can be also expressed as the cross of the diagonals: (A-C)x(B-D). Indeed, if you apply distribution and anticommutativity to this cross product, you will see it reduces to the same cyclic summatory of cross products. And beyondIn fact, this is true for n-sided polygons. You can easily demonstrate this yourself by drawing a pentagon, then an hexagon, and generalizing the idea. The result is that for n vertices Vi, i={0, 1, 2, ...n-1} forming a polygon,ConclusionsThis is extremely useful trick for 4 kilobyte demo coding, when you want to avoid doing some vertex substractions in otther to compute your face normals (and vertex normals too, as explaine in the article about clever 3D mesh normalization. The problem this technique might have arises in the cases where the polygons or mesh are big and some of it's vertices are far from the origin. In that case the cross products might be dealing with very parallel vectors and the precision of the result might be compromised. THe regular method of computing normals doesn't suffer from this as vertices get substracte form each other. However, for most use cases, the method presented here works just fine. Promise. |