Drawing Collision on Screen

Question

And here we are for another question.

After the previous one, i finally completed the kDop system and everything related. (Hierarchycal tree of kDop, etc..) Everything works fine.

Now i want to draw on screen the collision for debug purpose and to see the result of the work. (To see if the hierarchical choice i've done in a particular mode is fine or not)

For the AABB/Sphere no problem, its pretty much easy to create. The problem is with the kDOP...

I have :

axises (1,0,0)(0,1,0)(0,0,1)(1,1,1)(-1,1,1)(1,-1,1)(1,1,-1)(1,1,0)(1,0,1),(0,1,1),(1,-1,0),(1,0,-1),(0,1,-1) and the Min/Max values calculated using the axes.

How can i create a series of polygon (a simple mesh in fact) with these data? (I don't care about implementation, i just want to understand it theorically so I can implement it)

Thanks a lot for the answers!!!

EDIT : I can calculate EASILY the normals of the mesh cause I already have the axis. The problem is calculating the vertex position...

EDIT 2: I found on the net this code that seems to be useful (or at least in the doc it says its for creating a debug mesh), but I don't know how to use it to find the vertex position :

    real Kdop::getDistanceOfPlaneToOrigin(int k) const {
        if (k < 0 || k >= mK) {
            return 0.0f;
        }
        if (k >= mK/2) {
            return (real) (mDistances[k] * -1.0);
        }
        return mDistances[k];
    }

EDIT 3: I thought and having normals and a point (the origin, that i'm sure the plane pass over), i can build all the planes related to the operation... Now I need something more....

Answer 1

Did you look at the marching cube algorithm? (http://en.wikipedia.org/wiki/Marching_cubes)

I don't know if it can be used as is, but you can probably inspire yourself from it.

Answer 2

In general, each vertex is the intersection of three planes. Additionally, each vertex you want to draw needs to be on the correct side of all remaining planes. This may be an annoying combinatorial description of the problem, but with a kDop, at least it's a fixed-size problem...

To get a bit more clever about it, you should look at some Linear Programming math. Specifically, once you have a valid vertex (i.e., an intersection of 3 planes that is on the correct side of the remaining planes), you can slide along each edge to the next valid vertex. You can recursively explore the entire graph of valid vertices and edges this way: do a breadth-first search of the graph, keeping track of which vertices you've explored -- and once you've exhausted the possibilities (finite, remember!) you've got what you want to draw.

Oh, and to calculate the actual vertices based on the planes, check out this mathworld page.

[edit:] -- Actually, you may be able to simplify your search quite a lot, if you know for sure that none of your planes are redundant (i.e., if none of them are entirely outside your kDop). In that case, your kDop has a standard structure, with each polygon having a fixed configuration of neighbors; in that case, you can just plug your planes in, compute your fixed set of vertices, and draw your standard figure with them. You could easily (if somewhat tediously) work out all the details by hand.

You might want to watch out for degenerate cases, though -- e.g. if you put an oriented cube in your kDop, so that most of your facets are zero-sized.

[edit2:] -- On further consideration, I'm thinking your configuration may not be entirely fixed. For example, say there are 4 nearby planes; and based on their depth, the edge between them may go one way or another, like so:

plane A     |    plane B
            |
           / \
          /   \
         /     \
________/       \
        |        \
        |         \
plane C | plane D  \

        vs.

plane A |    plane B
        |
        |
________|
         \
          \
          |\
          | \
          |  \
          |   \
          |    \
          |     \
          |      \
          |       \
          |        \
plane C   | plane D \

However, I think you can still simplify your setup somewhat. You will still need to check whether your vertices are valid or not, but you can reduce both the number of vertices and the number of planes to check by considering your particular plane configuration.