source/collada/GeomReindex.cpp

   1 /* Copyright (C) 2009 Wildfire Games.
   2  * This file is part of 0 A.D.
   3  *
   4  * 0 A.D. is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * 0 A.D. is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include "precompiled.h"
  19
  20 #include "GeomReindex.h"
  21
  22 #include "FCollada.h"
  23 #include "FCDocument/FCDEntity.h"
  24 #include "FCDocument/FCDGeometryMesh.h"
  25 #include "FCDocument/FCDGeometryPolygons.h"
  26 #include "FCDocument/FCDGeometryPolygonsInput.h"
  27 #include "FCDocument/FCDGeometrySource.h"
  28 #include "FCDocument/FCDSkinController.h"
  29
  30 #include <cassert>
  31 #include <vector>
  32 #include <map>
  33 #include <algorithm>
  34
  35 typedef std::pair<float, float> uv_pair_type;
  36
  37 struct VertexData
  38 {
  39         VertexData(const float* pos, const float* norm, const std::vector<uv_pair_type> &uvs,
  40                    const std::vector<FCDJointWeightPair>& weights)
  41                 : x(pos[0]), y(pos[1]), z(pos[2]),
  42                 nx(norm[0]), ny(norm[1]), nz(norm[2]),
  43                 uvs(uvs),
  44                 weights(weights)
  45         {
  46         }
  47
  48         float x, y, z;
  49         float nx, ny, nz;
  50         std::vector<uv_pair_type> uvs;
  51         std::vector<FCDJointWeightPair> weights;
  52 };
  53
  54 bool similar(float a, float b)
  55 {
  56         return (fabsf(a - b) < 0.000001f);
  57 }
  58
  59 bool operator==(const FCDJointWeightPair& a, const FCDJointWeightPair& b)
  60 {
  61         return (a.jointIndex == b.jointIndex && similar(a.weight, b.weight));
  62 }
  63
  64 bool operator<(const FCDJointWeightPair& a, const FCDJointWeightPair& b)
  65 {
  66         // Sort by decreasing weight, then by increasing joint ID
  67         if (a.weight > b.weight)
  68                 return true;
  69         else if (a.weight < b.weight)
  70                 return false;
  71         else if (a.jointIndex < b.jointIndex)
  72                 return true;
  73         else
  74                 return false;
  75 }
  76
  77 bool operator==(const uv_pair_type& a, const uv_pair_type& b)
  78 {
  79         return similar(a.first, b.first) && similar(a.second, b.second);
  80 }
  81
  82 bool operator==(const VertexData& a, const VertexData& b)
  83 {
  84         return (similar(a.x,  b.x)  && similar(a.y,  b.y)  && similar(a.z,  b.z)
  85                  && similar(a.nx, b.nx) && similar(a.ny, b.ny) && similar(a.nz, b.nz)
  86                  && (a.uvs == b.uvs)
  87                  && (a.weights == b.weights));
  88 }
  89
  90 bool operator<(const VertexData& a, const VertexData& b)
  91 {
  92 #define CMP(f) if (a.f < b.f) return true; if (a.f > b.f) return false
  93         CMP(x);  CMP(y);  CMP(z);
  94         CMP(nx); CMP(ny); CMP(nz);
  95         CMP(uvs);
  96         CMP(weights);
  97 #undef CMP
  98         return false;
  99 }
 100
 101 template <typename T>
 102 struct InserterWithoutDuplicates
 103 {
 104         InserterWithoutDuplicates(std::vector<T>& vec) : vec(vec)
 105         {
 106         }
 107
 108         size_t add(const T& val)
 109         {
 110                 typename std::map<T, size_t>::iterator it = btree.find(val);
 111                 if (it != btree.end())
 112                         return it->second;
 113
 114                 size_t idx = vec.size();
 115                 vec.push_back(val);
 116                 btree.insert(std::make_pair(val, idx));
 117                 return idx;
 118         }
 119
 120         std::vector<T>& vec;
 121         std::map<T, size_t> btree; // for faster lookups (so we can build a duplicate-free list in O(n log n) instead of O(n^2))
 122
 123 private:
 124         InserterWithoutDuplicates& operator=(const InserterWithoutDuplicates&);
 125 };
 126
 127 void CanonicaliseWeights(std::vector<FCDJointWeightPair>& weights)
 128 {
 129         // Convert weight-lists into a standard format, so simple vector equality
 130         // can be used to determine equivalence
 131         std::sort(weights.begin(), weights.end());
 132 }
 133
 134 void ReindexGeometry(FCDGeometryPolygons* polys, FCDSkinController* skin)
 135 {
 136         // Given geometry with:
 137         //   positions, normals, texcoords, bone blends
 138         // each with their own data array and index array, change it to
 139         // have a single optimised index array shared by all vertexes.
 140
 141         FCDGeometryPolygonsInput* inputPosition = polys->FindInput(FUDaeGeometryInput::POSITION);
 142         FCDGeometryPolygonsInput* inputNormal   = polys->FindInput(FUDaeGeometryInput::NORMAL);
 143         FCDGeometryPolygonsInput* inputTexcoord = polys->FindInput(FUDaeGeometryInput::TEXCOORD);
 144
 145         size_t numVertices = polys->GetFaceVertexCount();
 146
 147         assert(inputPosition->GetIndexCount() == numVertices);
 148         assert(inputNormal  ->GetIndexCount() == numVertices);
 149         assert(inputTexcoord->GetIndexCount() == numVertices);
 150
 151         const uint32* indicesPosition = inputPosition->GetIndices();
 152         const uint32* indicesNormal   = inputNormal->GetIndices();
 153         const uint32* indicesTexcoord = inputTexcoord->GetIndices();
 154
 155         assert(indicesPosition);
 156         assert(indicesNormal);
 157         assert(indicesTexcoord); // TODO - should be optional, because textureless meshes aren't unreasonable
 158
 159         FCDGeometrySourceList texcoordSources;
 160         polys->GetParent()->FindSourcesByType(FUDaeGeometryInput::TEXCOORD, texcoordSources);
 161
 162         FCDGeometrySource* sourcePosition = inputPosition->GetSource();
 163         FCDGeometrySource* sourceNormal   = inputNormal  ->GetSource();
 164
 165         const float* dataPosition = sourcePosition->GetData();
 166         const float* dataNormal   = sourceNormal  ->GetData();
 167
 168         if (skin)
 169         {
 170 #ifndef NDEBUG
 171                 size_t numVertexPositions = sourcePosition->GetDataCount() / sourcePosition->GetStride();
 172                 assert(skin->GetInfluenceCount() == numVertexPositions);
 173 #endif
 174         }
 175
 176         uint32 stridePosition = sourcePosition->GetStride();
 177         uint32 strideNormal   = sourceNormal  ->GetStride();
 178
 179         std::vector<uint32> indicesCombined;
 180         std::vector<VertexData> vertexes;
 181         InserterWithoutDuplicates<VertexData> inserter(vertexes);
 182
 183         for (size_t i = 0; i < numVertices; ++i)
 184         {
 185                 std::vector<FCDJointWeightPair> weights;
 186                 if (skin)
 187                 {
 188                         FCDSkinControllerVertex* influences = skin->GetVertexInfluence(indicesPosition[i]);
 189                         assert(influences != NULL);
 190                         for (size_t j = 0; j < influences->GetPairCount(); ++j)
 191                         {
 192                                 FCDJointWeightPair* pair = influences->GetPair(j);
 193                                 assert(pair != NULL);
 194                                 weights.push_back(*pair);
 195                         }
 196                         CanonicaliseWeights(weights);
 197                 }
 198
 199                 std::vector<uv_pair_type> uvs;
 200                 for (size_t set = 0; set < texcoordSources.size(); ++set)
 201                 {
 202                         const float* dataTexcoord = texcoordSources[set]->GetData();
 203                         uint32 strideTexcoord = texcoordSources[set]->GetStride();
 204
 205                         uv_pair_type p;
 206                         p.first = dataTexcoord[indicesTexcoord[i]*strideTexcoord];
 207                         p.second = dataTexcoord[indicesTexcoord[i]*strideTexcoord + 1];
 208                         uvs.push_back(p);
 209                 }
 210
 211                 VertexData vtx (
 212                         &dataPosition[indicesPosition[i]*stridePosition],
 213                         &dataNormal  [indicesNormal  [i]*strideNormal],
 214                         uvs,
 215                         weights
 216                 );
 217                 size_t idx = inserter.add(vtx);
 218                 indicesCombined.push_back((uint32)idx);
 219         }
 220
 221         // TODO: rearrange indicesCombined (and rearrange vertexes to match) to use
 222         // the vertex cache efficiently
 223         // (<http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html> etc)
 224
 225         FloatList newDataPosition;
 226         FloatList newDataNormal;
 227         FloatList newDataTexcoord;
 228         std::vector<std::vector<FCDJointWeightPair> > newWeightedMatches;
 229
 230         for (size_t i = 0; i < vertexes.size(); ++i)
 231         {
 232                 newDataPosition.push_back(vertexes[i].x);
 233                 newDataPosition.push_back(vertexes[i].y);
 234                 newDataPosition.push_back(vertexes[i].z);
 235                 newDataNormal  .push_back(vertexes[i].nx);
 236                 newDataNormal  .push_back(vertexes[i].ny);
 237                 newDataNormal  .push_back(vertexes[i].nz);
 238                 newWeightedMatches.push_back(vertexes[i].weights);
 239         }
 240
 241         // (Slightly wasteful to duplicate this array so many times, but FCollada
 242         // doesn't seem to support multiple inputs with the same source data)
 243         inputPosition->SetIndices(&indicesCombined.front(), indicesCombined.size());
 244         inputNormal  ->SetIndices(&indicesCombined.front(), indicesCombined.size());
 245         inputTexcoord->SetIndices(&indicesCombined.front(), indicesCombined.size());
 246
 247         for (size_t set = 0; set < texcoordSources.size(); ++set)
 248         {
 249                 newDataTexcoord.clear();
 250                 for (size_t i = 0; i < vertexes.size(); ++i)
 251                 {
 252                         newDataTexcoord.push_back(vertexes[i].uvs[set].first);
 253                         newDataTexcoord.push_back(vertexes[i].uvs[set].second);
 254                 }
 255                 texcoordSources[set]->SetData(newDataTexcoord, 2);
 256         }
 257
 258         sourcePosition->SetData(newDataPosition, 3);
 259         sourceNormal  ->SetData(newDataNormal,   3);
 260
 261         if (skin)
 262         {
 263                 skin->SetInfluenceCount(newWeightedMatches.size());
 264                 for (size_t i = 0; i < newWeightedMatches.size(); ++i)
 265                 {
 266                         skin->GetVertexInfluence(i)->SetPairCount(0);
 267                         for (size_t j = 0; j < newWeightedMatches[i].size(); ++j)
 268                                 skin->GetVertexInfluence(i)->AddPair(newWeightedMatches[i][j].jointIndex, newWeightedMatches[i][j].weight);
 269                 }
 270         }
 271 }