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}
(3) 
_{Dec}

2015 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(12) 
_{Nov}

_{Dec}
(1) 
2016 
_{Jan}

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

_{Jun}
(1) 
_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 


1
(4) 
2
(1) 
3

4

5
(29) 
6
(1) 
7
(1) 
8
(1) 
9
(3) 
10
(6) 
11
(9) 
12
(5) 
13
(2) 
14
(3) 
15
(18) 
16
(5) 
17
(5) 
18
(5) 
19

20
(1) 
21
(3) 
22
(10) 
23
(2) 
24

25
(9) 
26
(1) 
27

28
(1) 
29
(1) 
30
(7) 
31
(3) 



From: igrok <igrok@bl...>  20040315 21:29:36

I'd like to say thankyou for the responses I recieved regarding this = topic. Its taking a long time to check up and test all the ideas given and I haven't yet solved it unfortunately, although I have found a few maths = bugs along the way. I just wanted to respond to a couple of the points raised. > 2) This is typical impulsebased artifact. Typically you would damp = the=20 > rigidbody's angular momentum so it will eventual rest on more than one = point. If I dampen the angular momentum things get considerably worse because = it relies on a very tiny amount of momentum to fall off a single point in the = first place (i.e. collapse on to it's side), damping it results in it endless hovering on = one vertex. Unless there is some trick to this? All I'm doing is AngMom *=3D 0.999 = each frame. > When you say it jumps from corner to corner what are you describing? It lands on one vertex. The collision impulses push it upwards and it = starts to rotate, but its pushed a little too hard and rotates a little bit too much so = that instead of falling on its side, it often lands on the next vertex along, and then = repeats.  Original Message =20 From: igrok=20 To: gdalgorithmslist@...=20 Sent: Tuesday, March 09, 2004 10:33 PM Subject: [Algorithms] Rigid Body impulses I've been working on a fairly simple rigid body simulator, but would = like to ask a couple of questions about issues that have been dogging me. 1. I apply impulses at the points of collision, but I've noticed a = difference in the way that many books/papers/code handle this section. When calculating = the magnitude of the impulse, j, some versions also add on the depth of = the collision contact, but many do not. I've found that I *must* add the depth = otherwise I get sinking problems and general instability, but I'm not sure how many = simulations get away without doing this at all. Is this something that is unusual? 2. Although I've got 'flat' collisions (face against face) and = friction to work pretty well, to the point that I can stack boxes without instability, I'm = finding that point collisions cause very unrealistic behaviour. For example, if I drop a box downwards towards a plane so it strikes = the surface=20 on a single corner, it often has a tendancy to float around on this = point, skimming across the surface as it bobs up and down. Sometimes it may jump from = corner to corner, but it won't ever settle on to a flat side of the cube. I get = pretty much the same problems even if I turn off friction, so it's not that. Is there any common mistake that could cause this problem? (dropping on to an edge or a side always comes out looking normal) A few details about my collision implementation: Up to 4 colliding points are calculated for a box vs a plane. Each one = is processed one at a time, with an impulse being applied at the point of contact. = Linear and angular velocities are not updated until after all collisions have = been resolved. (I've seen many implementations that update these immediately after = each collision point is resolved, but I found it to be very unstable that way as it = seemed to increase jittering). Any help would be appreciated. Thanks igrok. 
From: Jonathan Henckel <jhenckel@cs...>  20040315 18:13:01

