Skip to main content

Crate neco_geometry

Crate neco_geometry 

Source
Expand description

§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

Surface Patches

ChartPatch represents either:

  • A full chart with an optional disk constraint.
  • A trimmed declaration.

DiskConstraint tests exact membership in the closed unit disk.

Borrowed accessors expose:

  • The chart.
  • The domain.
  • The disk constraint.
  • The trimmed declaration.

This capability has no dependency on CAD or GPU crates.

§Numeric encoding

Converts surface patches and seams to finite f32 data and returns their rounding bounds separately. It preserves:

  • Polynomial exponents.
  • Domain closure.
  • Outer and hole vertices.
  • Disk constraints.
  • Orientation.

The main APIs are:

  • encode_chart_patch: Returns numeric patch data and rounding bounds.
  • encode_seam_association: Encodes both seam endpoints with the same conversion.
  • EncodedSeamAssociation: Parameter pairs and orientations in source endpoint order.
  • EncodingPrecision: 1–256 enclosure bits and a finite, nonnegative maximum rounding error.
  • EncodedSurfacePatch: Full or trimmed numeric patch.
  • EncodedCoefficients: Term lists in x, y, z, denominator order.
  • EncodedDomain: Parameter endpoints and closure flags.
  • EncodedTrimRestriction: Outer and hole vertices.
  • EncodingBounds: F32 format and the maximum scalar-rounding bound.
  • EncodingFailure: Precision, range, or lower-operation failure with an input location.

Converts each rational or algebraic enclosure midpoint through f64 to f32, then measures its distance from both endpoints using exact dyadic arithmetic. For a RealAlgebraic value whose candidate lies inside the enclosure, exact equality with the source establishes a zero bound. For the remaining values, it rounds the larger distance upward to f64 and returns the maximum bound once in EncodingBounds.

The caller maps chart identities to its own primitive identifiers.

Consumers propagate rounding bounds through their evaluations and combine them with GPU arithmetic bounds. Encoding runs on the CPU with core and alloc.

§GPU crossing evaluation

The optional gpu feature evaluates ray contacts with affine planes and stereographic spheres with denominator 1 + u² + v². Construct GPU data from an encoded patch and its rounding bounds, then combine numerical evaluation code, crossing code, and the caller’s entry point into one WGSL program.

GpuCrossingSurface::from_encoded: constructs numeric GPU data
GPU_CROSSING_WGSL: supplies crossing and contact WGSL code
NecoGpuSurface / neco_gpu_surface: surface type and function defined by numerical evaluation code
entry point: supplied by the caller

The caller allocates GPU resources and executes the program. Choose the WGSL query for the required result:

  • neco_gpu_surface_bounds: Computes three-dimensional bounds for the surface over the parameter rectangle, including encoding error.

  • neco_gpu_surface_ray_excluded: Returns true for certified ray exclusion. Closed contacts and numerically indeterminate cases remain candidates for contact evaluation.

  • neco_gpu_surface_contact: Returns a residual-checked approximate point candidate after checking parameter-domain inclusion. It handles known double roots and original outer trim edges when the source expression matches the GPU model and the predicates establish the result. Indeterminate predicates remain Unknown.

    Hit / Miss / Unknown / LowerEvaluationFailure
  • neco_gpu_contact_normal: Returns an estimated world-space unit normal from the same primitive and a Hit’s parameters, preserving the chart orientation. Non-Hit inputs, non-finite values, and degenerate differentials yield an unavailable normal.

    NecoGpuContactNormal: direction, valid
    valid: 1 = available, 0 = unavailable
  • neco_gpu_contact_seam_classification: Reads the independent seam proximity classification when a point candidate is available. Contact compares the distance from the candidate to a seam endpoint with the error bounds.

    Off / Contact / Unknown
  • neco_gpu_crossing: Uses the same point calculation and returns an overall Unknown whenever the seam proximity classification is other than off.

§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.

OperationConstraintBehavior on Violation
Intersection ConstructionIteration limit of the root separation settings (depth of bisecting the parameter interval) ≤ 19, subintervals produced by bisection ≤ 65,535Returns GeometryFailure
Boundary DerivationBoundary candidates ≤ 64, intersection sets ≤ 16, candidate parameter values and parameter values for probing both sides of the boundary ≤ 4,096 each per candidateReturns GeometryFailure
Input ValidationRejects 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 TrimThe 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 rejectedReturns GeometryFailure
Ray CrossingThe 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 loopsReturns 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)

Structs§

AlgebraicBoundary
AlgebraicRegion
AtomSignResult
BoundaryAtomLocus
BoundaryBranchEvidence
BoundaryCandidate
BoundaryCandidateSeed
BoundaryCoverageEvidence
BoundaryDerivationRequest
BoundaryIntersectionSelector
BoundaryRestrictionChart
BoundaryRootEvidence
BoundarySideSample
BoundaryStratification
BoundaryStratum
BoundaryTransitionWitness
BoundaryTypes
BranchIdentity
CanonicalAtom
ChartDefinition2
ChartDefinition3
ChartDisplayName
ChartDomainId
CheckedRay2
CheckedRay3
CheckedRay2ParameterRange
CheckedRayCrossingHit
CheckedRayCrossingTargetSet
CheckedRayCrossingWitness
CheckedTriangleTarget
CheckedTrimmedParametricSurfaceTarget
CoincidentSupport
ContactOrder
ConvergenceWitness
CoordinateEnclosure2
CoordinateEnclosure3
CurveBranch
Direction2
Direction3
DiskConstraint
Enclosure
EncodedCoefficients
EncodedDiskConstraint
EncodedDomain
EncodedSeamAssociation
EncodedSurfaceTerm
EncodedTrimRestriction
EncodingBounds
EncodingPrecision
ExactExpressionRequirement
ExactRayCrossingTargetSet
ExactTriangleTarget
ExistenceWitness
GpuCrossingDomain
GpuCrossingPrimitive
GpuCrossingSeam
GpuCrossingSurface
Encoded data for affine planes and rational stereographic spheres with denominator 1 + u² + v². Supports coefficients through 65,536, encoding bounds through 1e-6, domain endpoints in [-1, 1], primitives through 1e6, and ray components through 1e4. Hit denotes an approximate candidate checked by residual and classification tests; Unknown is indeterminate.
GpuCrossingTrim
ImplicitSurfaceDeclaration
IntersectionComponentIdentity
IntersectionComponentIter
IntersectionComponentViewEntry
IntersectionConstraint
IntersectionConstructionRequest
IntersectionConstructionRequestBody
IntersectionCurve
IntersectionDomain
IntersectionEvidenceRef
IntersectionPoint
IntersectionResidual
IntersectionSet
IntersectionWitness
MembershipJudgmentRequest
MultivariatePolynomial3
NecoImplementationSource
OwnerId
PairedSurfaceSeam
ParameterInterval
ParametricCurveDeclaration
ParametricSurfaceChart2
ParametricSurfaceDeclaration
Point2
Point3
PolynomialTerm3
PositiveRayParameterRange
RationalFunction3
RationalFunctionDomain3
Ray2
Ray3
Ray2ParameterRange
RayCrossingHit
RayCrossingPolicy
RayCrossingTargetId
RayCrossingWitness
RealAlgebraic
RegionAffineMap3
RegionConstructionRequest
RegionMembershipRequest
RegionMembershipResult
RegionPolynomial3
RegionPolynomialTerm
RegionTypes
ResidualFunction
ResidualSourceId
RootBracket
RootIsolation
RootIsolationPolicy
SeamEnd
ShapeEvaluationRequest
StratificationEvidence
SurfaceChartIdentity
SurfaceCrossingCandidate
SurfaceParameterDomain
SurfaceParameterPoint
SurfaceTrimLoop2
TrimmedParametricSurfaceTarget
TrimmedSurfaceDeclaration
UniquenessWitness
Vector2
Vector3

