When triangles are moving, do you think their traces as prisms and then check if the two prisms intersect or not? But I think there are some cases that these two prisms intersect with each other, but the two triangles actually don't intersect (although both of them pass the same area, the time could be different). Is that correct?
keenan
@yongchi1 Correct: even if the vertices move along linear trajectories, the volume swept out in time by the triangle is not exactly a triangular prism. Notice for instance that the sides of this "prism" are bounded by four segments that may not be in a common plane: the initial and final edge of a triangle, and two segments connecting vertices in time. Instead, each edge sweeps out a bilinear patch. So to exactly detect if two triangles collide, you'd need to be able to determine if there are any intersections between a pair of bilinear patches at a common time t. (Your quiz should help you build up the tools needed to solve this kind of problem.)
Of course, if the time step is small and/or the motion is slow, then you may be able to get away with using some kind of approximating triangular prism, and just consider plane-plane intersections. But the result will still be approximate.
nrauen
Is there a standard formula or method for doing higher order objects in more dimensions. Would it be similar methods of constantly reducing the problem to a lower dimension the way we are doing with triangles as lines?
theyComeAndGo
Why do we have to approximate the process by stepping through time, if we can use an implicit formula to actually check if there's any solution to this intersection problem?
keenan
@nrauen Nope, no standard formula---just many different possible algorithms, each with its own pros and cons! :-)
keenan
@theyComeAndGo Because solving this implicit equation may be (very) hard, and cannot always be done exactly; one may need to fall back on numerical strategies which do not always work, or can produce inaccurate results (and hence bogus behavior). It is certainly one path people go down, though. If you want to get a sense of this, try completely solving the 3rd question in today's quiz, i.e., try exactly evaluating the intersection time between the point and the segment. :-)
tpan496
Generally how do we decide when to fall back on numerical methods? When would the calculations become too complex to resolve?
keenan
@tpan496 In general there is no easy answer to "which equations can be solved in closed form"; for instance, even for things like quadratic and cubic equations it took mankind hundreds of years to uncover the closed-form solution. These days, fields like algebraic geometry (for instance) provide a lot of knowledge about what kinds of equations can/cannot be solved, though there are still many cases where the answer is not clear.
In practice, you look at the form of equation you have to solve, and then Google around for whether there is a known closed form solution. ;-) For instance, you know that linear systems can be solved, and quadratic equations can be solved. Over time, you come to learn that certain other equations (bilinear, cubic, etc.) can be solved, and get a sense for how stable they are numerically. Sometimes, even if there is a closed form, you may be better off using an iterative numerical approach like Newton's method either for accuracy/stability reasons, or efficiency reasons (or both).
When triangles are moving, do you think their traces as prisms and then check if the two prisms intersect or not? But I think there are some cases that these two prisms intersect with each other, but the two triangles actually don't intersect (although both of them pass the same area, the time could be different). Is that correct?
@yongchi1 Correct: even if the vertices move along linear trajectories, the volume swept out in time by the triangle is not exactly a triangular prism. Notice for instance that the sides of this "prism" are bounded by four segments that may not be in a common plane: the initial and final edge of a triangle, and two segments connecting vertices in time. Instead, each edge sweeps out a bilinear patch. So to exactly detect if two triangles collide, you'd need to be able to determine if there are any intersections between a pair of bilinear patches at a common time t. (Your quiz should help you build up the tools needed to solve this kind of problem.)
Of course, if the time step is small and/or the motion is slow, then you may be able to get away with using some kind of approximating triangular prism, and just consider plane-plane intersections. But the result will still be approximate.
Is there a standard formula or method for doing higher order objects in more dimensions. Would it be similar methods of constantly reducing the problem to a lower dimension the way we are doing with triangles as lines?
Why do we have to approximate the process by stepping through time, if we can use an implicit formula to actually check if there's any solution to this intersection problem?
@nrauen Nope, no standard formula---just many different possible algorithms, each with its own pros and cons! :-)
@theyComeAndGo Because solving this implicit equation may be (very) hard, and cannot always be done exactly; one may need to fall back on numerical strategies which do not always work, or can produce inaccurate results (and hence bogus behavior). It is certainly one path people go down, though. If you want to get a sense of this, try completely solving the 3rd question in today's quiz, i.e., try exactly evaluating the intersection time between the point and the segment. :-)
Generally how do we decide when to fall back on numerical methods? When would the calculations become too complex to resolve?
@tpan496 In general there is no easy answer to "which equations can be solved in closed form"; for instance, even for things like quadratic and cubic equations it took mankind hundreds of years to uncover the closed-form solution. These days, fields like algebraic geometry (for instance) provide a lot of knowledge about what kinds of equations can/cannot be solved, though there are still many cases where the answer is not clear.
In practice, you look at the form of equation you have to solve, and then Google around for whether there is a known closed form solution. ;-) For instance, you know that linear systems can be solved, and quadratic equations can be solved. Over time, you come to learn that certain other equations (bilinear, cubic, etc.) can be solved, and get a sense for how stable they are numerically. Sometimes, even if there is a closed form, you may be better off using an iterative numerical approach like Newton's method either for accuracy/stability reasons, or efficiency reasons (or both).