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
(13) 
2
(15) 
3
(54) 
4
(51) 
5
(10) 
6
(2) 
7
(25) 
8
(25) 
9
(19) 
10
(18) 
11
(25) 
12
(9) 
13
(7) 
14
(20) 
15
(55) 
16
(35) 
17
(34) 
18
(23) 
19
(8) 
20
(5) 
21
(19) 
22
(16) 
23
(5) 
24
(19) 
25
(39) 
26
(11) 
27
(4) 
28
(7) 
29
(16) 
30
(35) 



From: Jon Watte <hplus@mi...>  20030418 21:34:12

> Why in the world would you care so much about invariance? If the=20 > points are so close together that you're snapping them, why does=20 > it matter if you snap them to exactly the same spot or not? =20 Suppose you want to match up more than one item, i e you have some=20 kind of multiitem layout tool, and you don't want cracking between=20 the items. Of course, you have to contend with other things, such as making=20 sure the modelview matrices are the same, that they all get=20 quantized to the same position, etc. My opinion is that this can=20 only realistically be done if you export in some 90degreeangle=20 identity orientation, and quantize to known, fixed bins (we use=20 "millimeters"). Cheers, / h+ 
From: Chris Butcher \(BUNGIE\) <cbutcher@mi...>  20030418 21:20:07

> Original Message > From: gdalgorithmslistadmin@... [mailto:gdalgorithms > listadmin@...] On Behalf Of Charles Bloom > Sent: Friday, April 18, 2003 1:46 PM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] merging of points in 3D space [bcc][fake adr] >=20 > Why in the world would you care so much about invariance? If the points > are so close together that you're snapping them, why does it matter if you > snap them to exactly the same spot or not? Seems very odd to me. > Certainly reproducability is nice for making sure you don't have any odd > bugs, but doesn't seem important in real usage. >=20 > Snapping like this should only be done for tiny tiny tolerances, eg. > points that the artists intended to be on top of each other but failed to > connect because the art packages just suck. If you're using big > tolerances, should be doing a PM simplify instead. A PM Simplify will > properly sort the operations by error metric, be SRT invariant, preserve > topology, etc. >=20 Invariance is important to us because we have a BSPdriven world builder that is extremely sensitive to the precise details of points and planes. If an artist has a space that builds into a BSP in one orientation, they want it to build the same in another orientation. We had serious issues with our previous point welding system that was based on three axis sweeps, because geometry that wasn't aligned to the axes of the world coordinate system would end up welding differently. Note that the issue isn't whether points welded or not  that is, as you say, a boolean decision and very unlikely to change under rotation. The issue is how the points separate into groups, and what the position of the postwelded points are. We quite frequently have groups of points that cluster loosely and span multiple weld epsilons. If they welded into groups in a significantly different way under rotation, then that would change the weights that we apply to those point groups when trying to build BSP planes, and basically you can get a situation where small differences can cascade through the system and cause geometry not to import successfully.  Chris Butcher Rendering & Simulation Lead Halo 2  Bungie Studios butcher@... 
From: Charles Bloom <cbloom@cb...>  20030418 20:46:52

At 01:13 PM 4/18/2003 0700, you wrote: > We wanted to take the approach that all of our geometry operations >should be rotationally invariant, because we had a bunch of problems in >Halo 1 where an object would import differently (i.e. incorrectly) if >the artist rotated it by some non90 degree angle. Why in the world would you care so much about invariance? If the points are so close together that you're snapping them, why does it matter if you snap them to exactly the same spot or not? Seems very odd to me. Certainly reproducability is nice for making sure you don't have any odd bugs, but doesn't seem important in real usage. Snapping like this should only be done for tiny tiny tolerances, eg. points that the artists intended to be on top of each other but failed to connect because the art packages just suck. If you're using big tolerances, should be doing a PM simplify instead. A PM Simplify will properly sort the operations by error metric, be SRT invariant, preserve topology, etc.  Charles Bloom cb@... http://www.cbloom.com 
From: Chris Butcher \(BUNGIE\) <cbutcher@mi...>  20030418 20:14:03

