You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

2015 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(12) 
_{Nov}

_{Dec}
(1) 
2016 
_{Jan}

_{Feb}
(1) 
_{Mar}
(1) 
_{Apr}
(1) 
_{May}

_{Jun}
(1) 
_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 







1
(4) 
2
(3) 
3
(3) 
4
(4) 
5
(10) 
6
(10) 
7
(6) 
8
(8) 
9
(1) 
10
(7) 
11
(7) 
12
(6) 
13
(6) 
14
(19) 
15
(1) 
16

17
(2) 
18
(3) 
19
(1) 
20

21
(2) 
22
(3) 
23
(2) 
24
(2) 
25

26
(3) 
27
(26) 
28
(4) 
29
(4) 
30







From: Jim Van Verth <jvsquare@nc...>  20060408 03:52:07

The article that I suspect Jonathan was trying to think of is in _GPG 4_, and it's called "Using the Covariant Matrix for Better Fitting Bounding Objects." However, using the covariant matrix won't give you best fit, i.e. a minimum volume box. For that, see http://www.geometrictools.com/Containment.html. There's a description of how it works in Eberly's _3D Game Engine Design_, but it makes my head hurt. I've got source code for the covariant matrix method if you still need it  drop me a line. Jim 
From: Jonathan Blow <jon@nu...>  20060408 02:55:08

btw I think I remember one place where I have seen the solution to this=20 written up, it was in Gottschalk's OBB paper: http://citeseer.ist.psu.edu/gottschalk96obbtree.html Maik Wagner wrote: > Hi, > > what should i say. I'm still stupid myself :) (still student) > But when reading your question one word came to my mind: PCA=20 > (principal components analysis). > I am not that experienced, but with that you should be able to get the=20 > at least 2 dimensions, where points are spread out most, and third=20 > would just be a cross product. With that new coordinate system, it=20 > should be kinda easy to determine the min and maxspread of your=20 > points, which then would give you a bounding box. (rotation and=20 > translation should be easily extracted i think) > > > In fact PCA uses "Eigenve{kc}toren" (its an german expression, and as=20 > there is no really english equivalent, its also used in english). No=20 > matter whats mathematically behind, it gives you vectors with the=20 > greatest spread in dimensions. > > I think using this you should get a quite good (perhaps the best!?)=20 > result. > > Don't blame me if this is not what you wanted to hear, thats my first=20 > answer here. > > Regards, > Maik > > John Ratcliff wrote: > >> Ok, I realize this may be a dumb question but I suppose that is the=20 >> point. I want to do something that I believe should be really simple=20 >> to do. In fact I have an enormous amount of reference material that=20 >> implies the solution is simple. However, I have yet to find a=20 >> solution that is presented in a form that, to me, makes common sense. >> >> I am curious, can anyone on this list direct me to a routine that=20 >> does the following: >> >> void computeOBB(unsigned int vcount,const float *points,float=20 >> *sides,float *matrix); >> >> This hypothetical, and eminently useful, routine would accept an=20 >> array of 3d data points and return and oriented bounding box=20 >> represented as =91width,depth,height=92 (stored in =91sides=92) and a = 4x4=20 >> rotation and translation matrix where the translation is the center=20 >> of the box. >> >> I have found all manner of samples that compute some magical=20 >> mathematical entity called an =91eigen vector=92 but when I try to use= =20 >> the matrix it produces it is not valid. >> >> Maybe I=92m just dumb. In fact, I know I=92m dumb. It just surprises m= e=20 >> that something so basic, so common, isn=92t just laying around in a Ge= m=20 >> somewhere. In fact, it probably is and I haven=92t found it yet. Or,=20 >> maybe the problem is more difficult than I think and there are any=20 >> number of possible =91best fit=92 oriented bounding boxes possible for= an=20 >> arbitrary point cloud. Maybe this is, in fact, a really difficult=20 >> optimization problem. >> >> I would appreciate a code snippet and, if you can=92t provide one, I=20 >> will just write my own the slow, painful, dumb way. I just hate=20 >> writing code that I figured I should find somewhere on the net as=20 >> easily as a quaternion or matrix implementation. >> >> Thanks, >> >> John >> > > > >  > This SF.Net email is sponsored by xPML, a groundbreaking scripting=20 > language > that extends applications into web and mobile media. Attend the live=20 > webcast > and join the prime developer group breaking into this new coding=20 > territory! > http://sel.asus.falkag.net/sel?cmd____________________________________= ___________=20 > > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > 
From: Jonathan Blow <jon@nu...>  20060408 02:54:14

Yes, "Principal Component Analysis" is another term for the same=20 solution we're talking about... it can be a good term to use when doing=20 web searches. Maik Wagner wrote: > Hi, > > what should i say. I'm still stupid myself :) (still student) > But when reading your question one word came to my mind: PCA=20 > (principal components analysis). > I am not that experienced, but with that you should be able to get the=20 > at least 2 dimensions, where points are spread out most, and third=20 > would just be a cross product. With that new coordinate system, it=20 > should be kinda easy to determine the min and maxspread of your=20 > points, which then would give you a bounding box. (rotation and=20 > translation should be easily extracted i think) > > > In fact PCA uses "Eigenve{kc}toren" (its an german expression, and as=20 > there is no really english equivalent, its also used in english). No=20 > matter whats mathematically behind, it gives you vectors with the=20 > greatest spread in dimensions. > > I think using this you should get a quite good (perhaps the best!?)=20 > result. > > Don't blame me if this is not what you wanted to hear, thats my first=20 > answer here. > > Regards, > Maik > > John Ratcliff wrote: > >> Ok, I realize this may be a dumb question but I suppose that is the=20 >> point. I want to do something that I believe should be really simple=20 >> to do. In fact I have an enormous amount of reference material that=20 >> implies the solution is simple. However, I have yet to find a=20 >> solution that is presented in a form that, to me, makes common sense. >> >> I am curious, can anyone on this list direct me to a routine that=20 >> does the following: >> >> void computeOBB(unsigned int vcount,const float *points,float=20 >> *sides,float *matrix); >> >> This hypothetical, and eminently useful, routine would accept an=20 >> array of 3d data points and return and oriented bounding box=20 >> represented as =91width,depth,height=92 (stored in =91sides=92) and a = 4x4=20 >> rotation and translation matrix where the translation is the center=20 >> of the box. >> >> I have found all manner of samples that compute some magical=20 >> mathematical entity called an =91eigen vector=92 but when I try to use= =20 >> the matrix it produces it is not valid. >> >> Maybe I=92m just dumb. In fact, I know I=92m dumb. It just surprises m= e=20 >> that something so basic, so common, isn=92t just laying around in a Ge= m=20 >> somewhere. In fact, it probably is and I haven=92t found it yet. Or,=20 >> maybe the problem is more difficult than I think and there are any=20 >> number of possible =91best fit=92 oriented bounding boxes possible for= an=20 >> arbitrary point cloud. Maybe this is, in fact, a really difficult=20 >> optimization problem. >> >> I would appreciate a code snippet and, if you can=92t provide one, I=20 >> will just write my own the slow, painful, dumb way. I just hate=20 >> writing code that I figured I should find somewhere on the net as=20 >> easily as a quaternion or matrix implementation. >> >> Thanks, >> >> John >> > > > >  > This SF.Net email is sponsored by xPML, a groundbreaking scripting=20 > language > that extends applications into web and mobile media. Attend the live=20 > webcast > and join the prime developer group breaking into this new coding=20 > territory! > http://sel.asus.falkag.net/sel?cmd____________________________________= ___________=20 > > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > 
From: John Ratcliff <jratcliff@in...>  20060408 02:54:11

Thanks for the links guys. You can rest assured that when I get it working I will insert it as a code suppository into the internet with exactly the single API call I described to begin with. Lately I have been acquiring a real pet peeve about code resuse. It seems you can't just get a single routine without refactoring a few thousand lines of code. What does it matter if something is 'open source' if you have to spend a week refactoring thousands of lines of code just to take advantage of it. In lieu of us having an ANSI standard set of vector, matrix, and quaternion libraries I remain a big fan of 'const float *'. I'll go ahead and follow the links and come up with a nice turnkey solution from there. Much thanks, John Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Andy O'Neil Sent: Friday, April 07, 2006 8:31 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] Best Fit Oriented Bounding Box There should be an implementation of this algorithm in the RAPID collision detection library, though it's been a while since I last looked at it. You can download it from http://www.cs.sunysb.edu/~algorith/implement/RAPID/implement.shtml . Cheers, Andy ________________________________ From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of John Ratcliff Sent: Friday, April 07, 2006 7:56 PM To: gdalgorithmslist@... Subject: [Algorithms] Best Fit Oriented Bounding Box Ok, I realize this may be a dumb question but I suppose that is the point. I want to do something that I believe should be really simple to do. In fact I have an enormous amount of reference material that implies the solution is simple. However, I have yet to find a solution that is presented in a form that, to me, makes common sense. I am curious, can anyone on this list direct me to a routine that does the following: void computeOBB(unsigned int vcount,const float *points,float *sides,float *matrix); This hypothetical, and eminently useful, routine would accept an array of 3d data points and return and oriented bounding box represented as 'width,depth,height' (stored in 'sides') and a 4x4 rotation and translation matrix where the translation is the center of the box. I have found all manner of samples that compute some magical mathematical entity called an 'eigen vector' but when I try to use the matrix it produces it is not valid. Maybe I'm just dumb. In fact, I know I'm dumb. It just surprises me that something so basic, so common, isn't just laying around in a Gem somewhere. In fact, it probably is and I haven't found it yet. Or, maybe the problem is more difficult than I think and there are any number of possible 'best fit' oriented bounding boxes possible for an arbitrary point cloud. Maybe this is, in fact, a really difficult optimization problem. I would appreciate a code snippet and, if you can't provide one, I will just write my own the slow, painful, dumb way. I just hate writing code that I figured I should find somewhere on the net as easily as a quaternion or matrix implementation. Thanks, John  This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.asus.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Maik Wagner <maikwagner@we...>  20060408 02:48:07

