ID map with shared vertices

OpenGL OpenGL: Advanced Coding
1

Hi all,

I would like to draw an ID map, i.e. an image with one color per face.
Normally I do it using flat shading and giving to all the vertices in one face the same color.
Unfortunately, I now have to do it with shared vertices, which breaks all my assumption. So here are the 3 questions:

  • Is it possible to specify a color per face using vertex arrays?
  • When I draw with flat shading and I give one color per vertex with vertex arrays, what is the color that gets picked?
  • Finally, do you have any idea on how to number the vertices in a mesh of arbitrary topology (i.e. I will always have enough vertices, but choosing the color I believe is an NP-complete problem like graph coloring).

If you have any idea on how to solve the problem in a completely different way, I would like to hear.

Thanks to alla of you

–xelatihy

2

  1. You can’t specify colors per face with vertex arrays, but you can disable the color array and specify the color manually. Of course that doesn’t make your program faster…

  2. With flat shading the faces always get the color of the last vertex.

  3. I don’t see the problem with numbering vertices. Just give each vertex a number. You can use numbers with up to 24 bit (32 bit if you use the alpha buffer too). You only have to set the color components to the individual bytes of the number. For example you could take the array index as the number for your vertex.

Perhaps I didn’t understand your third question right (English is not my native language), but I don’t see a NP complete problem.

3

The NP-complete part (I am not clearly sure about it yet), it that given an input mesh or arbitrary topology, you will have to set the color of each vertex so that at least one vertex in the mesh has the color of a face. For regular structure it is easy, but from a completely generic one, the only two algorithms that I can think of are a Greedy algorithm (that would not work), or an algorithm that would require eventually a full search (exponential). Randomized algorithm would take the badness of the Greedy approach out, but they cannot give garantees about the coloring, which I cannot afford.

Thanks anyway for your input, it is of much use.

–xelatihy

4

Ok, I see where the problem is.

If I understand this right you want to assign every vertex a color so that each face gets a unique color.

I am rather sure that this is NP complete or even worse. It can be unsolveable in some cases.

Just think of a sphere made of triangles. For this figure you have more faces than vertices (each vertex is shared by 8 faces, each face has 3 vertices).

The only way to solve this is to precompute data, and it could be neccessary to either split some vertices or assign some faces the same color. If vertex splitting is acceptable you can try to make an algorithm that finds a good aproximation to the best solution in realtime.

5

> I am rather sure that this is NP complete
> or even worse. It can be unsolveable in
> some cases.

It depends on whether you want to modify the mesh or not.

Worst case, you split each vertex out for each face, and give all three vertices for the face the color you decided on for that face. While it’ll render somewhat slower than an optimal mesh (if you’re transform bound), it will work.

It’s trivial to know that you can’t do it at all if you’re not allowed to modify the mesh. Think about a typical heightmap where each vertex is shared by six faces. There’s more faces than vertices; clearly you can’t color each triangle separately when only given per-vertex color changes (as is the case in OpenGL).