I'm working on a simple Pinball game to help me learn and understand some of the 3d physics. I'm struggling, but progressing.

What I have now is a ball that can interact with triangles. Adding a radius to the ball wass giving me problems.

This code gives me the correct position of where the ball will hit the plane. And the new velocity is calculated as such.

// d is the magnitude of the new velocity
// if vel magnitude was 20 but we only moved 15 
// then the new magnitude is of length 5
this->vel = ( ( tri->normal *
                tri->normal.dotProduct( -this->vel ) *
                2.0 ) +
              this->vel ).normalize() * d;

There is a slight problem in that if the ball is just on the edges of 2 joined triangles then it will pass thru sometimes.

Also what I need now is a good tutorial on 'rolling ball physics' (I can't seem to find any good ones).

And some ides on how to incorporate friction, gravity, ...

Any help would be great.

I don't know of any rolling ball physics tutorials, but google might find you something.

newball = pv - ( vhat * fabs( ( radius - len ) / sin( this->angleBetween( -v ) ) ) );
Um... what exactly is that doing? Shouldn't the new ball position just be:
newball = pv + this->normal * 2.0 * (radius - len);//assumes normal is a unit vector
Based upon the theory that, after the ball hit the surface, it bounced, and the distance it bounced is equal to how far it would have gone through the surface if it hadn't bounced? (note that the 2.0 in there should be the same as the 2.0 in your velocity calculation... if elasticity changes, both numbers should change)
edit: Just saw this:

When modified for finding the point of collision, I end up with something like this:

float tick_fraction = 1 - (len-radius) / (plen-len);//time before collision
newball = p + tick_fraction * v;//position at that time

Friction... any time there's an impact, you want to get a velocity portion normal to the polygon and a velocity portion in-plane (perpendicular to the normal) of the polygon... and the friction applies a force the ball in the opposite direction of the in-plane velocity component, proportional to... I'm not precisely sure, probably proportional to the in-plane velocity and some kind of surface parameter. Once you add friction though, you'll also need to add spin, because the friction force is applied at the point of contact in a direction not pointing towards the center of the ball, so spin is imparted. And once there's spin, you calculate friction for motion due to spin also... at that point, the in-plane velocity is the sum of the regular in-plane velocity and the portion due to spin, which, if I were to guess of the top of my head, might be cross product of the normal vector with the axi of spin, multiplied by the magnitude of the spin and the radius. Don't quote me on that, I probably got it wrong. Also, you might want some kind of threshold between static friction and dynamic friction.

Gravity seems fairly straightforward, just add it to the velocity vector every tick. Though you might need some kind of weird optimizations for dealing with continuous rolling contact with a surface once gravity is in.

Um... I don't see any code that deals with triangles really, what I see mostly looks like it deals with infinite planes. Maybe you have code for discarding infinite-plane collisions where the contact point isn't on triangle, and you're not showing that code here? If so, your problem could be that you're not accounting for collision that occur when the edge of the ball touches one of the triangle edges, such that the ball penetrates the infinite plane before it touches the triangle. For that you'd need to have something for colliding a line with a sphere, which doesn't sound too hard (equivalent to a cylinder with a point, after all), and maybe also something to deal with collisions with the corners of the triangle. If that's not your issue, maybe you have rounding problems, dunno.

Also, is Triangle::normal normalized? If not, why? If so, why divide by it's length in Triangle::distance?

No, it wouldn't.

Look at bottom left of picture:

{"name":"590331","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f396971a547a904313dbab2a7284106d.png","w":640,"h":480,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f396971a547a904313dbab2a7284106d"}

R is radius
L is len
P1 is p + v and is too close to plane
P2 is where it needs to be

D0 != ( R - L )

Using trig: sin( angle ) = y / h;

or h = y / sin( angle )
or D0 = ( R - L ) / sin( angle )

newlength = ( ( radius - len ) / sin( this->angleBetween( -v ) ) );
newball = pv - ( vhat * fabs( newlength ) );

Yes, 'isPossible' deals with infinite planes.
Here is the code for the collision of the triangle.

Hm... I stand by my original equations.

In your diagram, I'm interpretting the following:
P0 = position at time 0
P1 = position at time 1 if collision is ignored
P2 = position at time T, when the collision occurs (0 <= T < 1)
P3 = position at time 1, with collision taken into account

The initial formula I gave
pv + this->normal * 2.0 * (radius - len);
is for P3

The formula I added a few minutes after then:
float tick_fraction = 1 - (len-radius) / (plen-len);
newball = p + tick_fraction * v;//position at that time
is for P2 (and also T)

Hm... actually, on closer look, I believe that your formula yields the same results as my second formula. I got confused with the trig there. I still think my formula is superior, as it is faster and uses no trig

edit:
(added extra excuse above) (revised excuse)
Also, that additional code confirms that the problem is that you aren't handling collisions with the edges, and thus you should have balls passing through polygon boundaries on convex surfaces (though not concave ones). You need to add a second check, to see if the ball hits any of the edges.
edit2:
For an example, consider this 2 dimensional case:
Your ball is at (0,2) at time 0. Its velocity is (0,-5). There is a line segment begining at (sqrt(2)/2,0) and extending rightwards to (5,0). The ball has radius 1. Your algorithm finds that it hit the infinite line at point (0,0), but that that lies outside of the line segment, because the X coordinate, 0, is less than the line segments lowest X coordinate, which is sqrt(2)/2, and ignores the collision with the infinite line. However, at time 0.2+0.2*sqrt(2)/2, the ball hits the edge of the line segment and deflects such that its new velocity should be... um... it would take me a bit to calculate that (edit3: new velocity is (-5,0)). But, it does deflect at that time.

You would think it, but it's not. Mainly because I'm not worried about P3. The ball needs to be placed at P2. You can't just put the ball at P3 after a collision because there might be another collision inbetween P2 and P3.

_move is called recursively until the magnitude of velocity is zero.

That's what I'm not sure about.

You still seem to be ignoring my formula for P2 and T, which, as I mentioned, is faster and yields the same results. But that's okay. Some games do put the ball at P3 (or the rough equivalent) for speed or simplicity (or possibly even stability) reasons, but I guess that's not what you want.

Minor stylistic points: what you called "velocity" in your code is what I would call a "delta" or "movement". I would have the functions return the time passed before collision rather than calculate that from the distance moved.

Hm... actually... more importantly, the way you have that set up, I think it can pass through one triangle before hitting another, if the triangle it should have hit came later in the list than another triangle further along the path, thus skipping a collision. I think you need to test against all possible triangles, find which one has the lowest time, apply that collision, then repeat. Like this:

My earlier statement that all you needed for gravity was to add the gravity vector to the velocity vector every tick was based upon the assumption that you didn't need more accuracy than the typical game. If you want total accuracy w/ gravity, then you have to resolve you collision equations assuming a parabolic movement path (nasty!). The above code attempts to make a compromise for decent gravity.

Which part? I mean, are you unsure you need to add it, or are you unsure on sphere-line collision detection, or unsure on sphere-line velocity / angle calculations, or thinking there might be a better way, or what?

Ok, I really appreciate your help. You gave me something to think about with that shortest time idea.

Velocity can also be defined as rate of change of displacement or just as the rate of displacement, depending on how the term displacement is used.

I don't want to upset you but I still think you have the wrong formula for P2.

I did realize that my sin function will only work on planes perp to z. I need to work on that.

And I'm unsure about the calculations. I don't know how to check for a collision against an edge.

Since you're trying (I think) to correctly handle arbitrary numbers of collisions per ball per tick, what I would call "continuous time physics", I think that, or something like it, is essential.

The issue I have is that the quantity you refer to as velocity, you then... break down, ablate, in such a manner that it's not really "per unit of time" anymore. Just semantics, but something I shy away from for fear of getting confused.

You're not likely to upset me.
Hm... oops, sign error: for P2, I meant (radius-len) rather than (len-radius); tick_fraction is supposed to be between 0 and 1, the ratio of movement prior to penetration of the infinite plane to total movement, using only the portion in direction of the normal vector in order to simplify calculations. At which point, the numbers are, (5 radius - 2 plen = 3 penetration in the direction of the normal vector) / (10 len - 2 plen = 8 movement in the direction of the normal vector), is 3/8, substracted from 1 is 5/8, 0.625, or 62.5% of the movement done prior to the collision. Multiplied by the movement delta, yields (10.825,6.25,0), magnitude 12.5.

Your formula looked at the penetration distance in the direction of the normal vector, ( radius - len ), and divided by the sin of the angle to convert to absolute distance, and multiplied by the direction vector, and ended up with (12.124, 7.0, 0), magnitude 14.

Even with the sign error corrected, the two formula disagreed on the example numbers? Why? Because the example numbers are not internally consistent. I believe you meant them to correspond to an example in which the plane is flat on the X-Z plane (ie in form Y = some constant), and the ball is vertically 10 units from the plane. That example yeilds the angle you gave, and the plen you gave, but the len value should be zero in that case, not 2. There is no possible plane & position corresponding to that angle and len and plen and velocity. If the value of len is corrected to 0, then both of our equations yield the same result: (8.66, 5.0, 0) : magnitude 10.

The math isn't pretty, and optimizing it may be quite difficult, but the basics are, I think, easier than the stuff you already have working. It'll take me a bit to come up with some equations/code, I'll edit this post later to add some, or add another post if you've replied.
edit: Bleh. I thought it was easier that the other stuff, but I haven't found an easy way to do it. I started algebriacally, found it too messy, tried a little calc, decided I didn't know what I was doing, and finally resorted to using trig to transform the problem to two dimensions, then to one dimension, and finally in one dimension I can solve it. I have a solution written up, but there's got to be an easier, simpler, faster way. And it's still written up as a mixture of english, equations, and code, nothing consistent or readable. Maybe you or someone else on this forum can come up with a simpler faster way, but this is what I have atm so:

Let sphere pos = P; edge endpoints = E1 & E2. Then this should work (in pseudocode):

I think it should work, anyway. Rush-typed from memory. I'm late to class!

Yeah, it looks about right, but he's looking for a continuous time solution, not a single-point-in-time solution. Or at least, his sphere-plane solution was using continuous time. Perhaps once he realizes how nasty continuous time solutions can be he'll switch over to a discrete-time method or some hybrid.

Thanks guys. I'll try that edge detection code.

continuous-time? discrete-time? I don't understand. I am looking for single point in time solution.

I messed up on the numbers sorry. After sitting there and coming up with some real numbers you are right. I just didn't see it until I did the math.

Discrete Time Physics vs Continuous Time Physics

In the simplest case of game programming, time is broken into fixed-size slices, movement equations are handled via Eulers method, and collisions are detected in a manner independant of velocities. In short, details smaller than the time slice size just aren't worried about. Precision is inversely proportional to the size of the timeslice (called "delta_t" in this example).

//typical discrete time aproximations
Vector old_position = position;
position += velocity * delta_t;
velocity += acceleration * delta_t;
Obj *obj = find_collision();
if (obj) {
  position = old_position;
  handle_collision(obj);
}

The function find_collision in the above sample might not even look at the objects velocity, merely position and shape. In some implementations, like the one above, when an object overlaps with another, it is simply moved to its previous position to prevent the overlap. In other implementations, the overlap may be allowed, permiting the bounce mechanics to seperate them on the next tick. Other implementations might use a limited continuous time solution in which the handling of collisions was exact so long as each object collided with no more than one other object per tick, or might search for a non-overlapping position, either by a binary search along the initial trajectory, by a random search along the new trajectory or old trajectory, or some other thing. In some implementations small fast moving objects accidentally pass through narrow objecst somtimes. Well, there's a lot of variations, most of which improve accuracy in some circumstances, but the key point is that precision of most of the mechanics is limited by a time slice size.

edit: The sort of math specific to discrete time stuff is the sort of math that might be covered in a class called "Numerical Methods". Solutions found (aproximated) by discrete time methods would usually not be acceptable in, say, a physics class.

In a continuous time simulation, on the other hand, precision (at least of the continuous time portions) is independant of the time slice size, and usually attempts to follow exact solutions rather than aproximations. Collision detection functions always use the velocities, and the resulting formulas can be extremely complicated if anything more than the simplest primitives are involved. Continuous time solutions are generally more complicated and more difficult to optimize. They tend to be slower for complex systems, but can be faster for simple systems.

Why did I think you were trying for continuous time physics? Your plane-sphere collision function works on continuous time at least for single-sphere-plane-pairs (ie you detected collisions not merely at a single point in time, but at any time within a specified range of time), and used an exact solution independant of time slice size. You didn't like putting the ball at the endpoint of the bounce in case it hit something else within the same time slice (which would have made it dependant upon tick length). Your collision checking loop restarted itself when a collision was found. The system you were looking at seemed fairly simple - only the ball had a velocity, and it was perfectly symmetric, and it only collided with one kind of shape. All things that are pretty much required in continuous time solutions, and, while sometimes used in discrete time simulations, not particularly widespread so far as I know.

Anyway, if you aren't looking for continous time solutions, disregard most of the code I've posted; the loop that made sure that collisions were handled in the physically correct order and sphere-line collision function were both intended for continuous-time calculations, and needlessly complicated and slow for the average game. Though, even in that code, gravity was aproximated discretely due to the excesive complexity of doing it exactly.

I think I understand better. I would rather have discrete.

EDIT:
Everthing seems to be working but a couple of problems. I attached an exe.

Assume 0 at bottom of screen

1. If I drop the ball at 100 when it hits the ground it should come back to 100, but it's going past 100 to approx 105. The next bounce ...

The velocity(delta) is increasing

2. I'm having trouble with the edges. Here is that pseudo code turned into code.

Didn't notice the edit for a while, thought the thread was dead.

Comments:
1. More code is always helps. Well, usually. I've already gotten into trouble making assumptions/guesses about the nature of code not posted here.
2. You have a "2.0 * (1.0 + tri->elasticity)". That should probably be either "2.0" or "(1.0 + tri->elasticity)", but not the product of the two, as the total is supposed to work out a number between 1.0 (totally inelastic) and 2.0 (perfectly elastic). However, that probably shouldn't cause your problem, as it should produce a very different result if tri->elasticity was anything more than 0.1 or so, and no problem if tri->elasticity is 0. If tri->elasticity was 0.01, that would produce the gradual speedup, though.
3. In the case of a collision with a corner, the normal vector is not equal to the normal vector of the triangle, but instead the normal vector of the line from the corner to the center of the ball. But, that shouldn't cause any of your problems, I think. Just in case, you might put in a check on a corner collision to discard it if the dot product of the balls velocity and the triangles normal vector is positive.
4. In your checkEdge(), try changing
double pdist = edir.dotProduct( toEdge2 );todouble pdist = edir.dotProduct( toEdge1 );

edit: hm... for the slow speedup, try this:

to this:

I know I kinda recommended the former as more accurate, but it's concievable it introduced some kind of subtle bias in favor of bouncing up higher or lower than the fall down... need to think about it for a bit.
edit2: also, post more code. At least a little bit before and after loop on findEarliestCollision(), and whatever calls checkEdge()

Since I was the last to post, I had to edit then bump.

I've attached all the code.

2. At the moment tri->elasticity is set to zero
I've been trying all sorts of ideas. I had one where:
dropped at Y
bounce 1 reached Y + X( some amount )
bounce 2 reached Y
bounce 3 reached Y + X( some amount )
bounce 4 reached Y

The problem lies in that the magnitude of vel when it hit should have the same magnitude of bounce but it is not.

3. changing
double pdist = edir.dotProduct( toEdge2 );
to
double pdist = edir.dotProduct( toEdge1 );
had not effect

I'll be gone for a few hours so anything you could help with would be great.
Thanks.

EDIT:
Saw your edit after you posted and the change didn't fix it. It was still too much.

Hmm, the program also fails to detect collision with the circle in the center, if you drop the ball below that circle and let the ball bounce up in to it ... which is weird, any you should probably look in to that.

Also, eventually the ball escaped through the arc'ed top corner of the playing field when I left it to just go for a while. It looked like it saw the collision -- there was a bit of red marking the spot where the ball flew through. Might want to look in to that.

From my observations, most of the detection problems do seem related to the handling of collision-with-point issues. You may want to store vertex normals (which would be nice for rendering it pretty later, anyway, right?).

I suppose that might work -- the hope being that if you discard this collision, you'll find (and react to) the collision with the 'more relevant' edge? Wouldn't look quite as good as reacting with some average vertex normal, I think, though.
edit2: Not sure about the collision with points issue, actually.

edit:

The thing is that you're using simple Euler integration for everything, and the way it works out is that the accel due to gravity is either too much or too little depending on when you apply it. So, what I'm saying specifically about your code is, you have this:

    ball.pos += ( ball.vel * time_remaining );
    ball.vel += ( gravity * time_remaining );

That will always bounce to high. This, on the other hand:

    ball.vel += ( gravity * time_remaining );
    ball.pos += ( ball.vel * time_remaining );

That will always bounce too low.
The 'correct' solution would probably look like this:

   ball.vel += .5 * ( gravity * time_remaining );
   ball.pos += ( ball.vel * time_remaining );
   ball.vel += .5 * ( gravity * time_remaining );

But to be on the save side you might want to weight it more like .6 to .4 ...

Changing the gravity stuff fixed the bouncing problem. The change is removing the "ball.vel += gravity * delta_t;" that happened per collision and changing the per-tick one from "ball.vel += gravity * time_remaining;" to "ball.vel += gravity * 1.0".

That causes a decrease in the accuracy of simulation, but it's well worth it to eliminate the higher bounces. They were happening because a subtle issue in when gravity was accounted for. If you want to keep the accuracy while still eliminating the higher bounces, the possibilities that occur to me include
A. force gravity updates at peaks of ballistic paths. This makes the loop that calls findEarliestCollision a little more complicated, but not insanely complicated.
B. switching the collision detection to looking at parabolic paths instead of linear. That would make checkCollision much more complicated, but would improve accuracy significantly.
Probably neither are worth it to you.

For the collisions with the center circle thingy, try these changes:
1. in checkCollision(), you return checkInside() if you think there's any chance of a planar collision. Instead, do an if (checkInside()) return true, and if there's not a planar collision continue on to the checkEdge calls.
2. If you do get a true value from checkEdge, and return it, t, never gets set, so findEarliestCollision disregards it because it fails the t > VZERO check. Setting to some arbitrary value like 0.01 will force it to work, though defeating the point of some of that logic.
3. I also added these three lines to checkCollision, otherwise some strange things happened when the ball rolled around on the circle in the middle.
if ( plen <= len ) return false;

The gravity works now. All I did was change

ball.vel += .5 * ( gravity * time_remaining );
ball.pos += ( ball.vel * time_remaining );
ball.vel += .5 * ( gravity * time_remaining );

I left in the

ball.vel += gravity * delta_t;

because it works better that way.

The top of the circle is where two planes come together, so it's the edge problem again.

I'll work on the edge problem. Thanks for the help.

When I do that on my version, and set the ball to bouncing vertically, it very gradually increases in bounce height, maybe 1% every 5 bounces. Perhaps I changed something else?

The edge problem is fixed in my version, with the changes described previously.

You're right. It does change slightly.

Which 'previously'?
Could you post your edge code?

Strange... now I don't get that anymore. I'm not sure what changed, but it now seems to work perfectly with that, whereas before it would keep bouncing faster with that. Maybe I screwed up or fixed something else and forgot about it.

Sure. The 'previously' was this:

code is this:

And the total code that I'm using atm is attached to this post

Also worth noting -- when you start working with non-elastic walls (or even just partially elastic walls), you'll want to add a line in calculate tick to make sure the ball gets 'pushed out' of walls that it is inside. This:

            ball.vel += ( tri->normal * 
                          tri->normal.dotProduct( -ball.vel ) * 
                          (1 + tri->elasticity) ); // after this line 
            ball.pos += ( tri->normal * .5 ); // put this line

should do the trick. Otherwise the ball will slowly merge whatever it's sliding on.

edit:
Also (this doesn't really matter, but) there's a bit of sloppiness left over from the code I gave for checking edges. In "Triangle::checkEdge", this:

   double distToLine = ( ball.pos - P_onE ).getLength();
   
   return ( distToLine < ball.radius );

has no particular reason not to be written as this:

   double distToLineSq = ( ball.pos - P_onE ).getSquaredLength();
   
   return ( distToLineSq < ball.radius * ball.radius );

(and that would be more consistent with the rest of the code, which was written to avoid sqrt.