• Advertisement

Randy Gaul

  • Content count

  • Joined

  • Last visited

Community Reputation

2773 Excellent


About Randy Gaul

  • Rank

Recent Profile Visitors

7765 profile views
  1. From OBB-OBB intersection test to Sweep OBB test?

    You cannot form a simple equation and solve it if your OBBs carry angular velocity. Otherwise, conceptually, finding a time of impact (TOI) along a given axis can be done by simple linear interpolation. For example, say we have a point A traveling along a velocity V at a plane P. It is possible to do: d0 = Distance(A, P); d1 = Distance(A + V * dt, P); Then d0 and d1 can be used to lerp from A to A * V + dt by forming the interpolant: d0 / (d0 - d1). The same concept can apply to any axis and any given point, even axes and points on the surface of OBBs.
  2. Seperating Axis 2D Projection Issue

    Oh no do not bother printing to console. Debug render with lines and points on the screen, just like you are rendering your boxes!
  3. Seperating Axis 2D Projection Issue

    Nice work, I'm surprised someone found your mistake! A little tidbit of advice: make sure to start debug rendering some of your inner calculations next time you write this kind of code. You can render transforms, planes, normals, points, projected points, etc. to make sure you are understanding the linear algebra.
  4. I dunno. Test it out and see which one is better.
  5. If you try passing a bunch of SSE types as parameters to a function you will seen find you need __vectorcall on MSVC. Your tutorial author may have been just avoiding this and using a pointer instead. Whether a function call will be better off passing SSE types as parameters, or with pointers, depends on the context. It is not a straight-forward answer, unless you're just passing one or two XMVECTOR, then doing this as a parameter on 64bit builds will be good since floating point operations are going to be done in SIMD registers anyways (so loads/stores are super cheap or sometimes non-existent).
  6. 2d Physics: Solving for 2 Contact Points

    Your solver currently treats each contact point in isolation. Given the first contact point is perfectly solved, the second contact point, once solved, invalidates the solution to the first, thus causing jitter. A very good way to reduce jitter is to implement an iterative solver where the various contact points communicate with one another to somehow converge upon an acceptable solution altogether. My personal favorite resource for learning one good solution is under GDC 2006 here: http://box2d.org/downloads/. Specifically this link to the powerpoint and this link to the demo code.
  7. rigid body fixed constraint

    Just want to point out I wrote that before I knew much calculus. Although I did get it working, I didn't test it out much and the results weren't all that great. So probably not a good idea to use my link as a reference
  8. I don't have experience specifically with continuous cloth detection, but what is preventing you from using a mixture of CCD and DCD? Typically the solver does not care about what kind of collision detection is used, and can be black boxed from a collision detection point of view. Depending on your use case there can be many ways to simplify the collision detection. Maybe ray to triangle is not the best option, especially since rays can shoot through vertices or edges in your cloth mesh. Also your point, as represented by a ray, may not make sense either unless it strictly travels along a line over the given timestep.
  9. High Speed Collision Detecting in Super M

    To me it sounds like you should implement a different collision strategy. The points strategy you have so far works well if you are using a tile grid, and you limit speeds so that objects can not *tunnel* (a link on tunneling) through one another. But, since you want to have faster speeds, you need a new strategy that can cope with tunneling easily. First I would try representing your box not as four points, but as a full 2D area, implicitly defined by a point + width and height (or some similar format). This will prevent the possibility of your box points from straddling a skinny wall. Next, you need to figure out a way to find the time of impact, of when your box will collide between two game ticks. Implementing time of impact solvers is typically quite difficult. Your best bet would be to try a binary search algorithm. Here is a link: http://digitalrune.github.io/DigitalRune-Documentation/html/138fc8fe-c536-40e0-af6b-0fb7e8eb9623.htm#Bisection
  10. You can try Bounce if you didn't like PhysX: https://github.com/irlanrobson/bounce
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  • Advertisement