🔒 Locked

Pack Triangles tightly

Started by Gagyi Jan 8, 2007 at 2:12 PM 10 replies 1.6k views

Original Post

Jan 8, 2007 at 2:12 PM

Well, my game reached the level that i need lightmapping on my buildings, because vertex lighting looks horrible. I understand how to lightmap, but all the algorithms i found needs UV coordinates. I tried to find how to calculate them, with no success. I found an article how to get a triangles's vertices' UV coordinates properly, but still dont know how to pack these triangles in an efficient way. So Im stuck, missing the final link. So the question is, how to put triangles on a 256x256 texture, in a way that the unused texels number will be minimal? [Edited by - Gagyi on January 10, 2007 12:02:59 PM]

Zakwayda

Jan 8, 2007 at 2:20 PM

Quote:
Original post by Gagyi
So the question is, how to put triangles on a 256x256 texture, in a way that the unused texels number will be minimal?

This is usually referred to as a bin packing problem. It's well researched, and lots of people have written bin packers for lightmaps, so it shouldn't be too hard to find code and/or references.

I think I have some bin packing code lying around somewhere. I don't know if it's the best possible implementation and/or algorithm, but it should be suitable for most purposes. I can post it if you like.

(Actually, I think I posted it in a thread here along with some images a while back. I'll see if I can't find the thread...)

Zakwayda

Jan 8, 2007 at 2:25 PM

Haha, found it :) The linked thread includes my bin packing code along with some images showing the output, as well as links to some other references.

'Hope that helps.

SimmerD

Jan 8, 2007 at 4:07 PM

jyk's code looks pretty good, but here's another I wrote a couple of years ago. I'm using it offline for building my lightmaps, and realtime ( at a low resolution ) to pack shadows into a shadow atlas in my game.

I recommend the FirstFit, rather than the BestFit function, as it's almost as good and way faster.

You can change the Rects operator< in order to make it sort by area, perimeter, their average, or something else...

Good luck!

#pragma once#include "types.h"#include <vector>#include <algorithm>namespace Pack{    struct Rect    {        int32 id;        int32 w;        int32 h;        int32 x;        int32 y;        Rect( const int32 aid, const int32 aw, const int32 ah, const int32 ax, const int32 ay ) : id ( aid ), w( aw ), h( ah ), x( ax ), y( ay )        {        }        Rect(): id(0), w(0), h( 0), x(0), y(0)        {        }        bool operator<( const Rect& rhs ) const        {            if ( max( w,h ) == max( rhs.w, rhs.h ) )            {                //if ( ( w + h ) == ( rhs.w + rhs.h ) )                {                    if ( ( w * h ) == ( rhs.w * rhs.h ) )                    {                        return id < rhs.id;                    }                    return ( ( w * h ) > ( rhs.w * rhs.h ) );                }                //return ( ( w + h ) > ( rhs.w + rhs.h ) );            }            else            {                return ( max( w,h ) > max( rhs.w, rhs.h ) );            }        }    };    struct rect_compare : public std::binary_function< const Rect&, const Rect&, bool >    {        bool operator()( const Rect& lhs, const Rect& rhs ) const        {            return ( lhs < rhs );        }    };    struct Atlas    {        int32 mWidth;        int32 mHeight;        typedef unsigned char Cell;        std::vector< Cell > mCells;        bool Initialize( int32 w, int32 h )        {            mWidth = max( 1, w );            mHeight = max( 1, h );            Clear();            return true;        }        void Clear()        {            mCells.clear();            mCells.insert( mCells.begin(), mWidth * mHeight, 0x0 );        }        int32 GetCell( int32 x, int32 y ) const        {            if ( ( x >= 0 ) && ( x < mWidth ) && ( y < mHeight ) && ( y >= 0 ) )            {                return ( mCells[ y * mWidth + x ] );            }            return 0;        }        bool SetCell( int32 x, int32 y )        {            if ( ( x >= 0 ) && ( x < mWidth ) && ( y < mHeight ) && ( y >= 0 ) )            {                if ( mCells[ y * mWidth + x ] != 0 )                {                    assert( false );                }                mCells[ y * mWidth + x ] = 1;                return true;            }            return false;        }        int32 GetScore( const Rect& r ) const        {            int32 total_score = 0;            // go through top & bottom            for ( int32 xx = 0; xx < r.w; ++xx )            {                total_score += GetCell( xx + r.x, r.y );                total_score += GetCell( xx + r.x, r.y + r.h - 1 );            }            // check left & right edges, skipping corners, which were done above            for ( int32 yy = 1; yy < r.h - 1; ++yy )            {                total_score += GetCell( r.x, r.y + yy );                total_score += GetCell( r.x + r.w - 1, r.y + yy );            }            return total_score;        }        bool IsValid( const Rect& r ) const        {            for ( int32 yy = r.y; yy < r.y + r.h; ++yy )            {                for ( int32 xx = r.x; xx < r.x + r.w; ++xx )                {                    if ( mCells[ yy * mWidth + xx ] != 0 )                    {                        return false;                    }                }            }            return true;        }        float GetFractionUsed() const        {            if ( mCells.size() == 0 )            {                return 1.0f;            }            int32 total = 0;            for ( size_t t = 0; t < mCells.size(); ++t )            {                if ( mCells[ t ] != 0 )                {                    ++total;                }            }            return ( (float)total / ( (float)mCells.size() ) );        }        bool PlaceRect( const Rect& r )        {            for ( int32 yy = r.y; yy < r.y + r.h; ++yy )            {                for ( int32 xx = r.x; xx < r.x + r.w; ++xx )                {                    mCells[ yy * mWidth + xx ] = 1;                }            }            return true;        }        bool FindFirstFit( Rect& r )        {            int32 best_score = INT_MAX;            Rect test_rect( r );            bool bFound = false;            for ( int32 yy = 0; yy < mHeight + 1 - r.h; ++yy )            {                test_rect.y = yy;                for ( int32 xx = 0; xx < mWidth + 1 - r.w; ++xx )                {                    test_rect.x = xx;                    if ( GetCell( test_rect.x + test_rect.w - 1, test_rect.y + test_rect.h - 1 ) != 0 )                    {                        xx += test_rect.w;                        continue;                    }                    if ( GetCell( test_rect.x + test_rect.w - 1, test_rect.y ) != 0 )                    {                        xx += test_rect.w;                        continue;                    }                    if ( IsValid( test_rect ) )                    {                        r = test_rect;                        return true;                    }                }            }            return ( false );        }        bool FindBestFit( Rect& r )        {            r.x = 0;            r.y = 0;            int32 best_score = INT_MAX;            Rect bigger_rect;            bool bFound = false;            Rect test_rect( r );            bigger_rect.h = r.h + 2;            bigger_rect.w = r.w + 2;            for ( int32 yy = 0; yy < mHeight - r.h; ++yy )            {                test_rect.y = yy;                bigger_rect.y = yy - 1;                for ( int32 xx = 0; xx < mWidth - r.w; ++xx )                {                    test_rect.x =  xx;                    bigger_rect.x = xx - 1;                    if ( GetCell( test_rect.x + test_rect.w - 1, test_rect.y + test_rect.h - 1 ) != 0 )                    {                        xx += test_rect.w;                        continue;                    }                    if ( GetCell( test_rect.x + test_rect.w - 1, test_rect.y ) != 0 )                    {                        xx += test_rect.w;                        continue;                    }                    if ( !IsValid( test_rect ) )                    {                        continue;                    }                    const int32 this_score = GetScore( bigger_rect );                    if ( this_score < best_score )                    {                        best_score = this_score;                        r.x = test_rect.x;                        r.y = test_rect.y;                    }                }            }            if ( best_score < INT_MAX )            {                return true;            }            else            {                return false;            }        }    };};

