Hi everyone.
I am creating a road game where curved roads are drawn using bezier curves.
However I am having trouble mapping the curved roads to the tile map. How I am doing it is calculating each point along the curve and then setting the tile to occupied using this:
mymap[(int)(bt.x/10.0)][(int)(bt.y/10.0)] = 1;
However if the gap between the points is too big then it skips the tiles in between.
Any help would be appreciated.
Mapping bezeir curve to tiles
Quote:Original post by codeman_nzWell, I can tell you you're not doing that, because there's an infinite number of such points.
How I am doing it is calculating each point along the curve
You could try iterating over the curve (parametrically, which I assume is what you're doing) in smaller increments, but whether or not you catch every tile will still be dependent on how the control points are configured. A better solution might be to test each tile for intersection with the curve (one option would be to represent the curve as a line strip for this purpose); this should guarantee that no tiles are skipped.
[Edit: It should be possible to construct an exact Bezier curve vs. axis-aligned box test, I think, if you want to go that way.]
Author
Quote:Original post by jykWell, I can tell you you're not doing that, because there's an infinite number of such points.
Yes correct. I am only doing 100 points. But I am worried that increasing the number of points will decrease performance. Also, as you said, there is no guarantees that decreasing the number of increments will get all the points.
What is an exact Bezier curve vs. axis-aligned box test?
Quote:Original post by codeman_nzIt would probably be easier to subdivide the curve, yielding a line strip, and then test the tiles against the individual line segments. (If you need help with the line segment vs. box test, you can ask here or in Math & Physics.)
What is an exact Bezier curve vs. axis-aligned box test?
As for the exact test, this is speculative, but I believe a Bezier curve intersects an axis-aligned box if it intersect an edge of the box, or if its first or last control point is contained in the box. For the edge tests, I believe you can compute the points of intersection with the edges' supporting lines by solving a quadratic or cubic equation (assuming your curves are quadratic or cubic), and then checking to see if any of the intersection points (if there are any) lie on the edge.
Author
Quote:Original post by jyk
What is an exact Bezier curve vs. axis-aligned box test?It would probably be easier to subdivide the curve, yielding a line strip, and then test the tiles against the individual line segments. (If you need help with the line segment vs. box test, you can ask here or in Math & Physics.)
So how would I go the line segment vs. box test?
Since you are using a 2D array of integers, you can treat the tile map as a bitmap and use any type of function used to plot pixels.
Here is some code to demonstrate:
The AdaptiveSubdivideCurve function takes four vertices and a tolerance value (plugging in 1.0f works fine) and draws a Bezier curve with adaptive subdivision. Since two point on the curve in screen space are not guaranteed to be coincident (you'll get gaps), I use a modified Bresenham line drawing algorithm to plot a line of pixels between the two end points when the flatness tests are satisfied. If there is only a single pixel to draw, the DrawLine function plots it and exits.
The floating point variables are needed for the subdivision to work, but just supply integer values for the vertex coordinates.
If your tile map is 100x100, this would draw a bell shaped curve in the tile map:
Here is some code to demonstrate:
#define ABS(x) (x < 0 ? -x : x)#define SIGN(x) ((x) < 0 ? -1 : ((x) > 0 ? 1 : 0))typedef struct vertex{ float x,y;}void DrawLine(int Ax,int Ay,int Bx,int By,float r,float g,float b){ int y,x,dy,dx,sx,sy; int accum; dx = Bx - Ax; dy = By - Ay; sx = SIGN(dx); sy = SIGN(dy); dx = ABS(dx); dy = ABS(dy); Bx += sx; By += sy; if(dx > dy) { accum = dx >> 1; do{ // OpenGL was used to test this. Remove the GL calls // and uncomment your "mymap"line. glBegin(GL_POINTS); glColor3f(r,g,b); glVertex2i(Ax,Ay); glEnd(); //if(((Ax >= 0) && (Ax < maxXBounds)) && ((Ay >= 0) && (Ay < maxYBounds)) //mymap[Ax][Ay] = 1; accum -= dy; if(accum < 0) { accum += dx; Ay += sy; } Ax += sx; }while(Ax != Bx); }else{ accum = dy >> 1; do{ // OpenGL was used to test this. Remove the GL calls // and uncomment your "mymap"line. glBegin(GL_POINTS); glColor3f(r,g,b); glVertex2i(Ax,Ay); glEnd(); //if(((Ax >= 0) && (Ax < maxXBounds)) && ((Ay >= 0) && (Ay < maxYBounds)) //mymap[Ax][Ay] = 1; accum -= dx; if(accum < 0) { accum += dy; Ax += sx; } Ay += sy; }while(Ay != By); }}void AdaptiveSubdivideCurve(vertex p1,vertex p2,vertex p3,vertex p4,float tol){ bool l,r; float xs,ys; float xe,ye; float t; xs = p1.x - p2.x; ys = p1.y - p2.y; xe = p4.x - p2.x; ye = p4.y - p2.y; t = xs * ye - xe * ys; l = ((t * t) <= tol); xs = p1.x - p3.x; ys = p1.y - p3.y; xe = p4.x - p3.x; ye = p4.y - p3.y; t = xs * ye - xe * ys; r = ((t * t) <= tol); if(l && r) { DrawLine(p1.x,p1.y,p4.x,p4.y,0.0f,0.0f,0.0f); }else{ vertex l2,l3; vertex r2,r3; vertex h,m; h.x = (p2.x + p3.x) / 2; h.y = (p2.y + p3.y) / 2; l2.x = (p1.x + p2.x) / 2; l2.y = (p1.y + p2.y) / 2; l3.x = (l2.x + h.x) / 2; l3.y = (l2.y + h.y) / 2; r3.x = (p3.x + p4.x) / 2; r3.y = (p3.y + p4.y) / 2; r2.x = (h.x + r3.x) / 2; r2.y = (h.y + r3.y) / 2; m.x = (l3.x + r2.x) / 2; m.y = (l3.y + r2.y) / 2; AdaptiveSubdivideCurve(p1,l2,l3,m,tol); // Left curve AdaptiveSubdivideCurve(m,r2,r3,p4,tol); // Right curve }}The AdaptiveSubdivideCurve function takes four vertices and a tolerance value (plugging in 1.0f works fine) and draws a Bezier curve with adaptive subdivision. Since two point on the curve in screen space are not guaranteed to be coincident (you'll get gaps), I use a modified Bresenham line drawing algorithm to plot a line of pixels between the two end points when the flatness tests are satisfied. If there is only a single pixel to draw, the DrawLine function plots it and exits.
The floating point variables are needed for the subdivision to work, but just supply integer values for the vertex coordinates.
If your tile map is 100x100, this would draw a bell shaped curve in the tile map:
vertex p1,p2,p3,p4;p1.x = 10;p1.y = 90;p2.x = 10;p2.y = 10;p3.x = 90;p3.y = 10;p4.x = 90;p4.y = 90;AdaptiveSubdivideCurve(p1,p2,p3,p4,1.0f);
Author
Thanks for that, it is very useful. How would I modify this to handle a tilemap with 10x10 pixel tiles?
Quote:Original post by codeman_nz
Thanks for that, it is very useful. How would I modify this to handle a tilemap with 10x10 pixel tiles?
Replace the drawing of pixels, i.e. glVertex2i(Ax,Ay) in the code snippet, with setting tile types in your map array. The size of your tiles doesn't matter.
As a general theory about this - similar to MarkS's solution but without the Bresenham approximation:
You know that the tiles you're trying to mark will form a continuous path from the start to the end of the curve. In fact, it's not just the start and end of the curve: you can pick *any* two points on the curve and the tiles between them should be a continuous path. At the smallest level, it means that picking two nearby points on the curve should yield adjacent tiles.
So, I think something like this would work:
I think there might be a problem with it, though: if AreTilesAdjacent() counts two diagonal tiles as adjacent, then it might miss some tiles, and if it doesn't count them as adjacent, then you might get a stack overflow from curves that juuuuust scrape the corner of a tile. I think there's a solution to this that involves computing the convex hull of the curve segment though.
You know that the tiles you're trying to mark will form a continuous path from the start to the end of the curve. In fact, it's not just the start and end of the curve: you can pick *any* two points on the curve and the tiles between them should be a continuous path. At the smallest level, it means that picking two nearby points on the curve should yield adjacent tiles.
So, I think something like this would work:
void ActivateTiles(BezierCurve curve, TileGrid grid){ ActivateTiles(curve, grid, 0, 1);}void ActivateTiles(BezierCurve curve, TileGrid grid, float p1, float p2){ vertex v1, v2; v1 = curve.SampleParametric(p1); v2 = curve.SampleParametric(p2); TileRef t1, t2; t1 = grid.GetTileAtPoint(v1); t2 = grid.GetTileAtPoint(v2); grid.ActivateTile(t1); grid.ActivateTile(t2); if(grid.AreTilesAdjacent(t1, t2)) return; float midpoint = (p1 + p2) * 0.5f; ActivateTiles(curve, grid, p1, midpoint); ActivateTiles(curve, grid, midpoint, p2);}I think there might be a problem with it, though: if AreTilesAdjacent() counts two diagonal tiles as adjacent, then it might miss some tiles, and if it doesn't count them as adjacent, then you might get a stack overflow from curves that juuuuust scrape the corner of a tile. I think there's a solution to this that involves computing the convex hull of the curve segment though.
I think if the distance between your points is at most half the smallest width or height of a tile, you will get all tiles. See Nyquist's sampling theorem.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
