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}

S  M  T  W  T  F  S 






1
(17) 
2
(3) 
3
(4) 
4
(14) 
5
(12) 
6
(16) 
7
(28) 
8
(28) 
9
(12) 
10
(5) 
11
(17) 
12
(16) 
13
(37) 
14
(26) 
15
(10) 
16
(1) 
17
(2) 
18
(11) 
19
(9) 
20
(22) 
21
(14) 
22
(23) 
23
(4) 
24
(2) 
25
(16) 
26
(6) 
27
(3) 
28
(5) 
29
(4) 
30
(2) 
From: Thatcher Ulrich <tu@tu...>  20021114 23:46:58

20 * Log(2) ~= 6 dB On Nov 14, 2002 at 06:04 0500, Michael Pohoreski wrote: > > Wouldn't that be Log(20) / 5 = 6.505... ? > > Cheers > > Original Message > From: Jon Watte [mailto:hplus@...] > > dB are defined as 20 dB for a 10x increase in voltage. This > comes out to 6.0xxx dB per 2x increase. > > Cheers, > > / h+  Thatcher Ulrich http://tulrich.com 
From: Michael Pohoreski <MP<ohoreski@cy...>  20021114 23:04:25

Wouldn't that be Log(20) / 5 =3D 6.505... ? =20 Cheers Original Message From: Jon Watte [mailto:hplus@...]=20 Sent: Thursday, November 14, 2002 3:50 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] Logarithmic Volume vs. Linear Voltage ? =09 =09 =20 dB are defined as 20 dB for a 10x increase in voltage. This comes out to 6.0xxx dB per 2x increase. =20 Cheers, =20 / h+ =20 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Michael Pohoreski Sent: Thursday, November 14, 2002 12:14 PM To: Game Dev Algorithms Subject: [Algorithms] Logarithmic Volume vs. Linear Voltage ? =09 =09 Is there a formula to convert a logarithmic volume to/from a linear voltage? The PS2 uses a linear voltage, but DirectX uses a logarithmic volume. I'm trying to match the two up. i.e. Our engine accepts a percentage volume; how do I convert this volume to it's "native" value for each platform? One of the posts in the PS2 SPU newsgroup mentioned doubling the voltage gives a +6 dB increase, but I don't see where this values comes from. We now return you to our regularly scheduled debate on floatingpoint precision and epsilons...:) Lots of good info in that thread! 
From: Manny <manny@si...>  20021114 20:56:04

Looking into this a few months back I came up with: DirectSound: "V" = Volume 0 = 0 decibels 10000 = 100 decibels decibels is a logarithmic scale based on 10 ^ x want "Q" , linear such that 0.0 = silence and 1.0 = full volume then Q = 10 ^ (1 / 1000)(V) V = (1000)(log Q) (but note that Q = 0 is undefined, just map it to 10000) I found substituting 2500 for 1000 "sounded better" while playing with the volume slider a number > 1000 maps the linear Q onto less than the entire 10000 range Manny At 03:14 PM 11/14/2002 0500, you wrote: >Is there a formula to convert a logarithmic volume to/from a linear >voltage? The PS2 uses a linear voltage, but DirectX uses a logarithmic >volume. I'm trying to match the two up. i.e. Our engine accepts a >percentage volume; how do I convert this volume to it's "native" value for >each platform? > >One of the posts in the PS2 SPU newsgroup mentioned doubling the voltage >gives a +6 dB increase, but I don't see where this values comes from. > >We now return you to our regularly scheduled debate on floatingpoint >precision and epsilons&:) Lots of good info in that thread! 
From: Jon Watte <hplus@mi...>  20021114 20:50:58

Logarithmic Volume vs. Linear Voltage ? dB are defined as 20 dB for a 10x increase in voltage. This comes out to 6.0xxx dB per 2x increase. Cheers, / h+ Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Michae= l Pohoreski Sent: Thursday, November 14, 2002 12:14 PM To: Game Dev Algorithms Subject: [Algorithms] Logarithmic Volume vs. Linear Voltage ? Is there a formula to convert a logarithmic volume to/from a linear voltage? The PS2 uses a linear voltage, but DirectX uses a logarithmic volume. I'm trying to match the two up. i.e. Our engine accepts a percentage volume; how do I convert this volume to it's "native" value fo= r each platform? One of the posts in the PS2 SPU newsgroup mentioned doubling the voltag= e gives a +6 dB increase, but I don't see where this values comes from. We now return you to our regularly scheduled debate on floatingpoint precision and epsilons=85:) Lots of good info in that thread! 
From: <christer_ericson@pl...>  20021114 20:39:38

Ville Miettinen wrote: >Charles, I don't think that really contradicts my definition. Perhaps I >should've just formulated it a bit better. The way I understand it, >"robustness", when referring to algorithms (and the usage here differs >somewhat from the mainstream usage of the word) is an absolute quality of >an algorithm; for a certain input domain, within defined error bounds, the >algorithm operates as advocated. If there is even a single case where >inside the input domain an incorrect (i.e. outside the error bounds) >answer is received, the algorithm just is not robust. So, yes, I'd >definitely agree that such a convex hull code would be (or could be) >robust. Robust algorithms have additional nice properties; when combined >together, two robust algorithms produce a new robust one etc. Several people have commented on your definition of robustness already, but I feel a need to comment anyway. Robustness is defined in several different ways in the literature. Your definition above is used by some, but I would argue that the majority subscribes to a slightly less rigorous definition, where robustness is equated with 'failing gracefully'. This means that, say, a robust convex hull algorithm may for some degenerate cases return a hull that is concave, but under no circumstances must it fail to terminate for a given input. In other words, under this definition there is a difference between _correctness_ and _robustness_. I only have a few of my collected robustness papers here at work, but here are two relevant quotes expressing this view of robustness: Shirra, Stefan. "Robustness and Precision Issues in Geometric Computation": "In general, robustness is a measure of the ability to recover from error conditions, e.g., tolerance of failures of internal components or errors in input data. Often an implementation of an algorithm is considered to be _robust_ if it produces the correct result for some perturbation of the input. It is called _stable_ if the perturbation is small." Milenkovic, Victor. "Robust Polygon Modeling": "For _strict robust geometry_, the task is the _accurate_ construction of a _feasible_ representation of some geometric object using _rounded arithmetic_." Christer Ericson Sony Computer Entertainment, Santa Monica 
From: Michael Pohoreski <MP<ohoreski@cy...>  20021114 20:14:08

Is there a formula to convert a logarithmic volume to/from a linear voltage? The PS2 uses a linear voltage, but DirectX uses a logarithmic volume. I'm trying to match the two up. i.e. Our engine accepts a percentage volume; how do I convert this volume to it's "native" value for each platform? One of the posts in the PS2 SPU newsgroup mentioned doubling the voltage gives a +6 dB increase, but I don't see where this values comes from. We now return you to our regularly scheduled debate on floatingpoint precision and epsilons...:) Lots of good info in that thread! 
From: <christer_ericson@pl...>  20021114 20:04:40

Ville Miettinen wrote: >>need the intersection point at which your ray intersects the triangle, >>you _must_ leave the confines of exact computation and enter epsilon land. >>Whenever you actually need to _compute_ intersection >>points (and not just test them), you basically don't have a choice: it's >>epsilons for you. > >Uhm. nope. That's where rational arithmetics come in. If we can make the >assumption that the input data (i.e. triangle vertex coordinates etc.) is >completely accurate, we can easily compute the intersection points _exactly_. >Certain operations (add,sub,mul,div,comparisons) can be done exactly using >rationals, whereas others (square roots, sin/cos/tan etc.) cannot. These >operations can then be accelerated by using floatingpoint filters. Uhm, nope, back at you. Unless you're running on a Turing machine, that is. The problem is that you would have to carry these exact numbers (e.g. rationals) forward from frame to frame, and they would, in general, grow without bounds. I can see it now, "Please connect additional harddisk. Press a key when ready." So, no, in practice you cannot work exactly when _computing_ intersections that are carried to the next frame (such as positional information computed during collision detection). This is wellknown and mentioned in just about any research paper on robustness. I see that my comment might be interpreted as saying that you always have to use epsilons when you're computing intersections and I guess this might be what you objected to. I hope it should now be clear that's not what I meant, but in the general sense. If you have, say, an intersection calculation that is only used as part of a subsequent predicate test, you can obviously compute this rationally without problems (assuming no trig, etc). Christer Ericson Sony Computer Entertainment, Santa Monica 
From: Ville Miettinen <wili@hy...>  20021114 19:43:12

Charles, I don't think that really contradicts my definition. Perhaps I should've just formulated it a bit better. The way I understand it, "robustness", when referring to algorithms (and the usage here differs somewhat from the mainstream usage of the word) is an absolute quality of an algorithm; for a certain input domain, within defined error bounds, the algorithm operates as advocated. If there is even a single case where inside the input domain an incorrect (i.e. outside the error bounds) answer is received, the algorithm just is not robust. So, yes, I'd definitely agree that such a convex hull code would be (or could be) robust. Robust algorithms have additional nice properties; when combined together, two robust algorithms produce a new robust one etc. So, yes, there are tons of robust floatingpoint based algorithms out there, with and without epsilon code. There is also loads of code that people tend to call "robust", according to the mainstream usage of the word, because it doesn't crash and behaves well. So, I'd still like to stick with the binary definition. It was my mistake to mention Shewchuk's stuff in the same paragraph (his boolean predicates being exact as well as robust); that made my view of the definition sound much stricter than I intended. cheers, wili On Thu, 14 Nov 2002, Charles Bloom wrote: > > At 12:35 PM 11/14/2002 +0200, gdalgorithmslistadmin@... > wrote: > >IMHO not. You cannot be a "little bit pregnant" nor can an implementation be > >"quite robust". Either the routine works guaranteedly under all > >circumstances (such as an implementation using Shewchuk's predicates) or it > >doesn't. > > Nonsense. Wellwritten "epsilon" code has wellcontroled and understood > failure > cases with reliable failure modes. For example, you can write convexhull > computation code using floats and epsilons which fails in that each of the > planes > of the hull may be pushed back by as much as epsilon which compared to the > correct > (smaller) hull. If you write your code well you can gaurantee that each > face of the > hull you make is only off the true hull by at most epsilon. This what we call > "robust" epsilon code. > > If, on the other hand, you write epsilon code without care, and simply check > that each predicate is correct within epsilon, then you can make hulls that are > way off where they should be. > > >  > Charles Bloom cbloom@... http://www.cbloom.com > > > >  > This sf.net email is sponsored by: To learn the basics of securing > your web site with SSL, click here to get a FREE TRIAL of a Thawte > Server Certificate: http://www.gothawte.com/rd524.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: Charles Bloom <cbloom@cb...>  20021114 18:58:14

At 12:35 PM 11/14/2002 +0200, gdalgorithmslistadmin@... wrote: >IMHO not. You cannot be a "little bit pregnant" nor can an implementation be >"quite robust". Either the routine works guaranteedly under all >circumstances (such as an implementation using Shewchuk's predicates) or it >doesn't. Nonsense. Wellwritten "epsilon" code has wellcontroled and understood failure cases with reliable failure modes. For example, you can write convexhull computation code using floats and epsilons which fails in that each of the planes of the hull may be pushed back by as much as epsilon which compared to the correct (smaller) hull. If you write your code well you can gaurantee that each face of the hull you make is only off the true hull by at most epsilon. This what we call "robust" epsilon code. If, on the other hand, you write epsilon code without care, and simply check that each predicate is correct within epsilon, then you can make hulls that are way off where they should be.  Charles Bloom cbloom@... http://www.cbloom.com 
From: Christopher Phillips <cphillips@re...>  20021114 15:44:05

=20 True ;) =20 Original Message From: Jamie Fowlston [mailto:jamief@...] Sent: 14 November 2002 15:39 To: gdalgorithmslist@... Subject: RE: [Algorithms] RE: higher accuracy <snip> I'll take two commercial games through an arduous quality assurance = process as a proof of robustness :)=20 </snip> =20 i wouldn't (sorry christopher, but i'm sure you'd be first to admit = that the Driver 1 and 2 physics aren't always flawless :) =20 jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of = Gribb, Gil Sent: 14 November 2002 15:17 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy >Sorry Gil but I have to challenge you on that. Write even a = "completely=20 robust" triangle/ray intersection routine with floats/doubles (i.e.=20 without reverting to exact arithmetics) and I'll buy you as many pints = of=20 beer you can drink.=20 Well, I am a little busy today getting my robust physics to run a bit faster...as physics can never be fast enough. So this will be = necessarily brief. But I never said I could write a completely or even sortof robust triangleray intersection routine. I said I could get "completely = robust physics" which I didn't define very precisely :) In my opinion, lack of precision isn't a problem in a games because = accuracy isn't important in games. You are free to choose the nature of the inaccuracy for the purpose of robustness. For example, interpenetration = or nearinterpenetration is tricky to deal with and illconditioned, so I = use a far less accurate solution that results in objects being nowhere near interpenetrating.=20 I suppose technically this is an "epsilon" approach, but I hate to be = lumped in with that. I have certainly taken over a few projects in trouble = that used the epsilon approach. I don't have multiple epsilons and they = don't have to be tweaked. Objects are kept at least a certain, relatively = large, distance appart and the code is carefully thought out to always err on = the side of caution. The system can robustly produce well conditioned = output given lesswell conditioned input, so that as the system is interated = it does not degrade. It sounds quite similar to the onesided collision = that has been discussed in this space. Alot less accuracy, alot more = robustness. I'll take two commercial games through an arduous quality assurance = process as a proof of robustness :) It works flawlessly in practice, which I = think is more important than it working flawlessly in theory. Gil=20 My experiences so far have been that using exact arithmetic / = predicates:=20 a) makes your code shorter, easier to read and much easier to debug=20 b) in general is not that slow (assuming either staticfilter = predicates=20 or dynamic filtering). For example the ray/tri routine we currently use = is=20 less than twice as slow as the fastest float implementation I know=20 (M=F6llerTrumbore) and tri/box routines are 1.5x10x _faster_.=20 c) once you've paid the initial overhead of either adapting an existing = library or writing your own, it's definitely not a waste of programming = time  quite on the contrary. Your code just _works_ when you write it. = And more importantly, you *know* that it will work. The time gains from = reduced debugging and hacking are quite significant.=20 Of course, in any practical application a lot of the programming can be = done with using ordinary floats. However, when you begin to do anything = even remotely related to computational geometry, your luck runs out = unless=20 you can somehow bound the input data very strictly.=20 cheers,=20 wili=20 On Wed, 13 Nov 2002, Gribb, Gil wrote:=20 > To present a contrary viewpoint...=20 >=20 > All of this is a waste of CPU time (and programming time). It isn't = that=20 > hard to get completely robust physics using just floats if you take = the=20 > right approches.=20 >=20 > Gil=20 >=20 > Original Message=20 > From: Ville Miettinen [ mailto:wili@... <mailto:wili@...> ]=20 > Sent: Wednesday, November 13, 2002 10:37 AM=20 > To: 'gdalgorithmslist@...'=20 > Subject: RE: [Algorithms] RE: higher accuracy [spam?][bcc][fake adr]=20 >=20 >=20 > >should cover all your arbitrary precision arithmetic needs :)=20 >=20 > I think that is a bit of an overstatement. Shewchuk's stuff is = extremely=20 > useful (we use his code in all of our intersection routines etc.), = but his > main contribution has been in the field of predicates, not = constructions.=20 > This means that one can use his code to perform predicate queries, = e.g. "is=20 > this point in the positive halfspace of a plane", but cannot = construct=20 > anything; for example clipping a triangle or even a line is not=20 > possible/easy using just predicates. Some constructions can be done = using a=20 > binary search: a ray/triangle intersection query requires 24 = orient3d()=20 > queries to discover whether the ray and triangle intersect; getting = the=20 > intersection point (distance) is more tricky, the only way it can be = done=20 > using predicates is to find the value a bit at a time (max 32 = iterations for=20 > floats).=20 >=20 > When we need to use constructions, we usually switch over to rational = > numbers. There are tons of reasonably good math packages for this = (GMP and > LEDA are probably the best ones). Because processing rational numbers = is=20 > _very_ expensive, we accelerate their use by a "filter class" that performs=20 > all operations using interval arithmetics first, reverting to = rational=20 > numbers only if needed. This is very close to what Shewchuk does in = his=20 > predicates, although in our case the filter is dynamic, not static. = We also=20 > use symbolic arithmetic to detect equalities in expressions (very = useful, as=20 > this is the weak point of interval arithmetics), expression templates = to get=20 > rid of temporaries (C++ issue) and lazy evaluation (i.e. expressions = are=20 > turned into trees that are evaluated only when necessary). Instead of using=20 > GMP or similar packages, we wrote our rational arithmetic code from scratch=20 > in x86 assembler  processing rational numbers (bigints) is one of = the few=20 > areas where assembler coding makes sense anymore. We are going to = make our > package available (for free, without any boring licenses) sometimes = early=20 > next year.=20 >=20 > The nice thing about using exact arithmetics is that your CG code = will=20 > _work_. No more epsilon values or hacks. I get much more code done = during=20 > the day and sleep better at night. =3D)=20 >=20 > cheers,=20 > wili=20 >=20 > =20 > o Ville Miettinen, Lead Programmer=20 > o Hybrid Graphics, Ltd.=20 > o Email: wili@...=20 > o Web: http://www.hybrid.fi=20 >=20 >=20 >=20 > Original Message=20 > From: gdalgorithmslistadmin@...=20 > [ mailto:gdalgorithmslistadmin@... <mailto:gdalgorithmslistadmin@...> ]On Behalf Of = Jamie=20 > Fowlston=20 > Sent: Wednesday, November 13, 2002 15:17=20 > To: gdalgorithmslist@...=20 > Subject: RE: [Algorithms] RE: higher accuracy=20 >=20 >=20 > http://www2.cs.cmu.edu/~quake/robust.html <http://www2.cs.cmu.edu/~quake/robust.html>; =20 >=20 > should cover all your arbitrary precision arithmetic needs :)=20 >=20 > jamie=20 >=20 >=20 > Original Message=20 > From: gdalgorithmslistadmin@...=20 > [ mailto:gdalgorithmslistadmin@... <mailto:gdalgorithmslistadmin@...> ]On Behalf Of = Ben=20 > Glancy=20 > Sent: 13 November 2002 12:34=20 > To: gdalgorithmslist@...=20 > Subject: [Algorithms] RE: higher accuracy=20 >=20 >=20 > Speaking of accuracy, how can I store even greater accuracy = than a=20 > double?=20 >=20 > The calculator on windows looks like it has about 50 odd digits after = the=20 > decimal point.=20 >=20 >=20 > The content of this message and any attached file are confidential = and/or=20 > privileged and are for the intended recipient only. If you are not = the=20 > intended recipient, any unauthorised use, disclosure, copying, distribution=20 > or other dissemination is strictly prohibited. If you receive this = message > in error please notify the sender immediately by email, telephone or = fax and=20 > then delete this email. Any attachment with this message should be = checked > for viruses before it is opened. Magenta Software Limited cannot be = held=20 > responsible for any failure by the recipient to check for viruses = before=20 > opening any attachment. Copyright in this email and attachments = created by > us belongs to Magenta Software Limited. Should you communicate with = anyone > at Magenta Software Limited by email you consent to us monitoring and = > reading any such correspondence.=20 >=20 >=20 >=20 >=20 > =20 > This sf.net email is sponsored by: Are you worried about=20 > your web server security? Click here for a FREE Thawte=20 > Apache SSL Guide and answer your Apache SSL security=20 > needs: http://www.gothawte.com/rd523.html <http://www.gothawte.com/rd523.html>; =20 > _______________________________________________=20 > GDAlgorithmslist mailing list=20 > GDAlgorithmslist@...=20 > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist <https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist>; =20 > Archives:=20 > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 <http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188>; =20 >=20 >=20 >=20 > =20 > This sf.net email is sponsored by: Are you worried about=20 > your web server security? Click here for a FREE Thawte=20 > Apache SSL Guide and answer your Apache SSL security=20 > needs: http://www.gothawte.com/rd523.html <http://www.gothawte.com/rd523.html>; =20 > _______________________________________________=20 > GDAlgorithmslist mailing list=20 > GDAlgorithmslist@...=20 > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist <https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist>; =20 > Archives:=20 > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 <http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188>; =20 >=20 >=20 > =20 > This sf.net email is sponsored by: Are you worried about=20 > your web server security? Click here for a FREE Thawte=20 > Apache SSL Guide and answer your Apache SSL security=20 > needs: http://www.gothawte.com/rd523.html <http://www.gothawte.com/rd523.html>; =20 > _______________________________________________=20 > GDAlgorithmslist mailing list=20 > GDAlgorithmslist@...=20 > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist <https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist>; =20 > Archives:=20 > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 <http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188>; =20 >=20 =20 This sf.net email is sponsored by: Are you worried about=20 your web server security? Click here for a FREE Thawte=20 Apache SSL Guide and answer your Apache SSL security=20 needs: http://www.gothawte.com/rd523.html <http://www.gothawte.com/rd523.html>; =20 _______________________________________________=20 GDAlgorithmslist mailing list=20 GDAlgorithmslist@...=20 https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist <https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist>; =20 Archives:=20 http://sourceforge.net/mailarchive/forum.php?forum_ida88 <http://sourceforge.net/mailarchive/forum.php?forum_ida88>; =20 Virus scanned and cleared ok 
From: Jamie Fowlston <jamief@qu...>  20021114 15:38:19

RE: [Algorithms] RE: higher accuracy [spam?][bcc][fake adr]<snip> I'll take two commercial games through an arduous quality assurance proce= ss as a proof of robustness :) </snip> i wouldn't (sorry christopher, but i'm sure you'd be first to admit that = the Driver 1 and 2 physics aren't always flawless :) jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Gribb, Gil Sent: 14 November 2002 15:17 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy >Sorry Gil but I have to challenge you on that. Write even a "completel= y robust" triangle/ray intersection routine with floats/doubles (i.e. without reverting to exact arithmetics) and I'll buy you as many pints = of beer you can drink. Well, I am a little busy today getting my robust physics to run a bit faster...as physics can never be fast enough. So this will be necessarily brief. But I never said I could write a completely or even sortof robust triangleray intersection routine. I said I could get "completely robust physics" which I didn't define very precisely :) In my opinion, lack of precision isn't a problem in a games because accuracy isn't important in games. You are free to choose the nature of t= he inaccuracy for the purpose of robustness. For example, interpenetration o= r nearinterpenetration is tricky to deal with and illconditioned, so I us= e a far less accurate solution that results in objects being nowhere near interpenetrating. I suppose technically this is an "epsilon" approach, but I hate to be lumped in with that. I have certainly taken over a few projects in troubl= e that used the epsilon approach. I don't have multiple epsilons and they don't have to be tweaked. Objects are kept at least a certain, relatively large, distance appart and the code is carefully thought out to always er= r on the side of caution. The system can robustly produce well conditioned output given lesswell conditioned input, so that as the system is intera= ted it does not degrade. It sounds quite similar to the onesided collision t= hat has been discussed in this space. Alot less accuracy, alot more robustnes= s. I'll take two commercial games through an arduous quality assurance process as a proof of robustness :) It works flawlessly in practice, whic= h I think is more important than it working flawlessly in theory. Gil My experiences so far have been that using exact arithmetic / predicate= s: a) makes your code shorter, easier to read and much easier to debug b) in general is not that slow (assuming either staticfilter predicate= s or dynamic filtering). For example the ray/tri routine we currently use= is less than twice as slow as the fastest float implementation I know (M=F6llerTrumbore) and tri/box routines are 1.5x10x _faster_. c) once you've paid the initial overhead of either adapting an existing library or writing your own, it's definitely not a waste of programming time  quite on the contrary. Your code just _works_ when you write it. And more importantly, you *know* that it will work. The time gains from reduced debugging and hacking are quite significant. Of course, in any practical application a lot of the programming can be done with using ordinary floats. However, when you begin to do anything even remotely related to computational geometry, your luck runs out unl= ess you can somehow bound the input data very strictly. cheers, wili On Wed, 13 Nov 2002, Gribb, Gil wrote: > To present a contrary viewpoint... > > All of this is a waste of CPU time (and programming time). It isn't t= hat > hard to get completely robust physics using just floats if you take t= he > right approches. > > Gil > > Original Message > From: Ville Miettinen [mailto:wili@...] > Sent: Wednesday, November 13, 2002 10:37 AM > To: 'gdalgorithmslist@...' > Subject: RE: [Algorithms] RE: higher accuracy [spam?][bcc][fake adr] > > > >should cover all your arbitrary precision arithmetic needs :) > > I think that is a bit of an overstatement. Shewchuk's stuff is extrem= ely > useful (we use his code in all of our intersection routines etc.), bu= t his > main contribution has been in the field of predicates, not constructions. > This means that one can use his code to perform predicate queries, e.= g. "is > this point in the positive halfspace of a plane", but cannot constru= ct > anything; for example clipping a triangle or even a line is not > possible/easy using just predicates. Some constructions can be done using a > binary search: a ray/triangle intersection query requires 24 orient3= d() > queries to discover whether the ray and triangle intersect; getting t= he > intersection point (distance) is more tricky, the only way it can be done > using predicates is to find the value a bit at a time (max 32 iterati= ons for > floats). > > When we need to use constructions, we usually switch over to rational > numbers. There are tons of reasonably good math packages for this (GM= P and > LEDA are probably the best ones). Because processing rational numbers= is > _very_ expensive, we accelerate their use by a "filter class" that performs > all operations using interval arithmetics first, reverting to rationa= l > numbers only if needed. This is very close to what Shewchuk does in h= is > predicates, although in our case the filter is dynamic, not static. W= e also > use symbolic arithmetic to detect equalities in expressions (very useful, as > this is the weak point of interval arithmetics), expression templates= to get > rid of temporaries (C++ issue) and lazy evaluation (i.e. expressions = are > turned into trees that are evaluated only when necessary). Instead of using > GMP or similar packages, we wrote our rational arithmetic code from scratch > in x86 assembler  processing rational numbers (bigints) is one of t= he few > areas where assembler coding makes sense anymore. We are going to mak= e our > package available (for free, without any boring licenses) sometimes early > next year. > > The nice thing about using exact arithmetics is that your CG code wil= l > _work_. No more epsilon values or hacks. I get much more code done during > the day and sleep better at night. =3D) > > cheers, > wili > >  > o Ville Miettinen, Lead Programmer > o Hybrid Graphics, Ltd. > o Email: wili@... > o Web: http://www.hybrid.fi > > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Ja= mie > Fowlston > Sent: Wednesday, November 13, 2002 15:17 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] RE: higher accuracy > > > http://www2.cs.cmu.edu/~quake/robust.html > > should cover all your arbitrary precision arithmetic needs :) > > jamie > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Be= n > Glancy > Sent: 13 November 2002 12:34 > To: gdalgorithmslist@... > Subject: [Algorithms] RE: higher accuracy > > > Speaking of accuracy, how can I store even greater accuracy tha= n a > double? > > The calculator on windows looks like it has about 50 odd digits after the > decimal point. > > > The content of this message and any attached file are confidential and/or > privileged and are for the intended recipient only. If you are not th= e > intended recipient, any unauthorised use, disclosure, copying, distribution > or other dissemination is strictly prohibited. If you receive this message > in error please notify the sender immediately by email, telephone or = fax and > then delete this email. Any attachment with this message should be checked > for viruses before it is opened. Magenta Software Limited cannot be held > responsible for any failure by the recipient to check for viruses bef= ore > opening any attachment. Copyright in this email and attachments creat= ed by > us belongs to Magenta Software Limited. Should you communicate with anyone > at Magenta Software Limited by email you consent to us monitoring and > reading any such correspondence. > > > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >  This sf.net email is sponsored by: Are you worried about your web server security? Click here for a FREE Thawte Apache SSL Guide and answer your Apache SSL security needs: http://www.gothawte.com/rd523.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Gribb, Gil <ggribb@ra...>  20021114 15:16:58

