PtexExtractor/PtexLayout.cpp

//**************************************************************************/
// Copyright (c) 2010 Autodesk, Inc.
// All rights reserved.
//
// Use of this software is subject to the terms of the Autodesk license
// agreement provided at the time of installation or download, or which
// otherwise accompanies this software in either electronic or hard copy form.
//
//**************************************************************************/
// DESCRIPTION:
// CREATED: August 2010
//**************************************************************************/

#include <math.h>
#include "PtexLayout.h"
#include <QtGui/QWidget>
#include <QtGui/QGridLayout>

#define RES_TOL (0.1f)

// RTTI macro, needed for each class.
IMPLEMENT_SCLASS( PtexLayout, Layout, "ptexlayout", 5 );

// Default constructor
PtexLayout::PtexLayout( void ) :
    m_eDistribution( this, "distribution" ),
    m_fDensity( this, "density" ),
    m_sTexelCount( this, "texelcount" )
{ 
    m_eDistribution.SetName( QObject::tr("Texel Distribution:") );
    m_eDistribution.SetToolTip( QObject::tr("Controls how the sample points are distributed across the surface") );
    m_eDistribution.AddItem( QObject::tr("Uniform") );
    m_eDistribution.AddItem( QObject::tr("Based on Face Size") );
    m_eDistribution.AddItem( QObject::tr("Based on UV Size") );
    m_eDistribution.AddItem( QObject::tr("Use PTEX Setup") );
    m_eDistribution = 0;

    m_fDensity.SetName( QObject::tr("Density:") );
    m_fDensity = 0.5f;

    m_sTexelCount.SetName( QObject::tr("Number of texels:") );
    m_sTexelCount = "100000";
    m_iDesiredTexelCount = 100000;
};

// Create the user interface widget for the layout, which consists of a single widget at this moment, the quality slider.
QWidget *PtexLayout::UserInterface( void )
{ 
    QWidget *w = new QWidget;
    QGridLayout *l = new QGridLayout;

    QLabel *t = new QLabel( QObject::tr("Ptex resolution options") );
    QFont f = t->font();
    f.setBold( true );
    t->setFont( f );
    l->addWidget( t );

    // If there are multiple attributes, they can be added to the QGridLayout object the same way. All added attribute will appear on the UI in a 
    // different row.
    l->addWidget( m_fDensity.CreateEditorWidget( NULL, 150 ) );
    l->addWidget( m_sTexelCount.CreateEditorWidget( NULL, 150 ) );
    l->addWidget( m_eDistribution.CreateEditorWidget( NULL, 150 ) );
    w->setLayout( l );        
    return w;
};

// Calculate the area of a triangle using Heron's formula
float TriangleArea( const Vector &vC0, const Vector &vC1, const Vector &vC2 )
{
    float a = (vC0-vC1).Length();
    float b = (vC0-vC2).Length();
    float c = (vC2-vC1).Length();
    float s = (a+b+c)*0.5f;
    return sqrtf(s*(s-a)*(s-b)*(s-c));
};

