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
(8) 
2
(13) 
3
(4) 
4
(3) 
5
(3) 
6
(4) 
7
(1) 
8
(6) 
9
(18) 
10
(10) 
11
(12) 
12
(5) 
13
(7) 
14
(11) 
15
(1) 
16

17
(5) 
18
(5) 
19
(4) 
20
(1) 
21
(1) 
22
(2) 
23

24

25

26

27

28
(5) 
29

30
(2) 



From: Emil Persson <humus@co...>  20090930 22:21:55

I think the z instead of w is an error in the original code. It would probably still work fairly OK though most of the time, simply because z and w usually are fairly close, except close to the camera (which is also why a depth buffer often looks like plain white when viewed directly without increasing contrast). Emil Original Message From: Christian Heckl [mailto:c.heckl@...] Sent: 30 September 2009 23:53 To: gdalgorithmslist@... Subject: [Algorithms] Question to High Quality Antialiased Lines (Shader X7)/ Perspective divide Hi out there, I am currently working on rendering laser beams through billboards in a deferred rendering environment. I have strong aliasing issues when viewing these beams from afar as they are pretty thin with respect to the overall world geometry. The result is a "marchingant" stipplelike pattern as shown in the attached image. Inspired by "Simplified HighQualityAntiAliased Lines" (Shader X7) I decided that keeping the projected beams from falling below a certain pixel threshold when viewed from afar (thus effectively making them slightly thicker) would very well solve my problems and be "plausible" enough. Unfortunately, I cannot quite make sense of some of the steps in the shader code. To correctly calculate the position of the corners of the billboard, the screen space vector between the start and endpoint is taken as such: p0 = start * world_view_projection p1 = end * world_view_projection //some modifications to p0.y and p1.y according to aspect ratio ... //Calc vectors between points in screen space < Original comment delta2.xy = p1.xy / p1.z  p0.xy/p0.z; //< I dont quite get why the divisor is z and not w (for the homogenization step after the projection which is my understanding of screen space) delta_p.xy = delta2.xy delta_p.z = p1.z  w1.z; //Calc UV basis vectors float len = length(delta2.xy); float3 U = delta_p / len; //< Why would I not use normalize(p1/p1.w  p0/p0.w) as a basis for U? ...//offset = (U * factor_u + V * factor_v) //Undo perspective divide since the hardware will do it // < Original Comment, though perspective divide to my knowledge is /w not /z Output.position.xy += offset * Output.position.z; // < Output.position.z is p0.z or p1.z, I would multiply by Output.position.w here Can somebody shed some light on this? It might be something obvious, I just don't see it right now. Thanks in advance for any pointers, other solutions for solving the stipple problem are also welcome! (i.e. do i need a higher tesselation to avoid rasterizing very long and thin triangles?) Chris P.S.: I made the two modifications and it still looks "correct" (i.e. I can't spot any differences). 
From: Christian Heckl <c.heckl@qu...>  20090930 22:06:22

Hi out there, I am currently working on rendering laser beams through billboards in a deferred rendering environment. I have strong aliasing issues when viewing these beams from afar as they are pretty thin with respect to the overall world geometry. The result is a "marchingant" stipplelike pattern as shown in the attached image. Inspired by "Simplified HighQualityAntiAliased Lines" (Shader X7) I decided that keeping the projected beams from falling below a certain pixel threshold when viewed from afar (thus effectively making them slightly thicker) would very well solve my problems and be "plausible" enough. Unfortunately, I cannot quite make sense of some of the steps in the shader code. To correctly calculate the position of the corners of the billboard, the screen space vector between the start and endpoint is taken as such: p0 = start * world_view_projection p1 = end * world_view_projection //some modifications to p0.y and p1.y according to aspect ratio ... //Calc vectors between points in screen space < Original comment delta2.xy = p1.xy / p1.z  p0.xy/p0.z; //< I dont quite get why the divisor is z and not w (for the homogenization step after the projection which is my understanding of screen space) delta_p.xy = delta2.xy delta_p.z = p1.z  w1.z; //Calc UV basis vectors float len = length(delta2.xy); float3 U = delta_p / len; //< Why would I not use normalize(p1/p1.w  p0/p0.w) as a basis for U? ...//offset = (U * factor_u + V * factor_v) //Undo perspective divide since the hardware will do it // < Original Comment, though perspective divide to my knowledge is /w not /z Output.position.xy += offset * Output.position.z; // < Output.position.z is p0.z or p1.z, I would multiply by Output.position.w here Can somebody shed some light on this? It might be something obvious, I just don't see it right now. Thanks in advance for any pointers, other solutions for solving the stipple problem are also welcome! (i.e. do i need a higher tesselation to avoid rasterizing very long and thin triangles?) Chris P.S.: I made the two modifications and it still looks "correct" (i.e. I can't spot any differences). 
From: Osman, Brian <BO<sman@vv...>  20090928 18:16:33

I think it's worth pointing out that unless you've planned ahead (or are happy with some visual strangeness), this isn't going to work very well for arbitrary meshes. Without constraints on the UV mapping, you're going to get really crazy behavior along UV seams of the mesh. Even with constraints, I don't see any general case where you're going to be able to keep the mapped texture continuous across the mesh. Brian From: Sim Dietrich [mailto:simmer@...] Sent: Monday, September 28, 2009 1:44 PM To: Game Development Algorithms Subject: Re: [Algorithms] Scroll direction algorithm If you have a tangent space basis for the mesh then this gives you the information you need. You can use this to convert from left/right in world, view or model space, and convert into UV space. You can look up tangent space lighting tutorials, then interpret the scroll direction as a light direction. Put the scroll direction vector in model space, then through the pervertex or perpixel tangent space matrix ( which will account for the texture direction flips ), then scale the resulting vector based on the scroll speed and time, then add this to the initial model UVs. That should work... On Mon, Sep 28, 2009 at 9:22 AM, Zafar Qamar <zafar.qamar@...> wrote: Hi, I have a question about an algorithm in a shader. I hope this is the right place to post. I basically have a mesh that has a texture on. In my shader I want the effect to generally look like it is moving across the mesh from left to right. Imagine it is a simple scrolling texture with some spots on, for the case of this question. However, the mesh has been UV mapped such that generally the texture looks like it is scrolling in the right direction, but some areas have the texture scrolling in completely the wrong direction. Is there some maths algorithm I can use to possibly get around this? I apologise if my question is not clear. Cheers Zafar Qamar ************************************************************************ ********** Disclaimer The information and attached documentation in this email is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or emailing the sender. Please note that without Codemasters' prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful. Attachments to this email may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened. Any offer contained in this communication is subject to Codemasters' standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this email is subject to contract and Codemasters' board approval. Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters. This footnote also confirms that this email message has been swept by SurfControl for the presence of computer viruses. ************************************************************************ **********   Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 912, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis t 
From: Oscar Forth <oscar@tr...>  20090928 17:46:22

