Sign in to follow this  

Is there algorithm for boxcasting or thickray casting?

This topic is 1108 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am not sure what the correct name is called but here is my problem: I have implemented a casting ray function that works as expected. However, because I am using a loose grid structure, (ie, objects that overlap multiple grids are only put into one grid), the ray cast may miss certain objects. What I need, I think is a box casting where I need to get every grid the box hits from its initial position to final position. Does anyone have such algorithm? Or pointing out to a solution to this problem, thanks!

This pic from N tutorials is a nice summary of this problem: 6Cp6L.gif

My ray cast implementation only hit the blue cells but as you can see, it may miss certain objects. They are only put into the grid where the x is.

Edited by user12345

Share this post


Link to post
Share on other sites

I'm not sure how the pic shows the problem, since it hits all the objects, is there another case you are thinking of?  It does look like that pic is doing a variation of either a Bresenham or Xu's line drawing algorithm.  You can modify the algorithms to do width.

 

If you really want to, you could just create a rectangle of the desired width, and of the desired length, and test the objects against that.  You could probably do both the line algorithm from the pic as a first pass, and then only test collision with the rectangle against those objects in the blue squares.  That would catch cases where the object is in the tile, but not within the width of the line.

Edited by ferrous

Share this post


Link to post
Share on other sites

The raycast (which is not Bresenhams, since Bresenhams does not catch all the cells the ray traverse through) only hits the blue cells. However, because I am using the loose grid structure, objects are only put into cells where the x is. Thus, in the picture, the ray cast will miss all 3 objects.

 

I am using this as a first pass so false positives are ok. But the ray cast first pass is currently under inclusive. I need something like this:

 

Yd0NY.png

 

Does the algorithm you posted guarantee that all the gray and blue cells will be hit?

Edited by user12345

Share this post


Link to post
Share on other sites

Ah, thanks for the second picture. and longer explanation.  Bresenham will only really miss the diagonal case, Wu's will get it, if that's the kind of granularity you need, and then you just need to modify the width.

Something like http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm

 

Just ignore intensity/alpha for your purposes, and consider it to be 'full intensity' or as a square that has been hit by the sweep.

Edited by ferrous

Share this post


Link to post
Share on other sites

I have implemented Wu's based on the article on the wiki and here is a live version: http://jsfiddle.net/yoc6cq0f/4/. It seems to work ok for x-axis major increments, but sometimes it looks like it misses some diagonals, I dont know if that is just a graphic thing. Also when the mode switches (~45 degrees) there is a noticeable jump with the tiles covered.

 

Also I dont quite know how to apply Wus to a box with x,y, width and height since Wus, as I understand it, only cares about line thickness.

 

 

 

 

 

Relevant portions of the code:

 

function wu(x0, y0, x1, y1){
    var gX0 = x0 * 10;
    var gY0 = y0 * 10;
    var gX1 = x1 * 10;
    var gY1 = y1 * 10;
 
    var yMajor = Math.abs(y1 - y0) > Math.abs(x1 - x0);
 
    var temp;
    if (yMajor){
        // swap(x0, y0);
        temp = x0;
        x0 = y0;
        y0 = temp;
        // swap(x1, y1);
        temp = x1;
        x1 = y1;
        y1 = temp;
    }
 
    if (x0 > x1){
        //swap (x0, x1);
        temp = x0;
        x0 = x1;
        x1 = temp;
        //swap (y0, y1);
        temp = y0;
        y0 = y1;
        y1 = temp;
    }
 
    var dx = x1 - x0;
    var dy = y1 - y0;
    var slopeYX = dy/dx;
 
    // ignore end points for now;
 
    var xend = Math.round(x0);
    var yend = y0 + slopeYX * (xend - x0);
    var xStart = xend;
    var yStart = Math.round(yend);
 
    var errY = yend + slopeYX;
 
    // 2nd end point calcs ommited
    xend = Math.round(x1);
    yend = y1 + slopeYX * (xend - x1);
    var xEnd = xend;
    var yEnd = Math.round(yend);
 
    for (var x = xStart; x < xEnd; x++){
        if (yMajor){
            plot(Math.round(errY)-1, x);
            plot(Math.round(errY), x);
            plot(Math.round(errY)+1, x);
            //console.log(Math.round(errY), x);
            //console.log(Math.round(errY)+1, x);
        } else {
            plot(x, Math.round(errY)-1);
            plot(x, Math.round(errY));
            plot(x, Math.round(errY)+1);
            //console.log(x, Math.round(errY));
            //console.log(x, Math.round(errY)+1);
        }
        errY += slopeYX;
    }
}
Edited by user12345

