• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
CC Ricers

Quadtree dilemma

13 posts in this topic

I'm considering situations where the object may be small, but it is in the dead center of the world or contained in more than one top-level node. If I were to give these objects the largest it will completely fit in, it would have to be the root node. Should I be listing one node per object, or should I list multiple child nodes per object for a tighter fit? This picture illustrates a case I'm trying to figure out.

 

2HezD.png

 

The blue outline represents the camera's view. I might be thinking that for a one-node-per-object approach, the root node would have too many objects to render. In this example the camera is only in one node, but the worst case scenario is that it draws everything from the root node, because for some objects the root node is the smallest one it can completely fit in, removing all the efficiency of the rendering.

Edited by CC Ricers
0

Share this post


Link to post
Share on other sites

In most cases, this is okay, just draw all 4.  These days it's probably quicker to just draw all the leaves you can see at your chosen quadtree depth.  If you've go so many objects that a quadtree doesn't work, then it's not really the quadtree that isn't working, it just becomes less applicable to your application.

 

I think the small object that spans all 4 leaves should probably exist in all 4 leaves but when you render it, just set a 'alreadyRendered' flag to make sure you don't render it 4 times.

0

Share this post


Link to post
Share on other sites

That isn’t how the tree is meant to be traversed for rendering.  The camera’s frustum isn’t inside any of the nodes.
It starts at the top node and checks for overlap into child nodes before going into them, recursively (an explicit stack helps here).

bool CFrustum::GatherObjects( const CFrustum &, std::vector<CNodeObjects *> & );

The frustum isn’t registered inside the quad-tree, it is just passed in when objects inside it are to be gathered.

You are thinking about collision detection. That is when both objects live inside the tree there are certain optimizations you can do based on the depth of each object (allowing you to cap how high up the tree you have to go).

Frustum culling is not done this way.

Firstly the frustum always starts at the root node and goes recursively into children it overlaps.
Secondly, on each level, the children of those nodes are tested individually against the frustum using frustum <-> AABB testing.

So you aren’t going to have objects being added multiple times or lose optimization by having to traverse too close to the root node just because of one small object sitting in the middle, or have the same thing cause you to render tons more objects than you otherwise would.


L. Spiro

Edited by L. Spiro
2

Share this post


Link to post
Share on other sites

You should also look into loose quadtrees.  The benefit is that you can find exactly what level of the tree and what node in that level an object belongs by looking at its bounding center and bounding radius.

0

Share this post


Link to post
Share on other sites
For static data you can use an R-tree, which allows nodes to be anywhere within the parent and in any number.

As it removes the restrictions of a quad tree, it can be more optimal for a given set of data. Because the bounding boxes are fitted around the contents, overlap is not a problem.

However, it is difficult to maintain in an optimal form if there are many insertions and deletions. It's best to build the whole tree from a known set of data.
0

Share this post


Link to post
Share on other sites

L. Spiro, since the frustum isn't registered by the quad tree, and the tree nodes are used by the frustum to check for overlap before getting the objects, does this mean that objects can have a one-to-many relationship with the nodes?

0

Share this post


Link to post
Share on other sites

One-to-many which way?  One node to many objects?  Yes.  One object to many nodes?  No.

After the frustum is found to overlap a node of the tree, all the objects on that node are checked against the frustum.  Standard quad-tree rules apply.  Each node can have many objects and each object must be contained entirely inside only one node, which should be the smallest node that can contain the object entirely.

 

 

L. Spiro

1

Share this post


Link to post
Share on other sites
I've never actually implemented a quadtree, but as I understand it, the trick is that it's recursive... most objects will be several levels down, but objects that are sitting on boundaries have to be higher up. So yeah, in your picture, those objects would indeed go in the root node because the very first division has boundary lines there. But keep in mind that those objects are very large relative to the world size. Most could only fit in a first or second division cell at most anyway.

For collision detection, I usually use a fixed-size grid, where objects can belong to multiple cells, and use timestamps to avoid testing pairs twice. Could use that in quadtrees as well, I think. Subdivide until you're a minimum of maybe 3 levels deep, and if you're sitting on any boundaries, just link into to all the cells. Then at the start of the frame, increment a global timestamp value (just an int), and when you render each object, set its timestamp equal to the global, or reject it if it was already equal (i.e. had been drawn this frame from a different cell).

