Thread: [Algorithms] spline name
Brought to you by:
vexxed72
From: Jarkko L. <al...@gm...> - 2008-11-04 11:10:32
|
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 V. <and...@ni...> - 2008-11-04 11:59:57
|
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:al...@gm...] 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 L. <al...@gm...> - 2008-11-04 12:25:39
|
I don't think it's cubic Hermite curve since it's defined with 4 points rather than 2 points + their tangents. I think Catmull-Rom 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:and...@ni...] 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:al...@gm...] 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 V. <and...@ni...> - 2008-11-04 12:31:52
|
A Catmull-Rom 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:al...@gm...] Sent: 04 November 2008 12:26 To: and...@ni...; '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 Catmull-Rom 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:and...@ni...] 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:al...@gm...] 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 L. <al...@gm...> - 2008-11-04 12:39:39
|
Well, with the same logic you could call it to B-spline or Bezier spline since any cubic spline can be transformed to another ;) Cheers, Jarkko _____ From: Andrew Vidler [mailto:and...@ni...] Sent: Tuesday, November 04, 2008 2:33 PM To: 'Game Development Algorithms' Subject: Re: [Algorithms] spline name A Catmull-Rom 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:al...@gm...] Sent: 04 November 2008 12:26 To: and...@ni...; '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 Catmull-Rom 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:and...@ni...] 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:al...@gm...] 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 F. <sim...@po...> - 2008-11-04 12:43:14
|
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:and...@ni...] 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:al...@gm...] 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 V. <and...@ni...> - 2008-11-04 12:35:27
|
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:sim...@po...] Sent: 04 November 2008 12:28 To: and...@ni...; 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:and...@ni...] 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:al...@gm...] 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 L. <al...@gm...> - 2008-11-04 12:53:56
|
Yes, M_interp looks awfully familiar (: Cheers, Jarkko _____ From: Simon Fenney [mailto:sim...@po...] Sent: Tuesday, November 04, 2008 2:28 PM To: and...@ni...; 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:and...@ni...] 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:al...@gm...] 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 B. <wi...@wh...> - 2008-11-04 13:05:33
|
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:sim...@po...] Sent: Tuesday, November 04, 2008 2:28 PM To: and...@ni...; 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:and...@ni...] 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:al...@gm...] 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://moblin-contest.org/redirect.php?banner_id=100&url=/ ------------------------------------------------------------------------------ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jarkko L. <al...@gm...> - 2008-11-04 13:22:00
|
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:wi...@wh...] 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:al...@gm...> To: 'Game Development Algorithms' <mailto:gda...@li...> 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:sim...@po...] Sent: Tuesday, November 04, 2008 2:28 PM To: and...@ni...; 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:and...@ni...] 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:al...@gm...] 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://moblin-contest.org/redirect.php?banner_id=100&url=/ _____ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Robin G. <rob...@gm...> - 2008-11-04 16:49:34
|
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 <sim...@po...>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 W. <jw...@gm...> - 2008-11-04 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 (pre-computed) polyphase interpolator, for example. Additionally, I've used it in 2D for interpolating height maps to get smoother sub-sample 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 L. <al...@gm...> - 2008-11-04 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:jw...@gm...] 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 (pre-computed) polyphase interpolator, for example. Additionally, I've used it in 2D for interpolating height maps to get smoother sub-sample 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://moblin-contest.org/redirect.php?banner_id=100&url=/ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Sam Y. <sam...@gm...> - 2008-11-05 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 B. <wb...@gm...> - 2008-11-05 12:10:51
|
You can do Jacobi iterations, which are more or less the same thing as Gauss-Seidel without the intermediate results. Or you can do red-black gauss-seidel 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 G-S, 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...@gm...> 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://moblin-contest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: Anders N. <ja...@an...> - 2008-11-12 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 <al...@gm...> 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://moblin-contest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Jarkko L. <al...@gm...> - 2008-11-13 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:ja...@an...] 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 <al...@gm...> 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://moblin-contest.org/redirect.php?banner_id=100&url=/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------- 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://moblin-contest.org/redirect.php?banner_id=100&url=/ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |