🔒 Locked

Fundamental 'flaw' with Relief/Parallax-Occlusion Mapping

Started by jollyjeffers Dec 5, 2006 at 4:15 PM 34 replies 27.6k views

Original Post

Dec 5, 2006 at 4:15 PM

Evening all, As those of you follow my developer journal probably know, I'm currently writing part of a book on lighting techniques with Direct3D 10. One of the parts I'm covering that I haven't experimented with before is Relief Mapping / Parallax Occlusion Mapping (which as far as I can tell are two names for pretty much the same thing). Whilst I have some copy-n-paste reference code I'm implementing the whole algorithm myself so that I fully understand it and, for obvious reasons, I'm not going to steal/publish someone else's code [wink] Anyway, I've had a strange recurring bug with my implementation that I'm starting to think is a fundamental flaw with the whole RM/POM algorithm. The ATI sample in the DX-SDK can be pushed to generate the same error given appropriate height maps and constants. I don't have time to draw and upload a proper image, so bare with the ASCII art [cool]:


              eye
              /
1.0 +--------/-----------------+
    |       /                  |
    |      /                   |
0.0 +-----x--------------------+
        pixel

So the basic idea is that for the currently rendered pixel we trace a ray and check for intersections. Easy. You can flip the various definitions around and get much the same results (e.g. defining the pixel as the bottom of the volume or the top of the volume), but in particular it's the wrapping issue that I'm seeing:


                 eye
                _/
1.0       +---_x---------------------
          | _/
          |/
        _/|
       /  |
0.0   /   +--------------------------

In the above (crap) diagram, if the target pixel is defined at the top of the volume then you get the situation where the ray "overshoots" and leaves the bounding volume. At the edge of a texture this tends to mean it wraps around and you pick up the pixels from the opposite edge of the height/normal map. If you define the pixel at the bottom of the volume then you can get the following case:


                                        eye
                                       _/
1.0   +-------------------------+    _/
      |                         |  _/
      |                         |_/
      |                        _/
      |                       / |
0.0   +----------------------x--+

Which is slightly less obvious, but it means that whilst tracing the ray you end up taking samples from the opposite side of the height map. It seems to me that you can't really avoid this problem - the heightmap scale and the viewing angle are key factors in determining whether you go out-of-bounds and they're both key inputs into the algorithm. All the sample code I've played with - reference material from research papers, ATI's sample etc... can demonstrate the above effects in some form. Seems that they get away with it by clever texture mapping and/or heightmaps (e.g. having a "wall" around the edge of the texture). Having a relatively small height scale makes it relatively difficult to spot this problem unless you really look for it. So, I'm done explaining my observations now - anyone care to comment? Who else has implemented these algorithms and either seen, or even better - disproved/solved this problem... Cheers, Jack

l0calh05t

Dec 5, 2006 at 11:00 PM

If i understand your post correctly, that's quite normal for paralax mapping, to prevent it you'll need something more complex such as view-dependent displacement mapping or generalized displacement maps. Both are per-pixel displacement mapping methods which solve this problem.

Matt Aufderheide

Dec 6, 2006 at 12:03 AM

can you explain this "view dependent displacement mapping" more? any links to info about these techniques?

Dragon_Strike

Dec 6, 2006 at 1:45 AM

isnt this easily solved by using a larger texture with offseted texture coordinates so that the the larger texture looks like the original but can use the extra information that is outside the face...

rick_appleton

Dec 6, 2006 at 3:12 AM

Note: I've never implemented any of this.

It definately sounds like a limitation of the algorithm. There's only a few things you can do in such cases:

1 wrap around to the other side of the texture
2 clamp to that edge
3 define special behaviour in the shader

It sounds like you (and the other algorithms) are doing 1, which seems erronous to me.
2 might be a better solution, and definately a quick fix if it 'works'. Obviously it won't be quite accurate, but then it shouldn't be incorrect either. Since you've already processed the boundary pixel, you know that there is 'nothing' outside it. So you might as well use that final value.
3 would be the best solution but might be difficult to implement. If I've got this right one of those two error cases (or both) should actually be discarded since the pixel you should see is off the edge of the texture (and so presumably off the edge of the mesh, if not tiling the texture (in which case the entire problem is moot) ).

Also, as far as I've understood it (although like I said, I've never looked into this stuff), relief is a somewhat more detailed version of parralax occlusion mapping. Not too sure why I think that though.

jollyjeffers

Dec 6, 2006 at 3:53 AM

Thanks for the replies everyone [smile]

Quote:
If i understand your post correctly, that's quite normal for paralax mapping

Quote:
It definately sounds like a limitation of the algorithm

That's good to hear - at least it's not something stupid I've done!

Quote:
isnt this easily solved by using a larger texture with offseted texture coordinates so that the the larger texture looks like the original but can use the extra information that is outside the face

Yes, having some sort of 'border' region built into the texture could possibly work but I don't think its a workable solution.

Firstly you'd need to start modifying your models and textures to suit the algorithm (easier said than done) and secondly it's likely to start introducing awkward cases where you specifically need parts of a texture to line up to specific geometry - e.g. a sign on a wall..

rick_appleton, your workarounds are much the same as what I'd been contemplating.

Quote:
1 wrap around to the other side of the texture

Yes, this is what mine and the other reference samples I've seen do. It is obviously the easiest, but it does generate the errors as described above.

Quote:
2 clamp to that edge

It sort of solves the problem but introduces a more noticeable artifact in places. In the areas where it'd normally wrap-around you get a stretched area that is actually MORE noticeable! Bit difficult to explain without an example image.

Quote:
3 define special behaviour in the shader

This is my current area of investigation. Generating the TS ray to trace is a rather trivial detail in mine and other implementations - I'm thinking it needs to be a lot more rigourous. The down-side is that it'll be a whole lot more expensive to execute [headshake]

Currently the algorithm just takes the intersection points with Z=1 and Z=0 (according to whether you want the target pixel at the top or bottom of the volume) and goes from there. What I'm thinking is that we also need to generate the intersection based on U=0/U=1 and V=0/V=1:

Instead of

+---------------+   _/ Z=1|               | _/|               |/|             _/||            /  |+-----------x---+ Z=0

We have:

+---------------+ |               |  |               |Z=0.5|             _/||            /  |+-----------x---+ Z=0

Which I suppose could be implemented in UV first and then solved for Z by considering it in the following (top-down view) terms:

               eye              _/+----------+_/|         _||       _/ ||     _/   ||    x     ||          |+----------+

+----------+|         _*|       _/ ||     _/   ||    x     ||          |+----------+

Just thinking out-loud really: does the above seem reasonable?

Cheers,
Jack

Jason Z

Dec 6, 2006 at 6:23 AM

Hi Jack,

What you are proposing is actually quite reasonable. You just have to modify the shader to only work in the tangent space bounds of (0,1), and then you will have to texkill whatever falls outside of those bounds.

For the ray entering the box at the near box plane (call it short) do what you have described - simply modify your starting height in the dynamic loop. Be careful to adjust your step size according to this parameter.

For the ray exiting the box without hitting the isosurface, you must check to see if the final offset coordinates are outside of your intended range. This should also be relatively simple, and you can use texkill to cull the pixel or use the alpha value set to zero if you are using an alpha test and/or alpha blending.

I think this has the potential to work. Be sure to post the results when you get them, and I'll try a couple things out today at work in parallel.

Also, clamping to the edges will simply extrude the isosurface at the edge of the texture out to as far as the ray goes outside the box. This might be acceptable if you put a two pixel boundary around the outside of the texture that is set to maximum depth. This would extrude just a flat plane, which may be acceptable in certain circumstances.

EDIT: I believe the distinction is that Relief Mapping uses a binary search while Parallax Occlusion Mapping uses a linear search. Both have pros and cons - speed vs accuracy and dependant vs non-dependant texture lookups.

bennyW

Dec 6, 2006 at 7:14 AM

Quote:

...and then you will have to texkill whatever falls outside of those bounds.

Yep, I was thinking the same thing for the top example Jolly presented.

And if you're outside the bounds looking in, maybe artificially place the eye vector so its lined up with the edge, that way the texture doesn't 'slide' toward you as you move further outside the bounds. The vector to eye won't be perfect when you're outside the bounds, but it might not make that much difference.

BennyW

jollyjeffers

Dec 6, 2006 at 8:36 AM

Quote:
You just have to modify the shader to only work in the tangent space bounds of (0,1), and then you will have to texkill whatever falls outside of those bounds.

I wasn't going to texkill, I was thinking about modifying the ray such that no pixels outside of the normal (0,1) range are sampled. Remove the need for the ray to be unit-length, probably consider it to be more a line segment than a ray even.

But I suppose, functionally, thats the same [smile]

Quote:
For the ray exiting the box without hitting the isosurface, you must check to see if the final offset coordinates are outside of your intended range. This should also be relatively simple, and you can use texkill to cull the pixel or use the alpha value set to zero if you are using an alpha test and/or alpha blending.

I don't think I'll be going with the pixels defined at z=1 on the top of the box. Not only does this special case seem harder to solve the very idea that the height-map is an intrusion rather than an extrusion is the opposite of all other techniques I've been using. I count two reasons to avoid it!

Quote:
Also, clamping to the edges will simply extrude the isosurface at the edge of the texture out to as far as the ray goes outside the box. This might be acceptable if you put a two pixel boundary around the outside of the texture that is set to maximum depth. This would extrude just a flat plane, which may be acceptable in certain circumstances.

Yup, from thinking about it I think it's the rarer case that it is acceptable rather than being a valid hack for the general case - call it a neat context-specific optimization.

Quote:
I believe the distinction is that Relief Mapping uses a binary search while Parallax Occlusion Mapping uses a linear search. Both have pros and cons - speed vs accuracy and dependant vs non-dependant texture lookups.

That does seem to be the most obvious implementation detail differing between the two. Although that strikes me as more implementation than algorithm - the results and general idea (ray tracing) is the same, just the way its achieved differs.

Quote:
And if you're outside the bounds looking in, maybe artificially place the eye vector so its lined up with the edge, that way the texture doesn't 'slide' toward you as you move further outside the bounds. The vector to eye won't be perfect when you're outside the bounds, but it might not make that much difference.

Not sure I see how modifying the eye vector will change anything. Care to elaborate more?

Quote:
I think this has the potential to work. Be sure to post the results when you get them

I'll either post them back to this thread or stick them in my journal. Provided they work of course [lol]

Will be interested to hear if you (or anyone else) comes up with alternatives and/or working solutions.

I've been doodling on paper this afternoon (dont have access to my dev machine at work [sad]):

float3 end_pos = float3( texcoord.xy, 0.0f ); // where it hits the bottom of the volumefloat3 ray_dir = normalize( viewdir ); // where it hits the top of the volumefloat3 start_pos = float3( end_pos.xy + ray_dir.xy, 1.0f );// clip to boundsstart_pos.xy = saturate( start_pos.xy );start_pos.z = length( end_pos.xy - start_pos.xy );// At this point we iterate from 'start_pos' through to 'end_pos'// and check for all intersections. // Iterations will be:float step_size = start_pos.z / NUM_SAMPLES;float3 curr_pos = start_pos;int samples_taken = 0;float prev_surf_height = start_pos.z;while( samples_taken < NUM_SAMPLES ){    float h = texHeightMap.SampleGrad( s, curr_pos.xy, dx, dy ).r;    if( h > curr_pos.z )    {        // we've crossed the boundary        samples_taken = NUM_SAMPLES;        // We now need to solve the intersection        // of the view and surface lines to        // determine the final point of intersection    }    ++samples_taken;    prev_surf_height = curr_pos.z;    curr_pos -= step_size;}

Or the code should be something like that - I've spent so much time on this I've almost memorised it [headshake]

Cheers,
Jack

bennyW

Dec 6, 2006 at 9:50 AM

Quote:

Not sure I see how modifying the eye vector will change anything. Care to elaborate more?

Yes, in my own implementation which is similiar to your top diagram, the further I move from edge, texels further into the texture get sampled.

Ex.

          eye           |           |    1.0       +X-------------------------          ||          ||             ||                ||         0.0       +--------------------------

 eye    \__           \__        1.0       +X-------------------------          | \__          |    \__          |       \__          |          \__0.0       +--------------------------

I was just suggesting that in these situations, keep the eye vector the same as the top case if you're outside the bounds to prevent the sliding.
The eye vector won't be correct, but the relative direction to most of the pixels may be close enough to suffice.

Ascii art is fussy :(

BennyW

sirob

Dec 6, 2006 at 10:16 AM

Here are a couple thoughts of ways to at least minimize this:

(these are very very rough ideas)

1) Instead of having the pixel at the top or bottom of the volume, move it to the center.

                                 _/ eye                               _/1.0   +----------------------_/-+      |                    _/   |      |                  _/     |      |-----------------X-------|      |                         |      |                         |0.0   +-------------------------+

I'm not too sure how good that would work out with your code, but it would reduce the possible error to half, although you would encounter both types.

2) You could do some kind of smart prediction when going outside the texture -- something like taking the last two samples, getting the difference between them and using that value to extrapolate outside the actual texture.
You'd obviously have to be extremely careful, and it would only reduce artifacts, and sometimes might cause more artifacts, but it's worth considering.

3) I'd reconsider having an "overlapping edge" around the texture. I had to use this when texturing terrain, and this was both simple and looked good. When you're using linear blending you'll be getting rough edges around texture seams, and using an overlapping edge completely removes this issue. At least for terrain, the system to do this might already be in-place.

4) Volume Textures and Cube Maps can sample past edges, I think. While this is surely sub-optimal, and would be very specific, if the terrain could be mapped to a volume texture instead of a number of regular ones you could seamlessly jump between them when sampling.

Anyways, hope this helps.

lonesock

Dec 6, 2006 at 11:35 AM

This is a fundamental flaw. I've seen 2 fixes.

1) for smoothly curving geometry, introduce 2 new parameters to your mesh, a "falloff" term in the u&v directions, which modulates the light ray to simulate the curvature of the surface at any given point. Only works for smooth models. See the section of "Curved Relief Mapping" here

2) the other thing I've seen (used for concave geometry, like the inside of a room, etc.) is modifying the fragment's z-depth so overlapping is actually done with the z-buffer. See the "Z-correct bump mapping" section here

regarding the differences between RM and POM, they both use linear steps as the 1st phase of the intersection search. The difference is that RM uses a fixed # of steps (so the step size is chosen so that in N steps it will reach the "bottom" of the texture), but in POM the number of steps is dynamically chosen so that rays which are pointing directly down get fewer steps (linear interpolation will work very well in that case, and you can't miss any features on the heightmap), but rays which are nearly tangential to the surface get a higher number of steps. This distributes the load over the different cases, so you can use more fragment horsepower where it's needed.

Other methods use variations of these (Steep Parallax Mapping) or are entirely different (Cone Step Mapping {wink wink}, and Radial Step Mapping {not out yet, more winking [8^)

zedzeek

Dec 6, 2006 at 5:04 PM

from memory, search the www.opengl.org advanced forum i believe this was discussed 1-2 years ago

jbarcz1

Dec 6, 2006 at 8:26 PM

I'm not sure if this is the case or not, but wouldn't the problem go away if your artists just make sure that the heightmap textures tile smoothly?

If not, then texkilling can definitely solve this problem, but it be worked around fairly well just by having artists be more careful with how they model their scenes. If you're careful to lay out your UVs in such a way that these boundary conditions aren't visible from any reasonable camera position, then you can work around the problem. This is one of the reasons why the building in the ATI toyshop demo had those large cement blocks on the corners.

l0calh05t

Dec 7, 2006 at 12:20 AM

View dependent displacement mapping link:
http://research.microsoft.com/users/lfwang/vdm.pdf

Jason Z

Dec 7, 2006 at 3:48 AM

I think I have to disagree with the general consensus here - the algorithm is not fundamentally flawed. Jack's original problem is that he doesn't want to sample beyond the texture's bounds, both on the far side as well as the near side. This is essentially trying to render the entire isosurface without any cutoff at the edges of the polygons. I did some work last night and produced the following image:

This is much the same as my normal implementation of parallax occlusion mapping, with four conditional statements added to show what I am talking about:

if ( finalCoords.x < 0 )
OUT.color = float4( 0, 1, 0, 0 ); // output green

if ( finalCoords.y < 0 )
OUT.color = float4( 0, 0, 1, 0 ); // output blue

if ( finalCoords.x > 1 )
OUT.color = float4( 1, 0, 0, 0 ); // output red

if ( finalCoords.y > 1 )
OUT.color = float4( 1, 0, 1, 0 ); // output magenta

As you can see from the image, only the surface represented by the heightmap is actually drawn. I used the multiple colors for clarity of what is happening - when each of the final texture coordinates goes out of range the pixel can be cancelled. To perform a finalized version of the shader, you could use:

clip( finalCoords );
clip( 1-finalCoords );

In this case, the colored areas of the image above would be removed leaving behind only the desired isosurface.

My implementation uses the heightmap to push down the surface, as opposed to Jack's which pushes up the surface. To render the part of the heightmap closest to the camera in the above image, I would simply need to render a box that would represent the volume of the desired surface. Then the box face that is facing the camera would render the remaining portion that is currently cut off by the leading edge.

The "push up" and "push down" methods are actually very close to equivalent, and can also be used in the same way. You would just have to render the box on top of the surface plane instead of below it.

Also, note that there isn't anything forcing you to use the domain of [0,1] for the texture coordinates either. If you have some geometry that will be using POM and tiling a portion of the texture, you can just add a per-vertex set of limits on the texture coordinates. This would remove any restrictions on your use of the texture.

I think parallax occlusion mapping is more than adequate for what Jack is trying to do, you just have to be willing to modify the implementation a little bit.

RAZORUNREAL

Dec 7, 2006 at 4:34 AM

Great post!

Quote:
Original post by Jason Z
The "push up" and "push down" methods are actually very close to equivalent, and can also be used in the same way. You would just have to render the box on top of the surface plane instead of below it.

Surely for the "push up" version, the outer edges edges of the actual surface would be cut off? I can see how it would be equivelant for anything concave, but in the convex case you are rendering a mesh smaller than the surface you wish to represent, so not all the required fragments would be processed.

Jason Z

Dec 7, 2006 at 4:46 AM

Quote:
Original post by RAZORUNREAL
Great post!

Quote:
Original post by Jason Z
The "push up" and "push down" methods are actually very close to equivalent, and can also be used in the same way. You would just have to render the box on top of the surface plane instead of below it.

Surely for the "push up" version, the outer edges edges of the actual surface would be cut off? I can see how it would be equivelant for anything concave, but in the convex case you are rendering a mesh smaller than the surface you wish to represent, so not all the required fragments would be processed.

Actually, by rendering a box (think of a bounding box for the heightmap surface) you are ensuring that any fragment that should be visible on the surface is drawn. This includes the push up and push down cases.

stevenmarky

Dec 7, 2006 at 5:34 AM

First of all, very nice image Jason Z!
I've not implemented it myself or read a lot about the theory (so sorry if I get this wrong).
But if I understand correctly Jason Z you would still have a similar problem to jollyjeffers depending on the height map used - in the picture you showed the center edge between the two quads is very high on the height map.
If it was low you would have some 'clipping' going on.

Edit, I drew a diagram and realised in most situations you wouldn't want that part drawn (yellow) anyway. The red square is the quad which is in front of the black square (which shows the maximum depth of the effect).

[Edited by - stevenmarky on December 7, 2006 10:34:36 AM]

jollyjeffers

Dec 7, 2006 at 8:43 AM

Firstly - apologies for the slow reply. I ended up getting pretty busy and didn't get a chance to do any work on this [headshake].

lonesock, some interesting ideas and links there. Thanks! I've come across mentions of similar things and read some of those papers but I might have a look through them again. Although, whilst mentioning them in my text is likely I doubt I'll have the time (nor page count) to cover them - I need to pick one algorithm and stick with it.

Quote:
search the www.opengl.org advanced forum i believe this was discussed 1-2 years ago

I've had a look through their forums before - I found them pretty difficult to search/navigate. Spent a few hours trying to dig up information on various methods but gave up in the end...

Quote:
wouldn't the problem go away if your artists just make sure that the heightmap textures tile smoothly?

Yes, you can either hide or eliminate much of these artifacts via clever texturing. But that just creates extra work for the artist and might prove difficult if the technology requires characteristics that conflict with what the artist is trying to represent. In short, its a work-around I don't much like [smile]

Quote:
View dependent displacement mapping link:
http://research.microsoft.com/users/lfwang/vdm.pdf

Having had a quick look at the paper I have vague memories of reading it at some point in the past. Might well have another read of it if I get time. Thanks for the link.

Quote:
To perform a finalized version of the shader, you could use:

clip( finalCoords );
clip( 1-finalCoords );

In this case, the colored areas of the image above would be removed leaving behind only the desired isosurface

I've implemented this method - seems to be a very simple solution to the problem. I like it [grin]:

My experiments with modifying the ray (as I previously suggested) have mostly failed. I'm pretty sure it's just my implementation is broken but it's a good hint that the modification isn't quite as straight-forward as I'd hoped. However the clipping method you suggest works fine apart from a couple of minor aliasing issues on the borders...

Quote:
Also, note that there isn't anything forcing you to use the domain of [0,1] for the texture coordinates either. If you have some geometry that will be using POM and tiling a portion of the texture, you can just add a per-vertex set of limits on the texture coordinates. This would remove any restrictions on your use of the texture.

I'd been thinking of utilizing a geometry shader to create proper clip-planes for arbitrary texturing. I don't think it'll work too well with neighbouring triangles but for boundary edges it should work a treat - and be completely transparent to the core application..

Jason - thanks again for your help/suggestions. Been most useful!

Cheers,
Jack

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.