High Performance GPU‐based Proximity Queries using Distance Fields
Identifieur interne : 004033 ( Istex/Corpus ); précédent : 004032; suivant : 004034High Performance GPU‐based Proximity Queries using Distance Fields
Auteurs : T. Morvan ; M. Reimers ; E. SamsetSource :
- Computer Graphics Forum [ 0167-7055 ] ; 2008-12.
English descriptors
- KwdEn :
Abstract
Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.
Url:
DOI: 10.1111/j.1467-8659.2008.01183.x
Links to Exploration step
ISTEX:B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBCLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">High Performance GPU‐based Proximity Queries using Distance Fields</title><author><name sortKey="Morvan, T" sort="Morvan, T" uniqKey="Morvan T" first="T." last="Morvan">T. Morvan</name><affiliation><mods:affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</mods:affiliation></affiliation></author><author><name sortKey="Reimers, M" sort="Reimers, M" uniqKey="Reimers M" first="M." last="Reimers">M. Reimers</name><affiliation><mods:affiliation>Centre of Mathematics for Applications, University of Oslo, Norway</mods:affiliation></affiliation></author><author><name sortKey="Samset, E" sort="Samset, E" uniqKey="Samset E" first="E." last="Samset">E. Samset</name><affiliation><mods:affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</mods:affiliation></affiliation><affiliation><mods:affiliation>Interventional Centre, Rikshospitalet Medical Centre, Norway</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1111/j.1467-8659.2008.01183.x</idno><idno type="url">https://api.istex.fr/document/B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">004033</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">High Performance GPU‐based Proximity Queries using Distance Fields</title><author><name sortKey="Morvan, T" sort="Morvan, T" uniqKey="Morvan T" first="T." last="Morvan">T. Morvan</name><affiliation><mods:affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</mods:affiliation></affiliation></author><author><name sortKey="Reimers, M" sort="Reimers, M" uniqKey="Reimers M" first="M." last="Reimers">M. Reimers</name><affiliation><mods:affiliation>Centre of Mathematics for Applications, University of Oslo, Norway</mods:affiliation></affiliation></author><author><name sortKey="Samset, E" sort="Samset, E" uniqKey="Samset E" first="E." last="Samset">E. Samset</name><affiliation><mods:affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</mods:affiliation></affiliation><affiliation><mods:affiliation>Interventional Centre, Rikshospitalet Medical Centre, Norway</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Computer Graphics Forum</title><idno type="ISSN">0167-7055</idno><idno type="eISSN">1467-8659</idno><imprint><publisher>Blackwell Publishing Ltd</publisher><pubPlace>Oxford, UK</pubPlace><date type="published" when="2008-12">2008-12</date><biblScope unit="volume">27</biblScope><biblScope unit="issue">8</biblScope><biblScope unit="page" from="2040">2040</biblScope><biblScope unit="page" to="2052">2052</biblScope></imprint><idno type="ISSN">0167-7055</idno></series><idno type="istex">B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC</idno><idno type="DOI">10.1111/j.1467-8659.2008.01183.x</idno><idno type="ArticleID">CGF1183</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0167-7055</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>GPU</term><term>I.3.5 [Computer Graphics]: Geometric Algorithms</term><term>I.3.7 [Computer Graphics]: Animation; virtual reality</term><term>collision detection</term><term>distance fields</term><term>proximity queries</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.</div></front></TEI><istex><corpusName>wiley</corpusName><author><json:item><name>T. Morvan</name><affiliations><json:string>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</json:string></affiliations></json:item><json:item><name>M. Reimers</name><affiliations><json:string>Centre of Mathematics for Applications, University of Oslo, Norway</json:string></affiliations></json:item><json:item><name>E. Samset</name><affiliations><json:string>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</json:string><json:string>Interventional Centre, Rikshospitalet Medical Centre, Norway</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>proximity queries</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>collision detection</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>distance fields</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>GPU</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>I.3.5 [Computer Graphics]: Geometric Algorithms</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>I.3.7 [Computer Graphics]: Animation; virtual reality</value></json:item></subject><articleId><json:string>CGF1183</json:string></articleId><language><json:string>eng</json:string></language><abstract>Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.</abstract><qualityIndicators><score>7.204</score><pdfVersion>1.4</pdfVersion><pdfPageSize>544.178 x 742.648 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>6</keywordCount><abstractCharCount>1044</abstractCharCount><pdfWordCount>7889</pdfWordCount><pdfCharCount>47627</pdfCharCount><pdfPageCount>13</pdfPageCount><abstractWordCount>142</abstractWordCount></qualityIndicators><title>High Performance GPU‐based Proximity Queries using Distance Fields</title><genre.original><json:string>article</json:string></genre.original><genre><json:string>article</json:string></genre><host><volume>27</volume><publisherId><json:string>CGF</json:string></publisherId><pages><total>13</total><last>2052</last><first>2040</first></pages><issn><json:string>0167-7055</json:string></issn><issue>8</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><eissn><json:string>1467-8659</json:string></eissn><title>Computer Graphics Forum</title><doi><json:string>10.1111/(ISSN)1467-8659</json:string></doi></host><publicationDate>2008</publicationDate><copyrightDate>2008</copyrightDate><doi><json:string>10.1111/j.1467-8659.2008.01183.x</json:string></doi><id>B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC</id><score>1</score><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC/fulltext/pdf</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">High Performance GPU‐based Proximity Queries using Distance Fields</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Blackwell Publishing Ltd</publisher><pubPlace>Oxford, UK</pubPlace><availability><p>WILEY</p></availability><date>2008</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">High Performance GPU‐based Proximity Queries using Distance Fields</title><author><persName><forename type="first">T.</forename><surname>Morvan</surname></persName><affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</affiliation></author><author><persName><forename type="first">M.</forename><surname>Reimers</surname></persName><affiliation>Centre of Mathematics for Applications, University of Oslo, Norway</affiliation></author><author><persName><forename type="first">E.</forename><surname>Samset</surname></persName><affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</affiliation><affiliation>Interventional Centre, Rikshospitalet Medical Centre, Norway</affiliation></author></analytic><monogr><title level="j">Computer Graphics Forum</title><idno type="pISSN">0167-7055</idno><idno type="eISSN">1467-8659</idno><idno type="DOI">10.1111/(ISSN)1467-8659</idno><imprint><publisher>Blackwell Publishing Ltd</publisher><pubPlace>Oxford, UK</pubPlace><date type="published" when="2008-12"></date><biblScope unit="volume">27</biblScope><biblScope unit="issue">8</biblScope><biblScope unit="page" from="2040">2040</biblScope><biblScope unit="page" to="2052">2052</biblScope></imprint></monogr><idno type="istex">B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC</idno><idno type="DOI">10.1111/j.1467-8659.2008.01183.x</idno><idno type="ArticleID">CGF1183</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2008</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.</p></abstract><textClass xml:lang="en"><keywords scheme="keyword"><list><head>keywords</head><item><term>proximity queries</term></item><item><term>collision detection</term></item><item><term>distance fields</term></item><item><term>GPU</term></item></list></keywords></textClass><textClass xml:lang="en"><keywords scheme="keyword"><list><head>keywords</head><item><term>I.3.5 [Computer Graphics]: Geometric Algorithms</term></item><item><term>I.3.7 [Computer Graphics]: Animation; virtual reality</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2008-12">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><original>false</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Wiley, elements deleted: body"><istex:xmlDeclaration>version="1.0" encoding="UTF-8" standalone="yes"</istex:xmlDeclaration><istex:document><component version="2.0" type="serialArticle" xml:lang="en"><header><publicationMeta level="product"><publisherInfo><publisherName>Blackwell Publishing Ltd</publisherName><publisherLoc>Oxford, UK</publisherLoc></publisherInfo><doi origin="wiley" registered="yes">10.1111/(ISSN)1467-8659</doi><issn type="print">0167-7055</issn><issn type="electronic">1467-8659</issn><idGroup><id type="product" value="CGF"></id><id type="publisherDivision" value="ST"></id></idGroup><titleGroup><title type="main" sort="COMPUTER GRAPHICS FORUM">Computer Graphics Forum</title></titleGroup></publicationMeta><publicationMeta level="part" position="12008"><doi origin="wiley">10.1111/cgf.2008.27.issue-8</doi><numberingGroup><numbering type="journalVolume" number="27">27</numbering><numbering type="journalIssue" number="8">8</numbering></numberingGroup><coverDate startDate="2008-12">December 2008</coverDate></publicationMeta><publicationMeta level="unit" type="article" position="4" status="forIssue"><doi origin="wiley">10.1111/j.1467-8659.2008.01183.x</doi><idGroup><id type="unit" value="CGF1183"></id></idGroup><countGroup><count type="pageTotal" number="13"></count></countGroup><titleGroup><title type="tocHeading1">Articles</title></titleGroup><copyright>© 2008 The Authors Journal compilation © 2008 The Eurographics Association and Blackwell Publishing Ltd.</copyright><eventGroup><event type="firstOnline" date="2008-09-10"></event><event type="publishedOnlineFinalForm" date="2008-11-21"></event><event type="xmlConverted" agent="Converter:BPG_TO_WML3G version:2.3.5 mode:FullText source:FullText result:FullText" date="2010-04-07"></event><event type="xmlConverted" agent="Converter:WILEY_ML3G_TO_WILEY_ML3GV2 version:4.0.1" date="2014-03-15"></event><event type="xmlConverted" agent="Converter:WML3G_To_WML3G version:4.1.7 mode:FullText,remove_FC" date="2014-10-16"></event></eventGroup><numberingGroup><numbering type="pageFirst" number="2040">2040</numbering><numbering type="pageLast" number="2052">2052</numbering></numberingGroup><linkGroup><link type="toTypesetVersion" href="file:CGF.CGF1183.pdf"></link></linkGroup></publicationMeta><contentMeta><unparsedEditorialHistory>Submitted January 2008Revised April 2008Accepted May 2008</unparsedEditorialHistory><countGroup><count type="figureTotal" number="13"></count><count type="tableTotal" number="2"></count><count type="formulaTotal" number="93"></count><count type="referenceTotal" number="36"></count><count type="linksCrossRef" number="94"></count></countGroup><titleGroup><title type="main">High Performance GPU‐based Proximity Queries using Distance Fields</title></titleGroup><creators><creator creatorRole="author" xml:id="cr1" affiliationRef="#a1"><personName><givenNames>T.</givenNames><familyName>Morvan</familyName></personName></creator><creator creatorRole="author" xml:id="cr2" affiliationRef="#a2"><personName><givenNames>M.</givenNames><familyName>Reimers</familyName></personName></creator><creator creatorRole="author" xml:id="cr3" affiliationRef="#a1 #a3"><personName><givenNames>E.</givenNames><familyName>Samset</familyName></personName></creator></creators><affiliationGroup><affiliation xml:id="a1" countryCode="NO"><unparsedAffiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</unparsedAffiliation></affiliation><affiliation xml:id="a2" countryCode="NO"><unparsedAffiliation>Centre of Mathematics for Applications, University of Oslo, Norway</unparsedAffiliation></affiliation><affiliation xml:id="a3" countryCode="NO"><unparsedAffiliation>Interventional Centre, Rikshospitalet Medical Centre, Norway</unparsedAffiliation></affiliation></affiliationGroup><keywordGroup xml:lang="en"><keyword xml:id="k1">proximity queries</keyword><keyword xml:id="k2">collision detection</keyword><keyword xml:id="k3">distance fields</keyword><keyword xml:id="k4">GPU</keyword></keywordGroup><keywordGroup xml:lang="en"><keyword xml:id="k5">I.3.5 [Computer Graphics]: Geometric Algorithms</keyword><keyword xml:id="k6">I.3.7 [Computer Graphics]: Animation; virtual reality</keyword></keywordGroup><abstractGroup><abstract type="main" xml:lang="en"><title type="main">Abstract</title><p> <i>Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.</i> </p></abstract></abstractGroup></contentMeta></header></component></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>High Performance GPU‐based Proximity Queries using Distance Fields</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>High Performance GPU‐based Proximity Queries using Distance Fields</title></titleInfo><name type="personal"><namePart type="given">T.</namePart><namePart type="family">Morvan</namePart><affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">M.</namePart><namePart type="family">Reimers</namePart><affiliation>Centre of Mathematics for Applications, University of Oslo, Norway</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">E.</namePart><namePart type="family">Samset</namePart><affiliation>Interventional Centre, Faculty of Medicine, University of Oslo, Norway</affiliation><affiliation>Interventional Centre, Rikshospitalet Medical Centre, Norway</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="article" displayLabel="article"></genre><originInfo><publisher>Blackwell Publishing Ltd</publisher><place><placeTerm type="text">Oxford, UK</placeTerm></place><dateIssued encoding="w3cdtf">2008-12</dateIssued><edition>Submitted January 2008Revised April 2008Accepted May 2008</edition><copyrightDate encoding="w3cdtf">2008</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType><extent unit="figures">13</extent><extent unit="tables">2</extent><extent unit="formulas">93</extent><extent unit="references">36</extent></physicalDescription><abstract lang="en">Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.</abstract><subject lang="en"><genre>keywords</genre><topic>proximity queries</topic><topic>collision detection</topic><topic>distance fields</topic><topic>GPU</topic></subject><subject lang="en"><genre>keywords</genre><topic>I.3.5 [Computer Graphics]: Geometric Algorithms</topic><topic>I.3.7 [Computer Graphics]: Animation; virtual reality</topic></subject><relatedItem type="host"><titleInfo><title>Computer Graphics Forum</title></titleInfo><genre type="journal">journal</genre><identifier type="ISSN">0167-7055</identifier><identifier type="eISSN">1467-8659</identifier><identifier type="DOI">10.1111/(ISSN)1467-8659</identifier><identifier type="PublisherID">CGF</identifier><part><date>2008</date><detail type="volume"><caption>vol.</caption><number>27</number></detail><detail type="issue"><caption>no.</caption><number>8</number></detail><extent unit="pages"><start>2040</start><end>2052</end><total>13</total></extent></part></relatedItem><identifier type="istex">B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC</identifier><identifier type="DOI">10.1111/j.1467-8659.2008.01183.x</identifier><identifier type="ArticleID">CGF1183</identifier><accessCondition type="use and reproduction" contentType="copyright">© 2008 The Authors Journal compilation © 2008 The Eurographics Association and Blackwell Publishing Ltd.</accessCondition><recordInfo><recordContentSource>WILEY</recordContentSource><recordOrigin>Blackwell Publishing Ltd</recordOrigin></recordInfo></mods></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/HapticV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004033 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 004033 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= HapticV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:B8F2171A2D8C45B8209F4B8F9F365D8B5119CFBC
|texte= High Performance GPU‐based Proximity Queries using Distance Fields
}}
| This area was generated with Dilib version V0.6.23. |  |