How to Flip Triangles in Triangle Mesh

Warning! Some information on this page is older than 6 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

Sat
19
Jan 2013

Given triangle mesh, as we use it in real-time rendering of 3D graphics, we say that each triangle have two sides, depending on whether its vertices are oriented clockwise or counterclockwise from particular point of view. In Direct3D, by default, triangles oriented clockwise are considered front-facing and they are visible, while triangles oriented counterclockwise are invisible because they are discarded by the API feature called backface culling.

When we have backface culling enabled and we convert mesh between coordinate systems, we sometimes need to "flip triangles". When vertices of each triangle are separate, an algorithm for this is easy. We just need to swap first with third vertex of each triangle (or any other two vertices). So we can start implementing the flipping method like this:

class CMesh
{
    ...
    D3D11_PRIMITIVE_TOPOLOGY m_Topology;
    bool m_HasIndices;
    std::vector<SVertex> m_Vertices;
    std::vector<uint32_t> m_Indices;
};

void CMesh::FlipTriangles()
{
    if(m_Topology == D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST)
    {
        if(m_HasIndices)
            FlipTriangleListInArray<uint32_t>(m_Indices);
        else
            FlipTriangleListInArray<SVertex>(m_Vertices);
    }
    ...
}

Where the function template for flipping triangles in a vector is:

template<typename T>
void CMesh::FlipTriangleListInArray(std::vector<T>& values)
{
    for(size_t i = 0, count = values.size(); i < count - 2; i += 3)
        std::swap(values[i], values[i + 2]);
}

Simple reversing all elements in the vector with std::reverse would also do the job. But things get complicated when we consider triangle strip topology. (I assume here that you know how graphics API-s generate orientation of triangles in a triangle strip.) Reversing vertices works, but only when number of vertices in the strip is odd. When it's even, triangles stay oriented in the same way.

I asked question about this on forum.warsztat.gd (in Polish). User albiero proposed following solution: just duplicate first vertex. It will generate additional degenerate (invisible) triangle, but thanks to this all following triangles will be flipped. It seems to work!

I also wanted to handle strip-cut index (a special value -1 which starts new triangle strip), so the rest of my fully-featured algorithm for triangle flipping is:

    ...
    else if(m_Topology == D3D11_PRIMITIVE_TOPOLOGY_TRIANGLESTRIP)
    {
        if(m_HasIndices)
        {
            size_t begIndex = 0;
            while(begIndex < m_Indices.size())
            {
                const size_t indexCount = m_Indices.size();
                while(begIndex < indexCount && m_Indices[begIndex] == UINT_MAX)
                    ++begIndex;
                if(begIndex == indexCount)
                    break;
                size_t endIndex = begIndex + 1;
                while(endIndex < indexCount && m_Indices[endIndex] != UINT_MAX)
                    ++endIndex;
                // m_Indices.size() can change here!
                FlipTriangleStripInArray<uint32_t>(m_Indices, begIndex, endIndex);
                begIndex = endIndex + 1;
            }
        }
        else
            FlipTriangleStripInArray<SVertex>(m_Vertices, 0, m_Vertices.size());
    }
}

Where function template for flipping triangles in selected part of a vector is:

template<typename T>
void CMesh::FlipTriangleStripInArray(std::vector<T>& values, size_t begIndex, size_t endIndex)
{
    const size_t count = endIndex - begIndex;
    if(count < 3) return;
    // Number of elements (and triangles) is odd: Reverse elements.
    if(count % 2)
        std::reverse(values.begin() + begIndex, values.begin() + endIndex);
    // Number of elements (and triangles) is even: Repeat first element.
    else
        values.insert(values.begin() + begIndex, values[begIndex]);
}

Comments | #directx #rendering #algorithms Share

Comments

[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2024