Visualization Library: X:/dropbox/visualizationlibrary/src/vlGraphics/DoubleVertexRemover.cpp Source File

Go to the documentation of this file.
00001 /**************************************************************************************/
00002 /*                                                                                    */
00003 /*  Visualization Library                                                             */
00004 /*  http://www.visualizationlibrary.org                                               */
00005 /*                                                                                    */
00006 /*  Copyright (c) 2005-2010, Michele Bosi                                             */
00007 /*  All rights reserved.                                                              */
00008 /*                                                                                    */
00009 /*  Redistribution and use in source and binary forms, with or without modification,  */
00010 /*  are permitted provided that the following conditions are met:                     */
00011 /*                                                                                    */
00012 /*  - Redistributions of source code must retain the above copyright notice, this     */
00013 /*  list of conditions and the following disclaimer.                                  */
00014 /*                                                                                    */
00015 /*  - Redistributions in binary form must reproduce the above copyright notice, this  */
00016 /*  list of conditions and the following disclaimer in the documentation and/or       */
00017 /*  other materials provided with the distribution.                                   */
00018 /*                                                                                    */
00019 /*  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND   */
00020 /*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED     */
00021 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE            */
00022 /*  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR  */
00023 /*  ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES    */
00024 /*  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;      */
00025 /*  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON    */
00026 /*  ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT           */
00027 /*  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS     */
00028 /*  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.                      */
00029 /*                                                                                    */
00030 /**************************************************************************************/
00031 
00032 #include <vlGraphics/DoubleVertexRemover.hpp>
00033 #include <vlCore/Time.hpp>
00034 
00035 using namespace vl;
00036 
00037 namespace
00038 {
00039   class LessCompare
00040   {
00041   public:
00042     LessCompare(const Geometry* geom)
00043     {
00044       if (geom->vertexArray())
00045         mAttribs.push_back(geom->vertexArray());
00046       if (geom->normalArray())
00047         mAttribs.push_back(geom->normalArray());
00048       if (geom->colorArray())
00049         mAttribs.push_back(geom->colorArray());
00050       if (geom->secondaryColorArray())
00051         mAttribs.push_back(geom->secondaryColorArray());
00052       if (geom->fogCoordArray())
00053         mAttribs.push_back(geom->fogCoordArray());
00054       for(int i=0; i<VL_MAX_TEXTURE_UNITS; ++i)
00055         if (geom->texCoordArray(i))
00056           mAttribs.push_back(geom->texCoordArray(i));
00057       for(int i=0; i<geom->vertexAttribArrays()->size(); ++i)
00058         mAttribs.push_back(geom->vertexAttribArrays()->at(i)->data());
00059     }
00060 
00061     bool operator()(u32 a, u32 b) const 
00062     { 
00063       for(unsigned i=0; i<mAttribs.size(); ++i)
00064       {
00065         int val = mAttribs[i]->compare(a,b);
00066         if (val != 0)
00067           return val < 0;
00068       }
00069       return false;
00070     }
00071 
00072   protected:
00073     std::vector< const ArrayAbstract* > mAttribs;
00074   };
00075 
00076   class EqualsCompare
00077   {
00078   public:
00079     EqualsCompare(const Geometry* geom)
00080     {
00081       if (geom->vertexArray())
00082         mAttribs.push_back(geom->vertexArray());
00083       if (geom->normalArray())
00084         mAttribs.push_back(geom->normalArray());
00085       if (geom->colorArray())
00086         mAttribs.push_back(geom->colorArray());
00087       if (geom->secondaryColorArray())
00088         mAttribs.push_back(geom->secondaryColorArray());
00089       if (geom->fogCoordArray())
00090         mAttribs.push_back(geom->fogCoordArray());
00091       for(int i=0; i<VL_MAX_TEXTURE_UNITS; ++i)
00092         if (geom->texCoordArray(i))
00093           mAttribs.push_back(geom->texCoordArray(i));
00094       for(int i=0; i<geom->vertexAttribArrays()->size(); ++i)
00095         mAttribs.push_back(geom->vertexAttribArrays()->at(i)->data());
00096     }
00097 
00098     bool operator()(u32 a, u32 b) const 
00099     { 
00100       for(unsigned i=0; i<mAttribs.size(); ++i)
00101       {
00102         if (mAttribs[i]->compare(a,b) != 0)
00103           return false;
00104       }
00105       return true;
00106     }
00107 
00108   protected:
00109     std::vector< const ArrayAbstract* > mAttribs;
00110   };
00111 }
00112 
00113 //-----------------------------------------------------------------------------
00114 template<class T>
00115 ref<ArrayAbstract> VertexMapper::regenerateT(ArrayAbstract* data, const std::vector<u32>& map_new_to_old) const
00116 {
00117   ref<T> in_data = cast<T>(data);
00118   if (in_data)
00119   {
00120     ref<T> out_data = new T;
00121     out_data->resize(map_new_to_old.size());
00122     for(unsigned i=0; i<map_new_to_old.size(); ++i)
00123         out_data->at(i) = in_data->at(map_new_to_old[i]);
00124     return out_data;
00125   }
00126   return NULL;
00127 }
00128 //-----------------------------------------------------------------------------
00129 ref<ArrayAbstract> VertexMapper::regenerate(ArrayAbstract* data, const std::vector<u32>& map_new_to_old) const
00130 {
00131   ref<ArrayAbstract> out_data;
00132 
00133   if ( (out_data = regenerateT<ArrayInt4>(data, map_new_to_old)) )
00134     return out_data;
00135   else
00136   if ( (out_data = regenerateT<ArrayInt3>(data, map_new_to_old)) )
00137     return out_data;
00138   else
00139   if ( (out_data = regenerateT<ArrayInt2>(data, map_new_to_old)) )
00140     return out_data;
00141   else
00142   if ( (out_data = regenerateT<ArrayUInt4>(data, map_new_to_old)) )
00143     return out_data;
00144   else
00145   if ( (out_data = regenerateT<ArrayUInt3>(data, map_new_to_old)) )
00146     return out_data;
00147   else
00148   if ( (out_data = regenerateT<ArrayUInt2>(data, map_new_to_old)) )
00149     return out_data;
00150   else
00151   if ( (out_data = regenerateT<ArrayFloat4>(data, map_new_to_old)) )
00152     return out_data;
00153   else
00154   if ( (out_data = regenerateT<ArrayFloat3>(data, map_new_to_old)) )
00155     return out_data;
00156   else
00157   if ( (out_data = regenerateT<ArrayFloat2>(data, map_new_to_old)) )
00158     return out_data;
00159   else
00160   if ( (out_data = regenerateT<ArrayDouble4>(data, map_new_to_old)) )
00161     return out_data;
00162   else
00163   if ( (out_data = regenerateT<ArrayDouble3>(data, map_new_to_old)) )
00164     return out_data;
00165   else
00166   if ( (out_data = regenerateT<ArrayDouble2>(data, map_new_to_old)) )
00167     return out_data;
00168   else
00169   if ( (out_data = regenerateT<ArrayFloat1>(data, map_new_to_old)) )
00170     return out_data;
00171   else
00172   if ( (out_data = regenerateT<ArrayDouble1>(data, map_new_to_old)) )
00173     return out_data;
00174   else
00175   if ( (out_data = regenerateT<ArrayUInt1>(data, map_new_to_old)) )
00176     return out_data;
00177   else
00178   if ( (out_data = regenerateT<ArrayInt1>(data, map_new_to_old)) )
00179     return out_data;
00180   else
00181   if ( (out_data = regenerateT<ArrayByte1>(data, map_new_to_old)) )
00182     return out_data;
00183   else
00184   if ( (out_data = regenerateT<ArrayShort1>(data, map_new_to_old)) )
00185     return out_data;
00186   else
00187   if ( (out_data = regenerateT<ArrayUByte1>(data, map_new_to_old)) )
00188     return out_data;
00189   else
00190   if ( (out_data = regenerateT<ArrayUShort1>(data, map_new_to_old)) )
00191     return out_data;
00192   else
00193   if ( (out_data = regenerateT<ArrayUByte2>(data, map_new_to_old)) )
00194     return out_data;
00195   else
00196   if ( (out_data = regenerateT<ArrayUByte3>(data, map_new_to_old)) )
00197     return out_data;
00198   else
00199   if ( (out_data = regenerateT<ArrayUByte4>(data, map_new_to_old)) )
00200     return out_data;
00201   else
00202   if ( (out_data = regenerateT<ArrayByte2>(data, map_new_to_old)) )
00203     return out_data;
00204   else
00205   if ( (out_data = regenerateT<ArrayByte3>(data, map_new_to_old)) )
00206     return out_data;
00207   else
00208   if ( (out_data = regenerateT<ArrayByte4>(data, map_new_to_old)) )
00209     return out_data;
00210   else
00211   if ( (out_data = regenerateT<ArrayShort2>(data, map_new_to_old)) )
00212     return out_data;
00213   else
00214   if ( (out_data = regenerateT<ArrayShort3>(data, map_new_to_old)) )
00215     return out_data;
00216   else
00217   if ( (out_data = regenerateT<ArrayShort4>(data, map_new_to_old)) )
00218     return out_data;
00219   else
00220   if ( (out_data = regenerateT<ArrayUShort2>(data, map_new_to_old)) )
00221     return out_data;
00222   else
00223   if ( (out_data = regenerateT<ArrayUShort3>(data, map_new_to_old)) )
00224     return out_data;
00225   else
00226   if ( (out_data = regenerateT<ArrayUShort4>(data, map_new_to_old)) )
00227     return out_data;
00228 
00229   return NULL;
00230 }
00231 //-----------------------------------------------------------------------------
00232 void DoubleVertexRemover::removeDoubles(Geometry* geom)
00233 {
00234   Time timer;
00235   timer.start();
00236 
00237   mMapNewToOld.clear();
00238   mMapOldToNew.clear();
00239 
00240   u32 vert_count = (u32)(geom->vertexArray() ? geom->vertexArray()->size() : geom->vertexAttribArray(VA_Position) ? geom->vertexAttribArray(VA_Position)->data()->size() : 0);
00241   
00242   VL_CHECK(vert_count);
00243   if (!vert_count)
00244     return;
00245 
00246   std::vector<u32> verti;
00247   verti.resize(vert_count);
00248   mMapOldToNew.resize(vert_count);
00249 
00250   for(u32 i=0; i<verti.size(); ++i)
00251   {
00252     verti[i] = i;
00253     mMapOldToNew[i] = 0xFFFFFFFF;
00254   }
00255 
00256   std::sort(verti.begin(), verti.end(), LessCompare(geom));
00257   EqualsCompare equal_vertex(geom);
00258   mMapNewToOld.reserve(vert_count);
00259   u32 unique_vert_idx = 0;
00260   for(unsigned i=1; i<verti.size(); ++i)
00261   {
00262     if ( !equal_vertex(verti[unique_vert_idx], verti[i]) )
00263     {
00264       for(unsigned j=unique_vert_idx; j<i; ++j)
00265         mMapOldToNew[verti[j]] = (u32)mMapNewToOld.size();
00266       mMapNewToOld.push_back(verti[unique_vert_idx]);
00267       unique_vert_idx = i;
00268     }
00269   }
00270   for(unsigned j=unique_vert_idx; j<verti.size(); ++j)
00271   {
00272     mMapOldToNew[verti[j]] = (u32)mMapNewToOld.size();
00273     mMapNewToOld.push_back(verti[unique_vert_idx]);
00274   }
00275 
00276   // regenerate vertices
00277 
00278   geom->regenerateVertices(mMapNewToOld);
00279 
00280   // regenerate DrawCall
00281 
00282   std::vector< ref<DrawCall> > draw_cmd;
00283   for(int idraw=0; idraw<geom->drawCalls()->size(); ++idraw)
00284     draw_cmd.push_back( geom->drawCalls()->at(idraw) );
00285   geom->drawCalls()->clear();
00286 
00287   for(u32 idraw=0; idraw<draw_cmd.size(); ++idraw)
00288   {
00289     ref<DrawElementsUInt> de = new DrawElementsUInt( draw_cmd[idraw]->primitiveType() );
00290     geom->drawCalls()->push_back(de.get());
00291     const u32 idx_count = draw_cmd[idraw]->countIndices();
00292     de->indexBuffer()->resize(idx_count);
00293     u32 i=0;
00294     for(IndexIterator it = draw_cmd[idraw]->indexIterator(); it.hasNext(); it.next(), ++i)
00295       de->indexBuffer()->at(i) = mMapOldToNew[it.index()];
00296   }
00297 
00298   Log::debug( Say("DoubleVertexRemover : time=%.2ns, verts=%n/%n, saved=%n, ratio=%.2n\n") << timer.elapsed() << mMapNewToOld.size() << verti.size() << verti.size() - mMapNewToOld.size() << (float)mMapNewToOld.size()/verti.size() );
00299 }
00300 //-----------------------------------------------------------------------------