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
(13) 
2
(10) 
3
(5) 
4
(20) 
5
(34) 
6
(16) 
7
(35) 
8
(19) 
9
(3) 
10
(2) 
11
(17) 
12
(16) 
13
(2) 
14

15
(1) 
16

17

18
(13) 
19
(21) 
20
(7) 
21
(4) 
22
(5) 
23
(1) 
24

25

26
(1) 
27

28
(7) 
29
(20) 
30
(10) 
From: Willem de Boer <wdeboer@pl...>  20050429 12:13:46

Hi, > off the top of my head, try this >=20 > x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x )  Q.w * x ) >=20 After some mulling over the result I previously obtained, I arrived at the following routine for rotating a vector=20 v by a unit quaternion q: float3 RotateVector3ByQuaternion( float3 v, float4 q ) { w =3D q.xyz; float3 vww =3D dot(v,w)*w; float3 res =3D 2.f * (vww + (q.w*q.w  0.5f) * v + q.w*cross(v,w) ); return res; } That's 1 dot product, 1 cross product, 7 adds, 11 multiplies, compared to 2 cross products, 6 adds, 6 multiplies for Christian's solution.  Willem H. de Boer Homepage: http://www.whdeboer.com=20 
From: <c.schueler@ph...>  20050429 09:16:23

off the top of my head, try this x' =3D x + 2 * cross( Q.xyz, cross( Q.xyz, x )  Q.w * x ) if it doesnt work, try changing  with + or reverse the cross prod = arguments. Original Message From: gdalgorithmslistadmin@... = [mailto:gdalgorithmslistadmin@...] On Behalf Of = Newport, Matthew Sent: Thursday, April 28, 2005 11:59 PM To: gdalgorithmslist@... Subject: [Algorithms] Fastest way to rotate a vector by a quaternion in = a shader Looking through the list archives I came across this snippet from Jarkko = Lempiainen regarding rotating a vector by a quaternion in a shader: "Yeah, last time I checked rotating a vector with a quaternion was total = of 6 instructions, which is the same as your 2*crossprod + 2 mads I = guess" I've been playing around with the definitions for quaternion = multiplication and rotating a vector by a quaternion and the best I've = been able to do is 8 instructions. Can anyone enlighten me on how it's = done in 6? Bonus points for a derivation I can follow :) This was my = best effort: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2  v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* Expanding this out and simplifying as best I could I got this down to = the following hlsl: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 vq =3D q.xyz; float3 vqcrossv =3D cross(vq, v); float3 wvplusvqcrossv =3D q.w * v + vqcrossv; float3 vqcrosswvplusvqcrossv =3D cross(vq, wvplusvqcrossv); float3 res =3D q.w * wvplusvqcrossv + vqcrosswvplusvqcrossv; res =3D dot(vq, v) * vq + res; return res; } Which works out to 8 clocks (2 cross products =3D 4 clocks, 1 dot = product, 3 mads). What's the secret of getting this down to 6? Thanks, Matt.  SF.Net email is sponsored by: Tell us your software development plans! = Take this survey and enter to win a oneyear sub to SourceForge.net Plus = IDC's 2005 lookahead and a copy of this survey Click here to start! = http://www.idcswdc.com/cgibin/survey?id=105hix _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: <c.schueler@ph...>  20050429 09:01:11

I would recommend to go for sprites. I have a dynamic sky, and I use a 32 x 64 pixel texture for the = gradient, and both the artists and I found it to be sufficient, = resolution wise. This is, I use the texture for the gradient only, no clouds, celestial = objects or flares. Christian Original Message From: gdalgorithmslistadmin@... = [mailto:gdalgorithmslistadmin@...] On Behalf Of = Megan Fox Sent: Thursday, April 28, 2005 11:46 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Sky gradients  vertex or pixel shaded? Looks nice, though I should clarify, I'm working on a freeroaming RPG  my reason for using gradients is that the entire sky system needs to = be dynamic. From sunrise to sunset to dusk to night, dynamic clouds and = weather during any of the above conditions, etc. Unless I misunderstand, yours is more of a static texture solution  = great for FPSs, but probably not ideal for my purposes? ... that said, you're controlling white point via pixel shader  = question on that: are you doing some manner of linear falloff for the = light edges? or exponential? or something else entirely? Megan Fox On 4/28/05, Emanuele Salvucci <info@...> wrote: > Objects for us too, no vertex coloring though. > =20 > We chose to use highres FDRI skyboxes. They're generated and "baked"=20 > skyes with HDRI data. White point is dynamically controlled via pixel=20 > shader: http://www.forwardgames.com ...follow the technology/research page=20 > and the highres texturing link. > =20 > A 1024x1024x6 skybox can take as little as 6 Mbytes, with no DXT1=20 > compression (blocky skyes aren't very beautiful :), compared to around = > 25Mbytes for uncompressed version, same resolution. > =20 > ...they can be layered...alpha blended...animated etc... > =20 > =20 > =20 > Best, > =20 >=20 > Emanuele Salvucci > MayaLightwave > Game Technical Artist > Lscript developer > =20 > http://www.forwardgames.com > emanueles@... > =20 > "#3. He causes things to look different so it would appear time has=20 > passed." ________________________________ >=20 > =20 > =20 > =20 >  Original Message  > From: "Megan Fox" <shalinor@...> > To: <gdalgorithmslist@...> > Sent: Thursday, April 28, 2005 7:29 PM > Subject: [Algorithms] Sky gradients  vertex or pixel shaded? >=20 > I have an excellent sky gradient system going using "just" vertex=20 > shading, where I can smoothly animate all the values, smoothly animate = > the falloff, etc... very nice... but I'm finding that the system is=20 > incapable of representing small flares, like daytime sun, short of an=20 > EXTREMELY tesselated skydome. (it of course represents large flare=20 > sunset conditions excellently, and does a great hazetosky fade, it=20 > just has trouble with small flares) >=20 > Now in our case, we're going to get around it with a sun sprite (and=20 > just alpha fade it out as we fade in the larger sunset gradient), but=20 > I'm curious, is it common to use some other method for this? Maybe=20 > people DO commonly have 30k tri hemisphere domes? Maybe pixel shading = > is the key (though I'm calling a pow at every point, that can't be a=20 > good idea for pixel shading)? >=20 > Or is our solution, just using sprites for any flares below a=20 > particular size, what most use? >=20 > Thanks, > Megan Fox >=20 >=20 >  > SF.Net email is sponsored by: Tell us your software development plans! = > Take this survey and enter to win a oneyear sub to SourceForge.net=20 > Plus IDC's 2005 lookahead and a copy of this survey Click here to=20 > start! http://www.idcswdc.com/cgibin/survey?id=105hix >=20 > _______________________________________________ > GDAlgorithmslist mailing list GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 >  SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a oneyear sub to SourceForge.net Plus IDC's 2005 lookahead and a copy of this survey Click here to start! http://www.idcswdc.com/cgibin/survey?id=105hix _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Willem de Boer <wdeboer@pl...>  20050429 08:00:00

