WIP 3D Engine (Update : v0.07 screenie preview) [v0.06]

[Clyde]

welldone dude.

Just something I noticed, is when you run the exe straight from the archive, without extracting everything, on certain parts of your cubes theres a cyan pixel,

[Hezad]

thanks

Just something I noticed, is when you run the exe straight from the archive, without extracting everything, on certain parts of your cubes theres a cyan pixel,

huh ? lol it's weird, I DL'ed the archive from here and I don't see any cyan pixels. But it looks like there are some surprises on different computers :S

[Shockwave]

Possibly Clyde has a fucked up pixel on his monitor, I'd guess that he is using an LCD screen and it might be time to buy a new one

The mapping works really well by the way

Well done!

[hellfire]

Did you notice there are still some texture deformations when the triangles are close?

Yes, you definatly have some serious pixelshaking going on.
I can't tell if it's because of missing precision or if there's something wrong with your interpolation - your code is a bit "cryptic" to read there
But it's easy to find out: Use only a single polygon for the floor-plane (of course the shading won't work properly then).
To be honest, you should seriously clean and structure your code a bit, use meaningful names for variables, encapsulate parts and split the source-files.

[Hezad]

Shockwave : thanks ^^ Well I hope for clyde it's a bug in the code but I hope for my code it's a dead pixel on his monitor ... Strange situation :p

hellfire : Yeah sorry about the interpolation code, I wrote it a bit like a draft and I didn't organized and/or rewritten it yet. I'll try the "single polygon for the floor-plane" :p (in fact I used several planes for the floor to tile the texture since I didn't write the tiletexture routine yet :p)

Code: [Select]

To be honest, you should seriously clean and structure your code a bit, use meaningful names for variables, encapsulate parts and split the source-files.
I totally agree -_- the point is, organizing code is my main problem ! I often get into some inextricable mess with my code !

For the 3d engine, I though about a new type : SceneType in which I could store all the objects in the current Scene, and use it to render the whole scene. (for now, I must specify in my subs which object I wanna render... not very practical). Do you think it could improve the organization/readability of my code ?

Anyway, before working on this, I have red a lot of stuff here I have to code (optimizations mainly)

*Working on the frustum clipping*


edit : Just cheated the clipping to test something, here's a preview aah the 20 FPS are coming back ^^

[hellfire]

I dug out some old software-rendering code this evening to check how I did things myself back then, especially the perspective mapping (I attached a little example, you can use the mouse to rotate the object).

I though about a new type in which I could store all the objects in the current Scene, and use it to render the whole scene.

I would separate rendering and scene-management.
For the latter I use a simple tree to manage objects with hierachical-structures.
There's one base-type for all different kinds of objects (eg. camera, light, mesh, etc) which basically contains a current transformation-matrix.
Each mesh is assigned to a material-object which manages vertex-processing and rendering.
Each material has an own vertex-structure (and stores or generates all vertex-parameters, eg. texture-coordinates for environment mapping) and a polyfiller to draw the resulting polygons.
Clipping is done via Sutherland/Hodgeman in 3D Camera-Space as a template-class, so it can process different vertex-types.
To perform the actual rendering, I just have to iterate a list of materials (actually there two, one for opaque and one for transparent objects) and everything is done.

Some more technical aspects:
When performing clipping, your triangle will become a convex polygon with an arbitray number of vertices. For the beginning you'll probably just split it back into triangles.
However, most of the time your meshes will contain a reasonable number of quads (usually 3d-modelling is done by deforming grids). You should consider taking this into account in your polyfiller, so you don't have to draw two "half quads" all the time. Handling arbitrary convex polygons sounds difficult, but your polyfiller will become much more straight forward.
Here's some pseudo-code that might be helpful (based on Mats' article):

Code: [Select]

struct Vertex
{
   float x,y,z;
   float u,v;
};

void drawPoly(Vertex *vtx, int vertices)
{
   // we want to draw the polygon from top to bottom:
   // find the vertices with minimum and maximum y-coordinate
   Vertex *min_vtx = &vtx[0];
   Vertex *max_vtx = &vtx[0];
   for(int n=1; n<vertices; n++, vtx++)
   {
      if (vtx[n].y < min_vtx->y) min_vtx = vtx;
      if (vtx[n].y > max_vtx->y) max_vtx = vtx;
   }

   int min_y = ceil(min_vtx->y);
   int max_y = ceil(max_vtx->y);

   // calculate deltas (on first triangle)
   float delta1=  vtx[1].y - vtx[2].y;
   float delta2=  vtx[0].y - vtx[2].y;
   float d =  1.0 / ((vtx[0].x - vtx[2].x) * delta1 - (vtx[1].x - vtx[2].x) * delta2);
   delta1*= d;
   delta2*= d;
   float deltau=  (vtx[0].u - vtx[2].u)*delta1 - (vtx[1].u - vtx[2].u)*delta2;
   float deltav=  (vtx[0].v - vtx[2].v)*delta1 - (vtx[1].v - vtx[2].v)*delta2;
   float deltaz=  (vtx[0].z - vtx[2].z)*delta1 - (vtx[1].z - vtx[2].z)*delta2;

   // we are now tracing the left and right sides of the polygon

   // initially start both sides at the top vertex
   Vertex *left_vtx = min_vtx;
   Vertex *right_vtx = min_vtx;

   // the height of the left and right slopes (initially 0, forces calculation when entering the loop)
   int right_height=0;
   int left_height=0;

   // left and right slopes
   float left_x, left_dx; // x-coordinate
   float left_z, left_dz; // z-coordinate
   float left_u, left_du; // texture U
   float left_v, left_dv; // texture V

   float right_x, right_dx;

   // draw polygon top->bottom
   // the loop isn't really required here since we terminate in the slope-calculation when reaching the bottom-vertex.
   for(int y=min_y; y<max_y; y++)
   {
      // at the end of right slope: calculate next one
      while (left_height <= 0)
      {
         // at the bottom: done.
         if(left_vtx == max_vtx) return;

         // the polygon is expected to be counter-clockwise
         // starting from the top, the left side has increasing vertices, right side has decreasing vertices
         Vertex *v1= left_vtx;
         left_vtx++;
         // if we're at the end of the vertex-list, wrap to the front
         if (left_vtx >= vtx+vertices) left_vtx= vtx;
         Vertex *v2= left_vtx;

         // the actual number of scanlines for this slope
         left_height = ceil(v2->y) - ceil(v1->y);

         // can be 0 which means the next vertex lies in the same scanline: go straight to the next slope
         if (left_height == 0)
            continue;

         // calculate slope v1 -> v2
         // this is the delta for all vertex-attributes to get to the enxt scanline
         float inv_height= 1.0 / (v2->y - v1->y);
         left_dx = (v2->x - v1->x) * inv_height;
         left_dz = (v2->z - v1->z) * inv_height;
         left_du = (v2->u - v1->u) * inv_height;
         left_dv = (v2->v - v1->v) * inv_height;

         // subpixel-correction:
         // the vertex' y-coordinate is some floating-point number, while the scanline is at an integer y-coordinate (rounded up)
         // so we are already a bit further on the y-axis and the vertex-attributes should be updated accordingly:
         // add a fraction of the y-delta to compensate
         float prestep= ceil(v1->y) - v1->y;
         left_x = v1->x + prestep * left_dx;
         left_z = v1->z + prestep * left_dz;
         left_u = v1->u + prestep * left_du;
         left_v = v1->v + prestep * left_dv;
      }

      // right slope: same procedure
      while (right_height <= 0)
      {
         if(right_vtx == max_vtx) return;

         // walk backwards through the vertex array
         Vertex *v1= right_vtx;
         right_vtx--;
         if(right_vtx < vtx) right_vtx= vtx+vertices-1;
         Vertex *v2= right_vtx;

         right_height = ceil(v2->y) - ceil(v1->y);
         if (right_height == 0)
            continue;

         float inv_height= 1.0 / (v2->y - v1->y);
         right_dx = (v2->x - v1->x) * inv_height;

         float prestep = ceil(v1->y) - v1->y;
         right_x = v1->x + prestep * right_dx;
      }

      // round x-coordinates to whole pixels
      int x1 = ceil(left_x);
      int x2 = ceil(right_x);

      // subtexel correction:
      // since we rounded to the next integer coordinate, we are already a bit further on the x-axis
      // update attributes accordingly:
      float prestep = x1 - left_x;
      float u = left_u + (prestep * deltau);
      float v = left_v + (prestep * deltav);
      float z = left_z + (prestep * deltaz);

      // draw the scanline:
      for (int x=x1;x<x2;x++)
      {
         // ...
         u+=deltau;
         v+=deltav;
         z+=deltaz;
      }

      // interpolate left and right slopes
      left_height--;
      left_x += left_dx;
      left_u += left_du;
      left_v += left_dv;
      left_z += left_dz;

      right_height--;
      right_x += right_dx;
   }
}


