ME964High Performance Computing for Engineering ApplicationsMidterm ProjectFor the midterm project, you will have to solve a collision detection problem: given anarbitrary number N of rigid spheres of radii iR, , ,1i N= � with i how ighlR R R� �distributed in the 3D space, find out which spheres are in contact/penetration with whichother spheres.Once you find a pair of spheres that are in contact, for this contact instance compute:- absolute collision location on object A (a vector in 3�)- absolute collision location on object B (a vector in 3�)- collision normal unit vector from body B to A (a vector in 3�)- object id for body A- object id for body BThe absolute collision location on object A is computed with respect to a global referenceframe as shown in , where this quantity is denoted Ar. Also note that the unit normalwould be along the line from BO to AO.Figure 1. Computation of the absolute location on object A1In order to understand what Bullet does and to increase your chances of matching itsbehavior, below is listed a summary of possible collision cases:A: B:Figure 2. Possible contact scenarios1. Sphere contacts sphere: one contact point (BAC C�), normal from center of B tocenter of A. This scenario is captured in (a).2. Sphere interpenetrates sphere: two different points AC and BC. This scenario iscaptured in (b) as well as in Figure 2(a).3. Sphere exactly on top of sphere, see Figure 2(b).4. Sphere inside sphere see Figure 2(c).5. Sphere inside sphere, not concentric, see Figure 2(d).6. Spheres are not in contact, not shownFor this project:1) Run the collision detection engine provided with the physics engine “Bullet” toverify the accuracy of your results. Using the Microsoft Developer StudioSolution provided, this process is automated to the extent to which you will get amessage “Test Passed” or “Test Failed”. In order to pass the test, the followingconditions must be satisfied:i) you should find the same number of contacts as “Bullet” doesii) you should find the same values for the absolute collision location onobject A and B (see )iii) you should find a contact normal that is within 10� from the BulletnormalNOTE: When you have a pair of bodies A and B, make sure you have thebody A be of lower index. Specifically, when running the comparison withBullet, please make sure that output is sorted by body A and then body B inincreasing order.2ABAB(a) (b) (c) (d)A BBA2) Run a work analysis for your algorithm and Bullet, and compare theirperformance. Specifically, run a collision detection for 1024, 4096,…,1048576bodies and do a regression analysis to gauge how your algorithm scales with thenumber of bodies.3) Read Chapter 5 of the textbook Patterns for Parallel Programming by TimothyG. Mattson, Beverly A. Sanders, Berna L. Massingill. Drawing on material youread out of this book (chapters 3, 4, and 5), comment on the patterns that you usedin designing the collision detection solution.Grading: Solving the collision detection problem on the GPU but not passing the Bulletvalidation: 30% Passing the Bullet validation: 10% Running the regression analysis and understanding the scaling of both Bullet andyour implementation: 20% Report on the parallel programming patterns that you used in your design: 15% PPT report and your presentation of the design and results (presentation will bemade on Nov. 18): 25% Running collision detection faster than Bullet: PricelessSubmission Policy:Submit your Developer Studio Solution along with the MS-Word doc report no later thanNovember 9, 11:59 PM if you choose to implement a brute force approach, or byNovember 17, 11:59 PM if you implement a more sophisticated approach.NOTE: The PPT report is due on November 17, 11:59 PM. Your presentation is slatedfor Nov. 18 during regular class hours. You will have a 10 minute time slot to make yourpresentation. The material and your presentation will account for
View Full Document
Unlocking...