// Main function, it processes the list of the given target surfaces, and collects the reference points on them.
void PtexLayout::ProcessSurface( SubdivisionLevel *pSurface )
{
    bool bFiltering = m_eDistribution != distCustom;
    InitializeResolution( pSurface );

    // Indicate that a section of reference points has begun. Each mesh will have its own section.
    BeginSection();

    if ( pSurface->Type() == Mesh::typeQuadric )
    {
        // Loop through all the faces of the mesh.
        for ( unsigned int f = 0; f < pSurface->FaceCount(); f++ )
        {
            int iHRes = 3, iVRes = 3;
            CalculateQuadResolution( f, iHRes, iVRes );
            int iHSize = 1<<iHRes, iVSize = 1<<iVRes;

            // Loop through the points of the grid.
            for ( int u = 0; u < iHSize; u++ )
                for ( int v = 0; v < iVSize; v++ )
                {
                    // For each point on the grid we create a reference point, and call the ProcessSurfacePoint function.
                    TargetLocation l;
                    l.m_aLayoutData[dataURes] = u+(iHRes<<24);
                    l.m_aLayoutData[dataVRes] = v+(iVRes<<24);
                    l.m_aLayoutData[dataFaceID] = f;
                        
                    // To properly define the point on the surface, we use the index of the face, and the coordinates inside the face calculated from the grid coordinate.
                    l.Fill( pSurface, f, (u+0.5f)/(float)iHSize, (v+0.5f)/(float)iVSize );
                        
                    if ( !bFiltering )
                        l.m_fDiameter = 0.0f;

                    ProcessSurfacePoint( l );
                };
        };
        // Declaring the end of the section, which will tell the PtexUtilizer objects that no more reference points will be generated for the current mesh, so they can finish
        // writing the ptex file into the disk.
    }
    else
    {
        PrepareAdjacency( pSurface );

        unsigned int iFaceID = 0;
        // NSided case, this is more complicated than the quad one.
        for ( unsigned int f = 0; f < pSurface->FaceCount(); f++ )
        {
            // We go through all the polygons of the target mesh, so we skip fake triangles.
            if ( pSurface->IsFakeTriangle( f ) )
                continue;

            // Calculate the number of sides for this poly.
            int iSideCount = 3, i = f;
            while ( f < pSurface->FaceCount() && pSurface->IsFakeTriangle( ++i ) )
                iSideCount++;

            // The number of the ptex faces generated for this polygon depends on the number of sides. For quads, we have 
            // to generate a single ptex face, for other polygons we generate one ptex face for each vertex, so the number
            // of ptex faces in that case is the same as the number of sides in the polygon.
            int iSubFaceCount = iSideCount;
            if ( iSideCount == 4 )
                iSubFaceCount = 1;

            // Collect the object space position of the corners of the polygon.
            Vector aCorners[16];
            Vector aUVCorners[16];
            MB_ONBUG( iSideCount >= 16 )
                continue;
            aCorners[0] = pSurface->TriangleVertexPosition( f, 0 );
            aCorners[1] = pSurface->TriangleVertexPosition( f, 1 );
            for ( int i = 0; i < iSideCount-2; i++ )
                aCorners[i+2] = pSurface->TriangleVertexPosition( f+i, 2 );
            if ( pSurface->HasTC() )
            {
                aUVCorners[0] = pSurface->TriangleVertexTC( f, 0 );
                aUVCorners[1] = pSurface->TriangleVertexTC( f, 1 );
                for ( int i = 0; i < iSideCount-2; i++ )
                    aUVCorners[i+2] = pSurface->TriangleVertexTC( f+i, 2 );
            };

            // Calculate the position of the center of the polygon/
            Vector vCenter;
            for ( int j = 0; j < iSideCount; j++ )
                vCenter += aCorners[j];
            vCenter *= 1/(float)iSideCount;
            Vector vUVCenter;
            for ( int j = 0; j < iSideCount; j++ )
                vUVCenter += aUVCorners[j];
            vUVCenter *= 1/(float)iSideCount;

            // Go through the subfaces.
            for ( int iSubFace = 0; iSubFace < iSubFaceCount; iSubFace++ )
            {
                Vector vCorner0, vCorner1, vCorner2, vCorner3;
                Vector vUVCorner0, vUVCorner1, vUVCorner2, vUVCorner3;
                int iURes = 3, iVRes = 3;
                if ( iSideCount == 4 )
                {
                    // When this polygon is a quad, then there is a single ptex face, which covers the full area of the quad.
                    MB_ASSERT( iSubFace == 0 );
                    vCorner0 = aCorners[0];
                    vCorner1 = aCorners[1];
                    vCorner2 = aCorners[2];
                    vCorner3 = aCorners[3];
                    vUVCorner0 = aUVCorners[0];
                    vUVCorner1 = aUVCorners[1];
                    vUVCorner2 = aUVCorners[2];
                    vUVCorner3 = aUVCorners[3];
                }
                else
                {
                    // When the polygon is not a quad, then each vertex will have its own ptex face. This ptex face will
                    // cover a rectangular area surrounded by the vertex, the center of the two edges attached to the
                    // vertex, and the center of the polygon.
                    iURes--;        // Since this is a subface, we halve the resolution.
                    iVRes--;
                    vCorner0 = aCorners[iSubFace];
                    vCorner1 = (vCorner0+aCorners[(iSubFace+1)%iSideCount])*0.5f;
                    vCorner2 = vCenter;
                    vCorner3 = (vCorner0+aCorners[(iSubFace-1+iSideCount)%iSideCount])*0.5f;
                    vUVCorner0 = aUVCorners[iSubFace];
                    vUVCorner1 = (vUVCorner0+aUVCorners[(iSubFace+1)%iSideCount])*0.5f;
                    vUVCorner2 = vUVCenter;
                    vUVCorner3 = (vUVCorner0+aUVCorners[(iSubFace-1+iSideCount)%iSideCount])*0.5f;
                };

                if ( m_eDistribution != distUVArea )
                    CalculateFaceResolution( vCorner0, vCorner1, vCorner2, vCorner3, f, iURes, iVRes );
                else
                    CalculateFaceResolution( vUVCorner0, vUVCorner1, vUVCorner2, vUVCorner3, f, iURes, iVRes );

                // Now that we have the object space position of the corners of the ptex face, we generate reference
                // points in that area in a grid layout.
                int iUSize = 1 << iURes, iVSize = 1 << iVRes;
                for ( int iU = 0; iU < iUSize; iU++ )
                    for ( int iV = 0; iV < iVSize; iV++ )
                    {
                        TargetLocation l;
                        l.m_aLayoutData[dataURes] = iU+(iURes<<24);
                        l.m_aLayoutData[dataVRes] = iV+(iVRes<<24);
                        l.m_aLayoutData[dataFaceID] = iFaceID;
                        if ( iSubFaceCount > 1 )
                            l.m_aLayoutData[dataFaceID] |= 0x80000000;
                            
                        float fU = ((float)iU+0.5f)/iUSize, fV = ((float)iV+0.5f)/iVSize;
                        Vector vH0 = vCorner0+(vCorner1-vCorner0)*fU;
                        Vector vH1 = vCorner3+(vCorner2-vCorner3)*fU;
                        l.FillNSided( pSurface, f, vH0+(vH1-vH0)*fV );  // We initialize the location based on the object space position of the reference point.
                        if ( iSubFaceCount == 1 && !bFiltering )
                            l.m_fDiameter = 0.0f;
                        ProcessSurfacePoint( l );
                    };
                iFaceID++;
            };
        };
    };
    EndSection();
    if ( m_eDistribution != distCustom )
        Kernel()->Log( QString( "Mesh %1 processed with %2 samples (desired: %3).\n" ).arg( pSurface->Name() ).arg( m_sRes.m_iTexelCount ).arg( m_iDesiredTexelCount ) );
    else
        Kernel()->Log( QString( "Mesh %1 processed with %2 samples.\n" ).arg( pSurface->Name() ).arg( m_sRes.m_iTexelCount ) );
};

