Randy Gaul

  • Content count

  • Joined

  • Last visited

Community Reputation

2768 Excellent


About Randy Gaul

  • Rank

Recent Profile Visitors

7006 profile views
  1. Character Solver

    Oh my mistake! I thought you were referring to "bilateral advancement", and didn't realize you were linking to a completely different algorithm. Yes, Catto is talking about the exact same thing I was on tigsource forums To clarify, I think you are on the right track by using a position level plane solver. They are really simple and efficient. Also, using a rounded shape like sphere/capsule is another good choice for characters. It would be wise to let your algorithm handle the case of multiple simultaneous planes. Since the plane solver presses the character along a given plane normal, which does not necessarily coincide with the character's previous path of motion, it is completely possible to "back up" into a configuration hitting multiple simultaneous planes. Gathering up planes is a matter of implementation. One idea would be to use Conservative Advancement (which will be very efficient if your capsule cannot rotate at run-time, and only translates) to find a TOI. At the TOI you should have a plane normal (e.g. from a previous GJK call, or perhaps from some collision detection algorithm; it's up to you). Press away from the plane to create a numeric buffer for subsequent Conservative Advancement calls, and zero out the velocity along the plane normal. Look for a colliding configuration, and then carry on with the remaining velocity if all is OK.
  2. Character Solver

    It's possible to use a much simpler algorithm for characters. Catto's algorithm is more complicated and overkill, intended to be able to solve the entire physics timestep continuously. A simpler Seidel solver can work for characters, along with something akin to Conservative Advancement.
  3. Extracting face/hit data after a GJK step

    Yeah, he means try to cache something from the last frame, that if validated on the next frame, can let you just simply not call your GJK or SAT routines. A good example for GJK is in Box2D. Typically for GJK caching the first step is to cache the "separating axis" from the previous frame. This can be used to warm start GJK, and in practice does work quite well, reducing GJK to a very early out with a couple support calls. The next step, like in Box2D, could be to cache an entire simplex. This can give GJK a good guess and at the very least skip the first couple iterations of building the simplex. In colliding configurations the previous simplex is probably still going to enclose the origin, or be very close. SAT algorithms can probably use similar techniques. Back in university I spent a couple months trying out all kinds of different caching methods to avoiding calling SAT. In the end I was unhappy with all results, as I could never really avoid running clipping routines. I wouldn't really know of good solutions here.
  4. Extracting face/hit data after a GJK step

    Even if you are implementing a TOI solver and then stop + slide, you will still have the possibility to enter colliding configurations, in which case you'd need full manifold generation in order to resolve the collision. This is because when a TOI is found, your shape is moved to the TOI. However, you can't move *directly* to the TOI, otherwise you cannot perform a sliding action as the next TOI search will hit the previously found shape and not move at all. Typically people move their shape to the TOI and then back up ever so slightly to make a numeric buffer for the TOI solver to find the next subsequent TOI. This backing up action usually happens along the collision normal, meaning it's completely possible to back up into colliding configuration. There are all kinds of weird solutions to this problem. Some people try "blacklisting" shapes, others trying solving for TOI on only one of the principles axes at a time, which effectively triples computational cost. Though so far the only working solution I've ever come up with is to just back up along the normal to create a numeric buffer. Lots of people try to implement some kind of character controller or physics simulation using GJK as their only collision detection workhorse -- it's not possible the moment non-trivial behavior is needed. Typically this kind of endeavor comes from ignorance of how the GJK algorithm actually works. It is fairly obvious that in the colliding case there is no useful information as the algorithm terminates. Since the GJK simplex crawls through the middle of the volume via support points, the origin can be enclosed by any arbitrary simplex within the volume. This means when GJK terminates all you know is your two volumes intersect *somewhere*, with no intelligent book-keeping to tell you *where* the overlap occurred. If GJK terminates with witness points (closest points), the contributing features are actually useful, since they are on known positions on each surface of each volume. These features are by definition the "closest features", and can be enumerated from the simplex vertices. However, care needs to be taken to look out for degenerate cases! Once people realize this they panic and try and implement EPA to build a contact manifold, which is not a very favorable strategy in 3D for many reasons. The only way to implement robust collision detection is old-fashioned building the contact manifold. Expanding Polytope Algorithm (EPA), (Separating Axis Theorem/Test) SAT-based alorithms, and Minkowski Portal Refinement (MPR) are the algorithms I am aware of. In my opinion the best by far are the SAT-based algorithms for both 2D and 3D.
  5. Extracting face/hit data after a GJK step

    IIRC that thread was about identifying closest features of two *disjoint* convex sets. It sounds like you want to identify features that contribute to the axis of minimum separation in the colliding case -- this isn't something that can easily be done after running GJK, since GJK does not really help in this case.
  6. That's not something answerable on a forum. You're basically asking how to create an entire physics sim. That said, the answers are in the link you posted earlier. If you can't find them in the link, I'm not really sure anyone can help you here. I appreciate the explicit description. I can't help you because what you are describing is not explicit, even though the description of it is clear. Your problem is vague, even though you described it nicely. There are many reasons why circles may get stuck inside each other, and the problems could be anywhere. There is no simple answer of "how to make them not stick together".
  7. I'd like to help but the question you're asking is very open ended. There isn't really a specific piece I can help you with here. I'd love to help, but it sounds like you're not sure where the problem is yet.
  8. Hi there, Dirk's advice is trying to describe a method to debug your code. The idea is if you get a working solution, then whenever you make small changes it is easy to know what broke. From here finding problems becomes much easier. The tutorial you posted is best used by referencing the source code in the final article. The source code is here: https://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-oriented-rigid-bodies--gamedev-8032 Unfortunately I don't have time to manually step through your code to look for problems. The best thing you can try doing is to take Dirk's advice and start with a small working solution. From there you can modify the working code to look more like your own code, and replace piece by piece until something breaks. This can give you clues on where problems lay.
  9. Creating Threads in Reloadable DLL

    Dang. OK in that case I'll just expose a wrapper callback from the main executable to my reloadable thread. I do want the reloadable thread to be able to spawn threads at-will, but have lifetimes in regards to the main executable.
  10. If I create a thread from a DLL which links against it's own CRT, and then reload that DLL, does it mess with the thread in any way? I'm wondering if the main application should expose a wrapper to create threads, just to avoid any weirdness when the DLL is reloaded during runtime. Reading here it seems like there's some weirdness involved in DLLMain: https://msdn.microsoft.com/en-us/library/windows/desktop/ms682453(v=vs.85).aspx?f=255&MSPPError=-2147217396. However, I'm not using DLLMain at all. But just wanted to check here in case anyone had any knowledge to share.
  11. Cloned the repo, had trouble building in 64bit, couldn't find your Utils.h include. Tried 32 bit and couldn't find SDL. Maybe you could try including the SDL headers into your project so people can just download and build without tinkering?
  12. Are you aware of placement new and placement delete? These can be used to invoke constructor/desctructor code, while the use of malloc/free (or similar functions) are just for the allocations.
  13. @OP that's a lot of code! Maybe it would be simpler to use malloc/free and perform your own alignment? Here was my strategy for 16 byte aligned allocations: https://github.com/RandyGaul/tinyheaders/blob/master/tinysound.h#L475-L490 static void* malloc16( size_t size ) { void* p = malloc( size + 16 ); if ( !p ) return 0; unsigned char offset = (size_t)p & 15; p = (void*)TS_ALIGN( p + 1, 16 ); *((char*)p - 1) = 16 - offset; TS_ASSERT( !((size_t)p & 15) ); return p; } static void free16( void* p ) { if ( !p ) return; free( (char*)p - (size_t)*((char*)p - 1) ); }
  14. When contact resolution fails

    It's not really a "physically based" phenomena. But the gist is to take the gradient from the constraint equation and use that as an orthogonal projection in terms of position. It's not physically based since this sort of post-project actually moves position, effectively doing work since the moment the position is moved the gradient changes. Whereas constraints apply velocities that fall under the principle of virtual work at an instant of time. In laymen's terms: take the direction velocity would be applied and do a position update instead!
  15. Collision Detection - why GJK?

    For spheres there were probably flaws in your implementation. Unfortunately most resources on GJK in existence are numerically unstable and don't actually perform well for robust collision detection, your linked article included. Every single resource I've been able to find has been quite flawed except for Erin's GDC lecture. I've heard positive things about Gino's book, but I myself haven't read it.