Line/Vector Intersection with Hieght Map

What I have so far: - The position of the camera's eye - A method of converting 2D input into a 3D point (OpenGL gluUnProject) (This seems to get a point just in front of the camera's eye) - Therefore, a vector can be created from the above two points (a line drawn representing this vector can be clearly seen to intersect with the map, but only when viewed from a different angle to that when the vector was created) - A height map (a uniform grid of heights) - A function that calculates the height at *any* point on the map What I would like to achieve: - To find the first intersection point of this vector on the map (there is the possibility of having more than one point) I have the idea of passing the x and y values of the vector to the height calculation function and comparing the result to the z value of the vector, scaling the (original) vector by a small amount if false and repeating. The problem with this is that the increment could "skip" over the first true value. Additionally, I could incorporate a range to the height check. Again, this has the possibility of producing an incorrect result. Is there a more accurate way of achieving this? Or should I attempt a completely different approach (in terms of input)? Thanks for any help with this

I'd basically walk the map cells using a DDA algorythm, to find the tiles underneath the ray, then test intersection with the tile triangles (the two of them).

It is possible to optimise the ray-tile triangle test, by just doing a ray-half plane intersection.

the DDA :

#include <stdio.h>#include <stdlib.h>#include <math.h>#include <gl/glut.h>inline float frand(float x=1.0f){	return (rand() / (float) RAND_MAX) * x;}//===========================================================================// VECTORS//===========================================================================class Vector{public:	float x,y;public:	inline Vector(void)	{}	inline Vector(float Ix,float Iy)	: x(Ix)	, y(Iy)	{}	inline Vector &operator /=(const float Scalar)	{ x /= Scalar; y /= Scalar;		return *this; }	inline Vector &operator *=(const float Scalar)	{ x *= Scalar; y *= Scalar;		return *this; }		inline Vector &operator +=(const Vector &Other) { x += Other.x;	y += Other.y;	return *this; }	inline Vector &operator -=(const Vector &Other) { x -= Other.x;	y -= Other.y;	return *this;	}	inline float operator ^ (const Vector &V)	const	{	return (x * V.y) - (y * V.x); } // cross product	inline float operator * (const Vector &V)	const	{	return (x*V.x) + (y*V.y); } // dot product	inline Vector operator * (float  s)			const	{	return Vector(x*s, y*s); }		inline Vector operator / (float  s)			const	{	return Vector(x/s, y/s); }		inline Vector operator + (const Vector &V)	const	{	return Vector(x+V.x, y+V.y); }			inline Vector operator - (const Vector &V)	const	{	return Vector(x-V.x, y-V.y); }	friend Vector operator * (float k, const Vector& V) {	return Vector(V.x*k, V.y*k); }		inline Vector operator -(void) const { return Vector(-x, -y); }		inline float length(void) const { return (float) sqrt(x*x + y*y); }	void randomise(const Vector& min, const Vector& max)	{		x = frand(max.x - min.x) + min.x;		y = frand(max.y - min.y) + min.y;	}};//--------------------------------------------------------------------------// window size//--------------------------------------------------------------------------float width  = 640;float height = 480;float zoom = 30.0f;Vector start;Vector end;void Reset(){	start.randomise(Vector(0, 0), Vector(width / zoom, height / zoom));	end.randomise(Vector(0, 0), Vector(width / zoom, height / zoom));}void renderPixel(int x, int y){	glColor4f(1, 1, 1, 1);	glBegin(GL_LINE_LOOP);	glVertex2f(x, y);	glVertex2f(x+1, y);	glVertex2f(x+1, y+1);	glVertex2f(x, y+1);	glEnd();}void dda(const Vector& start, const Vector& end){	const float tolerance = 1.0E-8f;		// render segment	glColor4f(1, 1, 1, 1);	glBegin(GL_LINES);	glVertex2f(start.x, start.y);	glVertex2f(end.x, end.y);	glEnd();	// increment	Vector delta = end - start;	Vector inc;	inc.x = (fabs(delta.x) < tolerance)? 1.0f / tolerance : 1.0f / fabs(delta.x);	inc.y = (fabs(delta.y) < tolerance)? 1.0f / tolerance : 1.0f / fabs(delta.y);	// pixel coords	int x = (int)(start.x);	int y = (int)(start.y);	int dx = (delta.x < 0.0f)? -1 : (delta.x > 0.0f)? 1 : 0;	int dy = (delta.y < 0.0f)? -1 : (delta.y > 0.0f)? 1 : 0;	Vector accum;	accum.x = (delta.x < 0.0f)? (start.x - (x)) * inc.x : ((x+1) - start.x) * inc.x;	accum.y = (delta.y < 0.0f)? (start.y - (y)) * inc.y : ((y+1) - start.y) * inc.y;	float t = 0.0f;	// dda	while (t <= 1.0f)	{		renderPixel(x, y);		if(accum.x < accum.y)		{			t		 = accum.x;			accum.x += inc.x;			x		+= dx;		}		else		{			t		 = accum.y;			accum.y += inc.y;			y		+= dy;		}	}}//-----------------------------------------------------// displays the objects//-----------------------------------------------------void Display(){	//--------------------------------------------------------------------------	// render stuff	//--------------------------------------------------------------------------	glClearColor(0, 0, 0, 0);	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);	glMatrixMode(GL_PROJECTION);	glLoadIdentity();	glOrtho(0, width / zoom, 0, height / zoom, -100, 100);		//-----------------------------------------------------------------	// Setup the model view matrix	//-----------------------------------------------------------------	glMatrixMode(GL_MODELVIEW);	glLoadIdentity();		dda(start, end);	glutSwapBuffers();}void Timer(int t){	Display();	glutTimerFunc(t, Timer, (int) 500.0f / 60.0f);}	void Reshape(int w, int h){	width  = w;	height = h;	glViewport(	0, 0, w, h);}void Keyboard(unsigned char key, int x, int y){	if (key == 27)		exit(0);	if(key == ' ')		Reset();}void main(int argc, char** argv){	//--------------------------------------------------------------------------	// OpenGL / GLUT init	//--------------------------------------------------------------------------    glutInit( &argc, argv );	glutInitDisplayMode		(GLUT_DOUBLE | GLUT_RGBA | GLUT_DEPTH);		glutInitWindowSize		(width, height);	glutInitWindowPosition	(0, 0);	glutCreateWindow		("dda");		glEnable				(GL_BLEND);	glBlendFunc				(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);	glDisable				(GL_DEPTH_TEST);	glDisable				(GL_LIGHTING);		glutDisplayFunc			(Display);	glutReshapeFunc			(Reshape);	glutTimerFunc			(0, Timer, (int) 100.0f / 60.0f);	glutKeyboardFunc		(Keyboard);	Reset					();	glutMainLoop			();}

I still maintain the code is correct. It's just the setup that might differ (if your cells are offset by 1/2 a pixel).

Topic Locked