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
(12) 
2
(4) 
3

4
(21) 
5
(3) 
6
(27) 
7
(31) 
8
(21) 
9
(2) 
10
(2) 
11
(14) 
12
(19) 
13
(24) 
14
(17) 
15
(27) 
16

17
(2) 
18
(2) 
19
(6) 
20
(1) 
21
(17) 
22
(12) 
23
(1) 
24
(1) 
25
(4) 
26
(16) 
27
(17) 
28
(7) 
29

30

31
(1) 






From: Michael Pohoreski <MP<ohoreski@cy...>  20020321 23:46:11

Carmack recently mentioned in his plan that nVidia updated their Shadow Volume page. http://developer.nvidia.com/view.asp?IO=3Drobust_shadow_volumes There is a text file "CarmackOnShadowVolumes.txt" at this page, in which Carmack describes how he arrived at "Carmack's Reverse" ! The page also contains's Heidmann's original article on stenciled shadow volumes. Very cool stuff. Interestingly, Jon says he posted his solution to a private mailing list. Anyone know which one? And more importantly, how to get read access :) P.S If you are already familiar with the info, sorry for posting (redundant info.) I 've only heard bits and pieices about Carmack's Reverse, so I thought I would share in case anyone is wondering what it's all about. P.P.S. Sorry if this post doesn't contain "algorithmic" content. :) I marked it SemiOT. 
From: Brian Sharon <bsharon@mi...>  20020321 21:25:30

There's nothing in the paper that mandates no restitution. No restitution arises from the fact that he's projecting penetrating bodies out to the surface and no further, killing his velocity normal to the collision plane. To implement restitution you could project things out further, or you can tweak the current and last positions simultaneously to apply an impulse that gives you the postcollision velocity you want. brian > Original Message > From: Chris Jenner [mailto:cjenner@...] > Sent: Thursday, March 21, 2002 9:52 AM > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics >=20 > I found the paper that I've read on the subject again at > http://www.ioi.dk/Homepages/tj/publications/gdc2001.htm so excuse me if > there is more to this system than I know about. >=20 > Also, please note that I'm not knocking what they do either. It seems > very > useful for what it is. >=20 > But, it is not a rigid body dynamics system. Try modelling a rubber ball > bouncing off a wall with it (you can't because there is no restitution). > Even worse, try modelling a car crash with it. >=20 > If someone has done this, and can show that it works well then I'll > happily > eat my words. >=20 > What you can do is get nice animations of fairly rigid or soft bodies > interacting with a static world. And you can get them cheaply as well. >=20 > It depends entirely on what you want the system for in the first place. >=20 > Chris. >=20 > [p.s. the problem of systems exploding is easy to get round with well > designed integration schemes. Obviously, if you put a lot of energy into > a > spring it will oscillate wildly which is why I would recommend hard limits > on any springs you have in your system, i.e. only compress so far before > rebounding, only extend so far before breaking.] >=20 >=20 > > Original Message > > From: Alex Clarke [mailto:alexc@...] > > Sent: 21 March 2002 17:16 > > To: Algorithms List > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > The fundamental problem with most of the implementatios of > > a physics simulatuions is that the timesteps are too big for > > the integrator to be numerically stable. This is especially > > true when you get large impulses with systems with springs > > (typically leading the simulation exploding). > > > > The hitman style systems use verlat intergration which is very > > resistant to exploding. They do use relaxation, and yes things > > can drift, but with sufficent relaxation iterations (I've had success > > with 5  10) and appropriate constraints this can be overcome. > > > > > > I presume you are doing physics for a game, some points: > > > > 1) Joe consumer does not know or care about totally accurate physics. > > Even if you wanted to, you couldn't anyway. > > 2) IMO the Hitman stuff is definately good enough. > > 3) It scales well: You can do cloth sims and use arbitary constraints. > > 4) It's faster (much simpler algrithm, and it's SIMD friendly) > > 5) It's easier to understand and debug. > > > > > Original Message > > > From: Chris Jenner [mailto:cjenner@...] > > > Sent: 21 March 2002 16:59 > > > To: 'Alex Clarke'; Algorithms List > > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > > > > I must admit that I haven't investigated Hitman's methods in > > > detail, but how > > > could it be more stable? > > > > > > correct me if I'm wrong, but didn't they handle constraints > > > by relaxation > > > implying that there will always be an error, and the errors > > > can get very > > > large if there are large forces or heavy collisions on part > > > of your jointed > > > system. > > > > > > I believe that their methods provide no way of modelling > > > acurate collision > > > response, even between two non articulated bodies, accounting > > > for variable > > > restitution, friction, mass, moments of inertia etc. (again, > > > I may be wrong > > > I think I only ever read one paper on the idea). You would > > > also lose any > > > hope of modelling more complex phenomenon like corriolis > > > forces acurately. > > > > > > If you want a simple method of preventing penetration with a > > > static world > > > then that's fine but if you want a realistic looking physics > > > engine then you > > > really need to look at a more detailed model. > > > > > > The other main option to Featherstone is lcp solvers of constraint > > > equations, which have the advantage that the multibody dynamics drop > > > straight out of the method used for contact resolution. It's > > > not exactly > > > fast though, especialy if the systems of constraints get > > > large and again it > > > requires a lot of effort and an understanding of the maths > > that you're > > > trying to do. > > > > > > > > > Chris. > > > > > > > Original Message > > > > From: Alex Clarke [mailto:alexc@...] > > > > Sent: 21 March 2002 16:24 > > > > To: Algorithms List > > > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > > > > > > > Why not use the Hitman style verlet physics for characters > > > rather than > > > > Featherstone's algorithm? It should be faster and more stable. > > > > > > > > Alex Clarke, Programmer (www.argonaut.com/malice.asp) > > > > Argonaut Games PLC 
From: Chris Jenner <cjenner@re...>  20020321 17:54:02

