openmesh: StripifierT.cc Source File

00001 /*===========================================================================*\
00002  *                                                                           *
00003  *                               OpenMesh                                    *
00004  *      Copyright (C) 2001-2011 by Computer Graphics Group, RWTH Aachen      *
00005  *                           www.openmesh.org                                *
00006  *                                                                           *
00007  *---------------------------------------------------------------------------* 
00008  *  This file is part of OpenMesh.                                           *
00009  *                                                                           *
00010  *  OpenMesh is free software: you can redistribute it and/or modify         * 
00011  *  it under the terms of the GNU Lesser General Public License as           *
00012  *  published by the Free Software Foundation, either version 3 of           *
00013  *  the License, or (at your option) any later version with the              *
00014  *  following exceptions:                                                    *
00015  *                                                                           *
00016  *  If other files instantiate templates or use macros                       *
00017  *  or inline functions from this file, or you compile this file and         *
00018  *  link it with other files to produce an executable, this file does        *
00019  *  not by itself cause the resulting executable to be covered by the        *
00020  *  GNU Lesser General Public License. This exception does not however       *
00021  *  invalidate any other reasons why the executable file might be            *
00022  *  covered by the GNU Lesser General Public License.                        *
00023  *                                                                           *
00024  *  OpenMesh is distributed in the hope that it will be useful,              *
00025  *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
00026  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
00027  *  GNU Lesser General Public License for more details.                      *
00028  *                                                                           *
00029  *  You should have received a copy of the GNU LesserGeneral Public          *
00030  *  License along with OpenMesh.  If not,                                    *
00031  *  see <http://www.gnu.org/licenses/>.                                      *
00032  *                                                                           *
00033 \*===========================================================================*/ 
00034 
00035 /*===========================================================================*\
00036  *                                                                           *             
00037  *   $Revision: 362 $                                                         *
00038  *   $Date: 2011-01-26 10:21:12 +0100 (Mi, 26 Jan 2011) $                   *
00039  *                                                                           *
00040 \*===========================================================================*/
00041 
00042 //=============================================================================
00043 //
00044 //  CLASS StripifierT - IMPLEMENTATION
00045 //
00046 //=============================================================================
00047 
00048 #define OPENMESH_STRIPIFIERT_C
00049 
00050 //== INCLUDES =================================================================
00051 
00052 #include <OpenMesh/Tools/Utils/StripifierT.hh>
00053 #include <list>
00054 
00055 
00056 //== NAMESPACES ===============================================================
00057 
00058 namespace OpenMesh {
00059 
00060 
00061   //== IMPLEMENTATION ==========================================================
00062 
00063 template <class Mesh>
00064 StripifierT<Mesh>::
00065 StripifierT(Mesh& _mesh) :
00066     mesh_(_mesh)
00067 {
00068 
00069 }
00070 
00071 template <class Mesh>
00072 StripifierT<Mesh>::
00073 ~StripifierT() {
00074 
00075 }
00076 
00077 template <class Mesh>
00078 unsigned int
00079 StripifierT<Mesh>::
00080 stripify()
00081 {
00082   // preprocess:  add new properties
00083   mesh_.add_property( processed_ );
00084   mesh_.add_property( used_ );
00085   mesh_.request_face_status();
00086 
00087   // build strips
00088   clear();
00089   build_strips();
00090 
00091   // postprocess:  remove properties
00092   mesh_.remove_property(processed_);
00093   mesh_.remove_property(used_);
00094   mesh_.release_face_status();
00095 
00096   return n_strips();
00097 }
00098 
00099 
00100 //-----------------------------------------------------------------------------
00101 
00102 
00103 template <class Mesh>
00104 void
00105 StripifierT<Mesh>::
00106 build_strips()
00107 {
00108   Strip                           experiments[3];
00109   typename Mesh::HalfedgeHandle   h[3];
00110   unsigned int                    best_idx, best_length, length;
00111   FaceHandles                     faces[3];
00112   typename FaceHandles::iterator  fh_it, fh_end;
00113   typename Mesh::FaceIter         f_it, f_end=mesh_.faces_end();
00114 
00115 
00116 
00117   // init faces to be un-processed and un-used
00118   // deleted or hidden faces are marked processed
00119   if (mesh_.has_face_status())
00120   {
00121     for (f_it=mesh_.faces_begin(); f_it!=f_end; ++f_it)
00122       if (mesh_.status(f_it).hidden() || mesh_.status(f_it).deleted())
00123         processed(f_it) = used(f_it) = true;
00124       else
00125         processed(f_it) = used(f_it) = false;
00126   }
00127   else
00128   {
00129     for (f_it=mesh_.faces_begin(); f_it!=f_end; ++f_it)
00130       processed(f_it) = used(f_it) = false;
00131   }
00132 
00133 
00134 
00135   for (f_it=mesh_.faces_begin(); true; )
00136   {
00137     // find start face
00138     for (; f_it!=f_end; ++f_it)
00139       if (!processed(f_it))
00140         break;
00141     if (f_it==f_end) break; // stop if all have been processed
00142 
00143 
00144     // collect starting halfedges
00145     h[0] = mesh_.halfedge_handle(f_it.handle());
00146     h[1] = mesh_.next_halfedge_handle(h[0]);
00147     h[2] = mesh_.next_halfedge_handle(h[1]);
00148 
00149 
00150     // build 3 strips, take best one
00151     best_length = best_idx = 0;
00152     for (unsigned int i=0; i<3; ++i)
00153     {
00154       build_strip(h[i], experiments[i], faces[i]);
00155       if ((length = experiments[i].size()) > best_length)
00156       {
00157         best_length = length;
00158         best_idx    = i;
00159       }
00160 
00161       for (fh_it=faces[i].begin(), fh_end=faces[i].end();
00162            fh_it!=fh_end; ++fh_it)
00163         used(*fh_it) = false;
00164     }
00165 
00166 
00167     // update processed status
00168     fh_it  = faces[best_idx].begin();
00169     fh_end = faces[best_idx].end();
00170     for (; fh_it!=fh_end; ++fh_it)
00171       processed(*fh_it) = true;
00172 
00173 
00174 
00175     // add best strip to strip-list
00176     strips_.push_back(experiments[best_idx]);
00177   }
00178 }
00179 
00180 
00181 //-----------------------------------------------------------------------------
00182 
00183 
00184 template <class Mesh>
00185 void
00186 StripifierT<Mesh>::
00187 build_strip(typename Mesh::HalfedgeHandle _start_hh,
00188             Strip& _strip,
00189             FaceHandles& _faces)
00190 {
00191   std::list<unsigned int>  strip;
00192   typename Mesh::HalfedgeHandle   hh;
00193   typename Mesh::FaceHandle       fh;
00194 
00195 
00196   // reset face list
00197   _faces.clear();
00198 
00199 
00200   // init strip
00201   strip.push_back(mesh_.from_vertex_handle(_start_hh).idx());
00202   strip.push_back(mesh_.to_vertex_handle(_start_hh).idx());
00203 
00204 
00205   // walk along the strip: 1st direction
00206   hh = mesh_.prev_halfedge_handle(mesh_.opposite_halfedge_handle(_start_hh));
00207   while (1)
00208   {
00209     // go right
00210     hh = mesh_.next_halfedge_handle(hh);
00211     hh = mesh_.opposite_halfedge_handle(hh);
00212     hh = mesh_.next_halfedge_handle(hh);
00213     if (mesh_.is_boundary(hh)) break;
00214     fh = mesh_.face_handle(hh);
00215     if (processed(fh) || used(fh)) break;
00216     _faces.push_back(fh);
00217     used(fh) = true;
00218     strip.push_back(mesh_.to_vertex_handle(hh).idx());
00219 
00220     // go left
00221     hh = mesh_.opposite_halfedge_handle(hh);
00222     hh = mesh_.next_halfedge_handle(hh);
00223     if (mesh_.is_boundary(hh)) break;
00224     fh = mesh_.face_handle(hh);
00225     if (processed(fh) || used(fh)) break;
00226     _faces.push_back(fh);
00227     used(fh) = true;
00228     strip.push_back(mesh_.to_vertex_handle(hh).idx());
00229   }
00230 
00231 
00232   // walk along the strip: 2nd direction
00233   bool flip(false);
00234   hh = mesh_.prev_halfedge_handle(_start_hh);
00235   while (1)
00236   {
00237     // go right
00238     hh = mesh_.next_halfedge_handle(hh);
00239     hh = mesh_.opposite_halfedge_handle(hh);
00240     hh = mesh_.next_halfedge_handle(hh);
00241     if (mesh_.is_boundary(hh)) break;
00242     fh = mesh_.face_handle(hh);
00243     if (processed(fh) || used(fh)) break;
00244     _faces.push_back(fh);
00245     used(fh) = true;
00246     strip.push_front(mesh_.to_vertex_handle(hh).idx());
00247     flip = true;
00248 
00249     // go left
00250     hh = mesh_.opposite_halfedge_handle(hh);
00251     hh = mesh_.next_halfedge_handle(hh);
00252     if (mesh_.is_boundary(hh)) break;
00253     fh = mesh_.face_handle(hh);
00254     if (processed(fh) || used(fh)) break;
00255     _faces.push_back(fh);
00256     used(fh) = true;
00257     strip.push_front(mesh_.to_vertex_handle(hh).idx());
00258     flip = false;
00259   }
00260 
00261   if (flip) strip.push_front(strip.front());
00262 
00263 
00264 
00265   // copy final strip to _strip
00266   _strip.clear();
00267   _strip.reserve(strip.size());
00268   std::copy(strip.begin(), strip.end(), std::back_inserter(_strip));
00269 }
00270 
00271 
00272 //=============================================================================
00273 } // namespace OpenMesh
00274   //=============================================================================