Simple 2d ray tracer - skeleton code

You're using OpenGL for this?  :-\

You'd be better just to construct your own component, with which you can perform pixel-shading with (fill in the colour of each pixel, one by one).


The task is really quite simple; you define a sphere with center c=(cx,cy,cz) and radius R.

The sphere can be defined by the implicit equation:

   (x - cx)² + (y - cy)² + (z - cz)² - R² = 0

Which can be rewritten in vector form:

   (p - c) . (p - c) - R² = 0

So, any point 'p' that satisfies this equation is on the sphere (this is the ray-sphere intersection BTW).

Now, if we plug the parametric line of:

   p(t) = o + td

(where o is the origin vector, t is a parameter, and d is the direction of the vector, relative to o)

into the above, then we get:

   (o + td - c) . (o + td - c) - R² = 0

And moving the terms around a bit, yields:

   (d . d) t² + 2d . (o - c) t + (o - c) . (o - c) - R² = 0

Here, everything is known, except the parameter 't'. So this is a classic quadratic equation in 't', meaning it has the form:

   At² + Bt + C = 0.

The solution to this equation is:

   t = (-B +/- sqrt(B² - 4AC)) / 2A

But in your case, you don't need to find the value of 't'. You just need to use the values of A, B, and C, to find out if there is a colission.

Well, the expression under the sqrt within that equation of 't': B²-4AC, is called the discriminant. And if this value is greater than or equal to 0, then there is a collision; else, it's a miss.

(Actually, if it's equal to 0, then there's just 1 collision, meaning that it just skims the surface of the sphere—touching it at one point only; and if it's greater than 0, then it goes through one end, and out of the other). :)


So, here's what you do for your very simple 2D ray tracer (for a right-handed coordinate system):

// center of sphere:
c = (0, 0, 10)

// radius of sphere:
R = 7

// perform the very very simple 2d ray tracing:
for i=0..w
   for j=0..h
     
      o = (i, j, 0)
      d = (0, 0, -1)
     
      discriminant = (d . (o - c))*(d . (o - c)) - (d.d)*((o - c) . (o - c) - R*R)
     
      if discriminant >= 0
         set color at (i,j) on the screen to the colour of the sphere
      else
         set color at (i,j) on the screen to the background colour



Where the notation of:

   'a . b'

is the "dot product" (or "scalar product"), and is the below operation between 2 vectors (a and b in this case):

   a . b = ax*bx + ay*by + az*bz

(So the result is a scalar of course).



Does that help?

By the way, just to clarify: the function p(t) defines the light ray, as it leaves your eyes (lol, obviously that's not really what happens, but that's how it's modelled).  :)

I understand your concepts, you have done a great job explaining.  Being I mainly write scripts at work, I am a little lost on the code.

You could then render the 'render' Image instance to a component, or output it to an image file, or something..

That is great!! Thanks for clearing it up for me.  

No problem. Cheers.

let me show you what I have and maybe you can tell me where I am wrong.  I can not get it to compile.

#include <GL/glut.h>
#include <iostream>
using namespace std;
void display();

int w = 400 ;  // image width
int h = 300 ;  // image height

class Vector3
{
    public:
        double x, y, z ;
   
   
    Vector3( double x_, double y_, double z_ )
    {
        x = x_ ;
        y = y_ ;
        z = z_ ;
    }
   
    Vector3()
    { x = y = z = 0.0 ; }
   
   
    inline double dot( Vector3 v )
    {
        return x*v.x + y*v.y + z*v.z ;
    }
   
    inline Vector3 operator-( const Vector3& v1, const Vector3& v2 )
    {
        return Vector3( v1.x-v2.x, v1.y-v2.y, v1.z-v2.z ) ;
    }
   
}

class rgb
{
    public:
        int r, g, b ;
   
    rgb( int r_, int g_, int b_ )
    {
        r = r_ ;
        g = g_ ;
        b = b_ ;
    }
   
}


class Sphere
{
    public:
        Vector3 C ;
        double R ;
        rgb colour ;
   
    Sphere( Vector3 C_, double R_, rgb colour_ )
    {
        C = C_ ;
        R = R_ ;
        colour = colour_ ;
    }
   
}

class Image
{
    public:
        rgb** raster ;
        int w, h ;
       
    Image( int w_, int h_ )
    {
        w = w_ ;
        h = h_ ;
       
        raster = new rgb*[w] ;
        for ( int i=0; i<w; i++ )
            raster[i] = new rgb[h] ;
    }
   
   
    void set( int i, int j, rgb& c )
    {
        raster[i][j] = c ;
    }
   
}




void init(void)
{
 glMatrixMode(GL_PROJECTION);
 glLoadIdentity();
 glOrtho(0, 500, 0, 500, -1, 1);
 rgb background( 0, 0, 0 ) ;  // background colour
 gluLookAt(0, 0, 0, 0, 0, 0, 0, 0, 0);
 display();
 }


void display(void)
{
Sphere sphere( Vector3( 0, 0, 10 ), 100, rgb( 255, 0, 0 ) ) ; // the sphere

Image render( w, h ) ; // the image to store the graphical data in

int o;
int d;

for ( int i=0; i<w; i++ )
{
    for ( int j=0; j<h; j++ )
    {
       
        Vector3 o( i, j, 0 ) ;
        Vector3 d( 0, 0, -1 ) ;
       
        double discriminant =
            d.dot( o-sphere.c ) * d.dot( o-sphere.c ) - d.dot( d ) * ( (o - sphere.c).dot( o - sphere.c ) - sphere.R*sphere.R ) ;
       
        if ( discriminant >= 0 )
        {
            render.set( i, j, sphere.colour ) ;
        } else
        {
            render.set( i, j, background ) ;
        }
    }
}

}

int main(int argc, char** argv)
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB | GLUT_DEPTH);
glutInitWindowSize (500, 500);
glutInitWindowPosition (100, 100);
glutCreateWindow(argv[0]);
init();
glutDisplayFunc(display);
glutMainLoop();
return 0;
}

