Здравствуйте, Евгений Коробко, Вы писали:

ЕК>Может, для рейтрейсера эффективнее не 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;
}