Drawing a Family Tree With Thousands of People: Server-Side Layout and Level-of-Detail Rendering
Notes on moving tree layout out of the client and into stored geometry, then rendering only the viewport across three levels of detail — so draw cost tracks what's on screen instead of how big the tree is.
A family tree has an awkward property: it has no natural size limit. One family adds a few dozen people and stops. Another keeps going for eight generations and passes a thousand. The screen showing it, meanwhile, is always about 1400 by 900 pixels.
That mismatch is the whole engineering problem, and it splits into two questions that turn out to be independent:
- Who decides where each person’s box goes — and how often does that get decided?
- What does the client actually draw, given that almost none of the tree is on screen at any moment?
This is a journal of working both out for srishtiuniverse.com, across a Spring Boot backend, a React web client and a Flutter mobile client. I’m only writing about tree building and rendering here; everything else about the system is out of scope.
Where the first version spent its time
The original arrangement was the obvious one. The backend assembled the entire tree — every person, every relationship, every node’s details — and handed it over. Each client then took that graph and worked out the geometry itself: the web app computed a layout and rendered it through ReactFlow, and there was a separate layout implementation on the server side for its own rendering path.
Two things about that shape bothered me once trees got large.
The layout was recomputed on every single view. Opening the tree meant solving the layout again, from scratch, in the client. But the arrangement of a tree only depends on the tree’s shape — and the shape doesn’t change when you look at it. I was paying a per-view cost for an answer that was the same every time.
Geometry had two independent implementations. Two layout engines, two sets of spacing rules, two chances to disagree. Any picture of the tree — the interactive view, an export — had to be produced by whichever engine that path happened to use.
And underneath both: rendering cost scaled with the whole tree, not the visible part. ReactFlow gives every node a real component in the DOM. That’s excellent when nodes are interactive things you want to style and attach handlers to, and a few hundred of them is comfortable. A thousand people means a thousand mounted components, each with layout, style recalculation and paint work, all of it happening whether or not you’re looking at that branch.
Concept: layout is a pure function of the tree, so compute it once
The reframe that made everything else fall out: a tree and a picture of a tree are two different artifacts with two different lifetimes.
The tree changes when someone edits it — a person is added, a person is removed, and so on. Between those events, every coordinate in the picture is constant. Anything constant between rare events doesn’t belong on the read path at all; it belongs computed once and stored.
So layout moved to the backend and became stored geometry. When the shape of the tree changes, the layout is recomputed and the results are saved: an (x, y) per person, and a list of points per edge. Nothing recalculates on a view.
That changes what the API returns. Instead of a graph for the client to solve, it returns the solution:
public class GraphResponse {
private List<Node> nodes; // id, data, children, position
private List<Edge> edges; // sourceId, targetId, points
private Metadata metadata; // nodeWidth, nodeHeight, actionWidth
private RootNode root; // where to point the camera initially
}The metadata block is small but load-bearing. Box dimensions are an input to the layout, so the clients have to agree with the server about them exactly — if the server spaces nodes for a 250-wide box and a client draws 260, every gap is wrong. Sending the dimensions that produced the layout means the clients can’t drift.
Concept: linear-time tidy trees
With layout server-side and computed only on change, it can be a proper algorithm rather than something that has to be cheap enough to run in a browser on every page view. The one that fits a tree is Buchheim et al.’s improvement on Walker’s algorithm — the linear-time refinement of Reingold–Tilford “tidy” layout.
It gives you the properties you actually want from a genealogy view: parents centered over their children, siblings evenly spaced, no subtree ever overlapping its neighbour, and the whole thing as narrow as those constraints allow. It runs in two walks over the tree.
The first walk assigns a preliminary x to every node, bottom-up:
private void firstWalk(BuchheimNode v) {
if (v.isLeaf()) {
BuchheimNode ls = v.leftSibling();
v.prelim = ls != null ? ls.prelim + NODE_WIDTH + X_GAP : 0;
} else {
BuchheimNode defaultAncestor = v.leftmost();
for (BuchheimNode w : v.children) {
firstWalk(w);
defaultAncestor = apportion(w, defaultAncestor);
}
executeShifts(v);
double mid = (v.leftmost().prelim + v.rightmost().prelim) / 2.0;
BuchheimNode ls = v.leftSibling();
if (ls != null) {
v.prelim = ls.prelim + NODE_WIDTH + X_GAP;
v.mod = v.prelim - mid; // remember the offset, don't push children yet
} else {
v.prelim = mid;
}
}
}A leaf goes just right of its left sibling. A parent wants to sit centered over its children — but it also has to clear its own left sibling’s subtree, so it may need to move right. The naive fix is to shift the entire subtree beneath it, which is what makes Walker’s original algorithm quadratic: deep trees shift the same nodes over and over.
Buchheim’s contribution is to defer those shifts. A node records a pending offset in mod rather than applying it, apportion resolves conflicts between adjacent subtrees using threaded contour pointers (nextLeft/nextRight walk the outline of a subtree without traversing its interior), and executeShifts distributes accumulated corrections across siblings in one pass. Then a single top-down walk turns deferred offsets into absolute coordinates:
private void secondWalk(BuchheimNode v, double m, int depth, Map<String, double[]> out) {
out.put(v.id, new double[]{ v.prelim + m, MARGIN + depth * (NODE_HEIGHT + Y_GAP) });
for (BuchheimNode child : v.children) {
secondWalk(child, m + v.mod, depth + 1, out);
}
}Accumulating m + v.mod down the recursion is what makes each node’s final x the sum of every deferred shift above it — collected in one traversal instead of applied repeatedly. Every node is touched a constant number of times, so the whole layout is O(n).
Two properties matter more than the speed, given that this output is stored and shared:
- It’s deterministic. The same tree produces byte-identical geometry every time. No random seeds, no iteration counts, no convergence thresholds — which is what makes the result safe to persist and to hand to different clients.
- Depth maps directly to y.
depth * (NODE_HEIGHT + Y_GAP)means generations are rows. That’s not a coincidence to be grateful for; it’s the reason a hierarchical layout is the right family here rather than a force-directed one.
Edges are precomputed too, as orthogonal elbows — four points from the bottom-center of the parent, out to a midpoint row, across, and into the top-center of the child:
double px = pp[0] + NODE_WIDTH / 2.0, py = pp[1] + NODE_HEIGHT; // parent bottom-center
double cx = cp[0] + NODE_WIDTH / 2.0, cy = cp[1]; // child top-center
double my = (py + cy) / 2.0; // shared midpoint row
updateEdge(parentId, childId, List.of(
new GraphResponse.Position(px, py),
new GraphResponse.Position(px, my),
new GraphResponse.Position(cx, my),
new GraphResponse.Position(cx, cy)
));So the clients never route a line. An edge arrives as a polyline; drawing it is moveTo then lineTo per point. Every geometric decision in the picture was made once, upstream.
Concept: one canvas, and a camera
With geometry arriving precomputed, the client’s job collapses to painting. That makes the per-node-component model the wrong trade: you’re paying for a thousand mounted, styled, individually-tracked elements to display what is really a single picture.
Both clients now draw the whole tree into one surface — Canvas 2D on the web, a CustomPainter in Flutter — under a camera transform:
ctx.translate(vp.x, vp.y);
ctx.scale(vp.scale, vp.scale);That’s the entire panning and zooming implementation. The viewport (vp) holds a translation and a zoom, everything is drawn in world coordinates, and the transform maps world to screen. Panning changes two numbers.
The payoff is that you can now ask a question you couldn’t ask before: what part of the world is on screen? Invert the transform and you have it as a rectangle:
const viewL = -vp.x / vp.scale;
const viewT = -vp.y / vp.scale;
const viewR = viewL + cw / vp.scale;
const viewB = viewT + ch / vp.scale;Culling: draw cost tracks the viewport, not the tree
Given that rectangle, every node gets one cheap rejection test before any drawing happens:
if (nx + metadata.nodeWidth < viewL || nx > viewR ||
ny + metadata.nodeHeight < viewT || ny > viewB) return;Four comparisons to skip a node entirely. Zoomed in on one family, the loop still visits every node but draws maybe twenty — so the expensive part of a frame is proportional to what’s visible, and a tree with 200 people costs the same to render as one with 2000 at the same zoom.
Edges need one extra consideration, and it’s the kind of thing you only find by looking at the result: an edge can be visible while neither of its endpoints is. A line from a parent above the screen to a child below it crosses the viewport, and testing endpoints alone would drop it. So edges are culled on their own bounding box, with padding:
const padding = 500;
if (maxX < viewL - padding || minX > viewR + padding ||
maxY < viewT - padding || minY > viewB + padding) return;The Flutter side precomputes each edge’s bounds once instead of recomputing per frame — the same idea, cached: if (!edge.bounds.overlaps(visibleRect)) continue;.
And since a static tree shouldn’t burn frames, painting is behind a dirty flag: an animation-frame loop runs continuously but only repaints when something actually changed — a pan, a zoom, a newly loaded image.
Concept: three levels of detail
Culling handles “zoomed in.” Zoomed out is the opposite problem: now everything is on screen, and the naive approach draws a thousand rounded cards, a thousand avatar images and a thousand measured, truncated text strings — to produce a picture in which each node is eight pixels wide and none of the text is legible.
The observation is that at low zoom, the most expensive things to draw are the ones carrying the least information. Nobody reads names at 6% zoom; they’re reading the shape of the tree — where the branches are, how deep it goes, which subtree is dense. So detail is tied to zoom, in three tiers:
const lod = isExporting
? "full"
: vp.scale > 0.3
? "full"
: vp.scale > 0.12
? "simple"
: "minimal";full(zoom above 30%) — rounded card, avatar clipped into a circle, name with ellipsis truncation measured against the box width, action affordance.simple(above 12%) — card and border, one centered name string. No images, no per-node measurement.minimal— a filled rectangle, and thinner edge strokes. Nothing else.
if (lod === "minimal") {
ctx.fillRect(nx, ny, metadata.nodeWidth, metadata.nodeHeight);
return;
}That early return is doing a lot of work. It skips a rounded-rect path, a stroke, an image draw, a font set, a text measurement and a fill — per node, for every node on screen, in exactly the regime where the most nodes are on screen. The whole-tree view is the cheapest view to draw rather than the most expensive one.
Text measurement is the sneaky cost, incidentally. measureText in the truncation loop shortens a string one character at a time until it fits — fine for twenty visible cards, not fine for a thousand. Tiering it away at simple matters more than the images do.
Two supporting details in the same spirit: images are cached by URL with a load callback that flips the dirty flag, so a scroll past 50 faces doesn’t re-request anything and a late-arriving image triggers exactly one repaint. And past 20 nodes, a minimap draws the whole tree as dots with a rectangle marking the current viewport — cheap to draw from positions you already have, and it’s what makes navigating a tree far larger than the screen feel bounded.
Both clients use the same thresholds and the same culling maths. Web and mobile are different rendering APIs, but the geometry they consume and the decisions they make about it are identical, which means the tree looks the same on a phone and a laptop.
What you give up, and getting it back
Drawing into a canvas means there are no per-node objects. Nothing to attach a click handler to, nothing to query, nothing the accessibility tree or the browser’s own hit-testing knows about. That’s the real cost of this approach, and it has to be paid back deliberately.
Since positions are stored server-side, both interactions resolve through coordinates. A click is converted from screen space back into world space with the same transform, inverted:
const worldX = (mouseX - vpx) / scale;
const worldY = (mouseY - vpy) / scale;and the person occupying that point is looked up by coordinate. The x-offset within the box even distinguishes a tap on the card from a tap on the action strip beside it:
GetPersonCoordinateResponse.CoordinateType type = GetPersonCoordinateResponse.CoordinateType.NODE;
if (x > (position.getX() + NODE_WIDTH)) type = GetPersonCoordinateResponse.CoordinateType.ACTION;Search works the same way in reverse: a name resolves to a position, and the camera animates there. The client never scans the tree for a match — it asks where to point, then points.
Design note. This trades a round trip per interaction for not maintaining a spatial index in each client. Given that both clients need identical behaviour and the positions are already stored, resolving centrally keeps one implementation instead of three. A client-side quadtree or uniform grid is the alternative if local, zero-latency hit-testing becomes the priority — the positions are all there in the payload to build one from.
Design notes for the next pass
Culling is a linear scan. Every frame iterates all nodes to test four inequalities each. That’s cheap next to drawing, and it kept the code simple, but it’s still O(n) per frame — the part that would matter first on a tree an order of magnitude larger. Bucketing nodes into a coarse grid by position, then visiting only the buckets the viewport touches, turns the scan into a lookup. Worth doing when profiles say the scan, rather than the drawing, is the frame budget.
The LOD thresholds are tuned to the current box size. 0.3 and 0.12 were chosen by zooming until text stopped being readable, against a 250×80 box. A more principled version derives them from the rendered size — switch away from text when cap height falls below ~10 device pixels — which would then hold automatically if node dimensions ever change.
The edge padding is a heuristic. 500 world units comfortably covers the longest elbow at the spacing in use. Deriving it from the maximum edge extent would make it self-adjusting.
Export takes the other path deliberately. Saving a PNG or PDF renders off-screen at full detail regardless of zoom, then scales down to stay inside browser canvas size limits — the one case where you want every name drawn, because the output is meant to be zoomed into later.
What I took away
The idea I keep reusing from this is the split I started with: the tree and the picture of the tree are different artifacts with different lifetimes. Once that was explicit, most of the design followed. Geometry that only changes on edit gets computed once and stored. Geometry the client already has doesn’t need recomputing. Detail nobody can see doesn’t need drawing.
The satisfying part is how the scaling behaviour inverted. Before, every additional person made every view of the tree more expensive for everyone. Now the layout cost is paid once per edit, and the drawing cost is bounded by the size of the screen — which is the one quantity in this whole problem that never grows.