Probably everyone knows this algorithm, but "the authorities were hiding from me." I found his verbal description on the third page of the search engine in the archive of auto-translations of the English-language forum. It seems to me that its detailed description (and with the code) is worthy of habrosta.
So, for example, you need to generate mobs for a toy and somewhere in the process to weed out those who are not standing on their feet. To do this, you need to find the center of mass of the mob (and this is almost the same as finding its volume) and make sure that it is somewhere above the legs of the mob.
A mob is a polyhedron, for simplicity we believe that a polyhedron consists only of triangles (the algorithm contains the
Gaussian area formula inside, so you can expand it for any polyhedron, but why ...). In addition, the polyhedron should not have self-intersections and limit the closed volume, as befits decent polyhedrons.
(well, like that)A small UPD explaining why on the KDPV the right mob is not OK, but the left OK:
The right picture is not OK because the mob will fall forward, because its center of mass is extended beyond the support area. The support area of a polygon standing on the surface is defined as the minimum polygon inside which all points on the surface are located. In the left case, the area of the support is shifted to the center of mass and more (because dinosaur paws are larger), and in the right picture the area itself is smaller and closer to the tail.
The ratio of the reference area to the center of mass will be something like this:
I'll start right away with the volume search code (Python, input - a list of points and a transition matrix):
some codedef RecSetDirsTriangles(para, Connects, TR): """ , """
The essence of the algorithm is to consider the volumes of figures that form the faces of the polyhedron that “fall” onto the xy plane. To do this, you need to know the projection area of the triangle and the sign with which to add the volume of the figure (truncated prism). In fact, if triangles are ordered in advance, both volume and sign are reduced to a single calculation.
Therefore, the first thing a recursive function collects triangles from is input. Assembles in such a way that when looking “outside” at a polyhedron, the directions of going around the triangles are the same (ideally counterclockwise; if you take the directions clockwise, the result will be correct, but negative - therefore, the volume modulus is given to the return).
This is very simple to achieve - we take some triangle (points a1, a2, a3), look for its neighbors and list two matching vertices in the reverse order (for example, like this: a2, a1, b1).
It turns out something like this:
Now, if we project such a triangle onto the xy plane, then the traversal order for the projection of the “upper” triangle will be the same as the one originally selected, and the traversal order for the projection of the “lower” triangle will change its direction. As a result, it will change the sign and area of this triangle, calculated by the Gauss formula. Here, the “lower” triangle - a conditional concept - means that the volume immediately below it is not included in the volume of the polyhedron. The “lower” triangle of a non-convex polyhedron can be higher than the “upper” one.
After these preliminary steps, in order to calculate the total volume of the polyhedron, you just need to add (taking into account the sign, which is obtained “by itself”) all the volumes of the truncated prisms collected from the faces and projections of these faces on the xy plane. And the volumes of prisms are considered as the product of the area (Gaussian, with a sign) and the arithmetic mean z-coordinates of the vertices of the triangle.
If the polyhedron intersects the xy plane, then when calculating the volume, all signs will cancel each other out and the result remains correct (you just need to take the prism heights without a module).
(somehow the “upper” truncated prism looks like)With the search for the center of mass, everything is approximately the same. Similarly, we need to find the centers of mass for each truncated prism and summarize coordinatewise, multiplying by the volume of the prism (it is assumed that the mass is distributed evenly throughout the volume and one can be replaced by another). To find the center of mass of a truncated prism, it is necessary to calculate the centers of mass of two tetrahedra (+1 function) and one ordinary prism. The algorithm also "does not deteriorate" if the polyhedron crosses the xy plane (and here could be a reproduction of Magritte).
(these two tetrahedra, marked red and red, together with a triangular prism (below the red tetrahedron) form the desired truncated prism. We need to find the centers of mass and volumes of all three figures. The designations roughly correspond to the designations in the code)Code that counts this and that:
a bit more code def RecSetDirsTriangles(para, Connects, TR):
A piece of the algorithm where the directions of the triangles are considered and used to understand the external and internal volume is a very strong move, it can be used a lot as you work with polyhedra. For example, if you need to calculate the direction of the normals "out" - it is enough to know the direction "counterclockwise" for one face - and voila!
(guess the movie!)