@Apoc
Just out of curiosity, would you mind to explain how your navmesh genertation algorithm works?
I'd first filter the graph for triangles you can't stand on and afterwards check if the connected triangles are traversable, or can you safely asume that all connected triangles you can stand on are traversable?
Edit: Stupid me, ofcourse it's possible that there are obstacles between to triangles you can stand on, but I'd guess you still would only need to check triangles around fences, trees and the like...