I've been looking around, trying to find out how to get the normal of a line segment. This has caused me quite a lot of trouble.

Every single time I've come across this stuff, I get something like:

Line1 = vector(x,y) _{(yes, because lines are usually defined by a single point)}
Line1.normal = vector(-y,x) _{(again, the normal [which I've always seen represented as a ray or line perpendicular to the original line segment] defined magically by a single vector)}

This all seems to be perfectly normal to everyone but me...so I fear I'm just being a massively dense dunderbum, but I can't find anything suggesting that this isn't how it appears.

Sorry if I sound a little frustrated, but I am. I guess it's just because it seems so incredibly simple, and yet fundamentally takes a neat little origami-crap on what I know of geometry. ( an origami-crap juuust big enough to keep me from doing what I need to do )

I really, really didn't want to resort to asking this here, but I'm about to flip my wig. Quick and easy answer? Anyone?

Thanks in advance.

A vector can be visualized as the line connecting the origin (0,0) and the co-ordinates specified by the vector.

So, if you have a line segment, then you need to use the 'slope' of the segment to calculate the normal. A normal is a single vector because its position doesn't matter; only its direction matters. If you want to draw the normal (N), choose any starting point you want, say P, and draw a line from P to P+N.

(I hope that made sense)

Oooo that makes sense!

But the only way I know of to find slope is:
slope = deltaY/deltaX

Which gives me a single number, making normal = (-y,x) Not really applicable.

Is there a different way I should be getting the slope, leaving me with a vector?

[edit]Unless I should just be using deltaX and deltaY as my (x,y) for the line?

I guess by slope I meant (deltaX, deltaY), so your normal is (-deltaY, deltaX)

Alright, cool.

I thought this would fix my problems, but it hasn't... I think my problem is that I need the dot product of N (normal) and V (movement vector of a point colliding with the line segment), but the issue is that I'm not using vectors for anything. Can I do this with normal floats?

[edit]I'm working from the bottom of this page. All of the (simple) math is using vectors, and I'm having a hard time working through them with floats.

This seems to be a problem you have with vector math in general, right? The page you linked would have left me totally blank, hadn't I already known all the vector stuff, so there's no need to reference to yourself as "massively dense dunderbum". I recommend catching up to the basics of vector math before even trying to understand the article. When you've got the basics down, return to it.

I'm not sure it's a problem with vector math that I have, so much as a problem implementing vector math without vectors...

Unless vectors are treated differently than two pair'd numbers?

Would I be wrong saying something like... Vector1(4,6) + Vector2(2,1) = (6,7)?

[edit] Before, I didn't mean that I had trouble figuring out how to get the dot product...I know how to get it, but it's giving me crazy values if I work through it without vectors.

They are not, because that is what vectors are. The operations you do on them a well defined.

That would be correct.

Remedy this situation. If you are using vector math and you are using C++, you should not be implementing your vector math as naked floats.

Alright...maybe I should just throw some code up then.

The Vn = [N.V]N is the part I'm having trouble with.

  float norm_x = (end->y - start->y) * -1;
  float norm_y = end->x - start->x;

//  This bit's iffy...  I need a vector for the normal veloctiy, found with [N.V]N
  float norm_x_vel = (norm_x*(pnt.x_vel/2) + norm_y*(pnt.y_vel/2)) * norm_x;
  float norm_y_vel = (norm_x*(pnt.x_vel/2) + norm_y*(pnt.y_vel/2)) * norm_y;

  float tan_x_vel = (pnt.x_vel/2) - norm_x_vel;
  float tan_y_vel = (pnt.y_vel/2) - norm_y_vel;

  float res = 1.0f;

  pnt.x_vel = (tan_x_vel - res*norm_x_vel);
  pnt.y_vel = (tan_y_vel - res*norm_y_vel);

I'm getting values of ~750 from norm_x_vel/norm_y_vel. But this is closer than what I had before. (sometimes as high as ~70,000)

[edit] As soon as this is done, I'll have accomplished what I set out to accomplish, and I'll need no more vector math. (until I start something new, o' course)

The normal vector is by definition of length = 1.

Put this after your calculate norm_x and norm_y:

float norm_x = (end->y - start->y) * -1;
float norm_y = end->x - start->x;

float norm_length = sqrt(norm_x * norm_x + norm_y * norm_y);

//probably do a check to see that normal vector is not of length = 0

//normalize the normal vector
norm_x /= norm_length;
norm_y /= norm_length;

//the rest of your code...

No. That's a normalized vector, not a normal vector. Not the same thing. It's often handy to keep your normals normalized, but they don't have to be.

Good to know! That helped a lot. It's still acting a bit funny though... Is the rest of my math right?

I stand corrected.

The website you are using, Anomie, is wrong (they never mentioned what type of a normal vector they seek directly) so technically it wasn't your mistake... but still if you knew how vectors work you'd see this error rather quickly.

It looks okay to me...

I'm not sure what you are trying to do here.

With regards to collisions, there are two totally different ways of modeling them:

The first is with a single instantaneous contact. You determine when and where the collision happened, and you place the point accordingly with its velocity reflected about the surface normal. You can make this more realistic by artificially adding a contact time, friction, spin etc. This is probably the wrong method for your purposes if you're attempting what I think you are...

The second method (which I consider far more elegant) is to model the collision as an acceleration of the point along the normal of the line segment. You're effectively creating a little spring during the contact time. The beauty of this approach is that rebound (reflection about the normal) is a natural consequence of the fact that you're only accelerating the point in the direction of the normal. The difficulty, however, is that if you're using a point (instead of a circle), the point will have to pass through the line segment (imagine the line segment is elastic, and the point stretches it a bit before rebounding). You can set the acceleration to something like if you want the line segment to be a hard surface (where x is the displacement of the point from the line along the line segment normal).

I did write a little demo many years ago which might be handy for you if I could just find it...

[edit]

Hehe, that's cute. I couldn't find it, but it seems someone cloned it for me, which is definitely a good thing if you knew what my code looked like back then SnookerClone.

I'm trying to do the 'Vn = [N.V]N' part of what's on that Gamasutra page, without any vectors. The idea was to break it into x_vel and y_vel...but I sure wouldn't bet money that I'm doing it right.

I'm all about elegance. The Gamasutra article was the only information I could find on collision response that wasn't specific to polygons or spheres, so I went with it. So how would I go about implementing your second method there? (all of my line segments are totally rigid, when it comes to collision)

[edit]Waithuh... Accelerate the particle by some degree in the direction of the normal... Of course!
[edit2] Okay...not as simple as I thought... Help?

The article is describing my first solution, but the formula is just plain wrong a bit misleading because it doesn't point out that the normal is normalized. You could do it something like this:

note: my functions are just pseudo code, but you should get the idea.

Aside from their normal vector gaffe, their formulas are fine (although I do agree that your second method is much better).

Get the unit normal vector to the line: N

Resolve the velocity along this normal vector: Vn = (V dot N) * N

Get the tangential velocity: Vt = V - Vn

Final velocity = Vt - Vn * K

Since when does a dot product return a vector? Pseudo-code or not, that is completely wrong.

Looking at it now, I think my problems might be from my collision detection stuff... As the particle's velocity decreases, it's more and more likely to pass through the line segment. (which is the problem I'm having, sorry for not mentioning that before)

Attached Win32 binary, for your viewing pleasure.

They are not vectors, they are the magnitude of the vectors resolved in the directions u and v (sorry, there was an error in my code).

Yeah true, "The relative velocity of the two bodies is checked by calculating N • V" was a bit misleading though, but I suppose the wording is actually correct since it's referring to a plane and not a line segment (relative velocity of a point with a stationary line segment would just be the magnitude of the velocity of the point). So yeah, it's exactly the same as my code, except that I waste time calculating two dot products (more intuitive) instead of one.

[edit]

Are you applying gravity before or after the collision? - because if you're doing the collisions first, then eventually it's going to fall through.

Otherwise you can just make it impossible for the point to ever cross the line: if it does, place it on the line (you should know how to check if it has crossed the line).

I'm applying gravity before the collision stuff, but...I think it's important that I work out what's wrong, rather than brute-force my way around the problem... All I'm doing is your direction test, and if it changes sign, register a collision. (also making sure the point lies within the area of the line)

So, before moving a point, you are checking if its new location cases a sign change. If it does, you're not moving it forward but instead registering a collision?

You're trying to find the equilibrium of a point (infinitely small) resting on a line (infinitely thin) - it's not exactly the most robust thing for a numerical integrator to model. Think about when the point is exactly on the line and stationary (this is what it's going to tend towards not counting floating point errors and the application of gravity with each step). As it reaches this equilibrium, it just needs a tiny floating point rounding error for the point to end up on the wrong side of the line.

You'll need to build in some sort of robustness yourself, or change what you are modeling (a circle colliding with a line, or a point colliding with a polygon).

Here comes a little function I cooked up. I think it works as it should.
It should return the vector that should be added to the colliding object's velocity if it doesn't loose any in the bounce.

Who has a better function?

(without reading all of the thread)

Rotate by Pi/4?

- I'll let you spot the redundancy

float length = hypotenuse.Dotproduct(line_normal) * hypotenuse_length;

Do I get a gold star?

Anything else? Maybe a completely different approach that's faster even?

{"name":"prod13608_lg.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/4\/64e6523352475d3c545de9cd6aabfb3e.jpg","w":500,"h":500,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/4\/64e6523352475d3c545de9cd6aabfb3e"}

Well, the original one is a single dot product, a single vector normalization and a few additions. I don't think it's possible to do much better than that.

I update the springs, update the particles, and then check for collision. The collision stuff checks the point's current location, and the point's current location plus it's current velocity.

I guess my problems make sense, with everything having no real space to take up... So can't I just add something like if( fabs(distance_from_line) < 4 )?

[edit] This has stopped most of my 'falling through' issues... The whole thing's still real jittery, though... I need to find out how to use RK-4 or Verlet Integration...

Ah, that was a bit hard to spot in all the discussion.

Much nicer.

Vector Project_collision_vector(const Vector& velocity, const Vector& line_direction)
{
  Vector line_normal(-line_direction.Y(), line_direction.X());
  line_normal.Normalize();
  return line_normal * velocity.Dotproduct(line_normal) * -2;
}

Then you would have a circle-line collision and not a point. Although if you want your triangle to behave robustly as a triangle with 3 sharp corners, you could do it like this: For each point on the triangle, calculate the midpoint of the remaining two points. So if your triangle is made up of the three points P1, P2 and P3, then for P1 the associated point is the midpoint of P2 and P3 - let's call it Q1.

Now a collision is identified by P1 and Q1 being on opposite sides of the line segment (using the direction test we've discussed before). We can assume that Q1 is always on the outside of the line segment. So we accelerate P1 away from the line segment it is colliding with along the normal to the line segment as before (solution 2 to the collision problem).

The solution is robust because even if P1 passes through the line segment, Q1 will still be on the opposite side, so the point will be accelerated away from the line segment :

http://www.allegro.cc/files/attachment/595320

Acc is in the direction of line segment normal, normalized, and potentially scaled by the distance of the point from the line. The sign of Acc needs to be modified according to the sign of the direction of P1 with the two line segment endpoints (so that if the collision happens from the opposite side, it will indeed accelerate downwards instead up upwards).

What I'm doing all this for is just a little physics toy, and the user would be creating their own shapes and things... I definitely wouldn't want to have a different case for each shape they could potentially make... And since it's just a toy, I'm not sure the circle-line bit bugs me. But they never calm down! Things stay jittery, and bounce a tiny bit. What's up with that?

Assuming you did not make any mistakes, that is a normal property of physics engines... Usually they take care of it through damping (i.e. always putting friction on everything).

The general case is to take Q as the centroid of the shape, however calculating the centroid, or even an estimation of the centroid (average of all points making up the shape) is computationally a lot more intensive. If it was me, I'd write some algorithm that tries to locate on "opposite" point (or set of points) for each point in any shape.

Yeah, and also, if you try stiffening up those springs in an attempt to get a rigid triangle, you're gonna end up with a stiff system - the bane of any simulation. If you want to do rigid bodies properly, you'll need to do them using rigid body dynamics - modeling a polygon as a set of points with definite relative positions, a centroid, angular velocity etc. Springs are good for jelly-like substances though.

Woo! Far enough along to start running into 'physics engine problems'! I've added friction like this:

  if( fabs(x_vel) > 0 ) x_vel -= FRICTION*x_vel;
  if( fabs(y_vel) > 0 ) y_vel -= FRICTION*y_vel;

But I still get a bit of jitter from any particles touching the line segment. Better ways?

[edit]

Awww... Seriously? There's no way to do that with my springs? They're so nice and elegant! I figured it was just because of my Euler stuff that stiff springs were acting badly...

[edit2]
Woooah...jelly back in 2003!

I'm afraid not. It will improve a bit with a better integrator, but not much. Also, a triangle is the only shape that will support itself without internal struts, so it gets very messy and inefficient to build rigid shapes from springs.

Well... What do you mean by 'improve a bit'? Right now if the spring is too stiff, the thing just explodes... I'm alright with a pixel or two of stretch/compression, is that do-able with my springs?

Yeah sure, decrease integration step size (i.e. more than one iteration per frame with smaller increments). Although keep in mind that it will become computationally expensive quite quickly, especially if you're planning to have hundreds triangles bouncing around. I don't know how much RK-4 will help - I've not used it for a physic based simulation before. I might try this evening though ...we shall see if 5 years at university studying maths and computer science has improved my jelly any.

Iterations per frame is no problem, but...smaller increments of what? Like...divide force by n before it's applied to velocity?

Jelly should always benefit from science!
(by the way, do you hate tabs?)

Yeah, normally delta values are multiplied by the time-step size.

5 years ago I did.

That was how I coded, back when I was into QBASIC!

A friend of mine did the same thing, but refused to leave any blank lines between stuff. I told him it was stupid and unreadable.

Anyways, doing five iterations per frame, and updating my position with velocity/5, the system loses all of its momentum. Is there something else I should be adjusting?

All delta values need to be scaled. So your friction, forces etc.

Everything needs to be in the form: x += delta_x * time_step.

So for example, if you had:

velocity.x *= 0.995; for dampening, you would need to convert this to:

velocity.x -= velocity.x *0.005 * time_step;

since:

velocity.x *= 0.995 * time_step; would of course be wrong.

And time_step would be 1/number_of_iterations?

[edit] Besides rigidity, the problem I'm having now seems to be stability. If I completely disable any dampening I get realistic momentum, but horribly erratic and uncontrollable springs. As I add dampening, the springs become more and manageable, but by the time they're anywhere near as mellow and stable as I want them, the momentum is completely gone from my system. Any ideas?

There's probably a clever component wise way to dampen only the energy associated with spring oscillations. I'll give it some thought.

Just to clear things up, the only place I'm applying my dampening is with the spring forces.

Not at my computer, but it's something like:

force = -(stiffness * (length - restLength)) - (DAMPENING * velocity);

...I think...

That doesn't make sense. You need to move that out of there. ..and I have a nice solution: when a spring contracts it looses energy, therefore you can dampen just the springs energy using this fact. I'll explain when I get back from bowling.

[edit]

To elaborate: the reason why what you have now is incorrect is, imagine the case where two points connected by a spring are moving quickly in the same direction, and maintaining the correct distance apart. A force will now be generated by your dampening component, which is incorrect.

The easiest way to dampen the system is to decay the velocity:

velocity -= DAMPENING*velocity;

The reason why it may appear that you're getting the correct dampening behaviour at the moment is because what you have is actually equivalent to what I am suggesting if you have a fixed number of springs (commutativity of addition). However you'll notice problems when you start adding more springs, and at some point (K*DAMPENING > 1) for K springs, it'll break altogether. So yeah, move that out of your spring force calculation, and dampen the velocity of each point independent of the springs attached to it.

However there is also a way to dampen the energy associated with a spring:

Consider the fact that the amount of energy held in a spring increases or decreases with the extension of the spring - we won't worry about the exact formula at the moment. So, if two points connected by a spring move towards each other when the spring is extended beyond its resting length, energy is being transfered from the spring to the particle as kinetic energy (or into another spring or whatever). Similarly, if it is compressed below its resting length, and the points then move away, energy is again lost from the spring. Thus if we dampen the force generated by the springs under these conditions, we can dissipate energy without tampering with the magnitude of the points velocity.

I've tested it with my jelly, and it has worked wonders for its stability.

That's like...totally sweet, dude... Sorry.

So then...I need to reduce the force from the springs by some rate, based on the amount it was stretched/compressed. How'd you implement that?

Before, I'd tried dampening this with a define - HEATLOSS, and I was kinda trying to do the same thing... Trying to model some non-visual expendature of energy...

[edit]Also, fixing that dampening stuff didn't really help...

You already have the current distance between the two points (let's call this length1). So now calculate length2, the distance between the two points adding the current velocity to the position of each: magnitude( (pnt2.p + pnt2.v) - (pnt1.p - pnt1.v)). The sign of (length2-length1) tells us if the points are moving towards each other or away.

Additionally the sign of (length1 - restLength) tells us if the spring is extended or contracted. So the sign of the product of these tells us if the spring is loosing energy or gaining energy.

  dampen = ((length2-length1)*(length1 - restLength) < 0 )  ?  0.7 : 1.0;

  force = -(stiffness * (length - restLength)) * dampen;

[edit]

I haven't looked at the energy equations in detail so the value of dampen is just picked out of thin air. There is probably a derivation to get exactly what dampen should be, and it's likely to be some function of the magnitude of energy conversion. I'll look at that in detail some time, but for the moment this works quite nicely. You can decrease 0.7 down to 0.3 and still see almost 0 momentum loss while the springs are quite heavily dampened.

That helped the springs a lot, but I'm still having issues with getting things (just the particles, I guess) to calm down. I'm not sure why... But I'm going to attach another binary, just so you can get a feel for what I'm saying.

Known Problems:

No loss of speed from the particles (I think).
Particles don't like colliding with the underside of a line segment.
Slope pulls particles up it, since I increased the angle.

Yeah, your collision code appears to be faulty.

Alright, thanks!

Going now to scour the intarwebs for information.