Puncte echidistant între curbe Bezier

Currently, I'm attempting to make multiple beziers have equidistant points. I'm currently using cubic interpolation to find the points, but because the way beziers work some areas are more dense than others and proving gross for texture mapping because of the variable distance. Is there a way to find points on a bezier by distance rather than by percentage? Furthermore, is it possible to extend this to multiple connected curves?

0
fr hi bn
Consultați, de asemenea, math.stackexchange.com/a/61796/589 .
adăugat autor lhf, sursa

3 răspunsuri

distanta dintre P_0 si P_3 (in forma cubica), da, dar cred ca stiai asta, e drept.

Distanta pe o curba este doar lungimea arcului:

fig 1 http://www.codecogs.com/eq.latex?%5Cint_%7Bt_0%7D%5E%7Bt_1%7D%20%7B%20|P'(t)|%20dt

Unde:

fig 2 http://www.codecogs.com/eq.latex?P%27(t)%20=%20[%7Bx%27,y%27,z%27%7D]%20=%20[%7B%5Cfrac%7Bdx(t)%7D%7Bdt%7D,%5Cfrac%7Bdy(t)%7D%7Bdt%7D,%5Cfrac%7Bdz(t)%7D%7Bdt%7D%7D]

(a se vedea restul)

Probabil, ați avea t_0 = 0, t_1 = 1.0 și dz (t) = 0 (planul 2d).

0
adăugat
Acesta este modul în care găsiți lungimea arcului dat de parametru, dar găsirea punctelor echidistant necesită inversarea acestei funcții. Noțiuni de bază de la unul la altul nu este banal. @Christian Romo: cum ai făcut-o? Adică, puteți folosi doar binar de căutare, dar asta ar fi oribil lent (pentru ceea ce am încercat să fac, oricum).
adăugat autor CromTheDestroyer, sursa

Aceasta se numește parametrizare "lungimea arcului". Am scris o lucrare despre asta acum câțiva ani:

http://www.saccade.com/writing/graphics/RE-PARAM.PDF

Ideea este de a calcula în prealabil o curbă de "parametrizare" și de a evalua curba prin aceasta.

0
adăugat
Utilizarea NURB nu va ajuta, problema fundamentală este aceeași. Sfârșitul lucrării prezintă o metodă de compunere a curbei de re-parametrizare cu originalul. Aceasta produce o nouă curbă cu parametrizare cu lungimea arcului, dar ordinea în cazul în care curba este mai mare, deci este mai lent de evaluat.
adăugat autor J. Peterson, sursa
Nu ați citit încă hârtia. Dar aș dori să întreb dacă există o modalitate mai bună de a defini curbele care nu ar trebui să fie "convertite" mai întâi. De exemplu. știți dacă aș folosi NURBS pentru a defini toate căile/curbele, ar susține parametrizarea mai rapidă a lungimii echidistante a arcului? Sau poate altfel? Editare: Cu mai repede vreau sa spun folosind CPU sau GPU.
adăugat autor Ciantic, sursa

Știu că aceasta este o întrebare veche, dar recent am intrat în această problemă și am creat o extensie UIBezierPath pentru a rezolva o coordonată X dată coordonatelor Y și viceversa. Scris rapid.

https://github.com/rkotzy/RKBezierMath

extension UIBezierPath {

func solveBezerAtY(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, y: CGFloat) -> [CGPoint] {

   //bezier control points
    let C0 = start.y - y
    let C1 = point1.y - y
    let C2 = point2.y - y
    let C3 = end.y - y

   //The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = C3 - 3.0*C2 + 3.0*C1 - C0
    let B = 3.0*C2 - 6.0*C1 + 3.0*C0
    let C = 3.0*C1 - 3.0*C0
    let D = C0

    let roots = solveCubic(A, b: B, c: C, d: D)

    var result = [CGPoint]()

    for root in roots {
        if (root >= 0 && root <= 1) {
            result.append(bezierOutputAtT(start, point1: point1, point2: point2, end: end, t: root))
        }
    }

    return result
}

func solveBezerAtX(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, x: CGFloat) -> [CGPoint] {

   //bezier control points
    let C0 = start.x - x
    let C1 = point1.x - x
    let C2 = point2.x - x
    let C3 = end.x - x

   //The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = C3 - 3.0*C2 + 3.0*C1 - C0
    let B = 3.0*C2 - 6.0*C1 + 3.0*C0
    let C = 3.0*C1 - 3.0*C0
    let D = C0

    let roots = solveCubic(A, b: B, c: C, d: D)

    var result = [CGPoint]()

    for root in roots {
        if (root >= 0 && root <= 1) {
            result.append(bezierOutputAtT(start, point1: point1, point2: point2, end: end, t: root))
        }
    }

    return result

}

func solveCubic(a: CGFloat?, var b: CGFloat, var c: CGFloat, var d: CGFloat) -> [CGFloat] {

    if (a == nil) {
        return solveQuadratic(b, b: c, c: d)
    }

    b /= a!
    c /= a!
    d /= a!

    let p = (3 * c - b * b)/3
    let q = (2 * b * b * b - 9 * b * c + 27 * d)/27

    if (p == 0) {
        return [pow(-q, 1/3)]

    } else if (q == 0) {
        return [sqrt(-p), -sqrt(-p)]

    } else {

        let discriminant = pow(q/2, 2) + pow(p/3, 3)

        if (discriminant == 0) {
            return [pow(q/2, 1/3) - b/3]

        } else if (discriminant > 0) {
            let x = crt(-(q/2) + sqrt(discriminant))
            let z = crt((q/2) + sqrt(discriminant))
            return [x - z - b/3]
        } else {

            let r = sqrt(pow(-(p/3), 3))
            let phi = acos(-(q/(2 * sqrt(pow(-(p/3), 3)))))

            let s = 2 * pow(r, 1/3)

            return [
                s * cos(phi/3) - b/3,
                s * cos((phi + CGFloat(2) * CGFloat(M_PI))/3) - b/3,
                s * cos((phi + CGFloat(4) * CGFloat(M_PI))/3) - b/3
            ]

        }

    }
}

func solveQuadratic(a: CGFloat, b: CGFloat, c: CGFloat) -> [CGFloat] {

    let discriminant = b * b - 4 * a * c;

    if (discriminant < 0) {
        return []

    } else {
        return [
            (-b + sqrt(discriminant))/(2 * a),
            (-b - sqrt(discriminant))/(2 * a)
        ]
    }

}

private func crt(v: CGFloat) -> CGFloat {
    if (v<0) {
        return -pow(-v, 1/3)
    }
    return pow(v, 1/3)
}

private func bezierOutputAtT(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, t: CGFloat) -> CGPoint {

   //bezier control points
    let C0 = start
    let C1 = point1
    let C2 = point2
    let C3 = end

   //The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = CGPointMake(C3.x - 3.0*C2.x + 3.0*C1.x - C0.x, C3.y - 3.0*C2.y + 3.0*C1.y - C0.y)
    let B = CGPointMake(3.0*C2.x - 6.0*C1.x + 3.0*C0.x, 3.0*C2.y - 6.0*C1.y + 3.0*C0.y)
    let C = CGPointMake(3.0*C1.x - 3.0*C0.x, 3.0*C1.y - 3.0*C0.y)
    let D = C0

    return CGPointMake(((A.x*t+B.x)*t+C.x)*t+D.x, ((A.y*t+B.y)*t+C.y)*t+D.y)
}

// TODO: - future implementation
private func tangentAngleAtT(start: CGPoint, point1: CGPoint, point2: CGPoint, end: CGPoint, t: CGFloat) -> CGFloat {

   //bezier control points
    let C0 = start
    let C1 = point1
    let C2 = point2
    let C3 = end

   //The cubic polynomial coefficients such that Bez(t) = A*t^3 + B*t^2 + C*t + D
    let A = CGPointMake(C3.x - 3.0*C2.x + 3.0*C1.x - C0.x, C3.y - 3.0*C2.y + 3.0*C1.y - C0.y)
    let B = CGPointMake(3.0*C2.x - 6.0*C1.x + 3.0*C0.x, 3.0*C2.y - 6.0*C1.y + 3.0*C0.y)
    let C = CGPointMake(3.0*C1.x - 3.0*C0.x, 3.0*C1.y - 3.0*C0.y)

    return atan2(3.0*A.y*t*t + 2.0*B.y*t + C.y, 3.0*A.x*t*t + 2.0*B.x*t + C.x)
}

}
0
adăugat