Sign in to follow this  
Decrius

3D triangle: get hill steepness

Recommended Posts

Decrius    100
I have no idea how it's called in english, but I want to know how steep the hill of a 3D triangle is on the x and y axis. I have 3 vertexes of the triangle with XYZ values, and I need the ammount of height increase for the x axis and the y axis...I hope you get what I mean. I'm really bad at 3D math...never had it in school, will have it in the university I guess :D [Edited by - Decrius on August 16, 2008 12:42:01 PM]

Share this post


Link to post
Share on other sites
Mike nl    390
I assume you mean that the ground is the XY plane, and Z is the height direction, and you want the steepness of a triangle, i.e., the angle to the ground?

I've never tried this, but after some thought, how about this:
Take the dot-product of the height-direction (0,0,1) and the normal of the triangle ABC (cross-product of AC and AB). Since (the absolute of) the dot-product of two vectors represents the cosine of the angle between those two vectors, take the inverse cosine to get the angle between the triangle normal and +Z, which is the same as the angle between the triangle and the XY plane.

Or in code:
steepness = acos(abs(dot(cross(C-A, B-A), Vector3(0,0,1)))
Note that the steepness is now in radians.

If you need help visualizing this, imagine the triangle flat on the ground, normal sticking straight up. The dot-product with +Z is 1, acos(1) = 0 degrees.
If the triangle is perpendicular to the ground plane, then the normal is parallel to the ground plane, the dot-product with +Z is 0, and acos(0) = 90 degrees.

Share this post


Link to post
Share on other sites
Decrius    100
I see, so you take C as the base point and take the difference between C and the other 2 (separately) points. But what is a cross-product and a dot-product?

Also, once you know the steepness, you can calculate the steepness along the X and Y axis separately I suppose? Because what I ultimately want to do, is getting known of 3 angles: x, y and z angles. The z angle (rotation around the z-axis) is no problem, I have that, the other 2 most correspond with the triangles angles. I need to place a model on a face and it should really have the same angles (a chest on a hill doesn't stand flat, does it? ;-)).

Thanks though!

Share this post


Link to post
Share on other sites
Kern_d    100
I think to get what you want you should just do

steepnessX = abs(dot(cross(C-A, B-A), Vector3(1,0,0))

and

steepnessY = abs(dot(cross(C-A, B-A), Vector3(0,1,0))

This should give you how much your normal is pointing in the x or y axis.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by Decrius
I see, so you take C as the base point and take the difference between C and the other 2 (separately) points. But what is a cross-product and a dot-product?

Also, once you know the steepness, you can calculate the steepness along the X and Y axis separately I suppose? Because what I ultimately want to do, is getting known of 3 angles: x, y and z angles. The z angle (rotation around the z-axis) is no problem, I have that, the other 2 most correspond with the triangles angles. I need to place a model on a face and it should really have the same angles (a chest on a hill doesn't stand flat, does it? ;-)).

Thanks though!
Google will tell you about the dot and cross products (just Google those terms - you could also try e.g. 'vector math tutorial').

There are methods for aligning an object to a surface that don't require getting the 'x, y, and z angles' (I assume you're referring to Euler angles here). One method is to compute an orientation from scratch using the triangle normal and a reference vector. Another method is to make a relative adjustment to an existing orientation that aligns the object to the surface.

For a non-moving item, the first of the two methods described above would probably be adequate. (All of these methods will require at least some basic vector math and/or trig, so post back if you need help with that.)

Share this post


Link to post
Share on other sites
Mike nl    390
Like jyk said, no need for complicated things here. What you want is a transformation matrix that aligns the object's Z axis with the normal of the face (I'll assume Z is 'up' in object space).

The only problem is that there's still a degree of freedom. That is, you can rotate the object around the normal and it'll still be placed properly on the terrain. Or, in other words, what should the object's X axis be aligned to? And only you can answer that, since you're making it :)

A suggestion though: it could be stored in the map, i.e., the map designer determines it.

Share this post


Link to post
Share on other sites
Decrius    100
Thanks for the replies guys, I'm pretty good at maths, but we only did 2D stuff till now (which can be complicated as well) so I'm fairly new to what the 3rd dimension involves and all those new terms that ship with it.

I'll explain what I want to achieve:
I build maps (area's you play in) for Call of Duty 4. Mapping is quite time consuming, and I'd love some ways to limit 'troll' work. One of the troll jobs with mapping, is placing grass. Imagine a map with a lot of grass textured terrain, some tree's...bushes...houses...what is missing is the grass model, which gives an incredible more realistic view, where the terrain is no longer consisting of flat, triangle pieces, but actually 'lives'.

To do this, you have multiple (~20) grass models which you have to place on the terrain triangles. While the map editor is quite nice (you place the grass above the terrain, then press a button and it randomly resizes and rotates the model, and makes it go along the steepness of a hill. This requires me to copy paste a lot (really a lot, to make it realistic, the grass models almost have to touch each other) of models, and press that button. Small maps...okay, but big maps, no way. So I'd love to make the computer do the troll work (and it's meant for that! hehe xD).

So, what I did, is building a interpreter of the map file format. It reads in the terrain triangles the map has. Whenever the texture is grass, it will randomly pick a few positions on the triangle (see my previous thread), and place grass models at those positions. Then it appends the data for the model placements to the map file, and I have grass models in my map :).

So, for each triangle I have 3 vertexes in a 3D space. I have a position on the triangle, but that's not important...if you look straight down at the triangle, it's always flat, so it has only one steepness level on the whole triangle.

This is how the model data looks like in a map:
...
// grass entity
{
"origin" "-87.04 -97.28 -46.08"
"modelscale" "1.45697"
"angles" "0 232 0"
"model" "foliage_grass_flowerplants_squareclump"
"classname" "misc_model"
}
...



origin is done, it's the XYZ values I calculate with Mike's formula in my previous thread. Model scale is purely random, so is the model and the second angle...which is the rotation around Z...which doesn't matter whenever it's flat (X and Y rotations are 0), but whenever that's not the case, the Z rotation might make the model not attach to the ground (place a model with X rotation 45 degree, and turn it around the Z axis 180 degree, it's now at right angles to the terrain, seen from the X axis).

So, what I want to figure out, is what the first and last angles should be, where it can also compensates the rotation around the Z axis...

Well, I find it quite hard to imagine this situation in my head, and I still ponder on how the origin (previous thread) can ever be calculated this way.

Anyways, I hope this cleared up the matter, I will look into the product terms tomorrow, getting late now...

Previous thread

Share this post


Link to post
Share on other sites
Decrius    100
Okay, I believe the dot product is not correct, since it should somewhere do something with an angle as well...but I don't know how to calculate it and with what :S. Anyways, this is the code, should these be correct?

struct Vertex
{
float x;
float y;
float z;

Vertex(float x = 0.0f, float y = 0.0f, float z = 0.0f) : x(x), y(y), z(z) {}
Vertex operator- (Vertex &vertex)
{
return Vertex(x - vertex.x, y - vertex.y, z - vertex.z);
}
};

Vertex cross(Vertex &vertex1, Vertex &vertex2)
{
return Vertex((vertex1.y * vertex2.z) - (vertex1.z * vertex2.y), (vertex1.z * vertex2.x) - (vertex1.x * vertex2.z), (vertex1.x * vertex2.y) - (vertex1.y * vertex2.x));
}

Vertex dot(Vertex &vertex1, Vertex &vertex2)
{
return Vertex((vertex1.x * vertex2.x), (vertex1.y * vertex2.y), (vertex1.z * vertex2.z));
}


Thanks!

Share this post


Link to post
Share on other sites
Mike nl    390
No, the cross is correct, but the dot-product is:

float dot(const Vertex &vertex1, const Vertex &vertex2)
{
return (vertex1.x * vertex2.x) + (vertex1.y * vertex2.y) + (vertex1.z * vertex2.z);
}


Finally, angle = acos(dot(v1, v2))
Then, angle is the angle between the two vectors.

However, to use this to get the angles which you seek is a different matter. You can try to take the dot product w.r.t. +X and +Y, but I have no idea if that's how CoD4 does it. And another problem with Euler angles is that the order in which they're applied matters. And I really don't know how CoD4 does that either. So you'll have to try some stuff.

Share this post


Link to post
Share on other sites
Decrius    100
Thank for your reply, but how can the dot-product ever be a value between -1 and 1? It gets to 16384 and 65536 for me (the triangles are from -128 to -128 x and y, and 0 to 64 z), so the result of acos is never right. What have I forgot? How can the dot-product ever result in a value between -1 and 1?

Share this post


Link to post
Share on other sites
Mike nl    390
As yes, it assumes all vectors are of unit length (length == 1), so you need to normalize the vectors BA and CA before taking the cross and then dot:

angle = acos(dot(cross(normalize(B - A), normalize(C - A)), Vector(0,0,1)))

normalize, in case you don't know, is:

Vector normalize(const Vector& v)
{
float length = sqrt(v.x*v.x + v.y*v.y + v.z*v.z);
return Vector(v.x / length, v.y / length, v.z / length);
}


i.e., divide the vector by its own length. This doesn't change the direction of the vector, but ensures its length is 1.

Share this post


Link to post
Share on other sites
Decrius    100
Thanks Mike! That seems to work! ;)

