RE: [Algorithms] GJK termination

[Gino v. d. B. <gva...@pl...>]

w * v / |w| does not have to be monotonic, so you 'll end up a lot of =
times with a nonoptimal distance.
=20
Gino=20


  _____ =20

	From: gda...@li... =
[mailto:gda...@li...] On Behalf Of Petr =
Sovis
	Sent: Sunday, April 10, 2005 2:48 PM
	To: gda...@li...
	Subject: Re: [Algorithms] GJK termination
=09
=09
	Hi,=20
	the algorithm itself is realy SOLID :), I don't use check if |v| is =
small or if w lies in wlast direction. Instead this I use:
	=20
	normal distance ( w * v / |w| =3D distance ) of line segment =
(plane,hyperplane) to zero point should always be lower then distance in =
last step. so I check if it's really lower. if not -> exit like objects =
are disjoint (or joint if you want to) because this happens only in =
small distance/penetration cases. This check can be done in very =
efficient way.=20
	=20
	wlast * vlast  / |wlast| < w * v / |w|=20
	(wlast * vlast )^2 * (|w|^2) <  (w * v)^2 * wlast|^2)=20
	=20
	important: check if (w * v) / |w| is bigger than some error - not zero! =

	=20
	P.S.this issue is not caused by instability of the algorithm but by =
instability of float/double math -> support function where could be =
division, sqrt=20
	P.S.S. hope it help otherwise sorry for mislead=20
	=20
	regards
	  Petr
	=20
	----- Original Message -----=20

		From: Andreas Brinck <mailto:And...@me...> =20
		To: gda...@li... ; =
gda...@li...=20
		Sent: Sunday, April 10, 2005 2:02 PM
		Subject: RE: [Algorithms] GJK termination

		Hi,
		=20
		I'm doing a 2D implementation so W.size() <=3D 2.
		=20
		I've implemented all of the fixes from Ginos paper but the algorithm =
still doesn't terminate. However, if I replace the termination =
condition:
		=20
		if w_k belongs to W_(k-1) U {w_(k-1)} then return
		=20
		with a check if w_k is equal to _any_ previous w (as you suggested) =
then the algorithm seems to terminate.
		=20
		I'm a little disappointed with the algorithm in general, it feels very =
frail, even if you manage to get it right.
		=20
		/A.B.

  _____ =20

		Fr=E5n: gda...@li... genom Dave Moore
		Skickat: fr 2005-04-08 16:58
		Till: gda...@li...
		=C4mne: Re: [Algorithms] GJK termination
	=09
	=09

		On Apr 8, 2005 5:13 AM, Andreas Brinck <And...@me...> =
wrote:=20
		> quick question: is it normal for the unmodified GJK algorithm to =
fail to=20
		> terminate if the two objects are intersecting?=20

		  What are W_k and v in your app (using the terminology from the van=20
		den Bergen paper) when the alg fails to terminate?=20
		  On convex polyhedra, GJK should always terminate in a finite number=20
		of steps, intersecting or not, but there are a couple FP accuracy=20
		issues to watch out for.  Off the top of my head: (check the vdB paper =

		or freesolid for a comprehensive list)=20
		  - (|v| > epsilon) due to inaccuracy in the convex combination of the =

		support set=20
		  - new support cycling between two points=20

		  If you're not terminating when size(W_k) =3D 4, you could add that=20
		condition, it's not foolproof, but it does catch many of the (|v| > e) =

		cases.  (You'll need to carefully set your epsilon value to catch all=20
		of these, which you should of course do anyways.)=20
		  For the cycling points, you'll need to check previous points that=20
		have been added to the W_k set to make sure that no w_k reappears.=20
		Other people should chime in here, I'm sure I've forgotten=20
		something... :)=20


		-------------------------------------------------------=20
		SF email is sponsored by - The IT Product Guide=20
		Read honest & candid reviews on hundreds of IT Products from real =
users.=20
		Discover which products truly live up to the hype. Start reading now.=20
		http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick=20
		_______________________________________________=20
		GDAlgorithms-list mailing list=20
		GDA...@li...=20
		https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list=20
		Archives:=20
		http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188=20

		###########################################
	=09
		This message has been scanned by F-Secure Anti-Virus for Microsoft =
Exchange.
		For more information, connect to http://www.f-secure.com/=20