In modern computing, meeting truly new algo-problems seems more rare nowadays. A 90-yr lecturer of mine even said "all possible algo problems were solved decades ago. ALL!" .
Well, here's one that wasn't a problem until DX10-class gpu hardware introduced a trick :)
The problem: add flat-attributes to vertices, and have triangle-indices arranged in such a way, that the first of the 3 vertices of the triangle contains the flat-data. The triangle's winding has to be kept intact ( {0,1,2} = {1,2,0} = {2,0,1} )
Some vertices might have to be duplicated (unwelded) when there are none to keep the current triangle's flat-data. The optimization target is to do as little duplication as possible.

Here's a HLL naive solution: http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&Number=265872#Post265872

Here's an example input data (that tetrahedron on that page), where my naive implementation unwelds one vertex:
int origIndices[4*3] = {
0, 1, 3,
1, 2, 3,
2, 0, 3,
0, 2, 1  // gets modified by the func to "4, 2, 1"
};
Here's that same data, prepared manually to introduce no unwelding in that simple func:
int origIndices[4*3] = {
0, 1, 3,
1, 2, 3,
3, 2, 0, // ******
0, 2, 1 // this gets changed by the func to  "2, 1, 0"
};


I've posted there 2 quick-ideas on result-optimization, that I haven't tackled yet.
Solve this for fun :D

(afaik, this problem hasn't been solved and optimized anywhere yet)

(btw pardon the inactive "memset(pResult,0,FNumNewVerts*NewVtxSize);" line there :) )
Posted on 2009-10-20 09:45:37 by Ultrano
That's not exactly new though, is it?
Flatshading required the first vertex to have the face normal for as long as I can remember, I think with both D3D and OpenGL.

And in a way your lecturer is right. This is just variation of one of the classic NP-complete problems (tri-color problem?). Such NP-complete problems are relatively easy to solve with a recursive algorithm that just tries all combinations and picks the best one. However, those algorithms are very slow.
Hence in practice such problems are usually solved with some kind of approximation. You just use some heuristics to pick the option that is most likely to be optimal.
You won't arrive at THE optimal solution, but it's generally close enough, and the real gain is in the running time of the algorithm, which is orders of magnitude faster.
Posted on 2009-10-20 11:39:10 by Scali
Here's a simpler explanation of the problem. Given an array  "int indices[3*NumRows]", rotate each row so that the first column contains each index only once, if at all.

Input:
0, 1, 3,
1, 2, 3,
2, 0, 3,
0, 2, 1

naive output:
0, 1, 3,
1, 2, 3,
2, 0, 3,
4, 2, 1  // see, the naive func couldn't find a solution for this, so it cloned item "0" to a new index, "4". It could have cloned "2" or "1" instead, too.

and the best output would be:
0, 1, 3,
1, 2, 3,
3, 2, 0,
2, 1, 0


See how the first column is "0 1 3 2", no index is used more than once in it.
Posted on 2009-10-20 11:43:08 by Ultrano
Well, here a combination of varying and flat is needed. I never saw even a hint on even flat reordering done anywhere, so it's new to me.
Posted on 2009-10-20 11:46:41 by Ultrano