How to Move a Model and Generate Its Collision Shape at the Same Time

How to move a model and generate its collision shape at the same time?

Hope this trick definitely helps. This physics lasts forever. ))

Sample Image

struct ARViewContainer: UIViewRepresentable {

let ball = ModelEntity(mesh: .generateSphere(radius: 0.5))
let anchor = AnchorEntity()

func makeUIView(context: Context) -> ARView {

let arView = ARView(frame: .zero)

ball.physicsBody = .init()
ball.physicsBody?.massProperties.mass = 0

ball.physicsMotion = .init()
ball.physicsMotion?.linearVelocity.x = 1.0
ball.physicsMotion?.angularVelocity.z = -.pi

ball.position.x = -4.0
ball.generateCollisionShapes(recursive: true)
anchor.addChild(ball)

anchor.position.z = -3.0
arView.scene.addAnchor(anchor)
return arView
}

func updateUIView(_ uiView: ARView, context: Context) { }
}

Collision Management in a Simulation with Discrete Motion

Two researchers, Ahmed Al Rowaei and Arnold Buss, published a paper in 2010 investigating the impact that using discrete time steps has on model accuracy/fidelity when the real-world system is event-based. There was also some follow-on work in 2011 with their colleague Stephen Lieberman. A major finding was that if you use time stepped models, order of execution matters and can cause the models to deviate from real-world behaviors in significant ways. Time-stepped models generally require you to introduce tie-breaking logic which doesn't exist in the real system. Logic that is needed for the model but doesn't exist in reality is called a "modeling artifact," and can lead to increased model complexity and inaccuracies. Systematic collision resolution schemes can lead to systematic biases.

Their recommendation was to build models based on continuous time. Events are scheduled using the actual (continuous) event times, which determine the order of event execution as in the real-world system. This occasionally (but rarely) requires priority tie breaking based on event type, so that (for example) departure events occur before arrival events if both were to occur at the exact same time.

If you insist on sticking with time-stepped models, a different strategy is to use two or more passes at each time step. The first pass lays out the desired state transitions and identifies potential conflicts, the last pass applies the actual transitions after conflicts have been resolved. The resolution process might be do-able in the initial setup pass, or may require additional passes if it's sufficiently complex.

Why all objects are sliding? Concave polygon collision shape in godot 3

If you don't want the trees to move. Ever. Make them StaticBody.

If you want them to be affected by gravity and allow other things to push them, then use RigidBody.

Since you are using RigidBody, I presume that is what you want. Which leads to the question: How to make a RigidBody that does not move until something pushes it? Add it sleeping. The RigidBody has a sleeping boolean property that you can set to true to disable its simulation.


By the way, you can also change the gravity_scale of the RigidBody. Which means you could add them with gravity_scale set to 0, and on the "body_entered" signal, set gravity_scale to 1.

And while we are at it, if using the "body_entered" signal is viable, another alternative to set the mode of the RigidBody to static, and change it o rigid on the "body_entered" signal. By the way, you would need to change mode using set_deferred or call_deferred because you cannot change mode while Godot is doing physics resolution (which is also when Godot sends the "body_entered" signal).

And yes, I know the RigidBody modes are confusing.

Transfer of energy from one object to another in collision (in pymunk/chipmunk)

Maybe I missed something in your code (I only have command line python here so I cant run your script), but I cant recreate your problem.

Here is a short code I tried which seems to work as you want:

import pymunk

s = pymunk.Space()

b1 = pymunk.Body(1,10)
b1.position = 0,0

b2 = pymunk.Body(1,10)
b2.position = 0,10

c1 = pymunk.Circle(b1, 1)
c1.elasticity = 1.0
c2 = pymunk.Circle(b2, 1)
c2.elasticity = 1.0

j1 = pymunk.constraint.PivotJoint(s.static_body, b1, (0,0),(0,0))
j1.max_force = 4.5
j1.max_bias = 0

j2 = pymunk.constraint.PivotJoint(s.static_body, b2, (0,0),(0,0))
j2.max_force = 4.5
j2.max_bias = 0

