Search code examples
algorithmgraphicsreverseprojection

Reverse the isometric projection algorithm


I've got this code:

const a = 2; // always > 0 and known in advance
const b = 3; // always > 0 and known in advance
const c = 4; // always > 0 and known in advance

for (let x = 0; x <= a; x++) {
  for (let y = 0; y <= b; y++) {
    for (let z = 0; z <= c; z++) {
      for (let p = 0; p <= 1; p++) {
        for (let q = 0; q <= 2; q++) {
          let u = b + x - y + p;
          let v = a + b + 2 * c - x - y - 2 * z + q;
          let w = c + x + y - z;
        }
      }
    }
  }
}

The code generates (a+1)*(b+1)*(c+1)*2*3 triplets of (u,v,w), each of them is unique. And because of that fact, I think it should be possible to write reversed version of this algorithm that will calculate x,y,z,p,q based on u,v,w. I understand that there are only 3 equations and 5 variables to get, but known boundaries for x,y,z,p,q and the fact that all variables are integers should probably help.

for (let u = ?; u <= ?; u++) {
  for (let v = ?; v <= ?; v++) {
    for (let w = ?; w <= ?; w++) {
      x = ?;
      y = ?;
      z = ?;
      p = ?;
      q = ?;
    }
  }
}

I even managed to produce the first line: for (let u = 0; u <= a + b + 1; u++) by taking the equation for u and finding min and max but I'm struggling with moving forward. I understand that min and max values for v are depending on u, but can't figure out the formulas.

Examples are in JS, but I will be thankful for any help in any programming language or even plain math formulas.

If anyone is interested in what this code is actually about - it projects voxel 3d model to triangles on a plain. u,v are resulting 2d coordinates and w is distance from the camera. Reversed algorithm will be actually a kind of raytracing.

UPDATE: Using line equations from 2 points I managed to create minmax conditions for v and code now looks like this:

for (let u = 0; u <= a + b + 1; u++) {
  let minv = u <= a ? a - u : -a + u - 1;
  let maxv = u <= b ? a + 2 * c + u + 2 : a + 2 * b + 2 * c - u + 3;
  for (let v = minv; v <= maxv; v++) {
    ...
  }
}

I think I know what to do with x, y, z, p, q on the last step so the problem left is minw and maxw. As far as I understand those values should depend both on u and v and I must use plane equations?


Solution

  • After spending some time with articles on geometry and with the huge help from Wolfram Alpha, I managed to write needed equations myself. And yes, I had to use plane equations.

    const a = 2; // always > 0 and known in advance
    const b = 3; // always > 0 and known in advance
    const c = 4; // always > 0 and known in advance
    
    const minu = 0;
    const maxu = a + b + 1;
    let minv, maxv, minw, maxw;
    let x, y, z, p, q;
    
    for (let u = minu; u <= maxu; u++) {
      if (u <= a) {
        minv = a - u;
      } else {
        minv = -a + u - 1;
      }
    
      if (u <= b) {
        maxv = a + 2 * c + u + 2;
      } else {
        maxv = a + 2 * b + 2 * c - u + 3;
      }
    
      for (let v = minv; v <= maxv; v++) {
        if (u <= b && v >= a + u + 1) {
          minw = (-a + 2 * b - 3 * u + v - 2) / 2;
        } else if (u > b && v >= a + 2 * b - u + 2) {
          minw = (-a - 4 * b + 3 * u + v - 5) / 2;
        } else {
          minw = a + b - v;
        }
    
        if (u <= a && v <= a + 2 * c - u + 1) {
          maxw = (-a + 2 * b + 3 * u + v - 1) / 2;
        } else if (u > a && v <= -a + 2 * c + u) {
          maxw = (5 * a + 2 * b - 3 * u + v + 2) / 2;
        } else {
          maxw = a + b + 3 * c - v + 2;
        }
    
        minw = Math.round(minw);
        maxw = Math.round(maxw);
    
        for (let w = minw; w <= maxw; w++) {
          z = (a + b + 3 * c - v - w + 2) / 3;
          q = Math.round(2 - (z % 1) * 3);
          z = Math.floor(z);
    
          y = (a + 4 * b + q - 3 * u - v + 2 * w + 3) / 6;
          p = 1 - (y % 1) * 2;
          y = Math.floor(y);
    
          x = (a - 2 * b - 3 * p + q + 3 * u - v + 2 * w) / 6;
          x = Math.round(x);
        }
      }
    }
    

    This code passes my tests, but if someone can create better solution, I would be very interested.