Sculpt: minor speedup for dyntopo
authorCampbell Barton <ideasman42@gmail.com>
Tue, 7 Oct 2014 19:02:08 +0000 (21:02 +0200)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 7 Oct 2014 19:02:08 +0000 (21:02 +0200)
Add retake to range-tree to avoid double lookup.

extern/rangetree/range_tree.hh
extern/rangetree/range_tree_c_api.cc
extern/rangetree/range_tree_c_api.h
source/blender/bmesh/intern/bmesh_log.c

index 919e0b049330d2ac53d7a0ada3cdda7dd338b32f..b247a0c6a1ecd05fd28d5fa67902b017eb86e359 100644 (file)
@@ -92,6 +92,28 @@ struct RangeTree {
                        tree.insert(Range(t + 1, cur.max));
        }
 
+       /* clone of 'take' that checks if the item exists */
+       bool retake(T t) {
+               #if RANGE_TREE_DEBUG_PRINT_FUNCTION
+               std::cout << __func__ << "(" << t << ")\n";
+               #endif
+
+               TreeIter iter = tree.find(Range(t));
+               if (iter == tree.end()) {
+                       return false;
+               }
+
+               Range cur = *iter;
+               tree.erase(iter);
+               if (t > cur.min)
+                       tree.insert(Range(cur.min, t - 1));
+               if (t + 1 <= cur.max)
+                       tree.insert(Range(t + 1, cur.max));
+
+               return true;
+       }
+
+
        /* Take the first element out of the first range in the
           tree. Precondition: tree must not be empty. */
        T take_any() {
index 79d3df5792b42bfd5cde57cd02ed27c01f442bc5..f040b5eaeb68de3ffb25e57c83b33e325ca6a887 100644 (file)
@@ -43,6 +43,11 @@ void range_tree_uint_take(RangeTreeUInt *rt, unsigned v)
        rt->take(v);
 }
 
+bool range_tree_uint_retake(RangeTreeUInt *rt, unsigned v)
+{
+       return rt->retake(v);
+}
+
 unsigned range_tree_uint_take_any(RangeTreeUInt *rt)
 {
        return rt->take_any();
index d78dc959a6c2005fd82ff3da8c83cd318852f6fd..f0a2af4a29a68aed925cc21e7f6649827f61668f 100644 (file)
@@ -35,6 +35,8 @@ void range_tree_uint_free(RangeTreeUInt *rt);
 
 void range_tree_uint_take(RangeTreeUInt *rt, unsigned v);
 
+bool range_tree_uint_retake(RangeTreeUInt *rt, unsigned v);
+
 unsigned range_tree_uint_take_any(RangeTreeUInt *rt);
 
 void range_tree_uint_release(RangeTreeUInt *rt, unsigned v);
index 0bb1a892ffeeaab4246e37d1ce176ea5d89e0239..709a174731f248f704bc4e5ac4d1befca99994ea 100644 (file)
@@ -423,9 +423,7 @@ static void bm_log_id_ghash_retake(RangeTreeUInt *unused_ids, GHash *id_ghash)
                void *key = BLI_ghashIterator_getKey(&gh_iter);
                unsigned int id = GET_UINT_FROM_POINTER(key);
 
-               if (range_tree_uint_has(unused_ids, id)) {
-                       range_tree_uint_take(unused_ids, id);
-               }
+               range_tree_uint_retake(unused_ids, id);
        }
 }