   Overlapping problem when generating UVs for a lightmap
  So I’m trying to generate a single lightmap texture for an entire polygonal scene, but first I must generate the texture coords for my polygons of course. I’ve already implemented this into my little demo, but I’m having a problem with overlapping (which I will explain in a second) . I’ve read a bunch of articles on how to generate the uv coords, and I’m pretty sure I understand it all, its just a few simple steps:1)Using the polygon’s normals (an absolute version of the normal) , find which axis they are primarily facing, and project them into 2d space2)Find the minimum and maximum UV coords for your entire scene. because the range of your polygon’s texture coords might be way out of range of the lightmap texture, subtract the mimumum UV coord from all your uv coords.3)Find the difference between minimum and maximum UV coord. Now divide all your texture coords by that difference so all your tex coords are in a 0.0f to 1.0f range4)I should be done calculating the texture coords for my lightmap.But here’s my problem, Lets say I have a polygon and it’s normal is ( 1, 0, 0 ) so we would use the Y and Z from the polygon’s position to copy into it’s UVs, so in that case the polygon’s verticies X is ignored when figuring out its texture coords. With one polygon for one lightmap that works just fine, but lets say I have 2 polygons in one lightmap, and they both fall in the same place in 3d space except the X is different (think of a box, the front and back of it would be mapped to the place on the texture)Does anyone Know what I mean or what I can do to fix multiple polygons texture coords getting mapped to the same place?If you care to see how I’m doing this, you can see my code: unsigned int i, j;MapObjectT* obj;MapFaceT* pFace;// GENERATE THE UVSfor( i = 0; i < uNumObjects; i++ ){obj = &pObjectArray[i];for( j = 0; j < obj->uNumVerts; j++ ){pFace = &obj->pFaceArray[j/3];if( pFace->vAbsNormal.x >= pFace->vAbsNormal.y && pFace->vAbsNormal.x >= pFace->vAbsNormal.z ){obj->pLightMapArray[ j ].x = obj->pVertexArray[ j ].z;obj->pLightMapArray[ j ].y = -obj->pVertexArray[ j ].y;}// Does the polygon primarily face along the Y-axis?else if( pFace->vAbsNormal.y >= pFace->vAbsNormal.x && pFace->vAbsNormal.y >= pFace->vAbsNormal.z ){obj->pLightMapArray[ j ].x = obj->pVertexArray[ j ].x;obj->pLightMapArray[ j ].y = -obj->pVertexArray[ j ].z;}// The polygon primarily face along the Z-axiselse{obj->pLightMapArray[ j ].x = obj->pVertexArray[ j ].x;obj->pLightMapArray[ j ].y = -obj->pVertexArray[ j ].y;}}}// FIND THE MIN AND MAX UVSVec2 minUV = pObjectArray[0].pLightMapArray[0];Vec2 maxUV = pObjectArray[0].pLightMapArray[0];for( i = 0; i < uNumObjects; i++ ){obj = &pObjectArray[i];for( j = 0; j < obj->uNumVerts; j++ ){if( obj->pLightMapArray[j].x < minUV.x )minUV.x = obj->pLightMapArray[j].x;if( obj->pLightMapArray[j].y < minUV.y )minUV.y = obj->pLightMapArray[j].y;if( obj->pLightMapArray[j].x > maxUV.x )maxUV.x = obj->pLightMapArray[j].x;if( obj->pLightMapArray[j].y > minUV.y )maxUV.y = obj->pLightMapArray[j].y;}}// MAKE THE UVS FIT ON A ( 0.0f to 1.0f ) rangeVec2 uvDiff = { 0.99f / (maxUV.x-minUV.x), 0.99f / (maxUV.y-minUV.y) };for( i = 0; i < uNumObjects; i++ ){obj = &pObjectArray[i];for( j = 0; j < obj->uNumVerts; j++ ){obj->pLightMapArray[j].x -= minUV.x;obj->pLightMapArray[j].y -= minUV.y;obj->pLightMapArray[j].x *= uvDiff.x;obj->pLightMapArray[j].y *= uvDiff.y;}}
  I was just thinking about this myself.  The problem with your approach so far is that you aren''t looking to see if other polygons are mapped to the same place in texture space.  You can either prevent them from overlapping in the first place, or detect overlaps.  To my mind, it''s easier to prevent overlaps.Here is my approach ( haven''t coded it yet, but I think it will work ) :1) For each triangle, calculate its face normal and normalize it.  Classify it into one of 6 UV projection directions - one for each major axis direction +-X, +-Y, +-Z.2) For every triangle ( not polygon ) in your scene, create an edge -> 2 triangle data structure.  Match up edges of the triangles with the 2 triangles that share the edge.  The matching criteria should be :  a) The two faces must share the same UV projection direction  b) The edge must match up in terms of xyz position3) When all edges are in the list, pick an edge to start with ( doesn''t matter which ), create a new chart, and find all of its neighbor faces and add them to the chart as well.  Recursively or iteratively find each of the neighbor''s neighbors, etc and add them to the chart, too.  Basically you are walking between faces via the edges.  For each edge you process, and remove the edge from the edge->face list.When you run out of neighbors, that chart is complete.  Now pick the next leftover edge from the edge->face list, and repeat the process to create the next chart.  If you have very complex gometry, you may end up with some charts of only a single triangle, altough these should be rare. 4) The chart list is a group of connected triangles that will all share a section of the lightmap.  Each wall or floor, for instance, will tend to end up in the same spot in UV space.  Overhangs or overlaps will automatically end up elsewhere, because you don''t combine faces with different UV projections in the same chart.  This prevents something like a brick sticking out of the wall at an angle from sharing lightmap texture coordinates with the wall below.The other possible overlap scenario is when something is floating in the air in front of the wall.  In this case, there are no connecting edges, so the floating object will get its own chart.5) Once all triangles are removed from the list and added to the chart list, you can actually allocate UV coordinates.6) For each chart, you have a list of triangles. Just find their 3d bounding box.  Project along their shared UV projection axis, and you have a unique 2D UV mapping.7) You''ll want to pack your charts into a big texture, known as an atlas.  I''m planning on treating my charts as solid rectangles for packing purposes, using their 2d bounding box, so I''ll be giving up some texture space, but saving hassle-factor.  I''m planning to use this idea for packing the charts into an atlas :http://www.blackpawn.com/texts/lightmaps/default.html;  OK, I think I got it now, Basicially in a short recap, this is what I think I have to doInstead of just using the normals of all the triangles to project them into UV Coords, use the normals and edges to put all the triangles into groups, and all the triangles in a group must share an edge and thier normal''s must classify into the same group ( like all +X primarily or all -Z or whatever )So now that all the triangles are all in groups, go through each group and project the triangles in a 2d manner so they have some UV coords. Now go through each group and find the min and max UV coord. So now we basicially have a bounding box around each group and we know how much space it takes up.So now we go through the list of objects again and now try and fit them neatly together, so their isn’t too much space between each group, and no group should overlap. So We set all our group’s UV coords all to sit at the origin by subtracting their group’s min UV coord to each triangle in the group. Now all our group’s triangles UV’s sit right at the origin, and we know where their UV’s bounding box (defined by min and max) is, go through all the groups again and start shifting their UV’s  over so none of their bounding boxes overlap. Now after this process is all done all we should have unique UV coords for all our triangles, so to make sure all the UV coords fit on a 0.0 to 1.0 range we just find how much space they take up, and dividing all the UV coords by that number.Does this Sound like a good plan?;  Yes, this looks exactly right.The next things to keep in mind are to handle the lightmap borders and/or mip-maps.If you want bilinear filtering ( and you do ), then you want either leave a 1 texel border around your object containing the closest lightmap value, or pull in your uvs at the edges of the group by 1/2 a texel.The border technique has the advantage that it doesn''t distort your lightmap at all, and also scales up to handle mip-maps.  For each extra mip-level you want beyond the main texture, you need to double your # of border texels.  I plan on having 1 or 2 mip-maps, so I will have to pack my lightmaps with an extra 2 or 4 texel border.  The next lowest mip-level will have a 1 or 2 texel border, etc.;  Oh alright, I think I got it now, thanks a bunch for all the help, I''ll try implimenting this stuff and see how things work out, thanks again for all the help :-) - John Moses ;  Woo! OK, I got it working :-)http://www.3denvy.com/moses/lightmap1.jpgYes, it's supposed to do this right now But it really sucks right now ;-)Basicially the reason it sucks is because the way I'm packing them onto the image, you'll see how horrible it is ;-)http://www.3denvy.com/moses/lightmap2.jpgBasicially when I map the polys I calculate each group's min and max UV, and then move all the groups UV's to the origin, then I go through the groups again and subtract the minUV from the maxUV, so the max UV is now correct to where the new UVs are at (on the origin!)So now Here is where I need some help, how do I shift the UVs over? so they dont overlap? I basicially did a for loop through all the groups and added the previous's maxUV to the currents uv coords, and thats why I got the horrible map :-) for( i = 1; i < uNumObjects; i++ ){prevObj = &pObjectArray[i-1];obj = &pObjectArray[i];for( j = 0; j < obj->uNumFaces; j++ ){pFace = &obj->pFaceArray[j];for( k = 0; k < 3; k++ ){pFace->pLightMaps[k].x += prevObj->maxUV.x;pFace->pLightMaps[k].y += prevObj->maxUV.y;}}obj->maxUV.x += prevObj->maxUV.x;obj->maxUV.y += prevObj->maxUV.y;}I Have a few ideas for better ways to shift over the UVs but I keep thinking and it looks like the only way I'll get it working is by trial and error, start with the first group, leave it at the origin, then step to the second group, try and place it at the origin, if it doesnt fit, shift it over just a bit on the x, repeat this process and it it still doesnt fit, then shift it a bit on the y, and keep trying, till everything in on the screenGot any better ideas?   [edited by - jMoses on February 5, 2004 8:44:17 AM] [edited by - jMoses on February 5, 2004 8:45:39 AM];  Hi,I''ve implemented the same technique already, and there is a nasty case that will make tris share uv space.  Imagine a spiral ramp (not a staircase).  Every tri in the ramp will be in the same normal classification (eg, +ve y) and will be connected to neighbouring tris, but because it''s a spiral, they still overlap when projected onto the 2d plane.I didn''t notice this problem and actually shipped 2 games before realising! Obviously our scenes just didn''t have geometry that showed up that case.Cheers,Matt Halpin ;  Ehehe, Ah well, I''ll just make sure no level has any scenarios like that, Im not about to try and solve that problem via code, i''ll just fix it in my level editor  - John Moses ;  Matt, good point.  I thought it seemed too simple! jmoses, did you check out that lightmap packing link I sent you?  That should do a better job than your approach. ;  I just realized that you could do the Separating Axis Theorem in 2D for the U,V triangles and detect that case.  Then you could split along the edge before the overlap, and make two charts. Then go through each remaining chart and check all other triangles against other connected tris.  You can actually skip the immediate neighbors, but its probably not worth it.If any of the tris overlap, then once again split into two charts, etc.