I understood how to create a TOctree, how to add and remove elements, but I have trouble understanding how to use it. I see that there are various iterators, but i don’t understand how it works.
Let’s see I have an octree with 3d coordinates (vectors), how do I search for a nearest point to some location? Something like:
FVector MyLoc;
FVector FoundLoc;
FoundLoc = Octree->FindNearest(MyLoc);
As far as I’m aware, TOctree only supports overlap queries via some pseudo-code like this:
FBoxCenterAndExtent bounds( point FVector( radius * 2.0f ) );
decltype(myTree)::TConstElementBoxIterator iterator( myTree, bounds );
float nearestSqrd = std::numeric_limits::max();
MyElement * nearestElement = nullptr;
while(iterator.HasPendingElements())
{
MyElement * element = iterator.GetCurrentElement();
float distSqrd = (element->position - point).SizeSquared();
if( distSqrd < nearestSqrd )
{
nearestSqrd = distSqrd;
nearestElement = element;
}
}
// if there is an overlap, nearestElement will point at the nearest, in the given radius
I’m just using decltype(myTree) because I don’t want to write the full specialization.
If you want a true k-nearest query, you could write your own iterator over the octree. In my work, I actually use a kd-tree, if you aren’t aware (but I think you are), kd-trees are a space-partitioning data structure designed for, “give me the k nearest points to this point.” I use nanoflann, it’s one of the fastest implementations out there. Recently it added a dynamic adaptor for adding/removing points. You could rebuild it every frame if you are making a bajillion queries, otherwise, building it is naturally a cost.
Oh, and nanoflann is header-only, which is great. Give it a look. The adaptor interface is a little clunky IMHO.
Cool, thank you, I will check that out. I found an example of TOctree use with iterators in UE code, I used that. It doesn’t use the box iterator but the other iterator.
Btw, I’m searching for some algorithms operating on sets of points, things like those:
Maybe you know some solutions for that?
Find duplicate points: For two points that are at almost the same position, an octree is good. Just use a box or sphere query, with the required distance. To detect exact duplicates, you can use a hash table or set on FVector.
Nearest points to a line segment: I assume you mean, find the nearest points to a line segment. A kd-tree might help, but you would have to write one whose distance measure was customized for that. I’m not aware of an existing implementation that does it, but it is possible.
Are these questions related to your Snap System Plugin? Are you perhaps trying to do things like find the nearest point on a mesh to a query point? In that case, I have some crude code, customized for my own work that you could hack for yours. It uses a kd-tree to find the nearest point on a mesh to a query point in O(log n) (ie, it’s crazy fast, practically constant-time).
I ported the code from VCGLib, which is amazing. It has so many useful functions on meshes (including spatial queries). The code I ported to Unreal is this.
Some features of VCGLib:
Here’s the code: https://github.com/timdecode/KdTreeF…_kdtree_face.h
It doesn’t work directly on UStaticMesh, you have to convert the UStaticMesh to a std::vector on TriangleSample container first.
Edit: Sorry, I forgot that VCGLib is GPL. That’s fine in my situation (I’m writing open source software as part of my research), but it’s copy-left. So, that’s evil.
@timtimmy Thank you!
No, i mean closest pair of points between 2 sets. If you have let’s say set A and set B, then the pair of points Pa,Pb such there is no other pair closest to each other.
I think if you put one set in a tree then searches all points from another set one by one it will be fast enough O(n log n) ?
Yes! Normally I use unreal collision queries only, they are very fast. But I thought of a feature where you have to search between points directly. I did that with octrees, but then realized it was not I wanted. (Basically I search if the socket is hidden behind something before snapping) So now I use ue queries and cache results and it works okay.
Still, those algorithms seems interesting.
Is it something like “spatial pattern matching”? I was making a context sensitive “autocomplete” feature for the plugin, for small things it works okay, but if there are many meshes and many sockets then the number of combination explodes.
Oh cool. This is interesting. Off the top of my head, I don’t know of an algorithm for this, but I’m sure there is something in the point cloud literature. However, maybe, you could beat the brute-force search of one tree like this.
So, O(log n log n). I think it will work? I could be wrong. It might require them not to have overlapping convex hulls. (Which, by the way, could be a good start, find the closest point between the convex hulls of both point sets, and go from there). But, you are right, I think O(n log n) might be fast enough, I’d try that first.
I wonder if they just define a list of compatible parts/modules for each edge type (I think I’m missing something)?
Sorry, I could explain better. Basically the plugin will snap (align) actors together and it’s based on sockets. When you move an actor with some sockets near to another actor with sockets the plugin will find the closest pair of sockets and “snap” actors according to that. It will adjust the transform of the moved actor so the matched sockets are in the same place. There is a little videoshowing that. There are some rules applied to know which socket will match and which will not. So, basically my sets of points are in fact sets of sockets (i.e. named transforms).
Now, the point of “spatial pattern matching” is to work another way around. Let’s say you have a list of parts (meshes), each part has some sockets defined. When you click on a socket in the world the plugin should search in the list and find a part that matches the best. You can see that in “autocomplete” from previous post . “Matching best” is defined by some simple metric, like for example how much sockets of the new part match sockets already in the world. So, like in that video, when you are in the corner the plugin should find the corner piece and not the straight one.
The brute force algorithm for that is trivial and it works, you just try all possible parts and all possible ways to attach them then you check how many matches you got. But of course it will have high complexity. So, that’s the thing I was talking about. It’s something like pattern matching for text but for sets of 3d points.