# UMD CMSC 427 - Collisions and Intersections (6 pages)

Previewing pages*1, 2*of 6 page document

**View the full content.**## Collisions and Intersections

Previewing pages *1, 2*
of
actual document.

**View the full content.**View Full Document

## Collisions and Intersections

0 0 45 views

Other

- Pages:
- 6
- School:
- University of Maryland, College Park
- Course:
- Cmsc 427 - Computer Graphics

**Unformatted text preview: **

Collisions and Intersections When objects move test for collision When projecting surfaces check for intersections Many slides adapted from Amitabh Varshney Collision Strategy Brute force test Fine if few shapes Test by bounding with simpler shape Only do brute force if necessary Use hierarchy of simpler shapes Faster for complex scenes 1 2D Intersections Sides intersect Or one inside other Sides Intersect Intersect lines and check whether intersection point is inside each line segment Check if each line divides other line segment in half 2 How to tell whether two line segments intersect First convert to equations for lines x1 y1 x2 y2 goes to y y2 y1 x2 x1 x y1 x2 x1 x1 y2 y1 Now suppose we have two lines y m1x b1 y m2x b2 Solve for x and y For example we have m1x b1 m2x b2 x b1 b2 m2 m1 Now we want to know whether x y is in between x1 y1 and x2 y2 and the same for the other line segment One simple way is to tell whether the sum of the distance from each end point to x y is the same as the distance between the end points This is a bit cumbersome We can do things with less computation by checking whether the line of line segment one divides the endpoints of line segment two and vice versa To do this compute the line the first line segment lies on and represent it as ax by c where a b is a unit vector Then compute a b x1 y1 c1 and a b x2 y2 c2 We should have either c1 c c2 or c2 c c1 One shape inside another Easier for convex shapes Convex polygon is inside iff all vertices are inside Vertex is inside iff it is on inside of each side If shape isn t convex decompose it into convex shapes 3 Recall from before how to tell if a point is inside a convex shape by judging whether it is on the appropriate side of each bounding line of the shape We can write a line as a b x y c Then a side of the line is a b x y c or c Circles easier Testing whether two circles intersect is much easier So put a circle around each shape How x2 y2 x1 y1 r1 r2 x2 x1 2 y2 y1 2 r1 r2 2 4 Circles

View Full Document