Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Quadtree terrain principle: questions on the principle of work and optimization

Discussion in 'World Building' started by Lesnikus5, Sep 2, 2019.

  1. Lesnikus5

    Lesnikus5

    Joined:
    May 20, 2016
    Posts:
    131
    Hello.

    I want to create a quadtree terrain. The landscape consists of square tiles-plains 10x10 m in size, more distant tiles are 20x20, 40x40, etc. When the camera moves, they must be rebuilt so that the camera is always in the center of the most detailed LOD.

    As I understand it, the usual way to build a quadtree is to create a recursive loop to check the distance from the center of the tile to the camera deeper in the tile tree, breaking or merging tiles of different LOD levels. That is, the cycle measures the distance from the camera to each tile. If the distance is less than the specified one, the tile will spawn 4 child tiles of a smaller size. Each of childs checks its distance to the camera and the cycle repeats.

    1) My first guess is that the larger parent mesh tile is removed, but the parent continues to check his distance to the camera. If distance increases back, the daughter tiles will be destroyed and everything will return to its original form. If you remove the parent after the spawn of the children, there will be confusion about which children should be combined to create the parent, so it is easier to check this in the parent without deleting it. It is right?

    2) If you check the distance to the camera for EVERY tile, this is a lot of extra work. Imagine we have such a landscape:
    LOD0 (view diameter = 8 tiles): 8 * 8 = 64 tiles,
    LOD1 (view radius = 4 tiles): 4 * 4 * 9 - (LOD0 64/4) = 128 tiles
    128 + 64 = 192 tiles. And these are only 2 LOD levels, not the desired 10.
    How to optimize this check? Checking the distance of each tile is crazy!

    3) Do not destroy and create tiles every time. This is bad for performance. It is necessary to use the same objects, rearranging them from one place to another. But if each tile exists as if by itself, not knowing about the existence of other tiles, how does it know where to get the missing tiles?

    4) Are there any other quadtree methods?

    If someone helps, thank you in advance!