UCSC CMPS 20 - Introduction to Collision Detection

Unformatted text preview:

Introduction to Collision Detection Lecture based on Real Time Collision Detection, Christer Ericson, Morgan Kauffman, 2005AnnouncementsTechnical Design DocumentTechnical Design Document (cont’d)Collision DetectionKey to collision detection: scalingNaïve Collision Detection: n x n checkingBroad vs Narrow SweepBroad sweep approachesReducing Cost of Checking Two Objects for CollisionCommon Bounding VolumesCircle Bounding BoxAxis-Aligned Bounding Boxes (AABBs)Axis Aligned Bounding Box Intersection (min-max)Axis Aligned Bounding Box Intersection (min-width)AABB Intersection (center-radius)HomeworkIntroduction to Collision DetectionLecture based on Real Time Collision Detection, Christer Ericson, Morgan Kauffman, 2005Game Design ExperienceProfessor Jim WhiteheadFebruary 9, 2009Creative Commons Attribution 3.0creativecommons.org/licenses/by/3.0Announcements•Homework #1, Revisited (Improved Design)►Due today►May turn it in to the box by my door by the end of the day►Also make sure you do electronic submission►See details on web site•Midterm exam►Aiming for return of exams on Wednesday►Will post answer key after class todayTechnical Design Document•Create a UML structure diagram for your game►Map out your design on paper, before writing code►Allows you to think about design decisions early►Due this Friday, February 13•In one or more UML diagrams, describe all of the classes and interfaces you will create for your project►For each class and interface, give•Class properties, methods, and variables►Show inheritance and containment relationshipsTechnical Design Document (cont’d)•Items that should be in your design ►input handling ►representation of game levels, if present ►player class ►enemy classes, including a container holding active enemies ►game object classes, including a container to hold them ►collision detection ►classes for drawing player, enemies, other game objects ►classes for handling audio ►menu system classes •Make sure TDD is consistent with game design►Are you missing anything?•Strongly recommend using a UML modeling tool►StarUML is free, has good set of features►http://staruml.sourceforge.net/en/ (see link on Tools page)Demonstration of use of StarUMLCollision Detection•Collision detection►Determining if two objects intersect (true or false)►Example: did bullet hit opponent?•Collision resolution (collision determination)►Determining when two objects came into contact•At what point during their motion did they intersect?•Example: Two balls needing to bounce off each other►Determining where two objects intersect•Which points on the objects touch during a collision?•Example: Pong: where ball hits paddle is important•Complexity of answering these questions increases in order given►If < when < whereKey to collision detection: scaling•Key constraint: only 16.667ms per clock tick►Limited time to perform collision detection•Object shapes in 2D games can be quite complex►Naïve: check two objects pixel-by-pixel for collisions•Many objects can potentially collide►Naïve: check every object pair for collisions•Drawback of naïve approach►Takes too long►Doesn’t scale to large numbers of objects•Approaches for scaling►Reduce # of collision pairs►Reduce cost of each collision checkChu Chu Rocket, DreamcastNaïve Collision Detection: n x n checking•Assume►n objects in game►All n objects can potentially intersect with each other•Conceptually easiest approach►Check each object against every other object for intersections►Leads to (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) checks►Done poorly, can be exactly n2 checks ►Example: 420 objects leads to 87,990 checks, per clock tickDemonstration of n x n collision checkingBroad vs Narrow Sweep•With many small objects in large playfield►Each object only has the potential to collide with nearby objects•Broad sweep►Perform a quick pass over n objects to determine which pairs have potentialto intersect, p•Narrow sweep►Perform p x p check of objectpairs that have potential tointersect•Dramatically reduces # of checksMushihimesamaBroad sweep approaches•Grid►Divide playfield into a grid of squares►Place each object in its square►Only need to check contents of square against itself and neighboring squares►See http://www.harveycartel.org/metanet/tutorials/tutorialB.html for example•Space partitioning tree►Subdivide space as needed into rectangles►Use tree data structure to point to objects in space►Only need to check tree leaves►Quadtree, Binary Space Partition (BSP)tree•Application-specific►2D-shooter: only need to checkfor collision against ship►Do quick y check for broad sweepPoint Quadtree (Wikipedia)Reducing Cost of Checking Two Objects for Collision•General approach is to substitute a bounding volume for a more complex object•Desirable properties of bounding volumes:►Inexpensive intersection tests►Tight fitting►Inexpensive to compute►Easy to rotate and transform►Low memory useMegaman X1 (Capcom). White boxes represent bounding volumes.Common Bounding Volumes•Most introductory game programming texts call AABBs simply “bounding boxes”Circle/Sphere Axis-Aligned Bounding Box(AABB)Oriented Bounding Box (OBB)Convex HullBetter bounds, better cullingFaster test, less memoryCircle Bounding Box•Simple storage, easy intersection test•Rotationally invariantstruct Point { int x; int y;}struct circle { Point c; // center int r; // radius }rcbool circle_intersect(circle a, circle b) { Point d; // d = b.c – a.c d.x = a.c.x – b.c.x; d.y = a.c.y – b.c.y; int dist2 = d.x*d.x + d.y*d.y; // d dot d int radiusSum = a.r + b.r; if (dist2 <= radiusSum * radiusSum) {return true; } else { return false; }}Compare Euclidean distance between circle centers against sum of circle radii.Axis-Aligned Bounding Boxes (AABBs)•Three common representations►Min-max►Min-widths►Center-radius// min.x<=x<=max.x// min.y<=y<=max.y struct AABB { Point min; Point max;}// min.x<=x<=min.x+dx// min.y<=y<=min.y+dystruct AABB { Point min; int dx; // x width int dy; // y width} // | c.x-x | <= rx | c.y-y | <= rystruct AABB { Point c; int rx; // x radius int ry; // y radius}minmaxmincdxdyryrxstruct Point { int x; int y;}Can easily be extended to 3DAxis Aligned Bounding Box Intersection (min-max)•Two AABBs intersect only if they


View Full Document

UCSC CMPS 20 - Introduction to Collision Detection

Documents in this Course
Load more
Download Introduction to Collision Detection
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Collision Detection and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Collision Detection 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?