Extras/ConvexDecomposition/vlookup.cpp

   1 #include "float_math.h"
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <assert.h>
   6
   7 #pragma warning(disable:4786)
   8
   9 #include <vector>
  10 #include <map>
  11 #include <set>
  12
  13
  14 /*----------------------------------------------------------------------
  15                 Copyright (c) 2004 Open Dynamics Framework Group
  16                                         www.physicstools.org
  17                 All rights reserved.
  18
  19                 Redistribution and use in source and binary forms, with or without modification, are permitted provided
  20                 that the following conditions are met:
  21
  22                 Redistributions of source code must retain the above copyright notice, this list of conditions
  23                 and the following disclaimer.
  24
  25                 Redistributions in binary form must reproduce the above copyright notice,
  26                 this list of conditions and the following disclaimer in the documentation
  27                 and/or other materials provided with the distribution.
  28
  29                 Neither the name of the Open Dynamics Framework Group nor the names of its contributors may
  30                 be used to endorse or promote products derived from this software without specific prior written permission.
  31
  32                 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  33                 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  34                 DISCLAIMED. IN NO EVENT SHALL THE INTEL OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  35                 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  36                 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
  37                 IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  38                 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39 -----------------------------------------------------------------------*/
  40
  41 // http://codesuppository.blogspot.com
  42 //
  43 // mailto: jratcliff@infiniplex.net
  44 //
  45 // http://www.amillionpixels.us
  46 //
  47
  48 // CodeSnippet provided by John W. Ratcliff
  49 // on March 23, 2006.
  50 //
  51 // mailto: jratcliff@infiniplex.net
  52 //
  53 // Personal website: http://jratcliffscarab.blogspot.com
  54 // Coding Website:   http://codesuppository.blogspot.com
  55 // FundRaising Blog: http://amillionpixels.blogspot.com
  56 // Fundraising site: http://www.amillionpixels.us
  57 // New Temple Site:  http://newtemple.blogspot.com
  58 //
  59 // This snippet shows how to 'hide' the complexity of
  60 // the STL by wrapping some useful piece of functionality
  61 // around a handful of discrete API calls.
  62 //
  63 // This API allows you to create an indexed triangle list
  64 // from a collection of raw input triangles.  Internally
  65 // it uses an STL set to build the lookup table very rapidly.
  66 //
  67 // Here is how you would use it to build an indexed triangle
  68 // list from a raw list of triangles.
  69 //
  70 // (1) create a 'VertexLookup' interface by calling
  71 //
  72 //     VertexLook vl = Vl_createVertexLookup();
  73 //
  74 // (2) For each vertice in each triangle call:
  75 //
  76 //     unsigned int i1 = Vl_getIndex(vl,p1);
  77 //     unsigned int i2 = Vl_getIndex(vl,p2);
  78 //     unsigned int i3 = Vl_getIndex(vl,p3);
  79 //
  80 //     save the 3 indices into your triangle list array.
  81 //
  82 // (3) Get the vertex array by calling:
  83 //
  84 //     const float *vertices = Vl_getVertices(vl);
  85 //
  86 // (4) Get the number of vertices so you can copy them into
  87 //     your own buffer.
  88 //     unsigned int vcount = Vl_getVcount(vl);
  89 //
  90 // (5) Release the VertexLookup interface when you are done with it.
  91 //     Vl_releaseVertexLookup(vl);
  92 //
  93 // Teaches the following lessons:
  94 //
  95 //    How to wrap the complexity of STL and C++ classes around a
  96 //    simple API interface.
  97 //
  98 //    How to use an STL set and custom comparator operator for
  99 //    a complex data type.
 100 //
 101 //    How to create a template class.
 102 //
 103 //    How to achieve significant performance improvements by
 104 //    taking advantage of built in STL containers in just
 105 //    a few lines of code.
 106 //
 107 //    You could easily modify this code to support other vertex
 108 //    formats with any number of interpolants.
 109
 110
 111
 112
 113 #include "vlookup.h"
 114
 115 namespace Vlookup
 116 {
 117
 118 class VertexPosition
 119 {
 120 public:
 121   VertexPosition(void) { };
 122   VertexPosition(const float *p)
 123   {
 124         mPos[0] = p[0];
 125         mPos[1] = p[1];
 126         mPos[2] = p[2];
 127   };
 128
 129         void Set(int index,const float *pos)
 130         {
 131                 const float * p = &pos[index*3];
 132
 133                 mPos[0]    = p[0];
 134                 mPos[1]    = p[1];
 135                 mPos[2]    = p[2];
 136
 137         };
 138
 139   float GetX(void) const { return mPos[0]; };
 140   float GetY(void) const { return mPos[1]; };
 141   float GetZ(void) const { return mPos[2]; };
 142
 143         float mPos[3];
 144 };
 145
 146 typedef std::vector< VertexPosition > VertexVector;
 147
 148 struct Tracker
 149 {
 150         VertexPosition mFind; // vertice to locate.
 151         VertexVector  *mList;
 152
 153         Tracker()
 154         {
 155                 mList = 0;
 156         }
 157
 158         void SetSearch(const VertexPosition& match,VertexVector *list)
 159         {
 160                 mFind = match;
 161                 mList = list;
 162         };
 163 };
 164
 165 struct VertexID
 166 {
 167         int mID;
 168         Tracker* mTracker;
 169
 170         VertexID(int ID, Tracker* Tracker)
 171         {
 172                 mID = ID;
 173                 mTracker = Tracker;
 174         }
 175 };
 176
 177 class VertexLess
 178 {
 179 public:
 180
 181         bool operator()(VertexID v1,VertexID v2) const;
 182
 183 private:
 184         const VertexPosition& Get(VertexID index) const
 185         {
 186                 if ( index.mID == -1 ) return index.mTracker->mFind;
 187                 VertexVector &vlist = *index.mTracker->mList;
 188                 return vlist[index.mID];
 189         }
 190 };
 191
 192 template <class Type> class VertexPool
 193 {
 194 public:
 195         typedef std::set<VertexID, VertexLess > VertexSet;
 196         typedef std::vector< Type > VertexVector;
 197
 198         int getVertex(const Type& vtx)
 199         {
 200                 mTracker.SetSearch(vtx,&mVtxs);
 201                 VertexSet::iterator found;
 202                 found = mVertSet.find( VertexID(-1,&mTracker) );
 203                 if ( found != mVertSet.end() )
 204                 {
 205                         return found->mID;
 206                 }
 207                 int idx = (int)mVtxs.size();
 208                 mVtxs.push_back( vtx );
 209                 mVertSet.insert( VertexID(idx,&mTracker) );
 210                 return idx;
 211         };
 212
 213
 214         const float * GetPos(int idx) const
 215         {
 216                 return mVtxs[idx].mPos;
 217         }
 218
 219         const Type& Get(int idx) const
 220         {
 221                 return mVtxs[idx];
 222         };
 223
 224         unsigned int GetSize(void) const
 225         {
 226                 return mVtxs.size();
 227         };
 228
 229         void Clear(int reservesize)  // clear the vertice pool.
 230         {
 231                 mVertSet.clear();
 232                 mVtxs.clear();
 233                 mVtxs.reserve(reservesize);
 234         };
 235
 236         const VertexVector& GetVertexList(void) const { return mVtxs; };
 237
 238         void Set(const Type& vtx)
 239         {
 240                 mVtxs.push_back(vtx);
 241         }
 242
 243         unsigned int GetVertexCount(void) const
 244         {
 245                 return mVtxs.size();
 246         };
 247
 248
 249         Type * getBuffer(void)
 250         {
 251                 return &mVtxs[0];
 252         };
 253
 254 private:
 255         VertexSet      mVertSet; // ordered list.
 256         VertexVector   mVtxs;  // set of vertices.
 257         Tracker        mTracker;
 258 };
 259
 260
 261 bool VertexLess::operator()(VertexID v1,VertexID v2) const
 262 {
 263
 264         const VertexPosition& a = Get(v1);
 265         const VertexPosition& b = Get(v2);
 266
 267   int ixA = (int) (a.GetX()*10000.0f);
 268   int ixB = (int) (b.GetX()*10000.0f);
 269
 270         if ( ixA      < ixB      ) return true;
 271         if ( ixA      > ixB      ) return false;
 272
 273   int iyA = (int) (a.GetY()*10000.0f);
 274   int iyB = (int) (b.GetY()*10000.0f);
 275
 276         if ( iyA      < iyB      ) return true;
 277         if ( iyA      > iyB      ) return false;
 278
 279   int izA = (int) (a.GetZ()*10000.0f);
 280   int izB = (int) (b.GetZ()*10000.0f);
 281
 282         if ( izA      < izB      ) return true;
 283         if ( izA      > izB      ) return false;
 284
 285
 286         return false;
 287 }
 288
 289
 290
 291
 292 }
 293
 294 using namespace Vlookup;
 295
 296 VertexLookup Vl_createVertexLookup(void)
 297 {
 298   VertexLookup ret = new VertexPool< VertexPosition >;
 299   return ret;
 300 }
 301
 302 void          Vl_releaseVertexLookup(VertexLookup vlook)
 303 {
 304   VertexPool< VertexPosition > *vp = (VertexPool< VertexPosition > *) vlook;
 305   delete vp;
 306 }
 307
 308 unsigned int  Vl_getIndex(VertexLookup vlook,const float *pos)  // get index.
 309 {
 310   VertexPool< VertexPosition > *vp = (VertexPool< VertexPosition > *) vlook;
 311   VertexPosition p(pos);
 312   return vp->getVertex(p);
 313 }
 314
 315 const float * Vl_getVertices(VertexLookup vlook)
 316 {
 317   VertexPool< VertexPosition > *vp = (VertexPool< VertexPosition > *) vlook;
 318   return vp->GetPos(0);
 319 }
 320
 321
 322 unsigned int  Vl_getVcount(VertexLookup vlook)
 323 {
 324   VertexPool< VertexPosition > *vp = (VertexPool< VertexPosition > *) vlook;
 325   return vp->GetVertexCount();
 326 }