j3 = pymunk.constraint.SimpleMotor(s.static_body,b1,0)
j3.max_force = 5000000
j4 = pymunk.constraint.SimpleMotor(s.static_body,b2,0)
j4.max_force = 5000000

s.add(b1,b2,c1,c2,j1,j2,j3,j4)

b1.apply_impulse_at_world_point((0,30),(0,0))

for x in range(25):
s.step(0.02)
print(b1.position, b2.position)

This prints out this on my screen (so b1 stopped and all the movement is transferred to b2):

Vec2d(0.0, 0.6) Vec2d(0.0, 10.0)
Vec2d(0.0, 1.1982) Vec2d(0.0, 10.0)
Vec2d(0.0, 1.7946) Vec2d(0.0, 10.0)
Vec2d(0.0, 2.3891999999999998) Vec2d(0.0, 10.0)
Vec2d(0.0, 2.9819999999999998) Vec2d(0.0, 10.0)
Vec2d(0.0, 3.573) Vec2d(0.0, 10.0)
Vec2d(0.0, 4.1622) Vec2d(0.0, 10.0)
Vec2d(0.0, 4.7496) Vec2d(0.0, 10.0)
Vec2d(0.0, 5.3352) Vec2d(0.0, 10.0)
Vec2d(0.0, 5.9190000000000005) Vec2d(0.0, 10.0)
Vec2d(0.0, 6.501) Vec2d(0.0, 10.0)
Vec2d(0.0, 7.081200000000001) Vec2d(0.0, 10.0)
Vec2d(0.0, 7.659600000000001) Vec2d(0.0, 10.0)
Vec2d(0.0, 8.2362) Vec2d(0.0, 10.0)
Vec2d(0.0, 8.228112001309862) Vec2d(0.0, 10.584682725252637)
Vec2d(0.0, 8.228112001309862) Vec2d(0.0, 11.159477451815137)
Vec2d(0.0, 8.228112001309862) Vec2d(0.0, 11.732472178377638)
Vec2d(0.0, 8.228112001309862) Vec2d(0.0, 12.303666904940137)
Vec2d(0.0, 8.228112001309862) Vec2d(0.0, 12.873061631502637)
Vec2d(0.0, 8.228112001309862) Vec2d(0.0, 13.440656358065137)

Collision detection between 2 linearly moving objects in WGS84

[Edit5] Complete reedit in case you need old sources see the revision history

As Nico Schertler pointed out checking for line to line intersection is insanity as the probability of intersecting 2 trajectories at same position and time is almost none (even when including round-off precision overlaps). Instead you should find place on each trajectory that is close enough (to collide) and both objects are there at relatively same time. Another problem is that your trajectories are not linear at all. Yes they can appear linear for shor times in booth WGS84 and Cartesian but with increasing time the trajectory bends around Earth. Also your input values units for speed are making this a bit harder so let me recapitulate normalized values I will be dealing with from now:

  1. Input

    consists of two objects. For each is known its actual position (in WGS84 [rad]) and actual speeds [m/s] but not in Cartesian space but WGS84 local axises instead. For example something like this:

    const double kmh=1.0/3.6;
    const double deg=M_PI/180.0;
    const double rad=180.0/M_PI;
    // lon lat alt
    double pos0[3]={ 23.000000*deg, 48.000000*deg,2500.000000 };
    double pos1[3]={ 23.000000*deg, 35.000000*deg,2500.000000 };
    double vel0[3]={ 100.000000*kmh,-20.000000*kmh, 0.000000*kmh };
    double vel1[3]={ 100.000000*kmh, 20.000000*kmh, 0.000000*kmh };

    Beware mine coordinates are in Long,Lat,Alt order/convention !!!

  2. output

    You need to compute the time in which the two objects "collide" Additional constrains to solution can be added latter on. As mentioned before we are not searching for intersection but "closest" approach instead that suffice collision conditions (like distance is smaller then some threshold).

After some taught and testing I decided to use iterative approach in WGS84 space. That brings up some problems like how to convert speed in [m/s] in WGS84 space to [rad/s] in WGS84 space. This ratio is changing with object altitude and latitude. In reality we need to compute angle change in long and lat axises that are "precisely" equal to 1m traveled distance and then multiply the velocities by it. This can be approximated by arc-length equation:

l = dang.R

Where R is actual radius of angular movement, ang is the angle change and l is traveled distance so when l=1.0 then:

dang = 1.0/R

If we have Cartesian position x,y,z (z is Earth rotation axis) then:

Rlon = sqrt (x*x + y*y)
Rlat = sqrt (x*x + y*y + z*z)

Now we can iterate positions with time which can be used to approximate closest approach time. We need to limit the max time step however so we do not miss to much of the Earth curvature. This limit is dependent on used speeds and target precision. So here the algorithm to find the approach:

  1. init

    set initial time step to the upper limit like dt=1000.0 and compute actual positions of booth objects in Cartesian space. From that compute their distance d1.

  2. iteration

    set d0=d1 then compute actual speeds in WGS84 for actual positions and add speed*dt to each objects actual WGS84 position. Now just compute actual positions in Cartesian space and compute their distance d1

    if d0>d1 then it menas we are closing to the closest approach so goto #2 again.

    In case d0==d1 the trajectories are parallel so return approach time t=0.0
    In case d0<d1 we already crossed the closest approach so set dt = -0.1*dt and if dt>=desired_accuracy goto #2 otherwise stop.

  3. recover best t

    After the iteration in #2 we should recover the best time back so return t+10.0*dt;

Now we have closest approach time t. Beware it can be negative (if the objects are going away from each other). Now you can add your constrains like

if (d0<_max_d)
if ((t>=0.0)&&(t<=_max_T))
return collision ...

Here C++ source for this:

//---------------------------------------------------------------------------
#include <math.h>
//---------------------------------------------------------------------------
const double kmh=1.0/3.6;
const double deg=M_PI/180.0;
const double rad=180.0/M_PI;
const double _earth_a=6378137.00000; // [m] WGS84 equator radius
const double _earth_b=6356752.31414; // [m] WGS84 epolar radius
const double _earth_e=8.1819190842622e-2; // WGS84 eccentricity
const double _earth_ee=_earth_e*_earth_e;
//--------------------------------------------------------------------------
const double _max_d=2500.0; // [m] collision gap
const double _max_T=3600000.0; // [s] max collision time
const double _max_dt=1000.0; // [s] max iteration time step (for preserving accuracy)
//--------------------------------------------------------------------------
// lon lat alt
double pos0[3]={ 23.000000*deg, 48.000000*deg,2500.000000 }; // [rad,rad,m]
double pos1[3]={ 23.000000*deg, 35.000000*deg,2500.000000 }; // [rad,rad,m]
double vel0[3]={ 100.000000*kmh,-20.000000*kmh, 0.000000*kmh }; // [m/s,m/s,m/s]
double vel1[3]={ 100.000000*kmh,+20.000000*kmh, 0.000000*kmh }; // [m/s,m/s,m/s]
//---------------------------------------------------------------------------
double divide(double x,double y)
{
if ((y>=-1e-30)&&(y<=+1e-30)) return 0.0;
return x/y;
}
void vector_copy(double *c,double *a) { for(int i=0;i<3;i++) c[i]=a[i]; }
double vector_len(double *a) { return sqrt((a[0]*a[0])+(a[1]*a[1])+(a[2]*a[2])); }
void vector_len(double *c,double *a,double l)
{
l=divide(l,sqrt((a[0]*a[0])+(a[1]*a[1])+(a[2]*a[2])));
c[0]=a[0]*l;
c[1]=a[1]*l;
c[2]=a[2]*l;
}
void vector_sub(double *c,double *a,double *b) { for(int i=0;i<3;i++) c[i]=a[i]-b[i]; }
//---------------------------------------------------------------------------
void WGS84toXYZ(double *xyz,double *abh)
{
double a,b,h,l,c,s;
a=abh[0];
b=abh[1];
h=abh[2];
c=cos(b);
s=sin(b);
// WGS84 from eccentricity
l=_earth_a/sqrt(1.0-(_earth_ee*s*s));
xyz[0]=(l+h)*c*cos(a);
xyz[1]=(l+h)*c*sin(a);
xyz[2]=(((1.0-_earth_ee)*l)+h)*s;
}
//---------------------------------------------------------------------------
void WGS84_m2rad(double &da,double &db,double *abh)
{
// WGS84 from eccentricity
double p[3],rr;
WGS84toXYZ(p,abh);
rr=(p[0]*p[0])+(p[1]*p[1]);
da=divide(1.0,sqrt(rr));
rr+=p[2]*p[2];
db=divide(1.0,sqrt(rr));
}
//---------------------------------------------------------------------------
double collision(double *pos0,double *vel0,double *pos1,double *vel1)
{
int e,i,n;
double p0[3],p1[3],q0[3],q1[3],da,db,dt,t,d0,d1,x,y,z;
vector_copy(p0,pos0);
vector_copy(p1,pos1);
// find closest d1[m] approach in time t[sec]
dt=_max_dt; // [sec] initial time step (accuracy = dt/10^(n-1)
n=6; // acuracy loops
for (t=0.0,i=0;i<n;i++)
for (e=0;;e=1)
{
d0=d1;
// compute xyz distance
WGS84toXYZ(q0,p0);
WGS84toXYZ(q1,p1);
vector_sub(q0,q0,q1);
d1=vector_len(q0);
// nearest approach crossed?
if (e)
{
if (d0<d1){ dt*=-0.1; break; } // crossing trajectories
if (fabs(d0-d1)<=1e-10) { i=n; t=0.0; break; } // parallel trajectories
}
// apply time step
t+=dt;
WGS84_m2rad(da,db,p0);
p0[0]+=vel0[0]*dt*da;
p0[1]+=vel0[1]*dt*db;
p0[2]+=vel0[2]*dt;
WGS84_m2rad(da,db,p1);
p1[0]+=vel1[0]*dt*da;
p1[1]+=vel1[1]*dt*db;
p1[2]+=vel1[2]*dt;
}
t+=10.0*dt; // recover original t
// if ((d0<_max_d)&&(t>=0.0)&&(t<=_max_T)) return collision; else return no_collision;
return t;
}
//---------------------------------------------------------------------------

Here an overview of example:

overview

Red is object0 and Green is object1. The White squares represents position at computed collision at time t_coll [s] with distance d_coll [m]. Yellow squares are positions at user defined time t_anim [s] with distance d_anim [m] which is controlled by User for debugging purposes. As you can see this approach works also for times like 36 hours ...

Hope I did not forget to copy something (if yes comment me and I will add it)

Location and time of impact for a moving point and a moving line segment (Continuous Collision Detection)

TLDR

I did read "...like 5 minutes to evaluate..."

No way too long, this is a real-time solution for many lines and points.

Sorry this is not a complete answer (I did not rationalize and simplify the equation) that will find the point of intercept, that I leave to you.

Also I can see several approaches to the solution as it revolves around a triangle (see image) that when flat is the solution. The approach bellow finds the point in time when the long side of the triangle is equal to the sum of the shorter two.

Solving for u (time)

This can be done as a simple quadratic with the coefficients derived from the 3 starting points, the vector over unit time of each point. Solving for u

The image below give more details.

  • The point P is the start pos of point
  • The points L1, L2 are the start points of line ends.
  • The vector V1 is for the point, over unit time (along green line).
  • The vectors V2,V3 are for the line ends over unit time.
  • u is the unit time
  • A is the point (blue), and B and C are the line end points (red)

There is (may) a point in time u where A is on the line B,C. At this point in time the length of the lines AB (as a) and AC (as c) sum to equal the length of line BC (as b) (orange line).

That means that when b - (a + c) == 0 the point is on the line. In the image the points are squared as this simplifies it a little. b2 - (a2 + c2) == 0

At the bottom of image is the equation (quadratic) in terms of u, P, L1, L2, V1, V2, V3.

That equation needs to be rearranged such that you get (???)u2 + (???)u + (???) = 0

