16

KD-trees are definitively not dynamic enough to be considered, honestly. Moving a few units can easily require you to rebuild the whole KD-Tree. Plus, a KD-tree is very efficient for queries, but not so much for neighbor searching. A quadtree is more flexible over time, as the modification are kept more locally. The disadvantage is that if you have many ...


11

Quadtrees typically store and retrieve rectangles. A point is a specific case where width and height are zero. The following logic is used to find home for new rectangles in the tree, starting with the root node: void Store(Rectangle rect) { if(I have children nodes) { bool storedInChild = false; foreach(Node childNode in nodes) ...


6

I'm not really good at fabricating N- statements, but the minimum search times for an object at child[0] of every child[0] should be close to the same +- a dimension. If the object falls at child[4] of every child[4] the calculation for the octtree could be as much as N^2(?) longer. Since you don't specify how/why the tree is being used, it's hard to give a ...


6

Lærne's suggestions are great, but I would also suggest a dynamic bounding volume tree of AABBs. Conceptually the dynamic bounding volume tree keeps a balanced tree of nodes which can be queried at any time for near elements by passing in an AABB and retrieving an overlapping pair. The tree is not rebuilt every frame. Instead each node's AABB is slightly ...


5

You can read a more detailed answer here:Which is the best LOD method for planet rendering? I'm doing exactly something similar for my computer science degree thesis and attacked the same problem. The problem you have is jitter, and you will find another one more called z-fighting. Jitter: Most of today’s GPUs support only 32-bit floating-point values, ...


5

Usually you'll just have a single quad tree. Often times this would be better as the different layers of collisions can be quite complex and numerous. Also I don't think a bottleneck has ever been that too many potential pairs are culled by layering instead of being implicitly culled by separating data structures. It's hard to make something faster and ...


4

Just like with any software architecture question, the short answer is "It depends..." Where do I put that quadtree? Any auxiliary data structures needed by one system only should be part of that system. So if that quadtree is only used by the CollisionSystem, then you can make it part of the system. But if that quadtree is used by many different ...


4

Update I have wrote Theraot.ECS inspired by Fastest way to look up an entity with a set of components?. However this answer motivated me to allow to specify custom containers for particular types. It would be necesary to provide an adapter to the interface IIntKeyCollection<TValue> exposed in the project. Which would in theory allow the ECS to use a ...


3

I'm doing research in autonomous navigation for robotics, and this is a familiar problem. The real world analogy is you have two vehicles (a robotic motorcycle and a robotic tank) that have to decide on going through a narrow alleyway or not. Dimensions and positions are known by whatever means (radar, LIDAR, maps, GPS, etc)--how do you program such a ...


3

As already stated in others comments I think you might be using the quadtree concept to solve the wrong problem. I spend most of my time managing massive amounts of data working with voxels and even I don't touch quad trees for anything related to generating my world data. The purpose of the quad tree is to help manage and work with your rendered world so ...


3

It's a quad tree so when you split it into 4 parts any entities belonging to the parent get divided between the children based on position.


2

I would add this as a comment in response to @Nathan Reed's answer, except it's too big to be a comment, and is perhaps in any case worthy of being a separate answer. We were doing precisely what was proposed in his answer, and in fact have comment in the source linking to this page. For the most part, it has worked extremely well, except that once every ...


2

It's not a full answer, but it's too long for a comment... From your question I presume you want to use a LOD system (geomipmap approach) and you're creating your mesh by cube subdivision, so why not to think about a LOD during both stages - mesh creation and rendering? You start from just a 6 planes, so it's really easy to tell which sides are connected. ...


2

Walk the quadtree recursively when saving: save_node(node n) { write_bbox(n.bbox) write_int(n.objects.length) for (object in n.objects) { write_object(object) } write_int(n.children.length) for (child in n.children) { save_node(child) } } save_node(quadtree.root) Read back the same way: read_node() { node n ...


2

After reading a lot about this over the years, the advice that I see the most is to avoid doing it at all. It might not feel like good advice at first, but the arguments are that the performance gains you get for making this kind of structure is totally overshadowed by the potential performance gain you would get by simply chopping your model into cubes at ...


2

If you make separate binary trees for different objects, you will destroy the whole purpose of the tree: logarithmic complexity. Say you sort your objects into different trees. Each tree's contents and ordering will have no bearing on collisions with items in other trees. You will be back to testing each item from one tree against each item from another. ...


2

Of course, if resources are scarce and speed critical, said depth should be determined through benchmarking, but here are some maths to help cornering it. Let us assume that we are dealing with n object for which we have to trace collisions, that their repartition in the world is uniform and they are small enough that no matter how fine the grid is, overlap ...


2

For performance reasons I never frustum cull on the CPU -- I just distance cull as part of the LOD determination so I'm rendering everything in front of and behind the camera (let the GPU do the culling for the frustum) so that when the player turns there is no potential lag while new terrain chunks are activated or (even worse) sent to the gpu. I also don't ...


2

It depends how you implement double dispatching how elegant it is. You are effectively trying to dispatch to a function that's able to handle collision between types X and Y and execute function for that type pair. This is basically a matrix lookup and you could implement it by registering collision functions to this matrix. Let say your type-ID is 0-based ...


2

In this case you have to decide what to do. In most cases, this is done automatically for you because your sorting is based upon <=, >=, < or > where you definitely get an answer, either true or false, so it really depends which type of comparison you use. For example if(x < middle_of_this_quad) add_to_left_subtree else ...


2

There are multiple solutions to this problem. You can place the object in the smallest node which fully contains it. You can split its edges among multiple nodes and tag them with which object they belong to. Another solution is to use a "loose" quadtree. The idea with a loose quadtree is that the nodes are larger than in a normal quadtree, such that they ...


2

GDX doesn't support it directly. A version for LibGDX https://github.com/alwex/QuadTree


2

Implementing LOD subdivision on terrain is quite complicated, I rather recommend to use a library or something. But if you prefer to learn the hard way here are the principal steps you need to do: First, unlike your assumption, you do not start with 6 meshes like the most zoomed out version, but you define your geometry at highest resolution (most zoomed in ...


2

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with. The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer ...


2

There are 2 ways to deal with boxes straddling a boundary. One is to keep the box in the vector of the node where it straddles the boundary and don't push it down. The other is to add the box to all subtrees it overlaps with. For the second option all you need to do is change first if in insert to: //Check if box overlaps boundary if (!mo_boundry.Overlaps(...


2

I can't recommend a structure that actually implements what you're asking for, but it definitely won't work like a quad tree. It may not be a tree at all and it might not even exist... A quad tree has a tree structure because each node represents the node above it divided into four quadrants. At any level these four quadrants cover all of the space covered ...


2

As explained in the answer by Romen, there aren't many applicable data structures which are not based on rectangles. But there are a couple other optimizations you can do for circle-circle collisions which could reduce your demand for a more optimized data-structure. Compare the square of the distance with the square of the radius. If you want to check if a ...


1

As I have done what you are trying to do, ala quad tree and splitting into chunks. A couple of things. For optimal performance, I have found that keep the vertex list as one buffer. Do your quadtree split on the indices. What this does is your indices dont have to be rebuilt and reflect the true index of the vertex in your mega buffer. NOW, if you ...


1

you could something like the following, that would at least limit the enemy-ray tests to quads that only intersect the line: void process_sub_quads(Quad q,Ray r) { for(int sq=0; sq<4; ++sq) { // query sub quads Quad sub_quad = q.sub_quad(sq) if(ray_box_intersection(r,sub_quad)) { if(sub_quad == lowest_quad) { ...


1

A k-d tree like Philipp suggested would likely be a good solution, but certainly more complicated to implement. Your proposed solution should work fine, but you may need to be clever with how you store your child indices/pointers, if your goal is to save space. If I were trying to solve this, given the limited information I have about your problem, I would ...


Only top voted, non community-wiki answers of a minimum length are eligible