I got it to compile, but when I run the executable - the window comes up and never displays anything (froze).  Here is the code I am using - If you would like for me to open a new question I can.

#include <GL/glut.h>
#include <iostream>

using namespace std;

void display();
void init();

int w = 400 ;  // image width
int h = 300 ;  // image height


class Vector3
{
    public:
        double x, y, z ;
   
   
    Vector3( double x_, double y_, double z_ )
    {
        x = x_ ;
        y = y_ ;
        z = z_ ;
    }
   
    Vector3()
    { x = y = z = 0.0 ; }
   
   
    inline double dot( Vector3 v )
    {
        return x*v.x + y*v.y + z*v.z ;
    }
   
   
   
};

inline Vector3 operator-( const Vector3& v1, const Vector3& v2 )
    {
        return Vector3( v1.x-v2.x, v1.y-v2.y, v1.z-v2.z ) ;
    }
      
class rgb
{
    public:
        int r, g, b ;
   
      rgb() {}
      
   
      rgb( int r_, int g_, int b_ )
    {
        r = r_ ;
        g = g_ ;
        b = b_ ;
    }
   
};

rgb background( 0, 0, 0 ) ;  // background colour
class Sphere
{
    public:
        Vector3 C ;
        double R ;
        rgb colour ;
   
    Sphere( Vector3 C_, double R_, const rgb &colour_ )
    {
        C = C_ ;
        R = R_ ;
        colour = colour_ ;
    }
   
};

class Image
{
    public:
        rgb** raster ;
        int w, h ;
       
    Image( int w_, int h_ )
    {
        w = w_ ;
        h = h_ ;
       
        raster = new rgb*[w] ;
        for ( int i=0; i<w; i++ )
            raster[i] = new rgb[h] ;
    }
   
   
    void set( int i, int j, rgb& c )
    {
        raster[i][j] = c ;
    }
   
};

void init()
{
 
 glMatrixMode(GL_PROJECTION);
 glLoadIdentity();
 glOrtho(0, 400, 0, 300, -1, 1);
 }


void display()
{
Sphere sphere( Vector3( 0, 0, 1 ), 100, rgb( 255, 0, 0 ) ) ; // the sphere

Image render( w, h ) ; // the image to store the graphical data in

int o;
int d;

for ( int i=0; i<w; i++ )
{
    for ( int j=0; j<h; j++ )
    {
       
        Vector3 o( i, j, 0 ) ;
        Vector3 d( 0, 0, -1 ) ;
                   
        double discriminant =
            d.dot( o-sphere.C ) * d.dot( o-sphere.C ) - d.dot( d ) * ( (o - sphere.C).dot( o - sphere.C ) - sphere.R*sphere.R ) ;
       
        if ( discriminant >= 0 )
        {
            render.set( i, j, sphere.colour ) ;
        } else
        {
            render.set( i, j, background ) ;
        }
    }
}

}

int main(int argc, char** argv)
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB | GLUT_DEPTH);
glutInitWindowSize (500, 500);
glutInitWindowPosition (100, 100);
glutCreateWindow(argv[0]);
init();
glutDisplayFunc(display);
glutMainLoop();
return 0;
}

You're not rendering anything to the display.

This:

        if ( discriminant >= 0 )
        {
            render.set( i, j, sphere.colour ) ;
        } else
        {
            render.set( i, j, background ) ;
        }

Should be changed to something like:

        if ( discriminant >= 0 )
        {
            glColor3i( sphere.colour.r, sphere.colour.g, sphere.colour.b ) ;
            glPointSize( 1.0 ) ;
            glBegin( GL_POINTS ) ;
                glVertex2i( i, j ) ;
            glEnd() ;
        } else
        {
            glColor3i( background.r, background.g, background.b ) ;
            glPointSize( 1.0 ) ;
            glBegin( GL_POINTS ) ;
                glVertex2i( i, j ) ;
            glEnd() ;
        }


(Obviously, it would actually be much more efficient to declare the glBegin() and glEnd() outside of the iterations)

I am asking a new question - that is only fair for your time