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

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

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

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

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

_{Jul}

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

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

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

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

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

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

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

2015 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(12) 
_{Nov}

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

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

_{Jun}
(1) 
_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

2017 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(1) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 




1
(8) 
2
(14) 
3
(1) 
4
(1) 
5
(3) 
6
(1) 
7

8
(6) 
9
(26) 
10
(12) 
11
(3) 
12
(2) 
13
(11) 
14
(4) 
15
(14) 
16
(20) 
17
(5) 
18
(1) 
19
(1) 
20
(12) 
21
(2) 
22

23
(3) 
24
(7) 
25
(7) 
26
(2) 
27
(16) 
28
(23) 
29
(8) 
30
(4) 
31
(5) 

From: Jonathan Blow <jon@nu...>  20060331 19:57:10

Jonathan Blow wrote: > > The first is, (assuming that things are moving linearly inside a > timestep), consider the point to be stationary, and just subtract its > velocity from the endpoints of the segment. This simplifies the > equations. As I look at the final equation, I realize you don't even need to bother with this, so ignore that part. You can just have a p(t) in the final equation I put down, and expand that into p0 + t delta p, and the equation is still just as easy to solve. Sorry about the extra confusion. So the only trick is testing against the full line, not just the segment. 
From: Jonathan Blow <jon@nu...>  20060331 19:46:30