> Original Message > From: gdalgorithmslistadmin@... [mailto:gdalgorithms > listadmin@...] On Behalf Of Gareth Lewin > Sent: Friday, April 18, 2003 9:27 AM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] merging of points in 3D space [bcc][fake adr] >=20 > Really ? >=20 > Would >=20 > [0, 0, 0.000] > [0, 0, 0.005] > [0, 0, 0.010] >=20 > be all that bad ? >=20 I don't know if that would be bad or not, it certainly sounds plausible. Everything depends on your problem domain. We wanted to take the approach that all of our geometry operations should be rotationally invariant, because we had a bunch of problems in Halo 1 where an object would import differently (i.e. incorrectly) if the artist rotated it by some non90 degree angle. So if you consider an algorithm that's taking a series of evenly spaced points along a line, you don't want the output points to be skewed in either direction along the line. For example (still with an epsilon of 0.005): [0, 0, 0.000] [0, 0, 0.004] [0, 0, 0.008] I believe there are only two correct answers here: [0, 0, 0.004] or [0, 0, 0.002] [0, 0, 0.006]  Chris Butcher Rendering & Simulation Lead Halo 2  Bungie Studios butcher@... 
From: Chris Butcher \(BUNGIE\) <cbutcher@mi...>  20030418 19:49:47

From: Charles Bloom <cbloom@cb...>  20030418 19:34:15

There's code for this in Galaxy. At 09:57 AM 4/18/2003 0700, Jon Watte wrote: > >> 1.000 1.000 1.000 >> 0.999 1.001 1.000 >> 1.000 1.002 0.989 etc > > >Either sort by one axis, and then walk the list, merging points >that are close enough (you only need to look a certain distance >ahead in the list to find matches). This is vaguely N*sqrt(N) in >runtime, assuming number of neighbors you need to consider >grows as root of total number of verts. > >Or round/quantize all points to even multiples of your weld >distance (typically, convert them all to shorts with the >appropriate scaling factor), and use a hash table to find >matches as you insert into the table. This is N runtime, in the >same sense as hashing is N in runtime. >  Charles Bloom cb@... http://www.cbloom.com 
From: Jon Watte <hplus@mi...>  20030418 16:59:04

> 1.000 1.000 1.000 > 0.999 1.001 1.000 > 1.000 1.002 0.989 etc Either sort by one axis, and then walk the list, merging points=20 that are close enough (you only need to look a certain distance=20 ahead in the list to find matches). This is vaguely N*sqrt(N) in=20 runtime, assuming number of neighbors you need to consider=20 grows as root of total number of verts. Or round/quantize all points to even multiples of your weld=20 distance (typically, convert them all to shorts with the=20 appropriate scaling factor), and use a hash table to find=20 matches as you insert into the table. This is N runtime, in the=20 same sense as hashing is N in runtime. Cheers, / h+ 
From: Doug Rogers <DRogers@nv...>  20030418 16:58:20

You can also use a kd tree do to pairwise nearest neighbor. Doug Original Message From: Doug Rogers Sent: Friday, April 18, 2003 9:38 AM To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] merging of points in 3D space Here is a general outline of what I do Create a list with pair entries d = x*x+y*y+z*z pair(d, point index) sort the list by d This gives you each point sorted by the distance to (0,0,0) starting at the first entry in the list d0 = first entry d look at the next entries in the list n(d) = next entry n if (abs(n(d)  d0) < threshold kill n(index) next entry Doug Original Message From: Peter Szinek [mailto:szyp@...] Sent: Friday, April 18, 2003 2:26 AM To: gdalgorithmslist@... Subject: [Algorithms] merging of points in 3D space Hello all, I am having the following problem: Consider an array of points in 3D given by (x, y, z). Every point is in the array more times (56 times, does not really matter) but the problem is that these points are not really the same  there are small differences between their coordinates e.g. points with coordinates 1.000 1.000 1.000 0.999 1.001 1.000 1.000 1.002 0.989 etc are considered to represent the same point. Now, my question is, how to 'merge' these points into one (e.g. in the previous example, keep only one such point) _VERY_ fast. The trivial algorithm is farfar away (as usual) from the fast enough. Any help appreciated.  Best regards, Peter mailto:szyp@...  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: Alen Ladavac <alen@cr...>  20030418 16:41:38

RE: [Algorithms] merging of points in 3D space [bcc][fake adr]I don't = actually get why would floodfilling up to 3*epsilon result in points = that are 2*epsilon apart, perhaps you should explain the algorithm in = more detail.=20 That note aside, I still don't see why would the limiting rule make it = be order independent? IMO, only floodfilling _without_ limiting, end = then using either a minimum point, or centroid, or similar would be = order independent. Or, am I missing something? Alen  Original Message =20 From: Chris Butcher (BUNGIE)=20 To: gdalgorithmslist@...=20 Sent: Friday, April 18, 2003 3:21 PM Subject: RE: [Algorithms] merging of points in 3D space [bcc][fake = adr] Even with a perfect spatial search algorithm, that's only half of the = problem. The really hard problem (IMHO) is deciding what merging points = really means. For example, if your epsilon is 0.005, what do you do with = this case? [0, 0, 0.000] [0, 0, 0.001] [0, 0, 0.002] [0, 0, 0.003] ... [0, 0, 0.998] [0, 0, 0.999] [0, 0, 1.000] My assertion is that you want to end up with points that look like = this: [0, 0, 0.005] [0, 0, 0.015] [0, 0, 0.025] ... [0, 0, 0.985] [0, 0, 0.995] We use an approach that tries to build connected neighbourhoods by = floodfilling from one point to another if they're within epsilon of = each other, but which will at no time grow a neighbourhood to be greater = than 3*epsilon in any coordinate axis. Be very wary of using a greedy algorithm that is = submissionorderdependent. If your artists are exporting from MAX or = something and they don't move points around in one area of their model, = they will definitely not expect those points to get welded differently = (potentially causing further errors down the line) just because = something else in the file changed.  Chris Butcher Rendering & Simulation Lead Halo 2  Bungie Studios butcher@... Original Message From: gdalgorithmslistadmin@... = [mailto:gdalgorithmslistadmin@...] On Behalf Of = Gribb, Gil Sent: Friday, April 18, 2003 6:12 AM To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] merging of points in 3D space [bcc][fake = adr] This ordering is not strong enough to sort on, in particular it isn't = transitive...some counter example points (e=3DEPSILON): A=3D(.5e,2e,0)=20 B=3D(0,6e,0)=20 C=3D(1.1e,0,0)=20 A<B and B<C but A > C=20 You don't really know what qsort is going to produce with this = predicate.=20 Often times just sorting on X and an appropriate search will be fast = enough in practice. Bin approaches can be better than that. Both of = these have bad worst case behavior. The theoretically satisfactory = algorithms are the same spatial search algorithms used for collision. Gil=20 Here is what I use:=20 1) Do a qsort() on the array, using a weak lexicografic ordering as=20 comparison function. I.e.=20 if (x0x1 < EPSILON) return 1;=20 else if (x0x1 > +EPSILON) return 1;=20 else if (y0y1 < EPSILON) return 1;=20 else if (y0y1 > +EPSILON) return 1;=20 else if (z0z1 < EPSILON) return 1;=20 else if (z0z1 > +EPSILON) return 1;=20 else return 0;=20 (This procedure is O(n log n).)=20 2) Then do a linear walk over the array comparing neighbors again and=20 eliminating those that are "equal", by the same comparison function. = (This=20 procedure is O(n).)=20 The expected overal performance should be bounded by O(n log n).=20 HTH,=20 Alen=20  Original Message =20 From: "Peter Szinek" <szyp@...>=20 To: <gdalgorithmslist@...>=20 Sent: Friday, April 18, 2003 9:25 AM=20 Subject: [Algorithms] merging of points in 3D space=20 > Hello all,=20 >=20 > I am having the following problem:=20 >=20 > Consider an array of points in 3D given by (x, y, z). Every point is = in=20 the=20 > array more times (56 times, does not really matter) but the problem = is=20 that=20 > these points are not really the same  there are small differences = between=20 their=20 > coordinates=20 > e.g. points with coordinates=20 >=20 > 1.000 1.000 1.000=20 > 0.999 1.001 1.000=20 > 1.000 1.002 0.989 etc=20 >=20 > are considered to represent the same point.=20 >=20 > Now, my question is, how to 'merge' these points into one (e.g. in = the=20 previous=20 > example, keep only one such point) _VERY_ fast. The trivial = algorithm is=20 farfar=20 > away (as usual) from the fast enough.=20 >=20 > Any help appreciated.=20 >=20 >=20 >=20 >=20 >=20 > =20 > Best regards,=20 > Peter mailto:szyp@...=20 >=20 >=20 >=20 > =20 > This sf.net email is sponsored by:ThinkGeek=20 > Welcome to geek heaven.=20 > http://thinkgeek.com/sf=20 > _______________________________________________=20 > GDAlgorithmslist mailing list=20 > GDAlgorithmslist@...=20 > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist=20 > Archives:=20 > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188=20 >=20 =20 This sf.net email is sponsored by:ThinkGeek=20 Welcome to geek heaven.=20 http://thinkgeek.com/sf=20 _______________________________________________=20 GDAlgorithmslist mailing list=20 GDAlgorithmslist@...=20 https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist=20 Archives:=20 http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188=20 
From: Doug Rogers <DRogers@nv...>  20030418 16:38:13

Here is a general outline of what I do Create a list with pair entries d = x*x+y*y+z*z pair(d, point index) sort the list by d This gives you each point sorted by the distance to (0,0,0) starting at the first entry in the list d0 = first entry d look at the next entries in the list n(d) = next entry n if (abs(n(d)  d0) < threshold kill n(index) next entry Doug Original Message From: Peter Szinek [mailto:szyp@...] Sent: Friday, April 18, 2003 2:26 AM To: gdalgorithmslist@... Subject: [Algorithms] merging of points in 3D space Hello all, I am having the following problem: Consider an array of points in 3D given by (x, y, z). Every point is in the array more times (56 times, does not really matter) but the problem is that these points are not really the same  there are small differences between their coordinates e.g. points with coordinates 1.000 1.000 1.000 0.999 1.001 1.000 1.000 1.002 0.989 etc are considered to represent the same point. Now, my question is, how to 'merge' these points into one (e.g. in the previous example, keep only one such point) _VERY_ fast. The trivial algorithm is farfar away (as usual) from the fast enough. Any help appreciated.  Best regards, Peter mailto:szyp@...  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: Alen Ladavac <alen@cr...>  20030418 16:27:17

RE: [Algorithms] merging of points in 3D space [bcc][fake adr]The = critique is well placed since, mathematically speaking, you should not = use a nontransitive relation as a sort criterion.=20 It all depends on whether you need some specific results, or just want = quick reduction. The method I suggested will not produce the same results as the trivial = algorithm, if the points (when projected to some axis) are allowed to = create small subsets where each point is near to at least one another, = but not to all of the points in the subset. But let's look at some other effects of having coordinates that are very = near, but not within epsilon, in the input set. If you happen to have = points with x coordinates of 0.5e, 0 and 1.1e, it might just as well = happen that they have same y and z (not different as in Gil's counter = example). So, you might have points: A=3D(0.5e,0,0)=20 B=3D(0,0,0)=20 C=3D(1.1e,0,0)=20 In such case even the trivial algorithm (comparing all pairs of points) = is illdefined as well. Depending on the order in which the points are = processed, the result might be one point. And in case that you get two = points (B and C), repeated applying of same (or even any other) = algorithm is not going to merge them. This gets us to the question: if the point A doesn't exist, but the = points B and C do, should they be merged then? Having such case suggests that the epsilon is too low. (Once you start = using epsilons in some part of code, you better be prepared for some = tweaking.) On a side note, you might want to preprocess all vertices by snapping = them to the epsilonsized grid. Then you can use the complete lexical = ordering (as if epsilon=3D0). This way you can guarantee that the result = will be independent of the vertex ordering, but again, B and C would not = be joined in that case. Perhaps that is desired, perhaps not. Cheers, Alen  Original Message =20 From: Gribb, Gil=20 To: 'gdalgorithmslist@...'=20 Sent: Friday, April 18, 2003 1:11 PM Subject: RE: [Algorithms] merging of points in 3D space [bcc][fake = adr] This ordering is not strong enough to sort on, in particular it isn't = transitive...some counter example points (e=3DEPSILON): A=3D(.5e,2e,0)=20 B=3D(0,6e,0)=20 C=3D(1.1e,0,0)=20 A<B and B<C but A > C=20 You don't really know what qsort is going to produce with this = predicate.=20 Often times just sorting on X and an appropriate search will be fast = enough in practice. Bin approaches can be better than that. Both of = these have bad worst case behavior. The theoretically satisfactory = algorithms are the same spatial search algorithms used for collision. Gil=20 Here is what I use:=20 1) Do a qsort() on the array, using a weak lexicografic ordering as=20 comparison function. I.e.=20 if (x0x1 < EPSILON) return 1;=20 else if (x0x1 > +EPSILON) return 1;=20 else if (y0y1 < EPSILON) return 1;=20 else if (y0y1 > +EPSILON) return 1;=20 else if (z0z1 < EPSILON) return 1;=20 else if (z0z1 > +EPSILON) return 1;=20 else return 0;=20 (This procedure is O(n log n).)=20 2) Then do a linear walk over the array comparing neighbors again and=20 eliminating those that are "equal", by the same comparison function. = (This=20 procedure is O(n).)=20 The expected overal performance should be bounded by O(n log n).=20 HTH,=20 Alen=20  Original Message =20 From: "Peter Szinek" <szyp@...>=20 To: <gdalgorithmslist@...>=20 Sent: Friday, April 18, 2003 9:25 AM=20 Subject: [Algorithms] merging of points in 3D space=20 > Hello all,=20 >=20 > I am having the following problem:=20 >=20 > Consider an array of points in 3D given by (x, y, z). Every point is = in=20 the=20 > array more times (56 times, does not really matter) but the problem = is=20 that=20 > these points are not really the same  there are small differences = between=20 their=20 > coordinates=20 > e.g. points with coordinates=20 >=20 > 1.000 1.000 1.000=20 > 0.999 1.001 1.000=20 > 1.000 1.002 0.989 etc=20 >=20 > are considered to represent the same point.=20 >=20 > Now, my question is, how to 'merge' these points into one (e.g. in = the=20 previous=20 > example, keep only one such point) _VERY_ fast. The trivial = algorithm is=20 farfar=20 > away (as usual) from the fast enough.=20 >=20 > Any help appreciated.=20 >=20 >=20 >=20 >=20 >=20 > =20 > Best regards,=20 > Peter mailto:szyp@...=20 >=20 >=20 >=20 > =20 > This sf.net email is sponsored by:ThinkGeek=20 > Welcome to geek heaven.=20 > http://thinkgeek.com/sf=20 > _______________________________________________=20 > GDAlgorithmslist mailing list=20 > GDAlgorithmslist@...=20 > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist=20 > Archives:=20 > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188=20 >=20 =20 This sf.net email is sponsored by:ThinkGeek=20 Welcome to geek heaven.=20 http://thinkgeek.com/sf=20 _______________________________________________=20 GDAlgorithmslist mailing list=20 GDAlgorithmslist@...=20 https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist=20 Archives:=20 http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188=20 
From: Gareth Lewin <GLewin@cl...>  20030418 16:27:12

Hmm, whenever I contradict people like Chris or Tom I always know I'm wrong, but just in case... > Original Message > From: Chris Butcher (BUNGIE) [mailto:cbutcher@...] > Even with a perfect spatial search algorithm, that's only > half of the problem. The really hard problem (IMHO) is > deciding what merging points really means. For example, if > your epsilon is 0.005, what do you do with this case? > > [0, 0, 0.000] > [0, 0, 0.001] > [0, 0, 0.002] > [0, 0, 0.003] > ... > [0, 0, 0.998] > [0, 0, 0.999] > [0, 0, 1.000] > > My assertion is that you want to end up with points that look > like this: > > [0, 0, 0.005] > [0, 0, 0.015] > [0, 0, 0.025] > ... > [0, 0, 0.985] > [0, 0, 0.995] > Really ? Would [0, 0, 0.000] [0, 0, 0.005] [0, 0, 0.010] be all that bad ? _______________________ Regards, Gareth Lewin Programmer, Climax Solent. (To anyone outside Climax, sorry for the disclaimer below) DISCLAIMER: Unless otherwise expressly stated, this message does not create or vary any contractual relationship between you and Climax Development Ltd. The contents of this email may be confidential and if you have received it in error, please delete it from your system, destroy any hard copies and contact the originator of the email. In accordance with the Telecommunications (Lawful Business Regulations) (Interception of Communications) Regulations 2000 the Company reserves the right and, may at any time, monitor and intercept (but not record) emails to establish if they are relevant to its business. 
From: Gareth Lewin <GLewin@cl...>  20030418 16:16:48

> Of course, you could make that *much* faster by writing > > if (distance_between_squared (p1,p2) < 0.001 * 0.001) > // or whatever you want the > epsilon to be > > > avoiding the square root :) Sorry, I meant to write psuedo code, it was an algorithm not a lowlevel example on how to solve the problem. _______________________ Regards, Gareth Lewin Programmer, Climax Solent. (To anyone outside Climax, sorry for the disclaimer below) DISCLAIMER: Unless otherwise expressly stated, this message does not create or vary any contractual relationship between you and Climax Development Ltd. The contents of this email may be confidential and if you have received it in error, please delete it from your system, destroy any hard copies and contact the originator of the email. In accordance with the Telecommunications (Lawful Business Regulations) (Interception of Communications) Regulations 2000 the Company reserves the right and, may at any time, monitor and intercept (but not record) emails to establish if they are relevant to its business. 
From: Gareth Lewin <GLewin@cl...>  20030418 16:15:18

> > I think this is the "trivial algorithm" Peter was originally > referring to :) > Shame on me! I missed that part. Ok here goes. Got this idea from Pierre. Push your points thru your collision engine. Set a sphere around each point and merge all colliding vertices. Another option is to sort by just a single axis ( Say the x ) and the run "the trivial" algorithm on blocks. So run it on every 10 verts steping only 1 forward So test 0..10 against each other then 1..11 etc. _______________________ Regards, Gareth Lewin Programmer, Climax Solent. (To anyone outside Climax, sorry for the disclaimer below) DISCLAIMER: Unless otherwise expressly stated, this message does not create or vary any contractual relationship between you and Climax Development Ltd. The contents of this email may be confidential and if you have received it in error, please delete it from your system, destroy any hard copies and contact the originator of the email. In accordance with the Telecommunications (Lawful Business Regulations) (Interception of Communications) Regulations 2000 the Company reserves the right and, may at any time, monitor and intercept (but not record) emails to establish if they are relevant to its business. 
From: Chris Butcher \(BUNGIE\) <cbutcher@mi...>  20030418 16:08:27

From: Nalin Savara <nsavara@vs...>  20030418 13:22:32

This tutorial demonstrates something like that; with java applets however. Using a separate thread to lock onto a fixed frame rate. http://www.1javastreet.com/vb/scripts/ShowCode.asp?txtCodeId=3270&lngWId=2 Regards, Nalin Savara  Original Message  From: "Sin Chian" <sin@...> To: <gdalgorithmslist@...> Sent: Friday, April 18, 2003 5:00 AM Subject: Re: [Algorithms] update game with constant interval > >  Original Message  > From: "Jones, Chris" <CJones@...> > To: <gdalgorithmslist@...> > Sent: Friday, April 18, 2003 1:27 AM > Subject: RE: [Algorithms] update game with constant interval > > > There was a big discussion on flipcode a while ago about this too: > > http://www.flipcode.com/cgibin/msg.cgi?showThread=TipMainLoopTimeSteps&for > um=totd&id=1 > > Chris > > > Original Message > > From: jason zhang [mailto:jason77@...] > > Sent: Wednesday, April 16, 2003 7:55 PM > > To: gdalgorithmslist@... > > Subject: [Algorithms] update game with constant interval > > > > Hello folks, > > I'd like to update my game logic with fixed delta time because > > physics and logic are easy to > > be unstable with variant delta time. And rendering will be done by > > interpolating between two > > update frames. > > I cannot find the discussion(I remember there were much) on this in > > the mail archive and on google. > > Maybe my search skills are so poor. Could someone give me some hints or > > links, please? And thanks. > > > > > > N¬±ùÞµéšŠX¬²š'²ŠÞu¼“†)äç¤Yé\¢g¢ > ž’š½éá¶ÚþØbžHzG(›û0%‚Šâ¶¬–+ > > ™¨¥Šx%ŠËF > > > > `¢¸†k%ŠËeŠËl²‹«qçè® > §zØm¶›?þX¬¶Ë(º·~ŠàzwþX¬¶ÏåŠËbú?Ö¥‚Šâ¶¬–+ > > ·!Š÷¬†Ûiÿû(º·~Šàzwþf¢•ªÜ†+Þýú+ºja¥ú+º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_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: Jonathan Perret <jperret@no...>  20030418 13:20:13

