opennurbs_mesh_tools.cpp
Go to the documentation of this file.
00001 /* $NoKeywords: $ */
00002 /*
00003 //
00004 // Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
00005 // OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
00006 // McNeel & Associates.
00007 //
00008 // THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
00009 // ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
00010 // MERCHANTABILITY ARE HEREBY DISCLAIMED.
00011 //                              
00012 // For complete openNURBS copyright information see <http://www.opennurbs.org>.
00013 //
00015 */
00016 
00017 #include "pcl/surface/3rdparty/opennurbs/opennurbs.h"
00018 
00019 
00021 // SwapMeshEdge()
00022 //
00023 
00024 bool ON_Mesh::SwapEdge_Helper( int topei, bool bTestOnly )
00025 {
00026   ON_Mesh& mesh = *this;
00027   const ON_MeshTopology& top = mesh.Topology();  
00028   const int F_count = mesh.m_F.Count();
00029   const int V_count = mesh.m_V.Count();
00030   const int topv_count = top.m_topv.Count();
00031   //const int tope_count = top.m_tope.Count();
00032 
00033   if ( topei < 0 || topei >= top.m_tope.Count() )
00034   {
00035     return false;
00036   }
00037 
00038   if ( top.m_topf.Count() != F_count )
00039     return false;
00040 
00041   const ON_MeshTopologyEdge& tope = top.m_tope[topei];
00042 
00043   if (    tope.m_topf_count != 2 
00044        || tope.m_topvi[0] == tope.m_topvi[1] 
00045        || tope.m_topvi[0] < 0
00046        || tope.m_topvi[1] < 0
00047        || tope.m_topvi[0] >= topv_count
00048        || tope.m_topvi[1] >= topv_count )
00049   {
00050     return false;
00051   }
00052 
00053   int fi0 = tope.m_topfi[0];
00054   int fi1 = tope.m_topfi[1];
00055   if ( fi0 < 0 || fi0 >= F_count || fi1 < 0 || fi1 >= F_count || fi0 == fi1 )
00056     return false;
00057 
00058   const ON_MeshFace& f0 = mesh.m_F[fi0];
00059   const ON_MeshFace& f1 = mesh.m_F[fi1];
00060   if ( !f0.IsValid(V_count) )
00061     return false;
00062   if ( !f1.IsValid(V_count) )
00063     return false;
00064   if ( !f0.IsTriangle() )
00065     return false;
00066   if ( !f1.IsTriangle() )
00067     return false;
00068 
00069   const ON_MeshTopologyFace& topf0 = top.m_topf[fi0];
00070   const ON_MeshTopologyFace& topf1 = top.m_topf[fi1];
00071 
00072   int fei0;
00073   for ( fei0 = 0; fei0 < 3; fei0++ )
00074   {
00075     if ( topf0.m_topei[fei0] == topei )
00076       break;
00077   }
00078   if ( fei0 >= 3 )
00079     return false;
00080 
00081   int f0_vi0 = f0.vi[(fei0+3)%4];
00082   int f0_vi1 = f0.vi[fei0];
00083   int f0_vi2 = f0.vi[(fei0+1)%3];
00084 
00085   int fei1;
00086   for ( fei1 = 0; fei1 < 3; fei1++ )
00087   {
00088     if ( topf1.m_topei[fei1] == topei )
00089       break;
00090   }
00091   if ( fei1 >= 3 )
00092     return false;
00093 
00094   int f1_vi0 = f1.vi[(fei1+3)%4];
00095   int f1_vi1 = f1.vi[fei1];
00096   int f1_vi2 = f1.vi[(fei1+1)%3];
00097 
00098   if ( topf0.m_reve[fei0] == topf1.m_reve[fei1] )
00099     return false;
00100   if ( f0_vi0 != f1_vi1 )
00101     return false;
00102   if ( f0_vi1 != f1_vi0 )
00103     return false;
00104 
00105   const ON_MeshTopologyVertex& topv0 = top.m_topv[tope.m_topvi[0]];
00106   const ON_MeshTopologyVertex& topv1 = top.m_topv[tope.m_topvi[1]];
00107   if ( topv0.m_v_count < 1 || topv1.m_v_count < 1 )
00108   {
00109     return false;
00110   }
00111   if ( topv0.m_vi[0] < 0 || topv0.m_vi[0] >= V_count )
00112   {
00113     return false;
00114   }
00115   if ( topv1.m_vi[0] < 0 || topv1.m_vi[0] >= V_count )
00116   {
00117     return false;
00118   }
00119 
00120   if ( bTestOnly )
00121     return true;
00122 
00123 
00124   ON_MeshFace newf0;
00125   ON_MeshFace newf1;
00126   newf0.vi[0] = f0_vi1;
00127   newf0.vi[1] = f0_vi2;
00128   newf0.vi[2] = f1_vi2;
00129   newf0.vi[3] = newf0.vi[2];
00130 
00131   newf1.vi[0] = f1_vi1;
00132   newf1.vi[1] = f1_vi2;
00133   newf1.vi[2] = f0_vi2;
00134   newf1.vi[3] = newf1.vi[2];
00135 
00136   mesh.m_F[fi0] = newf0;
00137   mesh.m_F[fi1] = newf1;
00138 
00139   mesh.DestroyTopology();
00140   mesh.DestroyPartition();
00141 
00142   return true;
00143 }
00144 
00145 bool ON_Mesh::IsSwappableEdge(int topei )
00146 {
00147   return const_cast<ON_Mesh*>(this)->SwapEdge_Helper( topei, true );
00148 }
00149 
00150 bool ON_Mesh::SwapEdge( int topei )
00151 {
00152   return SwapEdge_Helper( topei, false );
00153 }
00154 
00156 // CollapseMeshEdge()
00157 //
00158 
00159 // DO NOT PUT THIS CLASS IN A HEADER FILE
00160 class ON__MESHEDGE
00161 {
00162 public:
00163   // ON_Mesh m_V[] indices
00164   int vi0;
00165   int vi1; // always > vi0
00166   
00167   // ON_MeshTopology m_topvi[] indices
00168   int topvi0;
00169   int topvi1;
00170 
00171   // ON_Mesh m_V[] index of new vertex
00172   int newvi;
00173 
00174   // location of vertex that will replace the edge
00175   ON_3fPoint  newV;
00176   ON_3fVector newN;
00177   ON_2fPoint  newT;
00178 };
00179 
00180 // DO NOT PUT THIS CLASS IN A HEADER FILE
00181 class ON__NEWVI
00182 {
00183 public:
00184   // ON_Mesh m_V[] indices
00185   int oldvi;
00186   int newvi;
00187 };
00188 
00189 typedef int (*QSORTCMPFUNC)(const void*,const void*);
00190 
00191 static int CompareMESHEDGE( const ON__MESHEDGE* a, const ON__MESHEDGE* b )
00192 {
00193   // sort based on "vi0" and vi1" values (vi0 is always < vi1)
00194   int i = (a->vi0 - b->vi0);
00195   if ( 0 == i )
00196   {
00197     i = a->vi1 - b->vi1;
00198   }
00199   return i;
00200 }
00201 
00202 static int CompareNEWVI( const ON__NEWVI* a, const ON__NEWVI* b )
00203 {
00204   // sort based on "oldvi" value
00205   return a->oldvi - b->oldvi;
00206 }
00207 
00208 static int CompareInt( const void* a, const void* b )
00209 {
00210   return ( *((int*)a) - *((int*)b) );
00211 }
00212 
00213 bool ON_Mesh::CollapseEdge( int topei )
00214 {
00215   ON_Mesh& mesh = *this;
00216 
00217   ON__MESHEDGE me;
00218   memset(&me,0,sizeof(me));
00219   const ON_MeshTopology& top = mesh.Topology();  
00220   const int F_count = mesh.m_F.Count();
00221   const int V_count = mesh.m_V.Count();
00222   const int topv_count = top.m_topv.Count();
00223   //const int tope_count = top.m_tope.Count();
00224 
00225   if ( topei < 0 || topei >= top.m_tope.Count() )
00226   {
00227     return false;
00228   }
00229 
00230   const ON_MeshTopologyEdge& tope = top.m_tope[topei];
00231 
00232   if (    tope.m_topf_count < 1 
00233        || tope.m_topvi[0] == tope.m_topvi[1] 
00234        || tope.m_topvi[0] < 0
00235        || tope.m_topvi[1] < 0
00236        || tope.m_topvi[0] >= topv_count
00237        || tope.m_topvi[1] >= topv_count )
00238   {
00239     return false;
00240   }
00241 
00242   const ON_MeshTopologyVertex& topv0 = top.m_topv[tope.m_topvi[0]];
00243   const ON_MeshTopologyVertex& topv1 = top.m_topv[tope.m_topvi[1]];
00244   if ( topv0.m_v_count < 1 || topv1.m_v_count < 1 )
00245   {
00246     return false;
00247   }
00248   if ( topv0.m_vi[0] < 0 || topv0.m_vi[0] >= V_count )
00249   {
00250     return false;
00251   }
00252   if ( topv1.m_vi[0] < 0 || topv1.m_vi[0] >= V_count )
00253   {
00254     return false;
00255   }
00256   
00257   // create a ON__MESHEDGE for each face (usually one or two) that uses the edge
00258   ON__MESHEDGE* me_list = (ON__MESHEDGE*)alloca(tope.m_topf_count*sizeof(me_list[0]));
00259   int me_list_count = 0;
00260   int efi;
00261   for ( efi = 0; efi < tope.m_topf_count; efi++ )
00262   {
00263     int fi = tope.m_topfi[efi];
00264     if ( fi < 0 || fi >= F_count )
00265       continue;
00266     const ON_MeshFace& f = mesh.m_F[fi];
00267     if ( !f.IsValid(V_count) )
00268       continue;
00269     me.vi1 = f.vi[3];
00270     me.topvi1 = top.m_topv_map[me.vi1];
00271     int fvi;
00272     for ( fvi = 0; fvi < 4; fvi++ )
00273     {
00274       me.vi0 = me.vi1;
00275       me.topvi0 = me.topvi1;
00276       me.vi1 = f.vi[fvi];
00277       me.topvi1 = top.m_topv_map[me.vi1];
00278       if ( me.vi0 != me.vi1 )
00279       {
00280         if (    (me.topvi0 == tope.m_topvi[0] && me.topvi1 == tope.m_topvi[1])
00281              || (me.topvi0 == tope.m_topvi[1] && me.topvi1 == tope.m_topvi[0]) )
00282         {
00283           if ( me.vi0 > me.vi1 )
00284           {
00285             int i = me.vi0; me.vi0 = me.vi1; me.vi1 = i;
00286             i = me.topvi0; me.topvi0 = me.topvi1; me.topvi1 = i;
00287           }
00288           me_list[me_list_count++] = me;
00289           break;
00290         }
00291       }
00292     }
00293   }
00294 
00295   if (me_list_count<1)
00296   {
00297     return false;
00298   }
00299 
00300   // Sort me_list[] so edges using same vertices are adjacent
00301   // to each other in the list.  This is needed so that non-manifold
00302   // crease edges will be properly collapsed.
00303   ON_qsort(me_list,me_list_count,sizeof(me_list[0]),(QSORTCMPFUNC)CompareMESHEDGE);
00304 
00305   // create new vertex or vertices that edge will be
00306   // collapsed to.
00307   mesh.m_C.Destroy();
00308   mesh.m_K.Destroy();
00309   
00310   int mei;
00311   bool bHasVertexNormals = mesh.HasVertexNormals();
00312   bool bHasTextureCoordinates = mesh.HasTextureCoordinates();
00313   bool bHasFaceNormals = mesh.HasFaceNormals();
00314   if ( topv0.m_v_count == 1 || topv1.m_v_count == 1 )
00315   {
00316     // a single new vertex
00317     ON_Line Vline(ON_origin,ON_origin);
00318     ON_Line Tline(ON_origin,ON_origin);
00319     ON_3dVector N0(0,0,0);
00320     ON_3dVector N1(0,0,0);
00321     ON_3dPoint P;
00322     int vi, tvi, cnt;
00323 
00324     int newvi = topv0.m_vi[0];
00325 
00326     cnt = 0;
00327     for ( tvi = 0; tvi < topv0.m_v_count; tvi++ )
00328     {
00329       vi = topv0.m_vi[tvi];
00330       if ( vi < 0 || vi > V_count )
00331         continue;
00332       if ( vi < newvi )
00333         newvi = vi;
00334       cnt++;
00335       P = mesh.m_V[vi];
00336       Vline.from += P;
00337       if ( bHasVertexNormals )
00338       {
00339         N0 += ON_3dVector(mesh.m_N[vi]);
00340       }
00341       if ( bHasTextureCoordinates )
00342       {
00343         P = mesh.m_T[vi];
00344         Tline.from += P;
00345       }
00346     }
00347 
00348     if (cnt > 1)
00349     {
00350       double s = 1.0/((double)cnt);
00351       Vline.from.x *= s;
00352       Vline.from.y *= s;
00353       Vline.from.z *= s;
00354       Tline.from.x *= s;
00355       Tline.from.y *= s;
00356       Tline.from.z *= s;
00357       N0 = s*N0;
00358     }
00359 
00360     cnt = 0;
00361     for ( tvi = 0; tvi < topv1.m_v_count; tvi++ )
00362     {
00363       vi = topv1.m_vi[tvi];
00364       if ( vi < 0 || vi > V_count )
00365         continue;
00366       if ( vi < newvi )
00367         newvi = vi;
00368       cnt++;
00369       P = mesh.m_V[vi];
00370       Vline.to += P;
00371       if ( bHasVertexNormals )
00372       {
00373         N1 += ON_3dVector(mesh.m_N[vi]);
00374       }
00375       if ( bHasTextureCoordinates )
00376       {
00377         P = mesh.m_T[vi];
00378         Tline.to += P;
00379       }
00380     }
00381 
00382     if (cnt > 1)
00383     {
00384       double s = 1.0/((double)cnt);
00385       Vline.to.x *= s;
00386       Vline.to.y *= s;
00387       Vline.to.z *= s;
00388       Tline.to.x *= s;
00389       Tline.to.y *= s;
00390       Tline.to.z *= s;
00391       N1 = s*N1;
00392     }
00393 
00394     ON_3fPoint newV(Vline.PointAt(0.5));
00395     ON_3fVector newN;
00396     ON_2fPoint newT;
00397     if ( bHasVertexNormals )
00398     {
00399       N0.Unitize();
00400       N1.Unitize();
00401       ON_3dVector N = N0+N1;
00402       if ( !N.Unitize() )
00403       {
00404         N = (topv0.m_v_count == 1) ? mesh.m_N[topv0.m_vi[0]] :mesh.m_N[topv1.m_vi[0]];
00405       }
00406       newN = N;
00407     }
00408     if ( bHasTextureCoordinates )
00409     {
00410       newT = Tline.PointAt(0.5);
00411     }
00412     for ( mei = 0; mei < me_list_count; mei++ )
00413     {
00414       me_list[mei].newvi = newvi;
00415       me_list[mei].newV = newV;
00416       me_list[mei].newN = newN;
00417       me_list[mei].newT = newT;
00418     }
00419   }
00420   else
00421   {
00422     // collapsing a "crease" edge - attempt to preserve
00423     // the crease.
00424     memset(&me,0,sizeof(me));
00425     me.vi0 = -1;
00426     me.vi1 = -1;
00427     for ( mei = 0; mei < me_list_count; mei++ )
00428     {
00429       if ( 0 == mei && CompareMESHEDGE(&me,me_list+mei) )
00430       {
00431         // cook up new vertex
00432         me_list[mei].newvi = mesh.m_V.Count();
00433         me = me_list[mei];
00434         ON_Line line;
00435         line.from = mesh.m_V[me.vi0];
00436         line.to   = mesh.m_V[me.vi1];
00437         me.newV = line.PointAt(0.5);
00438         if ( bHasVertexNormals )
00439         {
00440           ON_3dVector N0(mesh.m_N[me.vi0]);
00441           ON_3dVector N1(mesh.m_N[me.vi1]);
00442           ON_3dVector N = N0 + N1;
00443           if ( !N.Unitize() )
00444             N = N0;
00445           me.newN = N;
00446         }
00447         if ( bHasTextureCoordinates )
00448         {
00449           line.from = mesh.m_T[me.vi0];
00450           line.to   = mesh.m_T[me.vi1];
00451           me.newT = line.PointAt(0.5);
00452         }
00453         me.newvi = (me.vi0 < me.vi1) ? me.vi0 : me.vi1;
00454       }
00455       else
00456       {
00457         me_list[mei].newvi = me.newvi;
00458         me_list[mei].newV = me.newV;
00459         me_list[mei].newN = me.newN;
00460         me_list[mei].newT = me.newT;
00461       }
00462     }
00463   }
00464 
00465   // We are done averaging old mesh values.
00466   // Change values in mesh m_V[], m_N[] and m_T[] arrays.
00467   for ( mei = 0; mei < me_list_count; mei++ )
00468   {
00469     mesh.m_V[me_list[mei].vi0] = me_list[mei].newV;
00470     mesh.m_V[me_list[mei].vi1] = me_list[mei].newV;
00471     if ( bHasVertexNormals )
00472     {
00473       mesh.m_N[me_list[mei].vi0] = me_list[mei].newN;
00474       mesh.m_N[me_list[mei].vi1] = me_list[mei].newN;
00475     }
00476     if ( bHasTextureCoordinates )
00477     {
00478       mesh.m_T[me_list[mei].vi0] = me_list[mei].newT;
00479       mesh.m_T[me_list[mei].vi1] = me_list[mei].newT;
00480     }
00481   }
00482 
00483   // make a map of old to new
00484   int old2new_map_count = 0;
00485   ON__NEWVI* old2new_map = (ON__NEWVI*)alloca(2*me_list_count*sizeof(old2new_map[0]));
00486 
00487   for ( mei = 0; mei < me_list_count; mei++ )
00488   {
00489     old2new_map[old2new_map_count].oldvi = me_list[mei].vi0;
00490     old2new_map[old2new_map_count].newvi = me_list[mei].newvi;
00491     old2new_map_count++;
00492     old2new_map[old2new_map_count].oldvi = me_list[mei].vi1;
00493     old2new_map[old2new_map_count].newvi = me_list[mei].newvi;
00494     old2new_map_count++;
00495   }
00496 
00497   // sort old2new_map[] so we can use a fast bsearch() call
00498   // to update faces.
00499   ON_qsort(old2new_map,old2new_map_count,sizeof(old2new_map[0]),(QSORTCMPFUNC)CompareNEWVI);
00500 
00501   // count faces that use the vertices that are being changed
00502   int bad_fi_count = 0;
00503   int topv_end, vei, fi, fvi23, fvi;
00504   ON__NEWVI nvi;
00505 
00506   for ( topv_end = 0; topv_end < 2; topv_end++ )
00507   {
00508     const ON_MeshTopologyVertex& topv = (topv_end) ? topv1 : topv0;
00509     for ( vei = 0; vei < topv.m_tope_count; vei++ )
00510     {
00511       topei = topv.m_topei[vei];
00512       if ( topei < 0 && topei >= top.m_tope.Count() )
00513         continue;
00514       bad_fi_count += top.m_tope[topei].m_topf_count;
00515     }
00516   }
00517   int* bad_fi = (int*)alloca(bad_fi_count*sizeof(*bad_fi));
00518   bad_fi_count = 0;
00519 
00520   // Go through all the faces that use the vertices at the
00521   // ends of the edge and update the vi[] values to use the
00522   // new vertices.
00523   for ( topv_end = 0; topv_end < 2; topv_end++ )
00524   {
00525     const ON_MeshTopologyVertex& topv = (topv_end) ? topv1 : topv0;
00526     for ( vei = 0; vei < topv.m_tope_count; vei++ )
00527     {
00528       topei = topv.m_topei[vei];
00529       if ( topei < 0 && topei >= top.m_tope.Count() )
00530         continue;
00531       const ON_MeshTopologyEdge& e = top.m_tope[topei];
00532       for ( efi = 0; efi < e.m_topf_count; efi++ )
00533       {
00534         fi = e.m_topfi[efi];
00535         if ( fi < 0 || fi >= F_count )
00536           continue;
00537         bool bChangedFace = false;
00538         ON_MeshFace& f = mesh.m_F[fi];
00539         for ( fvi = 0; fvi < 4; fvi++ )
00540         {
00541           nvi.oldvi = f.vi[fvi];
00542           ON__NEWVI* p = (ON__NEWVI*)bsearch(&nvi,old2new_map,old2new_map_count,sizeof(old2new_map[0]),(QSORTCMPFUNC)CompareNEWVI);
00543           if ( 0 != p && p->oldvi != p->newvi)
00544           {
00545             f.vi[fvi] = p->newvi;
00546             bChangedFace = true;
00547           }
00548         }
00549         if ( bChangedFace )
00550         {
00551           if ( !f.IsValid(V_count) )
00552           {
00553             if ( f.vi[3] == f.vi[0] )
00554             {
00555               f.vi[0] = f.vi[1];
00556               f.vi[1] = f.vi[2];
00557               f.vi[2] = f.vi[3];
00558             }
00559             else if ( f.vi[0] == f.vi[1] )
00560             {
00561               fvi23 = f.vi[0];
00562               f.vi[0] = f.vi[2];
00563               f.vi[1] = f.vi[3];
00564               f.vi[2] = fvi23;
00565               f.vi[3] = fvi23;
00566             }
00567             else if ( f.vi[1] == f.vi[2] )
00568             {
00569               fvi23 = f.vi[1];
00570               f.vi[1] = f.vi[0];
00571               f.vi[0] = f.vi[3];
00572               f.vi[2] = fvi23;
00573               f.vi[3] = fvi23;
00574             }
00575             if ( f.vi[0] == f.vi[1] || f.vi[1] == f.vi[2] || f.vi[2] == f.vi[0] || f.vi[2] != f.vi[3] )
00576             {
00577               bad_fi[bad_fi_count++] = fi;
00578             }
00579           }
00580           if ( bHasFaceNormals )
00581           {
00582             // invalid faces are removed below
00583             ON_3fVector a, b, n;
00584             a = mesh.m_V[f.vi[2]] - mesh.m_V[f.vi[0]];
00585             b = mesh.m_V[f.vi[3]] - mesh.m_V[f.vi[1]];
00586             n = ON_CrossProduct( a, b );
00587             n.Unitize();
00588             mesh.m_FN[fi] = n;
00589           }
00590         }
00591       }
00592     }
00593   }
00594 
00595   if ( bad_fi_count > 0 )
00596   {
00597     // remove collapsed faces
00598     ON_qsort(bad_fi,bad_fi_count,sizeof(bad_fi[0]),CompareInt);
00599     int bfi = 1;
00600     int dest_fi = bad_fi[0];
00601     for ( fi = dest_fi+1; fi < F_count && bfi < bad_fi_count; fi++ )
00602     {
00603       if ( fi == bad_fi[bfi] )
00604       {
00605         bfi++;
00606       }
00607       else
00608       {
00609         mesh.m_F[dest_fi++] = mesh.m_F[fi];
00610       }
00611     }
00612     while (fi<F_count)
00613     {
00614       mesh.m_F[dest_fi++] = mesh.m_F[fi++];
00615     }
00616     mesh.m_F.SetCount(dest_fi);
00617 
00618     if ( bHasFaceNormals )
00619     {
00620       bfi = 1;
00621       dest_fi = bad_fi[0];
00622       for ( fi = dest_fi+1; fi < F_count && bfi < bad_fi_count; fi++ )
00623       {
00624         if ( fi == bad_fi[bfi] )
00625         {
00626           bfi++;
00627         }
00628         else
00629         {
00630           mesh.m_FN[dest_fi++] = mesh.m_FN[fi];
00631         }
00632       }
00633       while (fi<F_count)
00634       {
00635         mesh.m_FN[dest_fi++] = mesh.m_FN[fi++];
00636       }
00637       mesh.m_FN.SetCount(dest_fi);
00638     }
00639   }
00640 
00641   mesh.Compact();
00642   mesh.DestroyTopology();
00643   mesh.DestroyPartition();
00644 
00645   return true;
00646 }
00647 
00648 
00649 //static int NewIndex( int old_index, int missing_index_count, const int* missing_index_list )
00650 //{
00651 //  // tool to calculate new indices when some elements are deleted from a list
00652 //  int delta;
00653 //  for ( delta = 0; delta < missing_index_count; delta++ )
00654 //  {
00655 //    if ( old_index < missing_index_list[delta] )
00656 //      break;
00657 //  }
00658 //  return old_index - delta;
00659 //}
00660 
00661 bool ON_Mesh::DeleteFace( int meshfi )
00662 {
00663   // Do NOT add a call Compact() in this function.
00664   // Compact() is slow and this function may be called
00665   // many times in sequence.  
00666   // It is the callers responsibility to call Compact()
00667   // when it is needed.
00668   bool rc = false;
00669 
00670   if ( meshfi >= 0 && meshfi < m_F.Count() )
00671   {
00672     if ( m_top.m_topf.Count() > 0 )
00673     {
00674       DestroyTopology();
00675     }
00676     DestroyPartition();
00677     DestroyTree();
00678     if ( m_FN.Count() == m_F.Count() )
00679     {
00680       m_FN.Remove(meshfi);
00681     }
00682     m_F.Remove(meshfi);
00683 
00684     // 6 Mar 2010 S. Baer
00685     // Invalidate the cached IsClosed flag. This forces the mesh to
00686     // recompute IsClosed the next time it is called
00687     SetClosed(-1);
00688 
00689     rc = true;
00690   }
00691   return rc;
00692 }
00693 
00694 ON_Mesh* ON_ControlPolygonMesh( 
00695           const ON_NurbsSurface& nurbs_surface, 
00696           bool bCleanMesh,
00697           ON_Mesh* input_mesh
00698           )
00699 {
00700   int u0 = 0;
00701   int u1 = nurbs_surface.CVCount(0);
00702 
00703   int v0 = 0;
00704   int v1 = nurbs_surface.CVCount(1);
00705 
00706   if ( 0 == nurbs_surface.m_cv || !nurbs_surface.IsValid() )
00707   {
00708     ON_ERROR("ON_ControlPolygonMesh - surface is not valid");
00709     return NULL;
00710   }
00711 
00712   ON_SimpleArray<double> gu(u1);
00713   ON_SimpleArray<double> gv(v1);
00714   gu.SetCount(u1);
00715   gv.SetCount(v1);
00716   nurbs_surface.GetGrevilleAbcissae(0,gu.Array());
00717   nurbs_surface.GetGrevilleAbcissae(1,gv.Array());
00718 
00719   ON_Interval d0 = nurbs_surface.Domain(0);
00720   ON_Interval d1 = nurbs_surface.Domain(1);
00721 
00722   bool bPeriodic0 = nurbs_surface.IsPeriodic(0)?true:false;
00723   bool bIsClosed0 = bPeriodic0 ? true : (nurbs_surface.IsClosed(0)?true:false);
00724   bool bPeriodic1 = nurbs_surface.IsPeriodic(1)?true:false;
00725   bool bIsClosed1 = bPeriodic1 ? true : (nurbs_surface.IsClosed(1)?true:false);
00726 
00727   if ( bPeriodic0 )
00728   {
00729     u1 -= (nurbs_surface.Degree(0) - 1);
00730     while ( u1 < nurbs_surface.CVCount(0) && gu[u0] < d0[0] && gu[u1-1] <= d0[1] )
00731     {
00732       u0++;
00733       u1++;
00734     }
00735     d0.Set(gu[u0],gu[u1-1]);
00736   }
00737 
00738   if ( bPeriodic1 )
00739   {
00740     v1 -= (nurbs_surface.Degree(1) - 1);
00741     while ( v1 < nurbs_surface.CVCount(1) && gv[v0] < d1[0] && gv[v1-1] <= d1[1] )
00742     {
00743       v0++;
00744       v1++;
00745     }
00746     d1.Set(gv[v0],gv[v1-1]);
00747   }
00748 
00749   ON_Mesh* mesh = (0 == input_mesh) ? new ON_Mesh() : input_mesh;
00750 
00751   int vertex_count = (u1-u0)*(v1-v0);
00752   int face_count = (u1-u0-1)*(v1-v0-1);
00753 
00754   mesh->m_V.Reserve(vertex_count);
00755   mesh->m_N.Reserve(vertex_count);
00756   mesh->m_T.Reserve(vertex_count);
00757   mesh->m_F.Reserve(face_count);
00758 
00759   ON_3dPoint V;
00760   ON_3dVector N;
00761   ON_2dPoint T;
00762 
00763   int hint[2] = {0,0};
00764   int i, j;
00765   int k = -1;
00766   for ( j = v0; j < v1; j++)
00767   {
00768     T.y = d1.NormalizedParameterAt(gv[j]);
00769     for ( i = u0; i < u1; i++)
00770     {
00771       nurbs_surface.GetCV( i, j, V);
00772       T.x = d0.NormalizedParameterAt(gu[i]);
00773       nurbs_surface.EvNormal(gu[i],gv[j],N,0,hint);
00774       mesh->m_V.AppendNew() = V;
00775       mesh->m_N.AppendNew() = N;
00776       mesh->m_T.AppendNew() = T;
00777       if ( i > u0 && j > v0 )
00778       {
00779         ON_MeshFace& f = mesh->m_F.AppendNew();
00780         f.vi[0] = k++;
00781         f.vi[1] = k;
00782         f.vi[2] = mesh->m_V.Count()-1;
00783         f.vi[3] = f.vi[2]-1;
00784       }
00785     }
00786     k++;
00787   }
00788   
00789   u1 -= u0;
00790   v1 -= v0;
00791 
00792   // make sure closed seams are spot on
00793   if ( bIsClosed0 )
00794   {
00795     i = 0;
00796     for ( j = 0; j < v1; j++ )
00797     {
00798       k = i + (u1-1);
00799       mesh->m_V[k] = mesh->m_V[i];
00800       if ( bPeriodic0 )
00801       {
00802         mesh->m_N[k] = mesh->m_N[i];
00803       }
00804       i = k+1;
00805       // do NOT synch texture coordinates
00806     }
00807   }
00808 
00809   if ( bIsClosed1 )
00810   {
00811     for ( i = 0, k = u1*(v1-1); i < u1; i++, k++ )
00812     {
00813       mesh->m_V[k] = mesh->m_V[i];
00814       if ( bPeriodic1 )
00815       {
00816         mesh->m_N[k] = mesh->m_N[i];
00817       }
00818       // do NOT synch texture coordinates
00819     }
00820   }
00821 
00822   // make sure singular ends are spot on
00823   i=0;
00824   for ( k = 0; k < 4; k++ )
00825   {
00826     if ( nurbs_surface.IsSingular(k) )
00827     {
00828       switch(k)
00829       {
00830       case 0: // 0 = south
00831         i = 0;
00832         j = 1;
00833         k = u1;
00834         break;
00835 
00836       case 1: // 1 = east
00837         i = u1-1;
00838         j = u1;
00839         k = u1*v1;
00840         break;
00841 
00842       case 2: // 2 = north
00843         i = u1*(v1-1);
00844         j = 1;
00845         k = u1*v1;
00846         break;
00847 
00848       case 3: // 3 = west
00849         i = 0;
00850         j = u1;
00851         k = u1*(v1-1)+1;
00852         break;
00853       }
00854       V = mesh->m_V[i];
00855       for ( i = i+j; i < k; i += j )
00856       {
00857         mesh->m_V[i] = V;
00858       }
00859     }
00860   }
00861 
00862   if ( bCleanMesh )
00863   {
00864     // Clean up triangles etc.
00865     ON_3dPoint P[4];
00866     ON_SimpleArray<int> badfi(32);
00867     for ( i = 0; i < mesh->m_F.Count(); i++ )
00868     {
00869       ON_MeshFace& f = mesh->m_F[i];
00870       P[0] = mesh->m_V[f.vi[0]];
00871       P[1] = mesh->m_V[f.vi[1]];
00872       P[2] = mesh->m_V[f.vi[2]];
00873       P[3] = mesh->m_V[f.vi[3]];
00874       if ( P[0] == P[1] )
00875       {
00876         f.vi[1] = f.vi[2];
00877         f.vi[2] = f.vi[3];
00878         P[1] = P[2];
00879         P[2] = P[3];
00880       }
00881       if ( P[1] == P[2] )
00882       {
00883         f.vi[2] = f.vi[3];
00884         P[2] = P[3];
00885       }
00886       if ( P[2] == P[3] )
00887       {
00888         f.vi[2] = f.vi[3];
00889         P[2] = P[3];
00890       }
00891       if ( P[3] == P[0] )
00892       {
00893         f.vi[0] = f.vi[1];
00894         f.vi[1] = f.vi[2];
00895         f.vi[2] = f.vi[3];
00896         P[0] = P[1];
00897         P[1] = P[2];
00898         P[2] = P[3];
00899       }
00900       if (    f.vi[0] == f.vi[1] 
00901            || f.vi[1] == f.vi[2] 
00902            || f.vi[3] == f.vi[0] 
00903            || P[0] == P[2] || P[1] == P[3] )
00904       {
00905         badfi.Append(i);
00906       }
00907     }
00908     
00909     if ( badfi.Count() > 0 )
00910     {
00911       if ( badfi.Count() == mesh->m_F.Count() )
00912       {
00913         if ( input_mesh )
00914         {
00915           mesh->Destroy();
00916         }
00917         else
00918         {
00919           delete mesh;
00920         }
00921         mesh = 0;
00922       }
00923       else
00924       {
00925         // remove bad faces
00926         i = badfi[0];
00927         j = i+1;
00928         k = 1;
00929         for ( j = i+1; j < mesh->m_F.Count(); j++ )
00930         {
00931           if ( k < badfi.Count() && j == badfi[k] )
00932           {
00933             k++;
00934           }
00935           else
00936           {
00937             mesh->m_F[i++] = mesh->m_F[j];
00938           }
00939         }
00940         mesh->m_F.SetCount(i);
00941       }
00942 
00943       // 29 May 2008: Mikko, TRR 34687:
00944       // Added crash protection. At this point mesh is NULL if it contained all bad faces.
00945       if ( mesh)
00946         mesh->CullUnusedVertices();
00947     }
00948   }
00949 
00950   return mesh;
00951 }
00952 
00954 //
00955 // mesh components
00956 static bool IsUnweldedEdge(int edgeidx, const ON_MeshTopology& Top)
00957 {
00958 
00959   const ON_MeshTopologyEdge& edge = Top.m_tope[edgeidx];
00960   if (1 == edge.m_topf_count)
00961     return true;
00962 
00963   if (1 == Top.m_topv[edge.m_topvi[0]].m_v_count || 1 == Top.m_topv[edge.m_topvi[1]].m_v_count)
00964   {
00965     //Both ends of the edge have to have more than one mesh vertex or they are for sure welded.
00966     //However having more than 1 vertex at both ends does not necessarily mean it is unwelded.
00967     return false; 
00968   }
00969 
00970   ON_3fPoint ptA = Top.m_mesh->m_V[Top.m_topv[edge.m_topvi[0]].m_vi[0]];
00971   ON_3fPoint ptB = Top.m_mesh->m_V[Top.m_topv[edge.m_topvi[1]].m_vi[0]];
00972   ON_SimpleArray<int> ptAindexes(Top.m_topv[edge.m_topvi[0]].m_v_count);
00973   ON_SimpleArray<int> ptBindexes(Top.m_topv[edge.m_topvi[1]].m_v_count);
00974 
00975   int i, ict = edge.m_topf_count;
00976   int j, jct;
00977   int k, kct;
00978   for (i=0; ict>i; i++)
00979   {
00980     const ON_MeshFace& face = Top.m_mesh->m_F[edge.m_topfi[i]];
00981     jct = face.IsQuad()?4:3;
00982     for (j=0; jct>j; j++)
00983     {
00984       if (ptA == Top.m_mesh->m_V[face.vi[j]])
00985       {
00986         if (0 == ptAindexes.Count())
00987         {
00988           ptAindexes.Append(face.vi[j]);
00989           continue;
00990         }
00991         else
00992         {
00993           kct = ptAindexes.Count();
00994           for (k=0; kct>k; k++)
00995           {
00996             if (ptAindexes[k] == face.vi[j])
00997               return false;
00998           }
00999           ptAindexes.Append(face.vi[j]);
01000         }
01001       }
01002       else if (ptB == Top.m_mesh->m_V[face.vi[j]])
01003       {
01004         if (0 == ptBindexes.Count())
01005         {
01006           ptBindexes.Append(face.vi[j]);
01007           continue;
01008         }
01009         else
01010         {
01011           kct = ptBindexes.Count();
01012           for (k=0; kct>k; k++)
01013           {
01014             if (ptBindexes[k] == face.vi[j])
01015               return false;
01016           }
01017           ptBindexes.Append(face.vi[j]);
01018         }
01019       }
01020     }
01021   }
01022 
01023   return true;
01024 }
01025 
01026 static void FindAdjacentFaces(const ON_MeshTopology& Top, 
01027                               ON_SimpleArray<int>& FacesToCheck, 
01028                               const ON_SimpleArray<int>& SortedFaceArray,
01029                               ON_SimpleArray<int>& DupFaceArray,
01030                               bool bUseVertexConnections, 
01031                               bool bTopologicalConnections)
01032 {
01033   int fi, vi, ei, facecount = FacesToCheck.Count(), totalcount = SortedFaceArray.Count();
01034   DupFaceArray.Zero();
01035   ON_SimpleArray<int> OldFacesToCheck = FacesToCheck;
01036 
01037   FacesToCheck.Empty();
01038 
01039   for (fi=0;fi<facecount;fi++)
01040   {
01041     if (totalcount > OldFacesToCheck[fi])
01042     {
01043       if (0 == SortedFaceArray[OldFacesToCheck[fi]])
01044       {
01045         FacesToCheck.Append(OldFacesToCheck[fi]);
01046         DupFaceArray[OldFacesToCheck[fi]] = 1;
01047       }
01048 
01049       if (false == bUseVertexConnections)
01050       {
01051         int j;
01052         const ON_MeshTopologyFace& face = Top.m_topf[OldFacesToCheck[fi]];
01053         for(ei=0;ei<(face.IsQuad()?4:3);ei++)
01054         {
01055           const ON_MeshTopologyEdge& edge = Top.m_tope[face.m_topei[ei]];
01056 
01057           if (1 == edge.m_topf_count || (false == bTopologicalConnections && true == IsUnweldedEdge(face.m_topei[ei], Top)))
01058             continue;
01059 
01060           for(j=0;j<edge.m_topf_count;j++)
01061           {  
01062             if (0 == SortedFaceArray[edge.m_topfi[j]] && 1 != DupFaceArray[edge.m_topfi[j]])
01063             {
01064               FacesToCheck.Append(edge.m_topfi[j]);
01065               DupFaceArray[edge.m_topfi[j]] = 1;
01066             }
01067           }
01068         }
01069       }
01070       else
01071       {
01072         int j, k, m;
01073         ON_3fPoint Pt;
01074         const ON_MeshFace& face = Top.m_mesh->m_F[OldFacesToCheck[fi]];
01075         for(vi=0;vi<(face.IsQuad()?4:3);vi++)
01076         {
01077           const ON_MeshTopologyVertex& vertex = Top.m_topv[Top.m_topv_map[face.vi[vi]]];
01078           for (j=0; vertex.m_tope_count>j; j++)
01079           {
01080             const ON_MeshTopologyEdge& edge = Top.m_tope[vertex.m_topei[j]];
01081             for (k=0; edge.m_topf_count>k; k++)
01082             {
01083               if (true == bTopologicalConnections)
01084               {
01085                 if (0 == SortedFaceArray[edge.m_topfi[k]] && 1 != DupFaceArray[edge.m_topfi[k]])
01086                 {
01087                   FacesToCheck.Append(edge.m_topfi[k]);
01088                   DupFaceArray[edge.m_topfi[k]] = 1;
01089                 }
01090               }
01091               else
01092               {
01093                 Pt = Top.m_mesh->m_V[vertex.m_vi[0]];
01094                 const ON_MeshFace& thisface = Top.m_mesh->m_F[edge.m_topfi[k]];
01095                 for (m=0; m<(thisface.IsQuad()?4:3);m++)
01096                 {
01097                   if (Pt != Top.m_mesh->m_V[thisface.vi[m]])
01098                     continue;
01099 
01100                   if (face.vi[vi] == thisface.vi[m] && 0 == SortedFaceArray[edge.m_topfi[k]] && 1 != DupFaceArray[edge.m_topfi[k]])
01101                   {
01102                     //Faces share vertex 
01103                     FacesToCheck.Append(edge.m_topfi[k]);
01104                     DupFaceArray[edge.m_topfi[k]] = 1;
01105                     break;
01106                   }
01107                 }
01108               }
01109             }
01110           }
01111         }
01112       }
01113     }
01114   }
01115 }
01116 
01117 
01118 int ON_Mesh::GetConnectedComponents( bool bUseVertexConnections, 
01119                                      bool bTopologicalConnections, 
01120                                      ON_SimpleArray<int>& facet_component_labels
01121                                    ) const
01122 {
01123   int i, facecount = m_F.Count(), meshidx = 0;
01124 
01125   //This array will act as an associative array to m_F since ON_MeshFace do not have something
01126   //like m_trim_user_i on a ON_BrepTrim.  It will have the indice of the final mesh the face 
01127   //belongs to.
01128   if (facecount != facet_component_labels.Count())
01129   {
01130     facet_component_labels.Reserve(facecount);
01131     facet_component_labels.SetCount(facecount);
01132   }
01133 
01134   //initialize to 0
01135   facet_component_labels.MemSet(0);
01136 
01137   ON_SimpleArray<int> DupFaceArray(facecount);
01138   DupFaceArray.SetCount(facecount);
01139 
01140   const ON_MeshTopology& Top = Topology();
01141   if (!Top.IsValid())
01142     return 0;
01143 
01144   ON_SimpleArray<int> FacesToCheck;
01145   FacesToCheck.Reserve(64);
01146   i = 0;
01147   while (i < facecount)
01148   {
01149     meshidx++;
01150 
01151     FacesToCheck.Append(i);
01152 
01153     while(0 != FacesToCheck.Count())
01154     {
01155       //Figure out which faces are connected to each other
01156       FindAdjacentFaces(Top, FacesToCheck, facet_component_labels, DupFaceArray, bUseVertexConnections, bTopologicalConnections);
01157       int j;
01158       for (j=0;j<FacesToCheck.Count();j++)
01159         facet_component_labels[FacesToCheck[j]] = meshidx;
01160     }
01161 
01162     for(;i<facecount;i++)
01163     {
01164       if (0 == facet_component_labels[i])
01165         break;
01166     }
01167   }
01168   
01169   return meshidx;
01170 }
01171 
01172 int ON_Mesh::GetConnectedComponents( bool bUseVertexConnections, 
01173                                      bool bTopologicalConnections, 
01174                                      ON_SimpleArray<ON_Mesh*>* components
01175                                    ) const
01176 { 
01177   int i, j, k, kct, facecount = m_F.Count();
01178   ON_SimpleArray<int> SortedFaceArray(facecount);
01179   SortedFaceArray.SetCount(facecount);
01180 
01181   int compct = GetConnectedComponents(bUseVertexConnections, bTopologicalConnections, SortedFaceArray);
01182   if (0 == compct || 0 == components)
01183     return compct;
01184 
01185   bool bHasFaceNormals = HasFaceNormals();
01186   bool bHasPrincipalCurvatures = HasPrincipalCurvatures();
01187   bool bHasSurfaceParameters = HasSurfaceParameters();
01188   bool bHasTextureCoordinates = HasTextureCoordinates();
01189   bool bHasVertexColors = HasVertexColors();
01190   bool bHasVertexNormals = HasVertexNormals();
01191 
01192   ON_MeshFace newface;
01193   newface.vi[0] = -1; newface.vi[1] = -1; newface.vi[2] = -1; newface.vi[3] = -1; 
01194 
01195   ON_SimpleArray<int> vertidxarray(m_V.Count());
01196   vertidxarray.SetCount(m_V.Count());
01197 
01198   const ON_3dPoint* pMesh_D = 0;
01199   if ( HasDoublePrecisionVertices() )
01200   {
01201     if ( m_V.Count() > 0 && HasSynchronizedDoubleAndSinglePrecisionVertices() )
01202     {
01203       pMesh_D = DoublePrecisionVertices().Array();
01204     }
01205   }
01206 
01207   ON_3dPointArray bogus_D;
01208 
01209   for (i=1;compct>=i;i++)
01210   {
01211     kct = vertidxarray.Count();
01212     for (k=0; kct>k; k++)
01213       vertidxarray[k] = -1;
01214 
01215     ON_Mesh* pNewMesh = new ON_Mesh();
01216     if (0 == pNewMesh)
01217       continue;
01218 
01219     ON_3dPointArray& pNewMesh_D = ( 0 != pMesh_D )
01220                        ? pNewMesh->DoublePrecisionVertices()
01221                        : bogus_D;
01222 
01223           for (j=0;j<facecount;j++)
01224     {
01225       if ( i == SortedFaceArray[j] )
01226       {
01227         const ON_MeshFace& face = m_F[j];
01228         kct = face.IsTriangle()?3:4; 
01229         for (k=0; k<kct; k++)
01230         {
01231           if (-1 != vertidxarray[face.vi[k]])
01232           {
01233             newface.vi[k] = vertidxarray[face.vi[k]];
01234             continue;
01235           }
01236 
01237           int newvi;
01238           if ( 0 != pMesh_D )
01239           {
01240             newvi = pNewMesh_D.Count();
01241             pNewMesh_D.Append(pMesh_D[face.vi[k]]);
01242           }
01243           else
01244           {
01245             newvi = pNewMesh->m_V.Count();
01246             pNewMesh->m_V.Append(m_V[face.vi[k]]);
01247           }
01248 
01249           newface.vi[k] = vertidxarray[face.vi[k]] = newvi;
01250 
01251           if (true == bHasPrincipalCurvatures)
01252             pNewMesh->m_K.Append(m_K[face.vi[k]]);
01253 
01254           if (true == bHasSurfaceParameters)
01255             pNewMesh->m_S.Append(m_S[face.vi[k]]);
01256 
01257           if (true == bHasTextureCoordinates)
01258             pNewMesh->m_T.Append(m_T[face.vi[k]]);
01259 
01260           if (true == bHasVertexColors)
01261             pNewMesh->m_C.Append(m_C[face.vi[k]]);
01262 
01263           if (true == bHasVertexNormals)
01264             pNewMesh->m_N.Append(m_N[face.vi[k]]);
01265         }
01266 
01267         if (3 == kct)
01268           newface.vi[3] = newface.vi[2];
01269 
01270         pNewMesh->m_F.Append(newface);
01271         if (true == bHasFaceNormals)
01272           pNewMesh->m_FN.Append(m_FN[j]);
01273       }
01274     }
01275 
01276     if ( 0 != pMesh_D )
01277       pNewMesh->UpdateSinglePrecisionVertices();
01278 
01279     pNewMesh->Compact();
01280 
01281     if (0 < pNewMesh->m_F.Count())
01282       components->Append(pNewMesh);
01283     else
01284     {
01285       delete pNewMesh;
01286       pNewMesh = 0;
01287     }
01288   }
01289 
01290   return compct;
01291 }


pcl
Author(s): Open Perception
autogenerated on Wed Aug 26 2015 15:27:02