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
(3) 
2
(15) 
3
(38) 
4
(23) 
5
(22) 
6
(42) 
7
(4) 
8
(7) 
9
(61) 
10
(13) 
11
(26) 
12
(22) 
13
(26) 
14
(1) 
15
(6) 
16
(12) 
17
(15) 
18
(20) 
19
(17) 
20
(44) 
21
(6) 
22
(1) 
23
(14) 
24
(28) 
25
(27) 
26
(24) 
27
(1) 
28
(2) 
29
(3) 
30
(17) 





From: <christer_ericson@pl...>  20020913 23:17:49

Charles Bloom wrote: >Yeah, but the point is that a sorted array is just a >representation of a binary tree. Once I have either one, >they're both log(N) to look up. Of course. My point was just that there's a big difference between them being "equivalent algorithmically" (as you put it) and being equivalent implementationally. Attempting to implement a nodebased tree structure for this is going to be way slower than just doing a single pass over the array of probabilities to create the array of partial sums. (I'm not saying _you_ would, just that it would be, in general.) Anyway, the suggestion to use Walker's alias method is clearly superior for all but small N's. I looked up the original article(*), and it even has sample FORTRAN code in it! (BTW, I wish more academic papers would have code or pseudocode in them, but I guess that's just too lowbrow and practical.) (*) Walker, Alastair J. An efficient method for generating discrete random variables with general distributions. ACM Journal on Mathematical Software, Vol 3, No 3, September 1977, pg. 253256. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: Charles Bloom <cbloom@cb...>  20020913 21:16:30