I should mention that if you store q as (cos(theta/2), sqrt(sin(theta/2).r) you can get rid of the sqrt in the vertex shader.  Willem H. de Boer Homepage: http://www.whdeboer.com=20 > Original Message > From: gdalgorithmslistadmin@...=20 > [mailto:gdalgorithmslistadmin@...] On=20 > Behalf Of Willem de Boer > Sent: Friday, April 29, 2005 9:54 AM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Fastest way to rotate a vector by a=20 > quaternion in a shader >=20 > Okay a notsorigorous derivation of a fast rotation: >=20 > Let q=3D(cos(theta/2),sin(theta/2).r) denote a unit quaternion,=20 > representing a rotation of theta radians about the unit vector r. >=20 > It is a basic fact of linear algebra that a rotation leaves=20 > one axis invariant (which happens to be our r; hey it's an=20 > eigenvector belonging to the eigenvalue 1!), and rotates its=20 > orthogonal complement, W, a plane by theta radians. So if=20 > we orthogonally project v onto W, perform a 2d rotation in W=20 > and add v's orthogonal projection onto r to the result, we're=20 > done. This amounts to >=20 > v' =3D (v,r)r + (v  (v,r)r)cos(theta) + (r x v)sin(theta) (1) >=20 > where we have assumed a righthanded orientation, and (. x .)=20 > denotes the cross product, and (. , .) denotes the dot product. > This equation can be shown to be equivalent to conjugation, > v'=3Dqvq* where v has been mapped to the quaternion v=3D(0,v). >=20 > All we have to do now is take our quaternion, q, extract r=20 > from it as well as cos(theta/2) and sin(theta/2), use some=20 > standard trigonometric identities to get cos(theta), and=20 > sin(theta), to wit: >=20 > cos(theta) =3D 2*cos^2(theta/2)  1, and > sin(theta) =3D 2*cos(theta/2)*sin(theta/2), >=20 > and then apply equation (1) to v, and we're done! >=20 > So that's 1 dot product (v,r), 1 crossproduct (rxv), > 8 multiplies and 4 adds, and one sqrt (to get sin(theta/2)).=20 >=20 > I think that should do it, I have used Eq. (1) successfully=20 > in the past. >=20 > Cheers, >  > Willem H. de Boer > Homepage: http://www.whdeboer.com=20 >=20 >=20 >=20 >=20 >  > SF.Net email is sponsored by: Tell us your software development plans! > Take this survey and enter to win a oneyear sub to=20 > SourceForge.net Plus IDC's 2005 lookahead and a copy of this=20 > survey Click here to start! =20 > http://www.idcswdc.com/cgibin/survey?id=105hix > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 
From: Willem de Boer <wdeboer@pl...>  20050429 07:54:15

Okay a notsorigorous derivation of a fast rotation: Let q=3D(cos(theta/2),sin(theta/2).r) denote a unit quaternion, representing a rotation of theta radians about the unit vector r. It is a basic fact of linear algebra that a rotation leaves=20 one axis invariant (which happens to be our r; hey it's an=20 eigenvector belonging to the eigenvalue 1!), and rotates its=20 orthogonal complement, W, a plane by theta radians. So if=20 we orthogonally project v onto W, perform a 2d rotation in W=20 and add v's orthogonal projection onto r to the result,=20 we're done. This amounts to v' =3D (v,r)r + (v  (v,r)r)cos(theta) + (r x v)sin(theta) (1) where we have assumed a righthanded orientation, and (. x .) denotes the cross product, and (. , .) denotes the dot product. This equation can be shown to be equivalent to conjugation, v'=3Dqvq* where v has been mapped to the quaternion v=3D(0,v). All we have to do now is take our quaternion, q, extract r from it as well as cos(theta/2) and sin(theta/2), use some standard trigonometric identities to get cos(theta), and sin(theta), to wit: cos(theta) =3D 2*cos^2(theta/2)  1, and sin(theta) =3D 2*cos(theta/2)*sin(theta/2), and then apply equation (1) to v, and we're done! So that's 1 dot product (v,r), 1 crossproduct (rxv),=20 8 multiplies and 4 adds, and one sqrt (to get sin(theta/2)).=20 I think that should do it, I have used Eq. (1) successfully in the past. Cheers,  Willem H. de Boer Homepage: http://www.whdeboer.com=20 
From: Emanuele Salvucci <info@fo...>  20050428 22:45:57

Well, the skybox choice is not strictly connected with the FDRI = system...but rather as you say, with the game genre. Being the skybox just like any other "scene" for us, we could implement = some more dynamic systems too...moving fading clouds objects...layered = haze etc. But we're not at that development stage (prototype) at the = moment. That'd be good for full production though. :) I think that what you can do with just vertex coloring, you can pretty = much do with textures and less vertices. The big deal is that doing that without tex compression would be Vram = overkill just for the sky system in a full game. While if you get to keep clear quality (no blockyness due to = compression) at little Vram cost...dynamic perpixel and texture stuff = is best, IMHO. FDRI and FNTC are some kind of new techniques. Never seen something = similar around...I did my "little" research. (tons of papers and patents = of any kind) :) The material blending stuff (not on the website yet) is interesting too, = for terrain texturing and lightmapping. On our full FDRI demo scene (441 lightmaps, 512x512 each + color = textures), at 1024x768 screen resolution, GeForce 6800 GT, the pixel = shader unit is not even 40% busy. Vram used is less than 170 Mb, = including the 500k triangles geometry, screen buffer, render to texture = buffer et al. Just imagine doing that with RGBE8HDRI textures for the whole scene.=20 Unfortunately being indipendent developers we have to wait until we sign = with any publisher before releasing full infos and specs about those = systems. ...let's hope someone gets interested soon! ;) Best, Emanuele Salvucci MayaLightwave Game Technical Artist Lscript developer http://www.forwardgames.com emanueles@... "#3. He causes things to look different so it would appear time has = passed." =   Original Message =20 From: "Megan Fox" <shalinor@...> To: <gdalgorithmslist@...> Sent: Thursday, April 28, 2005 11:46 PM Subject: Re: [Algorithms] Sky gradients  vertex or pixel shaded? Looks nice, though I should clarify, I'm working on a freeroaming RPG  my reason for using gradients is that the entire sky system needs to be dynamic. From sunrise to sunset to dusk to night, dynamic clouds and weather during any of the above conditions, etc. Unless I misunderstand, yours is more of a static texture solution  great for FPSs, but probably not ideal for my purposes? ... that said, you're controlling white point via pixel shader  question on that: are you doing some manner of linear falloff for the light edges? or exponential? or something else entirely? Megan Fox On 4/28/05, Emanuele Salvucci <info@...> wrote: > Objects for us too, no vertex coloring though. > =20 > We chose to use highres FDRI skyboxes. They're generated and "baked" = skyes > with HDRI data. > White point is dynamically controlled via pixel shader: = http://www.forwardgames.com > ...follow the technology/research page and the highres texturing = link. > =20 > A 1024x1024x6 skybox can take as little as 6 Mbytes, with no DXT1 > compression (blocky skyes aren't very beautiful :), compared to around > 25Mbytes for uncompressed version, same resolution. > =20 > ...they can be layered...alpha blended...animated etc... > =20 > =20 > =20 > Best,=20 > =20 >=20 > Emanuele Salvucci > MayaLightwave > Game Technical Artist > Lscript developer > =20 > http://www.forwardgames.com > emanueles@... > =20 > "#3. He causes things to look different so it would appear time has = passed." > ________________________________ >=20 > =20 > =20 > =20 >  Original Message =20 > From: "Megan Fox" <shalinor@...> > To: <gdalgorithmslist@...> > Sent: Thursday, April 28, 2005 7:29 PM > Subject: [Algorithms] Sky gradients  vertex or pixel shaded? >=20 > I have an excellent sky gradient system going using "just" vertex > shading, where I can smoothly animate all the values, smoothly animate > the falloff, etc... very nice... but I'm finding that the system is > incapable of representing small flares, like daytime sun, short of an > EXTREMELY tesselated skydome. (it of course represents large flare > sunset conditions excellently, and does a great hazetosky fade, it > just has trouble with small flares) >=20 > Now in our case, we're going to get around it with a sun sprite (and > just alpha fade it out as we fade in the larger sunset gradient), but > I'm curious, is it common to use some other method for this? Maybe > people DO commonly have 30k tri hemisphere domes? Maybe pixel shading > is the key (though I'm calling a pow at every point, that can't be a > good idea for pixel shading)? >=20 > Or is our solution, just using sprites for any flares below a > particular size, what most use? >=20 > Thanks, > Megan Fox >=20 >=20 >  > SF.Net email is sponsored by: Tell us your software development plans! > Take this survey and enter to win a oneyear sub to SourceForge.net > Plus IDC's 2005 lookahead and a copy of this survey > Click here to start!=20 > http://www.idcswdc.com/cgibin/survey?id=105hix >=20 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 >  SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a oneyear sub to SourceForge.net Plus IDC's 2005 lookahead and a copy of this survey Click here to start! http://www.idcswdc.com/cgibin/survey?id=105hix _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Newport, Matthew <mnewport@ea...>  20050428 21:59:28

Looking through the list archives I came across this snippet from Jarkko Lempiainen regarding rotating a vector by a quaternion in a shader: "Yeah, last time I checked rotating a vector with a quaternion was total of 6 instructions, which is the same as your 2*crossprod + 2 mads I guess" I've been playing around with the definitions for quaternion multiplication and rotating a vector by a quaternion and the best I've been able to do is 8 instructions. Can anyone enlighten me on how it's done in 6? Bonus points for a derivation I can follow :) This was my best effort: Multiplication of two quaternions: Qr =3D Q1.Q2 =3D ( w1.w2  v1.v2, w1.v2 + w2.v1 + v1 x v2 ) where v1 =3D (x,y,z) of Q1 w1 =3D (w) of Q1 v2 =3D (x,y,z) of Q2 w2 =3D (w) of Q2 and both . and x are the standard vector dot and cross products. Rotate a vector by a quaternion: v' =3D q.v.q* Expanding this out and simplifying as best I could I got this down to the following hlsl: float3 RotateVectorByQuaternion(float3 v, float4 q) { float3 vq =3D q.xyz; float3 vqcrossv =3D cross(vq, v); float3 wvplusvqcrossv =3D q.w * v + vqcrossv; float3 vqcrosswvplusvqcrossv =3D cross(vq, wvplusvqcrossv); float3 res =3D q.w * wvplusvqcrossv + vqcrosswvplusvqcrossv; res =3D dot(vq, v) * vq + res; return res; } Which works out to 8 clocks (2 cross products =3D 4 clocks, 1 dot = product, 3 mads). What's the secret of getting this down to 6? Thanks, Matt. 
From: Megan Fox <shalinor@gm...>  20050428 21:46:30

