?
Solved

Simple 2d ray tracer - skeleton code

Posted on 2006-04-17
11
Medium Priority
?
1,588 Views
Last Modified: 2013-12-06
I need help writing a very simple 2d ray tracer.  I just need the basics of showing a 2d sphere on the screen.  I am trying to learn how to do ray tracing and I feel like this skeleton code would be a good start to build off of.  Most of the examples I find on the web are too complex for me at this point.  I am running Cygwin and openGL.
 

Thanks

Jaziar
0
Comment
Question by:Jaziar
  • 6
  • 5
11 Comments
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16476430
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?
0
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16476446
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).  :)
0
 

Author Comment

by:Jaziar
ID: 16477814
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.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 25

Accepted Solution

by:
InteractiveMind earned 2000 total points
ID: 16478456
What problem are you having with the code exactly?


You merely need to break the scene down into classes of fundamental types.

In your case, all you need is:

   -  A vector class
   -  An RGB class (to store colours)
   -  A sphere class

The vector class will be able to perform the dot product and subtraction of vectors. And the sphere class will merely store the center point, the radius, and perhaps the colour of the sphere.


In C++, your vector class (generally named 'Vector3') will look like this:

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 ) ;
    }
   
}


Your RGB class:

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


And your sphere class:

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


You might even decide to create an Image class, to store the graphical data of your rendered image.
This would merely require you storing [typically] a 2D array of rgb's. Like so:

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 ;
    }
   
}




Now, for the actual algorithm. Based on the explanation provided in my last post, it would look something like this:



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

rgb background( 0, 0, 0 ) ;  // background colour

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


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 ) ;
        }
    }
}
0
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16478479
You could then render the 'render' Image instance to a component, or output it to an image file, or something..
0
 

Author Comment

by:Jaziar
ID: 16478694
That is great!! Thanks for clearing it up for me.  
0
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16479108
No problem. Cheers.
0
 

Author Comment

by:Jaziar
ID: 16479565
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;
}

0
 

Author Comment

by:Jaziar
ID: 16479910
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;
}

0
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16479958
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)
0
 

Author Comment

by:Jaziar
ID: 16480017
I am asking a new question - that is only fair for your time
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
Despite its rising prevalence in the business world, "the cloud" is still misunderstood. Some companies still believe common misconceptions about lack of security in cloud solutions and many misuses of cloud storage options still occur every day. …
Is your OST file inaccessible, Need to transfer OST file from one computer to another? Want to convert OST file to PST? If the answer to any of the above question is yes, then look no further. With the help of Stellar OST to PST Converter, you can e…
Suggested Courses
Course of the Month14 days, 14 hours left to enroll

840 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question