1 files changed, 30 insertions, 11 deletions

diff --git a/geometry/cellid.hpp b/geometry/cellid.hpp
index 2af9231d7c..5f7d9964ac 100644
--- a/geometry/cellid.hpp
+++ b/geometry/cellid.hpp
@@ -51,7 +51,7 @@ public:
   {
     ASSERT(IsValid(), (m_bits, m_level));
     ASSERT_GREATER_OR_EQUAL(m_level, level, ());
-    return CellId(m_bits >> ((m_level - level) << 1), level);
+    return CellId(m_bits >> (2 * (m_level - level)), level);
   }
 
   CellId Child(int8_t c) const
@@ -203,8 +203,8 @@ public:
   {
     bool operator()(CellId<DEPTH_LEVELS> const & id1, CellId<DEPTH_LEVELS> const & id2) const
     {
-      int64_t const n1 = id1.ToInt64LevelZOrder(DEPTH_LEVELS);
-      int64_t const n2 = id2.ToInt64LevelZOrder(DEPTH_LEVELS);
+      int64_t const n1 = id1.ToInt64ZOrder(DEPTH_LEVELS);
+      int64_t const n2 = id2.ToInt64ZOrder(DEPTH_LEVELS);
       ASSERT_EQUAL(n1 < n2, id1.ToString() < id2.ToString(), (id1, id2));
       return n1 < n2;
     }
@@ -214,25 +214,39 @@ public:
   // Numbering
 
   // Default ToInt64().
-  int64_t ToInt64(int depth) const { return ToInt64LevelZOrder(depth); }
+  int64_t ToInt64(int depth) const { return ToInt64ZOrder(depth); }
 
   // Default FromInt64().
-  static CellId FromInt64(int64_t v, int depth) { return FromInt64LevelZOrder(v, depth); }
+  static CellId FromInt64(int64_t v, int depth) { return FromInt64ZOrder(v, depth); }
 
-  // Level order, numbering by Z-curve.
-  int64_t ToInt64LevelZOrder(int depth) const
+  // Returns the 1-based number this cell would get in the Z-curve ordering (pre-order
+  // traversal of the quadtree) of all the cells in the tree of depth |depth|.
+  // The tree of one vertex is assumed to have depth 1.
+  int64_t ToInt64ZOrder(int depth) const
   {
     ASSERT(0 < depth && depth <= DEPTH_LEVELS, (m_bits, m_level, depth));
     ASSERT(IsValid(), (m_bits, m_level));
 
     if (m_level >= depth)
-      return AncestorAtLevel(depth - 1).ToInt64(depth);
+      return AncestorAtLevel(depth - 1).ToInt64ZOrder(depth);
 
     uint64_t bits = m_bits;
     uint64_t res = 0;
-    for (int i = 0; i <= m_level; ++i, bits >>= 2)
+    // When counting, group the nodes by their level.
+    // All nodes to the left of the current one at its level
+    // and, for every ancestor, all nodes to the left of the ancestor
+    // at the ancestor's level will show up earlier during the traversal.
+    // All ancestors are visited before the current node, so add +1 for them.
+    // The result is 1-based, so add +1 for the node itself too.
+    for (int i = 0; i <= m_level; ++i)
+    {
       res += bits + 1;
+      bits >>= 2;
+    }
 
+    // By the same reasoning, if the children of every node are ordered
+    // left to right, then all nodes at deeper levels that
+    // are strictly to the left will be visited before the current one.
     bits = m_bits;
     for (int i = m_level + 1; i < depth; ++i)
     {
@@ -245,8 +259,10 @@ public:
     return static_cast<int64_t>(res);
   }
 
-  // Level order, numbering by Z-curve.
-  static CellId FromInt64LevelZOrder(int64_t v, int depth)
+  // Returns the CellId with the 1-based number |v| in the Z-curve ordering (pre-order
+  // traversal of the quadtree) of all the cells in the tree of depth |depth|.
+  // The tree of one vertex is assumed to have depth 1.
+  static CellId FromInt64ZOrder(int64_t v, int depth)
   {
     ASSERT_GREATER(v, 0, ());
     ASSERT(0 < depth && depth <= DEPTH_LEVELS, (v, depth));
@@ -266,6 +282,9 @@ public:
   }
 
 private:
+  // Returns the total number of nodes in the tree of depth |depth|.
+  // The tree of one vertex is assumed to have depth 1.
+  // The first few values are 1, 5, 21, 85.
   static uint64_t TreeSizeForDepth(int depth)
   {
     ASSERT(0 < depth && depth <= DEPTH_LEVELS, (depth));