Я внедряю отбраковку усеченного конуса для динамических объектов в моем движке и читаю как можно больше о "свободных октридах".К сожалению, большинство источников довольно расплывчаты, и на самом деле это просто множество сообщений людей, говорящих о том, насколько они хороши, и что они дали O (1) вставку и удаление, но без объяснения какой-либо логики, стоящей за этим.
Я понимаюОсновные принципы, согласно которым октанты обрабатываются как большие, чем они, и что свободный фактор может доходить до 2. Это означает, что объект может быть вставлен в один узел в зависимости от его размера.Проблема в том, что во многих статьях не используется «k-фактор», равный 2 (возможно, для более плотной подгонки), и поэтому они теряют быстрое вставление / удаление;вместо этого они поддерживают структуру смежности, так что вы можете обойти все узлы на заданной глубине и проверить центр объекта с каждым узлом.
Мне нужен только грубый тест отбраковки, и я хотел бы получить O (1) время вставки и разработали формулу для расчета глубины (уровня), на которую должен быть вставлен объект.Однако я не могу найти ни одной статьи, в которой обсуждается формула для вычисления точного узла по размеру и положению объекта.
Полностью ли я неправильно понял алгоритм и ищу что-то, что невозможно?Если кто-то может указать мне какие-либо хорошие статьи или статьи (я прочитал http://tulrich.com/geekstuff/), то это было бы здорово.
PS. Стоит упомянуть, что я использую линейное октре, хранящееся в1D массив
Спасибо за любую помощь