texture aliasing

[raft]

hello,

this is what Egon said in an email:
Texture aliasing is an undersampling artifact that occurs, when only a few samples of a texture (due to the size of the polygon) are taken to draw the image.

Hardware is using mip mapping (i.e. smaller textures for smaller polygons in the distance) to work against this. The software renderer doesn't do this, because determining the correct mipmap level would be quite expensive. To prevent it (well, you can't really prevent it, just try to minimize the effect) use textures with less contrast and/or larger structures.

i guess, no matter how one selects a texture, he cannot avoid texture aliasing for objects like grass, trees etc due to the nature of thier texture.

so how to beat it when using software renderer ?

i thought of emulating mip mapping to some degree by re-assigning objects' textures based on distance, but i'm quite unsure if it worths a try. for trees it may help, but for large objects like ground it wont. (since camera is close to some part of object and far to other) this approach will also break 3DSLoader's multiple texture assignments to a single object. it requires an Object3D.recreateTextureCoords() each time the texture size changed (i dont know how expensive it is)

using PolygonManager to set textures per polygon instead of per object maybe an alternative but i guess doing that for every polygon will be a sure performance killer. also i dont know if there is a way of getting all polyon id's

so is there a nice solution for this ?
thx

Code Select Expand

r a f t

[EgonOlsen]

