Morph Shapes

I've been wanting to do a pyramid-type level, and some better outdoor hills, so I added some features to the level editor in the last few days to help.

Basically the idea was to take a set of selected vertices, and morph them towards some pre-defined shape. So far I have added hemisphere, hemi-cube, and pyramid. I added two parameters to control the final result, one is the 'strength', and the other is the 'sharpness'.

The strength is a float where 0 does nothing, 1 morphs directly to the shape, and in between goes part-way there. You can use a negative strength in order to make a depression instead of a bulge.

The sharpness is also a float that is used as an exponent, similar to the Blinn or Phong lighting models, that makes the shape skinnier. Right now this only applies to the pyramid and the hemisphere.

Here are some shots of the results :





Light Map Seams

So, to continue on lightmaps - last time I mentioned trying to avoid seams in the lightmapping process. There are several reasons why you might get seams.

One is that you may have varying texel density across two chunks of your world. I described yesterday how my lightmap atlas packer never shrinks uv triangles, so this was a non-issue for AG.

Another more common reason is at chart borders. Each chart is a group of connected triangles with the same UV mapping. So, a square piece of the floor might be in one chart, and packed in the atlas such that it has no neighbors right next to it in the texture. Bilinear filtering will inevitably sample the texels bordering the chart. If you have some color there ( like black ) you will get a nice dark fringe around your lightmap.

One common 'fix' for this is to bleed out the valid colors onto the borders. This is a form of a dilation filter. One simple way to do it is : for each invalid texel, you look at its 8 neighbor texels. If any are valid ( ie contain real lightmap data ), then you copy that info here. Keep going until all neighbor texels are handled.

The problem here is that you are copying data, so if you have two floor chunks that happen to be split into separate lightmap atlases or charts so they neighbor each other in world space, but not in texel space, you will create a seam. If the lighting smoothly varies along the two chunks of the border, from attenuation or especially shadow boundaries, you will get a discontinuity.

The correct solution to this problem is, for each chart border texel in uv space, find the lightmap texel for the bordering chunk of geometry in world space, then find its lightmap info, then copy that texel locally. That way, for every chart border, you end up with a ring of texels that exactly match what would be there if the two charts were a single chart. You can even do this on the GPU, by drawing textured lines or textured points.

That is the best way, but that's not what I do! ;)

The main issue is the lighting & shadowing being discontinuous - so there should be some way to solve this by modifying the lighting code.

That leads into the question of how to actually do the lighting for a lightmap...

There are a couple of methods. One is to rasterize your triangles into UV space. This would seem to require a sw
standard triangle rasterizer routine, and one that matches the rasterization rules such that it will be textured properly. This seemed to me a huge set of corner cases around the border of the triangles, so I didn't want to do this.

A simpler way to rasterize a triangle is to take its bounding box in uv space, and just walk through each texel in
the bounding box, and do an in/out triangle test. You can be conservative on the bounding box by a texel on either
side if you wish - just be sure to skip already rasterized texels from chart neighbors.

To do the in/out test, you use barycentric coordinates. And these coordinates turn out to be the key to fixing the
lighting discontinuities on chart boundaries.

Barycentric coordinates are simply 2d coordinates on the plane of a triangle. They are in the range [0..1] when
inside the triangle, but can take on other values outside the triangle. My solution to the lighting problem
was simply to light border texels outside the chart border triangles with positions & normals extrapolated
slightly outside the triangle. For a flat floor or wall, this works perfectly, b/c you are just doing the same
lighting from the same position that you would be doing from the other chart. So the east chart lights a little
extra to the east, and the west chart lights from those same positions to the west, and you get the same values.

Now, how to find which texel corresponds to which triangle? This took me a while to get right. One idea is to
rasterze triangle IDs into the lightmap atlas, and then sample it. Of course, this doesn't help you find texels
outside of a triangle for border lighting.

So, what I did was to repurpose my Axis-Aligned Bounding Box Tree code, and make a 2d aabb tree in uv space for
each uv triangle. Then I dropped spheres with a radius slightly bigger than sqrt(2) radius, then found the first
contact. This effectively gives you the nearest triangle to each texel center. If I didn't find a tri, that
meant that I was not near a chart border, so did nothing. If I did find a tri, I found the barycentric coords
of this texel center relative to the triangle, and use that to extrapolate the position & normal in order to
perform lighting.

Something I should point out is that you really want your lightmaps to use interpolated vertex normals, and not
just face normals. Here is a shot where I was incorrectly using nvmeshmender ( ironic, I know ), so I wasn't
getting smoothing on the columns or the arch. This is similar to what you would get if you were doing regular
lightmapping without interpolated vertex normals.



Another issue to worry about is how to position your uv triangles with respect the the lightmap texture. I initially thought I wanted to snap the chart uv borders to texel centers, to prevent bleeding. This is wrong - you want to snap them to in between texels, so that they can blend with their neighbor texels.

By doing the AABB method, you don't have to rasterize your tris into uv space, because you are going from uv->triangle rather than the other way around.

Next up is to discuss chart packing, which is a variant on the classic bin-packing problem. I've had a few requests to talk about my water rendering method, so I'll plan on covering that over next week.