>Sorry Gil but I have to challenge you on that. Write even a = "completely robust" triangle/ray intersection routine with floats/doubles (i.e. without reverting to exact arithmetics) and I'll buy you as many pints = of beer you can drink.=20 Well, I am a little busy today getting my robust physics to run a bit faster...as physics can never be fast enough. So this will be = necessarily brief. But I never said I could write a completely or even sortof robust triangleray intersection routine. I said I could get "completely = robust physics" which I didn't define very precisely :) In my opinion, lack of precision isn't a problem in a games because = accuracy isn't important in games. You are free to choose the nature of the inaccuracy for the purpose of robustness. For example, interpenetration = or nearinterpenetration is tricky to deal with and illconditioned, so I = use a far less accurate solution that results in objects being nowhere near interpenetrating.=20 I suppose technically this is an "epsilon" approach, but I hate to be = lumped in with that. I have certainly taken over a few projects in trouble = that used the epsilon approach. I don't have multiple epsilons and they = don't have to be tweaked. Objects are kept at least a certain, relatively = large, distance appart and the code is carefully thought out to always err on = the side of caution. The system can robustly produce well conditioned = output given lesswell conditioned input, so that as the system is interated = it does not degrade. It sounds quite similar to the onesided collision = that has been discussed in this space. Alot less accuracy, alot more = robustness. I'll take two commercial games through an arduous quality assurance = process as a proof of robustness :) It works flawlessly in practice, which I = think is more important than it working flawlessly in theory. Gil My experiences so far have been that using exact arithmetic / = predicates: a) makes your code shorter, easier to read and much easier to debug b) in general is not that slow (assuming either staticfilter = predicates or dynamic filtering). For example the ray/tri routine we currently use = is=20 less than twice as slow as the fastest float implementation I know (M=F6llerTrumbore) and tri/box routines are 1.5x10x _faster_. c) once you've paid the initial overhead of either adapting an existing library or writing your own, it's definitely not a waste of programming time  quite on the contrary. Your code just _works_ when you write it. And more importantly, you *know* that it will work. The time gains from reduced debugging and hacking are quite significant. Of course, in any practical application a lot of the programming can be done with using ordinary floats. However, when you begin to do anything even remotely related to computational geometry, your luck runs out = unless you can somehow bound the input data very strictly.=20 cheers, wili On Wed, 13 Nov 2002, Gribb, Gil wrote: > To present a contrary viewpoint... >=20 > All of this is a waste of CPU time (and programming time). It isn't = that > hard to get completely robust physics using just floats if you take = the > right approches. >=20 > Gil >=20 > Original Message > From: Ville Miettinen [mailto:wili@...] > Sent: Wednesday, November 13, 2002 10:37 AM > To: 'gdalgorithmslist@...' > Subject: RE: [Algorithms] RE: higher accuracy [spam?][bcc][fake adr] >=20 >=20 > >should cover all your arbitrary precision arithmetic needs :) >=20 > I think that is a bit of an overstatement. Shewchuk's stuff is = extremely > useful (we use his code in all of our intersection routines etc.), = but his > main contribution has been in the field of predicates, not = constructions. > This means that one can use his code to perform predicate queries, = e.g. "is > this point in the positive halfspace of a plane", but cannot = construct > anything; for example clipping a triangle or even a line is not > possible/easy using just predicates. Some constructions can be done = using a > binary search: a ray/triangle intersection query requires 24 = orient3d() > queries to discover whether the ray and triangle intersect; getting = the > intersection point (distance) is more tricky, the only way it can be = done > using predicates is to find the value a bit at a time (max 32 = iterations for > floats). >=20 > When we need to use constructions, we usually switch over to rational > numbers. There are tons of reasonably good math packages for this = (GMP and > LEDA are probably the best ones). Because processing rational numbers = is > _very_ expensive, we accelerate their use by a "filter class" that performs > all operations using interval arithmetics first, reverting to = rational > numbers only if needed. This is very close to what Shewchuk does in = his > predicates, although in our case the filter is dynamic, not static. = We also > use symbolic arithmetic to detect equalities in expressions (very = useful, as > this is the weak point of interval arithmetics), expression templates = to get > rid of temporaries (C++ issue) and lazy evaluation (i.e. expressions = are > turned into trees that are evaluated only when necessary). Instead of using > GMP or similar packages, we wrote our rational arithmetic code from scratch > in x86 assembler  processing rational numbers (bigints) is one of = the few > areas where assembler coding makes sense anymore. We are going to = make our > package available (for free, without any boring licenses) sometimes = early > next year. >=20 > The nice thing about using exact arithmetics is that your CG code = will > _work_. No more epsilon values or hacks. I get much more code done = during > the day and sleep better at night. =3D) >=20 > cheers, > wili >=20 >  > o Ville Miettinen, Lead Programmer > o Hybrid Graphics, Ltd. > o Email: wili@... > o Web: http://www.hybrid.fi >=20 >=20 >=20 > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of = Jamie > Fowlston > Sent: Wednesday, November 13, 2002 15:17 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] RE: higher accuracy >=20 >=20 > http://www2.cs.cmu.edu/~quake/robust.html >=20 > should cover all your arbitrary precision arithmetic needs :) >=20 > jamie >=20 >=20 > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of = Ben > Glancy > Sent: 13 November 2002 12:34 > To: gdalgorithmslist@... > Subject: [Algorithms] RE: higher accuracy >=20 >=20 > Speaking of accuracy, how can I store even greater accuracy than a > double? >=20 > The calculator on windows looks like it has about 50 odd digits after = the > decimal point. >=20 >=20 > The content of this message and any attached file are confidential = and/or > privileged and are for the intended recipient only. If you are not = the > intended recipient, any unauthorised use, disclosure, copying, distribution > or other dissemination is strictly prohibited. If you receive this = message > in error please notify the sender immediately by email, telephone or = fax and > then delete this email. Any attachment with this message should be = checked > for viruses before it is opened. Magenta Software Limited cannot be = held > responsible for any failure by the recipient to check for viruses = before > opening any attachment. Copyright in this email and attachments = created by > us belongs to Magenta Software Limited. Should you communicate with = anyone > at Magenta Software Limited by email you consent to us monitoring and > reading any such correspondence. >=20 >=20 >=20 >=20 >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 >=20 >=20 >  > This sf.net email is sponsored by: Are you worried about=20 > your web server security? Click here for a FREE Thawte=20 > Apache SSL Guide and answer your Apache SSL security=20 > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 >=20 >  > This sf.net email is sponsored by: Are you worried about=20 > your web server security? Click here for a FREE Thawte=20 > Apache SSL Guide and answer your Apache SSL security=20 > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20  This sf.net email is sponsored by: Are you worried about=20 your web server security? Click here for a FREE Thawte=20 Apache SSL Guide and answer your Apache SSL security=20 needs: http://www.gothawte.com/rd523.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Jamie Fowlston <jamief@qu...>  20021114 12:33:13

