0
$\begingroup$

I'm trying to write a raycaster similar to Voxlap, but it's many times slower. I've tried octrees, but the performance gains are marginal- only 10 to 20 percent. I use the algorithm from this site: https://lodev.org/cgtutor/raycasting.html

The full code: https://pastebin.com/kYs9zs7S

The raycasting loop:

      float cameraX = x/HALFRESX -1;

      for(int y = 0; y < RESY; y ++) { 


        float cameraY = y/HALFRESY -1;//cam vec, -1 to 1


        struct Point3D rayd;
        rayd.z = dir.z + plane.z*cameraY;
        rayd.x = dir.x + plane.x*cameraX;
        rayd.y = dir.y + plane.y*cameraX;

        struct Point3D delta;
        delta.y = fabsf(1/rayd.y);
        delta.x = fabsf(1/rayd.x);
        delta.z = fabsf(1/rayd.z);


        struct pos map;
        map.x = (char)pos.x;
        map.y = (char)pos.y;
        map.z = (char)pos.z; 

        struct pos s;
        struct pos step;
        struct Point3D sdist;
        if(rayd.x < 0) {
          step.x = -1;
          s.x = 1;
          sdist.x = (pos.x - map.x) * delta.x; 
        }
        else {
          step.x = 1;
          s.x = 0;
          sdist.x = (map.x + 1 - pos.x) * delta.x; 
        }
        if(rayd.y < 0) {
          step.y = -1;
          s.y = 1;
          sdist.y = (pos.y - map.y) * delta.y; 
        }
        else {
          step.y = 1;
          s.y = 0;
          sdist.y = (map.y + 1 - pos.y) * delta.y; 
        }

        if(rayd.z < 0) {
          step.z = -1;
          s.z = 1;
          sdist.z = (pos.z - map.z) * delta.z; 
        }
        else {
          step.z = 1;
          s.z = 0;
          sdist.z = (map.z + 1 - pos.z) * delta.z; 
        }



        char side; //either 0 (NS), or 1 (EW), or 2(UD)
        while( !MAP[map.x][map.y][map.z]) {
          if(sdist.y < sdist.x ) {
            if(sdist.y < sdist.z) {
              sdist.y += delta.y;
              map.y += step.y;
              side = 1; // y
            }
            else {
              sdist.z += delta.z;
              map.z += step.z;
              side = 2; 
            }
          }
          else {
            if(sdist.x < sdist.z) {
              sdist.x += delta.x;
              map.x += step.x;
              side = 0; 
            }
            else {
              sdist.z += delta.z;
              map.z += step.z; 
              side = 2; 
            }
          }
        }
        char blockHit = MAP[map.x][map.y][map.z];


#ifdef USE_REFLECTIONS
        bool reflect = false;
reflect:;
        if(blockHit == 6){
          reflect = true;
          if(!side) {
            step.x*=-1;
            sdist.x += delta.x;
            map.x += step.x;
            rayd.x*=-1;
          }
          else if(side == 1) {
            step.y*=-1;
            sdist.y += delta.y;
            map.y += step.y;
            rayd.y*=-1;
          }
          else {
            step.z*=-1;
            sdist.z += delta.z;
            map.z += step.z;
            rayd.z*=-1;
          }

          while( !MAP[map.x][map.y][map.z]) {
            if(sdist.y < sdist.x ) {
              if(sdist.y < sdist.z) {
                sdist.y += delta.y;
                map.y += step.y;
                side = 1; // y
              }
              else {
                sdist.z += delta.z;
                map.z += step.z;
                side = 2; 
              }
            }
            else {
              if(sdist.x < sdist.z) {
                sdist.x += delta.x;
                map.x += step.x;
                side = 0; 
              }
              else {
                sdist.z += delta.z;
                map.z += step.z; 
                side = 2; 
              }
            }
          }

        blockHit = MAP[map.x][map.y][map.z];
        }
#endif
        struct Point3D lightDist;
        struct Point3D hit;

        if(!side) {  // x side hit

          hit.x = map.x + s.x;
          float relativeHit = hit.x-pos.x;
          hit.y = pos.y + relativeHit/rayd.x*rayd.y;
          hit.z = pos.z + relativeHit/rayd.x*rayd.z;

        }
        else if(side == 1) {  // y side hit

          hit.y = map.y + s.y;
          float relativeHit = hit.y-pos.y;
          hit.x = pos.x + relativeHit/rayd.y*rayd.x;
          hit.z = pos.z + relativeHit/rayd.y*rayd.z;

        }
        else {  // z side hit

          hit.z = map.z + s.z;
          float relativeHit = hit.z-pos.z;
          hit.x = pos.x + relativeHit/rayd.z*rayd.x;
          hit.y = pos.y + relativeHit/rayd.z*rayd.y;
        }
        lightDist.x = light[0][0] - hit.x;  // x
        lightDist.y = light[0][1] - hit.y;  // y
        lightDist.z = light[0][2] - hit.z;  // z

        double lightdist = sqrt(lightDist.x*lightDist.x + lightDist.y*lightDist.y + lightDist.z*lightDist.z);
        if(lightdist > 32) {voxelColour = 32;}
        else if(lightdist > 4)  voxelColour = 1024/lightdist;
        else voxelColour = 255;



#ifdef USE_REFLECTIONS
        if(reflect) voxelColour/=1.2;
#endif

        void drawPixel( Uint32 colour) {
          pixels[y][x] = colour;
        }

        if(blockHit <3) drawPixel(0x010101*voxelColour);
        else if(blockHit == 3) drawPixel(voxelColour);
        else if(blockHit == 4) drawPixel(0x10000*voxelColour);
#ifdef USE_REFLECTIONS
        else if(blockHit == 6) goto reflect;
#endif
        else drawPixel(0x100*voxelColour);

      }
    }
