From: Jarkko Lempiainen <altairx@gm...>  20081104 11:10:32
Attachments:
Message as HTML

Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko 
From: Andrew Vidler <andrew.vidler@ni...>  20081104 11:59:57
Attachments:
Message as HTML

I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ 
From: Jarkko Lempiainen <altairx@gm...>  20081104 12:25:39
Attachments:
Message as HTML

I don't think it's cubic Hermite curve since it's defined with 4 points rather than 2 points + their tangents. I think CatmullRom would be a closer match, but it doesn't go through all the points within t=[0, 1] interval. Cheers, Jarkko _____ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: Tuesday, November 04, 2008 1:38 PM To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ 
From: Andrew Vidler <andrew.vidler@ni...>  20081104 12:31:52
Attachments:
Message as HTML

A CatmullRom spline is just a Cubic Hermite with a certain scheme for working out the tangents. :) See further down the Wikipedia page for details. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 12:26 To: andrew.vidler@...; 'Game Development Algorithms' Subject: RE: [Algorithms] spline name I don't think it's cubic Hermite curve since it's defined with 4 points rather than 2 points + their tangents. I think CatmullRom would be a closer match, but it doesn't go through all the points within t=[0, 1] interval. Cheers, Jarkko _____ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: Tuesday, November 04, 2008 1:38 PM To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ 
From: Jarkko Lempiainen <altairx@gm...>  20081104 12:39:39
Attachments:
Message as HTML

Well, with the same logic you could call it to Bspline or Bezier spline since any cubic spline can be transformed to another ;) Cheers, Jarkko _____ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: Tuesday, November 04, 2008 2:33 PM To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name A CatmullRom spline is just a Cubic Hermite with a certain scheme for working out the tangents. :) See further down the Wikipedia page for details. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 12:26 To: andrew.vidler@...; 'Game Development Algorithms' Subject: RE: [Algorithms] spline name I don't think it's cubic Hermite curve since it's defined with 4 points rather than 2 points + their tangents. I think CatmullRom would be a closer match, but it doesn't go through all the points within t=[0, 1] interval. Cheers, Jarkko _____ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: Tuesday, November 04, 2008 1:38 PM To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ 
From: Simon Fenney <simon.fenney@po...>  20081104 12:43:14
Attachments:
Message as HTML

No. AFAICS (and assuming my maths is correct) the cubic spline Jarkko has described has the following basis matrix: [ 9 27 27 9] M_interp =1/2 [ 18 45 36 9] [11 18 9 2] [ 2 0 0 0] Whereas for a Hermite spline we have (from Foley et al) [ 2 2 1 1] M_hermite = [3 3 2 1] [0 0 1 0] [1 0 0 0] Simon ________________________________ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: 04 November 2008 11:38 To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. ________________________________ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ 
From: Andrew Vidler <andrew.vidler@ni...>  20081104 12:35:27
Attachments:
Message as HTML

