Computational Geometry Resources

26 January 2026

A little while back, I got introduced to the wondrous world of Computational Geometry. This is a branch of computer science that concerns itself with data structures and algorithms for geometric problems.

Throughout the last year I’ve read numerous papers and books that helped me understand the field, and gave me the right handles for building a 3D modeling application.

Books are useful for building a strong foundation. Papers are useful for learning about the cutting edge and novel techniques.

Note that this document is a work-in-progress and I’ll occasionally add content to it.

Data structures #

Spatial Indexing #

Spatial indexing data structures solve a simple problem; improving the time complexity of spatial queries.

Let’s say we have a list of bounding boxes in N-dimensional space. For this list, I want to get all pairs of boxes that intersect with each other. The naive implementation would look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// returns all intersections between aabb and the provided list of aabbs
std::vector<int> get_intersections(const AABB& aabb, const std::vector<AABB>& aabbs) {
    std::vector<int> out;
    for (int i = 0; i < aabbs.size(); ++i) {
        if (aabbs.intersects_with(aabb[i])) {
            out.emplace_back(i, j);
        }
    }
    return out;
}

This has a time complexity of O(n), which is not ideal in the context of geometric problems, because we’re often dealing with large values for n. With a spatial indexing data structure, we can rewrite the function as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

std::vector<int> get_intersections(const AABB& aabb, const BVH& bvh) {
    // iterate recursively over bvh (using depth-first search)
    std::vector<int> out;
    std::stack<std::reference_wrapper<const BVHNode>> stack;
    stack.emplace(bvh.root());

    while (!stack.empty()) {
        const BVHNode& current = stack.top();
        stack.pop();

        const bool intersects = current.aabb().intersects_with(aabb);
        if (!intersects) {
            continue;
        }

        if (current.is_leaf()) {
            out.emplace_back(current.index());
        } else {
            // internal node, add children
            for (const BVHNode& child : current.children()) {
                stack.emplace(child);
            }
        }
    }
    return out;
}

While this might look intimidating, the amount of computation is drastically reduced, because we’re ignoring large amounts of bounding boxes when traversing the tree. Traversal is done using depth-first search (DFS).

Bounding volume hierarchy (BVH) #

RTree #

Spatial hash #

Octree #

VDB #

Mesh graph and boundary representation (BRep) #

Half Edge #

Winged Edge #

Partial Entity #

Algorithms #

Earcut and polygon triangulation #

Boolean operations #

Concepts #

Axis-aligned bounding box (AABB) #

Robustness #

Morton encoding #

Homogeneous integer coordinates #

CAD #

Surfaces #

Non-uniform rational B-splines (NURBS) #

Analytical surfaces (spherical) #

Topology #

Algorithms #

Unsorted #

Websites #

Books #

Papers #

Open-source repositories #