neco-geometry 0.2.0

exact shape declarations and evaluation over real algebraic coordinates
Documentation

neco-geometry

日本語

neco-geometry is a crate for evaluation and operations on curves and surfaces with real algebraic coordinates. Evaluation results are exact values or enclosing intervals (intervals guaranteed to contain the exact value).

Features

Shape Declaration and Evaluation

Evaluates declarations of curves and surfaces as exact values or as enclosing intervals.

  • Curves: rational charts (maps that give coordinates as rational functions of a parameter)
  • Parametric surfaces: surfaces whose coordinates are rational functions of two parameters
  • Implicit surfaces: sparse multivariate polynomials

Each enclosing interval carries provenance. The provenance consists of the owner identifier, the evaluation requirement, and the version and public API identifier of the implementation that computed it. The evaluation requirement contains the consumer identifier, the target expressions, the decision request, and the precision. The consumer is the place that receives the result of the evaluation. The decision request specifies which exact decision (zero, equality, sign, or degeneracy) the consumer requests on which of the target expressions (two expressions for equality).

Algebraic Region Classification

Represents regions by sign conditions on functions and logical formulas built from them, and classifies a given point as interior, boundary, or exterior.

Exact Intersection Construction

Constructs intersection sets (points, curves, parts where the two shapes coincide, etc.) from two shapes and root separation settings (a refinement method such as bisection, an iteration limit, and a target interval width). The intersection set is returned with evidence for the existence and uniqueness of the roots.

Boundary Derivation and Split by Dimension

The caller gives boundary candidates for each sign condition of an algebraic region. A candidate consists of a curve given by polynomials (a restriction chart), parameter values on that curve that may be boundary points, and parameter values for probing both sides of the boundary. A candidate can also select, by index, one of the intersection sets (results of intersection construction) that the caller gives to boundary derivation. The crate derives the boundary of the algebraic region by evaluating the function of the sign condition on the curve of each candidate. The derived boundary is split into 0-, 1-, and 2-dimensional parts. When a candidate selects an intersection set, the part derived from that candidate has dimension 0 if the set is points and dimension 1 if it is a curve. A part whose dimension cannot be determined is returned with its reason.

Ray Crossing

Evaluates crossings of a three-dimensional ray with triangles or surfaces over the whole range where the ray parameter is positive.

  • triangles
  • trimmed parametric surfaces (surfaces whose parameter domain is limited by polygonal trim loops for the outer boundary and holes)
  • implicit surfaces

The evaluation always returns the origin contact and the hits, and it returns the crossing parity when the result is determined, or the undetermined reason when the result is undetermined.

  • Origin contact: whether the ray origin lies in the interior or on the boundary of a target
  • Crossing parity: whether the number of crossings is even or odd
  • Hits: the ordered sequence of hits
  • Undetermined reason: the typed reason returned when the result is undetermined

Specifications and Constraints

Constraints are set to keep operations reliable and to limit the consumption of computational resources. Their values are the same in every execution environment.

Operation Constraint Behavior on Violation
Intersection Construction Iteration limit of the root separation settings (depth of bisecting the parameter interval) ≤ 19, subintervals produced by bisection ≤ 65,535 Returns GeometryFailure
Boundary Derivation Boundary candidates ≤ 64, intersection sets ≤ 16, candidate parameter values and parameter values for probing both sides of the boundary ≤ 4,096 each per candidate Returns GeometryFailure
Input Validation Rejects invalid intervals, polynomials with duplicate or zero-coefficient terms, invalid dimensions, invalid logical formulas for regions, and invalid settings (such as root separation settings) Rejected at construction, or returned as a typed GeometryFailure
Surface Chart and Trim The denominator polynomial has at least one term; each trim loop has at least 3 vertices inside the parameter domain; self-intersecting loops and hole loops that intersect the outer loop are rejected Returns GeometryFailure
Ray Crossing The parameter range is all positive values; caller-declared limits on targets and hits; rejection of degenerate triangles (collinear vertices or non-finite vertices) and invalid trim loops Returns a typed failure or an undetermined result

Runtime Configuration

The default configuration uses the standard library.

[dependencies]
neco-geometry = "0.2"

Disabling the default std feature leaves dynamic memory allocation as the only runtime requirement, so the crate can be used in environments without the standard library. Returned values and failures have the same meaning as in the default configuration.

[dependencies]
neco-geometry = { version = "0.2", default-features = false }

Dependencies

License

MIT License (see the repository LICENSE for details)