// This function initializates data structures used for resolution calculation.
void PtexLayout::InitializeResolution( const Mesh *pMesh )
{
        m_sRes.m_pMesh = pMesh;
        m_sRes.m_pUVGen = pMesh->ChildByClass<UVGeneratorNode>( false );
        m_sRes.m_iTexelCount = 0;

        // If custom distribution is selected, we don't need much initialization, since the resolution for each face is controlled 
        // explicitly by the user through the UVGeneratorNode object.
        if ( m_eDistribution == distCustom )
            return;

        // For UV and World based distributions, the total area of the surface has to be calculated.
        m_sRes.m_fTotalSurfaceArea = 0.0f;
        if ( m_eDistribution == distWorldArea || m_eDistribution == distUVArea )
        {
            for ( unsigned int i = 0; i < pMesh->FaceCount(); i++ )
            {
                if ( pMesh->Type() == Mesh::typeTriangular )
                {
                    Vector v0, v1, v2;
                    if ( m_eDistribution == distUVArea )
                    {
                        v0 = pMesh->TriangleVertexTC( i, 0 );
                        v1 = pMesh->TriangleVertexTC( i, 1 );
                        v2 = pMesh->TriangleVertexTC( i, 2 );
                    }
                    else
                    {
                        v0 = pMesh->TriangleVertexPosition( i, 0 );
                        v1 = pMesh->TriangleVertexPosition( i, 1 );
                        v2 = pMesh->TriangleVertexPosition( i, 2 );
                    };
                    m_sRes.m_fTotalSurfaceArea += TriangleArea( v0, v1, v2 );
                }
                else
                {
                    Vector v0, v1, v2, v3;
                    if ( m_eDistribution == distUVArea )
                    {
                        v0 = pMesh->QuadVertexTC( i, 0 );
                        v1 = pMesh->QuadVertexTC( i, 1 );
                        v2 = pMesh->QuadVertexTC( i, 2 );
                        v3 = pMesh->QuadVertexTC( i, 3 );
                    }
                    else
                    {
                        v0 = pMesh->QuadVertexPosition( i, 0 );
                        v1 = pMesh->QuadVertexPosition( i, 1 );
                        v2 = pMesh->QuadVertexPosition( i, 2 );
                        v3 = pMesh->QuadVertexPosition( i, 3 );
                    };
                    m_sRes.m_fTotalSurfaceArea += TriangleArea( v0, v1, v2 );
                    m_sRes.m_fTotalSurfaceArea += TriangleArea( v0, v2, v3 );
                };
            };
        }
        else
        {
            // When uniform distribution is selected, each face will get the same resolution, so we can assume that the area of each face is one.
            if ( pMesh->Type() == Mesh::typeQuadric )
                m_sRes.m_fTotalSurfaceArea = (float)pMesh->FaceCount();
            else
            {
                int s = 3;
                for ( unsigned int f = 0; f < pMesh->FaceCount(); f++ )
                {
                    if ( f < pMesh->FaceCount()-1 && pMesh->IsFakeTriangle( f+1 ) )
                        s++;
                    else
                    {
                        if ( s == 4 )
                            m_sRes.m_fTotalSurfaceArea++;
                        else
                            m_sRes.m_fTotalSurfaceArea += s;
                        s = 3;
                    };
                };
            };
        };

        // Ptex only allows power of two resolutions, so the ideal resolution should be aligned to the closes power of two values. 
        // When the ideal resolution is not close to a power of two number, then the plugin chooses based on which resolution fits 
        // better for the current desired texel count. m_fTolerance controls how close the face should be to a power of two number,
        // to disable this optimization. When uniform distribution is choosed, each face will have the same ideal resolution, so the
        // optimizations described above should be enabled to each face.
        if ( m_eDistribution == distUniform )
            m_sRes.m_fTolerance = 0.5f;
        else
            m_sRes.m_fTolerance = RES_TOL;

        m_sRes.m_fProcessedArea = 0.0f;
};  

// This function calculates the resolution for a given quad.
void PtexLayout::CalculateQuadResolution( unsigned int iQuadIndex, int &iHRes, int &iVRes )
{
    const Mesh *pMesh = m_sRes.m_pMesh;
    if ( m_eDistribution == distUVArea )
        CalculateFaceResolution( pMesh->QuadVertexTC( iQuadIndex, 0 ), pMesh->QuadVertexTC( iQuadIndex, 1 ), pMesh->QuadVertexTC( iQuadIndex, 2 ), pMesh->QuadVertexTC( iQuadIndex, 3 ), iQuadIndex, iHRes, iVRes );
    else
        CalculateFaceResolution( pMesh->QuadVertexPosition( iQuadIndex, 0 ), pMesh->QuadVertexPosition( iQuadIndex, 1 ), pMesh->QuadVertexPosition( iQuadIndex, 2 ), pMesh->QuadVertexPosition( iQuadIndex, 3 ), iQuadIndex, iHRes, iVRes );
};

// This function calculates which is the closest power of two number to an ideal resolution. If the ideal resolution is not close
// to a power of two number, the function is trying to choose the one which fits the desired texel count better.
int PtexLayout::Calculate1DResolution( float fIdeal )
{
    float f = logf(fIdeal)/logf(2.0f);
    float fRac = f-floorf(f);
    if ( f < 0 )
        f = 0;

    // fRac is the exponent of the distance from the lower power of two number. If this distance is close to 0 or 1 (i.e. fIdeal is close to a power of
    // two number), then that value will be choosed.
    if ( fRac < 0.5f-m_sRes.m_fTolerance )
        return int(f);
    if ( fRac > 0.5f+m_sRes.m_fTolerance )
        return int(f)+1;
    
    // In other cases, the decision will be made based on the current state of the extraction.
    unsigned int iExpectedTexelCount = m_sRes.m_iTexelCount*(m_sRes.m_fTotalSurfaceArea/m_sRes.m_fProcessedArea);
    if ( iExpectedTexelCount < m_iDesiredTexelCount )
        return int(f)+1;
    else
        return int(f);
};

