I made a level with a couple of ramps that you could also walk under. When I went to light it, I got some very strange artifacts with the lighting. When I looked at it closely, it looked as if the top of the ramp were somehow fighting with the floor underneath the ramp.
Because the ramp was connected to the floor, shallow, and facing mainly up, it was included in the same chart ( lightmap triangle group ) as the floor. The ramp top and floor were overlapping in UV space.
I verified this with Ultimate Unwrap3D after dumping out the level geometry, then set about finding a solution.
My algorithm was a local greedy recursive algorithm that, for each neighbor tri not already claimed in a chart, recursively called it and its neighbors to add them to the chart group.
What I needed was some sort of more global overview that could detect & prevent overlaps in uv space. Obviously a triangle is not going to have an overlap problem with its neighbor, if the uv mapping is reasonable, b/c there's no way to overlap a tri with a connected tri without flipping it over, so there needed to be some sort of persistence on a per-chart basis to find overlaps.
My first attempt was to have a per-chart AABB tree for each existing triangle, do a quick test for overlaps, then do triangle->triangle testing geometrically. This extra memory during the recursive call was causing a stack overflow, and I wasn't totally confident that the overlap testing math would handle the common case where two tris make a quad, and touch but don't overlap.
So, I decided to software rasterize instead. For each chart, I clear a 512x512 area of memory, and then write an 'x' into each spot containing a triangle. Before adding each additional neighbor tri, I check it by walking through the triangle pixels and testing for the fill color first. If there is no conflict, then I put 'x' in to the triangle's pixels.
Once I got this working as expected, I ran into an unexpected problem. Basically, I was getting non-overlapping areas, but since the tris came in to the grouping algorithm in random order, I got strange chart shapes like jigsaw puzzle pieces. This was causing havoc with the texel lightmap code which implicitly assumes that a nearby texel in lightmap space corresponds to a nearby texel in world space. This caused no lighting errors on the actual lightmap texels, but on the chart border pixels, which would bleed in due to bilinear filtering.
I then realized that one option to reduce the problem was to take advantage of the fact that the triangle order was random. In other words, I was free to order the triangles in any way I wanted, and to traverse the neighbors in any order, so I sorted the 3 neighbors of each triangle to chart those neighbors with the most similar normals first.
This solved the strange shape issue, but now there were nice straight seams.
The last fix was to add a feature to the level editor. The user can add a trigger, really only needed at the start of a ramp that could cross over the floor later on, that marks which triangles should be in their own chart. These marked charts are handled first, and then the normal algorithm proceeds afterwards.
I'm happy to report that this fixes all known issues.....