`4, wm
`
`^m^
`
`Fig. 9. 1 A volum e an d th e face s o f a
`boundary representation .
`
`opinion (Fig . 9.2) . I n short , an y singl e definitio n o f fac e i s likel y t o b e inadequat e
`for som e importan t application .
`The availabilit y o f explici t representation s o f edges , faces , an d vertice s make s
`boundary representation s quit e usefu l i n compute r visio n an d graphics . Th e com
`putational advantage s o f polyhedra l surface s ar e s o grea t tha t the y ar e ofte n presse d
`into servic e a s approximat e representation s o f nonpolyhedr a (Fig . 9.3) .
`An influentia l syste m fo r usin g facebase d representation s fo r plana r po
`lyhedral object s i s th e "winge d edge " representatio n [Baumgar t 1972] . Include d i n
`the syste m i s a n edito r fo r creatin g comple x polyhedra l object s (suc h a s tha t o f Fig .
`9.3) interactively . Th e syste m use s rule s fo r constructio n base d o n th e theore m o f
`Euler tha t i f Fi s th e numbe r o f vertice s i n a polyhedron , i s th e numbe r o f edges ,
`and Fthe numbe r o f faces , the n V — E + F = 2 . I n fact , th e formul a ca n b e ex
`tended t o dea l wit h nonsimpl y connecte d bodies . Th e extende d relatio n i s
`V E + F = 2(2 ? — H) y wit h B bein g th e numbe r o f bodie s an d H bein g th e
`
`266
`
`Ch. 9 Representations of ThreeDimensional
`
` Structures
`
`Fig. 9. 2 Wha t ar e th e faces ?
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 280
`
`
`
`Fig. 9. 3 A polyhedra l approximatio n t o a portio n o f a canin e hear t a t systol e an d
`diastole. Bot h exterio r (coars e grid ) an d interio r surface s (fin e grid ) ar e shown .
`
`number o f holes , o r "handles, " eac h resultin g fro m a hol e throug h a bod y [Laka
`tos 1976] . Baumgart' s syste m use s thes e rule s t o overse e an d chec k certai n validit y
`conditions o n th e construction s mad e b y th e editor .
`The "winge d edge " polyhedro n representatio n achieve s man y desiderat a fo r
`boundary representation s i n a n elegan t way . Thi s representatio n i s presente d
`below t o giv e a flavor o f th e feature s tha t hav e bee n traditionall y foun d useful .
`Given a s primitive s th e vertices , edges , faces , an d polyhedr a themselves , an d
`given variou s relation s betwee n thes e primitives , on e i s naturall y think s o f a recor d
`and pointe r (relational ) structur e i n whic h th e pointer s captur e th e binar y relation s
`and th e record s represen t primitive s an d contai n dat a abou t thei r location s o r
`parameters.
`In th e winge d edg e representation , ther e ar e dat a structur e records , o r nodes ,
`which contai n fields holdin g dat a o r link s (pointers ) t o othe r nodes . A n exampl e
`using thi s structur e t o describ e a tetrahedron i s show n i n Fig . 9.4 . Ther e ar e fou r
`kinds o f nodes : vertices, edges , faces , an d bodies . T o allo w convenien t acces s t o
`these nodes , the y ar e arrange d i n a circula r doubl y linke d list . Th e bod y node s ar e
`actually th e head s o f circula r structure s fo r th e faces , edges , an d vertice s o f th e
`body. Eac h fac e point s t o on e o f it s perimete r edges , an d eac h verte x point s t o on e
`of th e edge s impingin g o n it . Eac h edg e nod e ha s link s t o th e face s o n eac h sid e o f
`it, an d th e vertice s a t eithe r end .
`Figure 9. 4 show s onl y th e lastmentione d link s associate d wit h eac h edg e
`node. Th e reade r ma y notic e th e similarit y o f thi s dat a structur e wit h th e dat a
`structure fo r regio n mergin g i n Sectio n 5.4 . The y ar e topologicall y equivalent .
`Each edg e als o ha s associate d fou r link s whic h giv e th e nam e "winge d edge " t o th e
`representation. Thes e link s specif y neighborin g edge s i n orde r aroun d th e tw o
`faces whic h ar e associate d wit h th e edge . Th e complet e lin k se t fo r a n edg e i s
`shown i n Fig . 9.5 , togethe r wit h th e lin k informatio n fo r bodies , vertices , an d
`faces. T o allo w unambiguou s traversa l aroun d faces , an d t o preserv e th e notio n o f
`
`Sec. 9.2 Surface Representations
`
`267
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 281
`
`
`
`Fig. 9. 4 A subse t o f edg e link s fo r a
`tetrahedron usin g th e "winge d edge "
`representation.
`
`interior an d exterio r o f a polyhedron , a preferentia l orderin g o f vertice s an d line s i s
`picked (counterclockwise , say , a s see n fro m outsid e th e polyhedron) .
`Data fields i n eac h verte x allo w storag e o f threedimensiona l worl d coordi
`nates, an d als o o f threedimensiona l perspectiv e coordinate s fo r display . Eac h
`node ha s fields specifyin g it s nod e type , hidde n lin e eliminatio n information , an d
`other genera l information . Face s hav e fields fo r surfac e norma l vecto r informa
`tion, surfac e reflectance , an d colo r characteristics . Bod y node s carr y link s t o relat e
`them t o a tre e structur e o f bodie s i n a scene , allowin g fo r hierarchica l arrangemen t
`of subbodie s int o comple x bodies . Thu s bod y nod e dat a describ e th e scen e struc
`ture; fac e nod e dat a describ e surfac e characteristics ; edg e nod e dat a giv e th e topo
`logical informatio n neede d t o relat e faces , edges , an d vertices ; an d verte x nod e
`data describ e th e threedimensiona l verte x location .
`This ric h an d redundan t structur e lend s itsel f t o efficien t calculatio n o f usefu l
`functions involvin g thes e bodies . Fo r instance , on e ca n easil y follo w pointer s t o
`extract th e lis t o f point s aroun d a face , face s aroun d a point, o r line s aroun d a face .
`Winged edge s ar e no t a universa l boundar y representatio n fo r polyhedra , bu t the y
`do giv e a n ide a o f th e component s t o a representatio n tha t ar e likel y t o b e useful .
`Such a representatio n ca n b e mad e efficien t fo r accessin g al l faces , edges , o r ver
`tices; fo r accessin g verte x o r edg e perimeters ; fo r polyhedro n building ; an d fo r
`splitting edge s an d face s (usefu l i n constructio n an d hiddenlin e pictur e produc
`tion, fo r instance) .
`
`9.2.2 Surface s Base d o n Spline s
`
`The natura l extensio n o f polyhedra l surface s i s t o allo w th e surface s t o b e curved .
`However, wit h a n arbitrar y numbe r o f edge s fo r th e surface , th e interpolatio n o f
`
`268
`
`Ch. 9 Representations of ThreeDimensional
`
` Structures
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 282
`
`
`
`Boundary Representatio n Nod e Accessin g Function s
`
`To ente r an d travers e Fac e rin g o f a body :
`NextFace, PreviousFace :
`Bod y o r Fac e » ■ Fac e
`
`To ente r an d travers e Edg e rin g o f a body :
`NextEdge, PreviousEdge : Bod y o r Edg e * ■ Edg e
`
`To ente r an d travers e Verte x rin g o f a body :
`NextVert, PreviousVert :
`Bod y o r Verte x * Verte x
`First Edg e o f a Face :
`FirstEdge: Fac e * Edg e
`FirstEdge o f a Vertex :
`FirstEdge: Verte x > Edg e
`Faces o f a n Edge :
`[se e diagra m i n (a) ]
`N(ext) Face , P(revious ) Face : Edg e > Face
`Vertices o f a n Edge :
`[se e diagra m i n (a) ]
`N(extVert, P(revious)Vert :
`Edg e ► Verte x
`Neighboring Win g Edge s o f a n Edge :
`[se e diagra m i n (a) ]
`NCW, NCCW : Edg e < • Edg e
`(NFac e Edg e Clockwise ,
`NFace Edg e Counterclockwise )
`(PFace Edg e Clockwise ,
`PFace Edg e Counterclockwis e
`
`PCW, PCCW : Edg e * Edg e
`
`(b)
`
`NCCW(£)
`
`PCW{£)
`
`5 .
`
`NFacelf)
`
`PFace(£)
`
`{ Edge
`e
`
`NVert(f)
`
`NCW(£)
`
`PCCW(£)
`
`(a)
`
`Fig. 9. 5
`
`(a ) Nod e accessin g functions , (b ) Semantic s o f winge d edg e functions .
`
`interior fac e point s become s impracticall y complex . Fo r tha t reason , th e numbe r o f
`edges fo r a curve d fac e i s usuall y restricte d t o thre e o r four .
`A genera l techniqu e fo r approximatin g surface s wit h fourside d surfac e
`patches i s tha t o f Coon s [Coon s 1974] . Coon s specifie s th e fou r side s o f th e patc h
`with polynomials . Thes e polynomial s ar e use d t o interpolat e interio r points .
`Although thi s i s appropriat e fo r synthesis , i t i s no t s o eas y t o us e fo r analysis . Thi s
`is becaus e o f th e difficult y o f registerin g th e patc h edge s wit h imag e data . A give n
`surface wil l admi t t o man y patc h decompositions .
`An attractiv e representatio n fo r patche s i s spline s (Fig . 9.6) . I n general ,
`twodimensiona l splin e interpolatio n i s complex : Fo r tw o parameter s wan d vinter
`polate wit h
`
`x(w, v ) = £ X VijBijiu, v )
`'
`J
`similar t o Eq . (8.4) . However , fo r certai n application s a furthe r simplificatio n ca n
`be made . I n a manne r analogou s t o (8.9 ) defin e a gri d o f kno t point s v y
`corresponding t o Xy an d relate d b y
`
`(9.1;
`
`(9.2)
`Xij MVij
`Now rathe r tha n interpolatin g i n tw o dimension s simultaneously , interpolat e i n
`one direction , sa y / , t o obtai n
`t 2
`xiJ(t)=[P
`
`(9.3 )
`
`t
`
`l][C][v ;_ U o,v,, 0,v / + U o (v / + 2,, 0] 7"
`
`for eac h valu e ofj. No w comput e v„(f ) b y solvin g
`
`Xij(t) = M\jj(t)
`
`Sec. 9.2 Surface Representations
`
`(9.4)
`
`269
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 283
`
`
`
`Fig. 9. 6 Usin g splin e curve s t o mode l
`the surfac e o f a n object : a portio n o f a
`human spina l colum n take n fro m CA T
`data.
`for eac h valu e o f t. Finally , interpolat e i n th e othe r directio n an d solve :
`s 2 s
`xiJ(s,t)=[s3
`l][C][r l l.jU),TuU),vl+ijU),v,+2jO)]
`This i s th e basi s fo r th e splin e filterin g algorith m discusse d i n Sectio n 3.2.3 .
`Some advantage s o f splin e surface s fo r visio n ar e th e following .
`1. Th e splin e representatio n i s economical : th e spac e curve s ar e represente d a s a
`sparse se t o f kno t point s fro m whic h th e underlyin g curve s ca n b e interpolated .
`I t i s eas y t o defin e spline s interactivel y b y givin g th e kno t points ; referenc e
`representations ma y b e buil t u p easily .
`I t i s ofte n usefu l t o searc h th e imag e i n a directio n perpendicula r t o th e mode l
`reference surface . Thi s directio n i s a simpl e functio n o f th e loca l kno t points .
`
`(9.5 )
`
`2.
`
`3.
`
`9.2.3 Surface s Tha t Ar e Function s o n th e Spher e
`
`Some surface s ca n b e expresse d a s function s o n th e "Gaussia n sphere. " (th e dis
`tance fro m th e origi n t o a poin t o n th e surfac e i s a functio n o f th e directio n o f th e
`point, o r o f it s longitud e an d latitud e i f i t wer e radiall y projecte d o n a spher e wit h
`the cente r a t th e origin. ) Thi s clas s o f surfaces , althoug h restricted , i s usefu l i n
`some applicatio n area s [Schud y an d Ballar d 1978 , 1979] . Thi s sectio n explore s
`briefly tw o scheme s fo r representatio n o f thes e surfaces . Th e first specifie s expli
`citly th e distanc e o f th e surfac e fro m th e origi n fo r a se t o f vecto r direction s fro m
`the origin . Th e secon d i s aki n t o Fourie r descriptors ; a n economicall y specifie d se t
`of coefficient s characterize s th e surfac e wit h greate r accurac y a s th e numbe r o f
`coefficients increases .
`DirectionMagnitude Sets
`One approximatio n t o a spherica l functio n i s t o specif y a numbe r o f three
`dimensional directio n vector s fro m th e origi n an d fo r eac h a magnitude . Thi s i s
`equivalent t o specifyin g a se t o f (0 , </>, p ) point s i n a spherica l coordinat e syste m
`(Appendix 1) . Thes e point s ar e o n th e surfac e t o b e represented ; connectin g the m
`yields a n approximation .
`
`2 7 0
`
`Ch. 9 Representations of ThreeDimensional
`
` Structures
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 284
`
`
`
`It i s ofte n convenien t t o represen t direction s a s point s o n th e uni t (Gaussian )
`sphere centere d o n th e origin . Th e point s ma y b e connecte d b y straigh t line s t o
`form a polyhedro n wit h triangular , hexagona l o r rhomboida l faces . Movin g th e
`points o n th e spher e ou t (o r in ) b y thei r associate d magnitud e distort s thi s po
`lyhedron, movin g it s vertice s radicall y ou t o r in .
`The spherica l functio n determine s th e distanc e o f fac e vertice s fro m th e ori
`gin. Resolutio n a t th e surfac e increase s wit h th e numbe r o f faces . A n approxi
`mately isotropi c distributio n o f direction s ove r th e surfac e ma y b e obtaine d b y
`placing th e fac e vertice s (directions ) i n accordanc e wit h "geodesi c dome"lik e cal
`culations whic h mak e th e face s approximatel y equilatera l triangle s [Clinto n 1971] .
`Although th e geodesi c tesselatio n o f th e sphere' s surfac e i s mor e comple x
`than a straightforwar d (latitud e an d longitude , say ) division , it s pleasan t propertie s
`of isotrop y an d displa y [Brow n 1979a ; 1979b ; Schud y an d Ballar d 1978 ] sometime s
`recommend it . Som e exampl e shape s indicatin g th e rang e o f representabl e sur
`faces ar e give n i n Fig . 9.7 . Method s fo r tesselatin g th e spher e ar e give n i n Appen
`dix 1 .
`Spherical Harmonic Surfaces
`In tw o dimensions , Fourie r coefficient s ca n giv e approximation s t o certai n
`curved boundarie s (Sectio n 8.3.4) . Analogousl y i n thre e dimensions , a se t o f
`orthogonal function s ma y b e use d t o expres s a close d boundar y a s a se t o f
`coefficients whe n th e boundar y i s a functio n o n th e sphere . On e suc h decomposi
`tion i s spherical harmonics. Lo w orde r coefficient s captur e gros s shap e characteris
`tics; highe r orde r coefficient s represen t surfac e shap e variation s o f highe r spatia l
`frequency. Th e functio n wit h m = 0 i s a sphere , th e thre e wit h m = 1 represen t
`translation abou t th e origin , th e five wit h m = 2 ar e simila r t o prolat e an d oblat e
`spheroids, an d s o forth , th e lobednes s o f th e surface s increasin g wit h m . A sampl e
`three dimensiona l shap e an d it s "description " i s show n i n Fig . 9.8 .
`Spherical harmonic s ar e analog s o n th e spher e o f Fourie r function s o n th e
`plane; lik e Fourie r functions , the y ar e smoot h an d continuou s t o ever y order . The y
`may b e parameterize d b y tw o numbers , m an d n; thu s the y ar e a doubl y infinit e se t
`of function s whic h ar e continuous , orthogonal , singlevalued , an d complet e o n th e
`
`t
`
`Sec. 9.2 Surface Representations
`
`271
`
`Fig. 9. 7 Sampl e surface s describe d b y
`some 32 0 triangula r facet s i n a geodesi c
`tesselation.
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 285
`
`
`
`Fig. 9. 8 A spherica l harmoni c functio n descriptio n o f a n ellipsoid . Coefficient s
`are displaye d o n th e righ t a s gre y level s i n th e matri x forma t
`
`"oo
`
`"01
`« , ,
`
`^l i
`w 0 2
`
`"12
`
`"21
`
`v I 2
`
`v 2 2
`
`sphere. I n combination , th e harmonic s ca n thu s produc e al l "wellbehaved "
`spherical functions .
`The spherica l harmoni c function s U mn (9,<f>) an d V mn (9,<f>) ar e define d i n
`polar coordinate s by :
`(9.6 )
`Um„(9,<f>) = cos (nO) sin" (<f>)P(m, n, cos(0) )
`(9.7 )
`Ymn(0> 0 ) = si n (n9) sin " (<p)P(m, n, cos(</>) )
`with i n = 0,1,2 , ... , M\ n — 0,1 , ... , m. Her e P(m, n, x) i s th e «t h derivativ e o f
`the /wt h Legendr e polynomia l a s a functio n o f x. T o represen t a n arbitrar y shape ,
`let th e radiu s R i n pola r coordinate s b e a linea r su m o f thes e spherica l harmonics :
`M
`m
`Z A m„ U mn(9, <f>) + B mn V mn(9, 0 )
`OT = 0 « = o
`Any continuou s surfac e o n th e spher e ma y b e represente d b y a se t o f thes e rea l
`constants; reasonabl e approximation s t o hear t volume s ar e obtaine d wit h m < 5
`[Schudy an d Ballar d 1979] .
`Figure 9. 9 show s a fe w simpl e combination s o f function s o f lo w value s o f
`(m, n). Th e sphere , o r (0,0 ) surface , i s adde d t o th e mor e comple x one s t o ensur e
`positive volume s an d drawabl e surfaces .
`Spherical harmonic s hav e th e followin g attractiv e properties .
`1. The y ar e orthogona l o n th e spher e unde r th e inne r product ;
`
`R(0,4>)=j:
`
`(9.8 )
`
`272
`
`Ch. 9 Representations of ThreeDimensional
`
` Structures
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 286
`
`
`
`Fig. 9. 9 Simpl e combination s o f functions .
`
`(«, v ) — J uv s'm<f> dO d<f>
`
`2. Th e function s ar e arrange d i n increasin g orde r o f spatia l complexity .
`3. Th e whol e se t i s complete ; an y twicedifferentiabl e functio n o n th e spher e ca n
`be approximate d arbitraril y closely .
`Spherical harmonic s ca n provid e compact , nonredundan t description s o f sur
`faces tha t ar e usefu l fo r analysi s o f shape , bu t ar e les s usefu l fo r synthesis . Th e
`principal disadvantage s ar e tha t th e primitiv e function s ar e no t necessaril y relate d
`to th e desire d final shap e i n a n intuitiv e way , an d changin g a singl e coefficien t
`affects th e entir e resultin g surface .
`An exampl e o f th e us e o f spherica l harmonic s a s a volum e representatio n i s
`the representatio n o f hear t volum e [Schud y an d Ballar d 1978 , 1979] . I n extractin g
`a volum e associate d wit h th e hear t fro m ultrasoun d data , a larg e mas s o f dat a i s in
`volved. Th e dat a i s originall y i n th e for m o f ech o measurement s take n i n a se t o f
`twodimensiona l plane s throug h th e heart . Th e tas k i s t o choos e a surfac e sur
`rounding th e hear t volum e o f interes t b y optimizatio n technique s tha t wil l fit thre e
`dimensional timevaryin g data . Th e optimizatio n involve d i s t o find th e bes t
`coefficients fo r th e spherica l harmonic s tha t defin e th e surface . Th e goodnes s o f fit
`of a surfac e i s measure d b y ho w wel l i t matche s th e edg e o f th e volum e a s i t appear s
`in th e dat a slices . T o exten d spherica l harmonic s t o timevaryin g periodi c data , le t
`the radiu s R i n pola r coordinate s b e a linea r su m o f thes e spherica l harmonics :
`M m
`H
`m=0 w= 0
`
`R(0, 4>,t) =
`
`A mnU)Umn{9, 0 ) + B mnU)Vmn{9, 0 )
`
`(9.9 )
`
`Sec. 9.2 Surface Representations
`
`273
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 287
`
`
`
`The function s A it) an d B it) ar e give n b y Fourie r tim e series :
`/
`Am„(t) = a mm + 2 a >w,icos Otrt/r) + b mnism (2irt/r)
`/=i
`
`(9.10 )
`
`Bm„{i) = b mno + X c /ww co s (2TTr/r ) + d„ wis\n iltrt/r)
`i=i
`where t\s time , th e a mnh b mnh c mnh an d d mni ar e arbitrar y rea l constants , an d T th e
`period. An y continuou s periodicall y movin g surfac e o n th e spher e ma y b e
`represented b y som e selectio n o f thes e rea l constants ; i n th e cardia c application ,
`reasonable approximation s t o th e tempora l behavio r ar e obtaine d wit h t ^ 3 . Fig
`ure 9.1 0 show s thre e stage s fro m a movingharmonicsurfac
`e representatio n o f th e
`heart i n earl y systole . Th e atria , a t th e top , contrac t an d pum p bloo d int o th e ven
`tricles below , afte r whic h ther e i s a ventricula r contraction .
`
`(9.11 )
`
`9.3 GENERALIZE D CYLINDE R REPRESENTATION S
`
`The volum e o f man y biologica l an d manufacture d object s i s naturall y describe d a s
`the "swep t volume " o f a twodimensiona l se t move d alon g som e threespac e
`curve. Figur e 9.1 1 show s a "translationa l sweep " wherei n a soli d i s represente d a s
`the volum e swep t b y a twodimensiona l se t whe n i t i s translate d alon g a line . A
`"rotational sweep " i s similarl y define d b y rotatin g th e twodimensiona l se t aroun d
`an axis . I n "threedimensiona l sweeps, " volume s ar e swept . I n a "general " swee p
`scheme, th e twodimensiona l se t o r volum e i s swep t alon g a n arbitrar y spac e
`curve, an d th e se t ma y var y parametricall y alon g th e curv e [Binfor d 1971 ; Sorok a
`and Bajcs y 1976 ; Sorok a 1979a ; 1979b ; Shan i 1980] . Genera l sweep s ar e quit e a po
`pular representatio n i n compute r vision , wher e the y g o b y th e nam e generalized
`cylinders (sometime s "generalize d cones") .
`
`Fig. 9.1 0 Thre e stage s fro m a movin g har
`monic surfac e (see text and color insert).
`
`274
`
`Ch. 9 Representations of ThreeDimensional
`
` Structures
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 288
`
`
`
`Sweep
`
`A,
`
`Fig. 9.1 1 A translationa l sweep .
`A generalize d cylinde r (GC ) i s a soli d whos e axi s i s a 3 D spac e curv e (Fig .
`9.12a). A t an y poin t o n th e axi s a close d cros s sectio n i s defined . A usua l restrictio n
`is tha t th e axi s b e norma l t o th e cros s section . Usuall y i t i s easies t t o think o f a n axi s
`space curv e an d a cros s sectio n poin t se t function , bot h parameterize d b y ar c
`length alon g th e axi s curve . Fo r an y solid , ther e ar e infinitel y man y pair s o f axi s
`and cros s sectio n function s tha t ca n defin e it .
`Generalized cylinder s presen t certai n technica l subtletie s i n thei r definition .
`For instance , ca n i t b e determine d whethe r an y tw o cros s section s intersect , a s the y
`would i f th e axi s o f a circula r cylinde r wer e sharpl y ben t (Fig . 9.12b ) ? I f th e soli d i s
`defined a s th e volum e swep t b y th e cros s section , ther e i s n o conceptua l o r compu
`tational problem . A proble m migh t occu r whe n computin g th e surfac e o f suc h a n
`object. I f th e surfac e i s expresse d i n term s o f th e axi s an d crosssectio n function s
`(as below) , th e domai n o f object s mus t b e limite d s o tha t th e boundar y formul a
`indeed give s onl y point s o n th e boundary .
`Generalized cylinder s ar e intuitiv e an d appealing . Le t u s gran t tha t "patho
`logical" case s ar e barred , s o tha t relativel y simpl e mathematic s i s adequat e fo r
`representing them . Ther e ar e stil l technica l decision s t o mak e abou t th e represen
`tation. Th e axi s curv e present s n o difficulties , bu t a usabl e representatio n fo r th e
`crosssectio n se t i s ofte n no t s o straightforward . Th e mai n proble m i s t o choos e a
`usable coordinat e syste m i n whic h t o expres s th e cros s section .
`
`9.3.1 Generalize d Cylinde r Coordinat e System s an d Propertie s
`
`Two mathematica l function s definin g axi s an d cros s sectio n fo r eac h poin t defin e a
`unique soli d wit h th e "sweeping " semantic s describe d above . I n a fixed Cartesia n
`coordinate syste m x, y, z , th e axi s ma y b e represente d parametricall y a s a functio n
`of ar c lengths :
`
`(9.12 )
`z(s))
`a(s) (x(s),y(s),
`It i s convenien t t o hav e a loca l coordinat e syste m define d wit h origi n a t eac h
`point o f a (s) . I t i s i n thi s coordinat e syste m tha t th e cros s sectio n i s defined . Thi s
`system ma y chang e i n orientatio n a s th e axi s wind s throug h space , o r i t ma y b e
`most natura l fo r i t no t t o b e tie d t o th e loca l behavio r o f th e axis . Fo r instance , im
`agine tyin g a kno t i n a soli d rubbe r ba r o f squar e cros s section . Th e cros s sectio n
`
`9.3 Generalized Cylinder Representations
`
`275
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 289
`
`
`
`(b )
`(a)
`(a ) A generalize d cylinde r an d som e crosssectiona l coordinat e sys
`Fig. 9.1 2
`tems. (b ) A possibl y "pathological " situation . Cros s section s ma y b e simpl y
`described a s circle s centere d o n th e axis , bu t the n thei r intersectio n make s volum e
`calculations (fo r instance ) les s straightforward .
`
`will sta y approximatel y a square , an d (thi s i s th e point ) wil l remai n approximatel y
`fixed i n a coordinat e syste m tha t twist s an d turn s throug h spac e wit h th e axi s o f th e
`bar. O n th e othe r hand , imagin e bol t threads . The y ca n b e describe d b y a singl e
`cross sectio n tha t stay s fixed i n a coordinat e syste m tha t rotate s a s i t move s alon g
`the straigh t axi s o f th e bolt . Ther e i s n o a prior i reaso n t o suppos e tha t suc h a usefu l
`local coordinat e syste m shoul d twis t alon g th e G C axis .
`A coordinat e syste m tha t mirror s th e loca l behavio r o f th e G C axi s spac e
`curve i s th e "Frene t frame, " define d a t eac h poin t o n th e G C axis . Thi s fram e pro
`vides muc h informatio n abou t th e GCaxi s behavior . Th e G C axi s poin t form s th e
`origin, an d th e thre e orthogona l direction s ar e give n b y th e vector s (£ , v, £) ,
`where
`
`f = uni t vecto r tangen t axi s
`v = uni t vecto r directio n o f cente r o f curvatur e o f axi s
`normal curv e
`£ = uni t vecto r directio n o f cente r o f torsio n o f axi s
`Consider th e curv e t o b e produce d b y a poin t movin g a t constan t spee d throug h
`space; th e distanc e th e poin t travel s i s th e paramete r o f th e spac e curv e [O'Neil l
`1966]. Sinc e £ i s o f constan t length , it s derivativ e measure s th e wa y th e G C axi s
`turns i n space . It s derivativ e £ 'i s orthogona l t o £ an d th e lengt h o f £ 'measure s th e
`curvature K o f th e axi s a t tha t point . Th e uni t vecto r i n th e directio n o f £ ' i s v.
`Where th e curvatur e i s no t zero , a binorma l vecto r £ orthogona l t o £ an d v i s
`defined. Thi s binorma l £ i s use d t o defin e th e torsio n r o f th e curve . Th e vector s £ ,
`*>, £ obe y Frenet' s formulae :
`
`v' = K£ + ri
`C = TV
`
`(9.13)
`
`276
`
`Ch. 9 Representations ol ThreeDimensional
`
` Structures
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 290
`
`
`
`where
`
`(9.14 )
`K = curvatur e = —v' • £ = v • f '
`(9.15 )
`T = torsio n i> ' • £ « v • £ '
`The Frene t fram e give s goo d informatio n abou t th e axi s o f th e GC , bu t i t ha s
`certain problems . First , i t i s no t wel l define d whe n th e curvatur e o f th e G C axi s i s
`zero. Second , i t ma y no t reflec t know n underlyin g physica l principle s tha t generat e
`the cros s section s (a s i n th e bol t threa d example) . A solution , adopte d i n [Agi n
`1972, Shan i 1980] , i s t o introduc e a n additiona l paramete r tha t allow s th e cros s
`section t o rotat e abou t th e loca l axi s b y a n arbitrar y amount . Wit h thi s additiona l
`degree o f freedo m comes a n additiona l problem : Ho w ar e successiv e cros s section s
`registered? Figur e 9.1 3 show s tw o solution s i n additio n t o th e Frene t fram e solu
`tion.
`
`The cros s sectiona l curv e i s usuall y define d t o b e i n th e v£ plane , norma l t o
`£, th e loca l G C axi s direction . Th e cros s sectio n ma y b e describe d a s a poin t se t i n
`this plane , usin g inequalitie s expresse d i n th e vZ,
` coordinat e system . Th e cros s
`section boundar y (outlin e curve ) ma y b e use d instead , parameterize d b y anothe r
`parameter r . Le t thi s curv e b e give n b y
`cross sectio n boundar y = (x(r, s), y(r, s))
`The dependenc e o n 5 reflect s th e fac t tha t th e cros s sectio n shap e ma y var y alon g
`the G C axis . Th e expressio n abov e i s i n worl d coordinates , bu t shoul d b e move d t o
`
`(a)
`
`(b )
`
`\
`
`(0
`
`(a ) Loca l coordinate s ar e th e Frene t frame . Point s A an d B mus t correspond .
`Fig. 9.1 3
`(b) Loca l coordinate s ar e determine d b y th e cros s sectiona l shape , (c ) Loca l coordinate s ar e
`determined b y a heuristi c transformatio n fro m worl d coordinates .
`
`Sec. 9.3 Generalized Cylinder Representations
`
`277
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 291
`
`
`
`the loca l coordinate s o n th e G C axis . A transformatio n o f coordinate s allow s th e
`GC boundar y t o b e expresse d (i f th e G C i s wel l behaved ) a s
`(9.16)
`B(r, s) = a(s ) + x(r, s)v(s) + y(r, s) £ (s )
`One o f th e advantage s o f th e generalize d cylinde r representatio n i s tha t i t al
`lows man y parameter s o f th e soli d t o b e easil y calculated .
`•
`I n matchin g th e G C t o imag e dat a i t i s ofte n necessar y t o searc h perpendicula r
`
`to a cros s section . Thi s directio n i s give n fro m x(r, s), y{r, s) b y {{dy/ds)v, {dx/ds)0
`
`• Th e are a o f a cros s sectio n ma y b e calculate d fro m Eq . (8.16) .
`• Th e volum e o f a G C i s give n b y th e integra l of : th e are a a s a functio n o f th e axi s
`parameter multiple d b y th e incrementa l pat h lengt h o f th e G C axis , i.e. ,
`
`volume = J area(s ) ds
`
`9.3.2 Extractin g Generalize d Cylinder s
`
`Early wor k i n biologica l for m analysi s provide s a n exampl e o f th e proces s o f fittin g
`a G C t o rea l dat a an d producin g a descriptio n [Agi n 1972] . On e o f th e goal s o f thi s
`work wa s t o infe r th e stic k figure skeleto n o f biologica l form s fo r us e i n matchin g
`models als o represente d a s skeletons . I n Fig . 9.1 4 th e proces s o f inferrin g th e axi s
`from th e origina l strip e threedimensiona l dat a i s shown ; th e proces s iterate s to
`ward a satisfactor y fit, usin g onl y circula r cros s section s ( a commo n constrain t wit h
`"generalized" cylinders) . Figur e 9.1 5 show s th e dat a an d th e analysi s o f a comple x
`
`Fig. 9.1 4 Stage s i n extractin g a
`generalized cylinde r descriptio n fo r a
`circular cone , (a ) Fron t view , (b ) Initia l
`axis estimate , (c ) Preliminar y cente r an d
`axis estimate , (d ) Con e wit h smoothe d
`radius function , (e ) Complete d analysis .
`
`278
`
`Ch. 9 Representations of ThreeDimensional
`
` Structures
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 292
`
`
`
`(a)
`
`(b)
`
`Fig. 9.1 5
`
`(a ) T V imag e o f a doll , (b ) Complete d analysi s o f doll .
`
`biological form . I n rea l data , complexl y interrelate d GC s ar e har d t o decompos e
`into satisfactor y subparts . Withou t that , th e abilit y t o for m a satisfactor y articulate d
`skeleton i s severel y restricted .
`In late r work , GC s wit h splinebase d axe s an d cros s section s wer e use d t o
`model organ s o f th e huma n abdome n [Shan i 1980] . Figur e 9.1 6 show s a renditio n
`of a G C fit t o a huma n kidney .
`
`9.3.3 A Discret e Volumetri c Versio n o f th e Skeleto n
`
`An approximat e volum e representatio n tha t ca n b e quit e usefu l i s base d o n a n arti
`culated wir e fram e skeleto n alon g whic h sphere s (no t cros s sections ) ar e placed .
`
`Fig. 9.1 6 Generalize d cylinde r
`representation o f tw o kidney s an d a
`spinal column . Thi s coarse , nomina l
`model i s refine d durin g examinatio n o f
`CAT dat a (se e Fig . 9.6) .
`
`Sec. 9.3 Generalized Cylinder Representations
`
`279
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 293
`
`
`
`This representatio n ha s som e o f th e flavo r o f a n approximat e swee p representa
`tion. A n exampl e o f th e us e o f suc h a representatio n an d a figur e ar e give n i n Sec
`tion 7.3.4 . Thi s representatio n wa s originall y conceive d fo r graphic s application s
`(the sphere s loo k th e sam e fro m an y viewpoint ) [Badle r an d Bajcs y 1978] . Colli
`sion detectio n i s easy , an d threedimensiona l object s ca n b e decompose d int o
`spheres automaticall y [O'Rourk e an d Badle r 1979] . Fro m th e spheres , th e skele
`ton ma y b e derived , an d s o ma y th e surfac e o f th e solid . Thi s representatio n i s
`especially ap t fo r man y compute r visio n applicatio