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.
1 | // Vector is a class with 3 double vars and math functions to manipulate. |
2 | double Triangle::distance( Vector &p ) |
3 | { |
4 | // normal is the triangles normal vector |
5 | return this->normal.dotProduct( p - this->mid ) / this->normal.getLength(); |
6 | } |
7 | |
8 | double Triangle::angleBetween( Vector &p ) |
9 | { |
10 | return asin( ( this->normal.dotProduct( p ) / ( this->normal.getLength() * p.getLength() ) ) ); |
11 | } |
12 | |
13 | // p is ball pos |
14 | // v is ball vel |
15 | // newball is the new position if collision |
16 | // radius is radius of the ball |
17 | bool Triangle::isPossible( Vector &p, Vector &v, Vector &newball, double radius ) |
18 | { |
19 | static double plen; |
20 | static double len; |
21 | static Vector vhat; |
22 | static Vector pv; |
23 | |
24 | // current position plus velocity |
25 | // this will be the new position if there wasn't a hit |
26 | pv = p + v; |
27 | |
28 | // unit of velocity |
29 | vhat = v.normalize(); |
30 | |
31 | // VZERO 1e-9 |
32 | if ( fabs( this->normal.dotProduct( vhat ) ) <= VZERO ) |
33 | { |
34 | return false; |
35 | } |
36 | |
37 | // length of ball from plane |
38 | plen = this->distance( p ); |
39 | |
40 | // length of new position from plane |
41 | len = this->distance( pv ); |
42 | |
43 | if ( plen >= radius && len < radius ) |
44 | { |
45 | newball = pv - ( vhat * fabs( ( radius - len ) / sin( this->angleBetween( -v ) ) ) ); |
46 | |
47 | return true; |
48 | } |
49 | |
50 | return false; |
51 | } |
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:
This code gives me the correct position of where the ball will hit the plane. And the new velocity is calculated as such.
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.
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.
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?
Shouldn't the new ball position just be:
newball = pv + this->normal * 2.0 * (radius - len);
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 )
Yes, 'isPossible' deals with infinite planes.
Here is the code for the collision of the triangle.
1 | bool Triangle::collision( Vector &p, Vector &v, Vector &newball, double radius ) |
2 | { |
3 | static int vv[ 3 ][ 2 ] = |
4 | { |
5 | { 1, 2 }, |
6 | { 2, 0 }, |
7 | { 0, 1 } |
8 | }; |
9 | static Vector v1; |
10 | static Vector v2; |
11 | |
12 | // does the ball hit the triangle's plane |
13 | if ( this->isPossible( p, v, newball, radius ) ) |
14 | { |
15 | // this tells if the spot it hit is outside the triangle |
16 | for ( int i = 0; i < 3; i++ ) |
17 | { |
18 | v1 = this->vector[ vv[ i ][ 0 ] ] - newball; |
19 | v2 = this->vector[ vv[ i ][ 1 ] ] - newball; |
20 | |
21 | if ( this->normal.dotProduct( v1.crossProduct( v2 ) ) < -VZERO ) |
22 | { |
23 | return false; |
24 | } |
25 | } |
26 | |
27 | return true; |
28 | } |
29 | |
30 | return false; |
31 | } |
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.
I still think my formula is superior, as it is faster and uses no trig
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.
1 | void Ball::_move() |
2 | { |
3 | int i = 0; |
4 | bool hit = false; |
5 | Vector newPos; |
6 | |
7 | for ( std::list<Triangle>::iterator it = triList.tlist.begin(); it != triList.tlist.end(); it++ ) |
8 | { |
9 | Triangle *t = &(*it); |
10 | |
11 | if ( key[ KEY_ESC ] ) return; |
12 | |
13 | hit = t->collision( this->pos, |
14 | this->vel, |
15 | newPos, |
16 | this->radius ); |
17 | |
18 | if ( hit ) |
19 | { |
20 | |
21 | double d = ( this->vel.getLength() - |
22 | ( this->pos - newPos ).getLength() ); |
23 | |
24 | this->pos = newPos; |
25 | |
26 | if ( d <= VZERO ) |
27 | { |
28 | this->vel.zero(); |
29 | } |
30 | else |
31 | { |
32 | this->vel = ( ( t->normal * |
33 | t->normal.dotProduct( -this->vel ) * |
34 | 2.0 ) + |
35 | this->vel ).normalize() * d; |
36 | this->_move(); |
37 | } |
38 | |
39 | return; |
40 | } |
41 | |
42 | i++; |
43 | } |
44 | |
45 | this->pos += this->vel; |
46 | } |
You need to add a second check, to see if the ball hits any of the edges.
That's what I'm not sure about.
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.
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.
_move is called recursively until the magnitude of velocity is zero.
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:
1 | //returns true on a collision |
2 | //sets t to time until collision |
3 | //sets normal to the normal vector of the collision (which is a unit vector) |
4 | bool check_collision(const Ball &b, const Triangle &t, Vector &normal, double &time); |
5 | |
6 | bool find_earliest_collision(const Ball &b, const std::list<Triangle> triangles, Vector &normal, double &time, std::list<Triangle>::iterator which_tri) { |
7 | time = 9999999;//number bigger than 1 (the maximum time), don't care beyond that |
8 | double current_t; |
9 | Vector current_normal; |
10 | for (it = triangles.begin(); it != triangles.end(); it++) { |
11 | Vector normal; |
12 | double delta_t; |
13 | if (check_collision(b, *it, current_normal, current_t)) { |
14 | if (current_t < time && current_t > VZERO) {//edit fixed var name |
15 | time = current_t; |
16 | normal = current_normal; |
17 | which_tri = it; |
18 | } |
19 | } |
20 | } |
21 | if (time <= 1) return true; |
22 | else return false;//edit: added else condition |
23 | } |
24 | |
25 | void calculate_tick(Ball &b, std::list<Triangle> triangles) {//single time unit |
26 | double time_remaining = 1; |
27 | double delta_t; |
28 | Vector Normal; |
29 | std::list<Triangle>::iterator it; |
30 | while (find_earliest_collision(b, *it, normal, delta_t, it)) { |
31 | if (delta_t <= time_remaining) { |
32 | b.pos += b.vel * delta_t; |
33 | b.vel += gravity * delta_t; |
34 | b.vel += normal * dot_product(b.vel, normal) * (1 + it->elasticity);//made up elasticity as a use for the triangle iterator |
35 | time_remaining -= delta_t; |
36 | //edit: removed line that accidentally cut&pasted in from another version of this function |
37 | } |
38 | } |
39 | b.pos += time_remaining * b.vel; |
40 | b.vel += time_remaining * gravity; |
41 | } |
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.
That's what I'm not sure about.
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.
Minor stylistic points: what you called "velocity" in your code is what I would call a "delta" or "movement"
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.
1 | //Let's try some numbers: |
2 | v = ( 17.32, 10.0, 0.0 ): v.len = 20 |
3 | vhat = ( 0.866, 0.5, 0 ) : vhat.len = 1 |
4 | angle = 30 // angle between |
5 | radius = 5 |
6 | len = 2 |
7 | plen = 22 |
8 | |
9 | float tick_fraction = 1 - (len-radius) / (plen-len); |
10 | //float tick_fraction = 1 - (2-5) / (22-2) = 1.15 |
11 | |
12 | // newball = p + tick_fraction * v; |
13 | vector v1 = tick_fraction * v; |
14 | // v1 = ( 1.15 * v ) = ( 19.92, 11.5, 0.0 ) : .len = 23.00 |
15 | newball = p + v1; (overshot) |
16 | |
17 | |
18 | double d = ( radius - len ) / sin( this->angleBetween( -v ) ) |
19 | // = ( 5 - 2 ) / ( .5 ) = 6 |
20 | |
21 | vector v1 = v - ( vhat * fabs( d ) ) |
22 | // = ( 17.32, 10.00, 0.0 ) - ( 0.866, 0.5, 0 ) * 6 |
23 | // = ( 12.124, 7.0, 0.0 ): .len = 14 |
24 | newball = p + v1; |
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.
Ok, I really appreciate your help. You gave me something to think about with that shortest time idea.
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.
Velocity [en.wikipedia.org] 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.
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.
I don't want to upset you but I still think you have the wrong formula for P2.
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.
And I'm unsure about the calculations. I don't know how to check for a collision against an edge.
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:
1 | start with: |
2 | |
3 | line: 2 endpoints, E1 and E2 |
4 | ball path: position (B) and velocity (V) and radius (R) |
5 | E1,E2,B, and V are 3d vectors, R is a scalar |
6 | |
7 | 2 dimensionalify it: (is that a word?) |
8 | |
9 | pick an axi to eliminate... say, the Z axi |
10 | you need to rotate the line segment so that it falls on to the Z axi |
11 | (assuming that it doesn't already - you should check that first) |
12 | in order to simplify, lets subtract E1 from B now, so that ball position is take the line delta D = E2 - E1 |
13 | relative to it |
14 | cross product that with the Z axi to find an axi perp. to both |
15 | rotate everything around the resulting cross product by the angle between the Z axi and the line delta |
16 | now the line delta should align with the Z axi |
17 | so, you can now forget everything about the Z axi, and treat the problem as 2d |
18 | the endpoints are now identical on the X-Y plane |
19 | your velocity, projected into 2d, is now slower, etc |
20 | (make sure your velocity is still non-zero, otherwise no collision is possible) |
21 | |
22 | so now you have, in addition to the old stuff: |
23 | |
24 | D = E2 - E1 |
25 | E' = (0,0) |
26 | rotation_axi = cross_product(D, Z_axi) |
27 | rotation_amount = -angle_between(D, Z_axi) |
28 | //vector3 rotate3d( vector3 vect, vector3 axi, double radians ); |
29 | //vector::vector2(const vector3 &vect) : x(vect.x), y(vect.y) {} |
30 | B' = vector2(rotate(B - E1, rotation_axi, rotation_amount)); |
31 | V' = vector2(rotate(V, rotation_axi, rotation_amount)); |
32 | Evertying with a ' in the name is a 2d vector. |
33 | |
34 | 1 dimensionalify it: (is that a word?) |
35 | |
36 | rotate your coordinate system until the balls motion is on the X axi, straight right |
37 | |
38 | so no you have: |
39 | |
40 | //vector2 rotate2d( vector2 vect, double radians ); |
41 | B'' = rotate2d( B', -atan2(V'.y, V'.x)); |
42 | V'' = magnitude(V') (a scalar now) |
43 | |
44 | solve for collision: |
45 | |
46 | at the collision time, the distance from the ball to origin (what used to be the infinite line) is equal to the balls radius. |
47 | so... x^2 + y^2 = r^2... y is B''.y, r is R, solve for x |
48 | x = +/- sqrt(R*r - B''.y * B''.y); |
49 | if the quantity in the sqrt is negative, no collision is possible |
50 | otherwise, use only the positive square root (or 0) for the X coordinate of the ball at the time of collision |
51 | edit: no wait, use the negative square root, not the positive... er... I think... |
52 | X'' = -sqrt(R*r - B''.y * B''.y); |
53 | now you need to make this useful, not just an X coordinate in some bizarre transformed space. applying the reverse transformations doesn't appeal to me much. so... find how long it took for the ball to travel to that point, by dividin the transformed distance by the transformed speed |
54 | |
55 | now you have: |
56 | |
57 | T = (X'' - B''.x) / V'' (T is a scalar time) |
58 | |
59 | back to working with untransformed coordinates: |
60 | |
61 | E = either E1 or E2, don't care which |
62 | remember that D = E2 - E1 |
63 | remember that B is the untransformed original position of the Ball |
64 | and V is the untransformed original velocity of the Ball |
65 | find an "origin" for the line, O = E - D * (E . D) |
66 | the center of the Ball at collision time, C = B + V * T |
67 | the point of intersection I = O + D * (C . D) |
68 | and it falls onto the segment if and only if |
69 | (C . D) falls between (E1 . D) and (E2 . D) |
70 | the normal vector of the collision N = (B - I) / R |
71 | |
72 | my implimentation of rotate3d: |
73 | Vector3 rotate ( Vector3 vector, Vector3 axi, Angle angle ) { |
74 | if (angle == 0) return vector; |
75 | |
76 | double tmpd = magnitude_sqr(axi); |
77 | if (tmpd != 1) axi /= std::sqrt(tmpd); |
78 | //axi = unit_vector(axi); |
79 | double co = dot_product(vector, axi); |
80 | vector -= co * axi; |
81 | double m = magnitude(vector); |
82 | double zero = dot_product(vector, axi); |
83 | Vector3 y = cross_product ( vector, axi ); |
84 | Vector3 n = vector * cos(angle) + y * sin(angle); |
85 | vector = n + co * axi; |
86 | return vector; |
87 | } |
88 | |
89 | |
90 | |
91 | |
92 | optimization: a semi-fast discard method for maybe half the lines and verticies |
93 | (not good optimization, but it's a start) |
94 | |
95 | for the line segments: you can't hit a line segment from the side of it that the |
96 | triangle is on. so... |
97 | take the cross product of the normal vector and the line vector to get a |
98 | vector perp to both. point outward from the triangle edge |
99 | subtract one of the line endpoints from the ball center to get a relative position |
100 | take the dot product of the relative position and the outward vector |
101 | if the result is negative, no collision is possible |
102 | without passing through the triangle first |
103 | and if a collision with that edge is possible, then a collision with the opposite vertex |
104 | is not possible |
And I'm unsure about the calculations. I don't know how to check for a collision against an edge.
Let sphere pos = P; edge endpoints = E1 & E2. Then this should work (in pseudocode):
1 | bool checkCol(P, E1, E2) { |
2 | toedge1 = P-E1; |
3 | toedge2 = P-E2; |
4 | if (dot_product(toedge1, toedge1) < radius*radius || dot_product(toedge2, toedge2) < radius*radius) { |
5 | return true; // sphere collides with edge endpoints |
6 | } |
7 | edgevec = E2-E1; |
8 | edgelen = mag(edgevec); |
9 | edgedir = edgevec / edgelen; |
10 | proj_dist = dot_product(edgedir, toedge2); // project to_sphere along edge |
11 | if (proj_dist < 0) { |
12 | return false; |
13 | } |
14 | if (proj_dist > edgelen) { |
15 | return false; |
16 | } |
17 | P_onE = E1 + proj_dist * edgedir; |
18 | distToLine = mag(P-P_onE); |
19 | if (distToLine < radius) |
20 | return true; |
21 | else |
22 | return false; |
23 | } |
I think it should work, anyway. Rush-typed from memory. I'm late to class!
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.
but he's looking for a continuous time solution, not a single-point-in-time solution.
continuous-time? discrete-time? I don't understand. I am looking for single point in time solution.
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.
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.
1 | P0 = position at time 0 |
2 | P1 = position at time 1 if collision is ignored |
3 | P2 = position at time T, when the collision occurs (0 <= T < 1) |
4 | P3 = position at time 1, with collision taken into account |
5 | |
6 | With these numbers it will cross the horizontal triangle plane at ( 0, 0, 0 ) |
7 | |
8 | v = ( -17.32, -10.0, 0.0 ): v.len = 20 |
9 | vhat = ( -0.866, -0.5, 0.0 ): vhat.len = 1 |
10 | angle = 30 // angle between |
11 | |
12 | P0 = ( 20.78, 12.0, 0 ) // distance of 12.0 (plen) |
13 | P1 = ( 3.46, 2.0, 0 } // distance of 2.0 (len) |
14 | P2 = ( 8.656, 5.0, 0 ) // distance of 5 (radius) |
15 | P3 = ( 3.46, 8.0, 0 ) |
16 | |
17 | float tick_fraction = 1-(radius-len)/(plen-len) |
18 | = 1-(5-2)/(12-2) = 0.7 |
19 | |
20 | newball = p + tick_fraction * v |
21 | = ( 20.78, 12.0, 0 ) + (0.7)*( -17.32, -10.0, 0.0 ) |
22 | = ( 8.656, 5.0, 0 ) |
23 | |
24 | |
25 | newlength = ( ( radius - len ) / sin( this->angleBetween( -v ) ) ); |
26 | = ( ( 5 - 2 ) / .5 = 6 |
27 | |
28 | newball = p + v - ( vhat * fabs( newlength ) ); |
29 | = ( 20.78, 12.0, 0 ) + ( -17.32, -10.0, 0.0 ) - ( ( -0.866, -0.5, 0.0 ) * 6 ) |
30 | = ( 8.656, 5.0, 0 ) |
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
1 | while( ( tri = this->findEarliestCollision( ball, delta_t ) ) ) |
2 | { |
3 | if ( key[ KEY_ESC ] ) break; |
4 | |
5 | if ( delta_t <= time_remaining ) |
6 | { |
7 | ball.pos += ball.vel * delta_t; |
8 | ball.vel += gravity * delta_t; |
9 | |
10 | ball.vel += ( tri->normal * |
11 | tri->normal.dotProduct( -ball.vel ) * |
12 | 2.0 * |
13 | ( 1.0 + tri->elasticity ) ); |
14 | |
15 | time_remaining -= delta_t; |
16 | |
17 | tsel = tri; |
18 | hit = true; |
19 | } |
20 | } |
2. I'm having trouble with the edges. Here is that pseudo code turned into code.
1 | bool Triangle::checkEdge( const Ball &ball, const Vector &edge1, const Vector edge2 ) |
2 | { |
3 | Vector toEdge1 = ball.pos - edge1; |
4 | Vector toEdge2 = ball.pos - edge2; |
5 | |
6 | if ( toEdge1.getSquaredLength() < ( ball.radius * ball.radius ) || |
7 | toEdge2.getSquaredLength() < ( ball.radius * ball.radius ) ) |
8 | { |
9 | return true; |
10 | } |
11 | |
12 | Vector edge = edge2 - edge1; |
13 | double elen = edge.getLength(); |
14 | Vector edir = edge / elen; |
15 | |
16 | |
17 | double pdist = edir.dotProduct( toEdge2 ); |
18 | |
19 | if ( pdist < 0.0 || |
20 | pdist > elen ) |
21 | { |
22 | return false; |
23 | } |
24 | |
25 | Vector P_onE = edge1 + edir * pdist; |
26 | double distToLine = ( ball.pos - P_onE ).getLength(); |
27 | |
28 | return ( distToLine < ball.radius ); |
29 | } |
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:
1 | while( ( tri = this->findEarliestCollision( ball, delta_t ) ) ) |
2 | { |
3 | if ( key[ KEY_ESC ] ) break; |
4 | |
5 | if ( delta_t <= time_remaining ) |
6 | { |
7 | ball.pos += ball.vel * delta_t; |
8 | ball.vel += gravity * delta_t; |
9 | |
10 | ball.vel += ( tri->normal * |
11 | tri->normal.dotProduct( -ball.vel ) * |
12 | 2.0 * |
13 | ( 1.0 + tri->elasticity ) ); |
14 | |
15 | time_remaining -= delta_t; |
16 | |
17 | tsel = tri; |
18 | hit = true; |
19 | } |
20 | } |
to this:
1 | while( ( tri = this->findEarliestCollision( ball, delta_t ) ) ) |
2 | { |
3 | if ( key[ KEY_ESC ] ) break; |
4 | |
5 | if ( delta_t <= time_remaining ) |
6 | { |
7 | ball.pos += ball.vel * delta_t; |
8 | |
9 | ball.vel += ( tri->normal * |
10 | tri->normal.dotProduct( -ball.vel ) * |
11 | 2.0 * |
12 | ( 1.0 + tri->elasticity ) ); |
13 | |
14 | time_remaining -= delta_t; |
15 | |
16 | tsel = tri; |
17 | hit = true; |
18 | } |
19 | } |
20 | ball.vel += gravity * whatever;//whatever = initial value of delta_t, probably 1.0 |
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.
1. More code is always helps.
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?).
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.
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 problem lies in that the magnitude of vel when it hit should have the same magnitude of bounce but it is not.
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.
the changes described previously
Which 'previously'?
Could you post your edge code?
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?
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.
Which 'previously'?
Could you post your edge code?
Sure. The 'previously' was this:
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;
code is this:
1 | bool Triangle::checkCollision( const Ball &ball, double &t ) |
2 | { |
3 | static Ball newBall; |
4 | static double plen = 0.0; |
5 | static double len = 0.0; |
6 | |
7 | t = 0.0; |
8 | |
9 | plen = this->distance( ball.pos ); |
10 | len = this->distance( ball.pos + ball.vel ); |
11 | |
12 | if ( plen <= len ) return false; |
13 | // if ( len > ball.radius) return false; |
14 | // if ( plen < 0 ) return false; |
15 | |
16 | if ( plen >= ball.radius && len < ball.radius ) |
17 | { |
18 | t = 1.0 - ( ( ball.radius - len ) / ( plen - len ) ); |
19 | |
20 | newBall.pos = ball.pos + ball.vel * t; |
21 | newBall.vel = ball.vel; |
22 | newBall.radius = ball.radius; |
23 | |
24 | if (this->checkInside( newBall )) return true; |
25 | } |
26 | |
27 | t = 0.01; |
28 | return |
29 | this->checkEdge( ball, this->vector[ 2 ], this->vector[ 1 ] ) || |
30 | this->checkEdge( ball, this->vector[ 1 ], this->vector[ 0 ] ) || |
31 | this->checkEdge( ball, this->vector[ 0 ], this->vector[ 2 ] ); |
32 | } |
33 | Triangle *TList::findEarliestCollision( const Ball &ball, double &delta_t ) |
34 | { |
35 | Triangle *temp = NULL; |
36 | std::list<Triangle>::iterator it; |
37 | double currentT = 0.0; |
38 | |
39 | for ( it = this->tlist.begin(); it != this->tlist.end(); it++ ) |
40 | { |
41 | if ( (*it).checkCollision( ball, currentT ) ) |
42 | { |
43 | if ( currentT < delta_t && |
44 | currentT > VZERO ) |
45 | { |
46 | delta_t = currentT; |
47 | temp = &(*it); |
48 | } |
49 | } |
50 | } |
51 | |
52 | return temp; |
53 | } |
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.