• Advertisement


  • Content count

  • Joined

  • Last visited

Community Reputation

128 Neutral

About D956

  • Rank

Personal Information

  • Interests

Recent Profile Visitors

1971 profile views
  1. Character Solver

    I remember this post by you on the Bullet forums: I thought it sounded pretty good and was sad to see no physics talks at GDC 2016. Some topics I'm currently most interested in: Once I get this character controller stuff working properly I plan on looking into hull/mesh contacts with contact clustering and dealing with internal edges etc. Besides the character capsule, I'm currently only using convex polyhedra. Continous collision detection for small and/or fast moving objects. I've yet to seriously look into Catto's Bilateral Advancement algorithm. Block solvers. Haven't really looked into these much either. I see Erwin Coumans did a talk on MCLP solvers at GDC 2014.
  2. How to learn the math necessary?

  3. Character Solver

    Thanks for the tip, Dirk. Are there any physics talks planned for the next GDC? For anyone else implementing a character controller as described above, the following paper on avoiding the "fear of the wireframe" problem is pretty good: http://www.codercorner.com/MeshContacts.pdf Now I just have to look into modifying my GJK implementation to return feature IDs/types.
  4. C++ C++ IDE for Linux

    https://kate-editor.org/ It has plugins for GDB, projects and symbols. Although I don't really use those features. I've never really cared for IDEs.
  5. Character Solver

    Thanks for your advice. I will experiment and see what works best. Right now I'm only doing discrete collision detection using GJK and then plane solve. The next step is to add conservative advancement, which should be very straightforward. I'll also have to add a separating axis test for when the capsule's segment penetrates a polygon/object.
  6. 3 plane intersection and cross product question

    Have you solved it already? I just derived the plane intersection math myself and I see nothing wrong with your code except that the original GetIntersection function only divides cross(n1, n2) by denom, which is incorrect and probably a typo? So I think your bug(s) is/are located elsewhere.
  7. Character Solver

    I found this post by you: https://forums.tigsource.com/index.php?topic=51779.msg1203653#msg1203653 Isn't this pretty much Catto's algorithm outlined above?
  8. Character Solver

    Thank you very much for replying! I've been googling some more and came across documentation for the DigitalRune project (link). They also use a capsule shape and do a similar plane solve as Erin Catto describes. This is how they describe their position correction: This is very similar to Erin Catto's approach, except that Catto adds a "shape cast". So the game code decides it wants to move the player from the "initial position" to the "target position", then: DigitalRune algorithm: Clear the plane list. Detect collisions at the target position and collect bounding planes. If we don't find any collisions we are done. Plane solve to get a new target position. Go back to step 1. Erin Catto's algorithm as I now interpret it: Clear the plane list. Detect collisions at the target position and add bounding planes to the plane list. Plane solve to get the first solve position (target position -> solve position). Clear the plane list. Perform a shape cast from the initial position to the solve position. Set the target position to the shape cast position. Detect collisions at the target position and add bounding planes to the plane list. Plane solve to get a new solve position (target position -> solve position). If the distance between the new solve position and the old one is within some epsilon we are done. Otherwise go back to step 4. Erin Catto has as a first step "I first scan the environment for any overlaps". I assume he means the target position. It seems the plane solver is pretty much the same in both algorithms. I have attached a new test program. ESC to quit, arrow keys to move the circle. Seems to work fine, except I am currently not doing the shape cast. I guess the shape cast is there in case the plane solver moves past an object/polygon that wasn't detected during steps 2 & 7. As for the overcompensation; I will look into using normal averaging. Right now I simply use the normalised direction from the closest point on the segment to the circle centre as normal, which seems to work fine. Now I just have to implement it in my 3D game/engine and see how well it works there. test2.c
  9. Character Solver

    One solution to issue 4 is to collect polygons instead of only their planes. Then, during the position correction step I find the polygon with the smallest penetration that is still in front of the capsule and move the capsule in front of it's plane. Of course this leads to other problems... Catto doesn't mention any of this though, so I wonder if there's a trick to the algorithm so I only have to use planes.
  10. Character Solver

    The way I am reading the slides is that the algorithm has two parts to it. One part collects contact planes using a shape cast and the other part is a plane solver (NGS) that tries to find the closest point (solve point) to the target position whilst satisfying the plane constraints. Part one is described on page 59: Part two, what you are referring to, is described on page 60: I know. "segment_closest_point" in my test program actually accounts for this by returning a vertex of the line segment if the proper barycentric coordinate is negative. I guess I wasn't clear enough. I am currently using an AABB and it is working fine with static geometry. Except that now I want to add dynamic rigid bodies. Realising I will have to deal with penetration anyway, I decided to ditch this method and change to a position-based solver using a capsule shape like the one described by Erin Catto in the presentation above.
  11. Character Solver

    So right now for my character solver I compute the time of impact of a character AABB and convex polygons using an algorithm based on "Robust Continuous Collision Detection Between Arbitrary Polyhedra Using Trajectory Parameterization of Polyhedral Features" by J.M.P van Waveren (link) Doom 3 uses this for all of it's collisions so it never has to deal with penetration. This seems undesireable for a couple of reasons so I've decided I'm going to switch to a position solver instead. After some googling I came across Erin Catto's 2014 GDC presention "Understanding Constraints" (link) where he briefly describes how his character solver works. I've written a simple C program (attached to this post) to play around with these concepts and I have some questions that hopefuly I will be able to get answered here. Keys for the test program: ESC - quit r - reset s - step 1-8 - switch to setup 1-8 Here's how I intepret the algorithm: Let's call the current position of the character the 'initial position'. This position never changes during the algorithm. Let's call the position we are trying to move the character to the 'target position'. This position also never changes during the algorithm. Scan the environment for overlap with the capsule at the initial position and construct a list of contact planes. Perform a plane solve on the target position to get the first solve position. Perform a shape cast from the initial position to the solve position. Move to the first hit point and collect new contact planes there. Add these new planes to the list. Perform a plane solve on the target position to get the next solve point. If the distance between the new solve point and the old one is within some epsilon, we are done. Otherwise go back to step 3. Plane solve code: vec3_t p = target_position; vec3_t a = p + local_capsule_a; vec3_t b = p + local_capsule_b; for(uint32_t i = 0; i < max_iter; i++) { vec3_t last_p = p; for(uint32_t j = 0; j < plane_count; j++) { const plane3_t &plane = planes[j]; float d1 = point_distance(plane, a); float d2 = point_distance(plane, b); float dist; if(d1 < d2) dist = d1; else dist = d2; dist -= capsule_radius; if(dist < 0.0f) { p -= dist * plane.n; a = p + local_capsule_a; b = p + local_capsule_b; } } vec3_t delta = p - last_p; if(dot(delta, delta) < epsilon) break; } solve_position = p; Couple of issues: 1. Is this interpretation correct? 2. In the test program I am only adding one new plane per shape cast, is there a reason to collect more (all touching planes)? 3. In the test program I am using the segment planes directly. In 3D I would directly use the polygon planes. If I use the direction from the closest point on the segment to the circle centre I get into situations like this, where the character ends up away from the collision geometry: 4. If I naively add all overlapping planes during step 1 I get into sitations like this: The green circle is at the source position. Step 1 will find both planes and the character will end up in the corner, not touching either segment. In the test program I solve this problem by clearing the plane list after step 2, but this is insufficient as I also need to select the proper planes after a shape cast. I can think of some approaches to solving this problem, but instead of experimenting right away, I'd like to know how other people have solved this. What is a good way to determine which planes to actually use? test.c
  12. Linked list adventure

    I did that exercise once, but not in this forum. OOP vs Procedural (C++ vs C). OO tends to be bigger, more abstract and with more indirection than the other. Anyway you won't convince OOP heads to stop doing that, to many books, to many class hours, to many effort invested in something that is supposedly better than everything else.   If anyone is fluent in Spanish I did a talk in EVA (Argentinian GDC) about how OOP isn't the right tool for games.     Reminds me of Brian Will's presentations: https://www.youtube.com/watch?v=QM1iUe6IofM https://www.youtube.com/watch?v=IRTfhkiAqPw https://www.youtube.com/watch?v=V6VP-2aIcSc   I also really like this presentation by Eskil Steenberg and agree with most of it: https://www.youtube.com/watch?v=443UNeGrFoM There's also this nice interview with him on the Handmade Dev show: https://vimeo.com/193290840
  13. It's definitely possible to be self-taught and successful. From people who dropped out of college (e.g. John Carmack) to people who never went to college (e.g. Casey Muratori) to people who didn't even finish high school (e.g. Mike Acton from Insomniac Games, Markus "Notch" Persson of Minecraft fame)   But of course having a degree always helps with getting hired and since you're over halfway there and you've already put in so much money, I'd say it's probably best if you continued and got that piece of paper.
  14. Moving Aabb Vs Tri/aabb/sphere Code

      We're talking about continuous collision detection here. And the reason I don't like capsules is because of this:       This is a terrible argument.     Here's Doom3's source code: https://github.com/id-Software/DOOM-3-BFG The collision detection stuff is all in "neo/cm" and the player physics code can be found in "neo/d3xp/physics/"
  15. Moving Aabb Vs Tri/aabb/sphere Code

      Care to elaborate on this? In my view having a flat bottom is definitely desirable. I'm using an AABB for player collision and it works great.   My implementation is based on some of the concepts laid out in the following paper about the collision detection in Doom 3 (although I don't use Plücker coordinates):   http://mrelusive.com/publications/papers/Robust-Continuous-Collision-Detection.pdf   And I combine it with removing a degree of freedom with every iteration as described in this paper:   https://arxiv.org/ftp/arxiv/papers/1211/1211.0059.pdf
  • Advertisement