From: "Gareth Lewin" <GLewin@...> > Write a compare function that tests the distance between the points. > > bool AsSamePoint (point p1, point p2) > { > if (distance_between (p1,p2) < 0.001) // or whatever you want the > epsilon to be > return true; > return false; > } > > Then just test all points against all points. This is fine for offline. I think this is the "trivial algorithm" Peter was originally referring to :) Cheers, Jonathan 
From: Chris Wilson <Chris.Wilson@bl...>  20030418 13:12:36

Of course, you could make that *much* faster by writing if (distance_between_squared (p1,p2) < 0.001 * 0.001) // or whatever = you want the epsilon to be avoiding the square root :) Original Message From: Gareth Lewin [mailto:GLewin@...] Sent: 18 April 2003 14:00 To: gdalgorithmslist@... Subject: RE: [Algorithms] merging of points in 3D space Write a compare function that tests the distance between the points. bool AsSamePoint (point p1, point p2) { if (distance_between (p1,p2) < 0.001) // or whatever you want the epsilon to be return true; return false; } Then just test all points against all points. This is fine for offline. 
From: Gribb, Gil <ggribb@ra...>  20030418 13:11:35

This ordering is not strong enough to sort on, in particular it isn't transitive...some counter example points (e=EPSILON): A=(.5e,2e,0) B=(0,6e,0) C=(1.1e,0,0) A<B and B<C but A > C You don't really know what qsort is going to produce with this predicate. Often times just sorting on X and an appropriate search will be fast enough in practice. Bin approaches can be better than that. Both of these have bad worst case behavior. The theoretically satisfactory algorithms are the same spatial search algorithms used for collision. Gil Here is what I use: 1) Do a qsort() on the array, using a weak lexicografic ordering as comparison function. I.e. if (x0x1 < EPSILON) return 1; else if (x0x1 > +EPSILON) return 1; else if (y0y1 < EPSILON) return 1; else if (y0y1 > +EPSILON) return 1; else if (z0z1 < EPSILON) return 1; else if (z0z1 > +EPSILON) return 1; else return 0; (This procedure is O(n log n).) 2) Then do a linear walk over the array comparing neighbors again and eliminating those that are "equal", by the same comparison function. (This procedure is O(n).) The expected overal performance should be bounded by O(n log n). HTH, Alen  Original Message  From: "Peter Szinek" <szyp@...> To: <gdalgorithmslist@...> Sent: Friday, April 18, 2003 9:25 AM Subject: [Algorithms] merging of points in 3D space > Hello all, > > I am having the following problem: > > Consider an array of points in 3D given by (x, y, z). Every point is in the > array more times (56 times, does not really matter) but the problem is that > these points are not really the same  there are small differences between their > coordinates > e.g. points with coordinates > > 1.000 1.000 1.000 > 0.999 1.001 1.000 > 1.000 1.002 0.989 etc > > are considered to represent the same point. > > Now, my question is, how to 'merge' these points into one (e.g. in the previous > example, keep only one such point) _VERY_ fast. The trivial algorithm is farfar > away (as usual) from the fast enough. > > Any help appreciated. > > > > > >  > Best regards, > Peter mailto:szyp@... > > > >  > 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: Gareth Lewin <GLewin@cl...>  20030418 13:00:25

