Skip to content

Instantly share code, notes, and snippets.

@mucaho
Created March 13, 2016 00:48
Show Gist options
  • Save mucaho/77846e9fc0cd3c8b600c to your computer and use it in GitHub Desktop.
Save mucaho/77846e9fc0cd3c8b600c to your computer and use it in GitHub Desktop.
approximate distance ray <-> aabb
// See [this tutorial](http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml) and linked materials
//
// return distance to nearest corner of rectangle,
// or return Infinity if no intersection with ray
//
// origin = {_x, _y}
// direction = {x, y}
function approximateDistanceFromRay(origin, direction) {
var epsilon = 0.00000001; //maximum error allowed
var originX = origin._x,
originY = origin._y,
directionX = direction.x,
directionY = direction.y;
// rectangle bounds
var rect = this._cbr || this._mbr || this, // bounding box
minX = rect._x,
minY = rect._y,
maxX = rect._x + rect._w,
maxY = rect._y + rect._h;
var distances = [minX - originX, minY - originY, maxX - originX, maxY - originY], // distances from origin to each extremum of rectangle
minDistances = [Infinity, Infinity]; // minDistance in x and y axis
var axis,
norm,
normedDistances = [Infinity, Infinity, Infinity, Infinity], // distances from origin to each extremum of rectangle (scaled to the directional vector)
normedDistance,
minNormedDistances = [Infinity, Infinity], // // minDistance in x and y axis (scaled to directional vector)
scaledRayX, // the x-coordinate of the ray scaled to the above distance
scaledRayY; // the y-coordinate of the ray scaled to the above distance
if (directionX !== 0) {
norm = 1.0 / directionX;
normedDistances[0] = distances[0] * norm;
normedDistances[2] = distances[2] * norm;
}
if (directionY !== 0) {
norm = 1.0 / directionY;
normedDistances[1] = distances[1] * norm;
normedDistances[3] = distances[3] * norm;
}
for (var i = 0; i < 4; ++i) {
normedDistance = normedDistances[i];
if (normedDistance > 0) {
scaledRayX = originX + normedDistance * directionX;
scaledRayY = originY + normedDistance * directionY;
if ((minX - epsilon <= scaledRayX) && (scaledRayX <= maxX + epsilon) &&
(minY - epsilon <= scaledRayY) && (scaledRayY <= maxY + epsilon)) {
axis = i % 2;
if (normedDistance < minNormedDistances[axis]) {
minNormedDistances[axis] = normedDistance;
minDistances[axis] = distances[i];
}
}
}
}
return (
(minDistances[0] !== Infinity ? minDistances[0] : 0) * directionX +
(minDistances[1] !== Infinity ? minDistances[1] : 0) * directionY
) || Infinity;
}
// See [this tutorial](http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml) and linked materials
//
// return distance to nearest corner of rectangle on smallest axis,
// or return Infinity if no intersection with ray
//
// origin = {_x, _y}
// direction = {x, y}
function approximateDistanceFromRay (origin, direction) {
var rect = this._cbr || this._mbr || this; // bounding box
var minDistance = Infinity,
minIndex = -Infinity;
var epsilon = 0.00000001; //maximum error allowed
var originX = origin._x,
originY = origin._y,
dirX = direction.x,
dirY = direction.y;
// rectangle bounds
var minX = rect._x,
minY = rect._y,
maxX = rect._x + rect._w,
maxY = rect._y + rect._h;
var norm,
distances = [minX - originX, minY - originY, maxX - originX, maxY - originY], // distances from origin to each point of rectangle
normedDistances = [Infinity, Infinity, Infinity, Infinity], // distances from origin to each point of rectangle (scaled to the directional vector)
normedDistance,
scaledRayX, // the x-coordinate of the ray scaled to the above distance
scaledRayY; // the y-coordinate of the ray scaled to the above distance
if (dirX !== 0) {
norm = 1.0 / dirX;
normedDistances[0] = distances[0] * norm; // (minX - originX) * norm
normedDistances[2] = distances[2] * norm; // (maxX - originX) * norm
}
if (dirY !== 0) {
norm = 1.0 / dirY;
normedDistances[1] = distances[1] * norm; // (minY - originY) * norm
normedDistances[3] = distances[3] * norm; // (maxY - originY) * norm
}
for (var i = 0; i < 4; ++i) {
normedDistance = normedDistances[i];
if (normedDistance > 0) {
scaledRayX = originX + normedDistance * dirX;
scaledRayY = originY + normedDistance * dirY;
if ((normedDistance < minDistance) &&
(minX - epsilon <= scaledRayX) && (scaledRayX <= maxX + epsilon) &&
(minY - epsilon <= scaledRayY) && (scaledRayY <= maxY + epsilon)) {
minDistance = normedDistance;
minIndex = i;
}
}
}
// return minDistance; //scaled to directional vector
return distances[minIndex] || Infinity;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment