Jump to content
  • Advertisement
Sign in to follow this  
Alessandro

Finding points in 3D space after rotations/translations (images included)

This topic is 2511 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm trying to figure out how to retrieve points in 3D space in the following scenario.
If you take a look at the included image (click it to show it full size), basically I have a head model with a green hair attached to a hook point on the head itself.
The triangle coordinates (T1,T2,T3) of the hair follicle are known, and also hair points (H1,H2,H3,H4) are known.
The head (and the attached hair) are due to rotations and transformations in 3D space. I do not have access to that information. What I know are the final triangle coordinates (T1,T2,T3) and the hair hook point (T3=H1).
At this point I'd like to be able to calculate H2,H3,H4 so that they follow the original hair direction.

I'm at odds with math, but I thought I could do it with vectors.
If I save H1H2, H2H3, H3H4 before doing any transformation/rotation, could those be used later? I'm a bit confused...

hairIssue.jpg

Share this post


Link to post
Share on other sites
Advertisement
I can think of two solutions:

  1. Make a reference frame using T1 as origin, and {T2-T1, T3-T1, cross_product(T2-T1,T3-T1)} as basis vectors, express H1, H2, H3 and H4 in those coordinates and then use that representation to reconstruct their positions after the rotation.
  2. Since you know how T1, T2 and T3 are mapped by the movement (rotation + translation), you can reconstruct the movement with that information.

The first one is probably easier to implement.

Share this post


Link to post
Share on other sites
Alvaro, thank you very much for your quick response.
Would be possible to elaborate solution 1 a bit more?

Would solution 2 imply using matrices?

Share this post


Link to post
Share on other sites
The way I think about this, both solutions imply using matrices.

In the case of solution 1, we need to be able to express any point P in the frame of reference that has origin at T1 and basis vectors (T2-T1, T3-T1, cross_product(T2-T1,T3-T1)). Let's call these three vectors (V1, V2, V3). Expressing point in P that frame of reference means finding the coefficients k1, k2, k3 such that

P = T1 + k1 * V1 + k2 * V2 + k3 * V3

We can subtract T1 from both sides and we get

P - T1 = k1 * V1 + k2 * V2 + k3 * V3

If you compute P - T1 in standard coordinates, the mapping from standard coordinates to (V1, V2, V3) coordinates is a linear transformation, so it can be expressed as a 3x3 matrix M. Its inverse is the mapping that goes from coordinates in the basis (V1, V2, V3) to standard coordinates, which is very easy: It's just the 3x3 matrix that has V1, V2, V3 as columns. So invert that matrix and you'll get M. You can now multiply M by each of the vectors H1-T1, H2-T1, H3-T1, H4-T1 and you'll get the coordinates that we were looking for.

Finally, to obtain the new positions H1', H2', H3' and H4' you just compute T1' + k1 * (T2'-T1') + k2 * (T3'-T1') + k3 * cross_product(T2'-T1', T3'-T1') for each point.

Share this post


Link to post
Share on other sites
I'd rather respond in the open, in case someone else is interested in the code:
#include <iostream>

struct Point3D {
double x, y, z;

Point3D(double x, double y, double z) : x(x), y(y), z(z) {
}
};

struct Vector3D {
double x, y, z;

Vector3D(double x, double y, double z) : x(x), y(y), z(z) {
}
};

Vector3D operator-(Point3D p1, Point3D p2) {
return Vector3D(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z);
}

Vector3D operator+(Vector3D p1, Vector3D p2) {
return Vector3D(p1.x + p2.x, p1.y + p2.y, p1.z + p2.z);
}

Point3D operator+(Point3D p, Vector3D v) {
return Point3D(p.x + v.x, p.y + v.y, p.z + v.z);
}

Point3D operator+(Vector3D v, Point3D p) {
return p + v;
}

Vector3D operator*(Vector3D v, double s) {
return Vector3D(v.x*s, v.y*s, v.z*s);
}

Vector3D operator*(double s, Vector3D v) {
return v * s;
}

std::ostream &operator<<(std::ostream &os, Point3D p) {
return os << '(' << p.x << ',' << p.y << ',' << p.z << ')';
}

std::ostream &operator<<(std::ostream &os, Vector3D v) {
return os << '(' << v.x << ',' << v.y << ',' << v.z << ')';
}

struct Matrix3D {
double m11, m12, m13,
m21, m22, m23,
m31, m32, m33;

Matrix3D() {
}

Matrix3D(Vector3D col1, Vector3D col2, Vector3D col3)
: m11(col1.x), m12(col2.x), m13(col3.x),
m21(col1.y), m22(col2.y), m23(col3.y),
m31(col1.z), m32(col2.z), m33(col3.z) {
}
};

double determinant(Matrix3D const &m) {
return m.m11 * (m.m22 * m.m33 - m.m23 * m.m32)
- m.m12 * (m.m21 * m.m33 - m.m23 * m.m31)
+ m.m13 * (m.m21 * m.m32 - m.m22 * m.m31);
}

Matrix3D inverse(Matrix3D const &m) {
double i = 1.0/determinant(m);
Matrix3D result;
result.m11 = i * (m.m22 * m.m33 - m.m23 * m.m32);
result.m12 = i * (m.m13 * m.m32 - m.m12 * m.m33);
result.m13 = i * (m.m12 * m.m23 - m.m13 * m.m22);
result.m21 = i * (m.m23 * m.m31 - m.m21 * m.m33);
result.m22 = i * (m.m11 * m.m33 - m.m13 * m.m31);
result.m23 = i * (m.m13 * m.m21 - m.m11 * m.m23);
result.m31 = i * (m.m21 * m.m32 - m.m22 * m.m31);
result.m32 = i * (m.m12 * m.m31 - m.m11 * m.m32);
result.m33 = i * (m.m11 * m.m22 - m.m12 * m.m21);

return result;
}

Vector3D operator*(Matrix3D const &m, Vector3D v) {
return Vector3D(m.m11 * v.x + m.m12 * v.y + m.m13 * v.z,
m.m21 * v.x + m.m22 * v.y + m.m23 * v.z,
m.m31 * v.x + m.m32 * v.y + m.m33 * v.z);
}

Vector3D cross_product(Vector3D v1, Vector3D v2) {
return Vector3D(v1.y * v2.z - v1.z * v2.y,
v1.z * v2.x - v1.x * v2.z,
v1.x * v2.y - v1.y * v2.x);
}

int main() {
// Original positions
Point3D t1(2.0, 2.0, 2.0);
Point3D t2(3.0, 2.0, 2.0);
Point3D t3(2.0, 3.0, 2.0);
Point3D h1(4.0, 5.0, 6.0);
Point3D h2(5.0, 7.0, 9.0);
Point3D h3(6.0, 7.0, 2.0);
Point3D h4(4.0, 6.0, 3.0);

// New positions
Point3D T1(-2.0, 0.0, 2.0);
Point3D T2(-3.0, 0.0, 2.0);
Point3D T3(-2.0, -1.0, 2.0);

// m converts from standard coordinates to the basis I described earlier
Matrix3D m = inverse(Matrix3D(t2-t1, t3-t1, cross_product(t2-t1, t3-t1)));

// Matrix a maps the coordinates to the new location
Matrix3D a(T2-T1, T3-T1, cross_product(T2-T1, T3-T1));

Point3D H1 = T1 + a*(m*(h1-t1)); // If you implement the product of
Point3D H2 = T1 + a*(m*(h2-t1)); // a matrix times a matrix, you can
Point3D H3 = T1 + a*(m*(h3-t1)); // compute a*m in advance, if you are
Point3D H4 = T1 + a*(m*(h4-t1)); // going to do this for many points

std::cout << "H1 = " << H1 << '\n';
std::cout << "H2 = " << H2 << '\n';
std::cout << "H3 = " << H3 << '\n';
std::cout << "H4 = " << H4 << '\n';
}

Share this post


Link to post
Share on other sites
Hello Alvaro, the code works perfectly, thank you very much.


I'd like to ask, if it's not too much disturb, a little explanation of the theory behind it.
If I understand it correctly, you first calculate t2-t1, t3-t1 vectors, and the normal on point t1 (crossproduct call).
Then you build a matrix out of those 3 vectors, and you calculate the inverse matrix. Why? Is this done to get the local matrix of the basis vectors?

Also, besides translate/rotate, I tried also scaling the final triangle coordinates; the H1,H2,H3,H4 coordinates are calculated correctly, but I'd like to ask if it's possible to have those mantain the same distances as the originary h1,h2,h3,h4.

Share this post


Link to post
Share on other sites
My second post explained the theory behind the code. Try to read both the explanation and the code and see if it makes sense. If it doesn't, try to ask some more specific question about what it is that you don't understand.


Also, besides translate/rotate, I tried also scaling the final triangle coordinates; the H1,H2,H3,H4 coordinates are calculated correctly, but I'd like to ask if it's possible to have those mantain the same distances as the originary h1,h2,h3,h4.

Yes, of course that can be done. It probably just requires normalizing the three vectors (t2-t1, t3-t1, cross_product(t2-t1,t3-t1)) before and after the transformation. See if you can make the changes to the code to get that to work.

Well, now that I think about it, the fact that I picked t1 as the origin now becomes important, all of a sudden. So the correct solution probably involves deciding what point of the triangle the hair is attached at. Otherwise the problem is not well defined.

Share this post


Link to post
Share on other sites
Then you can change the roles so T3 is the distinguished point, instead of T1. Then just change the code to normalize the three vectors (t1-t3, t2-t3, cross_product(t1-t3, t2-t3)) and the three vectors (T1-T3, T2-T3, cross_product(T1-T3, T2-T3)).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!