efficient way to determine Quad Tree neighbors for Quad Sphere Face edges?












0















I've been trying to optimise how I lookup the neighbors for the Quad Tree faces in my Quad Sphere's Top and Bottom faces with the rest of the faces. I've attempted several methods to determine neighbors, where the latest one improved the lookup speed, but I'm wondering if there is something better



Method 1:



Keep a lookup table of all users of all vertices used by all Quads and then, for each Quad, find any other Quads that aren't ancestors that share edge vertices with the original Quad (minus the corner vertices because these are shared by multiple, non-neighbors). This works great for low numbers of subdivisions and vertices, but as each of these increases, the performance becomes much worse.
See example here of this implementation: https://github.com/bicarbon8/QuadSphere/blob/master/Assets/Scripts/QuadVertMap.cs#L104



Method 2:



Keep a lookup table of all Quads at each Level of subdivision, indexed by level and then for each Quad, find any other Quads at either the same level or one level less (parents level) that aren't ancestors and check their edge vertices to see if they match with the original Quad's edge vertices. This works better than Method 1, but still starts to suffer if you get too deep in the levels of subdivision. This looks like the following code snippet:



public Quad FindNeighbor(Quad quad, EdgeType edge)
{
Vector3 edgeVerts = quad.GetWorldVerts(quad.GetEdgeVerts(edge));
int level = quad.GetLevel(); // neighbors can only be equal or 1 lower level

List<Quad> potentialNeighbors = Quads[level].Where(n => n != quad).ToList();
if (potentialNeighbors.Any())
{
foreach (Quad potentialNeighbor in potentialNeighbors)
{
var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
if (topEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
if (bottomEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
if (leftEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
if (rightEdge.All(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
}
}

if (level > 0)
{
// if we made it this far we haven't found a neighbor yet so try 1 level lower Quads
potentialNeighbors = Quads[level - 1].Where(n => n != quad.GetParent()).ToList();
if (potentialNeighbors.Any())
{
foreach (Quad potentialNeighbor in potentialNeighbors)
{
var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
if (topEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
if (bottomEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
if (leftEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
if (rightEdge.Any(v => edgeVerts.Contains(v)))
{
return potentialNeighbor;
}
}
}
}

return null;
}


Is there anyone who has experience with this and is willing to share some other means of optimising the lookup? Thanks in advance.










share|improve this question



























    0















    I've been trying to optimise how I lookup the neighbors for the Quad Tree faces in my Quad Sphere's Top and Bottom faces with the rest of the faces. I've attempted several methods to determine neighbors, where the latest one improved the lookup speed, but I'm wondering if there is something better



    Method 1:



    Keep a lookup table of all users of all vertices used by all Quads and then, for each Quad, find any other Quads that aren't ancestors that share edge vertices with the original Quad (minus the corner vertices because these are shared by multiple, non-neighbors). This works great for low numbers of subdivisions and vertices, but as each of these increases, the performance becomes much worse.
    See example here of this implementation: https://github.com/bicarbon8/QuadSphere/blob/master/Assets/Scripts/QuadVertMap.cs#L104



    Method 2:



    Keep a lookup table of all Quads at each Level of subdivision, indexed by level and then for each Quad, find any other Quads at either the same level or one level less (parents level) that aren't ancestors and check their edge vertices to see if they match with the original Quad's edge vertices. This works better than Method 1, but still starts to suffer if you get too deep in the levels of subdivision. This looks like the following code snippet:



    public Quad FindNeighbor(Quad quad, EdgeType edge)
    {
    Vector3 edgeVerts = quad.GetWorldVerts(quad.GetEdgeVerts(edge));
    int level = quad.GetLevel(); // neighbors can only be equal or 1 lower level

    List<Quad> potentialNeighbors = Quads[level].Where(n => n != quad).ToList();
    if (potentialNeighbors.Any())
    {
    foreach (Quad potentialNeighbor in potentialNeighbors)
    {
    var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
    if (topEdge.All(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
    if (bottomEdge.All(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
    if (leftEdge.All(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
    if (rightEdge.All(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    }
    }

    if (level > 0)
    {
    // if we made it this far we haven't found a neighbor yet so try 1 level lower Quads
    potentialNeighbors = Quads[level - 1].Where(n => n != quad.GetParent()).ToList();
    if (potentialNeighbors.Any())
    {
    foreach (Quad potentialNeighbor in potentialNeighbors)
    {
    var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
    if (topEdge.Any(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
    if (bottomEdge.Any(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
    if (leftEdge.Any(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
    if (rightEdge.Any(v => edgeVerts.Contains(v)))
    {
    return potentialNeighbor;
    }
    }
    }
    }

    return null;
    }


    Is there anyone who has experience with this and is willing to share some other means of optimising the lookup? Thanks in advance.










    share|improve this question

























      0












      0








      0








      I've been trying to optimise how I lookup the neighbors for the Quad Tree faces in my Quad Sphere's Top and Bottom faces with the rest of the faces. I've attempted several methods to determine neighbors, where the latest one improved the lookup speed, but I'm wondering if there is something better



      Method 1:



      Keep a lookup table of all users of all vertices used by all Quads and then, for each Quad, find any other Quads that aren't ancestors that share edge vertices with the original Quad (minus the corner vertices because these are shared by multiple, non-neighbors). This works great for low numbers of subdivisions and vertices, but as each of these increases, the performance becomes much worse.
      See example here of this implementation: https://github.com/bicarbon8/QuadSphere/blob/master/Assets/Scripts/QuadVertMap.cs#L104



      Method 2:



      Keep a lookup table of all Quads at each Level of subdivision, indexed by level and then for each Quad, find any other Quads at either the same level or one level less (parents level) that aren't ancestors and check their edge vertices to see if they match with the original Quad's edge vertices. This works better than Method 1, but still starts to suffer if you get too deep in the levels of subdivision. This looks like the following code snippet:



      public Quad FindNeighbor(Quad quad, EdgeType edge)
      {
      Vector3 edgeVerts = quad.GetWorldVerts(quad.GetEdgeVerts(edge));
      int level = quad.GetLevel(); // neighbors can only be equal or 1 lower level

      List<Quad> potentialNeighbors = Quads[level].Where(n => n != quad).ToList();
      if (potentialNeighbors.Any())
      {
      foreach (Quad potentialNeighbor in potentialNeighbors)
      {
      var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
      if (topEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
      if (bottomEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
      if (leftEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
      if (rightEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      }
      }

      if (level > 0)
      {
      // if we made it this far we haven't found a neighbor yet so try 1 level lower Quads
      potentialNeighbors = Quads[level - 1].Where(n => n != quad.GetParent()).ToList();
      if (potentialNeighbors.Any())
      {
      foreach (Quad potentialNeighbor in potentialNeighbors)
      {
      var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
      if (topEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
      if (bottomEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
      if (leftEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
      if (rightEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      }
      }
      }

      return null;
      }


      Is there anyone who has experience with this and is willing to share some other means of optimising the lookup? Thanks in advance.










      share|improve this question














      I've been trying to optimise how I lookup the neighbors for the Quad Tree faces in my Quad Sphere's Top and Bottom faces with the rest of the faces. I've attempted several methods to determine neighbors, where the latest one improved the lookup speed, but I'm wondering if there is something better



      Method 1:



      Keep a lookup table of all users of all vertices used by all Quads and then, for each Quad, find any other Quads that aren't ancestors that share edge vertices with the original Quad (minus the corner vertices because these are shared by multiple, non-neighbors). This works great for low numbers of subdivisions and vertices, but as each of these increases, the performance becomes much worse.
      See example here of this implementation: https://github.com/bicarbon8/QuadSphere/blob/master/Assets/Scripts/QuadVertMap.cs#L104



      Method 2:



      Keep a lookup table of all Quads at each Level of subdivision, indexed by level and then for each Quad, find any other Quads at either the same level or one level less (parents level) that aren't ancestors and check their edge vertices to see if they match with the original Quad's edge vertices. This works better than Method 1, but still starts to suffer if you get too deep in the levels of subdivision. This looks like the following code snippet:



      public Quad FindNeighbor(Quad quad, EdgeType edge)
      {
      Vector3 edgeVerts = quad.GetWorldVerts(quad.GetEdgeVerts(edge));
      int level = quad.GetLevel(); // neighbors can only be equal or 1 lower level

      List<Quad> potentialNeighbors = Quads[level].Where(n => n != quad).ToList();
      if (potentialNeighbors.Any())
      {
      foreach (Quad potentialNeighbor in potentialNeighbors)
      {
      var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
      if (topEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
      if (bottomEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
      if (leftEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
      if (rightEdge.All(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      }
      }

      if (level > 0)
      {
      // if we made it this far we haven't found a neighbor yet so try 1 level lower Quads
      potentialNeighbors = Quads[level - 1].Where(n => n != quad.GetParent()).ToList();
      if (potentialNeighbors.Any())
      {
      foreach (Quad potentialNeighbor in potentialNeighbors)
      {
      var topEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Top));
      if (topEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var bottomEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Bottom));
      if (bottomEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var leftEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Left));
      if (leftEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      var rightEdge = potentialNeighbor.GetWorldVerts(potentialNeighbor.GetEdgeVerts(EdgeType.Right));
      if (rightEdge.Any(v => edgeVerts.Contains(v)))
      {
      return potentialNeighbor;
      }
      }
      }
      }

      return null;
      }


      Is there anyone who has experience with this and is willing to share some other means of optimising the lookup? Thanks in advance.







      unity3d quadtree






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked Nov 20 '18 at 15:55









      bicarbon8bicarbon8

      1627




      1627
























          1 Answer
          1






          active

          oldest

          votes


















          0














          What I've ended up doing, since this post didn't receive any responses, is assigning the sibling neighbors based on some basic rules and then for the non-sibling neighbors I locate the parent quad, get their neighbor children and see if any of them share an edge with this quad



          private void AddNeighbors()
          {
          switch (QuadType)
          {
          case QuadType.BottomLeft:
          // add siblings
          AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopLeft); });
          AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.BottomRight); });

          // add non-siblings
          AddNeighbor(EdgeType.Bottom, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
          });
          AddNeighbor(EdgeType.Left, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
          });
          break;
          case QuadType.BottomRight:
          // add siblings
          AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopRight); });
          AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.BottomLeft); });

          // add non-siblings
          AddNeighbor(EdgeType.Bottom, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
          });
          AddNeighbor(EdgeType.Right, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
          });
          break;
          case QuadType.TopLeft:
          // add siblings
          AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomLeft); });
          AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.TopRight); });

          // add non-siblings
          AddNeighbor(EdgeType.Top, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
          });
          AddNeighbor(EdgeType.Left, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
          });
          break;
          case QuadType.TopRight:
          // add siblings
          AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomRight); });
          AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.TopLeft); });

          // add non-siblings
          AddNeighbor(EdgeType.Top, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
          });
          AddNeighbor(EdgeType.Right, () =>
          {
          return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
          });
          break;
          }
          }


          this seems to work quickly as all Sibling neighbors are a direct assignment and the locating of non-sibling neighbors is limited to iterating over 4 sides of 4 quads. Here is the HasSharedEdge method:



          public bool HasSharedEdge(EdgeType edge, Quad quad)
          {
          var topLeft = quad.ToWorldVert(quad.TopLeft);
          var topRight = quad.ToWorldVert(quad.TopRight);
          var bottomLeft = quad.ToWorldVert(quad.BottomLeft);
          var bottomRight = quad.ToWorldVert(quad.BottomRight);
          // shared Top edge
          if (IsLineWithinEdge(edge, topLeft, topRight, Tolerance))
          {
          return true;
          }
          // shared Bottom edge
          if (IsLineWithinEdge(edge, bottomLeft, bottomRight, Tolerance))
          {
          return true;
          }
          // shared Left edge
          if (IsLineWithinEdge(edge, bottomLeft, topLeft, Tolerance))
          {
          return true;
          }
          // shared Right edge
          if (IsLineWithinEdge(edge, bottomRight, topRight, Tolerance))
          {
          return true;
          }

          return false;
          }


          Maybe this can help someone else in the future






          share|improve this answer























            Your Answer






            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "1"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53396824%2fefficient-way-to-determine-quad-tree-neighbors-for-quad-sphere-face-edges%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            0














            What I've ended up doing, since this post didn't receive any responses, is assigning the sibling neighbors based on some basic rules and then for the non-sibling neighbors I locate the parent quad, get their neighbor children and see if any of them share an edge with this quad



            private void AddNeighbors()
            {
            switch (QuadType)
            {
            case QuadType.BottomLeft:
            // add siblings
            AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopLeft); });
            AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.BottomRight); });

            // add non-siblings
            AddNeighbor(EdgeType.Bottom, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
            });
            AddNeighbor(EdgeType.Left, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
            });
            break;
            case QuadType.BottomRight:
            // add siblings
            AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopRight); });
            AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.BottomLeft); });

            // add non-siblings
            AddNeighbor(EdgeType.Bottom, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
            });
            AddNeighbor(EdgeType.Right, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
            });
            break;
            case QuadType.TopLeft:
            // add siblings
            AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomLeft); });
            AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.TopRight); });

            // add non-siblings
            AddNeighbor(EdgeType.Top, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
            });
            AddNeighbor(EdgeType.Left, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
            });
            break;
            case QuadType.TopRight:
            // add siblings
            AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomRight); });
            AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.TopLeft); });

            // add non-siblings
            AddNeighbor(EdgeType.Top, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
            });
            AddNeighbor(EdgeType.Right, () =>
            {
            return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
            });
            break;
            }
            }


            this seems to work quickly as all Sibling neighbors are a direct assignment and the locating of non-sibling neighbors is limited to iterating over 4 sides of 4 quads. Here is the HasSharedEdge method:



            public bool HasSharedEdge(EdgeType edge, Quad quad)
            {
            var topLeft = quad.ToWorldVert(quad.TopLeft);
            var topRight = quad.ToWorldVert(quad.TopRight);
            var bottomLeft = quad.ToWorldVert(quad.BottomLeft);
            var bottomRight = quad.ToWorldVert(quad.BottomRight);
            // shared Top edge
            if (IsLineWithinEdge(edge, topLeft, topRight, Tolerance))
            {
            return true;
            }
            // shared Bottom edge
            if (IsLineWithinEdge(edge, bottomLeft, bottomRight, Tolerance))
            {
            return true;
            }
            // shared Left edge
            if (IsLineWithinEdge(edge, bottomLeft, topLeft, Tolerance))
            {
            return true;
            }
            // shared Right edge
            if (IsLineWithinEdge(edge, bottomRight, topRight, Tolerance))
            {
            return true;
            }

            return false;
            }


            Maybe this can help someone else in the future






            share|improve this answer




























              0














              What I've ended up doing, since this post didn't receive any responses, is assigning the sibling neighbors based on some basic rules and then for the non-sibling neighbors I locate the parent quad, get their neighbor children and see if any of them share an edge with this quad



              private void AddNeighbors()
              {
              switch (QuadType)
              {
              case QuadType.BottomLeft:
              // add siblings
              AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopLeft); });
              AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.BottomRight); });

              // add non-siblings
              AddNeighbor(EdgeType.Bottom, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
              });
              AddNeighbor(EdgeType.Left, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
              });
              break;
              case QuadType.BottomRight:
              // add siblings
              AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopRight); });
              AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.BottomLeft); });

              // add non-siblings
              AddNeighbor(EdgeType.Bottom, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
              });
              AddNeighbor(EdgeType.Right, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
              });
              break;
              case QuadType.TopLeft:
              // add siblings
              AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomLeft); });
              AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.TopRight); });

              // add non-siblings
              AddNeighbor(EdgeType.Top, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
              });
              AddNeighbor(EdgeType.Left, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
              });
              break;
              case QuadType.TopRight:
              // add siblings
              AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomRight); });
              AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.TopLeft); });

              // add non-siblings
              AddNeighbor(EdgeType.Top, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
              });
              AddNeighbor(EdgeType.Right, () =>
              {
              return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
              });
              break;
              }
              }


              this seems to work quickly as all Sibling neighbors are a direct assignment and the locating of non-sibling neighbors is limited to iterating over 4 sides of 4 quads. Here is the HasSharedEdge method:



              public bool HasSharedEdge(EdgeType edge, Quad quad)
              {
              var topLeft = quad.ToWorldVert(quad.TopLeft);
              var topRight = quad.ToWorldVert(quad.TopRight);
              var bottomLeft = quad.ToWorldVert(quad.BottomLeft);
              var bottomRight = quad.ToWorldVert(quad.BottomRight);
              // shared Top edge
              if (IsLineWithinEdge(edge, topLeft, topRight, Tolerance))
              {
              return true;
              }
              // shared Bottom edge
              if (IsLineWithinEdge(edge, bottomLeft, bottomRight, Tolerance))
              {
              return true;
              }
              // shared Left edge
              if (IsLineWithinEdge(edge, bottomLeft, topLeft, Tolerance))
              {
              return true;
              }
              // shared Right edge
              if (IsLineWithinEdge(edge, bottomRight, topRight, Tolerance))
              {
              return true;
              }

              return false;
              }


              Maybe this can help someone else in the future






              share|improve this answer


























                0












                0








                0







                What I've ended up doing, since this post didn't receive any responses, is assigning the sibling neighbors based on some basic rules and then for the non-sibling neighbors I locate the parent quad, get their neighbor children and see if any of them share an edge with this quad



                private void AddNeighbors()
                {
                switch (QuadType)
                {
                case QuadType.BottomLeft:
                // add siblings
                AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopLeft); });
                AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.BottomRight); });

                // add non-siblings
                AddNeighbor(EdgeType.Bottom, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
                });
                AddNeighbor(EdgeType.Left, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
                });
                break;
                case QuadType.BottomRight:
                // add siblings
                AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopRight); });
                AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.BottomLeft); });

                // add non-siblings
                AddNeighbor(EdgeType.Bottom, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
                });
                AddNeighbor(EdgeType.Right, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
                });
                break;
                case QuadType.TopLeft:
                // add siblings
                AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomLeft); });
                AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.TopRight); });

                // add non-siblings
                AddNeighbor(EdgeType.Top, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
                });
                AddNeighbor(EdgeType.Left, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
                });
                break;
                case QuadType.TopRight:
                // add siblings
                AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomRight); });
                AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.TopLeft); });

                // add non-siblings
                AddNeighbor(EdgeType.Top, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
                });
                AddNeighbor(EdgeType.Right, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
                });
                break;
                }
                }


                this seems to work quickly as all Sibling neighbors are a direct assignment and the locating of non-sibling neighbors is limited to iterating over 4 sides of 4 quads. Here is the HasSharedEdge method:



                public bool HasSharedEdge(EdgeType edge, Quad quad)
                {
                var topLeft = quad.ToWorldVert(quad.TopLeft);
                var topRight = quad.ToWorldVert(quad.TopRight);
                var bottomLeft = quad.ToWorldVert(quad.BottomLeft);
                var bottomRight = quad.ToWorldVert(quad.BottomRight);
                // shared Top edge
                if (IsLineWithinEdge(edge, topLeft, topRight, Tolerance))
                {
                return true;
                }
                // shared Bottom edge
                if (IsLineWithinEdge(edge, bottomLeft, bottomRight, Tolerance))
                {
                return true;
                }
                // shared Left edge
                if (IsLineWithinEdge(edge, bottomLeft, topLeft, Tolerance))
                {
                return true;
                }
                // shared Right edge
                if (IsLineWithinEdge(edge, bottomRight, topRight, Tolerance))
                {
                return true;
                }

                return false;
                }


                Maybe this can help someone else in the future






                share|improve this answer













                What I've ended up doing, since this post didn't receive any responses, is assigning the sibling neighbors based on some basic rules and then for the non-sibling neighbors I locate the parent quad, get their neighbor children and see if any of them share an edge with this quad



                private void AddNeighbors()
                {
                switch (QuadType)
                {
                case QuadType.BottomLeft:
                // add siblings
                AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopLeft); });
                AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.BottomRight); });

                // add non-siblings
                AddNeighbor(EdgeType.Bottom, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
                });
                AddNeighbor(EdgeType.Left, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
                });
                break;
                case QuadType.BottomRight:
                // add siblings
                AddNeighbor(EdgeType.Top, () => { return GetParent().GetChild(QuadType.TopRight); });
                AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.BottomLeft); });

                // add non-siblings
                AddNeighbor(EdgeType.Bottom, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Bottom)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Bottom, c));
                });
                AddNeighbor(EdgeType.Right, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
                });
                break;
                case QuadType.TopLeft:
                // add siblings
                AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomLeft); });
                AddNeighbor(EdgeType.Right, () => { return GetParent().GetChild(QuadType.TopRight); });

                // add non-siblings
                AddNeighbor(EdgeType.Top, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
                });
                AddNeighbor(EdgeType.Left, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Left)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Left, c));
                });
                break;
                case QuadType.TopRight:
                // add siblings
                AddNeighbor(EdgeType.Bottom, () => { return GetParent().GetChild(QuadType.BottomRight); });
                AddNeighbor(EdgeType.Left, () => { return GetParent().GetChild(QuadType.TopLeft); });

                // add non-siblings
                AddNeighbor(EdgeType.Top, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Top)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Top, c));
                });
                AddNeighbor(EdgeType.Right, () =>
                {
                return GetParent().GetNeighbor(EdgeType.Right)?.GetChildren()?.FirstOrDefault(c => c != null && HasSharedEdge(EdgeType.Right, c));
                });
                break;
                }
                }


                this seems to work quickly as all Sibling neighbors are a direct assignment and the locating of non-sibling neighbors is limited to iterating over 4 sides of 4 quads. Here is the HasSharedEdge method:



                public bool HasSharedEdge(EdgeType edge, Quad quad)
                {
                var topLeft = quad.ToWorldVert(quad.TopLeft);
                var topRight = quad.ToWorldVert(quad.TopRight);
                var bottomLeft = quad.ToWorldVert(quad.BottomLeft);
                var bottomRight = quad.ToWorldVert(quad.BottomRight);
                // shared Top edge
                if (IsLineWithinEdge(edge, topLeft, topRight, Tolerance))
                {
                return true;
                }
                // shared Bottom edge
                if (IsLineWithinEdge(edge, bottomLeft, bottomRight, Tolerance))
                {
                return true;
                }
                // shared Left edge
                if (IsLineWithinEdge(edge, bottomLeft, topLeft, Tolerance))
                {
                return true;
                }
                // shared Right edge
                if (IsLineWithinEdge(edge, bottomRight, topRight, Tolerance))
                {
                return true;
                }

                return false;
                }


                Maybe this can help someone else in the future







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered Nov 23 '18 at 15:45









                bicarbon8bicarbon8

                1627




                1627
































                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Stack Overflow!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53396824%2fefficient-way-to-determine-quad-tree-neighbors-for-quad-sphere-face-edges%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    How to change which sound is reproduced for terminal bell?

                    Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

                    Can I use Tabulator js library in my java Spring + Thymeleaf project?