NormalGenerator.h

#pragma once
 
#include <vector>
#include <stdint.h>
 
namespace Cogs
{
  namespace Geometry
  {
    template<class IndexType, int maxSize>
    struct AdjacencyList_T
    {
      typedef std::vector<IndexType> IndexVector;
 
      AdjacencyList_T() = default;
 
      ~AdjacencyList_T()
      {
        if (currentSize == -1) {
          auto indexVector = reinterpret_cast<IndexVector *>(&data);
          indexVector->~IndexVector();
        }
      }
 
      void push_back(IndexType index)
      {
        static_assert(maxSize * sizeof(IndexType) >= sizeof(IndexVector), "No room for index vector.");
 
        if (currentSize == maxSize) {
          currentSize = -1;
 
          IndexType temp[maxSize];
          
          std::memcpy(temp, data, maxSize * sizeof(IndexType));
 
          auto indexVector = reinterpret_cast<IndexVector *>(&data);
          new (indexVector) IndexVector();
          indexVector->assign(temp, temp + maxSize);
        }
 
        if (currentSize == -1) {
          auto indexVector = reinterpret_cast<IndexVector *>(&data);
          indexVector->push_back(index);
        } else {
          data[currentSize++] = index;
        }
      }
 
      const IndexType & operator[](size_t i) const
      {
        if (currentSize == -1) {
          auto indexVector = reinterpret_cast<const IndexVector *>(&data);
 
          assert(i < indexVector->size() && "Index out of range.");
 
          return (*indexVector)[i];
        } else {
          return this->data[i];
        }
      }
 
      size_t size() const
      {
        if (currentSize == -1) {
          auto indexVector = reinterpret_cast<const IndexVector *>(&data);
          return indexVector->size();
        } else {
          return currentSize;
        }
      }
 
    private:
      IndexType data[maxSize];
 
      int8_t currentSize = 0;
    };
 
    typedef AdjacencyList_T<int32_t, 8> AdjacencyList;
 
    template<class IndexType, class AdjacencyListType, bool quads>
    void generateAdjacencyInfo(const size_t numFaces, const IndexType * indices, const size_t positionOffset, std::vector<AdjacencyListType> & adjacencyList)
    {
      const size_t numIndicesPerFace = quads ? 5 : 4;
 
      for (size_t i = 0; i < numFaces; i++) {
        const size_t baseIndex = i * numIndicesPerFace;
 
        adjacencyList[indices[baseIndex] - static_cast<IndexType>(positionOffset)].push_back(static_cast<IndexType>(i));
        adjacencyList[indices[baseIndex + 1] - static_cast<IndexType>(positionOffset)].push_back(static_cast<IndexType>(i));
        adjacencyList[indices[baseIndex + 2] - static_cast<IndexType>(positionOffset)].push_back(static_cast<IndexType>(i));
 
        if (quads) {
          adjacencyList[indices[baseIndex + 3] - positionOffset].push_back(static_cast<int32_t>(i));
        }
      }
    }
 
    template<class PositionType, class IndexType, class NormalType, bool quads>
    void calculateFaceNormals(const size_t numFaces, const PositionType * positions, const IndexType * indices, std::vector<NormalType> & faceNormals)
    {
      const size_t numIndicesPerFace = quads ? 5 : 4;
 
      NormalType faceNormal;
      PositionType leftLeg;
      PositionType rightLeg;
 
      // Calculate per face normals by doing a cross product of the legs in the triangle.
      for (size_t i = 0; i < numFaces; i++) {
        const size_t baseIndex = i * numIndicesPerFace;
 
        leftLeg = positions[indices[baseIndex + 1]] - positions[indices[baseIndex]];
        rightLeg = positions[indices[baseIndex + 2]] - positions[indices[baseIndex]];
 
        faceNormal = cross(rightLeg, leftLeg);
 
        faceNormal = normalize(faceNormal);
 
        faceNormals[i] = faceNormal;
      }
    }
 
    template<class NormalType, class AdjacencyListType>
    void calculateSmoothVertexNormals(NormalType * normals, const size_t numNormals, const std::vector<NormalType> & faceNormals, const size_t positionOffset, const std::vector<AdjacencyListType> & adjacencyList)
    {
      for (size_t i = positionOffset; i < numNormals; i++) {
        NormalType faceNormal = NormalType(0, 0, 0);
 
        const size_t adjacencyIndex = i - positionOffset;
        const size_t numAdjacentFaces = adjacencyList[adjacencyIndex].size();
 
        for (size_t k = 0; k < numAdjacentFaces; k++) {
          faceNormal = faceNormal + faceNormals[adjacencyList[adjacencyIndex][k]];
        }
 
        faceNormal = normalize(faceNormal);
 
        normals[i] = faceNormal;
      }
    }
 
    static double pi()
    {
      return 3.14159265358979323846;
    }
 
    template<class NormalType, class AdjacencyListType, class IndexType>
    void calculateFacetVertexNormals(const std::vector<NormalType> & faceNormals, const std::vector<AdjacencyListType> & adjacencyList, const IndexType * indexes, const float creaseAngle, bool quads, NormalType * normals)
    {
        const size_t numIndicesPerFace = quads ? 5 : 4;
        const size_t numVertexesPerFace = quads ? 4 : 3;
 
        const float threshold = std::cos(std::max(0.0f, std::min(creaseAngle, static_cast<float>(pi()))));
 
        for (size_t i = 0; i < faceNormals.size(); ++i) {
          const NormalType & faceNormal = faceNormals[i];
 
          for (size_t j = 0; j < numIndicesPerFace - 1; ++j) {
            const int currentIndex = indexes[i * numIndicesPerFace + j];
 
            NormalType vertexNormal = faceNormal;
 
            const AdjacencyListType & faceList = adjacencyList[currentIndex];
 
            for (size_t k = 0; k < faceList.size(); ++k) {
              const NormalType & adjacentFaceNormal = faceNormals[faceList[k]];
 
              if (static_cast<size_t>(faceList[k]) != i && dot(adjacentFaceNormal, faceNormal) > threshold) {
                vertexNormal = vertexNormal + adjacentFaceNormal;
              }
            }
 
            vertexNormal = normalize(vertexNormal);
 
            normals[i * numVertexesPerFace + j] = vertexNormal;
          }
        }
    }
 
    template<class IndexType, bool quads>
    void generateLinearIndexes(const size_t numFaces, IndexType * indexes)
    {
      int index = 0;
      int vertexIndex = 0;
 
      for (size_t i = 0; i < numFaces; ++i) {
        indexes[index++] = vertexIndex++;
        indexes[index++] = vertexIndex++;
        indexes[index++] = vertexIndex++;
 
        if (quads) {
          indexes[index++] = vertexIndex++;
        }
 
        indexes[index++] = -1;
      }
    }
 
    template<class ValueType, class IndexType>
    void reindexValues(const ValueType * inputValues, const IndexType * indexes, const size_t numFaces, const size_t numIndexesPerFace, ValueType * outputValues)
    {
      int index = 0;
 
      for (size_t i = 0; i < numFaces; ++i) {
        for (size_t j = 0; j < numIndexesPerFace - 1; ++j) {
          outputValues[index++] = inputValues[indexes[i * numIndexesPerFace + j]];
        }
      }
    }
 
    template<class NormalType>
    void correctZeroLengthNormals(NormalType * normals, const size_t numNormals)
    {
      for (size_t i = 0; i < numNormals; ++i) {
        if (normals[i] == NormalType(0, 0, 0) || normals[i][0] == std::numeric_limits<float>::quiet_NaN()) {
          normals[i] = NormalType(0, 0, 1);
        }
      }
    }
 
    template<class NormalType>
    void reverseNormalDirections(NormalType * normals, const size_t numNormals)
    {
      for (size_t i = 0; i < numNormals; ++i) {
        normals[i] = -normals[i];
      }
    }
 
    template<class AdjacencyListType>
    void addExtrusionSeamFaces(const size_t numFaces, size_t segmentCount, std::vector<AdjacencyListType> & adjacencyList)
    {
      const size_t numSections = numFaces / segmentCount;
 
      for (size_t i = 0; i < numSections; ++i) {
        const size_t firstSegmentIndex = i * (segmentCount + 1);
        const size_t lastSegmentIndex = i * (segmentCount + 1) + segmentCount;
 
        const size_t firstSegmentIndexNextRow = (i + 1) * (segmentCount + 1);
        const size_t lastSegmentIndexNextRow = (i + 1) * (segmentCount + 1) + segmentCount;
 
        adjacencyList[lastSegmentIndex].push_back(static_cast<int32_t>(i * segmentCount));
        adjacencyList[firstSegmentIndex].push_back(static_cast<int32_t>(i * segmentCount + (segmentCount - 1)));
        adjacencyList[lastSegmentIndexNextRow].push_back(static_cast<int32_t>(i * segmentCount));
        adjacencyList[firstSegmentIndexNextRow].push_back(static_cast<int32_t>(i * segmentCount + (segmentCount - 1)));
      }
    }
 
