PDA

View Full Version : mipmap level sampling filters



zen
03-05-2002, 06:16 AM
I want to implement mipmapping for my texture cache and from what I hear the gluBuildMipMaps sucks.I didn't wan't to use GLU routines anyway so I was thinking what I could use instead.I know there are some extensions for this but I can't rely on these since they won't be avail. on every machine.Since I won't be doing mipmap level generation on the fly I don't need a particularly fast resampling filter so I can use something besides the box filter.Are there any filters better suited for mipmap level generation?I assume some cubic filter would do the job.
Also I plan to use texture tiling so I'll need a texture border to avoid artifacts at tile boundaries.Say I load the (level 0)texture from file with the correct border(2^n+1*2^n+1) and I filter this to create the other levels.Is it safe to assume that these levels' borders will still be ok or will I have artifacts when smaller levels are used on the tile edges.

jwatte
03-05-2002, 08:42 AM
Texture borders are a single color. You're probably better off thinking of your textures as being size ((2^m)-1)x((2^n)-1), and then repeat the leftmost/bottommost row of the adjacent textures at the topmost/rightmost rows of the current texture.

As far as MIP mapping goes, box filtering is nice because it doesn't use neighbouring state, and thus won't have bleed artifacts. Any filter wider than that WILL have bleed artifacts in the situation you describe, unless you know exactly, at MIP map generation time, what all the neighbouring pixels are going to be, which means that the same "texture" may generate multiple different "images" depending on neighbours.

richardve
03-05-2002, 11:42 AM
There are some sample codes at the Game Developer Magazine (http://www.gdmag.com) website about using more advanced filters, which are way better than a simple box filter..

zen
03-05-2002, 01:45 PM
jwatte:I'm not sure I'm following here.AFAIK you can specify a texture border color as well as texture border in wich case your texture will be (2^n+2)*(2^m+2).What I want to do is what the red book suggests as a use for the texture border.Therefore I have to use normal 2^n*2^m textures with a border of the pixels of the adjacent tiles' edge-pixels,don't I?The tiles and the relationships between them will be constant.That means that at mipmap generation time I will know the adjacent tiles' texture.If I have the level 0 textures correctly set up with borders and scale these to create the other levels,will the borders created by this resampling be incorrect.I know that they will be different from the neighboring tile's edge pixels(as it should be)due to the filtering but will this difference create visible artifacts.Should I just stick to the box filter?
richardve:thanks for the link.I'll have a look.

[This message has been edited by zen (edited 03-05-2002).]

marcus256
03-07-2002, 02:54 AM
Filtering and digital signals (yes, textures are signals, 2D signals) are two of the most misinterpreted subjects in computer programming.

Basics:

1) If you use "real" images for textures (i.e. try to mimic real structures, with proper sampling etc), you should use a filter with as high order as possible, which gives it a sharp cutoff in frequency space.

2) If you are using "synthetic" images (e.g. checkers represented with only two levels of color), you are probably doing it "wrong" in the first place. Sometimes you should not even use mip mapping for such textures. You could just as well use a box filter for those textures.

Ok, with that said I will focus on category 1 of filtering. Perhaps it's easier to think of this in 1D space (it works just as well in 2D space)...?

A) The Nyquist sampling theorem roughly sais "any frequency component higher than half the sampling frequency will result in frequency folding". This is the effect seen for "distant" textured objects that do not use mip mapping (smooth textures starts looking "jittery" when they get sub-sampled).

What does it mean? When we downsample the original image to produce a sub-sampled mip map level we reduce the sample frequency by a factor of 2. That means that we need to remove half of the frequency components, or we will experience folding (i.e. image artifacts).

B) The "larger" the filter kernel (the higher the filter order), the sharper the frequency cutoff. The box filter has a very small filter kernel - hence it is bad at supressing high frequency components. The ideal filter is a s.c. sinc-filter (aka sin(x)/x, or brick-wall filter), with an infinite kernel size - it results in a constant 100% amplitude in the pass-band and 0% in the stop-band, with an infinitely sharp transition.

I will not describe how the sinc-filter works here, but some variant of it (preferably windowed) is what you would want to use. It also means that when you are tiling, you do not want just a "border" from the neighbouring tiles, but many more samples. The best solution would be to forget the idea of a border, and directly sample from the neghbouring tile's textures.



[This message has been edited by marcus256 (edited 03-07-2002).]

zen
03-07-2002, 03:08 PM
Hi markus,
thanks for posting.I have some knowledge of signals and filtering etc. so much of what you said,I allready knew *in theory*.You helped a lot though with applying this theory to image(2d signal as you pointed out) processing.I am having some trouble though with terminology mainly because I don't speak english every day.I see this 'filter kernel' thingie everywhere.What exactly is it?
Also,my idea of resampling is this:we reconstruct the analog out of the discrete 2d signal(as well as we can anyway,depending on initial sampling)and then resample this.Is this correct?So far no filtering is involved.I assume we filter the resampled image to improve its quality so the filtering process doesn't have anything to do with the resampling itself,does it?Anyway I have implemented a couple of FIR filters in matlab so in theory I know the theory but I have no idea where to begin with implementing it in C.Do you know of any usefull docs on resampling and box filters to help me start out?
Btw the border reffers to the problem with tiling textures when using the GL_LINEAR filter,not to mipmap generation,so I think I'll need to use it anyway.You're right though,I won't be able to use just the border to generate mipmaps mith higher order filters.Damn,this complicates things a little.Thanks again for the help,

Dimitris

jwatte
03-07-2002, 03:33 PM
Zen,

You can specify ONE color for ALL border texels. For more information, see OpenGL specification version 1.3, section 3.8.4: Texture Parameters.

marcus256,

I actually know a fair deal about the sampling theorem and windowed sinc reconstruction filters :-) When I said box filtering was convenient, it was in the context of many current graphics implementation tricks such as texture sheeting, which result in good enough visuals while boosting performance. Who can see a noise floor of -40 dB without looking hard? (that's my experience of noise behaviour for linear interpolating reconstruction)

If you treat a texture as a single infinitely repeating and/or extending image, then definitely make your kernel as wide as is practical without ringing.

zen
03-08-2002, 03:19 AM
jwatte:
I know about the TEXTURE_BORDER_COLOR parameter but I thought I can specify my own border.The specs say that the texture image given to opengl with TexImage2D must be (2^m+2b)*(2^n+2b) where b is the border width.
Also this is an extract from the red book,'using a textures border' for tiling large textures:


If you define a border for each texture whose texel values are equal to the values of the texels on the edge of the adjacent texture map, then when linear averaging takes place, the correct behavior results.

How exactly am I supposed to specify this border of texels from the edge of the adjacent tile if all texels must be the same?

zen
03-09-2002, 04:52 PM
marcus:no need to answer my questions.I found some more documents which answered them.
They also helped me write two simple downsampler routines,one using a nearest and one using a box filter.There are some details though,I'm not sure I got right so I'm going to post the code here in hope someone can tell me if it's correct:




#define idx(x,y) (((y)*hin+x)*ncomp)

void downsample_nearest(unsigned char *pin,int win,int hin,unsigned char *pout,int wout,int hout,int ncomp)
{
int i,j,k,ix,iy;
double dx,dy,x,y;
unsigned char *op,*ip;

/*calculate downsampling ratio*/
dx=(win-1.)/(wout-1.);
dy=(hin-1.)/(hout-1.);

for(i=0,op=pout;i<hout;i++)
for(j=0;j<wout;j++){
/*calculate sampling point*/
x=j*dx;
y=i*dy;

/*round to nearest*/
ix=(int)floor(x);
iy=(int)floor(y);

if(x-ix>0.5) ix++;
if(y-iy>0.5) iy++;

ip=[idx(ix,iy)];

/*and copy pixels*/
memcpy(op,ip,ncomp);
op+=ncomp;
}
}

void downsample_box(unsigned char *pin,int win,int hin,unsigned char *pout,int wout,int hout,int ncomp)
{
int i,j,k,x,y;
double dx,dy;
unsigned char *p0,*p1,*p2,*p3,*p;

/*calculate downsampling ratio(input is biased
to ensure that i*dx and i*dy are always smaller
than win-1 and hin-1 so that floor(j*dx)+1 and
floor(i*dy)+1 stays inside the image*/
dx=(win-1.01)/(wout-1.);
dy=(hin-1.01)/(hout-1.);

for(i=0,p=pout;i<hout;i++)
for(j=0;j<wout;j++){
/*calculate points surrounding the sampling point
(ceil(j*dx)=floor(j*dx)+1 and ceil(i*dx)=floor(i*dx)+1)*/
x=floor(j*dx);
y=floor(i*dy);

p0=[idx(x,y)];
p1=[idx(x,y+1)];
p2=[idx(x+1,y)];
p3=[idx(x+1,y+1)];

/*average surrounding pixels for each component*/
for(k=0;k<ncomp;k++)
*p++=(unsigned char)((p0[k]+p1[k]+p2[k]+p3[k])/4);
}
}



[This message has been edited by zen (edited 03-09-2002).]

[This message has been edited by zen (edited 03-09-2002).]

jwatte
03-10-2002, 07:22 AM
zen,

You're right about border texels, and I don't know what I was on. Perhaps I've ignored it because I found it not accelerated in the past.

I don't think you want to use the "-1" or "-1.01" adjustments in your filtering, as this will lead to off-by-one errors when you tile. Instead, think of filtering only the "content" of the texture, and grab the border separately from whatever texture is living next to it -- you shouldn't filter with the border.

Thus, for MIP maps, boxfiltering becomes a matter of summing every block of 4 pixels, and nearest becomes a matter of discarding every other scanline and every other pixel from the scanlines you keep. This special case can of course be implemented rather more efficiently than your current loops :-)

zen
03-10-2002, 03:28 PM
jwatte:I'm not using the border mechanism.I'm still going to use a border but it's part of the texture.The -1. (or -1.01) is there not because of the border but because indexing starts from zero.I use 1.01 because in the case of say j beeing wout-1 the dx*j=win-1 so floor(dx*j) is still win-1 and floor(dx*j)+1 is win which indexes out of the bounds of the image.By making dx slighly smaller floor(dx*j) is now win-2 so floor(dx*j)+1 is win-1 which is the last pixel and thus in bounds.I'm not sure if this doesn't cause any trouble at other pixel positions though.Do you think it's wrong?
Btw I will implement a special-case routine for halving an image but I need a genaral routine as well.Besides I want to understand how this works to implement better filters.

marcus256
03-11-2002, 11:58 PM
zen, your code looks correct, except perhaps that you may experience strange stuff with your casting, and I see no "wrapping" handling when indexing - but I assume you're aware of these problems.

My suggestion for going to higher order filters is to define a filter kernel beforehand (you know what a kernel is now?), and in your averaging step, loop over the kernel. The box filter kernel that you have implemented is:

[0.25 0.25]
[0.25 0.25]

I made (for fun) a 2D kernel based on a 20th order windowed sinc-filter (it's huge - 441 samples!). You can find it here: http://hem.passagen.se/opengl/subsample/subsample.html

I have not tried it, so I'm not sure how well it works. But you said you had time as this was a pre-processing step I think, so maybe it's worth trying it?

You can probably guess how I created it ("rotate" the 1D response around the filter peak to get a 2D response), so it should not be hard to do your own filters.

An alternative (and better) method is to model the brick-wall frequency response in the FFT-domain (a circle with the radius of the cutoff frequency, H = 1.0 inside the circle, H = 0.0 outside the circle), take the inverse 2D FFT to get the spatial domain 2D impulse response, and finally window/truncate it.

zen
03-12-2002, 05:20 AM
zen, your code looks correct, except perhaps that you may experience strange stuff with your casting, and I see no "wrapping" handling when indexing - but I assume you're aware of these problems.

Errr,actually I'm not.This is hust my first approach at a filter implementation.By wrapping do you mean that at the edges the pixels of the opposite edge are used?This is only usefull in the case of GL_REPEAT right?I use this 1.01 in order to never sample off the edge of the image as I explain above.Shouldn't I do this?
As for casting,do you mean C type casting?What will I have problems with,x=floor(j*dx) and y=floor(i*dy)?I casts are done automatically by the compiler there,I think.
About the higher order filters I will implement them later,other things are more important right now.