Point in Spline

Assuming the spline forms a simple, closed curve, the parity rule for rays still holds. If your point is inside the curve, then a ray originating at that point will intersect the curve in an odd number of _transverse_ intersection points.

In the polygon inclusion test, if the ray intersects a vertex and both edges sharing the vertex are on the same side of the ray, you have to adjust your intersection counting. Such a vertex counts as one intersection. It is possible the ray passes through a vertex but the shared edges are on opposite sides of the ray. This also counts as one intersection.

For the curve case, now you need to test whether the ray intersects the curve transversely (the intersection locally partitions the curve into two pieces, one on each side of the ray). If the intersection is not transverse, then the ray is tangent to the curve with the property that the local partition produces two curve pieces, both on the same side of the ray. This intersection counts only as one.

Now for an alternative that avoids the curve-ray intersection testing. You store the cubic spline in your efficient format. Consider having a bounding region (circle, rectangle, or low-vertex-count polygon) for the trigger. When the game character enters that region, you know he is capable of walking over the trigger. At this time, you generate a high-resolution polygon by sampling the spline. Use the point-in-polygon test now to see if the trigger is activated. Assuming the character makes it past that region without triggering an event, you can then discard the high-resolution polygon. Thus, the increased memory usage is only temporary, you avoid the more expensive point-in-curve test, and you need a point-in-bounding-region test (which is presumably something easy to implement for your choice of bounding region).

Quote:

Original post by Wasting Time Now for an alternative that avoids the curve-ray intersection testing. You store the cubic spline in your efficient format. Consider having a bounding region (circle, rectangle, or low-vertex-count polygon) for the trigger. When the game character enters that region, you know he is capable of walking over the trigger. At this time, you generate a high-resolution polygon by sampling the spline. Use the point-in-polygon test now to see if the trigger is activated. Assuming the character makes it past that region without triggering an event, you can then discard the high-resolution polygon. Thus, the increased memory usage is only temporary, you avoid the more expensive point-in-curve test, and you need a point-in-bounding-region test (which is presumably something easy to implement for your choice of bounding region).

Ah. Yeah, I currently have the spline inside a cylindrical volume that is scaled to fit the spline by the editor. Having the geo be temporary is definitely an interesting idea.

And the point-in-poly uses the ray counting method as you describe to determine collision.

However, I'm generating the vertices because I couldn't find/figure out how to do a straight up ray-curve intersection test. Everything I found was using something like strip trees to perform the actual ray-spline collision. I had been hoping for a more algebraic solution. The only solution that came close was one that required the curve to not extend outwards past it's vertices (a condition that doesn't work for me). Is there a non-iterative solution to ray-parameterized curve intersection?

-me

First, to correct my post, I said that if the ray intersects the polygon at a vertex, and both local edges are on the same side of the ray, the intersection is counted once--I meant twice. If one edge sharing the vertex is on one side of the ray and the other edge is on the other side of the ray, then the intersection is counted once.

Regarding an algebraic solution. Let the ray be P + s*D, where P is the ray origin, D is the unit-length ray direction, and s >= 0 is a scalar. Let E be a vector that is perpendicular to D. Consider the cubic polynomial A0 + t*A1 + t^2*A2 + t^3*A3, where A0 through A3 are 2-tuples and t is a scalar with 0 <= t <= 1. To find the intersection, set P + s*D = A0 + t*A1 + t^2*A2 + t^3*A3. Dot the equation with E to get 0 = (A0-P).E + t*A1.E + t^2*A2.E + t^3*A3.E. This is a cubic polynomial equation for which there are closed-form solutions (although you need to worry about numerical round-off problems when using floating-point arithmetic). If any of the t-roots is in [0,1], then for such a t, you can compute s by dotting the equation with D: s = (A0-P).D + t*A1.D + t^2*A2.D + t^3*A3.D. If s >= 0, you have an intersection.

cool. thanks very much.

-me