marcinfinitesimal533 Computational Geometry for AEC
This skill encapsulates the full breadth of computational geometry knowledge required for architecture, engineering, and construction workflows. It covers fundamental primitives, advanced surface mathematics, mesh processing, tessellation strategies, point cloud pipelines, and the precise tolerance management that separates prototype-grade geometry from fabrication-ready output.
1. Geometry Type Hierarchy
Every computational design system is built on a layered hierarchy of geometric types. Understanding the properties, capabilities, and conversion paths of each type is essential for selecting the right representation at every stage of a project.
1.1 Points, Vectors, Planes, Frames
Point (Point3d)
- Definition: A dimensionless location in 3D Euclidean space defined by (x, y, z) coordinates.
- Properties: No length, area, or volume. Carries only positional information.
- AEC use cases: Survey control points, grid intersections, insertion points for components, structural node locations, sensor positions.
- Conversion: A point can seed any higher-order geometry. Points become curve control points, mesh vertices, or centroid markers.
Vector (Vector3d)
- Definition: A direction and magnitude in 3D space, defined by (x, y, z) components. Unlike a point, a vector has no fixed position.
- Properties: Magnitude (length), direction (unit vector). Supports dot product, cross product, angle computation, projection.
- AEC use cases: Wind direction encoding, structural force vectors, surface normals for solar analysis, movement direction for pedestrian simulation, facade orientation vectors.
- Key operations: Normalize, scale, add, subtract, dot product (scalar projection), cross product (perpendicular vector), angle between vectors, reflection, rotation.
Plane
- Definition: An infinite flat surface defined by an origin point and a normal vector, or equivalently by an origin and two in-plane axes (X-axis, Y-axis) with the normal as Z-axis.
- Properties: Origin, Normal, XAxis, YAxis. Divides space into two half-spaces.
- AEC use cases: Floor levels, section cut planes, mirror planes for symmetric designs, construction planes for drawing, reference datums.
- Conversion: Planes can generate planar surfaces, serve as projection targets, or define local coordinate systems.
Frame
- Definition: A right-handed orthonormal coordinate system defined by an origin point and three mutually perpendicular unit vectors (X, Y, Z).
- Properties: Origin, XAxis, YAxis, ZAxis. Fully defines position and orientation.
- AEC use cases: Structural member local axes, robotic fabrication tool frames, camera positions for rendering, element insertion frames, joint coordinate systems.
- Distinction from Plane: A frame carries full rotational information (three axes), while a plane is defined by only one axis (the normal) plus a rotation ambiguity around that normal.
1.2 Curves
Line
- Definition: The shortest path between two points; a degree-1 NURBS curve with two control points.
- Properties: Start point, end point, length, midpoint, direction vector.
- AEC use cases: Grid lines, structural member centerlines, dimension lines, sight lines, setback lines.
- Conversion: Can be treated as a degree-1 NURBS curve, a polyline with two vertices, or a mesh edge.
Polyline
- Definition: A connected sequence of line segments defined by an ordered list of vertices.
- Properties: Vertex list, segment count, total length, is-closed flag, bounding box.
- AEC use cases: Property boundaries, road centerlines, building footprints, pipe routes, cable tray paths, simplified contour lines.
- Conversion: Each segment is a line. The entire polyline can be degree-elevated to a NURBS curve. Can be used as a mesh wireframe or triangulated polygon boundary.
Arc
- Definition: A portion of a circle defined by center, radius, start angle, and end angle (or equivalently by three points).
- Properties: Center, radius, start/end angles, arc length, start/end points, midpoint.
- AEC use cases: Curved walls, arch profiles, fillet transitions, roundabout geometry, curved beam profiles.
- Conversion: Can be represented exactly as a rational NURBS curve of degree 2 (using weights).
Circle
- Definition: A closed planar curve where every point is equidistant from the center. A special case of an arc (360 degrees) and of an ellipse (equal radii).
- Properties: Center, radius, plane, circumference, area.
- AEC use cases: Column cross-sections, roundabouts, circular openings, pipe profiles, rotunda plans.
- Conversion: Exactly representable as a rational NURBS curve of degree 2 with specific weights. Can be approximated by a polygon with n vertices.
Ellipse
- Definition: A closed planar curve defined by a center, two perpendicular semi-axes of different lengths.
- Properties: Center, semi-major axis (a), semi-minor axis (b), plane, eccentricity, perimeter (approximation), area.
- AEC use cases: Elliptical domes, stadium plans, oval windows, landscape features, acoustic reflectors.
- Conversion: Exactly representable as a rational NURBS curve. Can be approximated by a polyline or polygon.
NURBS Curve
- Definition: Non-Uniform Rational B-Spline curve defined by degree, control points, knot vector, and weights.
- Properties: Degree, control point count, knot vector, domain, length, is-closed, is-periodic, continuity.
- AEC use cases: Freeform facades, road alignments with complex geometry, landscape contours, furniture profiles, any smooth curved design element.
- Conversion: The universal curve representation. All other curve types can be expressed as NURBS curves. Can be approximated by a polyline (tessellated) for meshing or CNC output.
Polycurve (Composite Curve)
- Definition: An ordered sequence of connected curve segments that may include lines, arcs, and NURBS spans joined end-to-end.
- Properties: Segment list, total length, is-closed, continuity at joints (G0 minimum).
- AEC use cases: Road alignments (tangent-spiral-arc-spiral-tangent), building outlines mixing straight and curved edges, complex trim boundaries, rail profiles.
- Conversion: Can be rebuilt as a single NURBS curve (with potential continuity loss at joints). Each segment retains its native type.
1.3 Surfaces
Planar Surface
- Definition: A flat, bounded region of a plane defined by one or more closed boundary curves (outer boundary plus optional holes).
- Properties: Plane, area, centroid, boundary curves, perimeter.
- AEC use cases: Floor slabs, wall faces, ceiling panels, glass panes, site boundaries.
- Conversion: Trivially meshable. Representable as a degree-1 NURBS surface.
NURBS Surface
- Definition: A bi-parametric surface defined by a grid of control points, degrees in U and V directions, knot vectors in U and V, and weights.
- Properties: Degree U/V, control point grid (rows x cols), domain U/V, is-closed in U/V, is-trimmed, area, centroid.
- AEC use cases: Freeform facades, shell roofs, landscape terrain patches, furniture surfaces, ship hull forms.
- Conversion: Can be tessellated into a mesh. Can be trimmed, split, or joined with other surfaces.
Extrusion Surface
- Definition: A surface generated by sweeping a profile curve along a straight direction vector.
- Properties: Profile curve, direction vector, is-capped, length.
- AEC use cases: Walls, columns, mullions, linear structural members, ducting, pipe runs.
- Conversion: A special case of a sweep along a line. Representable as a NURBS surface or mesh.
Surface of Revolution
- Definition: A surface generated by rotating a profile curve around an axis.
- Properties: Profile curve, axis (point + direction), angle range, is-full-revolution.
- AEC use cases: Domes, columns with entasis, vases, cooling towers, rotational decorative elements.
- Conversion: Representable as a rational NURBS surface. Can be tessellated into a mesh.
Lofted Surface
- Definition: A surface interpolating or approximating a series of cross-section curves.
- Properties: Section curves, loft type (normal, loose, tight, uniform, closed), rebuild options.
- AEC use cases: Towers with varying floor plates, bridge decks, transition pieces between different profiles, terrain ribbons.
- Conversion: Results in a NURBS surface. Quality depends on curve compatibility (matching point counts and parameterization).
Swept Surface
- Definition: A surface generated by sweeping a profile curve along one or two rail curves.
- Properties: Profile curve(s), rail curve(s), sweep type, alignment options.
- AEC use cases: Handrails, cornices, moldings, highway guardrails, complex facade bands.
- Conversion: Results in a NURBS surface. Two-rail sweeps provide more geometric control than single-rail.
Pipe Surface
- Definition: A surface generated by sweeping a circular cross-section along a rail curve with specified radius.
- Properties: Rail curve, radius (or variable radii), cap type.
- AEC use cases: Structural tubes, piping systems, handrails, cable-stayed bridge cables, conduit runs.
- Conversion: A special case of a swept surface with circular profile. Representable as NURBS or mesh.
1.4 Solids
Brep (Boundary Representation)
- Definition: A solid defined by its bounding surfaces (faces), edges, and vertices, with topological connectivity information.
- Properties: Face list, edge list, vertex list, is-solid (closed), is-manifold, volume, centroid, surface area, Euler characteristic.
- AEC use cases: Building massing models, structural elements, MEP components, furniture, any volumetric design element requiring boolean operations.
- Conversion: Can be meshed for analysis or rendering. Can be sectioned to produce curves. Individual faces are surfaces.
Extrusion Solid
- Definition: A closed solid generated by extruding a closed planar curve along a direction, with top and bottom caps.
- Properties: Profile curve, direction, height, volume, surface area.
- AEC use cases: Columns, walls (prismatic), floor slabs, simple massing volumes, extruded structural profiles (I-beam, channel, angle).
- Conversion: A special case of Brep. Can be converted to mesh.
Boolean Result Solid
- Definition: A solid resulting from CSG (Constructive Solid Geometry) operations (union, difference, intersection) between two or more solids.
- Properties: Inherits Brep properties. Topology may be complex with many faces and edges depending on the intersection geometry.
- AEC use cases: Wall openings (difference), merged building volumes (union), spatial overlap analysis (intersection), complex façade panel geometries.
- Conversion: Standard Brep after boolean resolution. May require cleanup (merge coplanar faces, remove micro-edges).
1.5 Meshes
Triangular Mesh (Tri-mesh)
- Definition: A mesh composed entirely of triangular faces. Each face is defined by three vertex indices.
- Properties: Vertex count, face count, edge count, is-manifold, is-closed, surface area, volume (if closed), Euler characteristic.
- AEC use cases: FEA (finite element analysis) discretization, 3D printing, terrain surfaces (TIN), real-time visualization, photogrammetry output.
- Conversion: Universal mesh format. All other mesh types can be triangulated. Cannot directly convert to smooth NURBS without fitting.
Quadrilateral Mesh (Quad-mesh)
- Definition: A mesh composed entirely of four-sided faces. Each face is defined by four vertex indices.
- Properties: Same as tri-mesh plus: face planarity deviation, edge alignment quality.
- AEC use cases: Facade panelization (flat quads preferred for glass), structural shell analysis, subdivision surface base meshes, textile/fabric patterns.
- Conversion: Each quad can be split into two triangles. Quads can be derived from NURBS surface isoparm sampling.
Ngon Mesh
- Definition: A mesh allowing faces with any number of vertices (3, 4, 5, or more sides per face).
- Properties: Same as other meshes plus: maximum face valence, face planarity metrics.
- AEC use cases: Voronoi-based facade panels, organic surface panelization, architectural geometries where non-standard face shapes are acceptable.
- Conversion: Any ngon face can be triangulated by fan or ear-clipping methods.
Subdivision Mesh
- Definition: A coarse control mesh that defines a smooth limit surface via recursive subdivision rules (Catmull-Clark, Loop, Doo-Sabin).
- Properties: Control mesh, subdivision level, limit surface, crease edges, corner vertices.
- AEC use cases: Organic architectural forms, furniture design, smooth transitions between geometric elements, concept modeling.
- Conversion: At any subdivision level, the result is a standard mesh. The limit surface can be approximated by sufficient subdivision levels.
1.6 Other Geometric Types
Point Cloud
- Definition: An unstructured collection of points in 3D space, typically with associated attributes (color, intensity, normal, classification).
- Properties: Point count, bounding box, density, attributes per point.
- AEC use cases: As-built documentation, heritage preservation scanning, site survey, construction progress monitoring, clash detection against design models.
- Conversion: Can be meshed (Poisson, ball-pivoting, alpha shapes). Can be segmented and fitted with geometric primitives. Cannot directly become NURBS without reconstruction.
Voxels
- Definition: Volumetric pixels; a 3D grid of cubic cells, each storing a value (occupied/empty, density, material, temperature).
- Properties: Grid resolution (nx, ny, nz), voxel size, total volume, memory footprint.
- AEC use cases: Solar radiation analysis (volumetric irradiance), wind comfort studies (CFD grids), 3D printing slicing, structural topology optimization, spatial analysis (occupancy, visibility).
- Conversion: Voxel boundaries can be extracted as meshes (marching cubes algorithm). Voxels can be derived from mesh or Brep by spatial sampling.
2. NURBS Deep Dive
2.1 NURBS Curves
NURBS (Non-Uniform Rational B-Spline) curves are the industry-standard representation for freeform curves in CAD systems. They unify lines, arcs, circles, conics, and freeform curves under a single mathematical framework.
Degree and Order
- Degree (p): The polynomial degree of the basis functions. Common values: 1 (linear/polyline), 2 (conic sections, arcs), 3 (cubic, most common for freeform), 5 (automotive/aerospace).
- Order (k): k = p + 1. A cubic curve has order 4.
- Higher degree = smoother curve but more computational cost, potential oscillation, and harder to control locally.
- Degree 3 (cubic) is the workhorse of AEC: sufficient smoothness for architectural curves, good local control, efficient computation.
Control Points
- Control points define the shape of the curve. The curve does not generally pass through interior control points (except at endpoints for clamped curves).
- Minimum number of control points: degree + 1 (e.g., 4 for cubic).
- Moving a control point affects only a local region of the curve (local support property).
- More control points = more local control but more complex management.
Knot Vector
- An ordered sequence of non-decreasing parameter values that define where each basis function is active.
- Length of knot vector: n + p + 1, where n = number of control points, p = degree.
- Clamped (open) knot vectors: First and last knot values repeated p+1 times, forcing the curve through the first and last control points.
- Uniform knot vectors: Interior knots are equally spaced.
- Non-uniform: Interior knots at arbitrary spacing, allowing variable parameterization.
- Knot multiplicity: Repeating an interior knot reduces continuity at that parameter. Multiplicity = p creates a sharp corner (C0 only).
Weights
- Each control point has an associated weight (w_i). When all weights are equal, the curve is a non-rational B-spline.
- Rational NURBS (weights != 1) can exactly represent conic sections: circles, ellipses, hyperbolas, parabolas.
- Increasing a weight pulls the curve toward that control point; decreasing pushes it away.
- Weight of 1.0 is standard. For a circular arc of 90 degrees, the corner control point has weight sqrt(2)/2 ~ 0.7071.
Continuity
- G0 (Geometric positional): Curves share an endpoint. No smoothness guarantee.
- G1 (Geometric tangent): Curves share an endpoint and have the same tangent direction (but potentially different speeds/magnitudes).
- G2 (Geometric curvature): G1 plus matching curvature magnitude. Produces visually smooth transitions with no curvature discontinuity.
- G3 (Geometric torsion): G2 plus matching rate of curvature change. Used in high-end automotive and aerospace surfaces.
- C0, C1, C2, C3 (parametric continuity): Stricter than geometric continuity. C1 requires matching tangent vectors (same direction AND magnitude).
2.2 Curve Operations
| Operation | Description | AEC Application |
|---|---|---|
| Evaluate | Compute point at parameter t | Query any position along a road alignment |
| Tangent | Unit tangent vector at parameter t | Structural member orientation along curved path |
| Curvature | Curvature value and center at t | Identify tight bends in road design for safety |
| Division | Split curve at equal lengths/parameters/counts | Place equally spaced facade mullions |
| Offset | Parallel curve at distance d | Generate wall inner/outer faces from centerline |
| Fillet | Round corner between two curves | Smooth transitions at corridor junctions |
| Chamfer | Straight-cut corner between curves | Beveled edges on structural elements |
| Extend | Lengthen curve beyond endpoint | Extend a property line to intersection |
| Trim | Remove portion of curve at intersection | Cut curves at building footprint boundary |
| Split | Divide curve at parameter(s) | Break road alignment at intersection points |
| Join | Combine end-to-end curves into one | Assemble complex boundary from segments |
| Rebuild | Refit curve with new degree/point count | Simplify scanned data curve for clean geometry |
| Fit | Create curve through a set of points | Generate road alignment from survey points |
2.3 NURBS Surfaces
Degree in U and V
- NURBS surfaces have independent degrees in U and V directions.
- Common: degree 3 in both directions (bi-cubic).
- Can be asymmetric: degree 1 in U (ruled surface) and degree 3 in V.
Control Point Grid
- Arranged in an (m x n) grid where m = points in U direction, n = points in V direction.
- Surface shape is controlled by moving grid points.
- Local support: moving one control point affects only a local patch of the surface.
Isocurves (Isoparametric Curves)
- Curves on the surface at constant U or constant V parameter values.
- Useful for visualizing surface shape, generating panelization grids, and extracting section curves.
- Isocurve density can indicate surface curvature variation.
Trimmed vs. Untrimmed Surfaces
- Untrimmed: The surface exists over its full U-V domain. Boundary is defined by the domain edges.
- Trimmed: The visible boundary is defined by trim curves (2D curves in UV space + 3D edge curves). The underlying surface extends beyond the trim boundary.
- Trimmed surfaces are extremely common in AEC: any time a surface is cut, split, or bounded by non-rectangular boundaries.
- Trimmed surfaces can cause meshing difficulties and analysis inaccuracies if trim curves are not well-defined.
2.4 Surface Operations
| Operation | Description | AEC Application |
|---|---|---|
| Evaluate | Point + normal at (u,v) | Place elements on a freeform facade |
| Normal | Surface normal vector at (u,v) | Determine panel orientation for solar analysis |
| Gaussian Curvature | K = k1 * k2 at (u,v) | Identify regions requiring double-curved panels (K != 0) |
| Mean Curvature | H = (k1+k2)/2 at (u,v) | Detect minimal surface regions (H = 0) |
| Principal Curvatures | k1, k2 and their directions | Orient panelization grid along principal curvature lines |
| Offset | New surface at constant distance | Generate inner/outer shell surfaces |
| Extend | Lengthen surface beyond edge | Extend roof surface past wall line |
| Trim | Cut surface with curves/surfaces | Create openings in facade surface |
| Split | Divide surface at isocurves or cutting geometry | Segment facade into zones |
| Join | Combine adjacent surfaces | Assemble polysurface from patches |
| Rebuild | Refit with new degree/point counts | Simplify scanned-data surface |
| Isotrim | Extract sub-surface at UV interval | Extract individual panels from surface grid |
2.5 Surface Creation Methods
Loft
- Interpolates a surface through a set of section curves.
- Curves should have compatible directions and similar point counts for best results.
- Loft types: Normal, Loose, Tight, Straight (ruled between sections).
- AEC: Tower massing with varying floor plates, bridge deck surfaces, transition geometry.
Sweep 1-Rail
- Sweeps a profile curve along a single rail curve.
- Profile orientation options: freeform, roadlike (profile stays vertical), maintain height.
- AEC: Cornices, handrails, extruded mullion profiles along curved paths.
Sweep 2-Rail
- Sweeps one or more profile curves along two rail curves, scaling the profile to match rail separation.
- Provides more control than 1-rail sweep over surface width and shape variation.
- AEC: Variable-width soffits, tapered structural members, curved curtain wall bands.
Network Surface
- Creates a surface from a network of intersecting curves (U-curves and V-curves).
- Produces higher-quality surfaces than loft when curves in both directions are available.
- AEC: Complex facade surfaces defined by structural grid curves, boat hull forms.
Patch
- Fits a surface to a collection of points, curves, and/or edges as boundary conditions.
- Useful for filling gaps and creating surfaces from irregular boundary conditions.
- AEC: Terrain surface patches, infill surfaces for complex roof geometries, repair of scan data gaps.
Edge Surface
- Creates a surface from 2, 3, or 4 boundary edge curves.
- Simplest method for creating surfaces from boundary curves.
- AEC: Infill panels between structural members, simple canopy surfaces.
Revolve
- Rotates a profile curve around an axis to create a surface of revolution.
- AEC: Dome surfaces, circular columns with entasis, rotunda walls, decorative elements.
Extrude
- Moves a curve along a direction vector to create a ruled surface.
- AEC: Wall surfaces from plan curves, extruded structural profiles, simple facade panels.
2.6 Surface Continuity
| Continuity | Condition | Visual Effect | AEC Requirement |
|---|---|---|---|
| G0 | Shared edge, surfaces touch | Visible crease/edge | Acceptable for panel joints |
| G1 | Matching tangent planes across edge | Smooth shading, no sharp highlight break | Required for smooth facade surfaces |
| G2 | Matching curvature across edge | Perfectly smooth reflections | Required for high-end cladding, automotive-inspired architecture |
2.7 NURBS vs. Mesh Comparison
| Criterion | NURBS | Mesh |
|---|---|---|
| Precision | Mathematically exact, resolution-independent | Approximate, resolution-dependent |
| Memory | Compact for smooth surfaces (few control points) | Can be large (millions of faces for complex forms) |
| Rendering | Requires tessellation for GPU rendering | Directly renderable by GPU |
| Analysis | Exact normals and curvature everywhere | Requires interpolation between vertices |
| Fabrication | Direct CNC tool-path generation | Requires slicing or conversion |
| Boolean Operations | Computationally expensive, tolerance-sensitive | Faster but approximation errors |
| Editing | Intuitive control-point manipulation | Vertex-level editing, sculpting tools |
| Import/Export | STEP, IGES, 3DM | STL, OBJ, FBX, PLY, glTF |
| Best for | Design, documentation, manufacturing | Visualization, analysis, 3D printing, scanning |
3. Boolean Operations (CSG)
3.1 Operation Types
Union (Boolean Add)
- Combines two or more solids into a single solid encompassing the total volume of all inputs.
- Overlapping regions become interior and are removed.
- AEC: Merging building volumes, combining structural elements, assembling composite massing models.
Difference (Boolean Subtract)
- Removes the volume of one solid (tool) from another solid (target).
- The tool solid defines the void; the target retains its exterior minus the intersection.
- AEC: Creating window/door openings in walls, cutting pipe penetrations through slabs, carving atrium voids.
Intersection (Boolean And)
- Retains only the volume shared by two or more solids.
- AEC: Analyzing spatial overlaps (e.g., where two setback volumes intersect), generating connection pieces between structural elements, extracting shared zones.
Split
- Divides a solid into multiple pieces using a cutting surface or solid without removing any material.
- AEC: Splitting a building volume at floor levels, dividing a facade into panels, sectioning terrain.
3.2 Solid vs. Surface Booleans
- Solid booleans operate on closed (watertight) volumes. The result is always a valid closed solid.
- Surface booleans operate on open surfaces. Results may have naked (unbounded) edges and require careful boundary management.
- Solid booleans are more reliable because the inside/outside classification is unambiguous for closed volumes.
- Surface booleans often fail when surfaces are tangent, nearly coincident, or have edges exactly on the splitting surface.
3.3 Common Failures and Troubleshooting
| Problem | Cause | Solution |
|---|---|---|
| Non-manifold edges | Boolean result has edges shared by more than two faces | Increase tolerance, simplify input geometry, split into simpler operations |
| Naked edges | Input geometry is not closed | Ensure all inputs are valid closed Breps before boolean |
| Tolerance mismatch | Input geometries modeled at different tolerances | Standardize document tolerance before boolean |
| Coincident faces | Two faces lie exactly on the same plane | Offset one input slightly (0.001 units), or pre-split at coincident faces |
| Micro-edges/faces | Boolean creates tiny geometric features | Post-process: merge coplanar faces, collapse short edges, remove sliver faces |
| Operation returns empty | Solids do not overlap | Verify intersection exists before performing boolean |
| Wrong piece retained | Difference removes the wrong part | Reverse the order (A minus B vs B minus A), or check solid normals |
3.4 Boolean Operation Order
- Boolean operations are NOT commutative for difference: A - B != B - A.
- Union and intersection ARE commutative: A + B = B + A.
- For complex multi-body booleans, the order of operations can affect both the result and performance.
- Strategy: Perform booleans pairwise, starting with the simplest intersections, and validate at each step.
3.5 Performance Considerations
- Boolean complexity scales with the number of face-face intersections between input solids.
- Planar faces are cheapest; NURBS-NURBS intersections are most expensive.
- Pre-simplify inputs: merge coplanar faces, remove unnecessary detail, reduce control point counts.
- For repetitive booleans (e.g., 500 window openings), consider alternative strategies: split the wall surface rather than boolean each opening individually, or use face-replacement approaches.
- Mesh booleans (libigl, CGAL, Cork) are faster for complex geometry but introduce approximation.
4. Tessellation Methods
4.1 Voronoi Diagrams
2D Voronoi
- Partitions a plane into convex cells, each containing all points closest to one generator (seed) point.
- Cell boundaries are segments of perpendicular bisectors between adjacent generators.
- Properties: Every cell is convex; edges are equidistant from exactly two generators; vertices are equidistant from exactly three generators.
- AEC applications: Facade panel layouts, floor plan partitioning, urban block subdivision, landscape zone design, structural foam/bone-inspired patterns.
3D Voronoi
- Partitions 3D space into convex polyhedral cells.
- Cell faces are planar polygons on perpendicular bisector planes.
- AEC applications: 3D-printed structural lattices, acoustic diffuser geometry, volumetric space partitioning, porous material design.
Weighted Voronoi (Power Diagram / Laguerre Diagram)
- Each generator has an associated weight that controls cell size.
- Higher-weight generators produce larger cells.
- Enables control over cell size distribution while maintaining the Voronoi topology.
- AEC applications: Adaptive facade panels (larger in low-detail areas, smaller near stress concentrations), variable-density space partitioning.
Centroidal Voronoi Tessellation (CVT)
- An iterative refinement (Lloyd's algorithm) where generators are moved to their cell centroids.
- Converges to a tessellation where cells are approximately equal-sized and equilateral.
- Produces highly regular, aesthetically pleasing patterns.
- AEC applications: Regularized facade panels, uniform structural grid generation, even distribution of program zones.
4.2 Delaunay Triangulation
2D Delaunay
- The dual of the 2D Voronoi diagram. Connects generators with edges such that no generator lies inside the circumcircle of any triangle.
- Maximizes the minimum angle of all triangles (avoids sliver triangles).
- Unique for a given set of points (assuming no four co-circular points).
- AEC applications: Terrain TIN (Triangulated Irregular Network) generation, structural triangulated grids, FEA mesh generation.
3D Delaunay
- Tetrahedralization of a point set in 3D, dual to the 3D Voronoi diagram.
- No point lies inside the circumsphere of any tetrahedron.
- AEC applications: Volumetric FEA mesh generation, 3D terrain modeling, structural analysis discretization.
Constrained Delaunay Triangulation (CDT)
- A Delaunay triangulation that includes specified edges (constraints) as triangle edges.
- Ensures boundary conformity: building outlines, road edges, and property lines appear as mesh edges.
- AEC applications: Site plan meshing with boundary conformity, terrain meshing with breaklines (ridges, valleys, retaining walls).
4.3 Convex Hull
- The smallest convex set containing all input points.
- 2D: A convex polygon. 3D: A convex polyhedron.
- Algorithms: Graham scan (2D, O(n log n)), Quickhull (2D/3D), incremental insertion.
- AEC applications: Bounding volume for clash detection, simplified massing envelope, maximum buildable volume from setback points.
4.4 Alpha Shapes
- A generalization of the convex hull controlled by a parameter alpha.
- Alpha = infinity gives the convex hull; smaller alpha values reveal concavities and holes.
- Useful for reconstructing boundaries from unstructured point sets.
- AEC applications: Building footprint extraction from LiDAR point clouds, site boundary detection, as-built outline generation.
4.5 Quad Meshing from NURBS
Isoparm-based
- Sample the NURBS surface at regular U-V intervals to generate a structured quad grid.
- Simple and predictable but produces non-uniform cell sizes on surfaces with non-uniform parameterization.
- Reparameterize the surface first (arc-length parameterization) for more uniform quads.
- AEC: Facade panelization of smooth surfaces, structural grid for shell analysis.
Advancing Front
- Starts from the boundary and progressively fills the interior with quads.
- Produces better-quality quads near boundaries.
- AEC: Structural panel layouts that must respect edge conditions, floor tile patterns.
4.6 Hexagonal Tessellation
- Regular hexagons tile the plane with each cell having six equidistant neighbors.
- Three coordinate systems: offset, cube, axial.
- Hexagonal grids minimize perimeter-to-area ratio among regular tessellations.
- AEC: Facade panel patterns, landscape paving, structural honeycomb cores, acoustic tile layouts.
4.7 Penrose Tiling
- Aperiodic tiling using two tile shapes (kites and darts for P2, or thin and thick rhombi for P3).
- Never repeats but covers the plane completely; exhibits five-fold rotational symmetry.
- Matching rules prevent periodic arrangements.
- Inflation/deflation generates tiles at multiple scales.
- AEC: Decorative floor patterns, facade panel layouts with non-repeating aesthetic, Islamic-geometry-inspired designs.
4.8 Space-Filling Polyhedra
- Polyhedra that tile 3D space without gaps or overlaps.
- Examples: Cube, truncated octahedron, rhombic dodecahedron, gyrobifastigium, and the recently discovered "hat" aperiodic monotile (2D).
- AEC: 3D-printed structural infill, modular space-frame geometries, volumetric subdivision for analysis, acoustic chamber design.
4.9 AEC Tessellation Applications
| Application | Preferred Method | Reasoning |
|---|---|---|
| Facade panelization (flat glass) | Planar quad meshing | Glass panels must be planar; quads minimize waste |
| Facade panelization (decorative) | Voronoi, Penrose | Visual variety, non-repeating patterns |
| Structural diagrid | Delaunay / triangulated quad | Triangles are inherently rigid |
| Floor plan partitioning | Weighted Voronoi | Cell sizes can match programmatic area requirements |
| Terrain modeling | Constrained Delaunay TIN | Respects breaklines, handles irregular point distributions |
| Shell structure analysis mesh | Quad-dominant with boundary conformity | FEA requires quality elements at boundaries |
| 3D printing infill | Hexagonal / gyroid | High strength-to-weight ratio |
| Acoustic panels | Voronoi / Penrose | Non-repeating patterns diffuse sound effectively |
5. Surface Analysis
5.1 Gaussian Curvature (K)
- Definition: K = k1 * k2, the product of the two principal curvatures at a point.
- K > 0 (positive): Synclastic surface (dome, sphere). Both principal curvatures curve in the same direction. Cannot be flattened without stretching/compression.
- K = 0 (zero): Developable surface (cylinder, cone, tangent surface). At least one principal curvature is zero. Can be unrolled flat without distortion.
- K < 0 (negative): Anticlastic surface (saddle, hyperbolic paraboloid). Principal curvatures curve in opposite directions. Cannot be flattened.
Fabrication implications:
- K = 0 panels can be made from flat sheet material (metal, glass, plywood) by bending.
- K != 0 panels require molds, hot-forming, thermoforming, or panelization into smaller approximately-flat pieces.
- Threshold: |K| < tolerance can often be treated as developable for practical purposes.
5.2 Mean Curvature (H)
- Definition: H = (k1 + k2) / 2, the average of the principal curvatures.
- H = 0: Minimal surface (e.g., catenoid, helicoid, soap film). Minimal surfaces minimize area for given boundary conditions.
- H = constant != 0: Constant mean curvature surface (e.g., sphere, cylinder). These surfaces model soap bubbles and capillary surfaces.
- AEC relevance: Minimal surfaces are structurally efficient tension membranes. Constant-H surfaces appear in pneumatic structures.
5.3 Principal Curvatures (k1, k2) and Directions
- At every point on a smooth surface, there exist two orthogonal directions (principal directions) along which curvature is maximized (k1) and minimized (k2).
- k1 >= k2 by convention.
- Points where k1 = k2 are called umbilical points (curvature is the same in all directions, e.g., apex of a sphere).
- Principal curvature lines (integral curves of principal directions) form an orthogonal network on the surface.
- AEC applications: Orienting facade panel grids along principal curvature lines minimizes panel warping. Structural reinforcement can follow principal stress directions (which often align with principal curvature on shells).
5.4 Draft Angle Analysis
- Measures the angle between the surface normal and a specified pull direction (typically vertical for mold extraction).
- Used in manufacturing to ensure parts can be extracted from molds without undercuts.
- AEC relevance: Precast concrete panels need draft angles for mold extraction. Metal facade panels formed on male/female dies require draft analysis.
- Visualization: Color map from 0 degrees (normal parallel to pull direction) to 90 degrees (normal perpendicular).
5.5 Deviation Analysis
- Measures the distance between two surfaces or between a surface and a reference geometry (point cloud, mesh, or another surface).
- Results displayed as a color map with min/max/average/RMS deviation values.
- AEC applications: Comparing as-built scan to design model, quality control of fabricated panels, measuring facade flatness deviation.
- Tolerances: Typical facade panel flatness tolerance is 1-3mm; structural steel is 2-5mm; cast-in-place concrete is 5-15mm.
5.6 Zebra Stripe Analysis
- Projects parallel stripes (simulating a striped environment reflection) onto the surface.
- Reveals surface continuity issues that are invisible in standard shading:
- G0 joints: Stripes break/jump at the edge.
- G1 joints: Stripes are continuous but change direction abruptly (kink in stripe).
- G2 joints: Stripes flow smoothly across the edge.
- AEC applications: Quality-checking facade surfaces, verifying smooth transitions on freeform architecture, ensuring visual smoothness of polished surfaces.
5.7 Environment Map Analysis
- Maps a spherical or cylindrical environment image onto the surface via reflection vectors.
- Similar to zebra analysis but with a more complex pattern that reveals subtler imperfections.
- Used when the surface will be highly reflective (polished metal cladding, glass, water features).
5.8 Curvature Comb
- Displays curvature magnitude as a series of lines (comb teeth) perpendicular to a curve or surface edge.
- Comb height = curvature magnitude. Direction = toward center of curvature.
- Reveals: Curvature discontinuities (sudden jumps in comb height), inflection points (comb crosses the curve), curvature smoothness.
- AEC applications: Evaluating road alignment smoothness, checking facade curve fairness, verifying smooth handrail profiles.
5.9 Visualization Methods
| Method | What It Reveals | Best For |
|---|---|---|
| False-color curvature map | Curvature magnitude distribution | Identifying developable regions, panel rationalization |
| Zebra stripes | Surface continuity (G0/G1/G2) | Checking surface quality for reflective materials |
| Environment map | Surface smoothness and distortion | Polished/glossy facade panels |
| Curvature comb | Curvature profile along a curve | Road alignments, handrail profiles |
| Deviation color map | Distance to reference geometry | As-built vs. design comparison |
| Normal vector display | Surface orientation | Panel orientation, solar angle analysis |
| Isocurve density | Parameterization quality | Identifying surface stretching/compression |
6. Point Cloud Processing
6.1 Acquisition Methods
LiDAR (Light Detection and Ranging)
- Terrestrial laser scanning (TLS): Tripod-mounted scanner, sub-millimeter accuracy, 360-degree capture.
- Mobile laser scanning (MLS): Vehicle or backpack-mounted, covers large areas quickly, centimeter accuracy.
- Aerial LiDAR: Drone or aircraft-mounted, terrain mapping, building roof extraction.
- Typical output: 1-100 million points per scan, XYZ + intensity + return number.
- AEC context: As-built documentation of existing buildings, site surveys, construction monitoring.
Photogrammetry
- Reconstructs 3D geometry from overlapping 2D photographs using Structure from Motion (SfM) and Multi-View Stereo (MVS).
- Produces point clouds with color (RGB) information.
- Accuracy depends on camera quality, overlap, ground control poi
…(truncated)