BIAS LightGrid - Marching Cubes?
<i>This post was originally made by <b>danij</b> on the dengDevs blog. It was posted under the categories: Blog, Engine.</i>
In my down time I've been looking at the light grid implementation and have been considering different ways to improve the accuracy (though I appreciate it's only designed for approximating ambient light).
One idea I came up with after looking at the way the light factor is applied (distribution from source block using the two dimensional attribution <tt>factors</tt> array) would be to use a method similar to a Marching Cubes algorithm.
While initializing the light grid, where currently a single sample point at the center of each block is used to determine the block's sector:
* Instead how about taking four samples (one for each corner of the block). This will (potentially) give us four different sectors.
* Examine these four sectors to see which ones are the same to approximate a "shape" for the block ie zeroth (all points are in a sector (any)) OR top, bottom, left, right, topleft, topright, bottomleft, bottomright when one or more sample point is not in any sector (it's in the void).
* block->sector is still choosen by the sector at the center sample point.
* Assign this "shape" id property to <tt>gridblock_t</tt>.
In LG_Update() where the light attribution factor is determined for each block being updated in the light grid:
* Instead of ALWAYS using a Zeroth distribution factor (from the <tt>factors</tt> array) - select a factors array based on the "shape" of the block being updated.
What are your thoughts on this?
If I'm right, the above method should greatly improve the accuracy of the lightgrid and help to reduce the amount of "bleeding light" between disjoint sectors.
I'm not sure but this approach should be scalable in the way that the HQ2X/3X etc, smart texture filters are (of course the current method is already scalable in that reducing the blocksize yields more accurate results).
BTW - What is the reasoning behind using a 2D block grid with "Z bias" (and not "real" 3D)?
Given this decision I presume that you have decided that either sector-over-sector won't be implemented in the 1.9.x series OR that you have a different method in mind for when it is (portals?)?
In my down time I've been looking at the light grid implementation and have been considering different ways to improve the accuracy (though I appreciate it's only designed for approximating ambient light).
One idea I came up with after looking at the way the light factor is applied (distribution from source block using the two dimensional attribution <tt>factors</tt> array) would be to use a method similar to a Marching Cubes algorithm.
While initializing the light grid, where currently a single sample point at the center of each block is used to determine the block's sector:
* Instead how about taking four samples (one for each corner of the block). This will (potentially) give us four different sectors.
* Examine these four sectors to see which ones are the same to approximate a "shape" for the block ie zeroth (all points are in a sector (any)) OR top, bottom, left, right, topleft, topright, bottomleft, bottomright when one or more sample point is not in any sector (it's in the void).
* block->sector is still choosen by the sector at the center sample point.
* Assign this "shape" id property to <tt>gridblock_t</tt>.
In LG_Update() where the light attribution factor is determined for each block being updated in the light grid:
* Instead of ALWAYS using a Zeroth distribution factor (from the <tt>factors</tt> array) - select a factors array based on the "shape" of the block being updated.
What are your thoughts on this?
If I'm right, the above method should greatly improve the accuracy of the lightgrid and help to reduce the amount of "bleeding light" between disjoint sectors.
I'm not sure but this approach should be scalable in the way that the HQ2X/3X etc, smart texture filters are (of course the current method is already scalable in that reducing the blocksize yields more accurate results).
BTW - What is the reasoning behind using a 2D block grid with "Z bias" (and not "real" 3D)?
Given this decision I presume that you have decided that either sector-over-sector won't be implemented in the 1.9.x series OR that you have a different method in mind for when it is (portals?)?
Comments
The problem with preventing "leakage" is that sector heights can change, so new openings and closed areas may be formed. Any algorithm used for plugging the leaks has to be updateable during gameplay (e.g., whenever affected sector heights change).
<blockquote>Instead of ALWAYS using a Zeroth distribution factor (from the factors array) - select a factors array based on the "shape" of the block being updated.
What are your thoughts on this?</blockquote> That might work, although it needs to be updated whenever sector heights change. Perhaps we should just maintain a Reject style array of information that tells us which sectors are not reachable from contributing sectors.
<blockquote>If I'm right, the above method should greatly improve the accuracy of the lightgrid and help to reduce the amount of "bleeding light" between disjoint sectors.</blockquote> Accuracy is not important. The light grid is <i>supposed</i> to be inaccurate (i.e., smooth, like ambient light is in real life). The only relevant issue is the light leakage.
<blockquote> What is the reasoning behind using a 2D block grid with "Z bias" (and not "real" 3D)? Given this decision I presume that you have decided that either sector-over-sector won't be implemented in the 1.9.x series OR that you have a different method in mind for when it is (portals?)?</blockquote>
The purpose of the Z bias is to simulate the primary light direction being in the ceiling or the floor. This should give more realistic lighting in sky-ceiling sectors. When it comes to sector-over-sector stuff: when/if it will be implemented, the map geometry will most likely still remain 2D. There will just be a way to define a new world origin for certain regions of the map, and the renderer (and game logic, in certain cases) will have to take those into account in order to create a seamless impression of 3D. If we don't do it like this, the entire toolchain of BSP building and map editors will have to be rewritten.
Exactly. The change to the current algorithm I am proposing is designed to affect only one-sided lines by detecting the "solid edges" of every sector (the outline of the void basically). Then by changing the shape of the light distribution that _CAN_ be applied to the block, we make it much more difficult for a light to ever "leak" through a permanently solid wall.
The updated algorithm would not do anything to react to sectors opening/closing so another algorithm would be needed. I was looking for a quick n' simple change to the existing algorithm that would reduce the "leakage" as much as possible without incurring much more development work.
A Reject like approach would probably be a better alternative since it could support sectors opening/closing (though more work).
<blockquote>When it comes to sector-over-sector stuff: when/if it will be implemented, the map geometry will most likely still remain 2D.</blockquote>
Thanks for confirming what I thought.