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
(7) 
2

3

4
(10) 
5
(12) 
6
(15) 
7
(2) 
8
(8) 
9
(7) 
10
(1) 
11
(6) 
12
(7) 
13
(13) 
14
(35) 
15
(17) 
16
(15) 
17
(12) 
18
(4) 
19
(13) 
20

21

22

23
(15) 
24
(6) 
25
(4) 
26
(19) 
27
(33) 
28
(16) 
29
(31) 
30
(30) 

From: Jonathan Blow <jon@nu...>  20040427 21:47:50

> It seems to me like the outcome of thise technique is chaotic (at least > when I tried it > with pen and paper ) Did you test it yet? This is a wellunderstood technique, not something Christer just made up. Do a google search for "Method of Alternating Projections" and then look up the later expansion of the technique, by a guy named Halperin. 
From: PeterPike Sloan <ppsloan@wi...>  20040427 21:47:45

Can't you pose this as a LP problem? Find the point that maximizes the sum of distances to the oriented planes while always being on the correct side? That way you would also know if you have an infeasible set of planes (intersection of positive half spaces is NULL...) PeterPike=20 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Marius Elvert Sent: Tuesday, April 27, 2004 2:21 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Computing brush center from plane equs > You can get a point in the interior of the intersection volume by=20 > alternating projection. That is, start with an arbitrary point. Loop=20 > over all halfspaces in whichever order, projecting the point onto the=20 > hyperplane of the halfspace if it lies outside the halfspace. Repeat=20 > projection until the point lies inside all halfspaces. It seems to me like the outcome of thise technique is chaotic (at least when I tried it with pen and paper ) Did you test it yet? marius  This SF.Net email is sponsored by: Oracle 10g Get certified on the hottest thing ever to hit the market... Oracle 10g.=20 Take an Oracle 10g class now, and we'll give you the exam FREE. http://ads.osdn.com/?ad_id=3D3149&alloc_id=3D8166&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: <LtJax@t...>  20040427 21:20:39

> You can get a point in the interior of the intersection volume by > alternating > projection. That is, start with an arbitrary point. Loop over all > halfspaces > in whichever order, projecting the point onto the hyperplane of the > halfspace > if it lies outside the halfspace. Repeat projection until the point lies > inside all halfspaces. It seems to me like the outcome of thise technique is chaotic (at least when I tried it with pen and paper ) Did you test it yet? marius 
From: <christer_ericson@pl...>  20040427 20:08:40

Macro Corbetta wrote: > [...] >  intersect a line with both planes (this computation is very simple and > fairly fast) now find the middle point of the segment created by > intersecting the line with those 2 planes There's an infinite number of lines, in general, intersecting both planes. The odds of you picking one that passes through the intersection volume of the halfspaces is, um, zero. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: <christer_ericson@pl...>  20040427 20:01:10

Pierre Terdiman wrote: > I have a set of planes in worldspace. They define a convex volume, think > something like a Quake brush. The goal is to compute the vertices of that > volume, from the set of planes. A bruteforce, O(n^4), way of doing this is to consider all combinations of three planes, compute the intersection point of the three planes, then discard those intersection points that lie outside any of the input halfspaces. > But now I have some planes in worldspace, at arbitrary position. I'd like > to translate them so that the origin lies at the center of the volume. So I > need to compute this center, from the planes' equations  that is, without > first computing the actual vertices, of course (since that's the goal...). You can get a point in the interior of the intersection volume by alternating projection. That is, start with an arbitrary point. Loop over all halfspaces in whichever order, projecting the point onto the hyperplane of the halfspace if it lies outside the halfspace. Repeat projection until the point lies inside all halfspaces. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: Jon Watte <hplus@mi...>  20040427 18:33:56

> An algorithm perfectly fine in theory failed in practice because one value > had been kept in FP registers, keeping all the precision, while the other > had been stored to memory. When later those two values got compared for Some compilers have options to force FP data to memory, which may or may not help (I think MSVC calls this "increased FP consistency"). More importantly, you have control over the precision used internally. If your CPU has higher precision internally (say, 80 bits like the x87) than it stores externally (say, 64 bits) then you'll get these problems. The solution is to make sure you compute in a homogenous environment; the easiest way is to set the rounding mode to 53 bits mantissa rather than 69. Note that x87 promotes 32bit float to full register width as well, and other CPUs may also do this, so if this matters, don't use float for your internal calculation datatypes. >  Rewrite the small loop in assembly, where I can make sure the damn values > are kept in FP registers. The only assembly you need in this case is "fnstcw" to make sure the internal precision matches the external precision. Oh, and when you mix values, it gets even better when you start thinking about denormals. One over a denormal is infinity. Zero times infinity is infinity. Make sure you always go denormal in a consistent way, or, even better, always slam denormals to 0 for your datatype. Cheers, / h+ 
From: Newport, Matthew <mnewport@ea...>  20040427 17:39:22

Can't you set the FPU control word to use double precision rather than double extended precision for code that exhibits these kinds of problems? That way the FPU uses 64 bit rather than 80 bit floating point in the registers. Matt. Original Message From: Simon Fenney [mailto:simonf@...]=20 Sent: Tuesday, April 27, 2004 8:51 AM To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] EPA : working ? >Most compilers have an option to "improving floating point=20 >consistency"=20 >(/fp) which will force the values to be stored back to floats in=20 >memory. This makes it consistent, but unfortunately makes it=20 >consistent in=20 >the lowprecision way. The alternative is just to store doubles. > >Charles Bloom email "cb" http://www.cbloom.com=20 > That still doesn't solve the problem with x86 because it has 80bit internal(/infernal) registers. :( I ended up putting in explicit code wherever comparisons for convergence were done so that anything that was denormalised/smaller than could be done in single precision was forced to be zero. Simon > >At 03:36 PM 4/27/2004 +0200, you wrote: >>An algorithm perfectly fine in theory failed in practice=20 >because one value >>had been kept in FP registers, keeping all the precision,=20 >while the other >>had been stored to memory. When later those two values got=20 >compared for >>equality, the comparison failed although those values were=20 >perfectly equal >>to begin with. Bad luck, the algo was waiting for such an equality to >>actually exit :( > > > > > > > >This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek >For a limited time only, get FREE Ground shipping on all orders of $35 >or more. Hurry up and shop folks, this offer expires April 30th! >http://www.thinkgeek.com/freeshipping/?cpg=3D12297 >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > ****************** This email has been sent from Imagination Technologies Limited. =20 PowerVR, Metagence, Ensigma and PURE Digital are divisions=20 of Imagination Technologies Limited. The information contained in this email, including any attachment,=20 is confidential and may be legally privileged. It is intended solely=20 for the addressee(s) and access to this email by anyone else is=20 unauthorised. If you are not the intended recipient, any disclosure,=20 copying or distribution or use of the information contained in this=20 email, is prohibited and may be unlawful. If you have received this email in error, please notify the sender by return email and then=20 delete it from your system. Internet communications cannot be guaranteed to be secure,=20 error or virusfree. The sender does not accept liability for any errors=20 or omissions which arise as a result. Any views expressed in this message are those of the author, except=20 where the author specifies and, with authority, states them to be the=20 views of Imagination Technologies Ltd.  This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek For a limited time only, get FREE Ground shipping on all orders of $35 or more. Hurry up and shop folks, this offer expires April 30th! http://www.thinkgeek.com/freeshipping/?cpg=3D12297 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: <robin_green@pl...>  20040427 16:54:08

Message: 16 From: Guillaume Provost <Guillaume@...> Date: Mon, 26 Apr 2004 15:20:35 0400 Subject: [Algorithms] Approximating the pow() function > > Sorry for asking a really dumb question, but have any of you worked around > this issue? I want a cheap and fast approximation to the pow( ) function > without going through the standard math libs (this needs to be platform > independant / IEEE single precision floating point format). Well, if you're going to get into coding fast versions of the mathematical functions, starting with the single most difficult one to code accurately is a great place to start! > Unfortunately, the (relatively small) error introduced by the log base 2 gets > compounded when I compute the exponential portion. This results in a +50% > (or one exponential bit) in relative accuracy when dealing with higher > exponent values. Yup. In the book "Elementary Functions: Algorithms and Implementations" by JeanMichel Muller, he describes how bad the problem can be (p.178, "Notes on x^y") The power function F(x,y) = x^y is very difficult to implement if we want good accuracy. A straightforward use of the relationship x^y = exp(y*ln(x)) is to be avoided. First, it will always produce NaNs for negative values of x, although x^y is defined when x<0 and y is an integer. Second, unless the intermediate calculations are performed with a significantly larger precision, that formula may lead to very large relative errors. Assume that ln(x) is computed with relative error "r", that is the computed value oL of ln(x) satisfies: L = (1 + r) ln(x) If we neglect the error due to the implementation of the exponential function itself, we find that the computed value of x^y will be: exp(y*L) = exp(y*ln(x) + y*r*ln(x)) = x^y * e^(r*y*ln(x)) Therefore the error on the result,  r*y*ln(x)   e  1  > r*y*ln(x) can be very large (FOOTNOTE: Some programming languages avoid this problem by not offering function x^y. Of course, this is the best way to make sure that most programmers will use the bad solution exp(y*ln(x)) ) He then goes on to show some especially bad results along the number line (e.g. 5^441 has an error of 791 units_in_the_last_place (ulps), 56^156 has 1052 ulps). Basically, your lower bits are mush. The only way around this, he goes on to prove, is to use more bits of accuracy in the intermediate ln() calculation: Thus, to get a correct result, we must get ln(x) with a number of additional bits of precision that are slightly more than the number of exponent bits. So for IEEE754 values, you'll need to calculate ln(x) to at least 24+8=32 bits of mantissa. How is this done? By splitting the result across two floating point values, one carrying the upper bits and the remainder carrying the lower bits. ln(x) = a + b > Is there any other way to cheaply approximate pow( ) in a more precise way? > (Code appended). I thought about using a polynomial to interpolate the > mantissa portion across exponent values, but that only decreases the average > error  not the worst case error. I hope you can see that the answer to your question is no, there really is no way to accurately *and* quickly approximate the power function. This leads me to ask the killer question  *why* do you need the power function exactly? Are you looking for a fast way to shape specular reflection lobes? If you are, then there are other functions you can use: integer powers, polynomial approximations or rational functions. Christopher Schlick in Graphics Gems 4 has a paper on "A Fast Alternative to Phong's Specular Model" (p.385) where her proposes the function: S(n,t) = t / (n  n*t + t) where t varies from [0,1] and n is the "shaping power". He also has faster versions of bias() and gain() later in the book, again using a small rational approximation. Restricting yourself to integer powers can give fastish results: float powi(float x,int N) { float y,w; bool ns = false; bool xs = false; if(N<0) { ns = true; N = N; } if(x<0.0f) { xs = true; x = x; } if(N&1) y = x; else { y = 1.0f; xs = false; } w = x; N >>= 1; while(N) { w = w * w; if(N&1) y *= w; N >>= 1; } if(xs) y = y; if(ns) y = 1.0f/y; return y; } as can a rather nice floatingpoint hack, courtesy Matthew Jones of Infogrames, where you take a float, pretend that it's an integer and covert the result to a float. A magic constant is subtracted and the result is converted back to an integer. The resulting bit pattern is used as a float. Confused yet? Check out the last section in my GDC talk about Faster Math Functions for a better explanation: http://www.research.scea.com/gdc2003/fastmathfunctions.html  Robin Green R&D Programmer SCEA 
From: Jamie Fowlston <jamief@qu...>  20040427 16:05:54

the only time i've been bitten by the problem is when i take the return value of a function and immediately compare it to something that's been stored in memory. If you take the return value, and put it in a float variable before performing the comparison, it seems to behave itself. I'm no language or compiler lawyer, so i can't guarantee this will sort every case, but you may like to try it. jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Simon Fenney Sent: 27 April 2004 16:51 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] EPA : working ? >Most compilers have an option to "improving floating point >consistency" >(/fp) which will force the values to be stored back to floats in >memory. This makes it consistent, but unfortunately makes it >consistent in >the lowprecision way. The alternative is just to store doubles. > >Charles Bloom email "cb" http://www.cbloom.com > That still doesn't solve the problem with x86 because it has 80bit internal(/infernal) registers. :( I ended up putting in explicit code wherever comparisons for convergence were done so that anything that was denormalised/smaller than could be done in single precision was forced to be zero. Simon > >At 03:36 PM 4/27/2004 +0200, you wrote: >>An algorithm perfectly fine in theory failed in practice >because one value >>had been kept in FP registers, keeping all the precision, >while the other >>had been stored to memory. When later those two values got >compared for >>equality, the comparison failed although those values were >perfectly equal >>to begin with. Bad luck, the algo was waiting for such an equality to >>actually exit :( > > > > > > > >This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek >For a limited time only, get FREE Ground shipping on all orders of $35 >or more. Hurry up and shop folks, this offer expires April 30th! >http://www.thinkgeek.com/freeshipping/?cpg=12297 >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ****************** This email has been sent from Imagination Technologies Limited. PowerVR, Metagence, Ensigma and PURE Digital are divisions of Imagination Technologies Limited. The information contained in this email, including any attachment, is confidential and may be legally privileged. It is intended solely for the addressee(s) and access to this email by anyone else is unauthorised. If you are not the intended recipient, any disclosure, copying or distribution or use of the information contained in this email, is prohibited and may be unlawful. If you have received this email in error, please notify the sender by return email and then delete it from your system. Internet communications cannot be guaranteed to be secure, error or virusfree. The sender does not accept liability for any errors or omissions which arise as a result. Any views expressed in this message are those of the author, except where the author specifies and, with authority, states them to be the views of Imagination Technologies Ltd.  This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek For a limited time only, get FREE Ground shipping on all orders of $35 or more. Hurry up and shop folks, this offer expires April 30th! http://www.thinkgeek.com/freeshipping/?cpg=12297 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Simon Fenney <simonf@vi...>  20040427 15:51:32

>Most compilers have an option to "improving floating point >consistency" >(/fp) which will force the values to be stored back to floats in >memory. This makes it consistent, but unfortunately makes it >consistent in >the lowprecision way. The alternative is just to store doubles. > >Charles Bloom email "cb" http://www.cbloom.com > That still doesn't solve the problem with x86 because it has 80bit internal(/infernal) registers. :( I ended up putting in explicit code wherever comparisons for convergence were done so that anything that was denormalised/smaller than could be done in single precision was forced to be zero. Simon > >At 03:36 PM 4/27/2004 +0200, you wrote: >>An algorithm perfectly fine in theory failed in practice >because one value >>had been kept in FP registers, keeping all the precision, >while the other >>had been stored to memory. When later those two values got >compared for >>equality, the comparison failed although those values were >perfectly equal >>to begin with. Bad luck, the algo was waiting for such an equality to >>actually exit :( > > > > > > > >This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek >For a limited time only, get FREE Ground shipping on all orders of $35 >or more. Hurry up and shop folks, this offer expires April 30th! >http://www.thinkgeek.com/freeshipping/?cpg=12297 >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ****************** This email has been sent from Imagination Technologies Limited. PowerVR, Metagence, Ensigma and PURE Digital are divisions of Imagination Technologies Limited. The information contained in this email, including any attachment, is confidential and may be legally privileged. It is intended solely for the addressee(s) and access to this email by anyone else is unauthorised. If you are not the intended recipient, any disclosure, copying or distribution or use of the information contained in this email, is prohibited and may be unlawful. If you have received this email in error, please notify the sender by return email and then delete it from your system. Internet communications cannot be guaranteed to be secure, error or virusfree. The sender does not accept liability for any errors or omissions which arise as a result. Any views expressed in this message are those of the author, except where the author specifies and, with authority, states them to be the views of Imagination Technologies Ltd. 
From: Charles Bloom <cb@cb...>  20040427 15:38:22

Most compilers have an option to "improving floating point consistency" (/fp) which will force the values to be stored back to floats in memory. This makes it consistent, but unfortunately makes it consistent in the lowprecision way. The alternative is just to store doubles. At 03:36 PM 4/27/2004 +0200, you wrote: >An algorithm perfectly fine in theory failed in practice because one value >had been kept in FP registers, keeping all the precision, while the other >had been stored to memory. When later those two values got compared for >equality, the comparison failed although those values were perfectly equal >to begin with. Bad luck, the algo was waiting for such an equality to >actually exit :(  Charles Bloom email "cb" http://www.cbloom.com 
From: <Paul_Firth@sc...>  20040427 14:48:51

On 27/04/2004 15:34:23 gdalgorithmslistadmin wrote: >Yeah, but then again, isn't every boundary traversal algorithm? > > David Wu of Pseudo Interactive uses enhanced GJK with penalty methods to > enforce collision constraints. Of course if you really want to use > penalty methods in a game then you're going to need an Astable I'm not sure that I do (want to that is). I currently use an itterative impulse based system which is very stable and handles contact and all that jazz. Currently, however it handles penetration by factoring it in to the impulse calc rather than preventing it completly. Hence my current need for a fast collision system which works with penetrating polyhedra. 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: Nick Newson \(Circle Studio Ltd\) <Nick.Newson@ci...>  20040427 14:32:33

Yeah, but then again, isn't every boundary traversal algorithm? David Wu of Pseudo Interactive uses enhanced GJK with penalty methods to enforce collision constraints. Of course if you really want to use penalty methods in a game then you're going to need an Astable integrator, but that's another story. Check out David Wu's excellent GDC talks for a full description. Nick. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Paul_Firth@... Sent: 27 April 2004 15:18 To: gdalgorithmslist@... Subject: RE: [Algorithms] EPA : working ? On 27/04/2004 14:20:24 gdalgorithmslistadmin wrote:=20 >Not with the witness points exclusively. Figure 8 (b) in Mirtich's > paper "VClip: Fast and robust polyhedral collision detection" shows an > example where this is not the case. The witness points are intersection > points, however  there may be other points that are penetrating the > volume, but not intersecting the boundary. >=20 > You could still traverse the dual graph of the boundary to calculate the > maximum local penetrating depth. The expense of this depends on the > complexity of your volume. You'd have to update the closest Voronoi > region on each volume as you traversed them to ensure the set you'd be > looking at was only part of the penetrating primitives, but this still > doesn't feel efficient  it's still too global. Mmmm, so I guess vclip is another one which suffers from local minima. Are there *any* fast collision routines which correctly compute minimum directed distance including under penetration? As an aside, what do most people do for rigid body sims? Do you do it all with intervals and time of 1st contact or subdividing time until=20 you're within a threshold? What about for contact when there might be slight penetration due to inaccuracies, won't these routines be in trouble? 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  This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek For a limited time only, get FREE Ground shipping on all orders of $35 or more. Hurry up and shop folks, this offer expires April 30th! http://www.thinkgeek.com/freeshipping/?cpg=3D12297 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: <Paul_Firth@sc...>  20040427 14:18:04

On 27/04/2004 14:20:24 gdalgorithmslistadmin wrote: >Not with the witness points exclusively. Figure 8 (b) in Mirtich's > paper "VClip: Fast and robust polyhedral collision detection" shows an > example where this is not the case. The witness points are intersection > points, however  there may be other points that are penetrating the > volume, but not intersecting the boundary. > > You could still traverse the dual graph of the boundary to calculate the > maximum local penetrating depth. The expense of this depends on the > complexity of your volume. You'd have to update the closest Voronoi > region on each volume as you traversed them to ensure the set you'd be > looking at was only part of the penetrating primitives, but this still > doesn't feel efficient  it's still too global. Mmmm, so I guess vclip is another one which suffers from local minima. Are there *any* fast collision routines which correctly compute minimum directed distance including under penetration? As an aside, what do most people do for rigid body sims? Do you do it all with intervals and time of 1st contact or subdividing time until you're within a threshold? What about for contact when there might be slight penetration due to inaccuracies, won't these routines be in trouble? 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: Pierre Terdiman <pierre.terdiman@no...>  20040427 13:26:11

> You wouldn't be running this sort of code on an x86 would you? I had > nightmares with some of my own code (PVRTC texture compressor) that ran > perfectly well on a sensible architecture (eg Sparc, HP) where you ALWAYS > got the same FP precision. > > With x86 the precision depends on the whims of the compiler as to what stays > in the internal registers. It's of course running on a perfectly plain old x86, and I ran into exactly that sort of issues no later than last week. An algorithm perfectly fine in theory failed in practice because one value had been kept in FP registers, keeping all the precision, while the other had been stored to memory. When later those two values got compared for equality, the comparison failed although those values were perfectly equal to begin with. Bad luck, the algo was waiting for such an equality to actually exit :( I found three fixes :  Change the algo. Not nice since it's otherwise cute and fine and fast.  Force the compiler to actually recompute the same value all over again instead of caching it. Worked in my case, but was slower, and who knows it's not going to be stored to memory anyway the day I compile with VC7 ?  Rewrite the small loop in assembly, where I can make sure the damn values are kept in FP registers. ...well, I now have more assembly in my codebase. Sigh. I think Solid's bug is less subtle than that, however.  Pierre 
From: Gino van den Bergen <gvandenbergen@pl...>  20040427 13:19:03

> Original Message > From: gdalgorithmslistadmin@... [mailto:gdalgorithms > listadmin@...] On Behalf Of Paul_Firth@... > Sent: Tuesday, April 27, 2004 12:29 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] EPA : working ? >=20 > Hmmm, the title of Cameron's GJK paper "enhancing gjk: computing minimum > and penetration > distances between convex polyhedra" leads me to believe that this varient > does > at least... >=20 Cameron's penetration depth computation in that paper is an approximation returning a lower and upper bound for the penetration depth. The returned penetration depth vector's direction may differ considerably from the actual penetration depth. =20 > > > I did try vclip myself briefly, but I couldn't get it to work quite > right > > > and reverted > > > back to my partially explicit minkowski sum routine until I have some > more > > > time to play with vclip. > > > > Last time I checked, VClip didn't handle penetrating cases either. >=20 > The paper on vclip says it does handle penetration. >=20 > http://www.merl.com/papers/TR9705/ >=20 > Cheers, Paul. I think Mirtich's claim is that VClip *detects* penetrations. In contrast with the original LinCanny feature tracking algorithm as used in ICOLLIDE, VClip does not rely on a linear programming solver for detecting interpenetrations. VClip does not compute a penetration depth vector. GJK and VClip are algorithms for computing the closest points, and can be used for penetration depth computation for spherically expanded polyhedra. The sphere that is added to the boundary serves as a skin offset from the polyhedron (the bone). As long as the skins interpenetrate but the bones do not, the vector formed by the closest points is nonzero and points in the direction of the penetration depth. The actual depth is the sum of the radii minus the distance. If you can avoid the bones from interpenetrating then this method is much faster and more robust than a true penetration depth computation. Gino van den Bergen http://www.dtecta.com =20 =20 
From: Nick Newson \(Circle Studio Ltd\) <Nick.Newson@ci...>  20040427 13:18:34

Not with the witness points exclusively. Figure 8 (b) in Mirtich's paper "VClip: Fast and robust polyhedral collision detection" shows an example where this is not the case. The witness points are intersection points, however  there may be other points that are penetrating the volume, but not intersecting the boundary. You could still traverse the dual graph of the boundary to calculate the maximum local penetrating depth. The expense of this depends on the complexity of your volume. You'd have to update the closest Voronoi region on each volume as you traversed them to ensure the set you'd be looking at was only part of the penetrating primitives, but this still doesn't feel efficient  it's still too global. Cheers, Nick. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Paul_Firth@... Sent: 27 April 2004 13:44 To: gdalgorithmslist@... Subject: RE: [Algorithms] EPA : working ? On 27/04/2004 12:47:55 gdalgorithmslistadmin wrote:=20 >VClip does correctly identify penetrating objects as intersecting. > However, it only gives local witnesses to penetration, so this will not > give an accurate value for penetration depth. Marvellous. Actually, can't you easily work out the penetration from the witness points? Vertex/face, face/vertex, edge/edge and get a penetration measure from that? > If you had the linear velocities of the objects you can work this out > however via the projection onto the relative velocity of the movement > required to separate the object (along the relative velocity  > effectively pushing the objects apart to the position of first contact). No good if your objects aren't moving, though. 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  This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek For a limited time only, get FREE Ground shipping on all orders of $35 or more. Hurry up and shop folks, this offer expires April 30th! http://www.thinkgeek.com/freeshipping/?cpg=3D12297 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: <Paul_Firth@sc...>  20040427 12:44:32

On 27/04/2004 12:47:55 gdalgorithmslistadmin wrote: >VClip does correctly identify penetrating objects as intersecting. > However, it only gives local witnesses to penetration, so this will not > give an accurate value for penetration depth. Marvellous. Actually, can't you easily work out the penetration from the witness points? Vertex/face, face/vertex, edge/edge and get a penetration measure from that? > If you had the linear velocities of the objects you can work this out > however via the projection onto the relative velocity of the movement > required to separate the object (along the relative velocity  > effectively pushing the objects apart to the position of first contact). No good if your objects aren't moving, though. 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: Pierre Terdiman <pierre.terdiman@no...>  20040427 12:43:07

BTW it's not just an epsilon issue: at some point I found a redundant vertex in "computeClosest()", i.e. v1 or v2 was exactly the same as p0. So the determinant is exactly zero is this case, no matter what.  Pierre 
From: Simon Fenney <simonf@vi...>  20040427 12:04:40

>Original Message >From: Pierre Terdiman [mailto:pierre.terdiman@...] >Sent: 27 April 2004 12:48 >To: gdalgorithmslist@... >Subject: Re: [Algorithms] EPA : working ? > > >>Try enlarging these by an order of magnitude: > >It didn't change anything. However I noticed 2 things : > >1) In a particular scene, the Debug version failed while the >Release version >worked. However the Release version still failed for another scene. You wouldn't be running this sort of code on an x86 would you? I had nightmares with some of my own code (PVRTC texture compressor) that ran perfectly well on a sensible architecture (eg Sparc, HP) where you ALWAYS got the same FP precision. With x86 the precision depends on the whims of the compiler as to what stays in the internal registers. Simon ****************** This email has been sent from Imagination Technologies Limited. PowerVR, Metagence, Ensigma and PURE Digital are divisions of Imagination Technologies Limited. The information contained in this email, including any attachment, is confidential and may be legally privileged. It is intended solely for the addressee(s) and access to this email by anyone else is unauthorised. If you are not the intended recipient, any disclosure, copying or distribution or use of the information contained in this email, is prohibited and may be unlawful. If you have received this email in error, please notify the sender by return email and then delete it from your system. Internet communications cannot be guaranteed to be secure, error or virusfree. The sender does not accept liability for any errors or omissions which arise as a result. Any views expressed in this message are those of the author, except where the author specifies and, with authority, states them to be the views of Imagination Technologies Ltd. 
From: Nick Newson \(Circle Studio Ltd\) <Nick.Newson@ci...>  20040427 11:46:09

VClip does correctly identify penetrating objects as intersecting. However, it only gives local witnesses to penetration, so this will not give an accurate value for penetration depth. If you had the linear velocities of the objects you can work this out however via the projection onto the relative velocity of the movement required to separate the object (along the relative velocity  effectively pushing the objects apart to the position of first contact). Cheers, Nick. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Paul_Firth@... Sent: 27 April 2004 11:29 To: gdalgorithmslist@... Subject: Re: [Algorithms] EPA : working ? On 27/04/2004 10:16:58 gdalgorithmslistadmin wrote:=20 >> I was under the impression that GJK was the normal recommened tool for=20 the > > job (even though its slower under penetration), but I guess you ruled=20 that > > out already since EPA is based on it? >=20 > AFAIK GJK doesn't work when objects are penetrating. What works is the > extension of GJK named EPA. So I didn't "rule out" GJK, it's just not=20 enough > alone. Hmmm, the title of Cameron's GJK paper "enhancing gjk: computing minimum and penetration distances between convex polyhedra" leads me to believe that this varient=20 does at least... > > I did try vclip myself briefly, but I couldn't get it to work quite=20 right > > and reverted > > back to my partially explicit minkowski sum routine until I have some=20 more > > time to play with vclip. >=20 > Last time I checked, VClip didn't handle penetrating cases either. The paper on vclip says it does handle penetration. http://www.merl.com/papers/TR9705/ 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  This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek For a limited time only, get FREE Ground shipping on all orders of $35 or more. Hurry up and shop folks, this offer expires April 30th! http://www.thinkgeek.com/freeshipping/?cpg=3D12297 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Pierre Terdiman <pierre.terdiman@no...>  20040427 11:37:53

>Try enlarging these by an order of magnitude: It didn't change anything. However I noticed 2 things : 1) In a particular scene, the Debug version failed while the Release version worked. However the Release version still failed for another scene. 2) There's another reason why it can reach the part of the code I mentioned. That's when this method fails : if (facet>computeClosest(yBuf)) { ... } i.e. when this is false : if (m_det > MT_Scalar(0.0)) Apparently that's what happens for failing cases. I get this : v1dv1 * v2dv2  v1dv2 * v1dv2 = 1.5281926835086779e009 ...which gets truncated to 0 for m_det. Perhaps compiling using doubles will help, but it doesn't look like a fix  just a way to hide the bug. I tried a few workarounds. Just executing the first branch above all the time actually does fix the scene that failed or not in Debug/Release. However it doesn't fix all problems (in particular, my box stack still collapses). It should give you an idea of what's happening, nonetheless. I'm really interested in a fix for this one :)  Pierre 
From: Marco Corbetta <marco@cr...>  20040427 11:10:05

If they always define a convex volume, something like the following may work, although I haven't tried it in practice:  Search for the 2 planes having the most "opposite" normals (like 0,0,1 and 0,0,1) =20  intersect a line with both planes (this computation is very simple and fairly fast) now find the middle point of the segment created by intersecting the line with those 2 planes  find the middle point using other 2 opposite planes, then compute the distance from the previous middle point, average the values to get your approximate brush center. if you repeat that for all opposite planes in a convex volume, you should eventually get to the center of the brush, but I guess you could stop when the distance calculation gets below a certain threshold value (that means you're already getting close enough to the center) Let me know if that works :) Marco C. Crytek Original Message From: Pierre Terdiman [mailto:pierre.terdiman@...]=20 Sent: Montag, 26. April 2004 18:00 To: gdalgorithmslist@... Subject: [Algorithms] Computing brush center from plane equs Hi, I have a set of planes in worldspace. They define a convex volume, think something like a Quake brush. The goal is to compute the vertices of that volume, from the set of planes. The way I did that before was to convert the planes to dual space, compute a convex hull in that space, convert it back, and this gives the desired vertices. Until now my planes where defined in local space, and the origin was always guaranteed to be inside the volume, so there was no problem with the dual transform. But now I have some planes in worldspace, at arbitrary position. I'd like to translate them so that the origin lies at the center of the volume. So I need to compute this center, from the planes' equations  that is, without first computing the actual vertices, of course (since that's the goal...). I came up with an iterative algo that somehow seems to work, but I'm not even sure to understand why. So I'd like something better. Any ideas ? I'd like to avoid doing the actual clipping....  Pierre  This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek For a limited time only, get FREE Ground shipping on all orders of $35 or more. Hurry up and shop folks, this offer expires April 30th! http://www.thinkgeek.com/freeshipping/?cpg=3D12297 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 ____ This message contains confidential information and is intended only for = the individual named. If you are not the named addressee you should not = disseminate, distribute or copy this email. Please notify the sender = immediately by email if you have received this email by mistake and = delete this email from your system. Email transmission cannot be = guaranteed to be secure or errorfree as information could be intercepted, = corrupted, lost, destroyed, arrive late or incomplete, or contain viruses. = The sender therefore does not accept liability for any errors or omissions = in the contents of this message, which arise as a result of email = transmission. If verification is required please request a hardcopy = version. Crytek GmbH  http:// http://www.crytek.com 
From: <Paul_Firth@sc...>  20040427 10:37:07

On 27/04/2004 11:05:53 gdalgorithmslistadmin wrote: >Hello everybody, > > Could you share you experience on using stripified geometry for rendering? > I am particularly interested on stripe usefulness on PS2 platform. So far I've > heard > > mixed opinions on this  some people say we HAVE TO use stripes 'cause > they conserve VU memory and improve performance; others say > we would be better of using indexed primitives because it simplifies building > the > geometry, and that level geometry is not really easily stripifiable. > Maybe the answer is to use stripes for character models (which should be better > stripifiable), and use indexed primitives for level geometry? > > What do you people think? Strip it. I.e. everything. If you have really heavy lighting use indexed tristrips for the skins. You can even do a cunning reverse indexing where each vertex gets written to two locations within the output buffer on vu  this avoids the nasty memory lookup overhead of indices on vu. 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: <Paul_Firth@sc...>  20040427 10:29:17

On 27/04/2004 10:16:58 gdalgorithmslistadmin wrote: >> I was under the impression that GJK was the normal recommened tool for the > > job (even though its slower under penetration), but I guess you ruled that > > out already since EPA is based on it? > > AFAIK GJK doesn't work when objects are penetrating. What works is the > extension of GJK named EPA. So I didn't "rule out" GJK, it's just not enough > alone. Hmmm, the title of Cameron's GJK paper "enhancing gjk: computing minimum and penetration distances between convex polyhedra" leads me to believe that this varient does at least... > > I did try vclip myself briefly, but I couldn't get it to work quite right > > and reverted > > back to my partially explicit minkowski sum routine until I have some more > > time to play with vclip. > > Last time I checked, VClip didn't handle penetrating cases either. The paper on vclip says it does handle penetration. http://www.merl.com/papers/TR9705/ 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 