System and method for approximating parametric curves using optimal number of segments
View Patent ↗A system and method for approximating parametric curves may subdivide curves using a minimum number of subdivisions while meeting a given error tolerance. The method may include determining a subdivision point such that the maximum chord error on one side of the point is equal to the maximum chord error on the other side of the point, the chord error being the distance between the curve and a linear approximation thereof. These techniques may be applied recursively to sub-portions defined by the subdivision point if the maximum error is greater than a pre-determined error tolerance. The pre-determined error tolerance may be a default tolerance, or may be application-specific or user-configurable, in various embodiments. By subdividing a curve into fewer segments than conventional methods, the system and methods described herein may allow an alternate representation of the curve to be generated that includes less data than one generated using conventional methods.
1. A system comprising:
one or more processors;
a memory having instructions stored thereon that, if executed by the one or more processors, cause the one or more processors to perform operations comprising:
accessing data representing at least a portion of a parametric curve;
identifying a subdivision point along the at least a portion of the parametric curve such that when two linear segments are defined that connect the subdivision point to respective endpoints of the at least a portion of the parametric curve, a maximum chord error on each side of the subdivision point is equal,
wherein the maximum chord error is a maximum distance between each of the two linear segments and respective points on two sub-portions of the at least a portion of the parametric curve between the respective endpoints and the subdivision point;
storing data indicative of the subdivision point;
determining whether the maximum chord error exceeds a pre-determined error tolerance; and
in response to determining that the maximum chord error exceeds the pre-determined error tolerance:
dividing the at least a portion of the parametric curve into the two sub-portions at the identified subdivision point; and
repeating, for each of the two sub-portions, the identifying, the storing, and the determining.
2. The system of claim 1 , wherein the pre-determined error tolerance is a default error tolerance.
3. The system of claim 1 , wherein the pre-determined error tolerance is application-specific.
4. The system of claim 1 , wherein the pre-determined error tolerance is user-configurable.
5. The system of claim 1 , the operations further comprising:
generating an alternate representation of the at least a portion of the parametric curve comprising two piecewise segments defined by the subdivision point and the respective endpoints; and
storing data representing the alternate representation.
6. The system of claim 5 , wherein the two piecewise segments comprise the two linear segments.
7. The system of claim 5 , wherein the two piecewise segments comprise two curve segments.
8. The system of claim 1 , wherein the identifying a subdivision point comprises:
defining a set of simultaneous equations representing relationships between the subdivision point and respective points of maximum chord error on the at least a portion of the parametric curve on each side of the subdivision point; and
solving the set of simultaneous equations using an iterative solver.
9. The system of claim 8 , the operations further comprising:
prior to solving the set of simultaneous equations, initializing variables representing the subdivision point and the respective points using values that are dependent on a midpoint of the at least a portion of the parametric curve.
10. The system of claim 1 , wherein the one or more processors comprise one or more of a general-purpose central processing unit (CPU) and a graphics processing unit (GPU).
11. A non-transitory computer-readable storage medium having instructions stored thereon that, if executed by a processor, cause the processor perform operations comprising:
accessing data representing at least a portion of a parametric curve;
identifying a subdivision point along the at least a portion of the parametric curve such that when two linear segments are defined that connect the subdivision point to respective endpoints of the at least a portion of the parametric curve, a maximum chord error on each side of the subdivision point is equal,
wherein the maximum chord error is a maximum distance between each of the two linear segments and respective points on two sub-portions of the at least a portion of the parametric curve between the respective endpoints and the subdivision point;
storing data indicative of the subdivision point;
determining whether the maximum chord error exceeds a pre-determined error tolerance; and
in response to determining that the maximum chord error exceeds the pre-determined error tolerance:
dividing the at least a portion of the parametric curve into the two sub-portions at the identified subdivision point; and
repeating, for each of the two sub-portions, the identifying, the storing, and the determining.
12. The computer-readable medium of claim 11 , wherein the pre-determined error tolerance is application-specific or user-configurable.
13. The computer-readable storage medium of claim 11 , the operations further comprising:
generating an alternate representation of the at least a portion of the parametric curve comprising two piecewise segments defined by the subdivision point and the respective endpoints; and
storing data representing the alternate representation.
14. The computer-readable storage medium of claim 11 , wherein the identifying a subdivision point comprises:
defining a set of simultaneous equations representing relationships between the subdivision point and respective points of maximum chord error on the at least a portion of the parametric curve on each side of the subdivision point; and
solving the set of simultaneous equations using an iterative solver.
15. A computer-implemented method, comprising:
receiving, at a computing device, data representing at least a portion of a parametric curve;
identifying, by the computing device, a subdivision point along the at least a portion of the parametric curve such that when two linear segments are defined that connect the subdivision point to respective endpoints of the at least a portion of the parametric curve, a maximum chord error on each side of the subdivision point is equal,
wherein the maximum chord error is a maximum distance between each of the two linear segments and respective points on two sub-portions of the at least a portion of the parametric curve between the respective endpoints and the subdivision point;
storing data indicative of the subdivision point;
determining whether the maximum chord error exceeds a pre-determined error tolerance; and
in response to determining that maximum chord error exceeds the pre-determined error tolerance:
dividing the at least a portion of the parametric curve into the two sub-portions at the identified subdivision point; and
repeating, for each of the two sub-portions, the identifying, the storing, and the determining.
16. The computer-implemented method of claim 15 , wherein the pre-determined error tolerance is one or more of application-specific and user-configurable.
17. The computer-implemented method of claim 15 , further comprising:
generating, by the computing device, an alternate representation of the at least a portion of the parametric curve comprising two piecewise segments defined by the subdivision point and the respective endpoints; and
storing, in a repository accessible by the computing device, data representing the alternate representation.
18. The computer-implemented method of claim 15 , wherein the identifying a subdivision point comprises:
defining a set of simultaneous equations representing relationships between the subdivision point and respective points of maximum chord error on the at least a portion of the parametric curve on each side of the subdivision point; and
solving the set of simultaneous equations using an iterative solver module invoked by the computing device.