well the problem comes from the fact a give triangle could be mapped to any set of UVs. to know what direction you are scrolling the texture you'd need to know details about the triangle. AFAIK, you could do it with a geometry shader, but without adding a load of info to each certex you wouldn't be able to know the orientation. 2009/9/28 Zafar Qamar <zafar.qamar@...> > Hi, > > > > I have a question about an algorithm in a shader. I hope this is the right > place to post. > > > > I basically have a mesh that has a texture on. In my shader I want the > effect to generally look like it is moving across the mesh from left to > right. Imagine it is a simple scrolling texture with some spots on, for the > case of this question. > > > > However, the mesh has been UV mapped such that generally the texture looks > like it is scrolling in the right direction, but some areas have the texture > scrolling in completely the wrong direction. > > > > Is there some maths algorithm I can use to possibly get around this? > > > > I apologise if my question is not clear. > > > > Cheers > > Zafar Qamar > > > > > ********************************************************************************** > Disclaimer > > > The information and attached documentation in this email is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or emailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful. > > > Attachments to this email may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened. > > > Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this email is subject to contract and Codemasters’ board approval. > > Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters. > > This footnote also confirms that this email message has been swept by > SurfControl for the presence of computer viruses. > > ********************************************************************************** > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Sim Dietrich <simmer@gm...>  20090928 17:44:35

If you have a tangent space basis for the mesh then this gives you the information you need. You can use this to convert from left/right in world, view or model space, and convert into UV space. You can look up tangent space lighting tutorials, then interpret the scroll direction as a light direction. Put the scroll direction vector in model space, then through the pervertex or perpixel tangent space matrix ( which will account for the texture direction flips ), then scale the resulting vector based on the scroll speed and time, then add this to the initial model UVs. That should work... On Mon, Sep 28, 2009 at 9:22 AM, Zafar Qamar <zafar.qamar@...>wrote: > Hi, > > > > I have a question about an algorithm in a shader. I hope this is the right > place to post. > > > > I basically have a mesh that has a texture on. In my shader I want the > effect to generally look like it is moving across the mesh from left to > right. Imagine it is a simple scrolling texture with some spots on, for the > case of this question. > > > > However, the mesh has been UV mapped such that generally the texture looks > like it is scrolling in the right direction, but some areas have the texture > scrolling in completely the wrong direction. > > > > Is there some maths algorithm I can use to possibly get around this? > > > > I apologise if my question is not clear. > > > > Cheers > > Zafar Qamar > > > > > ********************************************************************************** > Disclaimer > > > The information and attached documentation in this email is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or emailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful. > > > Attachments to this email may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened. > > > Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this email is subject to contract and Codemasters’ board approval. > > Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters. > > This footnote also confirms that this email message has been swept by > SurfControl for the presence of computer viruses. > > ********************************************************************************** > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Jeff Russell <jeffdr@8m...>  20090928 17:38:58

You can try to project the texture 'U axis' into view space, or world space, and then you can know which direction you want the texture scrolling in. Jeff On Mon, Sep 28, 2009 at 11:22 AM, Zafar Qamar <zafar.qamar@...>wrote: > Hi, > > > > I have a question about an algorithm in a shader. I hope this is the right > place to post. > > > > I basically have a mesh that has a texture on. In my shader I want the > effect to generally look like it is moving across the mesh from left to > right. Imagine it is a simple scrolling texture with some spots on, for the > case of this question. > > > > However, the mesh has been UV mapped such that generally the texture looks > like it is scrolling in the right direction, but some areas have the texture > scrolling in completely the wrong direction. > > > > Is there some maths algorithm I can use to possibly get around this? > > > > I apologise if my question is not clear. > > > > Cheers > > Zafar Qamar > > > > > ********************************************************************************** > Disclaimer > > > The information and attached documentation in this email is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or emailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful. > > > Attachments to this email may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened. > > > Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this email is subject to contract and Codemasters’ board approval. > > Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters. > > This footnote also confirms that this email message has been swept by > SurfControl for the presence of computer viruses. > > ********************************************************************************** > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >  Jeff Russell Engineer, 8monkey Labs http://www.8monkeylabs.com 
From: Zafar Qamar <zafar.qamar@co...>  20090928 17:18:04

Hi, I have a question about an algorithm in a shader. I hope this is the right place to post. I basically have a mesh that has a texture on. In my shader I want the effect to generally look like it is moving across the mesh from left to right. Imagine it is a simple scrolling texture with some spots on, for the case of this question. However, the mesh has been UV mapped such that generally the texture looks like it is scrolling in the right direction, but some areas have the texture scrolling in completely the wrong direction. Is there some maths algorithm I can use to possibly get around this? I apologise if my question is not clear. Cheers Zafar Qamar ********************************************************************************** Disclaimer The information and attached documentation in this email is intended for the use of the addressee only and is confidential. If you are not the intended recipient please delete it and notify us immediately by telephoning or emailing the sender. Please note that without Codemasters’ prior written consent any form of distribution, copying or use of this communication or the information in it is strictly prohibited and may be unlawful. Attachments to this email may contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any documents before they are opened. Any offer contained in this communication is subject to Codemasters’ standard terms & conditions and must be signed by both parties. Except as expressly provided otherwise all information and attached documentation in this email is subject to contract and Codemasters’ board approval. Any views or opinions expressed are solely those of the author and do not necessarily represent those of Codemasters. This footnote also confirms that this email message has been swept by SurfControl for the presence of computer viruses. ********************************************************************************** 
From: Robin Green <robin.green@gm...>  20090922 16:12:02

