4 ms·

I remember that the OpenGL occlusion query code was especially glitchy-- it had a bad tendency to make things become invisible for no apparent reason! Context:

I remember that the OpenGL occlusion query code was especially glitchy-- it had a bad tendency to make things become invisible for no apparent reason! Context: I wrote Optimine (early graphics optimization mod) and MCRegion (optimized file format that became the Region/Anvil formats). This sounds very similar to http://en.wikipedia.org/wiki/Potentially_visible_set http://en.wikipedia.org/wiki/Potentially_visible_set I'm not sure why they're doing a full flood-fill-- why compute connectivity instead of visibility? Knowing the answers to "entering through face A, can a ray exit through face B?" should solve the same problem and also be easier to compute.

SquareWheel 12y ago
Ah, I thought I recognized that name. Optimine really made the game playable for me in early days, thanks for your contributions.
tom_0 12y ago
Hey, generalizing the answer like that is nice, the flood fill is definitely an approximation of that. However keep in mind that the flood fill is run only once, not per frame, so you have to check that "any ray from face A can exit through any point of face B", so I'm not sure it is easier to compute. I'm sure there is some way to get closer to this than a flood fill, but for 0.9 it had to be good enough!
- Ogre 12y ago
  For the actual occlusion test, you have a "don't go backwards" rule. If you have to go backwards to reach a chunk, you know it's not visible along that path (but may be on a different path, which you will eventually find). Without having thought about it a whole lot, does that work for the inside-a-chunk tests too? If you have to traverse an edge facing back towards the face you're coming from, does that mean there's no visible path from the first edge to the second? And if so, would that give a meaningful reduction in connectivity?
  - Ogre 12y ago
    Partly answering my own question after mulling it over, the difference in the pre-pass is that you're not actually coming "from" an edge or going "to" one when you're doing the flood fills, you're just testing which edges are connected to any given empty cell. But I still think there might be something to this idea. The simplest thing I can think of is to do no-backwards searches out from all the empty cells on each edge and see which other edges you reach. That's potentially 6x as many searches (slightly smaller and with some early outs since the connectivity is bi-directional), but at least it's still finite and predictable and isn't who knows how many raycasts. I don't know if that's acceptable for the pre-pass or not. But I also think there might be smarter ways to do it that only require a single search from each empty cell but remember directions traversed so you know if a particular path you've reached an edge along implies visibility or not. Maybe you can do the 6 searches in parallel, such that whenever they meet you know you've found a connection between the two edges they were coming from? I don't know if that means any less work except in cases where all 6 edges are trivially connected.
  - infogulch 12y ago
    There's a problem with that I think. If I understand correctly, the inside-a-chunk tests are filled directionless, so this wouldn't work. Basically it performs a flood fill on contiguous groups of all the transparent blocks in the chunk. If any group touches two sides they are considered to be able to see each other. Keep in mind this is precomputed and doesn't have a "looking-at" direction. Perhaps you could perform this test six times, one for each face. Then you would have a direction.
    - Ogre 12y ago
      Yeah, see my reply to myself, I beat you by a few minutes =) Whether 6X the searches is worth it or not is something only testing can answer, I think.
- Scaevolus 12y ago
  That's a fair point. The interior shape of most of the chunks you're handling is mostly convex anyways, so flood-fill's conservative visibility determinations will usually be equal to the precise numbers.
Ogre 12y ago
Glitchiness of occlusion may be driver or hardware dependent. I've been using it successfully, but haven't tested on a variety of hardware. The bigger issue is the two way communication between GPU and CPU. You want your pipeline to be one way, otherwise you either have stalls waiting for results (poor or inconsistent framerates), or things becoming visible one or more frames later than they should. For some applications, the latter is acceptable. For Minecraft (style) chunks, it might mean sometimes large amounts of terrain popping in a frame or two too late, which could be very noticeable. It seems like a combination of both might be feasible. Do something smart like this article on the CPU, which feeds into a greatly reduced set of occlusion queries, small enough to perhaps not introduce significant stalls using the first method. However, in this article's case, he's specifically targeting the mobile edition of minecraft, where hardware occlusion is not yet universally available! So fast CPU versions are definitely warranted, and I think he's got a really good solution.

SquareWheel 12y ago

Ah, I thought I recognized that name. Optimine really made the game playable for me in early days, thanks for your contributions.

tom_0 12y ago

Hey, generalizing the answer like that is nice, the flood fill is definitely an approximation of that. However keep in mind that the flood fill is run only once, not per frame, so you have to check that "any ray from face A can exit through any point of face B", so I'm not sure it is easier to compute. I'm sure there is some way to get closer to this than a flood fill, but for 0.9 it had to be good enough!

Ogre 12y ago
For the actual occlusion test, you have a "don't go backwards" rule. If you have to go backwards to reach a chunk, you know it's not visible along that path (but may be on a different path, which you will eventually find). Without having thought about it a whole lot, does that work for the inside-a-chunk tests too? If you have to traverse an edge facing back towards the face you're coming from, does that mean there's no visible path from the first edge to the second? And if so, would that give a meaningful reduction in connectivity?
- Ogre 12y ago
  Partly answering my own question after mulling it over, the difference in the pre-pass is that you're not actually coming "from" an edge or going "to" one when you're doing the flood fills, you're just testing which edges are connected to any given empty cell. But I still think there might be something to this idea. The simplest thing I can think of is to do no-backwards searches out from all the empty cells on each edge and see which other edges you reach. That's potentially 6x as many searches (slightly smaller and with some early outs since the connectivity is bi-directional), but at least it's still finite and predictable and isn't who knows how many raycasts. I don't know if that's acceptable for the pre-pass or not. But I also think there might be smarter ways to do it that only require a single search from each empty cell but remember directions traversed so you know if a particular path you've reached an edge along implies visibility or not. Maybe you can do the 6 searches in parallel, such that whenever they meet you know you've found a connection between the two edges they were coming from? I don't know if that means any less work except in cases where all 6 edges are trivially connected.
- infogulch 12y ago
  There's a problem with that I think. If I understand correctly, the inside-a-chunk tests are filled directionless, so this wouldn't work. Basically it performs a flood fill on contiguous groups of all the transparent blocks in the chunk. If any group touches two sides they are considered to be able to see each other. Keep in mind this is precomputed and doesn't have a "looking-at" direction. Perhaps you could perform this test six times, one for each face. Then you would have a direction.
  - Ogre 12y ago
    Yeah, see my reply to myself, I beat you by a few minutes =) Whether 6X the searches is worth it or not is something only testing can answer, I think.
Scaevolus 12y ago
That's a fair point. The interior shape of most of the chunks you're handling is mostly convex anyways, so flood-fill's conservative visibility determinations will usually be equal to the precise numbers.

Ogre 12y ago

Glitchiness of occlusion may be driver or hardware dependent. I've been using it successfully, but haven't tested on a variety of hardware. The bigger issue is the two way communication between GPU and CPU. You want your pipeline to be one way, otherwise you either have stalls waiting for results (poor or inconsistent framerates), or things becoming visible one or more frames later than they should. For some applications, the latter is acceptable. For Minecraft (style) chunks, it might mean sometimes large amounts of terrain popping in a frame or two too late, which could be very noticeable. It seems like a combination of both might be feasible. Do something smart like this article on the CPU, which feeds into a greatly reduced set of occlusion queries, small enough to perhaps not introduce significant stalls using the first method. However, in this article's case, he's specifically targeting the mobile edition of minecraft, where hardware occlusion is not yet universally available! So fast CPU versions are definitely warranted, and I think he's got a really good solution.