occlusion culling

sup /prog/,

So I'm gonna make myself a isometric game that is built up with cubes so one of the important things to me is occlusion culling when there are a ton of cubes on that screen to be drawn. As of right now i'm making a quick java version for quick deploy and easy access with swing, etc.(Later it'll be ported to either C or C++).

As of right now i kinda have an idea of how i could attack this by rendering 2 frames. Here's how it would work:

1st Frame:
-Rendered from left -> right; front -> back
-As it's rendering it would check each cube based on it's hit box to see if it is covered or partially visible
-If partially visible(or completely) =>Draw cube; add to a Array containing all the cubes that will be drawn in the 2nd frame
-else => Discard that cube and move to the next one

2nd Frame:
Very easy render from right->left; back -> front with all of the cubes that will be visible in that frame.


In theory this method should work if implemented correctly, but my question to /g/ is does anyone know of a simpler more optimized way of doing occlusion culling(without using openGL or restricting myself to DirectX).

Java

Now he has 2 problems

I'll ask the obvious question: how do you plan on determining which cubes are visible in your "first frame"? Regardless of the answer to that question, it's guaranteed that treating each cube individually will lead to a far slower solution than just drawing everything every frame.

VSD is one of the hardest problems in real time 3D rendering, and it's one of the main causes of shittily performing applications. Modern games (think Unreal Engine 3) use hierarchical delayed hardware occlusion queries. Going a bit back (Source engine, Unreal Engine 2) we have hybrid software methods including portals, occluders, and precomputed visibility (this last one in Quake derivatives including Source). Each method has a different set of trade-offs.

To answer your specific question, for a Minecraft clone, your best bet is probably to pack a bunch of cubes together (say, 10x10x10 units), frustum-cull these packs, then send each one as a batch in front-to-back order to the hardware. That's the best you can do if you expect landscapes where you can basically see everything from any given point. For closed spaces you might benefit from hardware occlusion queries, but this must be done very carefully as they have a significant cost. Here I'm assuming the world is dynamic enough that precomputing visibility is unfeasible.

>>4
>how do you plan on determining which cubes are visible in your "first frame"?
-As it's rendering it would check each cube based on it's hit box to see if it is covered or partially visible
-If partially visible(or completely) =>Draw cube; add to a Array containing all the cubes that will be drawn in the 2nd frame
-else => Discard that cube and move to the next one
I would run pixel checks in the frame to see if something is there or not there.


and yeah i could make it so i break the map up into chucks and then run those chucks through to see if they would be visible or not.

>>5
I would run pixel checks in the frame to see if something is there or not there.
This will not end well.

>>6
please express your concern

>>7
>>5
also to add onto that it would only look to see if any of the 4 corners on the isometric cube are visible. If 1 corner is visible when Drawn -> add to list else skip to next chuck(if i do in groups) or cube(if individually).

>>8
4 corners on the isometric cube
An isometric cube has six vertices on its visible perimeter - it is a hexagon in shape when rendered.  Unless you are talking about a bounding box for it ...

creating a minecraft clone
Oh, you.

>>8
What if the 4 corners aren't visible but a small portion of the face of the cube is?

>>10
As long as it's not written in Java, it should be an improvement.

As of right now i'm making a quick java version
Never mind.

>>1
cube
hit box
sage

If you used a functional language this could all be taken care of with a lambda-calculus s-expression tail-recursive abstract bullshite that you will never understand

>>9
I stand corrected, i would have to check each vertex.
>>11
see above
>>12
see the first parentheses in the first post

>>10
He referred to it as a minecraft clone, I have no comment on that and if i had to choose i would take infiniminer instead.

>>14
thank you

License Umbra.

A good question on /prog/? Real help in the first 3 replies? I found myself checking whether this was a necro thread from 2006.

>>5
I would run pixel checks in the frame to see if something is there or not there.
Isn't this what a depth buffer is for? If you're going to do this, let the video card do it for you. Just render all frames the way you would your "1st frame", except turn on depth test. Problem solved.

This is of course assuming you are sticking with a fixed isometric view, where your environment is very few cubes deep. If this is a Minecraft clone you are going to have a whole lot more problems. >>4 is basically correct here, except instead of making 10x10 packs, I would store it in an octree. You will want all the child nodes of each node depth-sorted, and paint everything front-to-back with a depth buffer, frustrum culling each node as you traverse it... you know the drill. Painting an octree is fairly straightforward.

>>1
I found this link for ya: http://www.gamedev.net/community/forums/topic.asp?topic_id=581073

It looks suspiciously similar to Minecraft, and it is from 2004, so maybe this is actually the Minecraft guy.

>>17
Something must be wrong with /prog/ today

I hope you're using an octree.

>>17
Ahem.  You do not need to depth-sort the child nodes in an octree.  Just traverse the tree correctly and the nodes will come out in depth order.  This is a property of all binary space partitioning trees in general, of which the octree is an example.

>>18

Member since: 11/16/2004
Posted - 8/31/2010 5:49:58 AM

I have the oldest non-administrator user account on gamedev.net.

>>23
Your momma must be real proud

>>23-24
I had a really small Slashdot user number but I don't remember my login.

>>25
s/S(.*?\s){3}/penis /