6
$\begingroup$

I'm trying to draw quadratic bezier curve (as line). I approximate quadratic bezier curve as parabola ($y=x^2$), according to this document http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html

There, in section "25.5 Antialiasing" Loop/Blinn claims that signed distance from point (x,y) to the curve $f$(which is $y=x^2$) is:

enter image description here

or:

enter image description here

Is this correct? [I read, that it is impossible to have another "parallel" bezier curve]

I ask this because, if I want to detect distance more than 1-2 pixels, and have a high
triangle base/height ratio, than "distance" shrinks on the base direction.

For example, here is 50px distance from inner side of the curve filled green, all other red (all ok): enter image description here

And this one shrunken (pay attention, that distance on height axis still is correct):

enter image description here

Curve drawing in triangle with coordinates (0,0) (0.5,0) (1,1). Which is 1st quadrant.

$\endgroup$

2 Answers 2

1
$\begingroup$

The formula gives only an approximation. If $f(\mathbf x)$ is a continuously differentiable function and the point $\mathbf a$ is ,,close'' to the implicit curve/surface $f(\mathbf x)=0$ and the closest point of the curve is $\mathbf a_0$ then $$ f(\mathbf a) = f(\mathbf a)-f(\mathbf a_0) \approx (\nabla f)\cdot (\mathbf a-\mathbf a_0). $$ The vectors $\nabla f$ and $\mathbf a-\mathbf a_0$ must be approximately parallel, so $$ f(\mathbf a) \approx \pm ||\nabla f(\mathbf a)|| \cdot ||\mathbf a-\mathbf a_0|| = ||\nabla f(\mathbf a)|| \cdot sd. $$

If the point $\mathbf a$ is far from the curve then the formula is useless.


If you need the precise distance from a parabola then it leads to some cubic equation.

$\endgroup$
7
  • $\begingroup$ Why it is important, for $a$ to be close to curve? $\endgroup$
    – tower120
    Sep 11, 2014 at 14:05
  • $\begingroup$ "If you need the precise distance from a parabola then it leads to some cubic equation." - Like what? $\endgroup$
    – tower120
    Sep 11, 2014 at 14:07
  • $\begingroup$ The estimates $f(\mathbf a)-f(\mathbf a_0) \approx (\nabla f(\mathbf a))\cdot (\mathbf a-\mathbf a_0) \approx (\nabla f(\mathbf a_0))\cdot (\mathbf a-\mathbf a_0)$ are valid only if $||\mathbf a-\mathbf a_0||$ is small. $\endgroup$
    – G.Kós
    Sep 11, 2014 at 15:03
  • $\begingroup$ Is it possible to get some formula to calculate minimal distance from point to $y=x^2$ (where x from 0 to 1)? $\endgroup$
    – tower120
    Sep 11, 2014 at 15:22
  • $\begingroup$ You have to minimize $(x-a)^2+(x^2-b)^2$ which is a quartic poynomial. $\endgroup$
    – G.Kós
    Sep 12, 2014 at 10:41
0
$\begingroup$

In my opinion, sd is not a distance at all, signed or not.

By analytic geometry, the distance of a point $P=(x_0,y_0)$ to the line given by the equation $f(x,y)=ax+by+c=0$ is $d=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}=\frac{|f(x_0,y_0)|}{||\vec\nabla f(x_0,y_0)||}$. I think, that is why they defined "signed distance" as $sd=\frac{f}{||\vec\nabla f||}$. But, it really does not make sense for curves of higher degrees. For example, the distance of $P=(x_0,y_0)$ to the circle given by the equation $f(x,y)=(x-a)^2+(y-b)^2-r^2=0$ is $d=|\sqrt{(x_0-a)^2+(y_0-b)^2}-r|$ which is $d=\frac{|f(x_0,y_0)|}{\sqrt{(x_0-a)^2+(y_0-b)^2}+r}$. But, the denominator of $d$ is not the magnitute of the gradient, that is, it is not $||\vec\nabla f(x_0,y_0)||=2\sqrt{(x_0-a)^2+(y_0-b)^2}$. In fact, the gradient is zero at the center $(a,b)$ and $sd(a,b)$ is not defined.

To find the distance of $P=(x_0,y_0)$ to the parabola $f(x,y)=y-x^2=0$ you have to solve this equation: $$2x^3+(1-2y_0)x-x_0=0.$$ It is not so difficult to derive it. See this link. Then the distance is $$d=\sqrt{1+\frac{1}{4x^2}}|x-x_0|=||\vec\nabla f(x,x^2)|||\frac{x-x_0}{2x}|$$ where $x\neq 0$ is the solution of the cubic equation above. Again, $sd$ is only a bad signed approximation here as I can see $d\approx\frac{|y_0-x_0^2|}{\sqrt{1+4x^2}}|\approx|sd|$, from a "rough figure" when $P$ is close to the graph of $y=x^2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .