SSAO Questions

Ideas, enhancements, feature requests and development related discussion.

SSAO Questions

Postby dcuny » Sun Feb 01, 2009 11:12 am

I've been looking over articles on SSAO (Screen Space Ambient Occlusion, for those not following my many prior threads ;)) and found this site particularly helpful, especially since he posted his source code filled with comments. :)

However, I'm having trouble understanding a couple points in the code.

In his energy minimization article, he shows a method to distribute samples evenly around a sphere. It's essentially the same as applying spring forces to the samples. The code is:
Code: Select all
    // Energy minimization
    int iter = 100;
    while( iter– ) {
        for( int i = 0; i < samples; i++ ) {
            Point3 force;
            Point3 res = Point3( 0.0f, 0.0f, 0.0f );
            Point3 vec;
            float fac;
            vec = sampleSphere[ i ];
            // Minimize with other samples
            for( int j = 0; j < samples; j++ ) {
                force = vec - sampleSphere[ j ];
                fac = DotProd( force, force );
                if( fac != 0.0f ) {
                    fac = 1.0f / fac;
                    res.x += fac * force.x;
                    res.y += fac * force.y;
                   res.z += fac * force.z;
                }
            }
            res = res * 0.5f;
            sampleSphere[ i ] += res;
            sampleSphere[ i ] = Normalize( sampleSphere[ i ] );
        }
    }
My question is with this line:
Code: Select all
fac = DotProd( force, force );
The dot product between two vectors will yield the cosine of the angle between them. So what's the point of performing the dot product against the same vector? I'm not sure what this "means".

The other question I've got is more a question of approach. Raytraced AO normally works by shooting off a bunch of rays from the point you're interested in evaluating evenly over that point's hemisphere, and determining what occludes it within a set distance. The ratio of rays that hit something nearby vs. the rays that don't gives the amount of occlusion (shading) for that point.

SSAO is similar, but instead of raytracing, it selects random points within a sphere, and tests if those sample points (relative to the point of interest) are occluded in screen space. Points in the sample sphere which are behind the point's hemisphere are discarded. This is typically done by doing a dot product between the screen point's normal (n) and a vector from the screen point to the sample point (s - p).

This is what I expected to see in the code - something like:
Code: Select all
float dp = DotProd( normal, Normalize( s - p ) );
Instead, he's got:
Code: Select all
      // Get sample point, in camera space
      Point3 samplePoint = p + vector;

      // Get screen coordinate of the sample point
      Point2 screenSamplePoint = MapCamToScreen( samplePoint );
      int sx = int( screenSamplePoint.x + 0.5f );
      int sy = int( screenSamplePoint.y + 0.5f );

      // If sample point is outside the bitmap then ignore it.
      // This code could potentially be skipped in a realtime scenario
      if( sx < 0 || sy < 0 || sx >= w || sy >= h )
         continue;

      // Get z-buffer depth at sample point
      float sampleZ = zBuffer[ sx, sy ];
      // Do nothing with samples that are the background
      if( sampleZ <= -1.0E30f || sampleZ == 0.0f )
         return;

      // Get the difference of the depth at the sample and the depth at p
      float zd = sampleZ - z;

      // Ignore samples with a depth outside the radius or further away than p
      if( zd < radius )
      {
         // Calculate difference in distance to sample point and the z depth at that point
         // Optimized by using squared, ok due to the nature of how we will use it
         // One could probably use samplePoint.z instead of length though.
         float zd2 = LengthSquared( samplePoint ) - sampleZ*sampleZ;

         // Check that the sample point is in front of the z-buffer depth at that point
         if( zd2 > 0.0f )
         {
            // Now get a new point that is samplePoint, but with an adjusted z depth
            Point3 p2 = Normalize( samplePoint ) * -sampleZ;

            // Get cosine of angle between the normal in p and a vector from p to p2
            float dp = DotProd( -normal, Normalize( p2 - p ) );
            // Check that the angle is inside the cone angle
            if( dp > coneAngle )
               occlusion += 1.0f;
         }
      }
