A conceptual question... how would YOU do this?

Sage
Posts: 1,199
Joined: 2004.10
Post: #1
I'm implementing a dynamic decal system that follows the camera and randomly splats decals over the static scene (terrain/rocks/etc) to add visual complexity. Think of it like you'd think of foliage -- it only needs to exist within some visible radius of the camera.

My decals work really well, actually, but for the situation where they overlap. After all, they're being randomly placed, and are bound to overlap now and then.

Here's a screenshot of a debug render for a little idea of what I'm describing.
[Image: Terrain-2009-09-10-02.png]

Here's some context:

1) I use multi-pass lighting. Render ambient, then render a lit pass for each enabled light. This means that the lit passes use additive blending.

2) The decals use a fixed polygon offset to "float" on top of the static scene.

As a result, two problems tend to show up.

1) When two decals overlap, there can be a bright stripe where, during the lit pass, their overlapping area is additively drawn on itself.

2) I depth sort transparent objects by distance to camera, but this means that as the camera moves around, the "top" decal changes, so you see popping.

Now, my question is how you might fix this. I see two options... I could prevent overlapping decals, or I could detect overlap and give one decal a "higher" polygon offset than the other. I'm not certain how well this would scale, but it might be the only way forward.

Or something else. Any opinions on this? I'd prefer a solution which allows overlap.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #2
The two simple solutions I can think of:
* Generate your decal spots similarly to a worley texture. Split the world into cubes. For each cube, use the cube's coordinates to generate a random offset within itself. If you inset each decal enough, you won't get any overlaps. In my experience, it's pretty hard to spot the grid artifacts in a worley texture at least.
* Use n offsets randomly. This will reduce the number of visible overlaps to 1/n. Not really sure how many distinct overlaps you could get away with.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #3
Skorche Wrote:The two simple solutions I can think of:
* Generate your decal spots similarly to a worley texture. Split the world into cubes. For each cube, use the cube's coordinates to generate a random offset within itself. If you inset each decal enough, you won't get any overlaps. In my experience, it's pretty hard to spot the grid artifacts in a worley texture at least.

This sounds hard Wink


Skorche Wrote:* Use n offsets randomly. This will reduce the number of visible overlaps to 1/n. Not really sure how many distinct overlaps you could get away with.

brilliant -- absolutely brilliant. I'll fine tune a bit, but I shouldn't need more than 4 to 8 levels.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #4
Another advantage of the first method (splitting the world up into chunks and splatting decals within that chunk) is you can save the seed for each chunk. That way you can "randomly" generate the exact same decals each time you visit the same area.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #5
TomorrowPlusX Wrote:This sounds hard Wink

It's actually really really easy.
The basic idea that I used was to use a permutation table to look up random offsets based on the coordinates of the cell you were considering. The following code is only 2D, but is easily extended to 3D:
Code:
int cell_index = permute[permute[x&0xFF] + (y&0xFF)];
float off_x = (float)permute[cell_index]/256.0f;
float off_y = (float)permute[cell_x]/256.0f;

x and y are the integer indexes of the cell in question. permute is a permutation table containing all the numbers from 0-255 in a scrambled order. Using this, there are only 256 possible random offsets, and the pattern repeats every 256x256 block of cells, but that's generally big enough that you can't see that much at once. Just use a bigger permutation table if you want more variation.

What I used it for was generating cellular textures like this: http://www.blackpawn.com/texts/cellular/default.html
The offsets were used as the centers of the cell areas. By generating the points this way it was really easy to find the closest point. Just look at the 9 squares around the one were the pixel was. I never remember seeing any artifact that made it obvious that it was generating the points on a grid like it was, and a texture big enough to show 256x256 cells would be massive.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
akb825 Wrote:Another advantage of the first method (splitting the world up into chunks and splatting decals within that chunk) is you can save the seed for each chunk. That way you can "randomly" generate the exact same decals each time you visit the same area.

FWIW, I've already got that aspect covered -- my distribution code always generates the same random distribution.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #7
Skorche Wrote:It's actually really really easy.
The basic idea that I used was to use a permutation table to look up random offsets based on the coordinates of the cell you were considering. The following code is only 2D, but is easily extended to 3D:
Code:
int cell_index = permute[permute[x&0xFF] + (y&0xFF)];
float off_x = (float)permute[cell_index]/256.0f;
float off_y = (float)permute[cell_x]/256.0f;

x and y are the integer indexes of the cell in question. permute is a permutation table containing all the numbers from 0-255 in a scrambled order. Using this, there are only 256 possible random offsets, and the pattern repeats every 256x256 block of cells, but that's generally big enough that you can't see that much at once. Just use a bigger permutation table if you want more variation.

What I used it for was generating cellular textures like this: http://www.blackpawn.com/texts/cellular/default.html
The offsets were used as the centers of the cell areas. By generating the points this way it was really easy to find the closest point. Just look at the 9 squares around the one were the pixel was. I never remember seeing any artifact that made it obvious that it was generating the points on a grid like it was, and a texture big enough to show 256x256 cells would be massive.

This is interesting, even if only for the fact that I could use this for some more naturalistic procedural noise generation. I'm currently using perlin noise to bias distribution of foliage density & color -- it looks great. Seems like a smart person could use this in a similar manner.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #8
As a followup -- I used the idea of random depth levels and it works excellently. It took a little tweaking. In the end I used my scene graph's draw order biasing as well as polygon offset. But it works, and it looks pretty great ( in my opinion )

[Image: Terrain-2009-09-11-05.png]
Quote this message in a reply
Moderator
Posts: 453
Joined: 2008.04
Post: #9
Yeah, that definitely looks awesome! Keep up the good work Grin

Howling Moon Software - CrayonBall for Mac and iPhone, Contract Game Dev Work
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #10
BTW, that "Worley" texture thing looks an awful lot like Perlin noise.

With using 2D Perlin or Simplex noise, you can achieve the same effect, by using a grid for the decals, and having the noise displace the vertices. As the noise field is continous, you should never get overlapping decals if your distortion isn't too high at the grid's frequency.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #11
DoG Wrote:BTW, that "Worley" texture thing looks an awful lot like Perlin noise.

With using 2D Perlin or Simplex noise, you can achieve the same effect, by using a grid for the decals, and having the noise displace the vertices. As the noise field is continous, you should never get overlapping decals if your distortion isn't too high at the grid's frequency.
They're essentially the same thing, you just use a different noise function within the grid.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #12
For what it's worth, I actually want the decals to be able to overlap. The random polygon offset stuff has helped with popping, but my current multipass additive lighting isn't compatible with this -- the lighting passes overlap and bright spots show up.

So, I'm in the process of a small refactoring of my rendering pipeline to support an opt-in "coalesced" render mode which should allow decals to overlap & be lit and still render beautifully.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #13
OK, so as a final followup, a couple notes.

1) I implemented a slightly more expensive render technique for overlapping decals which allows arbitrary overlaps without any popping or artifacts or lighting problems. It works great, but is a little more expensive.

2) I implemented a simple hash-space sphere-collision tester to quickly determine which decals are likely to require the more expensive render technique. It works quite well, the overlapping decals get the fancy render technique, the rest get the simpler faster technique.

Plus, I've been wanting for a while to write a simple hash space based collision tester, and it was actually kind of fun.
Quote this message in a reply
Post Reply