[PATCH 4/4] d2d1: Implement cubic bezier-line intersection.

[Giovanni Mascellani]

Hi,

Il 31/03/20 22:11, Connor McAdams ha scritto:
> +    p = (3.0f * b - a * a) / 3.0f;
> +    p_3 = p / 3.0f;
> +    q = (2.0f * a * a * a - 9.0f * a * b + 27.0f * c) / 27.0f;
> +    q2 = q / 2.0f;
> +    disc = q2 * q2 + p_3 * p_3 * p_3;

I don't think it is advisable to use Cardano's formula to solve a cubic,
because it can go numerically bad in a lot of ways. After a quick chat
with a friend into numerical computing, it seems that it is probably
better to do a few iterations of a numerical method, like the Aberth
method (see the Wikipedia page), which should converge rather quickly
and more or less always if the initial values are chosen not to be
symmetrical around the real axis. However, it requires to use complex
numbers.

A good criterion for halting the iterative search is when abs(p/p') is
smaller than epsilon, because that condition implies that a root is in a
neighbourhood of size approximately epsilon.

HTH, Giovanni.
-- 
Giovanni Mascellani <g.mascellani at gmail.com>
Postdoc researcher - Université Libre de Bruxelles

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: OpenPGP digital signature
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20200401/4ed2448f/attachment.sig>