Hacker News Reader

Comment by Ogre | Hacker News Reader

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?

View on HN

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.

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.

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.

Reply on news.ycombinator.com