HRESULT GeneratePointReps()

in DirectXMesh/DirectXMeshAdjacency.cpp [129:329]
152 lines of code
36 McCabe index (conditional complexity)

    HRESULT GeneratePointReps(
        _In_reads_(nFaces * 3) const index_t* indices, size_t nFaces,
        _In_reads_(nVerts) const XMFLOAT3* positions, size_t nVerts,
        float epsilon,
        _Out_writes_(nVerts) uint32_t* pointRep) noexcept
    {
        std::unique_ptr<uint32_t[]> temp(new (std::nothrow) uint32_t[nVerts + nFaces * 3]);
        if (!temp)
            return E_OUTOFMEMORY;

        uint32_t* vertexToCorner = temp.get();
        uint32_t* vertexCornerList = temp.get() + nVerts;

        memset(vertexToCorner, 0xff, sizeof(uint32_t) * nVerts);
        memset(vertexCornerList, 0xff, sizeof(uint32_t) * nFaces * 3);

        // build initial lists and validate indices
        for (size_t j = 0; j < (nFaces * 3); ++j)
        {
            index_t k = indices[j];
            if (k == index_t(-1))
                continue;

            if (k >= nVerts)
                return E_UNEXPECTED;

            vertexCornerList[j] = vertexToCorner[k];
            vertexToCorner[k] = uint32_t(j);
        }

        if (epsilon == 0.f)
        {
            auto hashSize = std::max<size_t>(nVerts / 3, 1);

            std::unique_ptr<vertexHashEntry*[]> hashTable(new (std::nothrow) vertexHashEntry*[hashSize]);
            if (!hashTable)
                return E_OUTOFMEMORY;

            memset(hashTable.get(), 0, sizeof(vertexHashEntry*) * hashSize);

            std::unique_ptr<vertexHashEntry[]> hashEntries(new (std::nothrow) vertexHashEntry[nVerts]);
            if (!hashEntries)
                return E_OUTOFMEMORY;

            uint32_t freeEntry = 0;

            for (size_t vert = 0; vert < nVerts; ++vert)
            {
                auto px = reinterpret_cast<const uint32_t*>(&positions[vert].x);
                auto py = reinterpret_cast<const uint32_t*>(&positions[vert].y);
                auto pz = reinterpret_cast<const uint32_t*>(&positions[vert].z);
                uint32_t hashKey = (*px + *py + *pz) % uint32_t(hashSize);

                uint32_t found = UNUSED32;

                for (auto current = hashTable[hashKey]; current != nullptr; current = current->next)
                {
                    if (current->v.x == positions[vert].x
                        && current->v.y == positions[vert].y
                        && current->v.z == positions[vert].z)
                    {
                        uint32_t head = vertexToCorner[vert];

                        bool ispresent = false;

                        while (head != UNUSED32)
                        {
                            uint32_t face = head / 3;
                            assert(face < nFaces);
                            _Analysis_assume_(face < nFaces);

                            assert((indices[face * 3] == vert) || (indices[face * 3 + 1] == vert) || (indices[face * 3 + 2] == vert));

                            if ((indices[face * 3] == current->index) || (indices[face * 3 + 1] == current->index) || (indices[face * 3 + 2] == current->index))
                            {
                                ispresent = true;
                                break;
                            }

                            head = vertexCornerList[head];
                        }

                        if (!ispresent)
                        {
                            found = current->index;
                            break;
                        }
                    }
                }

                if (found != UNUSED32)
                {
                    pointRep[vert] = found;
                }
                else
                {
                    assert(freeEntry < nVerts);
                    _Analysis_assume_(freeEntry < nVerts);

                    auto newEntry = &hashEntries[freeEntry];
                    ++freeEntry;

                    newEntry->v = positions[vert];
                    newEntry->index = uint32_t(vert);
                    newEntry->next = hashTable[hashKey];
                    hashTable[hashKey] = newEntry;

                    pointRep[vert] = uint32_t(vert);
                }
            }

            assert(freeEntry <= nVerts);

            return S_OK;
        }
        else
        {
            std::unique_ptr<uint32_t[]> xorder(new (std::nothrow) uint32_t[nVerts]);
            if (!xorder)
                return E_OUTOFMEMORY;

            // order in descending order
            MakeXHeap(xorder.get(), positions, nVerts);

            memset(pointRep, 0xff, sizeof(uint32_t) * nVerts);

            XMVECTOR vepsilon = XMVectorReplicate(epsilon * epsilon);

            uint32_t head = 0;
            uint32_t tail = 0;

            while (tail < nVerts)
            {
                // move head until just out of epsilon
                while ((head < nVerts)
                    && ((positions[tail].x - positions[head].x) <= epsilon))
                {
                    ++head;
                }

                // check new tail against all points up to the head
                uint32_t tailIndex = xorder[tail];
                assert(tailIndex < nVerts);
                _Analysis_assume_(tailIndex < nVerts);
                if (pointRep[tailIndex] == UNUSED32)
                {
                    pointRep[tailIndex] = tailIndex;

                    XMVECTOR outer = XMLoadFloat3(&positions[tailIndex]);

                    for (uint32_t current = tail + 1; current < head; ++current)
                    {
                        uint32_t curIndex = xorder[current];
                        assert(curIndex < nVerts);
                        _Analysis_assume_(curIndex < nVerts);

                        // if the point is already assigned, ignore it
                        if (pointRep[curIndex] == UNUSED32)
                        {
                            XMVECTOR inner = XMLoadFloat3(&positions[curIndex]);

                            XMVECTOR diff = XMVector3LengthSq(XMVectorSubtract(inner, outer));

                            if (XMVector2Less(diff, vepsilon))
                            {
                                uint32_t headvc = vertexToCorner[tailIndex];

                                bool ispresent = false;

                                while (headvc != UNUSED32)
                                {
                                    uint32_t face = headvc / 3;
                                    assert(face < nFaces);
                                    _Analysis_assume_(face < nFaces);

                                    assert((indices[face * 3] == tailIndex) || (indices[face * 3 + 1] == tailIndex) || (indices[face * 3 + 2] == tailIndex));

                                    if ((indices[face * 3] == curIndex) || (indices[face * 3 + 1] == curIndex) || (indices[face * 3 + 2] == curIndex))
                                    {
                                        ispresent = true;
                                        break;
                                    }

                                    headvc = vertexCornerList[headvc];
                                }

                                if (!ispresent)
                                {
                                    pointRep[curIndex] = tailIndex;
                                }
                            }
                        }
                    }
                }

                ++tail;
            }

            return S_OK;
        }
    }