Awesome. At 03:48 PM 9/13/2002 0400, DoRon B. Motter wrote: >A fast, fast method to do this is known as the alias method, check most >probability texts for more info. I happen to have a copy of Ross, "Intro >to Prob Models" around, so this is essentially his description. > >The method is the following (1based arrays...). > >Let P be your distribution of event probabilities (P = n). > >What you want to do is find n1 other _distributions_, Q(i) so that >each distribution Q(i) has at most 2 nonzero components. In addition, you >want P = (1/(n1)) Sum( Q(i) ); > >I will go into how to do that in a sec. But the idea is once you have the >Q(i)'s then simulating events from P is efficient. You only need to: > >1. Generate a random integer r1 in the range [1..n1] and find Q(r1) >2. Generate random float u1 in [0, 1] >3. Say Q(r1) has nonzero components i(r1) and j(r1) then > if(u1 < i(r1)) then use event i > else use event j > >The reason this will work is that you have your original probability >distribution written as an equally weighted sum of <=2element probability >distributions. So you choose a distribution Q at random (with equal >probability) then you can choose from within that probability >distribution. Step 3 works since Q(i)'s are distributions. >For efficiency you don't really need a new rn in step 2, >just use the remainder off your first one, etc. There are other >optimizations too, but that is the basic idea. > > >So... how do you get the Q(i)'s? > >Repeatedly do the following: > >Find elements i,j from your P (which must always exists) so that > P[i] < 1/(n1) and P[i] + P[j] >= 1/(n1) > >Then your distribution Q will contain all the mass for i in the sense: > Q[i] = (n1)P[i] > Q[j] = 1  Q[i] > >Now P is basically like > P=1/(n1)Q + (n2)/(n1)P' > >Where P' is the 'leftover' distribution (it is still a distribution).. > >Repeat the process on P' to obtain the next Q. Note that P'[i] = 0 >so you eliminate an element each time. So you will need at most n1 >distributions Q. Then you can use the method above to quickly find >events from P. > >hth > >DoRon > > > > > >On Fri, 13 Sep 2002, Johnson, James wrote: > > > > > For the dynamic case seems to me a cunning use of a priorty queue fits the > > bill. > > > > James > > > > Original Message > > From: Charles Bloom [mailto:cbloom@...] > > Sent: Friday, September 13, 2002 10:58 AM > > To: gdalgorithmslist@... > > Subject: [Algorithms] efficient random events > > > > > > > > I want to efficiently generate random events of this > > form : > > > > I know one event occurs (maybe it was random if it > > occurred or not, but at this point, it's going to > > occur). > > > > There are various types of event, and each one > > has a probability. All probabilities some to One. > > > > So, there are events A,B,C,D... and probabilities > > P(A),P(B),... with Sum[ P(i) ] = 1 > > > > Now, one way to do this totally correctly is as > > follows : > > > > Order the probabilities to cover the interval [0,1] > > So, [0, P(A)] means A [P(A),P(A)+P(B)] means B, etc. > > > > Generate a random float in [0,1] . The interval it > > falls in determines the event that happens. > > > > This is Ok. If the probabilities are constant, you > > can generate a binary tree to search for the interval > > and this can be done in O( log(N) ) where N is the > > number of events. > > > > If you discretize your probabilities to integers you > > can just make buckets and you can do this in O(1), but > > that takes too much memory if you have a lot of events. > > > > Any other brilliant ideas? I don't actually care if > > the method is a bit innacurate as long as it's fast. > > Also, I'll be actually spawning many events per frame, > > so if I could do a bunch at once, that would be ideal. > > > > > >  > > Charles Bloom cbloom@... http://www.cbloom.com > > > > > > > >  > > 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 > > > > > > > >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  Charles Bloom cbloom@... http://www.cbloom.com 
From: <christer_ericson@pl...>  20020913 19:52:06

Charles Bloom wrote: >Yeah, well a binary tree and a sorted array are equivalent >algorithmically; sorted arrays are indeed nice in practice. Note that nowhere did I say anything about sorting an array. Don't confuse the monotonically nondecreasing array produced by the single pass O(n) preprocessing I outlined with some method based on sorting the original array. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: DoRon B. Motter <dmotter@um...>  20020913 19:48:13

A fast, fast method to do this is known as the alias method, check most probability texts for more info. I happen to have a copy of Ross, "Intro to Prob Models" around, so this is essentially his description. The method is the following (1based arrays...). Let P be your distribution of event probabilities (P = n). What you want to do is find n1 other _distributions_, Q(i) so that each distribution Q(i) has at most 2 nonzero components. In addition, you want P = (1/(n1)) Sum( Q(i) ); I will go into how to do that in a sec. But the idea is once you have the Q(i)'s then simulating events from P is efficient. You only need to: 1. Generate a random integer r1 in the range [1..n1] and find Q(r1) 2. Generate random float u1 in [0, 1] 3. Say Q(r1) has nonzero components i(r1) and j(r1) then if(u1 < i(r1)) then use event i else use event j The reason this will work is that you have your original probability distribution written as an equally weighted sum of <=2element probability distributions. So you choose a distribution Q at random (with equal probability) then you can choose from within that probability distribution. Step 3 works since Q(i)'s are distributions. For efficiency you don't really need a new rn in step 2, just use the remainder off your first one, etc. There are other optimizations too, but that is the basic idea. So... how do you get the Q(i)'s? Repeatedly do the following: Find elements i,j from your P (which must always exists) so that P[i] < 1/(n1) and P[i] + P[j] >= 1/(n1) Then your distribution Q will contain all the mass for i in the sense: Q[i] = (n1)P[i] Q[j] = 1  Q[i] Now P is basically like P=1/(n1)Q + (n2)/(n1)P' Where P' is the 'leftover' distribution (it is still a distribution).. Repeat the process on P' to obtain the next Q. Note that P'[i] = 0 so you eliminate an element each time. So you will need at most n1 distributions Q. Then you can use the method above to quickly find events from P. hth DoRon On Fri, 13 Sep 2002, Johnson, James wrote: > > For the dynamic case seems to me a cunning use of a priorty queue fits the > bill. > > James > > Original Message > From: Charles Bloom [mailto:cbloom@...] > Sent: Friday, September 13, 2002 10:58 AM > To: gdalgorithmslist@... > Subject: [Algorithms] efficient random events > > > > I want to efficiently generate random events of this > form : > > I know one event occurs (maybe it was random if it > occurred or not, but at this point, it's going to > occur). > > There are various types of event, and each one > has a probability. All probabilities some to One. > > So, there are events A,B,C,D... and probabilities > P(A),P(B),... with Sum[ P(i) ] = 1 > > Now, one way to do this totally correctly is as > follows : > > Order the probabilities to cover the interval [0,1] > So, [0, P(A)] means A [P(A),P(A)+P(B)] means B, etc. > > Generate a random float in [0,1] . The interval it > falls in determines the event that happens. > > This is Ok. If the probabilities are constant, you > can generate a binary tree to search for the interval > and this can be done in O( log(N) ) where N is the > number of events. > > If you discretize your probabilities to integers you > can just make buckets and you can do this in O(1), but > that takes too much memory if you have a lot of events. > > Any other brilliant ideas? I don't actually care if > the method is a bit innacurate as long as it's fast. > Also, I'll be actually spawning many events per frame, > so if I could do a bunch at once, that would be ideal. > > >  > Charles Bloom cbloom@... http://www.cbloom.com > > > >  > 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: Charles Bloom <cbloom@cb...>  20020913 19:29:10

Yeah, well a binary tree and a sorted array are equivalent algorithmically; sorted arrays are indeed nice in practice. BTW cumulative probability trees are a really popular thing in data compression. This is a nice paper : http://www.cs.auckland.ac.nz/~peterf/ftplink/TechRep110.ps At 11:26 AM 9/13/2002 0700, christer_ericson@... wrote: >You don't need a binary tree for this. Let P[N] be your array >of probabilities (it doesn't have to sum to one if you don't >want to). At preprocessing time, form partial sums for all >elements in P such that P[k] = sum{i=0..k}P[i].  Charles Bloom cbloom@... http://www.cbloom.com 
From: Johnson, James <James.J<ohnson@si...>  20020913 19:00:23

For the dynamic case seems to me a cunning use of a priorty queue fits the bill. James Original Message From: Charles Bloom [mailto:cbloom@...] Sent: Friday, September 13, 2002 10:58 AM To: gdalgorithmslist@... Subject: [Algorithms] efficient random events I want to efficiently generate random events of this form : I know one event occurs (maybe it was random if it occurred or not, but at this point, it's going to occur). There are various types of event, and each one has a probability. All probabilities some to One. So, there are events A,B,C,D... and probabilities P(A),P(B),... with Sum[ P(i) ] = 1 Now, one way to do this totally correctly is as follows : Order the probabilities to cover the interval [0,1] So, [0, P(A)] means A [P(A),P(A)+P(B)] means B, etc. Generate a random float in [0,1] . The interval it falls in determines the event that happens. This is Ok. If the probabilities are constant, you can generate a binary tree to search for the interval and this can be done in O( log(N) ) where N is the number of events. If you discretize your probabilities to integers you can just make buckets and you can do this in O(1), but that takes too much memory if you have a lot of events. Any other brilliant ideas? I don't actually care if the method is a bit innacurate as long as it's fast. Also, I'll be actually spawning many events per frame, so if I could do a bunch at once, that would be ideal.  Charles Bloom cbloom@... http://www.cbloom.com  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: Chris Butcher (BUNGIE) <cbutcher@mi...>  20020913 18:35:12

The best answer depends on the distribution of your events. If the probabilties are roughly evenly distributed then a simple uniform subdivision of the [0,1) range would seem sufficient. Note that you don't have to sacrifice accuracy here necessarily because in each bucket you can store some more complex representation than just 'always A'. You could store two event identifiers and a real determining what fraction of the bucket's range is A and what fraction is B. Of course you can apply any hierarchical technique familiar from spatial subdivision to this as well. My first approach would be to generate 32bit random numbers and break this down in a bytewise fashion, so your hierarchy would be at most 4 levels deep and each level would contain a 256long decision table, each entry in the table pointing to either another table, a single event, or a small structure containing two events and the boundary value between them. I might be solving a different problem than the one you want, though. If you're looking at generating thousands of events with a loose approximation to the desired distribution, and you can pregenerate some amount of data, then you might consider chunking  generate blocks of n events each, and randomly select between m different blocks with equal probability each time you need to get some events back. You can vary the sizes of n and m based on the desired distribution and accuracy, if you feel so inclined.  Chris Butcher Rendering & Simulation Lead Halo 2  Bungie Studios butcher@... =20 Original Message From: Charles Bloom [mailto:cbloom@...]=20 Sent: Friday, September 13, 2002 10:58 To: gdalgorithmslist@... Subject: [Algorithms] efficient random events I want to efficiently generate random events of this form : I know one event occurs (maybe it was random if it occurred or not, but at this point, it's going to occur). There are various types of event, and each one has a probability. All probabilities some to One. So, there are events A,B,C,D... and probabilities P(A),P(B),... with Sum[ P(i) ] =3D 1 Now, one way to do this totally correctly is as follows : Order the probabilities to cover the interval [0,1] So, [0, P(A)] means A [P(A),P(A)+P(B)] means B, etc. Generate a random float in [0,1] . The interval it falls in determines the event that happens. This is Ok. If the probabilities are constant, you can generate a binary tree to search for the interval and this can be done in O( log(N) ) where N is the number of events. If you discretize your probabilities to integers you can just make buckets and you can do this in O(1), but that takes too much memory if you have a lot of events. Any other brilliant ideas? I don't actually care if the method is a bit innacurate as long as it's fast. Also, I'll be actually spawning many events per frame, so if I could do a bunch at once, that would be ideal.  Charles Bloom cbloom@... http://www.cbloom.com  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 
From: <christer_ericson@pl...>  20020913 18:31:24

Charles Bloom wrote: >[...] >So, there are events A,B,C,D... and probabilities >P(A),P(B),... with Sum[ P(i) ] = 1 >[...] >If the probabilities are constant, you >can generate a binary tree to search for the interval >and this can be done in O( log(N) ) where N is the >number of events. Charles, You don't need a binary tree for this. Let P[N] be your array of probabilities (it doesn't have to sum to one if you don't want to). At preprocessing time, form partial sums for all elements in P such that P[k] = sum{i=0..k}P[i]. Now given your random number r (between 0 and P[N1]), you can do a binary search of P to find the 'insertion' position of r in P, that position corresponds to your event. Those with a background in AI will recognize this as the traditional way of implementing the so called 'roulette wheel selection' in genetic algorithms. Christer Ericson Sony Computer Entertainment, Santa Monica 
From: Oscar Cooper <oscar.cooper@cr...>  20020913 18:29:03

log(N) is pretty good already :) If there's a lot of variation in the length of your intervals [P(A),P(A)+P(B)] and you have a very large number of possibilities, then the following scheme may help: First, sort all events by the length of the interval for which they occur. Partition your sorted probability space into a fixed number of buckets, such that if you have B buckets then the event corresponding to random number P lies in bucket floor(B * P), where 0 <= P < 1. You will need to split the intervals for events that cross partition boundaries on a prorata basis, such that the event lies in both partitions without changing the total probability of that event. You search a partition using the same binary algorithm, giving a total complexity O(c + log(M)). The most probable outcomes will lie in the smallest partitions ( ie. M < (N / B) ), so on average you should see a speedup. I assume you've already tried using a binary search on a sorted array, rather than a full on binary tree? Original Message From: Charles Bloom [mailto:cbloom@...] Sent: Friday, September 13, 2002 6:58 PM To: gdalgorithmslist@... Subject: [Algorithms] efficient random events I want to efficiently generate random events of this form : I know one event occurs (maybe it was random if it occurred or not, but at this point, it's going to occur). There are various types of event, and each one has a probability. All probabilities some to One. So, there are events A,B,C,D... and probabilities P(A),P(B),... with Sum[ P(i) ] = 1 Now, one way to do this totally correctly is as follows : Order the probabilities to cover the interval [0,1] So, [0, P(A)] means A [P(A),P(A)+P(B)] means B, etc. Generate a random float in [0,1] . The interval it falls in determines the event that happens. This is Ok. If the probabilities are constant, you can generate a binary tree to search for the interval and this can be done in O( log(N) ) where N is the number of events. If you discretize your probabilities to integers you can just make buckets and you can do this in O(1), but that takes too much memory if you have a lot of events. Any other brilliant ideas? I don't actually care if the method is a bit innacurate as long as it's fast. Also, I'll be actually spawning many events per frame, so if I could do a bunch at once, that would be ideal.  Charles Bloom cbloom@... http://www.cbloom.com  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: Thierry Tremblay <ttremblay@re...>  20020913 18:26:34

Hey all, I just finished implementing the structure of a loose octree. Nodes are allocated as they are needed and destroyed when they are empty. I have objects (spheres) moving in 3D space and the tree is updated as needed. Ok, got this part working. Adding ray casting seems pretty trivial. My question is about collision detection. Asking what objects intersect a given sphere (or point) is easy, but what about detecting all the colliding pairs between the objects in the tree? I couldn't find anything on the net... With a normal octree: for a given object in a given node, I would have to check against objects in the same node and in the child nodes. But with loose octrees, there are many other nodes overlapping the one where the object under consideration is. So I am a little confused as how to proceed from this point. There is also efficiency concerns such as not testing a given pair of objects twice. Keeping a list of already tested pairs could work, but don't seem optimal. As always, thanks for any help you can provide. Thierry 
From: Charles Bloom <cbloom@cb...>  20020913 17:58:41

I want to efficiently generate random events of this form : I know one event occurs (maybe it was random if it occurred or not, but at this point, it's going to occur). There are various types of event, and each one has a probability. All probabilities some to One. So, there are events A,B,C,D... and probabilities P(A),P(B),... with Sum[ P(i) ] = 1 Now, one way to do this totally correctly is as follows : Order the probabilities to cover the interval [0,1] So, [0, P(A)] means A [P(A),P(A)+P(B)] means B, etc. Generate a random float in [0,1] . The interval it falls in determines the event that happens. This is Ok. If the probabilities are constant, you can generate a binary tree to search for the interval and this can be done in O( log(N) ) where N is the number of events. If you discretize your probabilities to integers you can just make buckets and you can do this in O(1), but that takes too much memory if you have a lot of events. Any other brilliant ideas? I don't actually care if the method is a bit innacurate as long as it's fast. Also, I'll be actually spawning many events per frame, so if I could do a bunch at once, that would be ideal.  Charles Bloom cbloom@... http://www.cbloom.com 
From: Jamie Fowlston <jamief@qu...>  20020913 17:12:00

well, this is just a case of picking an appropriate level for your interface abstraction, just like with meshes et al. at a low level, we render each character as a separate quad. but at the public API level, strings are passed in whole, so the positioning, etc., of each character does depend on adjacent characters, and we do get all the benefits of a good font, etc. there's no reason that how you render your characters should be linked to the formatting of the strings they're in. jamie Original Message From: Jon Watte [mailto:hplus@...] Sent: 13 September 2002 17:58 To: Jamie Fowlston; Jonathan Perret; gdalgorithmslist@... Subject: RE: [Algorithms] Next generation GUI. > we render font to texture, use quad per character. platform > independent, we > have it working on linux, win32, freebsd, xbox, ps2.... I guess my point is more that you get better results when you render whole words (or the whole actual text) rather than rendering just individual characters. The reason for this is that (good) fonts and font renderers can (and do) make decisions about things like kerning and ligatures, which you cannot do when you just render a single character. (There's also the esoteric phenomenon of stochastic fonts, if you're way into typesetting land) If your font is Courier New or Lucida Typewriter, then there probably won't be a difference, though :) Whether you render with GDI, FreeType, QuickDraw or something else is probably more a matter of what your target platform(s) is/are. As you say, some libraries are more portable than others. Cheers, / h+ Did prepress in a previous life 
From: Jon Watte <hplus@mi...>  20020913 17:00:13

> we render font to texture, use quad per character. platform > independent, we > have it working on linux, win32, freebsd, xbox, ps2.... I guess my point is more that you get better results when you render whole words (or the whole actual text) rather than rendering just individual characters. The reason for this is that (good) fonts and font renderers can (and do) make decisions about things like kerning and ligatures, which you cannot do when you just render a single character. (There's also the esoteric phenomenon of stochastic fonts, if you're way into typesetting land) If your font is Courier New or Lucida Typewriter, then there probably won't be a difference, though :) Whether you render with GDI, FreeType, QuickDraw or something else is probably more a matter of what your target platform(s) is/are. As you say, some libraries are more portable than others. Cheers, / h+ Did prepress in a previous life 
From: Odin Jensen <odin@nu...>  20020913 14:06:47

At 09:53 13092002 0400, you wrote: >We're using an AABB tree for our static world, but the algorithm is >pretty similar. I can't think of any obvious reasons of why the test >would fail, except there's probably some simple bug somewhere :) >You're just using a normal ray right? It's not actually a lineswept >sphere? And I assume when you say "Ray in current bounding box" you >mean it intersects the bounding box and not necessarily totally inside >the bounding box, correct? Yes. I found the bug. I bailed out at first child intersection, while another child might actually hold a closer intersection. It works now, but I'll definately be looking into AABB trees instead. Thanks all for your input. I suspected the bug, but I just recently got proof for it :) Odin 
From: Odin Jensen <odin@nu...>  20020913 13:52:04

>In what way does it fail? It hits the incorrect triangle or misses? It misses. >"If we have children, loop through all these and return true on first >collision. return false if none of them had a collision." >Is it possible there's a closer collision in another child? That was what I was thinking. I'll have to look deeper into that. What are you guys doing for your octree collision tests? (I know it can be optimized with BSP's, AABox trees etc. but I just want to get the basics working here :) Thanks Odin 
From: Jeremiah Zanin <jeremiah@ou...>  20020913 13:11:39

In what way does it fail? It hits the incorrect triangle or misses? "If we have children, loop through all these and return true on first collision. return false if none of them had a collision." Is it possible there's a closer collision in another child? 
From: Jamie Fowlston <jamief@qu...>  20020913 10:24:58

could be this: there's an overlap between adjacent cells. so when you enter an overlapping volume, you need to consider the contributions that could come from all the cells that overlap the volume. you might be doing this, but it's not clear from your post :) jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Odin Jensen Sent: 13 September 2002 10:30 To: gdalgorithmslist@... Subject: [Algorithms] Ray cast failing on octree nodes edges Hi. Yet another octree question, but I'm getting better at it all the time, with the aid of you guys :) I have the apparent problem, that my raycast collision fails at odd times. I.e. works in most places, fails in some other places. Appears to fail on octree boundaries, suggesting it might be my duplicate polys messing with my code again. (I'm working to fix this ASAP :) My (recursive) algorithm works as follows Start at top node ofcourse. Ray in current bounding box? If (no) return false for no collision. If (yes) If we have children, loop through all these and return true on first collision. return false if none of them had a collision. If we didn't have children, loop through all triangles performing a ray plane test. If it succeeds, save distance between first point and intersection point + intersection point. I do this for all triangles, only keeping the smallest distance found. After this loop, return true if a collision was found, otherwise false. I've tried to add the closest point to triangle test too, but with little success. Thanks Odin  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: Jamie Fowlston <jamief@qu...>  20020913 09:55:42

we get all those things using freetype (http://www.freetype.org/) we render font to texture, use quad per character. platform independent, we have it working on linux, win32, freebsd, xbox, ps2.... jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Jon Watte Sent: 12 September 2002 18:44 To: Jonathan Perret; gdalgorithmslist@... Subject: RE: [Algorithms] Next generation GUI. > Rendering text fast enough is hard when you use 1 quad/character. > Is anybody doing the following : softrender each block of text to > a texture, upload it and render that ? Would it work ? I do this. It works great! I get the benefit of Windows GDI TrueType goodness (with antialiasing) and it uploads pretty quick when it actually changes (which is very seldom). Just make sure to select your font object into a screen device context before you select it into your offscreen device context, or you won't get the anti aliasing. (Gotta love Win32) Note that when you use GDI for rendering, you get all kinds of nice kerning and layout goodness which is neigh impossible to get using a regular "quads from a texture" "font". Cheers, / h+  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: Gareth Lewin <GL<ewin@cl...>  20020913 09:44:17

Try to imaging what a Sphere map is. It is basically a fisheye view with a 180 degree lens of the scene from a certain point. OT: I know that max can autogenerate cube maps for you, maybe it can generate sphere maps too ? > Original Message > From: Nguyen Binh [mailto:ngbinh@...] > Sent: 13 September 2002 08:34 > To: GdalgorithmsList > Subject: [Algorithms] Sphere map generation. Please help!!! > > > Hi list, > > Is there any other way to create nice looking sphere map texture > beside using ID3DXRenderToEnvMap? > > I'm trying to write a 3DSMax plugin to create Sphere map but I > don't really know the "math" of Sphere map. > > Thanks very much, > >  > Best regards, > >  > Nguyen Binh > Software Engineer > Glass Egg Digital Media > Me Linh Point Tower, 10th Floor > 2 Ngo Duc Ke > District 1, Ho Chi Minh City > Vietnam > Phone:(84.8)8238395 > Fax: (84.8)8238392 > http://www.glassegg.com >  > > > > >  > 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: Odin Jensen <odin@nu...>  20020913 09:29:12

Hi. Yet another octree question, but I'm getting better at it all the time, with the aid of you guys :) I have the apparent problem, that my raycast collision fails at odd times. I.e. works in most places, fails in some other places. Appears to fail on octree boundaries, suggesting it might be my duplicate polys messing with my code again. (I'm working to fix this ASAP :) My (recursive) algorithm works as follows Start at top node ofcourse. Ray in current bounding box? If (no) return false for no collision. If (yes) If we have children, loop through all these and return true on first collision. return false if none of them had a collision. If we didn't have children, loop through all triangles performing a ray plane test. If it succeeds, save distance between first point and intersection point + intersection point. I do this for all triangles, only keeping the smallest distance found. After this loop, return true if a collision was found, otherwise false. I've tried to add the closest point to triangle test too, but with little success. Thanks Odin 
From: Lorenzo Pastrana <pastrana@ul...>  20020913 08:56:41

It seemed obvius at the time I wrote but now it looks like im talking about tk May be I could have mentionned that the rendering is done in OpenGL and the default skin looks like MacOS X... Lo. > > There is a pretty good lgpl project on sf called NGL, they have a thing > called NUI witch takes all this stuff (TrueType, Unicode, Skins, Messaging > and Widgettry) quite seriously, and multiplateform, s'il vous plait! (no > consoles yet though :) > > Definietly worth a try : > > http://ngl.sf.net/ > Source is available on cvs. > > Lo. > 
From: Nguyen Binh <ngbinh@gl...>  20020913 07:38:47

Hi list, Is there any other way to create nice looking sphere map texture beside using ID3DXRenderToEnvMap? I'm trying to write a 3DSMax plugin to create Sphere map but I don't really know the "math" of Sphere map. Thanks very much,  Best regards,  Nguyen Binh Software Engineer Glass Egg Digital Media Me Linh Point Tower, 10th Floor 2 Ngo Duc Ke District 1, Ho Chi Minh City Vietnam Phone:(84.8)8238395 Fax: (84.8)8238392 http://www.glassegg.com  
From: Marin Kovacic <m.kovacic@in...>  20020913 06:15:44

> When a VIPM mesh decimates and a vert along a texture > boundary is chosen for removal then you could get a 'hole' > appearing in the mesh. My memory was vague but I think > I remember the two options here were to : > Don't decimate the edges (Which could seriously limit > how far down an object can scale. > Some funky scheme to use 3d flanges to cover up the holes. 3. only allow boundary>boundary collapses, but not boundary>interior (interior>boundary is also fine, obviously). You also need to make the edge on the other "side" of the boundary collapse in the same step. Furthermore, if two boundary edges that have the vertex you are collapsing "form a concave angle" (terminology?) in UV space you need to disallow it too. Any other cases (we've never had any) are probably rare and can be fixed manually by the artists (with collapse weights). 
From: Stefan Maton <metron@sk...>  20020913 05:56:06

