CODEWITHSUNDEEP
algorithmgraphicsreverseprojection
DEgorov
DEgorov

Reputation: 305

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?

Upvotes: 1

Views: 178

Answers (2)

DEgorov
DEgorov

Reputation: 305

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.

Upvotes: 1

Alois Christen
Alois Christen

Reputation: 547

If the triplets are really unique (didn't check that) and if p and q always go up to 1 and 2 (respectively), then you can "group" triplets together and go up the loop chain.

We'll first find the 3 triplets that where made in the same "q loop" : the triplets make with the same x,y,z,p. As only q change, the only difference will be v, and it will be 3 consecutive numbers. For that, let's group triplets such that, in a group, all triplets have the same u and same w. Then we sort triplets in groups by their v parameters, and we group them 3 by 3. Inside each group it's easy to assign the correct q variable to each triplet.

Then reduce the groups of 3 into the first triplet (the one with q == 0). We start over to assign the p variable : Group all triplets such that they have same v and w inside a group. Then sort them by the u value, and group them 2 by 2. This let's us find their p value. Remember that each triplet in the group of 3 (before reducing) has that same p value.

Then, for each triplet, we have found p and q. We solve the 3 equation for x,y,z :

  • z = -1 * ((v + w) - a - b - 3c -q)/3
  • y = (w - u + z + b - c - p)/2
  • x = u + y - b - p

Upvotes: 1

Related Questions