Hi, what should i say. I'm still stupid myself :) (still student) But when reading your question one word came to my mind: PCA (principal=20 components analysis). I am not that experienced, but with that you should be able to get the=20 at least 2 dimensions, where points are spread out most, and third would=20 just be a cross product. With that new coordinate system, it should be=20 kinda easy to determine the min and maxspread of your points, which=20 then would give you a bounding box. (rotation and translation should be=20 easily extracted i think) In fact PCA uses "Eigenve{kc}toren" (its an german expression, and as=20 there is no really english equivalent, its also used in english). No=20 matter whats mathematically behind, it gives you vectors with the=20 greatest spread in dimensions. I think using this you should get a quite good (perhaps the best!?) resul= t. Don't blame me if this is not what you wanted to hear, thats my first=20 answer here. Regards, Maik John Ratcliff wrote: > Ok, I realize this may be a dumb question but I suppose that is the=20 > point. I want to do something that I believe should be really simple=20 > to do. In fact I have an enormous amount of reference material that=20 > implies the solution is simple. However, I have yet to find a solution=20 > that is presented in a form that, to me, makes common sense. > > I am curious, can anyone on this list direct me to a routine that does=20 > the following: > > void computeOBB(unsigned int vcount,const float *points,float=20 > *sides,float *matrix); > > This hypothetical, and eminently useful, routine would accept an array=20 > of 3d data points and return and oriented bounding box represented as=20 > =91width,depth,height=92 (stored in =91sides=92) and a 4x4 rotation and= =20 > translation matrix where the translation is the center of the box. > > I have found all manner of samples that compute some magical=20 > mathematical entity called an =91eigen vector=92 but when I try to use = the=20 > matrix it produces it is not valid. > > Maybe I=92m just dumb. In fact, I know I=92m dumb. It just surprises me= =20 > that something so basic, so common, isn=92t just laying around in a Gem= =20 > somewhere. In fact, it probably is and I haven=92t found it yet. Or,=20 > maybe the problem is more difficult than I think and there are any=20 > number of possible =91best fit=92 oriented bounding boxes possible for = an=20 > arbitrary point cloud. Maybe this is, in fact, a really difficult=20 > optimization problem. > > I would appreciate a code snippet and, if you can=92t provide one, I=20 > will just write my own the slow, painful, dumb way. I just hate=20 > writing code that I figured I should find somewhere on the net as=20 > easily as a quaternion or matrix implementation. > > Thanks, > > John > 
From: Andy O'Neil <aoneil@au...>  20060408 01:30:24

There should be an implementation of this algorithm in the RAPID collision detection library, though it's been a while since I last looked at it. You can download it from http://www.cs.sunysb.edu/~algorith/implement/RAPID/implement.shtml . Cheers, Andy ________________________________ From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of John Ratcliff Sent: Friday, April 07, 2006 7:56 PM To: gdalgorithmslist@... Subject: [Algorithms] Best Fit Oriented Bounding Box Ok, I realize this may be a dumb question but I suppose that is the point. I want to do something that I believe should be really simple to do. In fact I have an enormous amount of reference material that implies the solution is simple. However, I have yet to find a solution that is presented in a form that, to me, makes common sense. I am curious, can anyone on this list direct me to a routine that does the following: void computeOBB(unsigned int vcount,const float *points,float *sides,float *matrix); This hypothetical, and eminently useful, routine would accept an array of 3d data points and return and oriented bounding box represented as 'width,depth,height' (stored in 'sides') and a 4x4 rotation and translation matrix where the translation is the center of the box. I have found all manner of samples that compute some magical mathematical entity called an 'eigen vector' but when I try to use the matrix it produces it is not valid. Maybe I'm just dumb. In fact, I know I'm dumb. It just surprises me that something so basic, so common, isn't just laying around in a Gem somewhere. In fact, it probably is and I haven't found it yet. Or, maybe the problem is more difficult than I think and there are any number of possible 'best fit' oriented bounding boxes possible for an arbitrary point cloud. Maybe this is, in fact, a really difficult optimization problem. I would appreciate a code snippet and, if you can't provide one, I will just write my own the slow, painful, dumb way. I just hate writing code that I figured I should find somewhere on the net as easily as a quaternion or matrix implementation. Thanks, John 
From: Jonathan Blow <jon@nu...>  20060408 01:18:40

I have read the solution to this online in places, but don't remember=20 where (and in fact I think there really may be an article on it in one=20 of the GPG books). What you want to do is build a covariance matrix of the set of points,=20 then take the eigenvectors of that (sorry John) which give you the plane=20 normals for the sides of your box. From that you can trivially find the=20 extents and center of the box. This will not actually be the best fit box, but it is pretty close in=20 most cases. I did this kind of thing in 2D in some of my Game Developer articles=20 (See for example=20 http://numbernone.com/product/My%20Friend,%20the%20Covariance%20Body/ind= ex.html).=20 The 3D version is a straightforward extension of that. (The code is=20 available at http://gdmag.com/code.htm, unfortunately I don't have it=20 conveniently linked from the article). There are some pictures in the=20 article that sort of illustrate the idea. As for the code you have giving you an invalid matrix... it's possible=20 that the code is not robust enough to deal with degenerate cases. For=20 example, if all your points lie in a plane, the eigenspace will only be=20 2D, and if the code doesn't know how to deal with that, it might blow up. So  sorry I am not handing you a shrinkwrapped solution, but I think=20 this is one of those problems that you would really be better off=20 understanding. Especially because you have done a lot of physicsrelated=20 stuff and this is basically the same thing. (The covariance matrix is=20 the same basic thing as an inertia tensor, it is just presented in a=20 slightly different form, cosmetically). John Ratcliff wrote: > > Ok, I realize this may be a dumb question but I suppose that is the=20 > point. I want to do something that I believe should be really simple=20 > to do. In fact I have an enormous amount of reference material that=20 > implies the solution is simple. However, I have yet to find a solution=20 > that is presented in a form that, to me, makes common sense. > > I am curious, can anyone on this list direct me to a routine that does=20 > the following: > > void computeOBB(unsigned int vcount,const float *points,float=20 > *sides,float *matrix); > > This hypothetical, and eminently useful, routine would accept an array=20 > of 3d data points and return and oriented bounding box represented as=20 > =91width,depth,height=92 (stored in =91sides=92) and a 4x4 rotation and= =20 > translation matrix where the translation is the center of the box. > > I have found all manner of samples that compute some magical=20 > mathematical entity called an =91eigen vector=92 but when I try to use = the=20 > matrix it produces it is not valid. > > Maybe I=92m just dumb. In fact, I know I=92m dumb. It just surprises me= =20 > that something so basic, so common, isn=92t just laying around in a Gem= =20 > somewhere. In fact, it probably is and I haven=92t found it yet. Or,=20 > maybe the problem is more difficult than I think and there are any=20 > number of possible =91best fit=92 oriented bounding boxes possible for = an=20 > arbitrary point cloud. Maybe this is, in fact, a really difficult=20 > optimization problem. > > I would appreciate a code snippet and, if you can=92t provide one, I=20 > will just write my own the slow, painful, dumb way. I just hate=20 > writing code that I figured I should find somewhere on the net as=20 > easily as a quaternion or matrix implementation. > > Thanks, > > John > 
From: John Ratcliff <jratcliff@in...>  20060408 00:57:45

Ok, I realize this may be a dumb question but I suppose that is the point. I want to do something that I believe should be really simple to do. In fact I have an enormous amount of reference material that implies the solution is simple. However, I have yet to find a solution that is presented in a form that, to me, makes common sense. I am curious, can anyone on this list direct me to a routine that does the following: void computeOBB(unsigned int vcount,const float *points,float *sides,float *matrix); This hypothetical, and eminently useful, routine would accept an array of 3d data points and return and oriented bounding box represented as 'width,depth,height' (stored in 'sides') and a 4x4 rotation and translation matrix where the translation is the center of the box. I have found all manner of samples that compute some magical mathematical entity called an 'eigen vector' but when I try to use the matrix it produces it is not valid. Maybe I'm just dumb. In fact, I know I'm dumb. It just surprises me that something so basic, so common, isn't just laying around in a Gem somewhere. In fact, it probably is and I haven't found it yet. Or, maybe the problem is more difficult than I think and there are any number of possible 'best fit' oriented bounding boxes possible for an arbitrary point cloud. Maybe this is, in fact, a really difficult optimization problem. I would appreciate a code snippet and, if you can't provide one, I will just write my own the slow, painful, dumb way. I just hate writing code that I figured I should find somewhere on the net as easily as a quaternion or matrix implementation. Thanks, John 