octree vs grid

[wizzard]

интересно, что 3d-DDA по octree (без какого-либо кэширования, простое сэмплирование вглубь по точкам) в 1.4 раза быстрее, чем DDA по 3d сетке. Учитывая, что глубина октри сейчас 7, похоже что скорость сэмплирования упирается в промахи по кэшу, а не в арифметику.

Да, дерево весит около 1 мб, решетка – 4 мб, размер кэша процессора – 3 мб.

upd: не особенно оптимизируя, трассировка по Revelles et al. дает 3.5х прирост. Мало! :)
upd2: во-первых, похоже что я ее неправильно курю (продолжаю трассировать внутри solid geometry), во-вторых, она все равно дает более качественную картинку, что радует.
upd3: ой, а вне дебаггера оно эмм в 7 раз быстрее работает, прикольно.

Comments

[sashman.livejournal.com]

кодицо кодицо

[ivan-ghandhi.livejournal.com]

А можно для тупых, что за DDA такое? (остальное я понимаю)

[wizzard]

DDA - Digital Differential Analyzer, метод рисования линий.
см. http://courses.ece.illinois.edu/ece390/archive/archive-f2000/mp/mp4/anti.html , http://www.siggraph.org/education/materials/HyperGraph/scanline/outprims/drawline.htm , ну и т.д.

Грубо говоря, если мы ищем пересечение луча с заполненной ячейкой решетки, то для этого нам достаточно "рисовать" линию вдоль луча до тех пор, пока мы не захотим "закрасить" заполненную ячейку.

Можно, конечно, любой алгоритм рисования линий использовать, просто это первое что вспомнилось и было реализовано :)

[wizzard]

"DDA по октри" - получается из обычного DDA заменой testPixel[x,y,z] на testOctree[x,y,z], т.е. тупо сэмплируем его вдоль луча такое же количество раз, в тех же точках.

Я, если честно, думал, что это будет медленнее и сделал просто чтобы проверить, что октри правильно строится :)