/* Ċ Ġ* ĠCopyright ĠÂ© Ġ 2 0 2 1 ĠE no ve a Ġ( fab ien . me ur isse @ en ove a . net ) Ċ Ġ* Ċ Ġ* ĠLicensed Ġunder Ġthe ĠApache ĠLicense , ĠVersion Ġ 2 . 0 Ġ( the Ġ" License "); Ċ Ġ* Ġyou Ġmay Ġnot Ġuse Ġthis Ġfile Ġexcept Ġin Ġcompliance Ġwith Ġthe ĠLicense . Ċ Ġ* ĠYou Ġmay Ġobtain Ġa Ġcopy Ġof Ġthe ĠLicense Ġat Ċ Ġ* Ċ Ġ* ĠĠĠĠ Ġhttp :// www . apache . org / licenses / LICENSE - 2 . 0 Ċ Ġ* Ċ Ġ* ĠUnless Ġrequired Ġby Ġapplicable Ġlaw Ġor Ġagreed Ġto Ġin Ġwriting , Ġsoftware Ċ Ġ* Ġdistributed Ġunder Ġthe ĠLicense Ġis Ġdistributed Ġon Ġan Ġ" AS ĠIS " ĠBASIS , Ċ Ġ* ĠWITHOUT ĠWARRANTIES ĠOR ĠCONDITIONS ĠOF ĠANY ĠKIND , Ġeither Ġexpress Ġor Ġimplied . Ċ Ġ* ĠSee Ġthe ĠLicense Ġfor Ġthe Ġspecific Ġlanguage Ġgoverning Ġpermissions Ġand Ċ Ġ* Ġlimitations Ġunder Ġthe ĠLicense . Ċ Ġ*/ Ċ package Ġdil iv ia . s 2 . coords Ċ Ċ import Ġdil iv ia . Pre Conditions . check State Ċ import Ġdil iv ia . Pre Conditions . require Argument Ċ import Ġdil iv ia . math . vectors . R 2 Point Ċ import Ġdil iv ia . s 2 . S 2 Point Ċ import Ġorg . apache . commons . math 3 . util . Fast Math . max Ċ import Ġorg . apache . commons . math 3 . util . Fast Math . min Ċ import Ġorg . apache . commons . math 3 . util . Fast Math . round Ċ Ċ enum Ġclass ĠProjection s Ġ{ ĊĠĠĠ ĠLINE AR , ĠT AN , ĠQU AD RAT IC Ċ } Ċ Ċ /** Ċ Ġ* ĠS 2 Ġcoordinate Ġsystems . Ċ Ġ* Ċ Ġ* ĠThis Ġobject Ġcontains Ġthe Ġvarious Ġcoordinate Ġsystems Ġused Ġthroughout Ġthe Ġlibrary . ĠMost Ġimportant ly , ĠS 2 Ġdefines Ġa Ċ Ġ* Ġframework Ġfor Ġde comp osing Ġthe Ġunit Ġsphere Ġinto Ġa Ġhierarchy Ġof Ġ" cells ". Ġ ĠEach Ġcell Ġis Ġa Ġquadr il ateral Ġbounded Ġby Ġfour Ċ Ġ* Ġge odes ics . ĠThe Ġtop Ġlevel Ġof Ġthe Ġhierarchy Ġis Ġobtained Ġby Ġproject ing Ġthe Ġsix Ġfaces Ġof Ġa Ġcube Ġonto Ġthe Ġunit Ġsphere , Ċ Ġ* Ġand Ġlower Ġlevels Ġare Ġobtained Ġby Ġsub div iding Ġeach Ġcell Ġinto Ġfour Ġchildren Ġrecursively . ĠCell s Ġare Ġnumber ed Ġsuch Ġthat Ċ Ġ* Ġse quent ially Ġincreasing Ġcells Ġfollow Ġa Ġcontinuous Ġspace - fill ing Ġcurve Ġover Ġthe Ġentire Ġsphere . ĠThe Ġtransformation Ġis Ċ Ġ* Ġdesigned Ġto Ġmake Ġthe Ġcells Ġat Ġeach Ġlevel Ġfairly Ġuniform Ġin Ġsize . Ċ Ġ* Ċ Ġ* Ċ Ġ* ĠS 2 Cell ĠDe composition Ċ Ġ* Ġ---------------- ----- Ċ Ġ* Ċ Ġ* ĠThe Ġfollowing Ġmethods Ġdefine Ġthe Ġcube - to - sphere Ġprojection Ġused Ġby Ġthe ĠS 2 Cell Ġdecomposition . Ċ Ġ* Ċ Ġ* ĠIn Ġthe Ġprocess Ġof Ġconverting Ġa Ġlatitude - longitude Ġpair Ġto Ġa Ġ 6 4 - bit Ġcell Ġid , Ġthe Ġfollowing Ġcoordinate Ġsystems Ċ Ġ* Ġare Ġused : Ċ Ġ* Ċ Ġ* Ġ Ġ( id ) Ċ Ġ* ĠĠĠ ĠAn ĠS 2 CellId Ġis Ġa Ġ 6 4 - bit Ġencoding Ġof Ġa Ġface Ġand Ġa ĠH il bert Ġcurve Ġposition Ġon Ġthat Ġface . Ċ Ġ* ĠĠĠ ĠThe ĠH il bert Ġcurve Ġposition Ġimplicitly Ġen codes Ġboth Ġthe Ġposition Ġof Ġa Ġcell Ġand Ġits Ġsub division Ġlevel Ċ Ġ* ĠĠĠ Ġ( see ĠS 2 CellId ). Ċ Ġ* Ċ Ġ* Ġ Ġ( face , Ġi , Ġj ) Ċ Ġ* ĠĠĠ ĠLeaf - cell Ġcoordinates . Ġ Ġ" i " Ġand Ġ" j " Ġare Ġintegers Ġin Ġthe Ġrange Ġ[ 0 ,( 2 ** 3 0 )- 1 ] Ġthat Ġidentify Ġa Ġparticular Ċ Ġ* ĠĠĠ Ġleaf Ġcell Ġon Ġthe Ġgiven Ġface . Ċ Ġ* ĠĠĠ ĠThe Ġ( i , Ġj ) Ġcoordinate Ġsystem Ġis Ġright - h anded Ġon Ġeach Ġface , Ġand Ġthe Ġfaces Ġare Ġorient ed Ġsuch Ġthat ĠH il bert Ċ Ġ* ĠĠĠ Ġcurves Ġconnect Ġcontinuous ly Ġfrom Ġone Ġface Ġto Ġthe Ġnext . Ċ Ġ* Ċ Ġ* Ġ Ġ( face , Ġs , Ġt ) Ċ Ġ* ĠĠĠ ĠCell - space Ġcoordinates . Ġ Ġ" s " Ġand Ġ" t " Ġare Ġreal Ġnumbers Ġin Ġthe Ġrange Ġ[ 0 , 1 ] Ġthat Ġidentify Ġa Ġpoint Ġon Ġthe Ċ Ġ* ĠĠĠ Ġgiven Ġface . Ġ ĠFor Ġexample , Ġthe Ġpoint Ġ( s , Ġt ) Ġ= Ġ( 0 . 5 , Ġ 0 . 5 ) Ġcorresponds Ġto Ġthe Ġcenter Ġof Ġthe Ġtop - level Ġface Ċ Ġ* ĠĠĠ Ġcell . Ġ ĠThis Ġpoint Ġis Ġalso Ġa Ġvertex Ġof Ġexactly Ġfour Ġcells Ġat Ġeach Ġsub division Ġlevel Ġgreater Ġthan Ġzero . Ċ Ġ* Ċ Ġ* Ġ Ġ( face , Ġsi , Ġti ) Ċ Ġ* ĠĠĠ ĠDis crete Ġcell - space Ġcoordinates . Ġ ĠThese Ġare Ġobtained Ġby Ġmultiply ing Ġ" s " Ġand Ġ" t " Ġby Ġ 2 ** 3 1 Ġand Ġrounding Ċ Ġ* ĠĠĠ Ġto Ġthe Ġnearest Ġunsigned Ġinteger . ĠDis crete Ġcoordinates Ġlie Ġin Ġthe Ġrange Ġ[ 0 , 2 ** 3 1 ]. Ġ ĠThis Ġcoordinate Ġsystem Ċ Ġ* ĠĠĠ Ġcan Ġrepresent Ġthe Ġedge Ġand Ġcenter Ġpositions Ġof Ġall Ġcells Ġwith Ġno Ġloss Ġof Ġprecision Ġ( including Ġnon - leaf Ġcells ). Ċ Ġ* ĠĠĠ ĠIn Ġbinary , Ġeach Ġcoordinate Ġof Ġa Ġlevel - k Ġcell Ġcenter Ġends Ġwith Ġa Ġ 1 Ġfollowed Ġby Ġ( 3 0 Ġ- Ġk ) Ġ 0 s . Ċ Ġ* ĠĠĠ ĠThe Ġcoordinates Ġof Ġits Ġedges Ġend Ġwith Ġ( at Ġleast ) Ġ( 3 1 Ġ- Ġk ) Ġ 0 s . Ċ Ġ* Ċ Ġ* Ġ Ġ( face , Ġu , Ġv ) Ċ Ġ* ĠĠĠ ĠCube - space Ġcoordinates Ġin Ġthe Ġrange Ġ[- 1 , 1 ]. Ġ ĠTo Ġmake Ġthe Ġcells Ġat Ġeach Ġlevel Ġmore Ġuniform Ġin Ġsize Ġafter Ċ Ġ* ĠĠĠ Ġthey Ġare Ġprojected Ġonto Ġthe Ġsphere , Ġwe Ġapply Ġa Ġnonlinear Ġtransformation Ġof Ġthe Ġform Ġu = f ( s ), Ġv = f ( t ). Ċ Ġ* ĠĠĠ ĠThe Ġ( u , Ġv ) Ġcoordinates Ġafter Ġthis Ġtransformation Ġgive Ġthe Ġactual Ġcoordinates Ġon Ġthe Ġcube Ġface Ċ Ġ* ĠĠĠ Ġ( modulo Ġsome Ġ 9 0 Ġdegree Ġrot ations ) Ġbefore Ġit Ġis Ġprojected Ġonto Ġthe Ġunit Ġsphere . Ċ Ġ* Ċ Ġ* Ġ Ġ( face , Ġu , Ġv , Ġw ) Ċ Ġ* ĠĠĠ ĠPer - face Ġcoordinate Ġframe . Ġ ĠThis Ġis Ġan Ġextension Ġof Ġthe Ġ( face , Ġu , Ġv ) Ġcube - space Ġcoordinates Ġthat Ġadds Ġa Ċ Ġ* ĠĠĠ Ġthird Ġaxis Ġ" w " Ġin Ġthe Ġdirection Ġof Ġthe Ġface Ġnormal . Ġ ĠIt Ġis Ġalways Ġa Ġright - h anded Ġ 3 D Ġcoordinate Ġsystem . Ċ Ġ* ĠĠĠ ĠCube - space Ġcoordinates Ġcan Ġbe Ġconverted Ġto Ġthis Ġframe Ġby Ġsetting Ġw = 1 , Ġwhile Ġ( u , v , w ) Ġcoordinates Ġcan Ġbe Ċ Ġ* ĠĠĠ Ġprojected Ġonto Ġthe Ġcube Ġface Ġby Ġdiv iding Ġby Ġw , Ġi . e . Ġ( face , Ġu / w , Ġv / w ). Ċ Ġ* Ċ Ġ* Ġ Ġ( x , Ġy , Ġz ) Ċ Ġ* ĠĠĠ ĠDirection Ġvector Ġ( S 2 Point ). Ġ ĠDirection Ġvectors Ġare Ġnot Ġnecessarily Ġunit Ġlength , Ġand Ġare Ġoften Ġchosen Ċ Ġ* ĠĠĠ Ġto Ġbe Ġpoints Ġon Ġthe Ġbi unit Ġcube Ġ[- 1 , + 1 ] x [- 1 , + 1 ] x [- 1 , + 1 ]. Ġ ĠThey Ġcan Ġbe Ġbe Ġnormalized Ġto Ġobtain Ġthe Ċ Ġ* ĠĠĠ Ġcorresponding Ġpoint Ġon Ġthe Ġunit Ġsphere . Ċ Ġ* Ċ Ġ* Ġ Ġ( lat , Ġlng ) Ċ Ġ* ĠĠĠ ĠLat itude Ġand Ġlongitude Ġ( S 2 LatLng ). Ġ ĠLat itude s Ġmust Ġbe Ġbetween Ġ- 9 0 Ġand Ġ 9 0 Ġdegrees Ġinclusive , Ġand Ċ Ġ* ĠĠĠ Ġlongitude s Ġmust Ġbe Ġbetween Ġ- 1 8 0 Ġand Ġ 1 8 0 Ġdegrees Ġinclusive . Ċ Ġ* Ċ Ġ* ĠNote Ġthat Ġthe Ġ( i , Ġj ), Ġ( s , Ġt ), Ġ( si , Ġti ), Ġand Ġ( u , Ġv ) Ġcoordinate Ġsystems Ġare Ġright - h anded Ġon Ġall Ġsix Ġfaces . Ċ Ġ* Ċ Ġ* ĠThis Ġclass Ġis Ġa Ġport Ġof Ġs 2 coords Ġand Ġs 2 metrics Ġof Ġthe ĠGoogle ĠS 2 ĠGeometry Ġproject Ċ Ġ* Ġ( https :// github . com / google / s 2 geometry ). Ċ Ġ* Ċ Ġ* Ġ@ author ĠF ab ien ĠMe ur isse Ġ< fab ien . me ur isse @ en ove a . net > Ċ Ġ* Ġ@ since Ġ 1 . 0 Ċ Ġ*/ Ċ object ĠS 2 Coords Ġ{ ĊĊĠĠĠ Ġ// ĠThe Ġcanonical ĠH il bert Ġtraversal Ġorder Ġlooks Ġlike Ġan Ġinverted Ġ' U ': ĊĠĠĠ Ġ// Ġthe Ġsub cells Ġare Ġvisited Ġin Ġthe Ġorder Ġ( 0 , 0 ), Ġ( 0 , 1 ), Ġ( 1 , 1 ), Ġ( 1 , 0 ). ĊĠĠĠ Ġ// ĠThe Ġfollowing Ġtables Ġencode Ġthe Ġtraversal Ġorder Ġfor Ġvarious ĊĠĠĠ Ġ// Ġorient ations Ġof Ġthe ĠH il bert Ġcurve Ġ( axes Ġsw apped Ġand / or Ġdirections ĊĠĠĠ Ġ// Ġof Ġthe Ġaxes Ġreversed ). ĊĊĠĠĠ Ġ// ĠTo gether Ġthese Ġflags Ġdefine Ġa Ġcell Ġorientation . Ġ ĠIf Ġ' k Swap Mask ' ĊĠĠĠ Ġ// Ġis Ġtrue , Ġthen Ġcanonical Ġtraversal Ġorder Ġis Ġf lipped Ġaround Ġthe ĊĠĠĠ Ġ// Ġdiagonal Ġ( i . e . Ġi Ġand Ġj Ġare Ġsw apped Ġwith Ġeach Ġother ). Ġ ĠIf ĊĠĠĠ Ġ// Ġ' k Invert Mask ' Ġis Ġtrue , Ġthen Ġthe Ġtraversal Ġorder Ġis Ġrotated Ġby Ġ 1 8 0 ĊĠĠĠ Ġ// Ġdegrees Ġ( i . e . Ġthe Ġbits Ġof Ġi Ġand Ġj Ġare Ġinverted , Ġor Ġequivalent ly , ĊĠĠĠ Ġ// Ġthe Ġaxis Ġdirections Ġare Ġreversed ). ĊĠĠĠ Ġinternal Ġval Ġk Swap Mask Ġ= Ġ 0 x 0 1 ĊĠĠĠ Ġinternal Ġval Ġk Invert Mask Ġ= Ġ 0 x 0 2 ĊĊĠĠĠ Ġ// Ġk IJ to Pos [ orientation ][ ij ] Ġ-> Ġpos ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// ĠGiven Ġa Ġcell Ġorientation Ġand Ġthe Ġ( i , j )- index Ġof Ġa Ġsub cell Ġ( 0 =( 0 , 0 ), ĊĠĠĠ Ġ// Ġ 1 =( 0 , 1 ), Ġ 2 =( 1 , 0 ), Ġ 3 =( 1 , 1 )), Ġreturn Ġthe Ġorder Ġin Ġwhich Ġthis Ġsub cell Ġis ĊĠĠĠ Ġ// Ġvisited Ġby Ġthe ĠH il bert Ġcurve Ġ( a Ġposition Ġin Ġthe Ġrange Ġ[ 0 .. 3 ]). ĊĠĠĠ Ġinternal Ġval Ġk IJ to Pos Ġ= ĠarrayOf ( ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠ Ġ( 0 , 0 ) Ġ( 0 , 1 ) Ġ( 1 , 0 ) Ġ( 1 , 1 ) ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 1 , Ġ 3 , Ġ 2 ), Ġ Ġ// Ġcanonical Ġorder ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 3 , Ġ 1 , Ġ 2 ), Ġ Ġ// Ġaxes Ġsw apped ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 2 , Ġ 3 , Ġ 1 , Ġ 0 ), Ġ Ġ// Ġbits Ġinverted ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 2 , Ġ 1 , Ġ 3 , Ġ 0 ), Ġ Ġ// Ġsw apped Ġ& Ġinverted ĊĠĠĠ Ġ) Ġ// [ 4 ][ 4 ]; ĊĊĠĠĠ Ġ// Ġk Pos To IJ [ orientation ][ pos ] Ġ-> Ġij ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// ĠReturn Ġthe Ġ( i , j ) Ġindex Ġof Ġthe Ġsub cell Ġat Ġthe Ġgiven Ġposition Ġ' pos ' Ġin Ġthe ĊĠĠĠ Ġ// ĠH il bert Ġcurve Ġtraversal Ġorder Ġwith Ġthe Ġgiven Ġorientation . Ġ ĠThis Ġis Ġthe ĊĠĠĠ Ġ// Ġinverse Ġof Ġthe Ġprevious Ġtable : ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// ĠĠ Ġk Pos To IJ [ r ][ k IJ to Pos [ r ][ ij ]] Ġ== Ġij ĊĠĠĠ Ġinternal Ġval Ġk Pos To IJ Ġ= ĠarrayOf ( ĊĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠĠĠ 0 ĠĠ 1 ĠĠ 2 ĠĠ 3 ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 1 , Ġ 3 , Ġ 2 ), ĠĠĠ Ġ// Ġcanonical Ġorder : ĠĠĠ Ġ( 0 , 0 ), Ġ( 0 , 1 ), Ġ( 1 , 1 ), Ġ( 1 , 0 ) ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 2 , Ġ 3 , Ġ 1 ), ĠĠĠ Ġ// Ġaxes Ġsw apped : ĠĠĠĠĠĠ Ġ( 0 , 0 ), Ġ( 1 , 0 ), Ġ( 1 , 1 ), Ġ( 0 , 1 ) ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 3 , Ġ 2 , Ġ 0 , Ġ 1 ), ĠĠĠ Ġ// Ġbits Ġinverted : ĠĠĠĠĠ Ġ( 1 , 1 ), Ġ( 1 , 0 ), Ġ( 0 , 0 ), Ġ( 0 , 1 ) ĊĠĠĠĠĠĠĠ Ġint ArrayOf ( 3 , Ġ 1 , Ġ 0 , Ġ 2 ), ĠĠĠ Ġ// Ġsw apped Ġ& Ġinverted : Ġ( 1 , 1 ), Ġ( 0 , 1 ), Ġ( 0 , 0 ), Ġ( 1 , 0 ) ĊĠĠĠ Ġ) Ġ// [ 4 ][ 4 ]; ĊĊĠĠĠ Ġ// Ġk Pos To Orientation [ pos ] Ġ-> Ġorientation _ modifier ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// ĠReturn Ġa Ġmodifier Ġindicating Ġhow Ġthe Ġorientation Ġof Ġthe Ġchild Ġsub cell ĊĠĠĠ Ġ// Ġwith Ġthe Ġgiven Ġtraversal Ġposition Ġ[ 0 .. 3 ] Ġis Ġrelated Ġto Ġthe Ġorientation ĊĠĠĠ Ġ// Ġof Ġthe Ġparent Ġcell . Ġ ĠThe Ġmodifier Ġshould Ġbe ĠXOR - ed Ġwith Ġthe Ġparent ĊĠĠĠ Ġ// Ġorientation Ġto Ġobtain Ġthe Ġcurve Ġorientation Ġin Ġthe Ġchild . ĊĠĠĠ Ġval Ġk Pos To Orientation Ġ= Ġint ArrayOf ( ĊĠĠĠĠĠĠĠ Ġk Swap Mask , ĊĠĠĠĠĠĠĠĠ 0 , ĊĠĠĠĠĠĠĠĠ 0 , ĊĠĠĠĠĠĠĠ Ġk Invert Mask Ġ+ Ġk Swap Mask , ĊĠĠĠ Ġ) ĊĊĠĠĠ Ġ// ĠThe ĠU , V , W Ġaxes Ġfor Ġeach Ġface . ĊĠĠĠ Ġval Ġk Face UV W Axes Ġ// [ 6 ][ 3 ][ 3 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ= ĠarrayOf ( ĊĠĠĠĠĠĠĠ ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 1 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 0 , Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 1 , Ġ 0 , Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 1 , Ġ 0 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 0 , Ġ 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 1 , Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 1 , Ġ 0 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ- 1 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 0 , Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 0 , Ġ- 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ- 1 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf (- 1 , Ġ 0 , Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 0 , Ġ- 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 1 , Ġ 0 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ- 1 , Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 1 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 1 , Ġ 0 , Ġ 0 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( 0 , Ġ 0 , Ġ- 1 ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) ĊĊĠĠĠ Ġ// ĠThe Ġpre computed Ġneighbors Ġof Ġeach Ġface Ġ( see ĠGet UV W Face ). ĊĠĠĠ Ġval Ġk Face UV WF aces Ġ// [ 6 ][ 3 ][ 2 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ= ĠarrayOf ( ĊĠĠĠĠĠĠĠ ĠarrayOf ( int ArrayOf ( 4 , Ġ 1 ), Ġint ArrayOf ( 5 , Ġ 2 ), Ġint ArrayOf ( 3 , Ġ 0 )), ĊĠĠĠĠĠĠĠ ĠarrayOf ( int ArrayOf ( 0 , Ġ 3 ), Ġint ArrayOf ( 5 , Ġ 2 ), Ġint ArrayOf ( 4 , Ġ 1 )), ĊĠĠĠĠĠĠĠ ĠarrayOf ( int ArrayOf ( 0 , Ġ 3 ), Ġint ArrayOf ( 1 , Ġ 4 ), Ġint ArrayOf ( 5 , Ġ 2 )), ĊĠĠĠĠĠĠĠ ĠarrayOf ( int ArrayOf ( 2 , Ġ 5 ), Ġint ArrayOf ( 1 , Ġ 4 ), Ġint ArrayOf ( 0 , Ġ 3 )), ĊĠĠĠĠĠĠĠ ĠarrayOf ( int ArrayOf ( 2 , Ġ 5 ), Ġint ArrayOf ( 3 , Ġ 0 ), Ġint ArrayOf ( 1 , Ġ 4 )), ĊĠĠĠĠĠĠĠ ĠarrayOf ( int ArrayOf ( 4 , Ġ 1 ), Ġint ArrayOf ( 3 , Ġ 0 ), Ġint ArrayOf ( 2 , Ġ 5 )) ĊĠĠĠ Ġ) ĊĊĠĠĠ Ġ/** ĠThe Ġsphere Ġto Ġunit Ġcube Ġprojection . Ġ*/ ĊĠĠĠ Ġvar Ġprojection : ĠS 2 Projection Ġ= ĠS 2 Quadr atic Projection ĊĊĠĠĠ Ġ/** ĠThis Ġis Ġthe Ġnumber Ġof Ġlevels Ġneeded Ġto Ġspecify Ġa Ġleaf Ġcell . Ġ*/ ĊĠĠĠ Ġconst Ġval Ġk Max Cell Level Ġ= Ġ 3 0 ĊĊĠĠĠ Ġ/** ĠThe Ġmaximum Ġindex Ġof Ġa Ġvalid Ġleaf Ġcell Ġplus Ġone . ĠThe Ġrange Ġof Ġvalid Ġleaf Ġcell Ġindices Ġis Ġ[ 0 .. k Limit IJ - 1 ]. Ġ*/ ĊĠĠĠ Ġval Ġk Limit IJ Ġ= Ġ 1 Ġshl Ġk Max Cell Level Ġ Ġ// Ġ== ĠS 2 CellId :: k MaxSize ĊĊĠĠĠ Ġ/** ĠThe Ġmaximum Ġvalue Ġof Ġan Ġsi - Ġor Ġti - coordinate . Ġ ĠThe Ġrange Ġof Ġvalid Ġ( si , ti ) Ġvalues Ġis Ġ[ 0 .. k Max Si Ti ]. Ġ*/ ĊĠĠĠ Ġval Ġk Max Si Ti Ġ= Ġ 1 . to UInt () Ġshl Ġ( k Max Cell Level Ġ+ Ġ 1 ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġan Ġs - Ġor Ġt - value Ġto Ġthe Ġcorresponding Ġu - Ġor Ġv - value . Ġ ĠThis Ġis Ġa Ġnon - linear Ġtransformation ĊĠĠĠĠ Ġ* Ġfrom Ġ[- 1 , 1 ] Ġto Ġ[- 1 , 1 ] Ġthat Ġattempts Ġto Ġmake Ġthe Ġcell Ġsizes Ġmore Ġuniform . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġs Ġa Ġs - Ġor Ġt - value Ġin Ġ[- 1 , 1 ] ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġu - Ġor Ġv - value Ġ( in Ġ[- 1 , 1 ]). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġst To Uv ( s : ĠDouble ): ĠDouble Ġ= Ġprojection . st To Uv ( s ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġinverse Ġof Ġthe Ġst To Uv Ġtransformation . Ġ ĠNote Ġthat Ġit Ġis Ġnot Ġalways Ġtrue Ġthat Ġuv To St ( st To Uv ( x )) Ġ== Ġx ĊĠĠĠĠ Ġ* Ġdue Ġto Ġnumerical Ġerrors . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġu Ġu - Ġor Ġv - value Ġ( in Ġ[- 1 , 1 ]) ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġs - Ġor Ġt - value Ġ( in Ġ[- 1 , 1 ]). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġuv To St ( u : ĠDouble ): ĠDouble Ġ= Ġprojection . uv To St ( u ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġthe Ġi - Ġor Ġj - index Ġof Ġa Ġleaf Ġcell Ġto Ġthe Ġminimum Ġcorresponding Ġs - or Ġt - value Ġcontained Ġby Ġthat Ġcell . ĊĠĠĠĠ Ġ* ĠThe Ġargument Ġmust Ġbe Ġin Ġthe Ġrange Ġ[ 0 .. 2 ** 3 0 ], Ġi . e . Ġup Ġto Ġone Ġposition Ġbeyond Ġthe Ġnormal Ġrange Ġof Ġvalid Ġleaf ĊĠĠĠĠ Ġ* Ġcell Ġindices . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġi Ġa Ġi - Ġor Ġj - index Ġof Ġa Ġleaf Ġcell ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġminim un Ġs - Ġor Ġt - value Ġcontained Ġby Ġthe Ġcell . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġij To St Min ( i : ĠInt ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire Argument Ġ{ Ġi Ġin Ġ 0 .. k Limit IJ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġ( 1 . 0 Ġ/ Ġk Limit IJ ) Ġ* Ġi ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGet Ġthe Ġi - Ġor Ġj - index Ġof Ġthe Ġleaf Ġcell Ġcontaining Ġthe Ġgiven Ġs - Ġor Ġt - value . ĊĠĠĠĠ Ġ* ĠIf Ġthe Ġargument Ġis Ġoutside Ġthe Ġrange Ġsp anned Ġby Ġvalid Ġleaf Ġcell Ġindices , Ġreturn Ġthe Ġindex Ġof Ġthe Ġclosest Ġvalid ĊĠĠĠĠ Ġ* Ġleaf Ġcell Ġ( i . e ., Ġreturn Ġvalues Ġare Ġclamp ed Ġto Ġthe Ġrange Ġof Ġvalid Ġleaf Ġcell Ġindices ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġs Ġa Ġs - Ġor Ġt - value ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġcell Ġindex . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġst To Ij ( s : ĠDouble ): ĠInt Ġ= Ġmax ( 0 , Ġmin ( k Limit IJ Ġ- Ġ 1 , Ġround ( k Limit IJ Ġ* Ġs Ġ- Ġ 0 . 5 ). toInt ())) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġan Ġsi - Ġor Ġti - value Ġto Ġthe Ġcorresponding Ġs - Ġor Ġt - value . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġsi Ġa Ġsi - Ġor Ġti - value ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġs - Ġor Ġt - Ġvalue . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsi Ti To St ( si : ĠUInt ): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire Argument Ġ{ Ġsi Ġ<= Ġk Max Si Ti Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġ( 1 . 0 Ġ/ Ġk Max Si Ti . toDouble ()) Ġ* Ġsi . toDouble () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGet Ġthe Ġsi - Ġor Ġti - coordinate Ġthat Ġis Ġnearest Ġto Ġthe Ġgiven Ġs - Ġor Ġt - value . ĊĠĠĠĠ Ġ* ĠThe Ġresult Ġmay Ġbe Ġoutside Ġthe Ġrange Ġof Ġvalid Ġ( si , ti )- values . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġs Ġa Ġs - Ġor Ġt - value ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġsi - Ġor Ġti - Ġvalue . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġst To Si Ti ( s : ĠDouble ): ĠUInt Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġk Max Si Ti Ġ== Ġ 2 ^ 3 1 , Ġso Ġthe Ġresult Ġdoesn 't Ġfit Ġin Ġan Ġint 3 2 Ġwhen Ġs Ġ== Ġ 1 . ĊĠĠĠĠĠĠĠ Ġreturn Ġround ( s Ġ* Ġk Max Si Ti . toDouble ()). to UInt () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġ( face , Ġu , Ġv ) Ġcoordinates Ġto Ġa Ġdirection Ġvector Ġ( not Ġnecessarily Ġunit Ġlength ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface UV Ġa Ġ( face , Ġu , Ġv ) Ġcoordinates ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġsphere Ġpoint ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface Uv To X yz ( face UV : ĠFace UV ): ĠS 2 Point Ġ= Ġface Uv To X yz ( face UV . face , Ġface UV . u , Ġface UV . v ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġ( face , Ġu , Ġv ) Ġcoordinates Ġto Ġa Ġdirection Ġvector Ġ( not Ġnecessarily Ġunit Ġlength ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber ĊĠĠĠĠ Ġ* Ġ@ param Ġuv ĠThe Ġ( u , v ) Ġcoordinates ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġsphere Ġpoint ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface Uv To X yz ( face : ĠInt , Ġuv : ĠR 2 Point ): ĠS 2 Point Ġ= Ġface Uv To X yz ( face , Ġuv [ 0 ], Ġuv [ 1 ]) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġ( face , Ġu , Ġv ) Ġcoordinates Ġto Ġa Ġdirection Ġvector Ġ( not Ġnecessarily Ġunit Ġlength ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber ĊĠĠĠĠ Ġ* Ġ@ param Ġu Ġthe Ġu Ġcoordinate ĊĠĠĠĠ Ġ* Ġ@ param Ġv Ġthe Ġv Ġcoordinate ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġsphere Ġpoint ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface Uv To X yz ( face : ĠInt , Ġu : ĠDouble , Ġv : ĠDouble ): ĠS 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( face ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 Ġ-> ĠS 2 Point ( 1 . 0 , Ġu , Ġv ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 1 Ġ-> ĠS 2 Point (- u , Ġ 1 . 0 , Ġv ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ-> ĠS 2 Point (- u , Ġ- v , Ġ 1 . 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 3 Ġ-> ĠS 2 Point (- 1 . 0 , Ġ- v , Ġ- u ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 4 Ġ-> ĠS 2 Point ( v , Ġ- 1 . 0 , Ġ- u ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> ĠS 2 Point ( v , Ġu , Ġ- 1 . 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠIf Ġthe Ġdot Ġproduct Ġof Ġp Ġwith Ġthe Ġgiven Ġface Ġnormal Ġis Ġpositive , Ġreturn Ġthe Ġcorresponding Ġu Ġand Ġv Ġvalues ĊĠĠĠĠ Ġ* Ġ( which Ġmay Ġlie Ġoutside Ġthe Ġrange Ġ[- 1 , 1 ]). Ġ ĠOtherwise Ġreturn Ġnull . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber . ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠThe Ġdirection Ġvector Ġto Ġconvert . ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġ( u , v ) Ġcoordinate Ġof Ġthe Ġvector Ġif Ġthe Ġdot Ġproduct Ġof Ġp Ġwith Ġthe Ġgiven Ġface Ġnormal Ġis Ġpositive Ġelse ĊĠĠĠĠ Ġ* Ġnull . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface X yz to Uv ( face : ĠInt , Ġp : ĠS 2 Point ): ĠR 2 Point ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( face Ġ< Ġ 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p [ face ] Ġ<= Ġ 0 ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p [ face Ġ- Ġ 3 ] Ġ>= Ġ 0 ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġvalid Face X yz To Uv ( face , Ġp ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGiven Ġa Ġ* valid * Ġface Ġfor Ġthe Ġgiven Ġpoint Ġp Ġ( mean ing Ġthat Ġdot Ġproduct Ġof Ġp Ġwith Ġthe Ġface Ġnormal Ġis Ġpositive ), ĊĠĠĠĠ Ġ* Ġset Ġthe Ġcorresponding Ġu Ġand Ġv Ġvalues Ġ( which Ġmay Ġlie Ġoutside Ġthe Ġrange Ġ[- 1 , 1 ]). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠA Ġpoint ĊĠĠĠĠ Ġ* Ġ@ param Ġuv ĠThe Ġ( u , v ) Ġcoordinate Ġpoint Ġto Ġupdate . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġvalid Face X yz To Uv ( face : ĠInt , Ġp : ĠS 2 Point , Ġuv : ĠR 2 Point ) Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire Argument Ġ{ Ġp . dot Prod ( norm ( face )) Ġ> Ġ 0 Ġ} ĊĠĠĠĠĠĠĠ Ġwhen Ġ( face ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġuv [ 0 ] Ġ= Ġp [ 1 ] Ġ/ Ġp [ 0 ]; Ġuv [ 1 ] Ġ= Ġp [ 2 ] Ġ/ Ġp [ 0 ]; Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠ 1 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġuv [ 0 ] Ġ= Ġ- p [ 0 ] Ġ/ Ġp [ 1 ]; Ġuv [ 1 ] Ġ= Ġp [ 2 ] Ġ/ Ġp [ 1 ]; Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġuv [ 0 ] Ġ= Ġ- p [ 0 ] Ġ/ Ġp [ 2 ]; Ġuv [ 1 ] Ġ= Ġ- p [ 1 ] Ġ/ Ġp [ 2 ]; Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠ 3 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġuv [ 0 ] Ġ= Ġp [ 2 ] Ġ/ Ġp [ 0 ]; Ġuv [ 1 ] Ġ= Ġp [ 1 ] Ġ/ Ġp [ 0 ]; Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠ 4 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġuv [ 0 ] Ġ= Ġp [ 2 ] Ġ/ Ġp [ 1 ]; Ġuv [ 1 ] Ġ= Ġ- p [ 0 ] Ġ/ Ġp [ 1 ]; Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġuv [ 0 ] Ġ= Ġ- p [ 1 ] Ġ/ Ġp [ 2 ]; Ġuv [ 1 ] Ġ= Ġ- p [ 0 ] Ġ/ Ġp [ 2 ]; Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGiven Ġa Ġ* valid * Ġface Ġfor Ġthe Ġgiven Ġpoint Ġp Ġ( mean ing Ġthat Ġdot Ġproduct Ġof Ġp Ġwith Ġthe Ġface Ġnormal Ġis Ġpositive ), ĊĠĠĠĠ Ġ* Ġreturn Ġthe Ġcorresponding Ġu Ġand Ġv Ġvalues Ġ( which Ġmay Ġlie Ġoutside Ġthe Ġrange Ġ[- 1 , 1 ]). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠA Ġpoint ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġ( u , v ) Ġcoordinate Ġpoint Ġto Ġupdate . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġvalid Face X yz To Uv ( face : ĠInt , Ġp : ĠS 2 Point ): ĠR 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġuv Ġ= ĠR 2 Point () ĊĠĠĠĠĠĠĠ Ġvalid Face X yz To Uv ( face , Ġp , Ġuv ) ĊĠĠĠĠĠĠĠ Ġreturn Ġuv ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠTransform Ġthe Ġgiven Ġpoint ĠP Ġto Ġthe Ġ( u , v , w ) Ġcoordinate Ġframe Ġof Ġthe Ġgiven Ġface ĊĠĠĠĠ Ġ* Ġ( where Ġthe Ġw - axis Ġrepresents Ġthe Ġface Ġnormal ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠThe Ġpoint Ġto Ġtransform . ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġ( u , v , w ) Ġcoordinate Ġframe ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface X yz ToU vw ( face : ĠInt , Ġp : ĠS 2 Point ): ĠS 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġresult Ġcoordinates Ġare Ġsimply Ġthe Ġdot Ġproducts Ġof ĠP Ġwith Ġthe Ġ( u , v , w ) ĊĠĠĠĠĠĠĠ Ġ// Ġaxes Ġfor Ġthe Ġgiven Ġface Ġ( see Ġk Face UV W Axes ). ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( face ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 Ġ-> ĠS 2 Point ( p . y , Ġp . z , Ġp . x ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 1 Ġ-> ĠS 2 Point (- p . x , Ġp . z , Ġp . y ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ-> ĠS 2 Point (- p . x , Ġ- p . y , Ġp . z ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 3 Ġ-> ĠS 2 Point (- p . z , Ġ- p . y , Ġ- p . x ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 4 Ġ-> ĠS 2 Point (- p . z , Ġp . x , Ġ- p . y ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> ĠS 2 Point ( p . y , Ġp . x , Ġ- p . z ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGet Ġthe Ġface Ġcontaining Ġthe Ġgiven Ġdirection Ġvector . ĊĠĠĠĠ Ġ* Ġ( For Ġpoints Ġon Ġthe Ġboundary Ġbetween Ġfaces , Ġthe Ġresult Ġis Ġarbitrary Ġbut Ġrepeat able .) ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠA Ġpoint . ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġface Ġcontaining Ġthe Ġgiven Ġdirection Ġvector . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface ( p : ĠS 2 Point ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġface Ġ= Ġp . largest Abs Component () ĊĠĠĠĠĠĠĠ Ġif Ġ( p [ face ] Ġ< Ġ 0 ) Ġface Ġ+= Ġ 3 ĊĠĠĠĠĠĠĠ Ġreturn Ġface ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġa Ġdirection Ġvector Ġ( not Ġnecessarily Ġunit Ġlength ) Ġto Ġ( face , Ġu , Ġv ) Ġcoordinates . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠA Ġpoint ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġ( face , Ġu , Ġv ) Ġcoordinates . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġxyz To Face Uv ( p : ĠS 2 Point ): ĠFace UV Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġface Ġ= Ġface ( p ) ĊĠĠĠĠĠĠĠ Ġval Ġuv Ġ= Ġvalid Face X yz To Uv ( face , Ġp ) ĊĠĠĠĠĠĠĠ Ġreturn ĠFace UV ( face Ġ= Ġface , Ġu Ġ= Ġuv . x , Ġv Ġ= Ġuv . y ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġa Ġdirection Ġvector Ġ( not Ġnecessarily Ġunit Ġlength ) Ġto Ġ( face , Ġsi , Ġti ) Ġcoordinates Ġand , Ġif Ġp Ġis Ġexactly ĊĠĠĠĠ Ġ* Ġequal Ġto Ġthe Ġcenter Ġof Ġa Ġcell , Ġreturn Ġthe Ġlevel Ġof Ġthis Ġcell Ġ(- 1 Ġotherwise ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠA Ġpoint ĊĠĠĠĠ Ġ* Ġ@ return Ġcell Ġlevel Ġand Ġ( face , Ġsi , Ġti ) Ġcoordinates Ġpair . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġxyz To Face Si Ti ( p : ĠS 2 Point ): ĠPair < Int , ĠFace Si Ti > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġ( face , Ġu , Ġv ) Ġ= Ġxyz To Face Uv ( p ) ĊĠĠĠĠĠĠĠ Ġval Ġsi Ġ= Ġst To Si Ti ( projection . uv To St ( u )) ĊĠĠĠĠĠĠĠ Ġval Ġti Ġ= Ġst To Si Ti ( projection . uv To St ( v )) ĊĠĠĠĠĠĠĠ Ġval Ġface Si Ti Ġ= ĠFace Si Ti ( face , Ġsi , Ġti ) ĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġthe Ġlevels Ġcorresponding Ġto Ġsi , ti Ġare Ġnot Ġequal , Ġthen Ġp Ġis Ġnot Ġa Ġcell ĊĠĠĠĠĠĠĠ Ġ// Ġcenter . Ġ ĠThe Ġsi , ti Ġvalues Ġ 0 Ġand Ġk Max Si Ti Ġneed Ġto Ġbe Ġhandled Ġspec ially ĊĠĠĠĠĠĠĠ Ġ// Ġbecause Ġthey Ġdo Ġnot Ġcorrespond Ġto Ġcell Ġcenters Ġat Ġany Ġvalid Ġlevel ; Ġthey ĊĠĠĠĠĠĠĠ Ġ// Ġare Ġmapped Ġto Ġlevel Ġ- 1 Ġby Ġthe Ġcode Ġbelow . ĊĠĠĠĠĠĠĠ Ġval Ġlevel Ġ= Ġk Max Cell Level Ġ- Ġ( si Ġor Ġk Max Si Ti ). count Trailing Zero Bits () ĊĠĠĠĠĠĠĠ Ġif Ġ( level Ġ< Ġ 0 Ġ|| Ġlevel Ġ!= Ġk Max Cell Level Ġ- Ġ( ti Ġor Ġk Max Si Ti ). count Trailing Zero Bits ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ- 1 Ġto Ġface Si Ti ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġcheck State Ġ{ Ġlevel Ġ<= Ġk Max Cell Level Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠIn Ġinfinite Ġprecision , Ġthis Ġtest Ġcould Ġbe Ġchanged Ġto ĠST Ġ== ĠSi Ti . ĠHowever , ĊĠĠĠĠĠĠĠ Ġ// Ġdue Ġto Ġrounding Ġerrors , ĠUV to ST ( XYZ to Face UV ( Face UV to XYZ ( ST to UV (... )))) Ġis ĊĠĠĠĠĠĠĠ Ġ// Ġnot Ġide mpot ent . ĠOn Ġthe Ġother Ġhand , Ġcenter _ raw Ġis Ġcomputed Ġexactly Ġthe Ġsame ĊĠĠĠĠĠĠĠ Ġ// Ġway Ġp Ġwas Ġoriginally Ġcomputed Ġ( if Ġit Ġis Ġindeed Ġthe Ġcenter Ġof Ġan ĠS 2 Cell ): ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġcomparison Ġcan Ġbe Ġexact . ĊĠĠĠĠĠĠĠ Ġval Ġcenter Ġ= Ġface Si Ti To X yz ( face Si Ti ). normalize () ĊĠĠĠĠĠĠĠ Ġreturn Ġ( if Ġ( p Ġ== Ġcenter ) Ġlevel Ġelse Ġ- 1 ) Ġto Ġface Si Ti ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġ( face , Ġsi , Ġti ) Ġcoordinates Ġto Ġa Ġdirection Ġvector Ġ( not Ġnecessarily Ġunit Ġlength ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface Si Ti Ġ( face , Ġsi , Ġti ) Ġcoordinates ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġdirection Ġvector . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface Si Ti To X yz ( face Si Ti : ĠFace Si Ti ): ĠS 2 Point Ġ= Ġface Si Ti To X yz ( face Si Ti . face , Ġface Si Ti . si , Ġface Si Ti . ti ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġ( face , Ġsi , Ġti ) Ġcoordinates Ġto Ġa Ġdirection Ġvector Ġ( not Ġnecessarily Ġunit Ġlength ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber ĊĠĠĠĠ Ġ* Ġ@ param Ġsi ĠThe Ġsi Ġcoordinate . ĊĠĠĠĠ Ġ* Ġ@ param Ġti ĠThe Ġti Ġcoordinate . ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġcorresponding Ġdirection Ġvector . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġface Si Ti To X yz ( face : ĠInt , Ġsi : ĠUInt , Ġti : ĠUInt ): ĠS 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġu Ġ= Ġprojection . st To Uv ( si Ti To St ( si )) ĊĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġprojection . st To Uv ( si Ti To St ( ti )) ĊĠĠĠĠĠĠĠ Ġreturn Ġface Uv To X yz ( face , Ġu , Ġv ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGet Ġthe Ġright - h anded Ġnormal Ġ( not Ġnecessarily Ġunit Ġlength ) Ġfor Ġan Ġedge Ġin Ġthe Ġdirection Ġof Ġthe Ġpositive Ġv - axis ĊĠĠĠĠ Ġ* Ġat Ġthe Ġgiven Ġu - value Ġon Ġthe Ġgiven Ġface . Ġ Ġ( This Ġvector Ġis Ġper pend icular Ġto Ġthe Ġplane Ġthrough Ġthe Ġsphere Ġorigin ĊĠĠĠĠ Ġ* Ġthat Ġcontains Ġthe Ġgiven Ġedge .) ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber . ĊĠĠĠĠ Ġ* Ġ@ param Ġu Ġu Ġcoordinate . ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġright - h anded Ġnormal Ġof Ġthe Ġedge . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġget UN orm ( face : ĠInt , Ġu : ĠDouble ): ĠS 2 Point Ġ= Ġwhen Ġ( face ) Ġ{ ĊĠĠĠĠĠĠĠĠ 0 Ġ-> ĠS 2 Point ( u , Ġ- 1 . 0 , Ġ 0 . 0 ) ĊĠĠĠĠĠĠĠĠ 1 Ġ-> ĠS 2 Point ( 1 . 0 , Ġu , Ġ 0 . 0 ) ĊĠĠĠĠĠĠĠĠ 2 Ġ-> ĠS 2 Point ( 1 . 0 , Ġ 0 . 0 , Ġu ) ĊĠĠĠĠĠĠĠĠ 3 Ġ-> ĠS 2 Point (- u , Ġ 0 . 0 , Ġ 1 . 0 ) ĊĠĠĠĠĠĠĠĠ 4 Ġ-> ĠS 2 Point ( 0 . 0 , Ġ- u , Ġ 1 . 0 ) ĊĠĠĠĠĠĠĠ Ġelse Ġ-> ĠS 2 Point ( 0 . 0 , Ġ- 1 . 0 , Ġ- u ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠReturn Ġthe Ġright - h anded Ġnormal Ġ( not Ġnecessarily Ġunit Ġlength ) Ġfor Ġan ĊĠĠĠ Ġ// Ġedge Ġin Ġthe Ġdirection Ġof Ġthe Ġpositive Ġu - axis Ġat Ġthe Ġgiven Ġv - value Ġon ĊĠĠĠ Ġ// Ġthe Ġgiven Ġface . ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGet Ġthe Ġright - h anded Ġnormal Ġ( not Ġnecessarily Ġunit Ġlength ) Ġfor Ġan Ġedge Ġin Ġthe Ġdirection Ġof Ġthe Ġpositive Ġu - axis ĊĠĠĠĠ Ġ* Ġat Ġthe Ġgiven Ġv - value Ġon Ġthe Ġgiven Ġface . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber . ĊĠĠĠĠ Ġ* Ġ@ param Ġv Ġv Ġcoordinate . ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġright - h anded Ġnormal Ġof Ġthe Ġedge . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġget V Norm ( face : ĠInt , Ġv : ĠDouble ): ĠS 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( face ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 Ġ-> ĠS 2 Point (- v , Ġ 0 . 0 , Ġ 1 . 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 1 Ġ-> ĠS 2 Point ( 0 . 0 , Ġ- v , Ġ 1 . 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ-> ĠS 2 Point ( 0 . 0 , Ġ- 1 . 0 , Ġ- v ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 3 Ġ-> ĠS 2 Point ( v , Ġ- 1 . 0 , Ġ 0 . 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 4 Ġ-> ĠS 2 Point ( 1 . 0 , Ġv , Ġ 0 . 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> ĠS 2 Point ( 1 . 0 , Ġ 0 . 0 , Ġv ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠReturn Ġthe Ġunit - length Ġnormal , Ġu - axis , Ġor Ġv - axis Ġfor Ġthe Ġgiven Ġface . ĊĠĠĠ Ġfun Ġnorm ( face : ĠInt ): ĠS 2 Point Ġ= Ġu vw Axis ( face , Ġ 2 ) ĊĊĠĠĠ Ġfun Ġu Axis ( face : ĠInt ): ĠS 2 Point Ġ= Ġu vw Axis ( face , Ġ 0 ) ĊĊĠĠĠ Ġfun Ġv Axis ( face : ĠInt ): ĠS 2 Point Ġ= Ġu vw Axis ( face , Ġ 1 ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGet Ġthe Ġgiven Ġaxis Ġof Ġthe Ġgiven Ġface Ġ( u = 0 , Ġv = 1 , Ġw = 2 ). ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber . ĊĠĠĠĠ Ġ* Ġ@ param Ġaxis ĠThe Ġaxis Ġ( u = 0 , Ġv = 1 , Ġw = 2 ) ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġu vw Ġaxis . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġu vw Axis ( face : ĠInt , Ġaxis : ĠInt ): ĠS 2 Point Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġk Face UV W Axes [ face ][ axis ] ĊĠĠĠĠĠĠĠ Ġreturn ĠS 2 Point ( p [ 0 ], Ġp [ 1 ], Ġp [ 2 ]) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠWith Ġrespect Ġto Ġthe Ġ( u , v , w ) Ġcoordinate Ġsystem Ġof Ġa Ġgiven Ġface , Ġreturn Ġthe Ġface Ġthat Ġlies Ġin Ġthe Ġgiven ĊĠĠĠĠ Ġ* Ġdirection Ġ( negative = 0 , Ġpositive = 1 ) Ġof Ġthe Ġgiven Ġaxis Ġ( u = 0 , Ġv = 1 , Ġw = 2 ). Ġ ĠFor Ġexample , Ġget UV W Face ( 4 , Ġ 0 , Ġ 1 ) ĊĠĠĠĠ Ġ* Ġreturns Ġthe Ġface Ġthat Ġis Ġadjacent Ġto Ġface Ġ 4 Ġin Ġthe Ġpositive Ġu - axis Ġdirection . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġface ĠThe Ġface Ġnumber . ĊĠĠĠĠ Ġ* Ġ@ param Ġaxis ĠThe Ġaxis Ġ( u = 0 , Ġv = 1 , Ġw = 2 ) ĊĠĠĠĠ Ġ* Ġ@ param Ġdirection ĠThe Ġdirection Ġ( negative = 0 , Ġpositive = 1 ) ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġface . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġu vw Face ( face : ĠInt , Ġaxis : ĠInt , Ġdirection : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire Argument Ġ{ Ġface Ġin Ġ 0 .. 5 Ġ} ĊĠĠĠĠĠĠĠ Ġrequire Argument Ġ{ Ġaxis Ġin Ġ 0 .. 2 Ġ} ĊĠĠĠĠĠĠĠ Ġrequire Argument Ġ{ Ġdirection Ġin Ġ 0 .. 1 Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġk Face UV WF aces [ face ][ axis ][ direction ] ĊĠĠĠ Ġ} Ċ Ċ } Ċ Ċ data Ġclass ĠFace IJ ( val Ġface : ĠInt , Ġval Ġi : ĠInt , Ġval Ġj : ĠInt , Ġval Ġorientation : ĠInt ?) Ċ data Ġclass ĠFace Si Ti ( val Ġface : ĠInt , Ġval Ġsi : ĠUInt , Ġval Ġti : ĠUInt ) Ċ data Ġclass ĠFace UV ( val Ġface : ĠInt , Ġval Ġu : ĠDouble , Ġval Ġv : ĠDouble ) Ġ{ ĊĠĠĠ Ġfun Ġget UV (): ĠR 2 Point Ġ= ĠR 2 Point ( u , Ġv ) Ċ } ĊĊ