16 янв. 2012 г.

Оптимизация мэша, вершинный кэш

При экспорте 3d моделей из редактора трехмерной графики или при чтении из таких форматов как 3ds, collada, fbx, ..., зачастую их данные содержат дублирующиеся вершины.
    Поэтому лучше при экспорте выполнять проверку на наличие таких вершин и сохранять только уникальные данные пропуская вертексы, у которых все вершинные атрибуты совпадают.
Если вершины мэша содержат только координаты, то оптимизация выглядела бы так:
Но как правило, каждая вершина, имеет несколько вершинных атрибутов (нормаль, тангенс/битангенс, текстурные координаты, цвет), поэтому она будет считаться уникальной только если совпадают все атрибуты.
    Алгоритм удаления дублирующихся вершин достаточно прост: каждую вершину в сетке модели необходимо проверить на уникальность, сравнивая все ее атрибуты с атрибутами других вершин, если они совпадают, то сравниваемая вершина пропускается, но при этом добавляется индекс уже имеющейся в новом наборе.
Функция склейки вершин:
void WeldVertices( MeshDesc_t& desc )
{
    ASSERT(desc.m_NumVertices < 65535 );

    MeshDesc_t tmpMesh;
    // указатели на текущие данные вершин исходного меша
    AtributeGroup pVatr;
    // выделяем память под временный меш
    AllocateMeshDesc(tmpMesh, desc.m_NumVertices, desc.m_NumIndices);

    size_t goodVertex = 0, counterIndex = 0;
    const size_t faceCout = desc.m_NumVertices / 3;

    // обходим все грани в сетке
    for( size_t face = 0; face < faceCout; ++face )
    {
        // обходим вершины текущей грани 
        for ( size_t i = 0; i < 3; ++i )
        {
            bool vertexFlag = false;
            // индекс вершины в полигоне
            size_t iv = face * 3 + i;
            /* указатели на начало данных атрибутов следующей вершины */
            pVatr.pNormal = &desc.m_pNormal[ 3 * iv ];
            pVatr.pPosition = &desc.m_pPosition[ 3 * iv ];
            pVatr.pTexCoord = &desc.m_pTexCoord[ 2 * iv ];

            uint16_t _ii = 0;
            // сравниваем текущую вершину со всем набором
            for ( ; _ii != goodVertex; ++_ii )
            {
                // сравниваем атрибуты вершин
                if(Compare3vf(pVatr.pPosition, tmpMesh.m_pPosition+(_ii*3)))
                    if(Compare3vf(pVatr.pNormal, tmpMesh.m_pNormal+(_ii*3)))
                        if(Compare2vf(pVatr.pTexCoord, tmpMesh.m_pTexCoord+(_ii*2)))
                            {
                                // если все атрибуты совпали
                                // добавляем только индекс текущей вершины
                                tmpMesh.m_pIndices[counterIndex++] = _ii;
                                vertexFlag = true;
                            }
            }

            if ( vertexFlag == true )
                continue;

            // добавляем уникальные атрибуты вершины и ее индекс
            /* позиция */
            memcpy(tmpMesh.m_pPosition+(3*goodVertex),pVatr.pPosition,3*sizeof(float));
            /* нормаль */
            memcpy(tmpMesh.m_pNormal  +(3*goodVertex),pVatr.pNormal,  3*sizeof(float));
            /* текстурные координаты */
            memcpy(tmpMesh.m_pTexCoord+(2*goodVertex),pVatr.pTexCoord,2*sizeof(float));    

            ++goodVertex;

            /* индекс вершины */
            tmpMesh.m_pIndices[counterIndex++] = _ii;
        }
    }

    /* удаляем старые данные исходного меша */
    FreeMeshDesc(desc);

    const size_t numIndex = counterIndex;
    /* выделяем память под актуальные данные вершинных
       атрибутов и индексов */
    AllocateMeshDesc(desc, goodVertex, numIndex);

    /* копируем новые значения атрибутов вертекса */
    memcpy(desc.m_pPosition,tmpMesh.m_pPosition,(3*goodVertex)*sizeof(float));
    memcpy(desc.m_pNormal,  tmpMesh.m_pNormal,  (3*goodVertex)*sizeof(float));
    memcpy(desc.m_pTexCoord,tmpMesh.m_pTexCoord,(2*goodVertex)*sizeof(float));

    /* копируем значения идексов */
    memcpy(desc.m_pIndices, tmpMesh.m_pIndices,numIndex * sizeof(uint16_t));

    /* удаляем временный меш */
    FreeMeshDesc(tmpMesh);
}
    Здесь проверяется только 3 вершинных атрибута (position, normal, tex.coord), при необходимости можно легко добавить и другие. Единственное ограничение накладывается на количество вершин в одной модели, оно не должно превышать числа в 65535 (максимальный индекс вершины(unsigned short)).
    После этого мы получаем сетку модели с меньшим количеством вершин, при не изменившимся количестве индексов. Это сэкономит нам немного видеопамяти.
    Для дальнейшей оптимизации можно реорганизовать данные индексного и вершинного буфера, таким образом, чтобы трансформации вертексов, как можно реже повторно вычислялись, а брались из кэше видеокарты, так называемом post-TnL(Transformations and Lightning).
    Для этих целей мы воспользуемся библиотекой NvTriStrip от NVIDIA.
Код оптимизации для Triangle list:
void RemapTriangleList( MeshDesc_t& desc, bool isSave )
{
    ASSERT(desc.m_NumVertices < 65535 );
    // устанавливаем размер вершинного кеша
    ::SetCacheSize( CACHESIZE_GEFORCE3 );
    // оптимизировать будем только TriangleList
    ::SetListsOnly( true );
    ::PrimitiveGroup* primGroups;
    unsigned short numGroups;

    ::GenerateStrips( desc.m_pIndices, desc.m_NumIndices, &primGroups, &numGroups );
    ASSERT( numGroups == 1 );
    ASSERT( primGroups->type == PT_LIST );

    ::PrimitiveGroup*  remapGroups;
    ::RemapIndices( primGroups, 1, desc.m_NumVertices, &remapGroups );

    MeshDesc_t tmpDesc;
    // выделяем память только под вершинные атрибуты
    AllocateMeshDesc(tmpDesc, desc.m_NumVertices, 0);

    // копируем новые значения индексного буфера
    memcpy(desc.m_pIndices,remapGroups->indices,
            remapGroups->numIndices*sizeof(uint16_t));

    // выполняем сопоставление вертексов с новыми значениями индексов
    for (size_t _ii = 0; _ii <   remapGroups->numIndices; ++_ii) {    
        /* старый индекс текущей вершины */
        uint16_t old_index = primGroups->indices[ _ii ];
        /* новый индекс текущей вершины */
        uint16_t new_index =  remapGroups->indices[ _ii ];
        
        /* переставляем вертексы */
        memcpy(tmpDesc.m_pPosition+(3*new_index),desc.m_pPosition+(3*old_index),3*sizeof(float));
        memcpy(tmpDesc.m_pNormal+  (3*new_index),desc.m_pNormal+  (3*old_index),3*sizeof(float));
        memcpy(tmpDesc.m_pTexCoord+(2*new_index),desc.m_pTexCoord+(2*old_index),2*sizeof(float));
    }
    
    const size_t numVert = tmpDesc.m_NumVertices;
    // присваеваем новые значения
    memcpy(desc.m_pPosition, tmpDesc.m_pPosition,(3*numVert)*sizeof(float));
    memcpy(desc.m_pNormal, tmpDesc.m_pNormal,    (3*numVert)*sizeof(float));
    memcpy(desc.m_pTexCoord, tmpDesc.m_pTexCoord,(2*numVert)*sizeof(float));

    /* удаляем временный меш */
    FreeMeshDesc(tmpDesc);

    delete[] remapGroups;
    delete[] primGroups;

    if (isSave)
        SaveMeshDesc("optimize.mesh", desc);
}
Тестовые конфигурации и время выполнения для модели с 64446 вершинами:
 WeldVerices 
Core 2 Duo T5850 2.17GHz
36 sec.
Core 2 Duo E6600 2.9GHz
25 sec.
RemapTriangleList
Core 2 Duo T5850 2.17GHz31 sec.
Core 2 Duo E6600 2.9GHz22 sec.
Для тестовой модели кролика количество вершин сократилось до 64310 и было сэкономлено всего 136 вершин ~4kb (так как сетка модели достаточно не регулярна), но для других моделей это число может быть значительно большим.
Source code: MeshOptimization_VS10

3 комментария:

  1. Я типа тут мимо проходил)
    Вообщем не лучшее это решение индексировать меш "влоб", сравнивая вершины "каждую с каждой". Пока у модели будет 64к вершины это еще допустимо для оффлайновой конвертации моделей, но когда у моделей порядка миллиона вершин, то этот подход потребует уже недели вычислений (5E11 проверок).

    Потому Вам бы стоило познакомиться с таким понятием как хеширование. Банальное вычисление хэш-кода для пакета вершинных атрибут уже бы сократило количество проверок с 3-х по 3 флоата до проверки одного целого, что немаловажно при полу-триллионах проверок.
    Второй совет - раскидать вершины по спискам по их хэш-кодам. Тоесть, если взять для хэша короткое целое, то это даст 65536 вариантов хэш-кода. Создаем соответственно 65536 списков. Далее - вычисляем хэш код для текущей вершины и проверяем все вершины в списке, соответствующему этому хэш-коду (разные вершины могут иметь одинаковый хэш), вместо проверок всего списка вершин. Если нашли совпадение - берем индекс этой вершины, иначе - присваиваем ей новый индекс и добавляем вершину в список.

    При таком подходе и с оптимизацией проверок получается проиндексировать модельку из миллиона вершин примерно за 2 секунды.

    ОтветитьУдалить
    Ответы
    1. Ну, если модель имеет более чем 64к вершин, то стоит задуматься о ее разделении на отдельные части (SubMesh). И как мне кажется модели с миллионами вершин скорее необходимы для достаточно специфических задачах (где и оптимизация то не особо нужна).
      А за советы спасибо возьму на вооружение)

      Удалить
    2. Ну миллионы вершин это как пример, хотя с ростом производительности видео это может оказатсья очень даже актуальным. Просто индексация вершин нужна при работе с большинством существующих форматов - 3ds,obj,asc,smd,dae и многими другими. Фактически я не знаю ни одного формата, который был бы индексированным и совместим с VBO.

      При Вашем подходе, даже для моделей/сабмешей с менее 64к вершин, при загрузке скажем 100 моделей только одно решение - "оффлайновая" индексация моделей во внутренний формат (которая к слову займет час). После оптимизации - появляется возможно грузить и индексировать все модели "на лету" (индексация модели из 64к полигонов занимает десяток миллисекунд), что позволяет использовать родные форматы и делает движок более гибким. Да и процесс пересохранения во внутренний формат "существенно" ускоряется.

      Просто когда-то тоже столкнулся с этой проблемой, именно при попытках экспортировать модели из графических пакетов. Модельки были по 100-200к полигонов, что вполне приемлемо для современных видеокарт (LOD0), но процесс индексации занимал часы, потому пришлось искать альтернативы.

      Удалить