## Re: [Algorithms] Multivariant curve fitting

 Re: [Algorithms] Multivariant curve fitting From: David Neubelt - 2009-03-10 19:12:13 ```Matthew, You can read up on moving least squares http://www.ams.org/mcom/1998-67-224/S0025-5718-98-00974-0/S0025-5718-98- 00974-0.pdf For that matter, I believe least squares works in n-dimensions I just never tried it. Also, discrete wavelets are used in image compression (essentialy a 2d function, f(x,y) = col) and I could imagine that they can be applied to your problem. Of course, wavelets are not smooth and require a lot of terms to approximate a quarter wave sinusoidal function. Though wavelets have a lot of really nice properties so it may be something to consider. What I've also done in the past is picked the strongest qualities of a function, such as at F(0) = 0, around F(0) looks like cos(theta), f'(1) = 0. I would then pick a polynomial that matches my number of constraints and solve for the coefficients. That usually gives really nice results because I'm choosing where the error should be really close and if I can choose a low number of constraints then I can have a low number of coeffecients which makes the approximation fast and accurate. Of course with this method I know what my function needs to look like so I can 'craft' the approximating function easily. If you're getting an unknown function this approach won't work. Shlick used this technique in his Fresnel approximation. Here is his example from his paper, For approximation sin(x) on the range[0, pi/2] f(0) = 0, f'(0) = 1, f(pi/2) = 1, f'(pi/2) = 0 // some constraints he said the function generally satisfies f(x) = (x^2 + ax + b)/(cx + d) // an approximating function The conditions leads to system of four equations {b = 0, {a = d, {a = pi/2 = c + 2a/pi {cpi^2 + 4pia + fa^2 giving the follow approximation of f(x) = sin x f(x) = x * (u + x) / (u + vx) with u = -pi^2 / 4 and v = pi + u His experimental tests showed the relative error of 1.4% and speed up factor of 230%. Incidentally, his fresnel approximation had a .6% error and a 3180% speed up :) -= Dave -----Original Message----- From: Matt J [mailto:mjohnson2005@...] Sent: Monday, March 09, 2009 6:11 PM To: Game Development Algorithms Subject: [Algorithms] Multivariant curve fitting How can I approximate a function such as func(a, b) = using polynomials? Right now I can use Maple and minimax to generate an approximation for any function that can be derived over a given domain. However it is not clear to me how I can extend that function into multiple variables, e.g. func(t, theta) , t = 0..1, theta = (-PI, PI) My numerical approximation book covers least square fitting of non-linear function for a single variable and a linear function for a multivariant function, so it seems like it may be possible to extend that to a multi-variable non-linear function. Is this the right approach or is there another way to do this? One issue with this approach is I'd have to generate a lot of data from my reference function (and it isn't clear how big dt or d(theta) steps would be to get an optimal solution) and I imagine it would be slow. Note that the latter isn't an issue, since I would generate it offline Matthew ------------------------------------------------------------------------ ------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t ```

