I need help with scripts that detect if two line segments intersect. The main problem I'm having is understanding dot product. If anyone can help, please reply!

What I would do, is the following:

And then when one line is done

Then if the first pen color is touching the second, do something

shoresbeep wrote:

What I would do, is the following:

And then when one line is done

Then if the first pen color is touching the second, do something

Thanks for trying to help, but I need a script that calculates it using math, so I can work with it in 3D. Different pen colors doesn't help, as the lines could intersect visually but not in space.

I see, can I get a link to the project?

shoresbeep wrote:

I see, can I get a link to the project?

I haven't really created much of a project yet, I've just been googling how to find the dot product and stuff.

Hmm, sorry I couldn't help…

Can't you just use?

It should work.

peppermintpatty5 wrote:

Can't you just use?

It should work.

No, for some reason, it doesn't work. Plus, I want the lines to be the same color. As I said in my reply earlier, the lines may intersect visually (on the screen, so touching (color) would come out true) while in 3D space, they would not be touching.

ianrocks wrote:

peppermintpatty5 wrote:

Can't you just use?

It should work.

No, for some reason, it doesn't work. Plus, I want the lines to be the same color. As I said in my reply earlier, the lines may intersect visually (on the screen, so touching (color) would come out true) while in 3D space, they would not be touching.

Aha, a 3D project! Well, I assume you have theoretical x, y, and z coordinates programmed in already. I also assume you know a good deal about math. Maybe you could test to see if two lines have an intersection point by substituting the equations of the lines into each other to determine if (and where) the lines intersect. It's a lot easier to see if lines intersect in the second dimension though. So with 2 dimensional lines, you would have equations like
x + 2y - 5 = 4x + y -20
and
x = 90 - y
I just made those two equations up, but substituting the line equations into each other will return an ordered pair. I don't know if this is helpful to you since I'm just throwing out random information, but I sincerely hope you can get your project to work.

peppermintpatty5 wrote:

ianrocks wrote:

peppermintpatty5 wrote:

Can't you just use?

It should work.

No, for some reason, it doesn't work. Plus, I want the lines to be the same color. As I said in my reply earlier, the lines may intersect visually (on the screen, so touching (color) would come out true) while in 3D space, they would not be touching.

Aha, a 3D project! Well, I assume you have theoretical x, y, and z coordinates programmed in already. I also assume you know a good deal about math. Maybe you could test to see if two lines have an intersection point by substituting the equations of the lines into each other to determine if (and where) the lines intersect. It's a lot easier to see if lines intersect in the second dimension though. So with 2 dimensional lines, you would have equations like
x + 2y - 5 = 4x + y -20
and
x = 90 - y
I just made those two equations up, but substituting the line equations into each other will return an ordered pair. I don't know if this is helpful to you since I'm just throwing out random information, but I sincerely hope you can get your project to work.

That is slightly helpful, however, when drawing the lines, the sprite goes to a point in space and then goes straight to another point. Finding the equation is a whole other matter. I looked up how to check for intersection and found a good explanation, but I can't seem to find a scratch tutorial on vector lines and dot product. I saw one once, and it was great, but I don't remember where I saw it. If you can find a good tutorial, I would really appreciate it.

shoresbeep wrote:

http://scratch.mit.edu/projects/40821/

Thank you!

If you're looking to check whether two arbitrary straight line segments in 3d actually intersect each other, then you're likely to hit rounding issues in the general case.

I'd say that your best bet would be to check the shortest distance between the two lines extended to infinity. If that distance is within some value (that you will have to decide is appropriate for your purposes) then you can carry on to see if the points of nearest approach of the two infinite lines are within the actual segments of the lines.

Anyway, for the dot-product of two vectors…

Given a 3d vector (i.e. a direction in 3d space, with 3 components): x1,y1,z1, and another: x2,y2,z2, the dot-product is a single value which comes from multiplying together the corresponding components of the two vectors, and adding everything:
dot-product = x1*x2 + y1*y2 + z1*z2

One thing it's very useful for is finding the angle between two vectors, because it turns out that:
dot-product = length of vector (x1,y1,z1) * length of vector (x2,y2,z2) * cosine of angle between vectors


When working with 3d vectors, you will probably also find the cross-product useful to know about, but I'll leave that for another time (it's actually quite handy for finding the closest approach of two lines…)

DadOfMrLog wrote:

If you're looking to check whether two arbitrary straight line segments in 3d actually intersect each other, then you're likely to hit rounding issues in the general case.

I'd say that your best bet would be to check the shortest distance between the two lines extended to infinity. If that distance is within some value (that you will have to decide is appropriate for your purposes) then you can carry on to see if the points of nearest approach of the two infinite lines are within the actual segments of the lines.

Anyway, for the dot-product of two vectors…

Given a 3d vector (i.e. a direction in 3d space, with 3 components): x1,y1,z1, and another: x2,y2,z2, the dot-product is a single value which comes from multiplying together the corresponding components of the two vectors, and adding everything:
dot-product = x1*x2 + y1*y2 + z1*z2

One thing it's very useful for is finding the angle between two vectors, because it turns out that:
dot-product = length of vector (x1,y1,z1) * length of vector (x2,y2,z2) * cosine of angle between vectors


When working with 3d vectors, you will probably also find the cross-product useful to know about, but I'll leave that for another time (it's actually quite handy for finding the closest approach of two lines…)

That helps so much! I just have one more thing to ask you: online, I found a formula to see if two lines intersect, but the equation was this h = ( (A-C) * P ) / ( F * P ) where * is dot product, not multiply. What does it mean, F dot product P? Here's the full equation I found:

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )
This h number is the key. If h is between 0 and 1, the lines intersect, otherwise they don't. If F*P is zero, of course you cannot make the calculation, but in this case the lines are parallel and therefore only intersect in the obvious cases.
The exact point of intersection is C + F*h.

ianrocks wrote:

shoresbeep wrote:

http://scratch.mit.edu/projects/40821/

Thank you!

No problem

ianrocks wrote:

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )

OK, from what you say above, I'm not clear about something…

The above points (A,B,C,D) and vectors (E,F,P) are all 2d - so do you actually only want to find the intersection of two lines on the 2d screen (so, they were 3d lines, but are now projected into 2d on the screen?), or are you really wanting to check for (near-)intersection in 3d space?

It makes some difference to the complexity of the answer…!

DadOfMrLog wrote:

ianrocks wrote:

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )

OK, from what you say above, I'm not clear about something…

The above points (A,B,C,D) and vectors (E,F,P) are all 2d - so do you actually only want to find the intersection of two lines on the 2d screen (so, they were 3d lines, but are now projected into 2d on the screen?), or are you really wanting to check for (near-)intersection in 3d space?

It makes some difference to the complexity of the answer…!

Sorry about that, I mean I want to check for line segments intersecting in 3D space. I would also like to figure it out for 2D though.
The main thing I would like to figure out, is how to check for a line segment intersecting a face of a polyhedron.

ianrocks wrote:

Sorry about that, I mean I want to check for line segments intersecting in 3D space.

OK, right - that does make things somewhat more complicated to explain than just the formula you have above…

ianrocks wrote:

I would also like to figure it out for 2D though.

2d is easy compared to 3d…

ianrocks wrote:

The main thing I would like to figure out, is how to check for a line segment intersecting a face of a polyhedron.

Oh, wow, proper collision-detection, eh…? I haven't got around to adding that into even my own 3d framework, yet, ‘cos it’s a lot of work to make it efficient for the general case…

OK, I can tell you some of the general thoughts I have about how I plan to do this myself (hopefully… maybe… one day…) Hopefully, it'll give you some ideas how to make an efficient collision-detection algorithm:

• if you have multiple 3d objects which are polyhedra with flat surfaces, bounded by straight-line edges, then the main thing you'll need is, as you say, to check intersection of line segments with faces.

• If you have more than a few of these 3d objects, then checking every line against every face all the time will be too expensive.

The above conclusion means we need to find a way to eliminate most cases as quickly as we can:

• If you are rendering with 3d, then you probably have some way to order the objects or surfaces that you are drawing on-screen (roughly, the furthest rendered first, the nearest last).

• The above suggests you have some kind of distance-order list, with an entry for each object you need to render (e.g. each surface, polyhedron, line, or however you split things for rendering).

• If you also create some kind of bounding sphere to go with each object (i.e. a minimum sphere centred on the point that's used in the order-list above, and which will contain the whole object), this means you have a way to immediately rule out many objects that cannot be touching each other. (They can only be touching if their order-distances are near enough for their bounding spheres to be touching).

• The above possible bounding-sphere touching test can so far only tell anything about objects that overlap in distance (from viewer), but don't tell anything about overlap ‘sideways’ (i.e. left-right & up-down from viewer's point-of-view).

• If there are still a number of possibly touching items it may be worth performing a complete set of bounding-sphere tests on them, to rule out more cases before turning to better intersection tests.

OK, so we've now got to the point of having to check specific objects to see if they intersect - for which face-line intersection is key…

• The best way *might be* to, again, try to rule out as many cases as possible quickly, so it's likely that checking bounding-boxes for each line/face pair is the way forward.

• So, for each line, find the min & max x,y,z co-ords of the points at the line ends. And for each face, find the min & max x,y,z co-ords of the points at the corners. These min & max co-ords define ‘bounding-boxes’ (cuboids) for these objects, and you can check very quickly if any line's box overlaps with a face's box. If not, then you rule out any further need to check intersection for that line/face pair.

• For any remaining line/face pair, you'll need to perform a more exact face/line intersection test.

I say “might be” above, since it's possible that doing the extra work of the bounding-boxes could prove not worthwhile if there are usually not that many remaining possible intersections after the bounding-sphere tests before. Probably the only way to know for sure is to try it in-game and see which works best.

Checking for intersection of a line segment with a face would have three parts:
1) Find the point where the infinite line intersects the infinite plane defined by the face.
2) Then check if that point lies within the line segment.
3) If so, finally check if the point also lies within the bounds of the face.
4) If it does, you've got a collision! (AT LAST!)

I think there's plenty for you to be thinking on *before* you get to the exact line/face intersection itself, and this post is already long enough, and I have some other things to do now. So I'll leave it there and work a bit later on typing up a (hopefully) reasonable explanation of how to do each of the above stages (1) to (3) for the line/face intersection (I'm assuming the simpler bounding-sphere/bounding-box checks above make enough sense as I've described them for you to be able to do something with them - let me know if not…)

DadOfMrLog wrote:

ianrocks wrote:

Sorry about that, I mean I want to check for line segments intersecting in 3D space.

OK, right - that does make things somewhat more complicated to explain than just the formula you have above…

ianrocks wrote:

I would also like to figure it out for 2D though.

Checking for intersection of a line segment with a face would have three parts:
1) Find the point where the infinite line intersects the infinite plane defined by the face.
2) Then check if that point lies within the line segment.
3) If so, finally check if the point also lies within the bounds of the face.
4) If it does, you've got a collision! (AT LAST!)

I think there's plenty for you to be thinking on *before* you get to the exact line/face intersection itself, and this post is already long enough, and I have some other things to do now. So I'll leave it there and work a bit later on typing up a (hopefully) reasonable explanation of how to do each of the above stages (1) to (3) for the line/face intersection (I'm assuming the simpler bounding-sphere/bounding-box checks above make enough sense as I've described them for you to be able to do something with them - let me know if not…)

Thank you so much for your help. I am fairly new to 3D stuff, so I am not 100% sure what you mean by bounding-boxes. I am at the stage where I can create most polyhedra with code, but I have yet to create an actual 3D room. I am not sure how to make the camera move. What I have so far is the camera is in a fixed position, with just the rendered shape rotating and zooming in/out. I am also not good at rendering order. I know how to do the filled faces, where it only renders if the points are arranged clockwise, but other than that, I can't do rendering order. Take a look at my games Navigation 3D and The Impossible Game 3D. For Navigation 3D, I used a variable that contains the overall x rotation mod 360 to see what should render first. For The Impossible Game 3D I used the same concept, but I don't know how to order the actual obstacles in relation to the cube, so it always renders the cube last for some reason. I attempted to script it, but it didn't change anything. If you know of any tutorials on rendering order, I would very much appreciate it if you could tell me.

P.S. When I have trouble with rendering order, I just make everything the same color XD

ianrocks wrote:

Thank you so much for your help. I am fairly new to 3D stuff, so I am not 100% sure what you mean by bounding-boxes.

Pretty much really as I described just before I used the term: the min & max values of the x/y/z co-ords for points in an object. That defines the smallest cuboid, with sides aligned with the x,y,z axes, that contains the object. Such a cuboid is useful as a quick way to eliminate non-touching sets of objects, so you avoid doing the much more expensive accurate touching tests on objects that cannot actually be touching.

TBH, though, I suspect that bounding-spheres might be accurate enough to catch nearly as many cases as bounding-boxes, and it's quicker than checking bounding-boxes, so it could end up being efficient enough just to go straight from bounding-sphere to fully accurate intersection test (without the bounding-box test).

ianrocks wrote:

I am at the stage where I can create most polyhedra with code, but I have yet to create an actual 3D room. I am not sure how to make the camera move.

OK, camera movement is easy, really - just change the offset of the points for the other objects (effectively, change what they consider to be the ‘origin’ point by adding an offset to all their co-ordinates). What's more difficult (and what you're probably thinking of) is camera rotation…

ianrocks wrote:

What I have so far is the camera is in a fixed position, with just the rendered shape rotating and zooming in/out. I am also not good at rendering order. I know how to do the filled faces, where it only renders if the points are arranged clockwise, but other than that, I can't do rendering order.

Yes, render order is actually technically impossible to get right in every case…

What I mean is that there is no algorithm that will render any arbitrary set of 3d objects in the right order from every viewpoint (even if those objects are not actually touching/intersecting each other yet…)

A simple example that shows the problem is to think of how you interleave four flaps at the top of a cardboard box to make it stay shut. If you look from the top then every one of the flaps overlaps another. If you now tilt and separate the flaps a bit, so they're no longer touching, you can see that they can still overlap, even though not touching. So there's no way you can draw the whole of each of them in a certain order to make it look right - any flap you choose has part of another flap behind it, so cannot be drawn first!

ianrocks wrote:

If you know of any tutorials on rendering order, I would very much appreciate it if you could tell me.
P.S. When I have trouble with rendering order, I just make everything the same color XD

Yes, cheat. -It really is the best way for render-ordering, since there isn't a way that can work for all cases.

For my own 3d framework I just order the list of objects (which I call ‘components’, each being something like a line/point/surface/polyhedron in 3d space, and used to build potentially larger 3d ‘structures’) by the distance from the viewer of the ‘average’ position of their points - i.e. the mean of all the points that the component contains. That can't possibly work in all cases, so I do have a couple of extra little tricks (cheats!), but essentially that's all there is to it - just take the list of objects, order by some measure of their distance from viewer, and then draw from furthest to nearest.

I guess none of that answers the original question of intersection though - maybe we'll get to that eventually…