Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo
Close
From: Amir Ebrahimi <gdlists@am...>  20090310 02:17:43
Attachments:
Message as HTML

On Mon, Mar 9, 2009 at 5:10 PM, Matt J <mjohnson2005@...> 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 
From: Matt J <mjohnson2005@gm...>  20090310 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 nonlinear 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 multivariable nonlinear 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 
From: Amir Ebrahimi <gdlists@am...>  20090310 02:17:43
Attachments:
Message as HTML

On Mon, Mar 9, 2009 at 5:10 PM, Matt J <mjohnson2005@...> 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 
From: Jon Olick <zelexi@gm...>  20090310 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 nonlinear 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 <mjohnson2005@...> 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 > nonlinear 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 multivariable nonlinear 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 > > >  > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist > 
From: Jeremiah Zanin <jeremiah.zanin@vo...>  20090310 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 <mjohnson2005@...> 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 nonlinear 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 multivariable nonlinear 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   _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis 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. 
From: Matt J <mjohnson2005@gm...>  20090311 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 <mjohnson2005@...> 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 > nonlinear 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 multivariable nonlinear 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 > 
From: David Neubelt <david@re...>  20090310 19:12:13

Matthew, You can read up on moving least squares http://www.ams.org/mcom/199867224/S0025571898009740/S0025571898 009740.pdf For that matter, I believe least squares works in ndimensions 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 nonlinear 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 multivariable nonlinear 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   _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis t 
From: Jon Watte <jwatte@gm...>  20090311 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 
From: David Neubelt <david@re...>  20090311 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, crossplatform capabilities. Quickly and easily build your RIAs with Flex Builder, the Eclipse(TM)based development software that enables intelligent coding and stepthrough debugging. Download the free 60 day trial. http://p.sf.net/sfu/wwwadobecom _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis t 