Determine the orientation of convex/concave hexahedra

algorithmscomputational geometryconvex-geometryorientationpolyhedra

I am writing a code that checks the orientation of a list of vertices (along with face connectivity) describing both convex and concave hexahedra. The face connectivity table stores the list of vertex indices that constitute each face, as described on p.27 of this document. I flag a hexahedron as being positively oriented if all faces are oriented (i.e. clockwise or counter-clockwise) such that the face normal points outward. The direction of the face normal can be determined by applying the right-hand rule in the plane of the face: four fingers curl in the direction of the face vertex orientation, and the thumb points in the direction of the face normal.

I also store the vertex list in the same order as in the linked document. However, the issue I have is that there are certain geometric operations (e.g. reflection about a plane) in my code that flip the orientation of a given hexahedron. I am currently able to check the orientation robustly for convex hexes by computing the centroid and ensuring that the face normals are outward-pointing with respect to it. However, this is not a robust procedure in the case of concave hexes because – (i) the centroid may lie outside the hex, or (ii) the interior side of a face may not be 'visible' to the centroid.

Can anyone suggest a robust procedure for checking the orientation of arbitrary hexahedra? Any advice would be greatly appreciated.

Best Answer

Given a simple flat face $ABCD$ with normal $n$, the signed area $x$ of $ABCD$ wrt $n$ is given by

$$x := \frac 14(\det(\overline{BA}, \overline{BC}, n) + \det(\overline{CB}, \overline{CD}, n) + \det(\overline{DC}, \overline{DA}, n)+ \det(\overline{AD}, \overline{AB}, n)).$$

This value is positive iff the normal satisfies the right-hand rule.

Ordering polygons on a polyhedron

icosahedron-based method for pixelizing the celestial sphere

"What is the best way to pixelize a sphere?" by Max Tegmark

gives a format that appears extremely similar to your proposal:

Tegmark starts with an icosahedron, just as you do, and recursively subdivides it, just as you do. So I find it hard to believe that his method is "computationally and geometrically far more complex than what [you] are proposing" or that it has significantly "greater distortion in either area or geometry".

Given some specified resolution (the same as your depth of recursion) and some point on a sphere, Tegmark's system assigns that point to a "pixel number" (the number indicating what major icosahedral face it is on, and which particular minor sub-triangle on that face that point is in).

quadrilateralized spherical cube

Wikipedia: "quadrilateralized spherical cube"

The all-sky, skyward looking, unfolded cube is reassembled by        
arranging the faces in a sideways T with the bar on the right side:  
                                      0                                  
                          4   3   2   1                                  
                                      5

where square face 0 is centered on the North pole, square face 5 is centered on the South pole, the vernal equinox -- at latitude=0, longitude=0 -- lies at the center of square face 1. Ecliptic longitude increases from face 1 to face 4.

other polyhedra

Tegmark mentions that "it is clearly desirable to use as small faces as possible".

Subdividing each face of a (30-faced) rhombic triacontahedron into two nearly-equilateral isosceles triangles gives the (60-faced) pentakis dodecahedron, as you mentioned, which one might expect to give less error than starting with a (20-faced) icosahedron.

Further subdividing each of those faces into two irregular triangles gives the (120-faced) disdyakis triacontahedron (dual to the truncated icosidodecahedron).

I've been told that the strictly convex polyhedron with the maximum number of identical faces (exactly equal-shaped and exactly equal-area) is that disdyakis triacontahedron.

However, apparently none of these shapes gives any improvement over your icosahedron proposal. Tegmark's code immediately breaks up each equilateral triangle of the 20-sided icosahedron into 6 identical irregular triangles. The resulting 20*6 = 120 identical triangles are the same triangles as the faces of the disdyakis triacontahedron, right?

Ordering polygons on a recursively subdivided polygon

The quadrilateralized spherical cube recursively subdivides each square -- each division of 4 by area adding 2 more bits of localization information -- using a Morton code (Z-order curve).

The Maidenhead Locator System uses a system similar to the Morton code. You might also want to look at the military grid reference system.

Other ways of ordering such subdivided square (i.e., drawing a path that hits the center of each square exactly once) include the Sierpiński curve, the Hilbert curve, the Peano curve, the Moore curve, etc.

There exist other space-filling curves based on recursively subdividing a triangle -- each division of 4 by area adding 2 more bits of localization area. (Do any of them have popular names?)

There are 2 popular ways of subdividing squares and triangles: ( a, b )

"Class I"/"alternate" method: each of the original triangles (or squares) is replaced with n^2 triangles (or squares) that exactly fit inside the original triangle (or square). (n=1 gives the original base shape, n=2 gives a shape with 4 times as many faces). The small triangles have edges (very close to) parallel to the original big triangles.

"Class II"/"triacon" method, employed on almost every major geodesic dome project in the 1950s ( a p. 30 ), each of the original triangles is replaced with 3*n^2 triangles. The small triangles have edges (very close to) right angles to the original big triangles. (Unreliable sources tell me the triacon method can be applied to the cube or rhombic solids, each of the original squares or rhombuses is replaced with 2*n^2 rhombuses). (n=1 converts the icosahedron to the pentakis dodecahedron I mentioned earlier; n=8 converts the icosahedron to an approximation of the Epcot "Spaceship Earth"; n=1 converts the cube into the rhombic dodecahedron, etc.).

EDIT:

The most common application of numbering the sides of a platonic solid is while making dice. One particular way of putting numbers of the sides of an icosahedron is shown on DiceCollector's page, but I don't know if that is particularly "standard". Have you considered asking "What is the proper way to number the sides of a 1d20 die?" or "What is the proper way to number the sides of a 1d120 die?", or both, on the https://rpg.stackexchange.com/ ?

[Math] Determine all convex polyhedra with $6$ faces

At Canonical Polyhedra. you can get the seven hexahedra and their duals. These are your 11, 2, 1, 3, XX, 7, 4. You are missing the (3,3,4,4,4,4) case. Vertices {{-0.930617,0,-1.00},{0.930617,0,-1.00},{-0.57586,-0.997418,0.07181},{0.57586,-0.997418,0.07181},{-0.57586,0.997418,0.07181},{0.57586,0.997418,0.07181},{0,0,1.81162}}, with faces {{1,2,6,5},{1,3,4,2},{1,5,7,3},{2,4,7,6},{3,7,4},{5,6,7}}}

Another view

One way to prove you have all of them is to start with the pyramid / 5-wheel graph. The pentagon with points connected to the center. A polyhedral graph is a planar graph that is 3-connected (no set of 3 vertices that disconnects the graph).

By repeated vertex splitting and merging, all n-faced polyhedra can be derived from the n-faced pyramid. You are missing the shape that merges two neighboring corners of a cube. This is Tutte's Wheel Theorem. Here is how the hexahedral graphs connect.

Canonical Polyhedra has code and pictures.