베지어 클리핑

Question

두 개의 임의의 채워진 2D 개체의 교차점(새로 채워진 개체)을 계산하는 알고리즘을 찾거나 만들려고 합니다.객체는 선이나 3차 베지어를 사용하여 정의되며 구멍이 있거나 자체 교차할 수 있습니다.나는 폴리곤과 동일한 작업을 수행하는 여러 기존 알고리즘을 알고 있습니다. 여기에 나열됨.하지만 베지어를 폴리곤으로 세분화하지 않고 지원하고 싶고, 교차점이 없는 영역에서는 출력이 입력과 거의 동일한 제어점을 가져야 합니다.

이것은 일부 CSG를 ​​수행하는 대화형 프로그램을 위한 것이지만 클리핑이 실시간일 필요는 없습니다.한동안 검색했지만 좋은 시작점을 찾지 못했습니다.

Answer 1

나는 다음 출판물이 베지어 클리핑에 관한 최고의 정보라고 생각했습니다.

티.W.Sederberg, BYU, 컴퓨터 지원 기하학적 디자인 강좌 노트

곡선 교차점에 대해 설명하는 7장은 온라인에서 볼 수 있습니다.교차점을 찾는 4가지 접근 방식을 간략하게 설명하고 베지어 클리핑에 대해 자세히 설명합니다.

http://www.tsplines.com/technology/edu/CurveIntersection.pdf

Answer 2

중복될 위험이 있다는 것을 알고 있지만 동일한 문제를 조사하고 학술 논문에서 읽었지만 작동하는 솔루션을 찾지 못한 솔루션을 찾았습니다.

베지어 곡선을 다음과 같이 두 개의 이변량 3차 방정식 세트로 다시 작성할 수 있습니다.

• Δx = ax₁*t₁^3 + bx₁*t₁^2 + cx₁*t₁ + dx₁ - ax₂*t₂^3 - bx₂*t₂^2 - cx₂*t₂ - dx₁
• Δy = ay₁*t₁^3 + by₁*t₁^2 + cy₁*t₁ + dy₁ - ay₂*t₂^3 - by₂*t₂^2 - cy₂*t₂ - dy₂

분명히 곡선은 Δx = Δy = 0인 (t₁,t²) 값에 대해 교차합니다.불행하게도 2차원에서 뿌리를 찾는 것이 어렵고, 다른 작가가 말했듯이 근사적인 접근 방식은 폭발하는 경향이 있다는 사실로 인해 복잡해졌습니다.

그러나 제어점에 정수나 유리수를 사용하는 경우 다음을 사용할 수 있습니다. 그뢰브너 기지 이변량 차수 3 다항식을 (아마도 최대 차수 9 따라서 9개의 가능한 교차점) 단변량 다항식으로 다시 작성합니다.그런 다음 한 차원에서 근(예: t²)을 찾고 결과를 다시 원래 방정식 중 하나에 연결하여 다른 차원을 찾으면 됩니다.

Burchburger는 "그뢰브너 기지:시스템 이론가를 위한 짧은 소개"그 말은 나에게 매우 도움이 되었습니다.구글해 보세요.도움이 되었던 또 다른 논문은 "3차 베지어 경로 및 오프셋 곡선을 빠르고 정확하게 평탄화" x 및 y 방정식에 대한 다항식 계수를 찾는 방법을 포함하여 베지어 곡선에 대한 많은 유틸리티 방정식이 있는 TF Hain의 글입니다.

베지어 클리핑이 이 특정 방법에 도움이 될지 여부에 대해서는 의심스럽습니다. 그러나 베지어 클리핑은 교차점이 있을 수 있는 위치를 좁히는 방법이지 그것이 어디에 있는지에 대한 최종(근사적일 수도 있음) 답을 찾기 위한 방법이 아닙니다.이 방법을 사용하면 단변량 방정식을 찾는 데 많은 시간이 소요되며 해당 작업은 클리핑으로 인해 더 쉬워지지 않습니다.뿌리를 찾는 것은 비교적 사소한 일입니다.

그러나 이 방법의 장점 중 하나는 곡선을 재귀적으로 세분화하는 데 의존하지 않으며 문제가 간단한 1차원 근 찾기 문제가 된다는 것입니다. 이는 쉽지 않지만 잘 문서화되어 있습니다.가장 큰 단점은 Groebner 베이스를 계산하는 데 비용이 많이 들고 부동 소수점 다항식을 다루거나 고차 베지어 곡선을 사용하는 경우 다루기가 매우 불편해진다는 것입니다.

교차점을 찾기 위해 Haskell에서 완성된 코드를 원한다면 알려주세요.

Answer 3

나는 아주 오래 전에 이 작업을 수행하는 코드를 작성했습니다.제가 작업하고 있던 프로젝트에서는 PostScipt 경로로 생성된 조각별 베지어 경계를 사용하여 정의된 2D 개체에 대해 설명했습니다.

내가 사용한 접근 방식은 다음과 같습니다.

곡선 p, q를 베지어 제어점으로 정의합니다.교차합니까?

제어점의 경계 상자를 계산합니다.겹치지 않으면 두 곡선이 교차하지 않습니다.그렇지 않으면:

p.x(t), p.y(t), q.x(u), q.y(u)는 0 <= t,u <= 1.0의 3차 다항식입니다.거리 제곱 (p.x - q.x) ** 2 + (p.y - q.y) ** 2는 (t,u)에 대한 다항식입니다.Newton-Raphson을 사용하여 0에 대해 해결해 보세요.0 <= t,u <= 1.0 외부의 해는 모두 폐기합니다.

N-R은 수렴할 수도 있고 수렴하지 않을 수도 있습니다.곡선이 교차하지 않거나 두 곡선이 거의 평행할 때 N-R이 폭발할 수 있습니다.따라서 임의의 횟수만큼 반복한 후에도 수렴되지 않으면 N-R을 차단하십시오.이는 상당히 작은 숫자일 수 있습니다.

N-R이 해로 수렴하지 않으면 하나의 곡선(예: p)을 t = 0.5에서 두 개의 곡선 pa, pb로 분할합니다.링크된 기사에서 볼 수 있듯이 이것은 쉽습니다. 단지 중간점을 계산하는 것뿐입니다.그런 다음 교차점에 대해 (q, pa) 및 (q, pb)를 재귀적으로 테스트합니다.(다음 재귀 계층에서 q는 p가 되므로 p와 q는 재귀의 각 겹에서 교대로 분할됩니다.)

경계 상자가 겹치지 않기 때문에 대부분의 재귀 호출은 빠르게 반환됩니다.

두 곡선이 평행하고 서로 닿지 않는 이상한 경우를 처리하려면 임의의 깊이에서 재귀를 차단해야 하지만 둘 사이의 거리가 임의로 작습니다. 차이는 아마도 1ULP에 불과할 것입니다.

3차 곡선에는 교차점이 여러 개 있을 수 있으므로 교차점을 찾았다고 해서 끝난 것이 아닙니다.따라서 교차점에서 각 곡선을 분할하고 (pa, qa), (pa, qb), (pb, qa), (pb, qb) 사이에 더 많은 교차가 있는지 재귀적으로 확인해야 합니다.

Answer 4

베지어 클리핑 수행에 관한 많은 학술 연구 논문이 있습니다.

http://www.andrew.cmu.edu/user/sowen/abstracts/Se306.html

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.6669

http://www.dm.unibo.it/~casciola/html/research_rr.html

설명하신 대로 간격 방법을 권장합니다. 왜냐하면 설명대로 다각형으로 나눌 필요가 없고 보장된 결과를 얻을 수 있을 뿐만 아니라 결과 집합에 대해 임의의 정밀도를 정의할 수 있기 때문입니다.간격 렌더링에 대한 자세한 내용은 다음을 참조할 수도 있습니다. http://www.sunfishstudio.com