0
\$\begingroup\$

I'm using an engine that implements a texture mapping technique where the texture map for each triangle is defined by a point(P) and 2 vectors(M, N) instead of per-vertex texture coordinates P defines the origin of the texture, M defines the horizontal end of the texture and N the vertical end The technique is better explained here: https://nothings.org/gamedev/ray_plane.html

Now, given a triangle ABC and a UV for each vertex of the triangle i needed to compute the PMN values for those UV coordinates, thankfully an answer that describes an algorithm from UV -> PMN already exists: https://gamedev.stackexchange.com/a/185429/147479

However i am now wondering if it's possible to construct different combinations of PMN(that would yield a correct result, small error margin is fine and expected)

Example using the UV -> PMN algorithm: the triangle ABC with positions {20, -75, -40) {-30, 15, 60} {-5, 26, 63} and UV coordinates {0.2, 0.4} {0.2, 0.9} {0.8, 0.5} could yield the PMN coordinates {30, -75, 16} {32, -37, 90} {4, -13, -80} and the error rate could be 0.0005(which is acceptable) the error rate can be determined by running the UV -> PMN algorithm, then converting the constructed PMN coordinates back to UV(algorithm described in the question i linked) and comparing the two (original UV's and the constructed ones from doing UV -> PMN -> UV)

A different combination could be something like {110, 54, -15} {44, -82, 16} {-14, -102, 130} it just has to match(small error margin is fine) the original UV coordinates (if it was converted back to UV coordinates)

Implementation of the algorithm DMGregory proposed:

            Vector3D pPrime = new Vector3D(65, -35, 77); // arbitrary point i picked
            while (true) {
                Matrix4d mat = new Matrix4d(
                        p.getX(), m.getX(), n.getX(), pPrime.getX(),
                        p.getY(), m.getY(), n.getY(), pPrime.getY(),
                        p.getZ(), m.getZ(), n.getZ(), pPrime.getZ(),
                        1, 1, 1, 1
                );

                //determine whether 4 points lie on the same plane or not
                if (mat.determinant() > 0.001) { // check against epsilon just in case
                    break;
                }

                double x = ThreadLocalRandom.current().nextInt(-200, 200);
                double y = ThreadLocalRandom.current().nextInt(-200, 200);
                double z = ThreadLocalRandom.current().nextInt(-200, 200);
                pPrime = new Vector3D(x, y, z);
            }

            Vector3D d = divide(pPrime.subtract(p), pPrime.subtract(p).getNorm());
            Vector3D mPrime = pPrime.add(m.subtract(p))
                    .subtract(d.scalarMultiply(m.subtract(p).dotProduct(d)));

            Vector3D nPrime = pPrime.add(n.subtract(p))
                    .subtract(d.scalarMultiply(n.subtract(p).dotProduct(d)));

Picking M, N values close to whole numbers:

            float eps = 0.07f;
            int i = 1;
            while (true) {
                List<Vector3D> newPMN = computeNewPMN(p, m, n);
                Vector3D pPrime = newPMN.get(0);
                Vector3D mPrime = newPMN.get(1);
                Vector3D nPrime = newPMN.get(2);

                double fractMX = mPrime.getX() % 1;
                double fractMY = mPrime.getY() % 1;
                double fractMZ = mPrime.getZ() % 1;

                double fractNX = nPrime.getX() % 1;
                double fractNY = nPrime.getY() % 1;
                double fractNZ = nPrime.getZ() % 1;

                boolean closeTo0 = abs(fractMX) < eps && abs(fractMY) < eps && abs(fractMZ) < eps && abs(fractNX) < eps && abs(fractNY) < eps && abs(fractNZ) < eps;
                float eps1 = 1f - eps;
                boolean closeTo1 = abs(fractMX) > eps1 && abs(fractMY) > eps1 && abs(fractMZ) > eps1 && abs(fractNX) > eps1 && abs(fractNY) > eps1 && abs(fractNZ) > eps1;
                if (closeTo0 || closeTo1) {
                    System.out.println("Found valid at " + i);
                    // do stuff with pPrime, mPrime, nPrime
                    break;
                }
                i++;
            }

where computeNewPMNcontains the code mentioned above

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Here's an algorithm to take the \$PMN\$ triangle given by my original answer, and replace it with an alternative \$P^\prime M^\prime N^\prime\$ of your choosing.

First: pick a new point \$P^\prime\$ arbitrarily. It needs to be outside the plane of \$PMN\$, but other than that you can put it anywhere you like. I expect you'll get less rounding errors the closer \$P^\prime - P\$ aligns with the normal to the plane of \$PMN\$ though.

Next, calculate the direction of displacement from \$P\$ to your new \$P^\prime\$:

$$\vec d = \frac {P^\prime - P}{||P^\prime - P||}$$

Use this to project \$M\$ and \$N\$ to a new plane through \$P^\prime\$, perpendicular to \$\vec d\$:

$$M^\prime = P^\prime + (M - P) - \vec d \left(\left(M-P\right)\cdot \vec d \right)\\ N^\prime = P^\prime + (N - P) - \vec d \left(\left(N-P\right)\cdot \vec d \right)$$

\$\endgroup\$
8
  • \$\begingroup\$ This is excellent, my goal with this was to generate a PMN triangle, where the 3 vertices are integers so i wanted to construct P, M, N values as close to a whole number as possible(as after constructing them i round them to an integer) What i did right now is take ur algorithm and run it until it finds a PMN triangle where each value is very close to an integer(i defined an epsilon) this works really well if the epsilon is 0.08 or greater (otherwise it gets extremely slow) for epsilon = 0.08, it currently takes 2m iterations on average (which takes under a second to compute) \$\endgroup\$
    – Suic
    Jan 16, 2022 at 17:19
  • \$\begingroup\$ So my question is whether theres a better way to generate PMN triangles that can be represented as integers without losing much accuracy? as the current bruteforce approach already takes ages to run if epsilon is under 0.07 (perhaps i need to adjust the range of the randomly generated P', not sure) What i currently do with the epsilon is check whether each component(fractional part) of both M' and N' is close to epsilon or close to 1 - epsilon, i have updated my answer with code that does that. \$\endgroup\$
    – Suic
    Jan 16, 2022 at 17:28
  • \$\begingroup\$ I could probably also improve my method in a way where it doesn't check the epsilon against all of the components of M and N but if instead 5 out of the 6 components are were within 0.001 and the 6th one was 0.05 then that would be better than for example all of the 6 components being within 0.15-0.2. This would probably help a bit, but im not sure how much(going to find out now) also, im not looking for a PMN triangle that has an error margin of 0.0001 as integers but 0.08 is a little too much as well (0.01 would already be acceptable) \$\endgroup\$
    – Suic
    Jan 16, 2022 at 17:34
  • \$\begingroup\$ After doing some more testing, currently the error rate i get is about 7-8% with an epsilon of 0.08 (which kinda makes sense) i also let it run with epsilon = 0.05, but no result after 15mins(Im not sure if it's simply not possible to construct a better(closer to an integer) PMN triangle for that specific triangle ABC or i just need to adjust my P' random range) \$\endgroup\$
    – Suic
    Jan 16, 2022 at 17:56
  • \$\begingroup\$ This sounds like a discrete optimization problem. You're searching for a set of 9 integers that minimize an error function. I'd recommend taking that question over to the Computer Science StackExchange. As a first heuristic, note that the further away P' is from P, the more granular control you have over the direction d, so focusing your search on somewhat distant P' values may help improve your success/error rates. \$\endgroup\$
    – DMGregory
    Jan 16, 2022 at 18:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .