You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 


1
(2) 
2

3
(1) 
4
(7) 
5
(3) 
6
(7) 
7
(1) 
8
(6) 
9
(17) 
10
(2) 
11
(7) 
12
(6) 
13

14

15
(6) 
16

17
(3) 
18
(4) 
19
(10) 
20
(2) 
21
(2) 
22
(24) 
23
(18) 
24

25
(3) 
26
(16) 
27
(1) 
28

29
(13) 
30
(9) 




From: PeterPike Sloan <ppsloan@wi...>  20041130 23:36:40

It's on my web page. There is also a paper on using this type of stuff for IK explicitly: "ArtistDirected Inverse Kinematic Using Radial Basis Function Interpolation", Rose et al Eurographics 2001. http://research.microsoft.com/~ppsloan/ The above paper does a couple of things, one is to use "pseudoexamples" (warping the basis functions associated with each animation effectively, but not introducing a new animation) to satisfy the IK constraints explicitly in the parameterization of the abstract space  ie: in your pointing example the abstract space could be a 2D plane (where the gun should point to), given a small number of examples, it would create basis functions for each example that when evaluated sum to 1 and at any location the gun should be pointing in the given direction (ie: just evaluating these basis functions makes everything work.) The idea of pseudo examples was developed more in the I3D paper  but it focused on shape and efficiency related issues more than animation. PeterPike Sloan (The knearest neighbor interpolants can sometimes be better behaved compared to the RBF stuff that we used, but I think there are scenarios where RBF's work quite well.) Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Alex Mohr Sent: Tuesday, November 30, 2004 3:01 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] calculating weights for blending arbitrary number of animations >I also saw a reference to another method called cardinal radial basis=20 >functions and a reference to a paper that I'm not able to find/download >on the web. SLOAN, P.P., ROSE, C., AND COHEN, M. F. 2001. Shape by example. >In Proceedings >of 2001 Symposium on Interactive 3D Graphics. > >Does anyone have a link? If I type 'shape by example' into google and hit "I'm feeling lucky", I get the pdf. Does this not work for you? Alex  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now.=20 http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Alex Mohr <amohr@cs...>  20041130 23:00:35

>I also saw a reference to another method called cardinal radial basis >functions and a reference to a paper that I'm not able to find/download on >the web. SLOAN, P.P., ROSE, C., AND COHEN, M. F. 2001. Shape by example. >In Proceedings >of 2001 Symposium on Interactive 3D Graphics. > >Does anyone have a link? If I type 'shape by example' into google and hit "I'm feeling lucky", I get the pdf. Does this not work for you? Alex 
From: Yordan Gyurchev <yordan@gy...>  20041130 22:05:56

Thanks for the paper. It references another paper: Articulated Body Deformation from Range Scan Data http://grail.cs.washington.edu/projects/digitalhuman/pub/allen02articulated.html Anyway they both apply the following formula: Wi = 1/(D(p,pi)  1/D(p,pk) where D is a distance function and p1... pk are the nearest pose parameters and p is the supplied new parameter. They also implied that Euclidian distance does the job. But I struggle to understand how this works when distance is 0 in either part of the binom... simply wont work. Its clear that I'm missing something. I also saw a reference to another method called cardinal radial basis functions and a reference to a paper that I'm not able to find/download on the web. SLOAN, P.P., ROSE, C., AND COHEN, M. F. 2001. Shape by example. In Proceedings of 2001 Symposium on Interactive 3D Graphics. Does anyone have a link? Yordan  Original Message  From: "Alex Mohr" <amohr@...> To: <gdalgorithmslist@...> Sent: Tuesday, November 30, 2004 7:38 PM Subject: Re: [Algorithms] calculating weights for blending arbitrary number of animations > This from SIGGRAPH last year may be relevant. Check the video, and I > believe the paper starting at section 4 would be most useful, but > reading the whole thing is probably worthwhile. > > http://www.cs.wisc.edu/graphics/Gallery/Kovar/ParamMotion/ > > Alex > > > >Hello, > > > >Imagine a soldier (or character with a weapon of some kind). We are tying > >to get its weapon (two weapons, two handed weapon) to point into the > >direction of aiming. > > > >We have 9 animations. Each represents a pose into a certain direction. Each > >"pose" animation has a vector associated with it. > >For a given character aiming direction vector we compute weight for each > >animation to contribute into the final anim. > > > >Question is: Given N (in this paricular case 9) vectors and the aiming one > >how to compute good weights that max to 1.0 when the aming coincides with > >them? (Did I mention that weights need to add up to 1.0? but of course you > >know that...) > > > >We have tried few methods and we have a couple of working but far from ideal > >bodged solutions. I'm sure someone has solved this problem elegantly with > >some clever maths. A lot of games seem to do that kind of thing although in > >some cases IK can be applied. > > > >One solution that gives smooth results is just a dot product. > > Wi = Vi dot Va where Wi are normalized afterwards with Wi = Wi/sum(Wi) (Wi > >weight for each bone, Vi  Direction vectors for anims, Va  aim vector) > >Unfortunately, this only works perfectly if all direction vectors (Vi) are > >perpendicular to each other so when they max out no other anim contributes > >to the final. It still works in other cases but the results are not accurate > >enough for us. > > > >We have also explored few solutions where assumptions have been made that > >some vectors lie in a certain plane but I'm looking for a generic solution > >that will work in all cases. > > > >Thanks, > >Yordan > > > > > > > > > > > >SF email is sponsored by  The IT Product Guide > >Read honest & candid reviews on hundreds of IT Products from real users. > >Discover which products truly live up to the hype. Start reading now. > >http://productguide.itmanagersjournal.com/ > >_______________________________________________ > >GDAlgorithmslist mailing list > >GDAlgorithmslist@... > >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > >Archives: > >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > >  > SF email is sponsored by  The IT Product Guide > Read honest & candid reviews on hundreds of IT Products from real users. > Discover which products truly live up to the hype. Start reading now. > http://productguide.itmanagersjournal.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > 
From: Jon Watte <hplus@mi...>  20041130 22:04:42

> Question is: Given N (in this paricular case 9) vectors and the aiming one > how to compute good weights that max to 1.0 when the aming coincides with > them? (Did I mention that weights need to add up to 1.0? but of course you > know that...) Here's one way: Project these vectors to points on the front plane, a unit distance away from the character. Perform a Delaunay triangulation on these points. Find the triangle which your desired aim vector lies within. Use barycentric coordinates for the three triangle vertex points, which map to the three vectors and weights you want to use. Note that almost all of this can be precalculated, and if the animations are constrained on a grid, the "find a triangle" is almost trivial, and the explicit triangulation doesn't have to be calculated. Cheers, / h+ 
From: Alex Mohr <amohr@cs...>  20041130 19:38:05

This from SIGGRAPH last year may be relevant. Check the video, and I believe the paper starting at section 4 would be most useful, but reading the whole thing is probably worthwhile. http://www.cs.wisc.edu/graphics/Gallery/Kovar/ParamMotion/ Alex >Hello, > >Imagine a soldier (or character with a weapon of some kind). We are tying >to get its weapon (two weapons, two handed weapon) to point into the >direction of aiming. > >We have 9 animations. Each represents a pose into a certain direction. Each >"pose" animation has a vector associated with it. >For a given character aiming direction vector we compute weight for each >animation to contribute into the final anim. > >Question is: Given N (in this paricular case 9) vectors and the aiming one >how to compute good weights that max to 1.0 when the aming coincides with >them? (Did I mention that weights need to add up to 1.0? but of course you >know that...) > >We have tried few methods and we have a couple of working but far from ideal >bodged solutions. I'm sure someone has solved this problem elegantly with >some clever maths. A lot of games seem to do that kind of thing although in >some cases IK can be applied. > >One solution that gives smooth results is just a dot product. > Wi = Vi dot Va where Wi are normalized afterwards with Wi = Wi/sum(Wi) (Wi >weight for each bone, Vi  Direction vectors for anims, Va  aim vector) >Unfortunately, this only works perfectly if all direction vectors (Vi) are >perpendicular to each other so when they max out no other anim contributes >to the final. It still works in other cases but the results are not accurate >enough for us. > >We have also explored few solutions where assumptions have been made that >some vectors lie in a certain plane but I'm looking for a generic solution >that will work in all cases. > >Thanks, >Yordan > > > > > >SF email is sponsored by  The IT Product Guide >Read honest & candid reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://productguide.itmanagersjournal.com/ >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Ryan Greene <ryang@co...>  20041130 19:34:36

I tried doing this exact system for a project I worked on in the past, but found the results to be pretty poor  it was rare that a character was aiming his weapon juuuust right. Furthermore, the cost of having an animator build _proper_ animations was just too much, so I wrote an IK solver to do the work. It took a little time to get it right, but the results are a whole lot better and easier to generate. I had my animators build a few base aiming poses from different positions  standing, crouching, and prone, then wrote special IK for each (although standing and crouching were nearly identical). I'm willing to bet the IK approach is slightly more expensive than blending together a few animations, but it is just so much easier (once you get over the fact that you're doing near fullbody IK), especially from an asset production standpoint. Another benefit we got from it was that it was easy to tie into weapon firing to simply adjust the IK to simulate weapon recoil w/o having to have another layer of animations to deal with. I'm sure other people have had good results from the animation blending technique, but from a project that had way too few animators doing way too many animations  IK is the way to go. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Yordan Gyurchev Sent: Tuesday, November 30, 2004 11:23 AM To: gdalgorithmslist@... Subject: [Algorithms] calculating weights for blending arbitrary number of animations Hello, Imagine a soldier (or character with a weapon of some kind). We are tying to get its weapon (two weapons, two handed weapon) to point into the direction of aiming. We have 9 animations. Each represents a pose into a certain direction. Each "pose" animation has a vector associated with it. For a given character aiming direction vector we compute weight for each animation to contribute into the final anim. Question is: Given N (in this paricular case 9) vectors and the aiming one how to compute good weights that max to 1.0 when the aming coincides with them? (Did I mention that weights need to add up to 1.0? but of course you know that...) We have tried few methods and we have a couple of working but far from ideal bodged solutions. I'm sure someone has solved this problem elegantly with some clever maths. A lot of games seem to do that kind of thing although in some cases IK can be applied. One solution that gives smooth results is just a dot product. Wi =3D Vi dot Va where Wi are normalized afterwards with Wi =3D = Wi/sum(Wi) (Wi weight for each bone, Vi  Direction vectors for anims, Va  aim vector) Unfortunately, this only works perfectly if all direction vectors (Vi) are perpendicular to each other so when they max out no other anim contributes to the final. It still works in other cases but the results are not accurate enough for us. We have also explored few solutions where assumptions have been made that some vectors lie in a certain plane but I'm looking for a generic solution that will work in all cases. Thanks, Yordan  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now.=20 http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Yordan Gyurchev <yordan@gy...>  20041130 19:24:38

Hello, Imagine a soldier (or character with a weapon of some kind). We are tying to get its weapon (two weapons, two handed weapon) to point into the direction of aiming. We have 9 animations. Each represents a pose into a certain direction. Each "pose" animation has a vector associated with it. For a given character aiming direction vector we compute weight for each animation to contribute into the final anim. Question is: Given N (in this paricular case 9) vectors and the aiming one how to compute good weights that max to 1.0 when the aming coincides with them? (Did I mention that weights need to add up to 1.0? but of course you know that...) We have tried few methods and we have a couple of working but far from ideal bodged solutions. I'm sure someone has solved this problem elegantly with some clever maths. A lot of games seem to do that kind of thing although in some cases IK can be applied. One solution that gives smooth results is just a dot product. Wi = Vi dot Va where Wi are normalized afterwards with Wi = Wi/sum(Wi) (Wi weight for each bone, Vi  Direction vectors for anims, Va  aim vector) Unfortunately, this only works perfectly if all direction vectors (Vi) are perpendicular to each other so when they max out no other anim contributes to the final. It still works in other cases but the results are not accurate enough for us. We have also explored few solutions where assumptions have been made that some vectors lie in a certain plane but I'm looking for a generic solution that will work in all cases. Thanks, Yordan 
From: Paul_F<irth@sc...>  20041130 12:01:58

gdalgorithmslistadmin@... wrote on 29/11/2004 17:30:05: > From what I understand (haven't looked at Minkowski differences or GJK until > now), GJK is just an optimization so that you don't have to check the > distance to the entire convex hull of the Minkowski Difference. Since speed > is not that important am I correct in assuming that the following code would > be the easiest to implement: > > 1. Find the set of differences between the triangle and the box > 2. Form the convex hull of this set > 3. Find the shortest distance to the origin from the convex hull Mmmm, good question. Maybe not  the vertex vs face and face vs vertex cases are really simple (just the same as in 2d on my page), but when it comes down to edge vs edge it gets more complex; Only a subset of all edge vs edge combinations form MD faces which lie on the convex hull of the MD. To detect which pairs you need, you must do some maths to test for intersection of the great arcs formed by the dual space projection of the edges onto the unit sphere. This sounds like a nightmare, but its not too bad actually. Once you find the edges in question they form faces of the MD just like the vertex face pairs did, and then its the minimum distance to each. Of course, as others have noted: if you don't need penetration distance (i.e. only you need only positive distance), then you can just take the minimum of distance between feature pairs of triangle and box. Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe 
From: Angel Popov <geleto@ge...>  20041130 09:37:37

I raypick using an id buffer. Draw the meshes, faces or whatever you want to pick, each one with a different color that corresponds to the ID. You can draw the id buffer once and as the mouse moves just do a single lookup to display some info in the status bar and/or highlight the face under the mouse. Advantages over analythic picking:  Very easy to implement  Works with geometry deformed by vertex shaders  Selecting only the visible geometry inside a view rectangle is much, much easier than doing this analythicaly.  Fast enough ( much faster in many cases ) A few disadvantages:  Selecting all faces (visible or hidden) inside a region requires depth peeling  Selecting subpixel faces inside a region is a bit tricky  you have to draw the edges as lines ontop the geometry, without writing to the zbuffer and use id peeling... 
From: <christer_ericson@pl...>  20041129 18:59:08

Andreas Brinck skrev: > does anyone know where I can find code that computes the distance=20 between a > box and a triangle. I was first thinking about extending David Eberly's > rectangle to triangle distance code, but I think the original code is=20 too > long as it is (every case written out explicitely). I'm also thinking=20 about > formulating the problem as a quadtratic programming problem with=20 constraints > but haven't been able to find a small free solver that is easy to=20 integrate > into my code. Any pointers would be much appreciated. I'm not aware of any small freelyavailable QP solvers, but if you are willing to implement them from scratch, the most promising ones for small problems seem to be the randomized algorithms of G=E4rtner and of Botkin. As others have mentioned, the GJK algorithm will give you the result you need, and there's code available for it. You can also implement it in terms of simpler primitives by recognizing that (for nonintersecting primitives) the closest points must be a vertex, on an edge or on a face of each primitive. You then write tests for all feature pairs, picking the pair of points giving the globally smallest distance. Trivially you can reduce this to triangle triangle distance computations, but those are sort of expensive in themselves. However, if you look at all featurefeature tests, there are certain tests that are not needed, such as faceface tests (which are subsumed by others). In your case I would probably go for GJK, because its pretty fast and code already exists. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: Tony Cox <tonycox@mi...>  20041129 17:58:44

>Don't use DirectPlay; it's pointless and stupid. >Use the internet protocol APIs directly. Thanks for that wellreasoned and fully substantiated critique. As it turns out, a good reason for not using DPlay anymore is that it's currently in maintenance mode  i.e. there will be no feature work, major bugfixes only (probably only security issues would make the bar), and will likely be phased out in the future. DPlay is neither pointless nor stupid; it's just being deprecated, is all. Tony Cox  Development Manager Studio ZR, Microsoft Game Studios 
From: Richard Mitton <rmitton@cl...>  20041129 17:42:50

1) Split box into triangles 2) For each triangle in box: Perform triangletriangle distance check And, to perform a triangletriangle distance check: http://www.magicsoftware.com/Source/Distance/WmlDistTri3Tri3.cpp "Haven't Tried It Though" (tm)  ()() Richard Mitton .:. rmitton@... ( '.') (")_(") xbox jester .:. climax action [kingston] > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...] On > Behalf Of Andreas.Brinck@... > Sent: 29 November 2004 15:55 > To: gdalgorithmslist@... > Subject: [Algorithms] Distance between box and triangle > > Hi, > > does anyone know where I can find code that computes the > distance between a box and a triangle. I was first thinking > about extending David Eberly's rectangle to triangle distance > code, but I think the original code is too long as it is > (every case written out explicitely). I'm also thinking about > formulating the problem as a quadtratic programming problem > with constraints but haven't been able to find a small free > solver that is easy to integrate into my code. Any pointers > would be much appreciated. > > /A.B. > ########################################### > > This message has been scanned by FSecure AntiVirus for > Microsoft Exchange. > For more information, connect to http://www.FSecure.com/ > > >  > SF email is sponsored by  The IT Product Guide Read honest & > candid reviews on hundreds of IT Products from real users. > Discover which products truly live up to the hype. Start reading now. > http://productguide.itmanagersjournal.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: Per Vognsen <Per.V<ognsen@ep...>  20041129 17:34:44

> Original Message > From: gdalgorithmslistadmin@... [mailto:gdalgorithms > listadmin@...] On Behalf Of Andreas.Brinck@... > Sent: Monday, November 29, 2004 12:30 PM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Distance between box and triangle >=20 > From what I understand (haven't looked at Minkowski differences or GJK > until > now), GJK is just an optimization so that you don't have to check the > distance to the entire convex hull of the Minkowski Difference. Since > speed > is not that important am I correct in assuming that the following code > would > be the easiest to implement: No. Explicitly computing the Minkowski sum is a lot of work. One of the nice things about GJK is that it never explicitly computes the Minkowski sum. > 1. Find the set of differences between the triangle and the box > 2. Form the convex hull of this set > 3. Find the shortest distance to the origin from the convex hull Per 
From: Andreas.B<rinck@me...>  20041129 17:29:27

From what I understand (haven't looked at Minkowski differences or GJK until now), GJK is just an optimization so that you don't have to check the distance to the entire convex hull of the Minkowski Difference. Since speed is not that important am I correct in assuming that the following code would be the easiest to implement: 1. Find the set of differences between the triangle and the box 2. Form the convex hull of this set 3. Find the shortest distance to the origin from the convex hull /A.B. Original Message From: Paul_Firth@... [mailto:Paul_Firth@...] Sent: den 29 november 2004 17:37 To: gdalgorithmslist@... Subject: Re: [Algorithms] Distance between box and triangle gdalgorithmslistadmin@... wrote on 29/11/2004 16:12:47: > Have you looked at Minkowski sums? I used to have a really good web link for > graphical examples using Java but have since lost it. :( I'm sure it came > from this list though. I have a page at http://www.pfirth.co.uk/collision.html and http://www.pfirth.co.uk/minkowski.html which might be of use... :) If you only want positive distance, GJK will be the fastest way to compute this. Probably. If not, you could either explicitly form the MD from the two shapes and take the minimum from the origin to each face of the MD as the minimum distance between the two, or you could use Gino van den Bergen's EPA algorithm (which is similar to GJK and takes the output of GJK as its input). Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ########################################### This message has been scanned by FSecure AntiVirus for Microsoft Exchange. For more information, connect to http://www.FSecure.com/ 
From: Davies, Matt <mdavies@t...>  20041129 16:38:52

Hi, the site you might be referring to is: http://www.pfirth.co.uk/collision.html Cheers Matt Davies Original Message From: Martin Piper [mailto:martin.piper@...] Sent: 29 November 2004 16:13 To: gdalgorithmslist@... Subject: Re: [Algorithms] Distance between box and triangle Have you looked at Minkowski sums? I used to have a really good web link for graphical examples using Java but have since lost it. :( I'm sure it came from this list though. Martin Piper http://www.ReplicaNet.com  Network middleware powering games.  Original Message  From: <Andreas.Brinck@...> To: <gdalgorithmslist@...> Sent: Monday, November 29, 2004 3:54 PM Subject: [Algorithms] Distance between box and triangle > Hi, > > does anyone know where I can find code that computes the distance between a > box and a triangle. I was first thinking about extending David Eberly's > rectangle to triangle distance code, but I think the original code is too > long as it is (every case written out explicitely). I'm also thinking about > formulating the problem as a quadtratic programming problem with constraints > but haven't been able to find a small free solver that is easy to integrate > into my code. Any pointers would be much appreciated. > > /A.B. > ########################################### > > This message has been scanned by FSecure AntiVirus for Microsoft Exchange. > For more information, connect to http://www.FSecure.com/ > > >  > SF email is sponsored by  The IT Product Guide > Read honest & candid reviews on hundreds of IT Products from real users. > Discover which products truly live up to the hype. Start reading now. > http://productguide.itmanagersjournal.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 _____________________________________________________________________ This email has been scanned for viruses by MCI's Internet Managed Scanning Services  powered by MessageLabs. For further information visit http://www.mci.com  Incoming mail is certified Virus Free. Checked by AVG antivirus system (http://www.grisoft.com). Version: 6.0.801 / Virus Database: 544  Release Date: 24/11/2004  Outgoing mail is certified Virus Free. Checked by AVG antivirus system (http://www.grisoft.com). Version: 6.0.801 / Virus Database: 544  Release Date: 24/11/2004 
From: Paul_F<irth@sc...>  20041129 16:37:09

gdalgorithmslistadmin@... wrote on 29/11/2004 16:12:47: > Have you looked at Minkowski sums? I used to have a really good web link for > graphical examples using Java but have since lost it. :( I'm sure it came > from this list though. I have a page at http://www.pfirth.co.uk/collision.html and http://www.pfirth.co.uk/minkowski.html which might be of use... :) If you only want positive distance, GJK will be the fastest way to compute this. Probably. If not, you could either explicitly form the MD from the two shapes and take the minimum from the origin to each face of the MD as the minimum distance between the two, or you could use Gino van den Bergen's EPA algorithm (which is similar to GJK and takes the output of GJK as its input). Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe 
From: Martin Piper <martin.piper@re...>  20041129 16:08:55

Have you looked at Minkowski sums? I used to have a really good web link for graphical examples using Java but have since lost it. :( I'm sure it came from this list though. Martin Piper http://www.ReplicaNet.com  Network middleware powering games.  Original Message  From: <Andreas.Brinck@...> To: <gdalgorithmslist@...> Sent: Monday, November 29, 2004 3:54 PM Subject: [Algorithms] Distance between box and triangle > Hi, > > does anyone know where I can find code that computes the distance between a > box and a triangle. I was first thinking about extending David Eberly's > rectangle to triangle distance code, but I think the original code is too > long as it is (every case written out explicitely). I'm also thinking about > formulating the problem as a quadtratic programming problem with constraints > but haven't been able to find a small free solver that is easy to integrate > into my code. Any pointers would be much appreciated. > > /A.B. > ########################################### > > This message has been scanned by FSecure AntiVirus for Microsoft Exchange. > For more information, connect to http://www.FSecure.com/ > > >  > SF email is sponsored by  The IT Product Guide > Read honest & candid reviews on hundreds of IT Products from real users. > Discover which products truly live up to the hype. Start reading now. > http://productguide.itmanagersjournal.com/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Andreas.B<rinck@me...>  20041129 15:54:20

Hi, does anyone know where I can find code that computes the distance between a box and a triangle. I was first thinking about extending David Eberly's rectangle to triangle distance code, but I think the original code is too long as it is (every case written out explicitely). I'm also thinking about formulating the problem as a quadtratic programming problem with constraints but haven't been able to find a small free solver that is easy to integrate into my code. Any pointers would be much appreciated. /A.B. ########################################### This message has been scanned by FSecure AntiVirus for Microsoft Exchange. For more information, connect to http://www.FSecure.com/ 
From: Andreas.B<rinck@me...>  20041129 10:47:39

Hi, for a given point I want to determine which triangle in a mesh that is the nearest one. I'm thinking about solving it like this: 1. Divide the space that the mesh occupies into a grid. 2. For each cell in the grid calculate a 'potentially nearest set' of triangles, i.e. all the triangles that for at least one point inside the cell is the closest one. 3. To find the closest triangle for a point we find which cell the point is inside and test the 'potentially nearest set' of that cell. The part I'm having problem with is step 2. One solution would be to subdivide each cell into a large number of points and test all triangles for each one to see which belong to the 'pcs'. This will probably be extremely slow and it won't give an exact result. I'm thinking about calculating the max distance of each triangle to a cell and using the smallest of these values as a threshold value for which triangles can be closest, any thoughts on this? Am I correct in assuming that the furthest away point in a triangle will be one of the vertices? /A.B. ########################################### This message has been scanned by FSecure AntiVirus for Microsoft Exchange. For more information, connect to http://www.FSecure.com/ 
From: <c.schueler@ph...>  20041129 09:03:20

Hi Megan, are you PC or console? On the PC, you pretty much can afford to have a = sysmem copy of every mesh, without colors, texcoords, etc, just the = geometry, so you can do a pertriangle ray intersection with it.=20 What I have is that the exporter will put a "geomesh" chunk into the = exported file which contains exactly this data, and which can be my read = by parts of the program that have no dependency on the rendering system = (ie. game logic running on a server). The picking archived with per triangle intersection is not pixel perfect = all the time (since it doesn't know about rasterisation rules) but it's = close, like in I never get a deviation by more than 1 pixel. In the = performance department it's 120 cycles per triangle, amortized (a = straight M=F6llerHaines implementation). If your're not shooting rays = every frame that's acceptable even without putting a bounding hierarchy = into the mesh. Cheers, Christian Original Message From: gdalgorithmslistadmin@... = [mailto:gdalgorithmslistadmin@...] On Behalf Of = Megan Fox Sent: Friday, November 26, 2004 4:29 AM To: gdalgorithmslist@... Subject: [Algorithms] Ray picking in editors  best done with collision = volumes, or visual volumes? It seems like either could work, but both appear to have (fairly major) drawbacks, so I'm curious what others have done here. On the one hand, I could use my visual bounding volumes for the picking. = This has the advantage that anything visible can be selected and worked = with, but my concern is that my visual bounding volumes are generally = not that accruate  they're just a bestfit AABB per mesh, that's it. = It seems like I'll have tons of cases where it becomes difficult to = select one object due to another piece of intersecting cruft (like a = particle fountain or light object or whatever). On the other hand, I could go with ray picking via my collision = routines. This has the advantage of fairly accurate bounds for all the = objects, but carries the significant disadvantage that just not = everything is going to BE collidable. Now I suppose I could get in the = habit of always defining a collision volume for an entity "just to be = thorough", even if said volume was just a triggertype sphere, but this = strikes me as fairly wasteful. I could also get in the habit of keeping = collision data around for these visualonly entities but only using it = when editing, except then I'm maybe just wasting effort when I should = just go with the preexisting visual AABBs. What have people used in their engines, and which ends up being "good = enough"? This doesn't have to be pixelperfect, my artist is just = getting tired of typing entity names into the console manually every = time he wants to toy with their position or a value ;) Thanks, Megan Fox  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. = Discover which products truly live up to the hype. Start reading now.=20 http://productguide.itmanagersjournal.com/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Paul Du Bois <paul.dubois@gm...>  20041129 04:27:20

I have a similar problem, but in 3D, and it is a pain in the butt. I do a sphere vs seaoftriangles intersection test and find the nearest feature, then travel (penetration distance + slop) outwards along the face normal (not the feature normal; that ended up not working so well). Repeat up to N times until the sphere is not intersecting any more, increasing slop as you go. Perform a sweep test from the final position to the original position. This works OK in practice, but I don't generally have to handle difficult cases; for those, it is likely to fail after N iterations. For your problem, it might help to think about it as something like Given a set of closed polygons S, a point P, and a radius r, determine whether P is in the volume minkowski_sum(S, circle of radius r). If it is, return the closest feature. This is a pretty easy collision problem. The minkowski sum can be precomputed for a few sample radii. You could simply the sum by only expanding edges and not verts; bevel the acute corners and make a bsp; etc etc. 
From: Jon Watte <hplus@mi...>  20041129 01:13:23

> On the other hand, I could go with ray picking via my collision > routines. This has the advantage of fairly accurate bounds for all > the objects, but carries the significant disadvantage that just not > everything is going to BE collidable. Now I suppose I could get in We raypick against the visible geometry using brute force (after doing visible bounds testing on the ray, of course). Yes, this is slow, but it's not like the user clicks the screen hundreds of times per second. Yes, this also means that we have to cache the visible geometry in triangle list form (at least vertices and indices) in readable system RAM. That doesn't necessarily have to be done in the notools release mode build, though. We also have a list of "nearby objects" where objects can be selected using regular list selection, for the cases where something has been configured with an invisible mesh or whatnot :) Cheers, / h+ 
From: Joe Ante <joe@ot...>  20041127 18:49:19

> What have people used in their engines, and which ends up being "good > enough"? This doesn't have to be pixelperfect, my artist is just > getting tired of typing entity names into the console manually every > time he wants to toy with their position or a value ;) If you care about getting it right and stopping your artists from bitching, you have to be pixel perfect. The easist way to do that is to render to a view and just use a shader which sets the pixel to an id of the rendered object. Then read the rendered pixel back. It is rather easy to do if you have a flexible graphics pipeline. And it is fast enough if you just use it for picking in an editor. Joachim Ante http://www.otee.dk 
From: John Miles <jmiles@po...>  20041126 21:40:13

It's helpful to do both. Small objects like arrows lying on the ground aren't easily selectable on a perpoly basis. What I do is fire a boundingvolume detection ray, then do a perpoly ray on whatever it hit. If the polygon ray hits the same object, I'm done. Otherwise, I cast another BV detection ray from the contact point along the same normal (with an exclusion flag set on the object so the ray won't hit it again.) The test ends when either the maximum ray distance is reached or no bounding volume is hit by the ray. The selected object, if any, is the last one whose bounding volume was struck. I go through all that for all UIdriven selection operations in both the editor and the game. It keeps the user from having to play hitthepixel, while preventing accidental selections.  jm > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Noel > Llopis > Sent: Thursday, November 25, 2004 9:30 PM > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Ray picking in editors  best done with > collision volumes, or visual volumes? > > > On Thursday 25 November 2004 19:29, Megan Fox wrote: > > It seems like either could work, but both appear to have (fairly > > major) drawbacks, so I'm curious what others have done here. > > I find that polygonlevel collision works best for editor picking. Start > with the rough BV for a quick cull, but then continue down to the poly > level. Performance shouldn't be an issue and they'll get exactly > what they > hit. > > > Noel > Games from Within > http://www.gamesfromwithin.com > > >  > 
From: Ben Garney <beng@ga...>  20041126 20:40:55

CAVEY GERARD wrote: >>Then after reading that lot you might be thinking of middleware: >>http://www.gamedev.net/features/reviews/productreview.asp?productid=240 >> >> You might also want to take a look at TNL if you're thinking of middleware (or just want to learn, it's duallicensed with the GPL and a commercial license, so you can read the source and docs for free): http://www.opentnl.org/ TNL has the benefit of having been used in several commercial games, including Tribes 1/2, so it will actually do, and do well, things that you'd need in an actual game. For me, it was very educational seeing where the original designers spent their time adding features, and where they left well enough alone... Ben Garney (Disclaimer: I work for the company that makes this.) 