Share this post


Link to post
Share on other sites

You can get thickness from the box, for your example above, you have the two points of the box perpendicular to the sweep, the distance between them is the thickness.  (or cheat and do as you are in your fiddle with multiple lines being cast)  

 

It looks like you might have some sort of error when the slope is y major, and possibly negative?  I see it flipping from correct to incorrect in certain cases.

Share this post


Link to post
Share on other sites

Hello again, I eventually decided to move away from Wu's because it is missing some diagonal cases and I am not if that is due to my implementation or the nature of algorithm. Anyhow, I devised my own algorithm that performs a true box cast that works here: http://jsfiddle.net/d5ab67fj/1/ and I will leave it there for future googlers that may bump into the same problem.

 

It is incomplete; the ends points are currently over inclusive and the algorithm does not work when x is 0 (or small); that can be easily fixed by allowing it to increment in the Y direction instead of X only. I shall now port it to 3D and hopefully that concludes this exercise for me. Thanks again for your suggest to look into the Wu's algorithm. It gave me the idea on how to tackle the problem.

Share this post


Link to post
Share on other sites

I think you have a collision detection problem, not a ray-casting problem.

Why can't you put a single object in multiple grid cells?  Each cell would contain a list of objects.

I think this would make more sense if you have a very large object that overlaps several grids.

Edited by sevenfold1

Share this post


Link to post
Share on other sites

Dont have objects larger than grid; objects are all fast moving, updating adjacent grids all the time is costly; ray cast/ box cast is less frequent than object updates; although ray cast in loose grid traverse more cells, each cell contains less objects on average.

Edited by user12345

Share this post


Link to post
Share on other sites
I don't know if this method has a name, but you can detect all the blue cells as the union of the cells you enter through a horizontal side and the cells you enter through a vertical side. Both sets are easy to generate, if you think about it for a minute, because the intersections of the ray with the horizontal (/vertical) lines that separate cells are evenly spaced.

You can do that for all three rays in your picture, if that's fast enough. Edited by Álvaro

Share this post


Link to post
Share on other sites

I think what you are suggesting is a ray cast algorithm? If so, I already have an efficient implementation of ray cast that contains no overlaps and generate cells based on the the order they are traversed. Multiple ray casts is of course an solution to this problem but they have 2 main disadvantages. First they return duplicates, second they do not generate cells based on the order they are traversed (as you are doing 1st ray -> 2nd ray etc... ) and thus you can not bail out early if something is already hit.

Share this post


Link to post
Share on other sites
Here, I implemented my own ray cast algorithm and the I modified so every time a new row is visited, all required cells to the right of the new cell are also visited, and similarly with new columns. The code I wrote only works in the case where the ray has a vector with positive x and y coordinates. So if you want to use my code, you'll have to change it to make it work in every case; this is just a proof of concept. [EDIT: Skip down to `visit_cells_in_box_sweep' to get to the meat of the code.]
 
 
#include <iostream>
#include <cmath>

struct Vector {
  float x, y;
 
  Vector(float x, float y) : x(x), y(y) {
  }
};

Vector operator*(float s, Vector const &v) {
  return Vector(s * v.x, s * v.y);
}

float dot(Vector const &v1, Vector const &v2) {
  return v1.x * v2.x + v1.y * v2.y;
}

float length(Vector const &v) {
  return std::sqrt(dot(v,v));
}

Vector normalized(Vector const &v) {
  return (1.0f / length(v)) * v;
}

struct Point {
  float x, y;
 
  Point(float x, float y) : x(x), y(y) {
  }
};

Point operator+(Point const &p, Vector const &v) {
  return Point(p.x + v.x, p.y + v.y);
}

struct Ray {
  Point p;
  Vector v;
 
  Ray(Point const &p, Vector const &v) : p(p), v(v) {
  }
 
  Point at(float t) const {
    return p + t * v;
  }
};

struct Cell {
  int x, y;
 
  Cell(int x, int y) : x(x), y(y) {
  }
 
