Jump to content
  • Advertisement

Randy Gaul

  • Content Count

  • Joined

  • Last visited

Community Reputation

2793 Excellent


About Randy Gaul

  • Rank

Recent Profile Visitors

9071 profile views
  1. Consider worst case of roughly 12 vertices against 12 vertices. That’s 144 loops. However this will operate on memory inside of a very small space in L1 cache. Pretty much, it’s going to be extremely fast.
  2. Randy Gaul

    Polygons and the Separating Axis Theorem

    The idea instead of computing min/max along an interval, you can use the concept of support points. This can reduce some redundancy in your code and potentially make it easier to pin-point the problem.
  3. Randy Gaul

    Polygons and the Separating Axis Theorem

    I'd like to help but I have trouble understanding what you need help with. Maybe you can try asking a more specific question as opposed to some paragraphs, and also if you can post a video/gif showing your problem that helps a lot as well.
  4. Randy Gaul

    GJK warm starting

    It's a fairly safe thing to do so long as the simplex is not degenerate (which can definitely happen!), so upon warm-starting check for a degenerate case, and if found, invalidate your GJK cache. Otherwise conceptually warm-starting should make quite a bit of sense. The GJK crawls through the volume of two shapes simultaneously -- so any configuration (that isn't degenerate) is OK as GJK iterations will always evolve the simplex towards the origin due to the properties of support mappings. Have you tried reading Box2D's source on warm-starting? It is really quite simple: https://github.com/erincatto/Box2D/blob/master/Box2D/Collision/b2Distance.cpp#L104-L165 . Also a little more info: https://pybullet.org/Bullet/phpBB3/viewtopic.php?t=3338
  5. I think this is pretty bad advice. Sure the rest of the things you listed need to be learned, but come on, don't use arrays? That just sounds like C++ dogma. Besides this bit here, I did like the majority of the rest of the advice in this thread. Just try to keep opinions on the down-low or at least say they are your opinion clearly. For example: in my personal opinion I think any new C/C++ guy should fully embrace pointers and arrays as a basic necessity. There's a lot of reasons why you have your opinion, and I have mine, and they are probably all off-topic, so just do the thread a favor and distinguish between personal taste and actual errors in the code.
  6. Randy Gaul

    AABB is Behind Plane Test

    This is a fine way to write this function (assuming your implementation is correct, which I didn't really read).
  7. Some links to read: The ping-pong effect for acute angles is a weakness of the iterative seidel solver. Any solution would involve somehow looking at more than one plane at a time to detect this kind of case. Collecting planes in a set, or otherwise, followed by something to "kick" the system out of the locally difficult state. I don't think that thread is quite what you're looking for -- but I was describing a way to get a makeshift contact normal by calling GJK between a line segment and some other shape. This normal may or may not be useful, and if extra care isn't taken the character can be pressed along this normal into a colliding configuration. I would suggest checking out the other links.
  8. You can do this with a simple algorithm in 2D using a brute-force method. It's super fast when you cap N to something reasonable. For a 2D OBB I imagine maybe N as 5-15 could look good for a lot of games. generate N points inside of obb let S be an empty set of polygons for each point A in N points let shape be initialized with obb for each other point B in N points create plane P between A and B assign A and B to P as references (in case this book-keeping is needed later) slice shape with P S.insert(shape) S is now the voronoi diagram How you generate your initial point set determines the style of the shatter. After this algorithm runs you can look at each shape relative to how close it is to the impact point, and assign initial velocities.
  9. Randy Gaul

    OBB intersection frustration (SAT)

    I'm a bit surprised copy + pasting Ericson's code doesn't work. Next step should probably be to debug render sub-expressions and start verifying lines you know to be correct, and take note of which ones you don't know to be correct.
  10. 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?
  11. 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
  12. 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.
  13. 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.
  14. 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
  15. 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.
  • 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!