Just after sending that GDAlgorithms post, I also found that the latest September 2009 edition of the ACM Journal of Computational Physics has a "Short Note" on SH rotations. I don't have the logins to read that yet unfortunately, but it cites the previous papers. http://portal.acm.org/citation.cfm?id=1563054.1563203&coll=GUIDE&dl=GUIDE  Robin Green. 2009/9/22 Grégory Jaegy <g.jaegy@...>: > This is very interesting indeed, thanks for pointing it out ! > > I wish I had some time to implement the paper and compare the > performance/results to my existing implementation ! > > Grégory Jaegy 
From: Grégory Jaegy <g.jaegy@fr...>  20090922 07:01:39

This is very interesting indeed, thanks for pointing it out ! I wish I had some time to implement the paper and compare the performance/results to my existing implementation ! Grégory Jaegy Message d'origine De : Robin Green [mailto:robin.green@...] Envoyé : lundi 21 septembre 2009 18:59 À : Game Development Algorithms Objet : [Algorithms] New research in SH rotations. I received in the mail this morning a print of a paper from a researcher in "Ambisonics" (the science of multidirectional or spherical sound field recording and playback), Michael Chapman, who claims to have new insight into producing rotation matrices for Spherical Harmonics based on his research into their symmetries: http://ambisonics.iem.at/symposium2009/proceedings/ambisym09chapmanshsymme tries.pdf/at_download/file Along with this was a reference to a recent 2006 paper on efficient SH rotations from Pinchon et al where they claim to have improved on Kautz, Sloan and Snyder's methods not just in generation but in compact storage as well: http://www.math.univtoulouse.fr/ArchiveMIP/publis/files/06.30.pdf Just in case anyone still cares about efficient rotation of SH functions.  Robin Green.   Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 912, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Robin Green <robin.green@gm...>  20090921 17:25:38

I received in the mail this morning a print of a paper from a researcher in "Ambisonics" (the science of multidirectional or spherical sound field recording and playback), Michael Chapman, who claims to have new insight into producing rotation matrices for Spherical Harmonics based on his research into their symmetries: http://ambisonics.iem.at/symposium2009/proceedings/ambisym09chapmanshsymmetries.pdf/at_download/file Along with this was a reference to a recent 2006 paper on efficient SH rotations from Pinchon et al where they claim to have improved on Kautz, Sloan and Snyder's methods not just in generation but in compact storage as well: http://www.math.univtoulouse.fr/ArchiveMIP/publis/files/06.30.pdf Just in case anyone still cares about efficient rotation of SH functions.  Robin Green. 
From: Andras Balogh <andras.balogh@gm...>  20090920 15:08:47

Hah, you're right. I've never realized you could do that. While the operations required are indeed trivial, it doesn't seem like I can express it with simple matrix operations. So the code to do it will be somewhat nontrivial, but that's fine. Thanks! Andras On Sat, 19 Sep 2009 08:41:58 0600, Staffan Langin <staffan.langin@...> wrote: > Hi there Andras, > > C = Y^1 * D * Y can be linearized by multiplying by Y (from the left). > > <=> > > Y*C=D*Y > > The equationsystem, Y*C=D*Y, is trivial to reformulate to the more > common > form Ax=b. > > > Best regards, > > Staffan Langin > > > > Original Message > From: Andras Balogh [mailto:andras.balogh@...] > Sent: den 17 september 2009 21:38 > To: gdalgorithmslist@... > Subject: [Algorithms] solving for multiple matrices > > Hi, I have a chain of transformations with multiple unknown (but fixed!) > transforms. What I do know is the end result transformation and some of > the transformations in between, and I know these for multiple frames. So > from here, I'd like to compute the unknowns. Here it is in more formal > version: > > I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1, > A2, B1 and B2, and also know this: > A1 = X * B1 * Y > A2 = X * B2 * Y > > I can compute X from the first equation: > X = A1 * Y^1 * B1^1 > > And substitute it into the second: > A2 = A1 * Y^1 * B1^1 * B2 * y > > Assigning: > C = A1^1 * A2 > D = B1^1 * B2 > > Then it becomes: > C = Y^1 * D * Y > > Now, how do I solve this for Y? This form lookes strangely familiar, but > I > cannot figure out what to do from here (wish I knew how to Google this > ;). > Hopefully there's an analytic solution to this. Any ideas? > > Thanks, > > > > Andras > >  >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register > now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register > now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Jon Watte <jwatte@gm...>  20090919 17:10:14

Marius Elvert wrote: > the mesh is always vertically aligned. (i.e. the world "up" axis can > always be mapped to V). Also, I don't mind if different, nonconnected > parts of the UV map are overlapping. Basically, I just want to remove For the noncylindrical edges, how about you pick one triangle as "reference" and then unfold all the other triangles to that plane? Then map UV to the coordinates of vertices in that plane. As long as your geometry is heightmaplike (modulo the steep cliff feature) this should be possible. For the cylinder shapes, though, you have to cut them at some point; they will not fully tile unless you're willing to sometimes significantly scale/distort the mapping. You might be able to get away with dual mappings, and ramp from one to the other using blending, if it's really important. Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Marius Elvert <marius.elvert@go...>  20090919 16:29:59

