Tile Culling -- SlopeWalk alg. explained
Posted: 05 May 2014, 00:43
Occlusion Culling aka http://en.wikipedia.org/wiki/Hidden_surface_determination is important thing in CG when you want to keep high fps in your program. Culling a tiles on regular 2D gird seems to be extremly simple to implement, as you can easily precompute boundary of visible set of tiles in the camera view and by walking around that boundary you can disable enable proper tiles. What is the shape of such tile set cut by camera planes ? Well it is Quadrilateral , except we are in the quantized space http://en.wikipedia.org/wiki/Quantization , so the sides of that q-l is not straight line , but rather up and down >> stairs << .
Previous tile culling alg. was flawed because it was working only for some special case ( case being the positional relation of our four points ) .
Currently I try to impment the most general polygon rasterizing algorithm , that is :
1. We choose the max and min points due to their Y value .
2. We sort all the points by the angle value in it's polar representation ( that is going , by visiting them clockwise due to the center of the polygon )
3. Now we have two paths from which we can walk from top to down vertices : call them left and right .
4. Between each following pair of vertices we can establish a >> slope << , which is just the the "a" in the eq. of linear form y = ax + b
5. Now start drawing our polygon Row by Row From top to bottom . Each Row has given the most left and rightmost tile due to use of both paths prepared before -- Left path for tracing the most Leftmost Tile , Right path teh most Rightmost Tile in each .
EDIT : Bertram , Could you merge in your branch into 'development' one ?
EDIT: I UNBURIED THAT THREAD SO WE CAN DISCUSS CULLING AGAIN
Previous tile culling alg. was flawed because it was working only for some special case ( case being the positional relation of our four points ) .
Currently I try to impment the most general polygon rasterizing algorithm , that is :
1. We choose the max and min points due to their Y value .
2. We sort all the points by the angle value in it's polar representation ( that is going , by visiting them clockwise due to the center of the polygon )
3. Now we have two paths from which we can walk from top to down vertices : call them left and right .
4. Between each following pair of vertices we can establish a >> slope << , which is just the the "a" in the eq. of linear form y = ax + b
5. Now start drawing our polygon Row by Row From top to bottom . Each Row has given the most left and rightmost tile due to use of both paths prepared before -- Left path for tracing the most Leftmost Tile , Right path teh most Rightmost Tile in each .
EDIT : Bertram , Could you merge in your branch into 'development' one ?
EDIT: I UNBURIED THAT THREAD SO WE CAN DISCUSS CULLING AGAIN