Problem with bird's eye view or 2.5D rendering of Map

Question

I'm developing a turn-by-turn navigation software and I'm using the following solution to make my lines of roads into 2.5D or 3D View

http://stackoverflow.com/questions/2808393/draw-2-5d-or-3d-map-with-c-from-lines

However, above solution is quite okay for lines within the view port which is 0 < x < width and 0 < y < height . However there are lines that its points may have y < 0 or x < 0 or y > height or x > width and then the above solution gone crazy. Could anyone help me figure out how to solve the problem?

vvvv With 3D algorithm vvvv

.

vvvv Without 3D algorithm vvvv

Update:: After using this code

double x = p->x();
double y = p->y();

double t = -0.5;
x = x - w / 2;
y = y - h / 2;
double a = h / (h + y* sin(t));
double u = a * x + w / 2;
double v = a * y * cos(t) + h / 2;

p->setX(u);
p->setY(v);
return p;

The map become like following

I think there's something wrong with Y calculations when they go way beyond negative values. I'm using Qt and cracks at line seems bug with Qt renderer, not related to our original problem.

Answer 1

The problem with the equation is that it allows the projected x value to cross the mid-line (w/2). This is not desirable when trying to model a perspective transform since lines should approach, but do not cross, a vanishing point. Also, because of the way the equation is written, this crossing happens in front of the camera instead of behind, which leads to unnecessary artifacts. Try something like this instead:

halfW = w/2
dx = (x - halfW)
dy = (h - y) // y increases downwards
// tune these constants to taste.
top = 1.25
bottom = 0.75
lowerBound = 0.1 // Avoids divide by zero and perspective lines crossing midline
x_ = (dx / max(lowerBound, (bottom + ((dy / h) * (top - bottom))))) + w/2

Answer 2

The problem is that the transformation you are using does not map straight lines to straight lines. Rather, straight lines generally go to parabolas. You can see that in the example images, where the more-or-less-straight main road going from top to bottom in the 2D view is transformed to a curved road in the 2.5D view. You would see the same thing for the lines that "go crazy" in your example if you broke them up into shorter segments.

Mathematically, you can see what is going on by going back to the transform you're using:

x_ = (x - w/2)*(t1+(y/h)*(t2-t1)) + w/2
y_ = y

If we express a straight line as x = ay+b, then a point (ay+b,y) on this line maps to (ay+b - w/2)*(t1+(y/h)*(t2-t1)) + w/2,y). This expression looks complicated, but you can see that it evaluates to something like (c*y^2+d*y+e,y), for suitable values of c,d,e, which is a parabola.

So your best bet is to abandon this transform and switch to a perspective transform.

In your original question, you mentioned that a non-affine transform of a rendered image was too slow. It seems that you have now switched to transforming the lines before rendering them, and that is fast enough. The only thing you have to do now is change the transform.

Here's a suggested transform. It is a couple of steps, and takes your 2D (x,y) coordinates to some 2.5D (u,v) coordinates. I assume you're using C#.

t = 0.3 // tilt angle - try different values    
X = x - w/2 ;
Y = y - h/2 ;
a = h/(h + Y*Math.Sin(t)) ;
u = a*X + w/2 ;
v = a*Y*Math.Cos(t) + h/2 ;

There is a parameter t here that defines the amount of tilt, expressed in radians. I'd suggest playing with a value of somewhere around 0.3, plus or minus.

I've worked this out with pencil and paper, but not run it, so let me know if this doesn't work .. it's always possible that there's been a transcription error.

Update: You want to avoid drawing any entity (line, polygon, whatever) that has a point (x,y) such that a is non-positive. Better still, to avoid overflow, you should avoid drawing when a<epsilon, where epsilon is some small positive value like 0.05 or 0.1.