Dark Bit Factory & Gravity

That looks really, really, really nice.

Well done :)

thanks a lot :)

Here's just a little pic resulting from a glitch I had when coding a GenerateSphere() sub, I like it :p

(http://freefile.kristopherw.us/uploads/hezad/glitchnice.jpg)

Update :


Vector Light replaced by Omni Light


(http://freefile.kristopherw.us/uploads/hezad/screen_gouraud_omnilight.jpg)
~20 rotating cubes with an omni light at the center of the screen

image hosted on Kristopher Windsor's image hosting service :p

Where's the file? :) Looks nice but I want to see it in action :D

uhuh oki :D

here it is ^^

and the code :

edit : erm the code must be too long, the code marks cut it :S but if anyone wants to see it, it's in the .rar :)

That's working really nicely :)

This computer is a P4 3.0 Ghz, but the computer is quite old and the frame rate is perfectly ok here, it does a fairly steady 29 - 32 fps.

I suspect that it would be a lot faster without the lightsourcing :) The lightsourcing looks very nice though.

thanks :) Well yeah, if I get off the light calculations and do only a texture mapping i get ~40FPS instead of 30 normally :)

But if cubes are a bit larger or nearer, it's getting worse lol I get ~10 FPS and even 3/4 FPS if they fill the whole screen :S

optimization .. :p

Optimization.. Well, this is coming I guess. and there are a few things that you can do to optimise it.

I think that what you have done there is achieved by less than 1% of people who learn programming, you've progressed a lot and I bet Relsoft will be really happy when he sees what you made since you read his tutorial, he is a member here and I know he likes to show people how to code things.

Anyway onto your demo, the two things that are a problem are the speed and texture warping.

Texture warping is unavoidable with affine texture mapping like you are doing.
It is more noticeable when there is a lot of perspective on the surface you are drawing, for example, some vertex is deep into the screen and other vertices are close, the texture seems to slide around the polygon.

There are solutions, firstly one of the fastest ways is to subdivide the surface into several smaller triangles and subdivide the UV's too, so in practice you might render


    /\
  /    \
------


Like this;


     *
    /_\
  / \/ \
  ------


(apologies for the dodgy ascii), this means that the warping effect is less noticeable.

Or you could use a perspective correct algorithm,  with this algorithm and as a side effect you get the z-co-ordinate of each pixel for your Z-Buffer.

Another thing you will probably want to look into is clipping and definately mip-mapping.

Both will increase your speed, clipping algorithms will enable you to chop up polygons and thereby discard geometary that is not visible.

Mip mapping you will generate a set of texture maps ranging from small size to large for your polygon and perform the cross-product equation on your polygon to determine it's area so that you can select the texture map that best fits the area of the polygon you are about to draw.

Smaller texture maps are faster, using mip mapping will also help avoid "dancing pixels" which are typically visible on small polygons where the routine is accessing a large texture map. These artifacts appear as flickering dots.

Anyway that's probably more than enough to be going along with, I reccomend that you start off with perspective correct textures :) Please do post if you need help or just to let us know how you are getting along. I for one am really enjoying this topic!

Hey :) I was coding something to enjoy my engine start (:p) but I didn't read what you just written while I was doing that, so the thing i'll attach with this post hasn't any of the optimizations you just told me.

So first, i'll answer you :)

QuoteI think that what you have done there is achieved by less than 1% of people who learn programming, you've progressed a lot and I bet Relsoft will be really happy when he sees what you made since you read his tutorial, he is a member here and I know he likes to show people how to code things.

Well, thanks ! this kind of comments surely puts me on the motivation track ! And Relsoft already commented it on the freebasic forums.
Even if I know it's far from a perfect thing, I have to admit I'm pretty proud (yeah auto-satisfaction .. :p) of what I have done so far but you know, sometimes you're so glad about some self-made stuff that you don't see crucial flaws. Until now, I think I saw them and you (and other people) really helped me to fix them.

So once again, thanks !!

QuoteTexture warping is unavoidable with affine texture mapping like you are doing.
It is more noticeable when there is a lot of perspective on the surface you are drawing, for example, some vertex is deep into the screen and other vertices are close, the texture seems to slide around the polygon.

(...)

Totally agree, I really need to code the corrected perspective stuff. It's already on my todo list and I spent some time with my friend "internet" to understand it :p Anyway, your explications are totally helpful and I think it'll help me to work on it !

Oh ! And don't worry about the ASCII diagram, It totally makes sense :)

QuoteAnother thing you will probably want to look into is clipping

Right ! But before, I need to make sure I totally understand/recode my coordinates system :the Z-buffer algo + the projection routine work but use some really weird Z constants and/or subtractions. So I really need to see what's going on in there before thinking about clipping :p
(By clipping, I guess you're speaking about not calculating poly's outside the viewing frustum  ?)

Quoteand definately mip-mapping.

QuoteMip mapping you will generate a set of texture maps ranging from small size to large for your polygon and perform the cross-product equation on your polygon to determine it's area so that you can select the texture map that best fits the area of the polygon you are about to draw.

Smaller texture maps are faster, using mip mapping will also help avoid "dancing pixels" which are typically visible on small polygons where the routine is accessing a large texture map. These artifacts appear as flickering dots.

!! I heard of mip-mapping so often .. I didn't understand in which way it could be helpful.. Now I do ! It has to be on my todo list :D Once again, Really clear explanation :)

QuoteAnyway that's probably more than enough to be going along with, I reccomend that you start off with perspective correct textures Smiley Please do post if you need help or just to let us know how you are getting along. I for one am really enjoying this topic!

perspective correct texture mapping is the first item on my list :D
I will post if I have questions (and I'm pretty sure i'll have :p), thanks !
And I'm glad you like this topic, really ! :)



To finish, I'll post the thing I spoke about at the beginning of this post, the Plasma Cube ! :D Well I already saw that kind of stuff pretty often but whatever ^^

Attached : Screenshot + Rar(Src+Exe)

thanks again Shockwave !

Bye :)

The other thing you need to look at speedwise is you are doing an incredible number of Single->Int conversions in your code,  potentially a dozen per pixel.  That is not a fast thing to do, so you might want to think about how you can do it all in integers.
If you backface cull, you won't see all the insides of the objects too - that will halve the number of faces you are considering.

Jim

Quoteyou might want to think about how you can do it all in integers

Yeah sure ! thanks I didn't think about that.

QuoteIf you backface cull, you won't see all the insides of the objects too

hm ? I don't understand :p Since faces are only drawn once, If I backface cull a face, it won't be calculated anyway, no ?

Quote from: Hezad on August 27, 2008

QuoteIf you backface cull, you won't see all the insides of the objects too

hm ? I don't understand :p Since faces are only drawn once, If I backface cull a face, it won't be calculated anyway, no ?

You can either use the normal to backface cull (is it pointing in or out) or just use the cross-product equation to determine if the points are clockwise or counter clockwise (clue: the result is either positive or negative), then you can decide whether to draw the polygon or not.

This means that for a cube which is made from 12 triangles, potentially you will only need to draw a maximum of 6 of them.

Rotating the vertices and doing a cross product calc is cheap when compared to drawing a texture mapped polygon, so what Jim is saying is that the calcs of rotating the object and doing that simple check to see if you should draw the polygon will speed things up a lot.

Quote(By clipping, I guess you're speaking about not calculating poly's outside the viewing frustum  ?)

I mean not drawing polys or parts of polys that lie outside the view frustrum. :)

Btw, the plasma cube looks really great! Nice colour choice.

If you clip the polygons, either in 3d (better) or in 2d screen space, then you can remove ALL the If checks that test if the triangle starts off the screen or if a pixel is off the screen.  Doing all that stuff up front makes the hard bit of drawing triangles simpler.

Jim

Yeah very cool plasma cube dude.

Welldone on your efforts,
Clyde

QuoteRotating the vertices and doing a cross product calc is cheap when compared to drawing a texture mapped polygon, so what Jim is saying is that the calcs of rotating the object and doing that simple check to see if you should draw the polygon will speed things up a lot.

QuoteIf you clip the polygons, either in 3d (better) or in 2d screen space, then you can remove ALL the If checks that test if the triangle starts off the screen or if a pixel is off the screen.  Doing all that stuff up front makes the hard bit of drawing triangles simpler.

So if I understand correctly (and sorry if it's not the case :p), I should verify if the current poly (or pixel?) is in the viewing frustum (in 3d) and then, calculate (Poly Normal [Dot] View Normal) to make sure the poly is visible (and if it's not, I "forget" it for the projection/lighting/rendering calculations) ?

thanks for your answers and for the comments about the plasma cube :)

Wow, this is some seriously impressive work and from what I gather by reading through the posts, you are a literal sponge for information.  You're able to keep progressing by answering sensible questions and acting on the responses.  Something to be encouraged and celebrated.

:clap:

Quote
If you clip the polygons, either in 3d (better) or in 2d screen space, then you can remove ALL the If checks that test if the triangle starts off the screen or if a pixel is off the screen.  Doing all that stuff up front makes the hard bit of drawing triangles simpler.

QuoteSo if I understand correctly (and sorry if it's not the case :p), I should verify if the current poly (or pixel?) is in the viewing frustum (in 3d) and then, calculate (Poly Normal [Dot] View Normal) to make sure the poly is visible (and if it's not, I "forget" it for the projection/lighting/rendering calculations) ?

Not really.
In 2d clipping, you do the whole process that you are currently doing, but just before you render the triangle you work out whether any of it is off screen.  If it is, then you can clip the triangle against the screen's rectangle and that will give you a set of triangles which can be rendered without any If testing.

In 3d clipping, you do that process in 3d against the pyramid which is your viewing frustum (imagine a square-based pyramid with the point at the camera and the rectangular base being your far-clip plane).  You can work out, before projection, which polygons are inside that volume.  The advantage of this is that you don't get range error problems when you do the perspective calculation - and you can't do 2d clipping without doing perspective - so you save yourself some real problems.

Jim

Xalthorn > thanks :D Well I ask questions so if people answer me, I have to take their answers into account :)

Jim > ok thanks, I start to understand your point :p But sorry for this last question but since I am not sure about it, I prefer to ask :
when you say

Quoteyou can clip the triangle against the screen's rectangle and that will give you a set of triangles which can be rendered without any If testing.

Do you mean I discard all the triangle if a part of it must be clipped (but it could appear suddenly in the screen if so, no ?) or shall I "just" don't draw the pixels out of screen ?
Because right now, Just before drawing the pixel, I do a "basic" 2D clipping :
If x>0 and x<xRes and y>0 and y<yRes then putPixel

So do you mean doing this but in 3D ? Or Did I totally misunderstand once again ? Sorry for insisting with it but in fact I guess I don't understand how I could verify whether the poly is in screen/viewing frustum or not without any if testing ..

:)

3D clipping means that you will have to chop up some triangles, it's different to just simple clipping to the viewport, you need to be able to calculate where your triangles intersect the view frustrum and possibly split them into more triangles.

For example consider this triangle;

|\
|  \
|    \
|      \
|        \
|          \
|_______\


and it intersects  the view frustrum;


  |\
_|_\_______________
  |    \
  |      \
  |        \
  |          \
  |_______\


Can be chopped up like this;



 
___________________
  |   / \
  | /     \
  |_____\


The part of the triangle that is outside the viwe area is discarded and two triangles are computed, includin new uv co-ordinates.

Not as hard as it sounds, a clue is you need to work out where the edges of the triangle intersect the clipping planes so that you can chop up the triangle :)

If you need more detailed help, ask away :)

aah okay now I got it, thanks ^^ I didn't understand the fact that I have to "create" new triangles when the current triangle have a part clipped.

Okay, so now I got it, i'll work on it. I still didn't coded the perspective correct mapping (I had a few tries but I didn't interpolate 1/z,u/z and v/z in a good way).

Anyway, I won't be at home for a week so I won't be able to work on it but once i'll get back, correct texture mapping and 3D clipping will be the first things i'll work on. And then, working on reducing the single>integer conversions. And then, maybe mip mapping :D

Still, while I were trying the perspective correct texture mapping, I reorganized a bit the code. So, a little update before the big stuff :

- It supports any number of lights (Add_Light, Set_Light)
- The projection/Z-buffer now recoded with a comprehensible Z-axis handling (It was needed for the 3d clipping and the correct texture mapping)
- New handling of shader calc and filling with user-friendly subs (Set_shader(), Set_Texture()) : if no texture is assigned to an object, it will automatically be rendered with the selected shader)

Thanks for your explanations everyone and see ya in a week or so !

It's cool that you continue to work on this :) It's been a nice topic so far, hopefully we'll see you implimenting clipping and mip mapping soon.

You will definately need to clip by chopping up triangles because you'll need to clip the triangles according to their depth as well as the x,y position :)

QuoteIf x>0 and x<xRes and y>0 and y<yRes then putPixel

If I had 2 tris filling the screen, that would mean I did this test 640x480 times with every single pixel passing he test, but if I knew the two tris were on screen before I tried drawing them I could remove all these 4 checks from every pixel.  That would be a massive speed up!  The chopping up might sound complicated, but it's worth wroking it out.

Jim
PS. btw, you want

QuoteIf x>=0 and x<xRes and y>=0 and y<yRes then putPixel

otherwise you won't be able to plot anything on the first scanline or the left column of pixels.

Hey :) I'm back :D

Well, I wanted to post a perspective correct mapping to celebrate the thing but nothing to do, I tried at least 4 or 5 times to rewrite the sub, it doesn't work...

With the advices provided here and the documentation on the internet, I understood that I should interpolate u/z and v/z (and 1/z but since I already know Z from the Z-Buffer calc, I also tried to use it instead of 1/z), and then multiply by the current Z to get the good uv coords. But erm.. It doesn't work >< It makes the program to crash (I guess the uv coords are too large for the texture ptr). Here is the code used in the subs, I hope it's readable :

Sub TSLine(ByVal x1 as integer,ByVal x2 as integer, y as integer,ByVal U1 as single,ByVal V1 as single,ByVal U2 as single,ByVal V2 as single,ByVal z1 as integer,ByVal z2 as integer,byval Texture as TextureT, r1 as integer,r2 as integer,g1 as integer,g2 as integer,b1 as integer,b2 as integer,_z1 as single,_z2 as single)
   
    dim as single dR,dG,dB
    dim as single R,g,b
   
    dim as single sr1,sr2,sg1,sg2,sb1,sb2
   
    dim as single dU,dV,dZ,U,V
    dim as single Uu1,Vv1,Uu2,Vv2
   
    dim as integer itx1,itx2,zz1,zz2
    Dim as single CurZ,xDiv,Cur_Z,_zz1,_zz2,d_Z
   
    if x1<x2 then
        zz1 = z1
        zz2 = z2
       
        _zz1 = _z1
        _zz2 = _z2
       
        itx1 = x1
        itx2 = x2
       
        Uu1 = u1
        Uu2 = u2
        Vv1 = v1
        Vv2 = v2
       
        sr1 = r1
        sr2 = r2
        sg1 = g1
        sg2 = g2
        sb1 = b1
        sb2 = b2
    else
        zz1 = z2
        zz2 = z1
       
        _zz1 = _z2
        _zz2 = _z1
       
        itx1 = x2
        itx2 = x1
       
        Uu1 = u2
        Uu2 = u1
        Vv1 = v2
        Vv2 = v1
       
        sr1 = r2
        sr2 = r1
        sg1 = g2
        sg2 = g1
        sb1 = b2
        sb2 = b1
    end if
   
    'Uu1 *= Texture.Size.x
    'Uu2 *= Texture.Size.x
    'Vv1 *= Texture.Size.y
    'Vv2 *= Texture.Size.y
   
    xDiv = 1/(itx2 - itx1)
   
    dR = xDiv * (sr2 - sr1)
    dG = xDiv * (sg2 - sg1)
    dB = xDiv * (sb2 - sb1)
   
    dZ = xDiv * (zz2 - zz1)
    d_Z = xDiv * (_zz2 - _zz1)
   
    dU = xDiv * (Uu2 - Uu1)
    dV = xDiv * (Vv2 - Vv1)
   
    CurZ = zz1
    Cur_Z = _zz1
   
    U = Uu1
    V = Vv1
   
    r = sr1
    g = sg1
    b = sb1
   
    dim as single ValU,ValV
    dim as integer it
    Dim as integer CurTex,Cr,Cg,Cb
   
   
    it = y*xRes + itx1
   
    for i as integer = itx1 to itx2-1

        if y>=0 and y<yRes and i>=0 and i<xRes then
           
            If (FOV - (-Camera.pos.z + CurZ))>0 then
               
                If Curz < ZBuffer(it) then
                   
                    ZBuffer(it) = CurZ
                   
                    'ValU = U*CurZ   '' (U/Z)*Z
                    'ValV = V*CurZ   '' (V/Z)*Z
                   
                    ValU = U/Cur_Z  '' (U/Z)/(1/Z)
                    ValV = V/Cur_Z  '' (V/Z)/(1/Z)
                   
                    CurTex = Texture.GFX[int(ValU*Texture.Size.x)+Texture.Size.x*int(ValV*Texture.Size.y)]
                   
                    Cb = ((CurTex and 255))*b*0.003921  '' 1/255
                    Cg = ((CurTex shr 8) and 255)*g*0.003921
                    Cr = ((CurTex shr 16) and 255)*r*0.003921
                   
                    ScrPtr[it] = rgb(Cr,Cg,Cb)
                   
                end if
            end if
       
        end if
       
        it+=1
       
        U += dU
        V += dV
       
        Cur_Z += d_Z
       
        r += dR
        g += dG
        b += dB
       
        curZ += dZ
       
    Next
   
End Sub
   
Sub Texture_Map_Shaded(ByVal Triangle as TriangleT, _
                       ByVal Texture as TextureT)      '' UV's saved in the Triangle.Vertex Type
   
   
    '' Sorting Y values
    if Triangle.Vertex(1).Pos2d.y < Triangle.Vertex(0).Pos2d.y then
        swap Triangle.Vertex(1),Triangle.Vertex(0)
    end if
    if Triangle.Vertex(2).Pos2d.y < Triangle.Vertex(0).Pos2d.y then
        swap Triangle.Vertex(2),Triangle.Vertex(0)
    end if
   
    if Triangle.Vertex(2).Pos2d.y < Triangle.Vertex(1).Pos2d.y then
        swap Triangle.Vertex(2),Triangle.Vertex(1)
    end if
   
    dim as integer dx1,dy1,dx2,dy2,dx3,dy3
    dim as single Slope1,Slope2,Slope3, dYDiv
   
    dim as single dU1,dU2,dU3,dV1,dV2,dV3
    dim as single USlope1,USlope2,USlope3
    dim as single VSlope1,VSlope2,VSlope3
   
    Dim as integer dz1,dz2,dz3,d_z1,d_z2,d_z3
    Dim as single zSlope1,zSlope2,zSlope3
    Dim as single _zSlope1,_zSlope2,_zSlope3
   
    dim as integer dr1,dg1,db1,dr2,dg2,db2,dr3,dg3,db3
    dim as single RSlope1, GSlope1,BSlope1
    dim as single RSlope2, GSlope2,BSlope2
    dim as single RSlope3, GSlope3,BSlope3
   
    '' interpolate 0 to 1 (pos + color)
   
    dZ1 = Triangle.Vertex(1).pos3d.z - Triangle.Vertex(0).pos3d.z
    d_z1 = 1/(Triangle.Vertex(1).pos3d.z+Triangle.Parent_Center.z) - 1/(Triangle.Vertex(0).pos3d.z+Triangle.Parent_Center.z)
   
    dX1 = Triangle.Vertex(1).pos2d.x - Triangle.Vertex(0).pos2d.x
    dY1 = Triangle.Vertex(1).pos2d.y - Triangle.Vertex(0).pos2d.y
   
    dU1 = Triangle.Vertex(1).U/(Triangle.Vertex(1).pos3d.z+Triangle.Parent_Center.z) - Triangle.Vertex(0).U/(Triangle.Vertex(0).pos3d.z+Triangle.Parent_Center.z)
    dV1 = Triangle.Vertex(1).V/(Triangle.Vertex(1).pos3d.z+Triangle.Parent_Center.z) - Triangle.Vertex(0).V/(Triangle.Vertex(0).pos3d.z+Triangle.Parent_Center.z)
   
    dr1 = Triangle.Vertex(1).color.r - Triangle.Vertex(0).color.r
    dg1 = Triangle.Vertex(1).color.g - Triangle.Vertex(0).color.g
    db1 = Triangle.Vertex(1).color.b - Triangle.Vertex(0).color.b
   
    if dY1 <> 0 then
       
        dYDiv = 1/dY1
       
        zSlope1 = dZ1 * dYDiv
        _zSlope1 = d_Z1 * dYDiv
       
        Slope1 = dX1 * dYDiv
       
        USlope1 = dU1 * dYDiv
        VSlope1 = dV1 * dYDiv
       
        RSlope1 = dR1 * dYDiv
        GSlope1 = dG1 * dYDiv
        BSlope1 = dB1 * dYDiv
       
    else
       
        zSlope1 = 0
        _zSlope1 = 0
       
        Slope1 = 0
       
        USlope1 = 0
        VSlope1 = 0
       
        RSlope1 = 0
        GSlope1 = 0
        BSlope1 = 0
    End if
   
   
    '' interpolate 1 to 2
   
    dZ2 = Triangle.Vertex(2).pos3d.z - Triangle.Vertex(1).pos3d.z
    d_Z2 = 1/(Triangle.Vertex(2).pos3d.z+Triangle.Parent_Center.z) - 1/(Triangle.Vertex(1).pos3d.z+Triangle.Parent_Center.z)
   
    dX2 = Triangle.Vertex(2).pos2d.x - Triangle.Vertex(1).pos2d.x
    dY2 = Triangle.Vertex(2).pos2d.y - Triangle.Vertex(1).pos2d.y
   
    dU2 = Triangle.Vertex(2).U/(Triangle.Vertex(2).pos3d.z+Triangle.Parent_Center.z) - Triangle.Vertex(1).U/(Triangle.Vertex(1).pos3d.z+Triangle.Parent_Center.z)
    dV2 = Triangle.Vertex(2).V/(Triangle.Vertex(2).pos3d.z+Triangle.Parent_Center.z) - Triangle.Vertex(1).V/(Triangle.Vertex(1).pos3d.z+Triangle.Parent_Center.z)

    dr2 = Triangle.Vertex(2).color.r - Triangle.Vertex(1).color.r
    dg2 = Triangle.Vertex(2).color.g - Triangle.Vertex(1).color.g
    db2 = Triangle.Vertex(2).color.b - Triangle.Vertex(1).color.b

    if dY2 <> 0 then
       
        dYDiv = 1/dY2
       
        zSlope2 = dZ2 * dYDiv
        _zSlope2 = d_Z2 * dYDiv
       
        Slope2 = dX2 * dYDiv
       
        USlope2 = dU2 * dYDiv
        VSlope2 = dV2 * dYDiv
       
        RSlope2 = dR2 * dYDiv
        GSlope2 = dG2 * dYDiv
        BSlope2 = dB2 * dYDiv
       
    else
       
        zSlope2 = 0
        _zSlope2 = 0
       
        Slope2 = 0
       
        USlope2 = 0
        VSlope2 = 0
       
        RSlope2 = 0
        GSlope2 = 0
        BSlope2 = 0
    End if
   
   
    '' interpolate 0 to 2
   
    dZ3 = Triangle.Vertex(0).pos3d.z - Triangle.Vertex(2).pos3d.z
    d_Z3 = 1/(Triangle.Vertex(0).pos3d.z+Triangle.Parent_Center.z) - 1/(Triangle.Vertex(2).pos3d.z+Triangle.Parent_Center.z)
   
    dX3 = Triangle.Vertex(0).pos2d.x - Triangle.Vertex(2).pos2d.x
    dY3 = Triangle.Vertex(0).pos2d.y - Triangle.Vertex(2).pos2d.y
   
    dU3 = Triangle.Vertex(0).U/(Triangle.Vertex(0).pos3d.z+Triangle.Parent_Center.z) - Triangle.Vertex(2).U/(Triangle.Vertex(2).pos3d.z+Triangle.Parent_Center.z)
    dV3 = Triangle.Vertex(0).V/(Triangle.Vertex(0).pos3d.z+Triangle.Parent_Center.z) - Triangle.Vertex(2).V/(Triangle.Vertex(2).pos3d.z+Triangle.Parent_Center.z)

    dr3 = Triangle.Vertex(0).color.r - Triangle.Vertex(2).color.r
    dg3 = Triangle.Vertex(0).color.g - Triangle.Vertex(2).color.g
    db3 = Triangle.Vertex(0).color.b - Triangle.Vertex(2).color.b

    if dY3 <> 0 then
       
        dYDiv = 1/dY3
       
        zSlope3 = dZ3 * dYDiv
        _zSlope3 = d_Z3 * dYDiv
       
        Slope3 = dX3 * dYDiv
       
        USlope3 = dU3 * dYDiv
        VSlope3 = dV3 * dYDiv
       
        RSlope3 = dR3 * dYDiv
        GSlope3 = dG3 * dYDiv
        BSlope3 = dB3 * dYDiv
       
    else
       
        zSlope3 = 0
        _zSlope3 = 0
       
        Slope3 = 0
       
        USlope3 = 0
        VSlope3 = 0
       
        RSlope3 = 0
        GSlope3 = 0
        BSlope3 = 0
       
    End if
   
   
    '' Drawing
   
    '' Top
   
    dim as single CurX1=Triangle.Vertex(0).pos2d.x, CurX2=Triangle.Vertex(0).pos2d.x
    dim as single CurU1, CurU2,_
                  CurV1, CurV2
   
    dim as single CurR1=Triangle.Vertex(0).Color.r,_
                   CurG1=Triangle.Vertex(0).Color.g,_
                   CurB1=Triangle.Vertex(0).Color.b,_
                   CurR2=Triangle.Vertex(0).Color.r,_
                   CurG2=Triangle.Vertex(0).Color.g,_
                   CurB2=Triangle.Vertex(0).Color.b
   
    dim as single CurZ1=Triangle.Vertex(0).pos3d.z, CurZ2=Triangle.Vertex(0).pos3d.z
    dim as single Cur_Z1, Cur_Z2
   
    CurZ1 += Triangle.Parent_Center.z
    CurZ2 += Triangle.Parent_Center.z
   
    CurU1 = Triangle.Vertex(0).U/CurZ1
    CurV1 = Triangle.Vertex(0).V/CurZ1
    CurU2 = Triangle.Vertex(0).U/CurZ1
    CurV2 = Triangle.Vertex(0).V/CurZ1
   
    Cur_Z1 = 1/CurZ1
    Cur_Z2 = 1/CurZ2
   
    'BufferIter = Triangle.Vertex(0).pos2d.y * xRes
   
    For y as integer = Triangle.Vertex(0).pos2d.y to Triangle.Vertex(1).pos2d.y-1
       
        TSLine(CurX1,CurX2,y,CurU1,CurV1,CurU2,CurV2, CurZ1, CurZ2, Texture,CurR1,CurR2,CurG1,CurG2,CurB1,CurB2,Cur_Z1,Cur_Z2)
       
        CurZ1 += zSlope1
        CurZ2 += zSlope3
       
        Cur_Z1 += _zSlope1
        Cur_Z2 += _zSlope3
       
        CurU1 += USlope1
        CurU2 += USlope3
        CurV1 += VSlope1
        CurV2 += VSlope3
       
        CurX1 += Slope1
        CurX2 += Slope3
       
        CurR1 += RSlope1
        CurR2 += RSlope3
        CurG1 += GSlope1
        CurG2 += GSlope3
        CurB1 += BSlope1
        CurB2 += BSlope3
       
        'BufferIter += xRes
       
    Next
   
    '' down
   
    CurZ1 = Triangle.Vertex(1).pos3d.z+Triangle.Parent_Center.z
    Cur_Z1 = 1/CurZ1
   
    CurU1 = Triangle.Vertex(1).U/CurZ1
    CurV1 = Triangle.Vertex(1).V/CurZ1
   
    CurX1 = Triangle.Vertex(1).pos2d.x
   
    CurR1 = Triangle.Vertex(1).color.r
    Curg1 = Triangle.Vertex(1).color.g
    Curb1 = Triangle.Vertex(1).color.b
   
    For y as integer = Triangle.Vertex(1).pos2d.y to Triangle.Vertex(2).pos2d.y-1
       
        TSLine(CurX1,CurX2,y,CurU1,CurV1,CurU2,CurV2, CurZ1, CurZ2, Texture,CurR1,CurR2,CurG1,CurG2,CurB1,CurB2,Cur_Z1,Cur_Z2)
       
        CurZ1 += zSlope2
        CurZ2 += zSlope3
       
        Cur_Z1 += _zSlope2
        Cur_Z2 += _zSlope3
       
        CurX1 += Slope2
        CurX2 += Slope3
       
        CurU1 += USlope2
        CurU2 += USlope3
        CurV1 += VSlope2
        CurV2 += VSlope3
       
        CurR1 += RSlope2
        CurR2 += RSlope3
        CurG1 += GSlope2
        CurG2 += GSlope3
        CurB1 += BSlope2
        CurB2 += BSlope3
       
    Next
   
End Sub

Can you see what's wrong in there ?
In the code, variables like _z or d_z or Cur_Z means 1/z (respectively  1/z, d(1/z) and Current1/Z) and I kept the name U and V to contain U/z and V/z.

Thanks in advance :)


(update in code)

You have almost certainly answered your own question, because you are not interpolating 1/z, but instead using your own z-buffer calculation and then multiplying that by a factor to use in your equation, then it' more than likely trying to fetch texels from way outside your texture map.

I sat down to read through the source, I am sorry, it's blurry to me with a lot of similar variables that I can't seem to keep track of easily. Anyway..

My advice to you would be to stick to interpolating 1/z.

In a nutshell, you should be doing something similar to this;

Interpolate U/Z, interpolate V/Z and interpolate 1/Z

To get your texels;

((U/Z) / (1/Z)) * Z = U
((V/Z) / (1/Z)) * Z = V

Something like that. It's been a long time since I did it, but I think that's about right.

It's not the fastest way of doing this but you should probably get it working this way first.

Some notes:

    if x1<x2 then
        zz1 = z1
        zz2 = z2
       
        _zz1 = _z1
        _zz2 = _z2
       
        itx1 = x1
        itx2 = x2
       
        Uu1 = u1
        Uu2 = u2
        Vv1 = v1
        Vv2 = v2
       
        sr1 = r1
        sr2 = r2
        sg1 = g1
        sg2 = g2
        sb1 = b1
        sb2 = b2
    else
        zz1 = z2
        zz2 = z1
       
        _zz1 = _z2
        _zz2 = _z1
       
        itx1 = x2
        itx2 = x1
       
        Uu1 = u2
        Uu2 = u1
        Vv1 = v2
        Vv2 = v1
       
        sr1 = r2
        sr2 = r1
        sg1 = g2
        sg2 = g1
        sb1 = b2
        sb2 = b1
    end if

better use a vertexstructure and just swap the pointers.
you don't even have to care about this if all polygons are defined in equal orientation and backface-culling is used to remove all polygons not facing the viewer (so the orientation of x1/x2 will never change).


    xDiv = 1/(itx2 - itx1)
   
    dR = xDiv * (sr2 - sr1)
    dG = xDiv * (sg2 - sg1)
    dB = xDiv * (sb2 - sb1)
   
    dZ = xDiv * (zz2 - zz1)

these gradients across your polygon are linear, this means they are the same for every scanline.
just calculate them once for the longest scanline (biggest deltax: highest precision).
this also means you just have to keep track of u,v,z of the left side of your polygon.

if y>=0 and y<yRes
you don't have to do this for every pixel of a scanline.
check this before you enter the inner loop.

if i>=0 and i<xRes then
don't do this for every pixel either.
instead just test how many pixels are "out" on the left side and update u,v,z (eg. deltaU*pixelsToSkip).
the pixels on the right can just be skipped.
when you interpolating x along your polygon edges, the starting "x" for each scanline is actually a floating-point value.
you should take this into account and update the starting u,v,z of each scanline by a fraction of your deltas (how much is missing from the actual floating-point "x" to the rounded integer-pixel-position).
this is necessary for "y", too and can incorporate clipping on the x/y-axes for free.

If (FOV - (-Camera.pos.z + CurZ))>0 then
if this is some approach of z-clipping, drop it. it doesn't work.
you must perform z-clipping before doing perspective division.
when z gets near 0 (and even flips sign right afterwards) your 2d-coordinates break.

ValU = U/Cur_Z
ValV = V/Cur_Z
this won't result in useful framerates because division is expensive.
instead calculate 1/z (and respective u,v) every 8 or 16 pixels and interpolate linearly between two pairs of perspective correct u,v. if you manage the latter with integer-precision only, you can get the division for free (fpu and cpu run in parallel), but you'll probably need some assembly here.
You can even interpolate u,v bi-linearly (across scanlines, for eaxmple between 4 points of a 8x8-grid):
on an average you just need to calculate two (depending on deltax) additional u,v on a scanline and can skip perspective divide for the next 7 scanlines.
If you want to look deeper into how certain division-algorithms (http://en.wikipedia.org/wiki/Division_(digital)) work, you can even approximate the next 1/z (since deltaz is usually small) by a single successive iteration and using the previous result as a starting point.

Cb = ((CurTex and 255))*b*0.003921  '' 1/255
Cg = ((CurTex shr 8) and 255)*g*0.003921
Cr = ((CurTex shr 16) and 255)*r*0.003921
as jim pointed out already, the float-to-integer conversion is expensive, too (and the precision is not necessary).
keep the interpolated r,g,b as integers with some additional fixed-point-precision (for example multiply all values by 2^16):
Cb = ((CurTex and 255) * (b shr 16) shr 8
(but this is essentially what they invented mmx (http://www.tommesani.com/MMXPrimer.html) for)
                   
CurTex = Texture.GFX[int(ValU*Texture.Size.x)+Texture.Size.x*int(ValV*Texture.Size.y)]
Same here (interpolate in integers). You can also try to make your textures' width a power of two, so you can replace the multiply by a shift.

Quoteuse the cross-product equation to determine if the points are clockwise or counter clockwise
Rotating the vertices and doing a cross product calc is cheap [...]

The cross-product of the rotated vertices of a triangle gives you the transformed normal-vector of the face.
you can compare it to the view-vector (by a dot-product) to see if it's facing in the same direction.
In camera-space the view-vector is simply (0,0,1) so you just have to look at the sign of the z-component of your (transformed) face-normal (which you can get by just a single dot-product).

Hey :)

Shockwave : Well, sorry for the blurry source ^^ Concerning the 1/z interpolation, the point is I also tried it :/ and several times ! But I don't know, maybe I just have to start again this sub..

hellfire : Thanks for all those useful advises/optimizations, I note them all for a future optimization session :p (for now I'm stuck with the perspective correct mapping stuff).
Just a note concerning the number of divisions in the sub : It's just a thing to test the texture mapping ; once it'll work, i'll reduce them drastically :)

Thanks ! I continue my peregrinations in the world of texture mapping :p



edit : Well, I started again the Sub coding but even if I payed attention to the u/z,v/z and 1/z interpolation, there's nothing to do, the result is .. Well let's say it's still not what I was expecting :p Here is a zip with the code and the compiled stuff. So after some reflexion, here is my thoughts :

- Maybe there's a problem with the world origin (Z origin is almost on the cubes line in what you can see in the exe), I guess signs are inverting somewhere ..
- I'm interpolating u/z,v/z and 1/z exactly like I was interpolating u,v, and z (excepted the fact that calculations are based on u/z,v/z and 1/z instead of u,v and z of course) and maybe I shouldn't, I don't know.

Anyway, I'm still on it and I can't wait to start optimizing and to code the clipping with the view frustum :)

edit-edit : In the exe, you can see the floor is rotating, it's totally normal :p it's here to test the mapping.

Code review looks OK, all except this bit

    CurZ1 += Triangle.Parent_Center.z
    CurZ2 += Triangle.Parent_Center.z
which I don't understand at all.  You need to make sure the z you have divided everything by is the z you use when you interpolate.


                ValU = (U_z/Cur_Z) '' ((U/Z)/(1/Z))
                ValV = (V_z/Cur_Z) '' ((V/Z)/(1/Z))

Good optimization, but you can still do

ooz = 1/z
ValU = U_z * ooz
ValV = V_z * ooz


Jim

Seems like you're nearly there :) Keep going!

A bit offtopic but might be handy if you start using meshes with more polygons:
You don't need O(n^2) for calculating per-vertex-normals.
Here's a short snippet from a C++ source:

// set vertex-normals to 0
for (i = 0; i < numVertices; i++)
  vertices[i].normal.set(0.0, 0.0, 0.0);

for (i = 0; i < numTriangles; i++)
{
  // 3 indices of triangle i into the vertex array
  int idx1= face[i][0];
  int idx2= face[i][1];
  int idx3= face[i][2];

  // get coordinates
  const Vector& v1= vertices[ idx1 ].pos;
  const Vector& v2= vertices[ idx2 ].pos;
  const Vector& v3= vertices[ idx3 ].pos;

  // calculate normal vector
  Vector n= (v2-v1) % (v3-v1)  // cross product

  // add face-normal to all adjacent vertices
  vertices[idx1].normal+= n;
  vertices[idx2].normal+= n;
  vertices[idx3].normal+= n;

  // store the face normal
  faceNormals[i]= n.normalize();
}

// normalize the vertex-normals
for (i = 0; i < numVertices; i++)
  vertices[i].normal.normalize();


Quote from: Jim on September 08, 2008
Code review looks OK, all except this bit

Code Select Expand


    CurZ1 += Triangle.Parent_Center.z
    CurZ2 += Triangle.Parent_Center.z
which I don't understand at all.  You need to make sure the z you have divided everything by is the z you use when you interpolate.

well in fact when I start my interpolation calcs, I use :
dZ2 = Triangle.Vertex(2).pos3d.z - Triangle.Vertex(1).pos3d.z

Even if I was using
dZ2 = (Triangle.Vertex(2).pos3d.z+TriangleCenter) - (Triangle.Vertex(1).pos3d.z+TriangleCenter)
it'd be the same result.

But I have to start interpolation on the good Z value by adding the objectCenter to it : each object vertex have their coordinates in object Space (Origin = object Center)

I tested to add triangleCenter to the vertices before calculating slopes but it's worse :S But strangely (or not?), for the 1/z interpolation, if I use 1/(z+objCenter), it doesn't work at all

Quote

Code Select Expand


                ValU = (U_z/Cur_Z) '' ((U/Z)/(1/Z))
                ValV = (V_z/Cur_Z) '' ((V/Z)/(1/Z))

Good optimization, but you can still do

Code Select Expand


ooz = 1/z
ValU = U_z * ooz
ValV = V_z * ooz


ah yeah, didn't noticed this one :p thanks


Shockwave : I'm still on it !  ;D


hellfire : ah cool :)  as far as I can understand, it calculates the normal on a vertex only 1 time instead of NbAdjacentTriangles times ?

I just compiled your source, added a texture and it looks fine.
What's the problem?...

o_O well, Its way better looking for you, it's strange. Anyway, look on the cubes side, we can see a non-well-textured triangle :S

Still, I can't understand why your floor's good looking while mine is completely distorted in the middle...  you only changed your texture ? Same Size ?

When I compile and run it on a different pc, the floor is black.

My guess to that, division by 0 somewhere, or division overflow.

Jim

- division by zero is really probable ! But since it wasn't making my computer to crash, I though the compiler was handling this. But as I see, it really depends about the computer .. grah :S

- division overflow ?

Thanks for the feedback, step by step, i'm sure i'll find where the bug comes from :)

YEEEEEYYYYYY !!!

Well I got something I think :D
I added an arbitrary number while dividing by Z :


_z1 = 1/(Triangle.Vertex(0).pos3d.z+triangle.parent_center.z+1000)
_z2 = 1/(Triangle.Vertex(1).pos3d.z+triangle.parent_center.z+1000)
_z3 = 1/(Triangle.Vertex(2).pos3d.z+triangle.parent_center.z+1000)


Since you spoke about division by 0, I expected it to be in the middle of the plane (its origin) so I added a number (here, 1000) to the divisor and it seems to work for me. The perspective mapping is still not perfect though :/ Anyway, it's way better :D

Here is a screen and a zip(code+exe+textures)



edit : Anyway, it's not a good solution since I could have large objects but far from the observer, And for those objects, I'd need to change the +1000 to a bigger value (it's a totally arbitrary number).. So in fact, i'm just moving the problem here .. I need to find a solution really resolving the problem :/

Well done!

"z=0" should be at the position of the camera.
anything that's behind it will be clipped anyway and your problem is solved.

yeah I though about it but my projection equation is :

zDiv = 1/(ZOOM + obj.Triangle(i).Vertex(j).ViewPos.z)

obj.Triangle(i).Vertex(j).pos2d.x = xRes*.5 + FOV * obj.Triangle(i).Vertex(j).ViewPos.x * zDiv
obj.Triangle(i).Vertex(j).pos2d.y = yRes*.5 - FOV * obj.Triangle(i).Vertex(j).ViewPos.y * zDiv


Do you think I can get out the ZOOM term without any distortion in some big objects ?

(Well, I just tested, And geting off the zoom term is way better in fact, FOV is much more effective)

A last question about the mapping though : Did you notice there are still some texture deformations when the triangles are close ? Is it normal (an effect I can't avoid) or is there still something not working here ?

thanks again !

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,

thanks :)

QuoteJust 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

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!

QuoteDid 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.

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)

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 ^^

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).

QuoteI 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 (http://www.exaflop.org/docs/fatmap)):

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;
   }
}


hey nice cube :D Thanks a lot for the code  :clap: 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

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:
x'= x / z
y'= y / z
Coordinates (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).

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.

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 !

Quoteclipping [...] 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:

   #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)

   // 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:

   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


hey :)

QuoteYou 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 :)

QuoteNow 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)

QuoteWon'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.

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

thanks again !

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 !!! :updance:

