# Irlan

Member

605

4067 Excellent

• Rank

• Website
• Interests
Programming

irlanrobson
• Github
irlanrobson
1. ## SAT sphere triangle test, calculating response

You can implement a position based constraint solver for this. Sharp corners requires a large number of solver iterations. Erin Catto (Box2D) described this algorithm at the end of his presentation:    http://box2d.org/files/GDC2014/GDC2014_ErinCatto.zip   It should be pretty easy to simplify it to your case and a great exercise. This is a very good resource with no lack of mathematical foundation.   Sorry, I cannot list you all the edge cases because I haven't taken the time to implement a robust character controller. But that is not a difficult problem we can tell you. If your engine supports double side collision the order of the triangle vertices doesn't matter.
2. ## SAT sphere triangle test, calculating response

You can use Barycentric coordinates to find the closest point on the triangle to the sphere center. Here's some personal code of mine you can use: // Convert a point Q from Cartesian coordinates to Barycentric coordinates (u, v) // with respect to a segment AB. // The last output value is the divisor. static B3_FORCE_INLINE void b3Barycentric(float32 out[3],     const b3Vec3& A, const b3Vec3& B,     const b3Vec3& Q) {     b3Vec3 AB = B - A;     b3Vec3 QA = A - Q;     b3Vec3 QB = B - Q;     float32 divisor = b3Dot(AB, AB);          out[0] = b3Dot(QB, AB);     out[1] = -b3Dot(QA, AB);     out[2] = divisor; } // Convert a point Q from Cartesian coordinates to Barycentric coordinates (u, v, w) // with respect to a triangle ABC. // The last output value is the divisor. static B3_FORCE_INLINE void b3Barycentric(float32 out[4],     const b3Vec3& A, const b3Vec3& B, const b3Vec3& C,     const b3Vec3& Q) {     b3Vec3 AB = B - A;     b3Vec3 AC = C - A;     b3Vec3 QA = A - Q;     b3Vec3 QB = B - Q;     b3Vec3 QC = C - Q;     b3Vec3 QB_x_QC = b3Cross(QB, QC);     b3Vec3 QC_x_QA = b3Cross(QC, QA);     b3Vec3 QA_x_QB = b3Cross(QA, QB);     b3Vec3 AB_x_AC = b3Cross(AB, AC);          float32 divisor = b3Dot(AB_x_AC, AB_x_AC);     out[0] = b3Dot(QB_x_QC, AB_x_AC);     out[1] = b3Dot(QC_x_QA, AB_x_AC);     out[2] = b3Dot(QA_x_QB, AB_x_AC);     out[3] = divisor; } // Return the closest point on a triangle ABC to a point Q. b3Vec3 Solve3(const b3Vec3& A, const b3Vec3& C, const b3Vec3& C, const b3Vec3& Q) {     // Test vertex regions     float32 wAB[3], wBC[3], wCA[3];     b3Barycentric(wAB, A, B, Q);     b3Barycentric(wBC, B, C, Q);     b3Barycentric(wCA, C, A, Q);          // R A     if (wAB[1] <= 0.0f && wCA[0] <= 0.0f)     {         return A;     }     // R B     if (wAB[0] <= 0.0f && wBC[1] <= 0.0f)     {         return B;     }     // R C     if (wBC[0] <= 0.0f && wCA[1] <= 0.0f)     {         return C;     }     // Test edge regions             float32 wABC[4];     b3Barycentric(wABC, A.point, B.point, C.point, Q);          // This is used to help testing if the face degenerates     // into an edge.     float32 area = wABC[3];     // R AB     if (wAB[0] > 0.0f && wAB[1] > 0.0f && area * wABC[2] <= 0.0f)     {         float32 s = wAB[2];         B3_ASSERT(s > 0.0f);         return (wAB[0] * A + wAB[1] * B) / s;     }     // R BC     if (wBC[0] > 0.0f && wBC[1] > 0.0f && area * wABC[0] <= 0.0f)     {         float32 s = wBC[2];         B3_ASSERT(s > 0.0f);         return (wBC[0] * B + wBC[1] * C) / s;     }     // R CA     if (wCA[0] > 0.0f && wCA[1] > 0.0f && area * wABC[1] <= 0.0f)     {         float32 s = wCA[2];         B3_ASSERT(s > 0.0f);         return (wCA[0] * C + wCA[1] * A) / s;     }     // R ABC/ACB     float32 s = wABC[3];     if (s <= 0.0f)     {         // Give up. Triangle is degenerate. // You should handle all cases correctly in production code.         return;     }     B3_ASSERT(s > 0.0f); return (wABC[0] * A + wABC[1] * B + wABC[2] * C) / s; } If you want to learn the math read Real-Time Collision Detection book.
3. ## SAT sphere triangle test, calculating response

The penetration depth is the distance between the closest points minus the sphere radius. The collision normal is the separating axis. If the triangle is static and you want a positional response then you can shift the sphere center by the penetration depth along the collision normal. Assume p2 is the closest point on the triangle to the sphere center. You can shift the sphere like this:   penetration = dot(p2 - center, normal) - radius center = center + penetration * normal
4. ## Quaternions and multiple rotations

I hope the following example helps.   Define ref_joint_rotation as a constant reference joint rotation. ref_joint_rotation transforms vectors defined in joint frame to vectors in parent joint frame at pose configuration. Now you want to define the current reference joint rotation cur_joint_rotation as the reference joint rotation plus a rotation about 90 degrees about the z axis relative to the parent frame. That's how you would do this: Vector3 axis axis.Set(0.0f, 0.0f, 1.0f); float angle = 0.5f * PI; Quaternion joint_rotation; joint_rotation.SetAxisAngle(axis, angle); cur_joint_rotation = joint_rotation * ref_joint_rotation; cur_joint_rotation rotates vectors in child frame to vectors in parent frame at the current configuration. Here the quaternion multiplication is defined in the original form. That is, a rotation by ref_joint_rotation followed by a rotation by joint_rotation.
5. ## D3D9 - Rotation on a specific local axis

Yes, is possible without quaternions.    You want to rotate the planet about the world x/y-axis of the ship.   Matrix33 rotation_x = MakeRotationFromAngleAxis(ship.rotation.x, angle_x); planet.rotation = rotation_x * planet.rotation;   Matrix33 rotation_y = MakeRotationFromAngleAxis(ship.rotation.y, angle_y); planet.rotation = rotation_y * planet.rotation;   MakeRotationFromAngleAxis returns a rotation matrix given an axis of rotation and angle of rotation about the axis. IIRC in DirectX there is a function called D3DXMatrixRotationAxis that computes this.   In DirectX you might need to swap the multiplication order. E.g:   planet.rotation = rotation_x * planet.rotation;   becomes   planet.rotation = planet.rotation * rotation_x;
6. ## LibGDX/Box2D orbital mechanics

You've multiplied -1 because the force direction should be planet_position - rocket_position.   I haven't read the rest of the code but as a beginner you should learn how to build or use a 2D math library before digging into game physics. If you're using Box2D for educational purposes I would just use its own.   With a math lib what you wrote becomes:   Vec2 displacement = planet.position - rocket.position; Vec2 force_direction = Normalize(displacement); float force_magnitude = planet.gravity * (rocket.mass * planet.mass) / LenghtSquared(displacement);   Vec2 F1 = force_magnitude * force_direction; Vec2 F2 = -F1;   rocket.ApplyForce(F1); planet.ApplyForce(F2);   Also...   When needed to calculate the angle between two vectors, don't use atan(y / x). Use atan2(y, x) if your math library has it because it can map to a larger angle range and handle x = 0.   You're passing degrees instead of radians to the cos and sin functions. I think in Java these functions also assume radians are given.    Don't use pow if the exponent is 2. Use base * base.
7. ## Calculating the moment of inertia of a 2D capsule

Here is the step-by-step calculation of the capsule inertia. I have the code in 3D so I downscaled it to 2D for your convenience. Of course you can simplify it but the decoupled approach is nice for clarification. You can also look use this image as a reference (originally from Dirk's paper).   float32 r = m_radius; float32 r2 = r * r; float32 w = 2.0f * r; float32 w2 = w * w; float32 h = b3Length(B - A); float32 h2 = h * h; // Rectangle inertia about the capsule center of mass b3MassData Ic_Rectangle; { // Rectangle mass float32 area = w * h; float32 mass = density * area; // Rectangle inertia about the center of mass (same as capsule center of mass) Ic_Rectangle.center = 0.5f * (A + B); Ic_Rectangle.mass = mass; Ic_Rectangle.I = mass * (w2 + h2) / 12.0f; } // Semicircle inertia about the capsule center of mass b3MassData Ic_Semicircle; { // Circle area and mass float32 circleArea = B3_PI * r2; float32 circleMass = density * circleArea; float32 circleI = circleMass * 0.5f * r2; // Semicircle area and mass float32 area = 0.5f * circleArea; float32 mass = 0.5f * circleMass; // Semicircle inertia about the base float32 Io = 0.5f * circleI; // Paralell axis theorem // I = Ic + m * d^2 // Ic = I - m * d^2 // Semicircle center of mass distance to the base float32 d1 = (3.0f / 8.0f) * r; // Semicircle inertia about its center of mass float32 Ic = Io - (mass * d1 * d1); // Semicircle center of mass distance to the capsule center of mass float32 d2 = d1 + 0.5f * h; // Semicircle inertia about the capsule center of mass float32 I = Ic + (mass * d2 * d2); Ic_Semicircle.center.Set(0.0f, d2); Ic_Semicircle.mass = mass; Ic_Semicircle.I = I; } // Capsule inertia about the capsule center of mass taking two semicircles into account b3MassData Ic_Capsule; Ic_Capsule.center = Ic_Rectangle.center; Ic_Capsule.mass = Ic_Rectangle.mass + 2.0f * Ic_Semicircle.mass; Ic_Capsule.I = Ic_Rectangle.I + 2.0f * Ic_Semicircle.I;
8. ## Calculating the moment of inertia of a 2D capsule

One problem is that momentOfInertiaOfSemiCircle is the moment of inertia of the (full) circle.    When I get home I'll try to derive you step-by-step.
9. ## Finding a point on trajectory in which we should change move vector

Oh, I see. The solution is obviously shape representation dependent. In 2D, a convex polygon is typically represented by a set of vertices and intersecting planes. Hence, one option, hypotetically, is inflate the planes by the sphere radius at initialization time.   Alternatively, I would extend the ray vs. static polygon test to dynamic sphere vs. static polygon test. I haven't tried this yet, but here is an example:   A ray:   p = p1 + t * s    A plane taking a radius r into account:   dot(n, p) = d +/- r   Solve for t:   dot(n, p1) + t * dot(n, s) = d +/- r t = ( +/- r - ( dot(n, p1) - d ) ) / dot(n, s)   I would use Real Time Collision Detection, page 219-220, as a reference.   Since the ray is paralell to the left wall the ray cast will have failed leaving the intersection point on the right wall as the solution to this simple problem.    Hope that helps.
10. ## Finding a point on trajectory in which we should change move vector

Well, looks like you've answered your question already.   Shift the collision plane by R along the plane normal and derive the contact point from the minimum time of impact via ray-cast.   You can also implement a iterative local plane solver. Note that for accute angles (not your case) you might need a large number of iteration to converge. I never implemented this algorithm, but it was covered at the end of this talk:   http://box2d.org/files/GDC2014/GDC2014_ErinCatto.zip
11. ## Physics - Fix sinking in impulse calculation?

Read the books referenced by the authors in each slideshow on Box2D resources. Usually each talk has a References section linking the materials that helped the author understand the subject being discussed in details.   Real-Time Collision Detection book and Dirk Gregorius's talks should be sufficient reads for learning how to detect collisions and generate contact points on primitives. On more complex shapes, you need the GJK and SAT algorithms. There are some resources on box2d.org and gamedev.net about these algorithms as well.   Computational Dynamics by Shabana covers constraints in details.
12. ## 3D collision question

As long as the other sphere/AABB is in the local space of the first AABB there is no problem in the code.   Contact impulse/force handlers assume the contact points and normals are in the same space. Usually in world space.   Contact points and normals can be transformed to the local space of the shapes before performing position correction iteratively. Each iteration the positions and orientations of the bodies are corrected by some ammount. Of course after this the contact points and normals might have changed so in a next iteration we need to rebuild contact points and normals. However, re-run collision detection each iteration can become pretty expensive. So an efficient method, but not as accurate as the former, is to put contact points in the local space before iterating, and then transform the local contact points and normals using the transforms in the current iteration.
13. ## Generating contacts from EPA result (normal + depth)

Oops, I wrote way too fast, sorry.   No, EPA finds 1 point each frame. So yes, one contact point can be added each frame. When there are more than 4 points you need reduce to 4 points. That's how Bullet does.    Dirk discussed state-of-the art contact creation and the reduction algorithm was mentioned in his talk at the GDC:   http://box2d.org/files/GDC2015/DirkGregorius_Contacts.pdf
14. ## Generating contacts from EPA result (normal + depth)

The simplest method is to add up to 4 contact points to a manifold each frame. Like Bullet does. When there are 4 contact points and a new point is about to be added then the combination of contact points that maximizes the contact area in the manifold is mantained. IIRC there is some code at btPersistentManifold.cpp implementing this algorithm. The downside for the contact solver is contact points proximity are matched against a distance tolerance. Not against the features that built them. Ocasionally (specially in stacking scenarios) the consequence is bad manifold stability.    I switched to SAT and clipping for contact generation since some time ago and can recommend. This is the common method used these days.
15. ## Proper 2d contact generation for speculative contacts

Before diving into CCD and CP    Read the maths and physics sections in the book Essential Math for Games and Interactive Applications Study all GDC presentations by Erin and Dirk Implement a decent debug drawing interface Port Box2D Lite to 3D Learn and implement the GJK and SAT algorithms Study sub-stepping Read Brian Mirtich CCD and CP thesis Study root-finding methods, it helps to understand the general problem of TOI computation    Make sure you understand every line of code of your physics engine and the limits of the engine. Comment the important parts, specially why and not how you wrote something. If you have a feature that you don't know how or why it worked (maybe you was too anxious to see the results on the screen or didn't have time to read about it properly) then remove it from your project and add it only after understanding. Usually you can see a well architected physics engine when the author understands the problems.     You can learn a lot when creating something from scratch using only the literature and skipping existing implementation, but currently this is impractical and error prone since there is a great deal of intuitive resources and discussions out there (e.g. gamedev/Bullet forums).   Box2D Lite doesn't have a state of the art dynamics for games implemented because of its position corrector. Once you're familiar with it you can try porting *Box2D* position correctors to 3D.