3d game engine function

[theturk1234]

Hi guys,

I'm developing a game engine. I need just one more function for it to be functionally operational.

I need a function to determine where a line intersects a square.

A line is simply defined by two points.
A square is just four coplanar points.

I know the coordinates of the line endpoints and the vertexes of the square.

Any ideas for a function to determine where they intersect? Assume that they do indeed intersect.

Thanks,
theturk1234

[gunnerfunner]

Does a line intersect a square => does a line intersect any of the four lines that make up the square => does a line intersect another line

See here for a C++ implementation to this question:

http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

[theturk1234]

Thanks gunnerfunner.
That is an excellent tutorial for determining where two line segments intersect.
But how could I use that to determine where a line and a square intersect?
I've looked all over but I really can't find a solution.

[Zhuge]

If you look over gunnerfunner's first sentence, they mention that checking if a line intersects a square is equivalent to checking if a line intersects any of the square's edges.

[theturk1234]

I don't understand. Am I missing something? How can checking if a line intersects another line determine where it intersects a square? I mentioned in my first post that the line does indeed intersect the square I need to make a function to find out WHERE it intersects. It has to work on any square and a line that intersects.

[Zhuge]

If a line intersects any edge of the square (these are four individual lines), then it intersects the square. The point that it intersects the square will be the same as where it intersects the edge(s), if ever. So, if you can figure out where a line intersects another line, repeating that process four times for each edge of the square will tell you where that line intersects the square.

[mbozzi]

The assumption in the posts above (which isn't necessarily reasonable in a 3D engine) is that the polygon and the ray are coplanar.

I know the thread is marked as "solved", but one way to do this is to solve the linear system describing the line and the plane in which the polygon appears, and then testing to see if any of the solutions lie inside the polygon.

You can do that by sending a ray through the polygon and counting the number of times it intersects a facet before it intersects the solution.
https://en.wikipedia.org/wiki/Point_in_polygon

In the case where there are an infinite number of solutions (i.e., the line and the plane are both parallel and coplanar), just do what Zhuge says.

If there are no solutions to the linear system, then of course they don't intersect.