3D Engine 11 - Light and lighting methods 3 (lightmaps)
Well, hello !
It's 21th of december .. wait! It's 22th of december, 1:51 o'clock to be precise. I'm in time pressure and need to translate two more tutorials, possibly write third one so i won't guff about how i've been lately ...
Today we're goinng to implement lightmapping - the very famous method since Quake I that started lightmap mayhem. Lightmaps themselves are textures, used for storing lighting values across all surfaces of our world. (it should be obvious none of them is repeated) They are most times low resolution, because they would take up too much memory. Advantage of lightmaps is they can be pre-computed. Disadvantage is - they're static. You can connect them with stencil to get nice dynamic-shadowed world, thus - with static lights. So, what are we rally going to do ?
It's 21th of december .. wait! It's 22th of december, 1:51 o'clock to be precise. I'm in time pressure and need to translate two more tutorials, possibly write third one so i won't guff about how i've been lately ...
Today we're goinng to implement lightmapping - the very famous method since Quake I that started lightmap mayhem. Lightmaps themselves are textures, used for storing lighting values across all surfaces of our world. (it should be obvious none of them is repeated) They are most times low resolution, because they would take up too much memory. Advantage of lightmaps is they can be pre-computed. Disadvantage is - they're static. You can connect them with stencil to get nice dynamic-shadowed world, thus - with static lights. So, what are we rally going to do ?
- Precompute lightmaps and store them some way
- Render scene with normal textures modulated by lightmaps
classic lightmap disadvantage - notice,
shadow is kind of edgy (low lightmap resolution)
How to map lightmap
As i told you, we need lightmaps all over our world. Next we need to have (aproximately) same size of texels on all surfaces and in ideal case we'd like texels to be square. (it means use different sizes of lightmaps for different-sized surfaces) Otherwise the result look quite ugly. The simplest way to do it is so-called planar mapping. We get surface normal, find it's greatest component and select apropriate plane. (it will be the closest one of coordinate planes xy xz yz) We will project our surface to this plane in order to get rectangle, bounding it. You propably got the idea that rectangle should be the lightmap. We can derive mapping coordinates from relative positions of surface vertices and imaginara texture rectangle. It won't be so easy, we're having couple of troubles:
The second problem is a bit more complicated. You can solve it by forcing lightmaps to be nearest power-of-two size, but this yields non-square texels (and of course not uniform-sized) Some of newer 3D accelerators can handle non-power-of-two textures. Shall we ? I think not. We will solve it by packing more textures into a few big texture pages, say 1024×1024. It has many advantages, even for 3D accelerators:
How to fill lightmaps
Any possible way. We can use whatever we'd like to use. In our example we will use Lambertian equation (get texel position in worldspace, create vector to light, meassure angle between this vector and normal, yielding diffuse-shaded surfaces) and then cast ray to light to see if texel is shadowed. We'll do single check, resulting in 0 / 1 visibility values, but you can do more checks and get nicely antialiassed shadows.
Next example will be radiosity so i'm planning to use this code for it as well and do some HDR lighting ...
How to do animated lightmaps
That's simple. Have you ever played System Shock 2 ? Walking trough hulls of abandoned Von Braun starship, blinking and flashing lights everywhere - that was pretty scary, not mentioned all these sounds ! Perfect game. But back to lightmaps. In this kind of games there's set of all lightmaps with some lit texels for every light. Then you can separately modulate lightmaps and make some of lights blinking, pulsing or flashing - whatewer you want. I'm in temptation to write something like this as well. Maybe i'll get some idea.
Next, there's another kind of animated lightmaps. You have some light motion animation and generate set of lightmaps for every frame of animation. Then you have animated lightmaps again. You can try doing some swaying lights or so ...
You can do semi-dynamic lightmaps - make one more layer of lightmaps and recompute it's contents each n-th frame. You can do also some simple shadows for moving lights with heavy help of some BSP-like technique to speed-up raytracing. You can also try projecting geometry in front of surface to it's lightmap to get shadows, but it's slow for high-poly scenes.
How to render lightmaps
When drawing surface, we have texture and corresponding lightmap. When drawing pixels, you modulate texture (diffuse color) by lightmap. Disadvantage of this system is you have lighting values in <0, 255> range. We'd like to be able to make texture shine when it's lightmap is too bright, instead of clamping it's values. We have today some formats for HDR support (16 bit per channel or floats) so we can display values in zero-infinity range. HDR is used by newer games such as Half-Life 2:
As i told you, we need lightmaps all over our world. Next we need to have (aproximately) same size of texels on all surfaces and in ideal case we'd like texels to be square. (it means use different sizes of lightmaps for different-sized surfaces) Otherwise the result look quite ugly. The simplest way to do it is so-called planar mapping. We get surface normal, find it's greatest component and select apropriate plane. (it will be the closest one of coordinate planes xy xz yz) We will project our surface to this plane in order to get rectangle, bounding it. You propably got the idea that rectangle should be the lightmap. We can derive mapping coordinates from relative positions of surface vertices and imaginara texture rectangle. It won't be so easy, we're having couple of troubles:
- we have triangles, not surfaces (ie. single lightmap should contain more trialngles)
- our lightmap propably won't ever be power-of-two sized
The second problem is a bit more complicated. You can solve it by forcing lightmaps to be nearest power-of-two size, but this yields non-square texels (and of course not uniform-sized) Some of newer 3D accelerators can handle non-power-of-two textures. Shall we ? I think not. We will solve it by packing more textures into a few big texture pages, say 1024×1024. It has many advantages, even for 3D accelerators:
- we won't waste too much space when using texture pages instead of many nearest pow-2 textures
- it will reduce number of texture switches, which can be expensive with hardware accelerators
- we will get our uniform square texels we always wanted !
How to fill lightmaps
Any possible way. We can use whatever we'd like to use. In our example we will use Lambertian equation (get texel position in worldspace, create vector to light, meassure angle between this vector and normal, yielding diffuse-shaded surfaces) and then cast ray to light to see if texel is shadowed. We'll do single check, resulting in 0 / 1 visibility values, but you can do more checks and get nicely antialiassed shadows.
Next example will be radiosity so i'm planning to use this code for it as well and do some HDR lighting ...
How to do animated lightmaps
That's simple. Have you ever played System Shock 2 ? Walking trough hulls of abandoned Von Braun starship, blinking and flashing lights everywhere - that was pretty scary, not mentioned all these sounds ! Perfect game. But back to lightmaps. In this kind of games there's set of all lightmaps with some lit texels for every light. Then you can separately modulate lightmaps and make some of lights blinking, pulsing or flashing - whatewer you want. I'm in temptation to write something like this as well. Maybe i'll get some idea.
Next, there's another kind of animated lightmaps. You have some light motion animation and generate set of lightmaps for every frame of animation. Then you have animated lightmaps again. You can try doing some swaying lights or so ...
You can do semi-dynamic lightmaps - make one more layer of lightmaps and recompute it's contents each n-th frame. You can do also some simple shadows for moving lights with heavy help of some BSP-like technique to speed-up raytracing. You can also try projecting geometry in front of surface to it's lightmap to get shadows, but it's slow for high-poly scenes.
How to render lightmaps
When drawing surface, we have texture and corresponding lightmap. When drawing pixels, you modulate texture (diffuse color) by lightmap. Disadvantage of this system is you have lighting values in <0, 255> range. We'd like to be able to make texture shine when it's lightmap is too bright, instead of clamping it's values. We have today some formats for HDR support (16 bit per channel or floats) so we can display values in zero-infinity range. HDR is used by newer games such as Half-Life 2:
Beautiful, isn't it ? (Half - Life 2 uses lightmaps in combination with
shadow-buffer which is (in result) pretty similar to stencil) We will do HDR lightmaps in next tutorial
with radiosity.
Now i'm gonna write example. Wait a minute, because i'm gonna debug it.
I was writing it slow for you to understand it. First we'll look at function, used for grouping faces together as they will be stored in lightmaps:
It's quite simple. We have our Group structure to store face groups. What's it doing ? We call Group_Faces(), pass it world (all vertices should be already transformed if necessary -> all matrices are unit) and function is examinating the world, face by face. For each of them it visit faces in already existing groups to check if there is coplanar neighbour. If ther is, it add face to group and also search if new face connected two or more groups together. In that case, groups are merged into one. You can also see some Check_GroupSize() calls. It checks if group is still small enough to fit into lightmap without stretching. Otherwise new group is set. Imagine a big house - all floors are coplanar, ie. they would all connect in single group of size of the house. That would require too big texture which we can't have. But we can have the same amount of smaller textures to divide parts of floor into ... So we create groups up to some maximal size.See Check_GroupSize() code:
This function uses minimal and maximal coordinates of group faces triangles to determine size. When creating new group, we determine mapping plane, coplanar with one of coordinate planes xy, xz or yz. How to choose one of these ? Simply select the gratest component of normal of some face in group (no matter which one, they have all the same normal in group, remember ?) In case x, we choose yz. Right ? Next from knowledge of plane we tell vectos v_u and v_v, showing directions (in worldspace) of increasing u and v lightmap coordinates. Next we can project our imaginary rectangle dimensions by performing dot product of v_max - v_min and v_u, respectively v_v vectors. I'll show you function, reponsible for computing these vectors right after inserting first face into new group:
Function Add_FaceToGroup() is just face-list manager function, but for code completeness:
This should be pretty clear. Function b_Same_Vertex() was already in stencil example and all it does is compare two vertices positions and return true / false. b_Neighbour_Face() is slightly modified out from stencil example aswell. There's a bit different coplanar face detection:
The result of calling described functions is you have all faces connected to groups as they will have single lightmap per group. You can see it on image below where color represents group id:
Now i'm gonna write example. Wait a minute, because i'm gonna debug it.
I was writing it slow for you to understand it. First we'll look at function, used for grouping faces together as they will be stored in lightmaps:
|
It's quite simple. We have our Group structure to store face groups. What's it doing ? We call Group_Faces(), pass it world (all vertices should be already transformed if necessary -> all matrices are unit) and function is examinating the world, face by face. For each of them it visit faces in already existing groups to check if there is coplanar neighbour. If ther is, it add face to group and also search if new face connected two or more groups together. In that case, groups are merged into one. You can also see some Check_GroupSize() calls. It checks if group is still small enough to fit into lightmap without stretching. Otherwise new group is set. Imagine a big house - all floors are coplanar, ie. they would all connect in single group of size of the house. That would require too big texture which we can't have. But we can have the same amount of smaller textures to divide parts of floor into ... So we create groups up to some maximal size.See Check_GroupSize() code:
|
This function uses minimal and maximal coordinates of group faces triangles to determine size. When creating new group, we determine mapping plane, coplanar with one of coordinate planes xy, xz or yz. How to choose one of these ? Simply select the gratest component of normal of some face in group (no matter which one, they have all the same normal in group, remember ?) In case x, we choose yz. Right ? Next from knowledge of plane we tell vectos v_u and v_v, showing directions (in worldspace) of increasing u and v lightmap coordinates. Next we can project our imaginary rectangle dimensions by performing dot product of v_max - v_min and v_u, respectively v_v vectors. I'll show you function, reponsible for computing these vectors right after inserting first face into new group:
|
Function Add_FaceToGroup() is just face-list manager function, but for code completeness:
|
This should be pretty clear. Function b_Same_Vertex() was already in stencil example and all it does is compare two vertices positions and return true / false. b_Neighbour_Face() is slightly modified out from stencil example aswell. There's a bit different coplanar face detection:
|
The result of calling described functions is you have all faces connected to groups as they will have single lightmap per group. You can see it on image below where color represents group id:
faces in groups
Now when all faces are divided, we should finish the mapping precedure.
We have all we need - we have min and max coordinate of each group geomethry, we have selected
mapping plane we can project gemoetry to and we have vectors showing u and v (worldspace)
direction. We're able to compute texture coordinates with knowledge of this. We can also compute
position of each lightmap texel (in worldspace again) so we can compute the very lightmap textures.
We set up next structure to keep some values for mapping and proceed with it:
... to explain it a bit. Our Generate_Map_Coords() function work with array of all groups and calculate mapping info structure for every of them. There belong lightmap worldspace origin v_org (origin = left upper corner) and two vectors v_u and v_v, showing directions of lightmap edges along u and v axis. Size of lightmap in worldspace (f_width, f_height) is also important for telling how much place in texture we will need. Next we pass every vertex of every face in this group and calculate his lightmap u, v coordinates. Now we have our rectangular textures (well, it could be square as well, but it's not going to happen too offen). Now we need power-of-two textures so it's time for some texture-page creating function
How to do that ? Don't think about it too much. You can't make it absolutely effective anyway. The simplest way is to make array of values, telling you how high every column of raster is occupied by textures. When inserting another texture, we will select some column and check lightmap width columns right of it. Find the greatest value from the table and check if that value plus lightmap height is below texture page height (so our texture fit). It's quite simple, but today i've problems with explaining so i better write it down in C:
So ... we have another structure with dimensions, frontline and image data buffer. Next here is p_Lightmap() we are not interested in, because all it does is to properly initialize structure i've just described. But the next function is much better in terms of features.
b_InsertTile() is attempting to place tile of some width and height into texture page. It's using parameters p_x and p_y for returning it's position in raster. The returning value of function simply translates into true = our tile fit or false = try it with another texture page or create a new one. I think the function is pretty self-explanatory so i won't describe it any further ...
I'd like mention my concern in one-pixel rectangles. We will want to filter our lightmap when rendering it ando our bilinear filter require some neighbour pixels so we will make this one-pixel rectangle arround lightmap and what is important - fill it by neighbouring values of lightmap texels. Then we can calmly sleep and dream about lightmap filtering ...
We also compute some odd transfromation matrix. Why ? What do we need to transform ? Our lightmap coordinates are computed for our texture rectangle, where [0, 0] is it's top left corner and [1, 1] is the opposite. But we've just moved that rectangle int bigger texture page so we need to recompute texture coordinates for all faces this rectangle is mapped to (all faces in current group) Now we finally have raster coordinates so nothing can stop us from writing simple routine that would calculate lightmap contents for us. We'll handle this simple. Lambert's rule, cast one ray to light, add ambient and over. The result is this:
Raytrace_Tile() gets group, mapping info, geomethry, raster position (and raster width, so we can compute index), raster buffer itself and ambient light color. On the beginning of the loop, position of texel in worldspace is computed. But it's position on that imaginary texture rectangle so we imediately project it on plane faces are lying on. All what remains is code, computing illumination of each pixel. I didn't add code for raytracing, find it in example ... Anyway, we're doner with computing lightmaps and we're going to see how to display them !
|
... to explain it a bit. Our Generate_Map_Coords() function work with array of all groups and calculate mapping info structure for every of them. There belong lightmap worldspace origin v_org (origin = left upper corner) and two vectors v_u and v_v, showing directions of lightmap edges along u and v axis. Size of lightmap in worldspace (f_width, f_height) is also important for telling how much place in texture we will need. Next we pass every vertex of every face in this group and calculate his lightmap u, v coordinates. Now we have our rectangular textures (well, it could be square as well, but it's not going to happen too offen). Now we need power-of-two textures so it's time for some texture-page creating function
How to do that ? Don't think about it too much. You can't make it absolutely effective anyway. The simplest way is to make array of values, telling you how high every column of raster is occupied by textures. When inserting another texture, we will select some column and check lightmap width columns right of it. Find the greatest value from the table and check if that value plus lightmap height is below texture page height (so our texture fit). It's quite simple, but today i've problems with explaining so i better write it down in C:
|
So ... we have another structure with dimensions, frontline and image data buffer. Next here is p_Lightmap() we are not interested in, because all it does is to properly initialize structure i've just described. But the next function is much better in terms of features.
b_InsertTile() is attempting to place tile of some width and height into texture page. It's using parameters p_x and p_y for returning it's position in raster. The returning value of function simply translates into true = our tile fit or false = try it with another texture page or create a new one. I think the function is pretty self-explanatory so i won't describe it any further ...
I'd like mention my concern in one-pixel rectangles. We will want to filter our lightmap when rendering it ando our bilinear filter require some neighbour pixels so we will make this one-pixel rectangle arround lightmap and what is important - fill it by neighbouring values of lightmap texels. Then we can calmly sleep and dream about lightmap filtering ...
We also compute some odd transfromation matrix. Why ? What do we need to transform ? Our lightmap coordinates are computed for our texture rectangle, where [0, 0] is it's top left corner and [1, 1] is the opposite. But we've just moved that rectangle int bigger texture page so we need to recompute texture coordinates for all faces this rectangle is mapped to (all faces in current group) Now we finally have raster coordinates so nothing can stop us from writing simple routine that would calculate lightmap contents for us. We'll handle this simple. Lambert's rule, cast one ray to light, add ambient and over. The result is this:
|
Raytrace_Tile() gets group, mapping info, geomethry, raster position (and raster width, so we can compute index), raster buffer itself and ambient light color. On the beginning of the loop, position of texel in worldspace is computed. But it's position on that imaginary texture rectangle so we imediately project it on plane faces are lying on. All what remains is code, computing illumination of each pixel. I didn't add code for raytracing, find it in example ... Anyway, we're doner with computing lightmaps and we're going to see how to display them !
baked texture
Before we get to that, i'd like to mention ... yes, i can mention one-pixel
frame again, because now it's time to fill it, but i wnated to mention blur. Since we're dealing
with point lights, the shadows might me quite hard so the simplest way to soften them is to apply
some blur to lightmaps (but separately ! not to whole texture page) With blur it looks better but
you mustn't blur it too much, otherwise there will be noticeable differences between edges of
neighbouring surfaces due to blur.
Tool is designed to be run from command line, where the first parameter
is compulsory ant contain filename of .3ds world. Another (optional) parameters are "-axxxxxx", where "xxxxxx" is hexadecimal ambient color,
next "-qx" where "x" is float multiplier of texture size againist world size (.5 is very reasonable, but it depends on your world scale),
Next is "-rx" where "x" is texture page resolution (default 512) and eventually "-bx" where "x" is radius
of blur (0 = no blur) ... Program work for a moment, plotting dot for each processed group and then
store lightmaps as bitmaps plus geomethry as .mesh file (don't try to find format description, i've just
created it) while .3ds doesn't contain any useful information (but cameras, animations, etc ...)
Now we'll proceed to rendering with lightmaps. Normally it's nothing complicated, but i've decided not to create 256-coloured lightmaps to perform optimalisation i've introduced for textures neither bilinear interpolation which is quite slow on that P133 back at home. It's time to learn something about dithering ...
Dithering
Dithering is method where color transitions are substituted by dispersing them. What does it mean ? We're not going to compute slow color transition for bilinear filter. We'll use advantage of our eye - some pattern of two different colors may appear as solid area of another color. That is exactly what we want to achieve ... And the result is very fast. Very maginifed it look like this:
Now we'll proceed to rendering with lightmaps. Normally it's nothing complicated, but i've decided not to create 256-coloured lightmaps to perform optimalisation i've introduced for textures neither bilinear interpolation which is quite slow on that P133 back at home. It's time to learn something about dithering ...
Dithering
Dithering is method where color transitions are substituted by dispersing them. What does it mean ? We're not going to compute slow color transition for bilinear filter. We'll use advantage of our eye - some pattern of two different colors may appear as solid area of another color. That is exactly what we want to achieve ... And the result is very fast. Very maginifed it look like this:
dithered lightmap
It's screenshot from near-wall, you can see several kinds of patterns, used for transition between texels.
How to do that ? We need some table, used for dispersing texture coordinates. I've managed to
get 4x4 dithering table form some old 256-color crap. What does it contain ? There are fractions in
range <0, 1), systemathically spread accross the table, which we will add to lightmap coordinate.
Where do we get values to index table ? It won't be texture fractional values this time. It will be
screen coordinates. Yes ! We'll take x and y of pixel, calculate index as if you were
texturing screen with that table and disturb u-v coordinates. I've been talking about single table,
but it's obvious we need two tables for both u and v coordinates. The second table is
constructed simply by reversing order of elements from first one. I think i've told you enough to
understand this piece of source:
NOn the beginning we have our tables. They're fractional numbers <0, 15/16> in fixed point. The function below is our classical texture loop, but there's a new fragment, computing dither table index out of screen position and then use it when getting lightmap texel. As it have texel color it modulate texture color with it and move on next pixels ...
Example can switch between three filter modes: texture and lightmap are dithered (F9), texture is bilinear filtered, lightmap dithered (F10) and in the end i've written even function where both, texture and lightmap are bilinear filtered (F11). But the result isn't as different as i'd expected:
|
NOn the beginning we have our tables. They're fractional numbers <0, 15/16> in fixed point. The function below is our classical texture loop, but there's a new fragment, computing dither table index out of screen position and then use it when getting lightmap texel. As it have texel color it modulate texture color with it and move on next pixels ...
Example can switch between three filter modes: texture and lightmap are dithered (F9), texture is bilinear filtered, lightmap dithered (F10) and in the end i've written even function where both, texture and lightmap are bilinear filtered (F11). But the result isn't as different as i'd expected:
bilinear filtered lightmaps
dithered lightmaps
dithered lightmaps with quincunx filter - nearly no difference from bilinear filter
What to say as conclusion ? I hope i haven't made too much of mistakes, but
it's 4:22 AM what justice me (or i hope so :o)) So ... see you later (when i sleep enough) Yes ! And
i'd forget to put here download of next s-buffer engine, this time with lightmaps.
well ... see you again ...
-tHE SWINe-
-tHE SWINe-
Valid HTML 4.01