Looks nice, though I should clarify, I'm working on a freeroaming RPG  my reason for using gradients is that the entire sky system needs to be dynamic. From sunrise to sunset to dusk to night, dynamic clouds and weather during any of the above conditions, etc. Unless I misunderstand, yours is more of a static texture solution  great for FPSs, but probably not ideal for my purposes? ... that said, you're controlling white point via pixel shader  question on that: are you doing some manner of linear falloff for the light edges? or exponential? or something else entirely? Megan Fox On 4/28/05, Emanuele Salvucci <info@...> wrote: > Objects for us too, no vertex coloring though. > =20 > We chose to use highres FDRI skyboxes. They're generated and "baked" sky= es > with HDRI data. > White point is dynamically controlled via pixel shader: http://www.forwardgames.= com > ...follow the technology/research page and the highres texturing link. > =20 > A 1024x1024x6 skybox can take as little as 6 Mbytes, with no DXT1 > compression (blocky skyes aren't very beautiful :), compared to around > 25Mbytes for uncompressed version, same resolution. > =20 > ...they can be layered...alpha blended...animated etc... > =20 > =20 > =20 > Best,=20 > =20 >=20 > Emanuele Salvucci > MayaLightwave > Game Technical Artist > Lscript developer > =20 > http://www.forwardgames.com > emanueles@... > =20 > "#3. He causes things to look different so it would appear time has passe= d." > ________________________________ >=20 > =20 > =20 > =20 >  Original Message =20 > From: "Megan Fox" <shalinor@...> > To: <gdalgorithmslist@...> > Sent: Thursday, April 28, 2005 7:29 PM > Subject: [Algorithms] Sky gradients  vertex or pixel shaded? >=20 > I have an excellent sky gradient system going using "just" vertex > shading, where I can smoothly animate all the values, smoothly animate > the falloff, etc... very nice... but I'm finding that the system is > incapable of representing small flares, like daytime sun, short of an > EXTREMELY tesselated skydome. (it of course represents large flare > sunset conditions excellently, and does a great hazetosky fade, it > just has trouble with small flares) >=20 > Now in our case, we're going to get around it with a sun sprite (and > just alpha fade it out as we fade in the larger sunset gradient), but > I'm curious, is it common to use some other method for this? Maybe > people DO commonly have 30k tri hemisphere domes? Maybe pixel shading > is the key (though I'm calling a pow at every point, that can't be a > good idea for pixel shading)? >=20 > Or is our solution, just using sprites for any flares below a > particular size, what most use? >=20 > Thanks, > Megan Fox >=20 >=20 >  > SF.Net email is sponsored by: Tell us your software development plans! > Take this survey and enter to win a oneyear sub to SourceForge.net > Plus IDC's 2005 lookahead and a copy of this survey > Click here to start!=20 > http://www.idcswdc.com/cgibin/survey?id=105hix >=20 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 > 
From: Emanuele Salvucci <info@fo...>  20050428 18:43:07

Objects for us too, no vertex coloring though. We chose to use highres FDRI skyboxes. They're generated and "baked" = skyes with HDRI data. White point is dynamically controlled via pixel shader: = http://www.forwardgames.com ...follow the technology/research page and the = highres texturing link. A 1024x1024x6 skybox can take as little as 6 Mbytes, with no DXT1 = compression (blocky skyes aren't very beautiful :), compared to around = 25Mbytes for uncompressed version, same resolution. ...they can be layered...alpha blended...animated etc... Best, Emanuele Salvucci MayaLightwave Game Technical Artist Lscript developer http://www.forwardgames.com emanueles@... "#3. He causes things to look different so it would appear time has = passed." =   Original Message =20 From: "Megan Fox" <shalinor@...> To: <gdalgorithmslist@...> Sent: Thursday, April 28, 2005 7:29 PM Subject: [Algorithms] Sky gradients  vertex or pixel shaded? I have an excellent sky gradient system going using "just" vertex shading, where I can smoothly animate all the values, smoothly animate the falloff, etc... very nice... but I'm finding that the system is incapable of representing small flares, like daytime sun, short of an EXTREMELY tesselated skydome. (it of course represents large flare sunset conditions excellently, and does a great hazetosky fade, it just has trouble with small flares) Now in our case, we're going to get around it with a sun sprite (and just alpha fade it out as we fade in the larger sunset gradient), but I'm curious, is it common to use some other method for this? Maybe people DO commonly have 30k tri hemisphere domes? Maybe pixel shading is the key (though I'm calling a pow at every point, that can't be a good idea for pixel shading)? Or is our solution, just using sprites for any flares below a particular size, what most use? Thanks, Megan Fox  SF.Net email is sponsored by: Tell us your software development plans! Take this survey and enter to win a oneyear sub to SourceForge.net Plus IDC's 2005 lookahead and a copy of this survey Click here to start! http://www.idcswdc.com/cgibin/survey?id=105hix _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: J. Perkins <starkos@gm...>  20050428 18:11:10

On 4/28/05, Megan Fox <shalinor@...> wrote: > Or is our solution, just using sprites for any flares below a > particular size, what most use? It has been quite some time since I last looked at it, but FlightGear (http://www.flightgear.org) has a great looking sky including sun, moon, and stars, and it is opensource. Might be a good place to look for ideas. From memory, I believe they were using a sprite for sun and moon, don't recall how they did the stars. Jason 
From: Chris Butcher \(BUNGIE\) <cbutcher@mi...>  20050428 18:05:39

> Original Message > From: gdalgorithmslistadmin@... [mailto:gdalgorithms > listadmin@...] On Behalf Of Megan Fox > Sent: Thursday, April 28, 2005 10:30 > To: gdalgorithmslist@... > Subject: [Algorithms] Sky gradients  vertex or pixel shaded? >=20 > Now in our case, we're going to get around it with a sun sprite (and > just alpha fade it out as we fade in the larger sunset gradient), but > I'm curious, is it common to use some other method for this? Maybe > people DO commonly have 30k tri hemisphere domes? Maybe pixel shading > is the key (though I'm calling a pow at every point, that can't be a > good idea for pixel shading)? >=20 > Or is our solution, just using sprites for any flares below a > particular size, what most use? >=20 Our skies are just objects like any other. So, it is up the artists to use whatever techniques are at their disposal. They rarely use vertex coloring, mostly preferring to use small textures.  Chris Butcher Networking & Simulation Lead Halo 2  Bungie Studios butcher@... 
From: Megan Fox <shalinor@gm...>  20050428 17:29:42

I have an excellent sky gradient system going using "just" vertex shading, where I can smoothly animate all the values, smoothly animate the falloff, etc... very nice... but I'm finding that the system is incapable of representing small flares, like daytime sun, short of an EXTREMELY tesselated skydome. (it of course represents large flare sunset conditions excellently, and does a great hazetosky fade, it just has trouble with small flares) Now in our case, we're going to get around it with a sun sprite (and just alpha fade it out as we fade in the larger sunset gradient), but I'm curious, is it common to use some other method for this? Maybe people DO commonly have 30k tri hemisphere domes? Maybe pixel shading is the key (though I'm calling a pow at every point, that can't be a good idea for pixel shading)? Or is our solution, just using sprites for any flares below a particular size, what most use? Thanks, Megan Fox 
From: Awen Limbourg <alimbourg@ed...>  20050426 07:41:57

After a mail exchange with Sindharta, i'm forwarding to the list: i'll = be glad if it could help someone else. OK, Translation data to Rotation, i'm not adressing the filtering = problem here: Sindharta's Mocap file is a C3D: it contains (global) position streams = for each joint origin of a skeleton: To answer your problem, we first need to build a skeleton: A skeleton is roughly a collection of 'bones', with hierarchy = information (to which parent is it linked...), and some local (relative to its = parent) transform values as references (aka the bind pose). A bone could look = like this ('C' speaking) struct Bone { char Name[]=20 Bone* Parent  or  int ParentIndex; Matrix4 ReferenceTransform (in 'local space') }; Bone Skeleton[48]; ***************** (From now, i'm assuming that marker positions in c3d are global = coordinates (world coordinates), and describing transformations of the origin of bones... bone lengths don't vary) Skeleton bind pose is important because we're going to use it as a = reference to compute how much rotation between an anim frame, and this pose, did occur. To build it, we need the position of each bone *origin* (hence my questions about the C3D you are using). Ususally a bind pose is = describing some TPose (used while rigging a character because it's easier to skin, = see http://web.alfredstate.edu/ciat/tutorials/SkeletonSetup.htm ) but you = can choose any frame of one of your anim as a reference.=20 To get a hierarchy structure, we need to know which bone is linked to = wich one, if you don't have any specifications file, you'll have to do this = 'by hand', guessing the relation parentchild using bone names: R and L means right and left (used for arms and legs) C7 and T10 could be part of the spine For example, here is Vicon's nomenclature for names and hierarchy fe: " BuildSkeleton(LHipJoint,LHJ,Pelvis) BuildSkeleton(RHipJoint,RHJ,Pelvis) BuildSkeleton(LFemur,LFE,LHipJoint) BuildSkeleton(RFemur,RFE,RHipJoint) BuildSkeleton(LTibia,LTI,LFemur) BuildSkeleton(RTibia,RTI,RFemur) BuildSkeleton(LFoot,LFO,LTibia) BuildSkeleton(RFoot,RFO,RTibia) BuildSkeleton(LToes,LTO,LFoot) BuildSkeleton(RToes,RTO,RFoot) BuildSkeleton(Torso,TRX,Pelvis) BuildSkeleton(Neck,NEC,Torso) BuildSkeleton(Head,HED,Neck) BuildSkeleton(LShoulder,LSJ,Torso) BuildSkeleton(RShoulder,RSJ,Torso) BuildSkeleton(LHumerus,LHU,LShoulder) BuildSkeleton(RHumerus,RHU,RShoulder) BuildSkeleton(LRadius,LRA,LHumerus) BuildSkeleton(RRadius,RRA,RHumerus) BuildSkeleton(LHand,LHN,LRadius) BuildSkeleton(RHand,RHN,RRadius) BuildSkeleton(LFingers,LFI,LHand) BuildSkeleton(RFingers,RFI,RHand) BuildSkeleton(LThumb,LTB,LRadius) BuildSkeleton(RThumb,RTB,RRadius) " Bone indices are often sorted by level hierarchy: the parent of all is usually the first one, and extremitites like toes at the end of the = array. After that, you need to transform bone global coordinates into local coordinates: let's decide that the bindpose is 'position only', so it's easy: just substract parent global position from global child position. Force it into your bone transform matrix, and set the rotation part to identity. OK your skeleton is done. Now some math with transform composition: LTM=3DLocalRotationMatrix*LocalTranslationMatrix GTM=3DLTM*GTMparent GTM=3DLTM*LTMparent*GTMgrandparent considering a bone, its children, and its parent: (Global Children Pos)=3D(Local Children Pos)*LTM Bone*GTM Bone Parent=20 (Global Children Pos)=3D(Local Children Pos)*Local Bone Rotation*Local = Bone Translation*GTM Parent If animations are rotation only, and because we know local translations = from the bindpose, the position of a bone is only affected by a variable: its parent rotation. for each frame of your anims start from the first very bone of your hierarchy and down to the children (hence one benefit of sorting skeleton by hierarchy level) 1) choose one of its child: we have to find a rotation that will transform the child local pos (stored in the Skeleton) into its current global pos (from the C3D) using: =09 GlobalChildPos=3DLocalChildPos*LocalRotation*LocalTranslation*GTMParent 2) compute M=3DInvert(LocalTranslation*GTMParent) 3) compute V1=3DGlobalChildPos*M and we know that V1=3DLocalChildPos*LocalRotation 4) so we have to find a rotation that will transform the LocalChildPos (as it's stored in the skeleton) into V1: for example, = compute an axis of rotation and an angle, with Normalized(CrossProduct(Normalized(LocalChildPos), Normalized(V1))) and acos(DotProduct(Normalized(LocalChildPos), Normalized(V1))). 5) hurray, you got a local parent rotation animation matrix: you can check that it transform all children LocalChildPos (from Skeleton) = into their global (from C3D) counterparts. 6) build and store its LTM and GTM: it will be used by its children Note:=20  if no parent is defined, the GTMParent matrix equals identity  Animation isn't 'rotationonly' for all bones: the very first bone probably 'moves' in translation... You'll have to deal with a special = case I'd like to add something about the resulting rotation: during final = step, there is only one single rotation as a solution to transform A1 into A2. = But this transformation is dependant of the *arbitrary* choice of your = initial bind pose: it wont probably reflect 'human' values, like 'forearm = twist', juste arbitray ones. By introducing initial joint orientation into the = bind pose, we could compute more relevant sets of anim rotation... If you = need to. =20 Awen Message d'origine De : gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] De la part de = Awen Limbourg Envoy=E9 : vendredi 15 avril 2005 12:07 =C0 : gdalgorithmslist@... Objet : RE: [Algorithms] Converting translation data to rotation data = and Reducing noise By translation datas are you speaking of (considering that your file are describing a complete body animation): Case A) raw global markers positionning from optical motion capture: = data in your files describes 4050 position steams (one per marker, 23 per = actual skeleton bones) ? Case B) raw global markers positionning from magnetic mocap: 1520*4 = streams of position ? Case C) processed global joint translation: barely 2030 joints but with = a hierarchy description somewhere ? Case A) its a very raw data file, better use MotionBuilder to transform markers into joint rotation by constraining skeleton joints (a typical = 2030 bones mocap skeleton should be ok). Very long/hard job for non = experienced animator. But MB has big tools to filter. Mathematical Case B) 34 = position streams per joint: it describes position and matrices axis. Possibly. Rebuild Matrices, extract angles. Case C) using some maths, we can compute some rotation from these data: = but it wont be the correct rotation from a human body. It will probably be = the 'lowest energy'/quickest rotation value... Are you sure that is what you want ? Cordially, Awen (better send me one file of yours to determinate its type) Message d'origine De : gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] De la part de Sindharta Tanuwijaya Envoy=E9 : mercredi 13 avril 2005 07:31 =C0 : gdalgorithmslist@... Objet : Re: [Algorithms] Converting translation data to rotation data = and Reducing noise Well, actually I am trying to fit motion capture data into muscle model = as desribed in this paper: "Creating and Retargetting motion by the musculoskeletal human body = model" http://www.it.cityu.edu.hk/~itaku/VisComp.pdf And for doing it, at first, I will need the rotational data, instead of = the translational data, and that`s why I am trying to obtain it. The next = step would be to calculate the forces in each node. Perhaps there is a good tool or SDK that can be used for it? Sindharta T.  Emanuele Salvucci <info@...> wrote: > I suppose you're building your own mocap system? >=20 > Not a technical answer, but If so, you might want to define a starting = > pose "takeclip" and build bones' > vectors from it. > Next takes will be computed based on the starting pose vectors.(this=20 > is at least how Vicon8 worked...I did quite some captures with it as a = > trained operator), >=20 > If this is the case, other people here will give better math insights=20 > on how to create/rotate vectors than me. ^_^ >=20 > FYI, most mocap systems are built on standard skeleton and anim=20 > formats (such as ASF/AMC Skeleton for Vicon8, which is Acclaim's > format: > http://www.motionrealityinc.com/software/asfamcspec.html > ) >=20 > Otherwise, if you're using some existing mocap data, you probably=20 > better off getting proper documentation on how to manage that specific = > type of data, and skeleton/bones definition. >=20 =20 Best, >=20 > Best, >=20 > Emanuele Salvucci > MayaLightwave > Game Technical Artist > Lscript developer >=20 > http://www.forwardgames.com > emanueles@... >=20 > "#3. He causes things to look different so it would appear time has=20 > passed." >=20 > =   >=20 >=20 >=20 >=20 =09 __________________________________ Do you Yahoo!?=20 Make Yahoo! your home page http://www.yahoo.com/r/hs  SF email is sponsored by  The IT Product Guide Read honest & candid = reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188  SF email is sponsored by  The IT Product Guide Read honest & candid = reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_ide95&alloc_id=14396&op=3Dick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Garett Bass <gtbass@st...>  20050423 07:39:08

I suspect you might also want to convolute against the Horowitz conjunct to reduce the Norbitstein quotient. Regards, Garett p.s. apologies in advance for any artificially induced confusion. Original Message From: Jon Watte [mailto:hplus@...] Sent: Friday, April 22, 2005 3:39 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries Yes, it seems building the DT this way, and then flipping to the dual Voronoi representation for actual map querying might be the easiest route. Thanks! Cheers, / h+ Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of PeterPike Sloan Sent: Friday, April 22, 2005 11:30 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries I believe it's fairly easy if you keep the connectivity of your cells. You have the set of cells that are to be removed, any cell which is adjacent (and not on the list) should be connected to the new point  so you can kind of walk this boundary region (always a d1 manifold) building cells as you do. I hope that makes sense... PeterPike Sloan  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Jon Watte <hplus@mi...>  20050422 20:38:05

Yes, it seems building the DT this way, and then flipping to the dual Voronoi representation for actual map querying might be the easiest route. Thanks! Cheers, / h+ Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of PeterPike Sloan Sent: Friday, April 22, 2005 11:30 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries I believe it's fairly easy if you keep the connectivity of your cells. You have the set of cells that are to be removed, any cell which is adjacent (and not on the list) should be connected to the new point  so you can kind of walk this boundary region (always a d1 manifold) building cells as you do. I hope that makes sense... PeterPike Sloan 
From: PeterPike Sloan <ppsloan@wi...>  20050422 18:30:30

I believe it's fairly easy if you keep the connectivity of your cells. You have the set of cells that are to be removed, any cell which is adjacent (and not on the list) should be connected to the new point  so you can kind of walk this boundary region (always a d1 manifold) building cells as you do. I hope that makes sense... PeterPike Sloan=20 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Jon Watte Sent: Thursday, April 21, 2005 6:19 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > The "incremental" algorithm is also quite easy to code up and extends=20 > to higher dimensions (drop a point in, blow away all of the cells=20 > whose circumsphere contains the point, reconnect to the new point...) Yes, but which points actually connect, and which are culled away by the sides of the polytope of the new point's cell? If there's a way to calculate this that's better than actually calculating the polytope, I'm interested! Cheers, / h+  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Jon Watte <hplus@mi...>  20050422 01:18:20

> The "incremental" algorithm is also quite easy to code up and extends to > higher dimensions (drop a point in, blow away all of the cells whose > circumsphere contains the point, reconnect to the new point...) Yes, but which points actually connect, and which are culled away by the sides of the polytope of the new point's cell? If there's a way to calculate this that's better than actually calculating the polytope, I'm interested! Cheers, / h+ 
From: PeterPike Sloan <ppsloan@wi...>  20050422 01:05:04

It's important to note that the edge flip algorithm (and the general formulation of constrained triangulations) don't extend to higher dimensions... The "incremental" algorithm is also quite easy to code up and extends to higher dimensions (drop a point in, blow away all of the cells whose circumsphere contains the point, reconnect to the new point...) PeterPike Sloan=20 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Alex Mohr Sent: Thursday, April 21, 2005 5:15 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Re: Fast nearest neighbour queries This is off the thread topic, but I think the easiest algorithm to code is the edge flip algorithm (google: edge flip delaunay). I've done it before and it's quite straightforward and the performance is quite good. I believe it's worst case N^2, but I think it rarely requires this many edge flips. Another cool thing is that you can also very easily extend this to do "constrained" Delaunay triangulations. Alex >Don't you just want the Delaunay triangulation of the nodes, i.e. the=20 >dual of the Voronoi diagram? > >See "Computational Geometry in C" (O'Rourke) for good stuff on this,=20 >but essentially you can compute the Delaunay triangulation directly=20 >using a convexhull algorithm, based on the observation that: > >The Delaunay triangulation of a set of points in two dimensions is=20 >precisely the projection onto the xyplane of the lower convex hull of=20 >the transformed points in three dimensions, transformed by mapping=20 >upwards to the paraboloid z =3D x*x + y*y. > >This relationship holds for higher dimensions. So, basically you can=20 >compute the Delaunay triangulation as fast as you can compute convex=20 >hulls. > > Tony > >Original Message >From: gdalgorithmslistadmin@... >[mailto:gdalgorithmslistadmin@...] On Behalf Of Jon >Watte >Sent: Thursday, April 21, 2005 4:32 PM >To: gdalgorithmslist@... >Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > > >> If you can spare the RAM, you could precompute a connectivity graph=20 >> and each node can store all of the closest nodes >to >it, >> and then on the first frame you do a global search using whatever >method, >> then you start out only searching its neighbors. As long as you=20 >> don't >move > >That's actually exactly what a Voronoi diagram is, and the search=20 >algorithm I suggested using. The main difficulty is calculating which=20 >nodes are actually "nearest" each other. This typically involves=20 >building cell side polygons through plane clipping, and keeping track=20 >of what you clip out (as preprocess). > >Cheers, > > / h+ > > > > >SF email is sponsored by  The IT Product Guide Read honest & candid=20 >reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > >SF email is sponsored by  The IT Product Guide Read honest & candid=20 >reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_ide95&alloc_id=14396&op=3Dclick >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_ide95&alloc_id=14396&op=3Dick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Alex Mohr <amohr@cs...>  20050422 00:14:59

This is off the thread topic, but I think the easiest algorithm to code is the edge flip algorithm (google: edge flip delaunay). I've done it before and it's quite straightforward and the performance is quite good. I believe it's worst case N^2, but I think it rarely requires this many edge flips. Another cool thing is that you can also very easily extend this to do "constrained" Delaunay triangulations. Alex >Don't you just want the Delaunay triangulation of the nodes, i.e. the >dual of the Voronoi diagram? > >See "Computational Geometry in C" (O'Rourke) for good stuff on this, but >essentially you can compute the Delaunay triangulation directly using a >convexhull algorithm, based on the observation that: > >The Delaunay triangulation of a set of points in two dimensions is >precisely the projection onto the xyplane of the lower convex hull of >the transformed points in three dimensions, transformed by mapping >upwards to the paraboloid z =3D x*x + y*y. > >This relationship holds for higher dimensions. So, basically you can >compute the Delaunay triangulation as fast as you can compute convex >hulls. > > Tony > >Original Message >From: gdalgorithmslistadmin@... >[mailto:gdalgorithmslistadmin@...] On Behalf Of Jon >Watte >Sent: Thursday, April 21, 2005 4:32 PM >To: gdalgorithmslist@... >Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > > >> If you can spare the RAM, you could precompute >> a connectivity graph and each node can store all of the closest nodes >to >it, >> and then on the first frame you do a global search using whatever >method, >> then you start out only searching its neighbors. As long as you don't >move > >That's actually exactly what a Voronoi diagram is, and the search >algorithm I suggested using. The main difficulty is calculating >which nodes are actually "nearest" each other. This typically >involves building cell side polygons through plane clipping, and >keeping track of what you clip out (as preprocess). > >Cheers, > > / h+ > > > > >SF email is sponsored by  The IT Product Guide >Read honest & candid reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > >SF email is sponsored by  The IT Product Guide >Read honest & candid reviews on hundreds of IT Products from real users. >Discover which products truly live up to the hype. Start reading now. >http://ads.osdn.com/?ad_ide95&alloc_id=14396&op=3Dclick >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Tony Cox <tonycox@mi...>  20050421 23:57:30

Don't you just want the Delaunay triangulation of the nodes, i.e. the dual of the Voronoi diagram? See "Computational Geometry in C" (O'Rourke) for good stuff on this, but essentially you can compute the Delaunay triangulation directly using a convexhull algorithm, based on the observation that: The Delaunay triangulation of a set of points in two dimensions is precisely the projection onto the xyplane of the lower convex hull of the transformed points in three dimensions, transformed by mapping upwards to the paraboloid z =3D x*x + y*y. This relationship holds for higher dimensions. So, basically you can compute the Delaunay triangulation as fast as you can compute convex hulls.  Tony Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Jon Watte Sent: Thursday, April 21, 2005 4:32 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] Re: Fast nearest neighbour queries > If you can spare the RAM, you could precompute > a connectivity graph and each node can store all of the closest nodes to it, > and then on the first frame you do a global search using whatever method, > then you start out only searching its neighbors. As long as you don't move That's actually exactly what a Voronoi diagram is, and the search algorithm I suggested using. The main difficulty is calculating which nodes are actually "nearest" each other. This typically involves building cell side polygons through plane clipping, and keeping track of what you clip out (as preprocess). Cheers, / h+  SF email is sponsored by  The IT Product Guide Read honest & candid reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Jon Watte <hplus@mi...>  20050421 23:31:10

> If you can spare the RAM, you could precompute > a connectivity graph and each node can store all of the closest nodes to it, > and then on the first frame you do a global search using whatever method, > then you start out only searching its neighbors. As long as you dont move That's actually exactly what a Voronoi diagram is, and the search algorithm I suggested using. The main difficulty is calculating which nodes are actually "nearest" each other. This typically involves building cell side polygons through plane clipping, and keeping track of what you clip out (as preprocess). Cheers, / h+ 
From: Jason Rooks <jasonrookslist@ho...>  20050421 23:08:50

>>find it potentially useful for all kinds of things  from defining areas >>for AI zone of influence, to storing spherical harmonics global lighting >>environments for interpolation. >Funny, thats exactly what I want to use it for. Thanks for the advice, I >think I will try a kdtree for starters as I"m more familiar with it. I dont think anyone has mentioned any methods exploiting frame to frame coherence (each renderable object could have a index to the lighting node(s) it is intepolating between). If you can spare the RAM, you could precompute a connectivity graph and each node can store all of the closest nodes to it, and then on the first frame you do a global search using whatever method, then you start out only searching its neighbors. As long as you dont move (since the last tick) further than the length of the path to a neighbor, you only have to check these neighbors. For each neighbor node you check that you moved further than the distance to, you also have to check all of its neighbors. If you teleport you could just mark the graph as dirty and start from scratch, to avoid a large recursive search. Jason Rooks 
From: Conor Stokes <bored_and_dangerous2003@ya...>  20050421 15:06:44

Actually, the nearest hit algorithm works well. I've used this principle with nearest triangle searching as well as nearest point searching on huge sets. But I've found that bounding volume hierarchies can be faster for nearest neighbour than spatial partitions (as much as I like KdTrees... and you can't use them in higher dimensions as the shape of the nodes diverge too much from a sphere and become less efficient). Mainly if you have a cache of previous "nearest" points (about 16 will do, in general). You find the closest one in the cache and use that to start culling (this works very well if your searches are close together in any way). Traverse in nearest distance order down to the children (you need to calculate the distance for culling anyway) and then whenever you find a hit point, you shrink the cull sphere.  Thatcher Ulrich <tu@...> wrote: > On Apr 19, 2005 at 08:45 0700, Jon Watte wrote: > > > > > To query for a closest neighbor, calculate a > bucket index from the point > > > coordinates and loop through all the points in > that bucket to find the > > > closest neighbor. Fast and cachefriendly. > > > > The problem with "nearest" queries is that any > fixed division (like > > a kd tree, octree, or BSP tree of the data points) > will suffer in > > querying, because you want the "closest" which is > a very different > > beast than "containment" or "overlap" which is > what those data > > structures optimize. You can fix this up running a > second query: > > once you find a candidate for the closest point, > see how far away > > it is, and run a sphere query from the query point > with the radius > > being the distance to the candidate, and examine > all the points > > within this sphere for closerness. > > I think it's simpler than that. Traverse the tree > in nearestfirst > order, keeping the nearest hit, and prune any > branches that are > further than the nearest hit. Should be one pass, > O(logn). > >  > Thatcher Ulrich > http://tulrich.com > > >  > This SF.Net email is sponsored by: New Crystal > Reports XI. > Version 11 adds new functionality designed to reduce > time involved in > creating, integrating, and deploying reporting > solutions. Free runtime info, > new features, or free trial, at: > http://www.businessobjects.com/devxi/728 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com 
From: Rodrigo H. <phamtompain@ya...>  20050420 21:21:05

>> Hehe, your knight can never be too strong ;p >> Just exagerated examples to show the difference between levels. >> Perhaps what you are looking for is a weighted normalization function? >> E.g. say that a class level/stat group should always sum to 1 but with >> different weights for different classes? >> ~neo Sounds like a nice solution! Say, I have to ensure that my modifiers' sum == X, and their values current distribution will define the effects on the Units of that class? I will test it right away! Thanks! 
From: neo binedell <neoji@mw...>  20050420 21:07:36

Hehe, your knight can never be too strong ;p =20 Just exagerated examples to show the difference between levels. =20 Perhaps what you are looking for is a weighted normalization function? =20 E.g. say that a class level/stat group should always sum to 1 but with different weights for different classes? =20 ~neo _____ =20 From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of = Rodrigo Greselle Hartmann Sent: 20 April 2005 08:05 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] Linear level up  Turn based strategy games. Hi! =20 Yes, I already had modifiers set up for each class. So, I already have different growth for each Unit stats, but the results are a bit = "bizarre" =3DD In other words, the 1.8 modifier applied on knight's strenght makes them = TOO strong with just some levels =3DD =20 I thought there was some kind of standard to deal with this... a mathematical parameter for modifiers, where they could be applied only = to ensure priority for one stat, instead of solely boosting it up... For = the given example, Strenght, you are raising it by at least 80% at each = level up. Too much! Even so, thanks for helping out =3DD =20 Rodrigo. =20 neo binedell <neoji@...> wrote: What about assigning modifiers per stat for each class? Simple example: ClassStatModifier { float strength; float magic; ... }; ClassStatModifier KnightClassLevel1 =3D { strength =3D 1.8; magic =3D 0.0; ...=20 }; ClassStatModifier WizardClassLevel1 =3D { strength =3D 1.1; magic =3D 1.8; ... } ClassLevelUps[ CLASS_COUNT ][ LEVEL_COUNT ]; // populate with all level entries for each class ...=20 void levelUp( Unit unit, int preyLevel ) {=20 ... ClassStatModifier *m =3D &ClassLevelUps[ unit.getClassID() ][ preyLevel ]; unit.strength *=3D m>strength; unit.magic *=3D m>magic; ... } regards neo Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of = Rodrigo H. Sent: 13 April 2005 05:36 PM To: gdalgorithmslist@... Subject: [Algorithms] Linear level up  Turn based strategy games. Hi, I'm developing a turnbased strategy game, in which Units have classes (Wizard, Knight) that affect their basic stats on level up. After a quick search for techniques, I've found a bit of information on linear level up  a technique where you give bonus to stats based on the delta level between the Unit leveling up, and the Unit being killed. But there are a set of modifiers to be applied in this calculation. A Knight, when he levels up, will gain a much better bonus on his Strength stat than a Wizard. Pretty simple concept, but I'm stuck on the implementation. Can someone give me a hint on a good solution? Currently, my UnitClass = class stores the modifiers, and it has the following method: levelUp(Unit unit, int preyLevel) where the Unit's stats are updated. I'm using Java, but all I want is pseudocode. ;) Thanks in advance, Rodrigo.  SF email is sponsored by  The IT Product Guide Read honest & candid = reviews on hundreds of IT Products from real users. Discover which products truly live up to the hype. Start reading now. http://ads.osdn.com/?ad_id=3D6595&alloc_id=3D14396&op=3Dclick _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188  This SF.Net email is sponsored by: New Crystal Reports XI. Version 11 adds new functionality designed to reduce time involved in creating, integrating, and deploying reporting solutions. Free runtime = info, new features, or free trial, at: = http://www.businessobjects.com/devxi/728 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 _____ =20 Yahoo! <http://us.rd.yahoo.com/mail/br/taglines/*http://br.acesso.yahoo.com//>; Acesso Gr=E1tis: Internet r=E1pida e gr=E1tis. Instale o discador agora! 