shewchuk's paper covers some of this (from 4.1): <snip> geometric algorithms are divided into several classes with varying amounts of robustness: exact algorithms, which are always correct= ; robust algorithms, which are always correct for some perturbation of the input; stable algorithms, for which the perturbation is small; quasi=ADrobust algorithms, whose results might be geometrically inconsist= ent, but nevertheless satisfy some weakened consistency criterion; and fragile algorithms, which are not guaranteed to produce any usable output at all </snip> jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Jason Williams Sent: 14 November 2002 12:16 To: gdalgorithmslist@... Subject: RE: [Algorithms] RE: higher accuracy > IMHO not. You cannot be a "little bit pregnant" nor can an > implementation be > "quite robust". Either the routine works guaranteedly under all > circumstances (such as an implementation using Shewchuk's > predicates) or it > doesn't. Of course there are differences in the failure rates of the > nonrobust routines, making some of them better than others. > However, just > to keep our terms straight, I'd stick to a binary definition > for robustness. I prefer to use the dictionary definition for my words instead of making = up my own meanings. >From dictionary.com: >ro=B7bust Pronunciation Key (rbst, rbst) >adj. >Full of health and strength; vigorous. >Powerfully built; sturdy. See Synonyms at healthy. >Requiring or suited to physical strength or endurance: robust labor. >Rough or crude; boisterous: a robust tale. >Marked by richness and fullness; fullbodied: a robust wine. So the general meaning of robust does not mean "indestructible". A robust building can still fall over in an earthquake, and a robust man = can still get weary. What about the "tecchy" meaning?... >robust >Said of a system that has demonstrated an ability to recover >gracefully from the whole range of exceptional inputs and >situations in a given environment. >One step below bulletproof. So that also does not mean "indestructible" or "never failing", merely th= at your program is able to cope gracefully with failure. It sounds to me mor= e like you mean bulletproof, indestructible, unfailing, guaranteed, or perh= aps perfect. It's virtually impossible to guarantee that any complex system will never fail  only that you've mathematically proved as much of it as you can, checked that your implementation matches your maths, and you've tested it for a long time on as many conceivable inputs as possible, and it hasn't failed to an "unacceptable level". Therefore, the idea of something being "acceptably robust" is perfectly sensible, in exactly the same way as you can "think you might be pregnant= " but not actually be sure. Jason  This sf.net email is sponsored by: To learn the basics of securing your web site with SSL, click here to get a FREE TRIAL of a Thawte Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Jason Williams <Jason.W<illiams@bl...>  20021114 12:15:52

> IMHO not. You cannot be a "little bit pregnant" nor can an=20 > implementation be > "quite robust". Either the routine works guaranteedly under all > circumstances (such as an implementation using Shewchuk's=20 > predicates) or it > doesn't. Of course there are differences in the failure rates of the > nonrobust routines, making some of them better than others.=20 > However, just > to keep our terms straight, I'd stick to a binary definition=20 > for robustness. I prefer to use the dictionary definition for my words instead of making = up my own meanings. From dictionary.com: >ro=B7bust Pronunciation Key (rbst, rbst) >adj.=20 >Full of health and strength; vigorous.=20 >Powerfully built; sturdy. See Synonyms at healthy.=20 >Requiring or suited to physical strength or endurance: robust labor.=20 >Rough or crude; boisterous: a robust tale.=20 >Marked by richness and fullness; fullbodied: a robust wine.=20 So the general meaning of robust does not mean "indestructible". A robust building can still fall over in an earthquake, and a robust man = can still get weary. What about the "tecchy" meaning?... >robust=20 >Said of a system that has demonstrated an ability to recover >gracefully from the whole range of exceptional inputs and >situations in a given environment. >One step below bulletproof. So that also does not mean "indestructible" or "never failing", merely = that your program is able to cope gracefully with failure. It sounds to = me more like you mean bulletproof, indestructible, unfailing, = guaranteed, or perhaps perfect. It's virtually impossible to guarantee that any complex system will = never fail  only that you've mathematically proved as much of it as you = can, checked that your implementation matches your maths, and you've = tested it for a long time on as many conceivable inputs as possible, and = it hasn't failed to an "unacceptable level". Therefore, the idea of something being "acceptably robust" is perfectly = sensible, in exactly the same way as you can "think you might be = pregnant" but not actually be sure. Jason 
From: Ville Miettinen <wili@ma...>  20021114 11:47:22

I agree with you completely and respect your opinion. Games aren't usually missioncritical software and if you can produce and ship your product faster, and it doesn't crash too often and it doesn't look funny, that's fine and dandy. There are other fields where similar or even the same algorithms are used, but bugs, inaccuracies and stability problems are frowned upon, such as simulation software, most CG libraries, embedded systems etc. I write software for both largescale visualization systems (gazillions of objects) and rendering code for mobile devices (where every byte and cycle counts). In both of these fields the customers have pretty strong feelings about the robustness of the code. So, same algorithms, different worlds, different requirements. In my free time, I'm happy to hack away and bend all rules. To prove that I'm not completely anal about things like this, here's a little .com file I hacked together last weekend :) ; 26 byte sierpinski triangle (wili@..., 2002) ; rules: enter mode 13h, draw sierpinski triangle, ; wait for keypress, return to text mode, don't crash ; it is probably possible to shave off 12 bytes ; (the mov ax,3 is a prime candidate). ; tested under win2k and winxp .386p code SEGMENT para public use16 ASSUME CS:code, DS:code org 100h entry: mov al,13h int 10h mov cx,0a57ch mov ds,cx foo: mov [si+320],al lodsb xor al,[si] loop foo int 16h mov ax,3 int 10h ret code ENDS END entry cheers, wili  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Chris Jenner Sent: Thursday, November 14, 2002 12:45 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy If that's your definition of robustness then I don't want to write robust code. I want to write games that create a detailed and believable environment, using a complex physics to create emergent gameplay. There's no point having a physics engine that can collide millimeter scale objects accurately against lightyear scale objects, if it's going to slow down the calculations of a few cars crashing together with all the debris that comes off. You can easily make the overall system 'robust' enough not to crash (or give incorrect looking behaviour) even if the collision sub system (for example) returns incorrect results for a couple of timesteps. Chris. Original Message From: Ville Miettinen [mailto:wili@...] Sent: 14 November 2002 10:36 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy IMHO not. You cannot be a "little bit pregnant" nor can an implementation be "quite robust". Either the routine works guaranteedly under all circumstances (such as an implementation using Shewchuk's predicates) or it doesn't. Of course there are differences in the failure rates of the nonrobust routines, making some of them better than others. However, just to keep our terms straight, I'd stick to a binary definition for robustness. cheers, wili  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of John Connors Sent: Thursday, November 14, 2002 12:07 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy Is there any way of quantifying "robustness"? Original Message From: Conor Stokes [mailto:cstokes@...] Sent: 14 November 2002 10:08 To: gdalgorithmslist@... Subject: Re: [Algorithms] RE: higher accuracy > > Sorry Gil but I have to challenge you on that. Write even a "completely > robust" triangle/ray intersection routine with floats/doubles (i.e. > without reverting to exact arithmetics) and I'll buy you as many pints of > beer you can drink. > Depends what you mean as robust  you can write a rather robust plücker space triangle ray intersection that only uses floats, if you make sure you have the same line at each shared edge of two triangles. There was a paper on this around (that talked about robust ray triangle intersections using shared edge plücker coords), but I can't seem to find it atm. Not that it will be accurate  just fairly robust. Conor Stokes  This sf.net email is sponsored by: To learn the basics of securing your web site with SSL, click here to get a FREE TRIAL of a Thawte Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 Virus scanned and cleared ok  This sf.net email is sponsored by: To learn the basics of securing your web site with SSL, click here to get a FREE TRIAL of a Thawte Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88  This sf.net email is sponsored by: To learn the basics of securing your web site with SSL, click here to get a FREE TRIAL of a Thawte Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 Virus scanned and cleared ok  This sf.net email is sponsored by: To learn the basics of securing your web site with SSL, click here to get a FREE TRIAL of a Thawte Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Tom Forsyth <tomf@mu...>  20021114 11:23:19

You missed the fourth (and by far the largest) clan  people who don't even realise there's a problem. Tom Forsyth  Muckyfoot bloke and Microsoft MVP. This email is the product of your deranged imagination, and does not in any way imply existence of the author. > Original Message > From: jeffrey Rainy [mailto:jrainy@...] > Sent: 13 November 2002 20:02 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] RE: higher accuracy > > > There are 3 school of thoughts (is this idiom correct in english?) : > > 1) The analytical bunch : > > They like to proove that their stuff is robust and precision > independant. With things like orientation theorem and > fixpoint arithmetic, they'll proove you that their stuff > works. This requires lots of work and carefull planning, but > works fine. The main risk is the boss's nephew who'll tell > him over the weekend that your 5000+ lines of finely crafted > code can be replaced by their hackish 50 lines + epsilon. > > 2) The precision boosters : > > They'll buy/borrow/import code and libraries that can handle > gazillions of decimals. The failure of their code will happen > with an expectation that is inversly proportionnal to the > number of digit. Never quite working, but at some point your > betatesting isn't long enough for the first bug to come out. > Of course, the performance can decrease significantly or the > error rate can change with the CPUbrand or framerate. > However, as long as you can bump the precision high enough > you can blind yourself in not seeing the bugs. > > 3) The epsilon clan : > > On a game per game basis, you can tweak things so that the > error condition become unreachable. You just have to put > epsilons here and there that prevent you from reaching the > tricky cases. This works great until you try to make > nanoscale spaceships or something like that. It involves > quite some black magic and is a little too informal for some > people. I can also easily turn into something buggy without > no one noticing. You just are never quite sure, IMHO. > > > > It isn't that hard to get completely robust physics using > just floats if you take the right approches. > > I'm not sure which approach you are refering to. One thing I > know, though, is that it is very hard to take people from one > gang and bring them into the other. From what I've seen, most > games ship with 3) in theory and 2) in practice. > > Trying to get 1) is a good aim to have, though. With carefull > coding, it can be done in floats, too. It's not a waste if it > is planned well and carried through. It is only a waste if > the boss nephew make you go 2) or if the deadlines make you go 3). > > > J. > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On > Behalf Of Gribb, Gil > Sent: Wednesday, November 13, 2002 14:19 > To: 'gdalgorithmslist@...' > Subject: RE: [Algorithms] RE: higher accuracy > > > To present a contrary viewpoint... > All of this is a waste of CPU time (and programming time). It > isn't that hard to get completely robust physics using just > floats if you take the right approches. > Gil > Original Message > From: Ville Miettinen [mailto:wili@...] > Sent: Wednesday, November 13, 2002 10:37 AM > To: 'gdalgorithmslist@...' > Subject: RE: [Algorithms] RE: higher accuracy [spam?][bcc][fake adr] > > > >should cover all your arbitrary precision arithmetic needs :) > I think that is a bit of an overstatement. Shewchuk's stuff > is extremely > useful (we use his code in all of our intersection routines > etc.), but his > main contribution has been in the field of predicates, not > constructions. > This means that one can use his code to perform predicate > queries, e.g. "is > this point in the positive halfspace of a plane", but cannot > construct > anything; for example clipping a triangle or even a line is not > possible/easy using just predicates. Some constructions can > be done using a > binary search: a ray/triangle intersection query requires 24 > orient3d() > queries to discover whether the ray and triangle intersect; > getting the > intersection point (distance) is more tricky, the only way it > can be done > using predicates is to find the value a bit at a time (max 32 > iterations for > floats). > When we need to use constructions, we usually switch over to rational > numbers. There are tons of reasonably good math packages for > this (GMP and > LEDA are probably the best ones). Because processing rational > numbers is > _very_ expensive, we accelerate their use by a "filter class" > that performs > all operations using interval arithmetics first, reverting to > rational > numbers only if needed. This is very close to what Shewchuk > does in his > predicates, although in our case the filter is dynamic, not > static. We also > use symbolic arithmetic to detect equalities in expressions > (very useful, as > this is the weak point of interval arithmetics), expression > templates to get > rid of temporaries (C++ issue) and lazy evaluation (i.e. > expressions are > turned into trees that are evaluated only when necessary). > Instead of using > GMP or similar packages, we wrote our rational arithmetic > code from scratch > in x86 assembler  processing rational numbers (bigints) is > one of the few > areas where assembler coding makes sense anymore. We are > going to make our > package available (for free, without any boring licenses) > sometimes early > next year. > The nice thing about using exact arithmetics is that your CG > code will > _work_. No more epsilon values or hacks. I get much more code > done during > the day and sleep better at night. =) > cheers, > wili >  > o Ville Miettinen, Lead Programmer > o Hybrid Graphics, Ltd. > o Email: wili@... > o Web: http://www.hybrid.fi > > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On > Behalf Of Jamie > Fowlston > Sent: Wednesday, November 13, 2002 15:17 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] RE: higher accuracy > > > http://www2.cs.cmu.edu/~quake/robust.html > should cover all your arbitrary precision arithmetic needs :) > jamie > > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On > Behalf Of Ben > Glancy > Sent: 13 November 2002 12:34 > To: gdalgorithmslist@... > Subject: [Algorithms] RE: higher accuracy > > > Speaking of accuracy, how can I store even greater > accuracy than a > double? > The calculator on windows looks like it has about 50 odd > digits after the > decimal point. > > > The content of this message and any attached file are > confidential and/or > privileged and are for the intended recipient only. If you > are not the > intended recipient, any unauthorised use, disclosure, > copying, distribution > or other dissemination is strictly prohibited. If you receive > this message > in error please notify the sender immediately by email, > telephone or fax and > then delete this email. Any attachment with this message > should be checked > for viruses before it is opened. Magenta Software Limited > cannot be held > responsible for any failure by the recipient to check for > viruses before > opening any attachment. Copyright in this email and > attachments created by > us belongs to Magenta Software Limited. Should you > communicate with anyone > at Magenta Software Limited by email you consent to us monitoring and > reading any such correspondence. > > > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > 
From: Conor Stokes <cstokes@tp...>  20021114 11:16:57