Sorry doing that manually is very tedious and very prone to mistakes. I don`t have the tools at hand to do that nor do I use python so the math lib you are using is unknown to me. However it should be able to help you find how to calculate the coefficients for (???)u2 + (???)u + (???) = 0

Sample Image

Update

Ignore most of the above as I made a mistake. b - (a + c) == 0 is not the same as b2 - (a2 + c2) == 0. The first one is the one needed and that is a problem when dealing with radicals (Note that there could still be a solution using a + bi == sqrt(a^2 + b^2) where i is the imaginary number).

Another solution

So I explored the other options.

The simplest has a slight flaw. It will return the time of intercept. However that must be validated as it will also return the time for intercepts when it intercepts the line, rather than the line segment BC

Thus when a result is found you then test it by dividing the dot product of the found point and line segment with the square of the line segments length. See function isPointOnLine in test snippet.

To solve I use the fact that the cross product of the line BC and the vector from B to A will be 0 when the point is on the line.

Some renaming

Using the image above I renamed the variables so that it is easier for me to do all the fiddly bits.

/*
point P is {a,b}
point L1 is {c,d}
point L2 is {e,f}
vector V1 is {g,h}
vector V2 is {i,j}
vector V3 is {k,l}

Thus for points A,B,C over time u */
Ax = (a+g*u)
Ay = (b+h*u)
Bx = (c+i*u)
By = (d+j*u)
Cx = (e+k*u)
Cy = (f+l*u)

/* Vectors BA and BC at u */
Vbax = ((a+g*u)-(c+i*u))
Vbay = ((b+h*u)-(d+j*u))
Vbcx = ((e+k*u)-(c+i*u))
Vbcy = ((f+l*u)-(d+j*u))

/*
thus Vbax * Vbcy - Vbay * Vbcx == 0 at intercept
*/

This gives the quadratic

0 = ((a+g*u)-(c+i*u)) * ((f+l*u)-(d+j*u)) - ((b+h*u)-(d+j*u)) * ((e+k*u)-(c+i*u))

Rearranging we get

0 = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)*u* u -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))*u +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

The coefficients are thus

 A = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)
B = -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))
C = (c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

We can solve using the quadratic formula (see image top right).

Note that there could be two solutions. In the example I ignored the second solution. However as the first may not be on the line segment you need to keep the second solution if within the range 0 <= u <= 1 just in case the first fails. You also need to validate that result.

Testing

To avoid errors I had to test the solution

Below is a snippet that generates a random random pair of lines and then generate random lines until an intercept is found.

The functions of interest are

  • movingLineVPoint which return the unit time of first intercept if any.
  • isPointOnLine to validate the result.

const ctx = canvas.getContext("2d");
canvas.addEventListener("click",test);
const W = 256, H = W, D = (W ** 2 * 2) ** 0.5;
canvas.width = W; canvas.height = H;
const rand = (m, M) => Math.random() * (M - m) + m;
const Tests = 300;
var line1, line2, path, count = 0;
setTimeout(test, 0);

// creating P point L line
const P = (x,y) => ({x,y,get arr() {return [this.x, this.y]}});
const L = (l1, l2) => ({l1,l2,vec: P(l2.x - l1.x, l2.y - l1.y), get arr() {return [this.l1, this.l2]}});
const randLine = () => L(P(rand(0, W), rand(0, H)), P(rand(0, W), rand(0, H)));
const isPointOnLine = (p, l) => {
const x = p.x - l.l1.x;
const y = p.y - l.l1.y;
const u = (l.vec.x * x + l.vec.y * y) / (l.vec.x * l.vec.x + l.vec.y * l.vec.y);
return u >= 0 && u <= 1;
}
// See answer illustration for names
// arguments in order Px,Py,L1x,l1y,l2x,l2y,V1x,V1y,V2x,V2y,V3x,V3y
function movingLineVPoint(a,b, c,d, e,f, g,h, i,j, k,l) {
var A = -(i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j;
var B = -d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j)
var C = +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

// Find roots if any. Could be up to 2
// Using the smallest root >= 0 and <= 1
var u, D, u1, u2;
// if A is tiny we can ignore
if (Math.abs(A) < 1e-6) {
if (B !== 0) {
u = -C / B;
if (u < 0 || u > 1) { return } // !!!! no solution !!!!
} else { return } // !!!! no solution !!!!
} else {
B /= A;
D = B * B - 4 * (C / A);
if (D > 0) {
D **= 0.5;
u1 = 0.5 * (-B + D);
u2 = 0.5 * (-B - D);
if ((u1 < 0 || u1 > 1) && (u2 < 0 || u2 > 1)) { return } // !!!! no solution !!!!
if (u1 < 0 || u1 > 1) { u = u2 } // is first out of range
else if (u2 < 0 || u2 > 1) { u = u1 } // is second out of range
else if (u1 < u2) { u = u1 } // first is smallest
else { u = u2 }
} else if (D === 0) {
u = 0.5 * -B;
if (u < 0 || u > 1) { return } // !!!! no solution !!!!
} else { return } // !!!! no solution !!!!
}
return u;
}

function test() {
if (count> 0) { return }
line1 = randLine();
line2 = randLine();
count = Tests
subTest();
}
function subTest() {
path = randLine()
ctx.clearRect(0,0,W,H);
drawLines();
const u = movingLineVPoint(
path.l1.x, path.l1.y,
line1.l1.x, line1.l1.y,
line2.l1.x, line2.l1.y,
path.vec.x, path.vec.y,
line1.vec.x, line1.vec.y,
line2.vec.x, line2.vec.y
);

if (u !== undefined) { // intercept found maybe
pointAt = P(path.l1.x + path.vec.x * u, path.l1.y + path.vec.y * u);
lineAt = L(
P(line1.l1.x + line1.vec.x * u, line1.l1.y + line1.vec.y * u),
P(line2.l1.x + line2.vec.x * u, line2.l1.y + line2.vec.y * u)
);
const isOn = isPointOnLine(pointAt, lineAt);
if (isOn) {
drawResult(pointAt, lineAt);
count = 0;
info.textContent = "Found at: u= " + u.toFixed(4) + ". Click for another";
return;
}
}
setTimeout((--count < 0 ? test : subTest), 18);
}

function drawLine(line, col = "#000", lw = 1) {
ctx.lineWidth = lw;
ctx.strokeStyle = col;
ctx.beginPath();
ctx.lineTo(...line.l1.arr);
ctx.lineTo(...line.l2.arr);
ctx.stroke();
}
function markPoint(p, size = 3, col = "#000", lw = 1) {
ctx.lineWidth = lw;
ctx.strokeStyle = col;
ctx.beginPath();
ctx.arc(...p.arr, size, 0, Math.PI * 2);
ctx.stroke();
}
function drawLines() {
drawLine(line1);
drawLine(line2);
markPoint(line1.l1);
markPoint(line2.l1);
drawLine(path, "#0B0", 1);
markPoint(path.l1, 2, "#0B0", 2);
}
function drawResult(pointAt, lineAt) {
ctx.clearRect(0,0,W,H);
drawLines();
markPoint(lineAt.l1, 2, "red", 1.5);
markPoint(lineAt.l2, 2, "red", 1.5);
markPoint(pointAt, 2, "blue", 3);
drawLine(lineAt, "#BA0", 2);
}
div {position: absolute; top: 10px; left: 12px}
canvas {border: 2px solid black}
<canvas id="canvas" width="1024" height="1024"></canvas>
<div><span id="info">Click to start</span></div>

Colliding shapes in python

  1. Collision detection is very easy in pygame. Take a look at using pygame.sprite. They have several functions to detect collisions. (spritecollide, groupcollide, etc) If you have some complex collision interaction generally you use the rect or circle to see if they collide, then only do your complex calculations on those. Though for most games you do not need to have the cost of perfect collision detection, close enough is good enough.
  2. As far was what happens when you collide, that is more physics then programming. Some concepts to keep in mind are: momentum conservation, elastic vs inelastic collisions, deflection angle. "How to building a 2D physics engine" is a bit too broad for SO question. Maybe look at how-to-create-a-custom-2d-physics-engine-oriented-rigid-bodies


Related Topics



Leave a reply



Submit