2D Texture Mapping

This article describes how we can add textures on existing surfaces. That way we can make objects more realistic and fancy. This method is called Texture Mapping

Loading images to use as textures

Until now we were only able to save rendered images. It is better to use some pictures (of yourself, your pet, friends etc.) as textures. Anymaps may have a simple structure, but we still need a parsing tool to get the informations we need.

Anymaps can be both in text and binary form, therefore we need 2 different parsers. The header is always text, but we need to look for "#". This symbolizes a comment until newline "\n" approaches, similar to "//" and "/*...*/" in C, C++ and Java.

My idea for an ideal PNM parser looks like this:

1. get file content as string
2. erase first characters from "#" to next "\n" (header only allows 1 #)
3. put string into a stringstream (#include <sstream>)
4. get header information: sstream >> magic_number >> width >> height
5. if magic_number is neither "P1" nor "P4" (PBM), stringstream >> color depth
6. read color codes depending on ASCII (P1, P2, P3) or BINARY (P4, P5, P6) format

Stringstream ignores whitespace and newline when using input operator ">>". It also casts them into strings and numbers.

Setting Texture Anchor Points

The easiest method which works for most 2D graphics is by assigning texture anchor points from 0 to 1. We do that by getting MIN and MAX for each point of an object and calculate the ratio for each point in our Object2D.

These u and v values can be saved as Vector2D in a Surface2D which got extended by a reference of a Texture object and 3 anchor points. It is important that the position of these points are the same as Surface points. So don't mix them up or our Texture might look strange when rendered.

Textures

In our framework we will connect a texture with a picture. Important are the differences between object coordinates, texture coordinates and pixel coordinates. Pixel coordinates are limited to a picture's size while world coordinates are infinite. Textures can be used on multiple objects, but each object, or rather surface, can use only one texture at a time.

The easiest object to put a texture on is a rectangle, because it already looks like a frame to a picture. But remember, we use 2 triangles for 1 rectangle (triangles are easiest surfaces in computer graphics). That means we need to define texture coordinates for some points in a rectangle twice.

The first thing we do is create a Texture object and assign an Image to it. With the coordinates u and v containing values between 0 and 1 we get pixel coordinates by calculating:



But using a simple multiplication with width and height retuns floating point numbers. The only correct pixel value can be found at its center, but always hitting this point is quite impossible. We need an interpolation between 4 pixels

In aboves picture we see a 3x3 image, visualized with a center dot for each pixel. From Surface2D we received the following values for u and v which results in the following pixel coordinates (marked with a blue dot):





Our priority pixel is ImageColor(1,2), the center would be at 1.5 and 2.5. Calculating the difference between pixel coordinates and priority coordinates we get for x +0.2 and for y -0.3. This means that we also need the following pixel colors and interpolate first for each row and for each color, placing x and y as the top left coordinate:

The result is a mix of 4 pixels calculating an average color.

Getting Texture coordinates from Screen coordinates

The usual render routine starts with transforming object coordinates into world coordinates and from them to screen coordinates. Only the world coordinates for each Surface2D gets transformed, the texture coordinates stay untouched. But we can only get x and y from render algorithms like rasterization. To get u and v we start with the following formula for calculating triangle coordinates:

There are 2 ways on getting scalar values s and t.

Calculating s and t directly

We calculate s and t directly by solving above equation after s/t. To save some space we use v1 and v2 which is equal to (P1-P0) and (P2-P0). Normally "P" is unknown, but in that case we know the point and can use v as (P-P0).

The point it inside of the triangle if the following conditions are fullfilled:

Using Barycentric coordinates

Another way to get s and t is by using Barycentric coordinates. To understand the connection we need to change the formula to calculate a point of a triangle:



We could say that (1-s-t) can be called r, but barycentric coordinates work with greek letters. So the formula is like

With the condition:



A point P forms 3 subtriangles with each corner point of the original triangle. α, β and γ define the ratio of the subtriangle's area on the opposite site of the belonging point compared to the area of the original triangle.

This means we can calculate barycentric constants like this:



If you are sure that point P is exactly on the triangle and not a bit above/below it, you can also calculate α = 1 - β - γ. But this certainty only exists in 2D, not in 3D.

After that we can use β and γ as constants s and t from our triangle formula and use that in our texture formula which is equal to that of a triangle.

Framework

I made almost no changes to the framework. The only classes with major changes are

• Image.h, Image.cpp for loading Portable Anymaps
• Texture.h, Texture.cpp for getting pixel color from image
• Object2D.h , Object2D.cpp
• Renderer2D.cpp rasterization to except coordinates as input for getting pixel color
• Scene2D.h, Scene2D.cpp to save a list of Texture objects as Map

I skipped the part where you can change texture coordinates on objects manually, I leave that to your skills ;). I also added 2 example pictures (found in trip advisors) as PPM in the repository. With my settings in main.cpp I get the following output

Please take a look at the two rectangles showing a picture of Eiffel tower each. The left one got linked with a texture after tranformation, the right one before transformation.

Conclusion

We learned how to load a Portable Anymap, put it into a texture and link a texture to a 2D object so that it can automatically set texture anchor points to each point. This was the final chapter about 2D rendering, there is hardly anything to be added. You should now be able to use textures and create your own 2D objects (like triangles or even polygons).

The next issue is finally the start of 3D rendering. We will need Object3D classes put into a Scene3D. We will extend rasterization algorithm to also consider pixel depths, calling it a depth buffer.

See you in the next issue.

Repository

https://github.com/rumpfc/CGG/tree/master/cgg03_2D_texture_mapping

Tested with:

• Visual Studio 2013 (Windows 8.1)
• GNU Compiler 4.9.2 (Ubuntu 12.04)

2D Transformations and Viewing

Transformations are important to place geometric objects in a scene. Not everything should be parallel to x- and y-axis and sometimes objects should be larger/smaller.

In the last post we used pixel coordinates to draw objects on a screen. This time we use a cartesian coordinate system which we will transform into screen coordinates step by step.

  

Cartesian Coordinate System

Pixel Coordinate System

Objects

Each object will contain a list of points, a list of lines where each start and end point of these lines target 2 points within the points' list and a list of triangles consisting of 3 points of the points' list. This will make it easy for us if we have to transform objects.

To draw these objects we use an algorithm similar to OpenGL's rasterization. Triangles are perfect with rasterization, therefore we use this to fill our objects. It sounds confusing, but even a triangle has a triangle. To avoid confusion we will call these classes differently: Triangle2D derived from Object2D and Surface2D (no derivation) for rasterization (drawing).

After this we use Bresenham's algorithm to draw boundary lines of our objects. We will skip complicated polygons and stay with simple objects:

• Rectangle2D (lines and fill)
• Ellipse2D (lines and fill)
• Triangle2D (lines and fill)
• Polyline2D (lines only)

Transformations

Transformations can be divided into

• Translation
• Rotation
• Scale
• Mirroring

Translation

Also called move. It moves points along x- and y-axis to its new position. You an simply calculate:

  and  

You can also use matrix multiplication to get the new position, but therefore you need homogeneous coordinates, which is always 1 in our program.

Translation by +4 and +5

Rotation

When we talk about rotations, we mean to rotate around the origin of our cartesian coordinate system.

The calculation of these new points originated from existing x and y values which have a certain angel to x-axis plus an additional angel θ:









This can be described in the following homogeneous matrix multiplication:

Scale

Scaling an object means to stretch it along x- and y-axis.

Calculations applies in multiplying x and y values by a scale value sx and sy:.

Like rotation and translation, we can use a homogeneous matrix calculation

Viewing

Imagine holding a picture frame in your hands and looking through it. You will see certain objects within that frame.

Now imagine that you have some squares in that picture frame representing your pixels (see second figure). Each object covers certain pixels with their color. Even though you see a 3D scene in your 2D picture frame right now, transforming a 2D scene in a 2D picture where our frame can be anywhere of any size works similar.

First we need to place our Viewport (red rectangle) in our coordinate system and see where our black point is located (here 0.5/1.0).

Our aim is to create a normalized square where our point is somewhere between -1 and +1 in both x- and y-direction. Any value outside of our scale means it is outside of our viewport and therefore we have to clip it (next issue).

Last but not least we use this normalized square to get a fitting pixel coordinate for our point. Consider that Point (-1/+1) represents pixel point (0/0) and Point (+1/-1) represents (width/height), depending of our image size. In other words: x-direction is like always, while y-direction is opposite..

First we scale the point by width/2 and height/2, mirror it along y-direction (y*(-1)) and translate it by width/2 and height/2. After that, we know where to draw our picture on our picture with x between 0 and width and y between 0 and height..

Our Camera2D will handle the creation of the correct TransformMatrix2D, We will also add a camera rotation, in case that we don't want to have a normal view. Our rotation happens to move counter clockwise (to the left), which happens when you rotate a camera clockwise (to the right)

Graphic Pipeline

Now that we know how to transform objects and how to calculate them to proper screen coordinates, we need to define the correct order of this:

1. Object Coordinates
1. scale
2. rotate
3. translate
2. World Coordinates
1. Rotation around View Center
2. Normalization from -1 to +1
3. Screen Transformation from 0 to Width and 0 to Height
3. Screen Coordinates

Rasterization

We already know how to draw a line, but we still don't know how to draw a triangle (the easiest object in the world) and fill it. Rasterization is a fast way and ideal for rendering triangles on a frame buffer (our Renderer). Normally we also need a z-buffer to figure out which pixel is closer to our camera lense (or our eye). But because we use a 2D scene we can ignore this and simply draw on our picture.

Our first task is to get our 3 points of the triangle and sort them along y-direction with P1 being the upper most point, P2 the middle point and P3 the lower most point. If two points happens to have the same y value, we also sort along x-direction so that we can keep looking left-right.

Under normal circumstances we split our triangle into 2 parts. The middle point (here P2) is going parallel to x-axis. Inspired by Digital Differential Analyzer (DDA) we calculate a left border (P1->P2) and a right border (P1->P3) and walk along that border.

We stop at each Y.5 value in y-direction and start walking in x-direction waiting at each X.5 value. as long as we are within both borders we can color that pixel and continue going torwards right border until we step outside. Then we go another step along y-direction and repeat the same process until we reach P2. In our 2nd part we will have 2 new borders (here P2->P3 and P1->P3), doing the same work like in part 1.

Rasterization: 1st part in blue, 2nd part in orange

After rasterization our triangle looks like this:

Consider that a triangle can also look in a different direction so that left border is (P1->P3) and having 2 right  borders (P1->P2 and P2->P3). Calculating a cross product (P1->P2 x P1->P3) helps us figuring out in which direction a triange may look.

Triangle looking in opposite direction

Framework

There are hardly any changes in our already known classes. I changed private Painter::drawLine() method into Painter::bresenham(), because I want to add another line drawing algorithm called DDA which also works for floating point numbers. Bresenham is only accurate with integer values.

Our new render class is called Renderer2D, it contains a Camera2D and a Scene2D instance. A scene has a list of Object2Ds, like Ellipse2D or Rectangle2D. I limited it to these 2 types because they are the easiest to implement. Both are created at coordinate origin.

The most difficult part is to create points which describe the border of an object and how to connect them with border lines and surface triangles. A rectangle consists of 2 triangles, which will be saved as Surface2D. For an ellipse we choose a pivot point and connect it with 2 other points on the border line which are neighbors. It would look like a fan.

Renderer2D first draws some lines which forms a cartesian coordinate system. This helps us to identify if our objects are drawn correctly. Next we draw each Object2D by using rasterization to fill it and Painter to draw lines. You will also notice that we transform the coordinates in Renderer2D::render(). That's because each object can move freely in the world, but every person sees them in a different view.

main.cpp  Scene2D.cpp

With the settings in these 2 source files we create an image which looks like this:

Summary

Our framework finally has basic finally has many basic elements needed for modern computer graphics, except for the fact that we will never use GPU. We learned How to transform objects and how to calculate each value into screen coordinates. We also learned rasterization, a render algorithm which is also used in OpenGL.

In the next issue we will discuss textures and how to add them on a object. We will change Image so that it can load PPM files and transform them into a Texture.

Repository:

https://github.com/rumpfc/CGG/tree/master/cgg02_2D_transform_viewing

Tested with:

• Visual Studio 2013 (Windows 8.1)
• GNU Compiler 4.9.2 (Ubuntu 12.04)

First Drawings

The best way to understand the future structure of our test application is to view a small class diagramm:

It describes our Render classes. We use Renderer as abstract base class which contains a Color buffer and the size of our buffer (width * height). From Renderer we derive one drawing class (RendererSimipleDrawing) and two additional abstract classes (Renderer2D and Renderer3D). We ignore the latter ones for this section and continue with some other important stuff for this post.

Update: Mathtools

Mathtools.h, Mathtools.cpp

We add a function pixelIndex(width, row, col) which returns an index of a 1-dimensional array according to row, column and width of a color buffer.

Color

Color.h, Color.cpp

This class contains color informations in RGB format (you could also add an alpha channel, but there is no actual need for that). Color channels can be combined and calculated similar to our Vector classes, with the difference that there are no dot and cross products.

red, green and blue color channels consists values between 0.0 and 1.0. We only have to consider that certain user inputs might be outside of our color scale (in constructor and setter).

There are 3 possibilities to change color:

• setColor(float r, float g, float b)
• setColor(float color[3])
• setColor(int colorcode)

where floats consists values between 0.0f and 1.0f and colorcode is written in 0xRRGGBB format.

IMPORTANT: DON'T FORGET 0x BEFORE WRITING COLOR CODES

Last but not least getter methods can return colors as float values AND as 8Bit color values. This is very important on creating Images in PPM.

Image

Image.h Image.cpp

The Image class is similar to Renderer class, with the difference that we can't "render" anything. It needs width, height and a color buffer as input, We might still change color of a single pixel of it with at(row, column). Normally we use a coordinate system where x goes left right and y goes from bottom up. But an image uses x left right and y top down.

The most important part of Image is its save method to create an Portable Pixmap (PPM) file. The structure looks as following:

P6 <width> <height> <max color> <RRGGBB><RRGGBB><RRGGBB>....

P6, width, height and max color have to be written in ASCII code, while the color for each pixel is in binary code. Example of the head line of a PPM file (above: Ascii, below: binary in hexdecimal code)

P6 640 480 255 <colors>

50 36 20 36 34 30 20 34 38 30 20 32 35 35 20 <colors>

• magic number P6 = 0x5036
• space = 0x20
• width 640 = 0x363430
• space = 0x20
• height 480 = 0x343830
• space = 0x20
• max color 255 = 0x323535
• space = 0x20

afterwards binary color codes are displayed (i.e. yellow = 0xFFFF00). That's why we need Color::getRed8B(), Color::getGreen8B() and Color::getBlue8B().

Painter

Painter.h, Painter.cpp

Finally, the class where we can draw something. This class has as attributes:

• renderer (to draw onto)
• line color
• fill color
• fill (bool)

and methods

• setLineColor(...)
• setFillColor(...) (sets fill attribute to true)
• setFiller(true or false)
• drawLine(...)
• drawRect(...)
• drawEllipse(...) (also to draw circles)

All drawing methods are based on Bresenham's algorithm to draw lines (even fillings xD) and border of ellipses. Because we don't use transformations (yet), we can simply consider that all fillable objects (rectangles and ellipses) are parallel to x- and y-axis. Except for using a loop which goes from one border (width and height) to another we simply draw a line of the filling color.

A bit tricky is filling out an ellipse/circle: I put in an additional variable lastDy to ask if dy was already used for filling. If not, draw a line from left to write of the current row.

Renderer (abstract)

Renderer.h, Renderer.cpp

Abstract class from which we derive other classes having the same important attributes:

• color buffer
• width
• height

and our most important methods

• initBuffer() (preparing our buffer)
• setBackgroundColor(...) (3 different possibilities)
• colorPixel(x, y, color) to color a pixel (x for column and y for row)
• getColor(x, y) to get and edit the color of pixel x/y
• createImage() puts color buffer into Image class
• render() abstract method we need to override later. needed for drawing

RendererSimpleDrawing (derived from Renderer)

RendererSimpleDrawing.h, RendererSimpleDrawing.cpp

This class is derived from class Renderer. There is nothing special about this class, except that we override render() so that we can draw something. We use Painter to draw on a Renderer.

The current render function creates the following picture:

Summary

We added quite a lot of new classes in our application and created the fundamentals for future algorithms. In the next issue we will discuss 2D transformations more clearly. Therefore we create a 2D objects which contains lots of points and lines to be drawn. Except for Painter::drawLine(...) we won't be able to use the other drawing methods like before. Even ellipses will consist of multiple lines, forming an "infinitygon".

Like always, you can find everything in my Repository. Code was compiled and tested with

• Visual Studio 2013 (Windows 8.1)
• GNU 4.9.2 (Ubuntu 12.04)

See you in my next post.

Basic Math classes

Let us beginn with fundamental elements for our algorithms: Vectors and Matrices.

I used 2 classes for both 2D and 3D Vectors:

Vector2D: 2-dimensional vector and point
Vector2D.h, Vector2D.cpp

Vector3D: 3-dimensional vector and point
Vector3D.h, Vector3D.cpp

• length() returns the length of a Vector
• normalize() reduces x, y, z so that Vector's length = 1

I admit at this part that I'm sort of lazy and I don't really see a programming difference between points and vectors. That's why I use them in one and the same class. You will also see that I overloaded operators which returns a Vector:

• Vector + Vector
• Vector - Vector
• Vector * scalar
• Vector / scalar
• scalar * Vector

Actually not really needed, but I also overloaded operator for Dot and Cross products:

• Dot Product: Vector * Vector (2D/3D), important for angles
• Cross Product: Vector % Vector (3D only), important for surfaces

That way I'm able to use Vector class like any other number data type (int, long, float, double etc.) and - unlike Java - don't need to write confusing calculation methods (add, sub, mul, div etc.)

I also used 2 classes for both 2D and 3D Matrices:

TransformMatrix2D: 3x3 Matrix for 2D coordinate transformations
TransformMatrix2D.h, TransformMatrix2D.cpp

TransformMatrix3D: 4x4 Matrix for 3D coordinate transformations
TransformMatrix3D.h, TransformMatrix3D.cpp

These two classes' only job is to setup transformation matrices. We have:

• Translation (2D and 3D)
• Scale (2D and 3D)
• Rotation (2D and 3D around x-, y- and z-axis
• Mirroring (2D only)

There is no single method where you can combine several transformations. The only way to do so is by multiplying them altogether. Therefore I overloaded * operator.

• Matrix * Matrix (2D and 3D)
• Matrix * Vector (2D and 3D)

We have no use for "+" and "-" operators, so I skipped that part.

Last but not least I provided some Mathtools to the project I might think very useful:

Mathtools.h, Mathtools.cpp

• Direction from one Point/Vector to another (destination - start)
• Distance between two Points/Vectors
• Dot- and Cross products
• Methods which return correct transformation matrices (even in combination)
• sin(x) and cos(x) where x is in degree (for human useage)

There might be a chance that we will include additional methods to this class, but I think I mentioned most of it. In the next issue we will setup a render class and our first graphical output in Portable Pixmap (PPM) format.

In addition I will describe some methods for coloring pixels, from simple ones to lightly complex ones. We will keep it with lines and circles (a rectangle has 4 lines ^^ ). It features drawing:

• Lines
• Circles
• Ellipses
• Rectangles
• Polygons
• Polylines

See ya in my next post.

Feel free to fork my repository and try the code yourself, but don't change it in master branch. Source code was compiled with Visual Studio 2013 (Windows 8.1) and GNU 4.9.2 (Ubuntu 12.04). If someone has a clue about improving my Makefile I'm thankful

Links:
Repository for that post

Welcome to Computer Graphics Guide

Hello and congratulations that you found this blog. You will learn here many fundamentals you want to know about computer graphics.

My name is Christian, I'm a computer scientist student and a mathematics tutor. I specialised myself in geometry, analytics and computer graphics algorithms. My vision is to show the maths and programs behind computer games (Legend of Zelda, Assassins Creed etc.) and computer animation movies (Finding Nemo, Shrek, How to train your Dragon etc.).

Every post will explain some maths of the current topic and will contain source codes (mostly in C++, later in Java too) which will explain everything. Having a functional progam shall help for a better understanding.

Each source code will only contain standard C++/Java libraries, so that you can compile and run the program immediately. I don't think it's a good idea to add special graphic libraries like OpenGL or DirectX, because there is no way to see grapic calculation processes.

Of course you need something what you can see. I will use (in C++) Portable Pixmaps (PPM) as image files. They don't use any compressions, but you also don't need to add libraries like OpenCV or LIBPNG for PNG files.

I hope you will enjoy my posts.
lg Christian