Line Intersecting Polygon Not Working

Newbie & Debugging Questions
#1

Hi There,

I’m writing a small space game using libgdx, the ship fires a laser, and I need to calculate when (if ever) it intersects a poly (asteroids). This is so I can stop the laser passing through the objects, and actually collide with them. My code seems to work some of the time, and completely fails at other points. I can’t figure out what causes it to fail, I’m pretty sure it’s not my poly definitions that are wrong, as sometimes it will work on an edge, other times not, there is no consistency.

I have checked the trace of my ray (strictly speaking a line) and it is spot on, so it’s not that. Here is the code, I’ll try to explain what I’ve done after.



//Beam Collisions

//If the beam isn't being fired, return
if(!active) return;
	
//Storing all the points to be checked on the beam, I've checked the all seem accurate, and have draw a line between them and they match the laser.	
List<Vector2> beamPoints = new ArrayList<Vector2>();

//Step allows me to reduce the number points I test when it finally works
int step = 1;
for(int n=0;n<maxHeight;n+=step){
	
        //Rotation is the rotation of the ship. I add 90 to it so the angle of my vector is from the x-axis. 
        //shipX is the world coords of the ship. x is the relative start point of the laser to the ship.
        //shipX refers to the centre of the ship, not the corner of the graphic.
	beamPoints.add(
			new Vector2(shipX+x+(float)(n*Math.cos(Math.toRadians(rotation+90))),
						shipY+y+(float)(n*Math.sin(Math.toRadians(rotation+90)))));
}
	
//Here I cycle through the entities to test if they collide. Currently the only entities are asteroids.	
for(Entity e : entities){
        //Skip over the entity if it's outside the render range or it has no geometry.
	if(!e.inRenderRange || e.getGeometry()==null) continue;

        //A list to store all the vertices of that asteroids geometry.
	List<Vector2> verts = new ArrayList<Vector2>();
	for(Vector2 v : e.getGeometry()){
		
                //Determining the x and y of the vertice to store. e.x is the asteroids world coords, I subtract the half the imageWidth because it's position is stored as the centre of the graphic.
                //I then add the relative x and y of the vertex.
                //I've turned off rotation for the asteroids, so that's not a problem.
		float nx = (e.x-e.imageWidth/2)+v.x;
		float ny = (e.y-e.imageHeight/2)+v.y;
		
		verts.add(new Vector2(nx,ny));
		
	}
	
        //Testing each of the points on the beam to see if there are in the poly.
	for(int j=0;j<beamPoints.size();j++){
		
                //Using Intersector, a class in Libgdx, I can safely assume this is working fine. 
		if(Intersector.isPointInPolygon(verts, beamPoints.get(j))){
			
                        //Changing the height (should be labelled length) of the beam to be that at which it collides. Step is one, so doesn't matter for now.
			height = j*step;
			break;
		}
	}
	
	
}

I should also point out from the following images that by the laser I mean the bright core, I haven’t bothered messing around with it’s glow, that’s not faulty, I just haven’t done it yet.

I hope this is enough code to go by, if there is anything else I can provide please ask; I’m greatful for whatever help you can give.

Cheers guys,

Daniel

#2

to fix your problem, you shouldn’t test laser-points, but just if the line of the laser is intersecting the triangles.
you would do it like this.

the laser is a half-line(?) so has a starting point and a direction.
the geometry you want to check against has a bunch of line-segments(start&end point or starting point + direction + length)

then just check if the half-line of the laser intersects any of the segments.

half-line intersection test with segment:


Halfline laser;
Segment geoPart;

if(abs(laser.dir dot geoPart) != 1)//dot=vector dot product; check if not parallel and are because of that intersecting
{
  //get intersection point and check if infront of laser(dot product > 0) and is in the segment
  //sry to lazy to write it for you^^ 
}
return false;
#3

The laser is line not a ray, it has a direction, a start point and a length, it’s a finite distance.
The geometry consists of line segments with start and end points (A list of vertices in order, from which I can deduce the points of the segments).

Would this affect your code in any way? I’m not particularly experienced in vector mathematics.

Thanks

#4

so your laser is a line-segment then? one start and end point.
a geometrie is build from line-segments.
you just have to check for each line-segment of your geometry if it intersects with the line-segment of the laser.
So just write a line-segment class, which has a “boolean intersects(LineSegment other)” method. Get a Iterable from your geometry and check


for(LineSegment s: geometry.getSegments())
{
  if(s.intersects(laser.getSegment())) return true;
}
#5

Off topic, but I’d recommend using Actors and Stages, so that you can just call actor.hit() and other built in methods, it also provides the ability to draw/update all actors thru the stage. If you’re interested take a look: http://code.google.com/p/libgdx-users/wiki/scene2d#Actor
http://code.google.com/p/libgdx-users/wiki/scene2d#Stage