The Mesh Project
HomeArticles
Computational Geometry Structures

The Foundation for High Performance Mesh Processing

Computational geometry is the foundation of modern mesh-processing algorithms. Operations such as intersection testing, spatial hierarchy construction, curvature estimation, and simulation preparation all rely on two core capabilities: precise geometric primitives and efficient spatial data structures.

This article introduces the geometric substrate of TheMeshProject: a minimal, robust, and composable set of structures that supports the higher-level algorithms used throughout the ecosystem.

Why Computational Geometry Matters in CAE

Computer-aided engineering workflows depend on geometric operations that are reliable at scale. These operations must be:

  • Fast — millions of evaluations per second
  • Numerically stable — robust under floating point error
  • Deterministic — consistent across platforms and compilers
  • Composable — usable inside larger pipelines without side effects

These requirements shape the design of TheMeshProject’s geometry layer, which emphasizes:

  • exact or filtered predicates
  • predictable memory layouts
  • separation of geometry vs. topology
  • modular, target based C++ components

Together, these choices create a geometry layer that is mathematically sound, implementation-friendly, and practical for engineering-scale workloads.

Core Geometric Primitives
1. Points, Vectors, and Normals

TheMeshProject represents positions, directions, and orientations with compact, fixed-size mathematical types:

  • basepoint3 (fpoint3/dpoint3) — position in \(\mathbb{R}^3\)
  • basevec3 (fvec3/dvec3) — direction or displacement
  • basevec3 (fvec3/dvec3) — normalized orientation

Common operations include:

  • dot and cross products
  • normalization
  • projections
  • distances and squared distances
  • barycentric coordinates

In performance-critical code, squared distances are preferred because they avoid unnecessary square root operations.

2. Lines, Rays, and Segments

Lines, rays, and segments appear throughout collision detection, ray casting, and mesh-query algorithms.

Common definitions include:

  • line: \(f(x)=ax+b\)
  • ray: \(x \ge 0\)
  • segment: \(x \in [0,1]\)

Key queries:

  • closest point
  • distance to point
  • segment–segment distance
  • intersection tests

Together, these structures provide the backbone for proximity and intersection algorithms.

3. Planes and Half-Spaces

A plane is commonly represented in one of two ways:

  • point + normal
  • normalized coefficients ax+by+cz+d=0

Core operations:

  • signed distance
  • projection
  • side of plane tests
  • clipping

Half-spaces are central to constructive solid geometry, convex decomposition, and mesh-clipping workflows.

4. Triangles and Tetrahedra

Triangles and tetrahedra are the fundamental elements of surface and volume meshes.

For triangles:

  • barycentric coordinates
  • area and normal
  • point in triangle tests
  • triangle–triangle intersection

For tetrahedra:

  • orientation tests
  • volume
  • point in tetrahedron

The associated predicates must be robust because even small numerical errors can cascade into major failures in CAE pipelines.

Spatial Data Structures

Geometric primitives define what can be computed; spatial data structures determine how efficiently those computations scale. In CAE workflows, acceleration structures are essential for keeping large geometric queries practical.

1. Axis Aligned Bounding Boxes (AABB)

Axis-aligned bounding boxes are simple, inexpensive bounding volumes commonly used in broad-phase geometry processing.

Properties:

  • cheap to compute
  • cheap to test
  • ideal for broad phase collision detection

Operations:

  • union
  • intersection
  • expansion
  • surface area heuristic (SAH) cost

Because AABBs are fast to compute and test, they are the basic building blocks of many bounding volume hierarchies.

2. Bounding Volume Hierarchies (BVH)

BVHs accelerate:

  • ray tracing
  • nearest neighbor queries
  • collision detection
  • mesh intersection

TheMeshProject uses a binary, SAH-optimized BVH designed around:

  • tight AABBs
  • cache friendly node layout
  • iterative traversal
  • optional parallel construction

This structure is central to high-performance geometry processing because it reduces the cost of repeated spatial queries.

3. k-d Trees

k-d trees excel at:

  • nearest neighbor search
  • point cloud processing
  • spatial partitioning

Compared with BVHs, k-d trees are:

  • better for point data
  • worse for triangle meshes
  • sensitive to unbalanced distributions

k-d trees will be added to the repository when they are needed in practice. Within TheMeshProject, they are intended primarily for point-based algorithms such as moving least squares surfaces, sampling, and reconstruction.

Exact and Robust Predicates

Floating-point arithmetic can become unreliable when geometric decisions depend on very small differences. Robust predicates reduce this risk by ensuring:

  • correct orientation tests
  • correct intersection tests
  • correct containment tests

To achieve this, TheMeshProject uses:

  • adaptive precision arithmetic
  • filtered predicates
  • epsilon free logic where possible

These techniques are essential for stable, repeatable CAE pipelines.

5. Integration in TheMeshProject

The geometry layer is implemented as a collection of modular C++ components with:

  • clean, minimal APIs
  • predictable performance
  • no hidden global state
  • compatibility with btm framework

These components support a broad range of mesh-processing workflows, including:

  • mesh intersection
  • remeshing
  • curvature estimation
  • segmentation
  • collision detection
  • simulation pre processing

Together, these capabilities make the geometry layer the foundation on which the rest of TheMeshProject is built.

6. What Comes Next

The next articles in this series will build on this foundation:

  • Robust Intersection Tests
  • Spatial Acceleration Structures in Practice
  • Signed Distance Fields and Voxel Geometry
  • Curvature Estimation
  • Mesh–Mesh Proximity and Collision Detection

With the geometric substrate in place, the series can now move toward the higher-level algorithms that rely on it.