Module csg 

Constructive solid geometry: box, cylinder and half-space primitives, combined by union, intersection and difference, and the CsgGeometry target built from them.

Solids and regions

A Csg is a tree whose leaves are Primitives and whose inner nodes are Csg::Union, Csg::Intersection and Csg::Difference; the operators nest freely. A CsgGeometry is an ordered list of top-level solids, each tagged with an index into a shared material list. One region per top-level solid, in the order listed. Space outside every solid is vacuum (Geometry::locate returns None).

Ownership rules

These are the rules of the triangle-mesh target, adopted verbatim (see the mesh module docs), so that a CSG solid, the same solid as a mesh and the same solid as a VoxelGrid agree on every shared face.

1. Overlap. Where solids overlap, the first listed solid owns the space, so a mask listed before a substrate cuts into it. No overlap search is needed.
2. Surface points, directional. A flight is owned, at each point, by the solid it is heading into: the state of a solid at the start of a flight is its state at pos + tol * dir. Geometry::locate has no direction; it uses the fixed offset tol * (1, 1, 1) / sqrt(3), so the lower faces (and edges, vertices) of an axis-aligned box belong to it and the upper ones do not, exactly as voxel faces do. Where that offset does not move a point off a surface (a plane containing the diagonal (1, 1, 1)), and for a flight lying exactly in a surface, the point belongs to the side that (1, 1, 1) points into, and for a plane containing the diagonal to the side its normal’s first non-zero component points away from. Each plane thus gives its points to exactly one side.
3. No re-hit. Crossings at t <= tol along the flight are ignored, so a particle that has just crossed a surface and sits on it (to rounding) does not cross it again.
4. Coincident and tangent surfaces. Along a flight every primitive and every boolean node is a sorted list of inside spans (below). At each node, spans no longer than tol are removed and gaps no longer than tol are closed. So a ray that grazes a cylinder or clips a box corner within tol does not enter it; a hole cut flush with a face leaves no sliver; and two boxes united along a shared face are one span with no crossing at the face. Crossings of different top-level solids within tol of each other are one event, so a flight through a surface shared by two solids passes directly from one to the other and never through vacuum between them. This is the CSG form of the mesh rule that two crossings of one solid closer than tol cancel.

The tolerance is tol = 1e-10 x the diagonal of the bounding box of all solids, the same constant as the mesh target (see CsgGeometry::tolerance_m).

Bounded solids

A half-space is unbounded, so it may only appear where a combination bounds it: every top-level solid must have a finite axis-aligned bounding box, otherwise CsgGeometry::new returns GeometryError::CsgUnbounded. Bounds are taken conservatively: a box’s own; a cylinder’s exact box (its end discs, each of which extends r sqrt(1 - a_k^2) along axis k for a unit axis a); a half-space whose normal is a coordinate axis is bounded on that one side, any other is unbounded; a union takes the hull of its operands, an intersection their overlap, a difference the bounds of what it cuts from. So a box cut by an oblique half-space, or six axis-aligned half-spaces intersected, are bounded, but a lone half-space or a union containing one is not. A top-level bounding box that is empty on some axis is rejected as GeometryError::CsgInvalid. The scene bounding box (for tol and Geometry::entry_point) is the hull of the top-level boxes.

Events

As for meshes: Geometry::exit reports Enter { region, pos } when the owner changes to a solid of a different material (a change between solids of the same material is not an event), and Escape when the flight leaves every solid. Geometry::flight is overridden to report the solid a clear flight ends in. The Face of an escape comes from the outward unit normal n of the surface crossed (for the subtracted operand of a difference, its inward normal): Face::Front if n_x is negative and the largest component in magnitude, Face::Back if positive and largest, Face::Side otherwise.

Ray classification

The ray-casting method of S. D. Roth, “Ray casting for modeling solids”, Computer Graphics and Image Processing 18 (1982) 109-144: each primitive is classified along the (whole, unbounded) line of the flight into the parameter spans where the line is inside it, and the span lists are combined up the tree by the set operation of each node. Every span end carries the outward normal of the surface it lies on; a difference negates the normals of the subtracted operand. Here union and difference are built from intersection and complement (A u B is the complement of A' n B', A - B is A n B'), and the rule 4 clean-up is applied at every node. Each primitive is convex, so its classification is a single span:

• Box, axis aligned: the intersection of the three slab intervals of T. L. Kay and J. T. Kajiya, “Ray tracing complex scenes”, Computer Graphics (Proc. SIGGRAPH ’86) 20 (4) (1986) 269-278.
• Cylinder, finite and capped: the slab interval of its two end planes (as for the box) intersected with the interval inside the infinite cylinder, whose ends are the roots of |w + t v|^2 = r^2 (w, v the components of the offset from the base and of the direction normal to the axis). The roots use the cancellation-free form of the quadratic formula, q = -(b + sgn(b) sqrt(b^2 - a c)), t = q / a and t = c / q (W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes, 3rd ed., Cambridge University Press 2007, section 5.6). A tangent line (zero discriminant) does not enter.
• Half-space {p : n . p <= offset}: the half-line on the inside of the plane crossing.

Geometry::locate classifies the offset point directly: a union holds it if any operand does, an intersection if all do, a difference if the first operand does and the second does not.

A flight classifies every primitive of every solid once, so its cost is linear in the total number of primitives. Nothing is cached between queries and no query depends on thread count or evaluation order.

Structs

CsgGeometry

A target of CSG solids, each tagged with a material. See the module docs for the ownership rules.

Enums

Csg

A constructive-solid-geometry tree. See the module docs.

Primitive

One axis-aligned primitive solid. Lengths in metres.