I'm looking for a way to find intersection between a ray and an extruded 2D shape or text (defied by a Bézier curve). Any ideas?

  • \$\begingroup\$ When you say 'extruded shape defined by a Bezier curve', do you mean a shape that's been extruded (or swept) along a Bezier curve, or a shape made up of Bezier curves that's been extruded along a straight line? \$\endgroup\$ – Steven Stadnicki May 30 '12 at 0:45
  • \$\begingroup\$ @StevenStadnicki I mean the latter, a shape made up of Bezier curves that's been extruded along a straight line e.g. a 3D text \$\endgroup\$ – Mαzen May 30 '12 at 17:19

The procedure is pretty straightforward; it breaks down into a small set of tests:

  • Transform your space (ray and text) so that the text lies in the XY plane and has been extruded along the Z axis; in fact, by judicious application of scaling matrices, you can set it up so that the Z-extrusion is from 0 to 1.
  • Figure out the values of t along your (transformed) ray (I'm presuming that your ray is of the form P=Po+Dt, where Po is the origin of the ray and D is its direction) that correspond to the values of z=0 and z=1; for instance, at z=1 we have 1=Po_z+D_z*t1, or in other words t1=(1-Po_z)/D_z. (Note that if D_z=0 - in other words, if the ray is in a plane perpendicular to the extrusion axis - you may have to special-case here).
  • If t0 and t1 are both less than zero, then the extrusion zone is 'behind' your ray and you can't have an intersection (I'm presuming your ray is one-sided here and that you don't care about intersections behind the camera).
  • Otherwise, set t0 = max(t0, 0) - this means that you won't start looking for intersections before the head of your ray or before the 'extrusion zone'.
  • Compute the two positions along your ray corresponding to (the new) t0 and t1, say P0 and P1. These are the endpoints of the line segment you'll check; they correspond to the part of your ray that lies within the extrusion zone.
  • Now, 'project down' to the plane of your extruded 2d shape by just throwing away the Z-component of your points P0 and P1 (this is the reason behind the transformation back in the first step). All the work from here will be done in two dimensions.
  • Perform a point-in-shape test on P0 (I'll explain how to do this in a few moments). If this test comes back positive, then your intersection time is at t0 (with the end-cap of the shape) - note that if t0=0, this can mean that your ray started within the shape, which is another thing that you may want to special-case.
  • Finally, find the first intersection (if any) of your line segment with the 2d shape; that t value will be the time along your ray that you intersect the extruded shape.

Of course, that last step is where all the details lie. It's not too hard to do segment-Bezier intersection and you can find most of the details with a bit of hunting around the web, but there are a lot of complications, and little tricks that you can do to speed things up and do as few tests as possible:

  • For starters, if your 2d shape is particularly complex then you may want to build a (2d) bounding volume hierarchy for it and use that to cull out pieces of your shape that can't possibly intersect the ray. Once you do this, you should be left with a (hopefully-short) list of individual Bezier curve segments (defined by their four control points C0, C1, C2, C3) that you need to test your line segment against.
  • You can shorten your line segment after every 'hit' that you find; for instance, if you find a segment-Bezier intersection at t2, then record t2 as the currently-closest hit point, and reset your segment's endpoints to be (t0, t2) for testing against the rest of the curves (since for the most part you no longer care about intersections after that point).
  • The most straightforward way to do the segment-Bezier intersection is by recursively subdividing the Bezier curve: keep a stack of curve chunks to test, and then at each step pop the current curve chunk off the stack. If it's 'short enough' (that is, the total distance between its control points is less than some threshold), then approximate it by a line segment between its two endpoints and test the intersection of your line segment with the approximating segment. Otherwise, check the intersection of your line segment with the bounding box of the current chunk (you can just use the bounding volume of the chunk's four control points for this bounding box, since the curve is guaranteed to lie between them); if there's no intersection, then you can discard the chunk entirely. If there is an intersection, subdivide the chunk into two subchunks C0, C4, C5, C6 and C6, C7, C8, C3 (this is the usual Bezier subdivision - I can point you to details on this if you need them) and push both of those subchunks onto your 'chunk stack'. Repeat until the stack is empty.

Finally, one detail to clean up: I mentioned doing a point-in-shape test up above. The most straightforward way of doing that is casting a (2d) ray from your point off to 'infinity' in any direction - or at least to a point beyond the overall bounding box of your shape - and count the number of intersections that you hit along the way; if this number is odd then your point is inside the shape, otherwise it's outside. There are a few subtle details to be careful of here - for instance, if your ray runs tangent to some curve segment - but the basic approach works quite well.

  • \$\begingroup\$ One fine explanation indeed. I'll try to implement it and come back once done. \$\endgroup\$ – Mαzen Jun 2 '12 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.