Learn Zig Series (#157) - Line Drawing: Bresenham
Published on HivePostify by @scipio · Wed Sep 02 2026
Learn Zig Series (#157) - Line Drawing: Bresenham
What will I learn? - Why drawing a straight line between two arbitrary points is a genuinely hard problem, and how the pixel grid quietly fights you every step of the way; - The naive floating-point DDA approach first -- so you feel exactly what is wrong with it before we fix it; - Bresenham's line algorithm from first principles: an integer-only decision variable that picks the next pixel with nothing but addition and comparison, no division, no floats, no drift; - How to grow the single-octant version into an all-directions routine that draws any line at any angle, clipping cleanly to the canvas; - How Zig's signed integers, ?Rgba optionals and anytype let us decouple the algorithm from the surface it draws on, so the same Bresenham serves a framebuffer, a counter, or an SVG writer; - How to test a line routine with no screen at all, and why the "hits both endpoints and is symmetric" property is the test that catches the most bugs; - Where this shows up in the real world (wireframes, UI, plotting) and how C, Rust and Go draw the exact same line.
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 setPixel/getPixel from episode 156 -- we draw straight into that buffer today; - Signed integers and control flow from the early episodes, and the anytype comptime-duck-typing trick we have leaned on 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) (this post)
Learn Zig Series (#157) - Line Drawing: Bresenham
Last episode we built a framebuffer -- a flat slice of pixels pretending to be a 2D grid, with setPixel, clear and fillRect. We can paint rectangles all day, but a picture is not made of rectangles. It is made of lines -- the edges of shapes, the strokes of a font, the wires of a 3D model projected flat. And drawing a line between two arbitrary points turns out to be one of those problems that looks trivial for about ten seconds and then bites you. Today we solve it properly, the way it has been solved since 1962, with an algorithm so lean it runs on a microcontroller with no floating-point unit at all. Here we go!
Solutions to Episode 156 Exercises
Before we draw a single line, here are the solutions to last episode's three framebuffer exercises.
Exercise 1 -- horizontal and vertical lines. The horizontal one is one @memset over a contiguous row; the vertical one steps by width. Both clip to the canvas. Note the + 1 that makes the endpoint inclusive:
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 hLine(self: Framebuffer, x0: usize, x1: usize, y: usize, color: Rgba) void { if (y >= self.height) return; // whole row off-canvas const lo = @min(x0, x1); if (lo >= self.width) return; const hi = @min(@max(x0, x1) + 1, self.width); // clip right edge, inclusive endpoint const start = y self.width + lo; const end = y self.width + hi; @memset(self.pixels[start..end], color); // one contiguous fill }
fn vLine(self: Framebuffer, x: usize, y0: usize, y1: usize, color: Rgba) void { if (x >= self.width) return; const lo = @min(y0, y1); const hi = @min(@max(y0, y1) + 1, self.height); var y = lo; while (y = dst.height) break; // below the canvas: no rows left const copyw = if (dstx >= dst.width) 0 else @min(src.width, dst.width - dstx); if (copyw == 0) continue; // this row lands entirely off the right edge const sstart = row src.width; const dstart = dy dst.width + dstx; @memcpy(dst.pixels[dstart .. dstart + copyw], src.pixels[sstart .. sstart + copyw]); } }
test "blit clips the part that falls off the destination" { var dpix: [16]Rgba = undefined; var dst = Framebuffer{ .pixels = &dpix, .width = 4, .height = 4 }; @memset(dst.pixels, .{ .r = 0, .g = 0, .b = 0 });
var spix: [4]Rgba = undefined; const src = Framebuffer{ .pixels = &spix, .width = 2, .height = 2 }; @memset(spix[0..], .{ .r = 9, .g = 9, .b = 9 });
blit(&dst, src, 3, 3); // only its top-left pixel fits in the corner try std.testing.expectEqual(@as(u8, 9), dst.pixels[3 4 + 3].r); // corner copied try std.testing.expectEqual(@as(u8, 0), dst.pixels[0].r); // rest untouched }
Exercise 3 -- a checkerboard exported to PGM. PGM is PPM's grayscale sibling: the magic bytes P5, then width, height, max value, then one byte per pixel. The pattern is a parity check on which cell each pixel falls into:
zig const std = @import("std");
fn checkerboard(pixels: []u8, width: usize, height: usize, cell: usize) void { var y: usize = 0; while (y white try std.testing.expectEqual(@as(u8, 0), buf[8]); // (8,0) flips -> black const pgm = try toPgm(std.testing.allocator, buf, w, h); defer std.testing.allocator.free(pgm); try std.testing.expect(std.mem.startsWith(u8, pgm, "P5\n16 16\n255\n")); try std.testing.expectEqual("P5\n16 16\n255\n".len + w h, pgm.len); }
Right -- framebuffer refreshed, exercises squared away. Now to the real subject.
Why a straight line is not straightforward
Here is the trap. You have two points, (x0, y0) and (x1, y1), and you want to light up the pixels between them. Your first instinct, and mine too the first time, is high-school algebra: the line is y = mx + b where m is the slope. So loop x from x0 to x1, compute y = round(mx + b), plot. Done, right?
It works -- for gentle slopes. But it has three real problems. First, it uses floating-point multiplication and rounding per pixel, which is slow and, on a chip with no FPU, not even available. Second, if the line is steeper than 45 degrees, stepping x by one skips whole rows of y, leaving a dashed, gappy line -- you would have to detect that case and loop over y instead. Third, floating-point rounding drifts: accumulate enough tiny errors and the line wobbles off its true path. We can do better with only integers, and that is Bresenham's gift.
The naive version first, so you feel the problem
Before the elegant solution, let us write the honest, naive one -- the DDA (Digital Differential Analyzer). It fixes the gap problem by stepping along whichever axis is longer, but it still leans on floats. We draw into the episode-156 framebuffer, which I have widened to accept signed coordinates -- crucial, because a line can start off the left edge at a negative x and we want to clip, not crash:
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); }
// signed coordinates: anything off-canvas is silently clipped, never a crash 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]; } };
Widening the coordinate to i64 is a small decision with big consequences. In episode 156 our pixels were addressed with usize, which is unsigned -- perfect for a buffer index that can never be negative. But a line lives in a coordinate space where negatives are completely normal (a shape half off the screen), so the drawing API speaks i64, and setPixel is the one place that converts, clips and guarantees the final index is a valid usize. The boundary between "geometry, which can be negative" and "memory, which cannot" lives in exactly one function. That is the same encapsulation discipline as last episode's private index helper.
Now the DDA itself:
zig pub fn drawLineFloat(fb: Framebuffer, x0: i64, y0: i64, x1: i64, y1: i64, color: Rgba) void { const dx: f64 = @floatFromInt(x1 - x0); const dy: f64 = @floatFromInt(y1 - y0); const steps: usize = @intFromFloat(@max(@abs(dx), @abs(dy))); // walk the LONGER axis if (steps == 0) { fb.setPixel(x0, y0, color); // start == end: a single dot return; } const xinc = dx / @as(f64, @floatFromInt(steps)); const yinc = dy / @as(f64, @floatFromInt(steps)); var x: f64 = @floatFromInt(x0); var y: f64 = @floatFromInt(y0); var i: usize = 0; while (i = x0, and 0 0) { // the true line has crossed into the next row y += 1; d -= 2 dx; } d += 2 dy; // every x step adds the rise } }
Read the loop as a running tally. d starts at 2dy - dx. Every column we add 2dy (the doubled rise). The moment d goes positive, the ideal line has drifted more than half a pixel above our current row, so we step y up and pay back 2dx. No division, no floats, no rounding -- just three integer operations per pixel, and the error can never drift because it is exact. That is the whole trick, and it is genuinely beautiful once it lands.
The all-octant version you will actually use
The shallow version only handles one of the eight directions a line can go. The production form handles them all with two sign variables (sx, sy) for the step direction and a symmetric error term that lets either axis be the long one. This is the version to memorise -- I have typed it from memory more times than any other graphics routine:
zig pub 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))); // note: dy is negative here const sx: i64 = if (x0 = dy) { // time to step along x err += dy; x += sx; } if (e2 = dy advances x, e2 = dy) { err += dy; x += sx; } if (e2 = 0 && x0 = 0 && y0 = dy) { err += dy; x0 += sx; } if (e2 (our ?Rgba again) or a bounds-checked buf[i] that panics -- the same safe-by-default posture as Zig. The image and tiny-skia crates give you drawline out of the box. Go leans on its standard image package plus golang.org/x/image/vector for anything fancy, with slice accesses bounds-checked at runtime and a panic (not corruption) if you overrun -- again landing in Zig's safety neighbourhood, trading a little speed for not trashing memory. The through-line: everyone runs the identical 1962 integer loop; they differ only in what happens the instant your index escapes the buffer. Zig hands you the raw-C speed and the clip-or-crash safety in one language, and lets you drop the check per build once you have earned it with tests.
Exercises
1. Break it on purpose, then prove the fix. Copy drawLine and change the y-branch to add dy instead of the correct dx. Now write a test that draws a steep line -- say (0,0) to (2,8), where y is the long axis -- and asserts a midpoint pixel like (1,4) is lit. Watch the broken version fail (or loop), then restore the dx and watch it pass. The lesson: the "hits both endpoints" test alone is not enough, because a shallow line barely exercises the y-branch -- you need a steep case to catch this class of bug.
2. Thick lines. Write drawThickLine(fb, x0, y0, x1, y1, width, color) that draws a line width pixels thick. The simplest correct approach: run Bresenham, and at each plotted point stamp a small filled square (or, better, a short perpendicular run) of the given width. Test that a horizontal thick line of width 3 lights three rows, and that the thickness clips at the canvas edge.
3. Extend the error term to a curve. Bresenham's decision-variable idea is not limited to lines. Using nothing but integer add and compare, implement drawCircle(fb, cx, cy, radius, color) for a circle centred at (cx, cy): track an integer error term as you step one octant from the top, and mirror each plotted point into the other seven octants by symmetry. Test that the four cardinal points (cx +/- radius, cy +/- radius) are lit. This is the exact same "integer decision variable" machinery, pointed at a rounder target.
What we learned
- Drawing a straight line between arbitrary pixels is deceptively hard: the slope-intercept approach is slow, gappy on steep slopes, and drifts; - The DDA fixes the gaps by walking the longer axis, but still pays floating-point add, round and cast on every pixel -- unavailable on an FPU-less chip; - Bresenham replaces all of that with a single integer error term: add the rise each step, and when it crosses the halfway mark, bump the minor axis and pay it back -- no floats, no division, no drift; - The all-octant form uses sx/sy sign steps and two (non-exclusive) if branches so one loop draws every direction, including exact 45-degree diagonals; - Making the coordinate API i64 and clipping inside setPixel puts the "geometry can be negative, memory cannot" boundary in exactly one place, so the line loop stays simple and still cannot overflow the buffer; - An anytype plot context decouples generating the pixels from consuming them, with zero runtime cost -- the same line drives a framebuffer, a counter, or a file; - We test drawing with no screen by asserting on read-back pixels, and the "both endpoints lit" plus "clips cleanly off-canvas" properties catch the overwhelming majority of bugs; - C, Rust and Go all run the identical integer loop -- they differ only in what happens when your index leaves the buffer, and Zig gives you the raw speed and the safety in the same language.
We can draw any line now, at any angle, without a single floating-point operation -- and the error-term trick we just learned is not really about lines at all. It is about walking a discrete grid to approximate a continuous shape using only integers, and that idea generalises to rounder things than lines, as exercise 3 hints. That is exactly where we go next. Keep this drawLine handy -- like the framebuffer before it, everything from here builds on top of it.
Bedankt en tot de volgende keer! ;-)
Tags: #stem#stemsocial#steemstem#zig#programming