Of course, it's questionable which is better performance-wise... depends on the world size and number of objects, I guess. In most cases, it would probably be better to just let a few things go in the root and first division nodes, to reduce the amount of list management. You can still reject them early by testing their bounding sphere/box against the frustum. Edited by DekuTree64
1

Share this post


Link to post
Share on other sites
In some form they need to because if you have the case above where an object sits across the corner between four (or across the edge of two) boxes and one of the boxes is out of the frustum, you'll still need to draw the object.
0

Share this post


Link to post
Share on other sites

RobMaddison, that is the edge case (no pun intended) that I most want to resolve. Those objects that straddle across the borders of two or more level-one nodes, however small they may be, meaning that the largest single node they can fit is in the root node.

 

One-to-many which way?  One node to many objects?  Yes.  One object to many nodes?  No.

After the frustum is found to overlap a node of the tree, all the objects on that node are checked against the frustum.  Standard quad-tree rules apply.  Each node can have many objects and each object must be contained entirely inside only one node, which should be the smallest node that can contain the object entirely.

 

 

L. Spiro

 

This is what I have assumed all along. So how does one deal with worst case scenario in which the majority of the objects can only fit properly in the root node of the tree? I would think that this would cause all objects at the root to be drawn, regardless of their visibility.


Wait, is this where frustum culling kicks in? I think I see how this works now. The worst case isn't drawing a large amount of objects from the root, it's culling all those objects, and then drawing just the ones inside the frustum.

Edited by CC Ricers
0

Share this post


Link to post
Share on other sites
How many objects are you likely to have that can move freely between nodes?

You can either have all objects at the leaf nodes and allow them to belong to up to 4 nodes, or only allow them to belong to one and if they happen to be spanning nodes, then move them up the tree until they are enclosed by only one. If your quadtree is only 2 levels deep (i.e.the root node and its children) then that will mean the objects will go into the root, but I would imagine that if your camera can move around the whole scene and it's fairly sizeable, you'd want far more levels.

If your game area is quite big and your objects are small, then the chances of them straddling nodes is pretty minimal. It all depends on how busy your scene is and how much depth you have in your quadtree. You can set this up fairly painlessly and just do some tests to see which way works best for you...
0

Share this post


Link to post
Share on other sites
Wait, is this where frustum culling kicks in? I think I see how this works now. The worst case isn't drawing a large amount of objects from the root, it's culling all those objects, and then drawing just the ones inside the frustum.
Yes, the ideal situation is that you are able to split your world into 'manageable' chunks and only draw what's in that 'conceptual' chunk if any part of it is in the frustum.

The quadtree concept works like this:

Check if the root node 'box' is in the camera frustum - if it isn't, then you draw nothing and rendering is complete.

If any part of it is in the frustum, you then look at it's 4 children recursively and check to see if any part of them are in the frustum, you then continue down the tree until you've either reached the smallest box (the leaf node), in which case you draw all of the objects within it, or just ignore it if it's empty.

You can quickly see that large parts of the game world can be ignored very quickly. The whole notion is "if I can't see a box on the screen, then ill never be able to see any of its 4 children (this happens recursively), and hence any of the objects that live in that box."

A quick side note that someone pointed out the other day on a similar topic, if a quad node at any particular level is contained entirely within the frustum, you know that all its children will also be in the frustum so you can stop drilling down and draw everything below that node.
0

Share this post


Link to post
Share on other sites
Wait, is this where frustum culling kicks in? I think I see how this works now. The worst case isn't drawing a large amount of objects from the root, it's culling all those objects, and then drawing just the ones inside the frustum.
Now you’ve got it.


L. Spiro
0

Share this post


Link to post
Share on other sites
Wait, is this where frustum culling kicks in? I think I see how this works now. The worst case isn't drawing a large amount of objects from the root, it's culling all those objects, and then drawing just the ones inside the frustum.
Now you’ve got it.


L. Spiro

 

Great, I can get started with populating the tree. I think the worst case won't be as bad as I thought. On older hardware, I've culled around 10,000 objects by brute force before noticing any slowdown.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0