home *** CD-ROM | disk | FTP | other *** search
/ Maximum CD 2007 September / maximum-cd-2007-09.iso / Assets / data / AssaultCube_v0.93.exe / source / src / tristrip.h < prev    next >
Encoding:
C/C++ Source or Header  |  2007-06-03  |  8.2 KB  |  267 lines
  1. VAR(dbgts, 0, 0, 1);
  2. VAR(tsswap, 0, 1, 1);
  3.  
  4. struct tristrip
  5. {
  6.     enum
  7.     {
  8.         // must be larger than all other triangle/vert indices
  9.         UNUSED  = 0xFFFE,
  10.         REMOVED = 0xFFFF
  11.     };
  12.  
  13.     enum
  14.     {
  15.         // must be larger than all other vert indices
  16.         RESTART = 0xFFFE,
  17.         LIST    = 0xFFFF
  18.     };
  19.  
  20.     struct triangle
  21.     {
  22.         ushort v[3], n[3];
  23.  
  24.         bool link(ushort neighbor, ushort old = UNUSED)
  25.         {
  26.             loopi(3)
  27.             {
  28.                 if(n[i]==neighbor) return true;
  29.                 else if(n[i]==old) { n[i] = neighbor; return true; }
  30.             }
  31.             if(dbgts && old==UNUSED) conoutf("excessive links");
  32.             return false;
  33.         }    
  34.  
  35.         void unlink(ushort neighbor, ushort unused = UNUSED)
  36.         {
  37.             loopi(3) if(n[i]==neighbor) n[i] = unused;
  38.         }
  39.  
  40.         int numlinks() const { int num = 0; loopi(3) if(n[i]<UNUSED) num++; return num; }
  41.  
  42.         bool hasvert(ushort idx) const { loopi(3) if(v[i]==idx) return true; return false; }
  43.         ushort diffvert(ushort v1, ushort v2) { loopi(3) if(v[i]!=v1 && v[i]!=v2) return v[i]; return UNUSED; }
  44.  
  45.         bool haslink(ushort neighbor) const { loopi(3) if(n[i]==neighbor) return true; return false; }
  46.     };
  47.  
  48.     vector<triangle> triangles;
  49.     vector<ushort> connectivity[4];
  50.     vector<uchar> nodes;
  51.  
  52.     void addtriangles(const ushort *triidxs, int numtris)
  53.     {
  54.         if(dbgts) conoutf("addtriangles: tris = %d, inds = %d", numtris, numtris*3);
  55.         loopi(numtris)
  56.         {
  57.             triangle &tri = triangles.add();
  58.             loopj(3) 
  59.             {
  60.                 tri.v[j] = *triidxs++;
  61.                 tri.n[j] = UNUSED;
  62.             }
  63.             if(tri.v[0]==tri.v[1] || tri.v[1]==tri.v[2] || tri.v[2]==tri.v[0])
  64.             {
  65.                 if(dbgts) conoutf("degenerate triangle");
  66.                 triangles.drop();
  67.             }
  68.         }
  69.     }
  70.  
  71.     struct edge { ushort from, to; };
  72.  
  73.     void findconnectivity()
  74.     {
  75.         hashtable<edge, ushort> edges;
  76.         nodes.setsizenodelete(0);
  77.         loopv(triangles)
  78.         {
  79.             triangle &tri = triangles[i];
  80.             loopj(3)
  81.             {
  82.                 edge e = { tri.v[j==2 ? 0 : j+1], tri.v[j] };
  83.                 ushort owner = i;
  84.                 edges.access(e, &owner);
  85.  
  86.                 while(nodes.length()<=tri.v[j]) nodes.add(0);
  87.                 nodes[tri.v[j]]++;
  88.             }
  89.         }
  90.         loopv(triangles)
  91.         {
  92.             triangle &tri = triangles[i];
  93.             loopj(3)
  94.             {
  95.                 edge e = { tri.v[j], tri.v[j==2 ? 0 : j+1] };
  96.                 ushort *owner = edges.access(e);
  97.                 if(!owner) continue;
  98.                 else if(!tri.link(*owner))
  99.                 {
  100.                     if(dbgts) conoutf("failed linkage 1: %d -> %d", *owner, i);
  101.                 }
  102.                 else if(!triangles[*owner].link(i))
  103.                 {
  104.                     if(dbgts) conoutf("failed linkage 2: %d -> %d", *owner, i);
  105.                     tri.unlink(*owner);
  106.                 }
  107.             }
  108.         }
  109.         loopi(4) connectivity[i].setsizenodelete(0);
  110.         loopv(triangles) connectivity[triangles[i].numlinks()].add(i);
  111.         if(dbgts) conoutf("no connections: %d", connectivity[0].length());
  112.     }
  113.  
  114.     void removeconnectivity(ushort i)
  115.     {
  116.         triangle &tri = triangles[i];
  117.         loopj(3) if(tri.n[j]<UNUSED)
  118.         {
  119.             triangle &neighbor = triangles[tri.n[j]];
  120.             int conn = neighbor.numlinks();
  121.             bool linked = false;
  122.             loopk(3) if(neighbor.n[k]==i) { linked = true; neighbor.n[k] = REMOVED; break; }
  123.             if(linked)
  124.             {
  125.                 connectivity[conn].replacewithlast(tri.n[j]);
  126.                 connectivity[conn-1].add(tri.n[j]);
  127.             }
  128.         }
  129.         removenodes(i);
  130.     }
  131.  
  132.     bool remaining() const
  133.     {
  134.         loopi(4) if(!connectivity[i].empty()) return true;
  135.         return false;
  136.     }
  137.  
  138.     ushort leastconnected()
  139.     {
  140.         loopi(4) if(!connectivity[i].empty()) 
  141.         { 
  142.             ushort least = connectivity[i].pop();
  143.             removeconnectivity(least);
  144.             return least;
  145.         }
  146.         return UNUSED;
  147.     }
  148.  
  149.     int findedge(const triangle &from, const triangle &to, ushort v = UNUSED)
  150.     {
  151.         loopi(3) loopj(3)
  152.         {
  153.             if(from.v[i]==to.v[j] && from.v[i]!=v) return i;
  154.         }
  155.         return -1;
  156.     }
  157.  
  158.     void removenodes(int i)
  159.     {
  160.         loopj(3) nodes[triangles[i].v[j]]--;
  161.     }
  162.  
  163.     ushort nexttriangle(triangle &tri, bool &nextswap, ushort v1 = UNUSED, ushort v2 = UNUSED)
  164.     {
  165.         ushort next = UNUSED;
  166.         int nextscore = 777;
  167.         nextswap = false;
  168.         loopi(3) if(tri.n[i]<UNUSED)
  169.         {
  170.             triangle &nexttri = triangles[tri.n[i]];
  171.             int score = nexttri.numlinks();
  172.             bool swap = false; 
  173.             if(v1!=UNUSED) 
  174.             {
  175.                 if(!nexttri.hasvert(v1))
  176.                 {
  177.                     swap = true;
  178.                     score += nodes[v2] > nodes[v1] ? 1 : -1;
  179.                 }
  180.                 else if(nexttri.hasvert(v2)) continue;
  181.                 else score += nodes[v1] > nodes[v2] ? 1 : -1;
  182.                 if(!tsswap && swap) continue;
  183.                 score += swap ? 1 : -1;
  184.             }
  185.             if(score < nextscore) { next = tri.n[i]; nextswap = swap; nextscore = score; }
  186.         }
  187.         if(next!=UNUSED) 
  188.         {
  189.             tri.unlink(next, REMOVED);
  190.             connectivity[triangles[next].numlinks()].replacewithlast(next);
  191.             removeconnectivity(next);
  192.         }
  193.         return next;
  194.     }
  195.  
  196.     void buildstrip(vector<ushort> &strip, bool reverse = false, bool prims = false)
  197.     {
  198.         ushort prev = leastconnected();
  199.         if(prev==UNUSED) return;
  200.         triangle &first = triangles[prev];
  201.         bool doswap;
  202.         ushort cur = nexttriangle(first, doswap);
  203.         if(cur==UNUSED)
  204.         {
  205.             loopi(3) strip.add(first.v[!prims && reverse && i>=1 ? 3-i : i]);
  206.             return;
  207.         }
  208.         int from = findedge(first, triangles[cur]), 
  209.             to = findedge(first, triangles[cur], first.v[from]);
  210.         if(from+1!=to) swap(int, from, to); 
  211.         strip.add(first.v[(to+1)%3]);
  212.         if(reverse) swap(int, from, to);
  213.         strip.add(first.v[from]);
  214.         strip.add(first.v[to]);
  215.  
  216.         ushort v1 = first.v[to], v2 = first.v[from];
  217.         while(cur!=UNUSED)
  218.         {
  219.             prev = cur;
  220.             cur = nexttriangle(triangles[prev], doswap, v1, v2);
  221.             if(doswap) strip.add(v2);
  222.             ushort v = triangles[prev].diffvert(v1, v2);
  223.             strip.add(v);
  224.             if(!doswap) v2 = v1;
  225.             v1 = v;
  226.         }
  227.  
  228.     }
  229.  
  230.     void buildstrips(vector<ushort> &strips, bool prims = true, bool degen = false)
  231.     {
  232.         vector<ushort> singles;
  233.         findconnectivity();
  234.         int numtris = 0, numstrips = 0;
  235.         while(remaining())
  236.         {
  237.             vector<ushort> strip;
  238.             bool reverse = degen && !strips.empty() && (strips.length()&1);
  239.             buildstrip(strip, reverse, prims);
  240.             numstrips++;
  241.             numtris += strip.length()-2;
  242.             if(strip.length()==3 && prims)
  243.             {
  244.                 loopv(strip) singles.add(strip[i]);
  245.                 continue;
  246.             }
  247.             if(!strips.empty())
  248.             {
  249.                 if(degen) { strips.dup(); strips.add(strip[0]); }
  250.                 else strips.add(RESTART);
  251.             }
  252.             loopv(strip) strips.add(strip[i]);
  253.         }
  254.         if(prims && !singles.empty())
  255.         {
  256.             strips.add(LIST);
  257.             loopv(singles) strips.add(singles[i]);
  258.         }
  259.         if(dbgts) conoutf("strips = %d, tris = %d, inds = %d, merges = %d", numstrips, numtris, numtris + numstrips*2, (degen ? 2 : 1)*(numstrips-1));
  260.     }
  261.  
  262. };
  263.  
  264. static inline uint hthash(const tristrip::edge &x) { return x.from^x.to; }
  265. static inline bool htcmp(const tristrip::edge &x, const tristrip::edge &y) { return x.from==y.from && x.to==y.to; }
  266.             
  267.