Sign in to follow this  
noisecrime

Constrain a point within a cicle with sliding beahviour

Recommended Posts

noisecrime    817
Hi,

So I thought this was going to be simple, but apparently not. Its a 2D problem involving a simple point, with direction and speed, that must be contained within a (very) large circle. If in a single frame the point collides/intersects with the circumference of the circle then any 'distance' to travel remaining should 'slide' it around the circumference, with respect to its original direction.

Now finding collision point is easy and I thought the sliding bit would be too. When I first causally considered the problem I figured i'd use the collision normal (point on circumference of circle back to its center) to get a tangent and simply slide along that tangent. Of course as soon as I sat down to implement this I realised that using a tangent wasn't going to work since moving along it instantly (ignoring rounding errors) moves you out of the circle.

So now i'm a bit stuck. I'm was thinking that a solution might be found with 'chords' but not made any progress there.
I could resort to implementing point/line intersections and define the large circle from many small lines, but it just feels like there should be a nice mathematical function to solve this?

I'm contemplating perhaps using the tangent to calculate the final position (which would be outside of the circle) then use the line from the final position to the center of the circle to intersect with the circle circumfernece to move the point back within the circle. This although not accurate would be perfectly suitable for my needs as its not a simulation, just a mechanic to keep a game object within a circle and let it slide around.

However then I face the issue of how to calculate which direction to slide around the circle based on the initial direction the point is travelling in, which again i'm drawing a blank on.
Finally i'm wondering whether any solution will guarantee the point remains within the circle, and whether to take floating point errors into consideration?

I'd appreciate any ideas or solutions to this problem, though as is clear my Maths is not strong so would prefer code/psudeo code.

Thanks

Share this post


Link to post
Share on other sites
clb    2147
[quote name='noisecrime' timestamp='1313898449' post='4851796']
Its a 2D problem involving a simple point, with direction and speed, that must be contained within a (very) large circle. If in a single frame the point collides/intersects with the circumference of the circle then any 'distance' to travel remaining should 'slide' it around the circumference, with respect to its original direction.

I'm contemplating perhaps using the tangent to calculate the final position (which would be outside of the circle) then use the line from the final position to the center of the circle to intersect with the circle circumfernece to move the point back within the circle. This although not accurate would be perfectly suitable for my needs as its not a simulation, just a mechanic to keep a game object within a circle and let it slide around.
[/quote]

I think you can use this method and solve exactly the distance to travel. If we denote by A the point before movement, B the point after movement (outside the circle), O the circle with position P and radius R, then

1. Adapt [url="http://mathworld.wolfram.com/Circle-LineIntersection.html%20"]this[/url] to compute the intersection of the line segment (A,B) and the circle O. Denote the intersection point by C.
2. Determine whether you need to go clockwise or counterclockwise along the circle: Take the perp-dot product (e.g. [url="http://mathworld.wolfram.com/PerpDotProduct.html"]here[/url], but don't invoke sin(), but use the method of replacing (x,y) with (-y, x) to generate a perpendicular vector to dot against) between the vectors normalized(B-C) and normalized(C-O) and depending on the sign of the result, you go CW or CCW.
3. Compute d=|C-B| to get the distance you need to travel along the circle perimeter. Generate a standard 2D rotation matrix M to rotate about origin. Use as the rotation angle the angle +/- d/R, depending on the sign of the perp-dot product.
4. Now the final point that has the sliding applied is M * (C-P)+P.

Share this post


Link to post
Share on other sites
noisecrime    817
Thanks for that.

I had considered rotating the point around the circle, but felt it was a bit of a roundabout method and guess I wanted to avoid matrices, plus I still had the issue of knowing which direction to rotate. However it sounds like a good suggestion and your method is clearly explained, so i'll give it a go.

After carefully reading your description everything looks clear except the specifics of the perp-dot product. Do you mean I should use the perpendicular vector of (B-C) and dot that with (C-O)? I think thats right, I don't generate a perp vector for both or anything?

Cheers

Share this post


Link to post
Share on other sites
clb    2147
If you have two vectors X=(x,y) and A=(a,b). Then the normal dot-product is of course X (dot) A = x*a + y*b. The perp-dot product of X and Y is only a small modification to this: it is defined to be the dot product of Y with a vector perpendicular to X. In 2D, if you have vector X=(x,y), you can easily generate a vector perpendicular to this by flipping the components and reversing the sign: X' = (-y, x). (Note that this corresponds to rotating the vector 90 degrees CCW). So X (perp-dot) A = X' (dot) A = -y * a + x * b.

The effect of this in this context is to see if the vector A is oriented "to the right" or "to the left" of the original vector X (the same when you dot a direction vector against a plane normal to see if it is pointing towards the positive or the negative side of the plane).

Looking again, I think I reversed the arguments wrong way around. Compute the perp-dot in the order (C-O) (perp-dot) (B-C), so that you'll find a vector perpendicular to (C-O) and dot it with (B-C).

Share this post


Link to post
Share on other sites
japro    887
Are you searching for analytical solution or a way to simulate it?

The equations of motion for constrained motion can often be obtained using the Lagrangian formalism:

1. Choose a coordinate system in which the constraints are trivially fulfilled, in this case polar coordinates with fixed radius, angle [i]phi[/i] and angular velocity [i]omega[/i].
2. Write potential and kinetic energy down in that coordinate system:

E = 0.5*m*(R^2 * omega^2)
V = -m*g*R*cos(phi)

3. Write the Lagrangian as L = V - E
4. obtain the equation of motion from:

d/dt (dL/domega ) + dL/dphi = 0

in this case:

m*R^2*domega/dt - m*g*R*sin(phi) = 0
=>
d^2phi/dt^2 = g/R*sin(phi)

Which is the differential equation of a pendulum...

Share this post


Link to post
Share on other sites
noisecrime    817
[quote name='japro' timestamp='1313922520' post='4851859']
Are you searching for analytical solution or a way to simulate it?

The equations of motion for constrained motion can often be obtained using the Lagrangian formalism:
[/quote]

Thanks, unfortunately you lost me at Lagrangian :)