// This function calculates the resolution for an arbitrary ptex face.
void PtexLayout::CalculateFaceResolution( const Vector &vC0, const Vector &vC1, const Vector &vC2, const Vector &vC3, unsigned int iFaceIndex, int &iHRes, int &iVRes )
{
    // If custom distribution is selected, the resolution is directly controlled by the UVGeneratorNode.
    if ( m_eDistribution == distCustom )
    {
        MB_ONBUG( m_sRes.m_pUVGen == 0 )
            return;
        iHRes = m_sRes.m_pUVGen->FaceSizeExponent( iFaceIndex )[0];
        iVRes = m_sRes.m_pUVGen->FaceSizeExponent( iFaceIndex )[1];
        m_sRes.m_iTexelCount += (1<<iHRes)*(1<<iVRes);
        return;
    };

    // In other cases the area of the face is controlling the resolution. The bigger the size, the bigger the resolution will be.
    float fFaceArea = TriangleArea( vC0, vC1, vC2 )+TriangleArea( vC1, vC2, vC3 );
    // If uniform distribution is selected, the area of each face is assumed to be one. This way each face will get similar resolutions.
    if ( m_eDistribution == distUniform )
        fFaceArea = 1.0;
    float fIdealTexelCount = m_iDesiredTexelCount*fFaceArea/m_sRes.m_fTotalSurfaceArea;

    float fWidth = ((vC0-vC1).Length()+(vC2-vC3).Length())*0.5f;
    float fHeight = ((vC0-vC3).Length()+(vC1-vC2).Length())*0.5f;
    float fAspect = fWidth/fHeight;
    float fIdealWidth = sqrtf(fIdealTexelCount*fAspect);
    iHRes = Calculate1DResolution( fIdealWidth );
    float fIdealHeight = fIdealTexelCount/(1<<iHRes);
    iVRes = Calculate1DResolution( fIdealHeight );

    MB_ONBUG( iHRes < 0 )
        iHRes = 0;
    MB_ONBUG( iVRes < 0 )
        iVRes = 0;

    m_sRes.m_fProcessedArea += fFaceArea;
    m_sRes.m_iTexelCount += (1<<iHRes)*(1<<iVRes);
    return;
};