Hi, I have a terrain mesh generator that generates cliffs in the mesh, very similar to the terrain used in Warcraft 3. See the brown parts in this: http://img178.imageshack.us/img178/8168/terrainwithcliff.jpg Now I want to generate UV coordinates for using a tiled texture on it. I figured that it might be a lot easier than generic unwrapping since the mesh is always vertically aligned. (i.e. the world "up" axis can always be mapped to V). Also, I don't mind if different, nonconnected parts of the UV map are overlapping. Basically, I just want to remove seams as good as possible from the mesh, while applying the tiled texture. Can anybody think of a good algorithm to do that? Possibly even one that would generate no seams at all? (This should be possible since the cliffs are, at least on one level, at most topologically equivalent to a cylinder) My only idea so far is to compute a "perfect" projection for each triangle and stuff the edge conditions into a linear equations solver, possibly with a finitefield for the "wraparound" effect, but that seems like a huge overkill, especially since I want to generate this at runtime. Thanks, Marius 
From: Staffan Langin <staffan.langin@ep...>  20090919 15:23:41

Hi there Gino, As you most probably already know, Cholesky decomposition can only be applied to a symmetric, PSD matrix. Even if the matrices only contain rotational transformations, I don't believe Y^T * D * Y generally would result in a symmetric, PSD matrix. In particular I don't believe the assertion C = U^T * U and D = V^T * V is generally true for matrices containing rotational transformations, since that implies that C and D are symmetric and PSD. Best regards, Staffan Langin Original Message From: Gino van den Bergen [mailto:gino.vandenbergen@...] Sent: den 18 september 2009 09:59 To: Game Development Algorithms Subject: Re: [Algorithms] solving for multiple matrices If Y can be considered a rotation then Y is orthogonal and thus Y^1 = Y^T, in which case this equation can be solved through Cholesky decomposition: For C = Y^T * D * Y, let's decompose C = U^T * U, and D = V^T * V then U^T U = Y^T * V^T * V * Y = (V * Y) ^T * (V * Y) this gives U = V * Y and thus Y = V^1 * U Basically you are taking the square root of a matrix. Hope this helps, Gino Andras Balogh wrote: > Both X and Y matrices represent a simple translation and rotation. For the > case of the Y matrix, the translation part will likely to be very small, > so I could probably pretend it's only rotation. > > What I would really like though, is to find a solution, where I could use > more than two equations, eg: > A1 = X * B1 * Y > A2 = X * B2 * Y > A3 = X * B3 * Y > ... > An = X * Bn * Y > > And then compute a least squares solution from this overconstrained > system. > BTW, when I said that I'm looking for an analytical solution, I just meant > something that is not based on an iterative approach. As long as I can get > to a part where I have to solve a large system of overconstrained linear > equations, I'm home. Unfortunately, I don't know how to make this linear.. > > > Andras > > > > > On Thu, 17 Sep 2009 16:32:25 0600, Jon Watte <jwatte@...> wrote: > > >> Andras Balogh wrote: >> >>> Then it becomes: >>> C = Y^1 * D * Y >>> >>> Now, how do I solve this for Y? This form lookes strangely familiar, >>> but I >>> cannot figure out what to do from here (wish I knew how to Google this >>> ;). >>> Hopefully there's an analytic solution to this. Any ideas? >>> >>> >>> >> That's the formula for applying a rotation in the reference frame of >> another rotation. >> >> Do you know anything more about these matrices than that they are >> matrices? Are they supposed to contain no scale? No translation? If you >> can formulate them as quaternions, writing out the analytical answer is >> a lot simpler :) >> >> Sincerely, >> >> jw >> >> >> >> > > > >   > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >   Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 912, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Staffan Langin <staffan.langin@ep...>  20090919 15:11:55

Hi there Andras, C = Y^1 * D * Y can be linearized by multiplying by Y (from the left). <=> Y*C=D*Y The equationsystem, Y*C=D*Y, is trivial to reformulate to the more common form Ax=b. Best regards, Staffan Langin Original Message From: Andras Balogh [mailto:andras.balogh@...] Sent: den 17 september 2009 21:38 To: gdalgorithmslist@... Subject: [Algorithms] solving for multiple matrices Hi, I have a chain of transformations with multiple unknown (but fixed!) transforms. What I do know is the end result transformation and some of the transformations in between, and I know these for multiple frames. So from here, I'd like to compute the unknowns. Here it is in more formal version: I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1, A2, B1 and B2, and also know this: A1 = X * B1 * Y A2 = X * B2 * Y I can compute X from the first equation: X = A1 * Y^1 * B1^1 And substitute it into the second: A2 = A1 * Y^1 * B1^1 * B2 * y Assigning: C = A1^1 * A2 D = B1^1 * B2 Then it becomes: C = Y^1 * D * Y Now, how do I solve this for Y? This form lookes strangely familiar, but I cannot figure out what to do from here (wish I knew how to Google this ;). Hopefully there's an analytic solution to this. Any ideas? Thanks, Andras   Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 912, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Andras Balogh <andras.balogh@gm...>  20090918 22:11:45

Well, I'm not sure how a different factorization will help, but I'll look into that. At the same time, I'm also starting to consider an iterative approach. What do you guys think? It seems to me that this is basically an inverse kinematics problem, right? Any pointers/advice, in case I'll decide to take that route? Thanks, Andras On Fri, 18 Sep 2009 10:44:12 0600, Bill Baxter <wbaxter@...> wrote: > That was my first thought too, but you don't need to a *Cholesky* > decomp on C and D. Another kind of factorization will do, like a > diagonalization  > http://en.wikipedia.org/wiki/Square_root_of_a_matrix > > bb > > On Fri, Sep 18, 2009 at 7:51 AM, Andras Balogh <andras.balogh@...> > wrote: >> Hmm, I just looked up Cholesky decomposition, and it says you can only >> do >> that if the matrix is symmetric and positive definite. Since the >> original >> definition of C = A1^1 * A2, where A1 and A2 both contain arbitrary >> translation and rotation, I don't think C will be symmetric. Or am I >> missing something? >> >> Andras >> >> >> On Fri, 18 Sep 2009 01:58:41 0600, Gino van den Bergen >> <gino.vandenbergen@...> wrote: >> >>> If Y can be considered a rotation then Y is orthogonal and thus Y^1 = >>> Y^T, in which case this equation can be solved through Cholesky >>> decomposition: >>> >>> For C = Y^T * D * Y, let's decompose >>> >>> C = U^T * U, and >>> D = V^T * V >>> >>> then >>> >>> U^T U = Y^T * V^T * V * Y >>> = (V * Y) ^T * (V * Y) >>> >>> this gives U = V * Y >>> >>> and thus Y = V^1 * U >>> >>> Basically you are taking the square root of a matrix. >>> >>> Hope this helps, >>> >>> Gino >>> >>> >>> >>> Andras Balogh wrote: >>>> Both X and Y matrices represent a simple translation and rotation. For >>>> the >>>> case of the Y matrix, the translation part will likely to be very >>>> small, >>>> so I could probably pretend it's only rotation. >>>> >>>> What I would really like though, is to find a solution, where I could >>>> use >>>> more than two equations, eg: >>>> A1 = X * B1 * Y >>>> A2 = X * B2 * Y >>>> A3 = X * B3 * Y >>>> ... >>>> An = X * Bn * Y >>>> >>>> And then compute a least squares solution from this overconstrained >>>> system. >>>> BTW, when I said that I'm looking for an analytical solution, I just >>>> meant >>>> something that is not based on an iterative approach. As long as I can >>>> get >>>> to a part where I have to solve a large system of overconstrained >>>> linear >>>> equations, I'm home. Unfortunately, I don't know how to make this >>>> linear.. >>>> >>>> >>>> Andras >>>> >>>> >>>> >>>> >>>> On Thu, 17 Sep 2009 16:32:25 0600, Jon Watte <jwatte@...> >>>> wrote: >>>> >>>> >>>>> Andras Balogh wrote: >>>>> >>>>>> Then it becomes: >>>>>> C = Y^1 * D * Y >>>>>> >>>>>> Now, how do I solve this for Y? This form lookes strangely familiar, >>>>>> but I >>>>>> cannot figure out what to do from here (wish I knew how to Google >>>>>> this >>>>>> ;). >>>>>> Hopefully there's an analytic solution to this. Any ideas? >>>>>> >>>>>> >>>>>> >>>>> That's the formula for applying a rotation in the reference frame of >>>>> another rotation. >>>>> >>>>> Do you know anything more about these matrices than that they are >>>>> matrices? Are they supposed to contain no scale? No translation? If >>>>> you >>>>> can formulate them as quaternions, writing out the analytical answer >>>>> is >>>>> a lot simpler :) >>>>> >>>>> Sincerely, >>>>> >>>>> jw >>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> >>>>  >>>> Come build with us! The BlackBerry® Developer Conference in SF, CA >>>> is the only developer event you need to attend this year. Jumpstart >>>> your >>>> developing skills, take BlackBerry mobile applications to market and >>>> stay >>>> ahead of the curve. Join us from November 912, 2009. Register >>>> now! >>>> http://p.sf.net/sfu/devconf >>>> _______________________________________________ >>>> GDAlgorithmslist mailing list >>>> GDAlgorithmslist@... >>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >>>> Archives: >>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >>>> >>> >>> >>>  >>> Come build with us! The BlackBerry® Developer Conference in SF, CA >>> is the only developer event you need to attend this year. Jumpstart >>> your >>> developing skills, take BlackBerry mobile applications to market and >>> stay >>> ahead of the curve. Join us from November 912, 2009. Register >>> now! >>> http://p.sf.net/sfu/devconf >>> _______________________________________________ >>> GDAlgorithmslist mailing list >>> GDAlgorithmslist@... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >> >> >> >>  >> Come build with us! The BlackBerry® Developer Conference in SF, CA >> is the only developer event you need to attend this year. Jumpstart your >> developing skills, take BlackBerry mobile applications to market and >> stay >> ahead of the curve. Join us from November 912, 2009. Register >> now! >> http://p.sf.net/sfu/devconf >> _______________________________________________ >> GDAlgorithmslist mailing list >> GDAlgorithmslist@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >> > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register > now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Bill Baxter <wbaxter@gm...>  20090918 16:44:44

