Lightmap generation with Radiosity

Does nobody know this algorithm/ graphics-technic or is my english too bad that nobody understand my problem? =(

I've never done anything like this, but you could try looking into the Half-Life or Quake compile tools. I know that the Half-Life community has produced highly improved versions of the original tools, so it's very likely that they improved the original lightmap generating code as well.

I'm currently playing with light map generation/radiosity as well. At the moment I use the following method to generate the light map atlas:

1.
First, for each face I calculate the set of all adjacent faces.

2.
Then, for each face find the major normal axis. I based this on this article, although I use all 6 axii (+x, -x, +y, -y, +z, -z). For the light map coordinates of each vertex of a face convert the vertex position in world space into light map coordinates, see article. Also, apply the scaling factor as shown in the article
For Example: face normal is on the +x axis: use (v.z, -v.y) as the texture coordinates vor vertex v. For -x the coordinates become (-v.z, -v.y).
At this point, you have all faces sorted into one of 6 sets, one set for each major axis. Each vertex of the faces should now also have preliminary lightmap coordinates based on their vertex position. Although the texture coordinates may not be valid at this point, the relative sizes of the occupied texture space resembles the relative size of the faces.
Note: if you share vertices between faces (easier to calculate adjacency), be sure to clone vertices that are used on different axii!

3. Create non-overlapping clusters of faces in each axis-group. Clustering is quite useful to remove as many seems between faces as possible by putting neighbouring faces tightly together on the texture atlas. This step is actually not very difficult if you have adjacency lists available. This step is done for each axis-related set of faces.

- You have a set of faces R that contains all faces not yet put in a cluster. This initially contains all faces for the current axis face group
- You have a queue Q that contains the list of faces that still need to be considered for the current cluster
- You have a list L that contains all faces in the current cluster.

The algorithm goes like this:

while(R is not empty) { face first = any face in R Q.enqueue(first) C = new list while(Q is not empty)    face f = Q.dequeue()   R.remove(f)   C.add(f)   for each face a adjacent to f     if R.contains(a)       Q.add(a)  store C as a new cluster somewhere

When the algorithm terminates, you have a bunch of clusters, each consisting of a list of adjacent faces that won't overlap. You should calculate the bounding rectangle of the faces' texture coordinates and probably sort the clusters by decreasing size.

3. Pack clusters in texture
I used the algorithm found here to pack the clusters into one or more textures. Works nicely.

There are several issues not handled here (dealing with faces or clusters too large for a texture), but this should get you started.

Edit: as an example, here's the result of the procedure described above when applied to a typical teapot mesh:


Clusters have green borders, faces are red with white borders. You see that some clusters waste quite some space, that's where possible improvements are. Besides that you at least have something to start with. Optimizing the face atlas can always be done later without much influence on the rest of the radiosity processor.

And here's a second (though useless) example: mapping a terrain with 524k triangles to a single light 1024x1024 map:
With the terrain in memory, atlas generation took about 15 seconds: 3.5 seconds for finding the adjacency, 7.5 seconds for determining major axii and clustering and about 4 seconds for packing the atlas. Implemented on .NET 3.5, running on a Intel E6750 dual core machine.


[Edited by - VizOne on August 21, 2009 2:10:04 AM]

Thanks for your help =)
That sounds logic and helpful.