    template<class AdjacencyListType>
    void addTriangleExtrusionSeamFaces(const size_t numFaces, size_t segmentCount, std::vector<AdjacencyListType> & adjacencyList)
    {
      const size_t numSections = (numFaces / 2) / segmentCount;
      const size_t facePerSectionCount = segmentCount * 2;
 
      for (size_t i = 0; i < numSections; ++i) {
        const size_t firstSegmentIndex = i * (segmentCount + 1);
        const size_t lastSegmentIndex = i * (segmentCount + 1) + segmentCount;
 
        const size_t firstSegmentIndexNextRow = (i + 1) * (segmentCount + 1);
        const size_t lastSegmentIndexNextRow = (i + 1) * (segmentCount + 1) + segmentCount;
 
        adjacencyList[firstSegmentIndex].push_back(static_cast<int32_t>(i * facePerSectionCount + (facePerSectionCount - 2)));
 
        adjacencyList[lastSegmentIndex].push_back(static_cast<int32_t>(i * facePerSectionCount));
        adjacencyList[lastSegmentIndex].push_back(static_cast<int32_t>(i * facePerSectionCount + 1));
 
        adjacencyList[firstSegmentIndexNextRow].push_back(static_cast<int32_t>(i * facePerSectionCount + (facePerSectionCount - 1)));
        adjacencyList[firstSegmentIndexNextRow].push_back(static_cast<int32_t>(i * facePerSectionCount + (facePerSectionCount - 2)));
 
        adjacencyList[lastSegmentIndexNextRow].push_back(static_cast<int32_t>(i * facePerSectionCount + 1));
      }
    }
 
    template<typename VectorType, typename IndexType>
    void generateNormals(VectorType * positions, const size_t numVertexes, IndexType * indexes, const size_t numIndexes, bool quads, bool flipNormals, bool correctNormals, std::vector<VectorType> & normals)
    {
      if (!numIndexes) return;
      if (!numVertexes) return;
 
      normals.resize(numVertexes);
 
      generateNormals(positions, normals.data(), numVertexes, indexes, numIndexes, flipNormals, correctNormals, quads);
    }
 
    template<typename VectorType, typename IndexType>
    void generateNormals(
      const VectorType * positions,
      VectorType * normals,
      const size_t numPositions,
      const IndexType * indices,
      const size_t numIndices,
      bool flipNormals,
      bool correctNormals,
      bool quads,
      size_t positionOffset)
    {
      const size_t numIndicesPerFace = quads ? 5u : 4u;
      const size_t numFaces = numIndices / numIndicesPerFace;
      const size_t numActualVertices = numPositions - positionOffset;
 
      std::vector<VectorType> faceNormals(static_cast<unsigned>(numFaces));
      std::vector<AdjacencyList> adjacencyList(static_cast<unsigned>(numActualVertices));
 
      if (quads) {
        generateAdjacencyInfo<IndexType, AdjacencyList, true>(numFaces, indices, positionOffset, adjacencyList);
 
        calculateFaceNormals<VectorType, IndexType, VectorType, true>(numFaces, positions, indices, faceNormals);
      } else {
        generateAdjacencyInfo<IndexType, AdjacencyList, false>(numFaces, indices, positionOffset, adjacencyList);
 
        calculateFaceNormals<VectorType, IndexType, VectorType, false>(numFaces, positions, indices, faceNormals);
      }
 
      if (correctNormals) {
        correctZeroLengthNormals(faceNormals.data(), faceNormals.size());
      }
 
      if (flipNormals) {
        reverseNormalDirections(faceNormals.data(), faceNormals.size());
      }
 
      calculateSmoothVertexNormals(normals, numPositions, faceNormals, positionOffset, adjacencyList);
    }
 
    template<typename VectorType, typename IndexType>
    void generateExtrusionNormals(VectorType * positions, const size_t numVertexes, IndexType * indexes, const size_t numIndexes, int segmentCount, bool quads, bool flipNormals, std::vector<VectorType> & normals)
    {
      if (!numVertexes) return;
      if (!numIndexes) return;
 
      const int numIndicesPerFace = quads ? 5 : 4;
      const int numVertices = numVertexes;
      const int numFaces = numIndexes / numIndicesPerFace;
 
      normals.resize(numVertices);
 
      std::vector<VectorType> faceNormals(numVertices);
      std::vector<AdjacencyList> adjacencyList(numVertices);
 
      if (quads) {
        generateAdjacencyInfo<IndexType, AdjacencyList, true>(numFaces, indexes, 0, adjacencyList);
      } else {
        generateAdjacencyInfo<IndexType, AdjacencyList, false>(numFaces, indexes, 0, adjacencyList);
      }
 
      if (quads) {
        addExtrusionSeamFaces(numFaces, segmentCount, adjacencyList);
      } else {
        addTriangleExtrusionSeamFaces(numFaces, segmentCount, adjacencyList);
      }
 
      if (quads) {
        calculateFaceNormals<VectorType, IndexType, VectorType, true>(numFaces, positions, indexes, faceNormals);
      } else {
        calculateFaceNormals<VectorType, IndexType, VectorType, false>(numFaces, positions, indexes, faceNormals);
      }
 
      if (flipNormals) {
        reverseNormalDirections(faceNormals.data(), faceNormals.size());
      }
 
      calculateSmoothVertexNormals(normals, numVertices, faceNormals, 0, adjacencyList);
    }
 
    template<typename VectorType, typename IndexType, typename Vector2Type>
    void generateFacetNormals(
      const VectorType * positions,
      const size_t numPositions,
      const IndexType * indexes,
      const size_t numIndexes,
      const Vector2Type * texCoords,
      bool quads, bool flipNormals, bool correctNormals, const float creaseAngle, bool createExtrusionSeam, const size_t segmentCount,
      std::vector<VectorType> & outputPositions,
      std::vector<VectorType> & outputNormals,
      std::vector<IndexType> & outputIndexes,
      std::vector<Vector2Type> * outputTexCoords)
    {
      if (!numPositions) return;
      if (!numIndexes) return;
 
      const size_t positionOffset = 0;
      const size_t numIndicesPerFace = quads ? 5 : 4;
      const size_t numVertexesPerFace = quads ? 4 : 3;
      const size_t numFaces = numIndexes / numIndicesPerFace;
      const size_t numActualVertices = numPositions - positionOffset;
 
      std::vector<VectorType> faceNormals(numFaces);
      std::vector<AdjacencyList> adjacencyList(numActualVertices);
 
      if (quads) {
        generateAdjacencyInfo<IndexType, AdjacencyList, true>(numFaces, indexes, positionOffset, adjacencyList);
      } else {
        generateAdjacencyInfo<IndexType, AdjacencyList, false>(numFaces, indexes, positionOffset, adjacencyList);
      }
 
      if (createExtrusionSeam) {
        if (quads) {
          addExtrusionSeamFaces(numFaces, segmentCount - 1, adjacencyList);
        } else {
          addTriangleExtrusionSeamFaces(numFaces, segmentCount - 1, adjacencyList);
        }
      }
 
      if (quads) {
        calculateFaceNormals<VectorType, IndexType, VectorType, true>(numFaces, positions, indexes, faceNormals);
      } else {
        calculateFaceNormals<VectorType, IndexType, VectorType, false>(numFaces, positions, indexes, faceNormals);
      }
 
      if (correctNormals) {
        correctZeroLengthNormals(faceNormals.data(), faceNormals.size());
      }
 
      if (flipNormals) {
        reverseNormalDirections(faceNormals.data(), faceNormals.size());
      }
 
      outputNormals.resize(numFaces * numVertexesPerFace);
      outputPositions.resize(numFaces * numVertexesPerFace);
 
      VectorType * normal = outputNormals.data();
      VectorType * position = outputPositions.data();
 
      calculateFacetVertexNormals(faceNormals, adjacencyList, indexes, creaseAngle, quads, normal);
 
      reindexValues(positions, indexes, numFaces, numIndicesPerFace, position);
 
      if (texCoords) {
        outputTexCoords->resize(numFaces * numVertexesPerFace);
 
        reindexValues(texCoords, indexes, numFaces, numIndicesPerFace, outputTexCoords->data());
      }
 
      outputIndexes.resize(numFaces * numIndicesPerFace);
      IndexType * newIndex = outputIndexes.data();
 
      if (quads) {
        generateLinearIndexes<IndexType, true>(numFaces, newIndex);
      } else {
        generateLinearIndexes<IndexType, false>(numFaces, newIndex);
      }
    }
  }
}