🗊Презентация Collision detection on the GPU

Категория: Технология
Нажмите для полного просмотра!
Collision detection on the GPU, слайд №1Collision detection on the GPU, слайд №2Collision detection on the GPU, слайд №3Collision detection on the GPU, слайд №4Collision detection on the GPU, слайд №5Collision detection on the GPU, слайд №6Collision detection on the GPU, слайд №7Collision detection on the GPU, слайд №8Collision detection on the GPU, слайд №9Collision detection on the GPU, слайд №10Collision detection on the GPU, слайд №11Collision detection on the GPU, слайд №12Collision detection on the GPU, слайд №13Collision detection on the GPU, слайд №14Collision detection on the GPU, слайд №15Collision detection on the GPU, слайд №16Collision detection on the GPU, слайд №17Collision detection on the GPU, слайд №18Collision detection on the GPU, слайд №19Collision detection on the GPU, слайд №20Collision detection on the GPU, слайд №21Collision detection on the GPU, слайд №22Collision detection on the GPU, слайд №23Collision detection on the GPU, слайд №24Collision detection on the GPU, слайд №25Collision detection on the GPU, слайд №26Collision detection on the GPU, слайд №27Collision detection on the GPU, слайд №28Collision detection on the GPU, слайд №29Collision detection on the GPU, слайд №30Collision detection on the GPU, слайд №31Collision detection on the GPU, слайд №32Collision detection on the GPU, слайд №33Collision detection on the GPU, слайд №34Collision detection on the GPU, слайд №35Collision detection on the GPU, слайд №36Collision detection on the GPU, слайд №37Collision detection on the GPU, слайд №38Collision detection on the GPU, слайд №39Collision detection on the GPU, слайд №40Collision detection on the GPU, слайд №41Collision detection on the GPU, слайд №42Collision detection on the GPU, слайд №43Collision detection on the GPU, слайд №44Collision detection on the GPU, слайд №45Collision detection on the GPU, слайд №46Collision detection on the GPU, слайд №47Collision detection on the GPU, слайд №48Collision detection on the GPU, слайд №49Collision detection on the GPU, слайд №50Collision detection on the GPU, слайд №51Collision detection on the GPU, слайд №52Collision detection on the GPU, слайд №53Collision detection on the GPU, слайд №54Collision detection on the GPU, слайд №55Collision detection on the GPU, слайд №56Collision detection on the GPU, слайд №57Collision detection on the GPU, слайд №58Collision detection on the GPU, слайд №59Collision detection on the GPU, слайд №60Collision detection on the GPU, слайд №61Collision detection on the GPU, слайд №62Collision detection on the GPU, слайд №63Collision detection on the GPU, слайд №64Collision detection on the GPU, слайд №65Collision detection on the GPU, слайд №66Collision detection on the GPU, слайд №67Collision detection on the GPU, слайд №68Collision detection on the GPU, слайд №69Collision detection on the GPU, слайд №70Collision detection on the GPU, слайд №71Collision detection on the GPU, слайд №72Collision detection on the GPU, слайд №73Collision detection on the GPU, слайд №74Collision detection on the GPU, слайд №75Collision detection on the GPU, слайд №76Collision detection on the GPU, слайд №77Collision detection on the GPU, слайд №78Collision detection on the GPU, слайд №79Collision detection on the GPU, слайд №80Collision detection on the GPU, слайд №81Collision detection on the GPU, слайд №82Collision detection on the GPU, слайд №83Collision detection on the GPU, слайд №84Collision detection on the GPU, слайд №85Collision detection on the GPU, слайд №86Collision detection on the GPU, слайд №87Collision detection on the GPU, слайд №88Collision detection on the GPU, слайд №89Collision detection on the GPU, слайд №90Collision detection on the GPU, слайд №91Collision detection on the GPU, слайд №92Collision detection on the GPU, слайд №93Collision detection on the GPU, слайд №94Collision detection on the GPU, слайд №95Collision detection on the GPU, слайд №96Collision detection on the GPU, слайд №97Collision detection on the GPU, слайд №98Collision detection on the GPU, слайд №99Collision detection on the GPU, слайд №100Collision detection on the GPU, слайд №101Collision detection on the GPU, слайд №102Collision detection on the GPU, слайд №103Collision detection on the GPU, слайд №104Collision detection on the GPU, слайд №105Collision detection on the GPU, слайд №106Collision detection on the GPU, слайд №107Collision detection on the GPU, слайд №108Collision detection on the GPU, слайд №109Collision detection on the GPU, слайд №110Collision detection on the GPU, слайд №111Collision detection on the GPU, слайд №112Collision detection on the GPU, слайд №113Collision detection on the GPU, слайд №114Collision detection on the GPU, слайд №115Collision detection on the GPU, слайд №116Collision detection on the GPU, слайд №117
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Collision detection on the GPU. Доклад-сообщение содержит 117 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Collision Detection on the GPU Mike Donovan CIS 665 Summer 2009
Описание слайда:
Collision Detection on the GPU Mike Donovan CIS 665 Summer 2009

