ÿþ<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv=Content-Type content="text/html; charset=unicode"> <meta name=ProgId content=Word.Document> <meta name=Generator content="Microsoft Word 12"> <meta name=Originator content="Microsoft Word 12"> <link rel=File-List href="gSaP_files/filelist.xml"> <link rel=Edit-Time-Data href="gSaP_files/editdata.mso"> <!--[if !mso]> <style> v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} </style> <![endif]--> <title> gSaP </title> <!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>liufu</o:Author> <o:Template>Normal</o:Template> <o:LastAuthor>liufu</o:LastAuthor> <o:Revision>45</o:Revision> <o:TotalTime>114</o:TotalTime> <o:Created>2010-09-06T04:50:00Z</o:Created> <o:LastSaved>2010-09-06T08:48:00Z</o:LastSaved> <o:Pages>3</o:Pages> <o:Words>751</o:Words> <o:Characters>4287</o:Characters> <o:Lines>35</o:Lines> <o:Paragraphs>10</o:Paragraphs> <o:CharactersWithSpaces>5028</o:CharactersWithSpaces> <o:Version>12.00</o:Version> </o:DocumentProperties> </xml><![endif]--> <link rel=dataStoreItem href="gSaP_files/item0020.xml" target="gSaP_files/props0021.xml"> <link rel=themeData href="gSaP_files/themedata.thmx"> <link rel=colorSchemeMapping href="gSaP_files/colorschememapping.xml"> <!--[if gte mso 9]><xml> <w:WordDocument> <w:TrackMoves>false</w:TrackMoves> <w:TrackFormatting/> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:DoNotPromoteQF/> <w:LidThemeOther>EN-US</w:LidThemeOther> <w:LidThemeAsian>ZH-CN</w:LidThemeAsian> <w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript> <w:Compatibility> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> <w:SplitPgBreakAndParaMark/> <w:DontVertAlignCellWithSp/> <w:DontBreakConstrainedForcedTables/> <w:DontVertAlignInTxbx/> <w:Word11KerningPairs/> <w:CachedColBalance/> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> <m:mathPr> <m:mathFont m:val="Cambria Math"/> <m:brkBin m:val="before"/> <m:brkBinSub m:val="&#45;-"/> <m:smallFrac m:val="off"/> <m:dispDef/> <m:lMargin m:val="0"/> <m:rMargin m:val="0"/> <m:defJc m:val="centerGroup"/> <m:wrapIndent m:val="1440"/> <m:intLim m:val="subSup"/> <m:naryLim m:val="undOvr"/> </m:mathPr></w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="true" DefSemiHidden="true" DefQFormat="false" DefPriority="99" LatentStyleCount="267"> <w:LsdException Locked="false" Priority="0" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Normal"/> <w:LsdException Locked="false" Priority="9" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="heading 1"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 2"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 3"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 4"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 5"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 6"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 7"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 8"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 9"/> <w:LsdException Locked="false" Priority="39" Name="toc 1"/> <w:LsdException Locked="false" Priority="39" Name="toc 2"/> <w:LsdException Locked="false" Priority="39" Name="toc 3"/> <w:LsdException Locked="false" Priority="39" Name="toc 4"/> <w:LsdException Locked="false" Priority="39" Name="toc 5"/> <w:LsdException Locked="false" Priority="39" Name="toc 6"/> <w:LsdException Locked="false" Priority="39" Name="toc 7"/> <w:LsdException Locked="false" Priority="39" Name="toc 8"/> <w:LsdException Locked="false" Priority="39" Name="toc 9"/> <w:LsdException Locked="false" Priority="35" QFormat="true" Name="caption"/> <w:LsdException Locked="false" Priority="10" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Title"/> <w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/> <w:LsdException Locked="false" Priority="11" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Subtitle"/> <w:LsdException Locked="false" Priority="22" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Strong"/> <w:LsdException Locked="false" Priority="20" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Emphasis"/> <w:LsdException Locked="false" Priority="59" SemiHidden="false" UnhideWhenUsed="false" Name="Table Grid"/> <w:LsdException Locked="false" UnhideWhenUsed="false" Name="Placeholder Text"/> <w:LsdException Locked="false" Priority="1" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="No Spacing"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 1"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 1"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 1"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 1"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 1"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 1"/> <w:LsdException Locked="false" UnhideWhenUsed="false" Name="Revision"/> <w:LsdException Locked="false" Priority="34" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="List Paragraph"/> <w:LsdException Locked="false" Priority="29" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Quote"/> <w:LsdException Locked="false" Priority="30" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Intense Quote"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 1"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 1"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 1"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 1"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 1"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 1"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 1"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 1"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 2"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 2"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 2"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 2"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 2"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 2"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 2"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 2"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 2"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 2"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 2"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 2"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 2"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 2"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 3"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 3"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 3"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 3"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 3"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 3"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 3"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 3"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 3"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 3"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 3"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 3"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 3"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 3"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 4"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 4"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 4"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 4"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 4"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 4"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 4"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 4"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 4"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 4"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 4"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 4"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 4"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 4"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 5"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 5"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 5"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 5"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 5"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 5"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 5"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 5"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 5"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 5"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 5"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 5"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 5"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 5"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 6"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 6"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 6"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 6"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 6"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 6"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 6"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 6"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 6"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 6"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 6"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 6"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 6"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 6"/> <w:LsdException Locked="false" Priority="19" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Subtle Emphasis"/> <w:LsdException Locked="false" Priority="21" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Intense Emphasis"/> <w:LsdException Locked="false" Priority="31" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Subtle Reference"/> <w:LsdException Locked="false" Priority="32" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Intense Reference"/> <w:LsdException Locked="false" Priority="33" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Book Title"/> <w:LsdException Locked="false" Priority="37" Name="Bibliography"/> <w:LsdException Locked="false" Priority="39" QFormat="true" Name="TOC Heading"/> </w:LatentStyles> </xml><![endif]--> <style> <!--.S {max-width: 42em ;} /* Font Definitions */ @font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:1; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:variable; mso-font-signature:0 0 0 0 0 0;} @font-face {font-family:Tahoma; panose-1:2 11 6 4 3 5 4 4 2 4; mso-font-charset:0; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-520081665 -1073717157 41 0 66047 0;} @font-face {font-family:Verdana; panose-1:2 11 6 4 3 5 4 4 2 4; mso-font-charset:0; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-1593833729 1073750107 16 0 415 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} h1 {mso-style-priority:9; mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"Heading 1 Char"; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; mso-outline-level:1; font-size:24.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; font-weight:bold;} a:link, span.MsoHyperlink {mso-style-priority:99; color:blue; text-decoration:underline; text-underline:single;} a:visited, span.MsoHyperlinkFollowed {mso-style-noshow:yes; mso-style-priority:99; color:blue; text-decoration:underline; text-underline:single;} p {mso-style-priority:99; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.MsoAcetate, li.MsoAcetate, div.MsoAcetate {mso-style-noshow:yes; mso-style-priority:99; mso-style-link:"Balloon Text Char"; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:8.0pt; font-family:"Tahoma","sans-serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph {mso-style-priority:34; mso-style-unhide:no; mso-style-qformat:yes; margin-top:0in; margin-right:0in; margin-bottom:0in; margin-left:.5in; margin-bottom:.0001pt; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.MsoListParagraphCxSpFirst, li.MsoListParagraphCxSpFirst, div.MsoListParagraphCxSpFirst {mso-style-priority:34; mso-style-unhide:no; mso-style-qformat:yes; mso-style-type:export-only; margin-top:0in; margin-right:0in; margin-bottom:0in; margin-left:.5in; margin-bottom:.0001pt; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.MsoListParagraphCxSpMiddle, li.MsoListParagraphCxSpMiddle, div.MsoListParagraphCxSpMiddle {mso-style-priority:34; mso-style-unhide:no; mso-style-qformat:yes; mso-style-type:export-only; margin-top:0in; margin-right:0in; margin-bottom:0in; margin-left:.5in; margin-bottom:.0001pt; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.MsoListParagraphCxSpLast, li.MsoListParagraphCxSpLast, div.MsoListParagraphCxSpLast {mso-style-priority:34; mso-style-unhide:no; mso-style-qformat:yes; mso-style-type:export-only; margin-top:0in; margin-right:0in; margin-bottom:0in; margin-left:.5in; margin-bottom:.0001pt; mso-add-space:auto; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} span.Heading1Char {mso-style-name:"Heading 1 Char"; mso-style-priority:9; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"Heading 1"; mso-ansi-font-size:14.0pt; mso-bidi-font-size:14.0pt; font-family:"Cambria","serif"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:major-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:major-fareast; mso-hansi-font-family:Cambria; mso-hansi-theme-font:major-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:major-bidi; color:#365F91; mso-themecolor:accent1; mso-themeshade:191; font-weight:bold;} span.BalloonTextChar {mso-style-name:"Balloon Text Char"; mso-style-noshow:yes; mso-style-priority:99; mso-style-unhide:no; mso-style-locked:yes; mso-style-link:"Balloon Text"; mso-ansi-font-size:8.0pt; mso-bidi-font-size:8.0pt; font-family:"Tahoma","sans-serif"; mso-ascii-font-family:Tahoma; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Tahoma; mso-bidi-font-family:Tahoma;} p.tabfont, li.tabfont, div.tabfont {mso-style-name:tabfont; mso-style-priority:99; mso-style-unhide:no; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; font-size:13.5pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.med, li.med, div.med {mso-style-name:med; mso-style-priority:99; mso-style-unhide:no; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:13.5pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.g, li.g, div.g {mso-style-name:g; mso-style-priority:99; mso-style-unhide:no; margin-top:12.0pt; margin-right:0in; margin-bottom:.2in; margin-left:0in; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} p.s, li.s, div.s {mso-style-name:s; mso-style-priority:99; mso-style-unhide:no; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman","serif"; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt;} @page WordSection1 {size:8.5in 11.0in; margin:1.0in 1.0in 1.0in 1.0in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.WordSection1 {page:WordSection1;} /* List Definitions */ @list l0 {mso-list-id:161046696; mso-list-type:hybrid; mso-list-template-ids:-1261041604 319855238 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;} @list l0:level1 {mso-level-tab-stop:none; mso-level-number-position:left; text-indent:-.25in; mso-ansi-font-size:12.0pt; mso-fareast-font-family:"Times New Roman"; mso-ansi-font-weight:normal;} @list l0:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} ol {margin-bottom:0in;} ul {margin-bottom:0in;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin:0in; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";} </style> <![endif]--><!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="18434"/> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--> </head> <body bgcolor="#003366" lang=EN-US link=blue vlink=blue style='tab-interval: .5in' alink="#FFFF00" topmargin=0> <div class=WordSection1> <div align=center> <table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width=930 style='width:697.5pt;mso-cellspacing:0in;background:#CCCCFF;mso-yfti-tbllook: 1184;mso-padding-alt:0in 0in 0in 0in'> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes;height:37.5pt'> <td style='padding:0in 0in 0in 0in;height:37.5pt'> <p class=MsoNormal align=center style='text-align:center'><span style='mso-fareast-font-family:"Times New Roman";mso-no-proof:yes'><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter"/> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"/> <v:f eqn="sum @0 1 0"/> <v:f eqn="sum 0 0 @1"/> <v:f eqn="prod @2 1 2"/> <v:f eqn="prod @3 21600 pixelWidth"/> <v:f eqn="prod @3 21600 pixelHeight"/> <v:f eqn="sum @0 0 1"/> <v:f eqn="prod @6 1 2"/> <v:f eqn="prod @7 21600 pixelWidth"/> <v:f eqn="sum @8 21600 0"/> <v:f eqn="prod @7 21600 pixelHeight"/> <v:f eqn="sum @10 21600 0"/> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/> <o:lock v:ext="edit" aspectratio="t"/> </v:shapetype><v:shape id="Picture_x0020_1" o:spid="_x0000_i1037" type="#_x0000_t75" alt="models" style='width:727.5pt;height:135.75pt;visibility:visible; mso-wrap-style:square'> <v:imagedata src="gSaP_files/image001.jpg" o:title="models"/> </v:shape><![endif]--><![if !vml]><img width=970 height=181 src="gSaP_files/image002.jpg" alt=models v:shapes="Picture_x0020_1"><![endif]></span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> <p align=center style='text-align:center'><span style='font-size:22.0pt'>&nbsp;</span><b><span style='font-size:18.0pt;font-family:"Verdana","sans-serif"'>Real-time Collision Culling of a Million Bodies on <o:p></o:p></span></b></p> <p align=center style='text-align:center'><b><span style='font-size:18.0pt; font-family:"Verdana","sans-serif"'>Graphics Processing Units</span></b><span style='font-family:"Verdana","sans-serif"'><o:p></o:p></span></p> <div align=center> <table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width=595 style='width:6.2in;mso-cellspacing:0in;background:#CCCCFF;mso-yfti-tbllook: 1184;mso-padding-alt:0in 0in 0in 0in' id=table1> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'> <td width=600 style='width:6.25in;padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><b><span style='font-size:13.5pt;mso-fareast-font-family:"Times New Roman"'>Fuchang Liu</span></b><b><sup><span style='font-family:"Verdana","sans-serif"; mso-fareast-font-family:"Times New Roman"'>1</span></sup></b><b><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>, </span></b><b><span style='font-size:13.5pt;mso-fareast-font-family:"Times New Roman"'>&nbsp;Takahiro Harada</span></b><b><sup><span style='font-family:"Verdana","sans-serif"; mso-fareast-font-family:"Times New Roman"'>2</span></sup></b><span style='font-size:13.5pt;font-family:"Verdana","sans-serif";mso-fareast-font-family: "Times New Roman"'>, </span><b><span style='font-size:13.5pt;mso-fareast-font-family: "Times New Roman"'>Youngeun Lee</span></b><b><sup><span style='font-family: "Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>1</span></sup></b><span style='font-size:13.5pt;font-family:"Verdana","sans-serif";mso-fareast-font-family: "Times New Roman"'> and</span><b><span style='font-size:13.5pt;mso-fareast-font-family: "Times New Roman"'> Young J. Kim</span></b><b><sup><span style='mso-fareast-font-family: "Times New Roman"'>1</span></sup></b><span style='mso-fareast-font-family: "Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td valign=bottom style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><sup><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>1</span></sup><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>Department of Computer Science &amp; Engineering <o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>Ewha Womans University, Seoul, Korea <o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:3'> <td style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'><a href="mailto:liufu@ewha.ac.kr">liufu@ewha.ac.kr</a>&nbsp; <a href="mailto:youngeunlee@ewhain.net">youngeunlee@ewhain.net</a>, <a href="mailto:kimy@ewha.ac.kr">kimy@ewha.ac.kr</a> <o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:4'> <td style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><sup><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>2</span></sup><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>Advanced Micro Devices, Inc. <o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:5'> <td style='padding:0in 0in 0in 0in'></td> </tr> <tr style='mso-yfti-irow:6;mso-yfti-lastrow:yes'> <td style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'><a href="mailto:Takahiro.Harada@amd.com">Takahiro.Harada@amd.com</a><span style='mso-spacerun:yes'>  </span><o:p></o:p></span></p> </td> </tr> </table> </div> <div class=MsoNormal align=center style='text-align:center'><span style='font-family:"Arial","sans-serif";mso-fareast-font-family:"Times New Roman"'> <hr size=2 width="100%" align=center> </span></div> <div align=center> <table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width=504 style='width:5.25in;mso-cellspacing:0in;background:#CCCCFF;mso-yfti-tbllook: 1184;mso-padding-alt:0in 0in 0in 0in' id=table4> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'> <td style='padding:0in 0in 0in 0in'></td> </tr> <tr style='mso-yfti-irow:1'> <td width=504 style='width:5.25in;padding:0in 0in 0in 0in'> <p class=MsoListParagraphCxSpFirst align=center style='text-align:center; text-indent:-.25in;mso-list:l0 level1 lfo2'><![if !supportLists]><i style='mso-bidi-font-style:normal'><span style='mso-bidi-font-size:11.0pt; font-family:"Verdana","sans-serif";mso-fareast-font-family:Verdana; mso-bidi-font-family:Verdana;mso-bidi-font-weight:bold'><span style='mso-list:Ignore'>1.<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp; </span></span></span></i><![endif]><i style='mso-bidi-font-style:normal'><span style='font-size:11.0pt;font-family:"Verdana","sans-serif";mso-bidi-font-weight: bold'>Published in the ACM Transactions on Graphics* <o:p></o:p></span></i></p> <p class=MsoListParagraphCxSpLast align=center style='text-align:center'><i style='mso-bidi-font-style:normal'><span style='font-size:11.0pt; font-family:"Verdana","sans-serif";mso-bidi-font-weight:bold'>(SIGGRAPH ASIA), Dec. 2010(<a href="gSaP.pdf">pdf</a>)</span></i></p> </td> </tr> <tr style='mso-yfti-irow:2;mso-yfti-lastrow:yes'> <td valign=bottom style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><i style='mso-bidi-font-style:normal'><span style='font-family:"Verdana","sans-serif"; mso-fareast-font-family:"Times New Roman"'>2</span></i><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'>. </span><i style='mso-bidi-font-style:normal'><span style='font-size:11.0pt; font-family:"Verdana","sans-serif";mso-bidi-font-weight:bold'>Source Code in C++ <p class=MsoListParagraphCxSpLast align=center style='text-align:center'><i style='mso-bidi-font-style:normal'><span style='font-size:11.0pt; font-family:"Verdana","sans-serif";mso-bidi-font-weight:bold'> (<a href="http://code.google.com/p/sweep-and-prune-gpu">http://code.google.com/p/sweep-and-prune-gpu</a>)</span></i></p> </td> </tr> </table> </div> <div class=MsoNormal align=center style='text-align:center'><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'> <hr size=2 width="100%" align=center> </span></div> </td> </tr> <tr style='mso-yfti-irow:1;height:17.25pt'> <td style='padding:0in 0in 0in 0in;height:17.25pt'> <p class=MsoNormal align=center style='text-align:center'><b><span style='mso-fareast-font-family:"Times New Roman"'>&nbsp;<o:p></o:p></span></b></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td style='padding:0in 0in 0in 0in'> <h1><span style='font-size:13.5pt;font-family:"Verdana","sans-serif"; mso-fareast-font-family:"Times New Roman"'>Abstract</span><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></h1> <p><span style='font-family:"Verdana","sans-serif"'>&nbsp;&nbsp;&nbsp; We cull collisions between very large numbers of moving bodies using graphics processing units (GPUs). To perform massively parallel sweep-and-prune (SaP), we mitigate the great density of intervals along the axis of sweep by using principal component analysis to choose the best sweep direction, together with spatial subdivisions to further reduce the number of false positive overlaps. Our algorithm implemented entirely on GPUs using the CUDA framework can handle a million moving objects at interactive rates. As application of our algorithm, we demonstrate the real-time simulation of very large numbers of particles and rigid-body dynamics.<o:p></o:p></span></p> <p align=center><span style='font-family:"Verdana","sans-serif"'>&nbsp; <object width="480" height="385"><param name="movie" value="http://www.youtube.com/v/7jIj6gQ5Zjo?fs=1&amp;hl=en_US"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/7jIj6gQ5Zjo?fs=1&amp;hl=en_US" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="480" height="385"></embed></object> </p> </td> </tr> <tr style='mso-yfti-irow:3;height:39.0pt'> <td style='padding:0in 0in 0in 0in;height:39.0pt'> <div class=MsoNormal align=center style='text-align:center'><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'> <hr size=2 width="100%" align=center> </span></div> </td> </tr> <tr style='mso-yfti-irow:4'> <td style='padding:0in 0in 0in 0in'> <h1><span style='font-size:13.5pt;font-family:"Verdana","sans-serif"; mso-fareast-font-family:"Times New Roman"'>Benchmarking Scenarios</span><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></h1> <p><b><span style='font-family:"Verdana","sans-serif"'>1. Random Configurations</span></b><span style='font-family:"Verdana","sans-serif"'>: <br> <br> We used a benchmark setup similar to the Bullet collision Library, in which a set of AABBs are uniformly distributed in space and moving randomly. As we changed the number of AABBs from 16K to 960K, we measured the performance of our algorithm and that of the three broad-phase CD algorithms provided in Bullet, which are BoxPruning, ArraySaP and an AABB dynamic tree. The first two algorithms are based on SaP and the last one using a dynamic bounding volume hierarchy. All of these algorithms run on CPU. The size of the AABBs also varies from 0.5% to 8% to the size of the bounding box of the workspace. As shown Figure below, our algorithm outperforms the fastest of the Bullet implementations (i.e. the AABB dynamic tree) by a factor of 71 times.<o:p></o:p></span></p> <table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width=964 style='width:723.0pt;mso-cellspacing:0in;background:#CCCCFF;mso-yfti-tbllook: 1184;mso-padding-alt:0in 0in 0in 0in'> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'> <td style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='mso-fareast-font-family:"Times New Roman";mso-no-proof:yes'><!--[if gte vml 1]><v:shape id="Picture_x0020_13" o:spid="_x0000_i1036" type="#_x0000_t75" alt="Club" style='width:576.75pt;height:255.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="gSaP_files/image003.jpg" o:title="Club"/> </v:shape><![endif]--><![if !vml]><img border=0 width=769 height=341 src="gSaP_files/image004.jpg" alt=Club v:shapes="Picture_x0020_13"><![endif]></span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> <p class=MsoNormal align=center style='text-align:center'><b style='mso-bidi-font-weight:normal'><span style='mso-fareast-font-family: "Times New Roman"'>Comparison of Collision Detection performance with the difference methods in Bullet CPU algorithm<o:p></o:p></span></b></p> <p class=MsoNormal align=center style='text-align:center'><b style='mso-bidi-font-weight:normal'><span style='mso-fareast-font-family: "Times New Roman"'><o:p>&nbsp;</o:p></span></b></p> <p class=MsoNormal><span style='font-family:"Verdana","sans-serif"'>We also investigated the the performance of our algorithm when only some of the objects are moving. The objects are one million AABBs of varying sizes, and we changed the percentage of moving objects from 5% to 25%. The figure below shows that the number of new collisions generated by moving objects, as a proportion of the total number of interferences is almost linear with computation time, which implies that as more collision pairs are introduced by moving objects, our algorithm requires more time to process them. This means that our algorithm efficiently utilizes the collision results introduced by static objects, which are cached from the previous time step.<o:p></o:p></span></p> <p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span style='mso-fareast-font-family:"Times New Roman"'><o:p>&nbsp;</o:p></span></b></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td width=964 style='width:723.0pt;padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='mso-fareast-font-family:"Times New Roman";mso-no-proof:yes'><!--[if gte vml 1]><v:shape id="Picture_x0020_12" o:spid="_x0000_i1035" type="#_x0000_t75" alt="timing of Club" style='width:475.5pt;height:267.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="gSaP_files/image005.jpg" o:title="timing of Club"/> </v:shape><![endif]--><![if !vml]><img border=0 width=634 height=357 src="gSaP_files/image006.jpg" alt="timing of Club" v:shapes="Picture_x0020_12"><![endif]></span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td valign=bottom style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><b style='mso-bidi-font-weight:normal'><span style='mso-fareast-font-family: "Times New Roman"'>Collision detection when only some objects are moving</span></b><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:3;mso-yfti-lastrow:yes'> <td style='padding:0in 0in 0in 0in'></td> </tr> </table> <div class=MsoNormal align=center style='text-align:center'><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'> <hr size=2 width="100%" noshade style='color:#3366CC' align=center> </span></div> <p><b><span style='font-family:"Verdana","sans-serif"'>2. Particle Simulation</span></b><span style='font-family:"Verdana","sans-serif"'>: <o:p></o:p></span></p> <p><span style='font-family:"Verdana","sans-serif"'>We benchmarked on large sets of particles of varying sizes. We did this by modifying an open particle simulation demo, originally from NVIDIA (Particles sample code in CUDA SDK). As shown in Figure below, we introduced 100K and 0.3M spheres of the size varying from 0.3% to 20% of the dimension of the workspace and simulated their motions under gravity. We then measure the performance of our algorithm and that of a uniform subdivision algorithm that also runs GPUs. While CD takes up most of the computation, it is hard to decouple the collision times from the simulation times using NVIDIA's uniform subdivision method. However, for 100K and 0.3M particles, our algorithm takes 56 <i style='mso-bidi-font-style: normal'>ms</i> and 252 <i style='mso-bidi-font-style:normal'>ms</i> on average for both collision detection and particle simulation while uniform subdivision 4452 <i style='mso-bidi-font-style:normal'>ms</i> and 53464 <i style='mso-bidi-font-style:normal'>ms</i>; thus our algorithm outperforms uniform subdivision by a factor of 212 times.<o:p></o:p></span></p> <div align=center> <table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width=504 style='width:5.25in;mso-cellspacing:0in;background:#CCCCFF;mso-yfti-tbllook: 1184;mso-padding-alt:0in 0in 0in 0in'> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'> <td style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='mso-fareast-font-family:"Times New Roman";mso-no-proof:yes'><!--[if gte vml 1]><v:shape id="Picture_x0020_11" o:spid="_x0000_i1034" type="#_x0000_t75" alt="hammer" style='width:4in;height:289.5pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="gSaP_files/image007.png" o:title="hammer"/> </v:shape><![endif]--><![if !vml]><img border=0 width=384 height=386 src="gSaP_files/image008.jpg" alt=hammer v:shapes="Picture_x0020_11"><![endif]></span><span style='mso-fareast-font-family:"Times New Roman"'><span style='mso-spacerun:yes'> </span><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td width=504 style='width:5.25in;padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='mso-fareast-font-family:"Times New Roman";mso-no-proof:yes'><!--[if gte vml 1]><v:shape id="Picture_x0020_10" o:spid="_x0000_i1033" type="#_x0000_t75" alt="timing of hammer" style='width:4in;height:289.5pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="gSaP_files/image009.png" o:title="timing of hammer"/> </v:shape><![endif]--><![if !vml]><img border=0 width=384 height=386 src="gSaP_files/image010.jpg" alt="timing of hammer" v:shapes="Picture_x0020_10"><![endif]></span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td valign=bottom style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><b style='mso-bidi-font-weight:normal'><span style='mso-fareast-font-family: "Times New Roman"'>Particle Simulation</span></b><span style='mso-fareast-font-family: "Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:3;mso-yfti-lastrow:yes'> <td style='padding:0in 0in 0in 0in'></td> </tr> </table> </div> <div class=MsoNormal align=center style='text-align:center'><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'> <hr size=2 width="100%" noshade style='color:#3366CC' align=center> </span></div> <p><b><span style='font-family:"Verdana","sans-serif"'>3. Approximate Rigid-Body Dynamics</span></b><span style='font-family:"Verdana","sans-serif"'>:<br><br> We approximated a rigid model with a set of uniform spheres, and used a penalty-based approach running in parallel on GPUs.<span style='mso-spacerun:yes'>  </span>This avoids narrow-phase Collision Detection. We simulated 16K torus models approximated by six spheres of varying size moving under gravity. We were able to simulate the approximate rigid-body dynamics entirely running on GPUs in 18 <i style='mso-bidi-font-style: normal'>ms</i>, including collision detection.<o:p></o:p></span></p> <p class=MsoNormal><span style='font-family:"Verdana","sans-serif"; mso-fareast-font-family:"Times New Roman"'>&nbsp;<o:p></o:p></span></p> <div align=center> <table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width=504 style='width:5.25in;mso-cellspacing:0in;background:#CCCCFF;mso-yfti-tbllook: 1184;mso-padding-alt:0in 0in 0in 0in' id=table10> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'> <td style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='mso-fareast-font-family:"Times New Roman";mso-no-proof:yes'><!--[if gte vml 1]><v:shape id="Picture_x0020_9" o:spid="_x0000_i1032" type="#_x0000_t75" alt="dybunny" style='width:366.75pt;height:276.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="gSaP_files/image011.jpg" o:title="dybunny"/> </v:shape><![endif]--><![if !vml]><img border=0 width=489 height=369 src="gSaP_files/image012.jpg" alt=dybunny v:shapes="Picture_x0020_9"><![endif]></span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td style='padding:0in 0in 0in 0in'></td> </tr> <tr style='mso-yfti-irow:2'> <td style='padding:0in 0in 0in 0in'></td> </tr> <tr style='mso-yfti-irow:3'> <td valign=bottom style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><span style='mso-fareast-font-family:"Times New Roman";mso-no-proof:yes'><!--[if gte vml 1]><v:shape id="Picture_x0020_8" o:spid="_x0000_i1031" type="#_x0000_t75" alt="timing of dybunny" style='width:369pt;height:276.75pt;visibility:visible;mso-wrap-style:square'> <v:imagedata src="gSaP_files/image013.png" o:title="timing of dybunny"/> </v:shape><![endif]--><![if !vml]><img border=0 width=492 height=369 src="gSaP_files/image014.jpg" alt="timing of dybunny" v:shapes="Picture_x0020_8"><![endif]></span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:4'> <td valign=bottom style='padding:0in 0in 0in 0in'> <p class=MsoNormal align=center style='text-align:center'><b style='mso-bidi-font-weight:normal'><span style='mso-fareast-font-family: "Times New Roman"'>Approximate Rigid-Body Dynamics for torus</span></b><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:5;mso-yfti-lastrow:yes'> <td style='padding:0in 0in 0in 0in'></td> </tr> </table> </div> <div class=MsoNormal align=center style='text-align:center'><span style='font-family:"Arial","sans-serif";mso-fareast-font-family:"Times New Roman"'> <hr size=2 width="100%" align=center> </span></div> <h1><span style='font-size:13.5pt;font-family:"Verdana","sans-serif"; mso-fareast-font-family:"Times New Roman"'>RELATED LINKS</span><span style='font-family:"Verdana","sans-serif";mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></h1> <p><b style='mso-bidi-font-weight:normal'><span style='font-family:"Verdana","sans-serif"'>Bullet collision Library:<o:p></o:p></span></b></p> <p><span style='font-family:"Verdana","sans-serif"'><span style='mso-spacerun:yes'>   </span><span style='mso-spacerun:yes'> </span><a href="http://bulletphysics.org/">http://bulletphysics.org</a><span style='mso-bidi-font-weight:bold'> <o:p></o:p></span></span></p> <p><b><span style='font-family:"Verdana","sans-serif"'>Real-Time Rigid Body Simulation on GPUs(GPU Gem3):</span></b><span style='font-family:"Verdana","sans-serif"'><o:p></o:p></span></p> <p style='text-indent:.25in'><span style='font-family:"Verdana","sans-serif"'><a href="http://http.developer.nvidia.com/GPUGems3/gpugems3_ch29.html">http://http.developer.nvidia.com/GPUGems3/gpugems3_ch29.html</a> <o:p></o:p></span></p> <p><b><span style='font-family:"Verdana","sans-serif"'>Particles:</span></b><span style='font-family:"Verdana","sans-serif"'><o:p></o:p></span></p> <p style='text-indent:.25in'><span style='font-family:"Verdana","sans-serif"'><a href="http://developer.download.nvidia.com/compute/cuda/sdk/website/C/src/particles/doc/particles.pdf">http://developer.download.nvidia.com/compute/cuda/sdk/website/C/src/particles/doc/particles.pdf</a> <o:p></o:p></span></p> <p style='text-indent:.25in'><span style='font-family:"Verdana","sans-serif"'><a href="http://developer.download.nvidia.com/compute/cuda/sdk/Projects/particles.zip">http://developer.download.nvidia.com/compute/cuda/sdk/Projects/particles.zip</a> <o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:5;mso-yfti-lastrow:yes'> <td style='background:#E0DFE3;padding:0in 0in 0in 0in'> <div align=center> <table class=MsoNormalTable border=0 cellspacing=1 cellpadding=0 width="100%" style='width:100.0%;mso-cellspacing:.7pt;mso-yfti-tbllook:1184;mso-padding-alt: 0in 5.4pt 0in 5.4pt' id=table12> <tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'> <td style='padding:.75pt .75pt .75pt .75pt'> <p class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Verdana","sans-serif";mso-fareast-font-family: "Times New Roman"'>Copyright 2010 Computer Graphics Laboratory</span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:1'> <td style='padding:.75pt .75pt .75pt .75pt'> <p class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Verdana","sans-serif";mso-fareast-font-family: "Times New Roman"'>Dept of Computer Science &amp; Engineering</span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:2'> <td style='padding:.75pt .75pt .75pt .75pt'> <p class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Verdana","sans-serif";mso-fareast-font-family: "Times New Roman"'>Ewha Womans University, Seoul, Korea</span><span style='mso-fareast-font-family:"Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:3;mso-yfti-lastrow:yes'> <td style='padding:.75pt .75pt .75pt .75pt'> <p class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Verdana","sans-serif";mso-fareast-font-family: "Times New Roman"'>Last update: 2010-09-06</span><span style='mso-fareast-font-family: "Times New Roman"'><o:p></o:p></span></p> </td> </tr> <tr style='mso-yfti-irow:3;mso-yfti-lastrow:yes'> <td style='padding:.75pt .75pt .75pt .75pt'> <p class=MsoNormal align=center style='text-align:center'><span style='font-size:10.0pt;font-family:"Verdana","sans-serif";mso-fareast-font-family: "Times New Roman"'><a href="http://www.ewha.ac.kr/korean/files/content/main_kor/etc/personal_01.html" target="_blank">[¬xÇÈô¼ô¼8Ö)¼hÎ]</a></span></p> </td> </tr> </table> </div> </td> </tr> </table> </div> <p class=MsoNormal><span style='mso-fareast-font-family:"Times New Roman"'><o:p>&nbsp;</o:p></span></p> </div> </body> </html> &nbsp;