www2.svjatoslav.eu Git - aukio-3d.git/blob

   1 /*
   2  * Aukio 3D engine. Author: Svjatoslav Agejenko.
   3  * This project is released under Creative Commons Zero (CC0) license.
   4  */
   5 package eu.svjatoslav.aukio.e3d.renderer.raster.shapes.basic.texturedpolygon;
   6
   7 import eu.svjatoslav.aukio.e3d.geometry.Point2D;
   8 import eu.svjatoslav.aukio.e3d.geometry.Point3D;
   9 import eu.svjatoslav.aukio.e3d.gui.RenderingContext;
  10 import eu.svjatoslav.aukio.e3d.math.Vertex;
  11 import eu.svjatoslav.aukio.e3d.renderer.raster.texture.TextureBitmap;
  12 import org.junit.Test;
  13
  14 import java.lang.reflect.Method;
  15 import java.util.Random;
  16
  17 import static org.junit.Assert.assertTrue;
  18 import static org.junit.Assert.fail;
  19
  20 /**
  21  * Correctness proof for the Quake-style subdivided perspective scanline
  22  * renderer: compared against an exact per-pixel divide oracle that mirrors
  23  * the production span walk, texel selection must never deviate by more
  24  * than one texel per axis (the ulp-boundary artifact inherent to
  25  * truncation, present in the affine path as well).
  26  */
  27 public class TexturedTrianglePerspectiveTest {
  28
  29     private static final int TEX_W = 64;
  30     private static final int TEX_H = 64;
  31
  32     private static TextureBitmap numberedTexture() {
  33         final int[] texPixels = new int[TEX_W * TEX_H];
  34         for (int i = 0; i < texPixels.length; i++)
  35             texPixels[i] = 0xFF000000 | i;
  36         return new TextureBitmap(TEX_W, TEX_H, texPixels, 1.0);
  37     }
  38
  39     /**
  40      * Exact oracle: replicates the production span setup (rounded
  41      * endpoints, gradients over the unclipped width, clip compensation),
  42      * but recovers u/v with a division at EVERY pixel.
  43      */
  44     private static void exactDrawHorizontalLine(
  45             final double su1, final double sv1, final double sw1,
  46             final double su2, final double sv2, final double sw2,
  47             final int rx1, final int rx2,
  48             final int clipMinX, final int clipMaxX,
  49             final int y, final int[] renderBufferPixels, final int width,
  50             final TextureBitmap textureBitmap) {
  51
  52         final double realWidth = rx2 - rx1;
  53         int x1 = Math.max(rx1, clipMinX);
  54         int x2 = Math.min(rx2, clipMaxX);
  55         if (x2 - x1 <= 0)
  56             return;
  57
  58         final double dsu = (su2 - su1) / realWidth;
  59         final double dsv = (sv2 - sv1) / realWidth;
  60         final double dsw = (sw2 - sw1) / realWidth;
  61
  62         double su = su1 + dsu * (x1 - rx1);
  63         double sv = sv1 + dsv * (x1 - rx1);
  64         double sw = sw1 + dsw * (x1 - rx1);
  65
  66         int renderBufferOffset = (y * width) + x1;
  67
  68         final int[] texPixels = textureBitmap.pixels;
  69
  70         for (int x = x1; x < x2; x++) {
  71             final double invW = 1d / sw;
  72             int itx = (int) (su * invW);
  73             int ity = (int) (sv * invW);
  74
  75             if (itx < 0) itx = 0;
  76             else if (itx > TEX_W - 1) itx = TEX_W - 1;
  77             if (ity < 0) ity = 0;
  78             else if (ity > TEX_H - 1) ity = TEX_H - 1;
  79
  80             renderBufferPixels[renderBufferOffset] = texPixels[ity * TEX_W + itx];
  81
  82             su += dsu;
  83             sv += dsv;
  84             sw += dsw;
  85             renderBufferOffset++;
  86         }
  87     }
  88
  89     @Test
  90     public void subdividedPerspectiveStaysWithinOneTexelOfExact() throws Exception {
  91         final int width = 256;
  92         final int height = 8;
  93         final Random random = new Random(2026);
  94         final TextureBitmap textureBitmap = numberedTexture();
  95
  96         final TexturedTriangle triangle = new TexturedTriangle(
  97                 new Vertex(new Point3D(0, 0, 0), new Point2D(0, 0)),
  98                 new Vertex(new Point3D(1, 0, 0), new Point2D(1, 0)),
  99                 new Vertex(new Point3D(0, 1, 0), new Point2D(0, 1)), null);
 100
 101         final Method draw = TexturedTriangle.class.getDeclaredMethod(
 102                 "drawHorizontalLinePerspectiveZ",
 103                 PerspectiveBorderInterpolator.class, PerspectiveBorderInterpolator.class,
 104                 int.class, RenderingContext.class, TextureBitmap.class);
 105         draw.setAccessible(true);
 106
 107         long totalPixels = 0;
 108         long identicalPixels = 0;
 109         int maxDeviation = 0;
 110
 111         for (int iteration = 0; iteration < 3000; iteration++) {
 112             // Random steep-perspective span: z varies up to 60x across the
 113             // span, texture coords may overshoot the texture (clamp path),
 114             // and the span may extend past the render bounds (clip path)
 115             final double sx1 = random.nextDouble() * width * 0.5;
 116             final double sx2 = sx1 + 4 + random.nextDouble() * (width - 8);
 117             final double z1 = 0.5 + random.nextDouble() * 31.5;
 118             final double z2 = 0.5 + random.nextDouble() * 31.5;
 119             final double u1 = random.nextDouble() * 144 - 16;
 120             final double v1 = random.nextDouble() * 144 - 16;
 121             final double u2 = random.nextDouble() * 144 - 16;
 122             final double v2 = random.nextDouble() * 144 - 16;
 123             final int y = 1 + random.nextInt(height - 2);
 124
 125             final double sw1 = 1d / z1, sw2 = 1d / z2;
 126             final double su1 = u1 * sw1, sv1 = v1 * sw1;
 127             final double su2 = u2 * sw2, sv2 = v2 * sw2;
 128
 129             final PerspectiveBorderInterpolator line1 = new PerspectiveBorderInterpolator();
 130             final PerspectiveBorderInterpolator line2 = new PerspectiveBorderInterpolator();
 131             line1.setPoints(new Point2D(sx1, y), new Point2D(sx1, y + 1), su1, sv1, sw1, su1, sv1, sw1);
 132             line2.setPoints(new Point2D(sx2, y), new Point2D(sx2, y + 1), su2, sv2, sw2, su2, sv2, sw2);
 133
 134             final RenderingContext context = new RenderingContext(width, height, 1);
 135             context.renderMinX = 0;
 136             context.renderMaxX = width;
 137
 138             java.util.Arrays.fill(context.depth, Float.NEGATIVE_INFINITY);
 139             draw.invoke(triangle, line1, line2, y, context, textureBitmap);
 140
 141             final int rx1 = (int) Math.round(sx1);
 142             final int rx2 = (int) Math.round(sx2);
 143             final int[] expected = new int[width * height];
 144             exactDrawHorizontalLine(su1, sv1, sw1, su2, sv2, sw2,
 145                     rx1, rx2, 0, width, y, expected, width, textureBitmap);
 146
 147             final int cx1 = Math.max(rx1, 0);
 148             final int cx2 = Math.min(rx2, width);
 149             for (int x = cx1; x < cx2; x++) {
 150                 final int a = context.pixels[y * width + x] & 0xFFFFFF;
 151                 final int e = expected[y * width + x] & 0xFFFFFF;
 152                 totalPixels++;
 153                 if (a == e) {
 154                     identicalPixels++;
 155                 } else {
 156                     final int deviation = Math.max(
 157                             Math.abs((a % TEX_W) - (e % TEX_W)),
 158                             Math.abs((a / TEX_W) - (e / TEX_W)));
 159                     maxDeviation = Math.max(maxDeviation, deviation);
 160                 }
 161             }
 162         }
 163
 164         final double identicalRatio = (double) identicalPixels / totalPixels;
 165         if (maxDeviation > 1) {
 166             fail("texel deviation " + maxDeviation + " exceeds 1 (identical="
 167                     + (identicalRatio * 100) + "% over " + totalPixels + " pixels)");
 168         }
 169         assertTrue("suspiciously few pixels tested: " + totalPixels, totalPixels > 100000);
 170         System.out.println("perspective-16 vs exact: identical=" + (identicalRatio * 100)
 171                 + "% maxTexelDeviation=" + maxDeviation
 172                 + " over " + totalPixels + " pixels");
 173     }
 174
 175     @Test
 176     public void affineWithinHalfTexelBound() throws Exception {
 177         // The paint() shortcut uses affine mapping when
 178         // texelSpan * (zRatio-1) < 2. Verify: for random spans satisfying
 179         // that bound, the affine renderer stays within one texel of the
 180         // exact per-pixel divide oracle.
 181         final int width = 320;
 182         final int height = 8;
 183         final Random random = new Random(77);
 184         final TextureBitmap textureBitmap = numberedTexture();
 185
 186         final TexturedTriangle triangle = new TexturedTriangle(
 187                 new Vertex(new Point3D(0, 0, 0), new Point2D(0, 0)),
 188                 new Vertex(new Point3D(1, 0, 0), new Point2D(1, 0)),
 189                 new Vertex(new Point3D(0, 1, 0), new Point2D(0, 1)), null);
 190
 191         final Method drawAffine = TexturedTriangle.class.getDeclaredMethod(
 192                 "drawHorizontalLineZ",
 193                 PolygonBorderInterpolator.class, PolygonBorderInterpolator.class,
 194                 int.class, RenderingContext.class, TextureBitmap.class);
 195         drawAffine.setAccessible(true);
 196
 197         long totalPixels = 0;
 198         int maxDeviation = 0;
 199
 200         for (int iteration = 0; iteration < 3000; iteration++) {
 201             final double sx1 = random.nextDouble() * width * 0.5;
 202             final double spanD = 4 + random.nextDouble() * 296;
 203             final double sx2 = Math.min(sx1 + spanD, width * 1.2);
 204             final double u1 = random.nextDouble() * 56;
 205             final double v1 = random.nextDouble() * 56;
 206             final double u2 = random.nextDouble() * 56;
 207             final double v2 = random.nextDouble() * 56;
 208             // z ratio strictly inside the bound, driven by the TEXEL span
 209             final double texelSpan = Math.max(Math.abs(u2 - u1), Math.abs(v2 - v1));
 210             final double z1 = 1 + random.nextDouble() * 30;
 211             final double r = 1 + random.nextDouble() * (1.9 / Math.max(texelSpan, 0.5));
 212             final double z2 = z1 * r;
 213             final int y = 1 + random.nextInt(height - 2);
 214
 215             final PolygonBorderInterpolator line1 = new PolygonBorderInterpolator();
 216             final PolygonBorderInterpolator line2 = new PolygonBorderInterpolator();
 217             line1.setPoints(new Point2D(sx1, y), new Point2D(sx1, y + 1),
 218                     new Point2D(u1, v1), new Point2D(u1, v1));
 219             line2.setPoints(new Point2D(sx2, y), new Point2D(sx2, y + 1),
 220                     new Point2D(u2, v2), new Point2D(u2, v2));
 221
 222             final RenderingContext context = new RenderingContext(width, height, 1);
 223             context.renderMinX = 0;
 224             context.renderMaxX = width;
 225
 226             java.util.Arrays.fill(context.depth, Float.NEGATIVE_INFINITY);
 227             drawAffine.invoke(triangle, line1, line2, y, context, textureBitmap);
 228
 229             // Exact oracle over the same span (gradients from z1/z2)
 230             final double sw1 = 1d / z1, sw2 = 1d / z2;
 231             final int rx1 = (int) Math.round(sx1);
 232             final int rx2 = (int) Math.round(sx2);
 233             final int[] expected = new int[width * height];
 234             exactDrawHorizontalLine(u1 * sw1, v1 * sw1, sw1, u2 * sw2, v2 * sw2, sw2,
 235                     rx1, rx2, 0, width, y, expected, width, textureBitmap);
 236
 237             final int cx1 = Math.max(rx1, 0);
 238             final int cx2 = Math.min(rx2, width);
 239             for (int x = cx1; x < cx2; x++) {
 240                 final int a = context.pixels[y * width + x] & 0xFFFFFF;
 241                 final int e = expected[y * width + x] & 0xFFFFFF;
 242                 totalPixels++;
 243                 final int deviation = Math.max(
 244                         Math.abs((a % TEX_W) - (e % TEX_W)),
 245                         Math.abs((a / TEX_W) - (e / TEX_W)));
 246                 maxDeviation = Math.max(maxDeviation, deviation);
 247             }
 248         }
 249
 250         if (maxDeviation > 1) {
 251             fail("affine deviation " + maxDeviation + " exceeds 1 texel within the bound"
 252                     + " over " + totalPixels + " pixels");
 253         }
 254         assertTrue("suspiciously few pixels tested: " + totalPixels, totalPixels > 100000);
 255         System.out.println("affine within bound: maxTexelDeviation=" + maxDeviation
 256                 + " over " + totalPixels + " pixels");
 257     }
 258
 259     @Test
 260     public void faceOnSpanMatchesAffineWithinOneTexel() throws Exception {
 261         // Constant z across the span: perspective correction must reduce
 262         // to the affine mapping (u linear in x), modulo the ulp-boundary
 263         // truncation artifact.
 264         final int width = 200;
 265         final int height = 4;
 266         final TextureBitmap textureBitmap = numberedTexture();
 267
 268         final TexturedTriangle triangle = new TexturedTriangle(
 269                 new Vertex(new Point3D(0, 0, 0), new Point2D(0, 0)),
 270                 new Vertex(new Point3D(1, 0, 0), new Point2D(1, 0)),
 271                 new Vertex(new Point3D(0, 1, 0), new Point2D(0, 1)), null);
 272
 273         final Method draw = TexturedTriangle.class.getDeclaredMethod(
 274                 "drawHorizontalLinePerspectiveZ",
 275                 PerspectiveBorderInterpolator.class, PerspectiveBorderInterpolator.class,
 276                 int.class, RenderingContext.class, TextureBitmap.class);
 277         draw.setAccessible(true);
 278
 279         final double z = 5.0;
 280         final double sw = 1d / z;
 281         final int y = 1;
 282         final double u1 = 2.0, v1 = 3.0, u2 = 30.0, v2 = 10.0;
 283
 284         final PerspectiveBorderInterpolator line1 = new PerspectiveBorderInterpolator();
 285         final PerspectiveBorderInterpolator line2 = new PerspectiveBorderInterpolator();
 286         line1.setPoints(new Point2D(10, y), new Point2D(10, y + 1), u1 * sw, v1 * sw, sw, u1 * sw, v1 * sw, sw);
 287         line2.setPoints(new Point2D(190, y), new Point2D(190, y + 1), u2 * sw, v2 * sw, sw, u2 * sw, v2 * sw, sw);
 288
 289         final RenderingContext context = new RenderingContext(width, height, 1);
 290         context.renderMinX = 0;
 291         context.renderMaxX = width;
 292         java.util.Arrays.fill(context.depth, Float.NEGATIVE_INFINITY);
 293         draw.invoke(triangle, line1, line2, y, context, textureBitmap);
 294
 295         for (int x = 10; x < 190; x++) {
 296             final double exactU = u1 + (u2 - u1) * (x - 10) / 180.0;
 297             final double exactV = v1 + (v2 - v1) * (x - 10) / 180.0;
 298             final int actualTexel = context.pixels[y * width + x] & 0xFFFFFF;
 299             final int du = Math.abs((actualTexel % TEX_W) - ((int) exactU));
 300             final int dv = Math.abs((actualTexel / TEX_W) - ((int) exactV));
 301             assertTrue("pixel " + x + ": texel deviation u=" + du + " v=" + dv,
 302                     du <= 1 && dv <= 1);
 303         }
 304     }
 305 }