10 ms·

Superformula

176 points by GuiA 10y ago

arcanus 10y ago
How hard is it to invert? e.g. given a set of points along a particular curve, how difficult is it to find the values of the 6 parameters that generated it?
- vinchuco 10y ago
  If you know a,b,m,n1,n2,n3, and use sufficient points, you may be able to get an interpolated approximation. In general, one can fit many such curves through a finite set of points. http://math.stackexchange.com/questions/65970/can-a-function-be-found-to-fit-any-set-of-points http://math.stackexchange.com/questions/65970/can-a-function... A question originally asked by Leibniz to determine the measure of usefulness of a law. https://plus.maths.org/content/omega-and-why-maths-has-no-toes https://plus.maths.org/content/omega-and-why-maths-has-no-to.... If you don't have the 6 parameters, good luck. A unique inverse is defined only for injective functions.
- mturmon 10y ago
  Someone experimented with this. See the links at the bottom of the Wikipedia article. This seems misguided to me -- why use a curve family when fitting is so hard -- but it has been done.
pavel_lishin 10y ago
> Currently, the superformula is patented by Gielis, [2] but the patent was withdrawn in 2006 because of the patent fees not being paid.[3] I did not know you could patent a mathematical formula.
- cschmidt 10y ago
  no doubt it was something like "a system and method for generating natural shapes"
  - messe 10y ago
    "Method and apparatus for synthesizing patterns" https://www.google.com/patents/EP1177529B1?cl=en https://www.google.com/patents/EP1177529B1?cl=en
- gnoway 10y ago
  You can't, only its application. Genicap's patent does cover application in software though.
  - flashman 10y ago
    Even patenting a formula's application is becoming more restricted. In Australia and the US, the two relevant tests seem to be whether the formula does something a human can't, and whether the formula is used to 'improve' the operations of a computer or machine (e.g. if it made your hard drive faster or controlled a robotic arm). I had to look into this regarding an algorithm we're building and whether it's patentable. If your formula is a mere scheme or method implemented in a computer, it's likely to be rejected. The following links add detail: http://www.fisheradamskelly.com.au/2015/12/full-federal-court-of-australia-adds-some-clarity-to-when-business-methods-are-patentable/ http://www.fisheradamskelly.com.au/2015/12/full-federal-cour... https://en.wikipedia.org/wiki/Alice_Corp._v._CLS_Bank_International https://en.wikipedia.org/wiki/Alice_Corp._v._CLS_Bank_Intern... http://www.ipwatchdog.com/2016/05/13/federal-circuit-says-software-patent-claims-not-abstract-are-patent-eligible/id=69147/ http://www.ipwatchdog.com/2016/05/13/federal-circuit-says-so...
- kirrent 10y ago
  In most jurisdictions you can't really patent the use of an abstract mathematical formula on a computer with no gain, but that's something the law has only caught up to in the last decade. The patent is most likely invalid in the EU and US but was approved way back when those standards for invalidity didn't exist in their current forms. Of course, a court wouldn't need to be bound by the original decision of the examiner and would determine validity based on current case law and practice.
- kevin_thibedeau 10y ago
  You can't. On one, Gielis even put the equation in claim 1 but somehow they got the village idiot for an examiner. http://www.google.com/patents/US7620527 http://www.google.com/patents/US7620527
  - 0xmohit 10y ago
    Patent 5533051 [0] is a classic. Some quotes: A second aspect of the present invention which further enhances its ability to achieve high compression percentages, is its ability to be applied to data recursively. Specifically, the methods of the present invention are able to make multiple passes over a file, each time further compressing the file. Thus, a series of recursions are repeated until the desired compression level is achieved. ... Thus, one skilled in the art can see that by keeping the appropriate counters, the direct bit encode method of the present invention is effective for reducing an input string by one bit regardless of the bit pattern of the input string. What would one say about the examiner now? [0] https://www.google.com/patents/US5533051 https://www.google.com/patents/US5533051
- tsomctl 10y ago
  Especially one that is obvious. I remember drawing similar things using a TI-84 in high school math, probably when we learned about polar coordinates.
  - nameless912 10y ago
    And let's not forget there's an implementation on Wikipedia.
  - SlashmanX 10y ago
    Well in this case the developer of NMS specifically said he was struggling with planet generation until he discovered that exact formula, so you can understand why there is _some_ (not a lot mind) reasoning for the company who owns this patent (who are making a game involving it iirc) are making this claim. Judging by their statement though it seems they want more of a 'partnership' type thing (knowledge sharing, ride on NMS coattails for a bit etc)
- Iv 10y ago
  Not in EU. Such a patent is invalid, but if they managed to get it approved by the EU patent bureau (which is known for accepting such baseless claims) then they have a patent that needs a court action to be invalidated. In the meantime, it is assumed to be valid.
  - pkaye 10y ago
    But it seems to be an EU patent based on this link (on the Wikipedia page) https://worldwide.espacenet.com/publicationDetails/biblio?CC=EP&NR=1177529&KC=&FT=E&locale=en_EP https://worldwide.espacenet.com/publicationDetails/biblio?CC...
    - Iv 10y ago
      Yes, this patent is supposed valid but any court would invalidate it. The EU patent bureau has produced a lot of these "method and apparatus". Turns out that one can't patent algorithms, but one can patent the machine composed of a computer running such an algorithm. It is a known loophole and I don't think any of these patents hold up in court. Actually, I am not even sure that they can enforce anything against a software company with this patent. Someone who distributes a software does not produce an "apparatus" so I am not sure if they can even launch a procedure based on that patent.
taserian 10y ago
Play with the superformula in d3.js: http://bl.ocks.org/mbostock/1021103 http://bl.ocks.org/mbostock/1021103
- taserian 10y ago
  Also, tweening between superformula shapes in d3.js: http://bl.ocks.org/mbostock/1020902 http://bl.ocks.org/mbostock/1020902
bluetidepro 10y ago
I am guessing this is being posted in relation to the new PS4 game coming out, "No Man's Sky". See controversial article about it here (published yesterday): http://www.pcgamer.com/company-claims-no-mans-sky-uses-its-patented-equation-without-permission/ http://www.pcgamer.com/company-claims-no-mans-sky-uses-its-p...
- deleted 10y ago
  [deleted]
- eridius 10y ago
  According to the Wikipedia page (which links to https://register.epo.org/application?number=EP05100648&lng=en&tab=main https://register.epo.org/application?number=EP05100648&lng=e...), the patent on the superformula was withdrawn in 2006 because the renewal fees stopped being paid. Seems pretty strange that Genicap could assert ownership of the formula when they let the patent expire.
  - the_mitsuhiko 10y ago
    It was transferred in early 2015 and the new owner started paying properly: https://register.epo.org/application?number=EP05100648&lng=en&tab=legal https://register.epo.org/application?number=EP05100648&lng=e...
    - Sir_Cmpwn 10y ago
      No Man's Sky was first publicly demoed in 2013. Seems suspect, this might be an opportunistic renewal hoping to collect rent.
      - jandrese 10y ago
        It is obviously rent seeking.
    - MasterYoda 10y ago
      How is that possible? In that case, it feels like a loophole there people could just skip the annual fees until an opertunity to sue someone occurs and then pay for all the years at ones. Feels also strange a patent that have been withdrawn could be sold.
mcphage 10y ago
If the superformula itself is patented, what protection does that give to a generalization of it, like replacing m with y & z as presented in the article?
- AstralStorm 10y ago
  None really, it is just prior art. The modification is substantial enough. Caveat: not a patent lawyer.
calebm 10y ago
Seems kind of like taking the fourier transform to the polar space.
deleted 10y ago
[deleted]
kordless 10y ago
The variations are interesting in relation to the approach and recession of the point on the line from the origin.
- carl_corder 10y ago
  This is my take away: PolarPlot[(Abs[Cos[2(t - Pi/2)/4]] + Abs[Sin[44(t - Pi/2)/4]])^(-1/(-0.2)), {t, 0, 2*Pi}, PlotRange -> {{-20, 20}, {-5, 32}}, PlotStyle -> Darker[Green, 0.2], PlotTheme -> "Marketing"]
darkstalker 10y ago
I wonder if there is a distance function to it, so you can render it in 3D using sphere tracing.
- Impossible 10y ago
  This Shadertoy (https://www.shadertoy.com/view/4llGWM https://www.shadertoy.com/view/4llGWM) uses sphere tracing it but doesn't use a real distance function, the author asks the same question.
Animats 10y ago
Aw, they're concave. Many years ago, when Symbolics LISP machines roamed the earth, Alex Pentland wrote the first animation physics engine. Everything was a deformed superellipse, or rather the solid of rotation of one. You could apply a bend and a taper to a superellipse-generated solid. These were called "superquadrics".[1] I spent much time trying to come up with an analytical formula for the closest distance between two such objects, for collision detection. This was a dead end; polyhedra and meshes, although they required much more bookkeeping, were more useful in programs. Interest in superquadrics died out.
- restalis 10y ago
  Did you intended to leave a reference for note [1]?
  - Animats 10y ago
    Sorry. [1] [1] http://www.cs.toronto.edu/~dt/papers/pami91/pami91.pdf http://www.cs.toronto.edu/~dt/papers/pami91/pami91.pdf
- LolWolf 10y ago
  Interesting. I'm still wondering about why we should use analytical solutions for shapes rather than meshes? What all is the general advantage? It seems like now we have enough computational power to not have to worry about such analytical solutions. Also, what is the advantage of using the 'Superformula' to create most shapes as opposed to using some simple parametrization of meshes and enforcing symmetry or something of the like?
mgalka 10y ago
For any D3 users, there is a superformula plugin. Very handy. http://bl.ocks.org/mbostock/1020902 http://bl.ocks.org/mbostock/1020902
iamcreasy 10y ago
This reminds me of the polygon tool of Inkscape . Video : https://www.youtube.com/watch?v=pBLy9KDPMHk https://www.youtube.com/watch?v=pBLy9KDPMHk
known 10y ago
Bang !
BoudewijnE 10y ago
> You can, however, patent the practical application of a mathematical formula > Genicap's patent calls out the formula's potential use in "graphics programs (e.g., 2D, 3D, etc.); CAD software; finite element analysis programs; wave generation programs; or other software," it doesn't specifically mention game design (procedurally generated or otherwise). http://arstechnica.com/gaming/2016/07/no-mans-sky-faces-potential-patent-fight-over-use-of-superformula/ http://arstechnica.com/gaming/2016/07/no-mans-sky-faces-pote...
sethx 10y ago
For even more gielis visualization pleasure, check this out: https://www.thregr.org/~wavexx/software/gte/ https://www.thregr.org/~wavexx/software/gte/
dotraul 10y ago
very cool
kgdinesh 10y ago
Can we formulate Mobius Strip using this?
LolWolf 10y ago
> While the above equation, dubbed the "superformula" by Gielis (2003), is clearly capable of describing a number of diverse biological shapes having a variety of symmetries, it seems unlikely that this formula has any particularly fundamental biological significance (Peterson 2002, Whitfield 2003) beyond as a possibly convenient parametrization. [1] I'm not a huge fan of these random parametrizations; overall, it seems like they have no physical significance (yay! it can describe a bunch of things! I can do that anyways by picking a linear space with enough dimensions or a nice non-linear kernel and projecting into the first few principal components, and best of all, it's going to be fit directly to my problem). I'd like to be enlightened as to why this is such a big deal and why anyone would do this instead of parametrization of meshes for procedural generation? It seems a few comments here are referencing NMS, hence the question. [1] http://mathworld.wolfram.com/Superellipse.html http://mathworld.wolfram.com/Superellipse.html
ii 10y ago
If I made a formula that is more generalized, patents still apply? Here it is in complex numbers: p = (r1*cos(ph1 + th) + 1.0*I*r2*sin(ph2 + th))* (Abs(cos(m*th/4)/a)**n2 + Abs(sin(m*th/4)/b)**n3)**(-1/n1) This can produce a number of interesting shapes that original Gielis transforms can't.

176 points by GuiA 10y ago

How hard is it to invert? e.g. given a set of points along a particular curve, how difficult is it to find the values of the 6 parameters that generated it?

vinchuco 10y ago
If you know a,b,m,n1,n2,n3, and use sufficient points, you may be able to get an interpolated approximation. In general, one can fit many such curves through a finite set of points. http://math.stackexchange.com/questions/65970/can-a-function-be-found-to-fit-any-set-of-points http://math.stackexchange.com/questions/65970/can-a-function... A question originally asked by Leibniz to determine the measure of usefulness of a law. https://plus.maths.org/content/omega-and-why-maths-has-no-toes https://plus.maths.org/content/omega-and-why-maths-has-no-to.... If you don't have the 6 parameters, good luck. A unique inverse is defined only for injective functions.
mturmon 10y ago
Someone experimented with this. See the links at the bottom of the Wikipedia article. This seems misguided to me -- why use a curve family when fitting is so hard -- but it has been done.

pavel_lishin 10y ago

> Currently, the superformula is patented by Gielis, [2] but the patent was withdrawn in 2006 because of the patent fees not being paid.[3] I did not know you could patent a mathematical formula.

cschmidt 10y ago
no doubt it was something like "a system and method for generating natural shapes"
- messe 10y ago
  "Method and apparatus for synthesizing patterns" https://www.google.com/patents/EP1177529B1?cl=en https://www.google.com/patents/EP1177529B1?cl=en
gnoway 10y ago
You can't, only its application. Genicap's patent does cover application in software though.
- flashman 10y ago
  Even patenting a formula's application is becoming more restricted. In Australia and the US, the two relevant tests seem to be whether the formula does something a human can't, and whether the formula is used to 'improve' the operations of a computer or machine (e.g. if it made your hard drive faster or controlled a robotic arm). I had to look into this regarding an algorithm we're building and whether it's patentable. If your formula is a mere scheme or method implemented in a computer, it's likely to be rejected. The following links add detail: http://www.fisheradamskelly.com.au/2015/12/full-federal-court-of-australia-adds-some-clarity-to-when-business-methods-are-patentable/ http://www.fisheradamskelly.com.au/2015/12/full-federal-cour... https://en.wikipedia.org/wiki/Alice_Corp._v._CLS_Bank_International https://en.wikipedia.org/wiki/Alice_Corp._v._CLS_Bank_Intern... http://www.ipwatchdog.com/2016/05/13/federal-circuit-says-software-patent-claims-not-abstract-are-patent-eligible/id=69147/ http://www.ipwatchdog.com/2016/05/13/federal-circuit-says-so...
kirrent 10y ago
In most jurisdictions you can't really patent the use of an abstract mathematical formula on a computer with no gain, but that's something the law has only caught up to in the last decade. The patent is most likely invalid in the EU and US but was approved way back when those standards for invalidity didn't exist in their current forms. Of course, a court wouldn't need to be bound by the original decision of the examiner and would determine validity based on current case law and practice.
kevin_thibedeau 10y ago
You can't. On one, Gielis even put the equation in claim 1 but somehow they got the village idiot for an examiner. http://www.google.com/patents/US7620527 http://www.google.com/patents/US7620527
- 0xmohit 10y ago
  Patent 5533051 [0] is a classic. Some quotes: A second aspect of the present invention which further enhances its ability to achieve high compression percentages, is its ability to be applied to data recursively. Specifically, the methods of the present invention are able to make multiple passes over a file, each time further compressing the file. Thus, a series of recursions are repeated until the desired compression level is achieved. ... Thus, one skilled in the art can see that by keeping the appropriate counters, the direct bit encode method of the present invention is effective for reducing an input string by one bit regardless of the bit pattern of the input string. What would one say about the examiner now? [0] https://www.google.com/patents/US5533051 https://www.google.com/patents/US5533051
tsomctl 10y ago
Especially one that is obvious. I remember drawing similar things using a TI-84 in high school math, probably when we learned about polar coordinates.
- nameless912 10y ago
  And let's not forget there's an implementation on Wikipedia.
- SlashmanX 10y ago
  Well in this case the developer of NMS specifically said he was struggling with planet generation until he discovered that exact formula, so you can understand why there is _some_ (not a lot mind) reasoning for the company who owns this patent (who are making a game involving it iirc) are making this claim. Judging by their statement though it seems they want more of a 'partnership' type thing (knowledge sharing, ride on NMS coattails for a bit etc)
Iv 10y ago
Not in EU. Such a patent is invalid, but if they managed to get it approved by the EU patent bureau (which is known for accepting such baseless claims) then they have a patent that needs a court action to be invalidated. In the meantime, it is assumed to be valid.
- pkaye 10y ago
  But it seems to be an EU patent based on this link (on the Wikipedia page) https://worldwide.espacenet.com/publicationDetails/biblio?CC=EP&NR=1177529&KC=&FT=E&locale=en_EP https://worldwide.espacenet.com/publicationDetails/biblio?CC...
  - Iv 10y ago
    Yes, this patent is supposed valid but any court would invalidate it. The EU patent bureau has produced a lot of these "method and apparatus". Turns out that one can't patent algorithms, but one can patent the machine composed of a computer running such an algorithm. It is a known loophole and I don't think any of these patents hold up in court. Actually, I am not even sure that they can enforce anything against a software company with this patent. Someone who distributes a software does not produce an "apparatus" so I am not sure if they can even launch a procedure based on that patent.

taserian 10y ago

Play with the superformula in d3.js: http://bl.ocks.org/mbostock/1021103 http://bl.ocks.org/mbostock/1021103

taserian 10y ago
Also, tweening between superformula shapes in d3.js: http://bl.ocks.org/mbostock/1020902 http://bl.ocks.org/mbostock/1020902

bluetidepro 10y ago

I am guessing this is being posted in relation to the new PS4 game coming out, "No Man's Sky". See controversial article about it here (published yesterday): http://www.pcgamer.com/company-claims-no-mans-sky-uses-its-patented-equation-without-permission/ http://www.pcgamer.com/company-claims-no-mans-sky-uses-its-p...

deleted 10y ago
[deleted]
eridius 10y ago
According to the Wikipedia page (which links to https://register.epo.org/application?number=EP05100648&lng=en&tab=main https://register.epo.org/application?number=EP05100648&lng=e...), the patent on the superformula was withdrawn in 2006 because the renewal fees stopped being paid. Seems pretty strange that Genicap could assert ownership of the formula when they let the patent expire.
- the_mitsuhiko 10y ago
  It was transferred in early 2015 and the new owner started paying properly: https://register.epo.org/application?number=EP05100648&lng=en&tab=legal https://register.epo.org/application?number=EP05100648&lng=e...
  - Sir_Cmpwn 10y ago
    No Man's Sky was first publicly demoed in 2013. Seems suspect, this might be an opportunistic renewal hoping to collect rent.
    - jandrese 10y ago
      It is obviously rent seeking.
  - MasterYoda 10y ago
    How is that possible? In that case, it feels like a loophole there people could just skip the annual fees until an opertunity to sue someone occurs and then pay for all the years at ones. Feels also strange a patent that have been withdrawn could be sold.

mcphage 10y ago

If the superformula itself is patented, what protection does that give to a generalization of it, like replacing m with y & z as presented in the article?

AstralStorm 10y ago
None really, it is just prior art. The modification is substantial enough. Caveat: not a patent lawyer.

calebm 10y ago

Seems kind of like taking the fourier transform to the polar space.

deleted 10y ago

[deleted]

kordless 10y ago

The variations are interesting in relation to the approach and recession of the point on the line from the origin.

carl_corder 10y ago
This is my take away: PolarPlot[(Abs[Cos[2(t - Pi/2)/4]] + Abs[Sin[44(t - Pi/2)/4]])^(-1/(-0.2)), {t, 0, 2*Pi}, PlotRange -> {{-20, 20}, {-5, 32}}, PlotStyle -> Darker[Green, 0.2], PlotTheme -> "Marketing"]

darkstalker 10y ago

I wonder if there is a distance function to it, so you can render it in 3D using sphere tracing.

Impossible 10y ago
This Shadertoy (https://www.shadertoy.com/view/4llGWM https://www.shadertoy.com/view/4llGWM) uses sphere tracing it but doesn't use a real distance function, the author asks the same question.

Animats 10y ago

Aw, they're concave. Many years ago, when Symbolics LISP machines roamed the earth, Alex Pentland wrote the first animation physics engine. Everything was a deformed superellipse, or rather the solid of rotation of one. You could apply a bend and a taper to a superellipse-generated solid. These were called "superquadrics".[1] I spent much time trying to come up with an analytical formula for the closest distance between two such objects, for collision detection. This was a dead end; polyhedra and meshes, although they required much more bookkeeping, were more useful in programs. Interest in superquadrics died out.

restalis 10y ago
Did you intended to leave a reference for note [1]?
- Animats 10y ago
  Sorry. [1] [1] http://www.cs.toronto.edu/~dt/papers/pami91/pami91.pdf http://www.cs.toronto.edu/~dt/papers/pami91/pami91.pdf
LolWolf 10y ago
Interesting. I'm still wondering about why we should use analytical solutions for shapes rather than meshes? What all is the general advantage? It seems like now we have enough computational power to not have to worry about such analytical solutions. Also, what is the advantage of using the 'Superformula' to create most shapes as opposed to using some simple parametrization of meshes and enforcing symmetry or something of the like?

mgalka 10y ago

For any D3 users, there is a superformula plugin. Very handy. http://bl.ocks.org/mbostock/1020902 http://bl.ocks.org/mbostock/1020902

iamcreasy 10y ago

This reminds me of the polygon tool of Inkscape . Video : https://www.youtube.com/watch?v=pBLy9KDPMHk https://www.youtube.com/watch?v=pBLy9KDPMHk

known 10y ago

Bang !

BoudewijnE 10y ago

> You can, however, patent the practical application of a mathematical formula > Genicap's patent calls out the formula's potential use in "graphics programs (e.g., 2D, 3D, etc.); CAD software; finite element analysis programs; wave generation programs; or other software," it doesn't specifically mention game design (procedurally generated or otherwise). http://arstechnica.com/gaming/2016/07/no-mans-sky-faces-potential-patent-fight-over-use-of-superformula/ http://arstechnica.com/gaming/2016/07/no-mans-sky-faces-pote...

sethx 10y ago

For even more gielis visualization pleasure, check this out: https://www.thregr.org/~wavexx/software/gte/ https://www.thregr.org/~wavexx/software/gte/

dotraul 10y ago

very cool

kgdinesh 10y ago

Can we formulate Mobius Strip using this?

LolWolf 10y ago

> While the above equation, dubbed the "superformula" by Gielis (2003), is clearly capable of describing a number of diverse biological shapes having a variety of symmetries, it seems unlikely that this formula has any particularly fundamental biological significance (Peterson 2002, Whitfield 2003) beyond as a possibly convenient parametrization. [1] I'm not a huge fan of these random parametrizations; overall, it seems like they have no physical significance (yay! it can describe a bunch of things! I can do that anyways by picking a linear space with enough dimensions or a nice non-linear kernel and projecting into the first few principal components, and best of all, it's going to be fit directly to my problem). I'd like to be enlightened as to why this is such a big deal and why anyone would do this instead of parametrization of meshes for procedural generation? It seems a few comments here are referencing NMS, hence the question. [1] http://mathworld.wolfram.com/Superellipse.html http://mathworld.wolfram.com/Superellipse.html

ii 10y ago

If I made a formula that is more generalized, patents still apply? Here it is in complex numbers: p = (r1*cos(ph1 + th) + 1.0*I*r2*sin(ph2 + th))* (Abs(cos(m*th/4)/a)**n2 + Abs(sin(m*th/4)/b)**n3)**(-1/n1) This can produce a number of interesting shapes that original Gielis transforms can't.