// This function prepares the object for the extraction, and returns the number of the expected reference points.
unsigned int PtexLayout::Prepare( void )
{
    // If custom distribution is selected, the number of the texels is controlled by the UVGeneratorNode attached to the mesh
    // for other distributions, the number of texels will be close to m_iDesiredTexelCount
    if ( m_eDistribution == distCustom )
    {
        unsigned int iRefCount = 0;
        for ( unsigned int c = 0; c < Extractor()->TargetCount(); c++ )
        {
            const Mesh *p = Extractor()->TargetMesh( c );
            const UVGeneratorNode *pUVGen = p->ChildByClass<UVGeneratorNode>( false );
            if ( pUVGen == 0 )
            {
                m_eDistribution = distUniform;
                MB_ERROR( QObject::tr("\"Use PTEX Setup\" can only be selected if the target mesh is already set up for PTEX.") );
            };

            // each face has to be checked, and their resolution should be summed
            for ( unsigned int f = 0; f < p->FaceCount(); f++ )
            {
                if ( p->Type() == Mesh::typeTriangular && p->IsFakeTriangle( f ) )
                    continue;
                UVGeneratorNode::DimData4 d = pUVGen->FaceSize( f );
                iRefCount += d.m_iData[0]*d.m_iData[1];
            };
        };
        return iRefCount;
    };

    if ( m_eDistribution == distUVArea )
    {
        for ( unsigned int i = 0; i < Extractor()->TargetCount(); i++ )
            if ( !Extractor()->TargetMesh( i )->HasTC() )
            {
                m_eDistribution = distUniform;
                MB_ERROR( QObject::tr("\"Based on UV Size\" can only be selected if the target mesh has texture coordinates.") );
            };
    };

    return m_iDesiredTexelCount;
};

// Serialize the state of the object. We only need to serialize the only one attribute which belongs to this class.
void PtexLayout::Serialize( Stream &s )
{
    if ( s.IsNewerThan( 0, this ) )
    {
        if ( s.IsNewerThan( 2, this ) )
            s == m_fDensity == m_eDistribution;
        if ( s.IsNewerThan( 3, this ) )
            s == m_iDesiredTexelCount;
        else
        {
            if ( s.IsNewerThan( 1, this ) )
            {
                int i;
                s >> i;
            }
            else
            {
                float f;
                s >> f;
            };
        };
    };
    if ( s.IsNewerThan( 4, this ) )
        s == m_sTexelCount;
    Layout::Serialize( s );
};

void PtexLayout::OnNodeEvent( const Attribute &a, NodeEventType e )
{
    if ( a == m_fDensity && e == etValueChanged )
    {
        if ( m_fDensity > 1 )
            m_fDensity = 1;
        if ( m_fDensity < 0 )
            m_fDensity = 0;
        int iTargetSampleCount = 10000*powf(100, m_fDensity);
        m_sTexelCount.SetValue( QString("%1").arg(iTargetSampleCount), true );
        m_iDesiredTexelCount = iTargetSampleCount;
    };
    if ( a == m_eDistribution && e == etValueChanged )
    {
        if ( m_eDistribution == distCustom )
        {
            for ( unsigned int i = 0; i < Extractor()->TargetCount(); i++ )
            {
                UVGeneratorNode *pG = Extractor()->TargetMesh( i )->ChildByClass<UVGeneratorNode>( false );
                if ( !pG )
                {
                    Kernel()->Interface()->HUDMessageShow( QObject::tr("Use PTEX Setup can only be selected if the target mesh is already set up for PTEX."),  mudbox::Interface::HUDmsgFade );
                    m_eDistribution.SetValue( distUniform, true );
                    return;
                };
            };
        };
        m_fDensity.SetConst( m_eDistribution == distCustom );
        m_sTexelCount.SetConst( m_eDistribution == distCustom );
    };
    if ( a == m_sTexelCount && e == etValueChanged )
    {
        qlonglong iDesiredTexelCount = m_sTexelCount.Value().toLongLong();
        if ( iDesiredTexelCount < 1 )
        {
            iDesiredTexelCount = 1;
            m_sTexelCount = "1";
        };
        if ( iDesiredTexelCount > 100000000 )
        {
            iDesiredTexelCount = 100000000;
            m_sTexelCount = "100000000";
        };
        m_iDesiredTexelCount = iDesiredTexelCount;
        float fDensity = logf(m_iDesiredTexelCount/10000)/logf(100.0f);
        fDensity = Min(Max(fDensity,0.0f),1.0f);
        m_fDensity = fDensity;
    };
};

