opengl - Cube world rendering optimizations

I'm making a Minecraft like game and I would like to apply some optimizations. Firstly I didn't and I rendered the world using a vbo in which I stored a cube model and I drow all blocks of the worlds and off course it caused lag if there were too many blocks. Then I decided to draw the world face-by-face and check if a face is hidden from another one.

This concept is simple if I have the world made only by cubes of the same size, like this: Blue and black block are two blocks of the same size and the red face is the face to ignore since is hidden (overlapped) by another opaque face.

As I said if I want to make blocks of different sizes (scale)/position/rotation but by always drawing them from faces, the matter is different since I can't know if a face is completely visible or not. Here's an image of a normal block with a "custom" block on it:

Blue block is the custom block, the black a "normal" block and the red is the face overlapped by the biggest one (then it should be ignored during rendering).

Here the rotation is null but if there's no way to check rotated faces I can simply ignore it and draws all rotated blocks by default (I don't rotate all the world lol)... that's not what I'd like to do but if there's no way or the way is too difficult...

Anyway, finally, how can I check (using GL functions or doing it in my code) if a face is hidden and to ignore it on rendering?

I forgot to say that another optimization I did is if a block is hidden (has a block relative to each face) by other blocks I don't draw it.

Answer

(In this answer I assume that your world is made of separate cubes. If some cubes joined together into grids, then the algorithm can be improved a lot.)

---

You can check if a side is completely inside of a cube, and only add it to your vertex buffer if it's not.

The algorithm is easy:

//  B······•
//  :'.     '.
//  :  A······C
//  :  :      :
//  •  :      :
//   '.:      :
//     D······•


bool point_cube_collision(vec3 point, vec3 a, vec3 b, vec3 c, vec3 d, vec3 size)
{
    // `size` must be equal to `length(b - a)`, but you should remember it instead of recomputing it each time.
    const float eps = 0.0001; // This is used to make block sides disappear if they're not intersecting, but just toucing. The number determines how far the sides can be from each other to still be considered intersecting.
    b -= a;
    c -= a;
    d -= a;
    b /= size;
    c /= size;
    d /= size;

    point -= a;
    float m = point • b; // • means dot product
    float n = point • c;
    float p = point • d;
    return m >= -eps && m <= size+eps
        && n >= -eps && n <= size+eps
        && p >= -eps && p <= size+eps;
}

Now if you want to check if an entire side hidden inside of a cube, you just check 4 corners of it, and if all of them a colliding with the cube, then the side is completely inside.

I assume you already use VBOs to render your world. If so, you should add a side to your VBO only if it's not (completely) submerged into a cube.

I think you already understood that performing such check (every time the world is changed) for every cube has O(n^2) complexity (for each cube you need to check all other cubes), which means that it will quickly become very slow when your world will get larger.

To make the computations a lot more faster, you could divide your world into chunks. Then instead of checking every cube for each vertex, you can check only those cubes which intersect with a chunk which contains a vertex.

---

If for some reason chunk system won't work well for you, then you can try something more tricky. Something like Dynamic Bounding Volume Tree (which is used in Bullet Physics to check if objects are close to each other). I'm not really sure if it will work well, but I also highly doubt that you will need to try it.