평행 곡선을 결정하는 것은 기본적인 2D 지오메트리 작업 중 하나입니다. 경로에서 스트로크 윤곽을 만드는 기초가되는 그래픽에 분명한 응용 프로그램이 있지만 컴퓨터 지원 제조 (유한 반경을 가진 밀링 도구의 경로 결정) 및 로봇 공학을위한 경로 계획에도 적용됩니다. 지금까지 문헌에는 많은 해결책이 있지만이 글에서는 더 깨끗한 해결책을 제안합니다.
좋은 설문 조사 논문은 Comparing입니다. 오프셋 곡선 근사 방법. 이러한 접근 방식의 주요 차이점은 곡선 표현의 선택입니다. 평행 곡선을 유도하는 데 매우 전문화 된 곡선 표현의 예는 피타고라스 호도 그래프입니다. Pythagorean Hodograph의이 평행 곡선은 정확한 매개 변수 다항식 곡선이지만, 소스 곡선을 표현으로 변환하고 결과 곡선이 고차 유리 다항식이므로 변환하려면 추가 근사가 필요하기 때문에 근사 기술이 실제로 필요합니다. 예를 들어, 입방 베지 어로.
특히이 블로그는 평행 곡선 문제에 특히 적합한 곡선 표현으로 조각 별 오일러 나선을 제안합니다. .
kurbo에는 이러한 많은 아이디어 (현재 아직 PR 단계에 있음)가 구현되어 있습니다. 또한 colab 노트북을 사용하여 여러 수학을 탐구했으며 그 사본도 사용 가능하게 만들었습니다.
교두
평행 곡선을 특별하게 만드는 것 중 하나는 교두가 자주 나타난다는 것입니다. 특히, 소스 커브의 곡률 반경이 오프셋과 일치 할 때마다 첨 점이 나타납니다. 이것은 일반 첨점으로 분류되며 많은 곡선 군의 기능입니다. 아래에서 조금 더 수량화하겠습니다.
평행 곡선을 계산하는 알고리즘의 일반적인 기능은 교두의 위치를 식별하고 그 위치를 세분화하는 것입니다. 이는 기본적으로 특정 곡률 값 (오프셋 거리의 역수)을 해결하는 것을 의미합니다. 소스 곡선이 3 차 베지 어인 경우 이러한 첨점은 최대 4 개까지있을 수 있으며이를 찾으려면 사소한 수치 해석이 필요합니다.
곡선 길이의 함수로서의 곡률
평행 곡선에 대한 나의 접근 방식 (그리고 제 논문을 포함한 제 커브 작업은 일반적으로 곡률과 호 길이의 관계를 고려하는 것입니다. 구체적인 직감은 자동차가 커브를 따라 일정한 속도로 주행 할 때 스티어링 휠의 위치라는 것입니다. 일부 곡선의 경우 곡률은 호 길이 (Cesàro 방정식)의 함수로 닫힌 형태의 분석 공식으로 표현 될 수 있지만 일반적으로 관계를 결정하려면 수치 기법이 필요합니다. 예를 들어 오일러 탐색기에는 대화 형 입방 베 지어 아래에 호 길이의 함수로 곡률 플롯이 있습니다. 그것을 실험하는 것은 직감을 발전시키는 훌륭한 방법입니다.
하나의 곡선 does 는 특히 간단한 Cesàro 방정식이 오일러 나선형입니다. 오일러 나선형 세그먼트의 공식은 다음과 같습니다.
(상세한 수학 및 코드를 따르려는 분들을위한 메모 : 대부분의 수학 및 숫자 코드는 $ -0.5 사용 leq s leq 0.5 $ 짝수 / 홀수 대칭을 활용하는 데 도움이되지만 kurbo의 ParamCurve 특성을 포함하여 매개 변수화 된 곡선에 대한 규칙은 $ 0 leq s leq 1 $입니다. 따라서 오프셋 0.5가 자주 표시됩니다. 유사하게 실제 호 길이에 대한 다양한 스케일링을 볼 수 있지만 매개 변수화 된 곡선 규칙은 호 길이를 1로 가정합니다.이 블로그에서는 너무 복잡하지 않고 직관을 제공하는 것이 목표이므로 이러한 세부 사항을 훑어 볼 것입니다. 세부 사항에서.)
오일러 나선의 평행 곡선
일반적으로 대부분의 곡선에는 평행 곡선에 대한 간단한 공식이 없습니다. 명백한 예외는 평행 곡선이 또 다른 원호 인 원호입니다. 평행 곡선에 대한 다루기 쉬운 표현이있는 또 다른 곡선 패밀리는 Pythagorean Hodographs입니다.
Cesàro 방정식 인 Euler의 매우 간단한 공식 덕분에 나선형은 평행 곡선에 대한 단순한 폐쇄 형 방정식을 사용하는 드문 곡선 중 하나입니다. 이 방정식은 Heinrich Wieleitner, Die Parallelkurve der Klothoide의 1906 년 논문에서 처음 발표되었습니다. 독일어를 읽지 못하는 사람들을 위해 Rahix는 친절하게 영어로 번역을 제공했습니다 : PDF, TeX 소스.
, Wieleitner가 더 단순화 할 수있는 기회를 놓친 것 같습니다. 당시의 스타일은 반경 으로 세사로 방정식을 작성하는 것이 었습니다. 곡률 (곡률의 역수)이지만 특히 오일러 나선 및 평행 곡선의 경우 곡률을 사용하면 훨씬 더 간단한 방정식이 직접 생성됩니다. 첨 점이 $ s_0 $에 있으면 방정식은 매우 간단합니다.
[kappa(s)=frac{c}{sqrt{s – s_0}} + frac{1}{l}]
방정식은 아래에 그래프로 표시되어 있으며이를 클릭하면 매개 변수 슬라이더가있는 Desmos 계산기 그래프로 연결됩니다.
여기서 $ c $는 나선의 매개 변수에 따른 계수입니다. Wieleitner 논문의 표기법에 연결하려면 $ c=a / sqrt {2 l ^ 3} $ 및 $ s_0=-a ^ 2 / {2l} $입니다. 또한이 방정식의 동등성과 Wieleitner 논문에서 더 많은 관련 방정식을 대화식으로 보여주는 Desmos 계산기 그래프를 만들었습니다.
특징적인 역 제곱근 곡률을 가진 위와 유사한 첨두를 가진 다른 곡선이 많이 있습니다. 가장 명확한 연결은 동일하지만 $ 1 / l $ 항이없는 원 인벌 류트입니다. 즉 오프셋이 무한대로 갈수록 오일러 나선 평행 곡선이 원 인벌 류트에 접근합니다. 이것은 원형 나선이 자체 평행 곡선이라는 사실에 대한 직관을 제공합니다. 원형 인벌 류트는 기어 톱니를 맞 물리기위한 최적화 된 프로파일로 가장 유명하며 경사 나 마찰없이 부드럽게 힘을 전달합니다.
기타 곡선 유사한 첨두에는 사이클로이드 (뿐만 아니라 에피 사이클로이드, 하이포 사이클로이드, 천체, 삼각근, 카디오이드 및 네 프로이드를 포함한 많은 변형)와 반입 방 포물선이 포함됩니다. 후자는 3 차 베 지어 (컨트롤 암이 대칭 X를 형성하는 경우)로 정확하게 표현 될 수 있기 때문에 특히 흥미 롭습니다.
오일러 나선의 평행 곡선은 완벽하게 구불 구불하며, 피타고라스 호도 그래프 곡선의 전통과 고차 유리 다항식에 따라 간단히 처리하기 위해 모든 다운 스트림을 요구할 수 있습니다. 그들. 하지만 다운 스트림 처리를 더 쉽게하기 위해 좀 더 다루기 쉬운 표현 인 부분 별 오일러 나선으로 다시 변환합니다.
Geometric Hermite interpolation
Hermite 보간은 잘 알려진 기술입니다. 가장 간단한 형식에서는 각 다항식 세그먼트의 매개 변수가 끝점의 값과 도함수에서 결정되는 일부 함수에 대한 부분 다항식 근사를 생성하는 데 사용됩니다. 예를 들어, 3 차 Hermite 보간에서 3 차 다항식은 끝점의 값과 1 차 도함수 (다항식에 대한 4 개의 계수에 해당하는 4 개의 값)에서 결정됩니다. 결과는 도함수가 정확히 일치하므로 (그리고 소스 곡선과 동일) C1 연속입니다.
2D에서는 구별이 있습니다. C1과 G1 (기하학적) 연속성 사이. C1 연속성에서 전체 미분은 방향과 크기 모두 일치해야합니다. 모션 곡선 애니메이션과 같은 응용 프로그램의 경우 크기가 중요하지만 (동작 속도를 나타냄) 곡선의 경우 중요하지 않습니다. G1 연속성은 접선이 일치해야하지만 미분의 크기를 지정하지 않습니다.
이러한 응용 프로그램에서 기하학적 Hermite 보간은 더 많습니다. 곡선의 모든 매개 변수를 사용하여 모양을 맞출 수 있으므로 효율적입니다. 오일러 나선은 기하학적 인 Hermite 보간에 특히 적합하며이 주제에 대한 문헌이 있습니다. 부드러움에 대한 합리적인 가정 (프랙탈 곡선은 제외하지만 단순한 첨점 포함)의 경우 정확도는 $ O (n ^ 4) $로 조정됩니다. 세분화 수를 두 배로 늘리면 오류가 16 배 감소합니다.이 배율은 다음과 같습니다. $ y $ 값이 작을 때 오일러 나선 세그먼트가 3 차 다항식에 근접하므로 1D 함수의 3 차 Hermite 보간은 놀라운 일이 아닙니다.
내 논문의 섹션 8.2는 G1 Hermite 제약 조건에서 오일러 나선형 매개 변수를 결정하는 시컨트 방법을 제공하며, 이는 kurbo PR의 fit_euler 메서드. 그것은 좋은 기술이고 그 수렴은 탁월합니다 (근 선형 문제에 대한 뉴턴 스타일 솔버의 전형적인 2 차적).하지만 저는 더 나은 방법을 실험 해 왔습니다. 연결된 노트북은 훨씬 더 빠른 다항식 근사 (2D Taylor 시리즈를 기반으로 함)를 탐색합니다. 측정시 7ns 대 240ns이고 광범위한 매개 변수에서 매우 정확해야합니다. 오류 경계를 엄격하게 설정하지는 않았지만이 접근 방식은 전체 알고리즘을 번개처럼 빠르게 만드는 데 도움이 될 것입니다.
Geometric Hermite 보간은 오일러 나선 세그먼트의 평행 곡선과 다른 오일러 나선 세그먼트를 근사하는 데 효과적입니다.
실제 평행 곡선은 파란색이고 근사값은 빨간색입니다. 거친 모양은 같지만 가운데가 튀어 나옵니다. 더 정확한 근사치를 만들기 위해이 오류를 추정 할 수 있어야합니다.
간단하고 정확한 오류 측정 항목
목표 오차 범위가 주어진 경우 근사화에 대한 가장 일반적인 접근 방식은 적응 형 세분화입니다. 오차를 근사화하고 목표를 초과하면 세분화합니다. 오류를 평가하는 것이 항상 쉬운 것은 아닙니다. 가장 일반적으로 길이를 따라 여러 지점에서 곡선을 평가하고 해당 지점이 소스 곡선에 얼마나 가까운 지 테스트하는 것과 같은 수치 기술을 기반으로합니다.
다행스럽게도 오일러 나선을 사용하여 오일러 나선 평행 곡선을 근사화하는 경우 오류에 대한 매우 간단한 공식이 있습니다. 실제로 적응 형 세분화를 완전히 피하고 오류 경계를 충족하는 데 필요한 세분화 수를 정확하게 예측할 수있을뿐만 아니라 각 세그먼트가 동일한 오류를 갖도록 세분화를 분석적으로 배치 할 수 있습니다.
코드 길이 1로 정규화됩니다. 여기서 오일러 나선 세그먼트의 호 길이는 $ a $이며, 중앙 곡률이 $ kappa_0 인 오일러 나선 세그먼트를 근사하는 오류입니다. $ 및 곡률 변화 $ kappa_1 $ 거리 별 오프셋 $ l $ :
[E approx 0.005aleft|frac{1}{kappa_0 a^{-1} + l^{-1}}right|kappa_1 ^ 2]
$ kappa_0 a ^ {-1} + l ^ {-1} $ 항은 교두로부터의 거리를 나타냅니다. 오차는이 거리에 반비례합니다. 또한 $ kappa_1 $는 세분화 수의 제곱으로 스케일되므로 전체 공식은 예상대로 네 번째 제곱으로 스케일됩니다.
정확한 세분
오류 메트릭에 대한 이러한 간단한 공식을 고려할 때, 우리는 단순히 오류 메트릭을 평가하고 임계 값이 충족되지 않으면 절반으로 세분화하는 일반적인 적응 형 세분화 접근 방식보다 더 잘할 수 있습니다. 정확히 얼마나 많은 세분화가 필요한지, 분할 할 위치를 정확히 계산하여 세분화 된 각 세그먼트의 오류가 동일합니다.
자세한 내용 첨부 된 노트에 있지만 본질은 이것입니다. 다음 공식에 따라 원래 곡선에서 $ s_i $를 선택하면 $ s_i $에서 $ s_ {i + 1} $까지의 각 세그먼트의 오류는 거의 동일합니다.
[s_i=s_0 + (t_0 + i Delta t)^frac{4}{3}]
여기 $ s_0 $는 교두. 이 공식을 사용하는 열쇠는 $ t_0 $를 선택하여 $ s_0 $가 엔드 포인트 중 하나에 도착한 다음 $ Delta t $ 및 $ n $를 선택하여 $ t_0 + n Delta t $가 다른 엔드 포인트에 도착하고 $ n $는 여전히 오류 한계를 충족하는 최소값입니다. 세부 사항은 계산 비용이 많이 들지는 않지만 약간 까다 롭고 노트북에서 찾을 수 있습니다.
이것은 정확히 동일한 오류가 발생하지는 않지만 약간 언더 슈트 교두에 매우 가까운 세그먼트의 경우. 결과 g 비 효율성은 아마도 실제로 몇 퍼센트 일 것입니다. 제 생각에는 그러한 직접적인 해결책을 가질 가치가 있습니다.
위의 이미지는이 정확한 접근 방식으로 생성 된 세분화를 약 10 분의 1 픽셀의 정확도로 보여 주며 글꼴 및 2D 아트 워크 응용 프로그램에 매우 적합합니다. 일반적으로 교두가없는 경우 2 ~ 4 개의 세분화가 있고 교두가있는 경우 최대 2 배가 있습니다. 이 블로그의 리드 이미지는 10 ^ -5 픽셀의 정확도를 가지고 있으며 이는 거의 모든 애플리케이션에 적합해야하며 세그먼트 수는 여전히 관리하기 쉽습니다. 교두 근처에서 세분화가 매끄럽게 증가하는 모습을 보여주기 때문에 마음에 듭니다.
오일러 나선 또는 포물선
심장에서 알고리즘은 다음과 유사합니다. 포물선으로 세분. 대신 오일러 나선을 사용하는 이유는 무엇입니까?
평행 곡선 알고리즘의 특히 까다로운 경우는 입력 곡선이 곡률이 거의 일치하는 원 호일 때입니다. 오프셋 거리. 정확한 결과는 반경이 매우 작은 또 다른 원호입니다. 그러나 곡선 표현으로 베 지어를 사용하면 근사 오차로 인해 곡률이 “잔물결”이됩니다. 최악의 경우 이러한 잔물결은 교두 생성을위한 임계 곡률 값에 걸쳐 있습니다. 각 2 차 베 지어는 이러한 두 개의 교두를 생성 할 수 있습니다. 세분화가 세분화 될수록 (결과의 정확성을 높이기 위해) 더 많은 교두가 있습니다!
물론 원호는 오일러 나선은 정확하게 표현할 수 있으며 평행 곡선에도 오류가 없습니다.
요약하면 Béziers로 곡선을 근사화하면 는 해당 평행 곡선에 첨점을 추가 하고 오일러 나선으로 곡선을 근사화 할 수 있습니다. 정확도를 희생하지 않고 제거 합니다. 이 관찰은 오일러 나선이 평행 곡선 문제에 대한 “더 깨끗한”해결책이라고 주장하는 주된 이유입니다.
오일러 나선형에서 큐빅 베지 어로
이전 블로그 게시물 인 Secrets of smooth Béziers가 공개 한 바, 오일러 나선 세그먼트를 근사화하기 위해 큐빅 베 지어를 맞추는 문제를 해결했습니다. 주제에 대해 더 많은 이야기가 있지만 여기서는 간단하고 매력적인 솔루션을 보여 드리겠습니다.
큐빅 베 지어를 사용하는 그래픽 디자이너는 일반적으로 제어점에서 끝점까지의 거리가 끝점 사이의 거리의 약 1/3 일 때 부드러운 곡선이 생성된다고합니다. 이 개념의보다 정확한 개선은 각 끝점 주위에 포물선을 그리는 것입니다. 정점은 코드를 따라 1/3, 직교 방향으로 거리는 2/3입니다. 오일러 나선 근사는 단순히 원하는 접선 방향의 포물선을 따라있는 점입니다.
대칭의 경우이 솔루션은 약간의 삼각법에서 볼 수 있듯이 3 차 베 지어를 사용하여 원호를 근사화하는 표준 솔루션과 동일합니다. 덜 분명한 것은 비대칭의 경우에도 매우 양호하다는 것입니다. 특히 베 지어의 원호 길이는 실제 곡선과 매우 잘 일치합니다. 오류 스케일링은 표준 Hermite 보간을 사용하는 것의 4 승 스케일링보다 낫지 만 (일관 적으로 arclength보다 작음), 이론적으로 가능한 6 승 스케일링만큼 좋지는 않습니다 (고 정확도 기하학적 Hermite 보간). . 그러나 실제로이를 달성하려면 위에서 언급 한 간단한 포물선 규칙과 비교하여 어려운 수치 기법이 필요합니다.
오류 경계도 마찬가지입니다. 분석적 추정의 견고 함으로 다음 이미지에서 시각화 할 수 있습니다.
여기서 k0은 수평축이고 k1은 수직축입니다. 수평 축 (k1=0)은 완벽한 원호를 나타내고 수직 (k0=0)은 대칭이 홀수 인 “s”곡선입니다. 두 경우 모두 특히 낮은 오류가 있습니다. 검은 색은 제로 오류, 빨간색은 실제 오류, 청록색은 대략적인 오류를 나타냅니다 ( fit_cubic_plot 오류 경계에 대한 관련 kurbo PR의 예에서 함수와 위의 플롯에 사용 된 코드). 따라서 중간 회색은 오차 범위가 빡빡하다는 것을 의미합니다.
$ n ^ 5 $ 스케일링을 사용한이 간단한 피팅은 매력적입니다. 평가가 매우 빠르며, 대부분의 경우 정확도를 위해 편안하지만 과도한 안전 여유가없는 큐빅 베 지어를 생성합니다. 특히 근사 파이프 라인 규모의 초기 단계가 $ n ^ 4 $이기 때문에 더욱 그렇습니다.
결론
평행 곡선 문제는 까다로워서 잘 알려져 있습니다. 그러나 문제의 큰 부분은 기본 곡선 표현으로 Bézier를 선택하는 것입니다. Bézier의 평행 곡선은 분석 및 근사화가 어려운 짐승이며 예측하기 어려운 위치에서 첨점을 잡기 쉽습니다. 대조적으로, 소스 곡선의 오일러 나선형 표현은 평행 곡선에 대한 깨끗한 분석 솔루션을 사용하여 이러한 문제를 단순화합니다.
오일러 나선형 표현의 장점에 대해이 블로그 게시물은 여러 가지 새로운 결과를 제시했습니다.
- 원의 나선과 관련하여 오일러 나선 평행 곡선에 대한 매우 간단한 닫힌 형태의 Cesàro 방정식.
- 이 평행 곡선을 조각 별 오일러 나선으로 근사화하기위한 간단한 분석 오류 메트릭 .
- 오일러 나선의 기하학적 Hermite 보간을위한 매우 효율적인 알고리즘입니다.
- 전자 오일러 나선을 3 차 베지 어로 효율적이고 직접적으로 근사하며 오차 범위도 좁습니다.
오일러 나선을 더 많이 사용할수록 곡선의 단순하고 효율적이며 다루기 쉬운 표현이라는 것을 알게됩니다. 예를 들어, 호 길이 매개 변수를 사용하여 정의 되었기 때문에 역 호 길이 문제는 거의 사소합니다. 문헌을 살펴 보려면 오일러 나선으로 작업하려면 프레 넬 적분 평가와 같은 까다로운 문제에 대한 솔루션이 필요한 것처럼 보이지만 실제로는 매우 효율적인 다항식 근사가 잘 작동하여 적당히 (예측 가능한!) 증가로 임의의 높은 정밀도의 결과를 생성합니다. 세분의 수. 이 곡선 표현이 평행 곡선을 결정하는 데 특히 얼마나 적합한 지 시연했으며 다른 고전적인 2D 지오메트리 문제에 대한 적합성을 탐색 할 수 있기를 기대합니다.
kurbo PR에서 평행 곡선의 실제 구현은 첨점 처리 및 신중한 오류 경계를 포함하여 100 줄 미만의 코드입니다. 그것은 오일러 나선이 다른 곡선 표현보다 “더 깨끗한”구현을 지원한다는 주장에 대한 추가 지원을 제공한다고 생각합니다. 나는 아직 end-to-end 구현에 대한 신중한 벤치마킹을하지 않았지만, 확실히 중요한 프리미티브의 성능을 기반으로 매우 빠르기를 기대합니다. 설계 응용 프로그램에서 이러한 작업을 사용할 수 있기 때문에 원활한 상호 작용으로 정확하고 강력한 지오메트리 작업을 제공하기를 원하기 때문에 속도가 중요합니다. 이것이 제가 구현을 위해 Rust를 선택한 주된 이유입니다.
마지막으로이 블로그 게시물의 결과는 대부분 실험을 통해 결정됩니다. 테스트를 통해 검증되었습니다 (대부분의 경우 무작위). 학술 논문이라면 수학적 기법을 사용하여 엄격하게 오류 경계 및 관련 결과를 도출합니다. 재미있게 들리면 연락하여 논문 공동 작업에 대해 논의 해 봅시다.
Hacker News에 대해 토론하세요.
RSS - Posts