(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 ! :D

thanks !

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.

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 :
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.

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

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


And a list of indices building triangles from the vertcies:
2,0,3 1,0,2
The 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:

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


A possible (no-overlapping) triangulation would be:
0,1,2  0,2,3  0,3,4  0,4,5
Does that already look like an algorithm? :)

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 :D

Hey :)

QuoteDoes 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 :

'' 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.

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:

            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:
            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


hey :)

ok, I see the point, I changed the FOV in zoom and aspect ratio and "putted" them in the camera space transformation. I understood the point with the logical error too. big k++ to you for all your help !! I continue to work on it and I'll post stuff once there'll be new stuff :)

thanks again !!

It may not be there yet Hezad but the speed increase already is nice, it was running at around 20fps before, it's not at about 36fps (default zoom), it gets much faster if I zoom it out and crashes if I zoom it in ;)

hehe cool for the speed increase :P And 'glad to see you back shockwave :D

Some news : I'm almost there !!

After days of trying to find a bug making my program to continue to crash, I think I got something ! Now the program don't crash anymore, and it even looks like the Left plane clipping works perfectly. Here is the program if you wanna test (You can still move with the keyboard arrows) :D

Well, there are still glitches with the bottom, right and top clipping .. But I'm glad, I thought I were really stuck here :p



EDIT :
Another good new !! I fixed the Perspective correct mapping bug, now the texture mapping works perfectly :D It looks ... so much better hehe ! The attached file is a version without this correction, i'll post this version later. Just have to finish the clipping, to code the backface culling and to optimize/reorganize a bit the code and then ... Mip Mapping !  :D  (or maybe the camera handling before :p)

You're really making great progress!
I'm just wondering why you sometimes start your arrays at index 0 and sometimes at index 1 ?

uhuh I edited my message at the same time ^^

thanks !

Concerning the arrays, some are starting at index 1 because I used an iteration variable the fill the array which starts to be incremented before the assigning values to the array.

eg : Iter+=1 : Array(iter) = stuff

so the array is used from 1 instead of 0 :P

Quotesome are starting at index 1

and you don't find that confusing?

Well ... lol not really, I'm pretty habituated, I do it all the time (yeah it's not a good habit :s ..)

hum.. But it'd be a good thing to change this habit .. let's start right now :p

Hi again folks :)

well, I know capital letters are not really welcome on boards but .. this time it's so awesome ..


CLIPPING IS NOW FULLY WORKING !!!! YEYHOO !

Dudes, I don't know how many hours I spent to find what wasn't working, I was almost desperate about it ^^ So it is really, really a liberation to see those cubes moving without any glitches and at ~15 FPS  :updance:  :updance:  :updance:

Oh and like I said in a previous recent post, I found what wasn't working in perspective mapping too ! So The clipping works, but the perspective correct texture mapping also works perfectly (on my computer though .. your turn to say me if it works on yours :D )

Once again, thanks A LOT to hellfire who spent a lot of time to help me with clipping.

Well done! (http://www.c-plusplus.de/forum/images/smiles/live.gif)
Runs at ~30fps (Intel Core2 3Ghz) and ~20fps (Core2 2Ghz), I guess you can easily make it 60 without even touching assembler.
But before you get your hands dirty in optimization, please take some time to think about conception and class design.

look great....run 25FPS ( mine is E6750)  The checkboard look great.

welldone

:cheers:

hellfire :
thanks :D So what would you advise me ? Using kind of a pipeline ?

eg :

- Objects Declaration (User Side)
- Objects Characteristics [texture, shader, rotation, translations] (User Side)
- Store everything in a Global Render List (Engine side)
- Calculate Shaders (Engine Side)
- Calculate Clipping + Projection (Engine Side)
- Render

and/or do you speak about totally changing the way I use my UDT's ?
Concerning the modularization, I thought about putting all engine subs in a .bi file and putting all the objects creation helping subs in another one.

I remember you spoke about materials but I thought I can create functions that create textures from procedural materials and a special type which could handle materials layers handling
e.g. in pseudo code :


Type Single_Material
   Tex as Texture
   Opacity as integer
   MapType as integer       '' (BumpMap, TextureMap, ColorMap, etc?)
End Type

Type Material
   Layers(NBLAYERS) as Single_Material
End type

CurrentObject = Apply_Material(Current_Material)



And then using the MapType variable before rendering to know which kind of Material to calculate.

Don't know if it's a good idea though :p


HotShot :

thanks :D

Works really nice here too, no clipping bugs at all.

When Hellfire talks about classes he does mean types, yep. I will suggest once you have that implimented that you add backface culling and mip mapping which will give you a further speed boost.

It looks bloody good thought Hezad.

Fair play to you.

Some notes:

In software-rendering, poly- and pixel-throughput are precious, so you'll usually have many special-case-optimized polyfillers.
In my renderer I used a "Material" class which creates all required vertex-data from a mesh and contains the polygon-rasterization-code.

The 3D-models (or complete scenes including animation) are usually loaded from files (exported from your favourite 3d-package).
For testing & debugging reasons my "Mesh" class has some static methods to create some simple objects like cube, cylinder, sphere or torus:
Mesh *mesh= Mesh::createTorus(100, 40);
Here "Mesh" is one of several object-types (all derived from one base-class) that are stored in a scene-tree (the hierarchical structure might not be required for you yet) and basically contains all information that can be applied by the 3d-software.
To get things rendering, I just need to assign it to a material:
Material *mat= new TextureGouraud(scenetree, Texture("texturefilename") );
mat->addMesh(mesh);

Here "Texture" can either be a bitmap loaded from a file or something procedurally generated (it just needs to derive from the same interface-class).

For rendering I just parse the material-list (stored in the scene-tree) and draw everything that got assigned.
The material has a "transform"-method to put the object where it belongs (multiply vertices by mesh' and camera's matrix) and to create all vertex-attributes; here: calculating rgb-values from vertexnormals and lights (which are also stored in the scene-tree, accessible by the material).
When that's done, polygon's are culled, clipped (each material has a vertex-class with a method for interpolation) and drawn.

For animation, each object has several animation-tracks which store position, rotation, scaling at certain timestamps (and interpolate in between).
"Procedural" animation (like deforming vertices) is job of the "Material", too (since it resambles the vertex-shader part).
Other approaches would just manually updated the mesh' transformation-matrix.

QuoteWhen Hellfire talks about classes he does mean types

True. "Classes" were mentioned a couple of times in the freebasic documentation, but I just realized they don't exist: :-\

QuoteThis keyword is supported in the latest fbc compiler, however, its usefulness is limited since classes and inheritance are not yet supported.

This is a knockout for most structured design strategies...

Hey :)

Shockwave :

QuoteWorks really nice here too, no clipping bugs at all.

When Hellfire talks about classes he does mean types, yep. I will suggest once you have that implimented that you add backface culling and mip mapping which will give you a further speed boost.

Glad to hear it works :) Backface culling was implemented just after the previous release :) Mip-Mapping is on the todo list, right after the pure code optimization part :) I'll start optimization with using Integers instead of singles most of the time. Then, I'll read once again all the thread to remind myself stuff people told me about optimization but forgotten ;D and then, MIPMAPPING :D

Quote
It looks bloody good thought Hezad.

thanks a lot shockwave  :cheers:



hellfire :

QuoteIn software-rendering, poly- and pixel-throughput are precious, so you'll usually have many special-case-optimized polyfillers.
In my renderer I used a "Material" class which creates all required vertex-data from a mesh and contains the polygon-rasterization-code.

The 3D-models (or complete scenes including animation) are usually loaded from files (exported from your favourite 3d-package).
For testing & debugging reasons my "Mesh" class has some static methods to create some simple objects like cube, cylinder, sphere or torus:
Code:

Mesh *mesh= Mesh::createTorus(100, 40);

Here "Mesh" is one of several object-types (all derived from one base-class) that are stored in a scene-tree (the hierarchical structure might not be required for you yet) and basically contains all information that can be applied by the 3d-software.
To get things rendering, I just need to assign it to a material:
Code:

Material *mat= new TextureGouraud(scenetree, Texture("texturefilename") );
mat->addMesh(mesh);

Here "Texture" can either be a bitmap loaded from a file or something procedurally generated (it just needs to derive from the same interface-class).

Thanks for that, I just implemented a start for a material UDT which I can edit in a similar way of OpenGL surface creation (I'll put here an example at the end of the post). Added a naive bmp loader for textures too. I also replaced the objects creation functions with Object Type subs.

QuoteFor animation, each object has several animation-tracks which store position, rotation, scaling at certain timestamps (and interpolate in between).
"Procedural" animation (like deforming vertices) is job of the "Material", too (since it resambles the vertex-shader part).
Other approaches would just manually updated the mesh' transformation-matrix.

Animation is not planned for now :p But I didn't know I can use materials to implement it :)

QuoteQuote
When Hellfire talks about classes he does mean types
True. "Classes" were mentioned a couple of times in the freebasic documentation, but I just realized they don't exist: Undecided

Badly true :P But Freebasic's UDTs permits already some interesting stuff (Type Subs/functions, Constructors, destructors, properties, Operators), it's totally sufficient for what I wanna do now :)

QuoteThis keyword is supported in the latest fbc compiler, however, its usefulness is limited since classes and inheritance are not yet supported.
This is a knockout for most structured design strategies...

Well I guess so, but since I don't really know all classes stuff, UDT's are fine for me now ^^




Engine News :

Before starting optimizations,  I wanted to modularize and reorganize a bit my code to help comprehension. So here are the news :

- Modularization : code broken into smaller header files (Engine.bi, DataTypes.bi, Materials.bi)
- Texture BMP loader
- Backface Culling
- /!\ New material Type to handle .. well, materials :p
        + Effective way (I hope) to create/edit materials in code
- Texture tiling routine
- Changed textures of the example for realistic ones


An example of material editing :




Dim as ObjectT MyObject

MyObject.GenerateCube(x0,y0,z0,SideSize)

Dim as TextureT CubeTex

CubeTex.LoadBMP "Texture_Cube.bmp"


Dim as MaterialT CubeMaterial

CubeMaterial.Edit
   
    Mat_Shader GOURAUD_SHADER
   
    Mat_Texture CubeTex,tileX,tileY

    Mat_Diffuse r,g,b

    Mat_ambient r,g,b

CubeMaterial.End_Edit

MyObject.Assign_Material CubeMaterial


And a screenshot with the new textures attached

Everything sounds plausible, I'm just wondering what this does:

Quote- Texture tiling routine

Usually you would make sure your texture-width/height is a power of two, scale your uv-coordinates and  and mask the appropriate bits ("and" instead of modulo).

Quotea material UDT which I can edit in a similar way of OpenGL