Not sure if it's a nice solution...anyway: I've written a polygon based mip mapper for the software renderer that sits on top of jPCT (i.e. it isn't part of the renderer itself). To run it, you need a new version of jPCT that adds a method getData() to VisList: http://www.jpct.net/download/beta/jpct_111pre4.jar

The used method has some drawbacks:

It's polygon based, i.e. a polygon has either mipmap x or y. Like the good old Riva 128 did it...  :wink:
It's "one step behind" because of using the VisList to process visible polygons only...but that shouldn't matter too much.
If filtering is used, the mipmaps will be filtered too. This may bring back some aliasing the mipmapping should actually help to get rid off. Turning off the filtering may help.

Here's the code: http://www.jpct.net/download/MipMapper.java

Add the call to MipMapper.mipMap(); behind your call to World.draw(...).

Please note: This is the result on 1.5h of work, so it's hacky and maybe buggy. Oh, and don't use this on the hardware renderer...there's simply no point in doing so. The hardware can do it better anyway.

[raft]

hey, i've asked for an idea, you've come with an implementation :lol:

i've adapted your MipMapper to karga. it's off by default, can be turned on/off by the key M. filtering also can be turned on/off by the key F. OGSS_FAST is default at the moment.

surprisingly (at least for me) while running it has little or no impact on overall performance and it reduces aliasing a lot. well not as much as oversampling but it performs quite better than oversampling. for the first use it takes a while to create initial images but that's all. i guess with some fine tuning (non linear distance etc) it will perform quite well

thanks a lot Egon :wink:

Code Select Expand

r a f t

[EgonOlsen]

hey, i've asked for an idea, you've come with an implementation :lol:

That's because i wasn't able to tell if it's a working idea before actually trying it... :wink:
Karga is really looking better with it enabled, you should make it default IMHO. Performance is sometimes even better on my machine than without it (something that i've noticed in my own test application too). I guess that's caused by a better cpu cache hitrate for the smaller textures.

[raft]

i first thought the non performance slow down is caused by this: the cost of checking lots of polygons' distance to camera is balanced by copying less pixels of texture to FrameBuffer. i dont know jPCT's internals but it should somehow copy some portion of texture to FrameBuffer

i think the same about default behaviour, i will do it after tuning MipMapper. i guess i must read something about how hardware does that

Code Select Expand

r a f t

[raft]

here is a simple area based MipMapper implementation based on Egon's one. it uses java5 syntax but not java5 specific classes so can be converted to earlier versions of java

to use, create an instance of MipMapper and add Object3D's to be mip mapped with addObject(Object3D). call MipMapper.mipMap(World, FrameBuffer) either before or after render/draw.

please note:
* it requires the upcoming version (1.11) of jPCT
* it isnt suitable for textures which are modified or replaced over time

Code Select Expand

r a f t

Code Select Expand


import com.threed.jpct.*;

import java.util.*;
import java.awt.*;
import java.awt.image.*;

/**
* a simple area based mip mapper implementation.
* i.e: mip map level per polygon is decided according to ratio:
* area of polygon on screen / area of polygon on texture
*
* @author r a f t
*/
public class MipMapper {
   /** the number of mipmap levels */
   public static final int LEVELS = 8; // enough for mip mapping a 1024x1024 texture to 8x8
   
   /** the minimum mipmap size (lower isn't possible, higher is) */
   public static final int MIN_SIZE = 8;
   
   /** original texture will be used dwon to this ratio (polygon area / texture area) */
   public static final float FIRST_LEVEL = 1/2.5f;
   
   /** debug switch for showing colored mip maps */
   public static boolean colorMipmaps = false;
   
   private final TextureManager tm = TextureManager.getInstance();
   
   private final int[] visListData = new int[2];
   
   private final BitSet changedObjects = new BitSet(256);
   private final BitSet processedTextures = new BitSet(256);
   
   private final Map<Integer, ObjectData> mipMapData = new HashMap<Integer, ObjectData>();
   private final Map<String, Integer> textureIds = new HashMap<String, Integer>();
   private final Set<String> createdTextures = new HashSet<String>();
   
   public MipMapper() {}
   
   /** adds the object to mipmap list */
   public void addObject(Object3D object3d) {
       mipMapData.put(object3d.getID(), new ObjectData(object3d));
   }
   
   /** removes the object from mipmap list */
   public void removeObject(int id) {
       mipMapData.remove(id);
   }
   
   /** creates mipmap textures if they arent already created */
   private void createMipMaps(Object3D object3d) {
       PolygonManager pm = object3d.getPolygonManager();
       
       for (int polygonId = 0; polygonId < pm.getMaxPolygonID(); polygonId++) {
           int textureId = pm.getPolygonTexture(polygonId);
           
           if (!processedTextures.get(textureId)) {
               
               Texture texture = tm.getTextureByID(textureId);
               int owidth = texture.getWidth();
               int oheight = texture.getHeight();
               
               TexelGrabber tg = new TexelGrabber();
               texture.setEffect(tg);
               texture.applyEffect();
               texture.removeEffect();
               
               int[] texels = tg.texels;
               BufferedImage origTextureImage = new BufferedImage(owidth, oheight, BufferedImage.TYPE_INT_RGB);
               int[] pixels = ((DataBufferInt) ((BufferedImage) origTextureImage).getRaster().getDataBuffer()).getData();
               
               Texture lastTexture = texture;
               int lastTextureId = textureId;
               
               for (int offset = 1; offset < LEVELS; offset++) {
                   int width = (int) ((float) owidth/Math.pow(2, offset));
                   int height = (int) ((float) oheight/Math.pow(2, offset));
                   
                   width = Math.max(MIN_SIZE, width);
                   height = Math.max(MIN_SIZE, height);
                   
                   if ((lastTexture.getWidth() != width) || (lastTexture.getHeight() != height)) {
                       
                       if (colorMipmaps) {
                           int[] tmpy = new int[texels.length];
                           int col = 200<<(8*((offset-1)%3));
                           for (int i = 0; i < tmpy.length; i++) {
                               tmpy[i] = col;
                           }
                           texels = tmpy;
                       }
                       System.arraycopy(texels, 0, pixels, 0, owidth*oheight);
                       
                       Image mipmapTextureImage = origTextureImage.getScaledInstance(width, height, Image.SCALE_SMOOTH);
                       Texture mipmapTexture = new Texture(mipmapTextureImage);
                       
                       String textureName = getTextureName(textureId, offset);
                       
                       if (tm.containsTexture(textureName))
                           tm.replaceTexture(textureName, mipmapTexture);
                       else tm.addTexture(textureName, mipmapTexture);
                       
                       lastTexture = mipmapTexture;
                       lastTextureId = tm.getTextureID(textureName);
                       
                       textureIds.put(textureName, lastTextureId);
                       createdTextures.add(textureName);
                       
                       Logger.log("mip map texture created " + textureName + " " + width + "x" + height, Logger.MESSAGE);
                       
                   } else {
                       // no need to create a new texture so use last one
                       String textureName = getTextureName(textureId, offset);
                       textureIds.put(textureName, lastTextureId);
                       
                       Logger.log("re-used last mipmap texture " + textureName + " " + width + "x" + height, Logger.MESSAGE);
                   }
                   
               } // for offset
               processedTextures.set(textureId);
           } // if (!processedTextures.get(textureId)
       } // for polygonId
   }
   
   private String getTextureName(int baseTextureId, int offset) {
       return "mipmap/" + baseTextureId + "/" + offset;
   }
   
   /**
    * Does the actual mipmapping based on the current visibility list.
    * Has to be executed after/before rendering/drawing the scene, so it's always
    * "one step behind" but if you don't move very fast, this shouldn't matter.
    */
   public void mipMap(World world, FrameBuffer buffer) {
       if (mipMapData.isEmpty())
           return; // no mipMapped objects so return
       
       VisList vl = world.getVisibilityList();
       
       int size = vl.getSize();
       int lastObjectId = -1;
       
       ObjectData objectData = null;
       changedObjects.clear();
       
       for (int i = 0; i < size; i++) {
           vl.getData(i, visListData);
           
           if (lastObjectId != visListData[0]) {
               lastObjectId = visListData[0];
               objectData = mipMapData.get(visListData[0]);
           }
           
           if (objectData != null) {
               SimpleVector v0, v1, v2;
               int polygonId = visListData[1];
               
               if ((v0 = Interact2D.project3D2D(world.getCamera(),
                       buffer, objectData.pm.getTransformedVertex(polygonId, 0))) == null)
                   continue;
               if ((v1 = Interact2D.project3D2D(world.getCamera(),
                       buffer, objectData.pm.getTransformedVertex(polygonId, 1))) == null)
                   continue;
               if ((v2 = Interact2D.project3D2D(world.getCamera(),
                       buffer, objectData.pm.getTransformedVertex(polygonId, 2))) == null)
                   continue;
               
               float polygonArea = calculateArea(v0, v1, v2);
               float ratio = polygonArea / objectData.textureAreas[polygonId];
               
               int offset = -1; boolean done = false;
               while (!done && (++offset < LEVELS - 1)) {
                   done = ratio > FIRST_LEVEL;
                   ratio *= 4f;
               }
               
               int targetTex = objectData.orgTex[polygonId][offset];
               
               if (targetTex != objectData.curTex[polygonId]) {

                   changedObjects.set(lastObjectId);
                   objectData.curTex[polygonId] = targetTex;
                   objectData.pm.setPolygonTexture(polygonId, targetTex);
               }
           }
       }
       
       for (int i = changedObjects.nextSetBit(0); i >= 0; i = changedObjects.nextSetBit(i+1)) {
           world.getObject(i).recreateTextureCoords();
       }
   }
   
   /** resets all textures to their original states
    * i.e. disables mip mapping */
   public void reset() {
       for (ObjectData objectData : mipMapData.values())
           objectData.reset();
   }
   
   /**
    * useful for cleanup purposes
    * (i.e you dont want call TextureManager.flush() for whatever reason)
    */
   public void dispose() {
       for (String textureName : createdTextures) {
           if (tm.containsTexture(textureName))
               tm.replaceTexture(textureName, tm.getDummyTexture());
           else Logger.log("couldnt find texture " + textureName, Logger.WARNING);

       }
   }
   
   private float calculateArea(SimpleVector... v) {
       float area = 0f;
       for (int i = 0; i < v.length; i++) {
           int j = (i + 1) % v.length;
           area += v[i].x * v[j].y;
           area -= v[i].y * v[j].x;
       }
       area /= 2.0;
       return (area < 0) ? -area : area;
   }
   
   /** data structure to store polygon data per object */
   private class ObjectData {
       private final Object3D object3d;
       private final PolygonManager pm;
       
       private final int[][] orgTex;
       private final int[] curTex;
       private final float[] textureAreas;
       
       private ObjectData(Object3D object3d) {
           this.object3d = object3d;
           pm = object3d.getPolygonManager();
           
           orgTex = new int[pm.getMaxPolygonID()][LEVELS];
           curTex = new int[pm.getMaxPolygonID()];
           
           textureAreas = new float[pm.getMaxPolygonID()];
           
           createMipMaps(object3d);
           
           for (int i = 0; i < orgTex.length; i++) {
               int textureId = pm.getPolygonTexture(i);
               
               orgTex[i][0] = textureId;
               for (int offset = 1; offset< LEVELS; offset++) {
                   orgTex[i][offset] = textureIds.get(getTextureName(textureId, offset));
               }

               curTex[i] = orgTex[i][0];
               
               float uvArea = calculateArea(pm.getTextureUV(i, 0), pm.getTextureUV(i, 1), pm.getTextureUV(i, 2));
               Texture texture = tm.getTextureByID(textureId);
               textureAreas[i] = uvArea * texture.getWidth() * texture.getHeight();
           }
       }
       
       private void reset() {
           boolean changed = false;
           for (int polygonId = 0; polygonId < orgTex.length; polygonId++) {
               int originalTextureId = orgTex[polygonId][0];
               
               if (originalTextureId != curTex[polygonId]) {
                   changed = true;
                   pm.setPolygonTexture(polygonId, originalTextureId);
                   curTex[polygonId] = originalTextureId;
               }
           }
           if (changed)
               object3d.recreateTextureCoords();
       }
   }
   
   /**
    * small helper class to access a texture's texels.
    */
   private class TexelGrabber implements ITextureEffect {
       
       private int[] texels = null;
       
       public void init(Texture tex) {}
       
       public void apply(int[] dest, int[] source) {
           texels = source;
       }
   }
}


[EgonOlsen]

Cool. It works much better than my distance based hack. I'll port this to Java 1.1 and replace the currently downloadable version with it, if you don't mind.

[raft]

sure. i'll be glad indeed

Code Select Expand

r a f t

[EgonOlsen]

I had to awake this thread from the dead to add that per polygon mip mapping for the software renderer will be added to 1.19. Compared to the solution discussed in this thread, this approach won't have any noticable performance hit when used on larger scenes.

[raft]

so will it be embedding this MipMapper inside jPCT or something else ?

[EgonOlsen]

Not really that one, but it's using the same approach. The good thing with moving it into the core is, that it doesn't need to redo all the vertex transformations because it has that data anyway. Plus it's no longer one step behind and there's no performance impact anymore.

[raft]

sounds great