  Cell() = default;
 
  Cell(Cell const &) = default;
};

bool operator==(Cell const &c1, Cell const &c2) {
  return c1.x == c2.x && c1.y == c2.y;
}

bool operator!=(Cell const &c1, Cell const &c2) {
  return !(c1 == c2);
}

template <typename Function>
void visit_cells_in_box_sweep(Ray const &ray, float half_width, Function f, float max_t) {
  float A = ray.v.y;
  float B = -ray.v.x;
  float min_C = A * (ray.p.x - half_width) + B * (ray.p.y + half_width);
  float max_C = A * (ray.p.x + half_width) + B * (ray.p.y - half_width);
 
  float next_horizontal = std::fmod(1.0f - ray.p.y, 1.0f) / ray.v.y;
  float next_vertical = std::fmod(1.0f - ray.p.x, 1.0f) / ray.v.x;
  Cell last_cell(int(std::floor(ray.p.x)), int(std::floor(ray.p.y)));
 
  while (1) {
    float next = std::min(next_horizontal, next_vertical);
    if (next >= max_t)
      break;
    
    Point intersection = ray.at(next);
    
    Cell cell;
    if (next_horizontal < next_vertical) {
      next_horizontal += 1.0f / ray.v.y;
      cell = Cell(int(std::floor(intersection.x)), int(std::round(intersection.y)));
    }
    else {
      next_vertical += 1.0f / ray.v.x;
      cell = Cell(int(std::round(intersection.x)), int(std::floor(intersection.y)));
    }
    if (cell.y > last_cell.y) {
      // New row
      for (int x = cell.x - 1; A * (x + 1) + B * cell.y >= min_C; --x)
    f(Cell(x, cell.y));
    }
    if (cell.x > last_cell.x) {
      // New columns
      for (int y = cell.y - 1; A * cell.x + B * (y + 1) <= max_C; --y)
    f(Cell(cell.x, y));
    }
    if (cell != last_cell)
      f(cell);
    last_cell = cell;
  }
}

void print_cell(Cell const &cell) {
  std::cout << "Visiting cell at (" << cell.x << "," << cell.y << ")\n";
}

int main() {
  Ray ray(Point(10.75f, 5.5f), normalized(Vector(0.5f, 1.0f)));
  visit_cells_in_box_sweep(ray, 0.5f, print_cell, 10.f);
}
Edited by Álvaro

Share this post


Link to post
Share on other sites

Hi, I implemented your algorithm here : http://jsfiddle.net/u0456cpu/1/, it doesnt seem to be working.

 

Did I do something wrong?

 