I found the paper that I've read on the subject again at http://www.ioi.dk/Homepages/tj/publications/gdc2001.htm so excuse me if there is more to this system than I know about. Also, please note that I'm not knocking what they do either. It seems very useful for what it is. But, it is not a rigid body dynamics system. Try modelling a rubber ball bouncing off a wall with it (you can't because there is no restitution). Even worse, try modelling a car crash with it. If someone has done this, and can show that it works well then I'll happily eat my words. What you can do is get nice animations of fairly rigid or soft bodies interacting with a static world. And you can get them cheaply as well. It depends entirely on what you want the system for in the first place. Chris. [p.s. the problem of systems exploding is easy to get round with well designed integration schemes. Obviously, if you put a lot of energy into a spring it will oscillate wildly which is why I would recommend hard limits on any springs you have in your system, i.e. only compress so far before rebounding, only extend so far before breaking.] > Original Message > From: Alex Clarke [mailto:alexc@...] > Sent: 21 March 2002 17:16 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > The fundamental problem with most of the implementatios of > a physics simulatuions is that the timesteps are too big for > the integrator to be numerically stable. This is especially > true when you get large impulses with systems with springs > (typically leading the simulation exploding). > > The hitman style systems use verlat intergration which is very > resistant to exploding. They do use relaxation, and yes things > can drift, but with sufficent relaxation iterations (I've had success > with 5  10) and appropriate constraints this can be overcome. > > > I presume you are doing physics for a game, some points: > > 1) Joe consumer does not know or care about totally accurate physics. > Even if you wanted to, you couldn't anyway. > 2) IMO the Hitman stuff is definately good enough. > 3) It scales well: You can do cloth sims and use arbitary constraints. > 4) It's faster (much simpler algrithm, and it's SIMD friendly) > 5) It's easier to understand and debug. > > > Original Message > > From: Chris Jenner [mailto:cjenner@...] > > Sent: 21 March 2002 16:59 > > To: 'Alex Clarke'; Algorithms List > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > I must admit that I haven't investigated Hitman's methods in > > detail, but how > > could it be more stable? > > > > correct me if I'm wrong, but didn't they handle constraints > > by relaxation > > implying that there will always be an error, and the errors > > can get very > > large if there are large forces or heavy collisions on part > > of your jointed > > system. > > > > I believe that their methods provide no way of modelling > > acurate collision > > response, even between two non articulated bodies, accounting > > for variable > > restitution, friction, mass, moments of inertia etc. (again, > > I may be wrong > > I think I only ever read one paper on the idea). You would > > also lose any > > hope of modelling more complex phenomenon like corriolis > > forces acurately. > > > > If you want a simple method of preventing penetration with a > > static world > > then that's fine but if you want a realistic looking physics > > engine then you > > really need to look at a more detailed model. > > > > The other main option to Featherstone is lcp solvers of constraint > > equations, which have the advantage that the multibody dynamics drop > > straight out of the method used for contact resolution. It's > > not exactly > > fast though, especialy if the systems of constraints get > > large and again it > > requires a lot of effort and an understanding of the maths > that you're > > trying to do. > > > > > > Chris. > > > > > Original Message > > > From: Alex Clarke [mailto:alexc@...] > > > Sent: 21 March 2002 16:24 > > > To: Algorithms List > > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > > > > Why not use the Hitman style verlet physics for characters > > rather than > > > Featherstone's algorithm? It should be faster and more stable. > > > > > > Alex Clarke, Programmer (www.argonaut.com/malice.asp) > > > Argonaut Games PLC > > > > > > _______________________________________________ > > > GDAlgorithmslist mailing list > > > GDAlgorithmslist@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > Virus scanned and cleared ok > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > Virus scanned and cleared ok 
From: Alex Clarke <alexc@ar...>  20020321 17:16:31

The fundamental problem with most of the implementatios of a physics simulatuions is that the timesteps are too big for the integrator to be numerically stable. This is especially true when you get large impulses with systems with springs (typically leading the simulation exploding). The hitman style systems use verlat intergration which is very resistant to exploding. They do use relaxation, and yes things can drift, but with sufficent relaxation iterations (I've had success with 5  10) and appropriate constraints this can be overcome. I presume you are doing physics for a game, some points: 1) Joe consumer does not know or care about totally accurate physics. Even if you wanted to, you couldn't anyway. 2) IMO the Hitman stuff is definately good enough. 3) It scales well: You can do cloth sims and use arbitary constraints. 4) It's faster (much simpler algrithm, and it's SIMD friendly) 5) It's easier to understand and debug. > Original Message > From: Chris Jenner [mailto:cjenner@...] > Sent: 21 March 2002 16:59 > To: 'Alex Clarke'; Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > I must admit that I haven't investigated Hitman's methods in > detail, but how > could it be more stable? > > correct me if I'm wrong, but didn't they handle constraints > by relaxation > implying that there will always be an error, and the errors > can get very > large if there are large forces or heavy collisions on part > of your jointed > system. > > I believe that their methods provide no way of modelling > acurate collision > response, even between two non articulated bodies, accounting > for variable > restitution, friction, mass, moments of inertia etc. (again, > I may be wrong > I think I only ever read one paper on the idea). You would > also lose any > hope of modelling more complex phenomenon like corriolis > forces acurately. > > If you want a simple method of preventing penetration with a > static world > then that's fine but if you want a realistic looking physics > engine then you > really need to look at a more detailed model. > > The other main option to Featherstone is lcp solvers of constraint > equations, which have the advantage that the multibody dynamics drop > straight out of the method used for contact resolution. It's > not exactly > fast though, especialy if the systems of constraints get > large and again it > requires a lot of effort and an understanding of the maths that you're > trying to do. > > > Chris. > > > Original Message > > From: Alex Clarke [mailto:alexc@...] > > Sent: 21 March 2002 16:24 > > To: Algorithms List > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > Why not use the Hitman style verlet physics for characters > rather than > > Featherstone's algorithm? It should be faster and more stable. > > > > Alex Clarke, Programmer (www.argonaut.com/malice.asp) > > Argonaut Games PLC > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > Virus scanned and cleared ok > 
From: Chris Jenner <cjenner@re...>  20020321 17:02:59

I must admit that I haven't investigated Hitman's methods in detail, but how could it be more stable? correct me if I'm wrong, but didn't they handle constraints by relaxation implying that there will always be an error, and the errors can get very large if there are large forces or heavy collisions on part of your jointed system. I believe that their methods provide no way of modelling acurate collision response, even between two non articulated bodies, accounting for variable restitution, friction, mass, moments of inertia etc. (again, I may be wrong I think I only ever read one paper on the idea). You would also lose any hope of modelling more complex phenomenon like corriolis forces acurately. If you want a simple method of preventing penetration with a static world then that's fine but if you want a realistic looking physics engine then you really need to look at a more detailed model. The other main option to Featherstone is lcp solvers of constraint equations, which have the advantage that the multibody dynamics drop straight out of the method used for contact resolution. It's not exactly fast though, especialy if the systems of constraints get large and again it requires a lot of effort and an understanding of the maths that you're trying to do. Chris. > Original Message > From: Alex Clarke [mailto:alexc@...] > Sent: 21 March 2002 16:24 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > Why not use the Hitman style verlet physics for characters rather than > Featherstone's algorithm? It should be faster and more stable. > > Alex Clarke, Programmer (www.argonaut.com/malice.asp) > Argonaut Games PLC > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > Virus scanned and cleared ok 
From: Jon Watte <hplus@mi...>  20020321 16:58:44

I ran this algorithm through some tests, and found a case where I think it might give you "inside" multiple polygons in a polygon mesh. Consider the polygon: double poly[ 6 ][ 2 ] = { { 4., 6. }, { 4., 4. }, { 5., 2. }, { 9., 2. }, { 9., 4. }, { 8., 6. }, }; Consider the two vertices: { 4., 4. } and { 9., 4. }. The algorithm will say that both are inside the polygon. However, that would mean that if you had an abutting polygon, the point would be inside that polygon, too. Now, it may be that I'm on crack or something, but when I've worried about this problem in the past, I've always ended up having to specialcase based on which direction the sign change happens to get this test to work right. Cheers, / h+ #include <stdio.h> enum { X = 0, Y = 1 }; /* CrossingsMultiplyTest courtecy of Eric Haines */ int CrossingsMultiplyTest( double pgon[][2], int numverts, double point[2] ) { register int j, yflag0, yflag1, inside_flag ; register double ty, tx, *vtx0, *vtx1 ; tx = point[X] ; ty = point[Y] ; vtx0 = pgon[numverts1] ; /* get test bit for above/below X axis */ yflag0 = ( vtx0[Y] >= ty ) ; vtx1 = pgon[0] ; inside_flag = 0 ; for ( j = numverts+1 ; j ; ) { yflag1 = ( vtx1[Y] >= ty ) ; /* Check if endpoints straddle (are on opposite sides) of X axis * (i.e. the Y's differ); if so, +X ray could intersect this edge. * The old test also checked whether the endpoints are both to the * right or to the left of the test point. However, given the faster * intersection point computation used below, this test was found to * be a breakeven proposition for most polygons and a loser for * triangles (where 50% or more of the edges which survive this test * will cross quadrants and so have to have the X intersection computed * anyway). I credit Joseph Samosky with inspiring me to try dropping * the "both left or both right" part of my code. */ if ( yflag0 != yflag1 ) { /* Check intersection of pgon segment with +X ray. * Note if >= point's X; if so, the ray hits it. * The division operation is avoided for the ">=" test by checking * the sign of the first vertex wrto the test point; idea inspired * by Joseph Samosky's and Mark HaighHutchinson's different * polygon inclusion tests. */ if ( ((vtx1[Y]ty) * (vtx0[X]vtx1[X]) >= (vtx1[X]tx) * (vtx0[Y]vtx1[Y])) == yflag1 ) { inside_flag = !inside_flag ; } } /* Move to the next pair of vertices, retaining info as possible. */ yflag0 = yflag1 ; vtx0 = vtx1 ; vtx1 += 2 ; } return( inside_flag ) ; } double poly[ 6 ][ 2 ] = { { 4., 6. }, { 4., 4. }, { 5., 2. }, { 9., 2. }, { 9., 4. }, { 8., 6. }, }; double poly2[ 5 ][ 2 ] = { { 0., 6. }, { 0., 2. }, { 5., 2. }, { 4., 4. }, { 4., 6. }, }; int main() { double pt[ 2 ] = { 4., 4. }; printf( "poly1: %s\n", CrossingsMultiplyTest( poly, 6, pt ) ? "inside" : "outside" ); printf( "poly2: %s\n", CrossingsMultiplyTest( poly2, 5, pt ) ? "inside" : "outside" ); return 0; } 
From: Alex Clarke <alexc@ar...>  20020321 16:24:35

