1 
`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  face­base 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  non­simpl 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   Three­Dimensional
`
`  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  last­mentione 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  three­dimensiona l  worl d coordi ­
`nates,  an d  als o  o f  three­dimensiona 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 three­dimensiona 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  hidden­lin 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   Three­Dimensional
`
`  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  four­side 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 , 
`two­dimensiona 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 . 
`Direction­Magnitude  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   Three­Dimensional
`
`  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 , single­valued , 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  "well­behaved " 
`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   Three­Dimensional
`
`  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 twice­differentiabl 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 
`two­dimensiona 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  time­varyin 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 time­varyin 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 O­trt/r)   +   b mnism  (2irt/r)  
`/=i 
`
`(9.10 ) 
`
`Bm„{i) =  b mno +  X   c /ww co s (2TT­r/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  moving­harmonic­surfac
`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   two­dimensiona l  se t move d  alon g  som e  three­spac 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  two­dimensiona 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 two­dimensiona l se t aroun d 
`an axis . I n "three­dimensiona l  sweeps, " volume s ar e swept . I n a  "general " swee p 
`scheme,  th e two­dimensiona 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  Three­Dimensional
`
`  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 cross­sectio 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 
`cross­sectio 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  cross­sectiona 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 GC­axi 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   Three­Dimensional
`
`  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  v­Z,
` 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  three­dimensiona 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   Three­Dimensional
`
`  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  spline­base 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  three­dimensiona 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