Quadtree террейн- как это делать?

Общие вопросы о Unity3D

Quadtree террейн- как это делать?

Сообщение Инженер 06 сен 2019, 09:55

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

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

Помогите пожалуйста разобраться.
Инженер
UNIт
 
Сообщения: 88
Зарегистрирован: 22 май 2016, 11:13

Re: Quadtree террейн- как это делать?

Сообщение IDoNotExist 06 сен 2019, 15:48

Инженер писал(а):Пытаюсь реализовать 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
Адепт
 
Сообщения: 1432
Зарегистрирован: 23 мар 2011, 09:18
Skype: iamnoexist

Re: Quadtree террейн- как это делать?

Сообщение Инженер 06 сен 2019, 22:28

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


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

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

Как эти проблемы можно обойти?
Инженер
UNIт
 
Сообщения: 88
Зарегистрирован: 22 май 2016, 11:13

Re: Quadtree террейн- как это делать?

Сообщение IDoNotExist 09 сен 2019, 11:28

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

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

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

Коллайдеры можно запихнуть в отдельное квадрадерево узлы которого делить уже в зависимости от дистанции. Либо использовать обычные чанки, с информацией о соседях, и включать коллайдеры только в том чанке в котором находится игрок/камера и в его соседях.
Аватара пользователя
IDoNotExist
Адепт
 
Сообщения: 1432
Зарегистрирован: 23 мар 2011, 09:18
Skype: iamnoexist

Re: Quadtree террейн- как это делать?

Сообщение Woolf 09 сен 2019, 12:56

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

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

Может ошибаюсь, но, вроде, на юнити же уже есть готовые решения?
Разработчик theFisherOnline - там, где клюёт
Разработчик Atom Fishing II - Первая 3D MMO про рыбалку
Разработчик Atom Fishing - Рыбалка на поплавок, донку, нахлыст, блесну в постъядерный период.
Аватара пользователя
Woolf
Адепт
 
Сообщения: 7179
Зарегистрирован: 02 мар 2009, 16:59

Re: Quadtree террейн- как это делать?

Сообщение Инженер 10 сен 2019, 20:57

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

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


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

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


На github- да, полно. Но я хотел, чтобы мне объяснили человеческим языком конкретные моменты. Разбирать чужой код мне довольно сложно. Проще понять на словах логику и написать код по-своему.
Инженер
UNIт
 
Сообщения: 88
Зарегистрирован: 22 май 2016, 11:13

Re: Quadtree террейн- как это делать?

Сообщение seaman 10 сен 2019, 22:02

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

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

Ну а так - все зависит от сложности ландшафта и как Вы строите ветки дерева.
seaman
Адепт
 
Сообщения: 8352
Зарегистрирован: 24 янв 2011, 12:32
Откуда: Самара

Re: Quadtree террейн- как это делать?

Сообщение Woolf 11 сен 2019, 08:14

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


Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка
Т.о. не надо проверять все. Проверяем, начиная с корня. Если целая ветвь не входит во флустум, то видимость её потомков уже не проверяется. Т.е. вы всегда проверяете на видимость только те плитки, которые входят во флустум. Ну и тут, понятное дело, тоже нужно выяснить баланс между количеством разбиений на плитки и их размерностью. Излишне мельчить тоже не стоит.
Разработчик theFisherOnline - там, где клюёт
Разработчик Atom Fishing II - Первая 3D MMO про рыбалку
Разработчик Atom Fishing - Рыбалка на поплавок, донку, нахлыст, блесну в постъядерный период.
Аватара пользователя
Woolf
Адепт
 
Сообщения: 7179
Зарегистрирован: 02 мар 2009, 16:59


Вернуться в Общие вопросы

Кто сейчас на конференции

Сейчас этот форум просматривают: Yandex [Bot] и гости: 15