Why not use the Hitman style verlet physics for characters rather than Featherstone's algorithm? It should be faster and more stable. Alex Clarke, Programmer (www.argonaut.com/malice.asp) Argonaut Games PLC 
From: Eric Haines <erich@ac...>  20020321 15:29:09

Stephen, > > > what's the fastest/most accurate algorithm to determine whether a point > > is in a triangle? > > > I don't need to know that for polygons other than triangles. thx > > > > I know this subject is like soooo two weeks ago by now, but I thought I'd > > add this to the pot (I've spent way too much time examining this problem in > > 2D): > > > > http://www.acm.org/pubs/tog/editors/erich/ptinpoly/ > >This is very interesting  but the original question was about >pointintriangle code  not pointinpolygon. You'll notice at the end of this article I compare the different algorithms for all sorts of different polygons, including 3 sided ones. Also, some of the fastest methods for testing point in polygon are based entirely on treating the polygon as a set of triangles (e.g. a fan) and testing whether the point is inside each triangle. As the article points out, the fastest point/triangle test appears to be the halfplane test (think of each edge of the triangle as a dividing line for the plane: if the point is inside all three lines, the point is inside the triangle), but only if you precompute and store the edge information for quick testing. Personally, my favorite is the Crossings Multiply test, since it's fast, so simple to code, and needs no extra precomputes. It also does a nice job of finding that a point is inside one and only one triangle if you're given a mesh. Here it is (the comments are longer than the code). If you want to hardwire it for triangles, it's easy to unroll the loop, etc: int CrossingsMultiplyTest( pgon, numverts, point ) double pgon[][2] ; int numverts ; double point[2] ; { register int j, yflag0, yflag1, inside_flag ; register double ty, tx, *vtx0, *vtx1 ; tx = point[X] ; ty = point[Y] ; vtx0 = pgon[numverts1] ; /* get test bit for above/below X axis */ yflag0 = ( vtx0[Y] >= ty ) ; vtx1 = pgon[0] ; inside_flag = 0 ; for ( j = numverts+1 ; j ; ) { yflag1 = ( vtx1[Y] >= ty ) ; /* Check if endpoints straddle (are on opposite sides) of X axis * (i.e. the Y's differ); if so, +X ray could intersect this edge. * The old test also checked whether the endpoints are both to the * right or to the left of the test point. However, given the faster * intersection point computation used below, this test was found to * be a breakeven proposition for most polygons and a loser for * triangles (where 50% or more of the edges which survive this test * will cross quadrants and so have to have the X intersection computed * anyway). I credit Joseph Samosky with inspiring me to try dropping * the "both left or both right" part of my code. */ if ( yflag0 != yflag1 ) { /* Check intersection of pgon segment with +X ray. * Note if >= point's X; if so, the ray hits it. * The division operation is avoided for the ">=" test by checking * the sign of the first vertex wrto the test point; idea inspired * by Joseph Samosky's and Mark HaighHutchinson's different * polygon inclusion tests. */ if ( ((vtx1[Y]ty) * (vtx0[X]vtx1[X]) >= (vtx1[X]tx) * (vtx0[Y]vtx1[Y])) == yflag1 ) { inside_flag = !inside_flag ; } } /* Move to the next pair of vertices, retaining info as possible. */ yflag0 = yflag1 ; vtx0 = vtx1 ; vtx1 += 2 ; } return( inside_flag ) ; } Eric 
From: Stephen J Baker <sjbaker@li...>  20020321 14:51:06

On Wed, 20 Mar 2002, Eric Haines wrote: > Marius, > > > At 04:41 PM 3/6/2002 +0100, you wrote: > > what's the fastest/most accurate algorithm to determine whether a point > is in a triangle? > > I don't need to know that for polygons other than triangles. thx > > I know this subject is like soooo two weeks ago by now, but I thought I'd > add this to the pot (I've spent way too much time examining this problem in > 2D): > > http://www.acm.org/pubs/tog/editors/erich/ptinpoly/ This is very interesting  but the original question was about pointintriangle code  not pointinpolygon.  Steve Baker (817)6192657 (Vox/VoxMail) L3Com/Link Simulation & Training (817)6192466 (Fax) Work: sjbaker@... http://www.link.com Home: sjbaker1@... http://www.sjbaker.org 
From: Chris Jenner <cjenner@re...>  20020321 14:25:20

You might have worked this out already, but once you get the simple = 1dof joints working, it's fairly easy to combine them to make more = complicated joints. It's not necessarily the most efficient way of doing things, = but saves a lot of coding. A ball joint can be created as a chain of two = 1dof revolute joints joined by a link of zero size and mass. > Original Message > From: Jorrit Rouwe [mailto:jorrit@...] > Sent: 21 March 2002 12:24 > To: Algorithms List > Subject: Re: [Algorithms] Articulated multibody physics >=20 >=20 > I've coded an implementation too, and agree that it is pretty=20 > stable *once* > you get it working :) >=20 > Unfortunately there is not much info on the web, so if you=20 > want other joints > that the standard joints described in Mirtich's thesis=20 > (rotation around 1 > axis, translation on 1 axis, screw like rotation/translation)=20 > you'll have to > derive them yourself. I tried to derive a ball joint but made=20 > a mistake and > never got it to work for more than a few seconds (after which=20 > it explodes). >=20 > Another problem of the approach is that it does not allow for=20 > loops in the > articulated structure. For example, you cannot have your=20 > character take both > hands of another character and insert joints to enforce that=20 > they stick > together. So for humans and motorcycles you would be ok, but=20 > you would have > to solve the contact with the ground / other characters using forces, > impulses, a penalty method, ... >=20 > Jorrit. >=20 > Jorrit Rouw=E9  Programmer, Tech Team >=20 > Lost Boys Games  Prins Hendrikkade 139  1011AS Amsterdam=20 > The Netherlands > Tel: +31 (0)20 4272277  Fax: +31 (0)20 4274040 =20 > jorrit@... > Amsterdam  Barcelona  Berlin  London  Madrid  Paris =20 > San Francisco  > Warsaw  Zurich  http://www.games.lostboys.com >=20 >  Original Message  > From: "Chris Jenner" <cjenner@...> > To: "Algorithms List" <gdalgorithmslist@...> > Sent: Thursday, March 21, 2002 12:40 PM > Subject: RE: [Algorithms] Articulated multibody physics >=20 >=20 > > You don't remember correctly, Jamie. > > > > The implementation of Featherstone's algorithm that I coded=20 > is physically > > acurate (within the limits of rigid body dynamics), efficient, and > effective > > without any extra degrees of freedom being added. It's=20 > also incredibly > > stable and unlike many other methods will not explode numerically. > > [For those of you who don't know, the Featherstone algorithm is a > > generalised coordinate method, guaranteeing that any=20 > solution is a valid > > state configuration complying with the constraints.] > > > > Multibody dynamics is a complicated problem, and so yes it=20 > can be slow if > > you want to accurately integrate through time and resolve=20 > collisions for > > long chains of joints while still retaining 'correct'=20 > physical behaviour. > > > > I would happily recommend the Featherstone algorithm to=20 > anyone who doesn't > > mind a bit of complicated maths. Whether or not it is the=20 > best in terms > of > > speed and accuracy is probably highly application dependent. > > >=20 >=20 >=20 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 Virus scanned and cleared ok 
From: Chris Jenner <cjenner@re...>  20020321 12:28:52

Most of the crashes came from bugs when I was developing the code. As I said, I wouldn't recommend the method to anyone who isn't happy about implementing complicated mathematical algorithms 'cos it's a b*****d to debug. There are also certain classes of multibody collision resolution problem that cannot be solved trivially. This, however, is not only a feature of the Featherstone algorithm, but a problem with any attempt at accurate multibody dynamics. [Consider a collision matrix which relates the impulse to be applied to resolve a collison to the initial relative velocity of the two colliding bodies. Inverting the collision matrix leads to a solution for the impulse. Constraints within a system lead to a collision matrix that is positive semidefinite, rather than positive definite for unconstrained rigid bodies, and so not necessarily invertible. A solution can be found in this case by single value decomposition. (See Mirtich, somewhere in the chapter on multibody collision resolution for a better explanation.)] Chris. > Original Message > From: Jamie Fowlston [mailto:jamief@...] > Sent: 21 March 2002 11:59 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > So were all those crashes purely from there being _no_ > correct solution > then? :) > > Jamie > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On > Behalf Of Chris > Jenner > Sent: 21 March 2002 11:41 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > You don't remember correctly, Jamie. > > The implementation of Featherstone's algorithm that I coded > is physically > acurate (within the limits of rigid body dynamics), > efficient, and effective > without any extra degrees of freedom being added. It's also > incredibly > stable and unlike many other methods will not explode numerically. > [For those of you who don't know, the Featherstone algorithm is a > generalised coordinate method, guaranteeing that any solution > is a valid > state configuration complying with the constraints.] > > Multibody dynamics is a complicated problem, and so yes it > can be slow if > you want to accurately integrate through time and resolve > collisions for > long chains of joints while still retaining 'correct' > physical behaviour. > > I would happily recommend the Featherstone algorithm to > anyone who doesn't > mind a bit of complicated maths. Whether or not it is the > best in terms of > speed and accuracy is probably highly application dependent. > > > Original Message > > From: Jamie Fowlston [mailto:jamief@...] > > Sent: 21 March 2002 11:01 > > To: Algorithms List > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > We implemented the Featherstone method (iirc) as seen in > > Mirtich's thesis > > for Stuntman. Last I knew, it was a bit slow, and you needed > > to add bogus > > extra degrees of freedom to stop the answers exploding numerically. > > > > Jamie > > > > > > Original Message > > From: gdalgorithmslistadmin@... > > [mailto:gdalgorithmslistadmin@...]On Behalf Of > > mark_me > > Sent: 21 March 2002 04:52 > > To: Algorithms List > > Subject: RE: [Algorithms] Articulated multibody physics > > > > > > I'm not sure if I understood your method right, It seems to > > me that you will > > end up with broken joints immediately. > > To do this correctly you need to consider the joints' forces > > , and if you > > have more than one force applied on the multi body > simultaneously ( on > > different bones ) then you need to solve a linear system of > > equations , > > which is here much easier than solving for resting contacts , > > but you will > > still have the problem of accuracy and you might need a > > velocity or position > > stabilizer to make sure your bones are always connected. I > > haven't tried > > that myself but Maybe one of the guys who tried it can tell > > us if it's fast > > enough for real time systems. > > > > There are some other ways like the relaxation method that > > Jacobsen described > > , and I think some people even talked about using the penalty > > method here , > > but I can't see how it could be suitable for this purpose. > > > > Original Message > > From: gdalgorithmslistadmin@... > > [mailto:gdalgorithmslistadmin@...]On > Behalf Of Ron > > Hay > > Sent: March 20, 2002 7:25 AM > > To: Algorithms List > > Subject: [Algorithms] Articulated multibody physics > > > > > > I'm currently working on a skeletal animation system for > our software, > > and have decided it would be extremely useful to be able to use the > > skeleton to be used not just for animation, but also for > vehicle (and > > otherwise) physics. So a motorcycle can be described as a single > > main "bone" (the body), with a 1dof rotator on the front connected > > to a translational bone with a spring attached, and a similar setup > > without the rotation on the back, represented the front and rear > > wheels, respectively. > > > > So, I did a web search for "articulated chains" and > > "multibody dynamics" > > and "articulated dynamics" and so on. I found many, many papers > > and sites, which showed the difficulties of such a problem. > And here > > I thought inverse kinematics was complicated. > > > > Anyway, my coworker and I thought of a simplification that we think > > would work decently, if not entirely 100% correct. Which is > > fine by us. > > I wanted to run it past the resident list physics gurus to get their > > comments. > > > > Basically, given a force on a bone, we first apply it > directly to the > > center of mass for the entire linkage. Then, we apply a torque to > > the entire linkage based on the force and its distance from > the center > > of mass. This is pretty standard for a single body, from > > what I understand. > > > > Seperately, for the bone the force is applied to, we > > determine the torque > > on the bone by finding the component of the original force that is > > perpendicular to the bone. Then, we propagate the component > > of the force > > that is parallel to the bone to the bones it is connected to, > > and continue > > on figuring out the torques and "propagation forces" > > recursively through > > the linkage. > > > > I'm going to be coding this up today and tomorrow, and I'll > > let people that > > are interested know how it turns out, but if anyone has any > > comments or > > experiences with such a problem, please send them! > > > > Ron Hay > > Developer > > Cybernet Systems. > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > Virus scanned and cleared ok > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > Virus scanned and cleared ok 
From: Jorrit Rouwe <jorrit@ga...>  20020321 12:21:18

I've coded an implementation too, and agree that it is pretty stable *once* you get it working :) Unfortunately there is not much info on the web, so if you want other joints that the standard joints described in Mirtich's thesis (rotation around 1 axis, translation on 1 axis, screw like rotation/translation) you'll have to derive them yourself. I tried to derive a ball joint but made a mistake and never got it to work for more than a few seconds (after which it explodes). Another problem of the approach is that it does not allow for loops in the articulated structure. For example, you cannot have your character take both hands of another character and insert joints to enforce that they stick together. So for humans and motorcycles you would be ok, but you would have to solve the contact with the ground / other characters using forces, impulses, a penalty method, ... Jorrit. Jorrit Rouwé  Programmer, Tech Team Lost Boys Games  Prins Hendrikkade 139  1011AS Amsterdam The Netherlands Tel: +31 (0)20 4272277  Fax: +31 (0)20 4274040  jorrit@... Amsterdam  Barcelona  Berlin  London  Madrid  Paris  San Francisco  Warsaw  Zurich  http://www.games.lostboys.com  Original Message  From: "Chris Jenner" <cjenner@...> To: "Algorithms List" <gdalgorithmslist@...> Sent: Thursday, March 21, 2002 12:40 PM Subject: RE: [Algorithms] Articulated multibody physics > You don't remember correctly, Jamie. > > The implementation of Featherstone's algorithm that I coded is physically > acurate (within the limits of rigid body dynamics), efficient, and effective > without any extra degrees of freedom being added. It's also incredibly > stable and unlike many other methods will not explode numerically. > [For those of you who don't know, the Featherstone algorithm is a > generalised coordinate method, guaranteeing that any solution is a valid > state configuration complying with the constraints.] > > Multibody dynamics is a complicated problem, and so yes it can be slow if > you want to accurately integrate through time and resolve collisions for > long chains of joints while still retaining 'correct' physical behaviour. > > I would happily recommend the Featherstone algorithm to anyone who doesn't > mind a bit of complicated maths. Whether or not it is the best in terms of > speed and accuracy is probably highly application dependent. > 
From: Jamie Fowlston <jamief@qu...>  20020321 11:59:34

So were all those crashes purely from there being _no_ correct solution then? :) Jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Chris Jenner Sent: 21 March 2002 11:41 To: Algorithms List Subject: RE: [Algorithms] Articulated multibody physics You don't remember correctly, Jamie. The implementation of Featherstone's algorithm that I coded is physically acurate (within the limits of rigid body dynamics), efficient, and effective without any extra degrees of freedom being added. It's also incredibly stable and unlike many other methods will not explode numerically. [For those of you who don't know, the Featherstone algorithm is a generalised coordinate method, guaranteeing that any solution is a valid state configuration complying with the constraints.] Multibody dynamics is a complicated problem, and so yes it can be slow if you want to accurately integrate through time and resolve collisions for long chains of joints while still retaining 'correct' physical behaviour. I would happily recommend the Featherstone algorithm to anyone who doesn't mind a bit of complicated maths. Whether or not it is the best in terms of speed and accuracy is probably highly application dependent. > Original Message > From: Jamie Fowlston [mailto:jamief@...] > Sent: 21 March 2002 11:01 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > We implemented the Featherstone method (iirc) as seen in > Mirtich's thesis > for Stuntman. Last I knew, it was a bit slow, and you needed > to add bogus > extra degrees of freedom to stop the answers exploding numerically. > > Jamie > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of > mark_me > Sent: 21 March 2002 04:52 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > I'm not sure if I understood your method right, It seems to > me that you will > end up with broken joints immediately. > To do this correctly you need to consider the joints' forces > , and if you > have more than one force applied on the multi body simultaneously ( on > different bones ) then you need to solve a linear system of > equations , > which is here much easier than solving for resting contacts , > but you will > still have the problem of accuracy and you might need a > velocity or position > stabilizer to make sure your bones are always connected. I > haven't tried > that myself but Maybe one of the guys who tried it can tell > us if it's fast > enough for real time systems. > > There are some other ways like the relaxation method that > Jacobsen described > , and I think some people even talked about using the penalty > method here , > but I can't see how it could be suitable for this purpose. > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Ron > Hay > Sent: March 20, 2002 7:25 AM > To: Algorithms List > Subject: [Algorithms] Articulated multibody physics > > > I'm currently working on a skeletal animation system for our software, > and have decided it would be extremely useful to be able to use the > skeleton to be used not just for animation, but also for vehicle (and > otherwise) physics. So a motorcycle can be described as a single > main "bone" (the body), with a 1dof rotator on the front connected > to a translational bone with a spring attached, and a similar setup > without the rotation on the back, represented the front and rear > wheels, respectively. > > So, I did a web search for "articulated chains" and > "multibody dynamics" > and "articulated dynamics" and so on. I found many, many papers > and sites, which showed the difficulties of such a problem. And here > I thought inverse kinematics was complicated. > > Anyway, my coworker and I thought of a simplification that we think > would work decently, if not entirely 100% correct. Which is > fine by us. > I wanted to run it past the resident list physics gurus to get their > comments. > > Basically, given a force on a bone, we first apply it directly to the > center of mass for the entire linkage. Then, we apply a torque to > the entire linkage based on the force and its distance from the center > of mass. This is pretty standard for a single body, from > what I understand. > > Seperately, for the bone the force is applied to, we > determine the torque > on the bone by finding the component of the original force that is > perpendicular to the bone. Then, we propagate the component > of the force > that is parallel to the bone to the bones it is connected to, > and continue > on figuring out the torques and "propagation forces" > recursively through > the linkage. > > I'm going to be coding this up today and tomorrow, and I'll > let people that > are interested know how it turns out, but if anyone has any > comments or > experiences with such a problem, please send them! > > Ron Hay > Developer > Cybernet Systems. > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > Virus scanned and cleared ok _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Chris Jenner <cjenner@re...>  20020321 11:42:18

You don't remember correctly, Jamie. The implementation of Featherstone's algorithm that I coded is physically acurate (within the limits of rigid body dynamics), efficient, and effective without any extra degrees of freedom being added. It's also incredibly stable and unlike many other methods will not explode numerically. [For those of you who don't know, the Featherstone algorithm is a generalised coordinate method, guaranteeing that any solution is a valid state configuration complying with the constraints.] Multibody dynamics is a complicated problem, and so yes it can be slow if you want to accurately integrate through time and resolve collisions for long chains of joints while still retaining 'correct' physical behaviour. I would happily recommend the Featherstone algorithm to anyone who doesn't mind a bit of complicated maths. Whether or not it is the best in terms of speed and accuracy is probably highly application dependent. > Original Message > From: Jamie Fowlston [mailto:jamief@...] > Sent: 21 March 2002 11:01 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > We implemented the Featherstone method (iirc) as seen in > Mirtich's thesis > for Stuntman. Last I knew, it was a bit slow, and you needed > to add bogus > extra degrees of freedom to stop the answers exploding numerically. > > Jamie > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of > mark_me > Sent: 21 March 2002 04:52 > To: Algorithms List > Subject: RE: [Algorithms] Articulated multibody physics > > > I'm not sure if I understood your method right, It seems to > me that you will > end up with broken joints immediately. > To do this correctly you need to consider the joints' forces > , and if you > have more than one force applied on the multi body simultaneously ( on > different bones ) then you need to solve a linear system of > equations , > which is here much easier than solving for resting contacts , > but you will > still have the problem of accuracy and you might need a > velocity or position > stabilizer to make sure your bones are always connected. I > haven't tried > that myself but Maybe one of the guys who tried it can tell > us if it's fast > enough for real time systems. > > There are some other ways like the relaxation method that > Jacobsen described > , and I think some people even talked about using the penalty > method here , > but I can't see how it could be suitable for this purpose. > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Ron > Hay > Sent: March 20, 2002 7:25 AM > To: Algorithms List > Subject: [Algorithms] Articulated multibody physics > > > I'm currently working on a skeletal animation system for our software, > and have decided it would be extremely useful to be able to use the > skeleton to be used not just for animation, but also for vehicle (and > otherwise) physics. So a motorcycle can be described as a single > main "bone" (the body), with a 1dof rotator on the front connected > to a translational bone with a spring attached, and a similar setup > without the rotation on the back, represented the front and rear > wheels, respectively. > > So, I did a web search for "articulated chains" and > "multibody dynamics" > and "articulated dynamics" and so on. I found many, many papers > and sites, which showed the difficulties of such a problem. And here > I thought inverse kinematics was complicated. > > Anyway, my coworker and I thought of a simplification that we think > would work decently, if not entirely 100% correct. Which is > fine by us. > I wanted to run it past the resident list physics gurus to get their > comments. > > Basically, given a force on a bone, we first apply it directly to the > center of mass for the entire linkage. Then, we apply a torque to > the entire linkage based on the force and its distance from the center > of mass. This is pretty standard for a single body, from > what I understand. > > Seperately, for the bone the force is applied to, we > determine the torque > on the bone by finding the component of the original force that is > perpendicular to the bone. Then, we propagate the component > of the force > that is parallel to the bone to the bones it is connected to, > and continue > on figuring out the torques and "propagation forces" > recursively through > the linkage. > > I'm going to be coding this up today and tomorrow, and I'll > let people that > are interested know how it turns out, but if anyone has any > comments or > experiences with such a problem, please send them! > > Ron Hay > Developer > Cybernet Systems. > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > Virus scanned and cleared ok 
From: Jamie Fowlston <jamief@qu...>  20020321 11:01:11

We implemented the Featherstone method (iirc) as seen in Mirtich's thesis for Stuntman. Last I knew, it was a bit slow, and you needed to add bogus extra degrees of freedom to stop the answers exploding numerically. Jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of mark_me Sent: 21 March 2002 04:52 To: Algorithms List Subject: RE: [Algorithms] Articulated multibody physics I'm not sure if I understood your method right, It seems to me that you will end up with broken joints immediately. To do this correctly you need to consider the joints' forces , and if you have more than one force applied on the multi body simultaneously ( on different bones ) then you need to solve a linear system of equations , which is here much easier than solving for resting contacts , but you will still have the problem of accuracy and you might need a velocity or position stabilizer to make sure your bones are always connected. I haven't tried that myself but Maybe one of the guys who tried it can tell us if it's fast enough for real time systems. There are some other ways like the relaxation method that Jacobsen described , and I think some people even talked about using the penalty method here , but I can't see how it could be suitable for this purpose. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Ron Hay Sent: March 20, 2002 7:25 AM To: Algorithms List Subject: [Algorithms] Articulated multibody physics I'm currently working on a skeletal animation system for our software, and have decided it would be extremely useful to be able to use the skeleton to be used not just for animation, but also for vehicle (and otherwise) physics. So a motorcycle can be described as a single main "bone" (the body), with a 1dof rotator on the front connected to a translational bone with a spring attached, and a similar setup without the rotation on the back, represented the front and rear wheels, respectively. So, I did a web search for "articulated chains" and "multibody dynamics" and "articulated dynamics" and so on. I found many, many papers and sites, which showed the difficulties of such a problem. And here I thought inverse kinematics was complicated. Anyway, my coworker and I thought of a simplification that we think would work decently, if not entirely 100% correct. Which is fine by us. I wanted to run it past the resident list physics gurus to get their comments. Basically, given a force on a bone, we first apply it directly to the center of mass for the entire linkage. Then, we apply a torque to the entire linkage based on the force and its distance from the center of mass. This is pretty standard for a single body, from what I understand. Seperately, for the bone the force is applied to, we determine the torque on the bone by finding the component of the original force that is perpendicular to the bone. Then, we propagate the component of the force that is parallel to the bone to the bones it is connected to, and continue on figuring out the torques and "propagation forces" recursively through the linkage. I'm going to be coding this up today and tomorrow, and I'll let people that are interested know how it turns out, but if anyone has any comments or experiences with such a problem, please send them! Ron Hay Developer Cybernet Systems. _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: mark_me <mark_me@so...>  20020321 04:53:40

I'm not sure if I understood your method right, It seems to me that you will end up with broken joints immediately. To do this correctly you need to consider the joints' forces , and if you have more than one force applied on the multi body simultaneously ( on different bones ) then you need to solve a linear system of equations , which is here much easier than solving for resting contacts , but you will still have the problem of accuracy and you might need a velocity or position stabilizer to make sure your bones are always connected. I haven't tried that myself but Maybe one of the guys who tried it can tell us if it's fast enough for real time systems. There are some other ways like the relaxation method that Jacobsen described , and I think some people even talked about using the penalty method here , but I can't see how it could be suitable for this purpose. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Ron Hay Sent: March 20, 2002 7:25 AM To: Algorithms List Subject: [Algorithms] Articulated multibody physics I'm currently working on a skeletal animation system for our software, and have decided it would be extremely useful to be able to use the skeleton to be used not just for animation, but also for vehicle (and otherwise) physics. So a motorcycle can be described as a single main "bone" (the body), with a 1dof rotator on the front connected to a translational bone with a spring attached, and a similar setup without the rotation on the back, represented the front and rear wheels, respectively. So, I did a web search for "articulated chains" and "multibody dynamics" and "articulated dynamics" and so on. I found many, many papers and sites, which showed the difficulties of such a problem. And here I thought inverse kinematics was complicated. Anyway, my coworker and I thought of a simplification that we think would work decently, if not entirely 100% correct. Which is fine by us. I wanted to run it past the resident list physics gurus to get their comments. Basically, given a force on a bone, we first apply it directly to the center of mass for the entire linkage. Then, we apply a torque to the entire linkage based on the force and its distance from the center of mass. This is pretty standard for a single body, from what I understand. Seperately, for the bone the force is applied to, we determine the torque on the bone by finding the component of the original force that is perpendicular to the bone. Then, we propagate the component of the force that is parallel to the bone to the bones it is connected to, and continue on figuring out the torques and "propagation forces" recursively through the linkage. I'm going to be coding this up today and tomorrow, and I'll let people that are interested know how it turns out, but if anyone has any comments or experiences with such a problem, please send them! Ron Hay Developer Cybernet Systems. _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Eric Haines <erich@ac...>  20020321 04:42:50

Marius, > At 04:41 PM 3/6/2002 +0100, you wrote: > what's the fastest/most accurate algorithm to determine whether a point is in a triangle? > I don't need to know that for polygons other than triangles. thx I know this subject is like soooo two weeks ago by now, but I thought I'd add this to the pot (I've spent way too much time examining this problem in 2D): http://www.acm.org/pubs/tog/editors/erich/ptinpoly/ There are timings at the end (YMMV), and pointers to C code. Eric 