$\endgroup$
2
$\begingroup$

You have a lot of if condition affecting different components of various Point3D. If conditions, especially hard to predict ones are very expensive, instead look into using SIMD to remove most of the conditions by replacing the false branches with identity operations.

for example

  if(!side) {
    step.x*=-1;
    sdist.x += delta.x;
    map.x += step.x;
    rayd.x*=-1;
  }
  else if(side == 1) {
    step.y*=-1;
    sdist.y += delta.y;
    map.y += step.y;
    rayd.y*=-1;
  }
  else {
    step.z*=-1;
    sdist.z += delta.z;
    map.z += step.z;
    rayd.z*=-1;
  }

can be replaced with

step = simd_xor(step, negateTable[side]); //negate can be done by xoring the sign bit
sdist = simd_add(sdist, simd_and(delta, addMask[side]));
map = simd_add(map, simd_and(step, addMask[side]));
rayd= simd_xor(step, negateTable[side]);
$\endgroup$
2
$\begingroup$

Disclaimer: I've only skimmed through the code.

To be honest, the best thing to do would be to use a profiler on your code to identify what actually is costing CPU cycles.

Having said that, some operations are more expensive than others - e.g. floating point division and sqrt OR, potentially far more detrimental to performance, cache misses.

WRT to the former, for example, in...

 double lightdist = sqrt(lightDist.x*lightDist.x + lightDist.y*lightDist.y + lightDist.z*lightDist.z);
        if(lightdist > 32) {voxelColour = 32;}
        else if(lightdist > 4)  voxelColour = 1024/lightdist;
        else voxelColour = 255;

...it doesn't look to me like you always need to compute the sqrt in two of the branches. Perhaps instead, just keep the square of the distance and compare against SQ(32), SQ(4) etc.

BTW: the following looks a little 'odd'

        rayd.z = dir.z + plane.z*cameraY;
        rayd.x = dir.x + plane.x*cameraX;
        rayd.y = dir.y + plane.y*cameraX;

Do you really intend to use cameraX twice? I've not really thought about it but it just looks suspicious.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.