Двумерный массив списков. Каждый список - номера треугольников (из nvtr), которые попадают в соответствующий прямоугольник. У меня сетка достаточно равномерная, так что в адаптивной прямоугольной сетке нужды не было. Если нужна адаптивная - например список списков. Первые k*p элементов символизируют первичную прямоугольную сетку. Если в этих элементах содержатся положительные числа - то это индексы из nvtr, если отрицательные - то это четыре элемента списка (с индексом больше чем k*p) являющиеся четырьмя прямоугольниками, на которые разбит первичный четырехугольник ну и дальше по рекурсии.

Под какую ось пишешь?

OcTree используется только для поиска вершин? Или еще для чего то? (Просто интересно)

А зачем вам дерево для поиска вертексов? У вас логическая единица задачи - треугольник.

Igors, есть какое-то решение? Или хотите посмотреть варианты?

Чисто к сведению: на юникс-лайк системах malloc/new не всегда возвращает NULL (или генерит bad_alloc в случае new), а возвращает "корректный" адрес на участок памяти. При первом обращении к такому участку памяти получаем краш. Так что проверки на NULL, ловля bad_alloc, установка new handler бесполезны. Все это связано с memory overcommit.. Думаю будет полезно ознакомиться.