[Hezad]

hey nice cube Thanks a lot for the code  I'm reading it right now I haven't a lot of C/C++ knowledge but I should understand the code after several readings. But there's something I don't understand :
AFAIK, Sutherland/Hodgman algorithm works on 2d polygons, so I'll need to project all polygons before using it, no ? So, should I code a quick clip with the view frustum (getting off the list all polys lying totally outside the view) and THEN, using the sutherland/hodgman algo on the remaining triangles to process the ones which are ON the frustum ( eg: two vertices inside, another one outside) ?

Sorry for asking so many questions ;o but before attacking optimizations and code organization with all the tips I red there, I'd like to have a good clipping code.

Oh and while I'm there, my perspective correct mapping is definitely not as correct as I'd like it to be .. The mapping on cubes is totally ok, but the one on the floor really looks like an affine texture mapping in fact (however, it's exactly the same sub used for the cubes and the floor ... strange o_O)

So my current ToDo list :
- Fixing the floor mapping bug
- Coding clipping

Future todo list :
- Optimize code/reorganize it
- TileTexture routine
- Mip-Mapping

[hellfire]

Sutherland/Hodgeman is usually applied in 2D-Coordinates, but it works just as well in 3D-Coordinates.
What I do is to transform all vertices into camera space, perform backface-culling and clip all remaining polygons to the view-frustum; in camera space this is extremely easy:
What's still left transformation-wise is just the perspective division:

Code: [Select]

x'= x / z
y'= y / zCoordinates (x', y') in the range -1..+1 are inside the view frustum; thus:
x > z : out on right
-x> z: out on left
y > z: out on bottom
-y> z: out on top
near > z: out on front
This resembles the clip-flags typically used by Sutherland/Hodgeman and is actually cheaper than performing clipping previous to transformation (which results in an additional dot-product per clipping-plane).

[Jim]

Division by 0...

1/0 = +infinity
-1/0 = -infinity
in fact
p/0 = +infinity
-p/0 = -infinity

Once you get an infinity in the fpu things will screw up.  Happens when your z is 0.  Often you can see if this is the case by adding
asm { finit }
to the inner loop in your code.  That resets the fpu and clears up the error, but it's slow, and you don't want to do this.

Division overflow...

With integers this can be a big problem...when you divide a 64bit number by a 32bit number, the result is expected to fit in 32bits, so...
00000001:00000000/1 is a division overflow, because the results is 00000001:00000000 which is over 32 bits long.
With float, the problem can still occur.   It happens when the z is very near 0 but the x or y are large, so

z = 0.000000001 x = 10000, y = 10000.
That would give x/z = 10000000000000000, which is possible to represent as a float, but probably not what you're expecting in your calcs.  And if you fed that to your triangle routine as an x coordinate you're going to take a very long time to draw a span!!

So, as hellfire has been trying to push you, you need to look at (at the very least) cohen sutherland hodgeman clipping to clip your polygons at z= some sensible value like 1 (near plane clip), and then to 3d clip (or at least 2d clip) after that.  That keeps the x,y,z in a sensible range, z will never be 0 or tiny, and you avoid all the the precision and range problems

Jim

PS, Yes, ZOOM should be removed from your perspective calc.  It has no real life analogy, it's a fudge to get round the above problems.

[Hezad]

Thanks for those informations I got it now ! Sorry for the time taken before responding but I wanted to finish clipping before posting a new message. But erm, since it's will take more time I expected, the less I can do is answering ! Just for info, what I got for the "clipping order" :

- First clipping (What poly is totally inside the view frustum ?)
- Backface culling on those polys (not implemented yet)
- Sutherland/hodgeman clipping for the triangles crossing the frustum (I'm pulling my hair out on this :p)


k++ to shockwave, hellfire and Jim. Thanks a lot !

[hellfire]

clipping [...] I'm pulling my hair out on this :p

Actually it's quite easy
Let's assume your vertices are already transformed into camera-space and all that's left is perspective division.
You first check for all vertices if it's outside of any planes of the view frustum and store the result in a bitmask.
As described above, the vertex/plane-test is simple in camera-space:

Code: [Select]

   #define CLIP_TOP 1
   #define CLIP_LEFT 2
   #define CLIP_RIGHT 4
   #define CLIP_BOTTOM 8
   #define CLIP_FRONT 16
   #define CLIP_BACK 32

   clip=0
   if -x>z then clip = clip or CLIP_LEFT
   if x>z then clip= clip or CLIP_RIGHT
   if y>z then clip= clip or CLIP_BOTTOM
   if -y>z then clip= clip or CLIP_TOP
   if z<znear then clip= clip or CLIP_FRONT
Note: I assume the negative y-axis going up
"And'ing" the clipflags of all vertices of a polygon tells if it's completely outside of any clip-plane (result is non-zero: skip it).
"Or'ing" the clipflags tells if the polygon needs any clipping at all (result is zero: draw it without clipping)

Now you go through the vertices of your polygon and check each edge (adjacent pair of vertices) if they are on different sides of a frustum-plane:
(I was too lazy to convert the syntax to freebasic)

Code: [Select]

   // dst: list of pointers to output vertices
   // src: list of pointers to input vertices
   // srcNum: number of input vertices
   int clipLeft(Vertex **dst, Vertex **src, int srcNum)
   {
      Vertex     *v1, *v2;
      int        n,num=0;
      int        c1,c2;

      v1= src[srcNum-1]; // start with the last vertex so we don't have to handle array-wrap
      for (n=0;n<srcNum;n++) // go through the whole polygon-array
      {
         v2= src[n]; // second vertex to check
       
         // extract the clip-information for the current plane (here: left)
         c1= v1->clip & CLIP_LEFT;
         c2= v2->clip & CLIP_LEFT;

         // if v1 is inside the frustum, just make a copy (pointer: cheap)
         if (c1==0) dst[num++]= v1;

         // if the two vertices are on different sides, create a new vertex on the plane
         if (c1!=c2)
         {
            // v'=v1+t*(v2-v1) intersects the clip-plane:
            // here: -v'.x=v'.z (see clipflags)
            float t= (v1->x + v1->z) / (v1->z + v1->x - v2->x - v2->z)
            // linear interpolation
            *scratch= v1 + t*(v2-v1);
            // update clipmask - remember that only the remaining and previously-set clip-planes are necessary to be checked
            scratch->clip= scratch->clipmask();

            dst[num++]= scratch++; // add to output (and point "scratch" to the next free vertex)
         }

         v1= v2; // next edge
      }

      return num; // number of output-vertices
   }
the output-array "dst" just stores pointers to the actual vertices because most of them just get copied and we just have to store the pointer then (some linked-list might work well, too).
"scratch" is a pool of temporary vertices so we don't have to allocate new memory (which is costly).
Just repeat the process for every clipping-plane. You just have to work out the edge/plane intersection-points (parameter "t"):
right: v.x = v.z
bottom: v.y= v.z
top: -v.y= v.z

For the resulting vertices all that's left to do is perspective transformation:

Code: [Select]

   z= 1.0 / z
   x= x*z
   y= y*z
   // the clipping-process ensured that all x,y are now in a range of -1..+1
   // we just have to scale them to the screen-dimensions:
   x= (1.0 + x) * xres * 0.5
   y= (1.0 + y) * yres * 0.5


[Hezad]

hey

You first check for all vertices if it's outside of any planes of the view frustum and store the result in a bitmask.
As described above, the vertex/plane-test is simple in camera-space:

The method with bitmask is really enjoyable, I guess I'll use it ! Thanks

Now you go through the vertices of your polygon and check each edge (adjacent pair of vertices) if they are on different sides of a frustum-plane:
(I was too lazy to convert the syntax to freebasic)

The code is self explaining, even in .. C++ I guess ? Well, it will be more than useful for me, k++ to you for that !

by the way, Won't there be any problem for the triangles crossing 2 or 3 planes at the same time ? (eg : A very big poly crossing Left, ZFar and Up planes)

[hellfire]

Won't there be any problem for the triangles crossing 2 or 3 planes at the same time ?

No, because you will always clip against one plane at a time.
In the "worst" case you clip so much off on one side that the polygon doesn't overlap a neighbouring side anymore.
So it's just important to recheck the flags after clipping.

[Hezad]

Well okay, so I have work to do now ^^

thanks again !

[Hezad]

Just a little message while i'm working on it :

I just implemented the clipping part without chopping new triangles. I was expecting nothing special when I ran it to see if there were any problem ...

I have between 18 and 24 FPS !!!

(yeah it's good news for me ^^ I had between 1 and 9 FPS when testing clipping before hellfire's snippets). And I didn't even implemented the triangles chopping nor the backface culling :p

On those words, I return to FBide !

thanks !

[Shockwave]

You should be able to get some really useful framerates when you are further along with the backface culling, and expect another speed up when you impliment mip maps too, not to mention a big improvement in image quality.

[Hezad]

Shockwave > Well, You won't see this message soon since you may not come here for some time 'cause of your leg but anyway, I have to finish the clipping part and the optimizations in code. And then, I'll work on mip-mapping


hellfire > Just saw the updates you made in your post about clipping, thanks But even if I really understood how to get the new vertices thanks to your code (I even implemented it), I don't see how I will "transform" those vertices into triangles. In the interpolation part of the clipping, I interpolated U and V and 1/Z coordinates too so the filling part can work. But I don't know how to select 3 good vertices to build a new triangle :/

I tried a naive way :

Code: [Select]

Newtriangle=( newvert(i),newvert(i+1),newvert(i+2) )but of course it don't work.

If you need to see the code, I'll post it

thanks again for your implication.

[hellfire]

Let's assume you have some mesh (vertices in random order):

Code: [Select]

0     1
 +---+
 |\  |
 | \ |
 |  \|
 +---+
3     2

And a list of indices building triangles from the vertcies:

Code: [Select]

2,0,3 1,0,2The order of the indices is counter-clockwise for all triangles (or the other way round, doesn't matter).

Since you use the same order to traverse the edges in the clipping-process, the resulting polygon is defined in counter-clockwise order, too:

Code: [Select]

     0 +
      / \
     /   \
  1 +     + 5
    |     |
  2 +     |
     \    |
    3 +---+ 4

A possible (no-overlapping) triangulation would be:

Code: [Select]

0,1,2  0,2,3  0,3,4  0,4,5Does that already look like an algorithm?

Code: [Select]

for i = 0 to numVertices-2
  drawTriangle v(0), v(i), v(i+1)
This always works as long as your polygon is convex (which it is).

So you were pretty close actually

[Hezad]

Hey

Does that already look like an algorithm? Smiley

hell yeah ^^

Well, I putted all this in my mind and I coded ... well, erm..


the point is ...


Well, It seems like it don't work lol

I set down the FOV to see where the triangles were chopped but it seems like they are not at all chopped :/ However, the triangles Count is much higher so there do are chopped triangles (much more : ~400 without chopping and 800/900 when chopped o_O)

I join the code + exe, you can move the camera with keyboard arrows. Once again, the perspective is deformed but it's normal, I set down the FOV to see the "borders" of the clipping.

I guess there is a problem in my perspective transformation so the x/z clipping doesn't work ?

here is just the perspective transformation routine :

Code: [Select]

'' projection
        for j as integer = 0 to 2

            obj.Triangle(i).Vertex(j).ViewPos.x = obj.Center.x + obj.Triangle(i).Vertex(j).pos3d.x - Camera.pos.x
            obj.Triangle(i).Vertex(j).ViewPos.y = obj.Center.y + obj.Triangle(i).Vertex(j).pos3d.y - Camera.pos.y
            obj.Triangle(i).Vertex(j).ViewPos.z = obj.Center.z + obj.Triangle(i).Vertex(j).pos3d.z - Camera.pos.z


            zDiv = FOV/(TriangleList(i).Vertex(j).ViewPos.z)
                       
            TriangleList(i).Vertex(j).pos2d.x = xRes*.5 + TriangleList(i).Vertex(j).ViewPos.x * zDiv
            TriangleList(i).Vertex(j).pos2d.y = yRes*.5 - TriangleList(i).Vertex(j).ViewPos.y * zDiv
        next
Some posts ago, you spoke about [-1;1] coords after Camera space transformation (Which is sorta the Vertex.ViewPos = triangle.center+vertex-Camera stuff you see in the code above, I have not implemented the camera rotation yet) but in my code, it's not in [-1;1] ..

In fact I'm starting to wonder seriously if I'm not totally lost between the camera space transformation, the 2d projection and the clipping ..

Of course, I'm not asking for you to look at the code in the zip, it's just to give some news. Still, if you see something wrong in the perspective code I posted, please tell me

thanks again .. and sorry for all those repeating questions :/

ps : Anyway, If I really don't manage to handle all those problems (Clipping, perspective correct mapping which still don't work, Code not well organized, ..), I may start again from scratch and force myself to use matrices transformation and organize way better the code.

[hellfire]

There's a logical error in your "Clip" function.
The principle is to take the input polygon (triangle) and clip it against the first clipping plane.
This results in a new polygon (vertices stored in "DestList").
Then you take the *new* (partially clipped) polygon and clip it against the next plane (and so on).

At the moment you're always clipping the *source* triangle and somehow collect all resulting vertices in "DestList".
Doesn't really make sense.

Your usage of "FOV" is a bit obscure to me.
You should try to understand that the field-of-view (commonly known as "zoom") is nothing else than a 2D (x,y) scaling in camera-space.
I expect that this scaling (including aspect-ratio, too) is already applied (contained in the transformation-matrix) when entering clipping. The clipflag-test assumes that the frumtum-planes are at x=z / y=z:
I'm not transforming the view-frustum according to the fov (which would result in arbitrary clipping planes and a more expensive clip-test). Instead I use a default frustum (which matches a fov of 90 degrees) and transform the vertices accordingly (they need to be transformed anyway).
I recommend to completely remove "FOV" and simply integrate it into the transformation:

Code: [Select]

            obj.Triangle(i).Vertex(j).ViewPos.x = (obj.Center.x + obj.Triangle(i).Vertex(j).pos3d.x - Camera.pos.x) * zoom
            obj.Triangle(i).Vertex(j).ViewPos.y = (obj.Center.y + obj.Triangle(i).Vertex(j).pos3d.y - Camera.pos.y) * zoom * aspectratio
            obj.Triangle(i).Vertex(j).ViewPos.z = (obj.Center.z + obj.Triangle(i).Vertex(j).pos3d.z - Camera.pos.z)

Since you clipped your polygons in normalized space (-1..+1), you must also scale them to screen-size when performing perspective transformation:

Code: [Select]

            zDiv = 1.0 / TriangleList(i).Vertex(j).ViewPos.z
            TriangleList(i).Vertex(j).pos2d.x = xRes*.5 + TriangleList(i).Vertex(j).ViewPos.x * zDiv * xRes*0.5
            TriangleList(i).Vertex(j).pos2d.y = yRes*.5 - TriangleList(i).Vertex(j).ViewPos.y * zDiv * yRes*0.5