1use alloc::boxed::Box;
2use alloc::format;
3use alloc::string::String;
4use alloc::vec;
5use alloc::vec::Vec;
6use core::cmp::Ordering;
7use core::num::NonZeroUsize;
8
9use neco_algnum::RealAlgebraic;
10use neco_bigint::{BigInt, BigUint, BigintError, Dyadic, RawRational, Sign};
11use neco_calculus::{
12 CalculusFailure, ConvergenceStatus as CalculusConvergenceStatus, DerivativeOrder, Enclosure,
13 ExactExpressionRequirement, NecoImplementationSource, OwnerId, Polynomial, PolynomialFailure,
14 RootBracket as CalculusRootBracket, RootEvidence as CalculusRootEvidence,
15 RootIsolation as CalculusRootIsolation, RootMultiplicity, RootRefinementMethod,
16 SurfacePolynomial,
17};
18use neco_geometry_foundation::{CheckedRay3, Direction3, Point2, Point3, Ray3, Vector3};
19
20use crate::evaluation::{
21 evaluate_shape, evaluate_surface_witness_checked, evaluate_surface_witness_exact,
22};
23use crate::types::{
24 point_on_loop, CertifiedShapeEvaluation, CoordinateEnclosure3, ExactShapeEvaluation,
25 GeometryFailure, ImplicitSurfaceDeclaration, SeamContact, ShapeCoordinate, ShapeDeclaration,
26 ShapeEvaluation, ShapeEvaluationRequest, SurfaceCrossingCandidate, SurfaceEvaluationWitness,
27 SurfaceParameterPoint, TrimClassification,
28};
29
30pub type BranchIdentitySet = Vec<BranchIdentity>;
31pub type CurveBranchSet = Vec<CurveBranch>;
32pub type IntersectionPointSet = Vec<IntersectionPoint>;
33pub type RootBracketSet = Vec<RootBracket>;
34pub type BranchIdentityRef = Option<BranchIdentity>;
35
36#[derive(Debug, Eq, PartialEq)]
37pub struct IntersectionDomain {
38 parameterization: String,
39 restriction: String,
40 support: String,
41}
42
43impl IntersectionDomain {
44 fn new(parameterization: String, restriction: String, support: String) -> Self {
45 Self {
46 parameterization,
47 restriction,
48 support,
49 }
50 }
51
52 pub fn parameterization(&self) -> &str {
53 &self.parameterization
54 }
55
56 pub fn restriction(&self) -> &str {
57 &self.restriction
58 }
59
60 pub fn support(&self) -> &str {
61 &self.support
62 }
63}
64
65#[derive(Debug, Eq, PartialEq)]
66pub struct ResidualFunction {
67 left_expression: String,
68 right_expression: String,
69 combined_expression: String,
70}
71
72impl ResidualFunction {
73 fn new(left_expression: String, right_expression: String) -> Self {
74 let combined_expression = format!("({left_expression}) - ({right_expression})");
75 Self {
76 left_expression,
77 right_expression,
78 combined_expression,
79 }
80 }
81
82 pub fn left_expression(&self) -> &str {
83 &self.left_expression
84 }
85
86 pub fn right_expression(&self) -> &str {
87 &self.right_expression
88 }
89
90 pub fn combined_expression(&self) -> &str {
91 &self.combined_expression
92 }
93}
94
95#[derive(Clone, Copy, Debug, Eq, PartialEq)]
96pub enum SupportEvidence {
97 CanonicalSupportAndChart,
98 CompatibleParametricSupports,
99 DistinctEvaluatedScalars,
100 EqualEvaluatedScalars,
101 EvaluatedSpatialCoordinates,
102 ImplicitSupportPair,
103}
104
105#[derive(Clone, Copy, Debug, Eq, PartialEq)]
106pub enum SupportUndeterminedReason {
107 IncompleteEvaluatedScalar,
108 NoCommonParameterization,
109 UnclassifiedEvidence,
110}
111
112#[derive(Debug, Eq, PartialEq)]
113pub enum SupportRelation {
114 Coincident { evidence: SupportEvidence },
115 Curve { evidence: SupportEvidence },
116 Disjoint { evidence: SupportEvidence },
117 Finite { evidence: SupportEvidence },
118 Undetermined { reason: SupportUndeterminedReason },
119}
120
121#[derive(Clone, Copy, Debug, Eq, PartialEq)]
122pub enum RankDegeneracyReason {
123 InsufficientCommonRank,
124}
125
126#[derive(Clone, Copy, Debug, Eq, PartialEq)]
127pub enum RankUndeterminedReason {
128 SupportRelationUnresolved,
129}
130
131#[derive(Debug, Eq, PartialEq)]
132pub enum RankEvidence {
133 Sufficient { rank: usize },
134 Degenerate { reason: RankDegeneracyReason },
135 Undetermined { reason: RankUndeterminedReason },
136}
137
138#[derive(Clone, Copy, Debug, Eq, PartialEq)]
139pub enum RootSign {
140 Negative,
141 Positive,
142 Zero,
143}
144
145#[derive(Clone, Copy, Debug, Eq, PartialEq)]
146pub enum RootUndeterminedReason {
147 ExactEvidenceUnavailable,
148 ExactMultiplicityUnavailable,
149 SignChangePointUnavailable,
150}
151
152#[derive(Clone, Debug, Eq, PartialEq)]
153pub struct ResidualSourceId(String);
154
155impl ResidualSourceId {
156 fn new(value: &str) -> Self {
157 Self(String::from(value))
158 }
159
160 pub fn as_str(&self) -> &str {
161 &self.0
162 }
163}
164
165#[derive(Debug, Eq, PartialEq)]
166pub enum RootEvidence {
167 SignChange {
168 lower_sign: RootSign,
169 upper_sign: RootSign,
170 derivative_enclosure: Enclosure,
171 source: ResidualSourceId,
172 },
173 EvenMultiplicityTouch {
174 order: usize,
175 point: RealAlgebraic,
176 source: ResidualSourceId,
177 },
178 HigherOrder {
179 order: usize,
180 point: RealAlgebraic,
181 source: ResidualSourceId,
182 },
183 SimpleRoot {
184 point: RealAlgebraic,
185 source: ResidualSourceId,
186 },
187 Undetermined {
188 reason: RootUndeterminedReason,
189 source: ResidualSourceId,
190 },
191}
192
193#[derive(Debug, Eq, PartialEq)]
194pub struct IntersectionConstraint {
195 left_operand: IntersectionOperand,
196 right_operand: IntersectionOperand,
197 residual_function: ResidualFunction,
198 domain: IntersectionDomain,
199 support_relation: SupportRelation,
200 rank_evidence: RankEvidence,
201}
202
203impl IntersectionConstraint {
204 fn new(
205 left_operand: IntersectionOperand,
206 right_operand: IntersectionOperand,
207 residual_function: ResidualFunction,
208 domain: IntersectionDomain,
209 support_relation: SupportRelation,
210 rank_evidence: RankEvidence,
211 ) -> Self {
212 Self {
213 left_operand,
214 right_operand,
215 residual_function,
216 domain,
217 support_relation,
218 rank_evidence,
219 }
220 }
221
222 pub fn left_operand(&self) -> &IntersectionOperand {
223 &self.left_operand
224 }
225
226 pub fn right_operand(&self) -> &IntersectionOperand {
227 &self.right_operand
228 }
229
230 pub fn residual_function(&self) -> &ResidualFunction {
231 &self.residual_function
232 }
233
234 pub fn domain(&self) -> &IntersectionDomain {
235 &self.domain
236 }
237
238 pub fn support_relation(&self) -> &SupportRelation {
239 &self.support_relation
240 }
241
242 pub fn rank_evidence(&self) -> &RankEvidence {
243 &self.rank_evidence
244 }
245
246 fn rank_is_undetermined(&self) -> bool {
247 matches!(
248 self.rank_evidence,
249 RankEvidence::Degenerate { .. } | RankEvidence::Undetermined { .. }
250 )
251 }
252}
253
254#[derive(Clone, Copy, Debug, Eq, PartialEq)]
255enum OperandSource {
256 Declaration,
257 Evaluated,
258}
259
260#[derive(Debug, Eq, PartialEq)]
261struct OperandDescriptor {
262 source: OperandSource,
263 family: crate::types::ShapeFamily,
264 support_id: String,
265 chart_id: String,
266 domain: String,
267 parameter_bounds: Option<(RealAlgebraic, RealAlgebraic)>,
268 expression: String,
269 polynomial: Option<Polynomial>,
270 exact_scalar: Option<RealAlgebraic>,
271 exact_point: Option<Point3>,
272 certified_scalar: Option<(
273 Enclosure,
274 OwnerId,
275 ExactExpressionRequirement,
276 NecoImplementationSource,
277 )>,
278}
279
280#[derive(Debug, Eq, PartialEq)]
281struct DerivedRootProblem {
282 constraint: IntersectionConstraint,
283 polynomial: Option<Polynomial>,
284 domain: Option<Enclosure>,
285}
286
287type PartitionCellId = usize;
288
289#[derive(Debug, Eq, PartialEq)]
290struct PartitionCell {
291 id: PartitionCellId,
292 depth: usize,
293 enclosure: Enclosure,
294 disposition: CellDisposition,
295}
296
297#[derive(Debug, Eq, PartialEq)]
298enum CellDisposition {
299 Candidate,
300 Coincident,
301 RootFree,
302 Unresolved { reason: PartitionUnresolvedReason },
303}
304
305#[derive(Debug, Eq, PartialEq)]
306enum RootCandidateBracket {
307 Exact { parameter: RealAlgebraic },
308 Certified(CalculusRootBracket),
309 Unresolved { enclosure: Enclosure },
310}
311
312#[derive(Debug, Eq, PartialEq)]
313struct RootCandidate {
314 bracket: RootCandidateBracket,
315 evidence: RootEvidence,
316 source_cell: PartitionCellId,
317}
318
319#[derive(Debug, Eq, PartialEq)]
320struct RootEnumeration {
321 candidates: Vec<RootCandidate>,
322 cells: Vec<PartitionCell>,
323}
324
325impl RootEnumeration {
326 fn incomplete(domain: Option<&Enclosure>) -> Self {
327 let cells = domain
328 .and_then(|enclosure| {
329 Some(vec![PartitionCell {
330 id: 0,
331 depth: 0,
332 enclosure: clone_enclosure(enclosure).ok()?,
333 disposition: CellDisposition::Unresolved {
334 reason: PartitionUnresolvedReason::DomainUnavailable,
335 },
336 }])
337 })
338 .unwrap_or_default();
339 Self {
340 candidates: Vec::new(),
341 cells,
342 }
343 }
344}
345
346type RootCandidateSet = RootEnumeration;
347
348#[derive(Clone, Copy, Debug, Eq, PartialEq)]
349enum PartitionUnresolvedReason {
350 DomainUnavailable,
351 MultipleExactDyadicRoots,
352 SignChangeUniqueness,
353 UncertifiedRoot,
354}
355
356enum CellAssessment {
357 Candidate(Vec<RootCandidate>),
358 ExactTouch {
359 candidate: Box<RootCandidate>,
360 pivot: Dyadic,
361 },
362 RootFree,
363 Unresolved(PartitionUnresolvedReason),
364}
365
366struct PendingPartitionCell {
367 id: PartitionCellId,
368 depth: usize,
369 enclosure: Enclosure,
370 suppressed_exact_endpoints: Vec<Dyadic>,
371}
372
373const ROOT_INTERVAL_PRECISION_BITS: u32 = 32;
374pub const MAX_ROOT_PARTITION_DEPTH: usize = 19;
375pub const MAX_ROOT_PARTITION_CELLS: usize = 65_535;
376
377fn partition_cells_for_depth(depth: usize) -> usize {
378 1usize
379 .checked_shl((depth + 1) as u32)
380 .and_then(|value| value.checked_sub(1))
381 .unwrap_or(MAX_ROOT_PARTITION_CELLS)
382 .min(MAX_ROOT_PARTITION_CELLS)
383}
384
385fn ensure_partition_cell_capacity(
386 completed_cells: usize,
387 pending_cells: usize,
388 child_cells: usize,
389 maximum_cells: usize,
390) -> Result<(), GeometryFailure> {
391 let requested_cells = completed_cells
392 .checked_add(pending_cells)
393 .and_then(|value| value.checked_add(child_cells))
394 .ok_or(GeometryFailure::RootPartitionIdentifierOverflow {
395 current_identifier: usize::MAX,
396 increment: child_cells,
397 })?;
398 if requested_cells > maximum_cells {
399 return Err(GeometryFailure::RootPartitionCellLimit {
400 requested_cells,
401 maximum_cells,
402 });
403 }
404 Ok(())
405}
406
407fn take_partition_cell_id(next_cell_id: &mut usize) -> Result<usize, GeometryFailure> {
408 let current_identifier = *next_cell_id;
409 *next_cell_id = current_identifier.checked_add(1).ok_or(
410 GeometryFailure::RootPartitionIdentifierOverflow {
411 current_identifier,
412 increment: 1,
413 },
414 )?;
415 Ok(current_identifier)
416}
417
418#[derive(Debug, Eq, PartialEq)]
419pub struct RootIsolation {
420 brackets: RootBracketSet,
421 completeness: ExistenceWitness,
422 method: RootRefinementMethod,
423 source_domain: IntersectionDomain,
424 source_function: ResidualFunction,
425 non_overlap: UniquenessWitness,
426}
427
428impl RootIsolation {
429 fn new(
430 brackets: RootBracketSet,
431 completeness: ExistenceWitness,
432 method: RootRefinementMethod,
433 source_domain: IntersectionDomain,
434 source_function: ResidualFunction,
435 non_overlap: UniquenessWitness,
436 ) -> Self {
437 Self {
438 brackets,
439 completeness,
440 method,
441 source_domain,
442 source_function,
443 non_overlap,
444 }
445 }
446
447 pub fn brackets(&self) -> &[RootBracket] {
448 &self.brackets
449 }
450
451 pub fn completeness(&self) -> &ExistenceWitness {
452 &self.completeness
453 }
454
455 pub fn method(&self) -> RootRefinementMethod {
456 self.method
457 }
458
459 pub fn source_domain(&self) -> &IntersectionDomain {
460 &self.source_domain
461 }
462
463 pub fn source_function(&self) -> &ResidualFunction {
464 &self.source_function
465 }
466
467 pub fn non_overlap(&self) -> &UniquenessWitness {
468 &self.non_overlap
469 }
470}
471
472#[derive(Debug, Eq, PartialEq)]
473pub struct BranchIdentity {
474 branch_id: String,
475 chart_id: String,
476 support_id: String,
477}
478
479impl BranchIdentity {
480 fn new(branch_id: String, chart_id: String, support_id: String) -> Self {
481 Self {
482 branch_id,
483 chart_id,
484 support_id,
485 }
486 }
487
488 pub fn branch_id(&self) -> &str {
489 &self.branch_id
490 }
491
492 pub fn chart_id(&self) -> &str {
493 &self.chart_id
494 }
495
496 pub fn support_id(&self) -> &str {
497 &self.support_id
498 }
499}
500
501#[derive(Debug, Eq, PartialEq)]
502pub struct IntersectionCurve {
503 branch_identity: BranchIdentity,
504 contact_order: ContactOrder,
505 residual: IntersectionResidual,
506 support_id: String,
507 witness: IntersectionWitness,
508}
509
510impl IntersectionCurve {
511 fn new(
512 branch_identity: BranchIdentity,
513 contact_order: ContactOrder,
514 residual: IntersectionResidual,
515 support_id: String,
516 witness: IntersectionWitness,
517 ) -> Self {
518 Self {
519 branch_identity,
520 contact_order,
521 residual,
522 support_id,
523 witness,
524 }
525 }
526
527 pub fn branch_identity(&self) -> &BranchIdentity {
528 &self.branch_identity
529 }
530
531 pub fn contact_order(&self) -> &ContactOrder {
532 &self.contact_order
533 }
534
535 pub fn residual(&self) -> &IntersectionResidual {
536 &self.residual
537 }
538
539 pub fn support_id(&self) -> &str {
540 &self.support_id
541 }
542
543 pub fn witness(&self) -> &IntersectionWitness {
544 &self.witness
545 }
546}
547
548#[derive(Debug, Eq, PartialEq)]
549pub struct CurveBranch {
550 branch_identity: BranchIdentity,
551 contact_order: ContactOrder,
552 residual: IntersectionResidual,
553 witness: IntersectionWitness,
554}
555
556impl CurveBranch {
557 fn new(
558 branch_identity: BranchIdentity,
559 contact_order: ContactOrder,
560 residual: IntersectionResidual,
561 witness: IntersectionWitness,
562 ) -> Self {
563 Self {
564 branch_identity,
565 contact_order,
566 residual,
567 witness,
568 }
569 }
570
571 pub fn branch_identity(&self) -> &BranchIdentity {
572 &self.branch_identity
573 }
574
575 pub fn contact_order(&self) -> &ContactOrder {
576 &self.contact_order
577 }
578
579 pub fn residual(&self) -> &IntersectionResidual {
580 &self.residual
581 }
582
583 pub fn witness(&self) -> &IntersectionWitness {
584 &self.witness
585 }
586}
587
588#[derive(Debug, Eq, PartialEq)]
589pub struct IntersectionPoint {
590 branch_identity: BranchIdentityRef,
591 contact_order: ContactOrder,
592 point: Point3,
593 residual: IntersectionResidual,
594 witness: IntersectionWitness,
595}
596
597impl IntersectionPoint {
598 fn new(
599 branch_identity: BranchIdentityRef,
600 contact_order: ContactOrder,
601 point: Point3,
602 residual: IntersectionResidual,
603 witness: IntersectionWitness,
604 ) -> Self {
605 Self {
606 branch_identity,
607 contact_order,
608 point,
609 residual,
610 witness,
611 }
612 }
613
614 pub fn branch_identity(&self) -> Option<&BranchIdentity> {
615 self.branch_identity.as_ref()
616 }
617
618 pub fn contact_order(&self) -> &ContactOrder {
619 &self.contact_order
620 }
621
622 pub fn point(&self) -> &Point3 {
623 &self.point
624 }
625
626 pub fn residual(&self) -> &IntersectionResidual {
627 &self.residual
628 }
629
630 pub fn witness(&self) -> &IntersectionWitness {
631 &self.witness
632 }
633}
634
635#[derive(Debug, Eq, PartialEq)]
636pub struct IntersectionResidual {
637 combined: ResidualValue,
638 left: ResidualValue,
639 right: ResidualValue,
640}
641
642impl IntersectionResidual {
643 fn new(combined: ResidualValue, left: ResidualValue, right: ResidualValue) -> Self {
644 Self {
645 combined,
646 left,
647 right,
648 }
649 }
650
651 pub fn combined(&self) -> &ResidualValue {
652 &self.combined
653 }
654
655 pub fn left(&self) -> &ResidualValue {
656 &self.left
657 }
658
659 pub fn right(&self) -> &ResidualValue {
660 &self.right
661 }
662}
663
664#[derive(Debug, Eq, PartialEq)]
665pub struct RootBracket {
666 contact_order: ContactOrder,
667 convergence: ConvergenceWitness,
668 lower: RealAlgebraic,
669 sign_change: bool,
670 upper: RealAlgebraic,
671 evidence: RootEvidence,
672 exact_parameter: Option<RealAlgebraic>,
673}
674
675impl RootBracket {
676 fn from_calculus(
677 bracket: &CalculusRootBracket,
678 isolation: &CalculusRootIsolation,
679 evidence: RootEvidence,
680 ) -> Result<Self, GeometryFailure> {
681 let contact_order = contact_order_from_evidence(&evidence);
682 Ok(Self {
683 contact_order,
684 convergence: ConvergenceWitness::from_calculus(isolation.witness())?,
685 lower: dyadic_to_real(bracket.enclosure().lower())?,
686 sign_change: matches!(bracket.evidence(), CalculusRootEvidence::SignChange { .. }),
687 upper: dyadic_to_real(bracket.enclosure().upper())?,
688 evidence,
689 exact_parameter: None,
690 })
691 }
692
693 fn from_unresolved(
694 enclosure: &Enclosure,
695 evidence: RootEvidence,
696 policy: &RootIsolationPolicy,
697 ) -> Result<Self, GeometryFailure> {
698 let lower = dyadic_to_real(enclosure.lower())?;
699 let upper = dyadic_to_real(enclosure.upper())?;
700 Ok(Self {
701 contact_order: contact_order_from_evidence(&evidence),
702 convergence: ConvergenceWitness::new(
703 lower.try_clone()?,
704 upper.try_clone()?,
705 lower.try_clone()?,
706 upper.try_clone()?,
707 0,
708 policy.method,
709 CalculusConvergenceStatus::IterationLimit,
710 ),
711 lower,
712 sign_change: false,
713 upper,
714 evidence,
715 exact_parameter: None,
716 })
717 }
718
719 fn from_exact(
720 parameter: RealAlgebraic,
721 evidence: RootEvidence,
722 policy: &RootIsolationPolicy,
723 ) -> Result<Self, GeometryFailure> {
724 let lower = parameter.try_clone()?;
725 let upper = parameter.try_clone()?;
726 Ok(Self {
727 contact_order: contact_order_from_evidence(&evidence),
728 convergence: ConvergenceWitness::new(
729 parameter.try_clone()?,
730 parameter.try_clone()?,
731 parameter.try_clone()?,
732 parameter.try_clone()?,
733 0,
734 policy.method,
735 CalculusConvergenceStatus::ExactDyadicRoot,
736 ),
737 lower,
738 sign_change: false,
739 upper,
740 evidence,
741 exact_parameter: Some(parameter),
742 })
743 }
744
745 pub fn contact_order(&self) -> &ContactOrder {
746 &self.contact_order
747 }
748
749 pub fn convergence(&self) -> &ConvergenceWitness {
750 &self.convergence
751 }
752
753 pub fn lower(&self) -> &RealAlgebraic {
754 &self.lower
755 }
756
757 pub fn sign_change(&self) -> bool {
758 self.sign_change
759 }
760
761 pub fn upper(&self) -> &RealAlgebraic {
762 &self.upper
763 }
764
765 pub fn evidence(&self) -> &RootEvidence {
766 &self.evidence
767 }
768}
769
770#[derive(Debug, Eq, PartialEq)]
771pub struct ExistenceWitness {
772 evidence: ExistenceEvidence,
773 method: WitnessMethod,
774 status: WitnessStatus,
775}
776
777impl ExistenceWitness {
778 fn new(evidence: ExistenceEvidence, method: WitnessMethod, status: WitnessStatus) -> Self {
779 Self {
780 evidence,
781 method,
782 status,
783 }
784 }
785
786 pub fn evidence(&self) -> ExistenceEvidence {
787 self.evidence
788 }
789
790 pub fn method(&self) -> WitnessMethod {
791 self.method
792 }
793
794 pub fn status(&self) -> &WitnessStatus {
795 &self.status
796 }
797}
798
799#[derive(Debug, Eq, PartialEq)]
800pub struct UniquenessWitness {
801 evidence: UniquenessEvidence,
802 method: WitnessMethod,
803 status: WitnessStatus,
804}
805
806impl UniquenessWitness {
807 fn new(evidence: UniquenessEvidence, method: WitnessMethod, status: WitnessStatus) -> Self {
808 Self {
809 evidence,
810 method,
811 status,
812 }
813 }
814
815 pub fn evidence(&self) -> UniquenessEvidence {
816 self.evidence
817 }
818
819 pub fn method(&self) -> WitnessMethod {
820 self.method
821 }
822
823 pub fn status(&self) -> &WitnessStatus {
824 &self.status
825 }
826}
827
828#[derive(Debug, Eq, PartialEq)]
829pub struct IntersectionWitness {
830 existence: ExistenceWitness,
831 uniqueness: UniquenessWitness,
832 root_isolation: RootIsolation,
833 constraint: IntersectionConstraint,
834}
835
836impl IntersectionWitness {
837 fn from_isolation_and_constraint(
838 isolation: RootIsolation,
839 constraint: IntersectionConstraint,
840 ) -> Self {
841 Self {
842 existence: clone_existence(&isolation.completeness),
843 uniqueness: clone_uniqueness(&isolation.non_overlap),
844 root_isolation: isolation,
845 constraint,
846 }
847 }
848
849 pub fn existence(&self) -> &ExistenceWitness {
850 &self.existence
851 }
852
853 pub fn uniqueness(&self) -> &UniquenessWitness {
854 &self.uniqueness
855 }
856
857 pub fn root_isolation(&self) -> &RootIsolation {
858 &self.root_isolation
859 }
860
861 pub fn constraint(&self) -> &IntersectionConstraint {
862 &self.constraint
863 }
864}
865
866#[derive(Debug, Eq, PartialEq)]
867pub struct ConvergenceWitness {
868 final_lower: RealAlgebraic,
869 final_upper: RealAlgebraic,
870 initial_lower: RealAlgebraic,
871 initial_upper: RealAlgebraic,
872 iterations: usize,
873 method: RootRefinementMethod,
874 status: CalculusConvergenceStatus,
875}
876
877impl ConvergenceWitness {
878 fn new(
879 final_lower: RealAlgebraic,
880 final_upper: RealAlgebraic,
881 initial_lower: RealAlgebraic,
882 initial_upper: RealAlgebraic,
883 iterations: usize,
884 method: RootRefinementMethod,
885 status: CalculusConvergenceStatus,
886 ) -> Self {
887 Self {
888 final_lower,
889 final_upper,
890 initial_lower,
891 initial_upper,
892 iterations,
893 method,
894 status,
895 }
896 }
897
898 pub fn final_lower(&self) -> &RealAlgebraic {
899 &self.final_lower
900 }
901
902 pub fn final_upper(&self) -> &RealAlgebraic {
903 &self.final_upper
904 }
905
906 pub fn initial_lower(&self) -> &RealAlgebraic {
907 &self.initial_lower
908 }
909
910 pub fn initial_upper(&self) -> &RealAlgebraic {
911 &self.initial_upper
912 }
913
914 pub fn iterations(&self) -> usize {
915 self.iterations
916 }
917
918 pub fn method(&self) -> RootRefinementMethod {
919 self.method
920 }
921
922 pub fn status(&self) -> CalculusConvergenceStatus {
923 self.status
924 }
925
926 fn from_calculus(witness: &neco_calculus::ConvergenceWitness) -> Result<Self, GeometryFailure> {
927 Ok(Self::new(
928 dyadic_to_real(witness.final_enclosure().lower())?,
929 dyadic_to_real(witness.final_enclosure().upper())?,
930 dyadic_to_real(witness.initial().lower())?,
931 dyadic_to_real(witness.initial().upper())?,
932 witness.iterations(),
933 witness.method(),
934 witness.status(),
935 ))
936 }
937}
938
939#[derive(Clone, Debug, Eq, PartialEq)]
940pub struct ContactOrder {
941 kind: ContactOrderKind,
942 order: usize,
943}
944
945impl ContactOrder {
946 fn new(kind: ContactOrderKind, order: usize) -> Self {
947 Self { kind, order }
948 }
949
950 pub fn kind(&self) -> ContactOrderKind {
951 self.kind
952 }
953
954 pub fn order(&self) -> usize {
955 self.order
956 }
957}
958
959#[derive(Debug, Eq, PartialEq)]
960pub struct IntersectionConstructionRequestBody {
961 left_operand: IntersectionOperand,
962 right_operand: IntersectionOperand,
963 root_isolation_policy: RootIsolationPolicy,
964}
965
966impl IntersectionConstructionRequestBody {
967 pub fn new(
968 left_operand: IntersectionOperand,
969 right_operand: IntersectionOperand,
970 root_isolation_policy: RootIsolationPolicy,
971 ) -> Self {
972 Self {
973 left_operand,
974 right_operand,
975 root_isolation_policy,
976 }
977 }
978
979 pub fn left_operand(&self) -> &IntersectionOperand {
980 &self.left_operand
981 }
982
983 pub fn right_operand(&self) -> &IntersectionOperand {
984 &self.right_operand
985 }
986
987 pub fn root_isolation_policy(&self) -> &RootIsolationPolicy {
988 &self.root_isolation_policy
989 }
990}
991
992#[derive(Debug, Eq, PartialEq)]
993pub struct IntersectionConstructionRequest {
994 body: IntersectionConstructionRequestBody,
995}
996
997impl IntersectionConstructionRequest {
998 pub fn new(body: IntersectionConstructionRequestBody) -> Self {
999 Self { body }
1000 }
1001
1002 pub fn body(&self) -> &IntersectionConstructionRequestBody {
1003 &self.body
1004 }
1005
1006 fn into_body(self) -> IntersectionConstructionRequestBody {
1007 self.body
1008 }
1009}
1010
1011#[derive(Debug, Eq, PartialEq)]
1012pub struct CoincidentSupport {
1013 left_support: ShapeDeclaration,
1014 residual: IntersectionResidual,
1015 right_support: ShapeDeclaration,
1016 witness: IntersectionWitness,
1017}
1018
1019impl CoincidentSupport {
1020 fn new(
1021 left_support: ShapeDeclaration,
1022 residual: IntersectionResidual,
1023 right_support: ShapeDeclaration,
1024 witness: IntersectionWitness,
1025 ) -> Self {
1026 Self {
1027 left_support,
1028 residual,
1029 right_support,
1030 witness,
1031 }
1032 }
1033
1034 pub fn left_support(&self) -> &ShapeDeclaration {
1035 &self.left_support
1036 }
1037
1038 pub fn residual(&self) -> &IntersectionResidual {
1039 &self.residual
1040 }
1041
1042 pub fn right_support(&self) -> &ShapeDeclaration {
1043 &self.right_support
1044 }
1045
1046 pub fn witness(&self) -> &IntersectionWitness {
1047 &self.witness
1048 }
1049}
1050
1051#[derive(Debug, Eq, PartialEq)]
1052pub struct RootIsolationPolicy {
1053 max_cells: usize,
1054 max_iterations: usize,
1055 method: RootRefinementMethod,
1056 target_width: Enclosure,
1057}
1058
1059impl RootIsolationPolicy {
1060 pub fn new(
1061 max_iterations: usize,
1062 method: RootRefinementMethod,
1063 target_width: Enclosure,
1064 ) -> Result<Self, GeometryFailure> {
1065 if max_iterations == 0 {
1066 return Err(GeometryFailure::RootIsolationPolicyInvalid);
1067 }
1068 if max_iterations > MAX_ROOT_PARTITION_DEPTH {
1069 return Err(GeometryFailure::RootIsolationResourceLimit {
1070 requested_depth: max_iterations,
1071 maximum_depth: MAX_ROOT_PARTITION_DEPTH,
1072 });
1073 }
1074 Ok(Self {
1075 max_cells: partition_cells_for_depth(max_iterations),
1076 max_iterations,
1077 method,
1078 target_width,
1079 })
1080 }
1081
1082 pub fn with_limits(
1083 max_iterations: usize,
1084 max_cells: usize,
1085 method: RootRefinementMethod,
1086 target_width: Enclosure,
1087 ) -> Result<Self, GeometryFailure> {
1088 if max_cells == 0 {
1089 return Err(GeometryFailure::RootIsolationPolicyInvalid);
1090 }
1091 if max_cells > MAX_ROOT_PARTITION_CELLS {
1092 return Err(GeometryFailure::RootPartitionCellLimit {
1093 requested_cells: max_cells,
1094 maximum_cells: MAX_ROOT_PARTITION_CELLS,
1095 });
1096 }
1097 let mut policy = Self::new(max_iterations, method, target_width)?;
1098 policy.max_cells = max_cells;
1099 Ok(policy)
1100 }
1101
1102 pub fn max_cells(&self) -> usize {
1103 self.max_cells
1104 }
1105
1106 pub fn max_iterations(&self) -> usize {
1107 self.max_iterations
1108 }
1109
1110 pub fn method(&self) -> RootRefinementMethod {
1111 self.method
1112 }
1113
1114 pub fn target_width(&self) -> &Enclosure {
1115 &self.target_width
1116 }
1117}
1118
1119#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1120pub enum IntersectionUndeterminedReason {
1121 BranchIdentityUndetermined,
1122 CoincidenceUndetermined,
1123 EvaluationUndetermined,
1124 MultiplicityUndetermined,
1125 RootIsolationIncomplete,
1126}
1127
1128#[derive(Debug, Eq, PartialEq)]
1129pub enum ResidualValue {
1130 Certified {
1131 owner: OwnerId,
1132 requirement: ExactExpressionRequirement,
1133 source: NecoImplementationSource,
1134 value: Enclosure,
1135 },
1136 Exact {
1137 value: RealAlgebraic,
1138 },
1139 Undetermined {
1140 reason: ResidualUndeterminedReason,
1141 },
1142}
1143
1144#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1145pub enum ResidualUndeterminedReason {
1146 OperandEvidenceUnresolved,
1147 ScalarResidualUnavailable,
1148}
1149
1150#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
1151pub struct IntersectionComponentIdentity(usize);
1152
1153impl IntersectionComponentIdentity {
1154 pub fn ordinal(&self) -> usize {
1155 self.0
1156 }
1157}
1158
1159#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1160pub enum IntersectionKind {
1161 Coincident,
1162 Curve,
1163 CurveBranches,
1164 Empty,
1165 FinitePoints,
1166 Point,
1167 Undetermined,
1168}
1169
1170pub enum ComponentEvidenceRef<'a> {
1171 Point(&'a IntersectionPoint),
1172 Curve(&'a IntersectionCurve),
1173 CurveBranch(&'a CurveBranch),
1174 Coincident(&'a CoincidentSupport),
1175}
1176
1177impl<'a> ComponentEvidenceRef<'a> {
1178 pub fn branch_identity(&self) -> Option<&'a BranchIdentity> {
1179 match self {
1180 Self::Point(value) => value.branch_identity(),
1181 Self::Curve(value) => Some(value.branch_identity()),
1182 Self::CurveBranch(value) => Some(value.branch_identity()),
1183 Self::Coincident(_) => None,
1184 }
1185 }
1186
1187 pub fn contact_order(&self) -> Option<&'a ContactOrder> {
1188 match self {
1189 Self::Point(value) => Some(value.contact_order()),
1190 Self::Curve(value) => Some(value.contact_order()),
1191 Self::CurveBranch(value) => Some(value.contact_order()),
1192 Self::Coincident(_) => None,
1193 }
1194 }
1195}
1196
1197pub struct IntersectionComponentViewEntry<'a> {
1198 identity: IntersectionComponentIdentity,
1199 evidence: ComponentEvidenceRef<'a>,
1200}
1201
1202impl<'a> IntersectionComponentViewEntry<'a> {
1203 pub fn identity(&self) -> IntersectionComponentIdentity {
1204 self.identity
1205 }
1206 pub fn evidence(&self) -> &ComponentEvidenceRef<'a> {
1207 &self.evidence
1208 }
1209}
1210
1211pub struct IntersectionComponentIter<'a> {
1212 inner: core::slice::Iter<'a, OwnedIntersectionComponent>,
1213}
1214
1215impl<'a> Iterator for IntersectionComponentIter<'a> {
1216 type Item = IntersectionComponentViewEntry<'a>;
1217
1218 fn next(&mut self) -> Option<Self::Item> {
1219 self.inner.next().map(|entry| {
1220 let evidence = match &entry.evidence {
1221 OwnedIntersectionEvidence::Point(value) => {
1222 ComponentEvidenceRef::Point(value.as_ref())
1223 }
1224 OwnedIntersectionEvidence::Curve(value) => {
1225 ComponentEvidenceRef::Curve(value.as_ref())
1226 }
1227 OwnedIntersectionEvidence::CurveBranch(value) => {
1228 ComponentEvidenceRef::CurveBranch(value.as_ref())
1229 }
1230 OwnedIntersectionEvidence::Coincident(value) => {
1231 ComponentEvidenceRef::Coincident(value.as_ref())
1232 }
1233 };
1234 IntersectionComponentViewEntry {
1235 identity: entry.identity,
1236 evidence,
1237 }
1238 })
1239 }
1240
1241 fn size_hint(&self) -> (usize, Option<usize>) {
1242 self.inner.size_hint()
1243 }
1244}
1245
1246impl ExactSizeIterator for IntersectionComponentIter<'_> {}
1247
1248pub enum IntersectionComponentView<'a> {
1249 Components(IntersectionComponentIter<'a>),
1250 NoComponents,
1251 Undetermined(IntersectionUndeterminedReason),
1252}
1253
1254#[derive(Debug, Eq, PartialEq)]
1255enum OwnedIntersectionEvidence {
1256 Point(Box<IntersectionPoint>),
1257 Curve(Box<IntersectionCurve>),
1258 CurveBranch(Box<CurveBranch>),
1259 Coincident(Box<CoincidentSupport>),
1260}
1261
1262#[derive(Debug, Eq, PartialEq)]
1263struct OwnedIntersectionComponent {
1264 identity: IntersectionComponentIdentity,
1265 evidence: OwnedIntersectionEvidence,
1266}
1267
1268impl OwnedIntersectionComponent {
1269 fn validate(&self) -> Result<(), GeometryFailure> {
1270 match self.evidence {
1271 OwnedIntersectionEvidence::Point(_)
1272 | OwnedIntersectionEvidence::Curve(_)
1273 | OwnedIntersectionEvidence::CurveBranch(_)
1274 | OwnedIntersectionEvidence::Coincident(_) => Ok(()),
1275 }
1276 }
1277}
1278
1279#[derive(Debug, Eq, PartialEq)]
1280#[must_use]
1281pub struct IntersectionSet {
1282 kind: IntersectionKind,
1283 witness: IntersectionWitness,
1284 residual: IntersectionResidual,
1285 reason: Option<IntersectionUndeterminedReason>,
1286 components: Vec<OwnedIntersectionComponent>,
1287}
1288
1289impl IntersectionSet {
1290 pub fn kind(&self) -> IntersectionKind {
1291 self.kind
1292 }
1293 pub fn witness(&self) -> &IntersectionWitness {
1294 &self.witness
1295 }
1296 pub fn residual(&self) -> &IntersectionResidual {
1297 &self.residual
1298 }
1299 pub fn component_view(&self) -> IntersectionComponentView<'_> {
1300 if let Some(reason) = self.reason {
1301 return IntersectionComponentView::Undetermined(reason);
1302 }
1303 if self.components.is_empty() {
1304 return IntersectionComponentView::NoComponents;
1305 }
1306 IntersectionComponentView::Components(IntersectionComponentIter {
1307 inner: self.components.iter(),
1308 })
1309 }
1310
1311 fn empty(residual: IntersectionResidual, witness: IntersectionWitness) -> Self {
1312 Self {
1313 kind: IntersectionKind::Empty,
1314 witness,
1315 residual,
1316 reason: None,
1317 components: Vec::new(),
1318 }
1319 }
1320
1321 fn undetermined(
1322 reason: IntersectionUndeterminedReason,
1323 residual: IntersectionResidual,
1324 witness: IntersectionWitness,
1325 ) -> Self {
1326 Self {
1327 kind: IntersectionKind::Undetermined,
1328 witness,
1329 residual,
1330 reason: Some(reason),
1331 components: Vec::new(),
1332 }
1333 }
1334
1335 fn from_components(
1336 kind: IntersectionKind,
1337 residual: IntersectionResidual,
1338 witness: IntersectionWitness,
1339 evidence: Vec<OwnedIntersectionEvidence>,
1340 ) -> Result<Self, GeometryFailure> {
1341 let expected = match kind {
1342 IntersectionKind::Coincident | IntersectionKind::Point | IntersectionKind::Curve => 1,
1343 IntersectionKind::FinitePoints | IntersectionKind::CurveBranches => {
1344 if evidence.is_empty() {
1345 return Err(if kind == IntersectionKind::FinitePoints {
1346 GeometryFailure::EmptyFinitePointComponents
1347 } else {
1348 GeometryFailure::EmptyCurveBranchComponents
1349 });
1350 }
1351 evidence.len()
1352 }
1353 IntersectionKind::Empty | IntersectionKind::Undetermined => {
1354 return Err(GeometryFailure::ComponentIdentityEvidenceMismatch);
1355 }
1356 };
1357 if evidence.len() != expected {
1358 return Err(GeometryFailure::ComponentIdentityEvidenceMismatch);
1359 }
1360 let components = evidence
1361 .into_iter()
1362 .enumerate()
1363 .map(|(ordinal, evidence)| OwnedIntersectionComponent {
1364 identity: IntersectionComponentIdentity(ordinal),
1365 evidence,
1366 })
1367 .collect::<Vec<_>>();
1368 if components
1369 .windows(2)
1370 .any(|pair| pair[0].identity >= pair[1].identity)
1371 {
1372 return Err(GeometryFailure::DuplicateIntersectionComponentIdentity);
1373 }
1374 for component in &components {
1375 component
1376 .validate()
1377 .map_err(|_| GeometryFailure::ComponentIdentityEvidenceMismatch)?;
1378 }
1379 if components.len() != expected {
1380 return Err(GeometryFailure::ComponentIdentityCanonicalizationFailure);
1381 }
1382 let kind_matches = match kind {
1383 IntersectionKind::Coincident => matches!(
1384 components[0].evidence,
1385 OwnedIntersectionEvidence::Coincident(_)
1386 ),
1387 IntersectionKind::Point | IntersectionKind::FinitePoints => components
1388 .iter()
1389 .all(|entry| matches!(entry.evidence, OwnedIntersectionEvidence::Point(_))),
1390 IntersectionKind::Curve => {
1391 matches!(components[0].evidence, OwnedIntersectionEvidence::Curve(_))
1392 }
1393 IntersectionKind::CurveBranches => components
1394 .iter()
1395 .all(|entry| matches!(entry.evidence, OwnedIntersectionEvidence::CurveBranch(_))),
1396 IntersectionKind::Empty | IntersectionKind::Undetermined => false,
1397 };
1398 if !kind_matches {
1399 return Err(GeometryFailure::ComponentIdentityEvidenceMismatch);
1400 }
1401 Ok(Self {
1402 kind,
1403 witness,
1404 residual,
1405 reason: None,
1406 components,
1407 })
1408 }
1409}
1410
1411#[derive(Debug, Eq, PartialEq)]
1412pub enum IntersectionOperand {
1413 Declaration(ShapeDeclaration),
1414 Evaluated(ShapeEvaluation),
1415}
1416
1417#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1418pub enum ContactOrderKind {
1419 HigherOrder,
1420 Tangent,
1421 Transverse,
1422 Undetermined,
1423}
1424
1425#[derive(Debug, Eq, PartialEq)]
1426pub enum WitnessStatus {
1427 Proved,
1428 Undetermined { reason: WitnessUndeterminedReason },
1429}
1430
1431#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1432pub enum WitnessMethod {
1433 CanonicalLowerEndpointOrdering,
1434 DeterministicDyadicCandidatePartition,
1435}
1436
1437#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1438pub enum ExistenceEvidence {
1439 CompleteCandidatePartition,
1440}
1441
1442#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1443pub enum UniquenessEvidence {
1444 PairwiseNonOverlappingBrackets,
1445}
1446
1447#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1448pub enum WitnessUndeterminedReason {
1449 BracketSetInvalid,
1450 PartitionOrCandidatesIncomplete,
1451}
1452
1453#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
1454pub struct RayCrossingTargetId(String);
1455
1456impl RayCrossingTargetId {
1457 pub fn new(value: impl Into<String>) -> Result<Self, GeometryFailure> {
1458 let value = value.into();
1459 if value.is_empty() {
1460 return Err(GeometryFailure::InvalidRayCrossingPolicy);
1461 }
1462 Ok(Self(value))
1463 }
1464 pub fn as_str(&self) -> &str {
1465 &self.0
1466 }
1467}
1468
1469#[derive(Debug, Eq, PartialEq)]
1470pub struct ExactTriangleTarget {
1471 pub id: RayCrossingTargetId,
1472 pub a: Point3,
1473 pub b: Point3,
1474 pub c: Point3,
1475}
1476
1477impl ExactTriangleTarget {
1478 pub fn new(
1479 id: RayCrossingTargetId,
1480 a: Point3,
1481 b: Point3,
1482 c: Point3,
1483 ) -> Result<Self, GeometryFailure> {
1484 if exact_triangle_is_degenerate(&a, &b, &c)? {
1485 return Err(GeometryFailure::DegenerateTriangle);
1486 }
1487 Ok(Self { id, a, b, c })
1488 }
1489}
1490
1491#[derive(Debug, PartialEq)]
1492pub struct CheckedTriangleTarget {
1493 pub id: RayCrossingTargetId,
1494 pub vertices: [[f64; 3]; 3],
1495 owner: OwnerId,
1496 requirement: ExactExpressionRequirement,
1497 source: NecoImplementationSource,
1498}
1499
1500impl CheckedTriangleTarget {
1501 pub fn new(
1502 id: RayCrossingTargetId,
1503 vertices: [[f64; 3]; 3],
1504 owner: OwnerId,
1505 requirement: ExactExpressionRequirement,
1506 source: NecoImplementationSource,
1507 ) -> Result<Self, GeometryFailure> {
1508 if vertices.iter().flatten().any(|value| !value.is_finite()) {
1509 return Err(GeometryFailure::DegenerateTriangle);
1510 }
1511 if checked_triangle_is_degenerate(vertices) {
1512 return Err(GeometryFailure::DegenerateTriangle);
1513 }
1514 Ok(Self {
1515 id,
1516 vertices,
1517 owner,
1518 requirement,
1519 source,
1520 })
1521 }
1522
1523 pub const fn owner(&self) -> OwnerId {
1524 self.owner
1525 }
1526
1527 pub fn requirement(&self) -> &ExactExpressionRequirement {
1528 &self.requirement
1529 }
1530
1531 pub const fn source(&self) -> NecoImplementationSource {
1532 self.source
1533 }
1534}
1535
1536fn exact_triangle_is_degenerate(
1537 a: &Point3,
1538 b: &Point3,
1539 c: &Point3,
1540) -> Result<bool, GeometryFailure> {
1541 let ab = [a.x.sub(&b.x)?, a.y.sub(&b.y)?, a.z.sub(&b.z)?];
1542 let ac = [a.x.sub(&c.x)?, a.y.sub(&c.y)?, a.z.sub(&c.z)?];
1543 let cross = [
1544 ab[1].mul(&ac[2])?.sub(&ab[2].mul(&ac[1])?)?,
1545 ab[2].mul(&ac[0])?.sub(&ab[0].mul(&ac[2])?)?,
1546 ab[0].mul(&ac[1])?.sub(&ab[1].mul(&ac[0])?)?,
1547 ];
1548 Ok(cross.iter().all(RealAlgebraic::is_zero))
1549}
1550
1551fn checked_triangle_is_degenerate(vertices: [[f64; 3]; 3]) -> bool {
1552 let ab = [
1553 vertices[1][0] - vertices[0][0],
1554 vertices[1][1] - vertices[0][1],
1555 vertices[1][2] - vertices[0][2],
1556 ];
1557 let ac = [
1558 vertices[2][0] - vertices[0][0],
1559 vertices[2][1] - vertices[0][1],
1560 vertices[2][2] - vertices[0][2],
1561 ];
1562 let cross = [
1563 ab[1] * ac[2] - ab[2] * ac[1],
1564 ab[2] * ac[0] - ab[0] * ac[2],
1565 ab[0] * ac[1] - ab[1] * ac[0],
1566 ];
1567 cross == [0.0; 3]
1568}
1569
1570#[derive(Debug, Eq, PartialEq)]
1571pub struct TrimmedParametricSurfaceTarget {
1572 id: RayCrossingTargetId,
1573 candidate: SurfaceCrossingCandidate,
1574}
1575
1576impl TrimmedParametricSurfaceTarget {
1577 pub fn new(id: RayCrossingTargetId, candidate: SurfaceCrossingCandidate) -> Self {
1578 Self { id, candidate }
1579 }
1580 pub fn id(&self) -> &RayCrossingTargetId {
1581 &self.id
1582 }
1583 pub fn candidate(&self) -> &SurfaceCrossingCandidate {
1584 &self.candidate
1585 }
1586}
1587
1588#[derive(Debug, Eq, PartialEq)]
1589pub struct CheckedTrimmedParametricSurfaceTarget {
1590 id: RayCrossingTargetId,
1591 candidate: SurfaceCrossingCandidate,
1592 owner: OwnerId,
1593 requirement: ExactExpressionRequirement,
1594 source: NecoImplementationSource,
1595}
1596
1597impl CheckedTrimmedParametricSurfaceTarget {
1598 pub fn new(
1599 id: RayCrossingTargetId,
1600 candidate: SurfaceCrossingCandidate,
1601 owner: OwnerId,
1602 requirement: ExactExpressionRequirement,
1603 source: NecoImplementationSource,
1604 ) -> Self {
1605 Self {
1606 id,
1607 candidate,
1608 owner,
1609 requirement,
1610 source,
1611 }
1612 }
1613
1614 pub fn id(&self) -> &RayCrossingTargetId {
1615 &self.id
1616 }
1617
1618 pub fn candidate(&self) -> &SurfaceCrossingCandidate {
1619 &self.candidate
1620 }
1621
1622 pub const fn owner(&self) -> OwnerId {
1623 self.owner
1624 }
1625
1626 pub fn requirement(&self) -> &ExactExpressionRequirement {
1627 &self.requirement
1628 }
1629
1630 pub const fn source(&self) -> NecoImplementationSource {
1631 self.source
1632 }
1633}
1634
1635#[derive(Debug, PartialEq)]
1636pub enum ExactRayCrossingTarget {
1637 Triangle(ExactTriangleTarget),
1638 TrimmedSurface(TrimmedParametricSurfaceTarget),
1639 ImplicitSurface {
1640 id: RayCrossingTargetId,
1641 surface: ImplicitSurfaceDeclaration,
1642 },
1643}
1644#[derive(Debug, PartialEq)]
1645pub enum CheckedRayCrossingTarget {
1646 Triangle(CheckedTriangleTarget),
1647 TrimmedSurface(Box<CheckedTrimmedParametricSurfaceTarget>),
1648}
1649
1650#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1651enum RayCrossingTargetFamily {
1652 Triangle,
1653 TrimmedSurface,
1654 ImplicitSurface,
1655}
1656
1657#[derive(Debug, PartialEq)]
1658pub struct ExactRayCrossingTargetSet(Vec<ExactRayCrossingTarget>);
1659impl ExactRayCrossingTargetSet {
1660 pub fn new(targets: Vec<ExactRayCrossingTarget>) -> Result<Self, GeometryFailure> {
1661 if targets.is_empty() {
1662 return Err(GeometryFailure::EmptyRayCrossingTargetSet);
1663 }
1664 let families = targets.iter().map(exact_target_family).collect::<Vec<_>>();
1665 if families.windows(2).any(|pair| pair[0] != pair[1]) {
1666 return Err(GeometryFailure::MixedRayCrossingTargetFamily);
1667 }
1668 let ids = targets.iter().map(exact_target_id).collect::<Vec<_>>();
1669 validate_target_ids(ids)?;
1670 Ok(Self(targets))
1671 }
1672 pub fn targets(&self) -> &[ExactRayCrossingTarget] {
1673 &self.0
1674 }
1675}
1676#[derive(Debug, PartialEq)]
1677pub struct CheckedRayCrossingTargetSet(Vec<CheckedRayCrossingTarget>);
1678impl CheckedRayCrossingTargetSet {
1679 pub fn new(targets: Vec<CheckedRayCrossingTarget>) -> Result<Self, GeometryFailure> {
1680 if targets.is_empty() {
1681 return Err(GeometryFailure::EmptyRayCrossingTargetSet);
1682 }
1683 let families = targets
1684 .iter()
1685 .map(checked_target_family)
1686 .collect::<Vec<_>>();
1687 if families.windows(2).any(|pair| pair[0] != pair[1]) {
1688 return Err(GeometryFailure::MixedRayCrossingTargetFamily);
1689 }
1690 let ids = targets.iter().map(checked_target_id).collect::<Vec<_>>();
1691 validate_target_ids(ids)?;
1692 Ok(Self(targets))
1693 }
1694 pub fn targets(&self) -> &[CheckedRayCrossingTarget] {
1695 &self.0
1696 }
1697}
1698
1699fn exact_target_family(target: &ExactRayCrossingTarget) -> RayCrossingTargetFamily {
1700 match target {
1701 ExactRayCrossingTarget::Triangle(_) => RayCrossingTargetFamily::Triangle,
1702 ExactRayCrossingTarget::TrimmedSurface(_) => RayCrossingTargetFamily::TrimmedSurface,
1703 ExactRayCrossingTarget::ImplicitSurface { .. } => RayCrossingTargetFamily::ImplicitSurface,
1704 }
1705}
1706fn checked_target_family(target: &CheckedRayCrossingTarget) -> RayCrossingTargetFamily {
1707 match target {
1708 CheckedRayCrossingTarget::Triangle(_) => RayCrossingTargetFamily::Triangle,
1709 CheckedRayCrossingTarget::TrimmedSurface(_) => RayCrossingTargetFamily::TrimmedSurface,
1710 }
1711}
1712fn exact_target_id(target: &ExactRayCrossingTarget) -> &RayCrossingTargetId {
1713 match target {
1714 ExactRayCrossingTarget::Triangle(target) => &target.id,
1715 ExactRayCrossingTarget::TrimmedSurface(target) => target.id(),
1716 ExactRayCrossingTarget::ImplicitSurface { id, .. } => id,
1717 }
1718}
1719fn checked_target_id(target: &CheckedRayCrossingTarget) -> &RayCrossingTargetId {
1720 match target {
1721 CheckedRayCrossingTarget::Triangle(target) => &target.id,
1722 CheckedRayCrossingTarget::TrimmedSurface(target) => target.id(),
1723 }
1724}
1725fn validate_target_ids(mut ids: Vec<&RayCrossingTargetId>) -> Result<(), GeometryFailure> {
1726 ids.sort_unstable();
1727 if ids.windows(2).any(|pair| pair[0] == pair[1]) {
1728 return Err(GeometryFailure::DuplicateRayCrossingTargetIdentity);
1729 }
1730 Ok(())
1731}
1732
1733#[derive(Debug, Eq, PartialEq)]
1734pub struct RayCrossingPolicy {
1735 pub root_isolation: RootIsolationPolicy,
1736 pub max_targets: NonZeroUsize,
1737 pub max_hits: NonZeroUsize,
1738}
1739impl RayCrossingPolicy {
1740 pub fn new(
1741 root_isolation: RootIsolationPolicy,
1742 max_targets: usize,
1743 max_hits: usize,
1744 ) -> Result<Self, GeometryFailure> {
1745 Ok(Self {
1746 root_isolation,
1747 max_targets: NonZeroUsize::new(max_targets)
1748 .ok_or(GeometryFailure::InvalidRayCrossingPolicy)?,
1749 max_hits: NonZeroUsize::new(max_hits)
1750 .ok_or(GeometryFailure::InvalidRayCrossingPolicy)?,
1751 })
1752 }
1753}
1754
1755#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1756pub enum RayOriginContact {
1757 None,
1758 Interior,
1759 Boundary,
1760}
1761#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1762pub enum RayCrossingLocation {
1763 Interior,
1764 TrimBoundary,
1765 HoleBoundary,
1766 Seam,
1767 Edge,
1768 Vertex,
1769}
1770#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1771pub enum CrossingMultiplicity {
1772 Simple,
1773 Odd(usize),
1774 Even(usize),
1775 Undetermined,
1776}
1777#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1778pub enum CrossingContribution {
1779 Toggle,
1780 NoToggle,
1781 Undetermined,
1782}
1783#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1784pub enum CrossingParity {
1785 Even,
1786 Odd,
1787 Undetermined,
1788}
1789#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1790pub enum RayCrossingUndeterminedReason {
1791 Edge,
1792 Vertex,
1793 TrimBoundary,
1794 HoleBoundary,
1795 DuplicateParameter,
1796 CoplanarOverlap,
1797 Coincident,
1798 InvalidMultiplicity,
1799 UnresolvedSeam,
1800 NormalIndeterminate,
1801}
1802
1803#[derive(Debug, Eq, PartialEq)]
1804pub enum RayNormal {
1805 Regular(Direction3),
1806 Undetermined,
1807}
1808
1809#[derive(Debug, Eq, PartialEq)]
1810pub struct RayCrossingHit {
1811 target_id: RayCrossingTargetId,
1812 parameter: RealAlgebraic,
1813 point: Point3,
1814 location: RayCrossingLocation,
1815 multiplicity: CrossingMultiplicity,
1816 contribution: CrossingContribution,
1817 normal: RayNormal,
1818}
1819
1820impl RayCrossingHit {
1821 pub fn new(
1822 target_id: RayCrossingTargetId,
1823 parameter: RealAlgebraic,
1824 point: Point3,
1825 location: RayCrossingLocation,
1826 multiplicity: CrossingMultiplicity,
1827 contribution: CrossingContribution,
1828 normal: RayNormal,
1829 ) -> Self {
1830 Self {
1831 target_id,
1832 parameter,
1833 point,
1834 location,
1835 multiplicity,
1836 contribution,
1837 normal,
1838 }
1839 }
1840 pub fn target_id(&self) -> &RayCrossingTargetId {
1841 &self.target_id
1842 }
1843 pub fn parameter(&self) -> &RealAlgebraic {
1844 &self.parameter
1845 }
1846 pub fn point(&self) -> &Point3 {
1847 &self.point
1848 }
1849 pub fn location(&self) -> RayCrossingLocation {
1850 self.location
1851 }
1852 pub fn multiplicity(&self) -> CrossingMultiplicity {
1853 self.multiplicity
1854 }
1855 pub fn contribution(&self) -> CrossingContribution {
1856 self.contribution
1857 }
1858
1859 pub fn normal(&self) -> &RayNormal {
1860 &self.normal
1861 }
1862}
1863
1864#[derive(Debug, PartialEq)]
1865pub struct CheckedRayCrossingHit {
1866 target_id: RayCrossingTargetId,
1867 parameter: Enclosure,
1868 point: CoordinateEnclosure3,
1869 location: RayCrossingLocation,
1870 multiplicity: CrossingMultiplicity,
1871 contribution: CrossingContribution,
1872 owner: OwnerId,
1873 requirement: ExactExpressionRequirement,
1874 source: NecoImplementationSource,
1875 normal: RayNormal,
1876}
1877
1878struct CheckedHitGeometry {
1879 location: RayCrossingLocation,
1880 multiplicity: CrossingMultiplicity,
1881 contribution: CrossingContribution,
1882 owner: OwnerId,
1883 requirement: ExactExpressionRequirement,
1884 source: NecoImplementationSource,
1885 normal: RayNormal,
1886}
1887
1888impl CheckedRayCrossingHit {
1889 fn from_exact_hit(
1890 target_id: RayCrossingTargetId,
1891 parameter: Enclosure,
1892 point: CoordinateEnclosure3,
1893 geometry: CheckedHitGeometry,
1894 ) -> Self {
1895 Self {
1896 target_id,
1897 parameter,
1898 point,
1899 location: geometry.location,
1900 multiplicity: geometry.multiplicity,
1901 contribution: geometry.contribution,
1902 owner: geometry.owner,
1903 requirement: geometry.requirement,
1904 source: geometry.source,
1905 normal: geometry.normal,
1906 }
1907 }
1908 pub fn target_id(&self) -> &RayCrossingTargetId {
1909 &self.target_id
1910 }
1911 pub fn parameter(&self) -> &Enclosure {
1912 &self.parameter
1913 }
1914 pub fn point(&self) -> &CoordinateEnclosure3 {
1915 &self.point
1916 }
1917 pub fn location(&self) -> RayCrossingLocation {
1918 self.location
1919 }
1920 pub fn multiplicity(&self) -> CrossingMultiplicity {
1921 self.multiplicity
1922 }
1923 pub fn contribution(&self) -> CrossingContribution {
1924 self.contribution
1925 }
1926 pub const fn owner(&self) -> OwnerId {
1927 self.owner
1928 }
1929
1930 pub fn requirement(&self) -> &ExactExpressionRequirement {
1931 &self.requirement
1932 }
1933
1934 pub const fn source(&self) -> NecoImplementationSource {
1935 self.source
1936 }
1937 pub fn normal(&self) -> &RayNormal {
1938 &self.normal
1939 }
1940}
1941
1942#[derive(Debug, Eq, PartialEq)]
1943pub struct RayCrossingWitness {
1944 target_count: usize,
1945 target_ids: Vec<RayCrossingTargetId>,
1946 parity: CrossingParity,
1947}
1948impl RayCrossingWitness {
1949 pub fn new(target_ids: Vec<RayCrossingTargetId>, parity: CrossingParity) -> Self {
1950 let target_count = target_ids.len();
1951 Self {
1952 target_count,
1953 target_ids,
1954 parity,
1955 }
1956 }
1957 pub fn target_count(&self) -> usize {
1958 self.target_count
1959 }
1960 pub fn target_ids(&self) -> &[RayCrossingTargetId] {
1961 &self.target_ids
1962 }
1963 pub fn parity(&self) -> CrossingParity {
1964 self.parity
1965 }
1966}
1967
1968#[derive(Debug, PartialEq)]
1969pub struct CheckedRayCrossingWitness {
1970 target_count: usize,
1971 target_ids: Vec<RayCrossingTargetId>,
1972 parity: CrossingParity,
1973}
1974impl CheckedRayCrossingWitness {
1975 pub fn new(target_ids: Vec<RayCrossingTargetId>, parity: CrossingParity) -> Self {
1976 let target_count = target_ids.len();
1977 Self {
1978 target_count,
1979 target_ids,
1980 parity,
1981 }
1982 }
1983 pub fn target_count(&self) -> usize {
1984 self.target_count
1985 }
1986 pub fn target_ids(&self) -> &[RayCrossingTargetId] {
1987 &self.target_ids
1988 }
1989 pub fn parity(&self) -> CrossingParity {
1990 self.parity
1991 }
1992}
1993#[derive(Debug, Eq, PartialEq)]
1994pub enum RayCrossingResult {
1995 Proved {
1996 origin_contact: RayOriginContact,
1997 parity: CrossingParity,
1998 hits: Vec<RayCrossingHit>,
1999 witness: RayCrossingWitness,
2000 },
2001 Undetermined {
2002 reason: RayCrossingUndeterminedReason,
2003 origin_contact: RayOriginContact,
2004 hits: Vec<RayCrossingHit>,
2005 witness: RayCrossingWitness,
2006 },
2007}
2008
2009#[derive(Debug, PartialEq)]
2010pub enum CheckedRayCrossingResult {
2011 Proved {
2012 origin_contact: RayOriginContact,
2013 parity: CrossingParity,
2014 hits: Vec<CheckedRayCrossingHit>,
2015 witness: CheckedRayCrossingWitness,
2016 },
2017 Undetermined {
2018 reason: RayCrossingUndeterminedReason,
2019 origin_contact: RayOriginContact,
2020 hits: Vec<CheckedRayCrossingHit>,
2021 witness: CheckedRayCrossingWitness,
2022 },
2023}
2024
2025pub fn cross_ray3(
2026 ray: Ray3,
2027 targets: ExactRayCrossingTargetSet,
2028 range: crate::types::PositiveRayParameterRange,
2029 policy: RayCrossingPolicy,
2030) -> Result<RayCrossingResult, GeometryFailure> {
2031 validate_policy(&policy.root_isolation)?;
2032 if targets.targets().len() > policy.max_targets.get() {
2033 return Err(GeometryFailure::RayCrossingTargetLimitExceeded);
2034 }
2035
2036 let mut origin_contact = RayOriginContact::None;
2037 let mut hits = Vec::new();
2038 let mut undetermined = None;
2039 for target in targets.targets() {
2040 match target {
2041 ExactRayCrossingTarget::Triangle(triangle) => {
2042 let evaluation = cross_exact_triangle(&ray, triangle, &range)?;
2043 origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2044 if let Some(reason) = evaluation.reason {
2045 undetermined.get_or_insert(reason);
2046 }
2047 if let Some(hit) = evaluation.hit {
2048 hits.push(hit);
2049 }
2050 }
2051 ExactRayCrossingTarget::ImplicitSurface { id, surface } => {
2052 let evaluation =
2053 cross_exact_implicit(&ray, id, surface, &range, &policy.root_isolation)?;
2054 origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2055 if let Some(reason) = evaluation.reason {
2056 undetermined.get_or_insert(reason);
2057 }
2058 hits.extend(evaluation.hits);
2059 }
2060 ExactRayCrossingTarget::TrimmedSurface(surface) => {
2061 let evaluation =
2062 cross_exact_trimmed_surface(&ray, surface.id(), surface.candidate(), &range)?;
2063 origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2064 if let Some(reason) = evaluation.reason {
2065 undetermined.get_or_insert(reason);
2066 }
2067 if let Some(hit) = evaluation.hit {
2068 hits.push(hit);
2069 }
2070 }
2071 }
2072 if hits.len() > policy.max_hits.get() {
2073 return Err(GeometryFailure::RayCrossingHitLimitExceeded);
2074 }
2075 }
2076 hits.sort_by(
2077 |left, right| match left.parameter.compare(&right.parameter) {
2078 Ok(Ordering::Equal) => left.target_id.cmp(&right.target_id),
2079 Ok(ordering) => ordering,
2080 Err(_) => Ordering::Equal,
2081 },
2082 );
2083 if hits.windows(2).any(|pair| {
2084 pair[0]
2085 .parameter
2086 .compare(&pair[1].parameter)
2087 .is_ok_and(|ordering| ordering == Ordering::Equal)
2088 }) {
2089 undetermined.get_or_insert(RayCrossingUndeterminedReason::DuplicateParameter);
2090 }
2091 let parity = if undetermined.is_some() {
2092 CrossingParity::Undetermined
2093 } else if hits
2094 .iter()
2095 .filter(|hit| hit.contribution == CrossingContribution::Toggle)
2096 .count()
2097 % 2
2098 == 0
2099 {
2100 CrossingParity::Even
2101 } else {
2102 CrossingParity::Odd
2103 };
2104 let target_ids = targets
2105 .targets()
2106 .iter()
2107 .map(exact_target_id)
2108 .map(|id| RayCrossingTargetId(id.0.clone()))
2109 .collect();
2110 let witness = RayCrossingWitness::new(target_ids, parity);
2111 Ok(match undetermined {
2112 Some(reason) => RayCrossingResult::Undetermined {
2113 reason,
2114 origin_contact,
2115 hits,
2116 witness,
2117 },
2118 None => RayCrossingResult::Proved {
2119 origin_contact,
2120 parity,
2121 hits,
2122 witness,
2123 },
2124 })
2125}
2126
2127pub fn cross_checked_ray3(
2128 ray: CheckedRay3,
2129 targets: CheckedRayCrossingTargetSet,
2130 range: crate::types::PositiveRayParameterRange,
2131 policy: RayCrossingPolicy,
2132) -> Result<CheckedRayCrossingResult, GeometryFailure> {
2133 validate_policy(&policy.root_isolation)?;
2134 if targets.targets().len() > policy.max_targets.get() {
2135 return Err(GeometryFailure::RayCrossingTargetLimitExceeded);
2136 }
2137 let exact_ray = match exact_ray_from_checked(&ray) {
2138 Some(exact_ray) => exact_ray,
2139 None => {
2140 return Ok(checked_undetermined_result(
2141 &targets,
2142 RayCrossingUndeterminedReason::InvalidMultiplicity,
2143 ));
2144 }
2145 };
2146 let mut origin_contact = RayOriginContact::None;
2147 let mut hits = Vec::new();
2148 let mut undetermined = None;
2149 for target in targets.targets() {
2150 match target {
2151 CheckedRayCrossingTarget::Triangle(triangle) => {
2152 let exact_triangle = match exact_triangle_from_checked(triangle) {
2153 Some(exact_triangle) => exact_triangle,
2154 None => {
2155 undetermined
2156 .get_or_insert(RayCrossingUndeterminedReason::InvalidMultiplicity);
2157 continue;
2158 }
2159 };
2160 let evaluation = cross_exact_triangle(&exact_ray, &exact_triangle, &range)?;
2161 origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2162 if let Some(reason) = evaluation.reason {
2163 undetermined.get_or_insert(reason);
2164 }
2165 if let Some(hit) = evaluation.hit {
2166 hits.push(checked_hit_from_exact(
2167 hit,
2168 triangle.owner(),
2169 clone_requirement(triangle.requirement())?,
2170 triangle.source(),
2171 )?);
2172 }
2173 }
2174 CheckedRayCrossingTarget::TrimmedSurface(surface) => {
2175 let evaluation = cross_exact_trimmed_surface(
2176 &exact_ray,
2177 surface.id(),
2178 surface.candidate(),
2179 &range,
2180 )?;
2181 origin_contact = combine_origin_contact(origin_contact, evaluation.origin_contact);
2182 if let Some(reason) = evaluation.reason {
2183 undetermined.get_or_insert(reason);
2184 }
2185 if let Some(hit) = evaluation.hit {
2186 hits.push(checked_surface_hit(hit, surface)?);
2187 }
2188 }
2189 }
2190 if hits.len() > policy.max_hits.get() {
2191 return Err(GeometryFailure::RayCrossingHitLimitExceeded);
2192 }
2193 }
2194 hits.sort_by(
2195 |left, right| match compare_enclosures(left.parameter(), right.parameter()) {
2196 Ok(ordering) => ordering.then(left.target_id().cmp(right.target_id())),
2197 Err(_) => left.target_id().cmp(right.target_id()),
2198 },
2199 );
2200 if hits
2201 .windows(2)
2202 .any(|pair| enclosures_overlap(pair[0].parameter(), pair[1].parameter()).unwrap_or(false))
2203 {
2204 undetermined.get_or_insert(RayCrossingUndeterminedReason::DuplicateParameter);
2205 }
2206 let parity = if undetermined.is_some() {
2207 CrossingParity::Undetermined
2208 } else if hits
2209 .iter()
2210 .filter(|hit| hit.contribution() == CrossingContribution::Toggle)
2211 .count()
2212 % 2
2213 == 0
2214 {
2215 CrossingParity::Even
2216 } else {
2217 CrossingParity::Odd
2218 };
2219 let target_ids = targets
2220 .targets()
2221 .iter()
2222 .map(checked_target_id)
2223 .map(|id| RayCrossingTargetId(id.0.clone()))
2224 .collect();
2225 let witness = CheckedRayCrossingWitness::new(target_ids, parity);
2226 Ok(match undetermined {
2227 Some(reason) => CheckedRayCrossingResult::Undetermined {
2228 reason,
2229 origin_contact,
2230 hits,
2231 witness,
2232 },
2233 None => CheckedRayCrossingResult::Proved {
2234 origin_contact,
2235 parity,
2236 hits,
2237 witness,
2238 },
2239 })
2240}
2241
2242struct ExactTriangleCrossing {
2243 origin_contact: RayOriginContact,
2244 hit: Option<RayCrossingHit>,
2245 reason: Option<RayCrossingUndeterminedReason>,
2246}
2247
2248struct ExactImplicitCrossing {
2249 origin_contact: RayOriginContact,
2250 hits: Vec<RayCrossingHit>,
2251 reason: Option<RayCrossingUndeterminedReason>,
2252}
2253
2254fn cross_exact_implicit(
2255 ray: &Ray3,
2256 id: &RayCrossingTargetId,
2257 surface: &ImplicitSurfaceDeclaration,
2258 range: &crate::types::PositiveRayParameterRange,
2259 policy: &RootIsolationPolicy,
2260) -> Result<ExactImplicitCrossing, GeometryFailure> {
2261 let polynomial = ray_polynomial(ray, surface)?;
2262 if polynomial.degree() == 0 {
2263 return Ok(ExactImplicitCrossing {
2264 origin_contact: RayOriginContact::None,
2265 hits: Vec::new(),
2266 reason: if polynomial.coefficients()[0].is_zero() {
2267 Some(RayCrossingUndeterminedReason::Coincident)
2268 } else {
2269 None
2270 },
2271 });
2272 }
2273
2274 let bound = isolation_bound(&polynomial)?;
2275 let domain = Enclosure::new(
2276 Dyadic::new(
2277 bound.integer().negated().map_err(map_bigint_failure)?,
2278 bound.exponent(),
2279 ),
2280 bound,
2281 )
2282 .map_err(|error| GeometryFailure::CalculusFailure {
2283 error: CalculusFailure::Interval(error),
2284 })?;
2285 let constraint = ray_constraint_positive(surface)?;
2286 let problem = DerivedRootProblem {
2287 constraint,
2288 polynomial: Some(
2289 polynomial
2290 .try_clone()
2291 .map_err(calculus_polynomial_failure)?,
2292 ),
2293 domain: Some(domain),
2294 };
2295 let candidates = enumerate_root_candidates(&problem, policy)?;
2296 let isolation = build_root_isolation(&problem, candidates, policy)?;
2297 let mut hits = Vec::new();
2298 let mut reason = None;
2299 for parameter in exact_positive_integer_roots(&polynomial)? {
2300 if !range.contains_exact(¶meter)? {
2301 continue;
2302 }
2303 let (multiplicity, contribution) = implicit_root_multiplicity(&polynomial, ¶meter)?;
2304 let point = evaluate_ray_point(ray, ¶meter)?;
2305 let normal = implicit_hit_normal(surface, &point)?;
2306 hits.push(RayCrossingHit::new(
2307 RayCrossingTargetId(id.0.clone()),
2308 parameter,
2309 point,
2310 RayCrossingLocation::Interior,
2311 multiplicity,
2312 contribution,
2313 normal,
2314 ));
2315 }
2316 for bracket in isolation.brackets() {
2317 let parameter = match bracket.evidence() {
2318 RootEvidence::EvenMultiplicityTouch { point, .. }
2319 | RootEvidence::HigherOrder { point, .. }
2320 | RootEvidence::SimpleRoot { point, .. } => point.try_clone()?,
2321 RootEvidence::SignChange { .. } | RootEvidence::Undetermined { .. } => {
2322 if bracket_overlaps_positive(bracket)?
2323 && !hits.iter().any(|hit| {
2324 hit.parameter
2325 .compare(bracket.lower())
2326 .is_ok_and(|ordering| ordering != Ordering::Less)
2327 && hit
2328 .parameter
2329 .compare(bracket.upper())
2330 .is_ok_and(|ordering| ordering != Ordering::Greater)
2331 })
2332 {
2333 reason.get_or_insert(RayCrossingUndeterminedReason::InvalidMultiplicity);
2334 }
2335 continue;
2336 }
2337 };
2338 if parameter.is_zero() || !range.contains_exact(¶meter)? {
2339 continue;
2340 }
2341 if hits.iter().any(|hit| {
2342 hit.parameter
2343 .compare(¶meter)
2344 .is_ok_and(|ordering| ordering == Ordering::Equal)
2345 }) {
2346 continue;
2347 }
2348 let point = evaluate_ray_point(ray, ¶meter)?;
2349 let (multiplicity, contribution) = match bracket.evidence() {
2350 RootEvidence::SimpleRoot { .. } => {
2351 (CrossingMultiplicity::Simple, CrossingContribution::Toggle)
2352 }
2353 RootEvidence::HigherOrder { order, .. } if order % 2 == 1 => (
2354 CrossingMultiplicity::Odd(*order),
2355 CrossingContribution::Toggle,
2356 ),
2357 RootEvidence::EvenMultiplicityTouch { order, .. }
2358 | RootEvidence::HigherOrder { order, .. } => (
2359 CrossingMultiplicity::Even(*order),
2360 CrossingContribution::NoToggle,
2361 ),
2362 _ => (
2363 CrossingMultiplicity::Undetermined,
2364 CrossingContribution::Undetermined,
2365 ),
2366 };
2367 let normal = implicit_hit_normal(surface, &point)?;
2368 hits.push(RayCrossingHit::new(
2369 RayCrossingTargetId(id.0.clone()),
2370 parameter,
2371 point,
2372 RayCrossingLocation::Interior,
2373 multiplicity,
2374 contribution,
2375 normal,
2376 ));
2377 }
2378 if hits.is_empty()
2379 && matches!(
2380 isolation.completeness().status(),
2381 WitnessStatus::Undetermined { .. }
2382 )
2383 {
2384 reason.get_or_insert(RayCrossingUndeterminedReason::InvalidMultiplicity);
2385 }
2386 Ok(ExactImplicitCrossing {
2387 origin_contact: RayOriginContact::None,
2388 hits,
2389 reason,
2390 })
2391}
2392
2393fn combine_origin_contact(left: RayOriginContact, right: RayOriginContact) -> RayOriginContact {
2394 match (left, right) {
2395 (RayOriginContact::Boundary, _) | (_, RayOriginContact::Boundary) => {
2396 RayOriginContact::Boundary
2397 }
2398 (RayOriginContact::Interior, _) | (_, RayOriginContact::Interior) => {
2399 RayOriginContact::Interior
2400 }
2401 _ => RayOriginContact::None,
2402 }
2403}
2404
2405fn cross_exact_trimmed_surface(
2406 ray: &Ray3,
2407 id: &RayCrossingTargetId,
2408 candidate: &SurfaceCrossingCandidate,
2409 range: &crate::types::PositiveRayParameterRange,
2410) -> Result<ExactTriangleCrossing, GeometryFailure> {
2411 let Some(chart) = affine_chart(candidate.declaration().chart().surface())? else {
2412 return Ok(ExactTriangleCrossing {
2413 origin_contact: RayOriginContact::None,
2414 hit: None,
2415 reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2416 });
2417 };
2418 let normal = cross_vector(&chart.du, &chart.dv)?;
2419 if vector_is_zero(&normal)? {
2420 return Ok(ExactTriangleCrossing {
2421 origin_contact: RayOriginContact::None,
2422 hit: None,
2423 reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2424 });
2425 }
2426 let origin_offset = Vector3 {
2427 x: chart.origin.x.sub(&ray.origin().x)?,
2428 y: chart.origin.y.sub(&ray.origin().y)?,
2429 z: chart.origin.z.sub(&ray.origin().z)?,
2430 };
2431 let denominator = dot_vector(&normal, ray.direction().vector())?;
2432 let numerator = dot_vector(&normal, &origin_offset)?;
2433 if denominator.is_zero() {
2434 if !numerator.is_zero() {
2435 return Ok(ExactTriangleCrossing {
2436 origin_contact: RayOriginContact::None,
2437 hit: None,
2438 reason: None,
2439 });
2440 }
2441 let Some((u, v)) = plane_parameters(&chart, ray.origin())? else {
2442 return Ok(ExactTriangleCrossing {
2443 origin_contact: RayOriginContact::None,
2444 hit: None,
2445 reason: Some(RayCrossingUndeterminedReason::Coincident),
2446 });
2447 };
2448 let (origin_contact, reason) = surface_origin_classification(candidate, &u, &v)?;
2449 return Ok(ExactTriangleCrossing {
2450 origin_contact,
2451 hit: None,
2452 reason: reason.or(Some(RayCrossingUndeterminedReason::Coincident)),
2453 });
2454 }
2455 let parameter = numerator.div(&denominator)?;
2456 let point_on_ray = evaluate_ray_point(ray, ¶meter)?;
2457 let Some((u, v)) = plane_parameters(&chart, &point_on_ray)? else {
2458 return Ok(ExactTriangleCrossing {
2459 origin_contact: RayOriginContact::None,
2460 hit: None,
2461 reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2462 });
2463 };
2464 let (origin_contact, origin_reason) = if parameter.is_zero() {
2465 surface_origin_classification(candidate, &u, &v)?
2466 } else {
2467 (RayOriginContact::None, None)
2468 };
2469 if !range.contains_exact(¶meter)? {
2470 return Ok(ExactTriangleCrossing {
2471 origin_contact,
2472 hit: None,
2473 reason: origin_reason,
2474 });
2475 }
2476 if !candidate.domain().contains(&u, &v)? {
2477 return Ok(ExactTriangleCrossing {
2478 origin_contact,
2479 hit: None,
2480 reason: origin_reason,
2481 });
2482 }
2483 let (location, hit_reason) = surface_hit_classification(candidate, &u, &v)?;
2484 let Some(location) = location else {
2485 return Ok(ExactTriangleCrossing {
2486 origin_contact,
2487 hit: None,
2488 reason: origin_reason,
2489 });
2490 };
2491 let reason = origin_reason.or(hit_reason);
2492 let contribution = if reason.is_some() {
2493 CrossingContribution::Undetermined
2494 } else {
2495 CrossingContribution::Toggle
2496 };
2497 let witness = evaluate_surface_witness_exact(
2498 candidate.declaration().chart(),
2499 candidate.domain(),
2500 &u,
2501 &v,
2502 )?;
2503 let point = match witness {
2504 SurfaceEvaluationWitness::Exact { point, .. } => point,
2505 SurfaceEvaluationWitness::Certified { .. } => {
2506 return Ok(ExactTriangleCrossing {
2507 origin_contact,
2508 hit: None,
2509 reason: Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
2510 });
2511 }
2512 };
2513 Ok(ExactTriangleCrossing {
2514 origin_contact,
2515 hit: Some(RayCrossingHit::new(
2516 RayCrossingTargetId(id.0.clone()),
2517 parameter,
2518 point,
2519 location,
2520 CrossingMultiplicity::Simple,
2521 contribution,
2522 ray_normal_from_vector(normal)?,
2523 )),
2524 reason,
2525 })
2526}
2527
2528struct AffineSurfaceChart {
2529 origin: Point3,
2530 du: Vector3,
2531 dv: Vector3,
2532}
2533
2534fn affine_chart(
2535 surface: &neco_calculus::RationalSurfacePolynomials,
2536) -> Result<Option<AffineSurfaceChart>, GeometryFailure> {
2537 let Some([origin_x, du_x, dv_x]) = affine_form(&surface.x)? else {
2538 return Ok(None);
2539 };
2540 let Some([origin_y, du_y, dv_y]) = affine_form(&surface.y)? else {
2541 return Ok(None);
2542 };
2543 let Some([origin_z, du_z, dv_z]) = affine_form(&surface.z)? else {
2544 return Ok(None);
2545 };
2546 Ok(Some(AffineSurfaceChart {
2547 origin: Point3 {
2548 x: origin_x,
2549 y: origin_y,
2550 z: origin_z,
2551 },
2552 du: Vector3 {
2553 x: du_x,
2554 y: du_y,
2555 z: du_z,
2556 },
2557 dv: Vector3 {
2558 x: dv_x,
2559 y: dv_y,
2560 z: dv_z,
2561 },
2562 }))
2563}
2564
2565fn affine_form(
2566 polynomial: &SurfacePolynomial,
2567) -> Result<Option<[RealAlgebraic; 3]>, GeometryFailure> {
2568 let mut constant = real_zero()?;
2569 let mut du = real_zero()?;
2570 let mut dv = real_zero()?;
2571 for term in polynomial.terms() {
2572 if term.exponent_u > 1 || term.exponent_v > 1 || term.exponent_u + term.exponent_v > 1 {
2573 return Ok(None);
2574 }
2575 let coefficient = RealAlgebraic::from_reduced_rational(&term.coefficient)
2576 .map_err(GeometryFailure::AlgebraFailure)?;
2577 match (term.exponent_u, term.exponent_v) {
2578 (0, 0) => constant = coefficient,
2579 (1, 0) => du = coefficient,
2580 (0, 1) => dv = coefficient,
2581 _ => return Ok(None),
2582 }
2583 }
2584 Ok(Some([constant, du, dv]))
2585}
2586
2587fn plane_parameters(
2588 chart: &AffineSurfaceChart,
2589 point: &Point3,
2590) -> Result<Option<(RealAlgebraic, RealAlgebraic)>, GeometryFailure> {
2591 let offset = Vector3 {
2592 x: point.x.sub(&chart.origin.x)?,
2593 y: point.y.sub(&chart.origin.y)?,
2594 z: point.z.sub(&chart.origin.z)?,
2595 };
2596 let pairs = [
2597 (&chart.du.x, &chart.dv.x, &offset.x),
2598 (&chart.du.y, &chart.dv.y, &offset.y),
2599 (&chart.du.z, &chart.dv.z, &offset.z),
2600 ];
2601 for first in 0..3 {
2602 for second in (first + 1)..3 {
2603 if let Some(values) = solve_2x2(
2604 [pairs[first].0, pairs[first].1, pairs[first].2],
2605 [pairs[second].0, pairs[second].1, pairs[second].2],
2606 )? {
2607 return Ok(Some(values));
2608 }
2609 }
2610 }
2611 Ok(None)
2612}
2613
2614fn solve_2x2(
2615 first: [&RealAlgebraic; 3],
2616 second: [&RealAlgebraic; 3],
2617) -> Result<Option<(RealAlgebraic, RealAlgebraic)>, GeometryFailure> {
2618 let det = first[0].mul(second[1])?.sub(&first[1].mul(second[0])?)?;
2619 if det.is_zero() {
2620 return Ok(None);
2621 }
2622 let u = first[2]
2623 .mul(second[1])?
2624 .sub(&first[1].mul(second[2])?)?
2625 .div(&det)?;
2626 let v = first[0]
2627 .mul(second[2])?
2628 .sub(&first[2].mul(second[0])?)?
2629 .div(&det)?;
2630 Ok(Some((u, v)))
2631}
2632
2633fn surface_origin_classification(
2634 candidate: &SurfaceCrossingCandidate,
2635 u: &RealAlgebraic,
2636 v: &RealAlgebraic,
2637) -> Result<(RayOriginContact, Option<RayCrossingUndeterminedReason>), GeometryFailure> {
2638 if !candidate.domain().contains(u, v)? {
2639 return Ok((RayOriginContact::None, None));
2640 }
2641 let (location, reason) = surface_hit_classification(candidate, u, v)?;
2642 Ok(match location {
2643 Some(RayCrossingLocation::Interior) => (RayOriginContact::Interior, reason),
2644 Some(_) => (
2645 RayOriginContact::Boundary,
2646 reason.or(Some(RayCrossingUndeterminedReason::TrimBoundary)),
2647 ),
2648 None => (RayOriginContact::None, None),
2649 })
2650}
2651
2652fn surface_hit_classification(
2653 candidate: &SurfaceCrossingCandidate,
2654 u: &RealAlgebraic,
2655 v: &RealAlgebraic,
2656) -> Result<
2657 (
2658 Option<RayCrossingLocation>,
2659 Option<RayCrossingUndeterminedReason>,
2660 ),
2661 GeometryFailure,
2662> {
2663 if let Some(reason) = unresolved_seam_reason(candidate.declaration(), u, v)? {
2664 return Ok((Some(RayCrossingLocation::Seam), Some(reason)));
2665 }
2666 if paired_seam_contains(candidate.declaration(), u, v)? {
2667 return Ok((Some(RayCrossingLocation::Interior), None));
2668 }
2669 match candidate.classify(u, v)? {
2670 TrimClassification::Outer => Ok((Some(RayCrossingLocation::Interior), None)),
2671 TrimClassification::Hole | TrimClassification::TrimExterior => Ok((None, None)),
2672 TrimClassification::TrimBoundary => {
2673 if hole_boundary_contains(candidate.declaration(), u, v)? {
2674 Ok((
2675 Some(RayCrossingLocation::HoleBoundary),
2676 Some(RayCrossingUndeterminedReason::HoleBoundary),
2677 ))
2678 } else {
2679 Ok((
2680 Some(RayCrossingLocation::TrimBoundary),
2681 Some(RayCrossingUndeterminedReason::TrimBoundary),
2682 ))
2683 }
2684 }
2685 }
2686}
2687
2688fn unresolved_seam_reason(
2689 declaration: &crate::types::TrimmedSurfaceDeclaration,
2690 u: &RealAlgebraic,
2691 v: &RealAlgebraic,
2692) -> Result<Option<RayCrossingUndeterminedReason>, GeometryFailure> {
2693 for seam in declaration.seams() {
2694 if let SeamContact::Undetermined { first, second } = seam {
2695 if parameter_equals(first.parameter(), u, v)?
2696 || parameter_equals(second.parameter(), u, v)?
2697 {
2698 return Ok(Some(RayCrossingUndeterminedReason::UnresolvedSeam));
2699 }
2700 }
2701 }
2702 Ok(None)
2703}
2704
2705fn paired_seam_contains(
2706 declaration: &crate::types::TrimmedSurfaceDeclaration,
2707 u: &RealAlgebraic,
2708 v: &RealAlgebraic,
2709) -> Result<bool, GeometryFailure> {
2710 for seam in declaration.seams() {
2711 if let SeamContact::Paired(paired) = seam {
2712 if parameter_equals(paired.first().parameter(), u, v)?
2713 || parameter_equals(paired.second().parameter(), u, v)?
2714 {
2715 return Ok(true);
2716 }
2717 }
2718 }
2719 Ok(false)
2720}
2721
2722fn hole_boundary_contains(
2723 declaration: &crate::types::TrimmedSurfaceDeclaration,
2724 u: &RealAlgebraic,
2725 v: &RealAlgebraic,
2726) -> Result<bool, GeometryFailure> {
2727 for hole in declaration.holes() {
2728 if point_on_loop(u, v, hole.vertices())? {
2729 return Ok(true);
2730 }
2731 }
2732 Ok(false)
2733}
2734
2735fn parameter_equals(
2736 point: &SurfaceParameterPoint,
2737 u: &RealAlgebraic,
2738 v: &RealAlgebraic,
2739) -> Result<bool, GeometryFailure> {
2740 Ok(point.u().compare(u)? == Ordering::Equal && point.v().compare(v)? == Ordering::Equal)
2741}
2742
2743fn vector_is_zero(vector: &Vector3) -> Result<bool, GeometryFailure> {
2744 Ok(vector.x.is_zero() && vector.y.is_zero() && vector.z.is_zero())
2745}
2746
2747fn real_zero() -> Result<RealAlgebraic, GeometryFailure> {
2748 RealAlgebraic::from_integer(BigInt::zero()).map_err(GeometryFailure::AlgebraFailure)
2749}
2750
2751fn real_abs(value: &RealAlgebraic) -> Result<RealAlgebraic, GeometryFailure> {
2752 let zero = real_zero()?;
2753 if value.compare(&zero)? == Ordering::Less {
2754 zero.sub(value).map_err(GeometryFailure::AlgebraFailure)
2755 } else {
2756 value.try_clone().map_err(GeometryFailure::AlgebraFailure)
2757 }
2758}
2759
2760fn exact_positive_integer_roots(
2761 polynomial: &Polynomial,
2762) -> Result<Vec<RealAlgebraic>, GeometryFailure> {
2763 let mut roots = Vec::new();
2764 for value in 1..=32 {
2765 let parameter =
2766 RealAlgebraic::from_integer(BigInt::try_from(value).map_err(map_bigint_failure)?)?;
2767 if polynomial
2768 .evaluate(¶meter)
2769 .map_err(calculus_polynomial_failure)?
2770 .is_zero()
2771 {
2772 roots.push(parameter);
2773 }
2774 }
2775 Ok(roots)
2776}
2777
2778fn implicit_root_multiplicity(
2779 polynomial: &Polynomial,
2780 parameter: &RealAlgebraic,
2781) -> Result<(CrossingMultiplicity, CrossingContribution), GeometryFailure> {
2782 let mut order = 1_usize;
2783 let mut current = polynomial
2784 .try_clone()
2785 .map_err(calculus_polynomial_failure)?;
2786 loop {
2787 let derivative = current
2788 .derivative(DerivativeOrder::new(1))
2789 .map_err(calculus_polynomial_failure)?;
2790 if !derivative
2791 .evaluate(parameter)
2792 .map_err(calculus_polynomial_failure)?
2793 .is_zero()
2794 {
2795 break;
2796 }
2797 order += 1;
2798 if order > 16 {
2799 return Ok((
2800 CrossingMultiplicity::Undetermined,
2801 CrossingContribution::Undetermined,
2802 ));
2803 }
2804 current = derivative;
2805 }
2806 Ok(match order {
2807 1 => (CrossingMultiplicity::Simple, CrossingContribution::Toggle),
2808 order if order % 2 == 1 => (
2809 CrossingMultiplicity::Odd(order),
2810 CrossingContribution::Toggle,
2811 ),
2812 order => (
2813 CrossingMultiplicity::Even(order),
2814 CrossingContribution::NoToggle,
2815 ),
2816 })
2817}
2818
2819fn bracket_overlaps_positive(bracket: &RootBracket) -> Result<bool, GeometryFailure> {
2820 Ok(bracket.upper().compare(&real_zero()?)? == Ordering::Greater)
2821}
2822
2823fn isolation_bound(polynomial: &Polynomial) -> Result<Dyadic, GeometryFailure> {
2824 let fallback = Dyadic::new(BigInt::try_from(1024_i32).map_err(map_bigint_failure)?, 0);
2825 let coefficients = polynomial.coefficients();
2826 let Some(degree) = coefficients.iter().rposition(|value| !value.is_zero()) else {
2827 return Ok(fallback);
2828 };
2829 let leading = real_abs(&coefficients[degree])?;
2830 if leading.is_zero() {
2831 return Ok(fallback);
2832 }
2833 let mut max_ratio = real_zero()?;
2834 for coefficient in &coefficients[..degree] {
2835 let ratio = real_abs(coefficient)?.div(&leading)?;
2836 if ratio.compare(&max_ratio)? == Ordering::Greater {
2837 max_ratio = ratio;
2838 }
2839 }
2840 let bound =
2841 RealAlgebraic::from_integer(BigInt::one().map_err(map_bigint_failure)?)?.add(&max_ratio)?;
2842 Ok(real_to_dyadic(&bound).unwrap_or(fallback))
2843}
2844
2845fn checked_undetermined_result(
2846 targets: &CheckedRayCrossingTargetSet,
2847 reason: RayCrossingUndeterminedReason,
2848) -> CheckedRayCrossingResult {
2849 let target_ids = targets
2850 .targets()
2851 .iter()
2852 .map(checked_target_id)
2853 .map(|id| RayCrossingTargetId(id.0.clone()))
2854 .collect();
2855 CheckedRayCrossingResult::Undetermined {
2856 reason,
2857 origin_contact: RayOriginContact::None,
2858 hits: Vec::new(),
2859 witness: CheckedRayCrossingWitness::new(target_ids, CrossingParity::Undetermined),
2860 }
2861}
2862
2863fn exact_ray_from_checked(ray: &CheckedRay3) -> Option<Ray3> {
2864 let origin = Point3 {
2865 x: f64_to_real(ray.origin()[0])?,
2866 y: f64_to_real(ray.origin()[1])?,
2867 z: f64_to_real(ray.origin()[2])?,
2868 };
2869 let direction = Vector3 {
2870 x: f64_to_real(ray.direction()[0])?,
2871 y: f64_to_real(ray.direction()[1])?,
2872 z: f64_to_real(ray.direction()[2])?,
2873 };
2874 Some(Ray3::new(
2875 origin,
2876 neco_geometry_foundation::Direction3::try_from_vector(direction).ok()?,
2877 ))
2878}
2879
2880fn exact_triangle_from_checked(triangle: &CheckedTriangleTarget) -> Option<ExactTriangleTarget> {
2881 ExactTriangleTarget::new(
2882 RayCrossingTargetId(triangle.id.0.clone()),
2883 Point3 {
2884 x: f64_to_real(triangle.vertices[0][0])?,
2885 y: f64_to_real(triangle.vertices[0][1])?,
2886 z: f64_to_real(triangle.vertices[0][2])?,
2887 },
2888 Point3 {
2889 x: f64_to_real(triangle.vertices[1][0])?,
2890 y: f64_to_real(triangle.vertices[1][1])?,
2891 z: f64_to_real(triangle.vertices[1][2])?,
2892 },
2893 Point3 {
2894 x: f64_to_real(triangle.vertices[2][0])?,
2895 y: f64_to_real(triangle.vertices[2][1])?,
2896 z: f64_to_real(triangle.vertices[2][2])?,
2897 },
2898 )
2899 .ok()
2900}
2901
2902fn f64_to_real(value: f64) -> Option<RealAlgebraic> {
2903 if !value.is_finite() {
2904 return None;
2905 }
2906 let integer = i32::try_from(value as i64).ok()?;
2907 if value != f64::from(integer) {
2908 return None;
2909 }
2910 RealAlgebraic::from_integer(BigInt::try_from(integer).ok()?).ok()
2911}
2912
2913fn checked_hit_from_exact(
2914 hit: RayCrossingHit,
2915 owner: OwnerId,
2916 requirement: ExactExpressionRequirement,
2917 source: NecoImplementationSource,
2918) -> Result<CheckedRayCrossingHit, GeometryFailure> {
2919 Ok(CheckedRayCrossingHit::from_exact_hit(
2920 RayCrossingTargetId(hit.target_id.0.clone()),
2921 real_to_enclosure(hit.parameter())?,
2922 CoordinateEnclosure3 {
2923 x: real_to_enclosure(&hit.point().x)?,
2924 y: real_to_enclosure(&hit.point().y)?,
2925 z: real_to_enclosure(&hit.point().z)?,
2926 },
2927 CheckedHitGeometry {
2928 location: hit.location(),
2929 multiplicity: hit.multiplicity(),
2930 contribution: hit.contribution(),
2931 owner,
2932 requirement,
2933 source,
2934 normal: hit.normal,
2935 },
2936 ))
2937}
2938
2939fn checked_surface_hit(
2940 hit: RayCrossingHit,
2941 surface: &CheckedTrimmedParametricSurfaceTarget,
2942) -> Result<CheckedRayCrossingHit, GeometryFailure> {
2943 let parameter = real_to_enclosure(hit.parameter())?;
2944 let point = match recover_checked_surface_point(&hit, surface)? {
2945 Some(point) => point,
2946 None => CoordinateEnclosure3 {
2947 x: real_to_enclosure(&hit.point().x)?,
2948 y: real_to_enclosure(&hit.point().y)?,
2949 z: real_to_enclosure(&hit.point().z)?,
2950 },
2951 };
2952 Ok(CheckedRayCrossingHit::from_exact_hit(
2953 RayCrossingTargetId(hit.target_id.0.clone()),
2954 parameter,
2955 point,
2956 CheckedHitGeometry {
2957 location: hit.location(),
2958 multiplicity: hit.multiplicity(),
2959 contribution: hit.contribution(),
2960 owner: surface.owner(),
2961 requirement: clone_requirement(surface.requirement())?,
2962 source: surface.source(),
2963 normal: hit.normal,
2964 },
2965 ))
2966}
2967
2968fn recover_checked_surface_point(
2969 hit: &RayCrossingHit,
2970 surface: &CheckedTrimmedParametricSurfaceTarget,
2971) -> Result<Option<CoordinateEnclosure3>, GeometryFailure> {
2972 let Some(chart) = affine_chart(surface.candidate().declaration().chart().surface())? else {
2973 return Ok(None);
2974 };
2975 let Some((u, v)) = plane_parameters(&chart, hit.point())? else {
2976 return Ok(None);
2977 };
2978 let u_enclosure = real_to_enclosure(&u)?;
2979 let v_enclosure = real_to_enclosure(&v)?;
2980 match evaluate_surface_witness_checked(
2981 surface.candidate().declaration().chart(),
2982 surface.candidate().domain(),
2983 &u_enclosure,
2984 &v_enclosure,
2985 surface.owner(),
2986 clone_requirement(surface.requirement())?,
2987 surface.source(),
2988 ) {
2989 Ok(SurfaceEvaluationWitness::Certified { x, y, z, .. }) => {
2990 Ok(Some(CoordinateEnclosure3 { x, y, z: *z }))
2991 }
2992 _ => Ok(None),
2993 }
2994}
2995
2996fn real_to_enclosure(value: &RealAlgebraic) -> Result<Enclosure, GeometryFailure> {
2997 let dyadic = real_to_dyadic(value)?;
2998 Enclosure::new(dyadic.try_clone().map_err(map_bigint_failure)?, dyadic).map_err(|error| {
2999 GeometryFailure::CalculusFailure {
3000 error: CalculusFailure::Interval(error),
3001 }
3002 })
3003}
3004
3005fn compare_enclosures(left: &Enclosure, right: &Enclosure) -> Result<Ordering, GeometryFailure> {
3006 dyadic_to_real(left.lower())?
3007 .compare(&dyadic_to_real(right.lower())?)
3008 .map_err(GeometryFailure::AlgebraFailure)
3009}
3010
3011fn enclosures_overlap(left: &Enclosure, right: &Enclosure) -> Result<bool, GeometryFailure> {
3012 let left_lower = dyadic_to_real(left.lower())?;
3013 let left_upper = dyadic_to_real(left.upper())?;
3014 let right_lower = dyadic_to_real(right.lower())?;
3015 let right_upper = dyadic_to_real(right.upper())?;
3016 Ok(left_lower.compare(&right_upper)? != Ordering::Greater
3017 && right_lower.compare(&left_upper)? != Ordering::Greater)
3018}
3019
3020fn cross_exact_triangle(
3021 ray: &Ray3,
3022 triangle: &ExactTriangleTarget,
3023 range: &crate::types::PositiveRayParameterRange,
3024) -> Result<ExactTriangleCrossing, GeometryFailure> {
3025 let ab = subtract_point(&triangle.b, &triangle.a)?;
3026 let ac = subtract_point(&triangle.c, &triangle.a)?;
3027 let normal = cross_vector(&ab, &ac)?;
3028 let origin_offset = subtract_point(&triangle.a, ray.origin())?;
3029 let denominator = dot_vector(&normal, ray.direction().vector())?;
3030 let numerator = dot_vector(&normal, &origin_offset)?;
3031 if denominator.is_zero() {
3032 return Ok(ExactTriangleCrossing {
3033 origin_contact: RayOriginContact::None,
3034 hit: None,
3035 reason: if numerator.is_zero() {
3036 Some(RayCrossingUndeterminedReason::CoplanarOverlap)
3037 } else {
3038 None
3039 },
3040 });
3041 }
3042 let parameter = numerator.div(&denominator)?;
3043 let point = evaluate_ray_point(ray, ¶meter)?;
3044 let location = triangle_location(&point, triangle, &normal)?;
3045 let origin_location = if numerator.is_zero() {
3046 triangle_location(ray.origin(), triangle, &normal)?
3047 } else {
3048 None
3049 };
3050 let origin_contact = match origin_location {
3051 Some(RayCrossingLocation::Interior) => RayOriginContact::Interior,
3052 Some(_) => RayOriginContact::Boundary,
3053 None => RayOriginContact::None,
3054 };
3055 if !range.contains_exact(¶meter)? {
3056 return Ok(ExactTriangleCrossing {
3057 origin_contact,
3058 hit: None,
3059 reason: match origin_location {
3060 Some(RayCrossingLocation::Edge) => Some(RayCrossingUndeterminedReason::Edge),
3061 Some(RayCrossingLocation::Vertex) => Some(RayCrossingUndeterminedReason::Vertex),
3062 _ => None,
3063 },
3064 });
3065 }
3066 let Some(location) = location else {
3067 return Ok(ExactTriangleCrossing {
3068 origin_contact,
3069 hit: None,
3070 reason: match origin_location {
3071 Some(RayCrossingLocation::Edge) => Some(RayCrossingUndeterminedReason::Edge),
3072 Some(RayCrossingLocation::Vertex) => Some(RayCrossingUndeterminedReason::Vertex),
3073 _ => None,
3074 },
3075 });
3076 };
3077 let reason = match location {
3078 RayCrossingLocation::Interior => None,
3079 RayCrossingLocation::Edge => Some(RayCrossingUndeterminedReason::Edge),
3080 RayCrossingLocation::Vertex => Some(RayCrossingUndeterminedReason::Vertex),
3081 _ => Some(RayCrossingUndeterminedReason::InvalidMultiplicity),
3082 };
3083 let contribution = if reason.is_some() {
3084 CrossingContribution::Undetermined
3085 } else {
3086 CrossingContribution::Toggle
3087 };
3088 Ok(ExactTriangleCrossing {
3089 origin_contact,
3090 hit: Some(RayCrossingHit::new(
3091 RayCrossingTargetId(triangle.id.0.clone()),
3092 parameter,
3093 point,
3094 location,
3095 CrossingMultiplicity::Simple,
3096 contribution,
3097 ray_normal_from_vector(normal)?,
3098 )),
3099 reason,
3100 })
3101}
3102
3103fn ray_normal_from_vector(vector: Vector3) -> Result<RayNormal, GeometryFailure> {
3104 match Direction3::try_from_vector(vector) {
3105 Ok(direction) => Ok(RayNormal::Regular(direction)),
3106 Err(neco_geometry_foundation::GeometryFailure::ZeroDirection) => {
3107 Ok(RayNormal::Undetermined)
3108 }
3109 Err(error) => Err(GeometryFailure::FoundationFailure { error }),
3110 }
3111}
3112
3113fn implicit_hit_normal(
3114 surface: &ImplicitSurfaceDeclaration,
3115 point: &Point3,
3116) -> Result<RayNormal, GeometryFailure> {
3117 ray_normal_from_vector(implicit_gradient(surface, point)?)
3118}
3119
3120fn implicit_gradient(
3121 surface: &ImplicitSurfaceDeclaration,
3122 point: &Point3,
3123) -> Result<Vector3, GeometryFailure> {
3124 let mut components = [
3125 RealAlgebraic::from_integer(BigInt::zero())?,
3126 RealAlgebraic::from_integer(BigInt::zero())?,
3127 RealAlgebraic::from_integer(BigInt::zero())?,
3128 ];
3129 for term in surface.equation().terms() {
3130 let values = [&point.x, &point.y, &point.z];
3131 let exponents = [term.exponent_x(), term.exponent_y(), term.exponent_z()];
3132 for component in 0..3 {
3133 if exponents[component] == 0 {
3134 continue;
3135 }
3136 let mut value = term.coefficient().try_clone()?;
3137 value = value.mul(&RealAlgebraic::from_integer(
3138 BigInt::try_from(exponents[component]).map_err(map_bigint_failure)?,
3139 )?)?;
3140 for axis in 0..3 {
3141 let power = if axis == component {
3142 exponents[axis] - 1
3143 } else {
3144 exponents[axis]
3145 };
3146 for _ in 0..power {
3147 value = value.mul(values[axis])?;
3148 }
3149 }
3150 components[component] = components[component].add(&value)?;
3151 }
3152 }
3153 Ok(Vector3 {
3154 x: components[0].try_clone()?,
3155 y: components[1].try_clone()?,
3156 z: components[2].try_clone()?,
3157 })
3158}
3159
3160fn subtract_point(left: &Point3, right: &Point3) -> Result<Vector3, GeometryFailure> {
3161 Ok(Vector3 {
3162 x: left.x.sub(&right.x)?,
3163 y: left.y.sub(&right.y)?,
3164 z: left.z.sub(&right.z)?,
3165 })
3166}
3167
3168fn cross_vector(left: &Vector3, right: &Vector3) -> Result<Vector3, GeometryFailure> {
3169 Ok(Vector3 {
3170 x: left.y.mul(&right.z)?.sub(&left.z.mul(&right.y)?)?,
3171 y: left.z.mul(&right.x)?.sub(&left.x.mul(&right.z)?)?,
3172 z: left.x.mul(&right.y)?.sub(&left.y.mul(&right.x)?)?,
3173 })
3174}
3175
3176fn dot_vector(left: &Vector3, right: &Vector3) -> Result<RealAlgebraic, GeometryFailure> {
3177 Ok(left
3178 .x
3179 .mul(&right.x)?
3180 .add(&left.y.mul(&right.y)?)?
3181 .add(&left.z.mul(&right.z)?)?)
3182}
3183
3184fn triangle_location(
3185 point: &Point3,
3186 triangle: &ExactTriangleTarget,
3187 normal: &Vector3,
3188) -> Result<Option<RayCrossingLocation>, GeometryFailure> {
3189 let pa = subtract_point(&triangle.a, point)?;
3190 let pb = subtract_point(&triangle.b, point)?;
3191 let pc = subtract_point(&triangle.c, point)?;
3192 let a = dot_vector(normal, &cross_vector(&pb, &pc)?)?;
3193 let b = dot_vector(normal, &cross_vector(&pc, &pa)?)?;
3194 let c = dot_vector(normal, &cross_vector(&pa, &pb)?)?;
3195 let signs = [a, b, c];
3196 let zero = real_zero()?;
3197 let positive = signs
3198 .iter()
3199 .filter(|value| value.compare(&zero).is_ok_and(|v| v == Ordering::Greater))
3200 .count();
3201 let negative = signs
3202 .iter()
3203 .filter(|value| value.compare(&zero).is_ok_and(|v| v == Ordering::Less))
3204 .count();
3205 if positive != 0 && negative != 0 {
3206 return Ok(None);
3207 }
3208 let zeroes = signs.iter().filter(|value| value.is_zero()).count();
3209 Ok(Some(match zeroes {
3210 0 => RayCrossingLocation::Interior,
3211 1 => RayCrossingLocation::Edge,
3212 _ => RayCrossingLocation::Vertex,
3213 }))
3214}
3215
3216fn ray_polynomial(
3217 ray: &Ray3,
3218 surface: &ImplicitSurfaceDeclaration,
3219) -> Result<Polynomial, GeometryFailure> {
3220 let mut result = Polynomial::zero().map_err(calculus_polynomial_failure)?;
3221 for term in surface.equation().terms() {
3222 let x = affine_polynomial(
3223 &ray.origin().x,
3224 &ray.direction().vector().x,
3225 term.exponent_x(),
3226 )?;
3227 let y = affine_polynomial(
3228 &ray.origin().y,
3229 &ray.direction().vector().y,
3230 term.exponent_y(),
3231 )?;
3232 let z = affine_polynomial(
3233 &ray.origin().z,
3234 &ray.direction().vector().z,
3235 term.exponent_z(),
3236 )?;
3237 let term_polynomial = polynomial_mul(&polynomial_mul(&x, &y)?, &z)?;
3238 let coefficient = term.coefficient().try_clone()?;
3239 let scaled = term_polynomial
3240 .coefficients()
3241 .iter()
3242 .map(|value| {
3243 value
3244 .mul(&coefficient)
3245 .map_err(GeometryFailure::AlgebraFailure)
3246 })
3247 .collect::<Result<Vec<_>, _>>()?;
3248 result = polynomial_add(
3249 &result,
3250 &Polynomial::from_coefficients(scaled).map_err(calculus_polynomial_failure)?,
3251 )?;
3252 }
3253 Ok(result)
3254}
3255
3256fn polynomial_add(left: &Polynomial, right: &Polynomial) -> Result<Polynomial, GeometryFailure> {
3257 let length = left.coefficients().len().max(right.coefficients().len());
3258 let zero = RealAlgebraic::from_integer(BigInt::zero())?;
3259 let mut coefficients = Vec::with_capacity(length);
3260 for index in 0..length {
3261 let lhs = left.coefficients().get(index).unwrap_or(&zero);
3262 let rhs = right.coefficients().get(index).unwrap_or(&zero);
3263 coefficients.push(lhs.add(rhs)?);
3264 }
3265 Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)
3266}
3267
3268fn polynomial_mul(left: &Polynomial, right: &Polynomial) -> Result<Polynomial, GeometryFailure> {
3269 let mut coefficients = Vec::with_capacity(left.degree() + right.degree() + 1);
3270 for _ in 0..=left.degree() + right.degree() {
3271 coefficients.push(RealAlgebraic::from_integer(BigInt::zero())?);
3272 }
3273 for (left_index, lhs) in left.coefficients().iter().enumerate() {
3274 for (right_index, rhs) in right.coefficients().iter().enumerate() {
3275 let product = lhs.mul(rhs)?;
3276 coefficients[left_index + right_index] =
3277 coefficients[left_index + right_index].add(&product)?;
3278 }
3279 }
3280 Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)
3281}
3282
3283fn affine_polynomial(
3284 origin: &RealAlgebraic,
3285 direction: &RealAlgebraic,
3286 exponent: u32,
3287) -> Result<Polynomial, GeometryFailure> {
3288 let mut result = Polynomial::constant(RealAlgebraic::from_integer(
3289 BigInt::one().map_err(map_bigint_failure)?,
3290 )?)
3291 .map_err(calculus_polynomial_failure)?;
3292 let affine =
3293 Polynomial::from_coefficients(alloc::vec![origin.try_clone()?, direction.try_clone()?])
3294 .map_err(calculus_polynomial_failure)?;
3295 for _ in 0..exponent {
3296 result = polynomial_mul(&result, &affine)?;
3297 }
3298 Ok(result)
3299}
3300
3301fn ray_constraint_positive(
3302 surface: &ImplicitSurfaceDeclaration,
3303) -> Result<IntersectionConstraint, GeometryFailure> {
3304 let declaration = ShapeDeclaration::ImplicitSurface(ImplicitSurfaceDeclaration::new(
3305 clone_polynomial3(surface.equation())?,
3306 ));
3307 let left = clone_declaration(&declaration)?;
3308 Ok(IntersectionConstraint::new(
3309 IntersectionOperand::Declaration(left),
3310 IntersectionOperand::Declaration(declaration),
3311 ResidualFunction::new(String::from("ray implicit"), String::from("0")),
3312 IntersectionDomain::new(
3313 String::from("ray-parameter"),
3314 String::from("0 < t < +infinity"),
3315 String::from("ray"),
3316 ),
3317 SupportRelation::Finite {
3318 evidence: SupportEvidence::ImplicitSupportPair,
3319 },
3320 RankEvidence::Sufficient { rank: 0 },
3321 ))
3322}
3323
3324fn evaluate_ray_point(ray: &Ray3, parameter: &RealAlgebraic) -> Result<Point3, GeometryFailure> {
3325 Ok(Point3 {
3326 x: ray
3327 .origin()
3328 .x
3329 .add(&ray.direction().vector().x.mul(parameter)?)?,
3330 y: ray
3331 .origin()
3332 .y
3333 .add(&ray.direction().vector().y.mul(parameter)?)?,
3334 z: ray
3335 .origin()
3336 .z
3337 .add(&ray.direction().vector().z.mul(parameter)?)?,
3338 })
3339}
3340
3341pub fn construct_intersection(
3342 request: IntersectionConstructionRequest,
3343) -> Result<IntersectionSet, GeometryFailure> {
3344 let body = request.into_body();
3345 let IntersectionConstructionRequestBody {
3346 left_operand,
3347 right_operand,
3348 root_isolation_policy,
3349 } = body;
3350 validate_policy(&root_isolation_policy)?;
3351
3352 let left_descriptor = resolve_operand(&left_operand)?;
3353 let right_descriptor = resolve_operand(&right_operand)?;
3354 let problem = derive_intersection_constraint(
3355 left_operand,
3356 right_operand,
3357 left_descriptor,
3358 right_descriptor,
3359 )?;
3360 let candidates = enumerate_root_candidates(&problem, &root_isolation_policy)?;
3361 let isolation = build_root_isolation(&problem, candidates, &root_isolation_policy)?;
3362 classify_constraint(problem, &isolation)
3363}
3364
3365fn validate_policy(policy: &RootIsolationPolicy) -> Result<(), GeometryFailure> {
3366 if policy.max_iterations == 0 || policy.max_cells == 0 {
3367 return Err(GeometryFailure::RootIsolationPolicyInvalid);
3368 }
3369 if policy.max_iterations > MAX_ROOT_PARTITION_DEPTH {
3370 return Err(GeometryFailure::RootIsolationResourceLimit {
3371 requested_depth: policy.max_iterations,
3372 maximum_depth: MAX_ROOT_PARTITION_DEPTH,
3373 });
3374 }
3375 if policy.max_cells > MAX_ROOT_PARTITION_CELLS {
3376 return Err(GeometryFailure::RootPartitionCellLimit {
3377 requested_cells: policy.max_cells,
3378 maximum_cells: MAX_ROOT_PARTITION_CELLS,
3379 });
3380 }
3381 Ok(())
3382}
3383
3384fn resolve_operand(operand: &IntersectionOperand) -> Result<OperandDescriptor, GeometryFailure> {
3385 match operand {
3386 IntersectionOperand::Declaration(declaration) => {
3387 let evaluation = evaluate_declaration_capability(declaration)?;
3388 descriptor_from_declaration(declaration, evaluation)
3389 }
3390 IntersectionOperand::Evaluated(evaluation) => descriptor_from_evaluation(evaluation),
3391 }
3392}
3393
3394fn derive_intersection_constraint(
3395 left_operand: IntersectionOperand,
3396 right_operand: IntersectionOperand,
3397 left: OperandDescriptor,
3398 right: OperandDescriptor,
3399) -> Result<DerivedRootProblem, GeometryFailure> {
3400 let residual_function =
3401 ResidualFunction::new(left.expression.clone(), right.expression.clone());
3402 let support = derive_support_relation(&left, &right);
3403 let rank = derive_rank_evidence(&left, &right, &support);
3404 let domain = IntersectionDomain::new(
3405 format!("{} x {}", left.chart_id, right.chart_id),
3406 format!("{} ∩ {}", left.domain, right.domain),
3407 format!("{} <> {}", left.support_id, right.support_id),
3408 );
3409 let polynomial = derive_residual_polynomial(&left, &right)?;
3410 let numeric_domain = derive_numeric_domain(&left, &right)?;
3411 let constraint = IntersectionConstraint::new(
3412 left_operand,
3413 right_operand,
3414 residual_function,
3415 domain,
3416 support,
3417 rank,
3418 );
3419 Ok(DerivedRootProblem {
3420 constraint,
3421 polynomial,
3422 domain: numeric_domain,
3423 })
3424}
3425
3426fn enumerate_root_candidates(
3427 problem: &DerivedRootProblem,
3428 policy: &RootIsolationPolicy,
3429) -> Result<RootCandidateSet, GeometryFailure> {
3430 let Some(polynomial) = problem.polynomial.as_ref() else {
3431 return Ok(RootEnumeration::incomplete(problem.domain.as_ref()));
3432 };
3433 let Some(domain) = problem.domain.as_ref() else {
3434 return Ok(RootEnumeration::incomplete(None));
3435 };
3436
3437 if polynomial.coefficients().iter().all(RealAlgebraic::is_zero)
3438 && matches!(
3439 problem.constraint.support_relation(),
3440 SupportRelation::Coincident { .. }
3441 )
3442 {
3443 return Ok(RootEnumeration {
3444 candidates: Vec::new(),
3445 cells: vec![PartitionCell {
3446 id: 0,
3447 depth: 0,
3448 enclosure: clone_enclosure(domain)?,
3449 disposition: CellDisposition::Coincident,
3450 }],
3451 });
3452 }
3453
3454 let source = problem.constraint.residual_function().combined_expression();
3455 let order_bound = DerivativeOrder::new(policy.max_iterations.max(2));
3456 let derivative = polynomial
3457 .derivative(DerivativeOrder::new(1))
3458 .map_err(calculus_polynomial_failure)?;
3459 let mut pending = vec![PendingPartitionCell {
3460 id: 0,
3461 depth: 0,
3462 enclosure: clone_enclosure(domain)?,
3463 suppressed_exact_endpoints: Vec::new(),
3464 }];
3465 let mut next_cell_id = 1;
3466 let mut cells = Vec::new();
3467 let mut candidates = Vec::new();
3468
3469 while let Some(PendingPartitionCell {
3470 id: cell_id,
3471 depth,
3472 enclosure,
3473 suppressed_exact_endpoints,
3474 }) = pending.pop()
3475 {
3476 match assess_partition_cell(
3477 polynomial,
3478 &derivative,
3479 &enclosure,
3480 cell_id,
3481 &order_bound,
3482 source,
3483 &suppressed_exact_endpoints,
3484 )? {
3485 CellAssessment::ExactTouch { candidate, pivot } => {
3486 cells.push(PartitionCell {
3487 id: cell_id,
3488 depth,
3489 enclosure: clone_enclosure(&enclosure)?,
3490 disposition: CellDisposition::Candidate,
3491 });
3492 let pivot_exhausts_polynomial =
3493 exact_touch_exhausts_polynomial(&candidate, polynomial);
3494 let pivot_is_unresolved =
3495 matches!(&candidate.bracket, RootCandidateBracket::Unresolved { .. });
3496 candidates.push(*candidate);
3497 if pivot_exhausts_polynomial || pivot_is_unresolved {
3498 continue;
3499 }
3500
3501 let has_lower_child = pivot != *enclosure.lower();
3502 let has_upper_child = pivot != *enclosure.upper();
3503 ensure_partition_cell_capacity(
3504 cells.len(),
3505 pending.len(),
3506 usize::from(has_lower_child) + usize::from(has_upper_child),
3507 policy.max_cells,
3508 )?;
3509 if has_lower_child {
3510 let lower = Enclosure::new(
3511 enclosure.lower().try_clone().map_err(map_bigint_failure)?,
3512 pivot.try_clone().map_err(map_bigint_failure)?,
3513 )
3514 .map_err(|error| GeometryFailure::CalculusFailure {
3515 error: CalculusFailure::Interval(error),
3516 })?;
3517 let lower_id = take_partition_cell_id(&mut next_cell_id)?;
3518 pending.push(PendingPartitionCell {
3519 id: lower_id,
3520 depth: depth + 1,
3521 suppressed_exact_endpoints: suppressed_endpoints_for_child(
3522 &suppressed_exact_endpoints,
3523 lower.lower(),
3524 lower.upper(),
3525 &pivot,
3526 )?,
3527 enclosure: lower,
3528 });
3529 }
3530 if has_upper_child {
3531 let upper = Enclosure::new(
3532 pivot.try_clone().map_err(map_bigint_failure)?,
3533 enclosure.upper().try_clone().map_err(map_bigint_failure)?,
3534 )
3535 .map_err(|error| GeometryFailure::CalculusFailure {
3536 error: CalculusFailure::Interval(error),
3537 })?;
3538 let upper_id = take_partition_cell_id(&mut next_cell_id)?;
3539 pending.push(PendingPartitionCell {
3540 id: upper_id,
3541 depth: depth + 1,
3542 suppressed_exact_endpoints: suppressed_endpoints_for_child(
3543 &suppressed_exact_endpoints,
3544 upper.lower(),
3545 upper.upper(),
3546 &pivot,
3547 )?,
3548 enclosure: upper,
3549 });
3550 }
3551 }
3552 CellAssessment::Candidate(cell_candidates) => {
3553 cells.push(PartitionCell {
3554 id: cell_id,
3555 depth,
3556 enclosure,
3557 disposition: CellDisposition::Candidate,
3558 });
3559 candidates.extend(cell_candidates);
3560 }
3561 CellAssessment::RootFree => cells.push(PartitionCell {
3562 id: cell_id,
3563 depth,
3564 enclosure,
3565 disposition: CellDisposition::RootFree,
3566 }),
3567 CellAssessment::Unresolved(reason) if depth < policy.max_iterations => {
3568 let midpoint =
3569 enclosure
3570 .midpoint()
3571 .map_err(|error| GeometryFailure::CalculusFailure {
3572 error: CalculusFailure::Interval(error),
3573 })?;
3574 if midpoint == *enclosure.lower() || midpoint == *enclosure.upper() {
3575 cells.push(PartitionCell {
3576 id: cell_id,
3577 depth,
3578 enclosure,
3579 disposition: CellDisposition::Unresolved { reason },
3580 });
3581 continue;
3582 }
3583 ensure_partition_cell_capacity(cells.len(), pending.len(), 2, policy.max_cells)?;
3584 let lower_id = take_partition_cell_id(&mut next_cell_id)?;
3585 let upper_id = take_partition_cell_id(&mut next_cell_id)?;
3586 let lower = Enclosure::new(
3587 enclosure.lower().try_clone().map_err(map_bigint_failure)?,
3588 midpoint.try_clone().map_err(map_bigint_failure)?,
3589 )
3590 .map_err(|error| GeometryFailure::CalculusFailure {
3591 error: CalculusFailure::Interval(error),
3592 })?;
3593 let upper = Enclosure::new(
3594 midpoint,
3595 enclosure.upper().try_clone().map_err(map_bigint_failure)?,
3596 )
3597 .map_err(|error| GeometryFailure::CalculusFailure {
3598 error: CalculusFailure::Interval(error),
3599 })?;
3600 let lower_suppressed = inherited_suppressed_endpoints(
3601 &suppressed_exact_endpoints,
3602 lower.lower(),
3603 lower.upper(),
3604 )?;
3605 let upper_suppressed = inherited_suppressed_endpoints(
3606 &suppressed_exact_endpoints,
3607 upper.lower(),
3608 upper.upper(),
3609 )?;
3610 pending.push(PendingPartitionCell {
3611 id: upper_id,
3612 depth: depth + 1,
3613 enclosure: upper,
3614 suppressed_exact_endpoints: upper_suppressed,
3615 });
3616 pending.push(PendingPartitionCell {
3617 id: lower_id,
3618 depth: depth + 1,
3619 enclosure: lower,
3620 suppressed_exact_endpoints: lower_suppressed,
3621 });
3622 }
3623 CellAssessment::Unresolved(reason) => cells.push(PartitionCell {
3624 id: cell_id,
3625 depth,
3626 enclosure,
3627 disposition: CellDisposition::Unresolved { reason },
3628 }),
3629 }
3630 }
3631
3632 Ok(RootEnumeration { candidates, cells })
3633}
3634
3635fn exact_touch_exhausts_polynomial(candidate: &RootCandidate, polynomial: &Polynomial) -> bool {
3636 let order = match candidate.evidence {
3637 RootEvidence::EvenMultiplicityTouch { order, .. }
3638 | RootEvidence::HigherOrder { order, .. } => order,
3639 RootEvidence::SignChange { .. }
3640 | RootEvidence::SimpleRoot { .. }
3641 | RootEvidence::Undetermined { .. } => return false,
3642 };
3643 order >= polynomial.coefficients().len().saturating_sub(1)
3644}
3645
3646fn inherited_suppressed_endpoints(
3647 inherited: &[Dyadic],
3648 lower: &Dyadic,
3649 upper: &Dyadic,
3650) -> Result<Vec<Dyadic>, GeometryFailure> {
3651 inherited
3652 .iter()
3653 .filter(|point| *point == lower || *point == upper)
3654 .map(|point| point.try_clone().map_err(map_bigint_failure))
3655 .collect()
3656}
3657
3658fn suppressed_endpoints_for_child(
3659 inherited: &[Dyadic],
3660 lower: &Dyadic,
3661 upper: &Dyadic,
3662 pivot: &Dyadic,
3663) -> Result<Vec<Dyadic>, GeometryFailure> {
3664 let mut endpoints = inherited_suppressed_endpoints(inherited, lower, upper)?;
3665 if !endpoints.iter().any(|point| point == pivot) {
3666 endpoints.push(pivot.try_clone().map_err(map_bigint_failure)?);
3667 }
3668 Ok(endpoints)
3669}
3670
3671fn assess_partition_cell(
3672 polynomial: &Polynomial,
3673 derivative: &Polynomial,
3674 enclosure: &Enclosure,
3675 cell_id: PartitionCellId,
3676 order_bound: &DerivativeOrder,
3677 source: &str,
3678 suppressed_exact_endpoints: &[Dyadic],
3679) -> Result<CellAssessment, GeometryFailure> {
3680 let lower_sign = polynomial
3681 .evaluate(&dyadic_to_real(enclosure.lower())?)
3682 .map_err(calculus_polynomial_failure)?
3683 .sign()
3684 .map_err(GeometryFailure::AlgebraFailure)?;
3685 let upper_sign = polynomial
3686 .evaluate(&dyadic_to_real(enclosure.upper())?)
3687 .map_err(calculus_polynomial_failure)?
3688 .sign()
3689 .map_err(GeometryFailure::AlgebraFailure)?;
3690 let midpoint = enclosure
3691 .midpoint()
3692 .map_err(|error| GeometryFailure::CalculusFailure {
3693 error: CalculusFailure::Interval(error),
3694 })?;
3695 let midpoint_sign = polynomial
3696 .evaluate(&dyadic_to_real(&midpoint)?)
3697 .map_err(calculus_polynomial_failure)?
3698 .sign()
3699 .map_err(GeometryFailure::AlgebraFailure)?;
3700
3701 let mut exact_points = Vec::new();
3702 if lower_sign == Sign::Zero
3703 && !suppressed_exact_endpoints
3704 .iter()
3705 .any(|point| point == enclosure.lower())
3706 {
3707 exact_points.push(enclosure.lower().try_clone().map_err(map_bigint_failure)?);
3708 }
3709 if upper_sign == Sign::Zero
3710 && enclosure.upper() != enclosure.lower()
3711 && !suppressed_exact_endpoints
3712 .iter()
3713 .any(|point| point == enclosure.upper())
3714 {
3715 exact_points.push(enclosure.upper().try_clone().map_err(map_bigint_failure)?);
3716 }
3717 if midpoint_sign == Sign::Zero && !exact_points.iter().any(|point| point == &midpoint) {
3718 exact_points.push(midpoint.try_clone().map_err(map_bigint_failure)?);
3719 }
3720
3721 if exact_points.len() > 1 {
3722 return Ok(CellAssessment::Unresolved(
3723 PartitionUnresolvedReason::MultipleExactDyadicRoots,
3724 ));
3725 }
3726 if let Some(pivot) = exact_points.into_iter().next() {
3727 let candidate = exact_touch_candidate(
3728 polynomial,
3729 enclosure,
3730 pivot.try_clone().map_err(map_bigint_failure)?,
3731 cell_id,
3732 order_bound,
3733 source,
3734 )?;
3735 return Ok(CellAssessment::ExactTouch {
3736 candidate: Box::new(candidate),
3737 pivot,
3738 });
3739 }
3740
3741 if opposite_nonzero(lower_sign, upper_sign) {
3742 let derivative_enclosure = derivative
3743 .evaluate_enclosure(enclosure, ROOT_INTERVAL_PRECISION_BITS)
3744 .map_err(calculus_polynomial_failure)?;
3745 if derivative_enclosure.contains_zero() {
3746 return Ok(CellAssessment::Unresolved(
3747 PartitionUnresolvedReason::SignChangeUniqueness,
3748 ));
3749 }
3750 let calculus_bracket = CalculusRootBracket::sign_change(
3751 polynomial
3752 .try_clone()
3753 .map_err(calculus_polynomial_failure)?,
3754 clone_enclosure(enclosure)?,
3755 )
3756 .map_err(|error| GeometryFailure::CalculusFailure {
3757 error: CalculusFailure::Root(error),
3758 })?;
3759 return Ok(CellAssessment::Candidate(vec![RootCandidate {
3760 bracket: RootCandidateBracket::Certified(calculus_bracket),
3761 evidence: RootEvidence::SignChange {
3762 lower_sign: root_sign(lower_sign),
3763 upper_sign: root_sign(upper_sign),
3764 derivative_enclosure,
3765 source: ResidualSourceId::new(source),
3766 },
3767 source_cell: cell_id,
3768 }]));
3769 }
3770
3771 let value_enclosure = polynomial
3772 .evaluate_enclosure(enclosure, ROOT_INTERVAL_PRECISION_BITS)
3773 .map_err(calculus_polynomial_failure)?;
3774 if !value_enclosure.contains_zero() {
3775 return Ok(CellAssessment::RootFree);
3776 }
3777 Ok(CellAssessment::Unresolved(
3778 PartitionUnresolvedReason::UncertifiedRoot,
3779 ))
3780}
3781
3782fn exact_touch_candidate(
3783 polynomial: &Polynomial,
3784 enclosure: &Enclosure,
3785 point: Dyadic,
3786 cell_id: PartitionCellId,
3787 order_bound: &DerivativeOrder,
3788 source: &str,
3789) -> Result<RootCandidate, GeometryFailure> {
3790 let multiplicity = match neco_calculus::classify_multiplicity(polynomial, &point, *order_bound)
3791 {
3792 Ok(multiplicity) => multiplicity,
3793 Err(error) if root_failure_is_undetermined(&error) => {
3794 return Ok(RootCandidate {
3795 bracket: RootCandidateBracket::Unresolved {
3796 enclosure: clone_enclosure(enclosure)?,
3797 },
3798 evidence: RootEvidence::Undetermined {
3799 reason: RootUndeterminedReason::ExactMultiplicityUnavailable,
3800 source: ResidualSourceId::new(source),
3801 },
3802 source_cell: cell_id,
3803 });
3804 }
3805 Err(error) => {
3806 return Err(GeometryFailure::CalculusFailure {
3807 error: CalculusFailure::Root(error),
3808 });
3809 }
3810 };
3811 let point = dyadic_to_real(&point)?;
3812 let order = match multiplicity {
3813 RootMultiplicity::Multiple(value) => value.get(),
3814 RootMultiplicity::Simple => 1,
3815 };
3816 let evidence = if order == 1 {
3817 RootEvidence::SimpleRoot {
3818 point: point.try_clone()?,
3819 source: ResidualSourceId::new(source),
3820 }
3821 } else if order > 2 {
3822 RootEvidence::HigherOrder {
3823 order,
3824 point: point.try_clone()?,
3825 source: ResidualSourceId::new(source),
3826 }
3827 } else {
3828 RootEvidence::EvenMultiplicityTouch {
3829 order,
3830 point: point.try_clone()?,
3831 source: ResidualSourceId::new(source),
3832 }
3833 };
3834 Ok(RootCandidate {
3835 bracket: RootCandidateBracket::Exact { parameter: point },
3836 evidence,
3837 source_cell: cell_id,
3838 })
3839}
3840
3841fn root_failure_is_undetermined(error: &neco_calculus::RootFailure) -> bool {
3842 matches!(
3843 error,
3844 neco_calculus::RootFailure::NoRootAtPoint
3845 | neco_calculus::RootFailure::NoEvenMultiplicityTouch
3846 | neco_calculus::RootFailure::MultiplicityUndetermined
3847 | neco_calculus::RootFailure::PointOutsideEnclosure
3848 )
3849}
3850
3851fn build_root_isolation(
3852 problem: &DerivedRootProblem,
3853 candidates: RootCandidateSet,
3854 policy: &RootIsolationPolicy,
3855) -> Result<RootIsolation, GeometryFailure> {
3856 let RootEnumeration { candidates, cells } = candidates;
3857 let mut candidate_brackets = Vec::new();
3858 let mut unresolved_candidate = false;
3859 for candidate in candidates {
3860 let source_cell = candidate.source_cell;
3861 let bracket = match candidate.bracket {
3862 RootCandidateBracket::Exact { parameter } => {
3863 RootBracket::from_exact(parameter, candidate.evidence, policy)?
3864 }
3865 RootCandidateBracket::Certified(calculus_bracket) => {
3866 let calculus_isolation = refine_root(&calculus_bracket, policy)?;
3867 RootBracket::from_calculus(
3868 &calculus_bracket,
3869 &calculus_isolation,
3870 candidate.evidence,
3871 )?
3872 }
3873 RootCandidateBracket::Unresolved { enclosure } => {
3874 unresolved_candidate = true;
3875 RootBracket::from_unresolved(&enclosure, candidate.evidence, policy)?
3876 }
3877 };
3878 candidate_brackets.push((source_cell, bracket));
3879 }
3880 let candidate_cell_ids: Vec<_> = cells
3881 .iter()
3882 .filter(|cell| matches!(cell.disposition, CellDisposition::Candidate))
3883 .map(|cell| cell.id)
3884 .collect();
3885 let candidate_source_cells: Vec<_> = candidate_brackets
3886 .iter()
3887 .map(|(source_cell, _)| *source_cell)
3888 .collect();
3889 let candidate_brackets_match = candidate_cell_ids.len() == candidate_brackets.len()
3890 && candidate_cell_ids.iter().all(|cell_id| {
3891 candidate_source_cells
3892 .iter()
3893 .filter(|source_cell| **source_cell == *cell_id)
3894 .count()
3895 == 1
3896 })
3897 && candidate_source_cells.iter().all(|source_cell| {
3898 candidate_cell_ids
3899 .iter()
3900 .any(|cell_id| cell_id == source_cell)
3901 });
3902 let duplicate_candidate = candidate_source_cells
3903 .iter()
3904 .enumerate()
3905 .any(|(index, cell_id)| {
3906 candidate_source_cells[..index]
3907 .iter()
3908 .any(|previous| previous == cell_id)
3909 });
3910 let mut ordering_failed = false;
3911 candidate_brackets.sort_by(
3912 |(_, left), (_, right)| match left.lower().compare(right.lower()) {
3913 Ok(ordering) => ordering,
3914 Err(_) => {
3915 ordering_failed = true;
3916 Ordering::Equal
3917 }
3918 },
3919 );
3920
3921 let mut overlap = false;
3922 let mut outside_domain = false;
3923 let brackets: Vec<_> = candidate_brackets
3924 .into_iter()
3925 .map(|(_, bracket)| bracket)
3926 .collect();
3927 if let Some(domain) = problem.domain.as_ref() {
3928 for bracket in &brackets {
3929 let lower_inside = bracket.lower().compare(&dyadic_to_real(domain.lower())?);
3930 let upper_inside = bracket.upper().compare(&dyadic_to_real(domain.upper())?);
3931 match (lower_inside, upper_inside) {
3932 (Ok(lower), Ok(upper)) if lower != Ordering::Less && upper != Ordering::Greater => {
3933 }
3934 (Ok(_), Ok(_)) => outside_domain = true,
3935 _ => ordering_failed = true,
3936 }
3937 }
3938 } else {
3939 outside_domain = true;
3940 }
3941 for pair in brackets.windows(2) {
3942 match pair[0].lower().compare(pair[1].lower()) {
3943 Ok(Ordering::Equal) => overlap = true,
3944 Ok(_) => {}
3945 Err(_) => ordering_failed = true,
3946 }
3947 match pair[0].upper().compare(pair[1].lower()) {
3948 Ok(Ordering::Greater) => overlap = true,
3949 Ok(_) => {}
3950 Err(_) => ordering_failed = true,
3951 }
3952 }
3953
3954 let partition_complete = !cells.is_empty()
3955 && cells.iter().all(|cell| {
3956 matches!(
3957 cell.disposition,
3958 CellDisposition::Candidate
3959 | CellDisposition::Coincident
3960 | CellDisposition::RootFree
3961 )
3962 });
3963 let structural_complete = partition_complete
3964 && candidate_brackets_match
3965 && !unresolved_candidate
3966 && !duplicate_candidate
3967 && !overlap
3968 && !outside_domain
3969 && !ordering_failed;
3970 let source_domain = clone_domain(problem.constraint.domain());
3971 let source_function = clone_residual_function(problem.constraint.residual_function());
3972 let completeness_status = if structural_complete {
3973 WitnessStatus::Proved
3974 } else {
3975 WitnessStatus::Undetermined {
3976 reason: WitnessUndeterminedReason::PartitionOrCandidatesIncomplete,
3977 }
3978 };
3979 let non_overlap_status =
3980 if !duplicate_candidate && !overlap && !outside_domain && !ordering_failed {
3981 WitnessStatus::Proved
3982 } else {
3983 WitnessStatus::Undetermined {
3984 reason: WitnessUndeterminedReason::BracketSetInvalid,
3985 }
3986 };
3987 let completeness = ExistenceWitness::new(
3988 ExistenceEvidence::CompleteCandidatePartition,
3989 WitnessMethod::DeterministicDyadicCandidatePartition,
3990 completeness_status,
3991 );
3992 let non_overlap = UniquenessWitness::new(
3993 UniquenessEvidence::PairwiseNonOverlappingBrackets,
3994 WitnessMethod::CanonicalLowerEndpointOrdering,
3995 non_overlap_status,
3996 );
3997 Ok(RootIsolation::new(
3998 brackets,
3999 completeness,
4000 policy.method,
4001 source_domain,
4002 source_function,
4003 non_overlap,
4004 ))
4005}
4006
4007fn classify_constraint(
4008 problem: DerivedRootProblem,
4009 isolation: &RootIsolation,
4010) -> Result<IntersectionSet, GeometryFailure> {
4011 let residual = residual_from_constraint(&problem.constraint)?;
4012 let root_witness = IntersectionWitness::from_isolation_and_constraint(
4013 clone_isolation(isolation)?,
4014 problem.constraint,
4015 );
4016 let constraint = root_witness.constraint();
4017 if constraint.rank_is_undetermined() {
4018 return Ok(undetermined_with(
4019 IntersectionUndeterminedReason::EvaluationUndetermined,
4020 residual,
4021 root_witness,
4022 ));
4023 }
4024 let unresolved_isolation = !matches!(
4025 root_witness.root_isolation().completeness().status(),
4026 WitnessStatus::Proved
4027 ) || !matches!(
4028 root_witness.root_isolation().non_overlap().status(),
4029 WitnessStatus::Proved
4030 );
4031 if unresolved_isolation {
4032 return Ok(undetermined_with(
4033 IntersectionUndeterminedReason::RootIsolationIncomplete,
4034 residual,
4035 root_witness,
4036 ));
4037 }
4038 match constraint.support_relation() {
4039 SupportRelation::Coincident { .. } => {
4040 let Ok((left, right)) = declaration_pair(constraint) else {
4041 return Ok(undetermined_with(
4042 IntersectionUndeterminedReason::CoincidenceUndetermined,
4043 residual,
4044 root_witness,
4045 ));
4046 };
4047 IntersectionSet::from_components(
4048 IntersectionKind::Coincident,
4049 clone_residual(&residual)?,
4050 clone_witness(&root_witness)?,
4051 vec![OwnedIntersectionEvidence::Coincident(Box::new(
4052 CoincidentSupport::new(
4053 left,
4054 clone_residual(&residual)?,
4055 right,
4056 clone_witness(&root_witness)?,
4057 ),
4058 ))],
4059 )
4060 }
4061 SupportRelation::Disjoint { .. } => Ok(IntersectionSet::empty(residual, root_witness)),
4062 SupportRelation::Finite { .. } => {
4063 let points = derive_points(constraint, isolation, &residual, &root_witness)?;
4064 match points.len() {
4065 0 => Ok(IntersectionSet::empty(residual, root_witness)),
4066 1 => {
4067 let point = points.into_iter().next().ok_or({
4068 GeometryFailure::CalculusFailure {
4069 error: CalculusFailure::Polynomial(
4070 PolynomialFailure::EmptyCoefficients,
4071 ),
4072 }
4073 })?;
4074 IntersectionSet::from_components(
4075 IntersectionKind::Point,
4076 residual,
4077 root_witness,
4078 vec![OwnedIntersectionEvidence::Point(Box::new(point))],
4079 )
4080 }
4081 _ => IntersectionSet::from_components(
4082 IntersectionKind::FinitePoints,
4083 residual,
4084 root_witness,
4085 points
4086 .into_iter()
4087 .map(|point| OwnedIntersectionEvidence::Point(Box::new(point)))
4088 .collect(),
4089 ),
4090 }
4091 }
4092 SupportRelation::Curve { .. } => {
4093 let identities = derive_branch_identities(constraint, isolation)?;
4094 if identities.is_empty() {
4095 return Ok(undetermined_with(
4096 IntersectionUndeterminedReason::BranchIdentityUndetermined,
4097 residual,
4098 root_witness,
4099 ));
4100 }
4101 if identities.len() != isolation.brackets().len() {
4102 return Ok(undetermined_with(
4103 IntersectionUndeterminedReason::BranchIdentityUndetermined,
4104 residual,
4105 root_witness,
4106 ));
4107 }
4108 let mut branches = Vec::new();
4109 for (ordinal, identity) in identities.into_iter().enumerate() {
4110 let Some(bracket) = isolation.brackets().get(ordinal) else {
4111 return Ok(undetermined_with(
4112 IntersectionUndeterminedReason::BranchIdentityUndetermined,
4113 residual,
4114 root_witness,
4115 ));
4116 };
4117 branches.push(CurveBranch::new(
4118 identity,
4119 bracket.contact_order().clone(),
4120 clone_residual(&residual)?,
4121 clone_witness(&root_witness)?,
4122 ));
4123 }
4124 if branches.len() == 1 {
4125 let branch = branches.into_iter().next().ok_or({
4126 GeometryFailure::CalculusFailure {
4127 error: CalculusFailure::Polynomial(PolynomialFailure::EmptyCoefficients),
4128 }
4129 })?;
4130 let identity = clone_identity(branch.branch_identity())?;
4131 let curve = IntersectionCurve::new(
4132 identity,
4133 branch.contact_order().clone(),
4134 branch.residual().clone_for_operation()?,
4135 constraint_support_id(constraint),
4136 clone_witness(&root_witness)?,
4137 );
4138 IntersectionSet::from_components(
4139 IntersectionKind::Curve,
4140 residual,
4141 root_witness,
4142 vec![OwnedIntersectionEvidence::Curve(Box::new(curve))],
4143 )
4144 } else {
4145 IntersectionSet::from_components(
4146 IntersectionKind::CurveBranches,
4147 residual,
4148 root_witness,
4149 branches
4150 .into_iter()
4151 .map(|branch| OwnedIntersectionEvidence::CurveBranch(Box::new(branch)))
4152 .collect(),
4153 )
4154 }
4155 }
4156 SupportRelation::Undetermined { .. } => Ok(undetermined_with(
4157 IntersectionUndeterminedReason::CoincidenceUndetermined,
4158 residual,
4159 root_witness,
4160 )),
4161 }
4162}
4163
4164fn derive_support_relation(left: &OperandDescriptor, right: &OperandDescriptor) -> SupportRelation {
4165 if left.support_id == right.support_id && left.chart_id == right.chart_id {
4166 return SupportRelation::Coincident {
4167 evidence: SupportEvidence::CanonicalSupportAndChart,
4168 };
4169 }
4170 let left_evaluated = matches!(left.source, OperandSource::Evaluated);
4171 let right_evaluated = matches!(right.source, OperandSource::Evaluated);
4172 if (left_evaluated && left.exact_point.is_some())
4173 || (right_evaluated && right.exact_point.is_some())
4174 {
4175 return SupportRelation::Finite {
4176 evidence: SupportEvidence::EvaluatedSpatialCoordinates,
4177 };
4178 }
4179 if left_evaluated && right_evaluated {
4180 if let (Some(left), Some(right)) = (&left.exact_scalar, &right.exact_scalar) {
4181 return if left == right {
4182 SupportRelation::Coincident {
4183 evidence: SupportEvidence::EqualEvaluatedScalars,
4184 }
4185 } else {
4186 SupportRelation::Disjoint {
4187 evidence: SupportEvidence::DistinctEvaluatedScalars,
4188 }
4189 };
4190 }
4191 if left.exact_scalar.is_some() || right.exact_scalar.is_some() {
4192 return SupportRelation::Undetermined {
4193 reason: SupportUndeterminedReason::IncompleteEvaluatedScalar,
4194 };
4195 }
4196 }
4197 if matches!(left.source, OperandSource::Declaration)
4198 && matches!(right.source, OperandSource::Declaration)
4199 {
4200 return match (left.family, right.family) {
4201 (
4202 crate::types::ShapeFamily::ParametricCurve,
4203 crate::types::ShapeFamily::ParametricCurve,
4204 )
4205 | (
4206 crate::types::ShapeFamily::ParametricSurface,
4207 crate::types::ShapeFamily::ParametricSurface,
4208 ) => SupportRelation::Curve {
4209 evidence: SupportEvidence::CompatibleParametricSupports,
4210 },
4211 (
4212 crate::types::ShapeFamily::ImplicitSurface,
4213 crate::types::ShapeFamily::ImplicitSurface,
4214 ) => SupportRelation::Curve {
4215 evidence: SupportEvidence::ImplicitSupportPair,
4216 },
4217 _ => SupportRelation::Undetermined {
4218 reason: SupportUndeterminedReason::NoCommonParameterization,
4219 },
4220 };
4221 }
4222 SupportRelation::Undetermined {
4223 reason: SupportUndeterminedReason::UnclassifiedEvidence,
4224 }
4225}
4226
4227fn derive_rank_evidence(
4228 left: &OperandDescriptor,
4229 right: &OperandDescriptor,
4230 support: &SupportRelation,
4231) -> RankEvidence {
4232 if matches!(support, SupportRelation::Undetermined { .. }) {
4233 return RankEvidence::Undetermined {
4234 reason: RankUndeterminedReason::SupportRelationUnresolved,
4235 };
4236 }
4237 if left.family == right.family {
4238 RankEvidence::Sufficient { rank: 1 }
4239 } else if (matches!(left.source, OperandSource::Evaluated) && left.exact_point.is_some())
4240 || (matches!(right.source, OperandSource::Evaluated) && right.exact_point.is_some())
4241 {
4242 RankEvidence::Sufficient { rank: 0 }
4243 } else {
4244 RankEvidence::Degenerate {
4245 reason: RankDegeneracyReason::InsufficientCommonRank,
4246 }
4247 }
4248}
4249
4250fn derive_residual_polynomial(
4251 left: &OperandDescriptor,
4252 right: &OperandDescriptor,
4253) -> Result<Option<Polynomial>, GeometryFailure> {
4254 match (left.source, right.source) {
4255 (OperandSource::Evaluated, OperandSource::Evaluated) => {
4256 if let (Some(left), Some(right)) = (&left.exact_scalar, &right.exact_scalar) {
4257 return Ok(Some(
4258 Polynomial::constant(left.sub(right).map_err(GeometryFailure::AlgebraFailure)?)
4259 .map_err(calculus_polynomial_failure)?,
4260 ));
4261 }
4262 if let (Some(left), Some(right)) = (&left.exact_point, &right.exact_point) {
4263 return Ok(Some(
4264 Polynomial::constant(
4265 left.x
4266 .sub(&right.x)
4267 .map_err(GeometryFailure::AlgebraFailure)?,
4268 )
4269 .map_err(calculus_polynomial_failure)?,
4270 ));
4271 }
4272 Ok(None)
4273 }
4274 (OperandSource::Evaluated, OperandSource::Declaration) => {
4275 let Some(polynomial) = right.polynomial.as_ref() else {
4276 return Ok(None);
4277 };
4278 if let Some(point) = left.exact_point.as_ref() {
4279 return negate_polynomial_plus_constant(polynomial, &point.x);
4280 }
4281 if let Some(value) = left.exact_scalar.as_ref() {
4282 return negate_polynomial_plus_constant(polynomial, value);
4283 }
4284 Ok(None)
4285 }
4286 (OperandSource::Declaration, OperandSource::Evaluated) => {
4287 let Some(polynomial) = left.polynomial.as_ref() else {
4288 return Ok(None);
4289 };
4290 if let Some(point) = right.exact_point.as_ref() {
4291 return subtract_constant_from_polynomial(polynomial, &point.x);
4292 }
4293 if let Some(value) = right.exact_scalar.as_ref() {
4294 return subtract_constant_from_polynomial(polynomial, value);
4295 }
4296 Ok(None)
4297 }
4298 (OperandSource::Declaration, OperandSource::Declaration) => {
4299 match (&left.polynomial, &right.polynomial) {
4300 (Some(left), Some(right)) => {
4301 let max = left.degree().max(right.degree());
4302 let mut coefficients = Vec::with_capacity(max + 1);
4303 for index in 0..=max {
4304 let left_value = left
4305 .coefficients()
4306 .get(index)
4307 .map(RealAlgebraic::try_clone)
4308 .transpose()?;
4309 let right_value = right
4310 .coefficients()
4311 .get(index)
4312 .map(RealAlgebraic::try_clone)
4313 .transpose()?;
4314 let zero = RealAlgebraic::from_integer(BigInt::zero())?;
4315 let left_value = left_value.unwrap_or(zero.try_clone()?);
4316 let right_value = right_value.unwrap_or(zero);
4317 coefficients.push(
4318 left_value
4319 .sub(&right_value)
4320 .map_err(GeometryFailure::AlgebraFailure)?,
4321 );
4322 }
4323 Ok(Some(
4324 Polynomial::from_coefficients(coefficients)
4325 .map_err(calculus_polynomial_failure)?,
4326 ))
4327 }
4328 _ => Ok(None),
4329 }
4330 }
4331 }
4332}
4333
4334fn subtract_constant_from_polynomial(
4335 polynomial: &Polynomial,
4336 value: &RealAlgebraic,
4337) -> Result<Option<Polynomial>, GeometryFailure> {
4338 let mut coefficients = Vec::with_capacity(polynomial.coefficients().len());
4339 for (index, coefficient) in polynomial.coefficients().iter().enumerate() {
4340 let adjusted = if index == 0 {
4341 coefficient
4342 .sub(value)
4343 .map_err(GeometryFailure::AlgebraFailure)?
4344 } else {
4345 coefficient.try_clone()?
4346 };
4347 coefficients.push(adjusted);
4348 }
4349 Ok(Some(
4350 Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
4351 ))
4352}
4353
4354fn negate_polynomial_plus_constant(
4355 polynomial: &Polynomial,
4356 value: &RealAlgebraic,
4357) -> Result<Option<Polynomial>, GeometryFailure> {
4358 let mut coefficients = Vec::with_capacity(polynomial.coefficients().len());
4359 for (index, coefficient) in polynomial.coefficients().iter().enumerate() {
4360 let negated = RealAlgebraic::from_integer(BigInt::zero())?
4361 .sub(coefficient)
4362 .map_err(GeometryFailure::AlgebraFailure)?;
4363 let adjusted = if index == 0 {
4364 value
4365 .sub(coefficient)
4366 .map_err(GeometryFailure::AlgebraFailure)?
4367 } else {
4368 negated
4369 };
4370 coefficients.push(adjusted);
4371 }
4372 Ok(Some(
4373 Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
4374 ))
4375}
4376
4377fn derive_numeric_domain(
4378 left: &OperandDescriptor,
4379 right: &OperandDescriptor,
4380) -> Result<Option<Enclosure>, GeometryFailure> {
4381 match (&left.parameter_bounds, &right.parameter_bounds) {
4382 (Some((left_lower, left_upper)), Some((right_lower, right_upper))) => {
4383 let lower = if left_lower.compare(right_lower)? == Ordering::Greater {
4384 left_lower
4385 } else {
4386 right_lower
4387 };
4388 let upper = if left_upper.compare(right_upper)? == Ordering::Less {
4389 left_upper
4390 } else {
4391 right_upper
4392 };
4393 if lower.compare(upper)? == Ordering::Greater {
4394 return Err(GeometryFailure::ParameterOutsideDomain);
4395 }
4396 let lower = real_to_dyadic(lower)?;
4397 let upper = real_to_dyadic(upper)?;
4398 Ok(Some(Enclosure::new(lower, upper).map_err(|error| {
4399 GeometryFailure::CalculusFailure {
4400 error: CalculusFailure::Interval(error),
4401 }
4402 })?))
4403 }
4404 (Some((lower, upper)), None) | (None, Some((lower, upper))) => {
4405 let lower = real_to_dyadic(lower)?;
4406 let upper = real_to_dyadic(upper)?;
4407 Ok(Some(Enclosure::new(lower, upper).map_err(|error| {
4408 GeometryFailure::CalculusFailure {
4409 error: CalculusFailure::Interval(error),
4410 }
4411 })?))
4412 }
4413 (None, None) if left.exact_scalar.is_some() && right.exact_scalar.is_some() => Ok(Some(
4414 Enclosure::new(
4415 Dyadic::new(BigInt::zero(), 0),
4416 Dyadic::new(BigInt::zero(), 0),
4417 )
4418 .map_err(|error| GeometryFailure::CalculusFailure {
4419 error: CalculusFailure::Interval(error),
4420 })?,
4421 )),
4422 (None, None) => Ok(None),
4423 }
4424}
4425
4426fn descriptor_from_declaration(
4427 declaration: &ShapeDeclaration,
4428 evaluation: ShapeEvaluation,
4429) -> Result<OperandDescriptor, GeometryFailure> {
4430 let family = declaration.family();
4431 let (support_id, chart_id, domain, parameter_bounds, expression, polynomial) = match declaration
4432 {
4433 ShapeDeclaration::ParametricCurve(value) => {
4434 let chart_id = match value.chart() {
4435 crate::types::CurveChart::Chart2(_) => String::from("chart-2"),
4436 crate::types::CurveChart::Chart3(_) => String::from("chart-3"),
4437 };
4438 let expression = curve_expression(value);
4439 let polynomial = curve_polynomial(value)?;
4440 (
4441 format!("curve:{}", expression),
4442 chart_id,
4443 String::from(value.chart_domain()),
4444 interval_bounds(value.domain()),
4445 expression,
4446 polynomial,
4447 )
4448 }
4449 ShapeDeclaration::ParametricSurface(value) => {
4450 let expression = surface_expression(value);
4451 (
4452 format!("surface:{}", expression),
4453 String::from("surface-chart"),
4454 String::from(value.chart().identity().domain_id().as_str()),
4455 None,
4456 expression,
4457 None,
4458 )
4459 }
4460 ShapeDeclaration::ImplicitSurface(value) => {
4461 let expression = implicit_expression(value);
4462 (
4463 format!("implicit:{}", expression),
4464 String::from("implicit-chart"),
4465 String::from("support-domain"),
4466 None,
4467 expression,
4468 implicit_polynomial(value)?,
4469 )
4470 }
4471 };
4472 let (exact_scalar, exact_point, certified_scalar) = evaluation_evidence(&evaluation)?;
4473 Ok(OperandDescriptor {
4474 source: OperandSource::Declaration,
4475 family,
4476 support_id,
4477 chart_id,
4478 domain,
4479 parameter_bounds,
4480 expression,
4481 polynomial,
4482 exact_scalar,
4483 exact_point,
4484 certified_scalar,
4485 })
4486}
4487
4488fn descriptor_from_evaluation(
4489 evaluation: &ShapeEvaluation,
4490) -> Result<OperandDescriptor, GeometryFailure> {
4491 let family = match evaluation {
4492 ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricCurve { .. })
4493 | ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ParametricCurve {
4494 ..
4495 }) => crate::types::ShapeFamily::ParametricCurve,
4496 ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricSurface { .. })
4497 | ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ParametricSurface {
4498 ..
4499 }) => crate::types::ShapeFamily::ParametricSurface,
4500 ShapeEvaluation::Exact(ExactShapeEvaluation::ImplicitSurface { .. })
4501 | ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ImplicitSurface {
4502 ..
4503 }) => crate::types::ShapeFamily::ImplicitSurface,
4504 ShapeEvaluation::Undetermined { family } => *family,
4505 };
4506 let (exact_scalar, exact_point, certified_scalar) = evaluation_evidence(evaluation)?;
4507 let expression = format!("evaluated:{family:?}:{evaluation:?}");
4508 Ok(OperandDescriptor {
4509 source: OperandSource::Evaluated,
4510 family,
4511 support_id: expression.clone(),
4512 chart_id: format!("evaluated-{family:?}"),
4513 domain: String::from("evaluated-domain"),
4514 parameter_bounds: None,
4515 expression,
4516 polynomial: None,
4517 exact_scalar,
4518 exact_point,
4519 certified_scalar,
4520 })
4521}
4522
4523type EvaluationEvidence = (
4524 Option<RealAlgebraic>,
4525 Option<Point3>,
4526 Option<(
4527 Enclosure,
4528 OwnerId,
4529 ExactExpressionRequirement,
4530 NecoImplementationSource,
4531 )>,
4532);
4533
4534fn evaluation_evidence(
4535 evaluation: &ShapeEvaluation,
4536) -> Result<EvaluationEvidence, GeometryFailure> {
4537 match evaluation {
4538 ShapeEvaluation::Exact(ExactShapeEvaluation::ImplicitSurface { scalar }) => {
4539 Ok((Some(scalar.try_clone()?), None, None))
4540 }
4541 ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricCurve { coordinate }) => {
4542 let point = match coordinate {
4543 ShapeCoordinate::Spatial(point) => clone_point(point)?,
4544 ShapeCoordinate::Planar(point) => Point3 {
4545 x: point.x.try_clone()?,
4546 y: point.y.try_clone()?,
4547 z: RealAlgebraic::from_integer(BigInt::zero())?,
4548 },
4549 };
4550 Ok((None, Some(point), None))
4551 }
4552 ShapeEvaluation::Exact(ExactShapeEvaluation::ParametricSurface { coordinate }) => {
4553 Ok((None, Some(clone_point(coordinate)?), None))
4554 }
4555 ShapeEvaluation::CertifiedEnclosure(CertifiedShapeEvaluation::ImplicitSurface {
4556 scalar,
4557 owner,
4558 requirement,
4559 source,
4560 }) => Ok((
4561 None,
4562 None,
4563 Some((
4564 clone_enclosure(scalar)?,
4565 *owner,
4566 clone_requirement(requirement)?,
4567 *source,
4568 )),
4569 )),
4570 ShapeEvaluation::CertifiedEnclosure(_) | ShapeEvaluation::Undetermined { .. } => {
4571 Ok((None, None, None))
4572 }
4573 }
4574}
4575
4576fn derive_points(
4577 constraint: &IntersectionConstraint,
4578 isolation: &RootIsolation,
4579 residual: &IntersectionResidual,
4580 witness: &IntersectionWitness,
4581) -> Result<IntersectionPointSet, GeometryFailure> {
4582 let Some(point) = operand_point(constraint.left_operand())
4583 .or_else(|| operand_point(constraint.right_operand()))
4584 else {
4585 return Ok(Vec::new());
4586 };
4587 isolation
4588 .brackets()
4589 .iter()
4590 .enumerate()
4591 .map(|(ordinal, bracket)| {
4592 Ok(IntersectionPoint::new(
4593 Some(derive_branch_identity(constraint, ordinal)),
4594 bracket.contact_order().clone(),
4595 clone_point(&point)?,
4596 clone_residual(residual)?,
4597 clone_witness(witness)?,
4598 ))
4599 })
4600 .collect()
4601}
4602
4603fn derive_branch_identities(
4604 constraint: &IntersectionConstraint,
4605 isolation: &RootIsolation,
4606) -> Result<BranchIdentitySet, GeometryFailure> {
4607 if constraint.support_relation().is_undetermined() {
4608 return Ok(Vec::new());
4609 }
4610 let count = isolation.brackets().len();
4611 Ok((0..count)
4612 .map(|ordinal| derive_branch_identity(constraint, ordinal))
4613 .collect())
4614}
4615
4616fn derive_branch_identity(constraint: &IntersectionConstraint, ordinal: usize) -> BranchIdentity {
4617 let support_id = constraint_support_id(constraint);
4618 let chart_id = constraint_chart_id(constraint);
4619 BranchIdentity::new(
4620 format!("{support_id}|{chart_id}|candidate-{ordinal}"),
4621 chart_id,
4622 support_id,
4623 )
4624}
4625
4626fn declaration_pair(
4627 constraint: &IntersectionConstraint,
4628) -> Result<(ShapeDeclaration, ShapeDeclaration), GeometryFailure> {
4629 match (constraint.left_operand(), constraint.right_operand()) {
4630 (IntersectionOperand::Declaration(left), IntersectionOperand::Declaration(right)) => {
4631 Ok((clone_declaration(left)?, clone_declaration(right)?))
4632 }
4633 _ => Err(GeometryFailure::EvaluationIndeterminacy {
4634 family: crate::types::ShapeFamily::ImplicitSurface,
4635 reason: crate::types::ShapeEvaluationIndeterminacy::DomainValidity,
4636 }),
4637 }
4638}
4639
4640fn operand_point(operand: &IntersectionOperand) -> Option<Point3> {
4641 match operand {
4642 IntersectionOperand::Evaluated(ShapeEvaluation::Exact(
4643 ExactShapeEvaluation::ParametricSurface { coordinate },
4644 )) => Some(clone_point(coordinate).ok()?),
4645 IntersectionOperand::Evaluated(ShapeEvaluation::Exact(
4646 ExactShapeEvaluation::ParametricCurve {
4647 coordinate: ShapeCoordinate::Spatial(coordinate),
4648 },
4649 )) => Some(clone_point(coordinate).ok()?),
4650 _ => None,
4651 }
4652}
4653
4654fn residual_from_constraint(
4655 constraint: &IntersectionConstraint,
4656) -> Result<IntersectionResidual, GeometryFailure> {
4657 let left = operand_residual_value(constraint.left_operand())?;
4658 let right = operand_residual_value(constraint.right_operand())?;
4659 let combined = match (&left, &right) {
4660 (ResidualValue::Exact { value: left }, ResidualValue::Exact { value: right }) => {
4661 ResidualValue::Exact {
4662 value: left.sub(right).map_err(GeometryFailure::AlgebraFailure)?,
4663 }
4664 }
4665 (
4666 ResidualValue::Certified {
4667 owner: left_owner,
4668 requirement: left_requirement,
4669 source: left_source,
4670 value: left,
4671 },
4672 ResidualValue::Certified { value: right, .. },
4673 ) => ResidualValue::Certified {
4674 owner: *left_owner,
4675 requirement: clone_requirement(left_requirement)?,
4676 source: *left_source,
4677 value: subtract_enclosures(left, right)?,
4678 },
4679 _ => ResidualValue::Undetermined {
4680 reason: ResidualUndeterminedReason::OperandEvidenceUnresolved,
4681 },
4682 };
4683 Ok(IntersectionResidual::new(combined, left, right))
4684}
4685
4686fn operand_residual_value(operand: &IntersectionOperand) -> Result<ResidualValue, GeometryFailure> {
4687 match operand {
4688 IntersectionOperand::Evaluated(ShapeEvaluation::Exact(
4689 ExactShapeEvaluation::ImplicitSurface { scalar },
4690 )) => Ok(ResidualValue::Exact {
4691 value: scalar.try_clone()?,
4692 }),
4693 IntersectionOperand::Evaluated(ShapeEvaluation::CertifiedEnclosure(
4694 CertifiedShapeEvaluation::ImplicitSurface {
4695 scalar,
4696 owner,
4697 requirement,
4698 source,
4699 },
4700 )) => Ok(ResidualValue::Certified {
4701 owner: *owner,
4702 requirement: clone_requirement(requirement)?,
4703 source: *source,
4704 value: clone_enclosure(scalar)?,
4705 }),
4706 _ => Ok(ResidualValue::Undetermined {
4707 reason: ResidualUndeterminedReason::ScalarResidualUnavailable,
4708 }),
4709 }
4710}
4711
4712fn undetermined_with(
4713 reason: IntersectionUndeterminedReason,
4714 residual: IntersectionResidual,
4715 witness: IntersectionWitness,
4716) -> IntersectionSet {
4717 IntersectionSet::undetermined(reason, residual, witness)
4718}
4719
4720fn refine_root(
4721 bracket: &CalculusRootBracket,
4722 policy: &RootIsolationPolicy,
4723) -> Result<CalculusRootIsolation, GeometryFailure> {
4724 match policy.method {
4725 RootRefinementMethod::Bisection => {
4726 neco_calculus::refine_root_bisection(bracket, policy.max_iterations)
4727 .map_err(map_calculus_failure)
4728 }
4729 RootRefinementMethod::NewtonBisection => {
4730 neco_calculus::refine_root_newton_bisection(bracket, policy.max_iterations, 32)
4731 .map_err(map_calculus_failure)
4732 }
4733 }
4734}
4735
4736fn contact_order_from_evidence(evidence: &RootEvidence) -> ContactOrder {
4737 match evidence {
4738 RootEvidence::SignChange { .. } | RootEvidence::SimpleRoot { .. } => {
4739 ContactOrder::new(ContactOrderKind::Transverse, 1)
4740 }
4741 RootEvidence::EvenMultiplicityTouch { order, .. } => {
4742 if *order == 2 {
4743 ContactOrder::new(ContactOrderKind::Tangent, 2)
4744 } else if *order > 2 {
4745 ContactOrder::new(ContactOrderKind::HigherOrder, *order)
4746 } else {
4747 ContactOrder::new(ContactOrderKind::Undetermined, 0)
4748 }
4749 }
4750 RootEvidence::HigherOrder { order, .. } => {
4751 ContactOrder::new(ContactOrderKind::HigherOrder, *order)
4752 }
4753 RootEvidence::Undetermined { .. } => ContactOrder::new(ContactOrderKind::Undetermined, 0),
4754 }
4755}
4756
4757fn clone_isolation(isolation: &RootIsolation) -> Result<RootIsolation, GeometryFailure> {
4758 let brackets = isolation
4759 .brackets
4760 .iter()
4761 .map(clone_bracket)
4762 .collect::<Result<Vec<_>, _>>()?;
4763 Ok(RootIsolation::new(
4764 brackets,
4765 clone_existence(&isolation.completeness),
4766 isolation.method,
4767 clone_domain(&isolation.source_domain),
4768 clone_residual_function(&isolation.source_function),
4769 clone_uniqueness(&isolation.non_overlap),
4770 ))
4771}
4772
4773fn clone_bracket(bracket: &RootBracket) -> Result<RootBracket, GeometryFailure> {
4774 Ok(RootBracket {
4775 contact_order: bracket.contact_order.clone(),
4776 convergence: ConvergenceWitness::new(
4777 bracket.convergence.final_lower.try_clone()?,
4778 bracket.convergence.final_upper.try_clone()?,
4779 bracket.convergence.initial_lower.try_clone()?,
4780 bracket.convergence.initial_upper.try_clone()?,
4781 bracket.convergence.iterations,
4782 bracket.convergence.method,
4783 bracket.convergence.status,
4784 ),
4785 lower: bracket.lower.try_clone()?,
4786 sign_change: bracket.sign_change,
4787 upper: bracket.upper.try_clone()?,
4788 evidence: clone_root_evidence(&bracket.evidence)?,
4789 exact_parameter: bracket
4790 .exact_parameter
4791 .as_ref()
4792 .map(|parameter| parameter.try_clone())
4793 .transpose()?,
4794 })
4795}
4796
4797pub(crate) fn clone_root_evidence(
4798 evidence: &RootEvidence,
4799) -> Result<RootEvidence, GeometryFailure> {
4800 Ok(match evidence {
4801 RootEvidence::SignChange {
4802 lower_sign,
4803 upper_sign,
4804 derivative_enclosure,
4805 source,
4806 } => RootEvidence::SignChange {
4807 lower_sign: *lower_sign,
4808 upper_sign: *upper_sign,
4809 derivative_enclosure: clone_enclosure(derivative_enclosure)?,
4810 source: source.clone(),
4811 },
4812 RootEvidence::EvenMultiplicityTouch {
4813 order,
4814 point,
4815 source,
4816 } => RootEvidence::EvenMultiplicityTouch {
4817 order: *order,
4818 point: point.try_clone()?,
4819 source: source.clone(),
4820 },
4821 RootEvidence::HigherOrder {
4822 order,
4823 point,
4824 source,
4825 } => RootEvidence::HigherOrder {
4826 order: *order,
4827 point: point.try_clone()?,
4828 source: source.clone(),
4829 },
4830 RootEvidence::SimpleRoot { point, source } => RootEvidence::SimpleRoot {
4831 point: point.try_clone()?,
4832 source: source.clone(),
4833 },
4834 RootEvidence::Undetermined { reason, source } => RootEvidence::Undetermined {
4835 reason: *reason,
4836 source: source.clone(),
4837 },
4838 })
4839}
4840
4841fn clone_existence(value: &ExistenceWitness) -> ExistenceWitness {
4842 ExistenceWitness::new(
4843 value.evidence,
4844 value.method,
4845 clone_witness_status(&value.status),
4846 )
4847}
4848
4849fn clone_uniqueness(value: &UniquenessWitness) -> UniquenessWitness {
4850 UniquenessWitness::new(
4851 value.evidence,
4852 value.method,
4853 clone_witness_status(&value.status),
4854 )
4855}
4856
4857fn clone_witness_status(status: &WitnessStatus) -> WitnessStatus {
4858 match status {
4859 WitnessStatus::Proved => WitnessStatus::Proved,
4860 WitnessStatus::Undetermined { reason } => WitnessStatus::Undetermined { reason: *reason },
4861 }
4862}
4863
4864fn clone_witness(value: &IntersectionWitness) -> Result<IntersectionWitness, GeometryFailure> {
4865 Ok(IntersectionWitness {
4866 existence: clone_existence(&value.existence),
4867 uniqueness: clone_uniqueness(&value.uniqueness),
4868 root_isolation: clone_isolation(&value.root_isolation)?,
4869 constraint: clone_constraint(&value.constraint)?,
4870 })
4871}
4872
4873fn clone_constraint(
4874 value: &IntersectionConstraint,
4875) -> Result<IntersectionConstraint, GeometryFailure> {
4876 Ok(IntersectionConstraint::new(
4877 clone_operand(value.left_operand())?,
4878 clone_operand(value.right_operand())?,
4879 clone_residual_function(value.residual_function()),
4880 clone_domain(value.domain()),
4881 clone_support_relation(value.support_relation()),
4882 clone_rank_evidence(value.rank_evidence()),
4883 ))
4884}
4885
4886fn clone_operand(value: &IntersectionOperand) -> Result<IntersectionOperand, GeometryFailure> {
4887 match value {
4888 IntersectionOperand::Declaration(declaration) => Ok(IntersectionOperand::Declaration(
4889 clone_declaration(declaration)?,
4890 )),
4891 IntersectionOperand::Evaluated(evaluation) => Ok(IntersectionOperand::Evaluated(
4892 clone_evaluation(evaluation)?,
4893 )),
4894 }
4895}
4896
4897fn clone_evaluation(value: &ShapeEvaluation) -> Result<ShapeEvaluation, GeometryFailure> {
4898 Ok(match value {
4899 ShapeEvaluation::Exact(evaluation) => ShapeEvaluation::Exact(match evaluation {
4900 ExactShapeEvaluation::ParametricCurve { coordinate } => {
4901 ExactShapeEvaluation::ParametricCurve {
4902 coordinate: clone_shape_coordinate(coordinate)?,
4903 }
4904 }
4905 ExactShapeEvaluation::ParametricSurface { coordinate } => {
4906 ExactShapeEvaluation::ParametricSurface {
4907 coordinate: clone_point(coordinate)?,
4908 }
4909 }
4910 ExactShapeEvaluation::ImplicitSurface { scalar } => {
4911 ExactShapeEvaluation::ImplicitSurface {
4912 scalar: scalar.try_clone()?,
4913 }
4914 }
4915 }),
4916 ShapeEvaluation::CertifiedEnclosure(evaluation) => {
4917 ShapeEvaluation::CertifiedEnclosure(match evaluation {
4918 CertifiedShapeEvaluation::ParametricCurve {
4919 coordinate,
4920 owner,
4921 requirement,
4922 source,
4923 } => CertifiedShapeEvaluation::ParametricCurve {
4924 coordinate: clone_shape_coordinate_enclosure(coordinate)?,
4925 owner: *owner,
4926 requirement: clone_requirement(requirement)?,
4927 source: *source,
4928 },
4929 CertifiedShapeEvaluation::ParametricSurface {
4930 coordinate,
4931 owner,
4932 requirement,
4933 source,
4934 } => CertifiedShapeEvaluation::ParametricSurface {
4935 coordinate: Box::new(clone_coordinate_enclosure3(coordinate)?),
4936 owner: *owner,
4937 requirement: clone_requirement(requirement)?,
4938 source: *source,
4939 },
4940 CertifiedShapeEvaluation::ImplicitSurface {
4941 scalar,
4942 owner,
4943 requirement,
4944 source,
4945 } => CertifiedShapeEvaluation::ImplicitSurface {
4946 scalar: clone_enclosure(scalar)?,
4947 owner: *owner,
4948 requirement: clone_requirement(requirement)?,
4949 source: *source,
4950 },
4951 })
4952 }
4953 ShapeEvaluation::Undetermined { family } => {
4954 ShapeEvaluation::Undetermined { family: *family }
4955 }
4956 })
4957}
4958
4959fn clone_shape_coordinate(value: &ShapeCoordinate) -> Result<ShapeCoordinate, GeometryFailure> {
4960 Ok(match value {
4961 ShapeCoordinate::Planar(point) => ShapeCoordinate::Planar(Point2 {
4962 x: point.x.try_clone()?,
4963 y: point.y.try_clone()?,
4964 }),
4965 ShapeCoordinate::Spatial(point) => ShapeCoordinate::Spatial(clone_point(point)?),
4966 })
4967}
4968
4969fn clone_shape_coordinate_enclosure(
4970 value: &crate::types::ShapeCoordinateEnclosure,
4971) -> Result<crate::types::ShapeCoordinateEnclosure, GeometryFailure> {
4972 Ok(match value {
4973 crate::types::ShapeCoordinateEnclosure::Planar(coordinate) => {
4974 crate::types::ShapeCoordinateEnclosure::Planar(crate::types::CoordinateEnclosure2 {
4975 x: clone_enclosure(&coordinate.x)?,
4976 y: clone_enclosure(&coordinate.y)?,
4977 })
4978 }
4979 crate::types::ShapeCoordinateEnclosure::Spatial(coordinate) => {
4980 crate::types::ShapeCoordinateEnclosure::Spatial(Box::new(clone_coordinate_enclosure3(
4981 coordinate,
4982 )?))
4983 }
4984 })
4985}
4986
4987fn clone_coordinate_enclosure3(
4988 value: &crate::types::CoordinateEnclosure3,
4989) -> Result<crate::types::CoordinateEnclosure3, GeometryFailure> {
4990 Ok(crate::types::CoordinateEnclosure3 {
4991 x: clone_enclosure(&value.x)?,
4992 y: clone_enclosure(&value.y)?,
4993 z: clone_enclosure(&value.z)?,
4994 })
4995}
4996
4997pub(crate) fn clone_support_relation(value: &SupportRelation) -> SupportRelation {
4998 match value {
4999 SupportRelation::Coincident { evidence } => SupportRelation::Coincident {
5000 evidence: *evidence,
5001 },
5002 SupportRelation::Curve { evidence } => SupportRelation::Curve {
5003 evidence: *evidence,
5004 },
5005 SupportRelation::Disjoint { evidence } => SupportRelation::Disjoint {
5006 evidence: *evidence,
5007 },
5008 SupportRelation::Finite { evidence } => SupportRelation::Finite {
5009 evidence: *evidence,
5010 },
5011 SupportRelation::Undetermined { reason } => {
5012 SupportRelation::Undetermined { reason: *reason }
5013 }
5014 }
5015}
5016
5017pub(crate) fn clone_rank_evidence(value: &RankEvidence) -> RankEvidence {
5018 match value {
5019 RankEvidence::Sufficient { rank } => RankEvidence::Sufficient { rank: *rank },
5020 RankEvidence::Degenerate { reason } => RankEvidence::Degenerate { reason: *reason },
5021 RankEvidence::Undetermined { reason } => RankEvidence::Undetermined { reason: *reason },
5022 }
5023}
5024
5025fn clone_residual(value: &IntersectionResidual) -> Result<IntersectionResidual, GeometryFailure> {
5026 Ok(IntersectionResidual::new(
5027 clone_residual_value(&value.combined)?,
5028 clone_residual_value(&value.left)?,
5029 clone_residual_value(&value.right)?,
5030 ))
5031}
5032
5033impl IntersectionResidual {
5034 fn clone_for_operation(&self) -> Result<Self, GeometryFailure> {
5035 clone_residual(self)
5036 }
5037}
5038
5039fn clone_residual_value(value: &ResidualValue) -> Result<ResidualValue, GeometryFailure> {
5040 Ok(match value {
5041 ResidualValue::Certified {
5042 owner,
5043 requirement,
5044 source,
5045 value,
5046 } => ResidualValue::Certified {
5047 owner: *owner,
5048 requirement: clone_requirement(requirement)?,
5049 source: *source,
5050 value: clone_enclosure(value)?,
5051 },
5052 ResidualValue::Exact { value } => ResidualValue::Exact {
5053 value: value.try_clone()?,
5054 },
5055 ResidualValue::Undetermined { reason } => ResidualValue::Undetermined { reason: *reason },
5056 })
5057}
5058
5059fn clone_domain(value: &IntersectionDomain) -> IntersectionDomain {
5060 IntersectionDomain::new(
5061 value.parameterization.clone(),
5062 value.restriction.clone(),
5063 value.support.clone(),
5064 )
5065}
5066
5067pub(crate) fn clone_residual_function(value: &ResidualFunction) -> ResidualFunction {
5068 ResidualFunction::new(
5069 value.left_expression.clone(),
5070 value.right_expression.clone(),
5071 )
5072}
5073
5074fn clone_identity(value: &BranchIdentity) -> Result<BranchIdentity, GeometryFailure> {
5075 Ok(BranchIdentity::new(
5076 value.branch_id.clone(),
5077 value.chart_id.clone(),
5078 value.support_id.clone(),
5079 ))
5080}
5081
5082fn clone_point(value: &Point3) -> Result<Point3, GeometryFailure> {
5083 Ok(Point3 {
5084 x: value.x.try_clone()?,
5085 y: value.y.try_clone()?,
5086 z: value.z.try_clone()?,
5087 })
5088}
5089
5090fn clone_enclosure(value: &Enclosure) -> Result<Enclosure, GeometryFailure> {
5091 Enclosure::new(
5092 value
5093 .lower()
5094 .try_clone()
5095 .map_err(|error| GeometryFailure::CalculusFailure {
5096 error: CalculusFailure::Polynomial(PolynomialFailure::Arithmetic(error)),
5097 })?,
5098 value
5099 .upper()
5100 .try_clone()
5101 .map_err(|error| GeometryFailure::CalculusFailure {
5102 error: CalculusFailure::Polynomial(PolynomialFailure::Arithmetic(error)),
5103 })?,
5104 )
5105 .map_err(|error| GeometryFailure::CalculusFailure {
5106 error: CalculusFailure::Interval(error),
5107 })
5108}
5109
5110fn clone_requirement(
5111 requirement: &ExactExpressionRequirement,
5112) -> Result<ExactExpressionRequirement, GeometryFailure> {
5113 ExactExpressionRequirement::new(
5114 requirement.consumer_id(),
5115 requirement.expressions(),
5116 requirement.decision(),
5117 requirement.precision(),
5118 )
5119 .map_err(|_| GeometryFailure::EvaluationIndeterminacy {
5120 family: crate::types::ShapeFamily::ImplicitSurface,
5121 reason: crate::types::ShapeEvaluationIndeterminacy::CalculusResult,
5122 })
5123}
5124
5125fn subtract_enclosures(left: &Enclosure, right: &Enclosure) -> Result<Enclosure, GeometryFailure> {
5126 Enclosure::new(
5127 left.lower()
5128 .sub(right.upper())
5129 .map_err(map_bigint_failure)?,
5130 left.upper()
5131 .sub(right.lower())
5132 .map_err(map_bigint_failure)?,
5133 )
5134 .map_err(|error| GeometryFailure::CalculusFailure {
5135 error: CalculusFailure::Interval(error),
5136 })
5137}
5138
5139pub(crate) fn dyadic_to_real(value: &Dyadic) -> Result<RealAlgebraic, GeometryFailure> {
5140 if value.is_zero() {
5141 return Ok(RealAlgebraic::from_integer(BigInt::zero())?);
5142 }
5143 let denominator = BigUint::one()
5144 .map_err(map_bigint_failure)?
5145 .shl_bits(value.exponent() as usize)
5146 .map_err(map_bigint_failure)?;
5147 let rational = RawRational::new(
5148 value.integer().try_clone().map_err(map_bigint_failure)?,
5149 denominator,
5150 )
5151 .reduce()
5152 .map_err(map_bigint_failure)?
5153 .into_reduced();
5154 RealAlgebraic::from_reduced_rational(&rational).map_err(GeometryFailure::AlgebraFailure)
5155}
5156
5157fn real_to_dyadic(value: &RealAlgebraic) -> Result<Dyadic, GeometryFailure> {
5158 let minimal = value.minimal_polynomial().polynomial();
5159 if minimal.degree() == Some(1) {
5160 let coefficients = minimal.coefficients();
5161 let mut numerator = coefficients[0].negated().map_err(map_bigint_failure)?;
5162 let leading = &coefficients[1];
5163 if matches!(leading.sign(), Sign::Negative) {
5164 numerator = numerator.negated().map_err(map_bigint_failure)?;
5165 }
5166 let denominator = leading.magnitude();
5167 let bit_len = denominator.bit_len();
5168 if bit_len > 0 && (0..bit_len - 1).all(|bit| !denominator.bit(bit)) {
5169 return Ok(Dyadic::new(numerator, (bit_len - 1) as u32));
5170 }
5171 }
5172 if value.is_zero() {
5173 return Ok(Dyadic::new(BigInt::zero(), 0));
5174 }
5175 if value.is_one() {
5176 return Ok(Dyadic::new(BigInt::one().map_err(map_bigint_failure)?, 0));
5177 }
5178 let sign = value.sign().map_err(GeometryFailure::AlgebraFailure)?;
5179 if matches!(sign, Sign::Negative) {
5180 let negative_one = BigInt::zero()
5181 .sub(&BigInt::one().map_err(map_bigint_failure)?)
5182 .map_err(map_bigint_failure)?;
5183 let magnitude = value.mul(&RealAlgebraic::from_integer(negative_one)?)?;
5184 let mut dyadic = real_to_dyadic(&magnitude)?;
5185 dyadic = Dyadic::new(
5186 dyadic.integer().negated().map_err(map_bigint_failure)?,
5187 dyadic.exponent(),
5188 );
5189 return Ok(dyadic);
5190 }
5191 let enclosure = value
5192 .enclose(0)
5193 .map_err(GeometryFailure::AlgebraFailure)?
5194 .enclosure()
5195 .try_clone()
5196 .map_err(map_bigint_failure)?;
5197 if enclosure.lower() == enclosure.upper() {
5198 return enclosure.lower().try_clone().map_err(map_bigint_failure);
5199 }
5200 Err(GeometryFailure::EvaluationIndeterminacy {
5201 family: crate::types::ShapeFamily::ParametricCurve,
5202 reason: crate::types::ShapeEvaluationIndeterminacy::DomainValidity,
5203 })
5204}
5205
5206fn map_bigint_failure(error: BigintError) -> GeometryFailure {
5207 GeometryFailure::CalculusFailure {
5208 error: CalculusFailure::Polynomial(PolynomialFailure::Arithmetic(error)),
5209 }
5210}
5211
5212fn map_calculus_failure(error: CalculusFailure) -> GeometryFailure {
5213 GeometryFailure::CalculusFailure { error }
5214}
5215
5216fn calculus_polynomial_failure(error: PolynomialFailure) -> GeometryFailure {
5217 GeometryFailure::CalculusFailure {
5218 error: CalculusFailure::Polynomial(error),
5219 }
5220}
5221
5222fn opposite_nonzero(left: Sign, right: Sign) -> bool {
5223 matches!(
5224 (left, right),
5225 (Sign::Negative, Sign::Positive) | (Sign::Positive, Sign::Negative)
5226 )
5227}
5228
5229fn root_sign(sign: Sign) -> RootSign {
5230 match sign {
5231 Sign::Negative => RootSign::Negative,
5232 Sign::Positive => RootSign::Positive,
5233 Sign::Zero => RootSign::Zero,
5234 }
5235}
5236
5237fn constraint_support_id(constraint: &IntersectionConstraint) -> String {
5238 format!(
5239 "{}|{}",
5240 operand_support_id(constraint.left_operand()),
5241 operand_support_id(constraint.right_operand())
5242 )
5243}
5244
5245fn constraint_chart_id(constraint: &IntersectionConstraint) -> String {
5246 format!(
5247 "{}|{}",
5248 operand_chart_id(constraint.left_operand()),
5249 operand_chart_id(constraint.right_operand())
5250 )
5251}
5252
5253fn operand_support_id(operand: &IntersectionOperand) -> String {
5254 match operand {
5255 IntersectionOperand::Declaration(value) => format!("declaration-{:?}", value.family()),
5256 IntersectionOperand::Evaluated(value) => format!("evaluated-{:?}", value),
5257 }
5258}
5259
5260fn operand_chart_id(operand: &IntersectionOperand) -> String {
5261 match operand {
5262 IntersectionOperand::Declaration(value) => format!("chart-{:?}", value.family()),
5263 IntersectionOperand::Evaluated(value) => format!("evaluation-{:?}", value),
5264 }
5265}
5266
5267fn curve_expression(value: &crate::types::ParametricCurveDeclaration) -> String {
5268 format!("curve-domain:{}", value.chart_domain())
5269}
5270
5271fn surface_expression(value: &crate::types::ParametricSurfaceDeclaration) -> String {
5272 format!("surface-domain:{}", value.chart().display_name().as_str())
5273}
5274
5275fn implicit_expression(value: &crate::types::ImplicitSurfaceDeclaration) -> String {
5276 format!("implicit-terms:{}", value.equation().terms().len())
5277}
5278
5279fn interval_bounds(
5280 interval: &crate::types::ParameterInterval,
5281) -> Option<(RealAlgebraic, RealAlgebraic)> {
5282 Some((
5283 interval.lower().try_clone().ok()?,
5284 interval.upper().try_clone().ok()?,
5285 ))
5286}
5287
5288fn curve_polynomial(
5289 value: &crate::types::ParametricCurveDeclaration,
5290) -> Result<Option<Polynomial>, GeometryFailure> {
5291 let chart = match value.chart() {
5292 crate::types::CurveChart::Chart2(chart) => chart.numerator_x(),
5293 crate::types::CurveChart::Chart3(chart) => chart.numerator_x(),
5294 };
5295 let coefficients = chart
5296 .to_real_algebraic_coefficients()
5297 .map_err(|error| GeometryFailure::CalculusFailure {
5298 error: CalculusFailure::Polynomial(PolynomialFailure::Algebra(error)),
5299 })?
5300 .into_coefficients();
5301 if coefficients.is_empty() {
5302 return Ok(Some(
5303 Polynomial::zero().map_err(calculus_polynomial_failure)?,
5304 ));
5305 }
5306 Ok(Some(
5307 Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
5308 ))
5309}
5310
5311fn implicit_polynomial(
5312 value: &crate::types::ImplicitSurfaceDeclaration,
5313) -> Result<Option<Polynomial>, GeometryFailure> {
5314 let mut coefficients = Vec::new();
5315 for term in value.equation().terms() {
5316 if term.exponent_y() != 0 || term.exponent_z() != 0 {
5317 return Ok(None);
5318 }
5319 while coefficients.len() <= term.exponent_x() as usize {
5320 coefficients.push(RealAlgebraic::from_integer(BigInt::zero())?);
5321 }
5322 coefficients[term.exponent_x() as usize] = term.coefficient().try_clone()?;
5323 }
5324 if coefficients.is_empty() {
5325 return Ok(Some(
5326 Polynomial::zero().map_err(calculus_polynomial_failure)?,
5327 ));
5328 }
5329 Ok(Some(
5330 Polynomial::from_coefficients(coefficients).map_err(calculus_polynomial_failure)?,
5331 ))
5332}
5333
5334fn clone_declaration(value: &ShapeDeclaration) -> Result<ShapeDeclaration, GeometryFailure> {
5335 match value {
5336 ShapeDeclaration::ParametricCurve(value) => Ok(ShapeDeclaration::ParametricCurve(
5337 crate::types::ParametricCurveDeclaration::new(
5338 clone_curve_chart(value.chart())?,
5339 crate::types::ParameterInterval::new(
5340 value.domain().lower().try_clone()?,
5341 value.domain().upper().try_clone()?,
5342 value.domain().lower_closed(),
5343 value.domain().upper_closed(),
5344 )?,
5345 ),
5346 )),
5347 ShapeDeclaration::ParametricSurface(value) => Ok(ShapeDeclaration::ParametricSurface(
5348 crate::types::ParametricSurfaceDeclaration::new(
5349 clone_surface_chart(value.chart())?,
5350 crate::types::SurfaceParameterDomain::new(
5351 clone_interval(value.domain().u())?,
5352 clone_interval(value.domain().v())?,
5353 ),
5354 ),
5355 )),
5356 ShapeDeclaration::ImplicitSurface(value) => Ok(ShapeDeclaration::ImplicitSurface(
5357 crate::types::ImplicitSurfaceDeclaration::new(clone_polynomial3(value.equation())?),
5358 )),
5359 }
5360}
5361
5362fn clone_curve_chart(
5363 value: &crate::types::CurveChart,
5364) -> Result<crate::types::CurveChart, GeometryFailure> {
5365 match value {
5366 crate::types::CurveChart::Chart2(chart) => Ok(crate::types::CurveChart::Chart2(
5367 neco_geometry_foundation::ChartDefinition2::new(
5368 chart.domain_id().try_clone()?,
5369 chart.display_name().try_clone()?,
5370 chart.coefficients().try_clone()?,
5371 chart.numerator_x().try_clone()?,
5372 chart.numerator_y().try_clone()?,
5373 chart.denominator().try_clone()?,
5374 )?,
5375 )),
5376 crate::types::CurveChart::Chart3(chart) => {
5377 Ok(crate::types::CurveChart::Chart3(clone_chart3(chart)?))
5378 }
5379 }
5380}
5381
5382fn clone_surface_chart(
5383 chart: &crate::types::ParametricSurfaceChart2,
5384) -> Result<crate::types::ParametricSurfaceChart2, GeometryFailure> {
5385 crate::types::ParametricSurfaceChart2::try_new(
5386 chart.identity().domain_id().try_clone()?,
5387 chart.display_name().try_clone()?,
5388 chart.identity().version(),
5389 chart.orientation(),
5390 crate::evaluation::clone_rational_surface(chart.surface())?,
5391 )
5392}
5393
5394fn clone_chart3(
5395 chart: &neco_geometry_foundation::ChartDefinition3,
5396) -> Result<neco_geometry_foundation::ChartDefinition3, GeometryFailure> {
5397 Ok(neco_geometry_foundation::ChartDefinition3::new(
5398 chart.domain_id().try_clone()?,
5399 chart.display_name().try_clone()?,
5400 chart.coefficients().try_clone()?,
5401 chart.numerator_x().try_clone()?,
5402 chart.numerator_y().try_clone()?,
5403 chart.numerator_z().try_clone()?,
5404 chart.denominator().try_clone()?,
5405 )?)
5406}
5407
5408fn clone_interval(
5409 value: &crate::types::ParameterInterval,
5410) -> Result<crate::types::ParameterInterval, GeometryFailure> {
5411 crate::types::ParameterInterval::new(
5412 value.lower().try_clone()?,
5413 value.upper().try_clone()?,
5414 value.lower_closed(),
5415 value.upper_closed(),
5416 )
5417}
5418
5419fn clone_polynomial3(
5420 value: &crate::types::MultivariatePolynomial3,
5421) -> Result<crate::types::MultivariatePolynomial3, GeometryFailure> {
5422 let terms = value
5423 .terms()
5424 .iter()
5425 .map(|term| {
5426 crate::types::PolynomialTerm3::new(
5427 term.coefficient().try_clone()?,
5428 term.exponent_x(),
5429 term.exponent_y(),
5430 term.exponent_z(),
5431 )
5432 })
5433 .collect::<Result<Vec<_>, _>>()?;
5434 crate::types::MultivariatePolynomial3::try_from_terms(terms)
5435}
5436
5437fn evaluate_declaration_capability(
5438 declaration: &ShapeDeclaration,
5439) -> Result<ShapeEvaluation, GeometryFailure> {
5440 match evaluate_shape(declaration_probe_request(declaration)?) {
5441 Ok(evaluation) => Ok(evaluation),
5442 Err(GeometryFailure::CalculusFailure {
5443 error: CalculusFailure::Polynomial(PolynomialFailure::EmptyCoefficients),
5444 }) => Ok(ShapeEvaluation::Undetermined {
5445 family: declaration.family(),
5446 }),
5447 Err(error) => Err(error),
5448 }
5449}
5450
5451fn declaration_probe_request(
5452 declaration: &ShapeDeclaration,
5453) -> Result<ShapeEvaluationRequest, GeometryFailure> {
5454 match declaration {
5455 ShapeDeclaration::ParametricCurve(value) => Ok(ShapeEvaluationRequest::new(
5456 clone_declaration(declaration)?,
5457 match value.chart() {
5458 crate::types::CurveChart::Chart2(_) | crate::types::CurveChart::Chart3(_) => {
5459 crate::types::ShapeEvaluationInput::ParametricCurve {
5460 parameter: value.domain().lower().try_clone()?,
5461 }
5462 }
5463 },
5464 )),
5465 ShapeDeclaration::ParametricSurface(value) => Ok(ShapeEvaluationRequest::new(
5466 clone_declaration(declaration)?,
5467 crate::types::ShapeEvaluationInput::ParametricSurface {
5468 u: value.domain().u().lower().try_clone()?,
5469 v: value.domain().v().lower().try_clone()?,
5470 },
5471 )),
5472 ShapeDeclaration::ImplicitSurface(_) => Ok(ShapeEvaluationRequest::new(
5473 clone_declaration(declaration)?,
5474 crate::types::ShapeEvaluationInput::ImplicitSurface {
5475 point: Point3 {
5476 x: RealAlgebraic::from_integer(BigInt::zero())?,
5477 y: RealAlgebraic::from_integer(BigInt::zero())?,
5478 z: RealAlgebraic::from_integer(BigInt::zero())?,
5479 },
5480 },
5481 )),
5482 }
5483}
5484
5485trait ChartDomain {
5486 fn chart_domain(&self) -> &str;
5487}
5488
5489impl ChartDomain for crate::types::ParametricCurveDeclaration {
5490 fn chart_domain(&self) -> &str {
5491 match self.chart() {
5492 crate::types::CurveChart::Chart2(chart) => chart.domain_id().as_str(),
5493 crate::types::CurveChart::Chart3(chart) => chart.domain_id().as_str(),
5494 }
5495 }
5496}
5497
5498trait SupportRelationExt {
5499 fn is_undetermined(&self) -> bool;
5500}
5501
5502impl SupportRelationExt for SupportRelation {
5503 fn is_undetermined(&self) -> bool {
5504 matches!(self, SupportRelation::Undetermined { .. })
5505 }
5506}
5507
5508#[cfg(test)]
5509mod tests {
5510 use super::*;
5511
5512 fn algebraic(value: i32) -> RealAlgebraic {
5513 RealAlgebraic::from_integer(BigInt::try_from(value).unwrap()).unwrap()
5514 }
5515
5516 fn unit_enclosure() -> Enclosure {
5517 Enclosure::new(
5518 Dyadic::new(BigInt::zero(), 0),
5519 Dyadic::new(BigInt::one().unwrap(), 0),
5520 )
5521 .unwrap()
5522 }
5523
5524 fn polynomial(coefficients: &[i32]) -> Polynomial {
5525 Polynomial::from_coefficients(coefficients.iter().map(|value| algebraic(*value)).collect())
5526 .unwrap()
5527 }
5528
5529 fn problem(polynomial: Polynomial) -> DerivedRootProblem {
5530 let operand = IntersectionOperand::Evaluated(ShapeEvaluation::Undetermined {
5531 family: crate::types::ShapeFamily::ParametricCurve,
5532 });
5533 DerivedRootProblem {
5534 constraint: IntersectionConstraint::new(
5535 operand,
5536 IntersectionOperand::Evaluated(ShapeEvaluation::Undetermined {
5537 family: crate::types::ShapeFamily::ImplicitSurface,
5538 }),
5539 ResidualFunction::new(String::from("left"), String::from("right")),
5540 IntersectionDomain::new(
5541 String::from("chart"),
5542 String::from("domain"),
5543 String::from("support"),
5544 ),
5545 SupportRelation::Finite {
5546 evidence: SupportEvidence::EvaluatedSpatialCoordinates,
5547 },
5548 RankEvidence::Sufficient { rank: 1 },
5549 ),
5550 polynomial: Some(polynomial),
5551 domain: Some(unit_enclosure()),
5552 }
5553 }
5554
5555 fn policy(max_iterations: usize) -> RootIsolationPolicy {
5556 RootIsolationPolicy::new(
5557 max_iterations,
5558 RootRefinementMethod::Bisection,
5559 unit_enclosure(),
5560 )
5561 .unwrap()
5562 }
5563
5564 #[test]
5565 fn sign_change_with_derivative_zero_is_unresolved() {
5566 let polynomial = polynomial(&[-1, 36, -96, 64]);
5567 let enclosure = unit_enclosure();
5568 let derivative = polynomial.derivative(DerivativeOrder::new(1)).unwrap();
5569 assert!(derivative
5570 .evaluate_enclosure(&enclosure, ROOT_INTERVAL_PRECISION_BITS)
5571 .unwrap()
5572 .contains_zero());
5573 assert!(matches!(
5574 assess_partition_cell(
5575 &polynomial,
5576 &derivative,
5577 &enclosure,
5578 0,
5579 &DerivativeOrder::new(2),
5580 "test",
5581 &[],
5582 )
5583 .unwrap(),
5584 CellAssessment::Unresolved(PartitionUnresolvedReason::SignChangeUniqueness)
5585 ));
5586 }
5587
5588 #[test]
5589 fn exact_touch_pivot_keeps_distinct_root_region_pending() {
5590 let polynomial = polynomial(&[-3, 22, -52, 40]);
5591 let enclosure = unit_enclosure();
5592 let derivative = polynomial.derivative(DerivativeOrder::new(1)).unwrap();
5593 let assessment = assess_partition_cell(
5594 &polynomial,
5595 &derivative,
5596 &enclosure,
5597 0,
5598 &DerivativeOrder::new(8),
5599 "test",
5600 &[],
5601 )
5602 .unwrap();
5603 let pivot = match assessment {
5604 CellAssessment::ExactTouch { candidate, pivot } => {
5605 assert!(matches!(
5606 candidate.evidence,
5607 RootEvidence::EvenMultiplicityTouch { .. }
5608 ));
5609 pivot
5610 }
5611 _ => panic!("expected the exact touch pivot"),
5612 };
5613 let lower = Enclosure::new(
5614 enclosure.lower().try_clone().unwrap(),
5615 pivot.try_clone().unwrap(),
5616 )
5617 .unwrap();
5618 assert!(!matches!(
5619 assess_partition_cell(
5620 &polynomial,
5621 &derivative,
5622 &lower,
5623 1,
5624 &DerivativeOrder::new(8),
5625 "test",
5626 &[pivot],
5627 )
5628 .unwrap(),
5629 CellAssessment::RootFree
5630 ));
5631
5632 let root_problem = problem(polynomial);
5633 let candidates = enumerate_root_candidates(&root_problem, &policy(2)).unwrap();
5634 let isolation = build_root_isolation(&root_problem, candidates, &policy(2)).unwrap();
5635 assert!(
5636 isolation.brackets().len() >= 2
5637 || matches!(
5638 isolation.completeness().status(),
5639 WitnessStatus::Undetermined { .. }
5640 )
5641 );
5642 }
5643
5644 #[test]
5645 fn suppressed_exact_endpoint_is_not_repeated_as_candidate() {
5646 let root_problem = problem(polynomial(&[0, 0, 1]));
5647 let enumeration = enumerate_root_candidates(&root_problem, &policy(4)).unwrap();
5648 assert_eq!(enumeration.candidates.len(), 1);
5649 assert!(matches!(
5650 enumeration.candidates[0].evidence,
5651 RootEvidence::EvenMultiplicityTouch { .. }
5652 ));
5653 }
5654}