Share this post


Link to post
Share on other sites
noisecrime    817
[quote name='clb' timestamp='1313910855' post='4851822']
I think you can use this method and solve exactly the distance to travel. If we denote by A the point before movement, B the point after movement (outside the circle), O the circle with position P and radius R, then
[/quote]

So i've implemented this method and it works on the whole, but there is an issue.

Whenever the (normalised) direction of the point when it intersects the circles circumference, matches that of the intersection point normal ( i.e normalised(origin - intersection point)) the point gets stuck, oscillating slightly backwards and forwardwards as the slide angle flips between signs. E.g. imagine starting the point at the circles origin (which happens to be 0,0,0) and it moves directly right (i.e. dx,dy = (1,0), then when it intersects with the circumference the normal on the circle will be (-1,0). Same case for say a direction of ( 0.7,0.7) when it hits the circle at 45degrees it oscillates and I guess for any other time when direction will equal the collision point normal.

Another example say you move (1,0) but start off below the circles origin, when you colllide with the circumference the point will slide upwards. However if you started just above the origin you would slide downwards. Obviously at some point these different slide directions meet and its at this point where it oscillates.

I'm a bit stumped as to how to fix it, as the behaviour above is with the sliding is what i want, but clearly there is a point where the slide becomes zero, or in this case due to rounding/precision errors the angle to move bounces between signs.

So am I right thinking this is expected behaviour? If so any bright ideas how to avoid the point getting stuck?

I also found that either due to precision errors, or perhaps my some what 'lazy' calculation of the intersect point using purely distance (magnitude) checks meant that it was still quite easy to escape the circle. The simple fix for this is to normalise the final position with respect to the circles origin and then multiply it by the radius - somesmallvalue, ensuring the final point is always within the circle.

I'll post the code i've got below, its a bit mess/inefficient as i'm getting 2D vector input (x,y), but doing all the calculations in 3D and i've not yet rationalised it. So I keep having to zero out y which contains the 3D objects height to avoid it being used in calculations etc.

[code]
void CollisionMovement( Vector3 input, float speed)
{
float circleRadius = 2000.0f;
Vector3 A = transform.position;
Vector3 B = transform.position + new Vector3(input.x, 0, input.y) * speed;

// zero out Y (height not required in 2D)
A.y = 0;
B.y = 0;

// Distance to Collision.
float d = B.magnitude - circleRadius;

if (d < 0)
{
B.y = transform.position.y;
transform.position = B;
return;
}

// Collision point
Vector3 C = A + new Vector3(input.x, 0, input.y) * (speed-d);
Vector3 COperp = new Vector3(-C.z, 0, C.x);
Vector3 BC = B-C;
COperp.Normalize();
BC.Normalize();

float direction = Vector3.Dot( COperp, BC);
float angle = d/circleRadius;

if (direction < 0) angle = -angle;

// Rotate to final point
Vector3 output = new Vector3(C.x * Mathf.Cos(angle) - C.z* Mathf.Sin(angle), 0, C.z * Mathf.Cos(angle) + C.x* Mathf.Sin(angle) );

// Fix Collision point to just inside circle
output = output.normalized*(circleRadius-1);
// Add height back in
output.y = transform.position.y;

transform.position = output;
}[/code]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this