> Original Message > From: Jon Watte [mailto:hplus@...] > > > Once you have a TOI heap, you pop the smallest TOI pair, integrate > > all objects up to TOI, solve the impact, repeat popintegratesolve. > > If the heap is empty, just integrate up to dt. > > > If you get a very early impact with high restitution > (billiard balls, say) > wouldn't it be possible that the bounding volume after impact > resolution can > now interpenetrate the bounding volume of something you > discarded in the > early phase? > > To solve this, wouldn't you have to start with a bounding > sphere around the > object, then extend that sphere radius by V*dt (because > that's how far > the thing could move in any direction), then do the overlap > test between > bounding volumes? It seems like, only if by moving in any > direction you > cannot intersect any other object moving in any direction, > can you isolate > an object or island of objects. Yes that is more correct. In fact you probably have to extend each sphere radius by V*dt where V is the maximum velocity of ANY object in the simulation! Because a slow moving object could get hit from behind and start moving faster. Ok, now I have to confess. A heap would be the proper way to do it, but since total realistism was not required, I didn't use a heap. I just integrated each object by the min TOI of all its pairs, and then threw away the rest of the time step for that object. If an object was not involved in any TOI pairs, then I integrated it a full step, dt. Thanks for keeping me honest. John 
From: Jonathan Henckel <jhenckel@cs...>  20040315 17:48:19

full narrow phase cd is 1. use GJK (or whatever) to find the contact plane and separation 2. get appropriate "features" from each object, i.e. face, edge, or vertex 3. find the contact set, i.e. a convex polygon on the contact plane, by taking the 2D intersection of the features. At first I thought only part (1) would be needed in TOI substeps. This is true for the translational part. However, to get correct limits of the angular integration, I needed to do part (2) also. The angle between each feature and its neighbors is also helpful to set the limit on the angular integration of the substep. John Original Message From: Bob Dowland [mailto:Bob.Dowland@...] Sent: Monday, 15 March, 2004 12:28 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] number of iterations to solve collision between > test nearest distance, repeat. John, did you find the need to implement some form of "supernarrow" phase test for these substep checks  eg one which just tracks the distance between contact points found in the narrow phase, or do you go for a full narrow phase cd each time? Original Message From: Jonathan Henckel [mailto:jhenckel@...] Sent: 15 March 2004 11:33 To: gdalgorithmslist@... Subject: RE: [Algorithms] number of iterations to solve collision between Igor, I think I understand what you are doing and I will explain how I solved this problem. The problem is... given three (or more) fast moving objects, how do you move them (integrate the position over time) so the all impacts are detected and handled at the correct moment in time. Is that the question? To do this you should use a TOI heap. See Brian Mirtich's Phd thesis for a description of the TOI heap. You can keep a persistent global heap of all pairs in the system (Brian does this) or you can use a transient heap which is reconstructed on every frame. I recommend the latter by using a broad phase algorithm with swept bounding volumes. For instance, if the broad phase uses AABB, take each object, whack a bounding sphere around the center of mass, sweep the sphere by the vector V*dt where dt is the maximum time step (e.g. 1/60 sec) which give a capsule, and finally whack an AABB around the capsule. Then the broad phase returns all pair of objects that can potentially be touching within the next dt. Next you analyse each pair (they are NOT ordered, thus AB==BA), and you need to determine the exact TOI (or miss) using GJK or whatever clever narrow phase algorithm you can think of, and insert each pairs into a TOI heap. Note if a pair does not hit within dt it is not inserted in the heap. Note that you may need to use iteration within the narrow phase TOI, i.e. integrate a little, test nearest distance, repeat. Do not use binary search for narrow phase TOI, there are much better ways. Once you have a TOI heap, you pop the smallest TOI pair, integrate all objects up to TOI, solve the impact, repeat popintegratesolve. If the heap is empty, just integrate up to dt. John From: Igor Kravtchenko I think I shouldn't mention "collision detection" because it clearly lends to confusion. I'm aware of ODE, broad/narrow phase algorithm, etc. Let me try to rephrase my question. Say your broad phase gives you 3 colliding bodies. They could in fact potentialy collide. At the current frame, these 3 bodies doesn't collide but they are going to collide in the next frame in a manner or another if you don't update their position/velocity. So, I'm talking here about a system that prevent from colliding not which separates collided entities. So now you have A B C and you know they can all collide each other, you have to move these bodies properly and indeed prevent them from colliding. My question is to know the optimal (theorical?) number of iterations for that. Currently, I would have 6 tests:  test1: try to move A at its destination and see if it not collide with B  test2: try to move A at its destination and see if it not collide with C if not any collision, set A to its destination otherwhise update with the nearest collided body  test3: try to move B at its destination and see if it not collide with A  test4: try to move B at its destination and see if it not collide with C if not any collision, set B to its destination otherwhise update with the nearest collided body  test5: try to move C at its destination and see if it not collide with A  test6: try to move C at its destination and see if it not collide with B if not any collision, set C to its destination otherwhise update with the nearest collided body That's not impulse based. Is there a (wellknown) way to reduce the number of such tests? Hope you get the idea. Igor. 
From: Jon Watte <hplus@mi...>  20040315 17:11:17

> Once you have a TOI heap, you pop the smallest TOI pair, integrate > all objects up to TOI, solve the impact, repeat popintegratesolve. > If the heap is empty, just integrate up to dt. If you get a very early impact with high restitution (billiard balls, say) wouldn't it be possible that the bounding volume after impact resolution can now interpenetrate the bounding volume of something you discarded in the early phase? To solve this, wouldn't you have to start with a bounding sphere around the object, then extend that sphere radius by V*dt (because that's how far the thing could move in any direction), then do the overlap test between bounding volumes? It seems like, only if by moving in any direction you cannot intersect any other object moving in any direction, can you isolate an object or island of objects. Cheers, / h+ 
From: Julian Serban <julianserban100@ho...>  20040315 15:48:53

I wasn't talking about OpenGL nor DirectX, I meant basic 3D. I need this for my 3D Engine, cause my current matrix should rotate the matrix so that the Camera got rotated so Z was deepth, Y height and X width, however it didn't work. So that's why I need a matrix that works, I mean, when I have multiplied the matrix with the vector, it should work.  Julian _________________________________________________________________ Få alle de nye og sjove ikoner med MSN Messenger http://messenger.msn.dk 
From: Tom Forsyth <tom.forsyth@ee...>  20040315 14:01:28

> From: Stephen J Baker >=20 > If you are using OpenGL, you shouldn't be attempting to put the camera > position and direction into the projection matrix. That's=20 > there for your > perspective parameters and nothing else. >=20 > I have a FAQ on the subject here: >=20 > http://www.sjbaker.org/steve/omniv/projection_abuse.html > > A similar situation may exist with D3D  but I don't use that API > so I don't know for sure. Yes. It's basically the same system with minor religious differences, so = you can get the same evilness. The major exception in both languages is if using vertex shaders  since you're doing everything manually, it's common to have a = WorldViewProjection matix. However, by far the best way to find this is to generate a = WorldView matrix and a Projection matrix and multiply them together, rather than = try to generate them in one go. You'll just get horribly confused, and it's unlikely to be significantly faster (how many times per frame do you do = this anyway? :) TomF. 
From: Stephen J Baker <sjbaker@li...>  20040315 13:27:26

Julian Serban wrote: > Hi, I need the perspective matrix for Camera Orientation. I have > searched and I couldn't find much about it, and specially nothing that > applies to what I need. If you are using OpenGL, you shouldn't be attempting to put the camera position and direction into the projection matrix. That's there for your perspective parameters and nothing else. I have a FAQ on the subject here: http://www.sjbaker.org/steve/omniv/projection_abuse.html A similar situation may exist with D3D  but I don't use that API so I don't know for sure.  The second law of Frisbee throwing states: "Never precede any maneuver by a comment more predictive than "Watch this!"...it turns out that this also applies to writing Fragment Shaders.  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: Bob Dowland <Bob.Dowland@bl...>  20040315 12:28:27

> test nearest distance, repeat. =20 John,=20 =20 did you find the need to implement some form of "supernarrow" phase = test for these substep checks  eg one which just tracks the distance = between contact points found in the narrow phase, or do you go for a = full narrow phase cd each time? Original Message From: Jonathan Henckel [mailto:jhenckel@...] Sent: 15 March 2004 11:33 To: gdalgorithmslist@... Subject: RE: [Algorithms] number of iterations to solve collision = between =20 Igor, I think I understand what you are doing and I will explain how I = solved this problem. The problem is... given three (or more) fast = moving objects, how do you move them (integrate the position over time) = so the all impacts are detected and handled at the correct moment in = time. Is that the question? =20 To do this you should use a TOI heap. See Brian Mirtich's Phd thesis = for a description of the TOI heap. You can keep a persistent global = heap of all pairs in the system (Brian does this) or you can use a = transient heap which is reconstructed on every frame. =20 =20 I recommend the latter by using a broad phase algorithm with swept = bounding volumes. For instance, if the broad phase uses AABB, take = each object, whack a bounding sphere around the center of mass, sweep = the sphere by the vector V*dt where dt is the maximum time step (e.g. = 1/60 sec) which give a capsule, and finally whack an AABB around the = capsule. Then the broad phase returns all pair of objects that can = potentially be touching within the next dt. Next you analyse each pair = (they are NOT ordered, thus AB=3D=3DBA), and you need to determine the = exact TOI (or miss) using GJK or whatever clever narrow phase algorithm = you can think of, and insert each pairs into a TOI heap. Note if a pair = does not hit within dt it is not inserted in the heap. Note that you = may need to use iteration within the narrow phase TOI, i.e. integrate a = little, test nearest distance, repeat. Do not use binary search for = narrow phase TOI, there are much better ways. =20 Once you have a TOI heap, you pop the smallest TOI pair, integrate all = objects up to TOI, solve the impact, repeat popintegratesolve. If the = heap is empty, just integrate up to dt. =20 John =20 From: Igor Kravtchenko I think I shouldn't mention "collision detection" because it clearly = lends to confusion. I'm aware of ODE, broad/narrow phase algorithm, etc. =20 Let me try to rephrase my question. =20 Say your broad phase gives you 3 colliding bodies. They could in fact = potentialy collide. At the current frame, these 3 bodies doesn't collide but they are going = to collide in the next frame in a manner or another if you don't update their position/velocity. So, = I'm talking here about a system that prevent from colliding not which separates collided = entities. =20 So now you have A B C and you know they can all collide each other, you = have to move these bodies properly and indeed prevent them from colliding. My question is = to know the optimal (theorical?) number of iterations for that. =20 Currently, I would have 6 tests:  test1: try to move A at its destination and see if it not collide with = B=20  test2: try to move A at its destination and see if it not collide with = C if not any collision, set A to its destination otherwhise update with = the nearest collided body =20  test3: try to move B at its destination and see if it not collide with = A=20  test4: try to move B at its destination and see if it not collide with = C if not any collision, set B to its destination otherwhise update with = the nearest collided body =20  test5: try to move C at its destination and see if it not collide with = A=20  test6: try to move C at its destination and see if it not collide with = B if not any collision, set C to its destination otherwhise update with = the nearest collided body =20 That's not impulse based. Is there a (wellknown) way to reduce the number of such tests? Hope you get the idea. =20 Igor. =20 ********************************************************************** The information contained in this email and its attachments is confidential. It is intended only for the named addressees=20 and may not be disclosed to anyone else without consent from Blue 52 Games Limited. Blue 52 give no warranty that this email=20 message (including any attachments to it) is free of any virus=20 or other harmful matter and accepts no responsibility for any=20 loss or damage resulting from the recipient receiving, opening or using it.=20 ********************************************************************** 
From: Nguyen Binh <ngbinh@gl...>  20040315 11:44:18

Hi , Sure it's n(n1)/2. BD> the larger applies if AB != BA the smaller if we take AB == BA. BD> Having said that why AB != BA? This does seem a little BD> strange  surely a collision between two bodies is a symmetric BD> thing (at least upto a difference in sign). I think the problem is Igor try to move the object to the exact location of collision so there are situation that what object to move first. So AB != BA. But as I state before, with small time step (50 > 60Hz) and not very fast object we can assume all objects are static to collision detection. Moreover a little penetration is acceptable (because we may not stop the object ontime ) and this depth can be solve very fast by apply contact constraints.  Best regards,  Nguyen Binh Software Engineer Glass Egg Digital Media E.Town Building 7th Floor, 364 CongHoa Street Tan Binh District, HoChiMinh City, VietNam, Phone : +84 8 8109018 Fax : +84 8 8109013 http://www.glassegg.com  
From: Jonathan Henckel <jhenckel@cs...>  20040315 11:35:00

Igor, I think I understand what you are doing and I will explain how I solved this problem. The problem is... given three (or more) fast moving objects, how do you move them (integrate the position over time) so the all impacts are detected and handled at the correct moment in time. Is that the question? To do this you should use a TOI heap. See Brian Mirtich's Phd thesis for a description of the TOI heap. You can keep a persistent global heap of all pairs in the system (Brian does this) or you can use a transient heap which is reconstructed on every frame. I recommend the latter by using a broad phase algorithm with swept bounding volumes. For instance, if the broad phase uses AABB, take each object, whack a bounding sphere around the center of mass, sweep the sphere by the vector V*dt where dt is the maximum time step (e.g. 1/60 sec) which give a capsule, and finally whack an AABB around the capsule. Then the broad phase returns all pair of objects that can potentially be touching within the next dt. Next you analyse each pair (they are NOT ordered, thus AB==BA), and you need to determine the exact TOI (or miss) using GJK or whatever clever narrow phase algorithm you can think of, and insert each pairs into a TOI heap. Note if a pair does not hit within dt it is not inserted in the heap. Note that you may need to use iteration within the narrow phase TOI, i.e. integrate a little, test nearest distance, repeat. Do not use binary search for narrow phase TOI, there are much better ways. Once you have a TOI heap, you pop the smallest TOI pair, integrate all objects up to TOI, solve the impact, repeat popintegratesolve. If the heap is empty, just integrate up to dt. John From: Igor Kravtchenko I think I shouldn't mention "collision detection" because it clearly lends to confusion. I'm aware of ODE, broad/narrow phase algorithm, etc. Let me try to rephrase my question. Say your broad phase gives you 3 colliding bodies. They could in fact potentialy collide. At the current frame, these 3 bodies doesn't collide but they are going to collide in the next frame in a manner or another if you don't update their position/velocity. So, I'm talking here about a system that prevent from colliding not which separates collided entities. So now you have A B C and you know they can all collide each other, you have to move these bodies properly and indeed prevent them from colliding. My question is to know the optimal (theorical?) number of iterations for that. Currently, I would have 6 tests:  test1: try to move A at its destination and see if it not collide with B  test2: try to move A at its destination and see if it not collide with C if not any collision, set A to its destination otherwhise update with the nearest collided body  test3: try to move B at its destination and see if it not collide with A  test4: try to move B at its destination and see if it not collide with C if not any collision, set B to its destination otherwhise update with the nearest collided body  test5: try to move C at its destination and see if it not collide with A  test6: try to move C at its destination and see if it not collide with B if not any collision, set C to its destination otherwhise update with the nearest collided body That's not impulse based. Is there a (wellknown) way to reduce the number of such tests? Hope you get the idea. Igor. 
From: Bob Dowland <Bob.Dowland@bl...>  20040315 10:08:42

hey guys, the difference between these two formulae is just a factor of = two (n^2n) / 2 =3D n(n1) / 2 the larger applies if AB !=3D BA the smaller if we take AB =3D=3D BA. Having said that why AB !=3D BA? This does seem a little strange  = surely a collision between two bodies is a symmetric thing (at least = upto a difference in sign). > Original Message > From: Paul_Firth@... [mailto:Paul_Firth@...] > Sent: 15 March 2004 09:47 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] number of iterations to solve collision > between rigid bodies >=20 >=20 > On 15/03/2004 07:38:07 gdalgorithmslistadmin wrote:=20 >=20 > >=20 > > n! test? > > Well if you have n bodies, you need to test one body again=20 > each other=20 > without=20 > > testing > > against itself. That makes n(n1). Right? >=20 > Nope.=20 >=20 > Its (n^2n) / 2. >=20 > Cheers, Paul. >=20 >=20 > ********************************************************************** > 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@... >=20 > This footnote also confirms that this email message has been checked > for all known viruses. >=20 > ********************************************************************** > SCEE 2004 >=20 >=20 >=20 >  > This SF.Net email is sponsored by: IBM Linux Tutorials > Free Linux tutorial presented by Daniel Robbins, President and CEO of > GenToo technologies. Learn everything from fundamentals to system > = administration.http://ads.osdn.com/?ad_id=3D1470&alloc_id=3D3638&op=3Dcli= ck > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 ********************************************************************** The information contained in this email and its attachments is confidential. It is intended only for the named addressees=20 and may not be disclosed to anyone else without consent from Blue 52 Games Limited. Blue 52 give no warranty that this email=20 message (including any attachments to it) is free of any virus=20 or other harmful matter and accepts no responsibility for any=20 loss or damage resulting from the recipient receiving, opening or using it.=20 ********************************************************************** 
From: <Paul_Firth@sc...>  20040315 09:49:42

On 15/03/2004 07:38:07 gdalgorithmslistadmin wrote: > > n! test? > Well if you have n bodies, you need to test one body again each other without > testing > against itself. That makes n(n1). Right? Nope. Its (n^2n) / 2. 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. ********************************************************************** SCEE 2004 
From: Igor Kravtchenko <igor@ob...>  20040315 07:38:29

n! test? Well if you have n bodies, you need to test one body again each other = without testing against itself. That makes n(n1). Right? In my previous example, I considered the broad phrase was already done. = There is nothing exceptional to grab 3 potential colliding bodies after a broad = phase. The thing that challenged me is the next: Say you have A B C. A can collide with B and B can collide with C. A and = C don't collide. We know this by a broad phrase that (for instance) detected the = collision by the volume each body swept during its time slice. With our current system, we would have 4 callbacks called. First time, = to solve exact collision and make a collision response between A and B. Second time, to solve = collision and [...] between C and B. Then between B and A and finally between B and C. You notice that making a collision response between A and B is not the = same thing than between B and A. Why? Because only *one* body moves at a time. Determining the exact time of collision takes place in the same part of = code than the collision response. At each iteration, we could at the very least stop the = simulator, it always ends up to a system without any collision. Hope to be clear enough (really not easy = to explain in a such vast domain). In the other hand, when I have a look at API like Tokamak or ODE, the = callback function that indicates a collision would be only called twice: one for AB, the other = for BC. My guess is that purely informational and the collision response doesn't = have to occur there. Igor.  Original Message =20 From: Ben Garney=20 To: gdalgorithmslist@...=20 Sent: Monday, March 15, 2004 7:42 AM Subject: Re: [Algorithms] number of iterations to solve collision = between rigid bodies If you have n items the minimum number of comparisons you can make is=20 indeed n!, unless you have some prior knowledge about them. This is = what=20 broad phase stuff is all about. If you are in a state where you can't=20 filter more efficiently, like you seem to be in now, you have to make = n!=20 comparisons. Non impulse based methods: ODE (and many other heavy duty real time=20 physics engines) use constraint based solutions, which usually revolve = around solving sets of linear equations. Then the complexity of the=20 operation depends on the size of the matrix and the algorithm you're=20 using  which may not be any better than O(n!), but it's probably a = lot=20 more robust than an impulse based solution. Hmm... What are you trying to do here, anyway? :/ Regards, Ben Igor Kravtchenko wrote: > =20 > I think I shouldn't mention "collision detection" because it clearly = > lends to confusion. > I'm aware of ODE, broad/narrow phase algorithm, etc. > =20 > Let me try to rephrase my question. > =20 > Say your broad phase gives you 3 colliding bodies. They could in = fact=20 > potentialy collide. > At the current frame, these 3 bodies doesn't collide but they are=20 > going to collide in the next frame > in a manner or another if you don't update their position/velocity.=20 > So, I'm talking here about a > system that prevent from colliding not which separates collided = entities. > =20 > So now you have A B C and you know they can all collide each other,=20 > you have to move these > bodies properly and indeed prevent them from colliding. My question = is=20 > to know the optimal > (theorical?) number of iterations for that. > =20 > Currently, I would have 6 tests: >  test1: try to move A at its destination and see if it not collide=20 > with B >  test2: try to move A at its destination and see if it not collide = with C > if not any collision, set A to its destination otherwhise update = with=20 > the nearest collided body > =20 >  test3: try to move B at its destination and see if it not collide=20 > with A >  test4: try to move B at its destination and see if it not collide = with C > if not any collision, set B to its destination otherwhise update = with=20 > the nearest collided body > =20 >  test5: try to move C at its destination and see if it not collide=20 > with A >  test6: try to move C at its destination and see if it not collide = with B > if not any collision, set C to its destination otherwhise update = with=20 > the nearest collided body > =20 > That's not impulse based. > Is there a (wellknown) way to reduce the number of such tests? > Hope you get the idea. > =20 > Igor. > =20 > >  Original Message  > *From:* Nguyen Binh <mailto:ngbinh@...> > *To:* Igor Kravtchenko <mailto:igor@...> > *Cc:* gdalgorithmslist@... > <mailto:gdalgorithmslist@...> > *Sent:* Monday, March 15, 2004 4:22 AM > *Subject:* Re: [Algorithms] number of iterations to solve > collision between rigid bodies > > Hi Igor, > > IK> Some times ago, I read a thread on this mailing about > IK> collision detection between rigid bodies. > IK> Someone (really don't remember who) told his physic system > only moves one body at a time. > > Maybe that's about the "iterative method" for solving = physics > constraints. The main idea of iterative is that we assume = all > constraints are "local" in very small step, so we can just > iterate through all of them and solve them one by one, after > "reasonable" iterations, (hopefully) we will get = "reasonable" > system. It's different from direct method, that is try to = solve > all constraints simultaneously > big matrix fed to LCP = solver, > huge mem usage,etc.. > > I'd guess many current commercial physics package use = iterative > method. :) > > Here is the descriptive language of it which I taken from = ODE > mailling list: > =20 > //This is an implementation of the iterated/relaxation = algorithm. > //Here is a quick overview of the algorithm per Sergi Valverde's > posts to the > //mailing list: > // > // for i=3D0..N1 do > // for c =3D 0..C1 do > // Solve constraint cth > // Apply forces to constraint bodies > // next > // next > // Integrate bodies =20 > > In this algo. N is the number of iterations. The bigger, the = more > accurate. > > C is the list of constraints > =20 > IK> So far, that was already what we did. For 3 bodies A B C, a > IK> raw algorithm gives test between: > > IK> AB AC > > IK> BA BC > > IK> CA CB > > OK. Collision detection and collision response are two = different > things.(Of course the latter is much more difficult). = Collision > detection is to find which objects are collided. Almost all > collision detection packages have two phase: > 1. Broad phase: Try to eliminate objects that are can't = collide > quickly by testing some sort of bounding volume of them > 2. Narrow phase: Here we only get objects that are likely to > collide so we may get down to detail (triangles,...) > > After collision detection, we have a list of colliding = objects. > Then we have to solve those collision by many ways : > + Penalty method (Google for it...) > + LCP method : Read the "Fast contact forces.." by = David > Baraff. It's the direct method > Or you can use the iterative method. > > You can get the source of a very nice physical package here = : > http://q12.org/ode > > And it has all the nice things I've mentioned. > > Hope that help! > > =20 > Best regards, > > =  > Nguyen Binh > Software Engineer > Glass Egg Digital Media > =20 > E.Town Building=20 > 7th Floor, 364 CongHoa Street > Tan Binh District, > HoChiMinh City, > VietNam, > > Phone : +84 8 8109018 > Fax : +84 8 8109013 > > http://www.glassegg.com <http://www.glassegg.com>; > =  >  This SF.Net email is sponsored by: IBM Linux Tutorials Free Linux tutorial presented by Daniel Robbins, President and CEO of GenToo technologies. Learn everything from fundamentals to system = administration.http://ads.osdn.com/?ad_id=3D1470&alloc_id=3D3638&op=3Dcli= ck _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Ben Garney <beng@ga...>  20040315 06:42:53

If you have n items the minimum number of comparisons you can make is indeed n!, unless you have some prior knowledge about them. This is what broad phase stuff is all about. If you are in a state where you can't filter more efficiently, like you seem to be in now, you have to make n! comparisons. Non impulse based methods: ODE (and many other heavy duty real time physics engines) use constraint based solutions, which usually revolve around solving sets of linear equations. Then the complexity of the operation depends on the size of the matrix and the algorithm you're using  which may not be any better than O(n!), but it's probably a lot more robust than an impulse based solution. Hmm... What are you trying to do here, anyway? :/ Regards, Ben Igor Kravtchenko wrote: > > I think I shouldn't mention "collision detection" because it clearly > lends to confusion. > I'm aware of ODE, broad/narrow phase algorithm, etc. > > Let me try to rephrase my question. > > Say your broad phase gives you 3 colliding bodies. They could in fact > potentialy collide. > At the current frame, these 3 bodies doesn't collide but they are > going to collide in the next frame > in a manner or another if you don't update their position/velocity. > So, I'm talking here about a > system that prevent from colliding not which separates collided entities. > > So now you have A B C and you know they can all collide each other, > you have to move these > bodies properly and indeed prevent them from colliding. My question is > to know the optimal > (theorical?) number of iterations for that. > > Currently, I would have 6 tests: >  test1: try to move A at its destination and see if it not collide > with B >  test2: try to move A at its destination and see if it not collide with C > if not any collision, set A to its destination otherwhise update with > the nearest collided body > >  test3: try to move B at its destination and see if it not collide > with A >  test4: try to move B at its destination and see if it not collide with C > if not any collision, set B to its destination otherwhise update with > the nearest collided body > >  test5: try to move C at its destination and see if it not collide > with A >  test6: try to move C at its destination and see if it not collide with B > if not any collision, set C to its destination otherwhise update with > the nearest collided body > > That's not impulse based. > Is there a (wellknown) way to reduce the number of such tests? > Hope you get the idea. > > Igor. > > >  Original Message  > *From:* Nguyen Binh <mailto:ngbinh@...> > *To:* Igor Kravtchenko <mailto:igor@...> > *Cc:* gdalgorithmslist@... > <mailto:gdalgorithmslist@...> > *Sent:* Monday, March 15, 2004 4:22 AM > *Subject:* Re: [Algorithms] number of iterations to solve > collision between rigid bodies > > Hi Igor, > > IK> Some times ago, I read a thread on this mailing about > IK> collision detection between rigid bodies. > IK> Someone (really don't remember who) told his physic system > only moves one body at a time. > > Maybe that's about the "iterative method" for solving physics > constraints. The main idea of iterative is that we assume all > constraints are "local" in very small step, so we can just > iterate through all of them and solve them one by one, after > "reasonable" iterations, (hopefully) we will get "reasonable" > system. It's different from direct method, that is try to solve > all constraints simultaneously > big matrix fed to LCP solver, > huge mem usage,etc.. > > I'd guess many current commercial physics package use iterative > method. :) > > Here is the descriptive language of it which I taken from ODE > mailling list: > > //This is an implementation of the iterated/relaxation algorithm. > //Here is a quick overview of the algorithm per Sergi Valverde's > posts to the > //mailing list: > // > // for i=0..N1 do > // for c = 0..C1 do > // Solve constraint cth > // Apply forces to constraint bodies > // next > // next > // Integrate bodies > > In this algo. N is the number of iterations. The bigger, the more > accurate. > > C is the list of constraints > > IK> So far, that was already what we did. For 3 bodies A B C, a > IK> raw algorithm gives test between: > > IK> AB AC > > IK> BA BC > > IK> CA CB > > OK. Collision detection and collision response are two different > things.(Of course the latter is much more difficult). Collision > detection is to find which objects are collided. Almost all > collision detection packages have two phase: > 1. Broad phase: Try to eliminate objects that are can't collide > quickly by testing some sort of bounding volume of them > 2. Narrow phase: Here we only get objects that are likely to > collide so we may get down to detail (triangles,...) > > After collision detection, we have a list of colliding objects. > Then we have to solve those collision by many ways : > + Penalty method (Google for it...) > + LCP method : Read the "Fast contact forces.." by David > Baraff. It's the direct method > Or you can use the iterative method. > > You can get the source of a very nice physical package here : > http://q12.org/ode > > And it has all the nice things I've mentioned. > > Hope that help! > >  > Best regards, > >  > Nguyen Binh > Software Engineer > Glass Egg Digital Media > > E.Town Building > 7th Floor, 364 CongHoa Street > Tan Binh District, > HoChiMinh City, > VietNam, > > Phone : +84 8 8109018 > Fax : +84 8 8109013 > > http://www.glassegg.com <http://www.glassegg.com>; >  > 
From: Nguyen Binh <ngbinh@gl...>  20040315 05:49:37

Hi Igor, IK> IK> I think I shouldn't mention "collision detection" because it clearly lends to confusion. IK> I'm aware of ODE, broad/narrow phase algorithm, etc. Yes. I'm quite understand your question now. :) But I think you follow another path than what I think we should follow on physical simulation. So let me have some for you to clarify your methods. IK> Let me try to rephrase my question. IK> IK> Say your broad phase gives you 3 colliding bodies. They could in fact potentialy collide. IK> At the current frame, these 3 bodies doesn't collide but they IK> are going to collide in the next frame IK> in a manner or another if you don't update their IK> position/velocity. So, I'm talking here about a IK> system that prevent from colliding not which separates collided entities. IK> IK> So now you have A B C and you know they can all collide each other, you have to move these IK> bodies properly and indeed prevent them from colliding. My IK> question is to know the optimal IK> (theorical?) number of iterations for that. IK> IK> Currently, I would have 6 tests: IK>  test1: try to move A at its destination and see if it not IK> collide with B  test2: try to move A at its destination and see IK> if it not collide with C IK> if not any collision, set A to its destination otherwhise IK> update with the nearest collided body What does this mean? How can you "update with the nearest collided body"? I don't think it's so simple. Let's consider just two simple spheres follow your comments: The case is : there are two spheres A, B : On test1 : try to move A at its destination and see if it not collide with B The result is : A "will" collide with B then there are two problems: 1) How can you move A to the nearest collided body? Suppose for these simple sphere, you will know how to move A to the exact position that make A and B not collide then you loose many physical characteristics like bouncyness, friction,... 2) The position of B is not in the present but the past. Does you just try to project out *offending points* like in "Advanced Character Physics" in Gamasutra? What I do is : 1) Do collision detection so I get a list of colliding objs. I just take into account current position of objs, so no future here. a) First I use some coarse BVBV test b) Then get into detail. On your case : if there are 3 objs that can potentially collide(That means those 3 objs passed the a) test) then how can we do anything except using n(n1)/2 tests? But exploiting temporal coherence here would do the magic. 2) Create contact constraints for those colliding objs. Those constraints encode physical things like bouncyness, friction force,..etc 3) Solve all constraints (contacts, ball, hinge,..etc) 4) Update all objs to new solved position 5) Render all objs 6) Go back to 1) This method work very well with small time step and not very fast obj. For very fast obj like a bullet, I use a ray instead. IK> Is there a (wellknown) way to reduce the number of such tests? IK> Hope you get the idea. I don't know. But IMHO, if all 3 objs are potentially collide then we have to test them in detail. How could we avoid such? IK> IK> Igor. IK> Hope that I get your idea.  Best regards,  Nguyen Binh Software Engineer Glass Egg Digital Media E.Town Building 7th Floor, 364 CongHoa Street Tan Binh District, HoChiMinh City, VietNam, Phone : +84 8 8109018 Fax : +84 8 8109013 http://www.glassegg.com  
From: Igor Kravtchenko <igor@ob...>  20040315 04:03:30

