|
|
|
|
Канал Игры Мечты: «Структуры данных: KD-Tree они же квадро деревья» |
|
|
|
VBKesha
 818 EGP
     
Рейтинг канала: 3(31)
Репутация: 132
Сообщения: 3330
Откуда: обл.Брянская г. Трубчевск
Зарегистрирован: 07.12.2005
  |
|
Может кто сталкивался с этими понятиями, подскажите тогда документацию на руском по этим структурам, и места их применения.
|
|
|
|
Jurec
 348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
 |
|
http://www.ray-tracing.ru/articles181.html
пойдет?
_________________
MOV topka, C++ |
|
|
|
Sh.Tac.
151 EGP
 
Рейтинг канала: 5(108)
Репутация: 14
Сообщения: 1426
Зарегистрирован: 27.07.2005
|
|
вот ещо Борескова можно почитать 
(у него правда на народе, убрал с глаз)
|
Cкрытый текст (кликните здесь для просмотра)
|
_________________
This is what you get ...
(c) Radiohead
Последний раз редактировалось: Sh.Tac. (23:10 28-09-2010), всего редактировалось 1 раз |
|
|
|
VBKesha
818 EGP
Рейтинг канала: 3(31)
Репутация: 132
Сообщения: 3330
Откуда: обл.Брянская г. Трубчевск
Зарегистрирован: 07.12.2005
|
|
Вроде то что надо!
|
|
|
|
DIMOSUS.X
997 EGP
     
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Моя реализация
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Нашел замену KD-Tree — Bounding Volume Hierarchy. Для случая отсечения по фруструму одной тысячи объектов уделывае KD-Tree в два раза 
добавлено спустя 5 минут:
Фактически подход очень похож на KD-Tree, только дочерние ноды могут пересекаться между собой и могут быть разного размера по всем трем измерениям (но при этом ни когда не выходят за пределы родительской ноды).
Такой подход решает главную проблему KD-Tree — неопределенность с объектами, которые попадают в несколько нод.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом.
Последний раз редактировалось: DIMOSUS.X (14:32 20-11-2016), всего редактировалось 1 раз |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
После оптимизации BVH у меня стал строиться в полтора раза быстрее KD-Tree, а отсечение по фраструму стало быстрее уже в четыре раза. Хотя может я хреновый кодер и плохо закодил KD-Tree 
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «Структуры данных: KD-Tree они же квадро деревья» |
|
|