Enums§

BoundaryEvidenceSource
BoundaryEvidenceStatus
BoundaryLocalEvidence
BoundaryResource
BoundaryStratumDimension
BoundaryUndeterminedReason
CalculusFailure
CertifiedShapeEvaluation
ChartPatch
CheckedRayCrossingResult
CheckedRayCrossingTarget
CheckedRayEvaluation2
CheckedRayEvaluation3
ComponentEvidenceRef
ContactOrderKind
CrossingContribution
CrossingMultiplicity
CrossingParity
CurveChart
EncodedSurfacePatch
EncodingFailure
EncodingFormat
EncodingLocation
ExactRayCrossingTarget
ExactRayEvaluation2
ExactRayEvaluation3
ExactShapeEvaluation
ExistenceEvidence
GeometryFailure
GpuCrossingClassification
Classifies a ray result; lower evaluation failures remain separate from uncertainty.
GpuCrossingFailure
GpuSeamClassification
IntersectionComponentView
IntersectionEvidenceKind
IntersectionKind
IntersectionOperand
IntersectionUndeterminedReason
MembershipClassification
NormalizedRegionFormula
RankDegeneracyReason
RankEvidence
RankUndeterminedReason
RayCrossingLocation
RayCrossingResult
RayCrossingUndeterminedReason
RayNormal
RayOriginContact
RegionFunction
RegionKind
RegionPoint
ResidualUndeterminedReason
ResidualValue
RootConvergenceStatus
RootEvidence
RootRefinementMethod
RootSign
RootUndeterminedReason
SeamContact
ShapeCoordinate
ShapeCoordinateEnclosure
ShapeDeclaration
ShapeEvaluation
ShapeEvaluationIndeterminacy
ShapeEvaluationInput
ShapeFamily
SignRelation
SupportEvidence
SupportRelation
SupportUndeterminedReason
SurfaceEvaluationWitness
SurfaceOrientation
TrimClassification
TrimLoopRole
UniquenessEvidence
WitnessMethod
WitnessStatus
WitnessUndeterminedReason

Constants§

BOUNDARY_ZERO_EXCLUSION_PRECISION_BITS
GPU_CROSSING_WGSL
Supplies WGSL contact, estimated oriented contact normals, and crossing queries with finite-surface candidates. Candidate bounds enclose the parameter rectangle and its encoding error. Unbounded or unsupported candidate computations preserve the ray for contact evaluation.
MAX_BOUNDARY_CANDIDATE_LOCI
MAX_BOUNDARY_CANDIDATE_PARAMETERS
MAX_BOUNDARY_INTERSECTIONS
MAX_BOUNDARY_SIDE_SAMPLES
MAX_GPU_TRIM_HOLES
MAX_GPU_TRIM_VERTICES
MAX_REGION_CANONICAL_ATOMS
MAX_REGION_EXPONENT_OPERATIONS
MAX_REGION_POLYNOMIAL_TERMS
MAX_ROOT_PARTITION_CELLS
MAX_ROOT_PARTITION_DEPTH

Functions§

construct_intersection
construct_region_types
cross_checked_ray3
cross_ray3
derive_boundary
encode_chart_patch
encode_seam_association
evaluate_checked_ray2
evaluate_checked_ray3
evaluate_ray2
evaluate_ray3
evaluate_shape
evaluate_surface_witness_checked
evaluate_surface_witness_exact

Type Aliases§

AtomSignResultSet
BoundaryCandidateSet
BoundaryStratumSet
BranchIdentityRef
BranchIdentitySet
CanonicalAtomSet
CurveBranchSet
IntersectionEvidenceSet
IntersectionPointSet
MembershipJudgmentResult
NormalizedRegionFormulaSet
RegionPointSet
RegionPolynomialTermSet
RootBracketSet
StringSet