CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Collision detection - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"b1bd5ea6-9863-4978-8f04-931bffda5254","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Collision_detection","wgTitle":"Collision detection","wgCurRevisionId":1259003655,"wgRevisionId":1259003655,"wgArticleId":171552,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Wikipedia articles that are too technical from March 2020","All articles that are too technical","Wikipedia articles with style issues from January 2023","All articles with style issues","Wikipedia articles with style issues from August 2014","Articles with multiple maintenance issues","Wikipedia articles with style issues from January 2024","Articles needing additional references from July 2024", "All articles needing additional references","All articles with unsourced statements","Articles with unsourced statements from June 2008","Articles needing additional references from January 2024","Articles needing additional references from August 2022","Articles with unsourced statements from August 2014","All articles lacking reliable references","Articles lacking reliable references from March 2018","Computational geometry","Computer graphics","Video game development","Computer physics engines","Robotics engineering"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Collision_detection","wgRelevantArticleId":171552,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true, "wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":40000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1550329","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready", "user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns", "ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Collision detection - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Collision_detection"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Collision_detection&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Collision_detection"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Collision_detection rootpage-Collision_detection skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Collision+detection" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Collision+detection" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Collision+detection" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Collision+detection" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Overview" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Overview</span> </div> </a> <ul id="toc-Overview-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Broad_phase" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Broad_phase"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Broad phase</span> </div> </a> <button aria-controls="toc-Broad_phase-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Broad phase subsection</span> </button> <ul id="toc-Broad_phase-sublist" class="vector-toc-list"> <li id="toc-Spatial_partitioning" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Spatial_partitioning"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Spatial partitioning</span> </div> </a> <ul id="toc-Spatial_partitioning-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bounding_volume_hierarchy" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bounding_volume_hierarchy"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Bounding volume hierarchy</span> </div> </a> <ul id="toc-Bounding_volume_hierarchy-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Exploiting_temporal_coherence" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Exploiting_temporal_coherence"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Exploiting temporal coherence</span> </div> </a> <ul id="toc-Exploiting_temporal_coherence-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Pairwise_pruning" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Pairwise_pruning"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>Pairwise pruning</span> </div> </a> <ul id="toc-Pairwise_pruning-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Narrow_phase" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Narrow_phase"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Narrow phase</span> </div> </a> <button aria-controls="toc-Narrow_phase-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Narrow phase subsection</span> </button> <ul id="toc-Narrow_phase-sublist" class="vector-toc-list"> <li id="toc-Bounding_volumes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bounding_volumes"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Bounding volumes</span> </div> </a> <ul id="toc-Bounding_volumes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Exact_pairwise_collision_detection" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Exact_pairwise_collision_detection"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Exact pairwise collision detection</span> </div> </a> <ul id="toc-Exact_pairwise_collision_detection-sublist" class="vector-toc-list"> <li id="toc-Collision_detection_between_convex_objects" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Collision_detection_between_convex_objects"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2.1</span> <span>Collision detection between convex objects</span> </div> </a> <ul id="toc-Collision_detection_between_convex_objects-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-A_priori_pruning" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#A_priori_pruning"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>A priori pruning</span> </div> </a> <ul id="toc-A_priori_pruning-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Triangle_centroid_segments" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Triangle_centroid_segments"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.4</span> <span>Triangle centroid segments</span> </div> </a> <ul id="toc-Triangle_centroid_segments-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Usage" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Usage"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Usage</span> </div> </a> <button aria-controls="toc-Usage-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Usage subsection</span> </button> <ul id="toc-Usage-sublist" class="vector-toc-list"> <li id="toc-Collision_detection_in_computer_simulation" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Collision_detection_in_computer_simulation"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Collision detection in computer simulation</span> </div> </a> <ul id="toc-Collision_detection_in_computer_simulation-sublist" class="vector-toc-list"> <li id="toc-A_posteriori_(discrete)_versus_a_priori_(continuous)" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#A_posteriori_(discrete)_versus_a_priori_(continuous)"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.1</span> <span><i>A posteriori</i> (discrete) versus <i>a priori</i> (continuous)</span> </div> </a> <ul id="toc-A_posteriori_(discrete)_versus_a_priori_(continuous)-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Video_games" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Video_games"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Video games</span> </div> </a> <ul id="toc-Video_games-sublist" class="vector-toc-list"> <li id="toc-Hitbox" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Hitbox"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2.1</span> <span>Hitbox</span> </div> </a> <ul id="toc-Hitbox-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Collision detection</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 15 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-15" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">15 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Detekce_koliz%C3%AD" title="Detekce kolizí – Czech" lang="cs" hreflang="cs" data-title="Detekce kolizí" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Kollisionserkennung_(algorithmische_Geometrie)" title="Kollisionserkennung (algorithmische Geometrie) – German" lang="de" hreflang="de" data-title="Kollisionserkennung (algorithmische Geometrie)" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Detecci%C3%B3n_de_colisiones" title="Detección de colisiones – Spanish" lang="es" hreflang="es" data-title="Detección de colisiones" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/D%C3%A9tection_de_collision" title="Détection de collision – French" lang="fr" hreflang="fr" data-title="Détection de collision" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%B6%A9%EB%8F%8C_%EA%B0%90%EC%A7%80" title="충돌 감지 – Korean" lang="ko" hreflang="ko" data-title="충돌 감지" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E8%A1%9D%E7%AA%81%E5%88%A4%E5%AE%9A" title="衝突判定 – Japanese" lang="ja" hreflang="ja" data-title="衝突判定" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Kollisjonsdeteksjon" title="Kollisjonsdeteksjon – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Kollisjonsdeteksjon" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Wykrywanie_kolizji" title="Wykrywanie kolizji – Polish" lang="pl" hreflang="pl" data-title="Wykrywanie kolizji" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Detec%C3%A7%C3%A3o_de_colis%C3%A3o" title="Detecção de colisão – Portuguese" lang="pt" hreflang="pt" data-title="Detecção de colisão" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D0%BD%D0%B0%D1%80%D1%83%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D1%82%D0%BE%D0%BB%D0%BA%D0%BD%D0%BE%D0%B2%D0%B5%D0%BD%D0%B8%D0%B9" title="Обнаружение столкновений – Russian" lang="ru" hreflang="ru" data-title="Обнаружение столкновений" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Collision_detection" title="Collision detection – Simple English" lang="en-simple" hreflang="en-simple" data-title="Collision detection" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%82%E0%B8%B1%E0%B9%89%E0%B8%99%E0%B8%95%E0%B8%AD%E0%B8%99%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%95%E0%B8%A3%E0%B8%A7%E0%B8%88%E0%B8%AA%E0%B8%AD%E0%B8%9A%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%8A%E0%B8%99" title="ขั้นตอนวิธีการตรวจสอบการชน – Thai" lang="th" hreflang="th" data-title="ขั้นตอนวิธีการตรวจสอบการชน" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%92%D0%B8%D1%8F%D0%B2%D0%BB%D0%B5%D0%BD%D0%BD%D1%8F_%D0%B7%D1%96%D1%82%D0%BA%D0%BD%D0%B5%D0%BD%D1%8C" title="Виявлення зіткнень – Ukrainian" lang="uk" hreflang="uk" data-title="Виявлення зіткнень" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E7%A2%B0%E6%92%9E%E6%8E%A2%E6%B8%AC" title="碰撞探測 – Cantonese" lang="yue" hreflang="yue" data-title="碰撞探測" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E7%A2%B0%E6%92%9E%E5%81%B5%E6%B8%AC" title="碰撞偵測 – Chinese" lang="zh" hreflang="zh" data-title="碰撞偵測" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1550329#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Collision_detection" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Collision_detection" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Collision_detection"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Collision_detection&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Collision_detection&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Collision_detection"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Collision_detection&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Collision_detection&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Collision_detection" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Collision_detection" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Collision_detection&oldid=1259003655" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Collision_detection&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Collision_detection&id=1259003655&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCollision_detection"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCollision_detection"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Collision_detection&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Collision_detection&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1550329" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Term in computer science</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">This article is about collision detection in computational geometry. For collision detection in computer networks, see <a href="/wiki/Carrier-sense_multiple_access_with_collision_detection" title="Carrier-sense multiple access with collision detection">Carrier-sense multiple access with collision detection</a>.</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">"Hitbox" redirects here. For other uses, see <a href="/wiki/Hitbox_(disambiguation)" class="mw-disambig" title="Hitbox (disambiguation)">Hitbox (disambiguation)</a>.</div><style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><style data-mw-deduplicate="TemplateStyles:r1248332772">.mw-parser-output .multiple-issues-text{width:95%;margin:0.2em 0}.mw-parser-output .multiple-issues-text>.mw-collapsible-content{margin-top:0.3em}.mw-parser-output .compact-ambox .ambox{border:none;border-collapse:collapse;background-color:transparent;margin:0 0 0 1.6em!important;padding:0!important;width:auto;display:block}body.mediawiki .mw-parser-output .compact-ambox .ambox.mbox-small-left{font-size:100%;width:auto;margin:0}.mw-parser-output .compact-ambox .ambox .mbox-text{padding:0!important;margin:0!important}.mw-parser-output .compact-ambox .ambox .mbox-text-span{display:list-item;line-height:1.5em;list-style-type:disc}body.skin-minerva .mw-parser-output .multiple-issues-text>.mw-collapsible-toggle,.mw-parser-output .compact-ambox .ambox .mbox-image,.mw-parser-output .compact-ambox .ambox .mbox-imageright,.mw-parser-output .compact-ambox .ambox .mbox-empty-cell,.mw-parser-output .compact-ambox .hide-when-compact{display:none}</style><table class="box-Multiple_issues plainlinks metadata ambox ambox-content ambox-multiple_issues compact-ambox" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/40px-Ambox_important.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/60px-Ambox_important.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/80px-Ambox_important.svg.png 2x" data-file-width="40" data-file-height="40" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span"><div class="multiple-issues-text mw-collapsible"><b>This article has multiple issues.</b> Please help <b><a href="/wiki/Special:EditPage/Collision_detection" title="Special:EditPage/Collision detection">improve it</a></b> or discuss these issues on the <b><a href="/wiki/Talk:Collision_detection" title="Talk:Collision detection">talk page</a></b>. <small><i>(<a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove these messages</a>)</i></small> <div class="mw-collapsible-content"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Technical plainlinks metadata ambox ambox-style ambox-technical" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>may be too technical for most readers to understand</b>.<span class="hide-when-compact"> Please <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Collision_detection&action=edit">help improve it</a> to <a href="/wiki/Wikipedia:Make_technical_articles_understandable" title="Wikipedia:Make technical articles understandable">make it understandable to non-experts</a>, without removing the technical details.</span> <span class="date-container"><i>(<span class="date">March 2020</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Tone plainlinks metadata ambox ambox-style ambox-Tone" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section's <b>tone or style may not reflect the <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">encyclopedic tone</a> used on Wikipedia</b>.<span class="hide-when-compact"> See Wikipedia's <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">guide to writing better articles</a> for suggestions.</span> <span class="date-container"><i>(<span class="date">January 2023</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Tone plainlinks metadata ambox ambox-style ambox-Tone" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article's <b>tone or style may not reflect the <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">encyclopedic tone</a> used on Wikipedia</b>.<span class="hide-when-compact"> See Wikipedia's <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">guide to writing better articles</a> for suggestions.</span> <span class="date-container"><i>(<span class="date">August 2014</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> </div> </div><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p><b>Collision detection</b> is the <a href="/wiki/Computational_problem" title="Computational problem">computational problem</a> of detecting an <a href="/wiki/Intersection_(geometry)" title="Intersection (geometry)">intersection</a> of two or more objects in virtual space. More precisely, it deals with the questions of <i>if</i>, <i>when</i> and <i>where</i> two or more objects intersect. Collision detection is a classic problem of <a href="/wiki/Computational_geometry" title="Computational geometry">computational geometry</a> with applications in <a href="/wiki/Computer_graphics" title="Computer graphics">computer graphics</a>, <a href="/wiki/Physical_simulation" title="Physical simulation">physical simulation</a>, <a href="/wiki/Video_game" title="Video game">video games</a>, <a href="/wiki/Robotics" title="Robotics">robotics</a> (including <a href="/wiki/Autonomous_driving" class="mw-redirect" title="Autonomous driving">autonomous driving</a>) and <a href="/wiki/Computational_physics" title="Computational physics">computational physics</a>. Collision detection <a href="/wiki/Algorithm" title="Algorithm">algorithms</a> can be divided into operating on 2D or 3D spatial objects.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=1" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Billiards_balls.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Billiards_balls.jpg/200px-Billiards_balls.jpg" decoding="async" width="200" height="150" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Billiards_balls.jpg/300px-Billiards_balls.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Billiards_balls.jpg/400px-Billiards_balls.jpg 2x" data-file-width="1024" data-file-height="768" /></a><figcaption>Billiards balls hitting each other in a virtual space are a classic example where collision detection computations are needed</figcaption></figure><p>Collision detection is closely linked to calculating the <a href="/wiki/Euclidean_distance" title="Euclidean distance">distance</a> between objects, as two objects (or more) intersect when the distance between them reaches zero or even becomes negative.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Negative distance indicates that one object has penetrated another. Performing collision detection requires more context than just the distance between the objects. </p><p>Accurately identifying the points of contact on both objects' surfaces is also essential for the computation of a physically accurate <a href="/wiki/Collision_response" title="Collision response">collision response</a>. The complexity of this task increases with the level of detail in the objects' representations: the more intricate the model, the greater the computational cost.<sup id="cite_ref-:col0_3-0" class="reference"><a href="#cite_note-:col0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>Collision detection frequently involves dynamic objects, adding a temporal dimension to distance calculations. Instead of simply measuring distance between static objects, collision detection algorithms often aim to determine whether the objects’ motion will bring them to a point in time when their distance is zero—an operation that adds significant computational overhead.<sup id="cite_ref-:col1_4-0" class="reference"><a href="#cite_note-:col1-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:col0_3-1" class="reference"><a href="#cite_note-:col0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>In collision detection involving multiple objects, a naive approach would require detecting collisions for all pairwise combinations of objects. As the number of objects increases, the number of required comparisons grows rapidly: for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> objects, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{n(n-1)}/{2}"> <semantics> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </mrow> <annotation encoding="application/x-tex">{n(n-1)}/{2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a36be4280e3279159a18a156dd1535325fb905a5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.926ex; height:2.843ex;" alt="{n(n-1)}/{2}"></span> intersection tests are needed with a naive approach. This quadratic growth makes such an approach computationally expensive as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> increases.<sup id="cite_ref-:col1_4-1" class="reference"><a href="#cite_note-:col1-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:0_5-0" class="reference"><a href="#cite_note-:0-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p><p>Due to the complexity mentioned above, collision detection is computationally intensive process. Nevertheless, it is essential for interactive applications like video games, robotics, and real-time physics engines. To manage these computational demands, extensive efforts have gone into optimizing collision detection algorithms. </p><p>A commonly used approach towards accelerating the required computations is to divide the process into two phases: the <b>broad phase</b> and the <b>narrow phase</b>.<sup id="cite_ref-:col1_4-2" class="reference"><a href="#cite_note-:col1-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> The broad phase aims to answer the question of whether objects might collide, using a conservative but efficient approach to rule out pairs that clearly do not intersect, thus avoiding unnecessary calculations. </p><p>Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. Here, more precise algorithms determine whether these objects actually intersect. If they do, the narrow phase often calculates the exact time and location of the intersection. </p> <div class="mw-heading mw-heading2"><h2 id="Broad_phase">Broad phase</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=2" title="Edit section: Broad phase"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This phase aims at quickly finding objects or parts of objects for which it can be quickly determined that no further collision test is needed. A useful property of such approach is that it is <a href="/wiki/Output-sensitive_algorithm" title="Output-sensitive algorithm">output sensitive</a>. In the context of collision detection this means that the time complexity of the collision detection is proportional to the number of objects that are close to each other. An early example of that is the I-COLLIDE<sup id="cite_ref-:0_5-1" class="reference"><a href="#cite_note-:0-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> where the number of required narrow phase collision tests was <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n+m)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n+m)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d103b38ce2abfde793118c89cd4fac5c956b89d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.858ex; height:2.843ex;" alt="{\displaystyle O(n+m)}"></span> where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is the number of objects and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>m</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle m}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}"></span> is the number of objects at close proximity. This is a significant improvement over the quadratic complexity of the naive approach. </p> <div class="mw-heading mw-heading3"><h3 id="Spatial_partitioning">Spatial partitioning</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=3" title="Edit section: Spatial partitioning"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Several approaches can grouped under the <a href="/wiki/Spatial_partitioning" class="mw-redirect" title="Spatial partitioning">spatial partitioning</a> umbrella, which includes <a href="/wiki/Octree" title="Octree">octrees</a> (for 3D), <a href="/wiki/Quadtree" title="Quadtree">quadtrees</a> (for 2D) <a href="/wiki/Binary_space_partitioning" title="Binary space partitioning">binary space partitioning</a> (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Dynamic scenes and deformable objects require updating the partitioning which can add overhead. </p> <div class="mw-heading mw-heading3"><h3 id="Bounding_volume_hierarchy">Bounding volume hierarchy</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=4" title="Edit section: Bounding volume hierarchy"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Bounding_volume_hierarchy" title="Bounding volume hierarchy">Bounding Volume Hierarchy</a> (BVH) a tree structure over a set of <a class="mw-selflink-fragment" href="#Bounding_volumes">bounding volumes</a>. Collision is determined by doing a tree traversal starting from the root. If the bounding volume of the root doesn't intersect with the object of interest, the traversal can be stopped. If, however there is an intersection, the traversal proceeds and checks the branches for each there is an intersection. Branches for which there is no intersection with the bounding volume can be culled from further intersection test. Therefore multiple objects can be determined to not intersect at once. BVH can be used with deformable objects such as cloth or soft-bodies but the volume hierarchy has to be adjusted as the shape deforms. For deformable objects we need to be concerned about self-collisions or self intersections. BVH can be used for that end as well. Collision between two objects is computed by computing intersection between the bounding volumes of the root of the tree as there are collision we dive into the sub-trees that intersect. Exact collisions between the actual objects, or its parts (often triangles of a <a href="/wiki/Triangle_mesh" title="Triangle mesh">triangle mesh</a>) need to be computed only between intersecting leaves.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> The same approach works for pair wise collision and self-collisions. </p> <div class="mw-heading mw-heading3"><h3 id="Exploiting_temporal_coherence">Exploiting temporal coherence</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=5" title="Edit section: Exploiting temporal coherence"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>During the broad-phase, when the objects in the world move or deform, the data-structures used to cull collisions have to be updated. In cases where the changes between two frames or time-steps are small and the objects can approximated well with an <a href="/wiki/Axis-aligned_bounding_box" class="mw-redirect" title="Axis-aligned bounding box">axis-aligned bounding boxes</a> the <a href="/wiki/Sweep_and_prune" title="Sweep and prune">sweep and prune</a> algorithm<sup id="cite_ref-:0_5-2" class="reference"><a href="#cite_note-:0-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> can be a suitable approach. </p><p>Several key observation make the implementation efficient: Two bounding-boxes intersect <a href="/wiki/If_and_only_if" title="If and only if">if, and only if</a>, there is overlap along all three axes; overlap can be determined, for each axis separately, by sorting the intervals for all the boxes; and lastly, between two frames updates are typically small (making sorting algorithms optimized for almost-sorted lists suitable for this application). The algorithm keeps track of currently intersecting boxes, and as objects moves, re-sorting the intervals helps keep track of the status.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Pairwise_pruning">Pairwise pruning</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=6" title="Edit section: Pairwise pruning"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1248332772"><table class="box-Multiple_issues plainlinks metadata ambox ambox-content ambox-multiple_issues compact-ambox" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/40px-Ambox_important.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/60px-Ambox_important.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/80px-Ambox_important.svg.png 2x" data-file-width="40" data-file-height="40" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span"><div class="multiple-issues-text mw-collapsible"><b>This section has multiple issues.</b> Please help <b><a href="/wiki/Special:EditPage/Collision_detection" title="Special:EditPage/Collision detection">improve it</a></b> or discuss these issues on the <b><a href="/wiki/Talk:Collision_detection" title="Talk:Collision detection">talk page</a></b>. <small><i>(<a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove these messages</a>)</i></small> <div class="mw-collapsible-content"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Technical plainlinks metadata ambox ambox-style ambox-technical" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>may be too technical for most readers to understand</b>.<span class="hide-when-compact"> Please <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Collision_detection&action=edit">help improve it</a> to <a href="/wiki/Wikipedia:Make_technical_articles_understandable" title="Wikipedia:Make technical articles understandable">make it understandable to non-experts</a>, without removing the technical details.</span> <span class="date-container"><i>(<span class="date">March 2020</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Tone plainlinks metadata ambox ambox-style ambox-Tone" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section's <b>tone or style may not reflect the <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">encyclopedic tone</a> used on Wikipedia</b>.<span class="hide-when-compact"> See Wikipedia's <a href="/wiki/Wikipedia:Writing_better_articles#Tone" title="Wikipedia:Writing better articles">guide to writing better articles</a> for suggestions.</span> <span class="date-container"><i>(<span class="date">January 2024</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Collision_detection" title="Special:EditPage/Collision detection">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span> <span class="date-container"><i>(<span class="date">July 2024</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> </div> </div><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S={S_{1},S_{2},\dots ,S_{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S={S_{1},S_{2},\dots ,S_{n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/82ab8405af4ab712c8b4d4e47a658ed87bc00832" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.412ex; height:2.509ex;" alt="{\displaystyle S={S_{1},S_{2},\dots ,S_{n}}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T={T_{1},T_{2},\dots ,T_{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T={T_{1},T_{2},\dots ,T_{n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b479580c6c1db84e33c21af1cda4536b0a719ee7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.346ex; height:2.509ex;" alt="{\displaystyle T={T_{1},T_{2},\dots ,T_{n}}}"></span> (for simplicity, we will assume that each set has the same number of triangles.) </p><p>The obvious thing to do is to check all triangles <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>S</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/222db49df2eefdb67737ba2d2dbd221a1bae0bf0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.335ex; height:2.843ex;" alt="{\displaystyle S_{j}}"></span> against all triangles <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/51cc852c6e446a4871f78e05492699a9525b9acb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.446ex; height:2.509ex;" alt="{\displaystyle T_{k}}"></span> for collisions, but this involves <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9810bbdafe4a6a8061338db0f74e25b7952620" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}"></span> comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles we need to check. </p><p>The most widely used family of algorithms is known as the <i>hierarchical bounding volumes</i> method. As a preprocessing step, for each object (in our example, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>) we will calculate a <a href="/wiki/Bounding_volume_hierarchy" title="Bounding volume hierarchy">hierarchy of bounding volumes</a>. Then, at each time step, when we need to check for collisions between <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>, the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For simplicity, we will give an example using bounding spheres, although it has been noted that spheres are undesirable in many cases.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (June 2008)">citation needed</span></a></i>]</sup> </p><p>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}"></span> is a set of triangles, we can pre-calculate a bounding sphere <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(E)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(E)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7efcbf46eeaf242b4a57e27413d69d8de0b20370" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.349ex; height:2.843ex;" alt="{\displaystyle B(E)}"></span>. There are many ways of choosing <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(E)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(E)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7efcbf46eeaf242b4a57e27413d69d8de0b20370" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.349ex; height:2.843ex;" alt="{\displaystyle B(E)}"></span>, we only assume that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(E)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(E)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7efcbf46eeaf242b4a57e27413d69d8de0b20370" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.349ex; height:2.843ex;" alt="{\displaystyle B(E)}"></span> is a sphere that completely contains <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}"></span> and is as small as possible. </p><p>Ahead of time, we can compute <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(S)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(S)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/93fe493dc8f9d402ebc492def1832a60a21e9451" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.073ex; height:2.843ex;" alt="{\displaystyle B(S)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/58329c775b28dba986ce47422a4eeca8ef9613b3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.21ex; height:2.843ex;" alt="{\displaystyle B(T)}"></span>. Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>. This is not much better than an <i>n</i>-body pruning algorithm, however. </p><p>If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E={E_{1},E_{2},\dots ,E_{m}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E={E_{1},E_{2},\dots ,E_{m}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/597c325e99f71c1aea40febe815eb214051f2114" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.015ex; height:2.509ex;" alt="{\displaystyle E={E_{1},E_{2},\dots ,E_{m}}}"></span> is a set of triangles, then we can split it into two halves <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(E):={E_{1},E_{2},\dots ,E_{m/2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> <mo>:=</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msub> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L(E):={E_{1},E_{2},\dots ,E_{m/2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e852003bdd81ec5e8f5f7bbfef0270d4553c5e43" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:25.698ex; height:3.176ex;" alt="{\displaystyle L(E):={E_{1},E_{2},\dots ,E_{m/2}}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> <mo>:=</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dc13274542c37a95cacfc6db242cbfe64c61ad7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:31.322ex; height:3.176ex;" alt="{\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}}"></span>. We can do this to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span>, and we can calculate (ahead of time) the bounding spheres <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(L(S)),B(R(S))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>L</mi> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>,</mo> <mi>B</mi> <mo stretchy="false">(</mo> <mi>R</mi> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(L(S)),B(R(S))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c85ca2c8903a9e4e3123cd82d28d8a4aada8a7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.144ex; height:2.843ex;" alt="{\displaystyle B(L(S)),B(R(S))}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(L(T)),B(R(T))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>L</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>,</mo> <mi>B</mi> <mo stretchy="false">(</mo> <mi>R</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(L(T)),B(R(T))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6e8e5f35a14ee07f0e575bbca7ab8f204ca2c841" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.419ex; height:2.843ex;" alt="{\displaystyle B(L(T)),B(R(T))}"></span>. The hope here is that these bounding spheres are much smaller than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(S)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(S)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/93fe493dc8f9d402ebc492def1832a60a21e9451" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.073ex; height:2.843ex;" alt="{\displaystyle B(S)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/58329c775b28dba986ce47422a4eeca8ef9613b3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.21ex; height:2.843ex;" alt="{\displaystyle B(T)}"></span>. And, if, for instance, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(S)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(S)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/93fe493dc8f9d402ebc492def1832a60a21e9451" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.073ex; height:2.843ex;" alt="{\displaystyle B(S)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(L(T))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>L</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(L(T))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0557b28f96fd600a89c1d9081bdf7f81488f2bb1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.602ex; height:2.843ex;" alt="{\displaystyle B(L(T))}"></span> do not intersect, then there is no sense in checking any triangle in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> against any triangle in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L(T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48ba63c960059a240ba065883c25abf1dad569c0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.028ex; height:2.843ex;" alt="{\displaystyle L(T)}"></span>. </p><p>As a <a href="/wiki/Precomputation" title="Precomputation">precomputation</a>, we can take each physical body (represented by a set of triangles) and recursively decompose it into a <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a>, where each node <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> represents a set of triangles, and its two children represent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5e2b06859874cbba17603928fd3097092ebd2895" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.456ex; height:2.843ex;" alt="{\displaystyle L(N)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d694574fe2f6db83f7da2f5d5325f26f61f7cf21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.637ex; height:2.843ex;" alt="{\displaystyle R(N)}"></span>. At each node in the tree, we can pre-compute the bounding sphere <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f885668a7b8825f61b83f4a8d556c87b9702714e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.637ex; height:2.843ex;" alt="{\displaystyle B(N)}"></span>. </p><p>When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles. </p><p>Many variants of the algorithms are obtained by choosing something other than a sphere for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B(T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/58329c775b28dba986ce47422a4eeca8ef9613b3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.21ex; height:2.843ex;" alt="{\displaystyle B(T)}"></span>. If one chooses <a href="/wiki/Axis-aligned_bounding_box" class="mw-redirect" title="Axis-aligned bounding box">axis-aligned bounding boxes</a>, one gets AABBTrees. <a href="/wiki/Oriented_bounding_box" class="mw-redirect" title="Oriented bounding box">Oriented bounding box</a> trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as <a href="/wiki/Spline_(mathematics)" title="Spline (mathematics)">splines</a> instead of simple triangles. </p><p><br /> </p> <div class="mw-heading mw-heading2"><h2 id="Narrow_phase">Narrow phase</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=7" title="Edit section: Narrow phase"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Objects that cannot be definitively separated in the broad phase are passed to the narrow phase. In this phase, the objects under consideration are relatively close to each other. Still, attempts to quickly determine if a full intersection is needed are employed first. This step is sometimes referred to as mid-phase.<sup id="cite_ref-:col1_4-3" class="reference"><a href="#cite_note-:col1-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Once these tests passed (e.g the pair of objects may be colliding) more precise algorithms determine whether these objects actually intersect. If they do, the narrow phase often calculates the exact time and location of the intersection. </p> <div class="mw-heading mw-heading3"><h3 id="Bounding_volumes">Bounding volumes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=8" title="Edit section: Bounding volumes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A quick way to potentially avoid a needless expensive computation is to check if the bounding volume enclosing the two objects intersect. If they don't, there is not need to check the actual objects. However, if the <a href="/wiki/Bounding_volume" title="Bounding volume">bounding volume</a> intersect, the more expensive computation has to be performed. In order for the bounding-volume test to add value, two properties need to be balanced: a) the cost of intersecting the bounding volume needs to be low and b) the bounding volume needs to be tight enough so that the number of 'false positive' intersection will be low. A false positive intersection in this case means that the bounding volume intersect but the actual objects do not. Different bounding volume types offer different trade-offs for these properties. </p><p><a href="/wiki/Minimum_bounding_box#Axis-aligned_minimum_bounding_box" title="Minimum bounding box">Axis-Align Bounding Boxes (AABB)</a> and <a href="/wiki/Cuboid" title="Cuboid">cuboids</a> are popular due to their simplicity and quick intersection tests. <sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Bounding volumes such as <a href="/wiki/Minimum_bounding_box#Arbitrarily_oriented_minimum_bounding_box" title="Minimum bounding box"> Oriented Bounding Boxes (OBB)</a>, <a href="/wiki/Bounding_volume#Common_types" title="Bounding volume">K-DOPs</a> and Convex-hulls offer a tighter approximation of the enclosed shape at the expense of a more elaborate intersection test. </p><p>Bounding volumes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping bounding volumes need be compared in detail.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Computing collision or overlap between bounding volumes involves additional computations, therefore, in order for it to beneficial we need the bounding volume to be relatively tight and the computation overhead to due the collisions to be low. </p> <div class="mw-heading mw-heading3"><h3 id="Exact_pairwise_collision_detection">Exact pairwise collision detection</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=9" title="Edit section: Exact pairwise collision detection"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1248666159">.mw-parser-output .tfd-dated{font-size:85%}.mw-parser-output .tfd-default{border-bottom:1px solid var(--border-color-base,#a2a9b1);clear:both;text-align:center}.mw-parser-output .tfd-tiny{font-weight:bold}.mw-parser-output .tfd-inline{border:1px solid var(--border-color-base,#a2a9b1)}.mw-parser-output .tfd-sidebar{border-bottom:1px solid var(--border-color-base,#a2a9b1);text-align:center;position:relative}@media(min-width:640px){.mw-parser-output .tfd-sidebar{clear:right;float:right;width:22em}}</style><p><span class="tfd tfd-dated tfd-inline">‹The <a href="/wiki/Help:Template" title="Help:Template">template</a> <i><a href="/wiki/Template:Manual" title="Template:Manual">Manual</a></i> is being <a href="/wiki/Wikipedia:Templates_for_discussion/Log/2024_November_25#Template:Manual" title="Wikipedia:Templates for discussion/Log/2024 November 25">considered for merging</a>.›</span> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"></p><table class="box-Manual plainlinks metadata ambox ambox-style" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>is written like <a href="/wiki/Wikipedia:What_Wikipedia_is_not#GUIDE" title="Wikipedia:What Wikipedia is not">a manual or guide</a>.</b><span class="hide-when-compact"> Please help <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Collision_detection&action=edit">rewrite this section</a> and remove advice or instruction.</span> <span class="date-container"><i>(<span class="date">January 2024</span>)</i></span></div></td></tr></tbody></table> <p>Objects for which pruning approaches could not rule out the possibility of a collision have to undergo an exact collision detection computation. </p> <div class="mw-heading mw-heading4"><h4 id="Collision_detection_between_convex_objects">Collision detection between convex objects</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=10" title="Edit section: Collision detection between convex objects"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>According to the <a href="/wiki/Hyperplane_separation_theorem" title="Hyperplane separation theorem">separating planes theorem</a>, for any two disjoint <a href="/wiki/Convex_set" title="Convex set">convex</a> objects, there exists a plane so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This property allows the development of efficient collision detection algorithms between convex objects. Several algorithms are available for finding the closest points on the surface of two convex polyhedral objects - and determining collision. Early work by <a href="/wiki/Ming_C._Lin" title="Ming C. Lin">Ming C. Lin</a><sup id="cite_ref-:1_11-0" class="reference"><a href="#cite_note-:1-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> that used a variation on the <a href="/wiki/Simplex_algorithm" title="Simplex algorithm">simplex algorithm</a> from <a href="/wiki/Linear_programming" title="Linear programming">linear programming</a> and the <a href="/wiki/Gilbert-Johnson-Keerthi_distance_algorithm" class="mw-redirect" title="Gilbert-Johnson-Keerthi distance algorithm">Gilbert-Johnson-Keerthi distance algorithm</a><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> are two such examples. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, and every step is initialized from the previous collision check<sup id="cite_ref-:1_11-1" class="reference"><a href="#cite_note-:1-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>. </p><p>The result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles. </p> <div class="mw-heading mw-heading3"><h3 id="A_priori_pruning">A priori pruning</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=11" title="Edit section: A priori pruning"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution. </p><p>Pruning is also desirable here, both <i>n</i>-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying physical system into consideration. </p><p>When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical <a href="/wiki/Root-finding_algorithm" title="Root-finding algorithm">root-finding algorithm</a> to compute the instant of impact. </p><p>As an example, consider two triangles moving in time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57cf3bc20cd19af2cbaf28273b6d6c4ee539a5ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.56ex; height:2.843ex;" alt="{\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>6</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46b9e9b93dad83ae2e340de805e1d30df097407b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.56ex; height:2.843ex;" alt="{\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}"></span>. At any point in time, the two triangles can be checked for intersection using the twenty planes previously mentioned. However, we can do better, since these twenty planes can all be tracked in time. If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(u,v,w)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>,</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P(u,v,w)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/04d09d6d0ab81fe806f172ee0eaec4af9c58402f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.744ex; height:2.843ex;" alt="{\displaystyle P(u,v,w)}"></span> is the plane going through points <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u,v,w}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>,</mo> <mi>w</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u,v,w}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4cabca98f60f9ee828adb0d73276eb90eb2ee56" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.189ex; height:2.009ex;" alt="{\displaystyle u,v,w}"></span> in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f936ddf584f8f3dd2a0ed08917001b7a404c10b5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.732ex; height:2.676ex;" alt="{\displaystyle \mathbb {R} ^{3}}"></span> then there are twenty planes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo stretchy="false">(</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc6557c773b8bc30821d876fadf5b2a06a047ddf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:19.75ex; height:3.009ex;" alt="{\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}"></span> to track. Each plane needs to be tracked against three vertices, this gives sixty values to track. Using a root finder on these sixty functions produces the exact collision times for the two given triangles and the two given trajectory. We note here that if the trajectories of the vertices are assumed to be linear polynomials in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>t</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/65658b7b223af9e1acc877d848888ecdb4466560" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}"></span> then the final sixty functions are in fact cubic polynomials, and in this exceptional case, it is possible to locate the exact collision time using the formula for the roots of the cubic. Some numerical analysts suggest that using the formula for the roots of the cubic is not as numerically stable as using a root finder for polynomials.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (June 2008)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading3"><h3 id="Triangle_centroid_segments">Triangle centroid segments</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=12" title="Edit section: Triangle centroid segments"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <a href="/wiki/Triangle_mesh" title="Triangle mesh">triangle mesh</a> object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh. A triangle centroid is a center of mass location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters. Given centroid points in both object and target it is possible to define the line segment connecting these two points. </p><p>The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian coordinates <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},y_{1},z_{1})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x_{1},y_{1},z_{1})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/781d7569148878d5fab8e65498162edcc5430791" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.59ex; height:2.843ex;" alt="{\displaystyle (x_{1},y_{1},z_{1})}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{2},y_{2},z_{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x_{2},y_{2},z_{2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b6c761bb04bd0bf983b9b8e83310e5407b7426ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.59ex; height:2.843ex;" alt="{\displaystyle (x_{2},y_{2},z_{2})}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{3},y_{3},z_{3})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x_{3},y_{3},z_{3})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94ba1a3c9bf8723b8006201b672500819c041d87" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.59ex; height:2.843ex;" alt="{\displaystyle (x_{3},y_{3},z_{3})}"></span> then the centroid is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </mfrac> </mrow> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </mfrac> </mrow> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo stretchy="false">(</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </mfrac> </mrow> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f128a8003a85f8125a796cd8a152771412fc81ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:50.606ex; height:6.343ex;" alt="{\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)}"></span>. </p><p>Here is the function for a line segment distance between two 3D points. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">d</mi> <mi mathvariant="normal">i</mi> <mi mathvariant="normal">s</mi> <mi mathvariant="normal">t</mi> <mi mathvariant="normal">a</mi> <mi mathvariant="normal">n</mi> <mi mathvariant="normal">c</mi> <mi mathvariant="normal">e</mi> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mo stretchy="false">(</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>z</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mo stretchy="false">(</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/db58ca90620dc84957b53a6d8a4351cbf678e955" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:49.92ex; height:4.843ex;" alt="{\displaystyle \mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}"></span> </p><p>Here the length/distance of the segment is an adjustable "hit" criteria size of segment. As the objects approach the length decreases to the threshold value. A triangle sphere becomes the effective geometry test. A sphere centered at the centroid can be sized to encompass all the triangle's vertices. </p> <div class="mw-heading mw-heading2"><h2 id="Usage">Usage</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=13" title="Edit section: Usage"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Collision_detection_in_computer_simulation">Collision detection in computer simulation</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=14" title="Edit section: Collision detection in computer simulation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Collision_detection" title="Special:EditPage/Collision detection">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span> <span class="date-container"><i>(<span class="date">January 2024</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. This is very CPU intensive for low softness materials. Some simulators estimate the time of collision by <a href="/wiki/Linear_interpolation" title="Linear interpolation">linear interpolation</a>, <a href="/wiki/Rollback_(data_management)" title="Rollback (data management)">roll back</a> the simulation, and calculate the collision by the more abstract methods of <a href="/wiki/Conservation_laws" class="mw-redirect" title="Conservation laws">conservation laws</a>. </p><p>Some iterate the linear interpolation (<a href="/wiki/Newton%27s_method" title="Newton's method">Newton's method</a>) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in <a href="/wiki/Air_traffic_control" title="Air traffic control">air traffic control</a>. </p><p>After an inelastic collision, special states of sliding and resting can occur and, for example, the <a href="/wiki/Open_Dynamics_Engine" title="Open Dynamics Engine">Open Dynamics Engine</a> uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a <a href="/wiki/Scene_graph" title="Scene graph">scene graph</a> avoids drift. </p><p>In other words, physical simulators usually function one of two ways: where the collision is detected <i><a href="/wiki/Empirical_evidence" title="Empirical evidence">a posteriori</a></i> (after the collision occurs) or <i><a href="/wiki/A_priori_and_a_posteriori" title="A priori and a posteriori">a priori</a></i> (before the collision occurs). In addition to the <i>a posteriori</i> and <i>a priori</i> distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than <i>a posteriori</i> and <i>a priori</i>. </p> <div class="mw-heading mw-heading4"><h4 id="A_posteriori_(discrete)_versus_a_priori_(continuous)"><span id="A_posteriori_.28discrete.29_versus_a_priori_.28continuous.29"></span><i>A posteriori</i> (discrete) versus <i>a priori</i> (continuous)</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=15" title="Edit section: A posteriori (discrete) versus a priori (continuous)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Collision_detection" title="Special:EditPage/Collision detection">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span> <span class="date-container"><i>(<span class="date">August 2022</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>In the <i>a posteriori</i> case, the physical simulation is advanced by a small step, then checked to see if any objects are intersecting or visibly considered intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are "fixed" to account for the collision. This method is called <i>a posteriori</i> because it typically misses the actual instant of collision, and only catches the collision after it has actually happened. </p><p>In the <i>a priori</i> methods, there is a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. This is called <i>a priori</i> because the collision detection algorithm calculates the instants of collision before it updates the configuration of the physical bodies. </p><p>The main benefits of the <i>a posteriori</i> methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the <i>a posteriori</i> algorithms are in effect one dimension simpler than the <i>a priori</i> algorithms. An <i>a priori</i> algorithm must deal with the time variable, which is absent from the <i>a posteriori</i> problem. </p><p>On the other hand, <i>a posteriori</i> algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small. </p><p>The benefits of the <i>a priori</i> algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical <a href="/wiki/Root-finding_algorithm" title="Root-finding algorithm">root finder</a> is usually involved. </p><p>Some objects are in <i>resting contact</i>, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (<i>a posteriori</i>) or slide (<i>a priori</i>) and their relative motion is below a threshold, friction becomes <a href="/wiki/Stiction" title="Stiction">stiction</a> and both objects are arranged in the same branch of the <a href="/wiki/Scene_graph" title="Scene graph">scene graph</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Video_games">Video games</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=16" title="Edit section: Video games"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Video games have to split their very limited computing time between several tasks. Despite this resource limit, and the use of relatively primitive collision detection algorithms, programmers have been able to create believable, if inexact, systems for use in games.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (August 2014)">citation needed</span></a></i>]</sup> </p><p>For a long time, video games had a very limited number of objects to treat, and so checking all pairs was not a problem. In two-dimensional games, in some cases, the hardware was able to efficiently detect and report overlapping pixels between <a href="/wiki/Sprite_(computer_graphics)" title="Sprite (computer graphics)">sprites</a> on the screen.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> In other cases, simply tiling the screen and binding each <i>sprite</i> into the tiles it overlaps provides sufficient pruning, and for pairwise checks, bounding rectangles or circles called <a href="/wiki/Hitbox" class="mw-redirect" title="Hitbox">hitboxes</a> are used and deemed sufficiently accurate. </p><p>Three-dimensional games have used spatial partitioning methods for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>-body pruning, and for a long time used one or a few spheres per actual 3D object for pairwise checks. Exact checks are very rare, except in games attempting to <a href="/wiki/Simulation_game" class="mw-redirect" title="Simulation game">simulate</a> reality closely. Even then, exact checks are not necessarily used in all cases. </p><p>Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use <i>a posteriori</i> collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, they might be simply moved back to their last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow them to move that far. </p><p>In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, <a href="/wiki/Binary_space_partitioning" title="Binary space partitioning">binary space partitioning</a> trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately. </p><p>A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed <a href="/wiki/Racing_game" title="Racing game">racecar video game</a>, from one simulation step to the next, it is conceivable that the cars would advance a substantial distance along the race track. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that posteriori algorithms require isn't implemented correctly, resulting in <a href="/wiki/Software_bug" title="Software bug">bugs</a> that can trap characters in walls or allow them to pass through them and fall into an endless void where there may or may not be a deadly <a href="/wiki/Bottomless_pit_(video_gaming)" class="mw-redirect" title="Bottomless pit (video gaming)">bottomless pit</a>, sometimes referred to as "black hell", "blue hell", or "green hell", depending on the predominant color. These are the hallmarks of a failing collision detection and physical simulation system. <i><a href="/wiki/Big_Rigs:_Over_the_Road_Racing" title="Big Rigs: Over the Road Racing">Big Rigs: Over the Road Racing</a></i> is an infamous example of a game with a failing or possibly missing collision detection system. </p> <div class="mw-heading mw-heading4"><h4 id="Hitbox">Hitbox</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=17" title="Edit section: Hitbox"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <b>hitbox</b> is an invisible shape commonly used in <a href="/wiki/Video_game" title="Video game">video games</a> for real-time collision detection; it is a type of bounding box. It is often a rectangle (in 2D games) or <a href="/wiki/Cuboid" title="Cuboid">cuboid</a> (in 3D) that is attached to and follows a point on a visible object (such as a model or a sprite). Circular or spheroidial shapes are also common, though they are still most often called "boxes". It is common for animated objects to have hitboxes attached to each moving part to ensure accuracy during motion.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Reliable_sources" title="Wikipedia:Reliable sources"><span title="The material near this tag may rely on an unreliable source. (March 2018)">unreliable source?</span></a></i>]</sup> </p><p>Hitboxes are used to detect "one-way" collisions such as a character being hit by a punch or a bullet. They are unsuitable for the detection of collisions with feedback (e.g. bumping into a wall) due to the difficulty experienced by both humans and <a href="/wiki/Artificial_intelligence_(video_games)" class="mw-redirect" title="Artificial intelligence (video games)">AI</a> in managing a hitbox's ever-changing locations; these sorts of collisions are typically handled with much simpler <a href="/wiki/Axis-aligned_bounding_box" class="mw-redirect" title="Axis-aligned bounding box">axis-aligned bounding boxes</a> instead. Players may use the term "hitbox" to refer to these types of interactions regardless. </p><p>A <b>hurtbox</b> is a hitbox used to detect incoming sources of damage. In this context, the term <i>hitbox</i> is typically reserved for those which deal damage. For example, an attack may only land if the hitbox around an attacker's punch connects with one of the opponent's hurtboxes on their body, while opposing hitboxes colliding may result in the players trading or cancelling blows, and opposing hurtboxes do not interact with each other. The term is not standardized across the industry; some games reverse their definitions of <i>hitbox</i> and <i>hurtbox</i>, while others only use "hitbox" for both sides. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=18" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1184024115">.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}</style><div class="div-col"> <ul><li><a href="/wiki/Collision_response" title="Collision response">Collision response</a></li> <li><a href="/wiki/Hit-testing" title="Hit-testing">Hit-testing</a></li> <li><a href="/wiki/Bounding_volume" title="Bounding volume">Bounding volume</a></li> <li><a href="/wiki/Game_physics" title="Game physics">Game physics</a></li> <li><a href="/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm" title="Gilbert–Johnson–Keerthi distance algorithm">Gilbert–Johnson–Keerthi distance algorithm</a></li> <li><a href="/wiki/Minkowski_Portal_Refinement" title="Minkowski Portal Refinement">Minkowski Portal Refinement</a></li> <li><a href="/wiki/Physics_engine" title="Physics engine">Physics engine</a></li> <li><a href="/wiki/Lubachevsky%E2%80%93Stillinger_algorithm" title="Lubachevsky–Stillinger algorithm">Lubachevsky–Stillinger algorithm</a></li> <li><a href="/wiki/Ragdoll_physics" title="Ragdoll physics">Ragdoll physics</a></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=19" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFTeschnerKimmerleHeidelbergerZachmann2005" class="citation journal cs1">Teschner, M.; Kimmerle, S.; Heidelberger, B.; Zachmann, G.; Raghupathi, L.; Fuhrmann, A.; Cani, M.-P.; Faure, F.; Magnenat-Thalmann, N.; Strasser, W.; Volino, P. (2005). <a rel="nofollow" class="external text" href="https://hal.inria.fr/inria-00394479/document">"Collision Detection for Deformable Objects"</a>. <i>Computer Graphics Forum</i>. <b>24</b>: 61–81. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.2505">10.1.1.58.2505</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fj.1467-8659.2005.00829.x">10.1111/j.1467-8659.2005.00829.x</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1359430">1359430</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computer+Graphics+Forum&rft.atitle=Collision+Detection+for+Deformable+Objects&rft.volume=24&rft.pages=61-81&rft.date=2005&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.58.2505%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1359430%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1111%2Fj.1467-8659.2005.00829.x&rft.aulast=Teschner&rft.aufirst=M.&rft.au=Kimmerle%2C+S.&rft.au=Heidelberger%2C+B.&rft.au=Zachmann%2C+G.&rft.au=Raghupathi%2C+L.&rft.au=Fuhrmann%2C+A.&rft.au=Cani%2C+M.-P.&rft.au=Faure%2C+F.&rft.au=Magnenat-Thalmann%2C+N.&rft.au=Strasser%2C+W.&rft.au=Volino%2C+P.&rft_id=https%3A%2F%2Fhal.inria.fr%2Finria-00394479%2Fdocument&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGoodmanO'RourkeTóth2018" class="citation book cs1">Goodman, Jacob E.; O'Rourke, Joseph; Tóth, Csaba D., eds. (2018). "39". <a rel="nofollow" class="external text" href="https://www.csun.edu/~ctoth/Handbook/HDCG3.html"><i>Handbook of discrete and computational geometry</i></a>. Discrete mathematics and its applications (3rd ed.). Boca Raton London New York: CRC Press, Taylor & Francis Group, a Chapman & Hall book. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4987-1139-5" title="Special:BookSources/978-1-4987-1139-5"><bdi>978-1-4987-1139-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=39&rft.btitle=Handbook+of+discrete+and+computational+geometry&rft.place=Boca+Raton+London+New+York&rft.series=Discrete+mathematics+and+its+applications&rft.edition=3rd&rft.pub=CRC+Press%2C+Taylor+%26+Francis+Group%2C+a+Chapman+%26+Hall+book&rft.date=2018&rft.isbn=978-1-4987-1139-5&rft_id=https%3A%2F%2Fwww.csun.edu%2F~ctoth%2FHandbook%2FHDCG3.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-:col0-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-:col0_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:col0_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAndrewsErlebenFerguson2022" class="citation book cs1">Andrews, Sheldon; Erleben, Kenny; Ferguson, Zachary (2022-08-02). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/3532720.3535640">"Contact and friction simulation for computer graphics"</a>. <i>ACM SIGGRAPH 2022 Courses</i>. ACM. pp. 1–172. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3532720.3535640">10.1145/3532720.3535640</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-9362-1" title="Special:BookSources/978-1-4503-9362-1"><bdi>978-1-4503-9362-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Contact+and+friction+simulation+for+computer+graphics&rft.btitle=ACM+SIGGRAPH+2022+Courses&rft.pages=1-172&rft.pub=ACM&rft.date=2022-08-02&rft_id=info%3Adoi%2F10.1145%2F3532720.3535640&rft.isbn=978-1-4503-9362-1&rft.aulast=Andrews&rft.aufirst=Sheldon&rft.au=Erleben%2C+Kenny&rft.au=Ferguson%2C+Zachary&rft_id=https%3A%2F%2Fdl.acm.org%2Fdoi%2F10.1145%2F3532720.3535640&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-:col1-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-:col1_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:col1_4-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:col1_4-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-:col1_4-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHadapEberleVolinoLin2004" class="citation book cs1">Hadap, Sunil; Eberle, Dave; Volino, Pascal; Lin, Ming C.; Redon, Stephane; Ericson, Christer (2004-08-08). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/1103900.1103915">"Collision detection and proximity queries"</a>. <i>ACM SIGGRAPH 2004 Course Notes</i>. ACM. p. 15. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1103900.1103915">10.1145/1103900.1103915</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-7801-7" title="Special:BookSources/978-1-4503-7801-7"><bdi>978-1-4503-7801-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Collision+detection+and+proximity+queries&rft.btitle=ACM+SIGGRAPH+2004+Course+Notes&rft.pages=15&rft.pub=ACM&rft.date=2004-08-08&rft_id=info%3Adoi%2F10.1145%2F1103900.1103915&rft.isbn=978-1-4503-7801-7&rft.aulast=Hadap&rft.aufirst=Sunil&rft.au=Eberle%2C+Dave&rft.au=Volino%2C+Pascal&rft.au=Lin%2C+Ming+C.&rft.au=Redon%2C+Stephane&rft.au=Ericson%2C+Christer&rft_id=https%3A%2F%2Fdl.acm.org%2Fdoi%2F10.1145%2F1103900.1103915&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-:0-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_5-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCohenLinManochaPonamgi1995" class="citation book cs1">Cohen, Jonathan D.; Lin, Ming C.; Manocha, Dinesh; Ponamgi, Madhav (1995). <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?doid=199404.199437">"I-COLLIDE: An interactive and exact collision detection system for large-scale environments"</a>. <i>Proceedings of the 1995 symposium on Interactive 3D graphics - SI3D '95</i>. ACM Press. pp. 189–ff. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F199404.199437">10.1145/199404.199437</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-89791-736-0" title="Special:BookSources/978-0-89791-736-0"><bdi>978-0-89791-736-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=I-COLLIDE%3A+An+interactive+and+exact+collision+detection+system+for+large-scale+environments&rft.btitle=Proceedings+of+the+1995+symposium+on+Interactive+3D+graphics+-+SI3D+%2795&rft.pages=189-ff&rft.pub=ACM+Press&rft.date=1995&rft_id=info%3Adoi%2F10.1145%2F199404.199437&rft.isbn=978-0-89791-736-0&rft.aulast=Cohen&rft.aufirst=Jonathan+D.&rft.au=Lin%2C+Ming+C.&rft.au=Manocha%2C+Dinesh&rft.au=Ponamgi%2C+Madhav&rft_id=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fdoid%3D199404.199437&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAkenine-MöllerHainesHoffmanPesce2018" class="citation book cs1">Akenine-Möller, Tomas; Haines, Eric; Hoffman, Naty; Pesce, Angelo; Iwanicki, Michał; Hillaire, Sébastien (2018). <a rel="nofollow" class="external text" href="https://www.realtimerendering.com"><i>Real-time rendering</i></a>. An A K Peters book (4th ed.). Boca Raton London New York: CRC Press, Taylor & Francis Group. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-138-62700-0" title="Special:BookSources/978-1-138-62700-0"><bdi>978-1-138-62700-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Real-time+rendering&rft.place=Boca+Raton+London+New+York&rft.series=An+A+K+Peters+book&rft.edition=4th&rft.pub=CRC+Press%2C+Taylor+%26+Francis+Group&rft.date=2018&rft.isbn=978-1-138-62700-0&rft.aulast=Akenine-M%C3%B6ller&rft.aufirst=Tomas&rft.au=Haines%2C+Eric&rft.au=Hoffman%2C+Naty&rft.au=Pesce%2C+Angelo&rft.au=Iwanicki%2C+Micha%C5%82&rft.au=Hillaire%2C+S%C3%A9bastien&rft_id=https%3A%2F%2Fwww.realtimerendering.com&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKlosowskiHeldMitchellSowizral1998" class="citation journal cs1">Klosowski, James T; Held, Martin; Mitchell, Joseph S.B.; Sowizral, Henry; Zikan, Karel (1998). "Efficient collision detection using bounding volume hierarchies of k-DOPs". <i>IEEE Transactions on Visualization and Computer Graphics</i>. <b>4</b> (1). IEEE: 21–36. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F2945.675649">10.1109/2945.675649</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Visualization+and+Computer+Graphics&rft.atitle=Efficient+collision+detection+using+bounding+volume+hierarchies+of+k-DOPs&rft.volume=4&rft.issue=1&rft.pages=21-36&rft.date=1998&rft_id=info%3Adoi%2F10.1109%2F2945.675649&rft.aulast=Klosowski&rft.aufirst=James+T&rft.au=Held%2C+Martin&rft.au=Mitchell%2C+Joseph+S.B.&rft.au=Sowizral%2C+Henry&rft.au=Zikan%2C+Karel&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFEricson2004" class="citation book cs1">Ericson, Christer (22 December 2004). <a rel="nofollow" class="external text" href="https://realtimecollisiondetection.net/books/rtcd/"><i>Real-time collision detection</i></a>. Morgan Kaufmann series in interactive 3D technology (Nachdr. ed.). Amsterdam Heidelberg: Elsevier. pp. 329–338. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-55860-732-3" title="Special:BookSources/978-1-55860-732-3"><bdi>978-1-55860-732-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Real-time+collision+detection&rft.place=Amsterdam+Heidelberg&rft.series=Morgan+Kaufmann+series+in+interactive+3D+technology&rft.pages=329-338&rft.edition=Nachdr.&rft.pub=Elsevier&rft.date=2004-12-22&rft.isbn=978-1-55860-732-3&rft.aulast=Ericson&rft.aufirst=Christer&rft_id=https%3A%2F%2Frealtimecollisiondetection.net%2Fbooks%2Frtcd%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCaldwell,_Douglas_R.2005" class="citation web cs1">Caldwell, Douglas R. (2005-08-29). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120728180104/http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm">"Unlocking the Mysteries of the Bounding Box"</a>. US Army Engineer Research & Development Center, Topographic Engineering Center, Research Division, Information Generation and Management Branch. Archived from <a rel="nofollow" class="external text" href="http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm">the original</a> on 2012-07-28<span class="reference-accessdate">. Retrieved <span class="nowrap">2014-05-13</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Unlocking+the+Mysteries+of+the+Bounding+Box&rft.pub=US+Army+Engineer+Research+%26+Development+Center%2C+Topographic+Engineering+Center%2C+Research+Division%2C+Information+Generation+and+Management+Branch&rft.date=2005-08-29&rft.au=Caldwell%2C+Douglas+R.&rft_id=http%3A%2F%2Fwww.stonybrook.edu%2Flibmap%2Fcoordinates%2Fseriesa%2Fno2%2Fa2.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGan_B,_Dong_Q2022" class="citation journal cs1">Gan B, Dong Q (2022). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/348937861">"An improved optimal algorithm for collision detection of hybrid hierarchical bounding box"</a>. <i>Evolutionary Intelligence</i>. <b>15</b> (4): 2515–2527. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs12065-020-00559-6">10.1007/s12065-020-00559-6</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Evolutionary+Intelligence&rft.atitle=An+improved+optimal+algorithm+for+collision+detection+of+hybrid+hierarchical+bounding+box&rft.volume=15&rft.issue=4&rft.pages=2515-2527&rft.date=2022&rft_id=info%3Adoi%2F10.1007%2Fs12065-020-00559-6&rft.au=Gan+B%2C+Dong+Q&rft_id=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F348937861&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-:1-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-:1_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:1_11-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLin,_Ming_C1993" class="citation web cs1">Lin, Ming C (1993). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140728124049/https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf">"Efficient Collision Detection for Animation and Robotics (thesis)"</a> <span class="cs1-format">(PDF)</span>. University of California, Berkeley. Archived from <a rel="nofollow" class="external text" href="https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2014-07-28.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Efficient+Collision+Detection+for+Animation+and+Robotics+%28thesis%29&rft.pub=University+of+California%2C+Berkeley&rft.date=1993&rft.au=Lin%2C+Ming+C&rft_id=https%3A%2F%2Fwwwx.cs.unc.edu%2F~geom%2Fpapers%2Fdocuments%2Fdissertations%2Flin93.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGilbertJohnsonKeerthi1988" class="citation journal cs1">Gilbert, E.G.; Johnson, D.W.; Keerthi, S.S. (1988). <a rel="nofollow" class="external text" href="https://graphics.stanford.edu/courses/cs448b-00-winter/papers/gilbert.pdf">"A fast procedure for computing the distance between complex objects in three-dimensional space"</a> <span class="cs1-format">(PDF)</span>. <i>IEEE Journal on Robotics and Automation</i>. <b>4</b> (2): 193–203. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F56.2083">10.1109/56.2083</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Journal+on+Robotics+and+Automation&rft.atitle=A+fast+procedure+for+computing+the+distance+between+complex+objects+in+three-dimensional+space&rft.volume=4&rft.issue=2&rft.pages=193-203&rft.date=1988&rft_id=info%3Adoi%2F10.1109%2F56.2083&rft.aulast=Gilbert&rft.aufirst=E.G.&rft.au=Johnson%2C+D.W.&rft.au=Keerthi%2C+S.S.&rft_id=https%3A%2F%2Fgraphics.stanford.edu%2Fcourses%2Fcs448b-00-winter%2Fpapers%2Fgilbert.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://amigadev.elowar.com/read/ADCD_2.1/Hardware_Manual_guide/node0004.html#line95">"Components of the Amiga: The MC68000 and the Amiga Custom Chips"</a> (Reference manual) (2.1 ed.). Chapter 1. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180717093216/http://amigadev.elowar.com/read/ADCD_2.1/Hardware_Manual_guide/node0004.html#line95">Archived</a> from the original on 2018-07-17<span class="reference-accessdate">. Retrieved <span class="nowrap">2018-07-17</span></span>. <q>Additionally, you can use system hardware to detect collisions between objects and have your program react to such collisions.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Components+of+the+Amiga%3A+The+MC68000+and+the+Amiga+Custom+Chips&rft.pages=Chapter+1&rft.edition=2.1&rft_id=http%3A%2F%2Famigadev.elowar.com%2Fread%2FADCD_2.1%2FHardware_Manual_guide%2Fnode0004.html%23line95&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://developer.valvesoftware.com/wiki/Hitbox">"Hitbox"</a>. <i>Valve Developer Community</i>. <a href="/wiki/Valve_Corporation" title="Valve Corporation">Valve</a><span class="reference-accessdate">. Retrieved <span class="nowrap">18 September</span> 2011</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Valve+Developer+Community&rft.atitle=Hitbox&rft_id=http%3A%2F%2Fdeveloper.valvesoftware.com%2Fwiki%2FHitbox&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACollision+detection" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Collision_detection&action=edit&section=20" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://gamma.cs.unc.edu/research/collision/">University of North Carolina at Chapel Hill collision detection research website</a></li> <li><a rel="nofollow" class="external text" href="http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances/">Prof. Steven Cameron (Oxford University) web site on collision detection</a></li> <li><a rel="nofollow" class="external text" href="http://demonstrations.wolfram.com/HowToAvoidACollision/">How to Avoid a Collision</a> by George Beck, <a href="/wiki/Wolfram_Demonstrations_Project" title="Wolfram Demonstrations Project">Wolfram Demonstrations Project</a>.</li> <li><a rel="nofollow" class="external text" href="http://geomalgorithms.com/a08-_containers.html">Bounding boxes and their usage</a></li> <li><a rel="nofollow" class="external text" href="http://programmerart.weebly.com/separating-axis-theorem.html">Separating Axis Theorem</a></li> <li><a rel="nofollow" class="external text" href="https://docs.unity3d.com/ScriptReference/Collision.html">Unity 3D Collision</a></li> <li><a rel="nofollow" class="external text" href="https://docs.godotengine.org/en/3.1/tutorials/physics/physics_introduction.html">Godot Physics Collision</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox authority-control" aria-label="Navbox" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q1550329#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh2005008469">United States</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="http://olduli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007535117905171">Israel</a></span></li></ul></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Collision_detection&oldid=1259003655">https://en.wikipedia.org/w/index.php?title=Collision_detection&oldid=1259003655</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Computational_geometry" title="Category:Computational geometry">Computational geometry</a></li><li><a href="/wiki/Category:Computer_graphics" title="Category:Computer graphics">Computer graphics</a></li><li><a href="/wiki/Category:Video_game_development" title="Category:Video game development">Video game development</a></li><li><a href="/wiki/Category:Computer_physics_engines" title="Category:Computer physics engines">Computer physics engines</a></li><li><a href="/wiki/Category:Robotics_engineering" title="Category:Robotics engineering">Robotics engineering</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Wikipedia_articles_that_are_too_technical_from_March_2020" title="Category:Wikipedia articles that are too technical from March 2020">Wikipedia articles that are too technical from March 2020</a></li><li><a href="/wiki/Category:All_articles_that_are_too_technical" title="Category:All articles that are too technical">All articles that are too technical</a></li><li><a href="/wiki/Category:Wikipedia_articles_with_style_issues_from_January_2023" title="Category:Wikipedia articles with style issues from January 2023">Wikipedia articles with style issues from January 2023</a></li><li><a href="/wiki/Category:All_articles_with_style_issues" title="Category:All articles with style issues">All articles with style issues</a></li><li><a href="/wiki/Category:Wikipedia_articles_with_style_issues_from_August_2014" title="Category:Wikipedia articles with style issues from August 2014">Wikipedia articles with style issues from August 2014</a></li><li><a href="/wiki/Category:Articles_with_multiple_maintenance_issues" title="Category:Articles with multiple maintenance issues">Articles with multiple maintenance issues</a></li><li><a href="/wiki/Category:Wikipedia_articles_with_style_issues_from_January_2024" title="Category:Wikipedia articles with style issues from January 2024">Wikipedia articles with style issues from January 2024</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_July_2024" title="Category:Articles needing additional references from July 2024">Articles needing additional references from July 2024</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_June_2008" title="Category:Articles with unsourced statements from June 2008">Articles with unsourced statements from June 2008</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_January_2024" title="Category:Articles needing additional references from January 2024">Articles needing additional references from January 2024</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_August_2022" title="Category:Articles needing additional references from August 2022">Articles needing additional references from August 2022</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_August_2014" title="Category:Articles with unsourced statements from August 2014">Articles with unsourced statements from August 2014</a></li><li><a href="/wiki/Category:All_articles_lacking_reliable_references" title="Category:All articles lacking reliable references">All articles lacking reliable references</a></li><li><a href="/wiki/Category:Articles_lacking_reliable_references_from_March_2018" title="Category:Articles lacking reliable references from March 2018">Articles lacking reliable references from March 2018</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 22 November 2024, at 21:21<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Collision_detection&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-68775984f6-zrmbp","wgBackendResponseTime":132,"wgPageParseReport":{"limitreport":{"cputime":"0.745","walltime":"1.161","ppvisitednodes":{"value":3438,"limit":1000000},"postexpandincludesize":{"value":126571,"limit":2097152},"templateargumentsize":{"value":22426,"limit":2097152},"expansiondepth":{"value":17,"limit":100},"expensivefunctioncount":{"value":14,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":83910,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 744.339 1 -total"," 31.93% 237.649 1 Template:Reflist"," 17.74% 132.035 2 Template:Multiple_issues"," 17.70% 131.717 4 Template:Cite_journal"," 16.47% 122.627 1 Template:Authority_control"," 10.91% 81.229 1 Template:Short_description"," 9.42% 70.088 9 Template:Ambox"," 7.28% 54.221 2 Template:Pagetype"," 7.20% 53.611 4 Template:Fix"," 7.07% 52.604 3 Template:Citation_needed"]},"scribunto":{"limitreport-timeusage":{"value":"0.440","limit":"10.000"},"limitreport-memusage":{"value":6555568,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-7cb57f8f57-h8lcx","timestamp":"20241125174852","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Collision detection","url":"https:\/\/en.wikipedia.org\/wiki\/Collision_detection","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1550329","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1550329","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-01-20T06:43:09Z","dateModified":"2024-11-22T21:21:23Z","headline":"term in computer science"}</script> </body> </html>