It's a good idea to follow standards, but remember that OpenGL's material-model was build around sgi's hardware-capabilities and is sometimes rather unflexible and you'll often want to take some shortcuts in order of optimization.
The important point is to offer the relevant features required to achieve certain effects.
If you want to get some ideas about how to use materials & lighting professionally, I can recommend this book:
(http://pixhost.eu/avaxhome/gfxworld/2006-12-06/1562059548.jpg) (http://www.3drender.com/light/index.html)

QuoteEverything sounds plausible, I'm just wondering what this does:
Quote
- Texture tiling routine
Usually you would make sure your texture-width/height is a power of two, scale your uv-coordinates and  and mask the appropriate bits ("and" instead of modulo).

I multiply (U,V) values of each vertex by NbTileX and NbTileY and then, while rendering, I check if final(u,v) is > 1. If it's the case, I do this :


if ValU>1 then ValU = ValU-int(ValU)
if ValU<0 then ValU=0
if ValV>1 then ValV = ValV-int(ValV)
if ValV<0 then ValV=0

It gives me ValU after int(ValU) repetitions.

QuoteIt's a good idea to follow standards, but remember that OpenGL's material-model was build around sgi's hardware-capabilities and is sometimes rather unflexible and you'll often want to take some shortcuts in order of optimization.
The important point is to offer the relevant features required to achieve certain effects.

Well, in fact I asked myself "what would I like to do for editing a material when coding with a 3d library ?" and I thought about this way. I have to admit I really didn't think about standards, This engine is not supposed to follow the standards since it surely won't be used excepted by myself ^^

QuoteIf you want to get some ideas about how to use materials & lighting professionally, I can recommend this book:

Some ideas, yep ! But I really don't want to code a professional product, I'd be incapable of doing that :p Just a personal learning tool and -hopefully- a nice gadget tool for people demos and/or code wanderings in the future :) But if I plan to buy a 3d book, I'll firstly look for this one :)

Quote from: Hezad on September 25, 2008

QuoteIf you want to get some ideas about how to use materials & lighting professionally, I can recommend this book:

Some ideas, yep ! But I really don't want to code a professional product, I'd be incapable of doing that :p

I don't know about that.. All you need to do is what you've done. Break it down into bits and work on it a bit at a time, even appreciating that it's not a professional product you would surely find some useful things in that book to help you improve the engine even more :)

Quote from: Hezad on September 25, 2008
But if I plan to buy a 3d book, I'll firstly look for this one :)

Enter a competition and win it and I'll buy the book for you :)
The prize fund for the remakes comp is £50 because it's joint sponsored by me and Rbz :) Normally they are half that amount.

Quoteeven appreciating that it's not a professional product you would surely find some useful things in that book to help you improve the engine even more Smiley

Yeah i'm sure about it :) I just wanted to underline the fact that my objectives are not professionals at all : They are just "let's make something beautiful (hopefully) and functional".

It doesn't change the fact this book looks bloody interesting :P

QuoteEnter a competition and win it and I'll buy the book for you Smiley
The prize fund for the remakes comp is £50 because it's joint sponsored by me and Rbz Smiley Normally they are half that amount.

:D Neat idea ! I'm not sure I will enter the comp since I don't have a good demo-scene culture, but i'll look for demos not remade yet ; maybe there will be one I want to work on ^^

Hey :) It's me again !

I'm trying to write a GenerateSphere Procedure ; having a curved surface is pretty useful for testing shaders/lighting ^^ (yeah, I wanted to relax a bit before entering the frightening world of optimization :D)

The routine works almost well : the sphere shape is well generated, the U,V values too. But there's a problem with the shading ! I use the Gouraud shader and some parts are ok, but some other parts looks like it was shaded with a flat shader :S or worse : it can look like the vertices color are inverted on some triangles (a dark vertice becomes bright and vice versa). Here is a screenshot to illustrate what I'm saying.

Here is the procedure :

Sub ObjectT.GenerateSphere(x0 as integer, y0 as integer, z0 as integer,Radius as integer,nbfaces as integer)
       
        '' x = r sin(theta) cos(phi)
        '' z = r sin(theta) sin(phi)
        '' y = r cos(theta)

        this.Center.x = x0
        this.Center.y = y0
        this.Center.z = z0
       
        dim as single dTheta, dPhi,UAng,Vang,UAng2,Vang2
        dim as integer ActualTri = 1
       
        dTheta = PI/nbFaces : dPhi = PIx2/nbFaces
       
        for theta as single = 0 to PI step dTheta
            for Phi as single = 0 to PIx2 step dPhi
               
                Uang = phi/PIx2
                Vang = Theta/PI
                Uang2 = (phi+dPhi)/PIx2
                Vang2 = (Theta+dTheta)/PI
               
                if theta<>0 and theta<>PI then
                    triangle(ActualTri).Vertex(0).pos3d.x = Radius * sin(theta) * cos(Phi)
                    triangle(ActualTri).Vertex(0).pos3d.y = Radius * cos(theta)
                    triangle(ActualTri).Vertex(0).pos3d.z = Radius * sin(theta) * sin(phi)
                    triangle(ActualTri).Vertex(0).U = Uang
                    triangle(ActualTri).Vertex(0).V = Vang
                   
                    triangle(ActualTri).Vertex(1).pos3d.x = Radius * sin(theta+dTheta) * cos(Phi)
                    triangle(ActualTri).Vertex(1).pos3d.y = Radius * cos(theta+dTheta)
                    triangle(ActualTri).Vertex(1).pos3d.z = Radius * sin(theta+dTheta) * sin(phi)
                    triangle(ActualTri).Vertex(1).U = Uang
                    triangle(ActualTri).Vertex(1).V = Vang2
                   
                    triangle(ActualTri).Vertex(2).pos3d.x = Radius * sin(theta) * cos(Phi+dPhi)
                    triangle(ActualTri).Vertex(2).pos3d.y = Radius * cos(theta)
                    triangle(ActualTri).Vertex(2).pos3d.z = Radius * sin(theta) * sin(phi+dPhi)
                    triangle(ActualTri).Vertex(2).U = Uang2
                    triangle(ActualTri).Vertex(2).V = Vang
                   
                end if
               
                ActualTri +=1
               
                If Phi <> PIx2 then
                    triangle(ActualTri).Vertex(0).pos3d.x = Radius * sin(theta) * cos(Phi+dPhi)
                    triangle(ActualTri).Vertex(0).pos3d.y = Radius * cos(theta)
                    triangle(ActualTri).Vertex(0).pos3d.z = Radius * sin(theta) * sin(phi+dPhi)
                    triangle(ActualTri).Vertex(0).U = Uang2
                    triangle(ActualTri).Vertex(0).V = Vang
                   
                    triangle(ActualTri).Vertex(1).pos3d.x = Radius * sin(theta+dTheta) * cos(Phi)
                    triangle(ActualTri).Vertex(1).pos3d.y = Radius * cos(theta+dTheta)
                    triangle(ActualTri).Vertex(1).pos3d.z = Radius * sin(theta+dTheta) * sin(phi)
                    triangle(ActualTri).Vertex(1).U = Uang
                    triangle(ActualTri).Vertex(1).V = Vang2
                   
                    triangle(ActualTri).Vertex(2).pos3d.x = Radius * sin(theta+dTheta) * cos(Phi+dPhi)
                    triangle(ActualTri).Vertex(2).pos3d.y = Radius * cos(theta+dTheta)
                    triangle(ActualTri).Vertex(2).pos3d.z = Radius * sin(theta+dTheta) * sin(phi+dPhi)
                    triangle(ActualTri).Vertex(2).U = Uang2
                    triangle(ActualTri).Vertex(2).V = Vang2
                   
                end if
               
                ActualTri +=1
            next
        next
       
        this.nb_triangles = ActualTri
       
    End sub

Any idea of what could make this procedure to bug ?

Thanks :D

It looks flat shaded tbh, it's probably a problem of normals.

Unit normals for a sphere are easy to generate fortunately, just generate a sphere with a radius of 1 for them :)

I'll try to calculate the normals by myself while generating the sphere then. But those normals should be okay since I have a procedure which precalculate automatically all normals :p

thanks for the advice anyway, I'll try it :)

Hazad, you are creating 3 independant vertices for each triangle.
Later you're calculating the per-vertex-normal by averaging the normals of all triangles adjacent to the a vertex.
But there is just one triangle (because there are no shared vertices) and it's the same for each vertex of triangle.
So you got exactly the same normal for each vertex of a face - which results in perfect flatshading :)

You probably do not want to store three (unshared) vertices per triangle, but instead store each vertex only once and, additionally, create a triangle-table storing three indices into the list of shared vertices.

This will save you quite a lot of transformation-work because in the average case a mesh has only half as many vertices as triangles.
Since you're now creating 3 vertices per triangle, you have six times as many vertices as are actually required...

Example:

Vertices:

Vector vertices[12]= {
  0, 32.647, 0,
  29.2, 14.6, 0,
  9.0233, 14.6, -27.771,
  -23.623, 14.6, -17.163,
  -23.623, 14.6, 17.163,
  9.0233, 14.6, 27.771,
  23.623, -14.6, -17.163,
  -9.0233, -14.6, -27.771,
  -29.2, -14.6, 0,
  -9.0233, -14.6, 27.771,
  23.623, -14.6, 17.163,
  0, -32.647, 0
};


Faces:

int triangles[20*3]= {
  0, 1, 2,
  0, 2, 3,
  0, 3, 4,
  0, 4, 5,
  0, 5, 1,
  1,10, 6,
  2, 6, 7,
  3, 7, 8,
  4, 8, 9,
  5, 9,10,
  6, 2, 1,
  7, 3, 2,
  8, 4, 3,
  9, 5, 4,
10, 1, 5,
11, 7, 6,
11, 8, 7,
11, 9, 8,
11,10, 9,
11, 6,10
};


Hey :)

I totally understood this :

QuoteYou probably do not want to store three (unshared) vertices per triangle, but instead store each vertex only once and, additionally, create a triangle-table storing three indices into the list of shared vertices.

thanks to the examples, and I like it :p

But there's something I don't understand :

QuoteLater you're calculating the per-vertex-normal by averaging the normals of all triangles adjacent to the a vertex.
But there is just one triangle (because there are no shared vertices) and it's the same for each vertex of triangle.

Why is there no shared vertices ? I mean, even if I don't use a vertex list/triangle table for now, there's a routine in my precalc_normals procedure which finds which vertex is shared with another (The way I do this is surely not the best way to do it, but I was expecting it to work at least :p)

And a last question, about the vertex list and the triangle table : Do you recommend me to use this approach in all the engine ? Or just while generating objects ? Because using it all along the code scares me a bit : I should change almost all the code when it comes to vertex handling !

My mistake, in my explanating I forget that you don't have indices at all.

