Jump to content
  • Advertisement

DrDeath3191

Member
  • Content Count

    38
  • Joined

  • Last visited

Community Reputation

113 Neutral

About DrDeath3191

  • Rank
    Member

Personal Information

  • Role
    Programmer
  • Interests
    Art
    Programming

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. DrDeath3191

    Continuous GJK for Linear Translations

    I looked a bit further into Erin's code. After plugging in my values (and unfortunately finding the same inaccuracy), I looked in the main method and found a variable called 'shouldBeZero'. As you can probably guess by the fact I'm bringing it up, it isn't. It evaluates to 3.24570510e-06. I'm hoping beyond hope that this means there is an issue I can actually fix, rather than having the TOI solver just randomly fail on occasion. It does seem weird that I'm having these issues with such small values. For reference, I am reproducing this issue by performing GJK on a point at (835.0f, 445.0f) and a line segment from (895.0f, 425.0f) to (895.0f, 475.0f). I realize the further you get from 0 the more inaccurate things get, but I thought it would take more. Especially since this algorithm seems commonly used. This issue is turning into a bit of a show-stopper right now; if just the distance were slightly off I think I could somewhat manage. The direction being off just breaks everything, though. I suppose I could just put the tolerance to 1.0 or something, but that seems rather excessive. I'm just not entirely sure how I can progress at this time.
  2. DrDeath3191

    Continuous GJK for Linear Translations

    You say 'you suspect'; have you not had issues with this sort of thing in your implementations? Well, the issue is not strictly with collisions; it appears that the witness points were slightly off to start, throwing the entire TOI solver off. Which is weird, because the case I'm testing right now is two 2D axis aligned squares, one moving horizontally into the other. There should be no y difference in the witness points at all, and yet one arrives out of thin air. It's minuscule, but enough to break everything. No sources I can find online mention anything about improving numeric stability in this algorithm, so I am currently at a bit of a loss. It is possible I'm just screwing up something very subtle, but I look at all publicly available implementations of GJK I can find, and I don't see any sort of fudging or tricks with regards to barycentric coordinates stuff.
  3. DrDeath3191

    Continuous GJK for Linear Translations

    Does it? Looking over the c2GJK method, I only see 'snapping' when the variable hit is non-zero (which only occurs if the simplex is a triangle) or if you're using radii and the distance is less than their sum (I'm having enough trouble with cubes and rectangles, thanks). So if the origin were to lie on a 2-simplex in your case, the precision may get a little screwy. I'm testing the TOI solver in the 2D case, and it seems to be having that issue; a mysterious inaccuracy of something in the vicinity of 3.05176e-05 in a direction perpendicular to the velocity, specifically when evaluating witness points on a 2-simplex. Checking if the velocity bound is zero and breaking out works for this situation, but unfortunately would cause the algorithm to return a false positive in the case where the shape really is moving perpendicular to the other shape's witness point. In a bit of messing around, I changed the grouping of multiplications when calculating witness points. It worked for the case I was testing, but made it break in other cases. That leads me back to the floating point precision theory and the depths of madness. You're clearly more experienced with this particular algorithm than I am; if you believe you can reduce your tolerance below 1.0e-5 (which I am using based on your example), there must be something I am missing to make this thing more numerically stable. Or perhaps I'm just not recognizing the 'snapping' code that you mentioned earlier.
  4. DrDeath3191

    Continuous GJK for Linear Translations

    Yes, your implementation certainly does that when it returns from the tetrahedral case. If, however, the origin were enclosed within a triangle they are not set to be explicitly equal, which could lead to error. Unless of course I'm missing something. And these may or may not be leading to issues with the TOI solver; I noticed in yours you never check for the velocity bound being 0. In a test case I'm running, what appears to be the correct time is found in the first iteration, then the small amount of distance between my witness points happens to be perpendicular to my velocity vector, leading to the following delta value being infinity. If I check for the velocity bound being 0 and exit out (or reduce my accuracy) your TOI solver works wonderfully (thanks so much for that resource), but I can't help but feel that this shouldn't be happening in the first place. Thanks again for all your help so far; I'd really be lost in the weeds without you!
  5. DrDeath3191

    Continuous GJK for Linear Translations

    Nothing super major to report, I am just curious about this point: Given that you felt the need to bold this sentence and asterisk the word disjoint, am I to infer that the distance version of this algorithm is not reliable for determining intersections as well? I was messing around and noticing that indeed it appears in certain circumstances to report a distance ever so slightly greater than zero while intersecting. I assume this is likely due to floating point error, but it would make me feel more comfortable knowing that for sure. If it is the case that it isn't reliable for that, I can just use the bastardized version for checking that prior to a full-on distance check. I just want to be sure I'm not overlooking something.
  6. DrDeath3191

    Continuous GJK for Linear Translations

    FUN FACT OF THE DAY When you swap around your vertices, it's probably a good idea to swap around the shape indices as well! Otherwise you risk looking and feeling incredibly stupid. So, suffice it to say, the 2D case is working now. Let's see if it fixes the 3D case. EDIT: Yes it does! I am so mad at myself. Time to look at that TOI solver after I cool off.
  7. DrDeath3191

    Continuous GJK for Linear Translations

    Thank you very much, I'll look into it later. Unfortunately I have to get the full GJK algorithm working before moving on to that. This has proven more difficult than I thought. I am using a couple of sources (including some old code of yours, Randy); I thought I had everything down correctly, but the calculated witness points are just entirely wrong most of the time. I have been bashing my head into the monitor to see where I screwed up, and I just cannot see it. This has been driving me mad for the last couple of days, so if someone could take a quick (well, as quick as your can given the code's length) glance at my code and see where I made an error, I would be quite pleased. Thank you for all your help, I really do appreciate it. Resource 1: https://gist.github.com/vurtun/29727217c269a2fbf4c0ed9a1d11cb40#file-gjk-c Resource 2: https://bitbucket.org/rgaul/lm/src/806fe4427db32f98e514c646b51f99ce1cfc5c14/src/lm/collision/query/lmDistance.cpp?at=default&amp;fileviewer=file-view-default My Code (Again, apologies for the length, but GJK is very wordy): #include <array> #include "GJKSolver.h" struct GJKSimplexStruct { std::array<glm::vec3, 4> verts{ glm::vec3(0.0f) }; std::array<size_t, 4> indicesA{ 0 }; std::array<size_t, 4> indicesB{ 0 }; std::array<float, 4> barycentricValues{ 1.0f }; size_t size = 0; glm::vec3 witnessA; glm::vec3 witnessB; float distance = std::numeric_limits<float>::max(); }; GJKSolver::GJKSolver() { } GJKSimplexStruct GJKSolver::solveDistance(glm::vec3* vertsA, glm::vec3* vertsB, size_t sizeA, size_t sizeB) { GJKSimplexStruct simplex; float GJK_EPSILON = std::numeric_limits<float>::epsilon(); glm::vec3 searchDirection = glm::vec3(1.0f, 0.0f, 0.0f); //get our first simplex point size_t indexA = supportIndex(searchDirection, vertsA, sizeA); size_t indexB = supportIndex(-searchDirection, vertsB, sizeB); glm::vec3 newPoint = vertsA[indexA] - vertsB[indexB]; //add first vertex to simplex simplex.indicesA[simplex.size] = indexA; simplex.indicesB[simplex.size] = indexB; simplex.barycentricValues[simplex.size] = 1.0f; simplex.verts[simplex.size] = newPoint; simplex.size++; float sqDistance = glm::dot(newPoint, newPoint); //16 is my arbitrary limit on the number of iterations for (int i = 0; i < 16; i++) { GJKSimplexStruct previousSimplex = simplex; //find the closest region on the simplex to the origin and remove //vertices that do not contribute switch (simplex.size) { //POINT CASE case 1: //only one point, clearly the point itself is closest break; //LINE CASE case 2: { glm::vec3 ab = simplex.verts[0] - simplex.verts[1]; glm::vec3 ba = simplex.verts[1] - simplex.verts[0]; float u = glm::dot(simplex.verts[1], ba); float v = glm::dot(simplex.verts[0], ab); if (v <= 0.0f) { //Region A simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } if (u <= 0.0f) { //Region B simplex.verts[0] = simplex.verts[1]; simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } //Region AB simplex.barycentricValues[0] = u; simplex.barycentricValues[1] = v; simplex.size = 2; break; } //TRIANGLE CASE case 3: { glm::vec3 ab = simplex.verts[0] - simplex.verts[1]; glm::vec3 ba = simplex.verts[1] - simplex.verts[0]; glm::vec3 bc = simplex.verts[1] - simplex.verts[2]; glm::vec3 cb = simplex.verts[2] - simplex.verts[1]; glm::vec3 ca = simplex.verts[2] - simplex.verts[0]; glm::vec3 ac = simplex.verts[0] - simplex.verts[2]; float u_ab = glm::dot(simplex.verts[1], ba); float v_ab = glm::dot(simplex.verts[0], ab); float u_bc = glm::dot(simplex.verts[2], cb); float v_bc = glm::dot(simplex.verts[1], bc); float u_ca = glm::dot(simplex.verts[0], ac); float v_ca = glm::dot(simplex.verts[2], ca); if (v_ab <= 0.0f && u_ca <= 0.0f) { //Region A simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } if (u_ab <= 0.0f && v_bc <= 0.0f) { //Region B simplex.verts[0] = simplex.verts[1]; simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } if (u_bc <= 0.0f && v_ca <= 0.0f) { //Region C simplex.verts[0] = simplex.verts[2]; simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } //calculate fractional area glm::vec3 n = glm::cross(ba, ca); float u_abc = glm::dot(glm::cross(simplex.verts[1], simplex.verts[2]), n); float v_abc = glm::dot(glm::cross(simplex.verts[2], simplex.verts[0]), n); float w_abc = glm::dot(glm::cross(simplex.verts[0], simplex.verts[1]), n); if (u_ab > 0.0f && v_ab > 0.0f && w_abc <= 0.0f) { //Region AB simplex.barycentricValues[0] = u_ab; simplex.barycentricValues[1] = v_ab; simplex.size = 2; break; } if (u_bc > 0.0f && v_bc > 0.0f && u_abc <= 0.0f) { //Region BC simplex.verts[0] = simplex.verts[1]; simplex.verts[1] = simplex.verts[2]; simplex.barycentricValues[0] = u_bc; simplex.barycentricValues[1] = v_bc; simplex.size = 2; break; } if (u_ca > 0.0f && v_ca > 0.0f && v_abc <= 0.0f) { //Region CA simplex.verts[1] = simplex.verts[0]; simplex.verts[0] = simplex.verts[2]; simplex.barycentricValues[0] = u_ca; simplex.barycentricValues[1] = v_ca; simplex.size = 2; break; } //Region ABC simplex.barycentricValues[0] = u_abc; simplex.barycentricValues[1] = v_abc; simplex.barycentricValues[2] = w_abc; simplex.size = 3; break; } //TETRAHEDRON CASE case 4: { glm::vec3 ab = simplex.verts[0] - simplex.verts[1]; glm::vec3 ba = simplex.verts[1] - simplex.verts[0]; glm::vec3 bc = simplex.verts[1] - simplex.verts[2]; glm::vec3 cb = simplex.verts[2] - simplex.verts[1]; glm::vec3 ca = simplex.verts[2] - simplex.verts[0]; glm::vec3 ac = simplex.verts[0] - simplex.verts[2]; glm::vec3 db = simplex.verts[3] - simplex.verts[1]; glm::vec3 bd = simplex.verts[1] - simplex.verts[3]; glm::vec3 dc = simplex.verts[3] - simplex.verts[2]; glm::vec3 cd = simplex.verts[2] - simplex.verts[3]; glm::vec3 da = simplex.verts[3] - simplex.verts[0]; glm::vec3 ad = simplex.verts[0] - simplex.verts[3]; float u_ab = glm::dot(simplex.verts[1], ba); float v_ab = glm::dot(simplex.verts[0], ab); float u_bc = glm::dot(simplex.verts[2], cb); float v_bc = glm::dot(simplex.verts[1], bc); float u_ca = glm::dot(simplex.verts[0], ac); float v_ca = glm::dot(simplex.verts[2], ca); float u_bd = glm::dot(simplex.verts[3], db); float v_bd = glm::dot(simplex.verts[1], bd); float u_dc = glm::dot(simplex.verts[2], cd); float v_dc = glm::dot(simplex.verts[3], dc); float u_ad = glm::dot(simplex.verts[3], da); float v_ad = glm::dot(simplex.verts[0], ad); if (v_ab <= 0.0f && u_ca <= 0.0f && v_ad <= 0.0f) { //Region A simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } if (u_ab <= 0.0f && v_bc <= 0.0f && v_bd <= 0.0f) { //Region B simplex.verts[0] = simplex.verts[1]; simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } if (u_bc <= 0.0f && v_ca <= 0.0f && u_dc <= 0.0f) { //Region C simplex.verts[0] = simplex.verts[2]; simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } if (u_bd <= 0.0f && v_dc <= 0.0f && u_ad <= 0.0f) { //Region D simplex.verts[0] = simplex.verts[3]; simplex.barycentricValues[0] = 1.0f; simplex.size = 1; break; } //calculate fractional area glm::vec3 n = glm::cross(da, ba); float u_adb = glm::dot(glm::cross(simplex.verts[3], simplex.verts[1]), n); float v_adb = glm::dot(glm::cross(simplex.verts[1], simplex.verts[0]), n); float w_adb = glm::dot(glm::cross(simplex.verts[0], simplex.verts[3]), n); n = glm::cross(ca, da); float u_acd = glm::dot(glm::cross(simplex.verts[2], simplex.verts[3]), n); float v_acd = glm::dot(glm::cross(simplex.verts[3], simplex.verts[0]), n); float w_acd = glm::dot(glm::cross(simplex.verts[0], simplex.verts[2]), n); n = glm::cross(bc, dc); float u_cbd = glm::dot(glm::cross(simplex.verts[1], simplex.verts[3]), n); float v_cbd = glm::dot(glm::cross(simplex.verts[3], simplex.verts[2]), n); float w_cbd = glm::dot(glm::cross(simplex.verts[2], simplex.verts[1]), n); n = glm::cross(ba, ca); float u_abc = glm::dot(glm::cross(simplex.verts[1], simplex.verts[2]), n); float v_abc = glm::dot(glm::cross(simplex.verts[2], simplex.verts[0]), n); float w_abc = glm::dot(glm::cross(simplex.verts[0], simplex.verts[1]), n); if (w_abc <= 0.0f && v_adb <= 0.0f && u_ab > 0.0f && v_ab > 0.0f) { //Region AB simplex.barycentricValues[0] = u_ab; simplex.barycentricValues[1] = v_ab; simplex.size = 2; break; } if (u_abc <= 0.0f && w_cbd <= 0.0f && u_bc > 0.0f && v_bc > 0.0f) { //Region BC simplex.verts[0] = simplex.verts[1]; simplex.verts[1] = simplex.verts[2]; simplex.barycentricValues[0] = u_bc; simplex.barycentricValues[1] = v_bc; simplex.size = 2; break; } if (v_abc <= 0.0f && w_acd <= 0.0f && u_ca > 0.0f && v_ca > 0.0f) { //Region CA simplex.verts[1] = simplex.verts[0]; simplex.verts[0] = simplex.verts[2]; simplex.barycentricValues[0] = u_ca; simplex.barycentricValues[1] = v_ca; simplex.size = 2; break; } if (v_cbd <= 0.0f && u_acd <= 0.0f && u_dc > 0.0f && v_dc > 0.0f) { //Region DC simplex.verts[0] = simplex.verts[3]; simplex.verts[1] = simplex.verts[2]; simplex.barycentricValues[0] = u_dc; simplex.barycentricValues[1] = v_dc; simplex.size = 2; break; } if (v_acd <= 0.0f && w_adb <= 0.0f && u_ad > 0.0f && v_ad > 0.0f) { //Region AD simplex.verts[1] = simplex.verts[3]; simplex.barycentricValues[0] = u_ad; simplex.barycentricValues[1] = v_ad; simplex.size = 2; break; } if (u_cbd <= 0.0f && u_adb <= 0.0f && u_bd > 0.0f && v_bd > 0.0f) { //Region BD simplex.verts[0] = simplex.verts[1]; simplex.verts[1] = simplex.verts[3]; simplex.barycentricValues[0] = u_bd; simplex.barycentricValues[1] = v_bd; simplex.size = 2; break; } //calculate fractional volume (keeping in mind some of these may //be negative) float denom = glm::dot(glm::cross(cb, ab), db); float volume = denom == 0.0f ? 1.0f : 1.0f / denom; float u_abcd = glm::dot(glm::cross(simplex.verts[2], simplex.verts[3]), simplex.verts[1]) * volume; float v_abcd = glm::dot(glm::cross(simplex.verts[2], simplex.verts[0]), simplex.verts[3]) * volume; float w_abcd = glm::dot(glm::cross(simplex.verts[3], simplex.verts[0]), simplex.verts[1]) * volume; float x_abcd = glm::dot(glm::cross(simplex.verts[1], simplex.verts[0]), simplex.verts[2]) * volume; if (x_abcd <= 0.0f && u_abc > 0.0f && v_abc > 0.0f && w_abc > 0.0f) { //Region ABC simplex.barycentricValues[0] = u_abc; simplex.barycentricValues[1] = v_abc; simplex.barycentricValues[2] = w_abc; simplex.size = 3; break; } if (u_abcd <= 0.0f && u_cbd > 0.0f && v_cbd > 0.0f && w_cbd > 0.0f) { //Region CBD simplex.verts[0] = simplex.verts[2]; simplex.verts[2] = simplex.verts[3]; simplex.barycentricValues[0] = u_cbd; simplex.barycentricValues[1] = v_cbd; simplex.barycentricValues[2] = w_cbd; simplex.size = 3; break; } if (v_abcd <= 0.0f && u_acd > 0.0f && v_acd > 0.0f && w_acd > 0.0f) { //Region ACD simplex.verts[1] = simplex.verts[2]; simplex.verts[2] = simplex.verts[3]; simplex.barycentricValues[0] = u_acd; simplex.barycentricValues[1] = v_acd; simplex.barycentricValues[2] = w_acd; simplex.size = 3; break; } if (w_abcd <= 0.0f && u_adb > 0.0f && v_adb > 0.0f && w_adb > 0.0f) { //Region ADB simplex.verts[2] = simplex.verts[1]; simplex.verts[1] = simplex.verts[3]; simplex.barycentricValues[0] = u_adb; simplex.barycentricValues[1] = v_adb; simplex.barycentricValues[2] = w_adb; simplex.size = 3; break; } //Region ABCD simplex.barycentricValues[0] = u_abcd; simplex.barycentricValues[1] = v_abcd; simplex.barycentricValues[2] = w_abcd; simplex.barycentricValues[3] = x_abcd; simplex.size = 4; break; } //error default: break; } //if we have a tetrahedron at this point, it means it encloses the origin; //we have an intersection if (simplex.size == 4) { break; } //find the closest point on our simplex to the origin float denom = 0.0f; for (size_t i = 0; i < simplex.size; i++) { denom += simplex.barycentricValues[i]; } denom = 1.0f / denom; glm::vec3 closestPoint; switch (simplex.size) { case 1: closestPoint = simplex.verts[0]; break; case 2: closestPoint = simplex.verts[0] * (denom * simplex.barycentricValues[0]) + simplex.verts[1] * (denom * simplex.barycentricValues[1]); break; case 3: closestPoint = simplex.verts[0] * (denom * simplex.barycentricValues[0]) + simplex.verts[1] * (denom * simplex.barycentricValues[1]) + simplex.verts[2] * (denom * simplex.barycentricValues[2]); break; case 4: closestPoint = simplex.verts[0] * (denom * simplex.barycentricValues[0]) + simplex.verts[1] * (denom * simplex.barycentricValues[1]) + simplex.verts[2] * (denom * simplex.barycentricValues[2]) + simplex.verts[3] * (denom * simplex.barycentricValues[3]); break; } //ensure we are actually getting closer to the origin float currentSqDistance = glm::dot(closestPoint, closestPoint); if (currentSqDistance > sqDistance) { break; } sqDistance = currentSqDistance; //get the new search direction glm::vec3 searchDirection; switch (simplex.size) { case 1: searchDirection = -simplex.verts[0]; break; case 2: { glm::vec3 ba = simplex.verts[0] - simplex.verts[1]; searchDirection = glm::cross(glm::cross(ba, -simplex.verts[0]), ba); break; } case 3: { searchDirection = glm::cross(simplex.verts[1] - simplex.verts[0], simplex.verts[2] - simplex.verts[0]); if (glm::dot(searchDirection, simplex.verts[0]) > 0) { searchDirection = -searchDirection; } } } //is this search direction numerically fit? //if this condition holds, it is likely the origin is on an edge //or triangle of the simplex. However, it could just be REALLY //close. if (glm::dot(searchDirection, searchDirection) < GJK_EPSILON * GJK_EPSILON) { break; } //calculate the next tentative simplex vertex using our search direction size_t indexA = supportIndex(searchDirection, vertsA, sizeA); size_t indexB = supportIndex(-searchDirection, vertsB, sizeB); glm::vec3 newPoint = vertsA[indexA] - vertsB[indexB]; //check for duplication; if we are revisiting a vertex already in //the simplex, then we won't be getting any closer bool duplicateFound = false; for (size_t j = 0; j < previousSimplex.size; j++) { if (indexA != previousSimplex.indicesA[j]) continue; if (indexB != previousSimplex.indicesB[j]) continue; duplicateFound = true; break; } if (duplicateFound) { break; } //add the current vertex to the simplex simplex.indicesA[simplex.size] = indexA; simplex.indicesB[simplex.size] = indexB; simplex.barycentricValues[simplex.size] = 1.0f; simplex.verts[simplex.size] = newPoint; simplex.size++; } //calculate witness points float denom = 0.0f; for (size_t i = 0; i < simplex.size; i++) { denom += simplex.barycentricValues[i]; } denom = 1.0f / denom; switch (simplex.size) { case 1: simplex.witnessA = vertsA[simplex.indicesA[0]]; simplex.witnessB = vertsB[simplex.indicesB[0]]; break; case 2: simplex.witnessA = vertsA[simplex.indicesA[0]] * (denom * simplex.barycentricValues[0]) + vertsA[simplex.indicesA[1]] * (denom * simplex.barycentricValues[1]); simplex.witnessB = vertsB[simplex.indicesB[0]] * (denom * simplex.barycentricValues[0]) + vertsB[simplex.indicesB[1]] * (denom * simplex.barycentricValues[1]); break; case 3: simplex.witnessA = vertsA[simplex.indicesA[0]] * (denom * simplex.barycentricValues[0]) + vertsA[simplex.indicesA[1]] * (denom * simplex.barycentricValues[1]) + vertsA[simplex.indicesA[2]] * (denom * simplex.barycentricValues[2]); simplex.witnessB = vertsB[simplex.indicesB[0]] * (denom * simplex.barycentricValues[0]) + vertsB[simplex.indicesB[1]] * (denom * simplex.barycentricValues[1]) + vertsB[simplex.indicesB[2]] * (denom * simplex.barycentricValues[2]); break; case 4: simplex.witnessA = vertsA[simplex.indicesA[0]] * (denom * simplex.barycentricValues[0]) + vertsA[simplex.indicesA[1]] * (denom * simplex.barycentricValues[1]) + vertsA[simplex.indicesA[2]] * (denom * simplex.barycentricValues[2]) + vertsA[simplex.indicesA[3]] * (denom * simplex.barycentricValues[3]); simplex.witnessB = simplex.witnessA; } simplex.distance = glm::distance(simplex.witnessA, simplex.witnessB); return simplex; } size_t GJKSolver::supportIndex(glm::vec3 searchDirection, glm::vec3* verts, size_t vertexCount) { if (vertexCount == 0) { return 0; } size_t maxIndex = 0; float maxProjection = glm::dot(verts[0], searchDirection); for (size_t i = 1; i < vertexCount; i++) { float currentProjection = glm::dot(verts[i], searchDirection); if (currentProjection > maxProjection) { maxProjection = currentProjection; maxIndex = i; } } return maxIndex; }
  8. DrDeath3191

    Continuous GJK for Linear Translations

    Well, I was also planning to venture into scaling objects as well; I figured with a ray-trace I could manipulate the velocity vector by the movement of the simplex's faces after scaling was applied. But seeing as the ray trace is more complicated than I thought and I have to do CA regardless, why not shoot for the stars at this point?
  9. DrDeath3191

    Continuous GJK for Linear Translations

    I was afraid of that. I was under the impression that a ray-cast against the CSO would be simpler than that considering rotation would not be applied. But if I'm going to go down the full CA route anyway, I guess I might as well handle rotational stuff as well. Thank you for the resources, I'll look into it.
  10. Hello everyone, Recently I have been revisiting my collision detection code. I was using axis-aligned bounding boxes before, which made continuous collision detection rather simple (If you're curious as to how I did that, here's a link to the article I read). However, I will have need to support different orientations and perhaps other shapes, so I clearly need to change what I am doing. I implemented the 'bastardized' version of the GJK algorithm the other day (article I based my implementation on); it's serving me quite well for discrete collisions. However, I need to be able to find the time of intersection for moving objects. The general theory should be the same as the link I included above for the AABB case; I want to perform a ray-cast against the Configuration Space Object of the two shapes of interest. I looked into the matter and found this paper. I found it entirely incomprehensible, and looked for further information, and I found this presentation made by the same man. It helped minimally. So I suppose I'm looking for a simpler explanation as to the differences between the discrete and continuous case, or perhaps even an example implementation of the ray-casting GJK algorithm. I know that I need to clip the vector representing my relative velocity and move the origin by the function mentioned in the slides (Slide 43-46), but when precisely do I do that? He mentions using the support planes as clipping planes; if he means the simplex, does that mean I only perform the clipping function when the simplex is a tetrahedron, as it is the only time the simplex would have such planes? Does he even mean the simplex in that regard? How would I calculate the v vector in the first place? I just find these explanations rather confusing, and unfortunately I have yet to find other options to help. Most articles about GJK focus on the discrete case, and the only information I found on ray-casting I have already included here. This topic seems complicated, so it is very likely I will have followup questions. Thank you for your assistance and patience.
  11. Yeah, I figured the hats would be safe. If people aren't bothered by that, it certainly makes my life easier. Thanks a lot! The GameController API is actually built on top of the Joystick API in SDL; it just has a database of recognized controllers whose axes and buttons it recognizes as "Left Analog X", "A Button", etc. So I could just access the mapping and treat it as a GameController with nothing lost. So using both or switching in the end would amount to the same thing, I think. Upon further thought, I think individual mappings per controller, rather than a generic mapping would probably be easier to handle and allow for more options. So with that I think all of my questions have been answered! Thanks to everyone for the help!
  12. Sorry for taking so long to get back to you guys on this. I think we may be having a miscommunication issue here. The issue isn't getting the inputs themselves, SDL has very nice functionality in regards to that. The issue is coming up with sensible defaults when I don't know what each button or axis is. Obviously, the correct solution for handling this is to allow users to remap their controls, which is simple enough to implement, but what if they want to use their newly plugged in joystick to navigate to that menu. If the joystick is recognized by SDL, I can refer to the mapping provided by it to create a sensible default. If it isn't, I can think of no other option than blatantly interrupting the player and saying "Hey, I don't know what this is, help me out." This may be the best solution, but I was hoping someone who had experience with this issue would provide a better option. Furthermore, should each joystick have an individual mapping, or not? I can imagine arguments being made for both cases, but again I'm not sure what players expect in terms of those options. For now, I'm just using the GameContoller API; it's simple enough and based on what I hear from this thread or other sources, it theoretically should not be too hard to switch to using the Joystick API.
  13. So, I am currently redesigning my input system to more easily allow for input mapping. In terms of mouse and keyboard, no issues there. However, I seem to be having a bit of trouble wrapping my head around what to do for controllers. I use SDL2 to read input events. SDL2 has 2 similar yet different APIs for controller input; the Joystick API and the GameController API. The Joystick API is very generic; it basically tells you how many buttons and axes the controller has, and leaves the rest for you to figure out. The GameController API is built on top of this system, but tries to map everything in a fashion similar to an XBox 360 controller, meaning that axes and buttons are fairly standardized, but this is only if the controller exists in SDL's database of known game controllers. I want to support as many control options as possible, while maximizing convenience for the players (and myself). Keeping that in mind, here are the questions I have regarding the design of the system: Should I actually bother using the Joystick API, or should I only accept GameControllers? The GameController API being standardized is certainly a strong positive, but this fundamentally limits the player's control options. As far as I understand the GameController API, it is strictly limited to mimicking a 360 controller. Meaning that if a controller is registered but has additional buttons or axes, I'm not sure how the API would handle it, or even if I would be allowed to use those. If I were to use the Joystick API, how would I handle things such as menu navigation? Joysticks are not in any way standardized, so I literally cannot tell up from right or what button should be the confirm button. I could have some sort of popup window forcing players to map those controls immediately, but that strikes me as intrusive and inelegant. This is not specifically SDL related necessarily, but should controllers that look similar have the same mappings? For example if a player has both a 360 controller and a DualShock, and he remaps controls on his 360 controller, should those carry over to the DualShock, or should they be treated separately? If so, this would seem to be a boon for using only the GameController API, but things like arcade sticks also can be considered GameControllers, it depends on if SDL2 recognizes it. In that case, would I try to treat the arcade stick GameController different than the first two, or just roll with the same mapping for all GameControllers? A lot of these questions come from my relative inexperience with PC gaming with a controller; I'm not entirely sure what players expect and demand from controller-related options. Any help you could provide would be greatly appreciated.
  14. So, it turns out I'm a bit of an imbecile. I was just telling you how chrono can use nanoseconds. I was using microseconds in the game. It appears to work now. Further testing will be required, no doubt. I'm just going to be in the idiot corner, hating myself.
  15. The chrono library's high_resolution_clock can get to nanosecond precision, so I'm not entirely convinced there's a problem there. As for the rest of your post; I must admit I'm having a little trouble understanding. It seems like way too much to accomplish something that should be so simple. However, from what I think I understand, you believe my server falls behind and continues to lose time in a downward spiral, right? However, that's not really what's happening: a frame arrives late, yes. But then it appears to correctly receive frames again for a few frames, then drops one again later, ad infinitum. In fact, after the initial failure, it fails again every 4 frames. A very distressing pattern. My interpolation buffer delays this for a bit, but that's all its done. Perhaps some sleep will help me piece it together.
  • 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!