Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // My method
- //
- // Things that are pre-computed:
- // local space edge normals and polygon projection onto edge.
- //
- // Things that are computed once per-update (on rotation change) and re-used in all
- // collision detection that occurs.
- //
- // world space edge normal (a rotation with cached sin/cos)
- // world space projection (gprojection = dot(object.pos, normal) + lprojection)
- // world space vertex perpdots: proj0 = perpdot(normal, vertex0)
- function circle2poly(circle, polygon) {
- var max_edge = null;
- var max_overlap;
- for (edge in polygon.edges) {
- var axis = edge.normal;
- var overlap = edge.gprojection - dot(circle.centre, edge.normal) - circle.radius;
- if (overlap < 0) return no_intersection; // early exit.
- if (max_edge == null || overlap > max_overlap) {
- max_overlap = overlap;
- max_edge = edge;
- }
- }
- var proj = perpdot(max_edge.normal,circle.centre);
- if (proj < max_edge.proj0) return circle2circle(circle.centre, circle.radius, max_edge.vertex0, 0);
- if (proj > max_edge.proj1) return circle2circle(circle.centre, circle.radius, max_edge.vertex1, 0);
- else return { axis : max_edge.normal, overlap : max_overlap };
- }
- function circle2circle(p0, r0, p1, r1) {
- var del = p0 - p1;
- var lsq = dot(del, del);
- var rsum = r0 + r1;
- if (lsq > rsum*rsum) return no_intersection;
- var dist = sqrt(lsq);
- return { axis : (del / dist), overlap : rsum - dist };
- }
- // Summary:
- // for each edge, we compute dot product, and 2 subtraction.
- // can get an early exit on any edge (possibly first one) -> quick to discard seperating case.
- //
- // 1 further dot product decides if we can exit with edge-circle intersection
- // or need to consider one of the two vertices.
- //
- // If we consider a vertex, we have subtraction, dot product, addition, multiplication
- // to get an exit.
- //
- // Otherwise in worst-case scenario, a division, 2 multiplications, sqrt and subtraction.
- //
- // Your method
- //
- // Things that can be pre-computed:
- // reciprocal of squared length edge (ilengthsq)
- //
- // Things computed once per update (change in rotation)
- // world space edge vector
- function circle2poly(circle, polygon) {
- var closest_axis = null;
- var closest_dist;
- for (edge in polygon.edges) {
- var t = dot(circle.centre - edge.vertex0, edge.edgeVector) * edge.ilengthsq;
- if (t < 0) t = 0; elif (t > 1) t = 1;
- var axis = circle.centre - (edge.vertex0 + (edge.edgeVector * t));
- var axislsq = dot(axis, axis);
- if (closest_axis == null || axislsq < closest_dist) {
- closest_axis = axis;
- closest_dist = axislsq;
- }
- }
- closest_axis = normalise(closest_axis);
- var circle_proj = dot(closest_axis, circle.centre) + circle.radius;
- var poly_proj = -inf;
- for (vertex in polygon.vertices) {
- var vproj = dot(vertex, closest_axis);
- if (vproj > poly_proj) poly_proj = vproj;
- }
- var overlap = poly_proj - circle_proj;
- if (overlap < 0) return no_intersection;
- else return { axis : closest_axis, overlap : overlap }
- }
- // Summary:
- // We have NO early exits!
- //
- // For each edge we compute 2 subtractions, a dot product, and a multiplication
- // A further 2 subtractions, 2 additions, and 2 multiplications
- // A further dot product.
- //
- // for normalisation, a dot product, sqrt, division and 2 multiplications
- //
- // another dot product and an addition.
- // For each vertex we compute a dot product
- //
- // Then a final subtraction at which point we determine intersection, or success.
- // Comparison: My method wins.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement