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}

2017 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(1) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 







1
(12) 
2
(5) 
3
(30) 
4
(13) 
5
(26) 
6
(37) 
7
(26) 
8
(24) 
9
(9) 
10
(34) 
11
(39) 
12
(16) 
13
(21) 
14
(27) 
15
(11) 
16
(2) 
17
(7) 
18
(6) 
19
(3) 
20
(15) 
21
(4) 
22

23

24
(6) 
25
(20) 
26
(32) 
27
(35) 
28
(28) 

From: Tyson Jensen <twjensen@sa...>  20030228 19:49:00

REAL robust Matrices require 3 sqrts to reorthonormalize. Why can REAL matrices just ignore this step but REAL quaternions have to have it? OTOH, the PS2 (modern example processor) does a 32bit sqrt in 7 cycles (less than a divide!). It is well worth the time to browse every new processor manual for cycle counts on various operations. Your expensive operation assumptions need to change every rev if you want to stay on top of performance. The ability to quickly see what way something is facing is pretty important for lots of situations, and matrices have a clear edge there. Quaternions are best in situations where you need lots of rotations, no scales, no shears, and limited translations. Sounds like a description of a typical IK / animation problem.... In such cases I prefer to use quaternions. In graphics, the hardware is all matrix optimized so I'm sticking with matrices there. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Richard Fabian Sent: Friday, February 28, 2003 2:18 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Quaternions or Matrices four reasons I can think of why we don't use quaternions as matrix replacements: you cannot directly build a quaternion from pos, dir, up neither can you use the rows to show what way something is facing until you convert it to a matrix. quaternions do not require 51 mults and 39 adds... REAL robust quaternion code also takes a sqrt for normalising the S value, which we all know is not good for speed. s values can become degraded if you chain enough quats together at the wrong angles.. you try it, you will find you are getting artifacts at certain rotations... do the math, and find out that it is a REAL limitation of quaternions... and of course there is the fact that you sometimes have to make up new standards like how to store mirroring, scale, shear. (although mirroring can be simply the lowest bit in your s value) > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...] On > Behalf Of Stefan Maton > Sent: 28 February 2003 09:49 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Quaternions or Matrices > > > > which gives a pointer to > > http://www.gamedev.net/reference/articles/article1199.asp > that has an > > interesting debate about this. > > Well, I don't think that helps me to understand why quaternions aren't > used more often. > > IMO the article doesn't take into account the effective number of > operations used to do a transformation. > > Using a 4x4 matrix (containing rotation, scaling and translation) > it takes 64 multiplications and 64 add operations to combine two > matrices (matrix multiplication). > > The same can be done with 51 multiplications and 39 add operations > using a quaternion and 2 vectors. > > Yes, there's a overhead because you have to convert the quaternion > into a matrix when passing it to OpenGL/DirectX but this takes 17 > mult and 15 add operations making it 68 mult and 54 add operations > to create a transformation matrix. > > Now, this doesn't make much benefit, if you only have the world and > one object to combine. But it makes a big difference when you do it > on a large number of objects. > > Kind regards, > Stefan > > >  > 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_id=6188 >  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_id=6188 
From: Tom Forsyth <tomf@mu...>  20030228 16:51:28

