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

[hellfire]

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

[Jim]

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

[Hezad]

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

thanks ^^

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

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

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

[Shockwave]

It's a real treat to see this working now

[Hezad]

It's a real treat to hear that ^^

Bload stuff is now fixed 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

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)

Code: [Select]

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

(b)

Code: [Select]

b=-(a>2)*6


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

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.

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.

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.

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

[hellfire]

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

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

Code: [Select]

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.

[Hezad]

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

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

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

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:

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.

[hellfire]

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.

[Hezad]

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

[Jim]

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

[Hezad]

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.

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

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

Code: [Select]

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.

[hellfire]

So, you have interpolated x, u/z, v/z, 1/z along the left & right edges of your polygon:

lx= left x-coordinate of your scanline
lu= u/z on left side
lv= v/z on left side
lz= 1/z on left side

rx= right x-coordinate of your scanline
ru= u/z on right side
rv= v/z on right side
rz= 1/z on right side

What you want to find is the delta from one pixel's perspective correct texture-coordinates to the next:
mipu= log2( lu/lz - (lu+deltau)/(lz+deltaz) )
mipv= log2( lv/lz - (lv+deltau)/(lz+deltaz) )

Now that's computationally a bit expensive to do per pixel.
So let's do things properly:
Split the scanline into pieces of, let's say, 8 pixels and calculate deltas to get from one set of (u/z, v/z, 1/z) to the one eight pixels further:
inv= 8.0 / (rx-lx)
du= (ru-lu) * inv
dv= (rv-lv) * inv
dz= (rz-lz) * inv

Calculate one pair of perspective correct texture-coordinates for the left and right side of the 8-pixel-span. Let's also make them integers (we multiply by 2^16 to keep some precision):

u1= lu/lz*65536.0
v1= lv/lz*65536.0

advance to the end of 8-pixel-span:
lu+=du
lv+=dv
lz+=dz

u2= lu/lz*65536.0
v2= lv/lz*65536.0

you can now interpolate linearly across the coordinate-pair:
ldu= (u2-u1) shr 3
ldv= (v2-v1) shr 3
(beware of freebasic's shift function)

here you can read the mipmap-level from the upper-word of the deltas (find fast ways for log2 here).
Adjust the texture-coordinates depending on the miplevel (level 0 is the original texture).
Texture-tiling is for free with a simple bitmask.

masku= (1 shl (log2(texture_width) - miplevel))-1
maskv= (1 shl (log2(texture_height) - miplevel))-1
texshift= log2(texture_width) - miplevel

for x=0 to 7
  u= (u1 shr (16+miplevel)) and masku
  v= (v1 shr (16+miplevel)) and maskv
  dest(x)= mipmap[ (v shl texshift) + u ]
  u1+=ldu
  v1+=ldv

(all without warranty)

[Hezad]

Rah how could I thank you for your implication ?! Thank you so much for all that. I didn't understand everything from the tiling part but don't worry, i'll work on that

Concerning the Log2 calculus algorithm, I guess it'd be preferable to use the one for evenly distributed inputs values ? Anyway, the listing says :

Code: [Select]

if (tt = v >> 24)
{
  r = 24 + LogTable256[tt];
}
else if (tt = v >> 16)
{
  r = 16 + LogTable256[tt];
}
else if (tt = v >> 8)
{
  r = 8 + LogTable256[tt];
}
else
{
  r = LogTable256[v];
}

but tt is not defined before.. it's declared as a "register unsigned int" so I guess the "register" thing has to do with that since it can't be used if always equaling 0 ..

[hellfire]

"register" is a c++ keyword which proposes to keep the variable in a register.
Modern compilers are usually clever enough to decide that on their own so just make "tt" an integer.
Notice that the expression inside the if() is an assignment and not a compare:

Code: [Select]

tt = v shr 24
if t<>0 then
  ...


[Hezad]

okay thanks I have lots to learn about C/C++ lol ...

I thought

Code: [Select]

if (tt = v >> 24)
{ ...
were equivalent to

Code: [Select]

if tt = v shr 24 then ...
instead of

Code: [Select]

tt = v shr 24
if t<>0 then ...
><

[Hezad]

Hey Just a quick post since I'm in a hurry. Here is a temp release of the Engine with the Mipmapping finally working thanks to hellfire.

The optimization brought is not implemented yet, I wanted to try quickly the "expensive" method before to ensure I wasn't making any mistakes with the rest of the code. That's why this release is a "temp" one. The real 0.03 will have the optimizations hellfire spoke about and bilinear filtering. So here it is

Changes list :

v0.03 temp Changes List



MAJOR :

- Mip Mapping fixed, now totally workind !
  > A gigantic thanks to hellfire (from dbf/gvy boards) which gave me the
  > code to find the current Level Of Details to use.

- Image loading (bmp loading with Bload) is fixed.
  > No more weird tricks with bload

- Added Render_Option()
  > Normal, Mipmap levels or Zbuffer

- GenerateMipMap() total rewrite
  > More efficient



Minor :

- Fixed a little bug in Z-buffer handling.
- More precise FPS calculus in the example source.

To Do next :
- LOD determination optimization
- bilinear filtering
- fixing some undetermined bug(s) in the clipping function.

[Shockwave]

The rewrite worked nice and you'll be pleased to know that it did not crash here

It looks lovely actually and great that you added som options during the demo to turn things off an on, you can see straight away the mipmapping makes a nice difference to the quality

[Hezad]

The rewrite worked nice and you'll be pleased to know that it did not crash here Smiley

I am ! 

It looks lovely actually and great that you added som options during the demo to turn things off an on, you can see straight away the mipmapping makes a nice difference to the quality Smiley

thanks I hope the bilinear filtering will add more quality to the rendering, but I'm a bit afraid of the FPS fall it will cause ..

[Stonemonkey]

I did some work on bi linear filtering a while ago and posted a little about it here: http://dbfinteractive.com/forum/index.php?topic=2285.0 there's a link to a bit about efficient blending there too.

EDIT:

There's also a little bit about the bleeding edges and clamping which can be useful for the filtering here: http://dbfinteractive.com/forum/index.php?topic=2342.0 although it's in c++.

[Hezad]

Yey ! Awesome trick thanks for sharing it, it'll definitely be useful

There's also a little bit about the bleeding edges and clamping which can be useful for the filtering here: http://dbfinteractive.com/forum/index.php?topic=2342.0 although it's in c++.

Well I have to admit I haven't understood all the vocabulary used in this thread I know (I think :p) what are bleeding edges, but clamping ? A literal translation didn't help