Search found 22 matches

by gino
Wed May 10, 2017 8:23 am
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Johnson's distance algorithm: can't find smallest simplex
Replies: 4
Views: 40283

Re: Johnson's distance algorithm: can't find smallest simple

Hi Gino, At this point I'm thinking of doing as suggested by Christer in his book, checking the origin against the Voronoi regions of the simplex and choosing the closest feature that way. While mathematically equivalent to Johnson's algorithm, a number of people have said it can help alleviate num...
by gino
Sun May 07, 2017 7:56 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Johnson's distance algorithm: can't find smallest simplex
Replies: 4
Views: 40283

Re: Johnson's distance algorithm: can't find smallest simple

Hi Adrian, I haven't checked your code so I cannot tell whether there is a bug in there. I do know that due to rounding issues it can happen that no proper simplex is found. In fact, the original paper by Gilbert Johnson and Keerthi already mentions the issue and offers a solution in form of backup ...
by gino
Sun Dec 07, 2014 11:02 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Continuous GJK for spherically extended objects
Replies: 1
Views: 6486

Re: Continuous GJK for spherically extended objects

Is there a way to perform a ray cast as described in Gino Van Den Bergen's Ray Casting against General Convex Objects , against spherically extended objects without having to calculate support points for the enlarged objects? With GJK you can adjust the termination condition to account for the slig...
by gino
Tue Jun 23, 2009 2:01 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Bullet's Voronoi Simplex Solver
Replies: 46
Views: 127826

Re: Bullet's Voronoi Simplex Solver

What you are suggesting is when only polytopes are used, you can do without the closest point computation, or at least you can skip all intermediate closest point computations and keep only the final one. Termination can be governed by detection of a repeated support point (vertex of the CSO, not ve...
by gino
Thu Mar 12, 2009 10:43 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Expanding Polytope Algorithm
Replies: 2
Views: 5945

Re: Expanding Polytope Algorithm

In principle, your approach could work for a pair of convex polytopes. However, since the boundary of the configuration space obstacle (Minkowski difference) of the polytopes may contain quadrilaterals it could very well happen that EPA cycles between two (or more) faces. Progressive growth of the e...
by gino
Tue Jun 12, 2007 1:00 pm
Forum: Links, Papers, Libraries, Demos, Movies, Comparisons
Topic: Rotational penetration depth
Replies: 5
Views: 10996

Re: EPA and PD^g

We claimed that the EPA is not exact in the following sense (neither do ours, DEEP): 1) It is not an analytical solution so that it cannot provide all PD solutions; e.g. imagine a sphere overlapped with itself; it has an infinite # of solutions to report, which the EPA cannot. 2) The result of EPA ...
by gino
Tue Apr 11, 2006 9:02 am
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Contact Manifold Generation: A question about GJK
Replies: 16
Views: 52911

Taking the closest features of the last-found simplices (sets of support points) for the two objects tested using GJK gives you a rough approximation of the contact manifold but you can do better, since (a) this simplex is usually not the complete manifold and (b) it is not necessarily a face of the...
by gino
Sun Mar 19, 2006 6:19 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Computing distance
Replies: 6
Views: 10209

Re: Computing distance

Hi! Anyone know of algorithm that compute the distances between two bodies as well as the penetration depth? Could I modify Bullet to get the distances? I need that distance because some time steppers use "prevent penetration" not "penetration correction" approach, so the distan...
by gino
Mon Feb 06, 2006 12:24 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Gino's Book - Robustness section
Replies: 4
Views: 9150

Using exact arithmetic sub would be 4e-8 but with floating-point arithmetic it is quite far from it ( see above ). So, I guess that this turned out to be a catastrophic cancellation situation because both results ( from floating-point and exact arithmetic ) don't have any digits in common, therefor...
by gino
Fri Feb 03, 2006 4:20 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Gino's Book - Robustness section
Replies: 4
Views: 9150

Re: Gino's Book - Robustness section

So, from page 59 I'm not understanding what Gino is trying to explain in the phrase that starts with "Assume". Hope that helps to clarify what's meant. Well put. Thanks Christer. The only thing I'd like to add is that computations would still classify as 'fairly accurate' if |ei| <= C * u...
by gino
Wed Nov 23, 2005 8:18 am
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Kinetic Sweep and Prune
Replies: 8
Views: 23391

The kinetic sweep and prune method, however, seems to maintain a consistent motion description, whereas in the 4D broad phase from my presentation the new target positions are set for each moving object in each time step. That's interesting... we don't need/use time steps, though we permit them if ...
by gino
Tue Nov 22, 2005 3:05 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Kinetic Sweep and Prune
Replies: 8
Views: 23391

For multi-body continuous motion Gino presented the 4D SAP Broadphase, please read page 47 and onwards in this presentation: https://www.cmpevents.com/Sessions/GD/ContinuousCollisionDetection1.ppt - How does the Kinetic Sweep and Prune compare to this 4D SAP Broadphase? At first glance they seem si...
by gino
Tue Oct 11, 2005 9:17 am
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Barycentric coordiantes and voronoi solver
Replies: 8
Views: 15608

Re: Barycentric coordiantes and voronoi solver

Which GJK implementation requires more information from the simplex solver, and how does it use this exactly, JMC ? Erwin The whole reason I brought this up was because SOLID uses the values even in the case that the simplex is full. Look at SOLIDs common_point and closest_points in DT_Convex.cpp. ...
by gino
Tue Oct 04, 2005 3:44 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Questions for Gino about your book
Replies: 3
Views: 8714

4) Could you describe the is_affinely_dependant test, and why you added that to your code. It isn't mentioned in the book at all. Thanks This test checks whether the current simplex W cup { w } has a zero "volume". Here "volume" means length (line segment), area (triangle) or vo...
by gino
Tue Oct 04, 2005 3:35 pm
Forum: Research and development discussion about Collision Detection and Physics Simulation
Topic: Questions for Gino about your book
Replies: 3
Views: 8714

Re: Questions for Gino about your book

I've compared your implementation of ISA-GJK in Solid 3.5.4 vs. the pseudo code you give in your book, and I have a few questions: 1) In the pseudo code, there is a check if the new support point is a member of the current simplex, but in your code you don't actually check for that, you only do in ...