Volumes Of Funhttp://www.volumesoffun.com/phpBB3/ Per vertex ambient occlusionhttp://www.volumesoffun.com/phpBB3/viewtopic.php?f=14&t=481 Page 1 of 2

 Author: Dynasty [ Thu Feb 14, 2013 4:44 am ] Post subject: Per vertex ambient occlusion I attempted to implement ambient occlusion on a per vertex basis for Ace of Spades maps. Unfortunately, it seems that the current raycasting is just too slow to be of much use. Ace of Spades maps can range from 2.8 - 5.7 million vertices.I attempted to cast rays at every vertex position. The algorithm I used to determine which directions to cast rays is described in http://www.xsi-blog.com/archives/115Picture of points distributed evenly on a unit hemisphere generated by the algorithm:I modified it like this so that it works on a hemisphere:Code:def pointsOnHemisphere(N):    old_N = N    N = 2 * N    pts = []    inc = math.pi * (3 - math.sqrt(5))    off = 2 / float(N)    for k in range(old_N, N):        y = k * off - 1 + (off / 2)        r = math.sqrt(1 - y*y)        phi = k * inc        pts.append([math.cos(phi)*r, y, math.sin(phi)*r])    return ptsSo my final conclusion is that AO is just too slow to be used on large maps. Of course, my C++ skills are currently lacking, and there is probably a lot of room for optimization. If anyone else wants to take a stab at the problem, please go ahead.

 Author: David Williams [ Thu Feb 14, 2013 9:13 am ] Post subject: Re: Per vertex ambient occlusion We have a 'TestRaycast' unit test in PolyVox so I just did some very quick calculations. It seems PolyVox can perform something in the order of 1 million ray casts per second. You have (say) 3 million vertices and I reckon you want to cast approx 100 rays for each. So that's 300 million rays = 300 seconds = 5 minutes.So yes, it does seem like this approach is too slow for your needs. Threading might help as might optimisations to the raycast but probably not enough.A different algorithm then? AO changes slowly, so what if you only cast 10 rays per vertex but then average together the results of neighbouring vertices? Or maybe 100 rays per vertex was too much anyway?One very fake approach I have thought about in the past is to threshold the volume so that all voxels are just solid (black) or empty (white), reduce the resolution, and then blur it. This should result in darker voxels near the walls and lighter ones further away. No physical basis though.Otherwise you could try just casting a one (or very few) rays per voxel in an upwards direction. This would give you shadows at least but not real AO.So yeah... I don't have any firm answers here as AO is an area which needs some research. We didn't get it into Voxeliens but we'll come back to it for Cubiquity I think.

 Author: Dynasty [ Sat Feb 16, 2013 7:47 pm ] Post subject: Re: Per vertex ambient occlusion I briefly read through some of the material related to ambient occlusion and cone tracing. I don't really see how implementing AO on the CPU is viable.You've said before that the current AO occlusion algorithm is inefficient. How can it be made better? I don't really see any way this can be done in reasonable amount of time on many different types of hardware.

 Author: Dynasty [ Sat Feb 16, 2013 9:13 pm ] Post subject: Re: Per vertex ambient occlusion I've been thinking about this problem a lot and I think that I have an elegant solution for per-face ambient occlusion.Here is an illustration of the approach in 2D. It can be pretty easily extended to 3D.Create a hemisphere radiating outward from the face you want to test. In the picture above, the pink dot is the voxel being tested. The black voxels are solid.Let the number of blue "surface" voxels be s.Project the solid voxels onto the surface of the hemisphere. The orange voxels are those which fall into the "shadow" of the solid black voxels. The important thing to realize is that for every voxel in the green area, we pre-compute which surface voxels will be marked as orange.Let the number of orange "shadow" voxels be r.Then the ambient occlusion multiplier is 1-(r/s)Using the 2D example above, the ambient occlusion multiplier is 1-(6/41)=0.85 which means that 85% of ambient light will reach that face.I'm not sure how fast this algorithm will be compared to the current one implemented.Edit: per-vertex AO could be possibly implemented by subdividing the grid. Also if you have an suggestions on how to determine which surface voxels fall into the shadow that would be awesome.Edit 2: This is most likely a numerical approximation to an integral that happens to work very well with voxel data. The more subdivisions made, the more accurate the result will be. Only one subdivision should be needed to achieve per-vertex AO!Edit 3: Also the current architecture of CubicSurfaceExtracter, etc is not particularly conducive to implementing this algorithm.

 Author: Dynasty [ Sun Feb 17, 2013 6:10 pm ] Post subject: Re: Per vertex ambient occlusion The algorithm I discussed previously probably has no advantage over the ray casting method. The primary bottleneck in the current algorithm is the large number of reads/writes made to memory. In the current implementation, anytime the raycaster wants to know if a voxel is solid or not it needs to pass an object to a callback, which in turn needs to get the pointer to the SimpleVolume, and then needs to get the specific voxel object, which calls another function which checks if the block is solid, and then even that block may call another function....To reduce memory requests I suggest that a boolean array be created which marks with a simple true and false whether or not a block is solid. Hopefully parts of this array will be stored in the CPU cache.Also the path of all the rays needs to be computed only once. This means that all of those floating point operations in the AO calculator can essentially be eliminated. Hopefully these arrays of relative points will also be stored in the CPU cache.

 Author: Dynasty [ Mon Feb 18, 2013 12:50 am ] Post subject: Re: Per vertex ambient occlusion Relevant discussion on Build and Shoot: http://www.buildandshoot.com/viewtopic. ... 57&p=14321I'm Yourself on the Build and Shoot forums by the way.