BezierSplineArcFittingScript

From Hive13 Wiki
Jump to navigation Jump to search


Property "ProjectImage" (as page type) with input value "{{{ProjectImage}}}" contains invalid characters or is incomplete and therefore can cause unexpected results during a query or annotation process.

Hive13 Project
Bezier Spline Arc-Fitting Script

ProjectImagePlaceholder.png

Status: Inactive
Start Date: 2014-08-01
End Date: ?

Github Repo

A script, targeting QCAD, to convert a Bezier Spline exported from Illustrator into a Polyline containing line and arc segments.

There's actually no real reason for this since the approximation by tiny lines of splines is usually enough for a machine to work with, but theoretically conversion to a polyline with arc segments will allow for much less generated G-Code, and I am nothing if not theoretical.

Maths

Naming conventions used:

p* - p0, p1, pc, pa, pb...
A point, with x, y, and optionally z coordinates. (in this case, however, z is always 0.)
v* - v01, vac, vs...
A vector with x, y, and z components.
n* - n0, n1p, na, nsb...
A vector normalized to a length of 1 unit.

Operators

|*| - |v|, |a + b|, |(|a| + b)|...
Vector normalization
× - a × b, (a × b) × c
Vector cross product
· - a · b, v * (n1 · n2)...
Vector dot product

Fitting a Biarc to a Convex Bezier Curve

This formula is a bit limited compared to some approaches, but produces a unique pair of arcs for a given bezier spline segment, provided that the cage formed by the control points is convex. Due to using a biarc, self intersection is not supported, and such a spline must be split into smaller splines until all such created sub-segments are convex.

For a cubic bezier spline with points p0, p1, p2, and p3, where p0 and p3 are the start and end points respectively, and p1 and p2 are control points.

v01 = p1 - p0
v12 = p2 - p1
n1p = |( |v01| + |v12| )|
v32 = p2 - p3
v21 = p2 - p1
n2p = |( |v32| + |v21| )|

pcx = Intersection( Line( point = p0, direction = n1p ), Line( point = p3, direction = n2p ) )

v03 = p3 - p0
v30 = -v03
ncx = |(v01 × v03) × v12|
n0 = |v01 × (v03 × v01)|
n3 = |v32 × (v30 × v32)|

pc0 = Intersection( Line( point = p0, direction = n0 ), Line( point = pcx, direction = ncx ) )
pc1 = Intersection( Line( point = pcx, direction = ncx ), Line( point = p3, direction = n3 ) )

Arc0 = Arc( start = p0, end = pc, center = pc0, startDirection = v01 )
Arc1 = Arc( start = pc, end = p3, center = pc1, startDirection = v12 )

Progress

Week of 2014-08-18

Made a final push to get the script working. It now successfully produces a polyline through one iteration of arcfitting with no spline splitting. Some curves are approximated pretty well, but particularly eccentric ellipses become lozenges, which is not desirable.

Week of 2014-08-25

Stubbed out guards (They all return false for now.) Figured at this point I should just convert it to coffeescript, which is morally and technically superior to javascript, and punt it over to github instead of dropbox.

Week of 2014-09-01

Rewrote in Coffeescript, made into Brunch project, added Lodash as a dep, refactored _v into V.js, a small underscore/lodash-esque to make working with QCAD's RVector class more natural looking. Uploaded to Github.