Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

127 Neutral

About user12345

  • Rank
  1. user12345

    AABB swept collision response with voxel world

    Rather than bring the object exactly to the edge, leave some space between them but also set the velocity opposite to normal to 0. 
  2. user12345

    AABB swept collision response with voxel world

    You need to find the closest collision first. Then do your collision response against that. Run the collision + resolution again using the time left and new position and velocity.
  3. 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/
  4. 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 . Still, I am sure others may find it useful.
  5. 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;     } } // based on http://en.cppreference.com/w/cpp/numeric/math/fmod implementation   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); }
  6. 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.
  7. 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.
  8. 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.
  9. 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;     } }
  10. 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:     Does the algorithm you posted guarantee that all the gray and blue cells will be hit?
  11. 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:  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.
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!