Jump to content
  • Advertisement

Randy Gaul

  • Content count

  • Joined

  • Last visited

Community Reputation

2792 Excellent


About Randy Gaul

  • Rank

Recent Profile Visitors

8893 profile views
  1. Randy Gaul

    QR Algorithm & Eigen value order

    "So, my question is. How can i re-order the results, so that 15 is where i expect it to be?" What are you expecting exactly?
  2. Randy Gaul

    Tetrahedron's face voronoi region testing

    They way I do this is to order the vertices and named them A, B, C and D. There are 15 regions in total. The interior region, and 14 exterior regions. There are 6 edge regions, 4 face regions, and 4 vertex regions, to form all 14 exterior edges. A simple way to figure out which region a given point is in, is to compute barycentric coordinates of the point against the tetrahedron. This will tell you which faces the point is in front of. Another approach would be to compute distance of point to plane for each face of the tetrahedron. Assuming the point is above a face, it can potentially also be in front of other faces, up to three. So some test would need to be done to see if the point is nearest to one of the edges, one of the faces, or potentially a vertex. In my own code I just up-front compute barycentric coordinates for the tetrahedron, along with coordinates for all the triangles, and directly enumerate the 15 different cases with 15 different checks (and 15 different return points). This can mostly be seen in Erin's 2D version, which is fairly straightforward to extend to 3D: http://box2d.org/files/GDC2010/Distance2D.zip
  3. Good questions. Minkowski stuff is useful to implement the GJK algorithm. GJK finds the two closest points between two convex sets. It does not do anything else -- if two shapes are colliding, all that is known after GJK runs is that they are colliding. It provides no information as to how, which is needed to resolve a collision. I suggest using a very straight-forward function to quickly test to see if two AABBs are touching at all. This can be coded in SIMD pretty easily if you want an extra speed boost. Reading about Minkowski stuff will not help you here. Something like this (which I grabbed from here https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detectionūüėě function intersect(a, b) { return (a.minX <= b.maxX && a.maxX >= b.minX) && (a.minY <= b.maxY && a.maxY >= b.minY) && (a.minZ <= b.maxZ && a.maxZ >= b.minZ); } If this function returns true, then you can use a more complicated function to compute penetration vector (axis of minimum penetration) and depth (like the function I linked you in my last post). Also it would be wise to use a capsule for your player collider, for a variety of reasons! Mainly to make things easy to implement.
  4. Randy Gaul

    Ellipsoid vs Convex shape GJK collision response

    Don't implement EPA. Use a capsule for your player instead of an ellipse. Once you find the TOI, place the capsule at this location. Then use GJK without considering the capsule radius. This will give you the closest points bewteen the capsule's interior line segment, and the other convex volume. From here calculating resolution terms is trivial.
  5. You should use a different algorithm. Using GJK for this task is A) overkill, and B) will not help you resolve the collision. Here's an example algorithm in 2D that can be extended to 3D: https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h#L1285-L1340
  6. Randy Gaul

    Incorrect angular collision response

    Haha that's a pretty good one! Thanks for sharing. Very entertaining. We have all struggled with this exact kind of mistake. Back when I intern at thatgamecompany I had a week long problem between row vs column notation. Nobody in the company understood which was which, and instead just had "a consistent ordering" in the codebase. But it was a problem when attempting to port in code with unknown ordering... Or implement papers where they have different notation compared to the code. For scalar multiplication one thing I found that helps is to only have on operator defined, so 0.5 * vec can compile, but vec * 0.5 can not compile. This kind of thing has prevented order swappings for me before, especially when porting code between code bases. --- One time I had a typo in the collision constraint code back in school. The typo was accidentally re-using an old vector in the solver, as opposed to the correct one, because of a typo. Funny thing was numerically each vector was nearly the same, so long as the constraint geometry was close to the origin. But, once shapes were far away from the origin the error would get larger. The result was whenever the player bumped into tables (the only dynamic objects) and woke them up, the collision constraints between the tables and the floor would make the table jiggle in a little spiral pattern. As if it were walking in a tiny circle. Really far away from the origin would make tables swirl violently. It took a month to find and fix that bug! I audited basically my entire rigid body engine. For the longest time I thought it was a bad inertia tensor. Turned out to just be a typo in the solver.
  7. Randy Gaul

    Raycast From Camera To Mouse Pointer

    Glad you got it working! Just posting up a reference in case anyone else comes along in this thread: https://github.com/RandyGaul/cute_headers/blob/master/cute_math.h#L630-L649 void compute_mouse_ray( float mouse_x, float mouse_y, float fov, float viewport_w, float viewport_h, float* cam_inv, float near_plane_dist, v3* mouse_pos, v3* mouse_dir ) { float aspect = (float)viewport_w / (float)viewport_h; float px = 2.0f * aspect * mouse_x / viewport_w - aspect; float py = -2.0f * mouse_y / viewport_h + 1.0f; float pz = -1.0f / tanf( fov / 2.0f ); v3 point_in_view_space( px, py, pz ); v3 cam_pos( cam_inv[ 12 ], cam_inv[ 13 ], cam_inv[ 14 ] ); float pf[ 4 ] = { getx( point_in_view_space ), gety( point_in_view_space ), getz( point_in_view_space ), 1.0f }; tgMulv( cam_inv, pf ); v3 point_on_clipping_plane( pf[ 0 ] , pf[ 1 ], pf[ 2 ] ); v3 dir_in_world_space = point_on_clipping_plane - cam_pos; v3 dir = norm( dir_in_world_space ); v3 cam_forward( cam_inv[ 8 ], cam_inv[ 9 ], cam_inv[ 10 ] ); *mouse_dir = dir; *mouse_pos = cam_pos + dir * dot( dir, cam_forward ) * vfloat( near_plane_dist ); }
  8. Randy Gaul

    Collision Detection - why GJK?

    It's my understanding that nowadays termination criteria are largely based on indices of the input geometry, as opposed to actual floating point positions. Then to prevent multi-step cycling, a clever distance check to the origin can be used to verify incremental progress. This was all from Erin's online resources.
  9. Randy Gaul

    Incorrect angular collision response

    Try running qu3e and record an input matrix and its corresponding output. Then, setup a test case where you use the exact same floating point values, and try to transform your inertia tensor. You should verify where the values are the exact same, or transposed, or otherwise incorrect.
  10. Randy Gaul

    What goes into a "Transform" structure in C/C++?

    Box2D has no scaling because scaling is not useful for a physics engine most of the time. Unity has scaling, because their transform is a general purpose tool to place anything anywhere with any rotate/scaling/translation.
  11. Randy Gaul

    Incorrect angular collision response

    I wrote qu3e, so if you're confused on how something relates to your code snippet, you can just ask here
  12. Randy Gaul

    Incorrect angular collision response

    Your tensors don't look right. You need to use R * I * R^T (or flipped about depending on your notation ordering). The rest more or less looks correct. Be sure to double check it against a known reference code (like Box2D *Lite* or qu3e).
  13. Randy Gaul

    Improving sleep system

    That is correct. Box2D's scheme will not put them to sleep. There are a lot of potential strategies for optimization for the islands not moving much. Caching manifolds or other caching systems can be used to try and skip narrow phase. The island building scheme can maybe be customized in some way to somehow skip non-moving bodies (like the beginning of a domino chain). But I think a caching mechanism would be better suited for this kind of problem, while leaving the island sleeping as a simple algorithm. Just my opinion.
  14. Randy Gaul

    Improving sleep system

    Have you research Box2D's sleep mechanism? The idea is sleep an entire island of bodies by crawling an island graph, and computing the maximum linear/angular velocities. A timers is accumulated while the max are underneath a threshold (one threshold for linear, and one for angular velocity). Once the timer reaches a threshold, the island is put to sleep. Islands are awoken by force events or other user events, and if another collider enters the broadphase bounding shape for any of the island entries.
  15. Randy Gaul

    Modeling restitution

    So I asked Dirk specifically, and he says LCP formulation cannot solve Newton cradle, and this is specifically a well-known topic in literature. I believe he referred to work by Kauffman. Basically affirming what d07RiV and myself were talking about earlier.
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!