3D.ru

Пытаюсь реализовать quadtree terrain. Встречал упоминания про рекурсивный метод, когда проверяется расстояние от камеры до плитки и если расстояние меньше заданного, плитка удаляется, вместо нее создаются 4 плитки меньшего размера и цикл для них повторяется. При этом каждая плитка независима, т.е. нет какого-то единого массива плиток, каждая работает сама по себе. Выглядит просто.

Я никак не могу понять, как узнать, какие плитки следует разбить на 4 дочерних плитки меньшего размера? Проверять расстояние до камеры ДЛЯ КАЖДОЙ плитки? Если у нас большой ландшафт, это могут быть тысячи проверок за один CheckDistance() ! Это безумное расточительство! Значит, есть способ как-то оптимизировать процесс, проверять не все плитки, а только нужные или что-то типа этого.

Помогите пожалуйста разобраться.

Инженер писал(а):Пытаюсь реализовать quadtree terrain. Встречал упоминания про рекурсивный метод, когда проверяется расстояние от камеры до плитки и если расстояние меньше заданного, плитка удаляется, вместо нее создаются 4 плитки меньшего размера и цикл для них повторяется. При этом каждая плитка независима, т.е. нет какого-то единого массива плиток, каждая работает сама по себе. Выглядит просто.

Я никак не могу понять, как узнать, какие плитки следует разбить на 4 дочерних плитки меньшего размера? Проверять расстояние до камеры ДЛЯ КАЖДОЙ плитки? Если у нас большой ландшафт, это могут быть тысячи проверок за один CheckDistance() ! Это безумное расточительство! Значит, есть способ как-то оптимизировать процесс, проверять не все плитки, а только нужные или что-то типа этого.

Помогите пожалуйста разобраться.

По хорошему, нужно проверять не дистанцию до узлов Quad Tree, а площадь которую этот узел занимает на экране, для этого переводишь все 4 точки узла в экранные координаты, и ищешь ограничивающий экранный Rect. Так же, чтобы не проверять все узлы, а только те которые видны камере, можно находить их пересечение с Фрустумом камеры.
https://docs.unity3d.com/ScriptReference/GeometryUtility.CalculateFrustumPlanes.html
https://docs.unity3d.com/ScriptReference/GeometryUtility.TestPlanesAABB.html

IDoNotExist писал(а):По хорошему, нужно проверять не дистанцию до узлов Quad Tree, а площадь которую этот узел занимает на экране

Интересно, но не понятно. Во-первых, логично сделать коллайдер только в области вокруг игрока. Значит дальние плитки не будут иметь коллайдеры. На сколько я понимаю, TestPlanesAABB работает с Bounds коллайдеров. Либо придется оставлять коллайдеры для всех уровней ЛОД, либо я чего-то не понимаю.

Во-вторых, если игрок посмотрит вверх, земля под ногами не будет попадать в область видимости, значит она перейдет в самый низкокачественный ЛОД или вообще удалится. Итог один- игрок провалится под землю. Можно, конечно, ближайшие к игроку плитки обрабатывать другим принципом, никогда не уничтожая и двигая вместе с камерой, даже если они за пределами экрана, но тогда этот принцип придется приучать дружить с другим принципом, описанном выше, что может вылиться в свои проблемы на счет сшивания границ между плитками, обрабатываемыми одним способом и другим.

Как эти проблемы можно обойти?

Инженер писал(а):TestPlanesAABB работает с Bounds коллайдеров. Либо придется оставлять коллайдеры для всех уровней ЛОД, либо я чего-то не понимаю.

Во первых, никто вам не запрещает сгенерировать свой Bounds который будет храниться в каждом узле дерева, во вторых, меши которые должны храниться в узлах дерева тоже будут содержать Bounds.

Инженер писал(а):Во-вторых, если игрок посмотрит вверх, земля под ногами не будет попадать в область видимости, значит она перейдет в самый низкокачественный ЛОД или вообще удалится. Итог один- игрок провалится под землю.

Коллайдеры можно запихнуть в отдельное квадрадерево узлы которого делить уже в зависимости от дистанции. Либо использовать обычные чанки, с информацией о соседях, и включать коллайдеры только в том чанке в котором находится игрок/камера и в его соседях.

Проверять расстояние до камеры ДЛЯ КАЖДОЙ плитки

Почему, для каждой? Вам название QuadTree ничего не говорит? )) Это дерево. Если ветка целиком не попадает во flustum камеры, отсекается ветка целиком и совершенно не важно уже, сколько там плиток-веточек внутри.

Пытаюсь реализовать quadtree terrain

Может ошибаюсь, но, вроде, на юнити же уже есть готовые решения?

IDoNotExist, благодарю за ответы, теперь вроде все понятно Не уверен, что пойду именно по этому пути, но альтернативные варианты тоже хочу знать. Может быть получится реализовать свой метод, который я уже некоторое время разрабатываю. Я догадался, что можно не считать расстояние до каждой существующей на сцене плитки, а брать только по одному ряду плиток в каждой из осей Х и Z в глобальных координатах. Количесиво проверок уменьшается в десятки раз.

Woolf писал(а):Если ветка целиком не попадает во flustum камеры, отсекается ветка целиком и совершенно не важно уже, сколько там плиток-веточек внутри.

Я имею ввиду необходимость проверки расстояния для видимых плиток ландшафта, а не вообще для всего quadtree. Если ландшафт большой, видимых плиток может быть очень много.

Woolf писал(а):Может ошибаюсь, но, вроде, на юнити же уже есть готовые решения?

На github- да, полно. Но я хотел, чтобы мне объяснили человеческим языком конкретные моменты. Разбирать чужой код мне довольно сложно. Проще понять на словах логику и написать код по-своему.

Я имею ввиду необходимость проверки расстояния для видимых плиток ландшафта, а не вообще для всего quadtree. Если ландшафт большой, видимых плиток может быть очень много.

Никто не говорит о "всем дереве". Вам написали о ветках дерева! Если ветка не видна - не видны все "плитки", которые в ней.

Ну а так - все зависит от сложности ландшафта и как Вы строите ветки дерева.

Я имею ввиду необходимость проверки расстояния для видимых плиток ландшафта

Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка
Т.о. не надо проверять все. Проверяем, начиная с корня. Если целая ветвь не входит во флустум, то видимость её потомков уже не проверяется. Т.е. вы всегда проверяете на видимость только те плитки, которые входят во флустум. Ну и тут, понятное дело, тоже нужно выяснить баланс между количеством разбиений на плитки и их размерностью. Излишне мельчить тоже не стоит.