폴리곤을 브러쉬로 드래그하여 벡터 이미지 편집

Question

목표는 다각형 모양의 페인트 브러시와 같이 화면에서 마우스를 드래그하여 브러쉬와 경로의 Minkowski sum을 생성하여 간단한 벡터 이미지 편집을하는 것입니다. 새 다각형은 이전에 기존의 다른 색상의 다각형에서 빼고 동일한 색상의 기존 다각형과 병합합니다.

각 마우스 움직임을 마우스의 이전 위치에서 현재 위치까지의 선분으로 가져 와서 해당 선분의 Minkowski 합계를 계산 한 다음 Weiler–Atherton clipping algorithm을 사용하여 해당 Minkowski 합계를 포함하도록 기존 다각형을 업데이트하십시오 .

Weiler-Atherton이 모든 마우스 움직임에 대해 실행하면 UI 지연이 발생할 가능성이 높으므로 최신 단계의 마우스 움직임을 따라 잡을 수있는 다른 스레드에 배치하거나 그 대안으로 지연을 계획합니다 도면이 완성 될 때까지 모든 Weiler-Atherton 계산을 저장 한 다음 저장시 대량 작업으로 수행하십시오. 이렇게하면 매우 많은 수의 겹치는 다각형이 누적되어 UI를 렌더링하는 데 걸리는 시간이 지연 될 수 있습니다.

질문 : 위의 계획은 Inkscape 및 기타 심각한 벡터 그래픽 편집 소프트웨어가이 작업을 수행하는 방식입니까? 그것은 알고리즘의 복잡성과 계산 복잡성 모두에서 미친 계획처럼 보입니다. 전문가는 무엇을 할 것인가?

다른 옵션 : 간단한 래스터 작업을 사용하여 페인팅을 수행 한 다음 래스터를 최종 단계로 벡터 이미지로 변환합니다. 래스터에서 벡터로 변환하는 것은 Weiler-Atherton보다 덜 까다 롭지 만 최종 출력물의 품질은 떨어질 수 있지만 더 나은 옵션 일 수 있습니까?

Answer 1

사용자가 마우스 버튼과 그림을 누르고있는 동안 모든 마우스 움직임 선 세그먼트를 기억하고 동시에 브러시 * 선 Minkowski를 화면 해상도 비트 맵으로 렌더링 할 수 있습니다.

사용자가 단추를 놓을 때까지 화면을 그릴 때 비트 맵을 사용할 수 있습니다. 이 때 Minkowski 모든 라인 선분의 합집합을 계산하고 결과 모양을 도면에 추가 할 수 있습니다.

너무 많은 모양의 결합을 동시에 계산하려면 일종의 스윕 라인 알고리즘이 가장 좋습니다. 눈에 띄는 지연을 유발하지 않을 O (N log N) 또는 선형 시간으로 작업을 수행 할 수 있어야합니다.

Answer 2

IMO Weiler-Atherton의 병목 현상은 교차로를 탐지하기 때문에 무차별 대입으로 적용 할 때 O (N²) 작업이 필요합니다. 나머지 처리는 O (N) 또는 O (NI)로 제한되어야하는 정점과 교차점 사이의 링크를 재구성하는 것입니다. 여기서 NI는 교차점 수를 나타냅니다.

이 특별한 경우에는 격자 또는 경계 상자의 계층 구조를 사용하여 교차로 검색 속도를 높일 수 있습니다. (그리드는 보조 비트 맵 렌더링을 사용하기 위해 Matt의 생각과 유사합니다.)

가장자리가 실제로 없으면 실행 시간이 두렵지 않습니다.

Answer 3

전문적인 벡터 그래픽 소프트웨어처럼 원하는 경우 (브러쉬 모양이 속도 나 스타일러스 압력에 반응 할 수있는 기능 포함) 임의의 브러시 모양을 사용하는 것처럼 불행하게도 상당히 복잡 할 수 있습니다.

"안, 김, 임 - 2D 곡선 객체의 일반적인 스윕 경계"에 설명 된 방법으로 실험하고있었습니다.전문적인 드로잉 응용 프로그램에서 기대할 수있는 많은 경우, 특히 브러시 모양이 동적 일 수있는 세부 사항을 처리하는 것처럼 보입니다. 원하는 해상도의 경계 곡선을 적응 형으로 생성하십시오. 2 차원 곡선의 가변 너비 오프셋. 등

당신이 일반화 된 방법이 필요하지 않는 경우이 방법을 단순화 할 수 있습니다 보인다. 그러나 나는 그것을 여기에 참조로 추가하고 싶다.

---

PS : 나는이 질문에 대해 여기에 포함 할 비 paywalled 링크를 검색 한 후이 와서 - Looking for an efficient algorithm to find the boundary of a swept 2d shape합니다. 당신이하려고하는 것과 매우 비슷합니다. :).