Questions tagged [quadtree]
The quadtree tag has no summary.
62 questions
0
votes
0
answers
98
views
Is there any benefit of combing Instance Meshing with quadtrees LoD?
I would like to know if there would be any benefit of combing Instance Meshing with quadtrees LoD? Besides the obvious performance improvement of only having one mesh
I wanted to try and implement ...
- 85
0
votes
1
answer
272
views
Quadtree UV mapping texture
I need help coming up with dynamic uv values (general formula) so that my texture looks continuous through all levels of my quadtree. level 0-1 works perfectly, level 1 subdivision looks great. but ...
- 85
0
votes
0
answers
55
views
How to separate player state on shared object?
I'm new to game dev and I'm learning about quadtrees for planet rendering. I'm curious on how do I separate player state with quadtrees. For example I have a ship A that's getting close to a planet, ...
- 3
0
votes
1
answer
189
views
What algorithm is best for finding non-static nearest neighbors on a 2d grid?
A bottleneck I've hit is querying Quadtrees for finding nearby locations. It's much faster than comparing each location, but I'd like to find faster methods that work for moving locations. Profiles ...
0
votes
0
answers
367
views
Can inserting/removing one point in a quadtree or octree cause multiple splits/collapses?
I was reading Robert Nystrom's Game Programming Patterns website and, in the section about spatial partitioning, particularly in the section on quadtrees, he mentions:
Objects can be added ...
- 157
0
votes
1
answer
769
views
Understanding this terrain intersection algorithm
I was looking for a fast way to get a ray intersection point of a terrain defined by a heightmap and I stumbled upon this: https://publications.lib.chalmers.se/records/fulltext/250170/250170.pdf
At ...
- 15
1
vote
1
answer
639
views
Calculating distance in procedurally generated mesh LOD system
I'm creating a procedurally generated planet mesh based on quadtree splitting to support LOD system. I cannot find any relevant info how can I calculate distance between the camera and LOD chunks.
I ...
- 57
1
vote
2
answers
2k
views
Optimizing a quadtree for circles and circular queries
I'm developing a 2D ant simulation in JavaScript. I'd like to implement a quadtree to store the positions of ants and other markers. I approximate all of these entities as circles, and I'm only ...
- 19
5
votes
1
answer
3k
views
Quadtree for AABB collision boxes
I have a whole bunch of entities constantly being processed and testing for collisions. I've tried to optimize this by stopping certain entity types from checking each other, dead entities not being ...
- 87
0
votes
2
answers
874
views
How to handle objects at the edges of spatial partition cells?
A lot of games store object positions as floats and have a closed ball for the game area (eg. a rectangle and objects are allowed to have position coordinates on all 4 edges).
However, this becomes ...
- 113
6
votes
2
answers
2k
views
Entity Component System: where do I put containers?
I'm pretty new when it comes to the whole Entity Component System structure and I got some questions I just can't wrap my head around.
I know that for example collisions, you'd have a ...
- 625
1
vote
1
answer
145
views
Unexpected output from the merging of a quadtree, when that data is converted to Box2D fixtures
I've been staring at this code trying to troubleshoot this for the past 3 days, but I seem to have gone Code Blind. I KNOW the issue is stupidly simple, but I just can't crack the problem.
I'm using ...
- 71
1
vote
0
answers
264
views
How should a 3D map be stored?
I have an array of 3d vertices, Vertex3D[][] ground;
so for each element in the array, I have an array of three 3D vertices, a triangle.
But this means I cannot ...
1
vote
0
answers
51
views
How to track/identify amorphous blobs in 2D or 3D space
In doing HTML/DOM work, you are working with concrete nodes which you can visibly touch and have a defined shape and boundary.
What I'm wondering though is like with a cloud like structure, or like a ...
- 177
0
votes
0
answers
114
views
Quadtree having ownership of entities, worth it?
Typically, you would have a list of entities stored somewhere, and you'd use quadtree when you need some collision testing between entities for example, by inserting all of the entities and generating ...
- 1
1
vote
0
answers
234
views
Is Quadtree Terrain Decimation applicable today?
It all started from that page.
https://www.gamasutra.com/view/feature/131841/continuous_lod_terrain_meshing_.php?print=1
I didn't quite got what it was all about, so I've looked at this.
https://www....
user120910
1
vote
0
answers
560
views
Chunked QuadTree creation & handling
I am new to LOD-based techniques so please be lenient with your comments about my naive questions.
Preface:
My aim is a simple terrain renderer (preferred C++ and OGL) that is to load a height-map (...
- 11
5
votes
1
answer
2k
views
Quad sphere subdivision algorithm
I like to generate some planets like Kerbal Space Program does. By some videos of the developers I know that they use a quadsphere, which consists of six “entities” as a minimum. These are all plane ...
- 131
0
votes
1
answer
599
views
How can I split my terrain into quads so that each quad would have a renderable vertex/index buffer? (DirectX11, C++)
I am creating a quad tree to store my terrain in chunks and currently have the implementation working to an extent.
I am currently starting with a grid of triangle pairs that make squares and ...
- 155
0
votes
1
answer
160
views
Using Lazer with a Quadtree
I have a quadtree implementation that works well with what I need for handling collisions between enemies, projectiles, and heroes.
However, most of these types of entities are pointbased, with ...
- 35
0
votes
2
answers
1k
views
Is there an existing Quadtree implementation in libGDX?
I've seen a lot of sites that recommends to use Quadtree for splitting the array by levels and nodes for a better performance for example in CollisionSystem there's ...
- 501
0
votes
2
answers
535
views
Drawbacks to an Octree and Quadtree hybrid?
I've implemented an octree to divide 3D space that contains several objects.
I've noticed in certain octree nodes I could use more refinement in some axis, but splitting the node into 8 children is a ...
- 13
2
votes
2
answers
681
views
Where should I store an object? - QuadTree
I'm designing a QuadTree to scene partitioning, I've read theory and seen some code examples.
When a node has more than 4 objects, it will be splitted into 4 sub-nodes and its objects will be put ...
- 23
0
votes
1
answer
254
views
QuadTree nice design for nodes
I'm using c++ and have some problems with the QuadTree design.
I have some components which are not related to the QuadTree directly. These components are eg. RenderableMesh, PointLight, etc. Some of ...
- 385
2
votes
1
answer
691
views
Quadtree splitting
A quadtree has limit on number of item in each nodes. Suppose a node has already has same number of item as the limit. If I add another item on same node the node should split and new item should be ...
- 143
1
vote
1
answer
441
views
QuadTree Checking Collision With Different Levels of Nodes
I am making a QuadTree for a 2D Platformer. Researched on it and I managed to make a pretty good one where each node stores its 4 SubNode and there's a MAX_OBJECTS for each Node and MAX_LEVELS which ...
1
vote
2
answers
208
views
How to handle (0,0) in 2D game quad tree?
I am not sure how to handle situation when out objects (player) is in center (0,0) point of game which is crossing of four quads. How to handle that case?
This image shows problem:
Red rectangle is ...
1
vote
1
answer
889
views
Efficient container(s) for units in an 2D RTS game
As the title says, I'm toying around with developing a 2D space RTS game. All of my units are spaceships that basically just shoot at one another, but they have to do a variety of other things as well:...
- 11
5
votes
1
answer
898
views
QuadTree-based pathfinding for a volume body
I want to make a game where a player follows a mouse pointer. The game is not tile-based. I use quadtree for a collision detection and everything works fine. But now I want to develop a player ...
- 163
0
votes
1
answer
3k
views
Should I use octree or quadtree for my spacial data structures? [closed]
I would like to know the advantages and disadvantages of using octree or quadtree for spacial data structures? In a 3d gaming setting would you ever need more than 4 children nodes? Does it take ...
- 554
2
votes
2
answers
2k
views
Using QuadTree for Procedural Generation
so I've been trying to start a new project that focuses on procedural room generation similar to what is seen in Binding of Isaac.
I plan to have the code use a QuadTree to help determine where ...
- 255
14
votes
2
answers
16k
views
Fully dynamic KD-Tree vs. Quadtree?
Working on my game, I'm at the point where I need to track all of the units in the world so that I can do nearest-neighbor checks for combat. This is an RTS-like game, with potentially thousands of ...
- 634
2
votes
1
answer
3k
views
Quadtree vs multiple resolution grids for terrain rendering
I have been thinking about quad trees with regards to terrain rendering.
From my understanding the basic functionality of quadtree terrain rendering is to frustum cull the terrain in such a manner:
...
- 133
2
votes
1
answer
251
views
Pair collision detection on quadtree
I'm planning to use a quadtree for optimizing collision detection. But this quadtree can handle only one type of objects (so I used a base class for my objects).
If I use double dispatch after two ...
- 393
1
vote
1
answer
1k
views
How do I construct the planes for my camera's frustum?
I'm trying to get a handle on frustum culling, but I'm not quite there yet.
I have a camera in three-dimensional space
...
- 123
4
votes
2
answers
2k
views
How should I choose quadtree depth?
I'm using a quadtree to prune collision detection pairs in a 2d world. How should I choose to what depth said quadtree is calculated?
The world is made mostly of moving objects1, so the cost of ...
- 161
2
votes
1
answer
686
views
Dynamic Quad/Oct Trees
I've recently discovered the power of Quadtrees and Octrees and their role in culling/LOD applications, however I've been pondering on the implementations for a Dynamic Quad/Oct Tree.
Such tree would ...
- 242
6
votes
2
answers
1k
views
How do I simplify terrain with tunnels or overhangs?
I'm attempting to store vertex data in a quadtree with C++, such that far-away vertices can be combined to simplify the object and speed up rendering.
This works well with a reasonably flat mesh, but ...
- 242
1
vote
0
answers
425
views
Overlap detection, nearest neighbors
I'm trying to get something similar to the Nearest Neightbor Problem, except I only want neighbors with radius overlapping a radius, and all of them.
I'll explain my problem before explaining what I ...
- 322
18
votes
1
answer
12k
views
When is a quadtree preferable over spatial hashing?
I'm making a 2d platformer with lots of objects at the same time. They're all AABB collision detected. I first tried a quadtree to decrease the number of of objects to check, tried a few different ...
- 283
5
votes
1
answer
2k
views
Planet sized quadtree terrain precision
I've been working on a planet sized and shaped terrain lib for a while (In webgl and Unity) and have a couple of working implementations [Quadtree cubesphere and circular clipmaps].
But both of them ...
- 353
1
vote
1
answer
1k
views
Storing a Quadtree
I have a quadtree which organize my terrain chunks (heightmap) and all the static objects of my 3D world. I use Axially Aligned Bounding Box as a volume for each node of the quadtree. Due to the ...
- 113
2
votes
0
answers
151
views
Framebuffer Heightmap Performance Problems
I am using a framebuffer to procedurally create heightmaps with perlin noise in GLSL shaders. There are two main problems that I am experiencing with this. I have a quadtree for the terrain and in the ...
- 622
13
votes
1
answer
7k
views
How Do Shapes (Rectangles) Work in Quad Trees?
I've been told that a quad tree is the ideal data structure for my game, but I'm having trouble understanding how exactly shapes work within quad trees.
I'm doing this in JavaScript, but I think ...
- 307
5
votes
2
answers
2k
views
Calculating adjacent quads on a quad sphere
I've been experimenting with generating a quad sphere. This sphere subdivides into a quadtree structure. Eventually I'm going to be applying some simplex noise to the vertices of each face to create a ...
- 906
0
votes
1
answer
526
views
Collision Detection: Simulation Inexplicably Slowing Down/How To Efficiently Calculate Extremes In Each Dimension
BACKGROUND: As discussed here: Fast 2D collision detection in an unbounded space I am working on a collision detection algorithm for a simulation. The catch that makes this case unique is that the ...
- 423
5
votes
2
answers
545
views
One or multiple quadtrees?
Let's say we have 100 objects of each of few types, that may have an effect if they collide with one other type, or they may not.
Is it better to have quadtrees for each object type, and check ...
- 393
7
votes
3
answers
4k
views
How to deal with objects placed in the root nodes of a quad tree?
I've implemented a quad tree where points and axis aligned rectangles can be put.
It works fine, except for one issue that I'll try to describe.
When you put a rectangle in the tree and this rectangle ...
user27061
1
vote
1
answer
1k
views
Efficient collision detection using quadtrees
I recently started to learn Java and OpenGL with the LWJGL and I'm making some simple games to get started.
At first, when I was going to implement collision detection I immediately thought there had ...
- 480
4
votes
1
answer
13k
views
C++ How to implement a spatial hash (for a 2d Game)
I feel kind of silly for asking this question, but are there examples or tutorials on how to implement a spatial hash (grid/cell-based partitioning), preferably in C++?
I'm stuck and I have no idea ...
- 205