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

[Hezad]

@hellfire :

You're totally right, I started to code the optimizations you wrote about, especially "one procedure per render type" and I gained 1-2 FPS on the most demanding rendering (Texture + gouraud shader + Fog + transparency) and at least 10 FPS on the Z-buffer rendering ^^

As promised, here is a screen comparing real-time rendering and super sampled rendering, I think it's way more visible with the checker tex.

[hellfire]

comparing real-time rendering and super sampled rendering

Remember that the anti-aliasing of edges inside the texture would already be handled by bilinear filtering...

[Hezad]

Yep, I started to work on bilinear filtering but the slow down was way to strong. I must work on optimization and camera handling before working on filtering again

[hellfire]

If you want to get some more performance from multisampling, you might want to try non-regular grids with samples shared across pixels:

Although there are 4 samples for each output-pixel, you just have to calculate two new samples per pixel.
Handling the different sampling-positions inside the polyfiller is a bit tricky, though.

[Hezad]

Thanks for the advice

Don't know yet if I'll use it (I'm still on my camera/optimization wanderings :p) but I'll definitely remember this 

[relsoft]

For static objects (Terrain,etc), I would suggest you do some space partitioning to speed things up quite a bit.

For outside areas with a free-look cam, you could use Octrees.  If you are going to limit your FOV from the top, Quadtrees would suffice.  Both would almost be coded exactly the same.

Here's a demo on how quadtrees could render stuff faster.

http://rel.betterwebber.com/mytutes/octreetute/octree_tute.zip

It's just sources and exes since I haven't coded anything since those. :*(

[Hezad]

Thanks for that The point is I don't know yet what this engine's purpose will be ! The main purpose is of course learning, but eh, since It has to be coded, why not making it useful ? In fact, I don't know if I want it to be a 3d engine designed for games, or for CG rendering ... Well, I guess in both cases, Space partitioning will help but I wanted to precise

thanks for the sources and the exes, I'll check that

[Hezad]

Heya

Nothing new, I didn't work on it since the last posts  There are so much stuff to do for it to be useful .. I got unmotivated. But right now I want to get back into it, I have a lot of ideas to code with software rendering but I HAVE TO code everything needed before (optimization, camera handling, texture filtering ..).

Okay, so now i'm focusing about camera handling.

Have I to use matrices inevitably ? In fact, for translations, it's pretty easy, no matrices needed. But for rotations ... I use three angle parameters to rotate all the world when needed. But if it works for the Y axis (eg, player rotation), when I wanna rotate along the X axis, it doesn't rotate in the camera space but in world space (So if I rotate along the Y axis and THEN rotate in the X axis, the X rotation isn't done about the direction I'm aiming but along a constant world X axis.

hum... I guess what I just wrote is simply illegible ... Sorry for that .. To resume in a sentence, When I rotate along the Y axis, the X axis stays constant instead of rotating "with me".

(You can see that in the last preview I posted if you try to rotate the camera with your mouse).

So my question is, Can I avoid that with "simple" angles parameters in the Camera Type ? Or MUST I use matrices ?

[hellfire]

Using matrices is inevitable and you might be surprised to hear that you are using them already.
You are now rotating your vertices using euler angles, applying one after another.
Euler rotation is nothing else than a 2d-rotation matrix (because the axis of rotation is cartesian, one component of your vector keeps unaffected):

Code: [Select]

x'= cos(a) * x - sin(a) * y + 0 * z
y'= sin(a) * x + cos(a) * y + 0 * z
z'=      0 * x     +  0 * y + 1 * z(exactcly what you do in "Rotate_Object")

Since a 2d-rotation (2x2 matrix) requires 4 multiplies/additions, you now already require a total of 12 mul/add (not containing translation) and your transformation will soon contain more components like scaling, shearing etc.
If you multiply the three matrices and translation to a single 4x3 matrix you just require 9 muls & 12 adds:

Code: [Select]

x'= Mxx * x - Mxy * y + Mxz * z  + Mxw
y'= Myx * x + Myy * y + Myz * z  + Myw
z'= Mzx * x + Mzy * y + Mzz * z  + Mzw

Rotating around cartesian axes is also rather unflexible, especially for camera-handling you'll preferably align your view along position- & target-vector (like gluLookAt does).
Try to understand that a matrix just defines the orientation (and origin) of a vector-space. The 3 vectors of the 3x3-part show were side/height/depth is. You can get from one space to another by multiplying with the corresponding matrix. get back again by multiplying with the inverse matrix.

[Hezad]

thanks hellfire, I think I start to see the point k++

So, for testing purposes, before implementing a LookAt camera, can I apply the 2d rotation matrix 3 times (each time for each axis) ?

[hellfire]

can I apply the 2d rotation matrix 3 times

That's basically what you already do.
If you want to keep the euler angles, I suggest to construct a 3x3 rotation-matrices for each axis and multiply them to a single matrix:
M = Mx * My * Mz
Notice that the order is important - traditionally one rotates around the "up"-axis first.

3x3 layout for (clockwise) rotation-matrices looks like this:

Code: [Select]

   1    0       0
   0  cos(x) -sin(x)
   0  sin(x)  cos(x)


Code: [Select]

cos(y)  0 -sin(y)
   0     1    0
 sin(y)  0  cos(y)


Code: [Select]

cos(z) -sin(z)  0   
 sin(z)  cos(z)  0   
   0       0     1
Notice that an angle of 0 results in an identity matrix.

[Clyde]

Firstly welldone on your development Hezad, and secondly ( or should this be first ) congrats on the first to get over 170 ( at time of typing ) replies in a Coding category; plus on your very first post too - all with cool and handy stuff from peeps.

Karma++

[Hezad]

@hellfire :
I don't particulary want to keep Euler angles, but I just want to understand what's going on before working on a look at procedure

I suggest to construct a 3x3 rotation-matrices for each axis and multiply them to a single matrix:
M = Mx * My * Mz

So, if I understand well, I "just" have to build the three 3x3 rotation matrices (the layouts you posted) in the good order and then multiply them. So, how can I use the resulting matrix ? Can I just rotate the viewpos by using numbers contained by the matrix ?



@Clyde :
Thanks a lot Credit goes to all the awesome information people posted here, especially hellfire !

btw, what do you mean by "peeps" ?

[Shockwave]

So, if I understand well, I "just" have to build the three 3x3 rotation matrices (the layouts you posted) in the good order and then multiply them. So, how can I use the resulting matrix ? Can I just rotate the viewpos by using numbers contained by the matrix ?

Yes
You rotate those points in the matrix and multiply everything with them.

And it will be quite fast too.

[Hezad]

Thanks Shockwave I have a last question though : if I multiply the three 3x3 matrices, it will result in a 3x3 matrix no? If I'd have a 3x1 matrix, I could multiply each point coordinate by a value in the matrix

e.g. :

Code: [Select]

point.x *= matrix(1)
point.y *= matrix(2)
point.z *= matrix(3)
But since the resulting matrix is a 3x3 one, what have I to do with the 6 remaining numbers ? Or how to use a 3x3 matrix to handle coordinates using 1x3 numbers ? Rah once again I'm lost. Now I know how to handle simple matrices, but I still don't understand how to handle the transformations they describe :S

Anyway, I coded a little Header to handle matrices (addition, subtraction, multiplication, create empty matrix, create Identity matrix, and a cast operator to print matrices on screen) to use it with my engine.

I post it here, maybe it'll be useful for someone :

matrix.bi :

Code: [Select]

'' Matrix.bi
''
'' 2008 - Hezad
''
''
''  Contact : Hezad0@Gmail.com


#Define nl chr(10)+chr(13)

Type Matrix
    as integer SizeX, SizeY
   
    as single ptr Dat
   
    Declare Constructor(sx as integer, sy as integer)
   
    Declare Operator Cast() as string
   
    Declare Function Value(i as integer, j as integer) as single
    Declare Sub Set(i as integer, j as integer,value as single)
   
    Declare function Transpose() as matrix
   
    Declare Sub LoadIdentity()
    Declare Sub Empty()
End type

Constructor Matrix(sx as integer, sy as integer)

    this.SizeX = sx
    this.SizeY = sy
   
    Dat = Callocate(sx*sy+1,Sizeof(single))

End Constructor

Operator Matrix.Cast() as string
   
    dim as string finStr
    dim as integer iter
   
    for j as integer = 0 to this.SizeY-1
       
        finStr += "["
       
        For i as integer = 0 to this.SizeX-1
           
            finStr += " "+str(this.Dat[iter])
            iter+=1
       
        next
       
        finStr += " ]"+nl
       
    next
   
    return finStr
   
End Operator

Operator + (LM as matrix, RM as matrix) as matrix
   
    if LM.SizeX<>RM.SizeX or LM.SizeY<>RM.SizeY then exit Operator
   
    Dim as matrix newMat = matrix(LM.SizeX,LM.SizeY)
   
    dim as integer iter
   
    for i as integer = 0 to LM.SizeX-1
        for j as integer = 0 to RM.SizeY-1
           
            NewMat.dat[iter] = LM.dat[iter] + RM.Dat[iter]
            iter+=1
        next
    next
   
    return NewMat
   
end Operator   

Operator - (LM as matrix, RM as matrix) as matrix
   
    if LM.SizeX<>RM.SizeX or LM.SizeY<>RM.SizeY then exit Operator
   
    Dim as matrix newMat = matrix(LM.SizeX,LM.SizeY)
   
    dim as integer iter
   
    for i as integer = 0 to LM.SizeX-1
        for j as integer = 0 to RM.SizeY-1
           
            NewMat.dat[iter] = LM.dat[iter] - RM.Dat[iter]
            iter+=1
        next
    next
   
    return NewMat
   
end Operator

Operator *(LM as matrix, RM as matrix) as matrix
   
    if LM.SizeX<>RM.SizeY or LM.SizeY<>RM.SizeX then exit Operator
   
    Dim as matrix newMat = matrix(RM.SizeY,LM.SizeX)
   
    dim as single curVal
   
    dim as integer iter
   
    for j as integer = 0 to newMat.SizeY-1
        for i as integer = 0 to newMat.SizeX-1
           
            curVal = 0
           
            for k as integer = 0 to LM.SizeX-1
                   
                curVal += LM.dat[k+j*LM.SizeX] * RM.dat[i+k*RM.SizeX]
               
            next
           
            newMat.dat[iter] = curval
           
            iter+=1
           
        next
    next
   
    return NewMat
   
end Operator

Operator *(LM as matrix, RM as single) as matrix
   
    Dim as matrix newMat = matrix(LM.SizeX,LM.SizeY)
   
    dim as integer iter
   
    for i as integer = 0 to newMat.SizeX-1
        for j as integer = 0 to newMat.SizeY-1
           
            newMat.dat[iter] = RM * LM.dat[iter]
           
            iter+=1
           
        next
    next
   
    return NewMat
   
end Operator

Sub Matrix.Empty()
   
    for i as integer = 0 to this.SizeX*this.SizeY-1
        this.Dat[i] = 0
    next

end sub

Sub Matrix.LoadIdentity()
   
    if this.SizeX <> this.SizeY then exit sub
   
    for i as integer = 0 to this.SizeX-1
        for j as integer = 0 to this.SizeY-1
            this.set i,j,iif(i=j,1,0)
        next
    next
   
end sub

function Matrix.Transpose() as Matrix
   
    dim as matrix tmp = matrix(this.SizeY,this.SizeX)
   
    For j as integer = 0 to this.SizeY-1
        for i as integer = 0 to this.SizeX-1
           
            tmp.dat[i+j*this.SizeY] = this.dat[j+i*this.SizeX]

        next
    next
   
    return tmp
   
end function

Function Matrix.Value(i as integer, j as integer) as single
   
    return this.Dat[i+j*this.SizeX]

end function

Sub Matrix.Set(i as integer, j as integer,value_m as single)
   
    this.Dat[i+j*this.SizeX] = value_m
   
end sub

matrixExample.bas

Code: [Select]

'' Matrix.bi Example file
''
'' 2008 - Hezad
''
''
''  Contact : Hezad0@Gmail.com


#include "matrix.bi



Dim as matrix A = Matrix(3,3), B = Matrix(3,3), ID = Matrix(3,3)

for i as integer = 0 to 2
    For j as integer = 0 to 2
        A.Set i,j,i*2+j
    next
next


Print "A =>"
Print A



B = A*A
Print "B = A*A =>"
Print B



B = A.Transpose
Print "B = A.Transpose =>"
Print B



ID.LoadIdentity
Print "ID.LoadIdentity =>"
Print ID



B.Empty
Print "B.Empty =>"
Print B



B = A*ID
Print "B = A*ID (=ID*A) =>"
Print B

sleep


edit : Attached a .rar (tested the header with the engine.., a funny bug to see : try to rotate the camera with your mouse ^^)

[hellfire]

You won't need matrices of different size.
I suggest to use 4x3 matrices which is a 3x3 matrix with an additional translation-vector.
Most APIs use 4x4 matrices, but I'm pretty sure you won't need those for a while.

Matrix:

Code: [Select]

xx xy xz   xp
yx yy yz   yp
zx zy zz   zp
[rotation] [position]
Try to understand that the 3x3 part consists of three vectors.
These vectors are the axes of your coordinate system:
(xx,yx,zx) points to the right
(xy,yy,zy) points up
(xz,yz,zz) points into depth

Identity matrix (transforms x,y,z to the same x,y,z):

Code: [Select]

1 0 0   0
0 1 0   0
0 0 1   0
Notice that the bases are the cartesian axes (transformation to the vector-space you're already in).

A vector describes a position or direction relative to a coordinate system.
When transforming a vector (x,y,z) to another coordinate-system, the components of the vector are then relative to new coordinate axes:

Code: [Select]

x'= xx*x + xy*y + xz*z + xp
y'= yx*x + yy*y + yz*z + yp
z'= zx*x + zy*y + zz*z + zp

Now we want to transform using two matrices "m1" and "m2":

Code: [Select]

  first transform (x,y,z) to (x1,y1,z1) using m1 (using equation above)
  x1= m1.xx*x + m1.xy*y + m1.xz*z + m1.xp
  y1= m1.yx*x + m1.yy*y + m1.yz*z + m1.yp
  z1= m1.zx*x + m1.zy*y + m1.zz*z + m1.zp

  then transform (x1,y1,z1) to (x2,y2,z2) using m2
  x2= m2.xx*x1 + m2.xy*y + m2.xz*z + m2.xp
  y2= m2.yx*x1 + m2.yy*y + m2.yz*z + m2.yp
  z2= m2.zx*x1 + m2.zy*y + m2.zz*z + m2.zp

This is twice the work, so we're looking for new matrix "n" which does both transforms at once.
We simply plug the first equation into the second and reorder back to matrix-layout (just shown for one component):

Code: [Select]

  x2= m2.xx * (m1.xx*x + m1.xy*y + m1.xz*z + m1.xp)   (equation for x1)
    + m2.xy * (m1.yx*x + m1.yy*y + m1.yz*z + m1.yp)   (equation for y1)
    + m2.xz * (m1.zx*x + m1.zy*y + m1.zz*z + m1.zp)   (equation for z1)
    + m2.xp

=> remove braces
  x2= m2.xx*m1.xx*x + m2.xy*m1.yx*x  + m2.xz*m1.zx*x
    + m2.xx*m1.xy*y + m2.xy*m1.yy*y + m2.xz*m1.zy*y
    + m2.xx*m1.xz*z + m2.xy*m1.yz*z + m2.xz*m1.zz*z
    + m2.xx*m1.xp + m2.xy*m1.yp + m2.xz*m1.zp + m2.xp

=> refactor to x,y,z:
  x2= (m2.xx*m1.xx+m2.xy*m1.yx+m2.xz*m1.zx) * x
    + (m2.xx*m1.xy+m2.xy*m1.yy+m2.xz*m1.zy) * y
    + (m2.xx*m1.xz+m2.xy*m1.yz+m2.xz*m1.zz) * z
    + (m2.xx*m1.xp + m2.xy*m1.yp + m2.xz*m1.zp + m2.xp)
So here we've got the first row of a matrix which transform "x" directly to "x2".

The complete new matrix "n" looks like this:

Code: [Select]

   n.xx= m2.xx*m1.xx + m2.xy*m1.yx + m2.xz*m1.zx
   n.xy= m2.xx*m1.xy + m2.xy*m1.yy + m2.xz*m1.zy
   n.xz= m2.xx*m1.xz + m2.xy*m1.yz + m2.xz*m1.zz
   n.xp= m2.xx*m1.xp + m2.xy*m1.yp + m2.xz*m1.zp + m2.xp

   n.yx= m2.yx*m1.xx + m2.yy*m1.yx + m2.yz*m1.zx
   n.yy= m2.yx*m1.xy + m2.yy*m1.yy + m2.yz*m1.zy
   n.yz= m2.yx*m1.xz + m2.yy*m1.yz + m2.yz*m1.zz
   n.yp= m2.yx*m1.xp + m2.yy*m1.yp + m2.yz*m1.zp + m2.yp

   n.zx= m2.zx*m1.xx + m2.zy*m1.yx + m2.zz*m1.zx
   n.zy= m2.zx*m1.xy + m2.zz*m1.zy + m2.zy*m1.yy
   n.zz= m2.zx*m1.xz + m2.zy*m1.yz + m2.zz*m1.zz
   n.zp= m2.zx*m1.xp + m2.zy*m1.yp + m2.zz*m1.zp + m2.zp


[Clyde]

@Hezad: No worries dude, btw peeps is a way I use to say people.

[Hezad]

@hellfire :

Thanks a lot mate, it'll definitely be helpful k++

@Clyde : thanks for the precision

[Hezad]

Finally !!!!!!!!!

UPDATE !

The engine hasn't progressed for a while because of the matrix stuff, I didn't know how to implement all this, even with the very good help I received here. But finally, the camera rotation now works Camera movement (correlated with its rotation) isn't implemented yet (or .. well, it's implemented but not working )

So I'm proud to announce the version 0.055 ! Here is the change log :

v0.055 Changes List



MAJOR :

 - Added Material Opacity handling.

 - Changed all the Render Subs. One Render procedure for each render type
   > Render_Opt_ZBuffer
   > Render_Opt_MipMap
   > Render_Flat_NoTex
   > Render_Flat_NoTex_Fog
   > Render_Flat_Tex
   > Render_Flat_Tex_Fog
   > Render_Smooth_NoTex
   > Render_Smooth_NoTex_Fog
   > Render_Smooth_Tex
   > Render_Smooth_Tex_Fog

 - Camera now uses a matrix for the engine to rotate Viewport !
        > New header : matrix.bi (handles matrices)


Minor :

 - Added Water Texture.


Known bugs :

 - Camera movement to code

 - Transparent Objects must be the last projected objects.

Attached : *.rar archive



edit : camera movement is now totally fixed I didn't uploaded the fix, but you'll see that with the 0.06

[hellfire]

Looks very nice but still needs some serious optimizing
(the zbuffer-view already got pretty fast, though!)

Your exponential fog is rather expensive:

Code: [Select]

blendfunc = exp(-(tmp_Z*_MAX_Z) * fog_Density)
Cr = blendfunc * Cr + (1-blendfunc) * Fog_Color.r
Cg = blendfunc * Cg + (1-blendfunc) * Fog_Color.g
Cb = blendfunc * Cb + (1-blendfunc) * Fog_Color.b
Generally I would recommend not to call any trigonometric functions on a per pixel basis
You can do a second pass which looks up the fog-density from the significant bits of zbuffer using a small table.
This way your polyfiller's innerloop gets tighter and the blending is only done once per pixel (due to overdraw you'll usually plot every pixel more than once).