Specifically, the lines:
Code: Select all
            // Now get a new point that is samplePoint, but with an adjusted z depth
            Point3 p2 = Normalize( samplePoint ) * -sampleZ;

            // Get cosine of angle between the normal in p and a vector from p to p2
            float dp = DotProd( -normal, Normalize( p2 - p ) );
Any clue what p2 might mean? I don't understand what normalizing the sample point does, and I really don't understand why he scales it by the negative z value.

I'd post a question in his blog, but it's filled up with spam posts. :?
Last edited by dcuny on Tue Feb 03, 2009 6:06 pm, edited 1 time in total.
Reason: Fixed link tag
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SSAO Questions

Postby dcuny » Sun Feb 01, 2009 11:33 am

Just a note - Wikipedia linked to a paper, I haven't seen before: Approximating Dynamic Global Illumination In Image Space. The video is here.

They include direct lighting by sampling the environment lighting at AO sample points, which is an idea I've been kicking around for a while. They also include perform one-bounce indirect lighting (similar to in Bunnell's paper).

They also perform depth peeling (storing multiple z values in the depth buffer) for resolving occlusion, which is another idea I've been kicking around. Only, unlike me, they actually implemented it. :P Of course, this only works to a point - as objects in the scene occlude other objects, the depth buffer eventually becomes exhausted. They use 2 depth layers.

Whether I'm clever enough to implement this remains to be seen. You can see by my prior questions that I get stumped fairly easily. :(
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SSAO Questions

Postby sascha » Mon Feb 02, 2009 9:35 am

The dot product between two vectors will yield the cosine of the angle between them.

Nope. A dot B = |A||B|cos(phi), i.e. the length of vector A, multiplied by the length of B, multiplied by the cosine of the angle between them.
You only yield the cosine if the two vectors have been normalized first. If A and B are identical, you'll basically get |A|^2, in case of a 3D vector x*x + y*y + z*z.
(A dot B for 3D vectors simply is A.x * B.x + A.y * B.y + A.z * B.z)
Note that javax.vecmath.Vector3D has a lenghtSquared() method that does just that, which is probably faster than calling dot(Vector3D v) on itself - in any case it's closer to self documenting code, in that the method name suggests what's going on, and if he insists on using the dot() method, a documentation comment would be appropriate (I know, I am the last person who should criticize others code documentation).

Any clue what p2 might mean? I don't understand what normalizing the sample point does, and I really don't understand why he scales it by the negative z value.

I don't know what it means, but what it does is (assuming we're talking about camera space) to move points that are off center closer to the camera. Take a piece of paper, and draw a scene from top-view. The camera in the center and a few random points in front of the camera. Now, the operation mentioned above keeps the directions constant, but moves points that are farther away from the camera's view-direction (i.e. the z-axis) closer to the camera (they get normalized and then multiplied by their z value). Or if you like, they get scaled by cos(phi), where phi is the angle between the vector pointing from the origin to p and the z axis. I'm not sure for what though... (and I hope that my explanation is right, but check it for yourself to be sure - there's no warranty ;-) )

You have yet to convince me that SSAO is of much use outside a game-engine. I still think that the pointcloud approach is quite as fast (in a production renderer), yields better (and more stable) results and is easier to control (and perhaps even easier to implement).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SSAO Questions

Postby dcuny » Mon Feb 02, 2009 12:58 pm

sascha wrote:Nope. A dot B = |A||B|cos(phi), i.e. the length of vector A, multiplied by the length of B, multiplied by the cosine of the angle between them.

OK, thanks!

...and I hope that my explanation is right, but check it for yourself to be sure - there's no warranty ;-) )

Again, thanks!

You have yet to convince me that SSAO is of much use outside a game-engine.

That's OK, I've yet to convince myself, either.

I still think that the pointcloud approach is quite as fast (in a production renderer), yields better (and more stable) results and is easier to control (and perhaps even easier to implement).

The point cloud is still going to have the same issues with offscreen occlusion. However, you're not going to have the problem that you get with SSAO, where all the backfaces have been discarded.

I'm not sure about the easier to implement bit, though. The point cloud is going to need a fairly complex structure to hold the information, and you're going to have to search it. SSAO uses a plain screen buffer, with the addition of normals - not complex at all. The code in the first example really is all there is to SSAO.

Yeah, I've implemented enough octrees and kd trees that I can pretty much do them in my sleep. They aren't that complex. SSAO also gives you some guarantee that the memory usage will be kept fairly low.

And keep in mind one of the reasons I'm going down this path is not because it's necessarily better, but there's a better chance I can actually implement it. :P

For "production quality" renderers, something like 3Delight is going to be impossible to beat.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SSAO Questions

Postby sascha » Mon Feb 02, 2009 2:09 pm

The point cloud is still going to have the same issues with offscreen occlusion.

Not necessarily. While you can e.g. use REYES to generate the point-cloud, you don't have to use the same camera. You could e.g. use a wider angle or move the camera backwards a bit, to also get points that otherwise would be off-screen or behind the camera. Alternatively you could also use an orthogonal projection of the entire scene to make the pointcloud, our you could even mix several pointclouds (IMHO it would make sense to have a precomputed pointcloud of all static objects, and blend in a per-frame pointcloud computed only for moving objects).

About the datastructures used for searching the pointcloud -> I have no idea. I once implemented a naive approach, it kinda worked for a small number of points (say less than 10000) but not for more, and it was quite slow. 3Delight on the other hand can easily handle a 100,000 points, and the AO step always requires just a few seconds. Its quite impossible that it accumulates the effect of each and every point for each and every pixel, but I really have got no idea how this could be optimized. It must be possible though (otherwise 3Delight wouldn't be that fast), so I assume that there should be some hints in one of the many papers you've mentioned :-)
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SSAO Questions

Postby John VanSickle » Mon Feb 02, 2009 2:11 pm

sascha wrote:I know, I am the last person who should criticize others code documentation.

I sometimes have the idea of not only removing comments from my code, but also to rename each label to a different combination of capital and lower-case letters. One label becomes xxXxxXxX. The next one becomes xXxxXxXx. And so on.

Or, even worse, a combination of numeral 1 and lower case l, or numeral 0 and upper case O. In some fonts these are indistinguishable characters.

so the code looks like:

Code: Select all
void l1l11l1l1::l11l1lll(short l1ll,short ll1l) {
    for(int l1ll1 = 0;l1ll1<l1ll;l1ll1++) {
        // similar evil follows
        // ...
    }
}
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: SSAO Questions

Postby sascha » Mon Feb 02, 2009 6:33 pm

I sometimes have the idea of not only removing comments from my code, but also to rename each label to a different combination of capital and lower-case letters. One label becomes xxXxxXxX. The next one becomes xXxxXxXx. And so on.

I think replacing class, method and variable names with random characters is a standard technique for obfuscation. But since we're talking about open source code, I think we're looking for exactly the opposite :-)

Personally I like the "self documenting code" approach described in the Code Complete book.
It suggests to not document the obvious but use meaningful class, method and variable names. Instead of documenting a block of code, it could also be refactored into a method with a meaningful name. He reasons that developers are trained to read code, not doc-comments, so if the code is written clearly, doc-comments should only be used to describe things the code itself can't.
So,
Code: Select all
i++; //increment i by 1
would e.g. become
Code: Select all
lineNumber++;
.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SSAO Questions

Postby dcuny » Mon Feb 02, 2009 9:03 pm

I've found it in my best interest to document even simple code lines like
Code: Select all
// Move to the next field
recordIndex++;
The main reason for this is to ensure that the code matches up with the intent. I've actually had someone track down a bug in my code because of exactly this sort of thing, where my comment claimed to be incrementing by one value, and the code was incrementing by another. (Note that in the code above, the comment refers to the field, but I'm incrementing the record index).

I also make the assumption that someone else is going to take over my code at some point. If the code is fully documented, it provides a bit more security to the person who's deciding if they want to take the task on. Of course, if the comments are useful and the variables are well named, it helps even more. ;)