This is pretty simple... There are 2 tricks to simplify it. The first is, (assuming that things are moving linearly inside a timestep), consider the point to be stationary, and just subtract its velocity from the endpoints of the segment. This simplifies the equations. The second is, instead of trying to test against the line segment, you test against the whole line. The point can only cross the line once during the timestep (due to linearity). So if it crosses, then you find the crossing point, and then determine whether that was inside the segment or outside (which is easy). Let's call the endpoints of the line A and B. They are really functions of t i.e. A(t) and B(t) but to keep the equations simple we will omit that.... The point you are testing is p. When p crosses the line, (p  A) dot (B  A)perp = 0. [Here dot is the 2d dot product and perp is the 2D operator that rotates the vector 90 degrees, i.e. Vperp = (Vy, Vx)]. The perp and the dot can be combined, so this is just: (p  A) perp_dot (B  A) = 0. So you just want to solve the equation above for t (which remember is implicit in the A and B). This is pretty trivial but the exact detail depends on your game. [I'm not sure if you are testing a point against, say, a rotating square or what.] Suppose this segment is some piece of an ngon and you know the positions of A and B both at the beginning and end of the timestep. So we will call them A0 and A1 = A0 + delta A, similarly for B. Then A(t) = A0 + t delta A And you just plug that in for A and B in the equation above and solve it. So you get: (p  A0  t delta A) perp_dot (B0  A0 + t(delta B  delta A)) = 0 which is pretty easy to solve, and there you go. If you have any questions about this feel free to drop me an email... this is maybe not the most lucid explanation. metanet software wrote: > > It turns out that determining the _time_ of collision would be very > useful; I've tried to figure this out in a few ways, however I always > end up with one too many unknowns (or one too few equations). I > suppose this is what Christer meant by "much more complicated" ;) > > > If we know that C intersects the quad Q1,Q2,Q3,Q4, then there must > exist a unique line L which passes through C and which intersects the > lines L1 = Q1 + t(Q4Q1) and L2 = Q2 + t(Q3Q2) at the same value of t. > > It seems like there should be a very straightforward solution, since > there can only be a single direction for L which intersects L1 and L2 > at the same t parameter, however.. I haven't managed to find it. > Substituting the parametric description of the intersection points and > rearranging always seems to produce an equation of the form x + y + xy > = 0.. which can't be solved without another equation. Of course, it's > also possible that I made some mistakes while rearranging things.. > > > A related problem is finding the point of intersection; once we know > the time of intersection t it is trivial to determine the point of > intersection (at time t, C is colinear with the segment, so it's easy > to find the parametric/barycentric coord of C in terms of the segment > endpoints). Similarly, given this parametric coord, it would be > trivial to determine the time of intersection. However, I know neither. > > Does anyone have any suggestions on how to approach this problem? It > seems irritatingly simple. > > thanks for your time, > raigan > > > */christer_ericson@.../* wrote: > > > > > given linesegment with endpoints A,B and endpoint velocities vA,vB, > > and point C with velocity vC [determine if intersection occurs] > > > > I should mention that I only need a boolean result, no time/point of > > intersection. > > In that you're working in 2D and are only interested in the boolean > result, this is pretty easy (3D or nonboolean results would make > it much more complicated). > > As others noted, the movement of segment AB will form a (possibly > concave or selfintersecting) quad in the plane. However, rather > than testing the moving point against this quad, the right approach > is to work in the space of the moving point C. > > C then becomes stationary and we turn the problem into that of > determining if C lies inside the quad Q determined by the four > points: Q1=A, Q2=B, Q3=B+vBvC, and Q4=A+vAvC. > > To correctly determine containment in Q you would have to determine > which of three cases you have: > > 1. Q is convex > 2. Q is concave > 3. Q is selfintersecting > > The first case is straightforward. C lies inside Q if C is > consistently to the left or right of all segments Q1Q2, Q2Q3, > Q3Q4, and Q4Q1. > > The second case corresponds to Q being a dart (Star Trek badge). > Split Q on the diagonal to form two triangles and test C for > containment in either triangle. > > For the third case, compute the point where the quad self > intersects and form two triangles extending from that point and > test C for containment in the triangles. > > > Christer Ericson > http://realtimecollisiondetection.net/ > > > >  > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the > live webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.asus.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > >  > Share your photos with the people who matter at *Yahoo! Canada Photos* > <http://photos.yahoo.ca>; 
From: Jonathan Blow <jon@nu...>  20060331 19:46:11

This is pretty simple... There are 2 tricks to simplify it. The first is, (assuming that things are moving linearly inside a timestep), consider the point to be stationary, and just subtract its velocity from the endpoints of the segment. This simplifies the equations. The second is, instead of trying to test against the line segment, you test against the whole line. The point can only cross the line once during the timestep (due to linearity). So if it crosses, then you find the crossing point, and then determine whether that was inside the segment or outside (which is easy). Let's call the endpoints of the line A and B. They are really functions of t i.e. A(t) and B(t) but to keep the equations simple we will omit that.... The point you are testing is p. When p crosses the line, (p  A) dot (B  A)perp = 0. [Here dot is the 2d dot product and perp is the 2D operator that rotates the vector 90 degrees, i.e. Vperp = (Vy, Vx)]. The perp and the dot can be combined, so this is just: (p  A) perp_dot (B  A) = 0. So you just want to solve the equation above for t (which remember is implicit in the A and B). This is pretty trivial but the exact detail depends on your game. [I'm not sure if you are testing a point against, say, a rotating square or what.] Suppose this segment is some piece of an ngon and you know the positions of A and B both at the beginning and end of the timestep. So we will call them A0 and A1 = A0 + delta A, similarly for B. Then A(t) = A0 + t delta A And you just plug that in for A and B in the equation above and solve it. So you get: (p  A0  t delta A) perp_dot (B0  A0 + t(delta B  delta A)) = 0 which is pretty easy to solve, and there you go. If you have any questions about this feel free to drop me an email... this is maybe not the most lucid explanation. metanet software wrote: > > It turns out that determining the _time_ of collision would be very > useful; I've tried to figure this out in a few ways, however I always > end up with one too many unknowns (or one too few equations). I > suppose this is what Christer meant by "much more complicated" ;) > > > If we know that C intersects the quad Q1,Q2,Q3,Q4, then there must > exist a unique line L which passes through C and which intersects the > lines L1 = Q1 + t(Q4Q1) and L2 = Q2 + t(Q3Q2) at the same value of t. > > It seems like there should be a very straightforward solution, since > there can only be a single direction for L which intersects L1 and L2 > at the same t parameter, however.. I haven't managed to find it. > Substituting the parametric description of the intersection points and > rearranging always seems to produce an equation of the form x + y + xy > = 0.. which can't be solved without another equation. Of course, it's > also possible that I made some mistakes while rearranging things.. > > > A related problem is finding the point of intersection; once we know > the time of intersection t it is trivial to determine the point of > intersection (at time t, C is colinear with the segment, so it's easy > to find the parametric/barycentric coord of C in terms of the segment > endpoints). Similarly, given this parametric coord, it would be > trivial to determine the time of intersection. However, I know neither. > > Does anyone have any suggestions on how to approach this problem? It > seems irritatingly simple. > > thanks for your time, > raigan > > > */christer_ericson@.../* wrote: > > > > > given linesegment with endpoints A,B and endpoint velocities vA,vB, > > and point C with velocity vC [determine if intersection occurs] > > > > I should mention that I only need a boolean result, no time/point of > > intersection. > > In that you're working in 2D and are only interested in the boolean > result, this is pretty easy (3D or nonboolean results would make > it much more complicated). > > As others noted, the movement of segment AB will form a (possibly > concave or selfintersecting) quad in the plane. However, rather > than testing the moving point against this quad, the right approach > is to work in the space of the moving point C. > > C then becomes stationary and we turn the problem into that of > determining if C lies inside the quad Q determined by the four > points: Q1=A, Q2=B, Q3=B+vBvC, and Q4=A+vAvC. > > To correctly determine containment in Q you would have to determine > which of three cases you have: > > 1. Q is convex > 2. Q is concave > 3. Q is selfintersecting > > The first case is straightforward. C lies inside Q if C is > consistently to the left or right of all segments Q1Q2, Q2Q3, > Q3Q4, and Q4Q1. > > The second case corresponds to Q being a dart (Star Trek badge). > Split Q on the diagonal to form two triangles and test C for > containment in either triangle. > > For the third case, compute the point where the quad self > intersects and form two triangles extending from that point and > test C for containment in the triangles. > > > Christer Ericson > http://realtimecollisiondetection.net/ > > > >  > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the > live webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.asus.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > >  > Share your photos with the people who matter at *Yahoo! Canada Photos* > <http://photos.yahoo.ca>; 
From: metanet software <metanet_gda4@ya...>  20060331 18:25:14

It turns out that determining the _time_ of collision would be very useful; I've tried to figure this out in a few ways, however I always end up with one too many unknowns (or one too few equations). I suppose this is what Christer meant by "much more complicated" ;) If we know that C intersects the quad Q1,Q2,Q3,Q4, then there must exist a unique line L which passes through C and which intersects the lines L1 = Q1 + t(Q4Q1) and L2 = Q2 + t(Q3Q2) at the same value of t. It seems like there should be a very straightforward solution, since there can only be a single direction for L which intersects L1 and L2 at the same t parameter, however.. I haven't managed to find it. Substituting the parametric description of the intersection points and rearranging always seems to produce an equation of the form x + y + xy = 0.. which can't be solved without another equation. Of course, it's also possible that I made some mistakes while rearranging things.. A related problem is finding the point of intersection; once we know the time of intersection t it is trivial to determine the point of intersection (at time t, C is colinear with the segment, so it's easy to find the parametric/barycentric coord of C in terms of the segment endpoints). Similarly, given this parametric coord, it would be trivial to determine the time of intersection. However, I know neither. Does anyone have any suggestions on how to approach this problem? It seems irritatingly simple. thanks for your time, raigan christer_ericson@... wrote: > given linesegment with endpoints A,B and endpoint velocities vA,vB, > and point C with velocity vC [determine if intersection occurs] > > I should mention that I only need a boolean result, no time/point of > intersection. In that you're working in 2D and are only interested in the boolean result, this is pretty easy (3D or nonboolean results would make it much more complicated). As others noted, the movement of segment AB will form a (possibly concave or selfintersecting) quad in the plane. However, rather than testing the moving point against this quad, the right approach is to work in the space of the moving point C. C then becomes stationary and we turn the problem into that of determining if C lies inside the quad Q determined by the four points: Q1=A, Q2=B, Q3=B+vBvC, and Q4=A+vAvC. To correctly determine containment in Q you would have to determine which of three cases you have: 1. Q is convex 2. Q is concave 3. Q is selfintersecting The first case is straightforward. C lies inside Q if C is consistently to the left or right of all segments Q1Q2, Q2Q3, Q3Q4, and Q4Q1. The second case corresponds to Q being a dart (Star Trek badge). Split Q on the diagonal to form two triangles and test C for containment in either triangle. For the third case, compute the point where the quad self intersects and form two triangles extending from that point and test C for containment in the triangles. Christer Ericson http://realtimecollisiondetection.net/  This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.asus.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188  Share your photos with the people who matter at Yahoo! Canada Photos 
From: Anders Nilsson <breakin.outbreak@gm...>  20060331 13:04:51

If I recall correctly, integrating 1 over the volume is the same as integrating (x+y+z)/3 over the surface (since grad((x+y+z)/3)=3D1). If you simplify the (x+y+z)/3expression then out comes the formula using tetrahedrons, ie sum the signed volumes of tetrahedron using triangle and the origin (the arbitrary point chosen as (0,0,0)). AndersN. 
From: PalKristian Engstad <pal_engstad@na...>  20060330 19:47:54

Hi Tom, First, yes, that's what I said. Tom Forsyth wrote: > Hierarchy data is one integer per bone  the index of the parent of tha= t > bone. That's trivial amounts of data, and it's stored once per skeleton= , not > once per animation (you always have more animations than skeletons :). > Can't see how that's significant. > =20 That's a slight oversimplification. There might be more data than that=20 in a hierarchy. For instance, if you have Maya (Set) Driven Keys, then=20 the DK data naturally belongs with the hierarchy data, since it is data=20 used once per model, and not once per animation. The same comment=20 applies to any runtime constraint data. Of course, it all depends on what you mean with a "joint hierarchy". We=20 typically put all of those things into the joint hierarchy, but I=20 suppose you could instead say that you have a "joint model", comprised=20 of "joint hierarchy data", "drivenkey data", "constraint data" and=20 perhaps more. Thanks, PKE. > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...] On Behalf Of > PalKristian Engstad > Sent: 29 March 2006 11:26 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Quaternion animation strategy > > > Hi, > > I think that's because  usually, there's a whole lot more animation da= ta > than hierarchy data. After all, in a game you would have tens to hundre= ds of > animations per character model, whereas the joint hierarchy is once per > model.=20 > > In other words, if you can reduce the size of the quaternions, which is > typically 90% or more of your animation data  the rest being translati= onal > and scaling data, then you are much better off. > > Robert Dibley wrote:=20 > Not sure how you came to that conclusion, we stored less data this way = as we > didn=92t have to store any hierarchy data. > PKE. > > =20 =20 P=E5lKristian Engstad (engstad@...), Lead Programmer, ICE team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North, Santa Monica, CA 90404, USA. Ph.: (310) 6339112. "Most of us would do well to remember that there is a reason Carmack is Carmack, and we are not Carmack.", Jonathan Blow, 2/1/2006, GD Algo Mailing List 
From: Willem de Boer <wdeboer@mi...>  20060330 08:01:54

I'm no expert on this either but yeah, the Fundamental Theorem of Calculus, Gauss's, Green's, and Stokes's are all special cases of the generalised Stokes theorem. But surely if we stay safely within the realm of 3dimensional Euclidian space we won't need to deal with it directly.=20  Willem=20 PS: You are the second game developer I've spoken to who's read (or at least skimmed) MTW's "Gravitation". Not a particularly light read :) Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of christer_ericson@... Sent: 29 March 2006 19:03 To: gdalgorithmslist@... Subject: RE: [Algorithms] Volume calculation for a two nonparallel triangles connected at the edges Willem de Boer wrote: > >An exact solution would require, I think, integrating over the > >surface of the shape ala Stokes' Theorem. The nonplanar sides > > That would be Gauss's theorem (the integral of a function over > a closed "regular" volume equals the integral of its divergence over > the boundary). As long as the nonplanar sides can be expressed > parametrically and are at leastpiecewise continuous, this should > be no problem. I meant the generalized Stokes' theorem (GST). This is way outside my area of expertise, but my understanding is that Gauss' theorem is a special case of GST (thus Green's theorem, Gauss' theorem, etc can all be conveniently (and probably sloppily) lumped together under the heading "(generalized) Stokes' theorem"). Certainly Misner et al's "Gravitation" has Gauss' theorem as a special case of GST. Is that not the case? Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica  This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.asus.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Tom Forsyth <tom.forsyth.gdalgo@ee...>  20060330 04:40:55

