3D algorithm

Look up coordinate transformations, perspective projection, and rasterization. Basically, you'll be reimplementing parts of the GPU pipeline, in the form of a software renderer. Knowledge of linear algebra helps a lot if you want to understand half of the code you're writing.

It typically goes roughly like this:
- transform each vertex to world coordinates, if it's not already done, this is useful if you want to have multiple instances of the same mesh without duplicating vertices, for instance suppose you want to have two bunnies side to side, you could duplicate each vertex to make two separate bunnies, or you could instead just reuse the same mesh, but simply moving each vertex in the second bunny off to the side (translation)
- transform each vertex to camera coordinates (rotating the world around the camera, so that you're facing what you want to face)
- transform each of those vertices to perspective coordinates (so that vertices further away from the camera tend to the point at infinity, giving the illusion of depth)
- from this, work out where each vertex would appear on the screen, in normalized screen coordinates (with coordinates ranging from -1 to +1 in X and Y dimensions) this is the step where you project your 3D vertices on your screen
- upscale these vertex locations to your desired resolution (e.g. 1024 * 768)
- for each pixel on the screen, work out which triangle it belongs to (depending on how you defined triangles, e.g. triangle list or triangle strip, or even using indices) this is the rasterization step
- shade the pixel (often you interpolate important data like normals, etc.. from the three vertices of the triangle)

As you can see, it can be a lot of work, and that's a very high-level overview (I ignored the depth and stencil buffers, as well as a lot of other stuff) but it's a good learning exercise. Make sure to take it step by step so that you don't get overwhelmed!

A billion percent thank you!

In Win32 there are some standard functions for example: SetWorldTransform, SetGrapicsMode, etc. and structs like XFORM.
Should I make any use of those functions and structs or should I rather make my own ones?


Kind regards,
Jonathan

In Win32 there are some standard functions for example: SetWorldTransform, SetGrapicsMode, etc. and structs like XFORM.
Should I make any use of those functions and structs or should I rather make my own ones?

I remember those functions, they seem to be remnants of some past era of software rendering using GDI (or they might be hardware-accelerated and used to draw desktop controls, I'm not sure). I wouldn't use them especially if you want to learn how transformation matrices work, since they hide all of that. All you really need is a form to display the results on, and a 2D array of pixels to render to, but of course you can use them if you find they are helpful. But you can absolutely do 100% of the rendering and computations without using built-in functions. You can even make your own vector and matrix class and roll with that, and I feel this is important if you've never done it before and are interested in low-level rendering.

It's up to you how deep you want to go. If you want to build on Win32 GDI to create your software renderer, you can absolutely do that and it's still fun (though you'll have to deal with the API, and you might not find as many tutorials as you'd like), or if you prefer to do everything from scratch, that's fun too but be ready to do a lot of linear algebra math!

By the way, re-writing existing code is not useless. It's important if you want to learn. Nobody would tell a beginner not to code Pong because it's already been done! It's only bad to reinvent the wheel if you want to get stuff done quickly, like a game. But If you're doing it for fun or for experience, reinventing the wheel is the right thing to do.

EDIT: The GDI API seems to be limited to 2D, so you might not find much use for GDI beyond accelerated pixel manipulation. I could be wrong though.

I'm looking up some information what GDI exactly is and this is a quote from wikipedia.

Simple games that do not require fast graphics rendering use GDI. However, GDI is relatively hard to use for advanced animation, and lacks a notion for synchronizing with individual video frames in the video card, lacks hardware rasterization for 3D, etc. Modern games usually use DirectX or OpenGL instead, which let programmers exploit the features of modern hardware.[/quote]

What makes DirectX a fast graphics renderer? How you decide the speed of rendering?
I just want to get low-level what programming concerns. I really want to get the knowledge into my head how it's done.
GDI only limited to 2D, how do I get the 3D in my program then? I'm assuming I need to calculate every pixel and draw them manually, please correct me if I'm wrong.

I want to achieve real-time rendering. Dragging a 3D model into your window and be able to translate, scale and rotate in your project.
But that is not for now, first the baby steps. But I can't do this alone sadly enough. Need some help from people who have experience in this because I can't find almost anything that helps me. maybe I'm not looking in the right place.


Kind regards,
Jonathan

Your graphics card already has all the steps I highlighted in my first post implemented, in hardware (not software). This means you can pump ridiculous amounts of triangles in it, and shade them in complex ways with multiple texturing and stuff and it'll still run in realtime. Furthermore, your graphics card is the component that's connected to your display monitor, and since the frame that's about to be rendered exists on the graphics card, it's very easy to send it to the screen. On the other hand, if you're using software rendering, then the frame is in system memory, and must be sent to the graphics card before being displayed, which is quite expensive (CPU to GPU transfers and vice versa are quite slow).

If you want to achieve realtime rendering, that is possible to some extent on a software renderer, but you certainly will not achieve the same amount of speed that can be achieved on a dedicated graphics card, and not with ease. The hardware is just superior in terms of performance. Unfortunately, you cannot really learn from hardware, so if you really want to know how it's done, you want to look at software rendering, which is great for learning, but remember it'll probably be quite slow without using a lot of optimization tricks and not using too many triangles.

Now it depends on your definition of "real-time" and "3D model". If you're talking about white triangles on black screen, on a model with like 10000 triangles, then sure - easily real-time. But if you want to draw a nice 1M polygon model with texturing and lighting... it's going to be harder for your software renderer than for the graphics card.

This is not to discourage you - graphics cards are designed with graphics performance in mind and are meant to be faster than processors for these kinds of operations, that's why you don't see a lot of software rendering around. But to learn the inner workings of graphics cards, there's nothing better.

I would like to write a small copy of DirectX. How do they handle the vertices and rendering of 3D models? How should it be handled for an optimal framework/engine?
If my GPU can handle all the math, how can I render my 3D model with it? I still need to use some math from your first post or don't I?

I'm looking up coordinate transformations and it's quite fun.
And how about particles? Like when I have 1 million particles. How should I best handle them? Do I need to do all calculations and rendering on the GPU? Or are there better/faster ways?

You are helping me already but I'm still a bit confused about how it all works with the gpu / cpu thing. I want to get an optimal render system for low poly models with materials, shaders, lightning, bouncings, etc. I know the pipeline for the graphics rendering but I can't go any further than the first step at the moment. For example I want to be able to load a whole environment like COD with all players, bullets, effects in it.


Kind regards,
Jonathan

I would like to write a small copy of DirectX. How do they handle the vertices and rendering of 3D models? How should it be handled for an optimal framework/engine?
If my GPU can handle all the math, how can I render my 3D model with it? I still need to use some math from your first post or don't I?

I'm looking up coordinate transformations and it's quite fun.
And how about particles? Like when I have 1 million particles. How should I best handle them? Do I need to do all calculations and rendering on the GPU? Or are there better/faster ways?

You are helping me already but I'm still a bit confused about how it all works with the gpu / cpu thing. I want to get an optimal render system for low poly models with materials, shaders, lightning, bouncings, etc. I know the pipeline for the graphics rendering but I can't go any further than the first step at the moment. For example I want to be able to load a whole environment like COD with all players, bullets, effects in it.


Kind regards,
Jonathan

So basically you want to write a software renderer which runs on the GPU right?
Remember that DirectX and OpenGL can communicate with your graphics driver, and I'm afraid you as a developer won't have that luxury (if you want to call it that). This only leaves you with the option to resort to GPGPU solutions, and while it's completely possible to write a software renderer with these, you probably won't be able to beat or even come near the performance a library like DirectX or OpenGL will give you. The reason for this is that DirectX and OpenGL are able to use the rasterizer hardware available on your GPU, while GPGPU solutions aren't able to do so.


Now the essential question here (before I ramble on) is: Why do you want do write your own renderer?

If this is just for learning I'd say try to do a very simple CPU-based renderer and leave the GPU out of the picture (except for maybe presenting your final result to the screen), this will teach you a lot about how the entire rasterization process works without having to worry about CPU-GPU communication and all that stuff. Try to implement each of the steps Bacterius laid out for you in his first post completely by yourself, from writing your own structures for managing vertices and indices to writing systems which can transform and shade these for you to get a final texture which you can then present to the screen.
Writing a simple software renderer which can do all of this is a very rewarding and fun experience which will teach you a lot. If you implement this well you could even use it do some very basic 3D games.

If this is about writing a production-quality renderer I'm going to be harsh and say: don't bother.
You're talking about rendering millions of particles, and rendering a huge amount of objects, so I'm guessing that this is actually what you want to do. I know re-inventing the wheel can be a lot of fun sometimes, but trying to implement something like this will put you in a lot of nasty sticky situations, and in the end you'll have a system which tries to sub-optimally solve a problem for which we already have 2 fast and proven solutions (being DirectX and OpenGL), if you even manage to complete your renderer at all (and I'm going to be harsh again and say that this is very unlikely as you don't have any previous experience writing software renderers).

If you want to do simple 3d lines and such, an easy way to get going is to try simple perspective. This is what I played around with before I went into matrix math. You will probably get into matrices at some point, but if you just want something basic, you can start with this.

3d without rotation or translation:

A single perspective transform is as easy as this:

//sw is screen width, sh is screen height
//zcut is z plane cutoff (don't render anything closer to or behind z) WHY? z=0 is forbidden. z > 1 means point is in front of camera. z=-1 means point is behind camera. zcutoff of .1, .01 etc are reasonable.


int perspective(float x, float y, float z, int* sx, int* sy)
{
if (z < zcutoff)
return 0; //refuse to transform

sx = x* sw / z; //scale X by screen height and distance.
//So, an object sw pixels wide at Z=1 is the width of the screen.
//Z=2, half the widht of the screen. Z=.5, twice the width of the screen. etc
sy = y* sh / z;
return 1;
}


To draw a line in 3d:

void line3d( float x, float y, float z, float x2, float y2, float z2)
{
int sx, sy, sx2, sy2;
//only draws if both points are in front of camera
//later, if you want to get fancy, if one is in front, and the other is behind, you clip at z=zcutoff

if (perspective(x,y,z, &sx, &sy) && perspective(x2,y2,z2,&sx2, &sy2))
draw_line(sx,sy,sx2,sy2);
}


With the above snippets, you should be able to draw a 3d perspective object from the point of view of the origin.

To move the camera around, just subtract the camera position from the coordinates:


int perspective(float x, float y, float z, int* sx, int* sy)
{

x -= camera_x;
y -= camera_y
z -= camera_z;

if (z < zcutoff)
return 0; //refuse to transform
sx = x* sw / z; //scale X by screen height and distance.
//So, an object sw pixels wide at Z=1 is the width of the screen.
//Z=2, half the widht of the screen. Z=.5, twice the width of the screen. etc
sy = y* sh / z;
return 1;
}


With that, you should be able to move around the 3d environment, but view is constrained to always looking down the Z axis. But, its a start.

The last thing you can do, is allow camera rotation along the y axis (like wolf3d). It's been a while but if http://www.siggraph....tran/2drota.htm is correct, then:


int perspective(float x, float y, float z, int* sx, int* sy)
{

float xr, yr, zr;
//translate to camera position

x -= camera_x;
y-= camera_y
z -= camera_z;


//rotate 2D about y axis:

xr = x * cos(camera_angle) - z * sin(camera_angle);
zr = z* cos(camera_angle) + x * sin(camera_angle);
yr = y; // height does not change



if (zr < zcutoff)
return 0; //refuse to transform
sx = xr* sw / zr; //scale X by screen height and distance.
//So, an object sw pixels wide at Z=1 is the width of the screen.
//Z=2, half the widht of the screen. Z=.5, twice the width of the screen. etc
sy = yr* sh / zr;
return 1;
}



That should give you 5 degrees of freedom: You can move up/down, left/right, forward/back and rotate about Y. So, it's 'DOOM' controls. You can add another rotation to look up/down, but at the point you should consider trying to understand matrices.

I wrote a software renderer to the OpenGL 1 Spec last year, compiled it and linked it to QuakeGL. It worked pretty well.

This is the book that made software rendering click for me: http://www.amazon.com/Building-3D-Game-Engine-C/dp/0471123269/ref=sr_1_6?ie=UTF8&qid=1354824709&sr=8-6&keywords=3d+game+engine+programming+C%2B%2B

It's pretty concise and straight forward. Not one of those books that you want to copy the code verbatim out of due to it's age. You really need to read it and understand it. This is what i had after a few weeks with the book:

That's pretty cool. Writing a software renderer can be fun. I wrote my first 3d programs in dos qbasic using the simple perspective and rotation transforms I posted up above. Just lines and such. Made little wireframe cube mazes to walk through. Later I moved onto Borland C and messed around with filling triangles with solid colors, and tried some texturing, which I could get on the walls but never worked properly on the floors. I made the jump to OpenGL, and had to learn matrices. I did eventually play around with software rendering again, and figured out the floors, but it was so much slower than hardware.

I resisted matrices for a while because they didn't make sense: 4x4 for 3d? 4 dimensions? It didn't make sense. When I first started using matrices, I started with translation + 3x3 matrices. A lot of my code still uses 3x3 matrices to track rotations. They make sense for 3d: for each axis in the rotated frame, there are 3 components in 'world' coordinates that make up those axes vectors. Now add in a translation. Now you have a 3x3 matrix and an awkward random 'add' for the translation. But, it just so happens if you put that 3x3 matrix inside a 4x4 matrix, put the translation on the side, and then pad out the rest of it with 0's or 1's, doing the 4x4 matrix multiply will do the same thing as the 3x3 matrix multiply, and then add the translation on. It's just a really cheap trick. Now you just get your CPU or GPU todo 4x4 matrix multiplies really fast, and then all your transform operations can be done by one heavy optimized math routine.

Thanks everyone!

Radikalizm, I'm not trying to make a commercial software renderer DirectX and OpenGL can't be beaten so I won't try to.
It's all learning purpose. You say that I first need to work with the CPU, how do I do that? How can I choose which one I can use to get my project running? I know the difference between both tho, cpu only does 1 thing at the time while a gpu does multiple things at the same time. But no idea when I'm using a cpu or a gpu.

DracoLacertae, thanks for the examples! So drawing lines isn't that hard to get in 3D Before I get on to it, I bought a math book which covers every mathematics what game programming concerns. So I hope to get a line or a 3D polygon on my screen today!

uglybdavis, nicely done!

It's all learning purpose. You say that I first need to work with the CPU, how do I do that? How can I choose which one I can use to get my project running? I know the difference between both tho, cpu only does 1 thing at the time while a gpu does multiple things at the same time. But no idea when I'm using a cpu or a gpu.[/quote]
If you're not sure, you're definitely using a CPU

You only "use" the GPU (at least the current generation) by programming little programs called shaders (in HLSL, or GLSL) which perform very specific tasks (e.g. transform vertices, or shade pixels). All the rest is done by the driver automatically. You don't actually write complete software on it. Everything that you code in C++ or C# or Java or whatever language, really, is done on your CPU.

It's all learning purpose. You say that I first need to work with the CPU, how do I do that? How can I choose which one I can use to get my project running? I know the difference between both tho, cpu only does 1 thing at the time while a gpu does multiple things at the same time. But no idea when I'm using a cpu or a gpu.

If you're not sure, you're definitely using a CPU

You only "use" the GPU (at least the current generation) by programming little programs called shaders (in HLSL, or GLSL) which perform very specific tasks (e.g. transform vertices, or shade pixels). All the rest is done by the driver automatically. You don't actually write complete software on it. Everything that you code in C++ or C# or Java or whatever language, really, is done on your CPU.
[/quote]
Damn, I messed up my mind then. Thank you for clearing this out!

That's why they introduced technologies like C++ AMP and CUDA which are basically extensions on top of C++, so that you don't have to bother with DirectX and OpenGL and their shaders. With these "extensions" you can just write your whole code in C++ and launch parallel kernels which are executed on the GPU.

But just start with a standard programming language running on solely the CPU and get your software rasterizer working on the CPU before you bother using a GPU to increase the performance.

Is Direct3D a separate set of API calls still or is it just all part of the same interface to DirectX? I would think getting a polygon on the screen in DirectX would be fairly simple.

I do recognize "SetGraphicsMode" as possibly a WinG call from back when keyboards were made with dinosaur bones.

I know the difference between both tho, cpu only does 1 thing at the time while a gpu does multiple things at the same time.

A CPU can do multiple things at a time when using multiple cores (and it can 'fake' doing multiple things on only one core), but it does indeed do this differently than a GPU
Modern GPUs are designed to handle wide SIMD instructions (doing the same operation on a larger set of data in parallel), hence their ability to do extremely fast floating point operations when compared to CPUs. Modern CPUs have SIMD instructions too though (like SSE on x86 architectures), but these are for smaller sets of data (mostly 128 bits).

Keep us posted on your progress by the way, I'm always very interested in these kinds of projects.

I will gladly post my progress but it will take a while, today I realized I better learn matrices through 2D and when I understand everything I'll change to 3D.

I'm making my own matrix class which will be supported with the function SetWorldTransform. This function works with XFORM but I'm not using this one. It's better to write my own calculations self so I can learn from it. When I got it all calculated I just put everything into an XFORM and transform the world. So when I understand the matrix and transform concept I go to 3D.

Or is there a better way to transform my object(rectangle, bitmap, etc)?
I know matrices needs to be used to transform such an object, but I mean, is there something else to transform my world with?

You might want to consider decoupling your renderer from systems such as GDI and use it purely as a back-end to present your final image, this will give you a cleaner system which is somewhat future-proof as GDI can be considered old right now.
You could eventually use a system like D2D as a back-end to present your image to the screen as well without having to make any changes to your renderer.

Have you ever written shaders before? If you haven't I'd advise to try and do some simple shaders in DirectX or OpenGL to get a feel for transformations and rasterization in general. They're a great instant-gratification kind of way to learn about all of this stuff, and it will probably make it easier for your to understand the steps you should take for a software rasterizer.
With a knowledge of shaders the concept of how to build systems for setting your own transformation matrices for your renderer becomes a piece of cake as well.

I would however be careful about writing your own matrix and vector implementations. They can be a great learning experience, but it's very easy to make small errors here an there when it comes to operations like matrix-matrix multiplications or matrix-vector multiplications, and those errors can introduce huge bugs in your renderer.
So if you intend to take the DIY route when it comes to math, be sure to write a ton of test cases before you actually start working with it, you want to make sure your math library completely works as intended.

Thanks for the help, I've made a colorshader last year, but I didn't understood a single line of code what I was writing. Shaders are quite hard to understand for me.

How does DirectX render his transformations?
I just made a matrix class that can translate, scale and rotate. Tested it and it works.
Don't mind how I use the methods. It's just a testing project.

Matrix matTranslate, matRotate, matScale, matWorld;
matTranslate.SetAsTranslate(-0.7f, -0.4f);
matRotate.SetAsRotate(80.0);
matScale.SetAsScale(0.5,0.5);
matWorld = matRotate * matScale * matTranslate;
Matrix::SetAsWorld(hDC, matWorld);

Rectangle(hDC, -1, -1, 1, 1);


This is what I use for my transformations:

Matrix::Matrix():
eM11(0.0f), eM12(0.0f), eM13(0.0f),
eM21(0.0f), eM22(0.0f), eM23(0.0f),
eM31(0.0f), eM32(0.0f), eM33(0.0f)
{
}

void Matrix::SetAsTranslate(float x, float y)
{
eM11 = 1.0f;
eM12 = 0.0f;
eM13 = 0.0f;
eM21 = 0.0f;
eM22 = 1.0f;
eM23 = 0.0f;
eM31 = x;
eM32 = y;
eM33 = 1.0f;
}

void Matrix::SetAsRotate(float radians)
{
eM11 = (float)cos(radians);
eM12 = (float)sin(radians);
eM13 = 0.0f;
eM21 = (float)-sin(radians);
eM22 = (float)cos(radians);
eM23 = 0.0f;
eM31 = 0.0f;
eM32 = 0.0f;
eM33 = 1.0f;
}

void Matrix::SetAsRotate(double degrees)
{
float radians = (float)(degrees/180 * M_PI);
eM11 = (float)cos(radians);
eM12 = (float)sin(radians);
eM13 = 0.0f;
eM21 = (float)-sin(radians);
eM22 = (float)cos(radians);
eM23 = 0.0f;
eM31 = 0.0f;
eM32 = 0.0f;
eM33 = 1.0f;
}

void Matrix::SetAsScale(float x, float y)
{
eM11 = x;
eM12 = 0.0f;
eM13 = 0.0f;
eM21 = 0.0f;
eM22 = y;
eM23 = 0.0f;
eM31 = 0.0f;
eM32 = 0.0f;
eM33 = 1.0f;
}

Matrix operator*(const Matrix& ref1, const Matrix& ref2)
{
Matrix mat;
mat.eM11 = ref1.eM11 * ref2.eM11 + ref1.eM12 * ref2.eM21 + ref1.eM13 * ref2.eM31;
mat.eM12 = ref1.eM11 * ref2.eM12 + ref1.eM12 * ref2.eM22 + ref1.eM13 * ref2.eM32;
mat.eM13 = ref1.eM11 * ref2.eM13 + ref1.eM12 * ref2.eM23 + ref1.eM13 * ref2.eM33;
mat.eM21 = ref1.eM21 * ref2.eM11 + ref1.eM22 * ref2.eM21 + ref1.eM23 * ref2.eM31;
mat.eM22 = ref1.eM21 * ref2.eM12 + ref1.eM22 * ref2.eM22 + ref1.eM23 * ref2.eM32;
mat.eM23 = ref1.eM21 * ref2.eM13 + ref1.eM22 * ref2.eM23 + ref1.eM23 * ref2.eM33;
mat.eM31 = ref1.eM31 * ref2.eM11 + ref1.eM32 * ref2.eM21 + ref1.eM33 * ref2.eM31;
mat.eM32 = ref1.eM31 * ref2.eM12 + ref1.eM32 * ref2.eM22 + ref1.eM33 * ref2.eM32;
mat.eM33 = ref1.eM31 * ref2.eM13 + ref1.eM32 * ref2.eM23 + ref1.eM33 * ref2.eM33;

return mat;
}

void Matrix::SetAsWorld(HDC hDC, const Matrix& mat)
{
XFORM form;
form.eM11 = mat.eM11;
form.eM12 = mat.eM12;
form.eM21 = mat.eM21;
form.eM22 = mat.eM22;
form.eDx = mat.eM31;
form.eDy = mat.eM32;

SetWorldTransform(hDC, &form);
}


The calculations I've written on paper first with help from a book. So I didn't copied anything from the internet. I'm getting the hang of matrices very fast with this book, next chapter is linear transformations!

But indeed, I'm using GDI and it's getting pretty classic. But I really don't want to use a single external library. Because it's too "easy" then.. I'm not trying to be stubborn. Any suggestions how I avoid the classic functions? DirectX also must use a classic way or are they working very low level and code all their rendering themselves?