Write a compare function that tests the distance between the points. bool AsSamePoint (point p1, point p2) { if (distance_between (p1,p2) < 0.001) // or whatever you want the epsilon to be return true; return false; } Then just test all points against all points. This is fine for offline. _______________________ Regards, Gareth Lewin Programmer, Climax Solent. (To anyone outside Climax, sorry for the disclaimer below) > Original Message > From: Peter Szinek [mailto:szyp@...] > Sent: 18 April 2003 10:26 > To: gdalgorithmslist@... > Subject: [Algorithms] merging of points in 3D space > > > Hello all, > > I am having the following problem: > > Consider an array of points in 3D given by (x, y, z). Every > point is in the > array more times (56 times, does not really matter) but the > problem is that > these points are not really the same  there are small > differences between their > coordinates > e.g. points with coordinates > > 1.000 1.000 1.000 > 0.999 1.001 1.000 > 1.000 1.002 0.989 etc > > are considered to represent the same point. > > Now, my question is, how to 'merge' these points into one > (e.g. in the previous > example, keep only one such point) _VERY_ fast. The trivial > algorithm is farfar > away (as usual) from the fast enough. > > Any help appreciated. > > > > > >  > Best regards, > Peter mailto:szyp@... > > > >  > 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 > DISCLAIMER: Unless otherwise expressly stated, this message does not create or vary any contractual relationship between you and Climax Development Ltd. The contents of this email may be confidential and if you have received it in error, please delete it from your system, destroy any hard copies and contact the originator of the email. In accordance with the Telecommunications (Lawful Business Regulations) (Interception of Communications) Regulations 2000 the Company reserves the right and, may at any time, monitor and intercept (but not record) emails to establish if they are relevant to its business. 
From: Alen Ladavac <alen@cr...>  20030418 12:44:52

Here is what I use: 1) Do a qsort() on the array, using a weak lexicografic ordering as comparison function. I.e. if (x0x1 < EPSILON) return 1; else if (x0x1 > +EPSILON) return 1; else if (y0y1 < EPSILON) return 1; else if (y0y1 > +EPSILON) return 1; else if (z0z1 < EPSILON) return 1; else if (z0z1 > +EPSILON) return 1; else return 0; (This procedure is O(n log n).) 2) Then do a linear walk over the array comparing neighbors again and eliminating those that are "equal", by the same comparison function. (This procedure is O(n).) The expected overal performance should be bounded by O(n log n). HTH, Alen  Original Message  From: "Peter Szinek" <szyp@...> To: <gdalgorithmslist@...> Sent: Friday, April 18, 2003 9:25 AM Subject: [Algorithms] merging of points in 3D space > Hello all, > > I am having the following problem: > > Consider an array of points in 3D given by (x, y, z). Every point is in the > array more times (56 times, does not really matter) but the problem is that > these points are not really the same  there are small differences between their > coordinates > e.g. points with coordinates > > 1.000 1.000 1.000 > 0.999 1.001 1.000 > 1.000 1.002 0.989 etc > > are considered to represent the same point. > > Now, my question is, how to 'merge' these points into one (e.g. in the previous > example, keep only one such point) _VERY_ fast. The trivial algorithm is farfar > away (as usual) from the fast enough. > > Any help appreciated. > > > > > >  > Best regards, > Peter mailto:szyp@... > > > >  > 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: Peter Szinek <szyp@po...>  20030418 11:54:48

