Changeset 3299

Timestamp:

11/06/09 16:29:04 (2 weeks ago)

Author:

kraftche

Message:

o Fix very broken vector-vector get_connectivity:

assumed that all entities in array had the same type as the first entity.

o Change vector-range get_connectivity such that it is worst-case

O(n ln n) instead of O(n²⁾

o Rewrite vector-vector get_adjacencies with specialized code instead

of call to range-range get_adjacencies

o Templatize implementation of range-range get_adjacencies such that

it can be shared by range-range get_adjacencies and vetor-range
get_adjacencies w/out converting the input list.

o Fix bug in some forms of get_adjancies when input list contains

only one entity and target type is vertex: still need to handle
INTERSECT/UNION flag if 'output' container is not empty.

o Fix inconsistent behavior for different versions and special

cases of get_adjacencies: all should return input entities if
asked for adjacent entities of the same dimension (not returning
such entities would be more consistent with iMesh, but that broke
other code in MOAB.)

Time required to skin a mesh using vertex->element adjacencies
was reduced from 9.32 seconds to 7.88 seconds with these changes.

Passes all tests.

Files:

• MOAB/trunk/MBCore.cpp (modified) (7 diffs)

MOAB/trunk/MBCore.cpp

@@ -947 +947 @@
   if (MB_SUCCESS != result) return result;
   
-  std::copy(tmp_connect.begin(), tmp_connect.end(), mb_range_inserter(connectivity));
+  std::sort( tmp_connect.begin(), tmp_connect.end() );
+  std::copy(tmp_connect.rbegin(), tmp_connect.rend(), mb_range_inserter(connectivity));
   return result;
 }
@@ -957 +958 @@
                                       bool topological_connectivity) const
 {
-  if (num_handles == 0) return MB_FAILURE;
-  
-    // Make sure the entity should have a connectivity.
-  MBEntityType type = TYPE_FROM_HANDLE(entity_handles[0]);
-
-  int i;
-  connectivity.clear();
-
-  // handle the special case where someone asks for the connectivity
-  // of a vertex.  This actually kind of makes sense for a sphere element.
-  if (type == MBVERTEX)
-  {
-    connectivity.reserve(num_handles);
-    std::copy(entity_handles, entity_handles+num_handles, 
-              std::back_inserter(connectivity));
-    return MB_SUCCESS;
-  }
-
-    // WARNING: This is very dependent on the ordering of the MBEntityType enum
-  if(type <= MBVERTEX || type >= MBENTITYSET)
-    return MB_TYPE_OUT_OF_RANGE;
-
-  MBErrorCode result = MB_SUCCESS, temp_result;
-  for (i = 0; i < num_handles; i++) {
-    const EntitySequence* seq = 0;
-
-      // We know that connectivity is stored in an EntitySequence so jump straight
-      // to the entity sequence
-    temp_result = sequence_manager()->find(entity_handles[i], seq);
-    if (seq == NULL) {
-      result = MB_ENTITY_NOT_FOUND;
-      continue;
-    }
-    else if (temp_result != MB_SUCCESS) {
-      result = temp_result;
-      continue;
-    }
-
-    const ElementSequence *elem_seq = static_cast<const ElementSequence*>(seq);
-      // let's be smart about this...
-    temp_result = elem_seq->get_connectivity(entity_handles[i], connectivity,
-                                             topological_connectivity);
-    if (MB_SUCCESS != temp_result) {
-      result = temp_result;
-      continue;
-    }
-  }
-  
-  return result;
+  connectivity.clear(); // this seems wrong as compared to other API functions,
+                        // but changing it breaks lost of code, so I'm leaving
+                        // it in.  - j.kraftcheck 2009-11-06
+  
+  MBErrorCode rval;
+  std::vector<MBEntityHandle> tmp_storage; // used only for structured mesh
+  const MBEntityHandle* conn;
+  int len;
+  for (int i = 0; i < num_handles; ++i) {
+    rval = get_connectivity( entity_handles[i], conn, len, topological_connectivity, &tmp_storage );
+    if (MB_SUCCESS != rval)
+      return rval;
+    connectivity.insert( connectivity.end(), conn, conn + len );
+  }
+  return MB_SUCCESS;
 }
 
@@ -1080 +1047 @@
 }
 
