Raytrace4.cpp

// include Simple Direct-media Layer
#include <SDL/SDL.h>
#pragma comment( lib, "SDL.lib" )

#include <math.h>
#include <intrin.h>

// setup some basic data types
typedef   signed long long s64;
typedef unsigned long long u64;
typedef unsigned int       u32;
typedef   signed int       s32;
typedef   signed short     s16;
typedef unsigned char      byte;
typedef   signed long long fp64;

// ---- ----- ---- ---- ---- ---- ---- ---- FRAMEWORK SPECIFICS
namespace framework
{
    #define _threading

    // number of threads alive
    volatile long threads = 0;

    // true while program is running
    volatile bool active = true;

    // the title name for this application
    const char *app_name    = "Raytrace Demo";

    // size of the video buffer
    const int vidSize       = 728;

    // pixel size
    const int vidScale      = 1;

    // video buffer
    u32 *video              = NULL;

    // number of pixels in the video buffer
    const int nPixels       = vidSize * vidSize;

    // calculated real SDL video buffer size
    const int scrRes        = vidSize * vidScale;

    // the real SDL video buffer
    SDL_Surface *screen     = NULL;

    // rate onTick is called in FPS
    const int tickFPS       = 60;

    // mouse position
    int mousex              = 0;
    int mousey              = 0;

}; // namespace framework
using namespace framework;

// ---- ----- ---- ---- ---- ---- ---- ---- MATH HELPER FUNCTIONS
namespace mathHelper
{
    static u32 randSeed = 0xBABEFACE;

    static s64 absi( s64 a )
    {
        if ( a < 0 ) return -a;
        else         return  a;
    }

    static s64 maxi( s64 a, s64 b )
    {
        if ( a > b ) return a;
        else         return b;
    }

    static s64 mini( s64 a, s64 b )
    {
        if ( a < b ) return a;
        else         return b;
    }

    inline u32 randi( void )
    {
        randSeed *= 1103515245;
        randSeed += 12345;
        return (randSeed >> 15) & 0xFFFF;
    }

    inline u32 scale( u32 a, byte scale )
    {
        return (a * scale) >> 8;
    }

}; // namespace mathHelper
using namespace mathHelper;

// ---- ----- ---- ---- ---- ---- ---- ---- FIXED POINT HELPER FUNCTIONS
namespace fixedPointHelper
{
    const fp64 fp_1 = 0x10000;

    fp64 fp_mul( fp64 a, fp64 b )
    {
        return (a * b) >> 16;
    }

    fp64 fp_div( fp64 a, fp64 b )
    {
        return (a << 16) / b;
    }

    fp64 fp_ceil( fp64 a )
    {
        return (a | 0xFFFF) + 1;
    }

    fp64 fp_floor( fp64 a )
    {
        return a & (~0xFFFF);
    }

    fp64 fp_fract( fp64 a )
    {
        return a & 0xFFFF;
    }

    fp64 fp_ifract( fp64 a )
    {
        return 0xFFFF - (a & 0xFFFF);
    }

    int fp_to_int( fp64 a )
    {
        return (int) (a >> 16);
    }

    fp64 int_to_fp( int a )
    {
        return (a << 16);
    }

    fp64 fp_rand( int max )
    {
        return ((randi() % max) << 16) | (randi() & 0xFFFF);
    }

}; // namespace fixedPointHelper
using namespace fixedPointHelper;

// ---- ----- ---- ---- ---- ---- ---- ---- DRAWING HELPER FUNCTIONS
namespace videoHelper
{
    static u32 drawColour = 0xFFFFFF;

    inline void plot( int x, int y )
    {
        bool out  = x < 0;
             out |= y < 0;
             out |= x >= vidSize;
             out |= y >= vidSize;
        if ( out ) return;
        video[ x + y * vidSize ] = drawColour;
    }

    inline u32 readPixel( int x, int y )
    {
        bool out  = x < 0;
             out |= y < 0;
             out |= x >= vidSize;
             out |= y >= vidSize;
        if ( out ) return 0;
        return video[ x + y * vidSize ];
    }

    void circle( s32 x0, s32 y0, s32 radius )
    {
        s32 error  =  1 - radius;
        s32 errorY =  1;
        s32 errorX = -2 * radius;

        s32 x = radius, y = 0;

        plot(x0, y0 + radius);
        plot(x0, y0 - radius);
        plot(x0 + radius, y0);
        plot(x0 - radius, y0);

        while(y < x)
        {
            if (error > 0)
                { x--; errorX += 2; error += errorX; }
                { y++; errorY += 2; error += errorY; }

            plot(x0 + x, y0 + y);
            plot(x0 - x, y0 + y);
            plot(x0 + x, y0 - y);
            plot(x0 - x, y0 - y);
            plot(x0 + y, y0 + x);
            plot(x0 - y, y0 + x);
            plot(x0 + y, y0 - x);
            plot(x0 - y, y0 - x);
        }
    }

    void line( s32 X0, s32 Y0, s32 X1, s32 Y1 )
    {
        s32  incrementVal = 0;
        s32  shortLen     = Y1 - Y0;
        s32  longLen      = X1 - X0;
        bool yLonger      = false;
        s32  decInc       = 0;
        s32  endVal       = 0;
        s32  j            = 0;

        if ( absi( shortLen ) > absi( longLen ) )
        {
            int swap = shortLen;
            shortLen = longLen;
            longLen  = swap;
            yLonger  = true;
        }

        endVal = longLen;

        if ( longLen < 0 )
        {
            incrementVal = -1;
            longLen      = -longLen;
        }
        else
            incrementVal = 1;

        if ( longLen == 0 )
            decInc = 0;
        else
            decInc = (shortLen << 16) / longLen;

        if ( yLonger )
        {
            for ( s32 i=0; i!=endVal; i+=incrementVal )
            {
                plot( X0 + (j >> 16), Y0 + i );
                j += decInc;
            }
        }
        else
        {
            for ( s32 i=0; i!=endVal; i+=incrementVal )
            {
                plot( X0 + i, Y0 + (j >> 16) );
                j += decInc;
            }
        }
    }

    u32 randColour( void )
    {
        return ((randi()&0xFF) << 16 ) | ((randi()&0xFF) << 8 ) | ((randi()&0xFF) );
    }

}; // namesapce videoHelper
using namespace videoHelper;

// ---- ----- ---- ---- ---- ---- ---- ---- DEMO CODE ( the good stuff )
namespace demo
{
    inline float isqrtf( float number )
    {
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
        return y;
    }

    struct vec3
    {
        float x, y, z;

        vec3( )
            : x( 0 ), y( 0 ), z( 0 )
        {
        }

        vec3( float _tx, float _ty, float _tz )
            : x( _tx ), y( _ty ), z( _tz )
        {
        }

        void fnorm( void )
        {
            float d = isqrtf( x*x + y*y + z*z );
            x *= d;
            y *= d;
            z *= d;
        }
/*
        void norm( void )
        {
            float d = 1.0f / sqrtf( x*x + y*y + z*z );
            x *= d;
            y *= d;
            z *= d;
        }
 */

        vec3 project( vec3 &a )
        {
            return (*this) * ((a * (*this)) / length( ));
        }

        vec3 operator - ( const vec3 &a ) const
        {
            return vec3( x - a.x, y - a.y, z - a.z );
        }

        vec3 operator + ( const vec3 &a ) const
        {
            return vec3( x + a.x, y + a.y, z + a.z );
        }

        float operator * ( const vec3 &a )
        {
            return x*a.x + y*a.y + z*a.z;
        }

        vec3 operator * ( const float s )
        {
            return vec3( x*s, y*s, z*s );
        }

        float length( void )
        {
            return sqrt( lengthSqr() );
        }

        float lengthSqr( void )
        {
            return x*x + y*y + z*z;
        }

        static vec3 findNormal( const vec3 &s, const vec3 &d )
        {
            vec3 n = d - s;
            n.fnorm( );
            return n;
        }

        static float lengthSqr( const vec3 &s, const vec3 &d )
        {
            return (d.x-s.x)*(d.x-s.x) + (d.y-s.y)*(d.y-s.y) + (d.z-s.z)*(d.z-s.z);
        }

    };

    struct sSphere
    {
        sSphere( )
            : origin( 0, 0, 0 ), radius( 0 )
        {
        }

        sSphere( vec3 &center, float r )
            : origin( center ), radius( r )
        {
        }

        sSphere( vec3 &center, float r, u32 c )
            : origin( center ), radius( r ), colour( c )
        {
        }

        vec3   origin;
        float radius;
        u32    colour;
    };

    struct sPlane
    {
        vec3  normal;
        float offset;
        u32   colour;
    };

    struct sRay
    {
        sRay( )
        {
        }

        sRay( vec3 &a )
            : origin( ), normal( a )
        {
        }

        sRay( vec3 &a, vec3 &b )
        {
            origin = a;
            normal = b - a;
            normal.fnorm( );
        }

        vec3 origin;
        vec3 normal;
    };

    //
    // precise ray intersection test
    //
    bool intersect( sRay &ray, sSphere &sphere, vec3 &ipoint )
    {
        float t1 = -1;
        float t2 = -1;
        float discriminant;
        float t = -1;
        //temporary == e-c
        vec3 temp = ray.origin - sphere.origin;
        float b = 2 * (ray.normal * temp);
        float a = ray.normal * ray.normal;
        float c = temp * temp - (sphere.radius * sphere.radius);
        float disc;
        disc = b*b - 4*a*c;
        if ( disc < 0 )
            return false;
        else
        {
            discriminant = 1.0f / isqrtf( disc );
            t1 = (-b+discriminant)/(2*a);
            t2 = (-b-discriminant)/(2*a);

            if (t2 > 0)
            {
                ipoint = ray.origin + ray.normal * t2;
                return true;
            }
            if ( t1 > 0 )
            {
                ipoint = ray.origin + ray.normal * t1;
                return true;
            }
        }
        return false;
    }

    bool intersect( sRay &ray, sPlane &plane, vec3 &ipoint )
    {
        float t = - ( ray.origin * plane.normal + plane.offset ) / ( ray.normal * plane.normal );
        ipoint = ray.origin + ray.normal * t;
        return (t > 0);
    }

    const int nSpheres = 3;

    sSphere spheres[ nSpheres ] =
    {
        sSphere( vec3(   0, 128.f - 128.f, 420        ), 32.f, randColour( ) ),
        sSphere( vec3( -64, 128.f -  48.f, 512.f-64.f ), 64.f, randColour( ) ),
        sSphere( vec3(  32, 128.f -  32.f, 360        ), 32.f, randColour( ) )
    };

    sPlane planes[] =
    {
        { vec3( 0,-1, 0), 128.0f, 0xC0D0E0 },
        { vec3( 0, 1, 0), 128.0f, 0xC0D0E0 },
        { vec3( 0, 0,-1), 512.0f, 0xC0D0E0 },
        { vec3( 1, 0, 0), 128.0f, 0xFF7070 },
        { vec3(-1, 0, 0), 128.0f, 0x70FF70 }
    };

    vec3 light( 0,-120, 256+128 );

    bool useShadows = true;

    void rayShoot( sRay &ray, vec3 &xpoint, vec3 &normal, u32 &colour, float &min )
    {
        min = 99999999.f;
        vec3  ipoint;

        // sphere intersections
        for ( int i=0; i<nSpheres; i++ )
        {
            sSphere &sphere = spheres[ i ];
            if ( intersect( ray, sphere, ipoint ) )
            {
                float dst = (ipoint-ray.origin).lengthSqr( );
                if ( dst < min /*|| min < 0.0f*/ )
                {
                    xpoint      = ipoint;
                    float irad  = 1.0f / sphere.radius;
                    min         = dst;
                    normal      = (ipoint - sphere.origin);
                    normal.x   *= irad;
                    normal.y   *= irad;
                    normal.z   *= irad;
                    colour      = sphere.colour;
                }
            }
        }

        // plane intersections
        for ( int i=0; i<5; i++ )
        {
            sPlane &plane = planes[i];
            if ( intersect( ray, plane, ipoint ) )
            {
                float dst = (ipoint-ray.origin).lengthSqr( );
                if ( dst < min /*|| min < 0.0f*/ )
                {
                    xpoint = ipoint;
                    min    = dst;
                    normal = plane.normal;
                    colour = plane.colour;
                }
            }
        }

    }

    void incWrap( float &x, float y )
    {
        const float _2PI = 6.28318530718f;
        if ( (x+=y) > _2PI ) x -= _2PI;
    }

    int renderRegion( void *arg )
    {
#ifdef _threading
        _InterlockedIncrement( &threads );
#endif
        float hvs = vidSize / 2.0;

        SDL_Rect *rect = (SDL_Rect*)arg;

        int x1 = rect->x;
        int x2 = rect->x + rect->w;
        int y1 = rect->y;
        int y2 = rect->y + rect->h;

#ifdef _threading
        while ( active )
        {
#endif
            for ( int y=y1; y<y2; y++ )
            {
                for ( int x=x1; x<x2; x++ )
                {
                    sRay ray( vec3( x-hvs, y-hvs, hvs*2 ) );
                    ray.normal.fnorm( );

                    vec3  ipoint;
                    vec3  normal;
                    float dist;

                    rayShoot( ray, ipoint, normal, drawColour, dist );

                    //
                    // dot product lighting
                    //
                    vec3 lightNorm = vec3::findNormal( ipoint, light );
                    float dplight = normal * lightNorm;
                    if (  dplight < 0.0f )
                          dplight = 0.0f;
                    u32 dp3 = (u32)( dplight * 255 );
                    drawColour = dp3 | (dp3 << 8) | (dp3 << 16);

                    //
                    // shadows
                    //

                    // distance from intersection point to light
                    float ldist = vec3::lengthSqr( ipoint, light );

                    // trace from light to interection point
                    sRay lightRay( light, ipoint );
                    u32   colour = 0;
                    float mdist  = 0;
                    rayShoot( lightRay, vec3(), vec3(), colour, mdist );

                    if ( useShadows )
                    {
                        if ( ldist-1 > mdist )
                            drawColour = 0; //(drawColour>>1) & 0x7f7f7f;
                    }

                    plot( x, y );
                }
            }
#ifdef _threading
        } // while ( active )
#endif

#ifdef _threading
        _InterlockedDecrement( &threads );
#endif
        return 1;
    }

    void onTick( void )
    {
        static float t=0.0f; incWrap( t, 0.012346f );
        spheres[0].origin.x = sin( (float)t ) * 64.f;

#ifndef _threading
        SDL_Rect r1 = { 0  ,   0, vidSize, vidSize };
        renderRegion( &r1 );
#endif

        static float g=0.0f; incWrap( g, 0.024243f );
        light.x = sin( g ) * 64;
        light.z = cos( g ) * 64 + (256+128);
    }

    void onInit( void )
    {
#ifdef _threading
        float hvs = vidSize / 2.0;
        SDL_Rect r1 = {     0  ,   0, hvs, hvs };
        SDL_Rect r3 = {     hvs,   0, hvs, hvs };

        SDL_Rect r5 = {     0  , hvs, hvs, hvs };
        SDL_Rect r7 = {     hvs, hvs, hvs, hvs };

        SDL_CreateThread( renderRegion, &r1 );
        SDL_CreateThread( renderRegion, &r3 );

        SDL_CreateThread( renderRegion, &r5 );
        SDL_CreateThread( renderRegion, &r7 );
#endif
    }

