nel/src/3d/mrm_internal.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program 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 Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18
  19 #include "nel/3d/mrm_internal.h"
  20 #include "nel/misc/common.h"
  21
  22
  23 using namespace std;
  24 using namespace NLMISC;
  25
  26 #ifdef DEBUG_NEW
  27 #define new DEBUG_NEW
  28 #endif
  29
  30 namespace NL3D
  31 {
  32
  33
  34 // ***************************************************************************
  35 sint    CMRMSewingMesh::mustCollapseEdge(uint lod, const CMRMEdge &edge, uint &vertToCollapse) const
  36 {
  37         nlassert(lod<_Lods.size());
  38         for(uint i=0;i<_Lods[lod].EdgeToCollapse.size();i++)
  39         {
  40                 if(edge==_Lods[lod].EdgeToCollapse[i])
  41                 {
  42                         // the vertex which must be collapsed is v0.
  43                         vertToCollapse= _Lods[lod].EdgeToCollapse[i].v0;
  44                         return i;
  45                 }
  46         }
  47         // not found
  48         return -1;
  49 }
  50
  51
  52 // ***************************************************************************
  53 sint    CMRMSewingMesh::getNumCollapseEdge(uint lod) const
  54 {
  55         nlassert(lod<_Lods.size());
  56         return (sint)_Lods[lod].EdgeToCollapse.size();
  57 }
  58
  59
  60 // ***************************************************************************
  61 void    CMRMSewingMesh::build(const CMesh::CInterface &meshInt, uint nWantedLods, uint divisor)
  62 {
  63         /* The polygon is MRM-egde-like reduced (pop an edge when needed)
  64                 At each lod we store what edge is collapsed.
  65         */
  66         _Lods.clear();
  67         _Lods.resize(nWantedLods);
  68
  69         // build edge list
  70         std::vector<CMRMEdge>   edgeList;
  71         uint    nMaxEdges= (uint)meshInt.Vertices.size();
  72         edgeList.resize(nMaxEdges);
  73         for(uint i=0;i<nMaxEdges;i++)
  74         {
  75                 edgeList[i].v0= i;
  76                 edgeList[i].v1= (i+1)%nMaxEdges;
  77         }
  78
  79         // build how many edges the coarsest lod will have. At least 3 edge for a correct cross section
  80         sint    nBaseEdges= nMaxEdges/divisor;
  81         nBaseEdges=max(nBaseEdges,3);
  82
  83         // must fill all LODs, from end to start. do not proces last lod since it will be the coarsest mesh (no collapse)
  84         for(uint lod=nWantedLods-1;lod>0;lod--)
  85         {
  86                 // Linear.
  87                 sint    nCurEdges= (sint)floor( 0.5f + nBaseEdges + (nMaxEdges-nBaseEdges) * (float)(lod-1)/(nWantedLods-1) );
  88                 nCurEdges=max(nCurEdges,3);
  89
  90                 // the current edge list is reduced until same size as wanted
  91                 while(nCurEdges<(sint)edgeList.size())
  92                 {
  93                         // search the smallest edge
  94                         float   bestDist= FLT_MAX;
  95                         uint    bestEdgeId= 0;
  96                         for(uint j=0;j<edgeList.size();j++)
  97                         {
  98                                 uint    precEdgeId= (uint)((j + edgeList.size() -1) % edgeList.size());
  99                                 CVector edgeDelta= (meshInt.Vertices[edgeList[j].v1].Pos - meshInt.Vertices[edgeList[j].v0].Pos);
 100
 101                                 // compute dist between 2 verts
 102                                 float   dist= edgeDelta.norm();
 103
 104                                 // compute dir of prec and cur edges
 105                                 CVector curEdgeDir= edgeDelta;
 106                                 CVector precEdgeDir= (meshInt.Vertices[edgeList[precEdgeId].v1].Pos - meshInt.Vertices[edgeList[precEdgeId].v0].Pos);
 107                                 curEdgeDir.normalize();
 108                                 precEdgeDir.normalize();
 109
 110                                 // compute how linear they are from -1 to 1.
 111                                 float   angularPart= curEdgeDir * precEdgeDir;
 112
 113                                 /* The more the edge is linear to the previous edge, the more we can collapse it.
 114                                         If totaly linear (curEdgeDir*precEdgeDir==1), it should be a good idea to collapse it now.
 115                                         But the fact is that this is an interface and we don't know what kind of mesh share those edges
 116                                         (I mean it is possible that neighbors faces are absolutely not coplanar).
 117                                         So don't add to much importance on Angular Part
 118                                 */
 119                                 const float     angularBias= 1; // if 0, 2 linear edges will collapse asap.
 120                                 dist*= angularBias + 1-angularPart;
 121
 122                                 // take min dist
 123                                 if(dist<bestDist)
 124                                 {
 125                                         bestDist= dist;
 126                                         bestEdgeId= j;
 127                                 }
 128                         }
 129
 130                         // mark as remove it
 131                         _Lods[lod].EdgeToCollapse.push_back(edgeList[bestEdgeId]);
 132                         // changes vert ids of the prec edge. eg: edge(12) is deleted=> 01 12 23... becomes 02 23 (NB: 1 is collapsed to 2)
 133                         uint    precEdgeId= (uint)((bestEdgeId+edgeList.size()-1)%edgeList.size());
 134                         edgeList[precEdgeId].v1= edgeList[bestEdgeId].v1;
 135                         // and erase the edge from the current list
 136                         edgeList.erase( edgeList.begin()+bestEdgeId );
 137                 }
 138         }
 139
 140 }
 141
 142
 143 } // NL3D