Sign in to follow this  
codeman_nz

Mapping bezeir curve to tiles

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Quote:
Original post by codeman_nz
How I am doing it is calculating each point along the curve
Well, I can tell you you're not doing that, because there's an infinite number of such points.

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.]

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Quote:
Original post by codeman_nz
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.)

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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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:


#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);



Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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:


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.

Share this post


Link to post
Share on other sites
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?


First, read the comments in my code. ;) Those comments do not exist outside of this thread and were made for you. Follow them.

As LorenzoGatti mentioned, the size of your tiles is completely irrelevant. The important thing is the dimensions of your tile map. Think of your tile map as a bitmap (it is, actually). If you are using an array of chars, you have an 8-bit bitmap, an array of longs would give you a 32-bit bitmap. I have successfully used a tile map as the image pointer to a Win32 GDI bitmap and used GDI calls to set tiles.

Anyway, the point is that no matter what you use to set the tile IDs in your tile map, make sure you stay within the array bounds.

Quote:
Original post by superpig
As a general theory about this - similar to MarkS's solution but without the Bresenham approximation


Of course there are other ways and I know that the Bresenham algorithm is looked down on, but it really is fitting here. Since a tile map is a 2D array of integers, there are no "half tiles", so an integer approximation is the best.

Anyway, I never could get adjacency to work, so I caved and just drew lines to fill the gaps. There is very little to no overdraw and the lines drawn are typically either very short of near vertical/horizontal, so the curve is nearly pixel perfect and far smoother than the typical polyline approximation.

Share this post


Link to post
Share on other sites
Quote:
Original post by codeman_nz
OK thanks. I looked into the Bresenham algorithm and looks like exactly what I need. Now how would I apply it to a road which is several tiles wide?


This is all VERY basic stuff. I want you to think it through, but I'll give you a hint:

You have two vertical Bezier curves defining the sides of the road with horizontal spans of tiles between them. How do you think you ca accomplish this?

Share this post


Link to post
Share on other sites
Thanks for the hint. I should make myself clear about what I'm trying to do.

I have a curved road which is created by a bezier curve going up through the middle. I create 100 points and calculate the parallel points either side of the centre points. The parallel points define the edge of the road.

I am now trying to map the entire road to a tile map. Currently I have Bresenham's line algorithm for the bezier curve going up through the middle of the road and that's working.

I am having trouble with the rest of the road. I tried calculating parallel points from each of the Bresenham's line algorithm points and then using another Bresenham's line algorithm between those parallel points but that didn't work.

I then tried an extension of Bresenham's line algorithm which deals with thick lines but that didn't work.

So now I'm stuck. I can map the centre of the road to the tilemap but can't do it for the rest of the road.

Share this post


Link to post
Share on other sites
I can't really comment on the Bresenham stuff you're doing, but here's an alternate solution you could try. For each tile, calculate the closest point on the curve to the tile center (the easiest way to do this would probably be to subdivide the curve into line segments, and then find the closest point on the line segments making up the curve). Then, if the (squared) distance from the tile center to the curve is below some threshold (e.g. the width of the road plus the half-width of a tile), consider the tile to be part of the road.

Share this post


Link to post
Share on other sites

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