Collision detection definition

collision detection between two rectangles and collision detection example
Dr.ShaneMatts Profile Pic
Dr.ShaneMatts,United States,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
MIT EECS 6.837 Computer Graphics Collision Detection and Response MIT EECS 6.837 – Durand MIT EECS 6.837 – Matusik Philippe Halsman: Dali Atomicus 1 This image is in the public domain. Source:Wikimedia Commons.Collisions • Detection • Response • Overshooting problem (when we enter the solid) 2 Collision Response for Particles N v 3 Collision Response for Particles N v v t v n v=v +v n t normal component tangential component 4 Collision Response for Particles N v • Tangential velocity v t often unchanged v t • Normal velocity v reflects: n v n N v v new ε=1 • Coefficient of restitution ε N • When ε = 1, mirror reflection v v new ε1 5 Collisions – Overshooting • Usually, we detect collision when it is too late: we are already inside x i x i+1 6 Collisions – Overshooting • Usually, we detect collision when it is too late: we are already inside • Solution: Back up x i • Compute intersection point backtracking • Ray-object intersection • Compute response there • Advance for remaining fractional time step x i+1 7 Collisions – Overshooting • Usually, we detect collision when it is too late: we are already inside • Solution: Back up x i • Compute intersection point backtracking • Ray-object intersection • Compute response there fixing • Advance for remaining fractional time step • Other solution: x i+1 Quick and dirty hack • Just project back to object closest point 8 Questions? • Pong: ε =? • http://www.youtube.com/watch?v=sWY0Q_lMFfw • http://www.xnet.se/javaTest/jPong/jPong.html Animation removed due to copyright restrictions. This image is in the public domain. Image courtesy of Chris Rand on Wikimedia Commons. License: CC-BY-SA. Source:Wikimedia Commons. This content is excluded from our Creative Commons license. For more info http://ocw.mit.edu/help/faq-fair-use/. rmation, see 9 Collision Detection in Big Scenes • Imagine we have n objects. Can we test all pairwise intersections? 2 – Quadratic cost O(n ) • Simple optimization: separate static objects 2 – But still O(static × dynamic+ dynamic ) 10 Hierarchical Collision Detection • Use simpler conservative proxies (e.g. bounding spheres) • Recursive (hierarchical) test – Spend time only for parts of the scene that are close • Many different versions, we will cover only one 11 Bounding Spheres • Place spheres around objects • If spheres do not intersect, neither do the objects • Sphere-sphere collision test is easy. Courtesy of Patrick Laug. Used with permission. © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 12 Sphere-Sphere Collision Test • Two spheres, centers C and C , radii r and r 1 2 1 2 • Intersect only if C C r +r 1 2 1 2 r 2 C r C 1 1 2 Courtesy of Patrick Laug. Used with permission. © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 13 Hierarchical Collision Test • Hierarchy of bounding spheres – Organized in a tree • Recursive test with early pruning Root encloses whole object © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 14 Examples of Hierarchy • http://isg.cs.tcd.ie/spheretree/ © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 15 Pseudocode (simplistic version) boolean intersect(node1, node2) // no overlap? == no intersection if (overlap(node1-sphere, node2-sphere) return false // recurse down the larger of the two nodes if (node1-radius()node2-radius()) for each child c of node1 if intersect(c, node2) return true else for each child c f node2 if intersect(c, node1) return true // no intersection in the subtrees? == no intersection return false 16 boolean intersect(node1, node2) if (overlap(node1-sphere, node2-sphere) return false if (node1-radius()node2-radius()) for each child c of node1 if intersect(c, node2) return true else for each child c f node2 if intersect(c, node1) return true return false node 1 node 2 © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see Courtesy of Patrick Laug. Used with permission. http://ocw.mit.edu/help/faq-fair-use/. 17 boolean intersect(node1, node2) if (overlap(node1-sphere, node2-sphere) return false if (node1-radius()node2-radius()) for each child c of node1 if intersect(c, node2) return true else for each child c f node2 if intersect(c, node1) return true return false © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see Courtesy of Patrick Laug. Used with permission. http://ocw.mit.edu/help/faq-fair-use/. 18 boolean intersect(node1, node2) if (overlap(node1-sphere, node2-sphere) return false if (node1-radius()node2-radius()) for each child c of node1 if intersect(c, node2) return true else for each child c f node2 if intersect(c, node1) return true return false © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see Courtesy of Patrick Laug. Used with permission. http://ocw.mit.edu/help/faq-fair-use/. 19 boolean intersect(node1, node2) if (overlap(node1-sphere, node2-sphere) return false if (node1-radius()node2-radius()) for each child c of node1 if intersect(c, node2) return true else for each child c f node2 if intersect(c, node1) return true return false © Gareth Bradshaw. All rights reserved. This content is excluded from our Creative Commons license. For more information, see Courtesy of Patrick Laug. Used with permission. http://ocw.mit.edu/help/faq-fair-use/. 20

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.