...but surely they're using doubles anyway? I agree with denormals if you're into that whole precisison thang. But burning clock cycles to very slightly improve the precision of something that I've said doesn't have to be very precise seems a bit pointless. Every time I say "float" instead of "double" I'm deliberately expressing my stance in the precision/speed tradeoff. Anyway, if I really cared I'd go and nobble the FP mode register every frame... :) 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: Christopher Phillips > [mailto:cphillips@...] > Sent: 28 February 2003 16:08 > To: 'gdalgorithmslist@...' > Subject: [Algorithms] demormals > > > > > I thought the point of denormals was more to prevent a sudden > gap/loss of > precision appearing around zero, rather than to get the extra > zeros per se. > > With them your floats near zero are spaced like this: > > . . . . . . . . ........0........ . . . . . . . . > > and without them your floats are spaced like this: > > . . . . . . . . ..... 0 ..... . . . . . . . . > > which can make for considerably less graceful degradation in > some instances. > > Still overkill for most console applications, although I'm > sure several > hundred physics programmers would disagree ;) > > > > Original Message > > From: Tom Forsyth [mailto:tom.forsyth@...] > > Sent: 26 February 2003 21:10 > > To: gdalgorithmslist@... > > Subject: Re: [Algorithms] Optimising a loop (Integration help) > > > > > > Fortunately they never _generate_ denormals either, they just > > set the result > > to +/0. Which is at least consistent. I was never that impressed by > > denormals anyway  it's a lot of hassle just to allow you six > > more zeros > > after the decimal point. If you really want to handle those sorts of > > numbers, you're going to switch to doubles. > > > > TomF  Muckyfoot coder. > > > >  > Virus scanned and cleared ok > > >  > 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_id=6188 > 
From: John Mckenna <jmckenna@re...>  20030228 16:34:46

After buying a toy football (that'd be "soccer ball" to some of you) the other day and staring at it for a while, I have another method. It's only an approximation, but that's fine for my application. It can be made to overstate the pentagon areas, which is actually better for me than the exact solution. Put the centre of one of the pentagonal faces on the positive x axis. Call that pentagon A, and five nearest pentagons BF. If x is negative, then negate the direction and set a flag. Take the dot product of the direction with the centre of each pentagon AF (A is trivial, because it's on the x axis). Test each dot product against two thresholds P and Q. P represents the radius of a pentagon. Q represents the radius of the surrounding ring of hexagons. If any of the dot products is greater than P, you're inside that pentagon and can return immediately (remembering that you're in the opposite pentagon if the flag was set). Otherwise, build a 6 bit number  each bit is '1' if the dot product from that pentagon is greater than Q. Do a table lookup, invert the top bit if the flag was set, and return. The indices of opposite faces differ in the top bit. Apart from that the mapping is arbitrary. There are five dot products of the input direction with constants. Four can be done in parallel with a matrix multiplication. Virus scanned and cleared ok 
From: IvanAssen Ivanov <assen@ha...>  20030228 16:29:20

> BTW: using the "plain" English form of soundex codes "chuj" > and "rachuj" are > different: C200 and R220. Then again "cox" is C200, which > would no doubt please Tony and his kinfolk round the world if > your game refused to accept their surname ;o) By the way, I guess some English filtering software would reject Tony's surname anyway :) regards, Assen ^^^ by the way, I have been denied registration at several sites :) 
From: IvanAssen Ivanov <assen@ha...>  20030228 16:25:54

> I don't > actually think there's a good solution to filtering out all > possible offensive language without an advanced AI IMHO, no matter how advanced this AI is, it will be still dumber than the users who try to circumvent it. Anything more than a simple blacklist seems like too much work for little practical results. 
From: Christopher Phillips <cphillips@re...>  20030228 16:12:14

I thought the point of denormals was more to prevent a sudden gap/loss of precision appearing around zero, rather than to get the extra zeros per se. With them your floats near zero are spaced like this: . . . . . . . . ........0........ . . . . . . . . and without them your floats are spaced like this: . . . . . . . . ..... 0 ..... . . . . . . . . which can make for considerably less graceful degradation in some instances. Still overkill for most console applications, although I'm sure several hundred physics programmers would disagree ;) > Original Message > From: Tom Forsyth [mailto:tom.forsyth@...] > Sent: 26 February 2003 21:10 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Optimising a loop (Integration help) > > > Fortunately they never _generate_ denormals either, they just > set the result > to +/0. Which is at least consistent. I was never that impressed by > denormals anyway  it's a lot of hassle just to allow you six > more zeros > after the decimal point. If you really want to handle those sorts of > numbers, you're going to switch to doubles. > > TomF  Muckyfoot coder. >  Virus scanned and cleared ok 
From: Matt Newport <matt.newport@ni...>  20030228 15:07:43

