Sign in to follow this  
zyrolasting

Still trying to understand Vector Projection

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
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
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
Quote:
Original post by zyrolasting
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.)
This has mostly been cleared up alredy, but...

The origin is completely arbitrary... you can switch origins any time you feel like it, and create a different coordinate system. In fact, that is how things are rotated and that sort of thing. If you want to rotate a cube, you perform a rotation around an origin which is at the center of the cube. But that origin is, itself, described in terms of the world origin <0,0,0>.

In "world space" there will necessarily be a common origin on which everything "agrees". Position would mean nothing without some implied origin. Olii mentioned that vectors and points are interchangeable in practical terms, and that is absolutely true... if you treat a <x,y,z> vector as a position, there is an implied origin of <0,0,0>. I only pointed out the distinction because you seemed to be conflating the two concepts a little bit, and I think it is or was contributing to your confusion.

For reasons that would be best understood after doing some linear algebra and learning about the relevant matrix transformations, a vector is actually a 4d entity in the form of <x,y,z,0> while a point is <x,y,z,1>. For simplicity, we can assume that common origin and drop the 4th dimension, and rely on context to know when we are discussing a vector or a point. Just remember that vectors have no position whatsoever, and if you are referring to a location, you are dealing with a point (which actually involves the implied <0,0,0> origin plus a vector offset).

Links:
** MIT OpenCourseware Linear Algebra class

** This may or may not be helpful.

** Rays are basically parametric line equations with a positive t value [P(t) = P0 + t*v]... once you understand these things, read all about how to test for intersections of rays and other objects/

Share this post


Link to post
Share on other sites
Quote:
Original post by Winegums
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.
As long as you are clear that your are "interpolating" between two points, as in a line segment [P(t) = P0 + t*(P1-P0) | 0 <= t <= 1]. If you are scaling a unit vector to produce a point on a line (which is what you said) then t is unconstrained. And for a ray it is constrained to all values >= 0.0.

Share this post


Link to post
Share on other sites
[quote]Original post by smitty1276
Quote:
Original post by Winegums
And for a ray it is constrained to all values >= 0.0.


Sorry, I should've clarified between infinite rays and line segments.

Share this post


Link to post
Share on other sites
I'm coming along. It's so nice to see such help you guys are.

Alright. Since I do tend to think visually about these kind of things, I slapped together another couple of images to see if I am following.

Scalars became easy to grasp after that post. Regardless of magnitude, the scalar represents a point on my ray from 0 to 1, beginning to end. Kind of like Texture Space in UV mapping. Smitty mentioning "interloping" made that click.

Photobucket

Checking an intersection itself is much clearer, but I do have couple more questions.

Photobucket

Apparently the point made from the scalar I choose needs to be checked in that interval. I understand that's the range of points available on a plane, right?
Olii mentioned an interval between 0 and timestep. I never saw anything like that before.

If the generated point is greater than or equal to the interval (How exactly is that checked in code?) there is either a collision or a pass-through (Another collision, really.) Less than represents no collison; my object has not gotten close enough.

Photobucket

I assume this is a good practice you mentioned, Olli?

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

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

I'm hearing t being mentioned as both a form of time and a scalar in your post, Wine. I guess this is a key reason for checking with velocity?

But regarding that formula, I didn't see you mention what f represents. Since T is right there with "scalar" in mind, I assume it is related to (or IS) the ray itself?


Tossing in another code attempt.

//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)

D3DXPLANE floor(0.0f,1.0f,0.0f,5.0f); /*Read this in book recently. Normal pointing up, distance 5 units from origin.*/

p = playerVec + FallDirection * 0.5 /*Checking halfway down on unit vector FallDirection*/




The only thing I think I'm still unclear on is plugging in for the plane equation.
Quote:

(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)


One of you most likely just told be, but what exactly is happening here?
How is this being stepped through?

I think I can assume a here is playerVec and b is FallDirection, right?
n and d are pretty obvious now, but what's happening in this process?
It looks like as you step through those equations, nothing was evaluated until the end. It just looks like parenthesis moving about to me.

Share this post


Link to post
Share on other sites
Quote:

I'm coming along. It's so nice to see such help you guys are.

Alright. Since I do tend to think visually about these kind of things, I slapped together another couple of images to see if I am following.

Scalars became easy to grasp after that post. Regardless of magnitude, the scalar represents a point on my ray from 0 to 1, beginning to end. Kind of like Texture Space in UV mapping. Smitty mentioning "interloping" made that click.


yes, similar concept. the ray equation p = s + d * t is a parametric equation.

the equation p(t) = p0 + t * (p1 - p0) can be re-shuffled to produce a more common linear interpolation equation p(t) = p0 * (1 - t) + p1 * t;

Again, that p0...p1 equation is also a by-product of a the original ray equation. It's just vector manipulations.

Quote:

Checking an intersection itself is much clearer, but I do have couple more questions.

Photobucket

Apparently the point made from the scalar I choose needs to be checked in that interval. I understand that's the range of points available on a plane, right?


you dont actually need to check the point to see if it is in the interval. The scalar value itself is what you check against the interval.

Quote:

Olii mentioned an interval between 0 and timestep. I never saw anything like that before.

this is standard procedure for collision detection. Objects trajectories are often reduced to linear trajectories aver a short time (the frame timestep), and you try to find the earliest collision happening withing that time step. That usually involves a 'trace', looking along the trajectory path and computing the time of collision (t).

Of course, to collide withing the frame timestep, t needs to be in range [0, timestep].


Quote:

If the generated point is greater than or equal to the interval (How exactly is that checked in code?) there is either a collision or a pass-through (Another collision, really.) Less than represents no collison; my object has not gotten close enough.

Photobucket


correct. It is possible you will miss collisions if your object moves by more than your probe depth.

Quote:

I assume this is a good practice you mentioned, Olli?


not really. This is a problem with checking points for collisions. Since points have no size, they can pass through things easily if you are no careful.

Quote:

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

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

I'm hearing t being mentioned as both a form of time and a scalar in your post, Wine. I guess this is a key reason for checking with velocity?

But regarding that formula, I didn't see you mention what f represents. Since T is right there with "scalar" in mind, I assume it is related to (or IS) the ray itself?


f(t) is basically a fancy mathematical representation for naming the parametric equation p0 = t * (p1 - p0). That's probably one of these maths notations you hate. It means "function of (parameter t)". It means that the parametric equation p0 + t * (p1 - p0) has one unknown quantity, and the result will depend only on the value of t.

you may be over-thinking things. consider the ray equation

p = s + d * t.

say you find a value for t = 0.77. What it really means is that the plane is at 0.77 times the vector d from the start position s. Regardless of what d and t actually means.

if d is a unit vector measuring units, it means that the plane is at 0.77 units away from start position.

if d is a velocity in meters / second, it means that the plane is at 0.77 seconds away from the start position.

if d is your your segment (end position - start position), it means that the plane is intersecting your segment roughly 3/4 the way through, and is close to the end point.

Quote:

Tossing in another code attempt.
*** Source Snippet Removed ***

The only thing I think I'm still unclear on is plugging in for the plane equation.
Quote:

(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)


One of you most likely just told be, but what exactly is happening here?
How is this being stepped through?

I think I can assume a here is playerVec and b is FallDirection, right?
n and d are pretty obvious now, but what's happening in this process?
It looks like as you step through those equations, nothing was evaluated until the end. It just looks like parenthesis moving about to me.


Let me put it in code :


bool rayPlaneIntersection(Vector playerVec, Vector fallDirection, float rayMaxRange, Vector planeNormal, float planeD, float& tParam, Vector& pIntersect)
{
tParam = (planeD - (playerVec.dotProduct(planeNormal)) / (fallDirection.dotProduct(planeNormal)); // intersection parameter.

if(tparam < 0.0 || tParam > rayMaxRange)
return false; // the plane is outside the range of the ray.

pIntersect = playerVec + fallDirection * tParam; // point of intersection
return true;
}


also, a couple of words of warning.

As you can see, if fallDirection.dotProduct(planeNormal) is close to 0, you will be doing a division by 0. It means basically that the fallDirection vector will become parallel to the plane (so there are no intersection possible). In that case, you just exit early with no intersection.


if(fabs(fallDirection.dotProduct(planeNormal)) < 0.000000001f)
return false;


secondly, you have to be careful what planeD represents. in litterature, planeD (the fourth parameter in the D3DXPLANE structure) can represent the distance of the plane to the origin, or the opposite, the distance of the origin to the plane. So there could be a sign involved (either use planeD or -planeD in the equation, see which one works).

Thridly, again in litterature, a ray is often considered to be semi-infinite. i.e. people would not use a 'max' value for the ray, but in practise, it is good to have a cap on the ray, especially in collision detection, where you will be dealing mostly with finite intervals. In ray-tracing rendering, less so. And in ray-tracing, the rayDirection vector would most likely expected to always be a unit vector.

Share this post


Link to post
Share on other sites
Quote:
Original post by zyrolasting

I assume this is a good practice you mentioned, Olli?

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

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

I'm hearing t being mentioned as both a form of time and a scalar in your post, Wine. I guess this is a key reason for checking with velocity?

But regarding that formula, I didn't see you mention what f represents. Since T is right there with "scalar" in mind, I assume it is related to (or IS) the ray itself?



The reason i mentioned both forms of t is that it can be confusing for someone to see a variable used in vector maths and physics which means different things in each. When considering finite line segments (ie a line with a beginning and end), t is a scalar to define how far along the line some point is.

f(t) is just "a function of t". f(t) could just be replaced with p, ie the point we want to find.

Quote:

The only thing I think I'm still unclear on is plugging in for the plane equation.
Quote:

(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)


One of you most likely just told be, but what exactly is happening here?
How is this being stepped through?



in the above, i believe a is the current position, and b is where you will end up if you keep falling (ie where you will be at the end of the next time step). This gives us a translation vector for this time step.

I'll try to talk through what oliii has said. I'm not 100% on it all, but I think i know what he's talking about.

as we've said, you can define a line segment as

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

where
p0 = start of line segment
p1 = end of line segment
t = scalar allowing us to find some point on the segment between p0 and p1 (inclusive).


and you can define a plane as
p.n = d

where
p is some point on the plane (any point will do)
n is the normal of the plane
d is the planes distance from the origin

we can substitute f(t) into the plane equation in place of p, which gives us

f(t).n = d

expanding this gives us what oliii has. By rearranging it we get everything in terms of t, which is what we want. We know everything else, and if t evaluates to be between 0 and 1, there is a ray-plane intersection.

worked example time!

plane with point s = (4,3,0) and normal n = (1,0,0)
ray with p0 = (1,3,0) and p1 = (7,9,0)



as you can see, the plane will be represented by the light blue line, and will lie parallel to the y-axis.

First thing to do is to find d. the equation of a plane says.

p.n = d

so plug in numbers

s.n = d
[4] [1]
[3] . [0] = d
[0] [0]

(4 * 1) + (3 * 0) + (0 * 0) = d
4 = d

Which makes sense, the plane is clearly 4 units from the origin.

So now we have the complete equation, we can replace the point on the plane p with the equation of a line


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

to find where on the line the intersection occurs

p.n = d

f(t).n = d

f(t).n = d

(p0 + t * (p1 - p0)) . n = d

after jiggering this around a bit (as oliii showed you) we get this equation in terms of t.

t = (d - (p0 . n)) / ((p1 - p0) . n)

we then substitute in our values for d, t, p0 and p1

            [1]    [1]          [7]  [1]    [1]
t = (4 - ([3] . [0] )) / (( [9] - [3] ) . [0] )
           [0]    [0]          [0]   [0]     [0]

                                         
                                                   [6]  [1]
t = (4 - ((1*1) + (3*0) + (0*0)) / ( [6] . [0] )
                                                   [0] [0]



t = (4 - ((1*1) + (3*0) + (0*0)) / ((6*1) + (6*0) + (0*0) )

t = (4 - 1) / (6)

t = 3/6 = 1/2 = 0.5f

As this value is in the range 0->1, we can infer that the ray intersects the plane at the point where t = 0.5. So what is this point in 3d space? We go back to the equation of a line to find out...


ray with p0 = (1,3,0) and p1 = (7,9,0)

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

            [1]             [7]    [1]
f(0.5) = [3] + (0.5) * ( [9] - [3] )
            [0]             [0]   [0]

            [1]             [6]
f(0.5) = [3] + (0.5) * ( [3] )
            [0]             [0]

           [1]    [3]
f(0.5) = [3] + ( [1.5] )
            [0]    [0]


            [4]
f(0.5) = [4.5]
            [0]

So the intersection occurs at point (4, 4.5, 0). Looking at the graph again, this is quite obvious (draw a line between p0 and p1, and you'll see it intersects at about there).

EDIT: Damnit, beaten to the punch!

DOUBLE EDIT: I suck at formatting, also not sure if I'm helping or not...please let me know if I'm just spewing maths at you unhelpfully.

[Edited by - Winegums on October 15, 2008 2:38:04 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by zyrolasting
Olii mentioned an interval between 0 and timestep. I never saw anything like that before.


(I started this ages ago and got pulled away, but it never hurts to read these sorts of things in several peoples' words, so here goes even though its been answered like 3 times now...)

Why is t as a timestep related to vectors? Imagine that an object is at a specific point, P0, in space. It is moving at a velocity V given in meters per second of V = <x, y, z>. Where will that object be in 1 second?

P(1.0) = P0 + 1.0 * V

In 2 seconds? P(2.0) = P0 + 2.0 * V.
In some specific value T seconds? P(T) = P0 + T * V.

The line segment between a current point and some position T seconds later is defined by all points from P0 along the line through P(T). Breakin' it down:

Current point:
PO is equal to P(0)
Position in t seconds:
P(T)
Vector from initial point to point in T seconds:
P(T) - P(0)

All points between initial point and point in T seconds (renaming function to F just it isn't confused with P above, and note that T and t are not the same thing):
F(t) = P(0) + t * ( P(T)-P(0) ) where t ranges from 0.0 to 1.0 (the full length)

Notice that at t=1.0, you get F(1.0) = P(0) + P(T) - P(0) = P(T) and at t=0.0, you get the initial point... that is interpolation between two points, and it can describe all points between the starting point and the location after T seconds.

Share this post


Link to post
Share on other sites
I feel like I'm having my head beaten in with a squiggly bracket, but this really is helping! Kudos to Wine for the deeper walk through there. It was very number jammed, but I think I needed to see where each was going like that. Things like that do help me. I do have a question about it a little down in this post.

Apparently all I need to concern myself with in basic collisions is to define start/end points, locate the point of collision (if any) and just run the code for either circumstance. Let me toss out my still hazy areas, I'll try not to eat TOO much of your time.

Olii, your code has parameters of type Vector. I thought I saw a vector header (as in .h) at one point, but could get no definition from it. D3DXVECTOR3 did not include a dotProduct function. Are you using another typedef and you didn't post it? Are we even using the same C language?

Quote:

ray with p0 = (1,3,0) and p1 = (7,9,0)

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

[1] [7] [1]
f(0.5) = [3] + (0.5) * ( [9] - [3] )
[0] [0] [0]

[1] [6]
f(0.5) = [3] + (0.5) * ( [3] )
[0] [0]

[1] [3]
f(0.5) = [3] + ( [1.5] )
[0] [0]


[4]
f(0.5) = [4.5]
[0]


Whoa, what? I know there can be a lot of good I can get from this, but what exactly is going on when you plug these in? Specifically, I notice you are making more use of the Y component of each vector. Also, what do the numbers represent above and below each evaluated formula? (I.E. [1][7][1] and the [0]s below each)

I think I understand the concept of velocity behind it. I think it's a little embarrassing I got told pretty much the same thing 4 times now, but even so.

So far I understand how to know how to "position" (lacking a better word if that's inaccurate) a ray and to make use of a scalar to specify a range to check for collisions. I understand that the collision has NOT happened if T is negative or above the maximum range of the ray.

I guess I can think of it like holding a pencil perpendicular to your arm and strafing into a wall. The pencil acts as the ray, and p0 would be the eraser and p1 would be the tip. Given our world, I suppose the scalar is always 1 there. If I walked to the right, I'd have a direction of (1.0f,0.0f,0.0f)

Going off Olii's snippet here.
I take the dot product of my start (A) vector and the plane normal, and divide it by my end (B) vector also by the plane normal, and have it subtracted from the plane's distance from the origin to find the point of intersection.

Repeating what I said above, I understand that the collision has NOT happened if T is negative or above the maximum range of the ray.

Hey, do any of you have a question you could quiz me with? Maybe I should try to see if I understand any of this with a more hands-on example.

Share this post


Link to post
Share on other sites
Quote:
Original post by zyrolasting
Whoa, what? I know there can be a lot of good I can get from this, but what exactly is going on when you plug these in? Specifically, I notice you are making more use of the Y component of each vector.
It looks like he just arbitrarily chose the y-component to illustrate the vector operations. You have to do those operations on all components, of course.

Quote:
I understand that the collision has NOT happened if T is negative or above the maximum range of the ray.
You're pretty much right, but you're approaching it slightly "backwards". A ray has no maximum range. It is just a line (an origin point and a direction vector). You determine what, if anything, the ray intersects in that direction. For collision, you will also determine how far your object will move along that direction vector in a given time interval and then you can check the distance to see if the ray intersection falls within the range of the motion.

Like I said, you were basically correct, but you might as well get the concepts/sematics clear now so it doesn't give you trouble later.
Quote:
The pencil acts as the ray, and p0 would be the eraser and p1 would be the tip. Given our world, I suppose the scalar is always 1 there. If I walked to the right, I'd have a direction of (1.0f,0.0f,0.0f)
Again, you're looking at it a little bit backwards.... a pencil is equivilent, roughly, to a line segment. You could describe it with the eraser as the origin, but the tip wouldn't necessarily be at t=1.0. The value of t that gives you the tip of the pencil would be whatever the length of the pencil is. POINT(t) = ERASER_POSITION + t*PENCIL_DIRECTION. If you really wanted to you could choose your units so that the pencil's length was length 1.0, but that seems arbitrary.

My main point is, again, rays have no length. They are infinite lines into space, described only by an origin point and a direction vector.



Share this post


Link to post
Share on other sites
It seems much that was discussed had more relation to line/segments rather than rays, even though rays were used. (Given we discussed "start" and "end" points.)
I understand what you mean about infinite distance. That is a lesson I learned in the first few weeks of geometry class. (Barely passed that class :p )

So I guess this just tells me that from the start point, the ray goes to infinity but there is still that "end" point and the scalar is going between the "start" and it?

Just curious here, are each of you guys approaching this in a slightly different way?

Share this post


Link to post
Share on other sites
Quote:
Original post by zyrolasting
It seems much that was discussed had more relation to line/segments rather than rays, even though rays were used. (Given we discussed "start" and "end" points.)
Yes, if you are talking about start and end points, then you are talking about line segments, but line segments are just lines with an extra piece of information. The original reply to your original question was describing plane/segment intersection test, which is a ray intersection test with the additional constraint that you must check t to see if it the ray/plane intersection occurs within the length of the line segment.

What I've been wanting to explain is that the existence of a "line segment" is superfluous to the intersection test. You do a ray/plane intersection... you find that it intersects at some value for t... you THEN check to see if t lies within the distance you are interested in (the "line segment").

Quote:
So I guess this just tells me that from the start point, the ray goes to infinity but there is still that "end" point and the scalar is going between the "start" and it?
No... a line or ray has no end point. The scalar can be any real number from negative infinity to positive infinity. (A ray is just a special case of a line, where you are only interested in points given by a positive scalar.)

Quote:
Just curious here, are each of you guys approaching this in a slightly different way?
No, we're all saying the same thing... I'm just being a stickler on the semantics because I think you'll benefit from understanding when you are talking about a point vs vector, or a line vs segment vs ray. [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by zyrolasting

Whoa, what? I know there can be a lot of good I can get from this, but what exactly is going on when you plug these in? Specifically, I notice you are making more use of the Y component of each vector. Also, what do the numbers represent above and below each evaluated formula? (I.E. [1][7][1] and the [0]s below each)



I had a bad feeling the formatting would mess this up...I was trying to represent vectors like..


p = (px, py, pz) in collum form...


[px]
[py]
[pz]

EDIT: Used forced spaces to try to make the layout a bit clearer...

Share this post


Link to post
Share on other sites
I do think I speak for everyone here that this may have been discussed enough...
Unless, Of course, something was left out.

I'll say one more time: Thanks so much for helping me through this. I haven't been to a forum this supportive before. I'm used to hearing stuff like: "Your FOR loop is crap" and that's it. :p

How about we try wrapping this up by having me try to apply this in code?

Here's my next attempt.


//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);
D3DXVECTOR3 PlaneNormal(0.0f,1.0f,0.0f);
D3DXVECTOR3 WhereItHappened;

float t, d = 5.0f, scl = 2.0f;


D3DXPLANE floor(PlaneNormal.x,PlaneNormal.y,PlaneNormal.z,d); //Normal pointing up, distance 5 units from origin.

/*I'll be checking 2 units down on unit vector FallDirection. (via scl variable
above) Even though I am checking 2 units down, those 2 units can be considered
a "cap" since I am, by basic ray definition, checking in infinite distance in
one direction.*/


t = (d - (D3DXVec3Dot(playerVec,PlaneNormal))/(D3DXVec3Dot(playerVec,planeNormal));
/*Find the parameter to check with scalar.*/

if (t < 0.0 || t > scl)
{
/*Nope. Nothing happened. Wrap up script and...*/
return false;
}

/*Got something. Where exactly did it happen?*/
pIntersect = playerVec + FallDirection * t; /*Find point of intersection.
Judging from Olii's example in code similar to this, it'd be better to
have a reference to the vector containing the result than to do it locally.*/

return true;




Am I still wrong or off anywhere? I think I'm getting it.
For the record, I remember your word of warning Olii.

Now, I just had an idea. I mentioned a player struct. Wouldn't be useful if I included another x, y and z coordinate group with stores the last position it was in? I figure it the player hits a wall, it's position should revert to the very last one. A engine I sometimes use, Game Maker, had a similar practice.

Share this post


Link to post
Share on other sites
Quote:
Original post by zyrolasting
t = (d - (D3DXVec3Dot(playerVec,PlaneNormal))/(D3DXVec3Dot(playerVec,planeNormal));

Am I still wrong or off anywhere? I think I'm getting it.
I haven't checked the math, but assuming Olii's intersection test is correct, you might have your operations grouped incorrectly (depending on where you meant to put the missing close parenthesis) and one of your vectors is wrong.

Olii's:
t = (d - (a . n)) / ((b - a) . n)
Yours (if I remove the unmatched parenthesis at front):
t = d - (a . n) / (a . n)

You need to use parenthesis to group the first part:
t = (d-(a.n)) / (a.n).

And the (a.n) in the divisor is wrong... to match the (b-a) in the example's divisor you need the downward fallDirection vector, not the position (which was a in Olii's example).

Quote:
I figure it the player hits a wall, it's position should revert to the very last one.
Not necessarily... your object could cover quite a lot of distance between undates. What if a bullet is travelling at supersonic speeds, and 1/30 sec later has impacted a wall? You want it on the wall, not in the gun.

In this situation, I would pull the object/player/whatever back along the negative velocity vector until its bounding volume is no longer intersecting the thing it collided with. Of course, you might want to have things bounce or reflect, which is another calculation.

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