This is not an opengl-specific question but I was wondering if there is any known and proven algorith/technique to generate valid 3d solids randomly? And by valid I mean a collection of vertices that can all be connected to form a solid.
All vertices can always be connected.
Your restrictions sound more like :
every vertex is connected to at least 3 edges.
every edge must be shared by 2 and only 2 triangles.
every edge must not intersect any of the triangles.
So a brute-force way would be to generate random points, connected by random edges to form triangles, then clean up every conflicting vertex and edge. Of course a lot of junk will be thrown out.
You may have other constraints, like all no disjoints parts, or no donut-holes, etc. So maybe a less brute force approach would be to go from a cube, and catmull-clark subdivide it with random noise, each iteration with a smaller magnitude.