function fmod(a,b){
    var result = Math.abs(a) % Math.abs(b);
    if (result<0) result += b;
    if (a >= 0){
        return result;
    } else {
        return - result;
    }
 
function visit_cells_in_box_sweep(x, y, vx, vy, halfWidth, max_t){
    var floor = Math.floor;
    var min = Math.min;
 
    var A = vy;
    var B = -vx;
    var min_C = A * (x - halfWidth) + B * (y + halfWidth);
    var max_C = A * (x + halfWidth) + B * (y - halfWidth);
    var next_horizontal = fmod(1.0 - y, 1.0)/vy;
    var next_vertical = fmod(1.0 - x, 1.0)/vx;
 
    var last_cell_x = floor(x);
    var last_cell_y = floor(y);
 
    var _ = 100; // break out of infinite loop just in case
    while (_>0){
        _--;
        var next = min(next_horizontal, next_vertical);
        if (next >= max_t)
            break;
        var rx = x + next * vx;
        var ry = y + next * vy;
        if (next_horizontal < next_vertical){
            next_horizontal += 1.0/ vy;
        } else {
            next_vertical += 1.0/ vx;
        }
        var cx = floor(rx);
        var cy = floor(ry);
 
        if (cy > last_cell_y){
            // new row
            for (var _x = cx - 1; A * (_x+1) + B * cy >= min_C; --_x){
                plotColored(_x, _y, 10, "black");
                //console.log(_x, _y);
            }
        }
        if (cx > last_cell_x){
            // new columns
            for (var _y = cy - 1; A * cx + B * (_y+1) <= max_C; --_y){
                plotColored(cx, _y, 10, "black");
                //console.log(cx, _y);
            }
        }
        if (cx !== last_cell_x && cy !== last_cell_y){
            plotColored(cx, cy, 10, "black");
           // console.log(cx,cy);
            last_cell_x = cx;
            last_cell_y = cy;
        }
    }
 
    x *= 10;
    y *= 10;
    vx *= 10;
    vy *= 10;
    halfWidth *= 10;
    ctx.beginPath();
    ctx.moveTo(x,y);
    ctx.lineTo(y+vx,y+vy);
    ctx.closePath();
    ctx.strokeStyle = "red";
    ctx.stroke();
 
    ctx.strokeRect(x-halfWidth, y-halfWidth, halfWidth*2, halfWidth*2);
}
Edited by user12345

Share this post


Link to post
Share on other sites
There were several details you got wrong. Here's a fixed version:

function visit_cells_in_box_sweep(x, y, vx, vy, halfWidth, max_t){
    var floor = Math.floor;
    var min = Math.min;

    var A = vy;
    var B = -vx;
    var min_C = A * (x - halfWidth) + B * (y + halfWidth);
    var max_C = A * (x + halfWidth) + B * (y - halfWidth);
    var next_horizontal = fmod(1.0 - y, 1.0)/vy;
    var next_vertical = fmod(1.0 - x, 1.0)/vx;

    var last_cell_x = floor(x);
    var last_cell_y = floor(y);

    var _ = 100; // break out of infinite loop just in case
    while (_>0){
        _--;
        var next = min(next_horizontal, next_vertical);
        if (next >= max_t)
            break;
        var rx = x + next * vx;
        var ry = y + next * vy;
        var cx;
        var cy;
        if (next_horizontal < next_vertical){
            next_horizontal += 1.0/ vy;
            cx = floor(rx);
            cy = floor(ry+.5);
        } else {
            next_vertical += 1.0/ vx;
            cx = floor(rx+.5);
            cy = floor(ry);
        }
        
        if (cy > last_cell_y){
            // new row
            for (var _x = cx - 1; A * (_x+1) + B * cy >= min_C; --_x){
                plotColored(_x, cy, 10, "red");
                //console.log(_x, _y);
            }
        }
        if (cx > last_cell_x){
            // new columns
            for (var _y = cy - 1; A * cx + B * (_y+1) <= max_C; --_y){
                plotColored(cx, _y, 10, "blue");
                //console.log(cx, _y);
            }
        }
        
        if (cx !== last_cell_x || cy !== last_cell_y){
            plotColored(cx, cy, 10, "black");
           // console.log(cx,cy);
            last_cell_x = cx;
            last_cell_y = cy;
        }
    }

    x *= 10;
    y *= 10;
    vx *= 10;
    vy *= 10;
    halfWidth *= 10;
    ctx.beginPath();
    ctx.moveTo(x,y);
    ctx.lineTo(y+vx,y+vy);
    ctx.closePath();
    ctx.strokeStyle = "red";
    ctx.stroke();

    ctx.strokeRect(x-halfWidth, y-halfWidth, halfWidth*2, halfWidth*2);
}
Edited by Álvaro

Share this post


Link to post
Share on other sites

Thanks for fixing it up! I was doing it more for curiosity than anything else.  Pretty neat algorithm. Too bad it is a few days too late for me sad.png. Still, I am sure others may find it useful.

Edited by user12345

Share this post


Link to post
Share on other sites

Actually now that I tested your algorithm a little, I found it missing cells when vx or vy is very small. I think this is because you are only tracing the ray from center of box then appending the row and columns. So if vx or vy is very small, the ray from center of box may still be in the same row/column. Whereas a ray from the corner of box may have intercepted other cells.

 

Oh and here is the fixed version for future reference: http://jsfiddle.net/u0456cpu/2/

Share this post


Link to post
Share on other sites
I see the problem, but I disagree somewhat with your diagnosis. The issue is that a column is not visited until a square in that column is hit by the central ray. If you allow the ray to go much further (multiply t_max by 10 and allow 1000 iterations), you can't see the problem in the demo anymore.

Right now I am thinking that my code might be OK for a range of angles, say between 22.5 and 67.5 degrees. For vectors closer to being aligned with an axis, it's probably better to visit adjacent squares only in rows, to the left and to the right. But I suspect there is a more elegant solution waiting to be found.

Share this post


Link to post
Share on other sites

This topic is 1108 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this