>IMHO not. You cannot be a "little bit pregnant" nor can an implementatio= n be >"quite robust". Either the routine works guaranteedly under all >circumstances (such as an implementation using Shewchuk's predicates) or= it >doesn't. Of course there are differences in the failure rates of the >nonrobust routines, making some of them better than others. However, ju= st >to keep our terms straight, I'd stick to a binary definition for robustness. Well, the pl=FCcker shared edge method works under all circumstances geometrical that I can think of  it handles rays at edges (the ray line = is either one side or the other), is self consistent given the two different windings etc. I hesitate in saying "fully robust", because there could always be a case= I, or the authors have not thought of. Robustness being in the eye of the beholder. Conor Stokes 
From: Chris Jenner <cjenner@re...>  20021114 10:50:59

If that's your definition of robustness then I don't want to write = robust code. I want to write games that create a detailed and believable environment, using a complex physics to create emergent gameplay. There's no point having a physics engine that can collide millimeter = scale objects accurately against lightyear scale objects, if it's going to = slow down the calculations of a few cars crashing together with all the = debris that comes off. You can easily make the overall system 'robust' enough not to crash (or = give incorrect looking behaviour) even if the collision sub system (for = example) returns incorrect results for a couple of timesteps. Chris. Original Message From: Ville Miettinen [mailto:wili@...]=20 Sent: 14 November 2002 10:36 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy IMHO not. You cannot be a "little bit pregnant" nor can an = implementation be "quite robust". Either the routine works guaranteedly under all circumstances (such as an implementation using Shewchuk's predicates) = or it doesn't. Of course there are differences in the failure rates of the nonrobust routines, making some of them better than others. However, = just to keep our terms straight, I'd stick to a binary definition for = robustness. cheers, wili  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of John Connors Sent: Thursday, November 14, 2002 12:07 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy Is there any way of quantifying "robustness"? Original Message From: Conor Stokes [mailto:cstokes@...] Sent: 14 November 2002 10:08 To: gdalgorithmslist@... Subject: Re: [Algorithms] RE: higher accuracy > > Sorry Gil but I have to challenge you on that. Write even a = "completely > robust" triangle/ray intersection routine with floats/doubles (i.e. > without reverting to exact arithmetics) and I'll buy you as many = pints of > beer you can drink. > Depends what you mean as robust  you can write a rather robust = pl=FCcker space triangle ray intersection that only uses floats, if you make sure = you have the same line at each shared edge of two triangles. There was a = paper on this around (that talked about robust ray triangle intersections = using shared edge pl=FCcker coords), but I can't seem to find it atm. Not that it will be accurate  just fairly robust. Conor Stokes  This sf.net email is sponsored by: To learn the basics of securing=20 your web site with SSL, click here to get a FREE TRIAL of a Thawte=20 Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 Virus scanned and cleared ok  This sf.net email is sponsored by: To learn the basics of securing=20 your web site with SSL, click here to get a FREE TRIAL of a Thawte=20 Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88  This sf.net email is sponsored by: To learn the basics of securing=20 your web site with SSL, click here to get a FREE TRIAL of a Thawte=20 Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 Virus scanned and cleared ok 
From: Conor Stokes <cstokes@tp...>  20021114 10:42:44

>Is there any way of quantifying "robustness"? There is, but it's a bit imprecise... ...darwinism hasn't caught up to that pun yet. Conor Stokes 
From: Ville Miettinen <wili@ma...>  20021114 10:35:34

IMHO not. You cannot be a "little bit pregnant" nor can an = implementation be "quite robust". Either the routine works guaranteedly under all circumstances (such as an implementation using Shewchuk's predicates) = or it doesn't. Of course there are differences in the failure rates of the nonrobust routines, making some of them better than others. However, = just to keep our terms straight, I'd stick to a binary definition for = robustness. cheers, wili  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of John Connors Sent: Thursday, November 14, 2002 12:07 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] RE: higher accuracy Is there any way of quantifying "robustness"? Original Message From: Conor Stokes [mailto:cstokes@...] Sent: 14 November 2002 10:08 To: gdalgorithmslist@... Subject: Re: [Algorithms] RE: higher accuracy > > Sorry Gil but I have to challenge you on that. Write even a = "completely > robust" triangle/ray intersection routine with floats/doubles (i.e. > without reverting to exact arithmetics) and I'll buy you as many = pints of > beer you can drink. > Depends what you mean as robust  you can write a rather robust = pl=FCcker space triangle ray intersection that only uses floats, if you make sure = you have the same line at each shared edge of two triangles. There was a = paper on this around (that talked about robust ray triangle intersections = using shared edge pl=FCcker coords), but I can't seem to find it atm. Not that it will be accurate  just fairly robust. Conor Stokes  This sf.net email is sponsored by: To learn the basics of securing=20 your web site with SSL, click here to get a FREE TRIAL of a Thawte=20 Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 Virus scanned and cleared ok  This sf.net email is sponsored by: To learn the basics of securing=20 your web site with SSL, click here to get a FREE TRIAL of a Thawte=20 Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: John Connors <jconnors@re...>  20021114 10:13:08

Is there any way of quantifying "robustness"? Original Message From: Conor Stokes [mailto:cstokes@...] Sent: 14 November 2002 10:08 To: gdalgorithmslist@... Subject: Re: [Algorithms] RE: higher accuracy > > Sorry Gil but I have to challenge you on that. Write even a = "completely > robust" triangle/ray intersection routine with floats/doubles (i.e. > without reverting to exact arithmetics) and I'll buy you as many = pints of > beer you can drink. > Depends what you mean as robust  you can write a rather robust = pl=FCcker space triangle ray intersection that only uses floats, if you make sure = you have the same line at each shared edge of two triangles. There was a = paper on this around (that talked about robust ray triangle intersections = using shared edge pl=FCcker coords), but I can't seem to find it atm. Not that it will be accurate  just fairly robust. Conor Stokes  This sf.net email is sponsored by: To learn the basics of securing=20 your web site with SSL, click here to get a FREE TRIAL of a Thawte=20 Server Certificate: http://www.gothawte.com/rd524.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 Virus scanned and cleared ok 
From: Conor Stokes <cstokes@tp...>  20021114 10:07:35

> > Sorry Gil but I have to challenge you on that. Write even a "completely > robust" triangle/ray intersection routine with floats/doubles (i.e. > without reverting to exact arithmetics) and I'll buy you as many pints = of > beer you can drink. > Depends what you mean as robust  you can write a rather robust pl=FCcker space triangle ray intersection that only uses floats, if you make sure y= ou have the same line at each shared edge of two triangles. There was a pape= r on this around (that talked about robust ray triangle intersections using shared edge pl=FCcker coords), but I can't seem to find it atm. Not that it will be accurate  just fairly robust. Conor Stokes 
From: Martin Gladnishki <bzb@wi...>  20021114 09:23:28

Yeah, sure you're right about the memory bandwith issues with doubles. What I was talking about (obviously not clearly enough :) were the penalties when converting to/from double/float. But well, I suppose the memory bandwith is more of an issue on PSx, dunno. And this is definitely not the right list to comment PSx features (chillout cpt.Hook, I'm done :) Cheers, Martin  Original Message  From: "Jon Watte" <hplus@...> To: <gdalgorithmslist@...> Sent: Wednesday, November 13, 2002 8:31 PM Subject: RE: [Algorithms] RE:acos function  double to float tip > > > P.S. I've always believed working with double's is faster than > > with float's > > (well, excluding those precision issues), but then again it may not be the > > case with PSx, I don't know. I've got to do my homework :))) > > Even on CPU architectures where the FPU often extends floating point > out to their full length (such as the x86 in vanilla precision mode) > it's not true that doubles are faster. Doubles take twice the storage > space, so you'll get twice the cache misses, twice the bus bandwidth > utilization, blah blah blah. > > When you can live with floats, you really should. Just don't convert > between integer, float and double willynilly in your inner loop (or > the story of how I sped up an inherited particle system 10x in 10 > minutes :) > > Cheers, > > / h+ > > > >  > This sf.net email is sponsored by: Are you worried about > your web server security? Click here for a FREE Thawte > Apache SSL Guide and answer your Apache SSL security > needs: http://www.gothawte.com/rd523.html > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: Ville Miettinen <wili@ma...>  20021114 08:50:31

>need the intersection point at which your ray intersects the triangle, >you _must_ leave the confines of exact computation and enter epsilon land. >Whenever you actually need to _compute_ intersection >points (and not just test them), you basically don't have a choice: it's >epsilons for you. Uhm. nope. That's where rational arithmetics come in. If we can make the assumption that the input data (i.e. triangle vertex coordinates etc.) is completely accurate, we can easily compute the intersection points _exactly_. Certain operations (add,sub,mul,div,comparisons) can be done exactly using rationals, whereas others (square roots, sin/cos/tan etc.) cannot. These operations can then be accelerated by using floatingpoint filters. >But that's the simple stuff. To address e.g. the ray lying in the face of >the triangle you have to introduce epsilons, essentially giving the plane a >thickness. This too can be made to work, but it's not trivial getting it >right. I've done a fair bit of epsilonhacking over the years and usually have got things "almost" to work; i.e. the code works on all of my input data, but I can construct (manually) special cases that fail. My biggest problem with using floating point+epsilon stuff is that the resulting routines are not usually "selfconsistent", and cannot therefore be easily tested. By selfconsistency I mean that for a line segment/triangle intersection test, intersect(v0,v1,v2,l0,l1) _should_ be equal to intersect(v2,v1,v0,l0,l1) (changing winding of triangle) or intersect(v0,v1,v2,l1,l0) (changing direction of line segment). Even if the routine would use very inaccurate arithmetics, such equivalences _should_ hold. The only way to achieve this is to sort the input vertices and lines (so that FPU ops are always done in the same order) > this adds quite a bit of extra overhead to the routines, and is difficult to get right. * * * I am not saying that everyone should switch over to exact arithmetics right away, nor do I think that epsilonhacking should be completely abandonded. All I am really trying to say is that people shouldn't have delusions about writing "robust" epsilonbased routines. Yes, they may work for your input data sets. Yes, you may never ever see a glitch in your game. No, they are not robust. cheers, wili  o Ville Miettinen, Lead Programmer o Hybrid Graphics, Ltd. o Email: wili@... o Web: http://www.hybrid.fi Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of christer_ericson@... Sent: Thursday, November 14, 2002 02:23 To: gdalgorithmslist@... Subject: RE: [Algorithms] RE: higher accuracy Ville Miettinen wrote: > On Wed, 13 Nov 2002, Gribb, Gil wrote: > > All of this is a waste of CPU time (and programming time). It isn't that > > hard to get completely robust physics using just floats if you take the > > right approches. > > Sorry Gil but I have to challenge you on that. Write even a "completely > robust" triangle/ray intersection routine with floats/doubles (i.e. > without reverting to exact arithmetics) and I'll buy you as many pints of > beer you can drink. Ville is correct in saying that you cannot _exactly_ determine e.g. ray/triangle intersections using floatingpoint arithmetic without resorting to something equivalent to e.g. Shewchuk's orientation predicate (computing the exact sign, but not necessarily exact value, of a scalar triple product). Of course, in many applications you don't have to determine intersections exactly. For collision detection, for example, it is generally good enough that you collide with either of the triangles your ray passes through the common edge of, it doesn't have to be the one triangle that real arithmetic would indicate was hit. However, the problem in this case is making the code robust enough that your ray is colliding with either, and don't have your code indicate that you hit neither. There are various tricks for addressing these situations. In this case, as long as you make sure you always treat the edge as oriented in the same direction during testing, you are guaranteed to hit either triangle (even though it might not be the correct triangle, in the real sense). But that's the simple stuff. To address e.g. the ray lying in the face of the triangle you have to introduce epsilons, essentially giving the plane a thickness. This too can be made to work, but it's not trivial getting it right. Working with exact predicates greatly simplify the logic of these things, at the cost of execution speed, but as Ville pointed out, floatingpoint filters take care of a huge majority of the cases, so the exact predicate only has to be called in very special cases. The problem is that you can only ever do predicate testing exactly without resorting to exact arbitraryprecision arithmetic. Whenever you actually need the intersection point at which your ray intersects the triangle, you _must_ leave the confines of exact computation and enter epsilon land. So, in this sense, Gil is right, because in a physics engine, you need to compute collision points etc. and these cannot be computed exactly (since that truly would require infiniteprecision arithmetic) but must be snapped to a representative point. And so, we've done a full circle. Ville is right. Gil is right. It's just a matter of how you define the problem. The bottom line: whenever applicable, exact computation (using predicates or otherwise) is good as it simplifies your logic and lets you sleep at night, never having to worry about ridicule from your teammates about your toosmall epsilon. Whenever you actually need to _compute_ intersection points (and not just test them), you basically don't have a choice: it's epsilons for you. Christer Ericson Sony Computer Entertainment, Santa Monica  This sf.net email is sponsored by: Are you worried about your web server security? Click here for a FREE Thawte Apache SSL Guide and answer your Apache SSL security needs: http://www.gothawte.com/rd523.html _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Dan Baker <danbaker@wi...>  20021114 00:37:02

If you think of ambient as a an approximation of a global illumination = term (which it is), then the hemisphere trick is just a much better = approximation of the global illumination term which looks _vastly_ = better then ambient. The idea is that each element of the surface is lit = by a hemisphere of incoming light. (i.e. half of an enviroment cube = map). Bump detail comes right out it with this techinique. The Xbox game = Shrek used this alot. If you take an average diffuse environment from an average scene (i.e. = integrate the envmap), you'll find that it is quite smooth  you can = model it fairly well with just 2 colors, the sky and ground color. Then = use the trick I described before to mix them. This is fairly close to = the 'correct' solution, but we found it is good to precompute an = occlusion term so that pits and valleys get darkened since they can't = get received the whole % of light from the hemisphere.=20 Dan Original Message From: Gottfried Chen [mailto:gottfried.chen@...]=20 Sent: Tuesday, November 12, 2002 2:01 AM To: gdalgorithmslist@... Subject: AW: [Algorithms] Bump maps and ambient light What we currently do and looks ok: The color texture contains all = details painted in but lit with ambient light only (so no particular = light direction is assumed and the contrast is low). So even when there = is no directional/point light, no details pop away and plain ambient = lighting is used. It still looks a bit flat but I think it's more = correct than assuming any light direction in ambient only cases. Gottfried > Urspr=FCngliche Nachricht > Von: Dan Baker [mailto:danbaker@...]=20 > Gesendet: Dienstag, 12. November 2002 07:50 > An: gdalgorithmslist@... > Betreff: RE: [Algorithms] Bump maps and ambient light >=20 >=20 > You can use the hemisphere lighting trick, works great for=20 > these scenarios >=20 > i.e. use a 2 color ambient term, one is the sky color, the=20 > other is the ground color. Take the dot product between the=20 > normal and the vertical (0,0,1), rerange it to go from 0 to 1=20 > (instead of 1 to 1) and then lerp between the sky and ground color. >=20 > Technically (if you work the integral of a 2 hemisphere=20 > lighting model), its supposed to be the sin, not the cos, but=20 > its hard to tell the difference.=20 >=20 > Dan >=20 > Original Message > From: Gottfried Chen [mailto:gottfried.chen@...]=20 > Sent: Monday, November 11, 2002 7:46 AM > To: gdalgorithmslist@... > Subject: [Algorithms] Bump maps and ambient light >=20 > When you use bump maps from a higher poly model and the model=20 > is placed into an area with ambient light only then there's=20 > the problem that the detail in this area is a lot lower then=20 > in lit places. What are good ways to solve this? >=20 >  Don't use ambient light (that's not possible for what we're=20 > doing, since we'd get big dark areas). >  Use a texture that has the detail painted into and=20 > switch/fade to this texture when you can't use dot3 lighting,=20 > though I don't think this'll look good. >  Light the model from a default direction in ambient only places. >=20 > Gottfried >=20 >=20 >  > This sf.net email is sponsored by:ThinkGeek > Welcome to geek heaven. > http://thinkgeek.com/sf=20 > _______________________________________________ > GDAlgorithmslist mailing list GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 >=20 >  > This sf.net email is sponsored by:ThinkGeek > Welcome to geek heaven. > http://thinkgeek.com/sf=20 > _______________________________________________ > GDAlgorithmslist mailing list GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20  This sf.net email is sponsored by:ThinkGeek Welcome to geek heaven. http://thinkgeek.com/sf _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 