// Precalculating the m_aFaceID and m_aTriangle arrays for the current mesh. This is only needed when the target mesh is not a full quad mesh.
void PtexLayout::PrepareAdjacency( const Mesh *pMesh )
{
    // The m_aFaceID array will containt the ID of the first ptex face which belongs to the given triangle. 
    // For example, if a pentagon represented by the triangles 5-6-7 is split into ptex face with the ID of 7-11, then the array will contain values:
    // m_aFaceID[5] = 7     // ID of the first ptex face belongs to this polygon
    // m_aFaceID[6] = -1        // because this is a fake triangle
    // m_aFaceID[7] = -1     // the same
    // m_aFaceID[8] = 12        // this belongs to the next polygon
    m_pMesh = pMesh;
    m_aFaceID.resize( pMesh->FaceCount() );
    unsigned int iTFaceID = 0;  // This is the ID of the current ptex face.
    for ( unsigned int i = 0; i < pMesh->FaceCount(); i++ )
    {
        MB_ASSERT( !pMesh->IsFakeTriangle( i ) );
        m_aFaceID[i] = iTFaceID;

        // Calculate the sides of the polygon.
        int s = 3;
        while ( i+1 < pMesh->FaceCount() && pMesh->IsFakeTriangle( i+1 ) )
        {
            i++;
            s++;
            m_aFaceID[i] = 0xffffffff;
        };

        // If the polygon is a quad, then a single ptex face will be generated for it, otherwise each corner will get its own ptex face.
        if ( s == 4 )
            iTFaceID++;
        else
            iTFaceID += s;
    };

    // Fill the m_aTriangle array, which is the opposite of the m_afaceID array, it contains the index of the triangle which represents
    // the polygon which belongs to the current ptex face. In the same example as above, the array will look like this:
    // m_aTriangle[7] = 5
    // m_aTriangle[8] = 5
    // m_aTriangle[9] = 5
    // m_aTriangle[10] = 5
    // m_aTriangle[11] = 5
    // m_aTriangle[12] = 8  // this belongs to the next polygon
    m_aTriangle.fill( 0xffffffff, iTFaceID );
    for ( int i = 0; i < m_aFaceID.size(); i++ )
        if ( m_aFaceID[i] != 0xffffffff )
            m_aTriangle[m_aFaceID[i]] = i;

    for ( int i = 1; i < m_aTriangle.size(); i++ )
        if ( m_aTriangle[i] == 0xffffffff )
            m_aTriangle[i] = m_aTriangle[i-1];
};

// This function calculates the adjacency info for an edge of a mudbox triangle. The iSegment parameter controls which part of the
// edge we are interested (0=first half, 1=second half). This function is only needed when the target mesh is not a full quad mesh.
unsigned int PtexLayout::AdjacentFaceForTriangle( unsigned int iFaceIndex, unsigned int iSide, unsigned int iSegment, unsigned int &iEdge ) const
{
    // Check which is the adjacent triangle (if any)
    MB_ONBUG( iFaceIndex >= m_pMesh->FaceCount() )
        return 0xffffffff;
    unsigned int a = m_pMesh->TriangleAdjacency( iFaceIndex, iSide );
    if ( a == 0xffffffff )
        return 0xffffffff;

    // And calculate the side count for the polygon the triangle represents.
    unsigned int t = a/3;
    MB_ONBUG( t >= m_pMesh->FaceCount() )
        return 0xffffffff; 
    while ( m_pMesh->IsFakeTriangle( t ) )
    {
        MB_ONBUG( t == 0 )
            return 0xffffffff;
        t--;
    };
    unsigned int h = t+1;
    while ( h < m_pMesh->FaceCount() && m_pMesh->IsFakeTriangle( h ) )
        h++;
    unsigned int s = h-t+2;

    MB_ONBUG( s >= 16 )
        return 0xffffffff;

    // Collect vertices of the adjacent polygon into a local array.
    unsigned int iV[16];
    iV[0] = m_pMesh->TriangleIndex( t, 0 );
    iV[1] = m_pMesh->TriangleIndex( t, 1 );
    for ( unsigned int f = 0; f < s-2; f++ )
        iV[f+2] = m_pMesh->TriangleIndex( t+f, 2 );
    unsigned int iA = m_pMesh->TriangleIndex( iFaceIndex, (iSide+1)%3 ), iB = m_pMesh->TriangleIndex( iFaceIndex, (iSide+2)%3 );

    // Search which side of the adjacent poly we are.
    unsigned int as = 0;
    while ( iB != iV[as] && iA != iV[(as+1)%s] )
    {
        as++;
        MB_ONBUG( as == s )
            return 0xffffffff;
    };

    // Quads are special case, since they are a single ptex face. In this case the iSegment parameter is ignored.
    if ( s == 4 )
    {
        iEdge = as;
        return m_aFaceID[t];
    };

    // For other polygons, the edge depends on the iSegment value.
    if ( iSegment )
    {
        as = (as+1)%s;
        iEdge = 3;
    }
    else
        iEdge = 0;
    return m_aFaceID[t]+as;
};

// This function calculates the adjacency info for an edge of a ptex face. If the edge is an internal edge of a polygon, the
// function calculates the values directly. In other cases it calls the function AdjacentFaceForTriangle. This function is only 
// needed when the target mesh is not a full quad mesh.
unsigned int PtexLayout::AdjacentFace( unsigned int iFaceID, unsigned int iSide, unsigned int &iEdge ) const
{
    // Get the index of the triangle which represents the polygon of the ptex face. This must be a real triangle (i.e. the first triangle of 
    // that polygon).
    unsigned int iFaceIndex = m_aTriangle[iFaceID];
    MB_ONBUG( m_pMesh->IsFakeTriangle( iFaceIndex ) )
        return 0xffffffff;

    // Calculate the number of sides of that polygon.
    unsigned int e = iFaceIndex+1;
    while ( e < m_pMesh->FaceCount() && m_pMesh->IsFakeTriangle( e ) )
        e++;
    unsigned int s = e-iFaceIndex+2;

    // If the polygon is a quad, there are no internal edges (since all quads are represented as a single ptex face),
    // so we call AdjacentFaceForTriangle. If the other side of the edge contains multiple ptex faces (i.e. it belongs to
    // a polygon which is not a quad), ptex expects the first subface encountered in a counter-clockwise (i.e. edgeid 
    // order) traversal of the face as the adjacent face, so we are looking for the second segment of the edge (iSegment=1)
    if ( s == 4 )
    {
        unsigned int b[4] = { 0, 0, 1, 1 };
        unsigned int s[4] = { 2, 0, 0, 1 };
        return AdjacentFaceForTriangle( iFaceIndex+b[iSide], s[iSide], 1, iEdge );
    };

    // When the current polygon is not a quad, then the edges 0 and 3 are external edges (see http://http://ptex.us/adjdata.html 
    // for more detail), so in that case we call AdjacentFaceForTriangle with the proper data.
    if ( iSide == 0 || iSide == 3 )
    {
        // First we calculate which edge of the polygon this ptex edge belongs to.
        unsigned int l = iFaceID-m_aFaceID[iFaceIndex];
        MB_ONBUG( l >= 16 )
            return 0xffffffff;
        if ( iSide )
            l = (l+s-1)%s;

        // If it is the first edge, then that is the last edge of the first triangle belongs to the polygon.
        if ( l == 0 )
            return AdjacentFaceForTriangle( iFaceIndex, 2, iSide ? 0 : 1, iEdge );
        // If it is the last edge, then it is the middle edge of the last triangle.
        if ( l == s-1 )
            return AdjacentFaceForTriangle( iFaceIndex+s-3, 1, iSide ? 0 : 1, iEdge );
        // In other cases, it is the first edge of the corresponding triangle.
        return AdjacentFaceForTriangle( iFaceIndex+l-1, 0, iSide ? 0 : 1, iEdge );
    };

    // When it is an internal edge, the adjacent ptex face will be another subface of the same polygon.
    if ( iSide == 2 )
        iEdge = 1;
    else
        iEdge = 2;
    return m_aFaceID[iFaceIndex]+((iFaceID-m_aFaceID[iFaceIndex]+(iSide==2 ? -1 : 1)+s)%s);
};