This smells like a classic case of optimising before you need to. Have you benchmarked the original method? Have you actually seen artifacts caused by the first? If not, no need to optimise.

Also, if you intend to do this at run time, it's more likely that you don't need to retessellate each frame, just cache the geometry somewhere. Do you intend to have this work with shapes that have holes?

Hi! Thank you for your comment. No, I haven't actually seen some artefacts, but I know that most 3d applications have problems with unoptimized triangles, especially when interpolating texture coordinates along the edges of these long, thin triangles. I don't want to optimize the triangles every frames but every time the mesh has been changed by the user.

Currently I implemented a very simple algorithm for testing issues, but it's still very slow. Basically it works by testing all adjoining triangles if it's possible to swap the diagonal in order to minimize the length of the sides of both triangles. It produces a nice triangle net but still has some performance issues I want to overcome at some time. If anyone knows an algorithm that is already existing, please let me know.

Christian

If you are interested in doing great quad meshes, here is a paper that looks interesting : http://www.graphics.rwth-aachen.de/uploads/media/spm08.pdf

About triangle, you should take a look at that paper : http://www.graphics.rwth-aachen.de/uploads/media/automatic_restoration.pdf
I haven't read it but it looks interesting !

EDIT : this one too : http://cit.zesoi.fer.hr/downloadPaper.php?paper=270