Zakwayda

Jan 8, 2007 at 4:19 PM

Quote:
Original post by SimmerD
jyk's code looks pretty good, but here's another I wrote a couple of years ago.

Yeah, the code I posted is nothing special - it was just an ad hoc solution to a particular problem I needed to solve. It sounds like your implementation is more comprehensive.

Anyway, at least the OP has plenty of material to work with now :)

Gagyi

Jan 10, 2007 at 8:50 AM

These are really interesting resources, and now i can start to implement one of them, really thank you two.
(sorry, i should have to search more, but i didnt even knew what i am looking for :S)

P.S: i found this thread really helpful too.

SoftwareGuy256

Jan 10, 2007 at 9:34 AM

One reason I hate posting on gamedev is because people don't answer the question. These posts don't really address the problem about packing triangles. It is a little more complicated than just solving some theoretical "bin packing problem" which already assumes that the triangles are packed into quads.

The method I use involves grouping planar triangles into quad regions, heuristic to calculate texel area, atlasing to a texture, then using shaders to force mip-levels and generate UV coordinates on the fly to solve trilinear filtering problems.

Gagyi

Jan 10, 2007 at 10:21 AM

Yep, i want to pack triangles, but packing rectangles is good *enough*. But, if anyone has a solution to pack triangles, please post it

SoftwareGuy256

Jan 10, 2007 at 10:57 AM

Read the paper on hierarchial face clustering. There's also a paper on applying that technique to speed up radiosity using this technique. There are several other papers that extend this result to seamless atlasing.

Sneftel

Jan 10, 2007 at 5:46 PM

Quote:
Original post by SoftwareGuy256
It is a little more complicated than just solving some theoretical "bin packing problem" which already assumes that the triangles are packed into quads.

The method I use involves grouping planar triangles into quad regions

Hm.

Gagyi

Jan 11, 2007 at 9:18 AM

Okay, people, no need to flame.
I just tought about it, and i dont have individual triangles, i have triangles grouped (because of texturing stuff), so the rectangle handling seems really good. Thank you again, i really appreciate your help.

P.S.: I like this forum, I got an answer in less than 24 hours. Nice ;)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.