Много читал на эту тему, но много вещей по-прежнему остается загадкой.
Хотелось бы получить информацию о BSP именно в применении к raytrace-системам.
Модели в рендере только мешевые (треугольнички). В дереве секущие плоскости перпендикулярны осям.
1. Как строить? Что делать с фейсами, которые пересекаются делящей плоскостью? Оставлять в текущем узле, или засовывать детям. Причем на последующих этапах тоже не совсем просто определить будет ли такой фейс принадлежать детенку детенка ("внуку")
2. В каком порядке оптимальнее трассировать? Как оптимальнее производить трассировку луча, если точка его начала лежит в каком-то из узлов...
3. Хотелось бы разобраться с BSP для начала, но интересует также kd-tree. Это то же BSP, но у которой секущая плоскость необязательно делит сцену ровно на 2 половины — её положение и ось рассечения выбирается так, чтобы оба полупространства содержали равное количество полигонов и количество пересекаемых этой плоскостью полигонов было минимальным. Т.е. на самом деле строится некоторая оценочная функция, значение которой зависит от кол-ва пересекаемых фейсов и от степени дизбаланса подпространств, затем та точка, в которой функция принимает минимальное значение и есть оптимальная — т.е. через неё нужно провести плоскость.
Я долго искал, но так ничего конкретного не нашёл, кроме диссертации одного человека, который показал, что kd-деревья являются наиболее быстрым алгоритмом для определения пересечения луча и полигона, чем те же OCTree, BSP Tree и т.п.. Но там весьма абстрактные понятия об этой самой оценочной функции, к сожалению. И о способе построения даже BSP я тоже толком не понял.
... << RSDN@Home 1.1.3 stable >>
Может, для рейтрейсера эффективнее не BSP, а группировка объектов?
Кстати, а кто-нибудь рассматривал возможность трейсинга в играх? Я когда-то видел демку, где все элементы были из сфер (кусков сфер). До сих пор не могу понять, как это могло работать. Ведь 640x480 и 30 fps — это 9 млн. пикселов в секунду. Для каждого пиксела если просчитывать пересечение лишь с 50-60 объектами, то получается 50 млн. пересечений в секунду — это совершенно нереальные цифры. Написанная на асме функция пересечения луча с прямоугольником (с поддержкой SSE) на моём athlon xp-1800 решала только 1 млн. пересечений в секунду.
Posted via RSDN NNTP Server 1.8
Здравствуйте, Евгений Коробко, Вы писали:
ЕК>Может, для рейтрейсера эффективнее не BSP, а группировка объектов?
Это каким образом? Вы имеете в виду Bounding Volumes? Я не думаю, что это эффективнее. Т.е. я уверен в обратном, поскольку диссертация одного человека на эту тему показала, что быстрее всего kd-trees (на тестовом наборе в 32 сцены с различным числом полигонов — от 10^3 до 10^5). Так что этот вопрос, думаю, не стоит обсуждать.
ЕК>Кстати, а кто-нибудь рассматривал возможность трейсинга в играх? Я когда-то видел демку, где все элементы были из сфер (кусков сфер). До сих пор не могу понять, как это могло работать. Ведь 640x480 и 30 fps — это 9 млн. пикселов в секунду. Для каждого пиксела если просчитывать пересечение лишь с 50-60 объектами, то получается 50 млн. пересечений в секунду — это совершенно нереальные цифры. Написанная на асме функция пересечения луча с прямоугольником (с поддержкой SSE) на моём athlon xp-1800 решала только 1 млн. пересечений в секунду.
Не знаю, почему у вас получилась такая маленькая производительность, может быть я неправильно считаю у себя на машине это число, но у меня без ассемблеров результат порядка 15 (microsoft compiler)-18 миллионов (Intel compiler).
В той рейтрейсовой игре есть ещё та большая разница, что пересечение определяется не с треугольником, а со сферой.
Мой кусок кода определения пересечения выглядит так (точнее это даже не мой):
#define EPSILON 0.000001
#define CROSS(dest,v1,v2) \
dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
dest[2]=v1[0]*v2[1]-v1[1]*v2[0];
#define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
#define SUB(dest,v1,v2) \
dest[0]=v1[0]-v2[0]; \
dest[1]=v1[1]-v2[1]; \
dest[2]=v1[2]-v2[2];
int _intersect_triangle1(double orig[3], double dir[3],
double vert0[3], double vert1[3], double vert2[3],
double *t, double *u, double *v)
{
double edge1[3], edge2[3], tvec[3], pvec[3], qvec[3];
double det,inv_det;
/* find vectors for two edges sharing vert0 */
SUB(edge1, vert1, vert0);
SUB(edge2, vert2, vert0);
/* begin calculating determinant - also used to calculate U parameter */
CROSS(pvec, dir, edge2);
/* if determinant is near zero, ray lies in plane of triangle */
det = DOT(edge1, pvec);
if (det > EPSILON)
{
/* calculate distance from vert0 to ray origin */
SUB(tvec, orig, vert0);
/* calculate U parameter and test bounds */
*u = DOT(tvec, pvec);
if (*u < 0.0 || *u > det)
return 0;
/* prepare to test V parameter */
CROSS(qvec, tvec, edge1);
/* calculate V parameter and test bounds */
*v = DOT(dir, qvec);
if (*v < 0.0 || *u + *v > det)
return 0;
}
else if(det < -EPSILON)
{
/* calculate distance from vert0 to ray origin */
SUB(tvec, orig, vert0);
/* calculate U parameter and test bounds */
*u = DOT(tvec, pvec);
if (*u > 0.0 || *u < det)
return 0;
/* prepare to test V parameter */
CROSS(qvec, tvec, edge1);
/* calculate V parameter and test bounds */
*v = DOT(dir, qvec) ;
if (*v > 0.0 || *u + *v < det)
return 0;
}
else return 0; /* ray is parallell to the plane of the triangle */
inv_det = 1.0 / det;
/* calculate t, ray intersects triangle */
*t = DOT(edge2, qvec) * inv_det;
(*u) *= inv_det;
(*v) *= inv_det;
return 1;
}
... << RSDN@Home 1.1.3 stable >>
>Вы имеете в виду Bounding Volumes? Я не думаю, что это эффективнее
Может, я чего-то не понимаю, но по-моему, BSP — это частный случай, когда в качестве Volume используется полупространство.
Сферы, конечно, работают быстрее. У меня есть подозрения на работу SSE на процессоре Athlon XP.
Posted via RSDN NNTP Server 1.8
Здравствуйте, Евгений Коробко, Вы писали:
>>Вы имеете в виду Bounding Volumes? Я не думаю, что это эффективнее
ЕК>Может, я чего-то не понимаю, но по-моему, BSP — это частный случай, когда в качестве Volume используется полупространство.
Давайте постараемся определится с терминологией: вы сказали, что для рейтрейсинга лучше использовать не BSP, а группировку объектов. Я не совсем понимаю, что вы имели в виду под группировкой. Bounding Volumes в данном контексте — это просто упрощенные оболочки для каждого отдельного объекта сцены.
ЕК>Сферы, конечно, работают быстрее. У меня есть подозрения на работу SSE на процессоре Athlon XP.
Подозрения связаны с тем, что он выполняет эти инструкции медленнее Pentium?
Я вот никогда не сталкивался с 3dnow! Интересно, они как-то могут помочь в такой математике как рейтрейс?
... << RSDN@Home 1.1.3 stable >>
Здравствуйте, Zlobnyi Serg.
Я сейчас занимаюсь этим вопросом, и нарыл пару неплохих статей.
Почитать про построение kd-tree можно сдесь
http://www.flipcode.com/articles/article_raytrace07.shtml
Там же есть замечательная ссылка на статейку, где очень подробно описываются эти деревья
