Giter VIP home page Giter VIP logo

Comments (8)

NaridaL avatar NaridaL commented on September 12, 2024

Hey, I implemented this function for 3d non-intersecting cubic curves. Posting it here
in case you find it useful: (NLA.equals and NLA.isZero are fuzzy comparison functions, solveCubicRoot2 is a modified version of your utils.roots which works when a == 0 and b == 0)

        /**
         * Returns curve parameter t for point p on curve.
         * @param p
         * @returns {*}
         */
        pointLambda: function (p) {
            var {p0, p1, p2, p3} = this
            // calculate cubic equation coefficients
            // a t³ + b t² + c t + d = 0
            // multiplying out the cubic Bézier curve equation gives:
            // a = -p0 + 3 p1 - 3 p2 + p3
            // b = 3 p0 - 6 p1 + 3 p2
            // c = -3 p0 + 3 p1
            // d = p0 - p
            var a = p1.minus(p2).times(3).minus(p0).plus(p3)
            var b = p0.plus(p2).times(3).minus(p1.times(6))
            var c = p1.minus(p0).times(3)
            var d = p0.minus(p)
            var results = null, newResults

            // assume passed point is on curve and that curve does not self-intersect,
            // i.e. there is exactly one correct result for t
            // try to find a single result in the x-dimension, if multiple are found,
            // filter them by checking the other dimesions
            if (NLA.isZero(a.x) && NLA.isZero(b.x) && NLA.isZero(c.x)) {
                // ax == bx == cx == 0 => x(t) = dx
                // x value is constant
                // if x == 0 for all t, this does not limit the result, otherwise, there is no result, i.e
                // the passed point is not on the curve
                assert(NLA.isZero(d.x))
            } else {
                newResults = solveCubicReal2(a.x, b.x, c.x, d.x)
                console.log('xres', a.x, b.x, c.x, d.x, newResults)
                if (results) {
                    results = results.filter(t => newResults.some(t2 => NLA.equals(t, t2)))
                } else {
                    results = newResults
                }
                if (results.length == 1) return results[0]
            }

            if (NLA.isZero(a.y) && NLA.isZero(b.y) && NLA.isZero(c.y)) {
                assert(NLA.isZero(d.y))
            } else {
                newResults = solveCubicReal2(a.y, b.y, c.y, d.y)
                console.log('yres', a.y, b.y, c.y, d.y, newResults,p.ss)
                if (results) {
                    results = results.filter(t => newResults.some(t2 => NLA.equals(t, t2)))
                } else {
                    results = newResults
                }
                if (results.length == 1) return results[0]
            }

            if (NLA.isZero(a.z) && NLA.isZero(b.z) && NLA.isZero(c.z)) {
                assert(NLA.isZero(d.z))
            } else {
                newResults = solveCubicReal2(a.z, b.z, c.z, d.z)
                if (results) {
                    results = results.filter(t => newResults.some(t2 => NLA.equals(t, t2)))
                } else {
                    results = newResults
                }
                if (results.length == 1) return results[0]
            }
            assert(false, 'found no t; point '+p.ss+' is not on curve')
        }

from bezierjs.

Pomax avatar Pomax commented on September 12, 2024

nice - does Cardano's algorithm break down on a=0 and b=0 though?

from bezierjs.

NaridaL avatar NaridaL commented on September 12, 2024

Well assuming the form a t³ + b t² + c t + d = 0, the first step is to normalize it to t³ + b/a t² + c/a t + d/a = 0 which obviously doesn't work for a == 0, so I pass it to a quadratic formula implementation, which also assumes a normalized form x² + c/b x + d/b = 0.

At that points it's just a line, solving is easy :-D

from bezierjs.

Pomax avatar Pomax commented on September 12, 2024

ah!

from bezierjs.

danmarshall avatar danmarshall commented on September 12, 2024

+1 on this feature.
@NaridaL , can you also provide your implementation of solveCubicRoot2 ?

from bezierjs.

NaridaL avatar NaridaL commented on September 12, 2024

@danmarshall As I said, it basically the same as @Pomax 's version, with added parameter checking. For what it's worth:

function solveCubicReal2(a, b, c, d) {
    if (NLA.isZero(a)) {
        if (NLA.isZero(b)) {
            return [-d/c]
        } else {
            return pqEquation(c / b, d / b)
        }
    }
    var div = a
    a = b/div
    b = c/div
    c = d/div
    var p = (3*b - a*a)/3,
        p3 = p/3,
        q = (2*a*a*a - 9*a*b + 27*c)/27,
        q2 = q/2,
        discriminant = q2*q2 + p3*p3*p3,
    u1,v1,x1,x2,x3
    // 18abcd - 4b³d + b²c² - 4ac³ - 27a²d²
    if (discriminant < -NLA.PRECISION) {
        var mp3 = -p/3,
            mp33 = mp3*mp3*mp3,
            r = Math.sqrt( mp33 ),
            t = -q/(2*r),
            cosphi = t<-1 ? -1 : t>1 ? 1 : t,
            phi = Math.acos(cosphi),
            crtr = Math.cbrt(r),
            t1 = 2*crtr
        x1 = t1 * Math.cos(phi/3) - a/3
        x2 = t1 * Math.cos((phi+2*Math.PI)/3) - a/3
        x3 = t1 * Math.cos((phi+4*Math.PI)/3) - a/3
        return [x1, x2, x3]
    } else if(discriminant <= NLA.PRECISION) {
        u1 = q2 < 0 ? Math.cbrt(-q2) : -Math.cbrt(q2)
        x1 = 2*u1-a/3
        x2 = -u1 - a/3
        return [x1,x2]
    } else {
        var sd = Math.sqrt(discriminant)
        u1 = Math.cbrt(-q2+sd)
        v1 = Math.cbrt(q2+sd)
        return [u1-v1-a/3]
    }
}

/*
 solves x² + px + q = 0
 */
function pqEquation(p, q) {
    // 4 times the discriminant:
    var discriminant4 = p * p / 4 - q
    if (discriminant4 < -NLA.PRECISION) {
        return []
    } else if (discriminant4 <= NLA.PRECISION) {
        return [-p/2]
    } else {
        var root = Math.sqrt(discriminant4)
        return [-p/2 - root, -p/2 + root]
    }
}

from bezierjs.

dashng avatar dashng commented on September 12, 2024

It is not clear enough. how should I involved these code to my project.

Bezier should be extended to support this feature?

from bezierjs.

Pomax avatar Pomax commented on September 12, 2024

you shouldn't, this code should get worked into bezierjs itself.

from bezierjs.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.