shade.ca
Games
Art
Coding
Beauty Contest
Reviews
Spoofs
Corporate site
Webcams
Links




Tell Me the Truth

Hacky the raccoon
Shade.ca Web Design

3D Molecule representation (C++)

SouthPark Slot Machine

Random Review
Random Review



Join our mailing list!   Tell a friend about this site!

3DMOL - The application

The application

Throughout the following pages, we will explain how we created our application. The knowledge you will get from this article will help you create your own 3D engine on your computer. Of course, the document will be written in an easy to understand way (even if you have no programming experience) and the actual code will only be used in examples. Evidently, we are not giving you our project's source code so that you can apply a few modifications and call it your own. We want to help you understand how basic 3D engines work. Furthermore, a good 3D engine is independent from the language in which it has been created; thus, we want to allow you to program in the language of your choice. It is interesting to note that the most important aspect of an application is not the actual code but rather the method used to resolve the problem. Also, what differenciates an advanced programmer from a beginner is his capacity to analyze problems and try to resolve them without touching a computer. The programmer must plan the application's structure and operation before starting its creation. In short, what follows is a step-by-step explanation of the construction of our 3D engine. Please note that some aspects will not be explained because, originally, this document was to be read by our chemistry teacher that has no programming knowledge. We leave it to you to explore the source code to find these aspects and acquire a better understanding of the operation of a 3D engine.



Object oriented programming

    We must first tell you that our application was created following object oriented programming, a concept that we will now define.

    Previously, linear programming was the only type of programming used. It consisted of a succession of commands that we read from top down. In addition, there were very few data types and those that existed were simple and preset by the programming language (integers, real numbers, characters, etc.).




    Since then, a new type of programming has been created. Object oriented programming allowed programmers to create unrestricted complex "objects" that can interact with each other. This method makes it possible to create complex symbolic objects to hold information in a more structured manner than with the basic data types. The programmer builds objects to fit his needs: he defines them. Here, we must take the term object in a broad manner because in programming languages, the term object does not only mean physical objects that we are accustomed to. A programming object can represent something physical or symbolic. Furthermore, the programmer can define the"properties"and"methods"of his objects. An objects properties are usually simpler data types such as strings of characters; they are the objects fundamental characteristics. On their side, an objects methods are the actions that it can execute on itself or other objects. Here are two examples that might help you understand these concepts:
        car"object"(concrete):
            properties: colour, name, year
            methods: move forwards, move backwards


        word list"object"(symbolic):
            properties: number of words, each of the words
            methods: add or remove a word




Steps to create a 3D engine

    The first step in the creation of a 3D engine is the development of two "Point" objects; they are quite simple objects with which we will create more complex ones. A two-dimensional point has to coordinates (x,y) (they are its properties) and a three-dimensional point has three (x,y,z). We have reached the end of the first step towards creating a functional 3D engine.

class point_2D
{
    public:
        // float: to accept non integer values during rotations
        float x, y;

        // functions
        inline void setcoords(float fx, float fy) { x = fx; y = fy; }
        ~point_2D() { x=0;y=0; }
};


class point_3D
{
    public:
        // float: to accept non integer values during rotations
        float x, y,z;

        // functions
        inline void setcoords(float fx, float fy, float fz) { x = fx; y = fy; z=fz; }
        ~point_3D() { x=0;y=0;z=0; }
};


    Secondly, by linking two points together (2D or 3D), we obtain a line. For our purposes, lines are not important; however, faces are. Here, we can start to see the usefulness of object oriented programming. We wish to group our points into a face (or polygon): we only need to define our "Face" object to contain an undefined quantity of "Point" objects. In the past, we would have had to define a list of coordinates without any real relation with each other. This is why object oriented programming helps simplify the conceptualization of the application.


class face
{
    public:
        // variables
        int * points;
        int nbofptsinface;

        // functions
        void set(int inputnb, int * inputarray);

        // clear memory
        ~face() { delete [] points; points=0; nbofptsinface=0; }
};