-MBErrorCode MBCore::get_adjacencies(const MBEntityHandle *from_entities,
-                                      const int num_entities,
-                                      const int to_dimension,
-                                      const bool create_if_missing,
-                                      std::vector<MBEntityHandle> &adj_entities,
-                                      const int operation_type)
+MBErrorCode MBCore::get_adjacencies( const MBEntityHandle *from_entities,
+                                     const int num_entities,
+                                     const int to_dimension,
+                                     const bool create_if_missing,
+                                     std::vector<MBEntityHandle> &adj_entities,
+                                     const int operation_type )
 {
   MBErrorCode result;
-  if (num_entities == 1) {
+  if (num_entities == 1 && adj_entities.empty()) {
     if(to_dimension == 0 && TYPE_FROM_HANDLE(from_entities[0]) != MBPOLYHEDRON)
       result = get_connectivity(&from_entities[0], 1, adj_entities);
     else
       result = aEntityFactory->get_adjacencies(from_entities[0], to_dimension, 
-                                               create_if_missing, adj_entities);
-    std::vector<MBEntityHandle>::iterator iter = 
-      std::remove(adj_entities.begin(), adj_entities.end(), MBEntityHandle(0));
-    if(iter != adj_entities.end())
-      adj_entities.erase(iter, adj_entities.end());
+                                             create_if_missing, adj_entities);
+    
+    //adj_entities.erase( std::remove( adj_entities.begin(), adj_entities.end(), 0 ), adj_entities.end() );
     return result;
   }
   
-  MBRange temp_range, temp_range2;
-  std::copy(from_entities, from_entities+num_entities,
-            mb_range_inserter(temp_range));
-  
-  result = get_adjacencies(temp_range, to_dimension, create_if_missing, temp_range2,
-                           operation_type);
-  if (MB_SUCCESS != result) 
-    return result;
-  
-  adj_entities.clear();
-  adj_entities.reserve(temp_range2.size());
-  for (MBRange::const_iterator it = temp_range2.begin();
-       it != temp_range2.end();
-       ++it)
-    adj_entities.push_back(*it);
-  
+  if (operation_type == MBInterface::UNION) {
+    std::vector<MBEntityHandle> tmp_storage;
+    const MBEntityHandle* conn;
+    int len;
+    for (int i = 0; i < num_entities; ++i) {
+      if(to_dimension == 0 && TYPE_FROM_HANDLE(from_entities[0]) != MBPOLYHEDRON) {
+        result = get_connectivity(from_entities[i], conn, len, false, &tmp_storage);
+        adj_entities.insert( adj_entities.end(), conn, conn+len );
+        if (MB_SUCCESS != result)
+          return result;
+      }
+      else {
+        result = aEntityFactory->get_adjacencies(from_entities[i], to_dimension, 
+                                                 create_if_missing, adj_entities);
+        if (MB_SUCCESS != result)
+          return result;
+      }
+    }
+    std::sort( adj_entities.begin(), adj_entities.end() );
+    adj_entities.erase( std::unique( adj_entities.begin(), adj_entities.end() ), adj_entities.end() );
+    return MB_SUCCESS;
+  }
+  
+  std::vector<MBEntityHandle> tmp_adj;
+  for (int i = 0; i < num_entities; ++i) {
+    tmp_adj.clear();
+    if(to_dimension == 0 && TYPE_FROM_HANDLE(from_entities[i]) != MBPOLYHEDRON)
+      result = get_connectivity(&from_entities[i], 1, tmp_adj);
+    else
+      result = aEntityFactory->get_adjacencies(from_entities[i], to_dimension, 
+                                               create_if_missing, tmp_adj);
+    if (MB_SUCCESS != result)
+      return result;
+    
+    if (tmp_adj.empty()) {
+      adj_entities.clear();
+      return MB_SUCCESS;
+    }
+    else if (i == 0 && adj_entities.empty())
+      adj_entities.swap(tmp_adj);
+    else {
+      std::sort( tmp_adj.begin(), tmp_adj.end() );
+      std::vector<MBEntityHandle>::iterator it, w;
+      for( it = w = adj_entities.begin(); it != adj_entities.end(); ++it ) {
+        if (std::binary_search( tmp_adj.begin(), tmp_adj.end(), *it ))
+          { *w = *it; ++w; }
+      }
+      adj_entities.erase( w, adj_entities.end() );
+    }
+  }
+ 
   return MB_SUCCESS;
 }
 
-MBErrorCode MBCore::get_adjacencies(const MBEntityHandle *from_entities,
-                                    const int num_entities,
-                                    const int to_dimension,
-                                      const bool create_if_missing,
-                                      MBRange &adj_entities,
-                                      const int operation_type)
-{
-  MBRange tmp_from_entities;
-  std::copy(from_entities, from_entities+num_entities, mb_range_inserter(tmp_from_entities));
-  return get_adjacencies(tmp_from_entities, to_dimension, create_if_missing, 
-                         adj_entities, operation_type);
-}
-
-MBErrorCode MBCore::get_vertices( const MBRange& from_entities,
-                                  MBRange& adj_entities )
-{
-  const size_t DEFAULT_MAX_BLOCKS_SIZE = 4000;
-  const size_t MAX_OUTER_ITERATIONS = 100;
-
-  std::vector<MBEntityHandle> temp_vec, storage;
-  std::vector<MBEntityHandle>::const_iterator ti;
-  MBErrorCode result = MB_SUCCESS, tmp_result;
-  MBRange::const_iterator i = from_entities.begin();
-  MBRange::iterator ins;
-  const MBEntityHandle* conn;
-  int conn_len;
-
-    // Just copy any vertices from the input range into the output
-  size_t remaining = from_entities.size();
-  for (; i != from_entities.end() && TYPE_FROM_HANDLE(*i) == MBVERTEX; ++i) 
-    --remaining;
-  adj_entities.merge( from_entities.begin(), i );
-  
-    // How many entities to work with at once? 2000 or so shouldn't require
-    // too much memory, but don't iterate in outer loop more than a
-    // 1000 times (make it bigger if many input entiites.) 
-  const size_t block_size = std::max( DEFAULT_MAX_BLOCKS_SIZE, remaining/MAX_OUTER_ITERATIONS );
-  while (remaining > 0) {
-    const size_t count = remaining > block_size ? block_size : remaining;
-    remaining -= count;
-    temp_vec.clear();
-    for (size_t j = 0; j < count; ++i, ++j) {
-      tmp_result = get_connectivity( *i, conn, conn_len, false, &storage );
-      if (MB_SUCCESS != tmp_result) {
-        result = tmp_result;
-        continue;
-      }
-
-      if (TYPE_FROM_HANDLE(*i) == MBPOLYHEDRON) {
-        storage.clear();
-        tmp_result = get_connectivity( conn, conn_len, storage );
-        if (MB_SUCCESS != tmp_result) {
-          result = tmp_result;
-          continue;
-        }
-        conn_len = storage.size();
-        conn = &storage[0];
-      }
-
-      const size_t oldsize = temp_vec.size();
-      temp_vec.resize( oldsize + conn_len );
-      memcpy( &temp_vec[oldsize], conn, sizeof(MBEntityHandle)*conn_len );
-    }
-
-    std::sort( temp_vec.begin(), temp_vec.end() );
-    ins = adj_entities.begin();
-    ti = temp_vec.begin();
-    while (ti != temp_vec.end()) {
-      MBEntityHandle first = *ti;
-      MBEntityHandle second = *ti;
-      for (++ti; ti != temp_vec.end() && (*ti - second <= 1); ++ti)
-        second = *ti;
-      ins = adj_entities.insert( ins, first, second );
-    }
-  }
-  return result;
-}
-
-MBErrorCode MBCore::get_adjacencies(const MBRange &from_entities,
-                                      const int to_dimension,
-                                      const bool create_if_missing,
-                                      MBRange &adj_entities,
-                                      const int operation_type)
-{
-  if (operation_type != MBInterface::INTERSECT &&
-      operation_type != MBInterface::UNION) return MB_FAILURE;
-
-  if(from_entities.size() == 0)
-    return MB_SUCCESS;
-
-    // special case for getting all vertices
-  if (to_dimension == 0 && operation_type == MBInterface::UNION) {
-    return get_vertices( from_entities, adj_entities );
-  }
-
+template <typename ITER> static inline
+MBErrorCode get_adjacencies_common( MBCore* mb,
+                             ITER begin, ITER end,
+                             const int to_dimension,
+                             const bool create_if_missing,
+                             MBRange &adj_entities,
+                             const int operation_type )
+{
   MBRange temp_range;
   std::vector<MBEntityHandle> temp_vec;
@@ -1220 +1133 @@
   MBErrorCode result = MB_SUCCESS, tmp_result;
 
-  for (MBRange::const_iterator from_it = from_entities.begin(); 
-       from_it != from_entities.end(); from_it++) 
+  for (ITER from_it = begin; from_it != end; from_it++) 
   {
       // running results kept in adj_entities; clear temp_vec and temp_range, which are working space
@@ -1228 +1140 @@
 
       // get the next set of adjacencies
-    if(to_dimension == 0 && TYPE_FROM_HANDLE(*from_it) != MBPOLYHEDRON)
-      tmp_result = get_connectivity(&(*from_it), 1, temp_vec);
+    MBEntityType type = TYPE_FROM_HANDLE(*from_it);
+    if (to_dimension == MBCN::Dimension(type)) 
+      { temp_vec.push_back(*from_it); tmp_result = MB_SUCCESS; }
+    else if(to_dimension == 0 && type != MBPOLYHEDRON)
+      tmp_result = mb->get_connectivity(&(*from_it), 1, temp_vec);
     else
-      tmp_result = aEntityFactory->get_adjacencies(*from_it, to_dimension, 
+      tmp_result = mb->a_entity_factory()->get_adjacencies(*from_it, to_dimension, 
                                                    create_if_missing, temp_vec);
     
@@ -1240 +1155 @@
       // if we're on the first iteration and we didn't come in with entities,
       // just get the first results and move on
-    if (adj_entities.empty() && from_it == from_entities.begin()) {
+    if (adj_entities.empty() && from_it == begin) {
       std::copy(temp_vec.rbegin(), temp_vec.rend(), mb_range_inserter(adj_entities));
       continue;
@@ -1276 +1191 @@
   return result;
 }
+
+MBErrorCode MBCore::get_adjacencies( const MBEntityHandle *from_entities,
+                                     const int num_entities,
+                                     const int to_dimension,
+                                     const bool create_if_missing,
+                                     MBRange &adj_entities,
+                                     const int operation_type )
+{
+  return get_adjacencies_common( this, from_entities, from_entities + num_entities,
+                          to_dimension, create_if_missing, adj_entities, operation_type );
+}
+
+MBErrorCode MBCore::get_vertices( const MBRange& from_entities,
+                                  MBRange& adj_entities )
+{
+  const size_t DEFAULT_MAX_BLOCKS_SIZE = 4000;
+  const size_t MAX_OUTER_ITERATIONS = 100;
+
+  std::vector<MBEntityHandle> temp_vec, storage;
+  std::vector<MBEntityHandle>::const_iterator ti;
+  MBErrorCode result = MB_SUCCESS, tmp_result;
+  MBRange::const_iterator i = from_entities.begin();
+  MBRange::iterator ins;
+  const MBEntityHandle* conn;
+  int conn_len;
+
+    // Just copy any vertices from the input range into the output
+  size_t remaining = from_entities.size();
+  for (; i != from_entities.end() && TYPE_FROM_HANDLE(*i) == MBVERTEX; ++i) 
+    --remaining;
+  adj_entities.merge( from_entities.begin(), i );
+  
+    // How many entities to work with at once? 2000 or so shouldn't require
+    // too much memory, but don't iterate in outer loop more than a
+    // 1000 times (make it bigger if many input entiites.) 
+  const size_t block_size = std::max( DEFAULT_MAX_BLOCKS_SIZE, remaining/MAX_OUTER_ITERATIONS );
+  while (remaining > 0) {
+    const size_t count = remaining > block_size ? block_size : remaining;
+    remaining -= count;
+    temp_vec.clear();
+    for (size_t j = 0; j < count; ++i, ++j) {
+      tmp_result = get_connectivity( *i, conn, conn_len, false, &storage );
+      if (MB_SUCCESS != tmp_result) {
+        result = tmp_result;
+        continue;
+      }
+
+      if (TYPE_FROM_HANDLE(*i) == MBPOLYHEDRON) {
+        storage.clear();
+        tmp_result = get_connectivity( conn, conn_len, storage );
+        if (MB_SUCCESS != tmp_result) {
+          result = tmp_result;
+          continue;
+        }
+        conn_len = storage.size();
+        conn = &storage[0];
+      }
+
+      const size_t oldsize = temp_vec.size();
+      temp_vec.resize( oldsize + conn_len );
+      memcpy( &temp_vec[oldsize], conn, sizeof(MBEntityHandle)*conn_len );
+    }
+
+    std::sort( temp_vec.begin(), temp_vec.end() );
+    ins = adj_entities.begin();
+    ti = temp_vec.begin();
+    while (ti != temp_vec.end()) {
+      MBEntityHandle first = *ti;
+      MBEntityHandle second = *ti;
+      for (++ti; ti != temp_vec.end() && (*ti - second <= 1); ++ti)
+        second = *ti;
+      ins = adj_entities.insert( ins, first, second );
+    }
+  }
+  return result;
+}
+
+MBErrorCode MBCore::get_adjacencies(const MBRange &from_entities,
+                                      const int to_dimension,
+                                      const bool create_if_missing,
+                                      MBRange &adj_entities,
+                                      const int operation_type)
+{
+  if (operation_type != MBInterface::INTERSECT &&
+      operation_type != MBInterface::UNION) return MB_FAILURE;
+
+  if(from_entities.size() == 0)
+    return MB_SUCCESS;
+
+    // special case for getting all vertices
+  if (to_dimension == 0 && operation_type == MBInterface::UNION) {
+    return get_vertices( from_entities, adj_entities );
+  }
+
+  return get_adjacencies_common( this, from_entities.begin(), from_entities.end(),
+                           to_dimension, create_if_missing, adj_entities, operation_type );
+}
+
 
 MBErrorCode MBCore::add_adjacencies(const MBEntityHandle entity_handle,