Hello all, I am having the following problem: Consider an array of points in 3D given by (x, y, z). Every point is in the array more times (56 times, does not really matter) but the problem is that these points are not really the same  there are small differences between their coordinates e.g. points with coordinates 1.000 1.000 1.000 0.999 1.001 1.000 1.000 1.002 0.989 etc are considered to represent the same point. Now, my question is, how to 'merge' these points into one (e.g. in the previous example, keep only one such point) _VERY_ fast. The trivial algorithm is farfar away (as usual) from the fast enough. Any help appreciated.  Best regards, Peter mailto:szyp@... 
From: <christer_ericson@pl...>  20030418 02:32:32

Guillaume Provost wrote: > If I took the dumb route and said, do the test for every poly, > edge, and point in the hull, then this algorithm would work would it not? I'm not 100% sure about what you mean by "this algorithm", but I believe the answer is yes. If you mean determining which face, edge, or vertex Voronoi feature region (VFR) the point is in by testing all the VFR's, then based on the type of region, doing a test against the extruded triangle, a cylinder, or a sphere, then absolutely. > Throw a localized marching search in the picture, that > converges towards the nearest face (ie: LinCanneys proximity query > algs) and you get less then Log(N) time at it. Utilizing coherence between queries you mean. Yeah, that can give you constant time queries in the best case. Worstcase you always have to move to the opposite side of the hull which I think makes it O(sqrt(N)) (is that right?) > You have'nt solved > any generic quadratic problems, but rather specialized your problem > space to the primitives involved. True. By working with an explicit face/vertex representation you can avoid dealing with quadratic programming. The quadratic programming problem typically applies when you're working with the hull as the intersection of a set of halfspaces. (Although in some sense you still have a quadratic problem even in the former case, since you still have to compute the distance to the edge cylinders and vertex spheres. Of course, they're now trivial QP problems.) I actually prefer approaches that break the problem into deciding which VFR you're in and then testing against that feature, since they're both conceptually simple and the math is straightforward. The only drawback is that you need to store more data than for a halfspaceonly representation. But you'd probably store the vertices of the hull for debugging purposes anyway, so it's not a big deal. > I would think such a system would > be faster than GJK, but I'm far from being knowledgeable about it, I don't think there's a definitive answer here. It depends on a number of things, such as the size of the hulls, whether you use coherence, etc. You do pretty much the same math in determining what VFR you're in as in doing the "Johnson" step of GJK. The big difference between stepping between VFR's (like in the LinCanny algorithm) and GJK, is that LinCanny moves on the surface of the hull, whereas GJK 'burrows' through the hull. > If Log(N) time is an acceptable measure, then by all means the > first 'culling pass' involved in testing against every extruded > plane equation will also give us the closest plane. I think you meant O(N) here, otherwise you couldn't be guaranteed to get the closest plane (unless you added some hierarchy to the representation). > If a vert lies > within the boundaries of the extruded planes but outside the actual > extruded hull, my instinct tells me the closest plane equation (its > associated verts, edges, and face) will always suffice in testing > this relationship. This is a bit of a stretch on my part, since I > can't actually prove it mathematically, but I can't picture a failure case. I think you are correct about this, but I don't have proof for it either, off the top of my head. I can see it being correct for 2D, I have to think about the 3D case. Christer Ericson Sony Computer Entertainment, Santa Monica 