In your PreCalc_Object_Normals function you check for each vertex of a triangle, if there's any other triangle with the same vertex-position. In theory this should work - but it doesn't because in SamePnt you're comparing two floating-point values for equality - which fails.
That's because the fpu internally calculates at a precision of 80bit while you're storing values at single(32bit) precision, so you can assume every assignment to a variable as rounding.

Reordering two iteration of your loop results in something like this:

u1 = round (phi/PIx2)
u2 = round ((phi+dPhi)/PIx2)
phi= round (phi+dPhi)
...
u3 = round (phi/PIx2)

Here u1 and u3 are not equal because of different rounding (the difference is rather small though).
That's why you can't find any adjacent triangle when calculating the normals.

The usual aproach for comparing floating-point values is something like this:
if abs(a-b)<EPS then equal

Quoteabout the vertex list and the triangle table:
Do you recommend me to use this approach in all the engine ?

Absolutely yes because you have much few vertices to transform and require less memory.
When you're at some point going for 3d-acceleration, this approach is also supported in hardware (index-buffers).

Another thing I noticed is that your vertex-structure is rather big. I recommend to split it into multiple arrays because you're now piping a lot of useless data through the cache when accessing a vertex (the polyfiller for example is not interessted in untransformed 3d-coordinates or normals).

rah supa k++ to you ^^ it works perfectly ! thanks a lot for finding the problem. I didn't know this stuff about rounding, I'll remember that !!

QuoteAbsolutely yes because you have much few vertices to transform and require less memory.
When you're at some point going for 3d-acceleration, this approach is also supported in hardware (index-buffers).

Another thing I noticed is that your vertex-structure is rather big. I recommend to split it into multiple arrays because you're now piping a lot of useless data through the cache when accessing a vertex (the polyfiller for example is not interessted in untransformed 3d-coordinates or normals).

Noted, I'll work on that then :)

Nice image :)

I thought it was a normals problem, glad you got it sorted out :) Can't wait to see it working!

Hey :D Well, I just finished to implement Mip Mapping :D

QuoteNice image Smiley

thanks ^^ I hope you'll like this version !

Well it's not filtered yet (or yes it is, but just an average of 4 colors on each stage) and there is still some flickering (not much though, excepted on the checkered sphere, it's awful oO but I think it's a problem with my MipMap generation routine).

I decided to set version numbers from now on, it'll be easier (even for me) to see what's new and when. Oh and I already heard some complaints (not here ^^) about the fact I don't respect the version number norms but whatever :P

So, here is the changes list :D :

Quotev0.02 Changes List



MAJOR :

- Added MipMapping handling !
  > Set_Mipmapping(ON/OFF) to set it.. well.. ON or OFF :D
  > LOD bias constant for now
  > No filtering yet (Bilinear planned)

- Added GenerateMipMap() procedure.
  > Generates MipMap GFX or loads it if file exists.

- Added Light Fall Off coefficient.
  > Permits Light intensity to fall off with distance between objects and lights.

- Added Object.GenerateSphere() procedure.
  > GenerateSphere (x0, y0, z0, Radius, Subdivisions)



Minor :

- TSLine and GLine subs replaced with macros.
- Some minor optimization.

I should work on optimization and on the vertex list / triangle table hellfire spoke about but I don't know yet how to start (I tried the vertex list/triangle table, but when I do this, I lost all information about U,V coordinates, normals, etc.. but I'm thinking about it :) ).
And concerning pure optimization, I still have lot of work to do, I haven't converted singles to integers, and I surely have some divisions/multiplications I could precalculate ...




edit : This version crashes on some computers ..

It locked up here after opening the screen unfortunately mate.

Illegal array access? Drawing something off screen?

Argh, problems coming ^^

Hum .. Could you compile the code without using Mip mapping please ? (beginning of test_gouraud.bas, change Set_MipMapping ON to MipMapping OFF). If you can't compile, I'll compile a version without mipmapping.

QuoteDrawing something off screen?

Hum .. Well, normally, it shouldn't be possible thanks to clipping

QuoteIllegal array access?

or pointer.
That would be much more probable since the mipmap processing uses different textures sizes, it could use a wrong size and look for a color outside the pointer/array .. But now, why does it work for me then ?

thanks for feedback :)


edit : aargh wait a minute ! I just remembered the fact that the mipmap pointers are not deallocated !! I forgot :P It could be the problem source I guess ? I fix it and I repost the .rar here :)

I cant compile it unfortunately since I have an old version of FB here, but what you said about pointers sounds likely to be the cause.

Something else that you should look into are any new floating point stuff you've got in there too.

I once had a bug whereby I was trying to convert a floating point varialbe into a colour value eg;

rgb (float,float,float)

I hadnt realised they were floats and it was crashing, it took me a while to figure it out.

PCs are strange like that.

I can code super illegal shit on my notebook, writing past buffer limits etc and it just runs it happily. On here it dies straight away.

I'll test your program on the laptop in a while too :)

QuoteI cant compile it unfortunately since I have an old version of FB here, but what you said about pointers sounds likely to be the cause.

No problem, I'll compile a "without Mipmapping" version :)

QuoteSomething else that you should look into are any new floating point stuff you've got in there too.

I once had a bug whereby I was trying to convert a floating point varialbe into a colour value eg;

rgb (float,float,float)

I hadnt realised they were floats and it was crashing, it took me a while to figure it out.

PCs are strange like that.

I can code super illegal shit on my notebook, writing past buffer limits etc and it just runs it happily. On here it dies straight away.

ah computers.. :P I'll check for the floats and colors stuff :)

QuoteI'll test your program on the laptop in a while too Smiley

cool :) grazie ^^


Now, I think I have something concerning the bug .. I wrote a destructor for my texture type to deallocate all the previously allocated pointers at the end but strangely, it makes the program to crash. It must be a sign ><

Something I noticed in your source you are using reserved keywords for commands etc, eg color in your type, and also pos. It's a good idea to call them something else, as the compiler may act up on you.

Also not sure if this'll work.


#include "fbgfx.bi" ' for constants


I'd put the comment part above the include. Also I tend to use #Include Once "includefile_example.bi".

Also, im not sure if it matters and theres a default, for calls to subs, with using ByVal before your variable name and its definition. eg Declare Sub Yo( ByVal PosX As Integer, ByVal PosY As Integer ). As in older versions there was either ByVal ( By Value ) or ByRef ( By Reference ). not 100% sure if that's been done away with in the newer FreeBASIC version.

Hey :)

About the reserved keywords, I think they can be used in user defined types as variables but not as subs (unless you undef them). But you're right, I should have good habits :p

About passing variables ByVal or ByRef, I think its ByRef by default on FB 0.18.xx (the version I use), but since other people could compile with other versions, and since the default may evolve in the next versions, I should always specify ByVal or Byref (what I don't do everywhere actually)

These are reasonable advices and I'll follow them right now, it may help for debugging ;)

Concerning the comment on the include statement, I only use fbfgx.bi for the scancodes constants and for now I only use them in the test source file (and this part works).

Thanks for (having take ? taken ? taking? arg I don't know ><) a look in the source :)

No worries mate, my few pennies worth that may assist you dude.

I can run the binary but when i press esc, visual studio asks me to select a debugger  ;D
When I recompile the source (with FreeBasic 0.2) it crashes right away,
when I disable mipmapping it works fine.
Error checking (-exx) reports:

QuoteAborting due to runtime error 12 ("segmentation violation" signal) in "materials.bi::LOADMIPMAP()"

Some notes about mipmapping:
What I've understood from a quick look at your source-code, you're now selecting a mipmap-level depending on the depth of a polygon.
Generally it's true that if a polygon is further away, it's also smaller and needs less texture-precision - but it's not a very clever approach (but some ps2 games use this way because the hardware doesn't support mipmapping and it's easy to do).
If you, for example, look from a steep angle at one side of a cube, this side is very narrow and only needs a low texture resolution - although the polygon might be very near to the viewer.

So let's assume you're interpolating texture-coordinates linearly (which is inevitable when you stop doing perspective divide for every pixel), a better approach is to look at the deltas for interpolating the texture-coordinates u & v across the scanline.
For example if one delta is >= 2.0 you'll always skip one texel when advancing to the next pixel. In such case you can savely use a mipmap with half the size.

For generating the mipmaps, you can simply scale the "current" mipmap to half the size on-the-fly (a simple 2x2 filter) so there's no reason to save all mip-levels.

hey hellfire :) thanks for the report !!! I tried to run with -exx but (I must be lame ^^) I never found the report :P

Okay, so it confirms what I was thinking, a segmentation violation. And in LoadMipmap. erm....



erm ...


*brain on fire* ^^

Okay I recap :
- A segmentation fault in LoadMipMap (so, surely pointer error or array error ... you have to know I use an array of pointers, in the new Texture Type (which handle MipMapping) in this way :
Texture.MipMap(NbLODS) as integer ptr
in which I keep the mipmaps image ptr

- A crash once the gfx screen opens (even on my computer this time) when I set the destructor of TextureT to destroy all the GFX contained in this type (Original size + MipMaps)

erm.. I continue to search in LoadMipmap :P



edit :
another thing you have to know, I store my images in integer ptrs. So to load bmps, since bload don't work with this kind of pointers as-is, I must do that :
Bload FileName, MipMap(CurrLOD)-8

If I get off the "-8", it don't work. It may come from here too since I use a cheat to load the bmps. But if it's the case, why did it work before and not now ?

Quotewhy did it work before and not now ?

Luck?  ;)

.. In those cases, I totally hate luck ><

:P Well so I guess the next step is a custom Bmp Loader ..

In your mipmap code, I think you need

        _pow2  = 1/(2^(CurrentLOD+1))
instead of
        _pow2  = 1/(2^CurrentLOD)

And remove the -8 from the bload
And change this bit
            MipMap(CurrLod) = Callocate(CurrX*CurrY-1+1000,Sizeof(integer))
I think the bload needs some more space for some reason.

Works for me then.

<edit>Look at the sample codes for bload and imagecreate
http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgBload (http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgBload)
http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgImagecreate (http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgImagecreate)
Seems you should use ImageCreate instead of Callocate and let FB worry about the image metadata size that it needs.

Jim

Ah ! Thanks a lot for that ! I'll upload the new exe with this post since I can't debug it at home (how to debug something which is working on your computer ?..  ;D)

strangely, getting off the "-8" on :
Bload fileN,this.GFX-8
makes my program to crash but inversely, the one you specified :

Bload MIPMAP_FOLDER+filen+"_MipMap"+str(CurrLOD)+".bmp",MipMap(CurrLOD)-8
doesn't make me crash if I get "-8" off.

Quote<edit>Look at the sample codes for bload and imagecreate
http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgBload
http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgImagecreate
Seems you should use ImageCreate instead of Callocate and let FB worry about the image metadata size that it needs.

Well in fact I totally agree, I should use ImageCreate with Any ptrs instead of Callocate with integer ptrs, but I started to code the engine using integer ptrs since I use them to directly write on the screen buffer. (And since the pointers returned with imageCreate have some headers and/or data before the image data, I don't know how to deal with them, I don't really want to use pset or put excepted on pre-rendering operations (like mipmap files writing))


Here are the new exes with those modifications (2 versions)

(too large to be attached here, links below)

- Engine With Mip Mapping (http://freefile.kristopherw.us/uploads/hezad/engine3d_with_mipmapping.rar)
- Engine without Mip Mapping (http://freefile.kristopherw.us/uploads/hezad/engine3d_with_no_mipmapping.rar)


In those versions, the GFX destructor is commented since it stills make me crash.

It's working pretty well now, but when you're approaching the checkered sphere from a distance, there's one point (very probably where you change from one mipmap to another) where the texture-coordinates "jump".

You have to get rid of all the -8 stuff.  There's no logic behind it.  You are effectively avoiding overwriting the end of your allocation and using -8 is making it overwrite the beginning instead.  Neither of these is good news at all, and hence the random crashes on different PCs.
The problem is Bload not just loads the pixels but it stores some other data too, like the x,y size and bpp.
My suggestion is you use ImageCreate to create a temp image for Bload to load into, then copy the image pixels into the memory you've Callocated.
Jim

QuoteIt's working pretty well now, but when you're approaching the checkered sphere from a distance, there's one point (very probably where you change from one mipmap to another) where the texture-coordinates "jump".

thanks ^^

About the "texture jump", there's no filtering yet so it could explain that I guess. I plan to code a bilinear filter :)

QuoteYou have to get rid of all the -8 stuff.  There's no logic behind it.  You are effectively avoiding overwriting the end of your allocation and using -8 is making it overwrite the beginning instead.  Neither of these is good news at all, and hence the random crashes on different PCs.
The problem is Bload not just loads the pixels but it stores some other data too, like the x,y size and bpp.
My suggestion is you use ImageCreate to create a temp image for Bload to load into, then copy the image pixels into the memory you've Callocated.
Jim

... OF COURSE !! arf why didn't I think about it ? it's a neat idea, thanks ! I'll code that tomorrow once I get up from bed ^^

It's a real treat to see this working now :)

It's a real treat to hear that ^^

Bload stuff is now fixed :D I'll post the next version once mipmap filtering is coded. I found a very useful link about little optimization tricks, I may also optimize a bit before the next version.

the link (lot of stuff for QB but lots of ideas useable with FB) :
http://www.phatcode.net/articles.php?id=232 (http://www.phatcode.net/articles.php?id=232)

An example :
I didn't know writing (a) instead of (b) was possible ! In fact it's pretty logical since logical operations return -1 if true and 0 if not in FB but I never thought about that :)

(a)
a=5
if a>2 then
b=6
end if


(b)
b=-(a>2)*6



hellfire > I just noticed your edit in the previous page :

QuoteSome notes about mipmapping:
What I've understood from a quick look at your source-code, you're now selecting a mipmap-level depending on the depth of a polygon.
Generally it's true that if a polygon is further away, it's also smaller and needs less texture-precision - but it's not a very clever approach (but some ps2 games use this way because the hardware doesn't support mipmapping and it's easy to do).
If you, for example, look from a steep angle at one side of a cube, this side is very narrow and only needs a low texture resolution - although the polygon might be very near to the viewer.

So let's assume you're interpolating texture-coordinates linearly (which is inevitable when you stop doing perspective divide for every pixel), a better approach is to look at the deltas for interpolating the texture-coordinates u & v across the scanline.
For example if one delta is >= 2.0 you'll always skip one texel when advancing to the next pixel. In such case you can savely use a mipmap with half the size.

I was precisely wondering about the fact that my "Z-based" mipmapping was wrong, thanks for pointing me on the deltas, I'll work on that for the next release.

QuoteFor generating the mipmaps, you can simply scale the "current" mipmap to half the size on-the-fly (a simple 2x2 filter) so there's no reason to save all mip-levels.

Won't it be really slow to iterate through all texels and "2x2-filter" them in the main loop ?

QuoteWon't it be really slow to iterate through all texels and "2x2-filter" them in the main loop ?

What I meant is that there's no need to store the mipmaps to *disk* because generating the mipmaps at *startup* is pretty fast.
At the moment you're scaling the original texture to create each mipmap; instead you can simply scale the previous level to half the resolution.

Quotethanks for pointing me on the deltas

You're welcome :)
You also might want to consider creating anistropic mipmaps to take the ratio of the deltas into account.
This results in a matrix of textures with the "basic" mipmaps on the diagonal.
Example for a 256x256 map:

256x256, 256x128, 256x64, 256x32, 256x16, 256x8, 256x4, 256x2, 256x1
128x256, 128x128, 128x64, 128x32, 128x16, 128x8, 128x4, 128x2, 128x1
64x256,  64x128,  64x64,  64x32,  64x16,  64x8,  64x4,  64x2,  64x1
32x256,  32x128,  32x64,  32x32,  32x16,  32x8,  32x4,  32x2,  32x1
16x256,  16x128,  16x64,  16x32,  16x16,  16x8,  16x4,  16x2,  16x1
  8x256,   8x128,   8x64,   8x32,   8x16,   8x8,   8x4,   8x2,   8x1
  4x256,   4x128,   4x64,   4x32,   4x16,   4x8,   4x4,   4x2,   4x1
  2x256,   2x128,   2x64,   2x32,   2x16,   2x8,   2x4,   2x2,   2x1
  1x256,   1x128,   1x64,   1x32,   1x16,   1x8,   1x4,   1x2,   1x1

Looks like a lot of data at first, but "just" requires 4x as much space as the original texture.

QuoteWhat I meant is that there's no need to store the mipmaps to *disk* because generating the mipmaps at *startup* is pretty fast.

oh okay :P I misunderstood you ^^ but for now I must say I like the idea of storing files the first time, and loading them after. However, I can't really tell you why .. Just a preference.

Quoteinstead you can simply scale the previous level to half the resolution.

Done some minutes ago ^^ totally rewritten the GenerateMipMap sub.

QuoteYou also might want to consider creating anistropic mipmaps to take the ratio of the deltas into account.
This results in a matrix of textures with the "basic" mipmaps on the diagonal.
Example for a 256x256 map:

Yep I red about it :) Still, I'll start by trying to finish the "basic" mip-mapping before ^^


And about it, I already have a new question troubling me :S

Every generated textures mipmap seem okay (reduced, blurred) excepted ... the checker one !
It's pretty normal, the box filter iterate every 2 pixels and since each checker square has a side proportional to 2, every new mipmap keep the same geometry.

But it's a problem !!
Since it's not blurred at all (excepted for the 2x2 mip-map and 1x1 mip-map which are simply grey), the texture looks always the same, whatever the distance/angle/dU/dV is !! And therefore, the Moiré effect stays here (and it's terrible, especially on floor) but worse : the limit between 4x4 and 2x2 mip-maps in 3D world is awful !
Is thought about using a texture with 3 squares per side instead of 2 but
1) it's not tilable and,
2) Anyway, it's not proportional to 2, so it doesn't fit in any texture size ><

Now I'm really wondering, I saw Mip-mapped checkered floors everywhere on the web, how do they do ?!!

Must I use some kind of 4*4 box filter ? or even odd*odd box filter ?
I guess bilinear filtering would solve the problem but I'm pretty sure (but I can be wrong) I saw some of those checkered floors with good mip-mapping using box filter on the net ..


edit : the attached images may seems to be actually blurred, but it's the jpg compression which do that.

I must admit your question bothered me for a moment, but the mipmaps of your checker-texture are perfectly okay.
You are using a texture which basically consists of 2x2 pixels (just scaled up to 64x64).
It's no surprise that you reach exactly this 2x2 texture when scaling it down again.

In the distance you can imaging each pixel of your polygon being filled by a rather big area of your texture. All texels in this area are summed up to a single color. Mipmapping reduces the size of this area to 2x2 texels but still your texture only contains black and white pixels.
At this point the bilinear filtering sums up the weighted black & white areas.
Since you're not yet doing bilinear filtering and just pick the nearest of the 4 surrounding pixels (which is either black or white), you still get usual sampling-artifacts just as if there wasn't any mipmapping.

hum .. So I can't pass through bilinear filtering :D Working on it right now then :)

At some point your checker will go to grey.  This is GOOD, because it's the way the sparkles are avoided when your object moves a tiny amount when it is very far away.  If your scene goes grey where you don't want it to, then you're probably not calculating the mipmap level to use correctly.  The 1 pixel grey texture shouldn't be used until your polygon is 1 pixel in size or mapping only 1 texel's worth of uv area.

You probably should bilinear filter your texture while calculating your mipmaps.  But it's simple, every 2x2 in the source texture becomes 1 pixel in the destination one, so very simply you can just add them all together and divide by 4.

Sometimes it depends.  I remember a problem I had with a texture which was supposed to be a chain link fence.  At full size, it works fine, grey criss-cross with transparent holes.  The next mipmap layer down though, it just went solid.  So mipmaps are not for every texture, and if you use alpha for transparency or punch-through you might want to change the way the averaging/bilinear works.

Jim

QuoteBut it's simple, every 2x2 in the source texture becomes 1 pixel in the destination one, so very simply you can just add them all together and divide by 4.

Well that's exactly what I'm doing now ^^ And it's the reason the Checker doesn't blur himself while generating mipmaps :)

QuoteYou probably should bilinear filter your texture while calculating your mipmaps.

while generating ? Shouldn't I apply the filter while rendering the pre-generated mipmap ?



and while i'm here, sorry but I have *again* a question about the LOD. I wanted to use the texel deltas method to apply the correct mipmap. But whatever I do (I tried looots of different ways to access the dU and dV values since I interpolate U/z and V/z instead of U and V), the rendering is weird (especially on spheres, the flat surfaces seem almost okay). I can see I'm almost there, but it's still far from perfect.

I attach a screenshot of the colored LOD rendering : The greener, the higher is the LOD (Do you see how the LOD "spreads" on the middle sphere ?).

And that's the code I'm actually using to find the deltas :

dim as single LODCOEF = 128
               
dU = dU_z*tmp_Z*LODCOEF
dV = dV_z*tmp_Z*LODCOEF

with dU_z = (u/z2 - U/z1) / (x2 - x1)
and tmp_Z = 1/CurrentZ

(I tried several values for the LOD coef)

I also tried to replace tmp_Z by the z2 and z1 values and/or 1/z2 and 1/z1 values.