    void onKeyHit( SDLKey key )
    {
        switch ( key )
        {
        case ( SDLK_SPACE ):
            useShadows = !useShadows;
        }
    }

}; // namespace demo
using namespace demo;

// ---- ----- ---- ---- ---- ---- ---- ---- FRAMEWORK FUNCIONS
namespace framework
{
    static bool app_init( void )
    {
        if ( SDL_Init( SDL_INIT_VIDEO ) != 0 )
            return false;

        SDL_WM_SetCaption( app_name, NULL );

        screen = SDL_SetVideoMode( scrRes, scrRes, 32, 0 );
        if ( screen == NULL )
            return false;

        if ( vidScale == 1 )    video = (u32*)screen->pixels;
        else                    video = new u32[ nPixels ];

        return true;
    }

    static void blit_2x( void )
    {
        //
        const int stride = screen->w;

        u32 *dst = (u32*) screen->pixels;

        int a = 0;

        for ( int i=0; i<nPixels; i++ )
        {
            u32 colour = video[ i ];

            // x4 pixel write
            dst[0       ] = colour;
            dst[1       ] = colour;
            dst[  stride] = colour;
            dst[1+stride] = colour;

            dst += 2;
            if ( a++ >= vidSize )
            {
                a = 0;
                // add on ONE stride not two since one length
                // has already been walked
                dst += stride;
            }
        }
    }

    static void app_draw( void )
    {
        if ( vidScale <= 1 )
            return;

        if ( vidScale == 2 )
        {
            blit_2x( );
            return;
        }

        for ( int i=0; i<nPixels; i++ )
        {
            SDL_Rect rect =
            {
                (i % vidSize) * vidScale,
                (i / vidSize) * vidScale,
                                vidScale,
                                vidScale
            };
            SDL_FillRect( screen, &rect, video[ i ] );
        }
    }

    static bool app_tick( void )
    {
        SDL_Event event;
        while ( SDL_PollEvent( &event ) )
        {
            switch ( event.type )
            {
            case ( SDL_QUIT ):
                active = false;
                break;
            case ( SDL_KEYUP ):
                {
                    if ( event.key.keysym.sym == SDLK_ESCAPE )
                    {
                        active = false;
                    }
                    else
                        onKeyHit( event.key.keysym.sym );
                }
                break;
            }
        }
        return active;
    }

    static void app_quit( void )
    {
        //
        if ( video != NULL )
            if ( video != screen->pixels )
                delete [] video;
        video = NULL;
        //
        if ( screen != NULL )
            SDL_FreeSurface( screen );
        //
        SDL_Quit( );
    }

}; // namespace framework

// windows entry point
int __stdcall WinMain( int, int, int, int )
{
    // start up SDL
    atexit( app_quit );
    if (! app_init( ) )
        return 1;
    // get keyboard access
    u32 keyCount = 0;
    byte *keys = SDL_GetKeyState( (int*) &keyCount );
    // seed the random
    randSeed ^= SDL_GetTicks( );
    // call the on initialize function
    onInit( );
    //
    int oldTicks = SDL_GetTicks( );
    // work out the tick threshold in milliseconds
    const int tickThresh = 1000 / tickFPS;
    //
    while ( app_tick( ) )
    {
        int diff = SDL_GetTicks() - oldTicks;

        if ( diff < 10  )
            SDL_Delay( 10 );

        if ( diff > 500 )
        {
            oldTicks += diff;
            continue;
        }

        while ( diff > tickThresh )
        {
            // grab the mouse state
            SDL_GetMouseState( &mousex, &mousey );
            // tick the application
            onTick( );
            app_draw( );
            SDL_Flip( screen );
            // progress the tick count
            oldTicks += tickThresh;
            diff     -= tickThresh;
        }
    }

    //
    while ( threads > 0 )
        SDL_Delay( 100 );

    return 0;
}