That was my first thought too, but you don't need to a *Cholesky* decomp on C and D. Another kind of factorization will do, like a diagonalization  http://en.wikipedia.org/wiki/Square_root_of_a_matrix bb On Fri, Sep 18, 2009 at 7:51 AM, Andras Balogh <andras.balogh@...> wrote: > Hmm, I just looked up Cholesky decomposition, and it says you can only do > that if the matrix is symmetric and positive definite. Since the original > definition of C = A1^1 * A2, where A1 and A2 both contain arbitrary > translation and rotation, I don't think C will be symmetric. Or am I > missing something? > > Andras > > > On Fri, 18 Sep 2009 01:58:41 0600, Gino van den Bergen > <gino.vandenbergen@...> wrote: > >> If Y can be considered a rotation then Y is orthogonal and thus Y^1 = >> Y^T, in which case this equation can be solved through Cholesky >> decomposition: >> >> For C = Y^T * D * Y, let's decompose >> >> C = U^T * U, and >> D = V^T * V >> >> then >> >> U^T U = Y^T * V^T * V * Y >> = (V * Y) ^T * (V * Y) >> >> this gives U = V * Y >> >> and thus Y = V^1 * U >> >> Basically you are taking the square root of a matrix. >> >> Hope this helps, >> >> Gino >> >> >> >> Andras Balogh wrote: >>> Both X and Y matrices represent a simple translation and rotation. For >>> the >>> case of the Y matrix, the translation part will likely to be very small, >>> so I could probably pretend it's only rotation. >>> >>> What I would really like though, is to find a solution, where I could >>> use >>> more than two equations, eg: >>> A1 = X * B1 * Y >>> A2 = X * B2 * Y >>> A3 = X * B3 * Y >>> ... >>> An = X * Bn * Y >>> >>> And then compute a least squares solution from this overconstrained >>> system. >>> BTW, when I said that I'm looking for an analytical solution, I just >>> meant >>> something that is not based on an iterative approach. As long as I can >>> get >>> to a part where I have to solve a large system of overconstrained >>> linear >>> equations, I'm home. Unfortunately, I don't know how to make this >>> linear.. >>> >>> >>> Andras >>> >>> >>> >>> >>> On Thu, 17 Sep 2009 16:32:25 0600, Jon Watte <jwatte@...> wrote: >>> >>> >>>> Andras Balogh wrote: >>>> >>>>> Then it becomes: >>>>> C = Y^1 * D * Y >>>>> >>>>> Now, how do I solve this for Y? This form lookes strangely familiar, >>>>> but I >>>>> cannot figure out what to do from here (wish I knew how to Google this >>>>> ;). >>>>> Hopefully there's an analytic solution to this. Any ideas? >>>>> >>>>> >>>>> >>>> That's the formula for applying a rotation in the reference frame of >>>> another rotation. >>>> >>>> Do you know anything more about these matrices than that they are >>>> matrices? Are they supposed to contain no scale? No translation? If you >>>> can formulate them as quaternions, writing out the analytical answer is >>>> a lot simpler :) >>>> >>>> Sincerely, >>>> >>>> jw >>>> >>>> >>>> >>>> >>> >>> >>> >>>  >>> Come build with us! The BlackBerry® Developer Conference in SF, CA >>> is the only developer event you need to attend this year. Jumpstart your >>> developing skills, take BlackBerry mobile applications to market and >>> stay >>> ahead of the curve. Join us from November 912, 2009. Register >>> now! >>> http://p.sf.net/sfu/devconf >>> _______________________________________________ >>> GDAlgorithmslist mailing list >>> GDAlgorithmslist@... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >>> >> >> >>  >> Come build with us! The BlackBerry® Developer Conference in SF, CA >> is the only developer event you need to attend this year. Jumpstart your >> developing skills, take BlackBerry mobile applications to market and stay >> ahead of the curve. Join us from November 912, 2009. Register >> now! >> http://p.sf.net/sfu/devconf >> _______________________________________________ >> GDAlgorithmslist mailing list >> GDAlgorithmslist@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Nguyen Binh <ngbinh@gm...>  20090918 15:36:45

You gotta be more precise about your definition of "transformation matrix" here. Normally, we refer to them as "rotation matrix" which is a member of SO(3) group. This type of group has been extensively studied and there are many mathematical tools for you to use. If you refer to them as homogeneous transformation which also contains translation then they belong to the set SO(3)xR^3. I don't think you can do a lot here. Note that when talking about symmetry, people usually mean "rotation matrix" as homogeneous matrix is not symmetry by definition.  Binh Nguyen Computer Science Department Rensselaer Polytechnic Institute Troy, NY, 12180  On Fri, Sep 18, 2009 at 10:51 AM, Andras Balogh <andras.balogh@...> wrote: > Hmm, I just looked up Cholesky decomposition, and it says you can only do > that if the matrix is symmetric and positive definite. Since the original > definition of C = A1^1 * A2, where A1 and A2 both contain arbitrary > translation and rotation, I don't think C will be symmetric. Or am I > missing something? > > Andras > > > On Fri, 18 Sep 2009 01:58:41 0600, Gino van den Bergen > <gino.vandenbergen@...> wrote: > >> If Y can be considered a rotation then Y is orthogonal and thus Y^1 = >> Y^T, in which case this equation can be solved through Cholesky >> decomposition: >> >> For C = Y^T * D * Y, let's decompose >> >> C = U^T * U, and >> D = V^T * V >> >> then >> >> U^T U = Y^T * V^T * V * Y >> = (V * Y) ^T * (V * Y) >> >> this gives U = V * Y >> >> and thus Y = V^1 * U >> >> Basically you are taking the square root of a matrix. >> >> Hope this helps, >> >> Gino >> >> >> >> Andras Balogh wrote: >>> Both X and Y matrices represent a simple translation and rotation. For >>> the >>> case of the Y matrix, the translation part will likely to be very small, >>> so I could probably pretend it's only rotation. >>> >>> What I would really like though, is to find a solution, where I could >>> use >>> more than two equations, eg: >>> A1 = X * B1 * Y >>> A2 = X * B2 * Y >>> A3 = X * B3 * Y >>> ... >>> An = X * Bn * Y >>> >>> And then compute a least squares solution from this overconstrained >>> system. >>> BTW, when I said that I'm looking for an analytical solution, I just >>> meant >>> something that is not based on an iterative approach. As long as I can >>> get >>> to a part where I have to solve a large system of overconstrained >>> linear >>> equations, I'm home. Unfortunately, I don't know how to make this >>> linear.. >>> >>> >>> Andras >>> >>> >>> >>> >>> On Thu, 17 Sep 2009 16:32:25 0600, Jon Watte <jwatte@...> wrote: >>> >>> >>>> Andras Balogh wrote: >>>> >>>>> Then it becomes: >>>>> C = Y^1 * D * Y >>>>> >>>>> Now, how do I solve this for Y? This form lookes strangely familiar, >>>>> but I >>>>> cannot figure out what to do from here (wish I knew how to Google this >>>>> ;). >>>>> Hopefully there's an analytic solution to this. Any ideas? >>>>> >>>>> >>>>> >>>> That's the formula for applying a rotation in the reference frame of >>>> another rotation. >>>> >>>> Do you know anything more about these matrices than that they are >>>> matrices? Are they supposed to contain no scale? No translation? If you >>>> can formulate them as quaternions, writing out the analytical answer is >>>> a lot simpler :) >>>> >>>> Sincerely, >>>> >>>> jw >>>> >>>> >>>> >>>> >>> >>> >>> >>>  >>> Come build with us! The BlackBerry® Developer Conference in SF, CA >>> is the only developer event you need to attend this year. Jumpstart your >>> developing skills, take BlackBerry mobile applications to market and >>> stay >>> ahead of the curve. Join us from November 912, 2009. Register >>> now! >>> http://p.sf.net/sfu/devconf >>> _______________________________________________ >>> GDAlgorithmslist mailing list >>> GDAlgorithmslist@... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >>> >> >> >>  >> Come build with us! The BlackBerry® Developer Conference in SF, CA >> is the only developer event you need to attend this year. Jumpstart your >> developing skills, take BlackBerry mobile applications to market and stay >> ahead of the curve. Join us from November 912, 2009. Register >> now! >> http://p.sf.net/sfu/devconf >> _______________________________________________ >> GDAlgorithmslist mailing list >> GDAlgorithmslist@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Andras Balogh <andras.balogh@gm...>  20090918 14:52:18

Hmm, I just looked up Cholesky decomposition, and it says you can only do that if the matrix is symmetric and positive definite. Since the original definition of C = A1^1 * A2, where A1 and A2 both contain arbitrary translation and rotation, I don't think C will be symmetric. Or am I missing something? Andras On Fri, 18 Sep 2009 01:58:41 0600, Gino van den Bergen <gino.vandenbergen@...> wrote: > If Y can be considered a rotation then Y is orthogonal and thus Y^1 = > Y^T, in which case this equation can be solved through Cholesky > decomposition: > > For C = Y^T * D * Y, let's decompose > > C = U^T * U, and > D = V^T * V > > then > > U^T U = Y^T * V^T * V * Y > = (V * Y) ^T * (V * Y) > > this gives U = V * Y > > and thus Y = V^1 * U > > Basically you are taking the square root of a matrix. > > Hope this helps, > > Gino > > > > Andras Balogh wrote: >> Both X and Y matrices represent a simple translation and rotation. For >> the >> case of the Y matrix, the translation part will likely to be very small, >> so I could probably pretend it's only rotation. >> >> What I would really like though, is to find a solution, where I could >> use >> more than two equations, eg: >> A1 = X * B1 * Y >> A2 = X * B2 * Y >> A3 = X * B3 * Y >> ... >> An = X * Bn * Y >> >> And then compute a least squares solution from this overconstrained >> system. >> BTW, when I said that I'm looking for an analytical solution, I just >> meant >> something that is not based on an iterative approach. As long as I can >> get >> to a part where I have to solve a large system of overconstrained >> linear >> equations, I'm home. Unfortunately, I don't know how to make this >> linear.. >> >> >> Andras >> >> >> >> >> On Thu, 17 Sep 2009 16:32:25 0600, Jon Watte <jwatte@...> wrote: >> >> >>> Andras Balogh wrote: >>> >>>> Then it becomes: >>>> C = Y^1 * D * Y >>>> >>>> Now, how do I solve this for Y? This form lookes strangely familiar, >>>> but I >>>> cannot figure out what to do from here (wish I knew how to Google this >>>> ;). >>>> Hopefully there's an analytic solution to this. Any ideas? >>>> >>>> >>>> >>> That's the formula for applying a rotation in the reference frame of >>> another rotation. >>> >>> Do you know anything more about these matrices than that they are >>> matrices? Are they supposed to contain no scale? No translation? If you >>> can formulate them as quaternions, writing out the analytical answer is >>> a lot simpler :) >>> >>> Sincerely, >>> >>> jw >>> >>> >>> >>> >> >> >> >>  >> Come build with us! The BlackBerry® Developer Conference in SF, CA >> is the only developer event you need to attend this year. Jumpstart your >> developing skills, take BlackBerry mobile applications to market and >> stay >> ahead of the curve. Join us from November 912, 2009. Register >> now! >> http://p.sf.net/sfu/devconf >> _______________________________________________ >> GDAlgorithmslist mailing list >> GDAlgorithmslist@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist >> > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register > now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Gino van den Bergen <gino.vandenbergen@gm...>  20090918 07:58:56

If Y can be considered a rotation then Y is orthogonal and thus Y^1 = Y^T, in which case this equation can be solved through Cholesky decomposition: For C = Y^T * D * Y, let's decompose C = U^T * U, and D = V^T * V then U^T U = Y^T * V^T * V * Y = (V * Y) ^T * (V * Y) this gives U = V * Y and thus Y = V^1 * U Basically you are taking the square root of a matrix. Hope this helps, Gino Andras Balogh wrote: > Both X and Y matrices represent a simple translation and rotation. For the > case of the Y matrix, the translation part will likely to be very small, > so I could probably pretend it's only rotation. > > What I would really like though, is to find a solution, where I could use > more than two equations, eg: > A1 = X * B1 * Y > A2 = X * B2 * Y > A3 = X * B3 * Y > ... > An = X * Bn * Y > > And then compute a least squares solution from this overconstrained > system. > BTW, when I said that I'm looking for an analytical solution, I just meant > something that is not based on an iterative approach. As long as I can get > to a part where I have to solve a large system of overconstrained linear > equations, I'm home. Unfortunately, I don't know how to make this linear.. > > > Andras > > > > > On Thu, 17 Sep 2009 16:32:25 0600, Jon Watte <jwatte@...> wrote: > > >> Andras Balogh wrote: >> >>> Then it becomes: >>> C = Y^1 * D * Y >>> >>> Now, how do I solve this for Y? This form lookes strangely familiar, >>> but I >>> cannot figure out what to do from here (wish I knew how to Google this >>> ;). >>> Hopefully there's an analytic solution to this. Any ideas? >>> >>> >>> >> That's the formula for applying a rotation in the reference frame of >> another rotation. >> >> Do you know anything more about these matrices than that they are >> matrices? Are they supposed to contain no scale? No translation? If you >> can formulate them as quaternions, writing out the analytical answer is >> a lot simpler :) >> >> Sincerely, >> >> jw >> >> >> >> > > > >  > Come build with us! The BlackBerry® Developer Conference in SF, CA > is the only developer event you need to attend this year. Jumpstart your > developing skills, take BlackBerry mobile applications to market and stay > ahead of the curve. Join us from November 912, 2009. Register now! > http://p.sf.net/sfu/devconf > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Andras Balogh <andras.balogh@gm...>  20090917 23:46:43

Both X and Y matrices represent a simple translation and rotation. For the case of the Y matrix, the translation part will likely to be very small, so I could probably pretend it's only rotation. What I would really like though, is to find a solution, where I could use more than two equations, eg: A1 = X * B1 * Y A2 = X * B2 * Y A3 = X * B3 * Y ... An = X * Bn * Y And then compute a least squares solution from this overconstrained system. BTW, when I said that I'm looking for an analytical solution, I just meant something that is not based on an iterative approach. As long as I can get to a part where I have to solve a large system of overconstrained linear equations, I'm home. Unfortunately, I don't know how to make this linear.. Andras On Thu, 17 Sep 2009 16:32:25 0600, Jon Watte <jwatte@...> wrote: > Andras Balogh wrote: >> >> Then it becomes: >> C = Y^1 * D * Y >> >> Now, how do I solve this for Y? This form lookes strangely familiar, >> but I >> cannot figure out what to do from here (wish I knew how to Google this >> ;). >> Hopefully there's an analytic solution to this. Any ideas? >> >> > > That's the formula for applying a rotation in the reference frame of > another rotation. > > Do you know anything more about these matrices than that they are > matrices? Are they supposed to contain no scale? No translation? If you > can formulate them as quaternions, writing out the analytical answer is > a lot simpler :) > > Sincerely, > > jw > > > 
From: Bill Baxter <wbaxter@gm...>  20090917 22:38:00

> Original Message > From: Andras Balogh [mailto:andras.balogh@...] > Sent: Thursday, September 17, 2009 12:38 PM > To: gdalgorithmslist@... > Subject: [Algorithms] solving for multiple matrices > > Hi, I have a chain of transformations with multiple unknown (but fixed!) transforms. What I do know is the end result transformation and some of the transformations in between, and I know these for multiple frames. So > from here, I'd like to compute the unknowns. Here it is in more formal > version: > > I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1, A2, B1 and B2, and also know this: > A1 = X * B1 * Y > A2 = X * B2 * Y > > I can compute X from the first equation: > X = A1 * Y^1 * B1^1 > > And substitute it into the second: > A2 = A1 * Y^1 * B1^1 * B2 * y > > Assigning: > C = A1^1 * A2 > D = B1^1 * B2 > > Then it becomes: > C = Y^1 * D * Y > > Now, how do I solve this for Y? This form lookes strangely familiar, but I cannot figure out what to do from here (wish I knew how to Google this ;). > Hopefully there's an analytic solution to this. Any ideas? > > Thanks, > > > > Andras It has the form of a similarity transformation, if that helps. http://mathworld.wolfram.com/SimilarityTransformation.html Similarity transforms preserve eigenvalues and consequently the trace and determinant of the matrix applied to, so if C and D don't have the same trace and determinant, then your Y doesn't exist. bb 
From: Jon Watte <jwatte@gm...>  20090917 22:32:43

Andras Balogh wrote: > > Then it becomes: > C = Y^1 * D * Y > > Now, how do I solve this for Y? This form lookes strangely familiar, but I > cannot figure out what to do from here (wish I knew how to Google this ;). > Hopefully there's an analytic solution to this. Any ideas? > > That's the formula for applying a rotation in the reference frame of another rotation. Do you know anything more about these matrices than that they are matrices? Are they supposed to contain no scale? No translation? If you can formulate them as quaternions, writing out the analytical answer is a lot simpler :) Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: David Bennett <dbennett@na...>  20090917 22:08:33

This is just a shot in the dark, but the wikipedia entry on "QZ decomposition" looks a lot like your original statement of the problem  http://en.wikipedia.org/wiki/Matrix_decomposition#QZ_decomposition I don't know if X & Y are "unitary" matrices though. I guess that depends on which kinds of transforms you are using. Hope that helps, David Bennett NAMCO BANDAI Games America Inc. Original Message From: Andras Balogh [mailto:andras.balogh@...] Sent: Thursday, September 17, 2009 12:38 PM To: gdalgorithmslist@... Subject: [Algorithms] solving for multiple matrices Hi, I have a chain of transformations with multiple unknown (but fixed!) transforms. What I do know is the end result transformation and some of the transformations in between, and I know these for multiple frames. So from here, I'd like to compute the unknowns. Here it is in more formal version: I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1, A2, B1 and B2, and also know this: A1 = X * B1 * Y A2 = X * B2 * Y I can compute X from the first equation: X = A1 * Y^1 * B1^1 And substitute it into the second: A2 = A1 * Y^1 * B1^1 * B2 * y Assigning: C = A1^1 * A2 D = B1^1 * B2 Then it becomes: C = Y^1 * D * Y Now, how do I solve this for Y? This form lookes strangely familiar, but I cannot figure out what to do from here (wish I knew how to Google this ;). Hopefully there's an analytic solution to this. Any ideas? Thanks, Andras  Come build with us! The BlackBerry® Developer Conference in SF, CA is the only developer event you need to attend this year. Jumpstart your developing skills, take BlackBerry mobile applications to market and stay ahead of the curve. Join us from November 912, 2009. Register now! http://p.sf.net/sfu/devconf _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Andras Balogh <andras.balogh@gm...>  20090917 19:37:51

Hi, I have a chain of transformations with multiple unknown (but fixed!) transforms. What I do know is the end result transformation and some of the transformations in between, and I know these for multiple frames. So from here, I'd like to compute the unknowns. Here it is in more formal version: I'd like to find 2 unknown matrices X and Y. I have 4 known matrices A1, A2, B1 and B2, and also know this: A1 = X * B1 * Y A2 = X * B2 * Y I can compute X from the first equation: X = A1 * Y^1 * B1^1 And substitute it into the second: A2 = A1 * Y^1 * B1^1 * B2 * y Assigning: C = A1^1 * A2 D = B1^1 * B2 Then it becomes: C = Y^1 * D * Y Now, how do I solve this for Y? This form lookes strangely familiar, but I cannot figure out what to do from here (wish I knew how to Google this ;). Hopefully there's an analytic solution to this. Any ideas? Thanks, Andras 