@YRH
I appreciate you.
It would be difficult for only me to develop this feature request by only myself, but I have researched technologies that seem to be related. This research may be wrong, but I am posting it in the hope that it will contribute to Krita even a little.
Google Gemini
Okay, here’s the English translation of the previous explanation of Centripetal Catmull-Rom splines in C++:
Centripetal Catmull-Rom Spline in C++
The Centripetal Catmull-Rom spline, unlike standard or tensioned Catmull-Rom splines, adjusts the progression of the parameter t based on the distances between control points. This helps prevent self-intersections and loops in areas where control points turn sharply, resulting in more natural and smoother curves.
Concept of Centripetal Catmull-Rom Splines
In standard Catmull-Rom splines, the parameter t increases linearly between control points. However, if the distances between control points vary significantly, this can lead to unnatural curve shapes.
In Centripetal Catmull-Rom splines, the parameter interval αi between each control point is calculated proportionally to the ω-th power of the Euclidean distance between the control points. A common value for ω is 0.5 (square root).
αi=∥Pi+1−Pi∥ω
Then, the parameter value ti corresponding to each control point Pi is calculated cumulatively:
t0=0
ti=ti−1+αi−1 (for i=1,…,n−1)
Finally, the parameter t is normalized to the range [0,1]:
t^i=tn−1ti
When calculating a point C(u) on the curve (0≤u≤1), we first identify the parameter interval [t^i,t^i+1] to which the given u belongs. Then, we calculate a local parameter t′ (0≤t′≤1) within that interval:
t′=t^i+1−t^iu−t^i
This t′ is then used in a similar interpolation formula as the standard Catmull-Rom spline. However, the interpolation weights are adjusted based on the parameter intervals.
Formula for Centripetal Catmull-Rom Splines
The point C(u) on the curve within the interval [Pi,Pi+1] is calculated using the parameters t^i and t^i+1.
First, the tangent vector di at each control point is calculated. In Centripetal Catmull-Rom splines, the tangent vector is computed considering the parameter intervals:
di=2t^i+1−t^i−1(Pi+1−Pi−1)
Special handling is needed for the first and last points. For example, the tangent at the first point can be proportional to P1−P0, and the tangent at the last point proportional to Pn−1−Pn−2.
Then, using the local parameter t′ within the interval [t^i,t^i+1], Hermite interpolation is performed:
C(t′)=(2t′3−3t′2+1)Pi+(−2t′3+3t′2)Pi+1+(t′3−2t′2+t′)di(t^i+1−t^i)+(t′3−t′2)di+1(t^i+1−t^i)
Where di and di+1 are the tangent vectors at Pi and Pi+1, respectively.
C++ Code Example (for ω=0.5)
C++
#include
#include
#include
#include // std::numeric_limits
struct Point {
double x;
double y;
};
// Function to calculate the distance between two points
double distance(const Point& p1, const Point& p2) {
return std::sqrt(std::pow(p1.x - p2.x, 2) + std::pow(p1.y - p2.y, 2));
}
// Function to calculate a point on the Centripetal Catmull-Rom spline
Point calculateCentripetalCatmullRomPoint(double u, const std::vector& p, const std::vector& t) {
int n = p.size();
if (n < 4) {
std::cerr << “Error: At least 4 control points are required for Centripetal Catmull-Rom spline.” << std::endl;
return {std::numeric_limits::quiet_NaN(), std::numeric_limits::quiet_NaN()};
}
// Determine which segment u belongs to
int segment = -1;
for (int i = 0; i < n - 1; ++i) {
if (u >= t[i] && u <= t[i + 1]) {
segment = i;
break;
}
}
if (segment == -1) {
return p[n - 1]; // Return the last point if u is 1, etc.
}
double localT = (u - t[segment]) / (t[segment + 1] - t[segment]);
// Select the four control points for interpolation
int i = segment + 1;
Point p0 = (i > 1) ? p[i - 2] : p[0];
Point p1 = p[i - 1];
Point p2 = p[i];
Point p3 = (i < n - 1) ? p[i + 1] : p[n - 1];
double t2 = localT * localT;
double t3 = localT * t2;
Point result;
result.x = 0.5 * (
(2 * p1.x) +
(-p0.x + p2.x) * localT +
(2 * p0.x - 5 * p1.x + 4 * p2.x - p3.x) * t2 +
(-p0.x + 3 * p1.x - 3 * p2.x + p3.x) * t3
);
result.y = 0.5 * (
(2 * p1.y) +
(-p0.y + p2.y) * localT +
(2 * p0.y - 5 * p1.y + 4 * p2.y - p3.y) * t2 +
(-p0.y + 3 * p1.y - 3 * p2.y + p3.y) * t3
);
return result;
}
int main() {
// Coordinates of the control points (at least 4 are required)
std::vector controlPoints = {
{100, 100},
{200, 300},
{300, 150},
{400, 250},
{500, 100}
};
int n = controlPoints.size();
// Calculate the parameter t
std::vector<double> t(n);
t[0] = 0.0;
for (int i = 0; i < n - 1; ++i) {
t[i + 1] = t[i] + std::pow(distance(controlPoints[i], controlPoints[i + 1]), 0.5);
}
// Normalize the parameter t to the range [0, 1]
for (int i = 0; i < n; ++i) {
t[i] /= t[n - 1];
}
// Number of points to generate on the curve
int numPoints = 100;
std::vector<Point> centripetalCatmullRomPoints;
// Calculate points on the curve by varying the parameter u from 0 to 1
for (int i = 0; i <= numPoints; ++i) {
double u = static_cast<double>(i) / numPoints;
Point point = calculateCentripetalCatmullRomPoint(u, controlPoints, t);
centripetalCatmullRomPoints.push_back(point);
}
// Display the calculated points of the Centripetal Catmull-Rom spline
std::cout << "Centripetal Catmull-Rom spline points:" << std::endl;
for (const auto& point : centripetalCatmullRomPoints) {
std::cout << "(" << point.x << ", " << point.y << ")" << std::endl;
}
return 0;
}
Explanation of the Code
distance Function: Calculates the Euclidean distance between two points.
calculateCentripetalCatmullRomPoint Function:
u: The parameter ranging from 0 to 1.
p: The vector of control points.
t: The vector of normalized parameter values corresponding to each control point.
Handles the error case where fewer than 4 control points are provided.
Determines the parameter interval [ti,ti+1] that the given u falls into.
Calculates the local parameter localT within that interval.
Selects the four control points Pi−1,Pi,Pi+1,Pi+2 needed for the interpolation (using repetition for endpoints).
Calculates the point on the curve using the standard Catmull-Rom spline formula, but with the parameterization adjusted for the distances between control points.
main Function:
Control Point Definition: Sets the coordinates of the control points in the controlPoints vector.
Parameter t Calculation:
Sets the first parameter t[0] to 0.
Calculates the parameter values for each control point by accumulating the square roots of the distances between consecutive control points.
Normalizes these parameter values to the range [0,1] by dividing by the last parameter value.
Number of Points (numPoints): Specifies how many points to generate on the curve for a smooth appearance.
Loop: Iterates through values of the parameter u from 0 to 1, calling calculateCentripetalCatmullRomPoint to get the corresponding point on the spline, and stores these points in the centripetalCatmullRomPoints vector.
Result Display: Prints the calculated coordinates of the Centripetal Catmull-Rom spline points.
Key Points
Parameter Calculation: The core of the Centripetal Catmull-Rom spline is the calculation of the parameter t based on the distances between control points.
Endpoint Handling: The calculateCentripetalCatmullRomPoint function handles the endpoints by repeating the first and last control points when selecting the four points for interpolation.
Value of ω: This example uses ω=0.5. Other values (like 0.0 for uniform or 1.0 for chordal) can be used, but 0.5 often yields good results.
Centripetal Catmull-Rom splines are useful for generating smooth and natural curves, especially when dealing with control points that have sharp turns. They are effective in preventing self-intersections that can occur with standard Catmull-Rom splines in such cases. Feel free to experiment with different control point configurations and observe the resulting curves.