Слайд 2


Overview Quick Background CPU Methods CULLIDE RCULLIDE QCULLIDE CUDA Methods
Описание слайда:
Overview Quick Background CPU Methods CULLIDE RCULLIDE QCULLIDE CUDA Methods

Слайд 3


Background Need to find collisions for lots of reasons Physics engines Seeing if a projectile hits an object Ray casting Game engines Etc…
Описание слайда:
Background Need to find collisions for lots of reasons Physics engines Seeing if a projectile hits an object Ray casting Game engines Etc…

Слайд 4


Background Broad phase: Looks at entire scene Looks at proxy geometry (bounding shapes) Determines if two objects may intersect Needs to be very fast
Описание слайда:
Background Broad phase: Looks at entire scene Looks at proxy geometry (bounding shapes) Determines if two objects may intersect Needs to be very fast

Слайд 5


Background Narrow phase: Looks at pairs of objects flagged by broad phase Looks at the actual geometry of an object Determines if objects are truly intersecting Generally slower
Описание слайда:
Background Narrow phase: Looks at pairs of objects flagged by broad phase Looks at the actual geometry of an object Determines if objects are truly intersecting Generally slower

Слайд 6


Background Resolution Compute forces according to the contact points returned from the narrow phase Can be non trivial if there are multiple contact points Returns resulting forces to be added to each body
Описание слайда:
Background Resolution Compute forces according to the contact points returned from the narrow phase Can be non trivial if there are multiple contact points Returns resulting forces to be added to each body

Слайд 7


CPU Methods Brute Force Check every object against every other N(N-1)/2 tests O(N²) Sweep and Prune Average case: O(N log N) Worst case: O(N²) Spatial Subdivisions Average case: O(N log N) Worst case: O(N²)
Описание слайда:
CPU Methods Brute Force Check every object against every other N(N-1)/2 tests O(N²) Sweep and Prune Average case: O(N log N) Worst case: O(N²) Spatial Subdivisions Average case: O(N log N) Worst case: O(N²)

Слайд 8


Sweep and Prune
Описание слайда:
Sweep and Prune

Слайд 9


Spatial Subdivisions
Описание слайда:
Spatial Subdivisions

Слайд 10


CULLIDE Came out of Dinesh’s group at UNC in 2003 Uses graphics hardware to do a broad-narrow phase hybrid No shader languages
Описание слайда:
CULLIDE Came out of Dinesh’s group at UNC in 2003 Uses graphics hardware to do a broad-narrow phase hybrid No shader languages

Слайд 11


Outline Overview Pruning Algorithm Implementation and Results Conclusions and Future Work
Описание слайда:
Outline Overview Pruning Algorithm Implementation and Results Conclusions and Future Work

Слайд 12


Outline Overview Pruning Algorithm Implementation and Results Conclusions and Future Work
Описание слайда:
Outline Overview Pruning Algorithm Implementation and Results Conclusions and Future Work

Слайд 13


Overview Potentially Colliding Set (PCS) computation Exact collision tests on the PCS
Описание слайда:
Overview Potentially Colliding Set (PCS) computation Exact collision tests on the PCS

Слайд 14


Algorithm
Описание слайда:
Algorithm

Слайд 15


Potentially Colliding Set (PCS)
Описание слайда:
Potentially Colliding Set (PCS)

Слайд 16


Potentially Colliding Set (PCS)
Описание слайда:
Potentially Colliding Set (PCS)

Слайд 17


Outline Problem Overview Overview Pruning Algorithm Implementation and Results Conclusions and Future Work
Описание слайда:
Outline Problem Overview Overview Pruning Algorithm Implementation and Results Conclusions and Future Work

Слайд 18


Algorithm
Описание слайда:
Algorithm

Слайд 19


Visibility Computations Lemma 1: An object O does not collide with a set of objects S if O is fully visible with respect to S Utilize visibility for PCS computation
Описание слайда:
Visibility Computations Lemma 1: An object O does not collide with a set of objects S if O is fully visible with respect to S Utilize visibility for PCS computation

Слайд 20


Collision Detection using Visibility Computations
Описание слайда:
Collision Detection using Visibility Computations

Слайд 21


PCS Pruning Lemma 2: Given n objects O1,O2,…,On , an object Oi does not belong to PCS if it does not collide with O1,…,Oi-1,Oi+1,…,On Prune objects that do not collide
Описание слайда:
PCS Pruning Lemma 2: Given n objects O1,O2,…,On , an object Oi does not belong to PCS if it does not collide with O1,…,Oi-1,Oi+1,…,On Prune objects that do not collide

Слайд 22


PCS Pruning O1 O2 … Oi-1 Oi Oi+1 … On-1 On
Описание слайда:
PCS Pruning O1 O2 … Oi-1 Oi Oi+1 … On-1 On

Слайд 23


PCS Pruning
Описание слайда:
PCS Pruning

Слайд 24


PCS Pruning
Описание слайда:
PCS Pruning

Слайд 25


PCS Computation Each object tested against all objects but itself Naive algorithm is O(n2) Linear time algorithm Uses two pass rendering approach Conservative solution
Описание слайда:
PCS Computation Each object tested against all objects but itself Naive algorithm is O(n2) Linear time algorithm Uses two pass rendering approach Conservative solution

Слайд 26


PCS Computation: First Pass
Описание слайда:
PCS Computation: First Pass

Слайд 27


PCS Computation: First Pass
Описание слайда:
PCS Computation: First Pass

Слайд 28


PCS Computation: First Pass
Описание слайда:
PCS Computation: First Pass

Слайд 29


PCS Computation: First Pass
Описание слайда:
PCS Computation: First Pass

Слайд 30


PCS Computation: First Pass
Описание слайда:
PCS Computation: First Pass

Слайд 31


PCS Computation: Second Pass
Описание слайда:
PCS Computation: Second Pass

Слайд 32


PCS Computation: Second Pass
Описание слайда:
PCS Computation: Second Pass

Слайд 33


PCS Computation: Second Pass
Описание слайда:
PCS Computation: Second Pass

Слайд 34


PCS Computation: Second Pass
Описание слайда:
PCS Computation: Second Pass

Слайд 35


PCS Computation: Second Pass
Описание слайда:
PCS Computation: Second Pass

Слайд 36


PCS Computation
Описание слайда:
PCS Computation

Слайд 37


PCS Computation
Описание слайда:
PCS Computation

Слайд 38


Collision detection on the GPU, слайд №38
Описание слайда:

Слайд 39


Collision detection on the GPU, слайд №39
Описание слайда:

Слайд 40


Collision detection on the GPU, слайд №40
Описание слайда:

Слайд 41


Collision detection on the GPU, слайд №41
Описание слайда:

Слайд 42


Collision detection on the GPU, слайд №42
Описание слайда:

Слайд 43


Algorithm
Описание слайда:
Algorithm

Слайд 44


Overlap Localization Each object is composed of sub-objects We are given n objects O1,…,On Compute sub-objects of an object Oi that overlap with sub-objects of other objects
Описание слайда:
Overlap Localization Each object is composed of sub-objects We are given n objects O1,…,On Compute sub-objects of an object Oi that overlap with sub-objects of other objects

Слайд 45


Overlap Localization Our solution Test if each sub-object of Oi overlaps with sub-objects of O1,..Oi-1 Test if each sub-object of Oi overlaps with sub-objects of Oi+1,...,On Linear time algorithm Extend the two pass approach
Описание слайда:
Overlap Localization Our solution Test if each sub-object of Oi overlaps with sub-objects of O1,..Oi-1 Test if each sub-object of Oi overlaps with sub-objects of Oi+1,...,On Linear time algorithm Extend the two pass approach

Слайд 46


Overlap Localization
Описание слайда:
Overlap Localization

Слайд 47


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 48


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 49


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 50


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 51


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 52


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 53


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 54


Overlap Localization: First Pass
Описание слайда:
Overlap Localization: First Pass

Слайд 55


Overlap Localization: Second Pass
Описание слайда:
Overlap Localization: Second Pass

Слайд 56


Overlap Localization
Описание слайда:
Overlap Localization

Слайд 57


Collision detection on the GPU, слайд №57
Описание слайда:

Слайд 58


Collision detection on the GPU, слайд №58
Описание слайда:

Слайд 59


Collision detection on the GPU, слайд №59
Описание слайда:

Слайд 60


Collision detection on the GPU, слайд №60
Описание слайда:

Слайд 61


Collision detection on the GPU, слайд №61
Описание слайда:

Слайд 62


Collision detection on the GPU, слайд №62
Описание слайда:

Слайд 63


Collision detection on the GPU, слайд №63
Описание слайда:

Слайд 64


Collision detection on the GPU, слайд №64
Описание слайда:

Слайд 65


Collision detection on the GPU, слайд №65
Описание слайда:

Слайд 66


Collision detection on the GPU, слайд №66
Описание слайда:

Слайд 67


Collision detection on the GPU, слайд №67
Описание слайда:

Слайд 68


Collision detection on the GPU, слайд №68
Описание слайда:

Слайд 69


Collision detection on the GPU, слайд №69
Описание слайда:

Слайд 70


Collision detection on the GPU, слайд №70
Описание слайда:

Слайд 71


Collision detection on the GPU, слайд №71
Описание слайда:

Слайд 72


Collision detection on the GPU, слайд №72
Описание слайда:

Слайд 73


Collision detection on the GPU, слайд №73
Описание слайда:

Слайд 74


Algorithm
Описание слайда:
Algorithm

Слайд 75


Visibility Queries We require a query Tests if a primitive is fully visible or not Current hardware supports occlusion queries Test if a primitive is visible or not Our solution Change the sign of depth function
Описание слайда:
Visibility Queries We require a query Tests if a primitive is fully visible or not Current hardware supports occlusion queries Test if a primitive is visible or not Our solution Change the sign of depth function

Слайд 76


Visibility Queries Depth function
Описание слайда:
Visibility Queries Depth function

Слайд 77


Bandwidth Analysis Read back only integer identifiers Independent of screen resolution
Описание слайда:
Bandwidth Analysis Read back only integer identifiers Independent of screen resolution

Слайд 78


Optimizations First use AABBs as object bounding volume Use orthographic views for pruning Prune using original objects
Описание слайда:
Optimizations First use AABBs as object bounding volume Use orthographic views for pruning Prune using original objects

Слайд 79


Advantages No coherence No assumptions on motion of objects Works on generic models A fast pruning algorithm No frame-buffer readbacks
Описание слайда:
Advantages No coherence No assumptions on motion of objects Works on generic models A fast pruning algorithm No frame-buffer readbacks

Слайд 80


Limitations No distance or penetration depth information Resolution issues No self-collisions Culling performance varies with relative configurations
Описание слайда:
Limitations No distance or penetration depth information Resolution issues No self-collisions Culling performance varies with relative configurations

Слайд 81


Assumptions Makes assumptions that their algorithm will get faster as hardware improves. Luckily they were right
Описание слайда:
Assumptions Makes assumptions that their algorithm will get faster as hardware improves. Luckily they were right

Слайд 82


RCULLIDE An improvement on CULLIDE in 2004 Resolves issue of screen resolution precision
Описание слайда:
RCULLIDE An improvement on CULLIDE in 2004 Resolves issue of screen resolution precision

Слайд 83


Overview A main issue with CULLIDE was the fact that it wasn’t reliable Collisions could easily be missed due to screen resolution
Описание слайда:
Overview A main issue with CULLIDE was the fact that it wasn’t reliable Collisions could easily be missed due to screen resolution

Слайд 84


Overview 3 kinds of error associated with visibility based overlap Perspective error Strange shapes from the transformation Sampling error Pixel resolution isn’t high enough Depth buffer precision error If distance between primitives is less than the depth buffer resolution, we will get incorrect results from our visibility query
Описание слайда:
Overview 3 kinds of error associated with visibility based overlap Perspective error Strange shapes from the transformation Sampling error Pixel resolution isn’t high enough Depth buffer precision error If distance between primitives is less than the depth buffer resolution, we will get incorrect results from our visibility query

Слайд 85


Reliable Queries The three errors cause the following: A fragment to not be rasterized A fragment is generated but not sampled where interference occurs A fragment is generated and sampled where the interference occurs but the precision of the buffer is not sufficient
Описание слайда:
Reliable Queries The three errors cause the following: A fragment to not be rasterized A fragment is generated but not sampled where interference occurs A fragment is generated and sampled where the interference occurs but the precision of the buffer is not sufficient

Слайд 86


Reliable Queries Use “fat” triangles Generate 2 fragments for each pixel touched by a triangle (no matter how little it is in the pixel) For each pixel touched by the triangle, the depth of the 2 fragments must bound the depth of all points of the triangle in that pixel Causes method to become more conservative (read: slower) but much more accurate
Описание слайда:
Reliable Queries Use “fat” triangles Generate 2 fragments for each pixel touched by a triangle (no matter how little it is in the pixel) For each pixel touched by the triangle, the depth of the 2 fragments must bound the depth of all points of the triangle in that pixel Causes method to become more conservative (read: slower) but much more accurate

Слайд 87


Minkowski Sum Scary name…easy math
Описание слайда:
Minkowski Sum Scary name…easy math

Слайд 88


Reliable Queries In practice, we use the Minkowski sum of a bounding cube B and the triangle T B = max(2dx, 2dy, 2dz) where dx,y,z are pixel dimensions If uniform supersampling is known to occur on the card, we can reduce the size of B We need B to cover at least 1 sampling point for the triangle it bounds
Описание слайда:
Reliable Queries In practice, we use the Minkowski sum of a bounding cube B and the triangle T B = max(2dx, 2dy, 2dz) where dx,y,z are pixel dimensions If uniform supersampling is known to occur on the card, we can reduce the size of B We need B to cover at least 1 sampling point for the triangle it bounds

Слайд 89


Reliable Queries Cubes only work for z-axis projections so in practice use a bounding sphere of radius sqrt(3)p/2
Описание слайда:
Reliable Queries Cubes only work for z-axis projections so in practice use a bounding sphere of radius sqrt(3)p/2

Слайд 90


Bounding Offset So far we’ve just dealt with single triangles but we need whole objects This is done using a Union of Object-oriented Bounding Boxes(UOBB)
Описание слайда:
Bounding Offset So far we’ve just dealt with single triangles but we need whole objects This is done using a Union of Object-oriented Bounding Boxes(UOBB)

Слайд 91


Algorithm
Описание слайда:
Algorithm

Слайд 92


Improvement over CULLIDE
Описание слайда:
Improvement over CULLIDE

Слайд 93


Performance Still runs faster than CPU implementations 3x slower than CULLIDE due to bounding box rasterization vs triangle rasterization
Описание слайда:
Performance Still runs faster than CPU implementations 3x slower than CULLIDE due to bounding box rasterization vs triangle rasterization

Слайд 94


QCULLIDE Extends CULLIDE to handle self collisions in complex meshes All running in real time
Описание слайда:
QCULLIDE Extends CULLIDE to handle self collisions in complex meshes All running in real time

Слайд 95


Self Collision Culling Note that only intersecting triangles that don’t share a vertex or edge are considered colliding
Описание слайда:
Self Collision Culling Note that only intersecting triangles that don’t share a vertex or edge are considered colliding

Слайд 96


Self Collision Culling Algorithm Include all potentially colliding primitives and PCS where each primitive is a triangle Perform the visibility test to see if a triangle is penetrating any other If completely visible, the object is not colliding
Описание слайда:
Self Collision Culling Algorithm Include all potentially colliding primitives and PCS where each primitive is a triangle Perform the visibility test to see if a triangle is penetrating any other If completely visible, the object is not colliding

Слайд 97


Q-CULLIDE Sets BFV – Objects fully visible in both passes and are pruned from the PCS FFV – Fully visible in only the first pass SFV – Fully visible in only the second pass NFV – Not fully visible in both passes
Описание слайда:
Q-CULLIDE Sets BFV – Objects fully visible in both passes and are pruned from the PCS FFV – Fully visible in only the first pass SFV – Fully visible in only the second pass NFV – Not fully visible in both passes

Слайд 98


Q-CULLIDE Properties of sets FFV and SFV are collision free No object in FFV collides with any other in FFV…same for SFV If an object is in FFV and is fully visible in the 2nd pass of the algorithm, we can prune it and vice versa
Описание слайда:
Q-CULLIDE Properties of sets FFV and SFV are collision free No object in FFV collides with any other in FFV…same for SFV If an object is in FFV and is fully visible in the 2nd pass of the algorithm, we can prune it and vice versa

Слайд 99


Algorithm
Описание слайда:
Algorithm

Слайд 100


Algorithm
Описание слайда:
Algorithm

Слайд 101


What’s Happening
Описание слайда:
What’s Happening

Слайд 102


Improvement Over CULLIDE
Описание слайда:
Improvement Over CULLIDE

Слайд 103


Improvements Over CULLIDE Sends an order of magnitude less collisions to the CPU than CULLIDE
Описание слайда:
Improvements Over CULLIDE Sends an order of magnitude less collisions to the CPU than CULLIDE

Слайд 104


Spatial Subdivision Partition space into uniform grid Grid cell is at least as large as largest object Each cell contains list of each object whose centroid is in the cell Collision tests are performed between objects who are in same cell or adjacent cells
Описание слайда:
Spatial Subdivision Partition space into uniform grid Grid cell is at least as large as largest object Each cell contains list of each object whose centroid is in the cell Collision tests are performed between objects who are in same cell or adjacent cells

Слайд 105


Parallel Spatial Subdivision Complications: Single object can be involved in multiple collision tests Need to prevent multiple threads updating the state of an object at the same time
Описание слайда:
Parallel Spatial Subdivision Complications: Single object can be involved in multiple collision tests Need to prevent multiple threads updating the state of an object at the same time

Слайд 106


Guaranteed Individual Collision Tests Prove: No two cells updated in parallel may contain the same object that is being updated Constraints Each cell is as large as the bounding volume of the largest object Each cell processed in parallel must be separated by each other cell by at least one intervening cell In 2d this takes _____ number of passes In 3d this takes _____ number of passes
Описание слайда:
Guaranteed Individual Collision Tests Prove: No two cells updated in parallel may contain the same object that is being updated Constraints Each cell is as large as the bounding volume of the largest object Each cell processed in parallel must be separated by each other cell by at least one intervening cell In 2d this takes _____ number of passes In 3d this takes _____ number of passes

Слайд 107


Example of Parallel Spatial Subdivision
Описание слайда:
Example of Parallel Spatial Subdivision

Слайд 108


Avoiding Extra Collision Testing Associate each object a set of control bits to test where its centroid resides Scale the bounding sphere of each object by sqrt(2) to ensure the grid cell is at least 1.5 times larger than the largest object
Описание слайда:
Avoiding Extra Collision Testing Associate each object a set of control bits to test where its centroid resides Scale the bounding sphere of each object by sqrt(2) to ensure the grid cell is at least 1.5 times larger than the largest object

Слайд 109


Implementing in CUDA Store list of object IDs, cell IDs in device memory Build the list of cell IDs from object’s bounding boxes Sorting list from previous step Build an index table to traverse the sorted list Schedule pairs of objects for narrow phase collision detection
Описание слайда:
Implementing in CUDA Store list of object IDs, cell IDs in device memory Build the list of cell IDs from object’s bounding boxes Sorting list from previous step Build an index table to traverse the sorted list Schedule pairs of objects for narrow phase collision detection

Слайд 110


Initialization
Описание слайда:
Initialization

Слайд 111


Construct the Cell ID Array Host Cells (H – Cells) Contain the centroid of the object Phantom Cells (P-Cells) Overlap with bounding volume but do not contain the centroid
Описание слайда:
Construct the Cell ID Array Host Cells (H – Cells) Contain the centroid of the object Phantom Cells (P-Cells) Overlap with bounding volume but do not contain the centroid

Слайд 112


Sorting the Cell ID Array What we want: Sorted by Cell ID H cells of an ID occur before P cells of an ID Starting with a partial sort H cells are before P cells, but array is not sorted by Cell ID Solution: Radix Sort Radix Sort ensures identical cell IDs remain in the same order as before sorting.
Описание слайда:
Sorting the Cell ID Array What we want: Sorted by Cell ID H cells of an ID occur before P cells of an ID Starting with a partial sort H cells are before P cells, but array is not sorted by Cell ID Solution: Radix Sort Radix Sort ensures identical cell IDs remain in the same order as before sorting.

Слайд 113


Sorting Cell Array
Описание слайда:
Sorting Cell Array

Слайд 114


Spatial Subdivision
Описание слайда:
Spatial Subdivision

Слайд 115


Create the Collision Cell List Scan sorted cell ID array for changes of cell ID Mark by end of the list of occupants of one cell and beginning of another Count number of objects each collision cell contains and convert them into offsets using scan Create entries for each collision cell in new array Start Number of H occupants Number of P occupants
Описание слайда:
Create the Collision Cell List Scan sorted cell ID array for changes of cell ID Mark by end of the list of occupants of one cell and beginning of another Count number of objects each collision cell contains and convert them into offsets using scan Create entries for each collision cell in new array Start Number of H occupants Number of P occupants

Слайд 116


Create Collision Cell List
Описание слайда:
Create Collision Cell List

Слайд 117


Traverse Collision Cell List
Описание слайда:
Traverse Collision Cell List

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию