WebGPU Graph Renderer

This is a toy project that was intended to be a graph rendering engine built using WebGPU and TypeScript. The main focus of this project was to serve as a playground for me to experiment with various graphic programming concept.

Overview

The goal of this engine is to support interactive manipulation and visualization of graphs at scale. It is designed to be extensible, with a clear separation between data modeling (the graph in core), rendering logic (GPU in renderer), interaction handling (through tool abstractions manage by an interactor in interaction), and hit-testing (through a GPUPicking in picking.

---

Technical Architecture and Design Decisions

Interaction Model: Tool-Based, Stateful Design

Way to overengineered and abstract on purpose, I was testing relevancy of design pattern.

• Interaction is organized via a stateful tool system (strategy pattern kindoff).
• The Interactor is the central input controller, dispatching pointer, keyboard, and wheel events to the currently active Tool.
• Tools encapsulate their own logic and state (SelectTool, DragTool, ConnectTool, etc.), enabling modular and scalable behavior.

Unified GPU Instancing: Nodes & Handles

The point was to bring test the limit of GPU instancing and delegate as much work as possible on GPU:

• A shared instancing buffer is used for both nodes and handles, enabling consistent rendering order and simplified pipeline management.
• Visual attributes like position, size, color, and kind (node or handle) are encoded per instance.
• Instance data is streamed to the GPU via a ResizableFloat32Array and backed by a GPUBuffer, allowing efficient partial updates.
• This unified approach ensures correct z-ordering (e.g., handles on top of nodes) without requiring multiple render passes.
• Handle are screen-space circles rendered using quads and a fragment shader distance field.

Dirty Flag System

The point was to test in practice how chirurgical update can be.

• A dirty tracking system enables both global and per-element synchronization:
  • dirty.global: triggers a full re-sync of GPU buffers.
  • dirty.nodes, dirty.edges: track fine-grained updates for incremental sync.
• Each renderer (NodeRenderer, EdgeRenderer, etc.) implements sync() and syncPartial() methods, allowing it to update only the elements that changed.

GPU-Based Picking

The desktop team at my work used it, at the time I cannot implement it on my side so I wanted to test it here (end up good ol' three raycaster perform better for my use case than a GPU picker)

• An offscreen render pass encodes picking IDs into RGB colors using an RGBA8Unorm texture.
• A compact ID-to-color encoding scheme minimizes GPU memory usage and bandwidth.
• A bidirectional mapping between internal numeric IDs and external unique IDs (node-..., handle-..., etc.) enables fast reverse lookups.
• Picking reads a 1×1 pixel region at the mouse position and decodes the color to resolve the selected element.

Quad tree

Yeah we reach the point where it is difficult to justify my choice... Ig I just wanted to implement a quad tree. And also it is just better for zone selection.

Edge Rendering

That part was kinda fun to learn about.

• Edges are rendered with GPU instancing using stroke extansion in vertex shader.
• Supports miter joins for sharp corners. (not rounded tho)
• Edge geometry is computed per edge segment and updated independently via partial syncs.

Compact Per-Handle Edge Registry

Some premature optimisation:

• A direct edge registry (_edgeRegistry) maps handle IDs to their corresponding edge ID, allowing O(1) access and dirty tracking.
• Since each handle can have at most one edge, this registry reduces iteration and lookup overhead significantly.

Buffer Management & Memory Efficiency

• Resizable buffers automatically grow to accommodate graph size and reduce memory churn.
• All per-instance buffers are aligned with GPU memory layout expectations (e.g., 32 or 56 bytes per instance).

---

Project Structure

/core             - Data model: Graph, Node, Edge, Handle
/renderer         - GPU rendering: NodeRenderer, EdgeRenderer, etc.
/picking          - Picking pass: color encoding and GPU readback
/interactor       - Input system with Tool routing
/shaders          - WGSL shader code
/utils            - Math, color, ID helpers

---

Pipeline Overview

1. User Input The user interacts with the application through mouse, keyboard, or touch input.

2. Interactor and Active Tool Input events are processed by the Interactor, which delegates them to the currently active tool (e.g., DragTool, SelectTool, etc.).

3. Graph Mutation The active tool applies changes to the graph structure—adding, moving, or removing nodes, handles, or edges.

4. Renderer Synchronization After the graph is updated, the renderers (e.g., NodeRenderer, EdgeRenderer) synchronize their internal GPU buffers with the graph's current state. This update can be full or partial depending on what changed.

5. WebGPU Frame Rendering The current frame is rendered using WebGPU, displaying all graph elements on the canvas.

---

Picking System

• A PickingRenderer performs a render pass where each instance is drawn with a unique RGB color that encodes its internal ID.
• The PickingManager maintains a bidirectional mapping between RGB values and element IDs.
• Only the 1x1 pixel under the cursor is read back asynchronously.
• Handles and nodes are currently supported; edge picking is planned.

---

Roadmap

• Basic deployment and demo via GitHub Pages
• Dirty state system for local/global sync
• Solving overlap: Per-object rendering OR Common instancing node-handle
• Partial buffer update for local change (with offsetMap uid -> bufferOffset)
• Node zIndexing (maybe just split instancing for selectedNode)
• Complete interaction tool implementation (drag, select, connect)
• Zoom and pan support in the viewport
• Group selection & apropriate SelectionTool
• Edge picking
• Minimap display
• Rounded line cap
• Automatic layout on multiple edge node

---

Guiding Principles

Having fun.