fork(2) download
copy 
  1. #include <iostream> 
  2. #include <array>
  3. #include <vector>
  4. #include <map>
  5.  
  6. using TIndices  = std::vector<int>;
  7. using TFace     = std::array<int, 3>;
  8. using TFaces    = std::vector<TFace>;
  9. using TVertex   = std::array<float, 3>;
  10. using TVertices = std::vector<TVertex>;
  11.  
  12. void GenerateAdjacencies( const TVertices &vertices, const TFaces &faces, TIndices &adj )
  13.     {
  14.         // associate each geometric vertex position with an unique ID
  15.         std::vector<int>      uniqueMap;
  16.         std::map<TVertex,int> tempUniqueVertices;
  17.         int uniqueIndex = 0;
  18.         for ( size_t vI = 0; vI < vertices.size(); ++ vI )
  19.         {
  20.             auto vIt = tempUniqueVertices.find( vertices[vI] );
  21.             if ( vIt == tempUniqueVertices.end() )
  22.             {
  23.                 tempUniqueVertices[ vertices[vI] ] = uniqueIndex;
  24.                 uniqueMap.push_back( uniqueIndex );
  25.                 uniqueIndex ++;
  26.             }
  27.             else
  28.                 uniqueMap.push_back( vIt->second );
  29.         }
  30.         tempUniqueVertices.clear();
  31.  
  32.         // find all edges and associate the edge with all the points, which form a triangle with it. 
  33.         std::map< std::tuple<int, int>, std::vector<int> > edges;
  34.         for ( auto & f : faces )
  35.         {
  36.           for ( int pI = 0; pI < 3; ++ pI )
  37.           {
  38.             int edgeU[2]{ uniqueMap[f[pI]], uniqueMap[f[(pI+1) % 3]] };
  39.             int i0 = edgeU[0] < edgeU[1] ? 0 : 1;
  40.             edges[{ edgeU[i0], edgeU[1-i0] }].push_back( f[(pI+2) % 3] );
  41.           }
  42.         }
  43.  
  44.         // create the adjacencies
  45.         for ( auto & f : faces )
  46.         {
  47.             for ( int pI = 0; pI < 3; ++ pI )
  48.             {
  49.                 int edgeU[2]{ uniqueMap[f[pI]], uniqueMap[f[(pI+1) % 3]] };
  50.                 int   i0   = edgeU[0] < edgeU[1] ? 0 : 1;
  51.                 auto &adjs = edges[{ edgeU[i0], edgeU[1 - i0] }];
  52.                 int   adjI = adjs.size() > 1 && adjs[0] == f[(pI+2) % 3] ? 1 : 0;
  53.                 adj.push_back( f[pI] );
  54.                 adj.push_back( adjs[adjI] );
  55.             }
  56.         }
  57.     }
  58.  
  59. int main( void )
  60. {
  61.     TVertices pt{
  62.         {  1.0f, -1.0f, -1.0f },
  63.         {  1.0f, -1.0f,  1.0f },
  64.         { -1.0f, -1.0f,  1.0f },
  65.         { -1.0f, -1.0f, -1.0f },
  66.         {  1.0f,  1.0f, -1.0f },
  67.         {  1.0f,  1.0f,  1.0f },
  68.         { -1.0f,  1.0f,  1.0f },
  69.         { -1.0f,  1.0f, -1.0f }
  70.     };
  71.  
  72.     TFaces indices{
  73.         { 2, 3, 4 },
  74.         { 8, 7, 6 },
  75.         { 5, 6, 2 },
  76.         { 6, 7, 3 },
  77.         { 3, 7, 8 },
  78.         { 1, 4, 8 },
  79.         { 1, 2, 4 },
  80.         { 5, 8, 6 },
  81.         { 1, 5, 2 },
  82.         { 2, 6, 3 },
  83.         { 4, 3, 8 },
  84.         { 5, 1, 8 }
  85.     };
  86.  
  87.     TVertices vertices;
  88.     TFaces    faces;
  89.     int vI = 0;
  90.     for ( auto &f : indices )
  91.     {
  92.       for ( int i = 0; i < 3; ++ i )
  93.         vertices.push_back( pt[f[i]-1] );
  94.       faces.push_back( { vI++, vI++, vI++ } );
  95.     }
  96.  
  97.     TIndices adj;
  98.     GenerateAdjacencies( vertices, faces, adj );
  99.  
  100.     for ( size_t fI = 0; fI < faces.size(); ++ fI )
  101.     {
  102.         std::cout << "(" << faces[fI][0] << ", " << faces[fI][1] << ", " << faces[fI][2] << ") -> ";
  103.  
  104.         for ( size_t aI = 0; aI < 6; ++ aI )
  105.           std::cout << adj[fI*6+aI] << " ";
  106.         std::cout << std::endl;
  107.     }
  108.  
  109.     return 0;
  110. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(0, 1, 2) -> 0 28 1 32 2 18 
(3, 4, 5) -> 3 12 4 11 5 21 
(6, 7, 8) -> 6 22 7 29 8 24 
(9, 10, 11) -> 9 3 10 14 11 27 
(12, 13, 14) -> 12 9 13 5 14 30 
(15, 16, 17) -> 15 19 16 31 17 33 
(18, 19, 20) -> 18 25 19 1 20 17 
(21, 22, 23) -> 21 34 22 4 23 8 
(24, 25, 26) -> 24 35 25 7 26 20 
(27, 28, 29) -> 27 6 28 10 29 2 
(30, 31, 32) -> 30 0 31 13 32 15 
(33, 34, 35) -> 33 26 34 16 35 23
https://ideone.com/96oXSY
adjacencies
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!