Hierarchy data is one integer per bone  the index of the parent of that bone. That's trivial amounts of data, and it's stored once per skeleton, = not once per animation (you always have more animations than skeletons :). Can't see how that's significant. TomF. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of PalKristian Engstad Sent: 29 March 2006 11:26 To: gdalgorithmslist@... Subject: Re: [Algorithms] Quaternion animation strategy Hi, I think that's because  usually, there's a whole lot more animation = data than hierarchy data. After all, in a game you would have tens to = hundreds of animations per character model, whereas the joint hierarchy is once per model.=20 In other words, if you can reduce the size of the quaternions, which is typically 90% or more of your animation data  the rest being = translational and scaling data, then you are much better off. Robert Dibley wrote:=20 Not sure how you came to that conclusion, we stored less data this way = as we didn=92t have to store any hierarchy data. PKE. =20 P=E5lKristian Engstad (engstad@...), Lead Programmer, ICE team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North, Santa Monica, CA 90404, USA. Ph.: (310) 6339112. "Most of us would do well to remember that there is a reason Carmack is Carmack, and we are not Carmack.", Jonathan Blow, 2/1/2006, GD Algo Mailing List 
From: Jose <rueda_jl@ya...>  20060330 00:41:19

Hello, everybody. Christer Ericson wrote >An exact solution would require, I think, integrating over the >surface of the shape ala Stokes' Theorem. Well, while you can compute it by reducing the volume integral to a surface integral (and maybe it's the best option), I don't think it is required at all. We can try a more direct approach. Let call the first triangle T0, with vertices a0, b0, c0, and the second triangle T1( a1, b1, c1 ), where a1 is the projection of a0, b1 of b0, and c1 of c0. We can express the surface of the first triangle by: Surface of T0 : r0( u, v ) = ( b0+(c0b0)*va0 )*u + a0 And, respectively: Surface of T1 : r1( u, v ) = ( b1+(c1b1)*va1 )*u + a1 where 0<=u<=1, 0<=v<=1 Now, we can parametrize the whole volume by: r( u, v, t ) = ( 1  t ) * r0( u, v ) + t * r1( u, v ), where 0<=t<=1 If I can remember correctly, the differential element of volume for this geometry is defined by dV = dot( (&r/&t)dt, cross( (&r/&u)du, (&r/&v)dv ) ), where & should be delta, the symbol for the partial derivative (sorry, I'm not an ASCII artist :) ). But we can actually compute this partial derivatives: &r/&t = (b0 + (c0  b0)v  a0)u  a0 + (b1 + (c1  b1)v  a1)u + a1 &r/&u = (1  t)(b0 + (c0  b0)*v  a0) + t * (b1 + (c1  b1)*v  a1) &r/&v = (1  t)(c0  b0)u + t * (c1  b1) * u You can get an analytic expression for dV (you only have to do the actual dot and cross products), as function of t, u and v (and the triangles' vertices, of course). The volume is V = int( dV over the volume of the figure ) = = int( int( int( dot( (&r/&t), cross( (&r/&u), (&r/&v) ) ) * dt*du*dv ), t=0..1, u=0..1, v=0..1 ); ( [int] is the definite integral, of course ) I haven't computed it, but I bet this has a closed form solution, whose only inputs are the vertices, which is what we were looking for. I recommend the use of a mathematical package to do the actual computation ;) \n \nI hope this is of any help, and not to have made any (too obvious) mistake ^^; \n \nBest regards. \n \n Jose \n \nPD: ... and sorry for my bad English...\n\n ",0] ); D(["ce"]); //> I hope this is of any help, and not to have made any (too obvious) mistake ^^; Best regards.  Jose PD: ... and sorry for my bad English...  LLama Gratis a cualquier PC del Mundo. Llamadas a fijos y móviles desde 1 céntimo por minuto. http://es.voice.yahoo.com 
From: Mark Wayland <Mwayland@to...>  20060329 22:23:34

Thanks Matt, I'll check it out.=20 > Original Message > From: gdalgorithmslistadmin@...=20 > [mailto:gdalgorithmslistadmin@...] On=20 > Behalf Of Matt Pharr > Sent: Wednesday, 29 March 2006 9:57 AM > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Approximating polygon vertex=20 > colours with runtime lights? >=20 >=20 > "Mark Wayland" <Mwayland@...> writes: > > I was wondering if someone might be able to 'shed some=20 > light' on where=20 > > I might start in working out, for a moderate number of=20 > polygons, what=20 > > set of runtime lights (both directional and point, up to a=20 > total of 3=20 > > or 4) would best approximate the lighting found in the=20 > vertex colours=20 > > of the polygons? >=20 > I believe that the following might be a good place to start=20 > (solving a more complex problem, but I assume the ideas are=20 > applicable): >=20 > http://www.graphics.cornell.edu/%7Ebjw/virtlite.html >=20 > "Fitting Virtual Lights For NonDiffuse Walkthroughs", Bruce=20 > Walter, Gun Alppay, Eric Lafortune, Sebastian Fernandez,=20 > Donald P. Greenberg, published at SIGGRAPH 1997. >=20 > Abstract >=20 > This paper describes a technique for using a simple shading=20 > method, such as the Phong lighting model, to approximate the=20 > appearance calculated by a more accurate method. The results=20 > are then suitable for rapid display using existing graphics=20 > hardware and portable via standard graphics API's. > Interactive walkthroughs of viewindependent nondiffuse=20 > global illumination solutions are explored as the motivating=20 > application. >=20 > matt >  > Matt Pharr > Neoptica > http://neoptica.com >=20 >=20 >=20 >  > This SF.Net email is sponsored by xPML, a groundbreaking=20 > scripting language > that extends applications into web and mobile media. Attend=20 > the live webcast > and join the prime developer group breaking into this new=20 > coding territory! > http://sel.asus.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&; > dat=3D121642 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 
From: PalKristian Engstad <pal_engstad@na...>  20060329 19:26:49

Hi, I think that's because  usually, there's a whole lot more animation=20 data than hierarchy data. After all, in a game you would have tens to=20 hundreds of animations per character model, whereas the joint hierarchy=20 is once per model. In other words, if you can reduce the size of the quaternions, which is=20 typically 90% or more of your animation data  the rest being=20 translational and scaling data, then you are much better off. Robert Dibley wrote: > > Not sure how you came to that conclusion, we stored less data this way=20 > as we didn't have to store any hierarchy data. > PKE. =20 P=E5lKristian Engstad (engstad@...), Lead Programmer, ICE team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North, Santa Monica, CA 90404, USA. Ph.: (310) 6339112. "Most of us would do well to remember that there is a reason Carmack is Carmack, and we are not Carmack.", Jonathan Blow, 2/1/2006, GD Algo Mailing List 
From: <christer_ericson@pl...>  20060329 18:02:55

Willem de Boer wrote: > >An exact solution would require, I think, integrating over the > >surface of the shape ala Stokes' Theorem. The nonplanar sides > > That would be Gauss's theorem (the integral of a function over > a closed "regular" volume equals the integral of its divergence over > the boundary). As long as the nonplanar sides can be expressed > parametrically and are at leastpiecewise continuous, this should > be no problem. I meant the generalized Stokes' theorem (GST). This is way outside my area of expertise, but my understanding is that Gauss' theorem is a special case of GST (thus Green's theorem, Gauss' theorem, etc can all be conveniently (and probably sloppily) lumped together under the heading "(generalized) Stokes' theorem"). Certainly Misner et al's "Gravitation" has Gauss' theorem as a special case of GST. Is that not the case? Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica 
From: <c.schueler@ph...>  20060329 10:22:31

