Surface To Surface Intersections - MIT

Surface to Surface IntersectionsN. M. Patrikalakis, T. Maekawa, K. H. Ko, H. MukundanMay 2004

IntroductionMotivation Surface to surface intersection (SSI) is needed in: Slide No. 2Solid modeling (B-rep)ContouringNumerically controlled machining (Milling)Collision avoidanceFeature recognitionManufacturing simulationComputer animation

IntroductionBackground Intersection of two parametric surfaces, P (σ , t ) Q(u , v) definedin parametric spaces 0 σ , t 1 and 0 u , v 1 can havemultiple components [4].Q(u, v)P (σ , t )3D Model Space 11tv000σ1Parametric spaceofP (σ , t )0u1Parametric spaceofQ(u, v)An intersection curve segment is represented by a continuoustrajectory in parametric space.Slide No. 3

IntroductionPossible Approaches Three popular methods Lattice methods Issues related to topology, missing roots. Subdivision based methods Issues related to topology, extraneous roots. Marching scheme (Our Choice) Intersection curve segment is computed through an IVP.Slide No. 4

IntroductionMarching Scheme A marching scheme involves: Identifying all components Obtaining an accurate starting point in each component Tracing the given intersection correctly Assumption: The given surfaces are Rational Polynomial Parametric (RPP). We are given an intersection curve segment. No singularities exist in the intersection curve segment.Slide No. 5

IntroductionObjective Given an error bound on the starting point in both parametricspaces, obtain a bound for the entire intersection curve segmentin 3D model space.Strict Error Bound on Starting Point (Given)Slide No. 6Strict Error Bound on the EntireIntersection Curve Segment (Goal)

Outline Problem Formulation Error Bounds in Parametric Space Error Bounds in 3D Model Space Results and Examples ConclusionsSlide No. 7

Problem FormulationTransversal Intersection Transversal intersection formulated as a system of ordinary differentialequations (ODEs) in parametric space [4].From P(σ , t ) Q(u , v), we obtain :Pdσ Det[c, Pt , N (σ , t )] ,ds N P (σ , t ) N P (σ , t )Pdt Det[ Pσ , c, N (σ , t )] ,ds N P (σ , t ) N P (σ , t )QDet[,,(u , v )]cQNduv ,ds N Q (u , v ) N Q (u , v )Qdv Det[Qu , c, N (u , v )] ,ds N Q (u , v ) N Q (u , v )where s is the arc length parameter andPσ , Pt , Q u , Q v are partial derivativesSlide No. 8NP P PtσNQ Q QuvNP NQc PN NQNormal to P (σ , t )Normal to Q (u , v )

Problem FormulationTangential Intersection ODEs have the same form as in transversal intersection caseDet[c, P , N P (σ , t )]tσ ' P,N (σ , t ) N P (σ , t )t' Det[ P , c, N P (σ , t )]Det[c, Q , N Q (u , v )]vu' Q,N (u , v ) N Q (u , v )σ,N (σ , t ) N P (σ , t )Normal to P (σ , t ) and N Q Q QPDet[Q , c, N Q (u , v )]v' Q u,N (u , v ) N Q (u , v )Normal to Q (u , v )NP P Pσtuvc is determined using the second derivative s of the surfaces. From the condition of equal normal curvatures we obtain the equationb11 (σ ' ) 2 2b12 (σ ' )(t ' ) b22 (t ' ) 2 0 where b 11 , b 12 , b 22 are functions of the first and second fundamentalform coefficients of the surfaces.2222For a unique marching direction, (b12 b11b22 ) 0 and (b12 b11 b22 ) 0 c Thus if:b11 0,ν Pσ Ptb, where ν 12ν Pσ Ptb11Slide No. 9or if:c b11 0, b22 0bPσ µ Pt, where µ 12b22Pσ µ Pt

Problem FormulationVector IVP for ODE Given a starting point (initial condition) belonging to anintersection curve segment, we can integrate the system ofODEs. The system of ODEs with the starting point represents an initialvalue problem (IVP). Written in vector notation as: dσ f1 (σ , t , u , v) ds dt f 2 (σ , t , u , v) ds du ds f 3 (σ , t , u , v) dv f (σ , t , u , v) ds 4dy f (y ), y (0) y 0dsSlide No. 10

Outline Problem Formulation Error Bounds in Parametric Space Review of Standard Schemes Interval Arithmetic Validated Interval Scheme Error Bounds in 3D Model Space Results and Examples ConclusionsSlide No. 11

Error Bounds in Parametric SpaceReview of Standard Schemes Well-known Standard Schemes: Properties of Standard Schemes: Runge-Kutta Method Adams-Bashforth Method Taylor Series Method Slide No. 12TheyTheyTheyTheyare approximation schemes and introduce a truncation errordo not consider uncertainty in initial conditionsare prone to rounding errorssuffer from straying or looping near closely spaced features

Error Bounds in Parametric SpaceInterval Arithmetic (Introduction) Intervals are defined by Example:[2]:π 3.14159265 3589793238 46 Kπ [3.141 , 3.142 ] [π ] Basic interval arithmetic operations are defined by:Slide No. 13

Error Bounds in Parametric SpaceInterval Arithmetic (Solution of IVPs) For strict bounds for IVPs in parametric space, we employ avalidated interval scheme for ODEs [3]. The error in starting point is bounded by an initial interval. Interval solution represents a family of solutions passing throughthe initial interval satisfying the governing ODEs.Slide No. 14

Error Bounds in Parametric SpaceValidated Interval Scheme (Introduction) Every step of a validated interval scheme involves[3]: Computing an interval valued function [y](s) such that: y(s) [y](s) , and The width of the[y](s) is below a given tolerance s [sj , sj 1] Verifying the existence and uniqueness of the solution in [sj , sj 1].Slide No. 15

Error Bounds in Parametric SpaceValidated Interval Scheme (Overview) One step of a validated interval scheme is done in two phases:Phase 1: Phase I Algorithm A step sizehj s j 1 s j An a priori enclosurey(s) [ y j ],[ y j ] such that: s [s j , s j 1] Phase II Algorithm[ yj ] compute a tighter bound [ y j 1]at s j 1 . UsingSlide No. 16

Error Bounds in Parametric SpaceValidated Interval Scheme (Phase I : Validation) yj ] and hj satisfying the relation:A pair of [ [ y j ] [y j ] f ([ y j ])h j This assures existence and uniqueness of the solution. This method is called a constant enclosure method [3]. The a priori enclosure [ yj ] bounds the true solution in theparametric space s [sj , sj 1] . Numerical implementation Choosing a [ yj ] and, Iterating to find a corresponding hj .Slide No. 17

Error Bounds in Parametric SpaceValidated Interval Scheme (Phase II : Tighter Bound) Using the a priori enclosure we This phase helps in the propagation of the solution by providingan initial interval for the successive step. The key idea is to use: Interval version of Taylor’s formula [3]. find a tighter bound [y j 1 ] at s j 1 [3].k 1[y j 1 ] [y j ] h j i f [ i ] ([y j ]) h j k f [ k ] ([y% j ])i 1where f [i ] ([y j ]) represents the i th Taylor coefficientobtained using a technique called Automatic Differentiation [3].Slide No. 18

Error Bounds in Parametric SpaceValidated Interval Scheme (Application to SSI) We represent the surfaces as interval surfaces. Interval surfaces have interval coefficients and are written as:[P ](σ , t ) and [Q](u , v) We obtain a vector interval ODE system :Tdy dσ dt du dv f ([y ( s)]) ds ds ds ds ds With an interval initial condition :[y 0 ] [[σ 0 ] [t0 ] [u0 ] [v0 ]]TSlide No. 19

Error Bounds in Parametric Space Validated ODE solver produces a priori enclosures in parametricspace of each surface, guaranteed to contain the true intersectioncurve segment. The union of a priori enclosures bounds the true intersectioncurve segment in parametric space.Slide No. 20

Outline Problem Formulation Error Bounds in Parametric Space Error Bounds in 3D Model Space Results and Examples ConclusionsSlide No. 21

Error Bounds in 3D Model SpaceMapping into 3D Model Space Mapping from parametric space to 3D model space using corresponding surfaces [P ](σ , t ) or [Q ](u , v) coupled with rounded interval arithmetic evaluation Ensures continuous error bounds in 3D model space [1]guaranteed to contain the true curve of intersection.Slide No. 22

Outline Problem Formulation Error Bounds in Parametric Space Error Bounds in 3D Model Space Results and Examples ConclusionsSlide No. 23

Results & ExamplesError Bounds in 3D Model Space (Transversal)0.0010.02Torus and cylinderSlide No. 24Two bi-cubic surfacesSelf intersection ofa bi-cubic surface

Results & ExamplesError Bounds in 3D Model Space (Tangential)Tangential intersections of parametric surfacesSlide No. 25

Results & ExamplesPreventing Straying and LoopingttσAdams-BashforthσRunge-KuttatPerturb ationSteps Req uired bythe M ethod 0.00000311390.0Singularity Reported-0.0000031303Result from avalidated intervalschemeσValidated ODE solver can correctly trace the intersection curve segment eventhrough closely spaced features, where standard methods fail.Slide No. 26

Outline Problem Formulation Error Bounds in Parametric Space Error Bounds in 3D Model Space Results and Examples ConclusionsSlide No. 27

ConclusionsMerits We realize validated error bounds in 3D model space whichenclose the true curve of intersection. The scheme can prevent the phenomenon of straying or looping. The scheme can accommodate the errors in: initial condition rounding during digital computation Validated error bounds for surface intersection is essential ininterval boundary representation for consistent solid models [5].Slide No. 28

ConclusionsLimitations and Future Work Limitations We assume that we have Identified each intersection curve segment Strict error bound on the starting point Increasing width of the interval solutions due to Rounding Phenomenon of wrapping Scope for future work Identification of all components Accurate evaluation of starting points in each of the componentSlide No. 29

Acknowledgements National Science Foundation Prof. T. Sakkalis Prof. N. NedialkovSlide No. 30

References1.Tracing surface intersections with a validated ODE system solver, Mukundan, H., Ko, K.H., Maekawa, T. Sakkalis, T., and Patrikalakis, N. M., Proceedings of the Ninth EG/ACMSymposium on Solid Modeling and Applications, G. Elber and G. Taubin, editors. Genova,Italy, June 2004. Eurographics Press.2.Moore R. E. Interval Analysis. Prentice-Hall, Englewood Cliffs, 1966.3.Nedialkov N. S. Computing the Rigorous Bounds on the Solution of an Initial ValueProblem for an Ordinary Differential Equation. PhD thesis, University of Toronto,Toronto, Canada, 1999.4.Patrikalakis N. M. and Maekawa T. Shape Interrogation for Computer Aided Design andManufacturing. Springer-Verlag, Heidelberg, 2002.5.Sakkalis T., Shen G. and Patrikalakis N.M., Topological and Geometric Properties ofInterval Solid Models, Graphical Models, 2001.6.Grandine T. A., Klein F. W.: A new approach to the surface intersection problem.Computer Aided Geometric Design 14, 2 (1997), 111–134. 650.Slide No. 31

Intersection of two parametric surfaces, defined in parametric spaces and can have multiple components[4]. An intersection curve segmentis represented by a continuous trajectory in parametric space. P(σ,t) Q(u,v) 0 σ,t 1 0 u,v 1 0 σ 1 0 u 1 0 1 t 0 1 v Parametric space of Q(u,v) Parametric space of P(σ,t) 3D Model Space P(σ,t .