Yes, quite possibly  but I think it's slightly ambiguous; you can also get a spline doing exactly what's described by using a Hermite and setting the tangents to: m0 = (1/6)( 54q(1/3)  27q(2/3)  33p0 + 6p1 ) m1 = (1/4)( 7p0 + 2m0 + 20p1  27P(2/3) (assuming I've worked it out right  quite possibly mistakes in there) :) Cheers, Andrew. _____ From: Simon Fenney [mailto:simon.fenney@...] Sent: 04 November 2008 12:28 To: andrew.vidler@...; Game Development Algorithms Subject: RE: [Algorithms] spline name No. AFAICS (and assuming my maths is correct) the cubic spline Jarkko has described has the following basis matrix: [ 9 27 27 9] M_interp =1/2 [ 18 45 36 9] [11 18 9 2] [ 2 0 0 0] Whereas for a Hermite spline we have (from Foley et al) [ 2 2 1 1] M_hermite = [3 3 2 1] [0 0 1 0] [1 0 0 0] Simon _____ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: 04 November 2008 11:38 To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ 
From: Jarkko Lempiainen <altairx@gm...>  20081104 12:53:56
Attachments:
Message as HTML

Yes, M_interp looks awfully familiar (: Cheers, Jarkko _____ From: Simon Fenney [mailto:simon.fenney@...] Sent: Tuesday, November 04, 2008 2:28 PM To: andrew.vidler@...; Game Development Algorithms Subject: Re: [Algorithms] spline name No. AFAICS (and assuming my maths is correct) the cubic spline Jarkko has described has the following basis matrix: [ 9 27 27 9] M_interp =1/2 [ 18 45 36 9] [11 18 9 2] [ 2 0 0 0] Whereas for a Hermite spline we have (from Foley et al) [ 2 2 1 1] M_hermite = [3 3 2 1] [0 0 1 0] [1 0 0 0] Simon _____ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: 04 November 2008 11:38 To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ 
From: Willem H. de Boer <willem@wh...>  20081104 13:05:33
Attachments:
Message as HTML

I know, it's called a Lempiainen curve! Seriously, there are many ways of defining a curve, many of which do not have a name, since it's fairly easy to come up with one and its basis matrix. Cheers, Willem  Original Message  From: Jarkko Lempiainen To: 'Game Development Algorithms' Sent: Tuesday, November 04, 2008 12:53 PM Subject: Re: [Algorithms] spline name Yes, M_interp looks awfully familiar (: Cheers, Jarkko  From: Simon Fenney [mailto:simon.fenney@...] Sent: Tuesday, November 04, 2008 2:28 PM To: andrew.vidler@...; Game Development Algorithms Subject: Re: [Algorithms] spline name No. AFAICS (and assuming my maths is correct) the cubic spline Jarkko has described has the following basis matrix: [ 9 27 27 9] M_interp =1/2 [ 18 45 36 9] [11 18 9 2] [ 2 0 0 0] Whereas for a Hermite spline we have (from Foley et al) [ 2 2 1 1] M_hermite = [3 3 2 1] [0 0 1 0] [1 0 0 0] Simon  From: Andrew Vidler [mailto:andrew.vidler@...] Sent: 04 November 2008 11:38 To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew.  From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________   This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblincontest.org/redirect.php?banner_id=100&url=/  _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Jarkko Lempiainen <altairx@gm...>  20081104 13:22:00
Attachments:
Message as HTML

I must applaud you for spelling my name right ;) But yeah, the motivation was just that I could call it with some recognizable name in code rather than invent something off the top of my head. I would have thought there is a name for it since it can be quite useful way for defining a curve. Cheers, Jarkko _____ From: Willem H. de Boer [mailto:willem@...] Sent: Tuesday, November 04, 2008 3:05 PM To: Game Development Algorithms Subject: Re: [Algorithms] spline name I know, it's called a Lempiainen curve! Seriously, there are many ways of defining a curve, many of which do not have a name, since it's fairly easy to come up with one and its basis matrix. Cheers, Willem  Original Message  From: Jarkko Lempiainen <mailto:altairx@...> To: 'Game Development Algorithms' <mailto:gdalgorithmslist@...> Sent: Tuesday, November 04, 2008 12:53 PM Subject: Re: [Algorithms] spline name Yes, M_interp looks awfully familiar (: Cheers, Jarkko _____ From: Simon Fenney [mailto:simon.fenney@...] Sent: Tuesday, November 04, 2008 2:28 PM To: andrew.vidler@...; Game Development Algorithms Subject: Re: [Algorithms] spline name No. AFAICS (and assuming my maths is correct) the cubic spline Jarkko has described has the following basis matrix: [ 9 27 27 9] M_interp =1/2 [ 18 45 36 9] [11 18 9 2] [ 2 0 0 0] Whereas for a Hermite spline we have (from Foley et al) [ 2 2 1 1] M_hermite = [3 3 2 1] [0 0 1 0] [1 0 0 0] Simon _____ From: Andrew Vidler [mailto:andrew.vidler@...] Sent: 04 November 2008 11:38 To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name I think you've just found a way of specifying the tangents for a cubic hermite curve? http://en.wikipedia.org/wiki/Cubic_Hermite_spline If you look at the formula for q(1/3) and q(2/3) then you'll get two equations in terms of the endpoints and the tangent at each endpoint  just rearranging for the tangents gives you two equations (one for each tangent) in terms of the endpoints and q(1/3), q(2/3)  which is what you've got. Unless there's some other characteristic of the spline that means it's not a Hermite? Cheers, Andrew. _____ From: Jarkko Lempiainen [mailto:altairx@...] Sent: 04 November 2008 11:10 To: 'Game Development Algorithms' Subject: [Algorithms] spline name Hi, Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) Cheers, Jarkko ______________________________________________________________________ This email has been scanned by the MessageLabs Email Security System. For more information please visit http://www.messagelabs.com/email ______________________________________________________________________ _____  This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblincontest.org/redirect.php?banner_id=100&url=/ _____ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Robin Green <robin.green@gm...>  20081104 16:49:34
Attachments:
Message as HTML

I don't know the name of that specific spline, but the family of interpolating splines (as opposed to approximating splines) derived from the Hermite are called "Cardinal Splines". http://www.bobpowell.net/cardinalspline.htm Essentially you take a Hermite and mess with the vector lengths to get various controls, commonly "tension" and "bias" and "continuity".  Robin Green. On Tue, Nov 4, 2008 at 4:28 AM, Simon Fenney <simon.fenney@...>wrote: > No. AFAICS (and assuming my maths is correct) the cubic spline Jarkko has > described has the following basis matrix: > [ 9 27 27 9] > M_interp =1/2 [ 18 45 36 9] > [11 18 9 2] > [ 2 0 0 0] > > Whereas for a Hermite spline we have (from Foley et al) > [ 2 2 1 1] > M_hermite = [3 3 2 1] > [0 0 1 0] > [1 0 0 0] > > Simon > 
From: Jon Watte <jwatte@gm...>  20081104 18:03:23

Jarkko Lempiainen wrote: > > Does anyone know if there is a name for a cubic spline which goes > through all the defined control points p0..p3 in the interval t=[0, > 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the > basis matrix for it, but don’t know what’s the name of the wheel I > just reinvented ;) > I would call that an "interpolating cubic spline" (or even "the interpolating ..."). It's used a lot in 1D, where it is a fast and cheap interpolator for sample rate conversion where you want continuous pitch bend and can't use a (precomputed) polyphase interpolator, for example. Additionally, I've used it in 2D for interpolating height maps to get smoother subsample areas. However, when you have a spline longer than 4 control points, you typically formulate it so that p0 is at t(1), p1 is at t(0), p2 is at t(1) and p3 is at t(2). Then you slide the entire set of control points over and start over from a new "t(0)" after reaching t(1). That way, you get an arbitrary length C1 continuous spline that interpolates all the points. Sincerely, jw 
From: Jarkko Lempiainen <altairx@gm...>  20081104 18:30:21

Thanks Jon. I think there's quite good consensus with the name now (: I'm using this in generalized curve fitting in arbitrary dimensions (e.g. rotation & translation compression of animation data). Cheers, Jarkko Original Message From: Jon Watte [mailto:jwatte@...] Sent: Tuesday, November 04, 2008 8:03 PM To: Game Development Algorithms Subject: Re: [Algorithms] spline name Jarkko Lempiainen wrote: > > Does anyone know if there is a name for a cubic spline which goes > through all the defined control points p0..p3 in the interval t=[0, > 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the > basis matrix for it, but don't know what's the name of the wheel I > just reinvented ;) > I would call that an "interpolating cubic spline" (or even "the interpolating ..."). It's used a lot in 1D, where it is a fast and cheap interpolator for sample rate conversion where you want continuous pitch bend and can't use a (precomputed) polyphase interpolator, for example. Additionally, I've used it in 2D for interpolating height maps to get smoother subsample areas. However, when you have a spline longer than 4 control points, you typically formulate it so that p0 is at t(1), p1 is at t(0), p2 is at t(1) and p3 is at t(2). Then you slide the entire set of control points over and start over from a new "t(0)" after reaching t(1). That way, you get an arbitrary length C1 continuous spline that interpolates all the points. Sincerely, jw  This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblincontest.org/redirect.php?banner_id=100&url=/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Sam Yatchmenoff <sam.yatchmenoff@gm...>  20081105 10:16:42

It seems to me that you cannot implement the gauss seidel method directly on a gpu because it uses intermediate results that you won't have access to on the same pass. Is there some trick to doing this or perhaps an equivalent method that can be implemented on a gpu? Sam Y 
From: Bill Baxter <wbaxter@gm...>  20081105 12:10:51

You can do Jacobi iterations, which are more or less the same thing as GaussSeidel without the intermediate results. Or you can do redblack gaussseidel where you update all the "red squares" in one pass, then the "black squares" in the second pass (red and black are staggered like a checkerboard). Those don't converge quite as fast as GS, but none of them is particularly great at removing low frequency residuals. For that you need to use a multigrid strategy. I think there are several papers on the topic of GPU multigrid solvers. bb On Wed, Nov 5, 2008 at 7:16 PM, Sam Yatchmenoff <sam.yatchmenoff@...> wrote: > It seems to me that you cannot implement the gauss seidel method > directly on a gpu because it uses intermediate results that you won't > have access to on the same pass. Is there some trick to doing this or > perhaps an equivalent method that can be implemented on a gpu? > > Sam Y > >  > This SF.Net email is sponsored by the Moblin Your Move Developer's challenge > Build the coolest Linux based applications with Moblin SDK & win great prizes > Grand prize is a trip for two to an Open Source event anywhere in the world > http://moblincontest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Anders Nilsson <jag@an...>  20081112 10:15:20

Hi Jarkko! Just to throw in another name in this discussion, there is something called Lagrange Interpolating Polynomial: http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html It creates a polynomial that passes through all of the points. Also Newton Polynomial (http://en.wikipedia.org/wiki/Newton_polynomial) could be mentioned. These doesn't take the fact that you have exactly 0, 1/3, 2/3, 1 as your coordinates though so a more fitting name might exists! Either way the nice thing here is that given the number of points and the order of the polynomial, there is only one solution so any name/method will do! Cheers, Anders Nilsson. On Tue, Nov 4, 2008 at 12:10 PM, Jarkko Lempiainen <altairx@...> wrote: > > Hi, > > > > Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) > > > > > > Cheers, Jarkko > > > >  > This SF.Net email is sponsored by the Moblin Your Move Developer's challenge > Build the coolest Linux based applications with Moblin SDK & win great prizes > Grand prize is a trip for two to an Open Source event anywhere in the world > http://moblincontest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Jarkko Lempiainen <altairx@gm...>  20081113 07:13:49

Ah, good to know. I actually implemented also a version of cubic spline setup which allows you to define t values for p1 and p2. Slightly more complex, but can be practical in some cases. Cheers, Jarkko Original Message From: Anders Nilsson [mailto:jag@...] Sent: Wednesday, November 12, 2008 12:15 PM To: Game Development Algorithms Subject: Re: [Algorithms] spline name Hi Jarkko! Just to throw in another name in this discussion, there is something called Lagrange Interpolating Polynomial: http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html It creates a polynomial that passes through all of the points. Also Newton Polynomial (http://en.wikipedia.org/wiki/Newton_polynomial) could be mentioned. These doesn't take the fact that you have exactly 0, 1/3, 2/3, 1 as your coordinates though so a more fitting name might exists! Either way the nice thing here is that given the number of points and the order of the polynomial, there is only one solution so any name/method will do! Cheers, Anders Nilsson. On Tue, Nov 4, 2008 at 12:10 PM, Jarkko Lempiainen <altairx@...> wrote: > > Hi, > > > > Does anyone know if there is a name for a cubic spline which goes through all the defined control points p0..p3 in the interval t=[0, 1], so that q(0)=p0, q(1/3)=p1, q(2/3)=p2 and q(1)=p3? I solved the basis matrix for it, but don't know what's the name of the wheel I just reinvented ;) > > > > > > Cheers, Jarkko > > > >  > This SF.Net email is sponsored by the Moblin Your Move Developer's challenge > Build the coolest Linux based applications with Moblin SDK & win great prizes > Grand prize is a trip for two to an Open Source event anywhere in the world > http://moblincontest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist  This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblincontest.org/redirect.php?banner_id=100&url=/ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 