2
$\begingroup$

In the attached image are three functions. The first is a displacement function which takes angle $t$, and returns a radius. The third one is a semicircle and the second one is a semicircle with the displacement function $d()$ applied.

Note that the second function includes $y$ in the right hand side (inside $\text{atan2}$). I need to factor this equation so that it is entirely dependent on $x$, and there is no $y$ variable on the right hand side of the equation.

Reproduced here, the equation is:

$y=\sqrt{ d(\text{atan2}( y, x ) )^2 - x^2 }$

I need to get this ^ y moved to the left.

graph

edit: bigger picture, I'm trying to do raycasting of a sphere with a displacement map using an orthographic camera. This is why I only care about the greatest y, because lower y are not visible to the camera due to occlusion. My thought was that if I could scan across with a single x, on a 2 dimension version of the problem I'd be closer to solving the 3 dimensional version.

edit: let me ask this a different way. Given a line, how can I find the location of a the points which this line intersects with the equation?

edit again: it seems the answer is binary search. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch21.html

  • 2
    Welcome to Math.SE! No apologies necessary; this is a perfectly well-formed question. But right off the bat, I can tell you that if you want $y$ to be purely a function of $x$, this is impossible, because for some values of $x$ (like around $x = 0.8$) there are multiple values of $y$ on the curve.2012-02-13
  • 0
    thank you for your reply. What I would like is, where there are multiple y, I want the greatest, or maximum y. Is that possible?2012-02-13

1 Answers 1

4

As Rahul has already commented, you can't solve this for $y$ because $y$ is not a single-valued function of $x$. I also doubt that you can express the greatest $y$ for a given $x$ in closed form.

In polar coordinates, your equation is just $r(\phi)=d(\phi)$, and this allows you to write both $x$ and $y$ as functions of the single parameter $\phi$:

$$ x=r\cos\phi=d(\phi)\cos\phi\;,\\ y=r\sin\phi=d(\phi)\sin\phi\;. $$

Now you could express $y$ as a function of $x$ if you could solve the first of these equations for $x$. With $d(\phi)=1+\sin(20\phi)/5$, this is $x=(1+\sin(20\phi)/5)\cos\phi$. You could express $\sin(20\phi)$ in terms of $\sin\phi$ and $\cos\phi$, but that would lead to a high-order polynomial in $\sin\phi$ and $\cos\phi$ whose roots are unlikely to have a closed form.

Often people post questions about parts of their problems, which turn out to be unsolvable because they've gone down a dead end with their bigger problem. If you tell us why you want to do this, we might be able to help you more, e.g. by suggesting how to do it in polar coordinates instead.

[Edit in response to the edit in the question:]

You could consider scanning through values of $\phi$ instead. Since

$$\dot x=\dot d\cos\phi-d\sin\phi=4\cos(20\phi)\cos\phi-(1+\sin(20\phi)/5)\sin\phi$$

(where the dot signifies differentiation with respect to $\phi$), you have $\Delta x\lt\sqrt{4^2+1.2^2}\Delta\phi\approx4\Delta\phi$, so with $\phi\in[0,\pi]$ instead of $x\in[-1.2,1.2]$ you'd only need about five times as many steps to get the same density of $x$ values everywhere.

  • 0
    "...whose roots are unlikely to have a closed form." - they do have a closed form; it just happens that they're not practical. :)2012-02-13
  • 0
    @J.M.: Do they? What is it?2012-02-13
  • 0
    Hmm, I thought it'd have to use theta functions, but after expressing $\sin\,20\phi$ in the form $p(\cos\,\phi)\sin\,\phi$, with $p(u)$ a 19th degree polynomial, it turns out that the roots of $p(u)$ are expressible as nice radicals (nested square roots). You want to see them?2012-02-13
  • 0
    I have edited the original question to express my wider goals. I was rather hoping to find a solution that didn't involve breaking into d()2012-02-13
  • 0
    @J.M.: Sorry, I see now that that was ambiguous -- I meant the entire polynomial whose zeroes would be the values of $\phi$ corresponding to $x$, not just the polynomial for $\sin(20\phi)$. I'm not too surprised that the roots of $p$ are expressible as nested radicals, since the regular icosagon is constructible.2012-02-13
  • 0
    @Breton: Not breaking into $d$ is out of the question. $d$ could be any function of $y/x$, so if you could solve this while treating $d$ as a black box, you could solve all sorts of transcendental equations.2012-02-13
  • 0
    Hmmm scanning ϕ doesn't really do me much good since i'd still need the kind of function I'm originally asking for to render the result of that.2012-02-13
  • 0
    @Breton: If you take sufficiently small steps in $\phi$, you can linearly interpolate the results; for each step you could test whether it steps over one of the $x$ values for which you need $y$ values; if so, you can calculate that $y$ value by interpolation. Then you just have to keep an array of $y$ values and overwrite them if you encounter a higher $y$ value for the same $x$ value.2012-02-13
  • 0
    I cannot do this in a gpu.2012-02-13
  • 0
    @Breton, so what you're saying is, you want to ray trace an implicit surface on the GPU? [There are lots of papers on that!](http://www.google.com/search?q=gpu+ray+tracing+implicit+surfaces)2012-02-13
  • 0
    Oooh thank you @RahulNarain2012-02-13
  • 0
    @Breton: This is an excellent example of what I was saying. You took two steps trying to solve your original problem, then told us about the subsubproblem you'd arrived at, and even when I asked you for the original problem, you only went back one step and told us about the subproblem; then when you mentioned the actual problem (doing this on a GPU), a mere ten minutes later someone gave you apparently very useful information.2012-02-13
  • 0
    yes thank you @joriki , being new to this community, I wasn't sure that posting something that essentially sounds like a programming problem would be appropriate. I reached a dead end on stack overflow, and tried to work it out myself, ending up at a mathematical dead end, which is why I ended up here, stating only the specific mathematical subproblem. - By way of explanation. I do agree with your general premise that broader context greatly helps in problem solving.2012-02-13
  • 0
    I find it fascinating though that when I end up at a mathematical dead end, it's usually because I've ended up with a problem that needs binary search. I suppose an even BROADER context would be that I don't know how to recognise these problems on sight.2012-02-13
  • 0
    it's also occured to me that I *could* do a search of ϕ instead. I've already got the function I need to pinpoint the point on a surface of a sphere from the picture plane. I can get ϕ from that, and search surrounding coordinates in the displaced function until the displaced surface projects onto the pixel I'm testing.2012-02-14