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?

CodePudding user response：

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

CodePudding user response：

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.