Learn Zig Series (#158) - Circle and Ellipse Rasterization
Published on HivePostify by @scipio · Thu Sep 03 2026
Learn Zig Series (#158) - Circle and Ellipse Rasterization
What will I learn? - Why a circle fights the pixel grid even harder than a line does, and why the obvious y = sqrt(rr - xx) approach leaves ugly gaps near the sides; - The midpoint circle algorithm -- Bresenham's integer decision-variable idea pointed at a rounder target, plotting one octant and mirroring it eight ways with nothing but add and compare; - How to turn a circle outline into a filled disc with horizontal spans, and why that is almost free once you have the symmetry; - The midpoint ellipse algorithm: two regions, two decision variables, and why the axis of steepest descent changes halfway round; - How Zig's i64 coordinate API and clipping-inside-setPixel keep every one of these routines safe no matter how far off-canvas the shape runs; - How an anytype plot context lets the same circle generator fill pixels, count them, or measure a bounding box with no screen at all; - How to test a curve with no display, and how C, Rust and Go draw the exact same integer circle.
Requirements - A working modern computer running macOS, Windows or Ubuntu; - An installed Zig 0.14+ distribution (download from ziglang.org) -- the code here is written and tested against Zig 0.16; - The Framebuffer, Rgba pixel and the signed-coordinate setPixel/getPixel from episode 156, plus the drawLine we built in episode 157 -- we lean on both today; - Signed integers, control flow and the anytype comptime-duck-typing trick we have used since episode 13; - The ambition to learn Zig programming.
Difficulty - Advanced
Curriculum (of the Learn Zig Series): - [Zig Programming Tutorial - ep001 - Intro](https://hive.blog/programming/@scipio/zig-programming-tutoroial-ep001-intro) - [Learn Zig Series (#2) - Hello Zig, Variables and Types](https://hive.blog/hive-196387/@scipio/learn-zig-series-2-hello-zig-variables-and-types) - [Learn Zig Series (#3) - Functions and Control Flow](https://hive.blog/hive-196387/@scipio/learn-zig-series-3-functions-and-control-flow) - [Learn Zig Series (#4) - Error Handling (Zig's Best Feature)](https://hive.blog/hive-196387/@scipio/learn-zig-series-4-error-handling-zigs-best-feature) - [Learn Zig Series (#5) - Arrays, Slices, and Strings](https://hive.blog/hive-196387/@scipio/learn-zig-series-5-arrays-slices-and-strings) - [Learn Zig Series (#6) - Structs, Enums, and Tagged Unions](https://hive.blog/hive-196387/@scipio/learn-zig-series-6-structs-enums-and-tagged-unions) - [Learn Zig Series (#7) - Memory Management and Allocators](https://hive.blog/hive-196387/@scipio/learn-zig-series-7-memory-management-and-allocators) - [Learn Zig Series (#8) - Pointers and Memory Layout](https://hive.blog/hive-196387/@scipio/learn-zig-series-8-pointers-and-memory-layout) - [Learn Zig Series (#9) - Comptime (Zig's Superpower)](https://hive.blog/hive-196387/@scipio/learn-zig-series-9-comptime-zigs-superpower) - [Learn Zig Series (#10) - Project Structure, Modules, and File I/O](https://hive.blog/hive-196387/@scipio/learn-zig-series-10-project-structure-modules-and-file-io) - [Learn Zig Series (#11) - Mini Project: Building a Step Sequencer](https://hive.blog/hive-196387/@scipio/learn-zig-series-11-mini-project-building-a-step-sequencer) - [Learn Zig Series (#12) - Testing and Test-Driven Development](https://hive.blog/hive-196387/@scipio/learn-zig-series-12-testing-and-test-driven-development) - [Learn Zig Series (#13) - Interfaces via Type Erasure](https://hive.blog/hive-196387/@scipio/learn-zig-series-13-interfaces-via-type-erasure) - [Learn Zig Series (#14) - Generics with Comptime Parameters](https://hive.blog/hive-196387/@scipio/learn-zig-series-14-generics-with-comptime-parameters) - [Learn Zig Series (#15) - The Build System (build.zig)](https://hive.blog/hive-196387/@scipio/learn-zig-series-15-the-build-system-buildzig) - [Learn Zig Series (#16) - Sentinel-Terminated Types and C Strings](https://hive.blog/hive-196387/@scipio/learn-zig-series-16-sentinel-terminated-types-and-c-strings) - [Learn Zig Series (#17) - Packed Structs and Bit Manipulation](https://hive.blog/hive-196387/@scipio/learn-zig-series-17-packed-structs-and-bit-manipulation) - [Learn Zig Series (#18b) - Addendum: Async Returns in Zig 0.16](https://hive.blog/hive-196387/@scipio/learn-zig-series-18b-addendum-async-returns-in-zig-016) - [Learn Zig Series (#19) - SIMD with @Vector](https://hive.blog/hive-196387/@scipio/learn-zig-series-19-simd-with-vector) - [Learn Zig Series (#20) - Working with JSON](https://hive.blog/hive-196387/@scipio/learn-zig-series-20-working-with-json) - [Learn Zig Series (#21) - Networking and TCP Sockets](https://hive.blog/hive-196387/@scipio/learn-zig-series-21-networking-and-tcp-sockets) - [Learn Zig Series (#22) - Hash Maps and Data Structures](https://hive.blog/hive-196387/@scipio/learn-zig-series-22-hash-maps-and-data-structures) - [Learn Zig Series (#23) - Iterators and Lazy Evaluation](https://hive.blog/hive-196387/@scipio/learn-zig-series-23-iterators-and-lazy-evaluation) - [Learn Zig Series (#24) - Logging, Formatting, and Debug Output](https://hive.blog/hive-196387/@scipio/learn-zig-series-24-logging-formatting-and-debug-output) - [Learn Zig Series (#25) - Mini Project: HTTP Status Checker](https://hive.blog/hive-196387/@scipio/learn-zig-series-25-mini-project-http-status-checker) - [Learn Zig Series (#26) - Writing a Custom Allocator](https://hive.blog/hive-196387/@scipio/learn-zig-series-26-writing-a-custom-allocator) - [Learn Zig Series (#27) - C Interop: Calling C from Zig](https://hive.blog/hive-196387/@scipio/learn-zig-series-27-c-interop-calling-c-from-zig) - [Learn Zig Series (#28) - C Interop: Exposing Zig to C](https://hive.blog/hive-196387/@scipio/learn-zig-series-28-c-interop-exposing-zig-to-c) - [Learn Zig Series (#29) - Inline Assembly and Low-Level Control](https://hive.blog/hive-196387/@scipio/learn-zig-series-29-inline-assembly-and-low-level-control) - [Learn Zig Series (#30) - Thread Safety and Atomics](https://hive.blog/hive-196387/@scipio/learn-zig-series-30-thread-safety-and-atomics) - [Learn Zig Series (#31) - Memory-Mapped I/O and Files](https://hive.blog/hive-196387/@scipio/learn-zig-series-31-memory-mapped-io-and-files) - [Learn Zig Series (#32) - Compile-Time Reflection with @typeInfo](https://hive.blog/hive-196387/@scipio/learn-zig-series-32-compile-time-reflection-with-typeinfo) - [Learn Zig Series (#33) - Building a State Machine with Tagged Unions](https://hive.blog/hive-196387/@scipio/learn-zig-series-33-building-a-state-machine-with-tagged-unions) - [Learn Zig Series (#34) - Performance Profiling and Optimization](https://hive.blog/hive-196387/@scipio/learn-zig-series-34-performance-profiling-and-optimization) - [Learn Zig Series (#35) - Cross-Compilation and Target Triples](https://hive.blog/hive-196387/@scipio/learn-zig-series-35-cross-compilation-and-target-triples) - [Learn Zig Series (#36) - Mini Project: CLI Task Runner](https://hive.blog/hive-196387/@scipio/learn-zig-series-36-mini-project-cli-task-runner) - [Learn Zig Series (#37) - Markdown to HTML: Tokenizer and Lexer](https://hive.blog/hive-196387/@scipio/learn-zig-series-37-markdown-to-html-tokenizer-and-lexer) - [Learn Zig Series (#38) - Markdown to HTML: Parser and AST](https://hive.blog/hive-196387/@scipio/learn-zig-series-38-markdown-to-html-parser-and-ast) - [Learn Zig Series (#39) - Markdown to HTML: Renderer and CLI](https://hive.blog/hive-196387/@scipio/learn-zig-series-39-markdown-to-html-renderer-and-cli) - [Learn Zig Series (#40) - Key-Value Store: In-Memory Store](https://hive.blog/hive-196387/@scipio/learn-zig-series-40-key-value-store-in-memory-store) - [Learn Zig Series (#41) - Key-Value Store: Write-Ahead Log](https://hive.blog/hive-196387/@scipio/learn-zig-series-41-key-value-store-write-ahead-log) - [Learn Zig Series (#42) - Key-Value Store: TCP Server](https://hive.blog/hive-196387/@scipio/learn-zig-series-42-key-value-store-tcp-server) - [Learn Zig Series (#43) - Key-Value Store: Client Library and Benchmarks](https://hive.blog/hive-196387/@scipio/learn-zig-series-43-key-value-store-client-library-and-benchmarks) - [Learn Zig Series (#44) - Image Tool: Reading and Writing PPM/BMP](https://hive.blog/hive-196387/@scipio/learn-zig-series-44-image-tool-reading-and-writing-ppmbmp) - [Learn Zig Series (#45) - Image Tool: Pixel Operations](https://hive.blog/hive-196387/@scipio/learn-zig-series-45-image-tool-pixel-operations) - [Learn Zig Series (#46) - Image Tool: CLI Pipeline](https://hive.blog/hive-196387/@scipio/learn-zig-series-46-image-tool-cli-pipeline) - [Learn Zig Series (#47) - Build a Shell: Parsing Commands](https://hive.blog/hive-196387/@scipio/learn-zig-series-47-build-a-shell-parsing-commands) - [Learn Zig Series (#48) - Build a Shell: Process Spawning](https://hive.blog/hive-196387/@scipio/learn-zig-series-48-build-a-shell-process-spawning) - [Learn Zig Series (#49) - Build a Shell: Built-in Commands](https://hive.blog/hive-196387/@scipio/learn-zig-series-49-build-a-shell-built-in-commands) - [Learn Zig Series (#50) - Build a Shell: Job Control and Signals](https://hive.blog/hive-196387/@scipio/learn-zig-series-50-build-a-shell-job-control-and-signals) - [Learn Zig Series (#51) - HTTP Server: Accept Loop and Parsing](https://hive.blog/hive-196387/@scipio/learn-zig-series-51-http-server-accept-loop-and-parsing) - [Learn Zig Series (#52) - HTTP Server: Router and Responses](https://hive.blog/hive-196387/@scipio/learn-zig-series-52-http-server-router-and-responses) - [Learn Zig Series (#53) - HTTP Server: Static Files and MIME](https://hive.blog/hive-196387/@scipio/learn-zig-series-53-http-server-static-files-and-mime) - [Learn Zig Series (#54) - HTTP Server: Middleware and Logging](https://hive.blog/hive-196387/@scipio/learn-zig-series-54-http-server-middleware-and-logging) - [Learn Zig Series (#55) - ECS Game Engine: Architecture](https://hive.blog/hive-196387/@scipio/learn-zig-series-55-ecs-game-engine-architecture) - [Learn Zig Series (#56) - ECS Game Engine: Component Storage](https://hive.blog/hive-196387/@scipio/learn-zig-series-56-ecs-game-engine-component-storage) - [Learn Zig Series (#57) - ECS Game Engine: Systems and Queries](https://hive.blog/hive-196387/@scipio/learn-zig-series-57-ecs-game-engine-systems-and-queries) - [Learn Zig Series (#58) - ECS Game Engine: Terminal Rendering](https://hive.blog/hive-196387/@scipio/learn-zig-series-58-ecs-game-engine-terminal-rendering) - [Learn Zig Series (#59) - Assembler: Instruction Encoding](https://hive.blog/hive-196387/@scipio/learn-zig-series-59-assembler-instruction-encoding) - [Learn Zig Series (#60) - Assembler: Two-Pass Assembly](https://hive.blog/hive-196387/@scipio/learn-zig-series-60-assembler-two-pass-assembly) - [Learn Zig Series (#61) - Assembler: Disassembler and Binary Inspector](https://hive.blog/hive-196387/@scipio/learn-zig-series-61-assembler-disassembler-and-binary-inspector) - [Learn Zig Series (#62) - File Systems: Reading Directories and Metadata](https://hive.blog/hive-196387/@scipio/learn-zig-series-62-file-systems-reading-directories-and-metadata) - [Learn Zig Series (#63) - File Watching: Detecting Changes](https://hive.blog/hive-196387/@scipio/learn-zig-series-63-file-watching-detecting-changes) - [Learn Zig Series (#64) - Process Management: Fork, Exec, Wait](https://hive.blog/hive-196387/@scipio/learn-zig-series-64-process-management-fork-exec-wait) - [Learn Zig Series (#65) - Pipes and Inter-Process Communication](https://hive.blog/hive-196387/@scipio/learn-zig-series-65-pipes-and-inter-process-communication) - [Learn Zig Series (#66) - Shared Memory and Semaphores](https://hive.blog/hive-196387/@scipio/learn-zig-series-66-shared-memory-and-semaphores) - [Learn Zig Series (#67) - Signal Handling Deep Dive](https://hive.blog/hive-196387/@scipio/learn-zig-series-67-signal-handling-deep-dive) - [Learn Zig Series (#68) - Unix Domain Sockets](https://hive.blog/hive-196387/@scipio/learn-zig-series-68-unix-domain-sockets) - [Learn Zig Series (#69) - Daemonization: Background Services](https://hive.blog/hive-196387/@scipio/learn-zig-series-69-daemonization-background-services) - [Learn Zig Series (#70) - Timers and Scheduling](https://hive.blog/hive-196387/@scipio/learn-zig-series-70-timers-and-scheduling) - [Learn Zig Series (#71) - Resource Limits and Capabilities](https://hive.blog/hive-196387/@scipio/learn-zig-series-71-resource-limits-and-capabilities) - [Learn Zig Series (#72) - System Call Wrappers](https://hive.blog/hive-196387/@scipio/learn-zig-series-72-system-call-wrappers) - [Learn Zig Series (#73) - seccomp and Sandboxing](https://hive.blog/hive-196387/@scipio/learn-zig-series-73-seccomp-and-sandboxing) - [Learn Zig Series (#74) - ptrace: Process Tracing](https://hive.blog/hive-196387/@scipio/learn-zig-series-74-ptrace-process-tracing) - [Learn Zig Series (#75) - Reading Kernel State from /proc and /sys](https://hive.blog/hive-196387/@scipio/learn-zig-series-75-reading-kernel-state-from-proc-and-sys) - [Learn Zig Series (#76) - Mini Project: Process Monitor](https://hive.blog/hive-196387/@scipio/learn-zig-series-76-mini-project-process-monitor) - [Learn Zig Series (#77) - Mini Project: File Sync Tool - Part 1](https://hive.blog/hive-196387/@scipio/learn-zig-series-77-mini-project-file-sync-tool-part-1) - [Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer](https://hive.blog/hive-196387/@scipio/learn-zig-series-78-mini-project-file-sync-tool-part-2-delta-transfer) - [Learn Zig Series (#79) - Mini Project: File Sync Tool - Part 3: Network Protocol](https://hive.blog/hive-196387/@scipio/learn-zig-series-79-mini-project-file-sync-tool-part-3-network-protocol) - [Learn Zig Series (#80) - Mini Project: File Sync Tool - Part 4: Polish](https://hive.blog/hive-196387/@scipio/learn-zig-series-80-mini-project-file-sync-tool-part-4-polish) - [Learn Zig Series (#81) - UDP Sockets and Datagrams](https://hive.blog/hive-196387/@scipio/learn-zig-series-81-udp-sockets-and-datagrams) - [Learn Zig Series (#82) - DNS Resolver from Scratch](https://hive.blog/hive-196387/@scipio/learn-zig-series-82-dns-resolver-from-scratch) - [Learn Zig Series (#83) - DNS Server Implementation](https://hive.blog/hive-196387/@scipio/learn-zig-series-83-dns-server-implementation) - [Learn Zig Series (#84) - HTTP/1.1 Deep Dive](https://hive.blog/hive-196387/@scipio/learn-zig-series-84-http11-deep-dive) - [Learn Zig Series (#85) - HTTP/2 Frames and Streams](https://hive.blog/hive-196387/@scipio/learn-zig-series-85-http2-frames-and-streams) - [Learn Zig Series (#86) - TLS via C Interop](https://hive.blog/hive-196387/@scipio/learn-zig-series-86-tls-via-c-interop) - [Learn Zig Series (#87) - WebSocket Protocol](https://hive.blog/hive-196387/@scipio/learn-zig-series-87-websocket-protocol) - [Learn Zig Series (#88) - WebSocket Server](https://hive.blog/hive-196387/@scipio/learn-zig-series-88-websocket-server) - [Learn Zig Series (#89) - MQTT Messaging Protocol](https://hive.blog/hive-196387/@scipio/learn-zig-series-89-mqtt-messaging-protocol) - [Learn Zig Series (#90) - Protocol Buffers Serialization](https://hive.blog/hive-196387/@scipio/learn-zig-series-90-protocol-buffers-serialization) - [Learn Zig Series (#91) - MessagePack Format](https://hive.blog/hive-196387/@scipio/learn-zig-series-91-messagepack-format) - [Learn Zig Series (#92) - gRPC Service in Zig](https://hive.blog/hive-196387/@scipio/learn-zig-series-92-grpc-service-in-zig) - [Learn Zig Series (#93) - SOCKS5 Proxy](https://hive.blog/hive-196387/@scipio/learn-zig-series-93-socks5-proxy) - [Learn Zig Series (#94) - NAT Traversal and Hole Punching](https://hive.blog/hive-196387/@scipio/learn-zig-series-94-nat-traversal-and-hole-punching) - [Learn Zig Series (#95) - Mini Project: Chat Server - Protocol Design](https://hive.blog/hive-196387/@scipio/learn-zig-series-95-mini-project-chat-server-protocol-design) - [Learn Zig Series (#96) - Mini Project: Chat Server - Server Core](https://hive.blog/hive-196387/@scipio/learn-zig-series-96-mini-project-chat-server-server-core) - [Learn Zig Series (#97) - Mini Project: Chat Server - Client TUI](https://hive.blog/hive-196387/@scipio/learn-zig-series-97-mini-project-chat-server-client-tui) - [Learn Zig Series (#98) - Mini Project: Chat Server - Rooms and History](https://hive.blog/hive-196387/@scipio/learn-zig-series-98-mini-project-chat-server-rooms-and-history) - [Learn Zig Series (#99) - Mini Project: DNS-over-HTTPS Proxy](https://hive.blog/hive-196387/@scipio/learn-zig-series-99-mini-project-dns-over-https-proxy) - [Learn Zig Series (#100) - Mini Project: Port Scanner](https://hive.blog/hive-196387/@scipio/learn-zig-series-100-mini-project-port-scanner) - [Learn Zig Series (#101) - Mini Project: HTTP Load Tester - Part 1](https://hive.blog/hive-196387/@scipio/learn-zig-series-101-mini-project-http-load-tester-part-1) - [Learn Zig Series (#102) - Mini Project: HTTP Load Tester - Part 2](https://hive.blog/hive-196387/@scipio/learn-zig-series-102-mini-project-http-load-tester-part-2) - [Learn Zig Series (#103) - Mini Project: Reverse Proxy - Routing](https://hive.blog/hive-196387/@scipio/learn-zig-series-103-mini-project-reverse-proxy-routing) - [Learn Zig Series (#104) - Mini Project: Reverse Proxy - Load Balancing](https://hive.blog/hive-196387/@scipio/learn-zig-series-104-mini-project-reverse-proxy-load-balancing) - [Learn Zig Series (#105) - Mini Project: Reverse Proxy - Health Checks](https://hive.blog/hive-196387/@scipio/learn-zig-series-105-mini-project-reverse-proxy-health-checks) - [Learn Zig Series (#106) - Linked Lists: Singly and Doubly](https://hive.blog/hive-196387/@scipio/learn-zig-series-106-linked-lists-singly-and-doubly) - [Learn Zig Series (#107) - Skip Lists](https://hive.blog/hive-196387/@scipio/learn-zig-series-107-skip-lists) - [Learn Zig Series (#108) - B-Trees](https://hive.blog/hive-196387/@scipio/learn-zig-series-108-b-trees) - [Learn Zig Series (#109) - Red-Black Trees](https://hive.blog/hive-196387/@scipio/learn-zig-series-109-red-black-trees) - [Learn Zig Series (#110) - Tries: Prefix Trees](https://hive.blog/hive-196387/@scipio/learn-zig-series-110-tries-prefix-trees) - [Learn Zig Series (#111) - Bloom Filters](https://hive.blog/hive-196387/@scipio/learn-zig-series-111-bloom-filters) - [Learn Zig Series (#112) - Cuckoo Filters](https://hive.blog/hive-196387/@scipio/learn-zig-series-112-cuckoo-filters) - [Learn Zig Series (#113) - Ring Buffers: Lock-Free](https://hive.blog/hive-196387/@scipio/learn-zig-series-113-ring-buffers-lock-free) - [Learn Zig Series (#114) - Memory Pools](https://hive.blog/hive-196387/@scipio/learn-zig-series-114-memory-pools) - [Learn Zig Series (#115) - Slab Allocators](https://hive.blog/hive-196387/@scipio/learn-zig-series-115-slab-allocators) - [Learn Zig Series (#116) - Sorting Algorithms in Zig](https://hive.blog/hive-196387/@scipio/learn-zig-series-116-sorting-algorithms-in-zig) - [Learn Zig Series (#117) - Binary Search Variations](https://hive.blog/hive-196387/@scipio/learn-zig-series-117-binary-search-variations) - [Learn Zig Series (#118) - Graph Representation](https://hive.blog/hive-196387/@scipio/learn-zig-series-118-graph-representation) - [Learn Zig Series (#119) - BFS and DFS](https://hive.blog/hive-196387/@scipio/learn-zig-series-119-bfs-and-dfs) - [Learn Zig Series (#120) - Dijkstra and A](https://hive.blog/hive-196387/@scipio/learn-zig-series-120-dijkstra-and-a) - [Learn Zig Series (#121) - Topological Sort](https://hive.blog/hive-196387/@scipio/learn-zig-series-121-topological-sort) - [Learn Zig Series (#122) - Union-Find](https://hive.blog/hive-196387/@scipio/learn-zig-series-122-union-find) - [Learn Zig Series (#123) - LRU Cache](https://hive.blog/hive-196387/@scipio/learn-zig-series-123-lru-cache) - [Learn Zig Series (#124) - Consistent Hashing](https://hive.blog/hive-196387/@scipio/learn-zig-series-124-consistent-hashing) - [Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index](https://hive.blog/hive-196387/@scipio/learn-zig-series-125-mini-project-search-engine-inverted-index) - [Learn Zig Series (#126) - Mini Project: Search Engine - TF-IDF](https://hive.blog/hive-196387/@scipio/learn-zig-series-126-mini-project-search-engine-tf-idf) - [Learn Zig Series (#127) - Mini Project: Search Engine - Query Parser](https://hive.blog/hive-196387/@scipio/learn-zig-series-127-mini-project-search-engine-query-parser) - [Learn Zig Series (#128) - Mini Project: Database Engine - Page Storage](https://hive.blog/hive-196387/@scipio/learn-zig-series-128-mini-project-database-engine-page-storage) - [Learn Zig Series (#129) - Mini Project: Database Engine - B-Tree Index](https://hive.blog/hive-196387/@scipio/learn-zig-series-129-mini-project-database-engine-b-tree-index) - [Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser](https://hive.blog/hive-196387/@scipio/learn-zig-series-130-mini-project-database-engine-sql-parser) - [Learn Zig Series (#131) - Lexing a Simple Language](https://hive.blog/hive-196387/@scipio/learn-zig-series-131-lexing-a-simple-language) - [Learn Zig Series (#132) - Recursive Descent Parsing](https://hive.blog/hive-196387/@scipio/learn-zig-series-132-recursive-descent-parsing) - [Learn Zig Series (#133) - AST Design and Traversal](https://hive.blog/hive-196387/@scipio/learn-zig-series-133-ast-design-and-traversal) - [Learn Zig Series (#134) - Type Checking](https://hive.blog/hive-196387/@scipio/learn-zig-series-134-type-checking) - [Learn Zig Series (#135) - Bytecode Design](https://hive.blog/hive-196387/@scipio/learn-zig-series-135-bytecode-design) - [Learn Zig Series (#136) - Stack-Based Virtual Machine](https://hive.blog/hive-196387/@scipio/learn-zig-series-136-stack-based-virtual-machine) - [Learn Zig Series (#137) - Closures and Upvalues](https://hive.blog/hive-196387/@scipio/learn-zig-series-137-closures-and-upvalues) - [Learn Zig Series (#138) - Garbage Collection: Mark and Sweep](https://hive.blog/hive-196387/@scipio/learn-zig-series-138-garbage-collection-mark-and-sweep) - [Learn Zig Series (#139) - Garbage Collection: Generational](https://hive.blog/hive-196387/@scipio/learn-zig-series-139-garbage-collection-generational) - [Learn Zig Series (#140) - JIT Compilation Basics](https://hive.blog/hive-196387/@scipio/learn-zig-series-140-jit-compilation-basics) - [Learn Zig Series (#141) - Regex: Thompson NFA](https://hive.blog/hive-196387/@scipio/learn-zig-series-141-regex-thompson-nfa) - [Learn Zig Series (#142) - Regex: NFA to DFA](https://hive.blog/hive-196387/@scipio/learn-zig-series-142-regex-nfa-to-dfa) - [Learn Zig Series (#143) - Regex: Matching Engine](https://hive.blog/hive-196387/@scipio/learn-zig-series-143-regex-matching-engine) - [Learn Zig Series (#144) - Code Generation: AST to Machine Code](https://hive.blog/hive-196387/@scipio/learn-zig-series-144-code-generation-ast-to-machine-code) - [Learn Zig Series (#145) - Register Allocation](https://hive.blog/hive-196387/@scipio/learn-zig-series-145-register-allocation) - [Learn Zig Series (#146) - Mini Project: Calculator - Lexer/Parser](https://hive.blog/hive-196387/@scipio/learn-zig-series-146-mini-project-calculator-lexerparser) - [Learn Zig Series (#147) - Mini Project: Calculator - Interpreter](https://hive.blog/hive-196387/@scipio/learn-zig-series-147-mini-project-calculator-interpreter) - [Learn Zig Series (#148) - Mini Project: Calculator - Bytecode Compiler](https://hive.blog/hive-196387/@scipio/learn-zig-series-148-mini-project-calculator-bytecode-compiler) - [Learn Zig Series (#149) - Mini Project: Calculator - VM with Debugger](https://hive.blog/hive-196387/@scipio/learn-zig-series-149-mini-project-calculator-vm-with-debugger) - [Learn Zig Series (#150) - Mini Project: Lisp - Reader](https://hive.blog/hive-196387/@scipio/learn-zig-series-150-mini-project-lisp-reader) - [Learn Zig Series (#151) - Mini Project: Lisp - Evaluator](https://hive.blog/hive-196387/@scipio/learn-zig-series-151-mini-project-lisp-evaluator) - [Learn Zig Series (#152) - Mini Project: Lisp - Special Forms and Macros](https://hive.blog/hive-196387/@scipio/learn-zig-series-152-mini-project-lisp-special-forms-and-macros) - [Learn Zig Series (#153) - Mini Project: Lisp - Standard Library](https://hive.blog/hive-196387/@scipio/learn-zig-series-153-mini-project-lisp-standard-library) - [Learn Zig Series (#154) - Mini Project: Regex Engine - NFA](https://hive.blog/hive-196387/@scipio/learn-zig-series-154-mini-project-regex-engine-nfa) - [Learn Zig Series (#155) - Mini Project: Regex Engine - Matching](https://hive.blog/hive-196387/@scipio/learn-zig-series-155-mini-project-regex-engine-matching) - [Learn Zig Series (#156) - Framebuffer Basics](https://hive.blog/hive-196387/@scipio/learn-zig-series-156-framebuffer-basics) - [Learn Zig Series (#157) - Line Drawing: Bresenham](https://hive.blog/hive-196387/@scipio/learn-zig-series-157-line-drawing-bresenham) - [Learn Zig Series (#158) - Circle and Ellipse Rasterization](https://hive.blog/hive-196387/@scipio/learn-zig-series-158-circle-and-ellipse-rasterization) (this post)
Learn Zig Series (#158) - Circle and Ellipse Rasterization
Last episode we tamed the straight line -- Bresenham's integer error term, no floats, no drift, one loop for all eight octants. And I ended by dropping a hint in exercise 3: that same integer-decision-variable trick is not really about lines at all, it is about walking a discrete grid to approximate a continuous shape. Today we cash that hint in. We draw circles and ellipses with nothing but integer add and compare, we fill them, and we do it in a way that cannot scribble outside the buffer no matter how far off-canvas the shape wanders. Here we go!
Solutions to Episode 157 Exercises
Before we round any corners, the three line exercises from last time.
Exercise 1 -- break drawLine on purpose, then prove the fix. The bug was replacing the dx in the y-branch with dy. The lesson is in the test: a shallow line barely touches the y-branch, so you need a steep line to expose it. Here is the correct routine and the steep-line test that pins a midpoint pixel down. If you introduce the bug (change err += dx to err += dy in the second if), this test fails or loops -- that is the point:
zig const std = @import("std");
const Rgba = packed struct { r: u8, g: u8, b: u8, a: u8 = 255 };
const Framebuffer = struct { pixels: []Rgba, width: usize, height: usize,
fn setPixel(self: Framebuffer, x: i64, y: i64, color: Rgba) void { if (x = self.width or uy >= self.height) return; self.pixels[uy self.width + ux] = color; }
fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba { if (x = self.width or uy >= self.height) return null; return self.pixels[uy self.width + ux]; } };
fn drawLine(fb: Framebuffer, x0: i64, y0: i64, x1: i64, y1: i64, color: Rgba) void { var x = x0; var y = y0; const dx: i64 = @intCast(@abs(x1 - x0)); const dy: i64 = -@as(i64, @intCast(@abs(y1 - y0))); const sx: i64 = if (x0 = dy) { err += dy; x += sx; } if (e2 = self.width or uy >= self.height) return; self.pixels[uy self.width + ux] = color; }
fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba { if (x = self.width or uy >= self.height) return null; return self.pixels[uy self.width + ux]; } };
fn drawThickLine(fb: Framebuffer, x0: i64, y0: i64, x1: i64, y1: i64, width: i64, color: Rgba) void { const half = @divTrunc(width, 2); var x = x0; var y = y0; const dx: i64 = @intCast(@abs(x1 - x0)); const dy: i64 = -@as(i64, @intCast(@abs(y1 - y0))); const sx: i64 = if (x0 = dy) { err += dy; x += sx; } if (e2 = self.width or uy >= self.height) return; self.pixels[uy self.width + ux] = color; }
fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba { if (x = self.width or uy >= self.height) return null; return self.pixels[uy self.width + ux]; } };
fn drawCircle(fb: Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void { var x: i64 = radius; var y: i64 = 0; var err: i64 = 0; while (x >= y) { // one plotted (x, y) mirrors into all eight octants fb.setPixel(cx + x, cy + y, color); fb.setPixel(cx - x, cy + y, color); fb.setPixel(cx + x, cy - y, color); fb.setPixel(cx - x, cy - y, color); fb.setPixel(cx + y, cy + x, color); fb.setPixel(cx - y, cy + x, color); fb.setPixel(cx + y, cy - x, color); fb.setPixel(cx - y, cy - x, color); y += 1; err += 1 + 2 y; if (2 (err - x) + 1 > 0) { x -= 1; err += 1 - 2 x; } } }
test "drawCircle lights the four cardinal points" { var pixels: [21 21]Rgba = undefined; var fb = Framebuffer{ .pixels = &pixels, .width = 21, .height = 21 }; @memset(fb.pixels, .{ .r = 0, .g = 0, .b = 0 }); const white = Rgba{ .r = 255, .g = 255, .b = 255 }; drawCircle(&fb, 10, 10, 8, white); try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 + 8, 10).?.r); // east try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 - 8, 10).?.r); // west try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10 + 8).?.r); // south try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10 - 8).?.r); // north }
Good. That circle is the seed of everything below. Now let us understand why it works, then grow it into filled discs and ellipses.
Why a circle fights the pixel grid
The line was hard because the pixel grid is discrete and a line is continuous. A circle is worse, because its slope changes at every point. Your first instinct -- and mine, once -- is high-school geometry again: a circle of radius r around the origin is xx + yy = rr, so solve for y, step x across the diameter, and plot y = round(sqrt(rr - xx)) above and below. Let us write exactly that, into the same episode-156 framebuffer (widened to i64 coordinates in episode 157), so we can feel the problem:
zig const std = @import("std");
pub const Rgba = packed struct { r: u8, g: u8, b: u8, a: u8 = 255 };
pub const Framebuffer = struct { pixels: []Rgba, width: usize, height: usize, allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator, width: usize, height: usize) !Framebuffer { return .{ .pixels = try allocator.alloc(Rgba, width height), .width = width, .height = height, .allocator = allocator, }; }
pub fn deinit(self: Framebuffer) void { self.allocator.free(self.pixels); }
pub fn clear(self: Framebuffer, color: Rgba) void { @memset(self.pixels, color); }
pub fn setPixel(self: Framebuffer, x: i64, y: i64, color: Rgba) void { if (x = self.width or uy >= self.height) return; self.pixels[uy self.width + ux] = color; }
pub fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba { if (x = self.width or uy >= self.height) return null; return self.pixels[uy self.width + ux]; } };
pub fn drawCircleFloat(fb: Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void { var x: i64 = -radius; while (x = y -- and mirrors every point eight ways. Inside that octant the curve never gets steeper than 45 degrees, so stepping the major axis by one never skips a row: no gaps, ever. And the decision of whether x should shrink this step is made by an integer error term that measures how far the true circle has drifted from the current pixel, exactly like the line's error term. No sqrt, no floats, no division.
The eight setPixel calls scream to be factored out. Let us give the symmetry its own helper -- we will reuse it in a moment for the generic version -- and read the loop carefully:
zig fn plot8(fb: Framebuffer, cx: i64, cy: i64, x: i64, y: i64, color: Rgba) void { fb.setPixel(cx + x, cy + y, color); fb.setPixel(cx - x, cy + y, color); fb.setPixel(cx + x, cy - y, color); fb.setPixel(cx - x, cy - y, color); fb.setPixel(cx + y, cy + x, color); fb.setPixel(cx - y, cy + x, color); fb.setPixel(cx + y, cy - x, color); fb.setPixel(cx - y, cy - x, color); }
pub fn drawCircle(fb: Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void { var x: i64 = radius; // start at due east: (radius, 0) var y: i64 = 0; var err: i64 = 0; while (x >= y) { // stay in the one octant where the slope is gentle plot8(fb, cx, cy, x, y, color); y += 1; err += 1 + 2 y; // moving y out always increases the error if (2 (err - x) + 1 > 0) { // has the true circle crossed inside x - 0.5? x -= 1; err += 1 - 2 x; // pulling x in pays the error back } } }
Read err as "how far outside the ideal circle is my current pixel, in units of rr". Each step moves y outward by one, which always pushes the error up by 1 + 2y (the algebra of (y+1)^2 - y^2). When that error grows past the point where the pixel one column inward is closer to the true circle, we decrement x and refund 1 - 2x. The whole thing is add, compare, add -- and because x only ever shrinks and y only ever grows, the loop marches cleanly from (radius, 0) up to the diagonal and stops. That is the entire algorithm. It has been drawing the circles on your screen, in one form or another, since the 1960s.
Filling a circle is almost free
An outline is nice, but half the time you want a solid disc -- a filled button, a bullet, a pie slice. Here the symmetry pays a second dividend. At each step the octant gives us a pair of x-extents at a given y: everything between cx - x and cx + x on row cy + y is inside the circle. So instead of plotting eight points, we draw four horizontal spans. A span is just a clipped horizontal run, and (as we learned last episode) a horizontal run is the cache-friendliest write there is:
zig fn hSpan(fb: Framebuffer, xa: i64, xb: i64, y: i64, color: Rgba) void { var x = @min(xa, xb); const hi = @max(xa, xb); while (x = y) { hSpan(fb, cx - x, cx + x, cy + y, color); // wide bands near the equator hSpan(fb, cx - x, cx + x, cy - y, color); hSpan(fb, cx - y, cx + y, cy + x, color); // tall thin caps near the poles hSpan(fb, cx - y, cx + y, cy - x, color); y += 1; err += 1 + 2 y; if (2 (err - x) + 1 > 0) { x -= 1; err += 1 - 2 x; } } }
test "fillCircle fills the centre and the cardinal extremes, but not outside" { var fb = try Framebuffer.init(std.testing.allocator, 21, 21); defer fb.deinit(); fb.clear(.{ .r = 0, .g = 0, .b = 0 }); const c = Rgba{ .r = 255, .g = 255, .b = 255 }; fillCircle(&fb, 10, 10, 8, c); try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10).?.r); // centre try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 + 8, 10).?.r); // east edge try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10 + 8).?.r); // south edge try std.testing.expectEqual(@as(u8, 0), fb.getPixel(10 + 8, 10 + 8).?.r); // corner outside the disc: black (proves disc, not square) try std.testing.expectEqual(@as(u8, 0), fb.getPixel(2, 2).?.r); // well outside the disc }
There is quit some overdraw here -- the four spans overlap along the diagonals, so the corner pixels get written twice. For a solid fill that is harmless (writing the same colour twice looks identical), and the code stays tiny. If you were blending semi-transparent colours it would matter, and you would switch to a scanline fill that computes each row exactly once; that is exactly the trade-off exercise 2 asks you to explore.
From circle to ellipse
A circle is an ellipse whose two radii happen to be equal. Drop that coincidence and the eight-way symmetry collapses to four-way (an ellipse has no diagonal symmetry, only across its two axes), and -- here is the interesting part -- the arc from one axis to the other has a point where its slope passes through 45 degrees. Before that point x is the major axis; after it, y is. So the midpoint ellipse algorithm runs in two regions, switching the axis it steps when the slope tips over. Two decision variables, one per region, each still pure integer arithmetic:
zig fn plot4(fb: Framebuffer, cx: i64, cy: i64, x: i64, y: i64, color: Rgba) void { fb.setPixel(cx + x, cy + y, color); fb.setPixel(cx - x, cy + y, color); fb.setPixel(cx + x, cy - y, color); fb.setPixel(cx - x, cy - y, color); }
pub fn drawEllipse(fb: Framebuffer, cx: i64, cy: i64, a: i64, b: i64, color: Rgba) void { const a2 = a a; const b2 = b b; var x: i64 = 0; var y: i64 = b; // start at the top of the ellipse var px: i64 = 0; // 2b2x, kept incrementally var py: i64 = 2 a2 y; // 2a2y, kept incrementally plot4(fb, cx, cy, x, y, color);
// Region 1: gentle slope, x is the major axis -- step x every iteration var p1: i64 = b2 - a2 b + @divTrunc(a2, 4); while (px 0) { y -= 1; py -= 2 a2; if (p2 > 0) { p2 += a2 - py; } else { x += 1; px += 2 b2; p2 += a2 - py + px; } plot4(fb, cx, cy, x, y, color); } }
The shape of it mirrors the circle: keep running totals (px, py) so the per-step work is a couple of adds, and let a decision variable pick when to advance the minor axis. The one wrinkle is the @divTrunc(..., 4) terms. The exact midpoint maths involves halves and quarters ((x + 0.5)^2 and a2/4), and rather than drag floats back in we scale into integers and truncate. That truncation makes the decision very slightly approximate at the sub-pixel level, but for integer pixel coordinates the drawn ellipse is indistinguishable from the exact one -- and we have kept the whole routine FPU-free. The px = y) { ctx.plot(cx + x, cy + y); ctx.plot(cx - x, cy + y); ctx.plot(cx + x, cy - y); ctx.plot(cx - x, cy - y); ctx.plot(cx + y, cy + x); ctx.plot(cx - y, cy + x); ctx.plot(cx + y, cy - x); ctx.plot(cx - y, cy - x); y += 1; err += 1 + 2 y; if (2 (err - x) + 1 > 0) { x -= 1; err += 1 - 2 x; } } }
const Bounds = struct { minx: i64 = 0, maxx: i64 = 0, miny: i64 = 0, maxy: i64 = 0, fn plot(self: Bounds, x: i64, y: i64) void { self.minx = @min(self.minx, x); self.maxx = @max(self.maxx, x); self.miny = @min(self.miny, y); self.maxy = @max(self.maxy, y); } };
test "midpointCircle reports a tight bounding box, no screen needed" { var b = Bounds{}; midpointCircle(0, 0, 10, &b); try std.testing.expectEqual(@as(i64, -10), b.minx); try std.testing.expectEqual(@as(i64, 10), b.maxx); try std.testing.expectEqual(@as(i64, -10), b.miny); try std.testing.expectEqual(@as(i64, 10), b.maxy); }
Tags: #stem#stemsocial#steemstem#zig#programming