efficient way to determine Quad Tree neighbors for Quad Sphere Face edges?
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
add a comment |
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
add a comment |
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
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
unity3d quadtree
asked Nov 20 '18 at 15:55
bicarbon8bicarbon8
1627
1627
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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
add a comment |
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
add a comment |
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
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
answered Nov 23 '18 at 15:45
bicarbon8bicarbon8
1627
1627
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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