I’m working on a custom polygon reduction algorithm.

I’m using algorithm that collapses edges. The only thing left to do is to implement some smart way to choose which edge to collapse.
And this is where all the fun begins…

Look at this picture:

Red edge is the collapsed one. Red dot - point to where edge is collapsed, blue edge - our problem.
Green and blue dots are two triangles that get overlapped.

Of course I can detect such cases, but this is just one example. Lot’s of other funny, but unwanted things can happen.

So, any hints for creating smart (smart enoguh) algorithm for selecting which edge to remove?

Not sure what is your goal, but if it is about reducing polygon count (geometry LOD for example), you should collapse the smallest edge, and do it again until ‘n’ edges have been collapsed. This will keep your topology mostly intact.

If you stretch that above picture vertically alot, then the smallest edge will be the red one, so the issue of flipping polygons must be addressed first. Luckily I allready did that

I’ve changed my cost computation algorithm, so now it takes normals of all triangles involved and checks how will these normals change. The situation I painted above is the case, when triangle’s normal changes by 180 degrees, so there’s no chance new algorithm will make the same mistake.

Smallest edge approach will probably not work well for me - I don’t care how large polygons are as long as they lay on the same plane I collapse them into few big polygons, while small bump in the middle of this flat area will be made of small polygons that I don’t want to remove.

Ok, but since the worst problem has been solved I will continue to work on my own for now. I’ll let you know if I run into other problems or when it’s done.

Any other hints are of course welcome in the meantime

The problem is the vertex at the center. You need to eliminate it. You will thus have 3 triangles to render and 1 edge has been eliminated. Problem solved!