That's pretty much what I was saying, only from my understanding of the = use of this dictionary you would not necessarily expect more negatives = than positives, hence my question. Wojciech said that this dictionary = would be used for word games and catching bad language. For a word game = you'll presumably be validating a user's word against a dictionary of = acceptable words. In this case I'd expect most words to be valid and = only a few to be invalid. For filtering bad language and catching = unacceptable words I'm not actually sure this is the best approach = anyway  you either need a dictionary of all acceptable words which runs = the risk of rejecting innocent misspellings, names and unusual words or = you need a dictionary of every possible variant of offensive words which = sounds impractical. Wojciech said he wanted the dictionary to catch = variations of vulgar words like "vul!ga*v", that doesn't seem practical = in a scheme that tries to catch bad language by checking a dictionary of = all variant spellings of potentially offensive words. I don't actually = think there's a good solution to filtering out all possible offensive = language without an advanced AI that has some 'understanding' of the = context. Matt. > Original Message > From: Tom Forsyth [mailto:tomf@...]=20 > Sent: 28 February 2003 13:41 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Dictionary compression >=20 >=20 > The idea of using a Bloom filter is to do a more through=20 > check if you get a positive isn't it? So sure, the filter=20 > might give a false positive, but then you do an actual=20 > dictionary search. As long as the number of positives (false=20 > or not) isn't too big (which is the assumption IIRC), you=20 > should be fine. >=20 > Tom Forsyth  Muckyfoot bloke and Microsoft MVP. >=20 > This email is the product of your deranged imagination, > and does not in any way imply existence of the author. >=20 > > Original Message > > From: Wojciech Wylon [mailto:wwylon@...] > > Sent: 28 February 2003 13:30 > > To: gdalgorithmslist@... > > Subject: RE: [Algorithms] Dictionary compression > >=20 > >=20 > > > Do you expect the majority of searches to be for > > nonexisting words or > > > existing words? A Bloom filter seems good if most=20 > searches are going > > to be > > > for nonexisting words (early out for most such words)=20 > but if most=20 > > > searches are for existing words you are still going to have to do > > another > > > search on the actual dictionary to confirm the word really > > does exist > > > aren't you? Or are you willing to accept some false positives if > > they're > > > rare? > >=20 > > [Wojciech Wylon] > > I have to admit my previous results for Bloom filter were "a=20 > > bit" wrong > > ;( > > If I will have one false positive per million  it will not be a > > problem. I have other problem with Bloom filter: if I use=20 > modulo prime > > for my hashing functions  the code is slower than other=20 > > variants, when > > I use "hash()& val" where val is power of 2 minus 1 than I have bad > > behavior (too many false positive)  probably I need to find better > > hashing functions... > >=20 > > BTW so far the best result I achieved with "perfect=20 > hashing"  560.000=20 > > fetches per sec/< 20MB of memory used. I suppose that it can be=20 > > further improved a bit... > >=20 > > Wojciech Wylon > >=20 > > =20 > > > Matt. > > >=20 > > > > [Wojciech Wylon] > > > > Yes I tested Bloom filters: > > > > For 2.000.000 I used array of size about 97.000.000=20 > bits (quite a=20 > > > > lot of memory) and 16 hashing functions. The results are quite=20 > > > > good: 1.200.000 fetches per second. > > > > For 10.000.000 of random (I used MarsenneTwister) tests for > > > > nonexisting words (27 letters) I have not got single false > > positive! > > > > > > > > The only problem I have is that there is (obvious) bug=20 > in the code=20 > > > > (I did it when I optimized hashing procedure  I use slightly =20 > > > > different hashing function for insertion and for > > > > testing)  when I remove the bug it start either to=20 > give quite a=20 > > > > lot of false positives or slow down considerable... I probably=20 > > > > have to rethink it once again... > > > > > > > > WW > > >=20 > > >  > > > Outgoing mail is certified Virus Free. > > > Checked by AVG antivirus system (http://www.grisoft.com). > > > Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 > > >=20 > > >=20 > > >=20 > > >  > > > This sf.net email is sponsored by:ThinkGeek > > > Welcome to geek heaven. > > > http://thinkgeek.com/sf=20 > > > _______________________________________________ > > > GDAlgorithmslist mailing list=20 > > > GDAlgorithmslist@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > > Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 > >=20 > >=20 > >  > > This sf.net email is sponsored by:ThinkGeek > > Welcome to geek heaven. > > http://thinkgeek.com/sf=20 > > _______________________________________________ > > GDAlgorithmslist mailing list=20 > 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: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_id=3D6188 >=20 >  > Incoming mail is certified Virus Free. > Checked by AVG antivirus system (http://www.grisoft.com). > Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 > =20 >=20  Outgoing mail is certified Virus Free. Checked by AVG antivirus system (http://www.grisoft.com). Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 =20 
From: Tom Forsyth <tomf@mu...>  20030228 13:47:33

The idea of using a Bloom filter is to do a more through check if you get a positive isn't it? So sure, the filter might give a false positive, but then you do an actual dictionary search. As long as the number of positives (false or not) isn't too big (which is the assumption IIRC), you should be fine. 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: Wojciech Wylon [mailto:wwylon@...] > Sent: 28 February 2003 13:30 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Dictionary compression > > > > Do you expect the majority of searches to be for > nonexisting words or > > existing words? A Bloom filter seems good if most searches are going > to be > > for nonexisting words (early out for most such words) but if most > > searches are for existing words you are still going to have to do > another > > search on the actual dictionary to confirm the word really > does exist > > aren't you? Or are you willing to accept some false positives if > they're > > rare? > > [Wojciech Wylon] > I have to admit my previous results for Bloom filter were "a > bit" wrong > ;( > If I will have one false positive per million  it will not be a > problem. I have other problem with Bloom filter: if I use modulo prime > for my hashing functions  the code is slower than other > variants, when > I use "hash()& val" where val is power of 2 minus 1 than I have bad > behavior (too many false positive)  probably I need to find better > hashing functions... > > BTW so far the best result I achieved with "perfect hashing"  560.000 > fetches per sec/< 20MB of memory used. I suppose that it can > be further > improved a bit... > > Wojciech Wylon > > > > Matt. > > > > > [Wojciech Wylon] > > > Yes I tested Bloom filters: > > > For 2.000.000 I used array of size about 97.000.000 bits > > > (quite a lot of memory) and 16 hashing functions. > > > The results are quite good: > > > 1.200.000 fetches per second. > > > For 10.000.000 of random (I used MarsenneTwister) tests for > > > nonexisting words (27 letters) I have not got single false > positive! > > > > > > The only problem I have is that there is (obvious) bug in the > > > code (I did it when I optimized hashing procedure  I use > > > slightly different hashing function for insertion and for > > > testing)  when I remove the bug it start either to give > > > quite a lot of false positives or slow down considerable... I > > > probably have to rethink it once again... > > > > > > WW > > > >  > > Outgoing mail is certified Virus Free. > > Checked by AVG antivirus system (http://www.grisoft.com). > > Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 > > > > > > > >  > > 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 > > > >  > 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_id=6188 > 
From: Wojciech Wylon <wwylon@ga...>  20030228 13:28:17

> Do you expect the majority of searches to be for nonexisting words or > existing words? A Bloom filter seems good if most searches are going to be > for nonexisting words (early out for most such words) but if most > searches are for existing words you are still going to have to do another > search on the actual dictionary to confirm the word really does exist > aren't you? Or are you willing to accept some false positives if they're > rare? [Wojciech Wylon] I have to admit my previous results for Bloom filter were "a bit" wrong ;( If I will have one false positive per million  it will not be a problem. I have other problem with Bloom filter: if I use modulo prime for my hashing functions  the code is slower than other variants, when I use "hash()& val" where val is power of 2 minus 1 than I have bad behavior (too many false positive)  probably I need to find better hashing functions... BTW so far the best result I achieved with "perfect hashing"  560.000 fetches per sec/< 20MB of memory used. I suppose that it can be further improved a bit... Wojciech Wylon > Matt. > > > [Wojciech Wylon] > > Yes I tested Bloom filters: > > For 2.000.000 I used array of size about 97.000.000 bits > > (quite a lot of memory) and 16 hashing functions. > > The results are quite good: > > 1.200.000 fetches per second. > > For 10.000.000 of random (I used MarsenneTwister) tests for > > nonexisting words (27 letters) I have not got single false positive! > > > > The only problem I have is that there is (obvious) bug in the > > code (I did it when I optimized hashing procedure  I use > > slightly different hashing function for insertion and for > > testing)  when I remove the bug it start either to give > > quite a lot of false positives or slow down considerable... I > > probably have to rethink it once again... > > > > WW > >  > Outgoing mail is certified Virus Free. > Checked by AVG antivirus system (http://www.grisoft.com). > Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 > > > >  > 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 
From: Joakim Hagdahl <disc@ho...>  20030228 12:05:35

Dont shy away from it though, its nice for interpolation, animations etc.  Original Message  From: "Stefan Maton" <metron@...> To: <gdalgorithmslist@...> Sent: Friday, February 28, 2003 12:50 PM Subject: RE: [Algorithms] Quaternions or Matrices > @All... I get your points. > > I think I have to rethink my quaternion based structure. > > Thanks, > Stefan > > >  > 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_id=6188 > 
From: Stefan Maton <metron@sk...>  20030228 11:50:10

@All... I get your points. I think I have to rethink my quaternion based structure. Thanks, Stefan 
From: Nick Newson <nnewson@fr...>  20030228 11:25:17

Yeap...and 4 vector register loads. On Fri, 28 Feb 2003, Paul Firth wrote: > > drastically reduced. On PS2 for example, you can rotate a vector with a > > matrix with 8 VU instructions. > > Erm, 4 you mean? ;) > > Cheers, Paul. > > > >  > 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_id=6188 > 
From: Dean Calver <deano@ec...>  20030228 10:46:28

But a 4x4 matrix is more general than a rotation, scale and translation. Shears and projective transforms and other 'odd' transforms all fall neatly into the matrix case but not the quaternion case. 4x4 matrices are a superset of the transforms we use on a day to day basis, its handy to have that flexibility for when you need it. I once inherited an engine that use quats and 2 vectors to pass things into the renderer and the first thing we had to we replace it with 4x4 matrices, the reason being our animation system sometimes used shears and we wanted to use projection for simple shadows. Your not comparing like for like when comparing quats and 4x4 matrices, 4x4 matrices are very powerful objects. Unit quats are just rotations, that can be a good thing higher up but at the lowest level matrices are more general. Bye, Deano Dean Calver, Eclipse Studios.  Original Message  From: "Stefan Maton" <metron@...> To: <gdalgorithmslist@...> Sent: Friday, February 28, 2003 9:48 AM Subject: RE: [Algorithms] Quaternions or Matrices > > which gives a pointer to > > http://www.gamedev.net/reference/articles/article1199.asp that has an > > interesting debate about this. > > Well, I don't think that helps me to understand why quaternions aren't > used more often. > > IMO the article doesn't take into account the effective number of > operations used to do a transformation. > > Using a 4x4 matrix (containing rotation, scaling and translation) > it takes 64 multiplications and 64 add operations to combine two > matrices (matrix multiplication). > > The same can be done with 51 multiplications and 39 add operations > using a quaternion and 2 vectors. > > Yes, there's a overhead because you have to convert the quaternion > into a matrix when passing it to OpenGL/DirectX but this takes 17 > mult and 15 add operations making it 68 mult and 54 add operations > to create a transformation matrix. > > Now, this doesn't make much benefit, if you only have the world and > one object to combine. But it makes a big difference when you do it > on a large number of objects. > > Kind regards, > Stefan > > >  > 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_id=6188 > > 
From: Matt Newport <matt.newport@ni...>  20030228 10:45:14

Do you expect the majority of searches to be for nonexisting words or = existing words? A Bloom filter seems good if most searches are going to = be for nonexisting words (early out for most such words) but if most = searches are for existing words you are still going to have to do = another search on the actual dictionary to confirm the word really does = exist aren't you? Or are you willing to accept some false positives if = they're rare? Matt. > [Wojciech Wylon]=20 > Yes I tested Bloom filters:=20 > For 2.000.000 I used array of size about 97.000.000 bits=20 > (quite a lot of memory) and 16 hashing functions.=20 > The results are quite good: > 1.200.000 fetches per second. > For 10.000.000 of random (I used MarsenneTwister) tests for=20 > nonexisting words (27 letters) I have not got single false positive! >=20 > The only problem I have is that there is (obvious) bug in the=20 > code (I did it when I optimized hashing procedure  I use=20 > slightly different hashing function for insertion and for=20 > testing)  when I remove the bug it start either to give=20 > quite a lot of false positives or slow down considerable... I=20 > probably have to rethink it once again... >=20 > WW  Outgoing mail is certified Virus Free. Checked by AVG antivirus system (http://www.grisoft.com). Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 =20 
From: Stefan Maton <metron@sk...>  20030228 10:40:46

> Well, I guess I should have made it more explicit: I posted a link to > the article because it is the starting point of a 'long' debate on this > thread: http://www.gamedev.net/community/forums/topic.asp?topic_id=25314 > (link at the beginning of the article) > > A lot of things are discussed there, including the point you are > mentioning. They however mention some cases where matrices are more > adapted than vectors/quaternions. Aaah... I remember having read it... Thanks, Stefan 
From: Matt Newport <matt.newport@ni...>  20030228 10:38:57

Have a look at = http://www.magicsoftware.com/Documentation/RotationIssues.pdf A few things to note: comparing quaternions to 4x4 matrix multiplys does = not make much sense, a 4x4 matrix can represent more than simple = rotation. When navigating a hierarchy I don't think it makes much sense = to use 4x4 matrices, use an sRT representation (uniform scale, rotation, = translation) and you can either use a float a quat and a vec3 or a float = a mat3x3 and a vec3. With quats it is cheaper to combine rotations but = applying the rotation to the translation vector is more expensive than = with the 3x3 matrix. It is also cheaper to assemble your final 4x4 = matrix (for passing to the software or hardware transform pipeline) from = a 3x3 rotation matrix, a scale factor and a translation vector than it = is to assemble it from a quat scale and translation.=20 Quaternions certainly have their uses but matrices are sometimes better. = As ever it all depends on the situation. Matt. > Original Message > From: Stefan Maton [mailto:metron@...]=20 > Sent: 28 February 2003 07:21 > To: Algorithms > Subject: [Algorithms] Quaternions or Matrices >=20 >=20 > Hi, >=20 > I've been working with quaternions for quite some time > now and have been using them within my engine for more > than 1 1/2 years. >=20 > I wonder why quaternions are not used on a broad manner. >=20 > Looking at the main functions : >=20 > Matrix(4x4) Multiply : 64 float mults and 64 float add=20 > Quaternion Multiply : 16 float mults and 12 float add >=20 > Matrix(4x4) Add : 16 float adds > Quaternion Add : 4 float adds >=20 > Additionally you only pass 10 floats (Quat, pos, scale) > instead of 16 when passing it through a hierarchy to be transformed. >=20 > Am I missing something ? >=20 > What does people make use matrices instead of quaternions ? >=20 > Kind regards, > Stefan >=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_id=3D6188 >=20 >  > Incoming mail is certified Virus Free. > Checked by AVG antivirus system (http://www.grisoft.com). > Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 > =20 >=20  Outgoing mail is certified Virus Free. Checked by AVG antivirus system (http://www.grisoft.com). Version: 6.0.458 / Virus Database: 257  Release Date: 24/02/2003 =20 
From: Stefan Maton <metron@sk...>  20030228 10:33:50

> Hardware friendly. > The kind of figures you're coming out with are not really relavent because > the hardware is optimised for matrices. SIMD support means this > drastically reduced. On PS2 for example, you can rotate a vector with a > matrix with 8 VU instructions. Ok... that's a point. > In all fixed vertex pipeline API that I know about you have to supply your > transform in matrices  so it makes sense to use them when you can. This doesn't mean that you cannot use Quaternion meanwhile. In my other post, I sent some numbers about the number of add/mults you have in both ways. Kind regards, Stefan 
From: Paul Firth <pfirth@at...>  20030228 10:22:56

> drastically reduced. On PS2 for example, you can rotate a vector with a > matrix with 8 VU instructions. Erm, 4 you mean? ;) Cheers, Paul. 
From: Richard Fabian <algorithms@th...>  20030228 10:21:48

four reasons I can think of why we don't use quaternions as matrix replacements: you cannot directly build a quaternion from pos, dir, up neither can you use the rows to show what way something is facing until you convert it to a matrix. quaternions do not require 51 mults and 39 adds... REAL robust quaternion code also takes a sqrt for normalising the S value, which we all know is not good for speed. s values can become degraded if you chain enough quats together at the wrong angles.. you try it, you will find you are getting artifacts at certain rotations... do the math, and find out that it is a REAL limitation of quaternions... and of course there is the fact that you sometimes have to make up new standards like how to store mirroring, scale, shear. (although mirroring can be simply the lowest bit in your s value) > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...] On > Behalf Of Stefan Maton > Sent: 28 February 2003 09:49 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Quaternions or Matrices > > > > which gives a pointer to > > http://www.gamedev.net/reference/articles/article1199.asp > that has an > > interesting debate about this. > > Well, I don't think that helps me to understand why quaternions aren't > used more often. > > IMO the article doesn't take into account the effective number of > operations used to do a transformation. > > Using a 4x4 matrix (containing rotation, scaling and translation) > it takes 64 multiplications and 64 add operations to combine two > matrices (matrix multiplication). > > The same can be done with 51 multiplications and 39 add operations > using a quaternion and 2 vectors. > > Yes, there's a overhead because you have to convert the quaternion > into a matrix when passing it to OpenGL/DirectX but this takes 17 > mult and 15 add operations making it 68 mult and 54 add operations > to create a transformation matrix. > > Now, this doesn't make much benefit, if you only have the world and > one object to combine. But it makes a big difference when you do it > on a large number of objects. > > Kind regards, > Stefan > > >  > 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_id=6188 > 
From: Vincent PRAT <vprat@if...>  20030228 10:13:59

Well, I guess I should have made it more explicit: I posted = a link to the article because it is the starting point of a 'long' deb= ate on this thread: http://www.gamedev.net/community/forums/topic.asp?to= pic_id=3D25314 (link at the beginning of the article) A lot of things are discussed there, including the point you= are mentioning. They however mention some cases where matrices a= re more adapted than vectors/quaternions. Have a nice read, Vincent Message d'origine De: "Stefan Maton" <metron@...> A: <gdalgorithmslist@...> Date: 28/02/03 Objet: RE: [Algorithms] Quaternions or Matrices > which gives a pointer to=20 > http://www.gamedev.net/reference/articles/article1199.asp = that has an > interesting debate about this. Well, I don't think that helps me to understand why quaterni= ons aren't used more often. IMO the article doesn't take into account the effective numb= er of operations used to do a transformation. Using a 4x4 matrix (containing rotation, scaling and transla= tion) it takes 64 multiplications and 64 add operations to combine= two matrices (matrix multiplication). The same can be done with 51 multiplications and 39 add oper= ations using a quaternion and 2 vectors. Yes, there's a overhead because you have to convert the quat= ernion into a matrix when passing it to OpenGL/DirectX but this tak= es 17 mult and 15 add operations making it 68 mult and 54 add oper= ations to create a transformation matrix. Now, this doesn't make much benefit, if you only have the wo= rld and one object to combine. But it makes a big difference when yo= u do it on a large number of objects. Kind regards, Stefan ____________________________________________________________= _________ GRAND JEU SMS : Pour gagner un NOKIA 7650, envoyez le mot IF= au 61321 (prix d'un SMS + 0.35 euro). Un SMS vous dira si vous avez g= agn=E9. R=E8glement : http://www.ifrance.com/_reloc/sign.sms 
From: Richard Fabian <algorithms@th...>  20030228 10:05:28

my mail is SOOOOOOOOOOOOOOOOOOO slow at the mment, o replied as soon as that hit my mail box. :S I posted the following mail at just after three :( > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...] On > Behalf Of Gareth Lewin > Sent: 27 February 2003 14:10 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Dictionary compression > > > Hey, I already admitted I was wrong. > > > Original Message > > From: Richard Fabian [mailto:algorithms@...] > > Sent: 27 February 2003 13:01 > > To: gdalgorithmslist@... > > Subject: RE: [Algorithms] Dictionary compression > > > > > > > > On the compression side, do you care about case ? If not you > > > > only need 26 > > > > values (4 bit) to store each character, pretty fast 2 to 1 > > > compression > > > > there. > > > > lol > > > > > > > >  > > This SF.NET email is sponsored by: > > SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See! > > http://www.vasoftware.com > > _______________________________________________ > > 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: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_id=6188 > 
From: Stefan Maton <metron@sk...>  20030228 09:48:41

> which gives a pointer to > http://www.gamedev.net/reference/articles/article1199.asp that has an > interesting debate about this. Well, I don't think that helps me to understand why quaternions aren't used more often. IMO the article doesn't take into account the effective number of operations used to do a transformation. Using a 4x4 matrix (containing rotation, scaling and translation) it takes 64 multiplications and 64 add operations to combine two matrices (matrix multiplication). The same can be done with 51 multiplications and 39 add operations using a quaternion and 2 vectors. Yes, there's a overhead because you have to convert the quaternion into a matrix when passing it to OpenGL/DirectX but this takes 17 mult and 15 add operations making it 68 mult and 54 add operations to create a transformation matrix. Now, this doesn't make much benefit, if you only have the world and one object to combine. But it makes a big difference when you do it on a large number of objects. Kind regards, Stefan 
From: Nick Newson <nnewson@fr...>  20030228 09:23:37

Hardware friendly. The kind of figures you're coming out with are not really relavent because the hardware is optimised for matrices. SIMD support means this drastically reduced. On PS2 for example, you can rotate a vector with a matrix with 8 VU instructions. In all fixed vertex pipeline API that I know about you have to supply your transform in matrices  so it makes sense to use them when you can. Nick. On Fri, 28 Feb 2003, Stefan Maton wrote: > Hi, > > I've been working with quaternions for quite some time > now and have been using them within my engine for more > than 1 1/2 years. > > I wonder why quaternions are not used on a broad manner. > > Looking at the main functions : > > Matrix(4x4) Multiply : 64 float mults and 64 float add > Quaternion Multiply : 16 float mults and 12 float add > > Matrix(4x4) Add : 16 float adds > Quaternion Add : 4 float adds > > Additionally you only pass 10 floats (Quat, pos, scale) > instead of 16 when passing it through a hierarchy to be > transformed. > > Am I missing something ? > > What does people make use matrices instead of quaternions ? > > Kind regards, > Stefan > > >  > 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_id=6188 > 
From: Vincent PRAT <vprat@if...>  20030228 08:29:43

There was a thread about this on flipcode just a few days/we= eks ago. http://www.flipcode.com/cgibin/msg.cgi?showThread=3D0000741= 7&forum=3D3dtheo ry&id=3D1 which gives a pointer to=20 http://www.gamedev.net/reference/articles/article1199.asp th= at has an interesting debate about this. Bye, I hope this helps Vincent PRAT site: http://vprat.alrj.org mail: vprat@... ____________________________________________________________= _________ Envie de discuter en "live" avec vos amis ? T=E9l=E9charger = MSN Messenger http://www.ifrance.com/_reloc/m la 1=E8re messagerie instant= an=E9e de France 
From: Stefan Maton <metron@sk...>  20030228 07:21:13

Hi, I've been working with quaternions for quite some time now and have been using them within my engine for more than 1 1/2 years. I wonder why quaternions are not used on a broad manner. Looking at the main functions : Matrix(4x4) Multiply : 64 float mults and 64 float add Quaternion Multiply : 16 float mults and 12 float add Matrix(4x4) Add : 16 float adds Quaternion Add : 4 float adds Additionally you only pass 10 floats (Quat, pos, scale) instead of 16 when passing it through a hierarchy to be transformed. Am I missing something ? What does people make use matrices instead of quaternions ? Kind regards, Stefan 