Jump to content
  • Advertisement
Sign in to follow this  
zyrolasting

Still trying to understand Vector Projection

This topic is 3537 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

Vector Projection and detecting intersections has simply been a bane for me when I have plans for my game. It's been tiring looking around google with no clear novice tutorial to find. My issue has more to do with how vectors find their place, how direction is found, and how to determine at what point along the vector something key is happening, or has happened. To clarify: 1. If I want to check from a vector for the player's foot, I start a vector close to his foot and make a another one a little down on Y and work with those? For that matter, does intersection need to be a "line segment" between two vectors, or can one be used? If it's the latter, I'm more confused. (Since I would imagine there would be magnitudes all coming from the world origin, and I have no idea how that could manage an active 3D environment.) 2. How do I determine direction with any vector? 3. Most Troubling. I've gotten answers to this before, but none of them were clear to an utter novice. Please walk me through how to take one (two?) vectors and see if it went through a plane. All I'm doing now is seeing if my character can land on floors from a jump or fall. To give you an idea of my experience on that, I'm still having issues with dot products. I remember mention of 'plugging-in' to a plane equation. Also do not understand that. Another topic I started had a user give me a good start with terminology, but inner workings are still alien to me. I do think this would be among the last of the things I need to really learn before trying anything major, so I would be very appreciative for help on this.

Share this post


Link to post
Share on other sites
Advertisement
1. If you want to detect collision with things under a player's feet then yes, what you'd have to do is a line segment intersection test. That's sometimes called 'probe'.

Vectors are defined as 3-tuples (x, y, z), which are their unique coordinates in cartesian space (for example, the typical cartesian frame of reference would have an origin o(0, 0, 0), and three orthonormal directions i(1, 0, 0), j(0, 1, 0) and k(0, 0, 1)).

position a would be defined as vector(x, y, z), and a would be equal to :

a = o + x * i + y * j + z * k;

a few vector rules : let a, b, c be three vectors, and k a scalar (a number).

(a + b) + c = a + (b + c)
(a + b) * k = (a * k) + (b * k)
(a - b) = -(b - a)
a * k = k * a

a few operators

a + b = vector(a.x + b.x, a.y + b.y, a.z + b.z);
a - b = vector(a.x - b.x, a.y - b.y, a.z - b.z);
a * k = vector(a.x * k, a.y * k, a.z * k);
a / k = vector(a.x / k, a.y / k, a.z / k);
-a = vector(-a.x, -a.y, -a.z);

A unit vector is a vector with length of precisely 1. the length of a vector is :

length(a) = square_root(a.x * a.x + a.y * a.y + a.z * a.z); (this is derived from the pythagoras theorem).

a vector cannot be divided by another vector.

The dot-product is defined as :

a . b = a.x * b.x + a.y * b.y + a.z * b.z

these properties apply :

a . (b + c) = (a . b) + (a . c)
a . b = b . a
a . (b * k) = k * (a . b)

The dot product is a by-product of trigonometry and pythagoras.

a . b = cosine(angle(a, b)) * length(a) * length(b)

all these rules are basically derived from axioms and theorems. You'd have to get a proper lecture on vectors, trigonometry and geometry (which you should do tbh, the best way to learn that stuff).





2. You cannot determine the direction of 'any' vector. Only vectors that represent displacement (a relative quantity). i.e. the direction of a position vector alone is meaningless.

However, the direction of the position a from the position b would be (a - b).

The distance of a from b would be length(a - b). The unit vector direction of a from b would be (a - b) / length(a - b).







3. finding the intersection of a plane and a segment falls down to resolving two linear vector equations :

You have a segment defined by two end points [a, b].

A point p is on segment [a, b] if p satisfies the equation :

p = a + t * (b - a), t in range [0, 1].

for example, if t = 0 :
p = a + 0 * (b - a)
=> p = a

for example, if t = 1 :
c = a + 1 * (b - a)
=> p = b

for example, if t = 0.5 :
c = a + 0.5 * (b - a)
=> p = (a + b) * 0.5
=> that is the point exactly in the middle of the segment.

a plane can de defined by a normal n, and a distance to the origin d (a scalar value).

a point p is on the plane (n, d) if p satisfies the equation :
(p . n) = d

All points on plane (n, d) satify that equation. That is the basic definition of a plane.

now you want to find p, a point that is both on the segment [a, b] and the plane (n, d)

your known variables are a, b, n and d.

your unknowns are p, t.

your equations are :

eq 1. p = a + t * (b - a), t in range [0, 1].
eq 2. (p . n) = d

by substituting p from eq 1 into eq 2, you get...

(a + t * (b - a)) . n = d

(a . n) + t * ((b - a) . n) = d

t * ((b - a) . n) = (d - (a . n))

=> t = (d - (a . n)) / ((b - a) . n)

pluging-in t into equation 1, you will get the point of intersection between the line going across the segment and the plane.

However, there is another constraint on the segment equation. t has to be in the range [0, 1].

if t is outside that range, it means that the point will be on the infinite line going through the segment, but outsude the segment end points. if t < 0, p will be before point a. if t > 1, p will be beyond point b.

in short, the segment will not intersect the plane. if p is in the range [0, 1], then the segment is intersecting the plane, and P will be your point of collision.

if vector a if your character feet position, the distance of the character feet to the plane would be length(p - a).




I have no idea if all that cleared it up, or muddied it further...

Share this post


Link to post
Share on other sites
Let me put it this way, Once I understand the concept of how exactly vectors act as operands, that response, I'm sure, will be a tremendous help. Many thanks for the effort! Bumping up rating. But, what I don't understand, again, is how a struct of 3 properties act as operands. For example, that confusion came in when you said...

"a few vector rules : let a, b, c be three vectors, and k a scalar (a number)."

Even though you followed with simple math operators, and I understand how SOME of the overloaded concepts work, (I.E. Adding is just that for each component) it seems a huge amount of processing goes into it beyond what is normally expected. To be blunt, it's a bit overwhelming.

I think what can help me here is some visual examples of the process of projection/intersection/collision/etc... Do you have a suggestion of what can be a good resource for that?

Share this post


Link to post
Share on other sites
Quote:
Original post by zyrolasting
...how vectors find their place, how direction is found ... a vector close to his foot and ... one a little down on Y and work with those? ... a "line segment" between two vectors...

2. How do I determine direction with any vector?
I think you are confusing yourself with incorrect terminology. A vector has no position. It has no "place", it cannot be "close to his foot", or "a little down on Y", nor can there exist a line segment "between two vectors".

Your second question there is key: you don't determine direction with a vector, as a vector basically is a direction, and nothing much more (it has a magnitude or "length").

Position--like the position of a foot--can be indicated as a "point", which can be described by a vector with respect to some arbitrary origin (point P = Origin + vector). Furthermore, a vector can be scaled (multiplied by a scalar value) so that a line or line segment can be defined as a parametric equation P(t) = P0 + t*directionVector, where any value of t produces a point P(t).

You might benefit from a brief tutorial in linear algebra. I'm sure there are some good crash courses online.

ADDED:

Also, you were asking about collisions and that sort of thing... once you understand vectors, and their role in defining lines in 3D space (like I said, a line is simply a point in space with a direction vector, and that "point in space" is itself described as an origin and a vector), then you can fairly easily test for intersections between lines in 3D space and simple polygons.

Share this post


Link to post
Share on other sites
Interesting, this all was just covered in the first chapter of Calc 3, good to see the class having its uses!

Share this post


Link to post
Share on other sites
Quote:
I think you are confusing yourself with incorrect terminology. A vector has no position. It has no "place", it cannot be "close to his foot", or "a little down on Y", nor can there exist a line segment "between two vectors".

Your second question there is key: you don't determine direction with a vector, as a vector basically is a direction, and nothing much more (it has a magnitude or "length").

Position--like the position of a foot--can be indicated as a "point", which can be described by a vector with respect to some arbitrary origin (point P = Origin + vector). Furthermore, a vector can be scaled (multiplied by a scalar value) so that a line or line segment can be defined as a parametric equation P(t) = P0 + t*direction Vector, where any value of t produces a point P(t).

You might benefit from a brief tutorial in linear algebra. I'm sure there are some good crash courses online.

ADDED:

Also, you were asking about collisions and that sort of thing... once you understand vectors, and their role in defining lines in 3D space (like I said, a line is simply a point in space with a direction vector, and that "point in space" is itself described as an origin and a vector), then you can fairly easily test for intersections between lines in 3D space and simple polygons.


This is in contrast to Olii's mention of probing, I think, so I'm a little lost there. But I guess... I stand corrected?

I can tell you one thing I was confused about was the relation of an origin to vectors in a complex 3D scene. Do you always have to use the World origin?
(All vectors "sprout" from one place to check about?) It is possible to use Mesh Origins? How do you know where the vector IS, really? When you say they have no place, I'm truly, honestly, lost. This was an issue for a bit. I assumed three things.

I guessed...
1. Vectors always are in relation to 0,0,0 in world space.
2. Vectors can be in relation to a translation in D3DT_WORLD.
3. Based on what you said, maybe a Vector from a desired point? (Another Vector? Please clarify.)

But nonetheless, this didn't really clear much up. I've tried asking around here before, but all I'm hit with in answers is more terms I am not familiar with and formulas when I still am not clear on their purpose. Listen, I'm not good at this. It's as simple as that. Sorry, but it's not my field. I will try my best to learn it, but really, baby steps.

This is what I see in my mind when considering the topic. I assume a player falling, and a vector is pulling out to check a collision with the floor (or other bounding area on the floor.) I will get to bounding shapes when they come, but one last time: How is the vector "placed" for the check? And for that matter, am I using one or two? If they define direction, wouldn't I need to check along it like a line? I am about to explode.

Photobucket

smitty, Thanks for the input. I'll read over your post a few times to see if I hit some epiphany. Since you mentioned a linear algebra class course, do you have a good idea for one someone like me could try? I have no extra funds to pay for a tuition of any kind right now, thanks to the economy.

You know what I think would help? Example code. Know of any I could look at and understand with due time? Would it be too much to ask if one of you wrote a snippet to show me? I use C++.

[Edited by - zyrolasting on October 14, 2008 1:53:51 AM]

Share this post


Link to post
Share on other sites
you are using two. in the case you draw, a position (the feet), and a direction (down).

Vectors (as in, a vector class) represent BOTH positions in space and directions in space. There is a conceptual difference between the two, but they are both part of the vector class that has a few properties. You will seldom see vectors derived into position and direction classes as it's not really enough of a leap. I have seen that happen (example, a normal class). For example, you could have a Position class, and a Direction class, to separate the two concepts. However, it will become very messy very quickly. It is best to put both concepts under the same roof.

There is however, an almost 'sure' way to tell both apart with an easy implementation. You add an extra dimemsion to the 3-tuple. A direction vector would be defined as (x, y, z, 0), and a position vector would be defined as vector(x, y, z, 1). This is what John Carmack used to compute his infinite shadow volumes for Doom 3. Representing a vector (position or direction) that way, as a 4-tuple, works hand-in-hand with 4x4 transform matrix maths, and rasterisers.







ok, let's take a concrete example. You cannot have the direction of 'Paris', only it's position, inside a frame of reference (say, a given 2D map of the world).

You can get the direction of 'Paris' FROM 'New York'. It is roughly 'east'.

'east' does not imply any distance. It is just a pure direction. This is akin to a unit vector, pointing from New York towards Paris. Unit vector have no magnitude (or rather, a magnitude of 1). When used in vector operations, they will not 'scale' products like other vectors would (usually, a product between vectors implies a scaling by the magnitude (magnitude, a.k.a. norm, a.k.a. length) of the vectors. see the dot product / trigonometry relationship). That is an important property, unit vectors conserve distances, and can be used for a multiple of things. Normalising a vector is basically forcing it's magnitude to be 1, therefore dividing it by its length.





The distance you will have to travel to reach Paris from New York would be 3,000 miles (or something). That's the norm of the vector (Paris - New York). You subtract the two position, and that will give you a vector, with an implicit heading (a unit vector on a compass, that is (Paris - New York) / length(Paris - New York)) and distance (length(Paris - New York)) from it.

Similarly, if you look at weather reports, winds are represented by unit directions (east wind, north-west...), and a magnitude (20 knots, 40 knots, ...).






In the case you present, you want to cast a ray, the trajectory of a point (the feet), going downwards, and find to moment when the point hits the plane. This is almost the equations I highlighted in my original post.

In my post, I was using a segment made from two end-points (two positions). You are using a ray, made of a start position (the feet), and a unit direction (going down). The ray can also have a maximum length.

The equations are almost exactly the same. a ray is made of an start position (s), a direction (d), and a maximum length (length). That direction vector (d) is usually a unit vector, to simplify things.

eq 1. p = s + d * t, t in range [0, length].

then the rest of the algorithm applies.


Share this post


Link to post
Share on other sites
That was a LOT clearer. I'm still a little hazy, but that helped a LOT.

Alright, if I were to heavily summarize here...

If my player begins to be pulled down by gravity, my only concern should be DOWN, or 0, -1, 0. A unit vector for down. I can apply that direction to the position of my character's feet. I guess I would use his positions. If there is any relation between model space in Maya and Model space in DirectX, I assume the origin local to the mesh is the same.

How about this? This on the right track?

//Assuming a pointer to player struct with position is available.

D3DXVECTOR3 playerVec(player->x,player->y,player->z)
D3DXVECTOR3 FallDirection(0.0f,-1.0f,0.0f)

p = playerVec + FallDirection * t

I'm still unclear on T, but from what I understand, if T is in range of 0 and the length of the vector (magitude) there IS a collision?

Also, I'm getting a vague message that T can be effectively anything between 0 and a scalar, but I'm also having a little trouble with that.
Can I set T to anything in code, (I.E. 2) and I'll just be checking 2 units down? Is that all there is to it?

Share this post


Link to post
Share on other sites
I think you're confusing physics and maths. 't' is used in linear interpolation (as time?), but also in physics to mean time. The difference is that in linear interpolation (ie finding a point on a line), the value is typically constrained between 0->1.

Quote:

How about this? This on the right track?

//Assuming a pointer to player struct with position is available.

D3DXVECTOR3 playerVec(player->x,player->y,player->z)
D3DXVECTOR3 FallDirection(0.0f,-1.0f,0.0f)

p = playerVec + FallDirection * t

I'm still unclear on T, but from what I understand, if T is in range of 0 and the length of the vector (magitude) there IS a collision?



t is just some scalar. it can be 0 (in which case p = playerVec), or it can be any other value. As for the collision stuff, it depends on how you're solving this equation (ie what you're solving it with respect to).

I think you're confused about t. If you want to find a point p on a line segment, t is a scalar ranging from 0->1 (using underline to denote vectors, and letters to denote scalars). Consider the following..

we want to find the poisition of point p in 3d space. this point lies halfway between a and b.
a is at (1,2,3)
b is at (1,2,6)

we can represent some point on a ray p as a function of this scalar t...

f(t) = p0 + t * (p1 - p0)

(you might also see the equation in the form f(t) = p0 + tpd . In this case the author has simply decided pd = (p1 - p0).)

where p0 is the start of the line, p1 is the end of the line, and t is a scalar between 0 and 1 (a value beyond these numbers means the point is behind the start or beyond the end of the ray).

plugging in our values for a, b, and t (we want the half way point, so t is a half, or 0.5), we get.

f(t) = (1,2,3) + 0.5 * ((1,2,6) - (1,2,3))
= (1,2,3) + 0.5 * (0,0,3)
= (1,2,3) + (0,0,1.5)
= (1,2,4.5)

meaning the point half way between a and b is (1,2,4.5). You can verify this with graph paper.

If you wanted to find t, you could rearrange the formula to find t (ie find where along the ray some point is).

The code you presented would move your player t units down the y axis (asuming it's position is set to be p. The code won't detect any sort of collision, for that you'd need to run an intersection test. If/when you're clear with what you're asking about so far, I'd be glad to talk to you about intersections.

[Edited by - Winegums on October 14, 2008 12:28:27 PM]

Share this post


Link to post
Share on other sites
Quote:

Alright, if I were to heavily summarize here...

If my player begins to be pulled down by gravity, my only concern should be DOWN, or 0, -1, 0. A unit vector for down. I can apply that direction to the position of my character's feet. I guess I would use his positions. If there is any relation between model space in Maya and Model space in DirectX, I assume the origin local to the mesh is the same.

How about this? This on the right track?


sounds good.

Quote:


//Assuming a pointer to player struct with position is available.

D3DXVECTOR3 playerVec(player->x,player->y,player->z)
D3DXVECTOR3 FallDirection(0.0f,-1.0f,0.0f)

p = playerVec + FallDirection * t

I'm still unclear on T, but from what I understand, if T is in range of 0 and the length of the vector (magitude) there IS a collision?


correct. Basically, an infinite line will always intersect with an infinite plane (unless the line is strictly parallel to the plane). So you need to bound the intersection to the interval you are interested in (between the ray start position and end position).

Quote:

Also, I'm getting a vague message that T can be effectively anything between 0 and a scalar, but I'm also having a little trouble with that.
Can I set T to anything in code, (I.E. 2) and I'll just be checking 2 units down? Is that all there is to it?


correct. It means you will be checking 2 units down under the feet of the player.

FallDirection doesn't have to be strictly normalised. For example, it is quite useful to replace FallDirection by the actual velocity of the player, and the length can be replaced by the timestep of your simulation.

If the parameter t is in range [0, timestep], and you use the player velocity vector as the direction, that in turn will tell you if the player's feet will hit the floor sometime during the frame. Also, as the player velocity increases, the effective 'probe' range will increase too.




EXTRAS :

Also, note that floating point drift can throw a spanner in the works, so sometimes, it is best to use the two methods : Using the velocity of the player, the time step, but also add a little probe with a fixed length underneath for when the velocity is very small (and you will run into floating point errors).

So, use two probes, one using velocity and timestep only, the other, just looking under the feet (using a fixed length, say 2 unit, looking straight down) for safety in case you run into floating point errors.

[Edited by - oliii on October 14, 2008 10:32:11 AM]

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!