Computational Geometry Structures
TheMeshProject — Foundations 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.
1. 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.
2. Core Geometric Primitives
2.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.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.
2.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.
2.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.
3. 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.
3.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.
3.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.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.
4. 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.