KiCad PCB EDA Suite
Loading...
Searching...
No Matches
bezier_curves.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2014-2023 KiCad Developers, see AUTHORS.txt for contributors.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 */
23
24/************************************/
25/* routines to handle bezier curves */
26/************************************/
27
28#include <bezier_curves.h>
29#include <geometry/ellipse.h>
30#include <trigo.h>
31#include <math/vector2d.h> // for VECTOR2D, operator*, VECTOR2
32#include <wx/debug.h> // for wxASSERT
33
34
35BEZIER_POLY::BEZIER_POLY( const VECTOR2I& aStart, const VECTOR2I& aCtrl1,
36 const VECTOR2I& aCtrl2, const VECTOR2I& aEnd )
37{
38 m_ctrlPts.emplace_back( VECTOR2D( aStart ) );
39 m_ctrlPts.emplace_back( VECTOR2D( aCtrl1 ) );
40 m_ctrlPts.emplace_back( VECTOR2D( aCtrl2 ) );
41 m_ctrlPts.emplace_back( VECTOR2D( aEnd ) );
42
43 m_minSegLen = 0.0;
44}
45
46
47BEZIER_POLY::BEZIER_POLY( const std::vector<VECTOR2I>& aControlPoints )
48{
49 m_ctrlPts.reserve( aControlPoints.size() );
50
51 for( const VECTOR2I& pt : aControlPoints )
52 m_ctrlPts.emplace_back( pt );
53
54 m_minSegLen = 0.0;
55}
56
57
58void BEZIER_POLY::GetPoly( std::vector<VECTOR2I>& aOutput, int aMinSegLen, int aMaxSegCount )
59{
60 aOutput.clear();
61 std::vector<VECTOR2D> buffer;
62 GetPoly( buffer, double( aMinSegLen ), aMaxSegCount );
63
64 aOutput.reserve( buffer.size() );
65
66 for( const VECTOR2D& pt : buffer )
67 aOutput.emplace_back( VECTOR2I( (int) pt.x, (int) pt.y ) );
68}
69
70
71void BEZIER_POLY::GetPoly( std::vector<VECTOR2D>& aOutput, double aMinSegLen, int aMaxSegCount )
72{
73 wxASSERT( m_ctrlPts.size() == 4 );
74 // FIXME Brute force method, use a better (recursive?) algorithm
75 // with a max error value.
76 // to optimize the number of segments
77 double dt = 1.0 / aMaxSegCount;
78 VECTOR2D::extended_type minSegLen_sq = aMinSegLen * aMinSegLen;
79
80 aOutput.clear();
81 aOutput.push_back( m_ctrlPts[0] );
82
83 // If the Bezier curve is degenerated (straight line), skip intermediate points:
84 bool degenerated = m_ctrlPts[0] == m_ctrlPts[1] && m_ctrlPts[2] == m_ctrlPts[3];
85
86 if( !degenerated )
87 {
88 for( int ii = 1; ii < aMaxSegCount; ii++ )
89 {
90 double t = dt * ii;
91 double omt = 1.0 - t;
92 double omt2 = omt * omt;
93 double omt3 = omt * omt2;
94 double t2 = t * t;
95 double t3 = t * t2;
96
97 VECTOR2D vertex = omt3 * m_ctrlPts[0]
98 + 3.0 * t * omt2 * m_ctrlPts[1]
99 + 3.0 * t2 * omt * m_ctrlPts[2]
100 + t3 * m_ctrlPts[3];
101
102 // a minimal filter on the length of the segment being created:
103 // The offset from last point:
104 VECTOR2D delta = vertex - aOutput.back();
105 VECTOR2D::extended_type dist_sq = delta.SquaredEuclideanNorm();
106
107 if( dist_sq > minSegLen_sq )
108 aOutput.push_back( vertex );
109 }
110 }
111
112 if( aOutput.back() != m_ctrlPts[3] )
113 aOutput.push_back( m_ctrlPts[3] );
114}
115
116
117template<typename T>
118void TransformEllipseToBeziers( const ELLIPSE<T>& aEllipse, std::vector<BEZIER<T>>& aBeziers )
119{
120 EDA_ANGLE arcAngle = -( aEllipse.EndAngle - aEllipse.StartAngle );
121
122 if( arcAngle >= ANGLE_0 )
123 arcAngle -= ANGLE_360;
124
125 /*
126 * KiCad does not natively support ellipses or elliptical arcs. So, we convert them to Bezier
127 * splines as these are the nearest thing we have that represents them in a way that is both
128 * editable and preserves their curvature accurately (enough).
129 *
130 * Credit to Kliment for developing and documenting this method.
131 */
133 const int minBeziersPerCircle = 4;
134
136 const int numBeziers = static_cast<int>(
137 std::ceil( std::abs( arcAngle.AsRadians() / ( 2 * M_PI / minBeziersPerCircle ) ) ) );
138
140 const double angleIncrement = arcAngle.AsRadians() / numBeziers;
141
142 /*
143 * Now, let's assume a circle of radius 1, centered on origin, with angle startangle
144 * x-axis-aligned. We'll move, scale, and rotate it later. We're creating Bezier curves that hug
145 * this circle as closely as possible, with the angles that will be used on the final ellipse
146 * too.
147 *
148 * Thanks to the beautiful and excellent https://pomax.github.io/bezierinfo we know how to
149 * define a curve that hugs a circle as closely as possible.
150 *
151 * We need the value k, which is the optimal distance from the endpoint to the control point to
152 * make the curve match the circle for a given circle arc angle.
153 *
154 * k = 4/3 * tan(θ/4), where θ is the angle of the arc. In our case, θ=angleIncrement
155 */
156 double theta = angleIncrement;
157 double k = ( 4. / 3. ) * std::tan( theta / 4 );
158
159 /*
160 * Define our Bezier:
161 * - Start point is on the circle at the x-axis
162 * - First control point just uses k as the y-value
163 * - Second control point is offset from the end point
164 * - End point is defined by the angle of the arc segment
165 * Note that we use double here no matter what the template param is; round at the end only.
166 */
167 BEZIER<double> first = { { 1, 0 },
168 { 1, k },
169 { std::cos( theta ) + k * std::sin( theta ),
170 std::sin( theta ) - k * std::cos( theta ) },
171 { std::cos( theta ), std::sin( theta ) } };
172
173 /*
174 * Now construct the actual segments by transforming/rotating the first one
175 */
176 auto transformPoint =
177 [&]( VECTOR2D aPoint, const double aAngle ) -> VECTOR2D
178 {
179 // Bring to the actual starting angle
180 RotatePoint( aPoint,
181 -EDA_ANGLE( aAngle - aEllipse.StartAngle.AsRadians(), RADIANS_T ) );
182
183 // Then scale to the major and minor radiuses of the ellipse
184 aPoint *= VECTOR2D( aEllipse.MajorRadius, aEllipse.MinorRadius );
185
186 // Now rotate to the ellipse coordinate system
187 RotatePoint( aPoint, -aEllipse.Rotation );
188
189 // And finally offset to the center location of the ellipse
190 aPoint += aEllipse.Center;
191
192 return aPoint;
193 };
194
195 for( int i = 0; i < numBeziers; i++ )
196 {
197 aBeziers.emplace_back( BEZIER<T>( {
198 transformPoint( first.Start, i * angleIncrement ),
199 transformPoint( first.C1, i * angleIncrement ),
200 transformPoint( first.C2, i * angleIncrement ),
201 transformPoint( first.End, i * angleIncrement )
202 } ) );
203 }
204}
205
206
207template void TransformEllipseToBeziers( const ELLIPSE<double>& aEllipse,
208 std::vector<BEZIER<double>>& aBeziers );
209template void TransformEllipseToBeziers( const ELLIPSE<int>& aEllipse,
210 std::vector<BEZIER<int>>& aBeziers );
void TransformEllipseToBeziers(const ELLIPSE< T > &aEllipse, std::vector< BEZIER< T > > &aBeziers)
Transforms an ellipse or elliptical arc into a set of quadratic Bezier curves that approximate it.
double m_minSegLen
Control points.
Definition: bezier_curves.h:64
BEZIER_POLY(const VECTOR2I &aStart, const VECTOR2I &aCtrl1, const VECTOR2I &aCtrl2, const VECTOR2I &aEnd)
std::vector< VECTOR2D > m_ctrlPts
Definition: bezier_curves.h:67
void GetPoly(std::vector< VECTOR2I > &aOutput, int aMinSegLen=0, int aMaxSegCount=32)
Convert a Bezier curve to a polygon.
Generic cubic Bezier representation.
Definition: bezier_curves.h:78
VECTOR2< NumericType > Start
Definition: bezier_curves.h:90
VECTOR2< NumericType > C1
Definition: bezier_curves.h:91
VECTOR2< NumericType > C2
Definition: bezier_curves.h:92
VECTOR2< NumericType > End
Definition: bezier_curves.h:93
double AsRadians() const
Definition: eda_angle.h:117
This class was created to handle importing ellipses from other file formats that support them nativel...
Definition: ellipse.h:34
NumericType MinorRadius
Definition: ellipse.h:69
EDA_ANGLE Rotation
Definition: ellipse.h:70
EDA_ANGLE StartAngle
Definition: ellipse.h:71
NumericType MajorRadius
Definition: ellipse.h:68
EDA_ANGLE EndAngle
Definition: ellipse.h:72
VECTOR2< NumericType > Center
Definition: ellipse.h:67
VECTOR2_TRAITS< double >::extended_type extended_type
Definition: vector2d.h:72
static constexpr EDA_ANGLE ANGLE_0
Definition: eda_angle.h:401
@ RADIANS_T
Definition: eda_angle.h:32
static constexpr EDA_ANGLE ANGLE_360
Definition: eda_angle.h:407
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:390
constexpr int delta
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Calculate the new point of coord coord pX, pY, for a rotation center 0, 0.
Definition: trigo.cpp:228
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:638
VECTOR2< double > VECTOR2D
Definition: vector2d.h:637