I think I shouldn't mention "collision detection" because it clearly = lends to confusion. I'm aware of ODE, broad/narrow phase algorithm, etc. Let me try to rephrase my question. Say your broad phase gives you 3 colliding bodies. They could in fact = potentialy collide. At the current frame, these 3 bodies doesn't collide but they are going = to collide in the next frame in a manner or another if you don't update their position/velocity. So, = I'm talking here about a system that prevent from colliding not which separates collided = entities. So now you have A B C and you know they can all collide each other, you = have to move these bodies properly and indeed prevent them from colliding. My question is = to know the optimal (theorical?) number of iterations for that. Currently, I would have 6 tests:  test1: try to move A at its destination and see if it not collide with = B=20  test2: try to move A at its destination and see if it not collide with = C if not any collision, set A to its destination otherwhise update with = the nearest collided body  test3: try to move B at its destination and see if it not collide with = A=20  test4: try to move B at its destination and see if it not collide with = C if not any collision, set B to its destination otherwhise update with = the nearest collided body  test5: try to move C at its destination and see if it not collide with = A=20  test6: try to move C at its destination and see if it not collide with = B if not any collision, set C to its destination otherwhise update with = the nearest collided body That's not impulse based. Is there a (wellknown) way to reduce the number of such tests? Hope you get the idea. Igor.  Original Message =20 From: Nguyen Binh=20 To: Igor Kravtchenko=20 Cc: gdalgorithmslist@...=20 Sent: Monday, March 15, 2004 4:22 AM Subject: Re: [Algorithms] number of iterations to solve collision = between rigid bodies Hi Igor, IK> Some times ago, I read a thread on this mailing about IK> collision detection between rigid bodies. IK> Someone (really don't remember who) told his physic system only = moves one body at a time. Maybe that's about the "iterative method" for solving physics constraints. The main idea of iterative is that we assume all constraints are "local" in very small step, so we can just iterate through all of them and solve them one by one, after "reasonable" iterations, (hopefully) we will get "reasonable" system. It's different from direct method, that is try to solve all constraints simultaneously > big matrix fed to LCP solver, huge mem usage,etc.. I'd guess many current commercial physics package use iterative method. :) Here is the descriptive language of it which I taken from ODE mailling list: =20 //This is an implementation of the iterated/relaxation algorithm. //Here is a quick overview of the algorithm per Sergi Valverde's posts = to the //mailing list: // // for i=3D0..N1 do // for c =3D 0..C1 do // Solve constraint cth // Apply forces to constraint bodies // next // next // Integrate bodies =20 In this algo. N is the number of iterations. The bigger, the more accurate. C is the list of constraints =20 IK> So far, that was already what we did. For 3 bodies A B C, a IK> raw algorithm gives test between: IK> AB AC IK> BA BC IK> CA CB OK. Collision detection and collision response are two different things.(Of course the latter is much more difficult). Collision detection is to find which objects are collided. Almost all collision detection packages have two phase: 1. Broad phase: Try to eliminate objects that are can't collide quickly by testing some sort of bounding volume of them 2. Narrow phase: Here we only get objects that are likely to collide so we may get down to detail (triangles,...) After collision detection, we have a list of colliding objects. Then we have to solve those collision by many ways : + Penalty method (Google for it...) + LCP method : Read the "Fast contact forces.." by David Baraff. It's the direct method Or you can use the iterative method. You can get the source of a very nice physical package here : http://q12.org/ode And it has all the nice things I've mentioned. Hope that help! =20 Best regards,  Nguyen Binh Software Engineer Glass Egg Digital Media =20 E.Town Building =20 7th Floor, 364 CongHoa Street Tan Binh District, HoChiMinh City, VietNam, Phone : +84 8 8109018 Fax : +84 8 8109013 http://www.glassegg.com  
From: Nguyen Binh <ngbinh@gl...>  20040315 03:28:00

Hi Igor, IK> Some times ago, I read a thread on this mailing about IK> collision detection between rigid bodies. IK> Someone (really don't remember who) told his physic system only moves one body at a time. Maybe that's about the "iterative method" for solving physics constraints. The main idea of iterative is that we assume all constraints are "local" in very small step, so we can just iterate through all of them and solve them one by one, after "reasonable" iterations, (hopefully) we will get "reasonable" system. It's different from direct method, that is try to solve all constraints simultaneously > big matrix fed to LCP solver, huge mem usage,etc.. I'd guess many current commercial physics package use iterative method. :) Here is the descriptive language of it which I taken from ODE mailling list: //This is an implementation of the iterated/relaxation algorithm. //Here is a quick overview of the algorithm per Sergi Valverde's posts to the //mailing list: // // for i=0..N1 do // for c = 0..C1 do // Solve constraint cth // Apply forces to constraint bodies // next // next // Integrate bodies In this algo. N is the number of iterations. The bigger, the more accurate. C is the list of constraints IK> So far, that was already what we did. For 3 bodies A B C, a IK> raw algorithm gives test between: IK> AB AC IK> BA BC IK> CA CB OK. Collision detection and collision response are two different things.(Of course the latter is much more difficult). Collision detection is to find which objects are collided. Almost all collision detection packages have two phase: 1. Broad phase: Try to eliminate objects that are can't collide quickly by testing some sort of bounding volume of them 2. Narrow phase: Here we only get objects that are likely to collide so we may get down to detail (triangles,...) After collision detection, we have a list of colliding objects. Then we have to solve those collision by many ways : + Penalty method (Google for it...) + LCP method : Read the "Fast contact forces.." by David Baraff. It's the direct method Or you can use the iterative method. You can get the source of a very nice physical package here : http://q12.org/ode And it has all the nice things I've mentioned. Hope that help!  Best regards,  Nguyen Binh Software Engineer Glass Egg Digital Media E.Town Building 7th Floor, 364 CongHoa Street Tan Binh District, HoChiMinh City, VietNam, Phone : +84 8 8109018 Fax : +84 8 8109013 http://www.glassegg.com  
From: Stephan Rose <kermos@so...>  20040315 00:33:37

Just a test.. Sorry.just making sure any bounces during my nameserver & mailserver switch didn't get me lost on this list. :) Thanks, Stephan 