Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Finding the Normal of a Line Segment

This thread is locked; no one can reply to it. rss feed Print
 1   2 
Finding the Normal of a Line Segment
james_lohr
Member #1,947
February 2002

{"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"}prod13608_lg.jpg

Quote:

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

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.

Anomie
Member #9,403
January 2008
avatar

Quote:

So, before moving a point...

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...

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

Trezker
Member #1,739
December 2001
avatar

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;
}

james_lohr
Member #1,947
February 2002

Quote:

So can't I just add something like if( fabs(distance_from_line) < 4 )?

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

Anomie
Member #9,403
January 2008
avatar

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?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

SiegeLord
Member #7,827
October 2006
avatar

Quote:

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

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

james_lohr
Member #1,947
February 2002

Quote:

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..

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.

Quote:

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

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. :)

Anomie
Member #9,403
January 2008
avatar

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]

Quote:

Yeah, and also, if you try stiffening up those springs in an attempt to get a rigid triangle...

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 am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

I figured it was just because of my Euler stuff that stiff springs were acting badly...

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.

Anomie
Member #9,403
January 2008
avatar

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?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

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. :P

Anomie
Member #9,403
January 2008
avatar

Quote:

(i.e. more than one iteration per frame with smaller increments)

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

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

smaller increments of what? Like...divide force by n before it's applied to velocity?

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

Quote:

(by the way, do you hate tabs?)

5 years ago I did. :P

Anomie
Member #9,403
January 2008
avatar

Quote:

5 years ago I did. :P

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?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

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.

Anomie
Member #9,403
January 2008
avatar

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?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

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.

Anomie
Member #9,403
January 2008
avatar

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...

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

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. :P

[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.

Anomie
Member #9,403
January 2008
avatar

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...

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Quote:

How'd you implement that?

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.

Anomie
Member #9,403
January 2008
avatar

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.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

james_lohr
Member #1,947
February 2002

Yeah, your collision code appears to be faulty.

Anomie
Member #9,403
January 2008
avatar

Alright, thanks!

Going now to scour the intarwebs for information.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

 1   2 


Go to: