12

1 : I can't understand at which point down the Chunked LOD pipeline that the mesh gets split into chunks. Is this during the initial mesh generation, or is there a separate algorithm which does this. It does not matter. For example, you can integrate the chunking into your mesh generation algorithm. You can even do this dynamically, so that lower levels are ...


12

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 ...


10

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) ...


5

To do a basic spatial hash (slightly more complicated forms exist), you need to generate a broad discrete grid location for any game location. This might be as easy as converting float positions to ints or taking int positions and dividing them all by 64 or some other constant. The idea there is to create a single discrete location most nearby objects will ...


5

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 ...


4

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, ...


4

What would be a good approach to let my character move? Should I have a player system that updates the Player's position or velocity? Or should I let it set a state & let another system update the movements of entities based on their velocities and their current state? Leaving the option open that I could move a character by clicking somewhere? I would ...


4

I don't understand why do you add the green ones? If you simply test in each step if the red overlaps with the child (simple test), it would look like this: Let's say your rectangle red is located in root and you want to retrieve the neighbours and put them into result child = root procedure populateResult if red collides with child add all ...


4

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

If storing extended objects (regions) in a quadtree, the object should be referenced from all the leaf nodes it touches. I wouldn't try to find the least common ancestor and store it there, because then e.g. a small object that happens to cross a high-level boundary will end up in a very high node, and must be tested against everything else in that large, ...


4

You must store it in the smallest node that completely contains it- even if this exceeds capacity (use a resizable container).


4

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 ...


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

Terminology first: I refer to quadtree quads as "nodes" within the quadtree structure, and I refer to flat array elements as "cells". Every individual quad, at each subdivision depth, should have it's own wireframe view component. You should also have a flat 2D array that represents all of the quadtree leaf (i.e. deepest level) nodes in your entire root ...


3

Here are a few links you may find useful; General Linking Page, Hugues Hoppe These should provide you with a huge amount of information so hopefully you can find something in there to get you going. Quad-trees and oct-trees are references to particular methods of spatially partitioning the world into smaller and easier to handle chunks. Because terrain ...


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

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

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

Without knowing the details of your game, I'd say: Keep It Simple. Updating the quadtree whenever something moves is a perfectly acceptable solution. I mention in my answer to a similar question that the simplest way to update the quadtree is to remove the item, then re-add it, but this can cause unnecessary overhead. The way I've done it in the past is like ...


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 easy to debug recursive structures, particularly when you're relying on a potentially bugged renderer to inform you. So the question is, Is this a bug in your rendering code, or somewhere else? Suggestions: Ensure that when a larger, parent quad subdivides, you stop rendering it. In other words, render only what are considered to be its leaves. ...


2

If you re-implement your quadtree to insert objects on borders into all siblings of that border, then the result you'll get is exactly the result you are trying to achieve (with an overhead of 2n per object where n is the number of borders the straddling object is in contact with.)


2

I'd go with some sort of notification/event system to keep the quadtree updated when an object moves. This would require telling the quadtree the previous location of the object (since that's where it was indexed) and the updated location, so the quadtree can check if the object should be reindexed.


2

I fixed the problem... Here is the revised code for the method "create()" if anyone is interested, Thanks for the time: public static void create(Quad quad, int i, int ii){ quad.children = true; i*=2; ii*=2; Vector3f parent = new Vector3f(i*quad.width/2, 0, ii*quad.width/2); System.out.println(parent + " "+ toString(quad)); if(quads =...


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

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

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

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 ...


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