I like to point out that you gain a lot of spacesaving from animation = compression if the motion of joints is recorded in parent space, since = joints usually don't move much with respect to their parent (mostly = translation is constant, and rotation can be brought down to a few = keys). You don't have this advantage if all joints are stored in the = same space, as the movements of end effectors can get quite complex, and = compression cannot compress much. Original Message From: gdalgorithmslistadmin@... = [mailto:gdalgorithmslistadmin@...] On Behalf Of = Jamie Fowlston Sent: Friday, March 24, 2006 11:33 AM To: gdalgorithmslist@... Subject: Re: [Algorithms] Quaternion animation strategy Robert Dibley wrote: > Just to suggest an alternative idea ... since you have to store the=20 > quaternion and offset for each bone anyway, I once worked on a game=20 > where we changed our animation system to store all these values = relative=20 > to the base pose. >=20 > This has the advantage that you don't have to keep loading up = different=20 > parent bones to apply to your next child when propagating. Oh, and = you=20 > don't need to know the parent relationship. >=20 > However it does have the disadvantage that you really have to use the=20 > animation as an absolute ... trying to mess with bit of it when you = don't=20 > have the parentrelative values can be tricky in some cases. The parentrelative values are still there (just multiply by the inverse = of your parent to base pose transform), you just have to do a few more=20 calculations to get at it. Jamie  This SF.Net email is sponsored by xPML, a groundbreaking scripting = language that extends applications into web and mobile media. Attend the live = webcast and join the prime developer group breaking into this new coding = territory! http://sel.asus.falkag.net/sel?cmd=3Dk&kid=110944&bid$1720&dat=121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Robert Dibley <blimey.rob@go...>  20060329 09:57:00

Not sure how you came to that conclusion, we stored less data this way as we didn't have to store any hierarchy data. Regards Robert _____ From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Mark Wayland Sent: 29 March 2006 10:50 To: gdalgorithmslist@... Subject: Re: [Algorithms] Quaternion animation strategy A good idea considering that any errors in interpolation of the parent bone(s) would not be propagated down the hierarchy, but means storing a bit more data... I guess nothing's free? ;) Cheers, Mark  Original Message  From: Robert <mailto:blimey.rob@...> Dibley To: gdalgorithmslist@... Sent: Friday, March 24, 2006 6:59 PM Subject: RE: [Algorithms] Quaternion animation strategy Just to suggest an alternative idea . since you have to store the quaternion and offset for each bone anyway, I once worked on a game where we changed our animation system to store all these values relative to the base pose. This has the advantage that you don't have to keep loading up different parent bones to apply to your next child when propagating. Oh, and you don't need to know the parent relationship. However it does have the disadvantage that you really have to use the animation as an absolute . trying to mess with bit of it when you don't have the parentrelative values can be tricky in some cases. So, it worked well for us, but YMMV. Regards Robert _____ From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Matt J Sent: 23 March 2006 23:54 To: gdalgorithmslist@... Subject: Re: [Algorithms] Quaternion animation strategy Hi James, I'll take another look at the export format, MDX, the guys who wrote these (unofficial) docs aren't mathematicians, but thanks to your clear response I think I can figure out for sure how it is done. Thanks a lot for the response. It was very helpful, it seems that you still use matrices for the final form and still use the concept of local transformations (i.e., in OpenGL you can think of a group of successive affine transformations as occuring on a local coordinate axis frame that "moves" around per joint, which is useful in this sense) and you use quaternions just as a means of storage and interpolation between different frames. One final question, I understand simply storing all the bones in the array, but in order to render a bone, it has to be aware of its parent bone's relative effect on the transformation, correct? It would seem you would still want to use the concept of a tree structure but your just storing the bones in an array and say, using an index/handle instead of a pointer to reference it? Or, is there another technique you use, say, like, propogating affine transformations made from one bone to the children of that bone? Thanks for the tips! Matthew > 1. Are the quaternions stored as the joints of the bones, or are they > used simply to interpolate two rotation matrices? In other words, is it > perfectly acceptable or usually practiced to store the quaternions > directly in the treebased bone data structure? We store a position vector and orientation quaternion for each bone in the skeleton. We build transform matrices from these as a final step once we go to skin the associated mesh. You may also find it advantageous to not store the bones in a strict tree structure; we simply keep an array of bones, where each bone may or may not be parented to another bone. This allows for more flexibility in rig construction and doesn't require a single "root" bone, and as a bonus has better cache performance. You would still have to traverse it as a tree structure, correct? Even if your rendering a bone, the rotation has to be in the context of the parent bones. > 2. How are these quaternions calculated? Do you find the cross product > of the vector formed by the two bones, and then build > it based on that vector and the angle of rotation?, using the form q = < > cos (theta / 2) , A sin(theta / 2) > where A is the axis of rotation. Your conversion from axis/angle to quaternion is correct but I'm not sure why you need to calculate the quaternion. We export the orientation as a quaternion directly from our art package. Right. This makes sense, the package would have a series of quaternions, and you just interpolate between them. I'll double check, I believe this is the format that MDX uses, although the (unofficial) docs aren't clear about this. > 3. So, suppose we are in model space, and every joint is a new rotation > based off of the previous joint. Is point P found by q_bone1 * q_bone2 * > P * q_bone1_conjugate * q_bone2_congjugate? Is that the equivalent of > applying two rotation matrices? It would seem like we do not worry about > using the concept of a local matrix anymore, but instead directly > transform the model points using quaternions and render them in model > space. Is this correct? If this is correct, it would seem we would also > need to keep track of the translations between bones. That seems simple > enough, it would seem before performing the quaternion rotation, you > would shift it so the bone starts at the origin of model space, do the > rotation, and shift it back. I think you are overcomplicating things. To skin the mesh we calculate transform matrices for all the bones in the skeleton (using the position and orientation) and use the standard skinning method (bone offset method I think it's called). Each vertex is transformed by the appropriately weighted skinning transform, which is the bone inverse reference transform (the bone's transform in the reference/bind pose exported from the art package) multiplied by the current bone transform. You can directly transfom a point by a quaternion but doing any more than one point will be slower than just converting the quaternion to a rotation matrix and transforming by the matrix. 
From: Mark Wayland <mwayland@to...>  20060329 09:50:05

A good idea considering that any errors in interpolation of the parent = bone(s) would not be propagated down the hierarchy, but means storing a = bit more data... I guess nothing's free? ;) Cheers, Mark  Original Message =20 From: Robert Dibley=20 To: gdalgorithmslist@...=20 Sent: Friday, March 24, 2006 6:59 PM Subject: RE: [Algorithms] Quaternion animation strategy Just to suggest an alternative idea . since you have to store the = quaternion and offset for each bone anyway, I once worked on a game = where we changed our animation system to store all these values relative = to the base pose. This has the advantage that you don't have to keep loading up = different parent bones to apply to your next child when propagating. = Oh, and you don't need to know the parent relationship. However it does have the disadvantage that you really have to use the = animation as an absolute . trying to mess with bit of it when you don't = have the parentrelative values can be tricky in some cases. So, it worked well for us, but YMMV. =20 Regards Robert =20 =  From: gdalgorithmslistadmin@... = [mailto:gdalgorithmslistadmin@...] On Behalf Of Matt = J Sent: 23 March 2006 23:54 To: gdalgorithmslist@... Subject: Re: [Algorithms] Quaternion animation strategy =20 Hi James,=20 =20 I'll take another look at the export format, MDX, the guys who wrote = these (unofficial) docs aren't mathematicians, but thanks to your clear = response I think I can figure out for sure how it is done. =20 Thanks a lot for the response. It was very helpful, it seems that you = still use matrices for the final form and still use the concept of local = transformations (i.e., in OpenGL you can think of a group of successive = affine transformations as occuring on a local coordinate axis frame that = "moves" around per joint, which is useful in this sense) and you use = quaternions just as a means of storage and interpolation between = different frames.=20 =20 One final question, I understand simply storing all the bones in the = array, but in order to render a bone, it has to be aware of its parent = bone's relative effect on the transformation, correct? It would seem you = would still want to use the concept of a tree structure but your just = storing the bones in an array and say, using an index/handle instead of = a pointer to reference it? Or, is there another technique you use, say, = like, propogating affine transformations made from one bone to the = children of that bone?=20 =20 Thanks for the tips! =20 Matthew =20 > 1. Are the quaternions stored as the joints of the bones, or are = they > used simply to interpolate two rotation matrices? In other words, = is it=20 > perfectly acceptable or usually practiced to store the quaternions > directly in the treebased bone data structure? We store a position vector and orientation quaternion for each bone = in the skeleton. We build transform matrices from these as a final step = once we go to skin the associated mesh. You may also find it advantageous to not store the bones in a strict tree structure; we simply keep an array of bones, where each bone may or may not be parented to another bone. This allows for more flexibility in rig=20 construction and doesn't require a single "root" bone, and as a = bonus has better cache performance. =20 You would still have to traverse it as a tree structure, correct? Even = if your rendering a bone, the rotation has to be in the context of the = parent bones.=20 =20 =20 > 2. How are these quaternions calculated? Do you find the cross = product > of the vector formed by the two bones, and then build=20 > it based on that vector and the angle of rotation?, using the form = q =3D < > cos (theta / 2) , A sin(theta / 2) > where A is the axis of = rotation. Your conversion from axis/angle to quaternion is correct but I'm not = sure why you need to calculate the quaternion. We export the = orientation as a quaternion directly from our art package. =20 Right. This makes sense, the package would have a series of = quaternions, and you just interpolate between them. I'll double check, I = believe this is the format that MDX uses, although the (unofficial) docs = aren't clear about this.=20 =20 > 3. So, suppose we are in model space, and every joint is a new = rotation > based off of the previous joint. Is point P found by q_bone1 * = q_bone2 *=20 > P * q_bone1_conjugate * q_bone2_congjugate? Is that the equivalent = of > applying two rotation matrices? It would seem like we do not worry = about > using the concept of a local matrix anymore, but instead directly=20 > transform the model points using quaternions and render them in = model > space. Is this correct? If this is correct, it would seem we would = also > need to keep track of the translations between bones. That seems = simple=20 > enough, it would seem before performing the quaternion rotation, = you > would shift it so the bone starts at the origin of model space, do = the > rotation, and shift it back. I think you are overcomplicating things. To skin the mesh we = calculate=20 transform matrices for all the bones in the skeleton (using the = position and orientation) and use the standard skinning method (bone offset method I think it's called). Each vertex is transformed by the appropriately weighted skinning transform, which is the bone inverse = reference transform (the bone's transform in the reference/bind pose exported from the art package) multiplied by the current bone = transform. You can directly transfom a point by a quaternion but doing any more = than one point will be slower than just converting the quaternion to = a rotation matrix and transforming by the matrix. =20 
From: Willem de Boer <wdeboer@mi...>  20060329 08:05:02

"(the integral of a function over a closed "regular" volume equals the integral of its divergence over the boundary)" Brainfart. *smack* Should be integral of divergence of function over regular volume=20 equals integral of function over boundary.  Willem=20 Original Message From: Willem de Boer=20 Sent: 29 March 2006 09:03 To: 'gdalgorithmslist@...' Subject: RE: [Algorithms] Volume calculation for a two nonparallel triangles connected at the edges >An exact solution would require, I think, integrating over the >surface of the shape ala Stokes' Theorem. The nonplanar sides That would be Gauss's theorem (the integral of a function over a closed "regular" volume equals the integral of its divergence over the boundary). As long as the nonplanar sides can be expressed parametrically and are at leastpiecewise continuous, this should=20 be no problem. Willem 
From: Willem de Boer <wdeboer@mi...>  20060329 08:03:18

>An exact solution would require, I think, integrating over the >surface of the shape ala Stokes' Theorem. The nonplanar sides That would be Gauss's theorem (the integral of a function over a closed "regular" volume equals the integral of its divergence over the boundary). As long as the nonplanar sides can be expressed parametrically and are at leastpiecewise continuous, this should=20 be no problem. Willem 
From: Matt Pharr <matt@ph...>  20060328 23:57:12

"Mark Wayland" <Mwayland@...> writes: > I was wondering if someone might be able to 'shed some light' on where I > might start in working out, for a moderate number of polygons, what set > of runtime lights (both directional and point, up to a total of 3 or 4) > would best approximate the lighting found in the vertex colours of the > polygons? I believe that the following might be a good place to start (solving a more complex problem, but I assume the ideas are applicable): http://www.graphics.cornell.edu/%7Ebjw/virtlite.html "Fitting Virtual Lights For NonDiffuse Walkthroughs", Bruce Walter, Gun Alppay, Eric Lafortune, Sebastian Fernandez, Donald P. Greenberg, published at SIGGRAPH 1997. Abstract This paper describes a technique for using a simple shading method, such as the Phong lighting model, to approximate the appearance calculated by a more accurate method. The results are then suitable for rapid display using existing graphics hardware and portable via standard graphics API's. Interactive walkthroughs of viewindependent nondiffuse global illumination solutions are explored as the motivating application. matt  Matt Pharr Neoptica http://neoptica.com 
From: Mark Wayland <Mwayland@to...>  20060328 23:42:16

Hi all, I was wondering if someone might be able to 'shed some light' on where I might start in working out, for a moderate number of polygons, what set of runtime lights (both directional and point, up to a total of 3 or 4) would best approximate the lighting found in the vertex colours of the polygons? Essentially, we want to perform a global lighting solution on a level and then calculate, for groups of objects, the runtime lighting that can be used to generate a rough approximation of that lighting (not for lighting a player, although this may be bonus, but to dynamically light the level). Thanks in advance, Mark 
From: Robert Dibley <blimey.rob@go...>  20060328 22:24:44

Considering that all he is after is a rough metric for determining whether he is "close" to a mesh with his convex hull, I would have thought that cheating would be perfectly reasonable  for example I would choose to use the very simple: Metric = average distance of the three vertex pairs * average area of the two triangles Doubtless not as accurate, but quick to compute and would probably give a reasonable metric for such tests. Regards Robert > Original Message > From: gdalgorithmslistadmin@... [mailto:gdalgorithms > listadmin@...] On Behalf Of > christer_ericson@... > Sent: 28 March 2006 23:18 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Volume calculation for a two nonparallel > triangles connected at the edges > > > John Ratcliff wrote: > > Ok, as promised here is a code snippet that computes the volume of a > convex > > mesh composed of triangles. > > Sure, but that's not the problem you posted. As Richard Mitton and > Greg James already pointed out, the object you described has non > planar faces and is neither mesh nor polyhedron. But perhaps the > polyhedral approximation that is the triangulation and flattening > of the side faces is sufficient? > > An exact solution would require, I think, integrating over the > surface of the shape ala Stokes' Theorem. The nonplanar sides > seems like it would make it much more iffy than applying Stokes > on a polyhedron (which is really what the above two code snippets > do). > > > Christer Ericson, Director of Tools and Technology > Sony Computer Entertainment, Santa Monica > > > >  > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the live > webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.asus.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: <christer_ericson@pl...>  20060328 22:19:19

John Ratcliff wrote: > Ok, as promised here is a code snippet that computes the volume of a convex > mesh composed of triangles. Sure, but that's not the problem you posted. As Richard Mitton and Greg James already pointed out, the object you described has non planar faces and is neither mesh nor polyhedron. But perhaps the polyhedral approximation that is the triangulation and flattening of the side faces is sufficient? An exact solution would require, I think, integrating over the surface of the shape ala Stokes' Theorem. The nonplanar sides seems like it would make it much more iffy than applying Stokes on a polyhedron (which is really what the above two code snippets do). Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica 
From: <robin_green@pl...>  20060328 18:38:18

Richard Wareham wrote: > On Mon, Mar 27, 2006 at 10:40:26AM 0800, robin_green@... wrote: >> >> In our experiments with GA, it really became clear that the problem was mapping >> the 32x32 vectormatrix multiplies into 4way SIMD machines. > > This is true if you go for trying to compute general multivector, > multivector products which is the Wrong Way (TM) to do it. I should have been clearer, I fully understand the sparseness of the product matrices and the process of reducing the operation to only the nonzero products. I was just wondering out loud if maybe "wasting" a few operations would allow more parallelization. > The work done to compute the dot product is > /exactly/ that of computing the classical dot product and the work done > to compute the bivector part is /exactly/ that of the crossproduct. I absolutely agree that GA operations are just another expression of LA operations and will, when properly factored, take exactly the same number of FLOPs. The FLOPS are not my problem, it's the surrounding logic and packaging overhead that I dislike. >> Do you know of any work on defining an abstract machine that would execute GA >> operations efficiently? > > You can use higher level knowledge to do these things. The following discussion is an example of exactly the problem I am concerned with. I agree with you that, by tracking the grades of arguments we can chain together optimised operations that do the minimum work necessary, but in order to do this we must have apriori information on the expected inputs and outputs. Both you and Christian Schuler propose using compiletime type systems (e.g. partially specialized templates) to produce more optimal code  to code a GA expression and cook it down at compile time to an optimized set of SIMD ops, baking in all the assumptions about input types and grades as you go. My problem is not with the optimality of GA, it's with runtime types. Any objectoriented implementation will eventually have to solve the runtime typing problem  this is especially of GA as it sells itself on the fact that common GA operations have good, robust geometric interpretations even when different grades are used as inputs. The operation to find the MEET of a planeplane is the same operation that calculates the MEET of a linesphere. Without compiletime knowledge of the types of our inputs we *still* have to generate all the possible combinations and use a dispatch mechanism to select the correct operation. All the baking did was to shift the dispatch, repackaging and grade classification problem to a higher level. My contention is this: LA always had strong typing of its inputs so we just knuckled down and got on with it. GA does not have these limitations, but our languages and platforms do. I suggest we design new platforms.  Robin Green. 
From: Jeremiah Zanin <jeremiahz@vo...>  20060328 14:26:45

Yes, very clever. I implemented a buoyancy system very similar to the = one described in your article for our current game, except I wasn't so = clever and precomputed all the tetrahedra for our collision models. And the = silly thing is...I use the surface triangles for calculating the submerged = surface area for drag! Doh! ________________________________________ From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of = Erin Catto Sent: Tuesday, March 28, 2006 12:20 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Volume calculation for a two nonparallel triangles connected at the edges BTW, a little plug here. You can find a discussion of=A0polyhedra = volume calculation in the context of buoyancy in GPG6. =A0 
From: <c.schueler@ph...>  20060328 12:26:39

It is possible to use your compiler as the machine. I tried this once it is very tedious typing, but was fun to get to grips = with GA nonetheless. There also exist automatic code generators to generate such algebras, = but I can't name one at the moment. Suppose you are doing a GA library in CL3+1 space (3dim space + 1 = homogeneous coordinate). You can have class Point { float x, y, z, w }; class Line { float yz, zx, xy, xw, yw, zw }; class Plane { float wyz, wzx, wxy, xyz }; class Volume { float wzyx; } Now you get to define operator ^ (join), the wedge product. Then you = have Line operator ^( Point, Point ); Plane operator ^( Line, Point ); Plane operator ^( Point, Line ); etc. so you can build a plane from 3 points, or a point and a line like: Point A, B, C; Plane P =3D A ^ B ^ C; and probably you want to have a sandwichoperator to represent the = famous RxR~ operation so you can rotate any of the objects with quaternions.=20 A general dualfunction=20 float dual( Volume ); Point dual( Plane ); Line dual( Line ); etc... can be used to build a meettemplate (I hope the formula is correct) template< type A, type B, type R > R meet( A, B ) { return dual( dual(A) ^ B ); } I hope I'm making the point clear. There exist a plethora of other possible combinations as well. Original Message From: gdalgorithmslistadmin@... = [mailto:gdalgorithmslistadmin@...] On Behalf Of = robin_green@... Sent: Monday, March 27, 2006 8:40 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Geomerics. Richard Wareham wrote: > > What most GA users at the moment do is develop huge GA libraries that > let them directly transliterate final equations into code. This is = often > massively redundant. Similarly one develops equations in linear = algebra > and instead of transliterating them directly one optimises them into = dot > products and SIMD operations. In our experiments with GA, it really became clear that the problem was = mapping the 32x32 vectormatrix multiplies into 4way SIMD machines. Each = element of a GA operation can be executed in parallel but each step of the GA = algorithm has to be serialized, leading to a nasty startstop style of execution that = *hurts*. It also leads to a design of library that relies on holding values in a = handful of compact representations (blades) and finding the optimal operation = between these blades by double or multipledispatch. One problem is that you don't know beforehand (well, I didn't) which representation is going to emerge from the preceding operation, leading = to small serialized batches of parallel multiplyadds interspersed with frantic, = non SIMD friendly casting, shuffling and memory movement ops. Do you know of any work on defining an abstract machine that would = execute GA operations efficiently? Would a machine with wider SIMD operations be = more efficient because the redundant multiplybyzero operations take no = longer than the ones that carry information? What would be the useful set of GA = operations this machine would have to encode? wedge product, dot product, add, = subtract, sure, but would adding a "meet" operation at the hardware level greatly = increase the efficiency of the abstract machine? Is there any proof that = multivectors are never generated by any useful Geometric algorithm, so that blade = operations are all we'll ever need to code? Just asking, like.  Robin Green.  This SF.Net email is sponsored by xPML, a groundbreaking scripting = language that extends applications into web and mobile media. Attend the live = webcast and join the prime developer group breaking into this new coding = territory! http://sel.asus.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Robert Dibley <blimey.rob@go...>  20060328 11:54:43

Ahh, sorry, so correct me if I'm wrong, but reading this I presume that what you have is two sets of point data, which form upward sloping lines, and you are looking for a height where the distance between the two lines is equal to a fixed value. Unfortunately there are likely to be cases where the answer is none, some or infinitely many solutions. Do you know anything else about the curves . e.g. do you know that they always get steeper as they go along ? Or that they start and end at certain values ? The best solution I can think of (without further information) is to invert your problem, so looking at each known point in either curve, find the separation between the two curves at the height of that point, then use those results to find which (if any) line segments meet your criteria at some point along their length. There seems little point in going for anything more than linear. And its nice and easy to find the intersections with a piecewise linear approach. Robert _____ From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Sindharta Tanuwijaya Sent: 28 March 2006 12:01 To: gdalgorithmslist@... Subject: RE: [Algorithms] Non Linear Programming ? Actually for x() and y(), I only have groups of points that represents a curve, and if possible I don't want to do curve fitting. Is it still possible to do Lagrange multipliers in this situation? The other solution that Robert Dibley suggested was inspiring, but in my case, at the end, I believe that I would still have to implement binary search to get the value of a. Sin Willem de Boer <wdeboer@...> wrote: Do you have parametric forms for x and y? Consider the function f(a,b) = x(a)  x(b)^2. We want to minimise f(a,b) with the constraint that a+b=c, or 0=g(a,b):=a+bc. This problem could be solved with Lagrange multipliers.  Willem _____ _____ Yahoo! <http://us.rd.yahoo.com/mail_us/taglines/postman3/*http:/us.rd.yahoo.com/evt =39666/*http:/beta.messenger.yahoo.com> Messenger with Voice. PCtoPhone calls for ridiculously low rates. 