3
\$\begingroup\$

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: enter image description here 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:

enter image description here 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.

\$\endgroup\$
  • \$\begingroup\$ How often your world is being changed? \$\endgroup\$ – HolyBlackCat Jan 7 '17 at 23:29
  • \$\begingroup\$ When it generated (I set all the blocks IN A CHUNK first and then update all) and when the player decide to place a block. \$\endgroup\$ – loryruta Jan 7 '17 at 23:48
  • \$\begingroup\$ Well, it's not too hard to do some calculations to see if a block side is completely inside of another block every time the world is changed. It will require O(n^2) time, but if you divide your world into chunks and do those computations on one chunk at a time, then it shouldn't be too bad. (I could make an answer to explain details if you need it.) If this approach won't work fast enough, then you could try something with Dynamic Bounding Volume Tree, but I'm not sure how well will it work. \$\endgroup\$ – HolyBlackCat Jan 8 '17 at 0:00
  • \$\begingroup\$ Yeah if you mind I appreciate a detailed response. It seems interesting. \$\endgroup\$ – loryruta Jan 8 '17 at 0:08
3
\$\begingroup\$

(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.

\$\endgroup\$
  • \$\begingroup\$ @loryruta Glad to hear that it worked. \$\endgroup\$ – HolyBlackCat Jan 9 '17 at 15:57
0
\$\begingroup\$

My suggestion would be using a 3D array of Block objects. You should check whether the block next to a block is solid then only render the visible faces

\$\endgroup\$
  • \$\begingroup\$ This system works only if I have all blocks of the same size, is that the issue in which I falled! \$\endgroup\$ – loryruta Jan 7 '17 at 22:52
  • \$\begingroup\$ Honestly, I can't see much if a way to remove those faces if you want to have your world procedurally generated \$\endgroup\$ – Leo Jan 8 '17 at 10:58
0
\$\begingroup\$

I'm not entirely sure about only rendering the faces themselves, but I know that not rendering objects that the camera cannot see directly would fall under the "culling" umbrella, and specifically I think you maybe want to look at occlusion culling. I'm not intimately familiar with OpenGL, but a quick google search yielded at least several ideas for implementing occlusion culling. Perhaps see this thread or this other one (both from the opengl formums) for some ideas.

There's also an article that I really liked which may give some general ideas as well. In there there's also a mention at Depth Pre-Pass as an option for your specific problem, which will do a rough cull of pixels that are behind other objects. It's not always an efficient method for all applications, but it might be worth your time to look into. I hope this helps a bit to give you some ideas.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.