빠른 폴리곤 렌더링 알고리즘을 찾고 있습니다

Question

마이크로 칩 dsPIC33FJ128GP802로 작업하고 있습니다. DSP 기반의 소형 마이크로 컨트롤러로 초당 4 천만 명령을 처리 할 필요가 없습니다. 볼록 (즉, 단순) 다각형을 렌더링하는 방법을 찾고 있습니다. 2 차원 도형, 정수 연산 및 픽셀 (즉, 픽셀 당 1 비트)을 설정하거나 지우고 있습니다. 이미 88 세로 16 행의 픽셀을 긋는 빠른 수평선과 수직선을 그리는 루틴을 가지고 있으므로 스캔 라인 알고리즘을 사용한다.

그러나 내가 찾은 모든 알고리즘은 나누기 (이 프로세서에서 18 사이클 소요) 및 부동 소수점 연산 (소프트웨어에서 에뮬레이트되므로 매우 느리며 많은 ROM을 차지합니다), 또는 내가 많은 양의 메모리를 가지고 있다고 가정하십시오. 난 단지 2K 왼쪽, ~ 14K 내 16K의 그래픽 RAM에 사용됩니다. 누구나 어셈블리에서 구현할 수있는 간단한 C 또는 의사 코드 구현으로 나를 가리킬 수있는 좋은 내장 된 머신 알고리즘을 아는 사람이 있습니까? 가급적 그물에, 나는 많은 프로그래밍 서적이있는 좋은 서점 근처에 살지 않는다.

감사합니다. :)

EDIT : 설명이 폴리곤 필링 알고리즘입니다. Bresenham의 선 그리기 알고리즘을 사용하여 폴리곤 개요 알고리즘을 구현할 수 있습니다 (Marc B가 제안함).

EDIT # 2 : 저는 파이썬에서 기본 알고리즘을 가지고 있다는 것을 모두에게 알리고 싶습니다. 여기 코드에 대한 링크가 있습니다. 공개 도메인 코드.

http://dl.dropbox.com/u/1134084/bresenham_demos.py

Answer 1

어떻게 라인 알고리즘 Bresenham's 어떻습니까? 몇 가지 설정을 한 후에는 순수한 정수 연산이며 폴리곤 모서리를 따라 시작점을 반복하여 폴리곤을 그릴 수 있습니다.

의견 후속 :

내가 ASCII이 그리는하려고합니다,하지만 아마 CRUD처럼 보일 것이다. Bresenham 's는 시작 가장자리를 선택하고 그 지점과 평행하게 bresenham 선을 캔버스를 가로 질러 반복적으로 이동하여 채워진 다각형을 그리는 데 사용할 수 있습니다.

의가이 같은 몇 가지 포인트를 가지고 있다고 가정 해 봅시다 :

*(1) 
         *(3) 

    *(2)   
       *(4) 

당신이 원하는 경우 가장 왼쪽의 시작 지점 (1)을 선택하고 결정할 수 있도록 다음은 왼쪽에서 오른쪽으로 정렬 우선 순위에 번호가 매겨집니다 수직으로 (시작 1,2) 또는 수평으로 (1,3) 이동하십시오. 아마도 DSP가 디스플레이를 어떻게 사용하는지에 달려 있지만 수직적으로 살펴 보겠습니다.

그래서 ... 1-2 선을 시작 bresenham 선으로 사용합니다. 선 1-3 및 2-4를 시작/끝점으로 사용하여 채우기 선의 시작점을 계산합니다. 각각에 대해 bresenham 계산을 시작하고 두 점 사이에 다른 Bresenham을 그립니다. 비슷한 :

1.1 -> 2.1, then 1.2 -> 2.2, then 1.3 -> 2.3 

등 ... 당신이 그 라인 중 하나의 끝에 도달 할 때까지. 이 경우 낮은 시작점이 (4)에 도달했을 때입니다. 이 시점에서 시작점을 모두 사용하여 포인트 3에 도달 할 때까지 4, 3 라인 반복을 시작하면 완료됩니다.

*------- 
\\\\\\\\    * 
    \\\\\\\\ 
    *-----\\   
     ------- * 

여기서 대시는 1-3 및 2-4에 따라 계산 한 시작점이며 슬래시는 채우기 선입니다.

물론 이것은 점이 올바르게 정렬되어 있고 볼록 다각형이있는 경우에만 작동합니다.오목면이라면 채우기 선이 경계를 넘지 않도록 조심해야 할 것입니다. 또는 일부 사전 가공을하고 원래의 폴리를 두 개 이상의 볼록한 것들로 세분해야합니다.

Answer 2

토마스, Bresenham 선 그리기 알고리즘을 사용할 수있는 경우이를 토대로 다음 개선 작업을 수행하십시오. 모든 정점을 가로 지르는 수평선을 사용하여 폴리곤을 하위 폴리곤으로 나눕니다. 그런 다음 Bresenham을 사용하여 각 하위 폴리선의 2 개의 왼쪽과 오른쪽을 추적하기 시작합니다. 이 방법으로 다각형의 각 스캔 라인에 대해 2 개의 종점을 갖게됩니다.

Answer 3

두 부분으로 문제를 해결하는 것이 더 쉬울 수 있습니다. 우선, 삼각형을 그리고 채우는 알고리즘을 찾고 쓰십시오. 둘째, 임의의 다각형을 삼각형으로 분할하는 알고리즘을 작성하십시오 (다른 꼭지점의 조합 사용).

삼각형을 그리거나 채우려면 Bresenham의 라인 알고리즘을 사용하여 점 0과 1 사이, 1과 2 사이의 선을 동시에 그립니다. 각 입력 점 x에 대해 픽셀이 같거나 같은 경우 y 두 줄로 생성 된 포인트 하나의 엔드 포인트에 도달하면 아직 완료되지 않은 측면과 아직 사용되지 않은 측면을 사용하여 계속하십시오.

편집 : 이 삼각형으로 볼록 다각형을 깰 위해 포인트를 준비하고 P1, P2, ... PN를 호출합니다. P1을 "루트"지점으로 놓고 그 지점과 인접한 점의 조합을 사용하여 삼각형을 만듭니다. 예를 들어, 오각형은 세 개의 삼각형 (P1-P2-P3, P1-P3-P4 및 P1-P4-P5)을 생성합니다. 일반적으로 N면을 가진 볼록 다각형은 N-2 삼각형으로 분해됩니다.

Answer 4

다각형 채우기/래스터/기타에 대해 Dr Dobbs의 Michael Abrash's articles을보고 싶을 수 있습니다. 고정 소수점 수학을 사용합니다

Answer 5

삼각형을 스캔 라인으로 렌더링하기 쉽기 때문에 다각형을 삼각형 컬렉션으로 변환하여 렌더링합니다. 그럼에도 불구하고 몇 가지 세부 사항이 있습니다.

본질적으로 draw-triangle 서브 절차 원료 삼각형 부여되며 진행 :

1. 은 (세 꼭지점 두 중첩) 축퇴 삼각형 거부.
2. Y에서 꼭지점을 정렬합니다 (정렬 논리를 하드 코딩 할 수있는 단 세 개만 있기 때문에).
3. 이제이 시점에서 세 가지 종류의 삼각형이 있다는 것을 알아야합니다. 하나는 평평한 상단, 하나는 평평한 바닥, 다른 하나는 "일반적인"삼각형입니다. 기본적으로 하나의 평면 유형으로 분할하여 일반 삼각형을 처리하려고합니다. 경사가 바뀌 었는지 감지하기 위해 모든 스캔 라인을 if 테스트하고 싶지 않기 때문입니다.
4. 평평한 삼각형을 렌더링하려면 두 개의 Bresenham 알고리즘을 병렬로 실행하여 가장자리를 구성하는 픽셀을 반복하고 각 수평 주사선의 끝점으로 사용하는 점을 사용합니다.