Learn Zig Series (#159) - Polygon Filling: Scanline
Published on HivePostify by @scipio · Fri Sep 04 2026
Learn Zig Series (#159) - Polygon Filling: Scanline
What will I learn? - Why an arbitrary polygon cannot lean on the tidy symmetry that made circles and ellipses easy to fill; - The even-odd (parity) rule: how a horizontal ray crossing a shape's outline tells you, crossing by crossing, whether you are inside or outside; - A scanline polygon fill written from scratch in Zig -- for every row, find where the edges cross it, sort those x-values, and paint the spans between pairs; - The half-open edge rule that stops shared vertices from being counted twice (the bug that leaves a stray dark pixel or bleeds a whole extra span); - How Zig's error unions and allocator make the "how many crossings can there be" question honest instead of a magic fixed array; - The active-edge idea -- decompose the polygon into edges once, keep only the edges the current row actually touches, and step each crossing incrementally with pure integer math; - Where scanline fill really lives (fonts, SVG, every vector renderer), and how C, Rust and Go write the exact same loop.
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 clipping signed-coordinate setPixel/getPixel from episode 156, and the fills we grew out of circles and ellipses in episode 158 -- today generalises that filling to any shape; - std.mem.sort, signed integers, 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) - [Learn Zig Series (#159) - Polygon Filling: Scanline](https://hive.blog/hive-196387/@scipio/learn-zig-series-159-polygon-filling-scanline) (this post)
Learn Zig Series (#159) - Polygon Filling: Scanline
Last episode we filled circles and ellipses, and the trick that made it easy was symmetry. A circle hands you eight mirrored points for the price of one octant; an ellipse hands you four. The fills fell out almost for free because the shape told us, at every row, exactly where its left and right edges were. But most of the shapes you actually want to fill -- a triangle, a five-pointed star, the outline of the letter A, a country on a map -- have no symmetry at all. So today we throw the crutch away and build the fill that works for any closed polygon: the scanline fill. It is one of those ideas that feels almost too simple once it clicks, and it is the exact algorithm sitting under every font renderer and vector engine you have ever used. Here we go!
Solutions to Episode 158 Exercises
Three exercises last time, all of them about turning our curve routines into something more. Here are my solutions.
Exercise 1 -- arcs, not whole circles. The task: draw only some of the eight octants, enough to build a rounded-rectangle corner. The clean approach keeps the midpoint loop untouched and simply guards each of the eight setPixel calls behind whether its octant is in the requested range. I number the octants 0 through 7 going clockwise from due east, and a tiny helper decides membership:
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 octantOn(o: usize, start: usize, end: usize) bool { return o >= start and o = y) { if (octantOn(0, start, end)) fb.setPixel(cx + x, cy - y, color); if (octantOn(1, start, end)) fb.setPixel(cx + y, cy - x, color); if (octantOn(2, start, end)) fb.setPixel(cx - y, cy - x, color); if (octantOn(3, start, end)) fb.setPixel(cx - x, cy - y, color); if (octantOn(4, start, end)) fb.setPixel(cx - x, cy + y, color); if (octantOn(5, start, end)) fb.setPixel(cx - y, cy + x, color); if (octantOn(6, start, end)) fb.setPixel(cx + y, cy + x, color); if (octantOn(7, start, end)) fb.setPixel(cx + x, cy + y, color); y += 1; err += 1 + 2 y; if (2 (err - x) + 1 > 0) { x -= 1; err += 1 - 2 x; } } }
test "single-octant arc lights its end and leaves the far side dark" { 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 }; drawArc(&fb, 10, 10, 8, 0, 0, white); // octant 0 only try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 + 8, 10).?.r); // east endpoint lit try std.testing.expectEqual(@as(u8, 0), fb.getPixel(10 - 8, 10).?.r); // west stays dark }
The lesson is that octant selection costs you nothing at runtime that matters -- you still walk the same loop, you simply skip stores. For a rounded rectangle you call drawArc four times, one quarter each, and stitch straight edges between them.
Exercise 2 -- a proper scanline fill of the disc. Our fillCircle overdrew the diagonals; the task was to write each row exactly once. For every vertical offset dy from -radius to +radius, we want the largest half-width hw with dydy + hwhw = 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 fillCircleScan(fb: Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void { var dy: i64 = -radius; while (dy each row drawn once try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10).?.r); // centre try std.testing.expectEqual(@as(u8, 0), fb.getPixel(2, 2).?.r); // corner outside the disc }
The test is the interesting part: because the number of lit pixels equals the area summed independently from the same rule, we have proven no pixel got written twice and none got skipped. That is a stronger statement than "the middle looks filled".
Exercise 3 -- fill the ellipse. Same idea, but the per-row half-width now obeys the ellipse relation hwhwb2 + dydya2 = 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 fillEllipse(fb: Framebuffer, cx: i64, cy: i64, a: i64, b: i64, color: Rgba) void { const a2 = a a; const b2 = b b; var dy: i64 = -b; while (dy = 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]; } };
The even-odd rule: parity as a compass
Here is the whole idea in one sentence: imagine a ray shot horizontally from far away toward a point; each time it crosses the polygon's outline it flips between outside and inside. Start outside (crossings = 0, even). Cross one edge -- now you are inside (odd). Cross a second -- back outside (even). So a point is inside the polygon exactly when the number of edge crossings strictly to one side of it is odd. This is the even-odd rule, and it works for any polygon, convex or concave, without knowing anything about its shape.
We can test the rule directly with a point-in-polygon check, which is a warm-up for the fill (same crossing math, one point instead of a whole row):
zig pub fn pointInPolygon(points: []const Point, px: i64, py: i64) bool { var inside = false; var j: usize = points.len - 1; var i: usize = 0; while (i py) != (b.y > py)) { const crossx = a.x + @divFloor((py - a.y) (b.x - a.x), b.y - a.y); if (px py) != (b.y > py) test is doing something sneaky and important: it is asking "does this edge have one endpoint above the ray and one at-or-below it?". By treating the comparison as strictly above versus not above, it counts each edge on a half-open interval -- and that is what stops a vertex shared by two edges from being counted as two crossings (which would break parity). Hold that thought; it is the single most common polygon-fill bug, and we are about to meet it head-on.
A scanline fill from scratch
The fill is the point-in-polygon test promoted from one point to an entire row at a time. For each scanline y between the polygon's top and bottom, we walk every edge, keep the ones that straddle y, compute where each crosses, sort those x-values, and paint the spans between consecutive pairs -- pair [0,1] is inside, [2,3] is inside, and so on, straight out of the even-odd rule:
zig pub fn fillPolygon(fb: Framebuffer, points: []const Point, color: Rgba) void { if (points.len = lo and y = lo and y = lo and y = e.ymin and y = 0) { while (acc. >= dy) : (acc. -= dy) x. += 1; } else { while (acc. with a fill attribute is scanline-filled. Every vector illustration, every filled region in a charting library, every map polygon, every filled shape in a game's 2D HUD -- all of it is this parity-and-spans loop. The even-odd rule you just learned is even a named attribute in the SVG spec (fill-rule="evenodd"), sitting right next to its cousin the nonzero winding rule, which counts edge directions instead of bare crossings so that overlapping sub-paths fill sensibly. Swapping our parity flip for a signed winding counter is a small change and a natural next experiment (it is exercise 3).
The same fill in C, Rust and Go
The algorithm is language-neutral integer arithmetic, so it ports almost line for line -- what changes is, once again, the story around memory. In C you malloc the crossings array yourself, remember to free it, qsort the x-values, and every buffer write is your responsibility to bounds-check:
c // C: scanline fill, manual crossings buffer, manual clipping on every store #include
static int cmpint(const void pa, const void pb) { int a = (const int )pa, b = (const int )pb; return (a > b) - (a maxy) maxy = py[i]; } for (int y = miny; y = lo && y = 0 && x = 0 && y you .sort(), panics rather than corrupts on an out-of-range index, and in practice reaches for tiny-skia, lyon or femtovg, which hand you a hardened, anti-aliased polygon fill out of the box. Go uses a slice you sort.Ints, bounds-checked writes that panic on overrun, and the standard image package plus golang.org/x/image/vector for a production rasteriser. The through-line is the one we keep meeting: everybody runs the identical mid-1970s scanline sweep, and they differ only in what happens the instant an index escapes the buffer, or an allocation fails. Zig gives you C's speed with the clip living in exactly one place -- setPixel -- and the failure spelled out in the function's !void.
Exercises
1. Filled polygon outlines that meet the fill. Combine today's fillPolygonAET with episode 157's drawLine: fill a polygon in one colour, then stroke its edges in another, so the border is crisp. Test that a boundary pixel takes the stroke colour while a deep-interior pixel keeps the fill colour. Watch the half-open rule -- the bottom edge of a filled polygon can come out one row short, and a stroke is a good way to see it.
2. A star, to prove concavity works. Build the ten vertices of a five-pointed star (alternating outer and inner radius around a centre, using the integer sin/cos table trick or precomputed points) and fill it with fillPolygon. Test that a point in one of the star's arms is lit, a point in a concave notch between two arms is dark, and the centre is lit. This is the shape that separates a real even-odd fill from a convex-only shortcut.
3. Nonzero winding rule. Replace the parity flip with a signed winding counter: give each edge a direction (+1 if it goes downward, -1 if upward), and instead of toggling inside/outside at each crossing, add the edge's direction and treat "winding != 0" as inside. Fill a shape with a hole wound the opposite way (an outer square anti-clockwise, an inner square clockwise) and test that the hole comes out empty under winding but filled under even-odd -- the classic difference between the two rules.
What we learned
- Circles and ellipses fill easily because symmetry hands you each row's extents; an arbitrary polygon has no such gift, so we ask each edge where it crosses the current row instead of asking the shape; - The even-odd rule says a point is inside when a ray from it crosses the outline an odd number of times -- parity is a compass that works for any polygon, convex or concave; - A scanline fill applies that rule a whole row at a time: gather the edge crossings for row y, sort them, and paint the spans between consecutive pairs; - The half-open y >= lo and y < hi edge test is the crucial detail -- it counts each edge once at a shared vertex (keeping parity correct) and skips horizontal edges for free (no divide-by-zero); - Zig's !void and an allocator turn the "how many crossings" question from a magic [64] cap into an honest, exactly-sized allocation with the one failure mode spelled out in the signature; - The active-edge table decomposes the polygon into edges once and touches only the edges each row spans; computing crossings from the lower endpoint makes the fast version byte-for-byte identical to the reference, and a Bresenham-style accumulator removes even the per-row multiply and divide; - Fonts, SVG, maps and every vector renderer are running this exact parity-and-spans sweep; C, Rust and Go write the identical loop and differ only in what happens when an index or an allocation goes wrong.
We can now fill any closed polygon, on top of the lines, circles and ellipses of the last episodes -- our little rasteriser draws real shapes now, not just primitives. But look at how every shape so far has been pinned to fixed pixel coordinates: we hand-typed the star's vertices, the triangle's corners, the circle's centre. The moment you want to move that polygon across the screen, spin it, or scale it to half size, you do not want to recompute every vertex by hand -- you want a single, composable way to transform a whole set of points at once. That machinery -- the matrices that rotate, scale and translate everything we draw -- is exactly where we head next. Keep these fill routines close; they are about to start drawing shapes that move.
Bedankt en tot de volgende keer! ;-)
@scipio
Tags: #stem#stemsocial#steemstem#zig#programming