Improve spline decomposition #2
Assignees
Comments
marvin0102
added a commit
to marvin0102/mado
that referenced
this issue
Jul 18, 2024
# 這是第一個提交說明： Fix the incorrect rendering of PNG file The red green blue permutations of twin and png are inconsistent. Reverse the RGB premutation of png to BGR to make them consistent. # 這是提交說明 sysprog21#2： Fix the incorrect rendering of PNG files Fix the RGB rendering of PNG files and pass the tests of color formats include RGB, RGBA, PALETTE and GRAY.
marvin0102
added a commit
to marvin0102/mado
that referenced
this issue
Jul 18, 2024
# 這是第一個提交說明： Fix the incorrect rendering of PNG file The red green blue permutations of twin and png are inconsistent. Reverse the RGB premutation of png to BGR to make them consistent. # 這是提交說明 sysprog21#2： Fix the incorrect rendering of PNG files Fix the RGB rendering of PNG files and pass the tests of color formats include RGB, RGBA, PALETTE and GRAY.
|
The font-edit is not only useful for observing how font rendering works but also serves as a testbed for evaluating the enhancement of iterative spline decomposition, where you can operate with floating point arithmetic instead of fixed-point arithmetic. 
|
|
Here are two books that might be helpful: A Primer on Bézier Curves Computer Aided Geometric Design In the second book 10.6 Error Bounds,
|
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Aug 8, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. See https://keithp.com/blogs/more-iterative-splines/ for details. See also: sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Aug 8, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. See https://keithp.com/blogs/more-iterative-splines/ for details. See also: sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Aug 8, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Aug 18, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Aug 18, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Aug 18, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Aug 18, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Sep 7, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Sep 15, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Sep 15, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Sep 15, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Sep 17, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
|
Another feasible interpolation method is called the Euler spiral. According to @weihsinyeh's notes, the Google team adopted the Euler spiral in their paper titled "GPU-friendly Stroke Expansion," published in the Proceedings of the ACM on Computer Graphics and Interactive Techniques in 2024. Raphael Linus Levien's work, From Spiral to Spline: Optimal Techniques in Interactive Curve Design, provides a detailed description of the characteristics of the curve, covering both its physical and mathematical aspects, as well as its application in font rendering.
|
weihsinyeh
added a commit
to weihsinyeh/mado
that referenced
this issue
Nov 2, 2024
This commit focuses on decomposing a spline into fewer segments by finding an optimal value of t that meets our target tolerance for flatness while ensuring it is at least as large as the maximum distance from the line segment connecting the starting and ending points of the original curve. The approach employs the bisection method to determine the value of t. The idea behind this method is based on the properties of curves. By choosing the point of maximum curvature as the junction between two line segments during curve fitting, we ensure that the curvature of all points on both segments is less than the maximum curvature of the original curve. This strategy guarantees that the two line segments fit the original curve as well as possible. Additionally, the properties of these two segments are such that the slope of the tangent line at all points in one segment is relatively positive compared to the slope of the line connecting the starting and ending points of the original curve, while the slope in the other line segment is relatively negative. Consequently, the point where the tangent line's slope is zero relative to the connecting line results in the maximum distance. This distance is recorded to ensure we maximize it as much as possible. Although this approach requires more computation to decompose the spline into fewer segments, the extra effort is justified for improved fit. I have modified the implementation of font-edit to use fixed-point arithmetic and used it as the evaluation testbed to do experiments as follows: original - Average number of _de_casteljau calls per point: 1.99 original - Average points per character: 18.89 flexibly update - Average number of _de_casteljau calls per point: 4.53 flexibly update - Average points per character: 16.30 See https://keithp.com/blogs/more-iterative-splines/ for details. Close sysprog21#2
|
Close via 7e25ecd |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The usual method to convert a spline into a sequence of line segments is to split the spline in half using de Casteljau's algorithm recursively until the spline can be approximated by a straight line within a defined tolerance. The commit 6d85b42 has already changed the original recursion to an iterative method, avoiding unbounded recursion. Four levels of recursion will consume more than 64 coordinates' worth of space, which can easily overflow the stack of a tiny machine. However, as Keith mentioned in Slightly Better Iterative Spline Decomposition, it is possible to make the overall computational cost lower than a straightforward binary decomposition, and no recursion is required.
See also: Decomposing Splines Without Recursion
The text was updated successfully, but these errors were encountered: