Как свернуть быстрое представление BVH в Haskell

Я играю с Haskell Raytracer и в настоящее время использую реализацию BVH, которая подчеркивает наивное двоичное дерево для хранения иерархии,

data TreeBvh
   = Node Dimension TreeBvh TreeBvh AABB
   | Leaf AnyPrim AABB

где Dimension - это X, Y или Z (используется для более быстрого обхода), а AABB - мой тип для ограничивающего по оси рамки. Это работает достаточно хорошо, но я бы очень хотел получить это так быстро, как только возможно. Поэтому мой следующий шаг (при использовании C/С++) заключается в том, чтобы использовать это дерево для построения сглаженного представления, где узлы хранятся в массиве, "левый" ребенок сразу же следует за родителем node, а индекс правого ребенка родительский хранится с родителем, поэтому у меня есть что-то вроде этого:

data LinearNode
   = LinearNode Dimension Int AABB
   | LinearLeaf AnyPrim AABB

data LinearBvh
   = MkLinearBvh (Array Int LinearNode)

Я еще не пробовал это, но я боюсь, что производительность все равно будет sub-par, потому что я не могу хранить экземпляры LinearNode в UArray, и я не мог бы сохранить индексирование Int справа ребенок вместе со значениями Float, которые составляют AABB в одном UArray (исправьте меня, если я ошибаюсь). И использование двух массивов будет означать плохую когерентность кэша. Поэтому я в основном ищу способ эффективно хранить свое дерево, чтобы я мог ожидать хорошей производительности для обхода. Это может быть

  • компактный
  • имеют хорошие локальные свойства.
  • работа с недавними компиляторами GHC
  • должен проходить как можно меньше ссылок (если "thunk" не может помочь производительности, поэтому "unboxed" типы помогут мне подумать)

Ответы

Ответ 2

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

Возможно, вам будет интересно сохранить дерево в плоском массиве в кэше, не обращая внимания ( "Van Emde Boas tree" ). Он должен работать, но кто знает.:)

(бесстыдный плагин: я уже некоторое время пытался сделать подобное, я использовал некоторые расширенные системные функции языка программирования ATS, чтобы сделать raytracer более безопасным и быстрым, см. код здесь: http://code.google.com/p/ats-miscellanea/ - к сожалению, я еще далеко не прошел)

Ответ 3

То, что вы предлагаете, было обнаружено много лет назад, оно называется иерархией ограничивающих интервалов (BIH).