I am currently reading Christer Ericson's Real-Time Collision Detection Book. The topic I'm particularly interested in, is the chapter about Discrete-orientation Polytopes (k-DOPs). In his words "...$k$-DOPs are convex polytopes, almost identical to the slab-based volumes except that the normals are defined as a fixed set of axes shared among all $k$-DOP bounding volumes. The normal components are typically limited to the set $\{−1, 0, 1\}$, and the normals are not normalized... Only the min-max intervals for each axis must be stored." So for example a Cube of side-length $2$ can be written as a $6$-DOP with face-normals $[(1,0,0),(0,1,0),(0,0,1)]$ and the min intervals would be $[-1,-1,-1]$ and the max intervals $[1,1,1]$. Another example would be an octahedron ($8$-DOP) with face-normals $[(1,1,1),(1,1,-1),(1,-1,1),(-1,1,1)]$.
Given the face-normals and the min-max intervals, I'm interested in calculating the vertices of the polytope. My first intuition was to calculate the linear equation system of every combination of $3\times 3$ Matrices (face-normals) with every combination of $3\times1$ vectors (corresponding min-max values). This works very well for the $6$-DOP example, since there is only one $3\times3$ Matrix and exactly $8$ combinations of vectors, leading to exactly $8$ linear equation systems. The result of these equations, are the vertices of the cube. In other words, I just calculate the intersections of all groups of three faces that are not parallel to each other. However, this approach fails for higher values of $k$, like the $8$-DOP, since there are intersections out of the $k$-DOP and therefore far too many Vertices calculated.
I am looking for a simple algorithm, to calculate the vertices of every given $k$-DOP. The algorithm can be a brute-force approach, as computation time is not relevant to me. What is important to me is an approach that is easy to understand. In another MathOverflow Q&A, a fast approach was suggested. As embarrassing as it is, the suggested approach is currently way over my head. In his question the author said he used a "Brute force method. Intersect each plane with each other plane to get a set of lines and then intersect these lines with each plane to find the correct line segment (or discard the line)." I'm not sure how to determine whether a line segment should be discarded or not.
Thanks to everyone helping in advance!