### Thread view

 [Algorithms] Multivariant curve fitting From: Matt J - 2009-03-10 01:10:40 ```How can I approximate a function such as func(a, b) = using polynomials? Right now I can use Maple and minimax to generate an approximation for any function that can be derived over a given domain. However it is not clear to me how I can extend that function into multiple variables, e.g. func(t, theta) , t = 0..1, theta = (-PI, PI) My numerical approximation book covers least square fitting of non-linear function for a single variable and a linear function for a multivariant function, so it seems like it may be possible to extend that to a multi-variable non-linear function. Is this the right approach or is there another way to do this? One issue with this approach is I'd have to generate a lot of data from my reference function (and it isn't clear how big dt or d(theta) steps would be to get an optimal solution) and I imagine it would be slow. Note that the latter isn't an issue, since I would generate it offline Matthew ```
 Re: [Algorithms] Multivariant curve fitting From: Amir Ebrahimi - 2009-03-10 02:17:43 Attachments: Message as HTML ```On Mon, Mar 9, 2009 at 5:10 PM, Matt J wrote: > How can I approximate a function such as func(a, b) = using polynomials? > Taylor series, possibly? http://en.wikipedia.org/wiki/Taylor_series#Taylor_series_in_several_variables ::Amir ```
 Re: [Algorithms] Multivariant curve fitting From: Jon Olick - 2009-03-10 06:03:19 Attachments: Message as HTML ```Hi Matt, The way I've done this in the past is to first define the number of degrees you want the polynomial to have. Degree >= than 3 gives a continuous non-linear curve which sounds like what you want. For degree 3 it would look something like: f(a,b) = c0*a*a + c1*b*b + c2*a*b + c3*a + c4*b + c5 You then reform this into a Ax = b problem. You can do this by having x be the unknown constants [c0 c1 c2 c3 c4 c5]. Set A as a m by 6 matrix [a*a b*b a*b a b 1] and set b as the m by 1 matrix of the values you get for f(a,b). Where m is the number of function samples. Solve the Ax = b like usual and you have your constants. And yeah, its not going to be very fast if m is large. ;) Best, Jon Olick On Mon, Mar 9, 2009 at 8:10 PM, Matt J wrote: > How can I approximate a function such as func(a, b) = using polynomials? > > Right now I can use Maple and minimax to generate an approximation for > any function that can be derived over a given domain. > > However it is not clear to me how I can extend that function into > multiple variables, e.g. func(t, theta) , t = 0..1, theta = (-PI, PI) > > My numerical approximation book covers least square fitting of > non-linear function for a single variable and a linear function for a > multivariant function, so it seems like it may be possible to extend > that to a multi-variable non-linear function. Is this the right > approach or is there another way to do this? One issue with this > approach is I'd have to generate a lot of data from my reference > function (and it isn't clear how big dt or d(theta) steps would be to > get an optimal solution) and I imagine it would be slow. Note that the > latter isn't an issue, since I would generate it offline > > Matthew > > > ------------------------------------------------------------------------------ > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > ```
 Re: [Algorithms] Multivariant curve fitting From: Jeremiah Zanin - 2009-03-10 14:44:20 ```I saw this on Insomniac's R&D page awhile back, perhaps it would help: http://www.insomniacgames.com/tech/articles/0209/ramezexchange.php On Mon, Mar 9, 2009 at 8:10 PM, Matt J wrote: How can I approximate a function such as func(a, b) = using polynomials? Right now I can use Maple and minimax to generate an approximation for any function that can be derived over a given domain. However it is not clear to me how I can extend that function into multiple variables, e.g. func(t, theta) , t = 0..1, theta = (-PI, PI) My numerical approximation book covers least square fitting of non-linear function for a single variable and a linear function for a multivariant function, so it seems like it may be possible to extend that to a multi-variable non-linear function. Is this the right approach or is there another way to do this? One issue with this approach is I'd have to generate a lot of data from my reference function (and it isn't clear how big dt or d(theta) steps would be to get an optimal solution) and I imagine it would be slow. Note that the latter isn't an issue, since I would generate it offline Matthew ------------------------------------------------------------------------ ------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t ------------------------------------------------------------------------------------------------------------------------- This message, including any attachments, may contain privileged and/or confidential information. Any distribution or use of this email by anyone other than the intended recipient(s) is strictly prohibited. If you are not the intended recipient, please notify the sender immediately and delete all copies. Thank you. ```
 Re: [Algorithms] Multivariant curve fitting From: Matt J - 2009-03-11 21:21:40 ```This sounds like a possible approach if you can extend the Remez algorithm to 2D because you can extend newton's algorithm to 2D as well. If a more perfect curve can be formed iteratively by looking for the local minimum or maximums in a 1D curve after sampling a certain number of points (why do I have a feeling this is related to Nyquist limit?), then why not extend that iterative method to a more perfect 2D surface by looking at the gradient (and Hessian matrix). I've never done this before, but it seems possible. > I saw this on Insomniac's R&D page awhile back, perhaps it would help: > > http://www.insomniacgames.com/tech/articles/0209/ramezexchange.php > > On Mon, Mar 9, 2009 at 8:10 PM, Matt J wrote: > How can I approximate a function such as func(a, b) = using polynomials? > > Right now I can use Maple and minimax to generate an approximation for > any function that can be derived over a given domain. > > However it is not clear to me how I can extend that function into > multiple variables, e.g. func(t, theta) , t = 0..1, theta = (-PI, PI) > > My numerical approximation book covers least square fitting of > non-linear function for a single variable and a linear function for a > multivariant function, so it seems like it may be possible to extend > that to a multi-variable non-linear function. Is this the right > approach or is there another way to do this? One issue with this > approach is I'd have to generate a lot of data from my reference > function (and it isn't clear how big dt or d(theta) steps would be to > get an optimal solution) and I imagine it would be slow. Note that the > latter isn't an issue, since I would generate it offline > ```
 Re: [Algorithms] Multivariant curve fitting From: David Neubelt - 2009-03-10 19:12:13 ```Matthew, You can read up on moving least squares http://www.ams.org/mcom/1998-67-224/S0025-5718-98-00974-0/S0025-5718-98- 00974-0.pdf For that matter, I believe least squares works in n-dimensions I just never tried it. Also, discrete wavelets are used in image compression (essentialy a 2d function, f(x,y) = col) and I could imagine that they can be applied to your problem. Of course, wavelets are not smooth and require a lot of terms to approximate a quarter wave sinusoidal function. Though wavelets have a lot of really nice properties so it may be something to consider. What I've also done in the past is picked the strongest qualities of a function, such as at F(0) = 0, around F(0) looks like cos(theta), f'(1) = 0. I would then pick a polynomial that matches my number of constraints and solve for the coefficients. That usually gives really nice results because I'm choosing where the error should be really close and if I can choose a low number of constraints then I can have a low number of coeffecients which makes the approximation fast and accurate. Of course with this method I know what my function needs to look like so I can 'craft' the approximating function easily. If you're getting an unknown function this approach won't work. Shlick used this technique in his Fresnel approximation. Here is his example from his paper, For approximation sin(x) on the range[0, pi/2] f(0) = 0, f'(0) = 1, f(pi/2) = 1, f'(pi/2) = 0 // some constraints he said the function generally satisfies f(x) = (x^2 + ax + b)/(cx + d) // an approximating function The conditions leads to system of four equations {b = 0, {a = d, {a = pi/2 = c + 2a/pi {cpi^2 + 4pia + fa^2 giving the follow approximation of f(x) = sin x f(x) = x * (u + x) / (u + vx) with u = -pi^2 / 4 and v = pi + u His experimental tests showed the relative error of 1.4% and speed up factor of 230%. Incidentally, his fresnel approximation had a .6% error and a 3180% speed up :) -= Dave -----Original Message----- From: Matt J [mailto:mjohnson2005@...] Sent: Monday, March 09, 2009 6:11 PM To: Game Development Algorithms Subject: [Algorithms] Multivariant curve fitting How can I approximate a function such as func(a, b) = using polynomials? Right now I can use Maple and minimax to generate an approximation for any function that can be derived over a given domain. However it is not clear to me how I can extend that function into multiple variables, e.g. func(t, theta) , t = 0..1, theta = (-PI, PI) My numerical approximation book covers least square fitting of non-linear function for a single variable and a linear function for a multivariant function, so it seems like it may be possible to extend that to a multi-variable non-linear function. Is this the right approach or is there another way to do this? One issue with this approach is I'd have to generate a lot of data from my reference function (and it isn't clear how big dt or d(theta) steps would be to get an optimal solution) and I imagine it would be slow. Note that the latter isn't an issue, since I would generate it offline Matthew ------------------------------------------------------------------------ ------ _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t ```
 Re: [Algorithms] Multivariant curve fitting From: Jon Watte - 2009-03-11 20:40:45 ```Matt J wrote: > How can I approximate a function such as func(a, b) = using polynomials? > Doesn't Taylor work in 2D? You get terms like C, ka+C, kb+C, ka2+ka+C, ka2+ka+kb+C, ka2+ka+kb2+kb+C, ka+kb2+kb+c, kb2+kb+C, ... (with varying k). Plug in the derivatives relative to a and b at each point, like regular Taylor approximation, and see what comes out! Sincerely, jw ```
 Re: [Algorithms] Multivariant curve fitting From: David Neubelt - 2009-03-11 21:07:51 ```Jon Watte wrote, > Doesn't Taylor work in 2D? Taylor works in 2D but Taylor is best used in situations where you need accuracy in a localized region. If he's looking for an approximation of a function in a global domain then using Chebyshev or Remez's algorithm, like the other poster suggested, is much better. If the function has periocity then Fourier is better. -= Dave -----Original Message----- From: Jon Watte [mailto:jwatte@...] Sent: Wednesday, March 11, 2009 1:41 PM To: Game Development Algorithms Subject: Re: [Algorithms] Multivariant curve fitting Matt J wrote: > How can I approximate a function such as func(a, b) = using polynomials? > Doesn't Taylor work in 2D? You get terms like C, ka+C, kb+C, ka2+ka+C, ka2+ka+kb+C, ka2+ka+kb2+kb+C, ka+kb2+kb+c, kb2+kb+C, ... (with varying k). Plug in the derivatives relative to a and b at each point, like regular Taylor approximation, and see what comes out! Sincerely, jw ------------------------------------------------------------------------ ------ Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are powering Web 2.0 with engaging, cross-platform capabilities. Quickly and easily build your RIAs with Flex Builder, the Eclipse(TM)based development software that enables intelligent coding and step-through debugging. Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t ```

## Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

No, thanks