Question How do I get a range of vertices/edges using a half-edge data structure?

I have a half-edge data structure in 2D which loops through edges in a triangle in a clockwise order. I'm trying to get a range of vertices within a target vertex. Let's say I want all vertices within a depth of 2 like the picture below where the yellow vertex 0 is the target and the green vertices are the one's being retrieved.




So far this is what I have:

Code (CSharp):

1. public List<Vertex> GetSurroundingVerts(int index)
2.         {
3.             List<Vertex> vertContainer = new List<Vertex>();
4.             HalfEdge startHE = Vertices[index].SourceHE;
5.             HalfEdge currentHE = startHE;
6.  
7.             vertContainer.Add(startHE.SourceVert);
8.  
9.             do
10.             {
11.                 vertContainer.Add(currentHE.Next.SourceVert);
12.                 currentHE = currentHE.Twin.Next;
13.             } while (currentHE != startHE);
14.             return vertContainer;
15.         }

This works for getting the immediate surrounding vertices of a target vertex but once you increase the range, using this approach for each vertex will be more expensive the larger the range is. For the example picture above we have to check 19 vertices. 19 * 6 = 114 iterations which already becomes more expensive than just using a for-loop and comparing each vertex with the target vertex.

Currently, I'm trying to see if an algorithm that can traverse through the edges in a straight direction is possible (0 to 1 to 7 to 19 to 37 in the picture below) but no luck so far.



What's the best way to go about retrieving the vertices in this situation?

 

I'm not sure I understand your problem entirely. And I don't know what a "HalfEdge" is. But could you not just look the indices of the vertices up in the triangle array? So you find out which index has the vertex you are interested in. Then you find all triplets of indices which contain this index. The other ones in those triplets are one "length" away. You put them in a List (avoid doubles) and do the same again for getting all 2 lengthss away.
It is advisable to not work directly on the mesh data but to make copies of those arrays and work on them. It could be useful to create a custom struct which contains triangle index and vertex so you don't have to look them up each other the whole time.

 

What's your opinion on comparing each vertex with the target vertex and calculating the distance between them and then filtering the ones that are too far away?

 

So like this?

Code (CSharp):

1.     public void GetSurroundingVerts(List<Vertex> vertContainer, int index)
2.             {
3.                 HalfEdge startHE = Vertices[index].SourceHE;
4.                 HalfEdge currentHE = startHE;
5.    
6.                 vertContainer.Add(startHE.SourceVert);
7.    
8.                 do
9.                 {
10.                     vertContainer.Add(currentHE.Next.SourceVert);
11.                     currentHE = currentHE.Twin.Next;
12.                 } while (currentHE != startHE);
13.             }
14.  

What if I need new vertex values and the number of vertex values needed is always changing?

 

That depends on the regularity of your mesh. If all your meshes are like the one in your example image it COULD work. But imagine the triangles on the right side of your image beeing larger and more spread out. Then this would probably not work properly with distance.
So you must decide if you want a selection via distance or via topology (which requires that you look up neighbouring triangles no matter the physical distane of the vertices).
But for a real suggestion we have too little information of what (different, if any) meshes you have, what you need this stuff for, how often it runs (realtime?) and what requirements you have.

The "algorithm" I suggested only iterates the number of your depth. So when you need a depth of 2 it would also require 2 iterations.

Normally you would decide wether to use spatial or topological distance from your requirements. Not what is cheaper to calulate. So decide what you need first, then see how you can make it fast enough.

Some questions you should answer for us beeing able to give better advise:
Is this the only mesh or are there different ones?
Is the order of the vertices (your numbers in the image) given or can it be different?
I guess any vertex can be selected?
What do you need the vertices in range for (coloring, deleting)?
How often does this happen? Can this be precalculated?
Is the "range"/distance the same or can it vary too?
Do you, in the end, need the vertices, edges or the triangles?
What is this HalfEdge structure you mentioned used for?

Since the "spatial acceleration structure" has it's own overhead I'm not sure this is viable here for so few points. If arbitrary or much larger meshes shall be used sure. But for so a small mesh it seems like overkill to me.

I have seen a video some time ago about a new Unity feature/API where balls in a certain range are selected. But I can't remember how it was called (and thus can't provide a link). Maybe Melv knows what I mean.

 

Your curiosity is way too easily peakable .
So I had a search in my link collection (you owe me one ):
The "video" I remembered was not from Unity but from this blog: https://unitycoder.com/blog/2018/10/31/find-nearby-objects-using-cullinggroup/
And here's the documentation about culling groups: https://docs.unity3d.com/ScriptReference/CullingGroup.html
I'm not sure if that helps here in this context. But if Niko is willing to tell us a bit more maybe we can narrow down our suggestions.

 

Unless we get a bit more information about what this is for and the constraints/requirements the speculation is not usefull (but it does not hurt anyone either )

I have restrained from suggesting DOTS/ECS for 2 reasons:
First it adds a whole layer of complexity and "paradigm shift" OP may not be comfortable with. (And maybe the huge performance gain is not even required).
Second Tiny and ECS are in a "experimental" state und unfortunately there is no official information about ECS for almost a year now. So adopting those promising tech comes with a risk.
And I'm not even talking about version compatibility here . So from my PoV it is a bit too early to apply these. But I'm eagerly waiting for an "official revive" to try ECS a bit.

 

Here's an example of what I'm trying to do: https://i.imgur.com/yeftyTm.gif

Is this the only mesh or are there different ones?
-There can be potentially more that are instantiated but they all should have their own mesh info.

Is the order of the vertices (your numbers in the image) given or can it be different?
-The order needs to be consistent for the triangles but as long as that's maintained then vertex numbers can be in any order.

I guess any vertex can be selected?
-Any vertex should be able to be selected

What do you need the vertices in range for (coloring, deleting)?
-I need them in order to displace and deform the mesh using mouse drag functionality. When the vertices get pushed in this manner, the edges will get stretched and when the edges reach a certain length, they will be split and subdivided to keep roundness.

How often does this happen? Can this be precalculated?
-Every frame. I don't think so. This needs to be checked and updated every frame.

Is the "range"/distance the same or can it vary too?
-This can be adjusted pre-initialization but in runtime, no.

Do you, in the end, need the vertices, edges or the triangles?
-Yes. I need them to update and deform the mesh.

What is this HalfEdge structure you mentioned used for?
-It's used for retrieving mesh data more easily. This data can be used for things like subdivision. You can retrieve edges surrounding a vertex and its triangles fairly easily. I need to retrieve edge data (especially boundary edges) and use it as part of my functionality. (https://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm)

Doesn't JOBS require me to run things in parallel? I don't think I can do that. The mesh data operations for me need to be ran in a specific order or calculations will get messed up.

Here's an example of what I'm trying to do: https://i.imgur.com/yeftyTm.gif

 

Hm, thats pretty specific behavior. From the looks of it, it seems the whole mesh is beeing "dragged" as even the rightmost vertex is moved a little to the left.

I meant it more wether they all look like this or they look completely different (for example a regular grid, or the model of a car).

What happens when you move the vertex towards the center? Shouldn't also vertices be removed when an edge gets too short (as seen on the outer vertiies you drag towards).

Inserting vertices adds some complexity since all your "initial" topology data is invalidated. But probably you need to calculate it again avery frame for the edge length alone. MelvMay's suggestion/example would give you the vertices in a certain range. But since you need more info (edges, insertion/deletion rules) you still need to calculate those.
Since it seems you have this functionality already in place I would try to optimize it if I were you.
I have quickly looked in your half-edge article. It seems you already have the topology connections there. So I don't understand your problem/question. From the dragged point/vertex you could just follow all it's connected ones.

 

The .GIF above is not using the half-edge data structure. It's using more of a brute-force approach to update the edge data.

The way I'm using to find the vertices in range in the .GIF is also brute force just checking the distance between the mouse position and the position of each vertex. I was wondering if this would still be more efficient than getting the surrounding vertices/edges using the half-edge approach. For example, if you had a 500 vertex mesh then that's 500 iterations but if we were using the half-edge approach, each mesh had on average 6 neighboring edges/vertices then that's worst case 500*6 = 3000 iterations.

If there are other tips or approaches on optimization that I might have skipped, that would be great to know!

Are there any caveats I need to note if I try to use this for mobile?

 

Why 500*6 = 3000? The point of using the topology information (neighbouring vertices) is to reduce the amount of total vertices need to be checked. SO you start at your dragged vertex. Find its around 6 neighbours. Put them in a list. Then you find all neighbours for those in the list too (and check if they are alrerady in the list, don't add them more than once). Then you have all vertices within the "depth" of 2 and this should be around 20-30 distance checks. And this topology stays the same so it does not need to run every frame, only when you split/remove edges it needs to be updated/recalculated. I thought that would be clear and that was what I tried to explain in my initial post. So this seems to be a "trivial" optimization and would reduce the number of vertices in need of checking to a small amount. Bot note this is the topological distance, not the world distance. Thats why I asked which of both you need.

Either which approach you need (world distance or topological distance) you don't need to run this every frame but you should define a threshold the mouse has to be moved before calculating the whole stuff again.

 

The standard solution to a problem like this is to apply Djikstras algorith. https://en.wikipedia.org/wiki/Dijkstra's_algorithm

This algorithm computes the cost (or distance in your case) from each point in a graph to some selected node. You want to compute this, then select all the nodes with distance <= 2.

Given your problem formulation you can optimize the solution a lot, for instance, you can break early when all nodes have at least distance > 2, since then no candidates can be found which you would select anyway.

 

What I meant was in situations where the number of vertices I want to retrieve gets larger.

The above is a circular mesh with 88 vertices. Let's say I want to create some proximity query that selects vertices within depth 3 from a target point (green). In total, I would have to iterate through 19 vertices (red). However, for each vertex, I would need to check neighbouring vertices which is 6 checks per vertex to decide if they are already marked as a selected vertex or not. I'm assuming I'd need to use a Contains function for List which is O(N) for each vertex that I check so not only do I need to check every neighbour if it exists or not (6 * 19 = 114 checks which is already more than 88 which is the number of vertices in the mesh) but I'd have to use Contains in each check. Is there a chance that just looping through each vertex, comparing their world distance with the target vertex and using that to dictate the vertices be more efficient? It gets even worse for bigger meshes.

 

Slowly I get the feeling we are talking at cross-purposes here. And I'm sorry if I am the one understanding you incorrectly. Or if I cannot make my point clear enough (I'm not a native english speaker).

How do you know which one are those 19? That is the point that you have to decide that you either:
1) iterate over all vertices, check their distance to your target and "select"/remember those that are close enough.
2) start from the green vertex and add it's surrounding 6 vertices to a collection (list, queue, you name it). Then check their neighbours and add them too (only once!). You NEED some topology information for that. I thought that your HalfEdge class would provide those (but I'm not sure and won't dig too deep into it). Or you could extract it from the triangles array as described in my first post.

That sounds indeed very wasteful and is not what I suggested (when I understand you correctly). There is no need for checks since the topology information (neighbours) should already be there (HalfEdge, or your own data structure). So you would only iterate over the neighbours.

Do you actually have a performance problem?
What is faster is hard to say as it depends on many factors (your implementation and optimization). If you are unsure implement both and profile which is faster.

As MelvMay demonstrated you can get along with thousands of vertices if you do it right. Do you actually need so big meshes? Your endgoal, what you want to do with those meshes is still beyond my understanding.

If you have already the brute force distance method running, I'd say go with it and try to optimize it since it is algorithmically easier (brute force). You could try MelvMay's jobs/burst approach.
It sounds as if you have not implemented this HalfEdge thing yet?

Edit: And as I said only do the work when it is neccessary. When nothing changed you don't need to calculate the neighbours again.

 

I get the feeling, having read through this thread properly, that topological distance (if that is a word) may not be what you are looking for. The gif shows some kind ot vertex dragging with falloff.

Have you tried something like that? Essentially you would at mouse down (dragging starts) put some weight on all the vertices in the mesh, and at each frame you set the position of the vertices as mouse position blended (using the weight) with the original vertex position.

Weight goes from one at the mouse pointer to zero at some max distance…. Or something like that.

When you get this working you can consider mesh relaxation, splitting triangles and so on.

 

Thanks for the help so far @ubbelito @exiguous @MelvMay

Currently I've put this problem on hold and have a much bigger problem in terms of edge collapsing https://forum.unity.com/threads/hav...ration-with-half-edge-data-structure.1199644/