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