On the question of using a point cloud, I think a Reyes renderer is particularly well suited for this task. The main problem is that it creates a huge amount of data, especially if you're dealing with production quality scenes, which is something I doubt I'll be dealing with. So you can't just hold all that in memory - it's got to be cached to disk somewhere, which adds an additional complexity. And the caching needs to be fairly smart, both in the size of the blocks, and tracking the most recently used blocks. This prevents unnecessary paging.

But you're still dealing with a lot of data, and putting it in an acceleration structure like a kd tree won't be enough. So you end up having to create an approximation layer on top of that, so you can use estimates of point clusters, instead of searching through all the points in a node. Again, that adds code complexity.

Blender uses octrees and spherical harmonics. Then again, they keep everything in memory, so it might not be the issues I'm worried about it being. Perhaps this is premature optimization on my part? :|

Point-based occlusion is still bound to the scene visibility. So you've still got the problem of only being able to occlude what's in the scene itself, so anything off-screen (for example, past the z clip plane or bounding pyramid) won't interact with the scene.

The other motivation is that SSOA can be "dropped into" any raster-based renderer, such as Inyo, without having to extensively rewrite the architecture. Then again, in theory I could add z-buffer shadows to Inyo, too. :P

The good news (for me) is that AO Isn't a primary effect, like shadows or reflections. It's more along the lines of specular highlights. It doesn't have to be accurate, it just needs to be plausible. I think you run into trouble when you try to use it to create effects like drop shadows.

My expectation is that SSAO will continue to progress in the immediate future, and we'll see some sort of hybrids appear. It didn't take people long to figure out that normals were necessary for high quality, and HSAO is a very clever development.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SSAO Questions

Postby sascha » Tue Feb 03, 2009 10:35 am

The main reason for this is to ensure that the code matches up with the intent.

I agree, but it wouldn't work for me. Right now I'm still in trial and error mode - so the half life of a block of codes is between a few hours and a few days. If I'd document everything that thoroughly, I'd spend more time on documenting obsolete code than anything else, and (that's the tricky part), I'd have to keep the docs up-to-date too.

So, one of my New Year's pledges is to browse through the code and document it thoroughly once it becomes fairly stable, but right now I focus on meaningful variable, method and class-names, because they kinda stay current automatically :-)

Point-based occlusion is still bound to the scene visibility

Wait a second please. One of us is missing something obvious here ;-)
As far as I understand, the pointcloud is usually created before rendering the scene, so you're free to compute it from any point of view. You can easily move the camera backwards and use a wider angle for dicing the pointcloud. Or use an orthographic projection for pointcloud creation, or any combination. And of course you'd want to switch off the hider, so backfacing and occluded parts of the geometry get diced into pointclouds as well. And you can modify the shading rate, to get fewer or more points.

As for the memory: I think it's safe to assume that even low-end desktop PCs or laptops have 1GB of RAM today, and anything that's used for rendering production quality images at 2K resolutions will have at least 4GB - and there's a lot of points that would fit into 1GB...
The nice thing about REYES is that it's a pipeline, so you don't have to keep the entire geometry in memory, so keeping a few million points (or disks) in memory for (and only during) the AO step shouldn't hurt.

I agree that the acceleration structures would be tricky, and I wouldn't start implementing anything before searching for papers that exactly describe some well-tested algorithm.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SSAO Questions

Postby dcuny » Tue Feb 03, 2009 6:02 pm

sascha wrote:If I'd document everything that thoroughly, I'd spend more time on documenting obsolete code than anything else...
Well, yes... documentation isn't a top priority. Writing good code is. (And it's good to hear you're finding time to work on JPatch!)

As far as I understand, the pointcloud is usually created before rendering the scene, so you're free to compute it from any point of view.

You're correct - the same sort of thing can be done with SSAO. For example, in Approximating Dynamic Global Illumination In Image Space, they use depth peeling and/or multiple cameras. However, at some point you've got to wonder whether when the "fixes" to make a technique work begin to outweigh the technique itself. :?

As for the memory...

I tend to write for lower-end machines, like the ones that I use. I probably underestimate the power of my current machine. But I'm always irritated by people who write great stuff that takes days to run. I'm not that patient. I had to re-render Dancing with Moai a number of times under a very tight deadline, so I appreciate the need for speed. I want the renderer to be "good enough" - but that's an always constantly moving target.

I was looking through the luxrenderer board the other day, and ran across the comment "I think with an athlon 1.2 CPU you won't be able to use lux at all imo...". Not be able to use it at all? Wow, that's some CPU hungry application! Not everyone has access to the latest quad core CPUs...

The nice thing about REYES is that it's a pipeline, so you don't have to keep the entire geometry in memory, so keeping a few million points (or disks) in memory for (and only during) the AO step shouldn't hurt.

This is the part I'm less sure about. Reyes is a pipeline because you typically can't fit all that geometry in memory. Granted, in a production environment, I suspect the real expense is often not the geometry, but the texture maps associated with that geometry.

Those "few million points" aren't discarded after they've been created. They need to be kept around, because they're used by the shaders to determine the occlusion. This is the main point where AO and SSAO differ - AO is dependent on the amount of geometry, where SSAO is fixed to the size of the render buffer.

I believe Pixar apparently uses spherical harmonics instead of disks. This allows a better sampling of the occlusion, since you can account for multiple directions, where in a hierarchy a disk ends up being an average of the occlusion.

Still, as you pointed out, Reyes can always bucket the geometry, so the AO structure shouldn't overwhelm the application.
I agree that the acceleration structures would be tricky, and I wouldn't start implementing anything before searching for papers that exactly describe some well-tested algorithm.

Yes, of course. I'm always scouring around, looking for a better/faster/easier way to render. :D

Besides, people keep coming up with clever twists. For example, both single bounce lighting and subsurface scattering can be simulated using AO. Instead of calculating the occlusion, Approximating Dynamic Global Illumination In Image Space uses the unoccluded points to calculate the contribution of global lighting, which turns out to have a number of benefits.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: SSAO Questions

Postby sascha » Tue Feb 03, 2009 8:01 pm

Well, my PC is more than 5 years old now, is a Pentium IV with 2 point something GHz (it wasn't the fastest one when I bought it, there have been 3+ GHz models around), and I used to have 1GB of RAM, but put in a second 1GB module some months ago. Since it's five years old, I think if JPatch runs fast enough on my machine it probably runs fast enough for most people. It doesn't mean that it wouldn't run on some 1GHz model with 512MB of RAM, but on the other hand, you wouldn't want to do realtime subdivision on a 286...
As for the graphics card: when my ATI card died a year ago I bought a relatively cheap nVidia 76xx. Nothing fancy, so again, if JPatch runs fast enough on that, it will on most PCs - I think.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: SSAO Questions

Postby dcuny » Wed Feb 04, 2009 1:25 am

I think I figured out what's happening with the second chunk of code.
ssao.png
ssao.png (16.46 KiB) Viewed 8662 times

The purple represents the depth buffer. We're looking to see if SP is an occluder for the point P. It lies behind the z buffer, so it's occluded. But it also lies behind point P, so it needs to be adjusted.

At this point, I probably would have simply replaced the SP z value with the z value from the depth buffer. Voila - SP is on the surface. But since they choose to do something much more complicated, I assume there's a good reason not to take my route. It probably has to do with the fact they've already tested to see if the point is in the radius of interest, and moving the point would require retesting.

Instead, they run a vector from the eye (0,0,0) to the sample point and normalize it. They then scale it by zd, which yields P2. Note that P2 is no longer behind P. A dot product test checks for self-occlusion, and we're good to go.

Once I sketched it out, it started to look awfully familiar, like Illustration 2 from Approximating Dynamic Global Illumination in Image Space, which I had just cited:
ssao2.png
ssao2.png (26.76 KiB) Viewed 8663 times

:roll:
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am


Return to Development

Who is online

Users browsing this forum: No registered users and 0 guests

cron