One problem though, it does take the steepness, but doesn't know the direction...
Sometimes I have to rotate it (from the top view) to get it exactly on the terrain.

Another point, it can have a random rotation, which somehow has to be included into the calculations (the 2 X and Y angles have to be adjusted to the rotation...).

It's really magic to me, lol, so sorry for asking so much :O

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Original post by Decrius
Thanks Mike! That seems to work! ;)

One problem though, it does take the steepness, but doesn't know the direction...
Sometimes I have to rotate it (from the top view) to get it exactly on the terrain.

Another point, it can have a random rotation, which somehow has to be included into the calculations (the 2 X and Y angles have to be adjusted to the rotation...).

It's really magic to me, lol, so sorry for asking so much :O
I would not use Euler angles to build the initial orientation for the grass mesh. Instead, I would do something like the following:

1. Compute the axis-angle rotation that rotates the default 'up' vector of the grass model onto the triangle normal. Both the axis and the angle can be computed using the cross product of the two vectors (ask if you need details).

2. Apply a random rotation about the local up vector of this new orientation. This will have the effect of randomly modifying the grass model's 'roll' without affecting its alignment.

3. Convert the resulting orientation matrix to an Euler-angle triple using the same conventions used by the map format (i.e. axis order and so on).

An alternative to step 1 is to build the orientation using cross products and a reference vector, as mentioned previously.

Obviously there's some math required here, but there's really no way around that. I would really recommend though that you not use Euler angles for this (except, of course, for the final representation as written to the map file).

Share this post


Link to post
Share on other sites
Decrius    100
Quote:
Original post by jyk
I would not use Euler angles to build the initial orientation for the grass mesh. Instead, I would do something like the following:

1. Compute the axis-angle rotation that rotates the default 'up' vector of the grass model onto the triangle normal. Both the axis and the angle can be computed using the cross product of the two vectors (ask if you need details).

2. Apply a random rotation about the local up vector of this new orientation. This will have the effect of randomly modifying the grass model's 'roll' without affecting its alignment.

3. Convert the resulting orientation matrix to an Euler-angle triple using the same conventions used by the map format (i.e. axis order and so on).

An alternative to step 1 is to build the orientation using cross products and a reference vector, as mentioned previously.

Obviously there's some math required here, but there's really no way around that. I would really recommend though that you not use Euler angles for this (except, of course, for the final representation as written to the map file).


Okay, thanks. The format in which it is written is the degree in which it's turned (around the X Y and Z axis).

What do you mean with the 'up' vector? Can you give me the details for step 1? :)

Share this post


Link to post
Share on other sites
Decrius    100
Okay I found it out! Haha! I thought it would be best not to ask ANOTHER math question...so it would look like you guys did the work, instead of me. So I've been digging the matter for a few days, and got results! It works exactly as I want!

Thanks a lot guys. Thanks Mike, fellow land mate ;).

Share this post


Link to post
Share on other sites
Mike nl    390
Quote:
Original post by Decrius
So I've been digging the matter for a few days, and got results! It works exactly as I want!

And that's what we like to see [wink]

Quote:
Original post by Decrius
Thanks a lot guys. Thanks Mike, fellow land mate ;).

Always for a fellow Dutchy [grin]

Share this post


Link to post
Share on other sites
Decrius    100
Hmm, I screamed victory just a little too early. It seemed to work, but after better research it didn't really.

The problem is, that I want to rotate the grass model along the z-axis seen from the grass model itself. Then I would have to translate that into x, y and z angles in the real grid.

I currently use this for the x and y angles. I would also calculate a rotation float from 0 to 360 to determine the rotation of the object (in it's own grid! so relative to itself, not to the world grid).

float angle_x = acos(abs(dot(cross(normalize(vertex3 - vertex1), normalize(vertex2 - vertex1)), Vertex(0.0f, 0.0f, 1.0f)))) * 180.0 / M_PI;
float angle_y = acos(abs(dot(cross(normalize(vertex3 - vertex1), normalize(vertex2 - vertex1)), Vertex(1.0f, 0.0f, 0.0f)))) * 180.0 / M_PI;


Since the math above is magic to me, I simply tried to rotate the 3 vertexes around the z-axis at point 0,0,0. Then the x and y angles would be compensated by the z angle (the rotation), and it would be perfect...but theory isn't reality here :'(...can't find why it didn't work, so I think it's best to make the changes to the math above, but I have no idea where.

So, input is: rotation of the model itself, 3 vertexes.
Output should be: 3 angles.

Thanks!

Share this post


Link to post
Share on other sites
Mike nl    390
Okay, let's take this from the top.

I take it you're not that good with linear algebra, so: we can define any transformation (such as translation, rotation, scaling) with a 4x4 matrix. To apply multiple transformations, we can simply multiply the matrices and the resulting matrix will describe the combined transformation. We can then convert the final rotation matrix into Euler angles. So let's take this process in steps.

First step is to rotate the model around Z the axis. Rotating around Z is just an operation in the XY plane so we'll create a matrix for the 2D rotation (assuming counterclockwise rotation):


Matrix z_rotation(
cos(angle), -sin(angle), 0, 0,
sin(angle), cos(angle), 0, 0,
0, 0, 1, 0,
0, 0, 0, 1 );



Then, we need to align the XY plane of the model with the triangle. This is a 3D rotation to align the Z axis of the model, with the triangle's normal vector. The normal vector can be found by taking the cross-product of two (normalized) vectors that lie on the triangle. Obviously, CA and BA lie on the triangle:

Vector3 normal = cross(normalize(C - A), normalize(B - A));


If you find that the model comes out flipped (i.e., aligned with the backside of the triangle), then the normal is pointing the opposite way and you need to swap C and B in that statement.

Now we need to find the rotation matrix that aligns +Z with that normal. This page gives an example of aligning +Y to a vector. So, following it's principle:

float xzLength = sqrt(normal.x * normal.x + normal.z * normal.z);
float yAngle = -acos(normal.z / xzLength);
float vecLength = sqrt(normal.x * normal.x + normal.y * normal.y + normal.z * normal.z);
float xAngle = -acos(xzLength / vecLength);



So all we need to do now is create two matrices, to rotate around X and Y:

Matrix x_rotation(
1, 0, 0, 0,
0, cos(xAngle), sin(xAngle), 0,
0, -sin(xAngle), cos(xAngle), 0,
0, 0, 0, 1 );

Matrix y_rotation(
cos(yAngle), 0, -sin(yAngle), 0,
0, 0, 0, 0,
sin(yAngle), 0, cos(yAngle), 0,
0, 0, 0, 1 );



Then, we can multiply all three rotations together:

Matrix final = z_rotation * y_rotation * x_rotation;



And finally, convert that matrix to euler angles:

float angle_x = atan2(-final.m12,final.m11);
float angle_y = atan2(-final.m20,final.m00);
float angle_z = asin(final.m10);



You'll have to experiment a bit with rotation direction (clockwise/counterclockwise; flip angles) as I don't know whether that stuff is left-handed or right-handed and whether it uses clockwise or counterclockwise rotations. It's also possible I named the final angles wrong.

I hope that if it doesn't work right way, you can figure it out with the information above. Use Google. Expect to learn about linear algebra.

[Edited by - Mike nl on August 20, 2008 2:08:20 PM]

Share this post


Link to post
Share on other sites
Decrius    100
Wow, thanks for your lengthy post! Very much appreciated, will try it out tomorrow.

Btw, why do you use a matrix? Is it just for simple value storage or has it a higher purpose?

Thanks!

Share this post


Link to post
Share on other sites
Gage64    1235
Quote:
Original post by Decrius
why do you use a matrix? Is it just for simple value storage or has it a higher purpose?


There's a sample chapter on matrices here. I highly recommend that you read it (at least the second part of it) - it has one of the clearest explanations of matrices I've ever seen.

For some of the stuff there, though, you'll need to know some vector math. For that, I recommend the sample chapter from here.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this