Different triangulation plugins can work, but you still get problems.
You should consider manually creating 'guides' in your models to provide triangulation 'hints' for your model. Take this part of the alamo model I'm doing. You can see how the lines in the faces help with the triangulation.
[image: Trian.jpg]
You can of course use the eraser tool and ctrl-click (PC, not sure Mac) to 'hide' the lines and they will still work as shown:
[image: Trian2.jpg]
FWIW, the fastest triangulation plugin I've found is the SketchUV plugin triangulator.