// defines all the points in a face in one command
void face::set(int inputnb, int * inputarray)
{
    int i;
    nbofptsinface = inputnb;
    points = new int[nbofptsinface];

    // define every point
    for(i = 0; i<nbofptsinface; i++)
    {
        points[i] = inputarray[i];
    }
};


    The next step is to define a "Form" object which regroups an undefined quantity of "Face" objects. For what follows, we will use a cube as an example to represent the different methods and properties of the "Form" object. It is very simple: one cube, six faces, eight points. Without any planning, we could have defined our cube as being composed of six faces of four points each. However, if we built our cube this way, we would triple the number of points needed in the computers memory. This is why our object will be composed of a list of eight points that are used by the different faces. This very economic idea came to us after reading a little 3D guide that comes with Allegro, our graphical library.

    We have just defined a list of points that we will name the "Local" list. These points are of the 3D type because a cube is a three-dimensional object. Let the point with the coordinates (0,0,0) be the center or the "Form" object. We will define every point of the "Local" list from the center of the object. For example, for a cube having a side of 2, would have the following "Local" list:
{ (-1,-1,-1), (-1,-1,1), (-1,1,-1), (-1,1,1), (1,-1,-1), (1,-1,1), (1,1,-1), (1,1,1) }

    Lets place this cube in a virtual world. Using its current coordinates, it would be centered on the origin of the virtual world. Lets imagine that we wanted to move the object: we would have to move every point individually. We created a second list named "World" to represent the coordinates of the object in the world. Furthermore, we will define a property of the "Form" object: the coordinates of the center of the object in the virtual world (these coordinates are stored in a 3D Point object). Also, we must add a method that applies the translation on every point in the "Local" list to create the "World" list. In addition, another property, a scaling factor, is added to the object and is used in conversion ( "Local" to "World" ) method. This will allow us to define a standard cube and size it to our needs. Now, we only need to define our "Form" object by specifying its center (using a 3D Point object) and the scaling factor. Then, we apply the method that converts the "Local" list to the "World" list, thus giving us the possibility to put our object anywhere in a three-dimensional world and allow us to move it by moving its center and recalculating the "World" list.

    We aren't finished ! We are approaching the heart of a 3D engine: rotating objects in a three-dimensional world. To achieve this goal, we need to define a third list "Aligned" and the angle values that we want our object to turn around each of the three axes (x,y,z). We must apply the same principle that we explained previously to convert the "World" list to the "Aligned" list. The equations for the rotations around each axis are demonstrated here.

    Until now, we manipulated points in our virtual world, but we must be able to display them on the screen. To do this, we must create a "Screen" list, made of two-dimensional points. Indeed, our world is three-dimensional, but our screen is flat (two dimensions). With this list comes a new method to convert points from 3D to 2D (see here for the demonstration of the formula).     We have now arrived at a point that depends directly on the programming language: displaying our objects. Depending on which language you choose, the programming could be very different but it all comes down to taking each face individually and drawing lines between each consecutive two-dimensional point. The 3D objects can be hard to imagine because the faces are not filled and we can see through the object.


for (j=0;j<facelist[i].nbofptsinface;j++)
    {
    // display border lines
    x1=(int) screenlist[ facelist[i].points[j] ].x;
    y1=(int) screenlist[ facelist[i].points[j] ].y;

    if (j==facelist[i].nbofptsinface-1)
        {
        x2=(int) screenlist[ facelist[i].points[0] ].x;
        y2=(int) screenlist[ facelist[i].points[0] ].y;
        }
    else
        {
        x2=(int) screenlist[ facelist[i].points[j+1] ].x;
        y2=(int) screenlist[ facelist[i].points[j+1] ].y;
        }

    line(bitmap, (int) x1, (int) y1, (int) x2, (int) y2, myColor);
    }



    At this step, we can only move one cube in our virtual world; we must render this situation more complex. That is why we created a sphere ( "Form" ) object to represent atoms. In general, we associate atoms to sphere more frequently that we do to cubes. However, we did not wish to create perfect spheres because in three dimensions, it would look like a circle, from any angle, when drawn on the screen. To make it seem like it was in 3D, we would need to create shading on the circle. Because we were lacking time, we decided we did not want 3DMOL to apply shading or textures on the faces of our objects. Therefore, we created a pseudo-sphere that is formed by 79 triangles. Furthermore, our first goal was to create molecules, not atoms. Therefore, we must create a "Molecule" object, regrouping an indefinite quantity of "Atom" objects. To draw the links between our atoms, we only need to link the centers of the "Form" objects; these are defined in the "World" list which have been converted to the "Aligned" list and finally projected to the screen in the "Screen" list.




(Screenshot #1: CH4 in version 1)


    Next, we decided to represent only a few molecules to test our software (CH4, C2H4, C2H2). After creating these molecules, we embellished the application by using different colors for each atom type. However, the most impressive modification came when we converted our objects from their wire-frame form to an opaque object. To do this, we must determine if the normal of each face points towards the viewer or if it points towards the back of the screen. By taking the first three points of each of the faces and by using the formula number 7 (face sorting), we can determine if we should draw the face or not. However, this equation only works if we have defined our faces as to have the points defined in a clockwise manner, if the face is viewed from the outside. Therefore, we can see that the faces of the "Form" object cannot be defined randomly. Furthermore, we cannot stop here because we do not control the order following which the atoms are displayed. Without doing this, we cannot know that the atoms that are closer to the viewer are drawn after the ones that are further away. If this happens, the objects will not be realistic: atoms that should be in the back will overlap closer atoms.

    Finally ! We now have a simple working 3D engine ! Our personal goal was to understand the development that we have just briefly explained to you, as well as the mathematics behind it. We did not want to apply formulas without understanding them, as most programmers do today. Indeed, a programmer can create an application similar to ours without even having learned any advanced mathematical concepts. However, he would not learn much from creating an application like ours. Furthermore, many features could be added to 3DMOL at the moment: lighting, textures, etc. However, adding these would have taken us much more than the fifteen weeks allotted to realize the project.




(Screenshot #2: C6H12 (boat) in version 7)



Programming error types
The following error types are defined to help comprehend the application of the scientific method in programming.

    Because no one is perfect, it is very probable that a programmer will make many errors during the construction of his software. This is a natural and inevitable process. Usually, these errors are harmless: the application does not start or ends unexpectedly. However, certain errors are more serious: they cause the computer to halt. A good programmer must be able to prevent all types of errors and know how to locate and correct them when they happen.

Syntax errors:
    This type of error is the simplest of all. Each programming language has strict syntax rules; if they aren't respected, the software cannot be compiled (transformed from source code to an executable computer application). For example, if a command must be used like this:
        Return();

    A syntax error would be caused if the programmer had written it like this:
        Retunr() ;

    Thus, syntax errors are usually caused by typing errors, the programmer not paying attention or because of a lack of the programming language. These errors are found by the compiler (the software that converts source code into executables) and are therefore easy to locate and correct.

Logical errors:
    Logical errors are the hardest to locate. In fact, we deduct their existence when our software behaves unexpectedly. Here is an example where a programmer would want an action to happen only if a variables value is equal or higher to zero:
        If ( myNumber is smaller than 0 ) and ( myNumber equals 0 )
            Return();

    However, the programmer will notice that the action never happens. This is a logical error because the operator "AND" and the programming requires that both terms compared with AND be true for the command to happen. In our example, a number can never equal 0 at the same time that it is smaller than 0. That is why we must use the operator "OR".

        If ( myNumber is smaller than 0 ) or ( myNumber equals 0 )
            Return();

    Usually, logical errors are more complex, but the example given help you comprehend that they are errors caused by the programmers erroneous thinking during the softwares construction.

Conceptualization errors:
    This error type is the worst and the most difficult to correct. A conceptualization error is caused by bad planning by the programmer during the conception of the application (before he even starts programming). This error type is similar to the problems that computer programmers had to correct before the start of the year 2000. A few programmers from the 80s defined the "Date" object by only two digits to represent the year. They quickly realized that years needed four digits because when they reached the year 2000, old applications and operating systems thought the year 1900 had arrived.



Application of the scientific method in software conception (general)

Problem:
    An application is needed to realize a certain task.

Hypothesis:
    The programmer can create an application that will fulfill the requirements.

Method:
    The programmer must first create the structure for the software that will resolve the problem. It must not be too detailed: it must be brief and concise without being too superficial.

    Next, he must use the structure he created to build the application in the language of his choice. With each new addition, he must test the software and make sure that everything is working normally. Only then can he proceed with the creation of the application.

Result:
    When he is done, the software works as wanted. If necessary, certain modifications that were not originally planned are made to the software.

Conclusion:
    Our hypothesis is verified, we have been able to create the desired application.



Application of the scientific method in the resolution of logical errors (specific)

Problem:
    Our application has unexpected behaviour.

Hypothesis:
    We can locate the error and correct it.

Method:
    In the previous situation where we had a logical error, the action was never performed. First, we would verify the conditions that have to be met for the action to happen.

    If we notice the error immediately, we correct it. If not, we must try to comprehend why it doesn't happen. We could start by displaying the variable myNumber to the screen before our verifications. Here, we notice that the number can be equal or greater than zero. Therefore, the error is not before the current line. However, when our number is equal or greater than zero, nothing happens. We can deduct that the error is located within the line that starts with"If", or later. By analyzing this line, we understand the error and correct it.

Result:
    The error is corrected and the application works as wanted.

Conclusion:
    Our hypothesis is verified, we have been able to correct the error.



A note from the authors - Introduction - The application
The mathematics behind the project. - Discussion





Jason  
( 2001-05-24 )  




Read this article in French




Back



Français - English