Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
November 26, 2020
arrowPress Releases







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

QuadTree in Unity

by Videep Mishraa on 10/27/20 10:37:00 am

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

 

First of all, I wanted to share why I created such a tree. My objective was very simple : to partition the space as per the mesh density based off vertex data. Once I know which are denser areas in a given area, I can have more control over it. Refer to the following image which shows how a particular scene can be divided into quad based structure:

Image for post

Quadtree Structure and Class

Quadtree : A quadtree is a tree data structure in which each internal node has exactly four children.

Now we have a starting point where we know that, if we start off with the root node, it would contain exactly 4 children nodes. For each child node, there will be 4 child nodes too.

Infinite nodes? If each node were to have 4 child nodes, then yes, the node structure will be infinite. We will look at how to control this in further sections.

The pseudo-structure of a quadtree can be as simple as what you can see in the image. This is all you need to create a tree structure with branches and leaves.

I have used the class-name as “Quad” to make it easier to understand. Lets see the various properties:

Image for post

Bounds : The area that the quad consists of. Each point will be checked if it lies in the bounds of the quad or not.

Children : If the number of data in a specific quad overflows, it would lead to the quad being subdivided into smaller sections. As explained earlier, each node will have 4 child nodes in a “Quadtree structure”.

MaxPoints : This is the number of maximum data this node can retain. If it exceeds, the quad will be subdivided.

Points : The actual data or just a simple counter to cross-check against the MaxPoints.While that’s all for the properties, lets take a look at the methods:

CreateQuad : This creates a quad object or a node by dividing the parent’s bounds by 4. For every quadrant that you create, a CreateQuad method will be called as per its own specific bounds. Like you see in the image below, the biggest quad is divided into 4 smaller out of which 3 are empty. 1 is then divided into smaller and smaller and smaller quads.

Image for post

Insert : This method is called for every point to check if the point lies in the specific quad or not. If the point lies in the quad or inside the bounds of the quad, then the data is added to the specific node. To further detail out, once the point is added to “Points” property, a check is performed if the number of “Points” are less than “MaxPoints”. Based on the result, the quad is further subdivided.

Quick optimization: Always check first if the point lies in the quad or not and if not, perform an early return. This will save lot of calculations.

Quad : This is the constructor of the class. As simple as it can be, just initializes the class and properties if required.

Subdivide : This is the function which is directly called if the “Points” outrun the “MaxPoints” count. This calls the “CreateQuad” function 4 times to create 4 different quads by subdividing the current quad’s area/bounds into 4 equal parts.

What next?

Once we have the class, we need to implement and start filling up the data. As we know that we need to have a root node. The user here has a choice to implement this in various ways. User can dynamically create multiple quadtrees at runtime or mark a whole area and do the quadtree partitioning. To make this very simple, I have taken up a 3d scene and the extents of the same. Then I created a “RootNode” and provided the bounds for the same.

As you can see in the image below, I have marked the root node and given a bounds of 500x500. This is huge looking at the 3d data I have, but makes it simpler to understand in this article:

Image for post

Sorting The Data

For this article, the data is the mesh. Hence, for each vertex in the scene, we will call the “Insert” method of the RootNode. If the root contains the vertex position, then it will add the point to its data, else will ignore it (here the dynamic creation of quads will be more effective).

If the number of points exceed, the root node will be subdivided into 4 parts and for-each the same “Insert” method will be called. Remember that each quad has the Insert function! The following image will help you understand the quads that were created:

Image for post

I have deliberately left a lot of free space so that we can see that where there is no or less data, the bounds of the quads are larger. This proves, that if the data overflows, then and only then, the quad will be subdivided. Here, I have kept the limit of 250 vertices per quad. We can clearly see the area highlighted in blue has more vertex, hence its further subdivided, whereas the other area has larger quads:

Image for post

Quick Tip : In unity the rectangle class takes x and y parameters only. Hence, for a 3d point, we can take only 2 axis. Here I have taken X and Z axis.

Conclusion

So here we conclude with the creation and implementation of the QuadTree data structure. We have seen the implementation and the uses also. Apart from what I have discussed, this can be used at a lot of places. Ideally terrain generation is the best example that can be given, where based on the distance of the player, the quads are subdivided to render higher detail. Those away from the user will be showing less data.

Hope this simplified version helps you to understand and implement your own Quadtree structure.


Related Jobs

Hit Factor Inc
Hit Factor Inc — San Diego, California, United States
[11.25.20]

Game Studio Engineering Lead - Remote
Square Enix Co., Ltd.
Square Enix Co., Ltd. — Tokyo, Japan
[11.24.20]

Experienced Game Developer
Deep Silver Volition
Deep Silver Volition — Champaign, Illinois, United States
[11.24.20]

Senior Technical Designer
Purdue University
Purdue University — West Lafayette, Indiana, United States
[11.24.20]

Assistant Professor in Game Design and Development





Loading Comments

loader image