In fact, it was a general question since it reduced it down to this (I think I didn't explain it as it should have been explained (Guillaume was quite near but didn't hit the target ;) ): I have an interface that is a common shader interface. I wanted this interface because I do not want to mirror into the application which pipeline is used to render a given set of primitives. The data tells the renderer what pipe to use. If there's a vertex shader defined (refered to or whatever) within the dataset of the mesh, the programmable pipe is used. If no such shader is defined, the hardwired pipe should be used. So the interface that is handed out to the application is : class IShader { public: virtual bool UseShader() = 0; } Now, the engine internal implementation of this interface must know the difference. I came to this conclusion after a more or less sleeples night ;) Why does it have to implement the difference between the two pipes ? Because they are declared in different ways. While the programmable pipe takes a shader code (usually a string or precompiled code), the hardwired pipe takes a 'declarator' consisting of a bunch of ulongs (dwords) describing the way, the hardwired pipe has to be set up. class IFixedPipe : public IShader { public: virtual bool SetFixedPipeShaderDesc( ulong* Declarator, int Size ) = 0; } and class IProgrammablePipe : public IShader { public: virtual bool SetProgrammablePipeShaderDesc( const char* pszShaderCode ) = 0; } So, finally the question came down to : How do you design your class interfaces within your engine to easily switch between the hardwired and the programmable pipeline without making heavy changements within your application code ? Kind regards, Stefan PS: Sorry that the discussion drifted away... I'm on the DirectX List but I thought the question itself was not API targeted. > Message d'origine > De : gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]De la part de > Brian Hook > Envoye : jeudi 12 septembre 2002 20:49 > A : 'Algorithms' > Objet : RE: [Algorithms] Fixed function and other shaders > > > Dammit, two list cop posts in one day. > > We originally didn't want to say anything about this thread since it > could have been fairly API agnostic to begin with, i.e. more of a > design/architectural question than an implementation issue. So to avoid > being fascist, we let it slide =) > > But it's now pretty clearly into DirectX terrain. There is a very good > DirectX mailing list available here: > > http://DISCUSS.MICROSOFT.COM/archives/DIRECTXDEV.html > > Thanks, > > The Admins > > > > >  > 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: Lorenzo Pastrana <pastrana@ul...>  20020913 04:30:17

There is a pretty good lgpl project on sf called NGL, they have a thing called NUI witch takes all this stuff (TrueType, Unicode, Skins, Messaging and Widgettry) quite seriously, and multiplateform, s'il vous plait! (no consoles yet though :) Definietly worth a try : http://ngl.sf.net/ Source is available on cvs. Lo. > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Jon > Watte > Sent: jeudi 12 septembre 2002 19:44 > To: Jonathan Perret; gdalgorithmslist@... > Subject: RE: [Algorithms] Next generation GUI. > > > > > Rendering text fast enough is hard when you use 1 quad/character. > > Is anybody doing the following : softrender each block of text to > > a texture, upload it and render that ? Would it work ? > > I do this. It works great! I get the benefit of Windows GDI TrueType > goodness (with antialiasing) and it uploads pretty quick when it > actually changes (which is very seldom). Just make sure to select > your font object into a screen device context before you select it > into your offscreen device context, or you won't get the anti > aliasing. (Gotta love Win32) > > Note that when you use GDI for rendering, you get all kinds of nice > kerning and layout goodness which is neigh impossible to get using a > regular "quads from a texture" "font". > > Cheers, > > / h+ > > > >  > 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 > 