DTFC — 완전 원 그리기
출처: [Dev.to](https://dev.to/g33kdaddy_7e5/ dtfc-draw-the-fing-circle-5bo)
오타가 난 코드가 오히려 더 정확한 코드일 이야기
부팅 시퀀스
연도: 1983년과 1987년 사이.
철판(하드웨어): 커스텀 보드 — 모터ola 68000 (32비트. 순수한 호화. 하드웨어 팀은 1주일 동안它について 논쟁을 벌였다.) 그리고 텍사스 인스트루먼츠 TMS34010, 행성상 최초의 프로그래머블 그래픽 칩 중 하나입니다.
VRAM: 256 킬로바이트. 오타가 아닙니다.
질량 저장소: 20 메가바이트. 전체. OS 없이 순수 SCSI와 같은 인터페이스.
미션: 400dpi로 A0 아키텍처 도면을 래스터화.
RTFM과 수학을 계산해 보세요:
A0 = 841 × 1189 mm
At 400 dpi → ~13,300 × 18,700 pixels
1 bit per pixel → ~30 MBEnter fullscreen mode
Exit fullscreen mode
출력 비트맵이 디스크에 맞지 않았습니다.
그 디스크는 또한 OS, FAT, 파일시스템 드라이버, 애플리케이션, 그리고 쿼드트리 압축된 소스 그림을 포함하고 있었습니다.
모든 바이트는 수동으로 협상되었고, 모든 사이클은 감사받았습니다.
전체 스택 — OS, 파일시스템, 디스크 리프트 스케줄러, 스와프 시스템 — 은 로직 분석기와 과도한 커피를 가진 몇몇 사람들에 의해 어셈블리어나 C로 처음부터 작성되었습니다.
이 환경에서 DTFC가 필요했습니다.
교과서 솔루션 (즉, 실행되지 않는 버전)
깨끗한 접근법: 원에 점을 두고 원주로 단계별로 회전시킵니다.
표준 회전 행렬, 각도 a = 2π/N을 N 단계에 적용합니다:
| cos(a) -sin(a) | applied to | x |
| sin(a) cos(a) | | y |코드:
float x = r, y = 0;
for (int i = 0; i > n);
y = y + (x >> n);Enter fullscreen mode
Exit fullscreen mode
0번 곱셈. apenas 이동과 덧셈만.
16비트 고정소수점(8.8 포맷)에서는 3~4 사이클 per 점.
8 MHz에서 수천 개의 원형 점을 초당 생성할 수 있습니다.
플롯터는 감당하지 못했습니다.
한 번 실행해 보았습니다.
원은 완벽하게 닫혔습니다.
배포합니다.
잠깐만. 여기 버그가 있습니다. 코드를 다시 보세요. 진심으로 보세요.
그것은 임시 변수가 있는 깨끗한 버전과 동일하지 않습니다.
원위치 업데이트 오류 — 초보자가 흔히 저지르는 실수, 코드 리뷰에서 눈썹을 찌푸리게 만드는 것입니다.
그것보다 더 나쁜 점이 있습니다. 위 수학에서 보여진 근사 행렬을 보세요:
| 1 -a | det = 1×1 − (−a)×a = 1 + a²
| a 1 |행렬식 1보다 큽니다. 각 단계는 반경이 약간 확대되어야 합니다.
N번 반복 후 나선형은 외부로 흐려져야 합니다. 원은 닫히지 않아야 합니다.
그럼에도 불구하고. 나선형이 없고, 원만 닫혔습니다.
어떻게?
포스트모르템 — “버그”가 실제로 계산하는 것
깨진 코드가 실제로는 대수적으로 어떻게 동작하는지 살펴보겠습니다:
x' = x - y*a
y' = y + x'*a
= y + (x - y*a)*a
= y + x*a - y*a²암시적 변환 행렬은:
| 1 -a |
| a 1-a² |행렬식:
1×(1−a²) − (−a)×a
= 1 − a² + a²
= 1정확히 1입니다. 근사적이지 않으며, “그래픽 작업에 충분하다”는 말이 아닙니다.
정확히, 대수적으로, 증명ably 1 — 임의의 a 값에 대해서.
“오류가 있는 원위치 업데이트는” 스파이럴 드리프트를 보상하는 것 그 이상을 합니다. 완전히 보정합니다 — 근사 오류의 +a²와 원위치 재사용의 −a²가 서로 완전히 상쇄됩니다.
버그가 버그를 수정했습니다.
DTFC — 최종, 배포, 여전히 실행 중
/*
** DTFC - Draw The F***ing Circle
**
** Radius r, centered at origin.
** N steps for a full revolution.
** shift = bit precision (e.g. shift=6 means a ≈ 1/64)
**
** No sin(). No cos(). No multiply. No temp variable.
** Just shifts, adds, and one algebraically perfect "mistake".
** Determinant = 1. Circle closes. Every time.
*/
int x = r, y = 0;
for (int i = 0; i > shift); /* wrong order. keep it. */
y = y + (x >> shift); /* new x. intentional. */
}Z80에서 실행됩니다. 6809에서도 실행됩니다. TMS34010에서도 실행됩니다. 지금 바로 Arduino에서도 실행될 수 있습니다.
논리 3줄. 삼각함 없음. 곱셈 없음.
한 줄에 숨겨진 행렬식이 보입니다.
AFAIK 이 기술은 교과서에서 전혀 본 적이 없습니다.
이것은 누구도 기록하지 않았으며,我所知의 경우도 마찬가지입니다.
이것은 Benson, Schlumberger Graphics, OCE 엔지니어들의 손끝에 살았던 것이었습니다. 메모리가 제한되고, 모든 사이클에 이름이 붙은 시대에 A0 플롯터와 래스터 엔진을 만들었습니다.
한 동료 — Sun Microsystems에서 최근 실리콘으로 만들어진 세계 최초의 하드웨어 트라이앵글 래스터라이저를 테이프 아웃한 사람 — 은 책상 위에 Graphics Gems을 두고, Knuth의 성경과 함께 두었습니다.
이 기술은 그 책에 한 페이지가 필요했습니다.
그건 이루어지지 않았습니다.
이것을 그 페이지로 보세요.
멈추고 불에 타라
때로는 버그가 프로그래머보다 더 현명할 수 있습니다.
때로는 제약 자체가 알고리즘이다.
그리고 때로는 8MHz에 256k의 VRAM을 가지고, Architects가 전혀 모르는 사이에 플롯터가 A0 도면을 스풀링하는 상황에서, 누군가가 올바른 버전보다 더 정확한 것을 우연히 작성합니다.
원은 닫혔습니다. 언제나 닫혔습니다.
— 메모리에서 회수됨, 약 40년 후. 여전히 컴파일되고 작동합니다.*
부록: 부동소수점에서도 동작해야 합니다. 대수학은 타입 시스템을 신경 쓰지 않습니다.
태그: #8bit #retrocomputing #graphics #fixedpoint #TMS34010 #68000
#circledrawing #linearlgebra #determinant #GraphicsGems #accidentalgenius*