diff options
author | Joe Crayne <joe@jerkface.net> | 2019-07-27 19:31:44 -0400 |
---|---|---|
committer | Joe Crayne <joe@jerkface.net> | 2019-07-27 19:36:31 -0400 |
commit | 175e4a0ee82e4db1fade4fbd8b5e55e88c21a826 (patch) | |
tree | 1110d5a7b63c49453395e04d9bb337285db2202f | |
parent | b79975c689f7c84e39c6ca326e93c58857ac6c37 (diff) |
Generalized curve-sampling to 3 dimensions.
-rw-r--r-- | Bezier.hs | 67 |
1 files changed, 63 insertions, 4 deletions
@@ -24,7 +24,7 @@ data Polygonization = Polygonization | |||
24 | type AllocatedRange = Polygonization | 24 | type AllocatedRange = Polygonization |
25 | 25 | ||
26 | data Curve = Curve | 26 | data Curve = Curve |
27 | { curvePlane :: Plane -- ^ Curve is embedded in this plane. | 27 | { curvePlane :: Maybe Plane -- ^ Curve is embedded in this plane. |
28 | , curveA :: Vector Float -- ^ 3d start point. | 28 | , curveA :: Vector Float -- ^ 3d start point. |
29 | , curveB :: Vector Float -- ^ 2nd 3d control point. | 29 | , curveB :: Vector Float -- ^ 2nd 3d control point. |
30 | , curveC :: Vector Float -- ^ 3rd 3d control point. | 30 | , curveC :: Vector Float -- ^ 3rd 3d control point. |
@@ -61,8 +61,24 @@ subdivideCurve δ curve range store = do | |||
61 | -- nutshell: we divide the half circle into n equal parts and sample the curve | 61 | -- nutshell: we divide the half circle into n equal parts and sample the curve |
62 | -- whenever the tangent line is at one of these angles to a fixed axis. | 62 | -- whenever the tangent line is at one of these angles to a fixed axis. |
63 | sampleCurve :: Real a => a -> Curve -> [Float] | 63 | sampleCurve :: Real a => a -> Curve -> [Float] |
64 | sampleCurve δ curve | G.init (curvePlane curve) /= ĵ = error "TODO: arbitrary plane normal in sampleCurve" | 64 | sampleCurve δ curve |
65 | sampleCurve δ curve@Curve{curveA = a, curveB = b, curveC = c, curveD = d} = do | 65 | | Just plane <- curvePlane curve |
66 | , G.init plane == ĵ = sampleCurveXZ δ curve | ||
67 | | otherwise = sampleCurveTwist δ curve | ||
68 | |||
69 | -- | Bounding box diagonal length for a cubic curve's 4 control points. | ||
70 | curveBBDiag :: Fractional b => Curve -> b | ||
71 | curveBBDiag Curve{curveA = a, curveB = b, curveC = c, curveD = d} = | ||
72 | realToFrac $ norm_2 ( mx - mn ) | ||
73 | where | ||
74 | mx = maximum [a,b,c,d] | ||
75 | mn = minimum [a,b,c,d] | ||
76 | |||
77 | |||
78 | -- | The Surazhsky curve sampling where the Y coordinates are ignored in order | ||
79 | -- that we can treat the curve in only two dimensions. | ||
80 | sampleCurveXZ :: Real a => a -> Curve -> [Float] | ||
81 | sampleCurveXZ δ curve@Curve{curveA = a, curveB = b, curveC = c, curveD = d} = do | ||
66 | let (x0,y0) = xz a -- We assume the curve is embedded in the xz plane so that | 82 | let (x0,y0) = xz a -- We assume the curve is embedded in the xz plane so that |
67 | (x1,y1) = xz b -- we can use a technique for 2 dimensional curves. | 83 | (x1,y1) = xz b -- we can use a technique for 2 dimensional curves. |
68 | (x2,y2) = xz c -- TODO: Use the correct projection here for curves | 84 | (x2,y2) = xz c -- TODO: Use the correct projection here for curves |
@@ -71,7 +87,7 @@ sampleCurve δ curve@Curve{curveA = a, curveB = b, curveC = c, curveD = d} = do | |||
71 | -- ought to be alright when δ is small relative to the curve's bounding | 87 | -- ought to be alright when δ is small relative to the curve's bounding |
72 | -- box. It was derived using the aproximation tan θ ≃ θ for small θ. | 88 | -- box. It was derived using the aproximation tan θ ≃ θ for small θ. |
73 | n = ceiling (pi/sqrt(2*realToFrac δ/dist)) | 89 | n = ceiling (pi/sqrt(2*realToFrac δ/dist)) |
74 | dist = maximum [ norm_2 (curveA curve - x) | x <- [b,c,d]] | 90 | where dist = curveBBDiag curve |
75 | tx = x3 - x0 | 91 | tx = x3 - x0 |
76 | ty = y3 - y0 | 92 | ty = y3 - y0 |
77 | θ₀ = atan2 ty tx -- For our fixed axis, we use the line connecting the | 93 | θ₀ = atan2 ty tx -- For our fixed axis, we use the line connecting the |
@@ -88,6 +104,49 @@ sampleCurve δ curve@Curve{curveA = a, curveB = b, curveC = c, curveD = d} = do | |||
88 | θ <- [ θ₀ + pi/fromIntegral n*fromIntegral i | i <- [ 0 .. n - 1 ] ] | 104 | θ <- [ θ₀ + pi/fromIntegral n*fromIntegral i | i <- [ 0 .. n - 1 ] ] |
89 | tangents (cos θ) (sin θ) x0 y0 x1 y1 x2 y2 x3 y3 | 105 | tangents (cos θ) (sin θ) x0 y0 x1 y1 x2 y2 x3 y3 |
90 | 106 | ||
107 | twistAbout :: Vector Float -> Vector Float -> Vector Float -> (Float,Float) | ||
108 | twistAbout ĥ k̂ v = let { x = dot ĥ v | ||
109 | ; y = v - scale x ĥ | ||
110 | } | ||
111 | in (x, (if dot y k̂ <0 then negate else id) $ realToFrac $ norm_2 y) | ||
112 | |||
113 | |||
114 | -- | The Surazhsky curve sampling where the middle two control points are | ||
115 | -- rotated about the line connecting the curve's end points in order that they | ||
116 | -- become coplanar so that we can treat the curve in only two dimensions. | ||
117 | sampleCurveTwist :: Real a => a -> Curve -> [Float] | ||
118 | sampleCurveTwist δ curve@Curve{curveA = a, curveB = b, curveC = c, curveD = d} = do | ||
119 | let (x0,y0) = twistAbout ĥ k̂ a | ||
120 | (x1,y1) = twistAbout ĥ k̂ b | ||
121 | (x2,y2) = twistAbout ĥ k̂ c | ||
122 | (x3,y3) = twistAbout ĥ k̂ d | ||
123 | -- ĥ = normalize $ vector $ map realToFrac $ toList (d - a) | ||
124 | ĥ = let v = d - a in scale (1 / realToFrac (norm_2 v)) v | ||
125 | k̂ = let { k = minimumBy (comparing $ \x -> abs (dot x ĥ)) $ map (subtract a) [b,c] | ||
126 | ; v = k - scale (dot k ĥ) ĥ } | ||
127 | in scale (1 / realToFrac (norm_2 v)) v | ||
128 | -- This computation of n was not detailed in the paper, but I figure it | ||
129 | -- ought to be alright when δ is small relative to the curve's bounding | ||
130 | -- box. It was derived using the aproximation tan θ ≃ θ for small θ. | ||
131 | n = 1 + ceiling (pi/sqrt(realToFrac δ/dist)) | ||
132 | where dist = curveBBDiag curve | ||
133 | tx = x3 - x0 | ||
134 | ty = y3 - y0 | ||
135 | θ₀ = atan2 ty tx -- For our fixed axis, we use the line connecting the | ||
136 | -- curve's end points. This has the nice property | ||
137 | -- that the first two returned sample points will be | ||
138 | -- at the maximum distance the curve makes with its | ||
139 | -- straight line aproximation. | ||
140 | -- | ||
141 | -- Idea: It occurs to me that we can extend the | ||
142 | -- Surazhsky method to 3 dimensions by obtaining a | ||
143 | -- parameterization using polar coordinates about this | ||
144 | -- axis. We might ignore curvature about this axis as | ||
145 | -- less important. | ||
146 | θ <- [ θ₀ + fromIntegral i * pi/fromIntegral n | i <- [ 0 .. n - 1 ] ] | ||
147 | tangents (cos θ) (sin θ) x0 y0 x1 y1 x2 y2 x3 y3 | ||
148 | |||
149 | |||
91 | tangents :: (Ord a, Floating a) => | 150 | tangents :: (Ord a, Floating a) => |
92 | a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> [a] | 151 | a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> [a] |
93 | tangents tx ty x0 y0 x1 y1 x2 y2 x3 y3 = filter relevent $ quadraticRoot a b c | 152 | tangents tx ty x0 y0 x1 y1 x2 y2 x3 y3 = filter relevent $ quadraticRoot a b c |