can you recast the problem in some way? regenerate the patch in line-segment space perhaps?
or can you just switch to a subdivision or parametric surface scheme where the surface passes though the control points? beziers have always seemed cumbersome to me, not only for modelling objects, but also for rendering. i''ve actually never understood why they caught on.
james
Colliding a Bezier Patch and a linesegment
They''re not actually bezier surfaces, they''re just uniform quadratic spline surfaces (the way I''m doing it, anyway). They''re very appealing to me because of the flexibility; all you have to do is give a set of points and it makes a smooth surface approximating or interpolating the points for you. I don''t know how else you would go about modeling an organic form that needs to be an accurate model of some real object. Field objects are cool, but not really practical for me. What we are trying to do is analytically solve a parametric system, so that we have a closed-form solution for an arbitrary set of points.
ok.
provided that the surface passes through the control points, you can simply transform the patch into the ray space to cast it as a two dimensional lookup problem instead of a disgustingly complex parametric solution. this solution will yield the exact answer, and probably in comparable time to approximations.
it is much more difficult to do this with beziers (which is why i asked) because you have to rebuild the patch so that geometrically it is identical, but based in a diffenent plane, and so all the control point locations get royally screwed up.
the steps:
transform the patch with a transformation matrix that has a forward vector parallel to the line segment. the up and right vectors can be whatever you want, provided up, right, and forward are all perpendicular. there is no translation or scaling, so you should use a 3x3 rotation matrix.
find which of the resulting patch poly(s) the line segment intersects. this is a 2D intersection problem as the ray will appear as a point. (note that when i say polys i mean the ones defined by your control points, not a tesselation of the patch)
for each intersected poly, find the u/v coordinates in the transformed patch of the ray.
feed those uv coordinates into the transformed patch to get the depth (or z) coordinate. check to see that the depth falls within the limits of the line segment.
if it''s within the limits, then you have a collision. if all you want is whether there was a collision, you can stop there, if you need to know exactly where it happened, invert the transformation matrix you used on the patch by transposing it (which works because it is a pure rotation matrix) and transform the collision point back.
this in my mind is much more simple than working it out in world-space, which is cumbersome at best. it also has lots of opportunity for early exit conditions to avoid unnecessary computation and is not an approximation, which is always nice.
hope this helps,
james
provided that the surface passes through the control points, you can simply transform the patch into the ray space to cast it as a two dimensional lookup problem instead of a disgustingly complex parametric solution. this solution will yield the exact answer, and probably in comparable time to approximations.
it is much more difficult to do this with beziers (which is why i asked) because you have to rebuild the patch so that geometrically it is identical, but based in a diffenent plane, and so all the control point locations get royally screwed up.
the steps:
transform the patch with a transformation matrix that has a forward vector parallel to the line segment. the up and right vectors can be whatever you want, provided up, right, and forward are all perpendicular. there is no translation or scaling, so you should use a 3x3 rotation matrix.
find which of the resulting patch poly(s) the line segment intersects. this is a 2D intersection problem as the ray will appear as a point. (note that when i say polys i mean the ones defined by your control points, not a tesselation of the patch)
for each intersected poly, find the u/v coordinates in the transformed patch of the ray.
feed those uv coordinates into the transformed patch to get the depth (or z) coordinate. check to see that the depth falls within the limits of the line segment.
if it''s within the limits, then you have a collision. if all you want is whether there was a collision, you can stop there, if you need to know exactly where it happened, invert the transformation matrix you used on the patch by transposing it (which works because it is a pure rotation matrix) and transform the collision point back.
this in my mind is much more simple than working it out in world-space, which is cumbersome at best. it also has lots of opportunity for early exit conditions to avoid unnecessary computation and is not an approximation, which is always nice.
hope this helps,
james
great thinking there james! im glad you proved there is indeed a analitical solution to this. damn hate approximations :|
Author
Wow! Major kudos, James 
I don''t see why transforming my Bezier control points into ray space is so bad.. the patch passes through the corner points, so provided the middle points are in the same position relative to the quad defined by the corner points, I don''t see a problem.
So, let me try and work my head around this...
We build a rotation matrix to get the patch into ray-space, by rotating by some function of (ray dot (0,0,1))...
We apply that matrix to all the control points of the patch.
We test the (X,Y) start position of the ray against the transformed X,Y coordinates of the control points, and figure out which set of 4 points encompass the (X,Y) start position of the ray (if any). Then, we use interpolation to get U,V coordinates on the patch.
OK, I think I''ve got that. I''ll need to find out how to collide a point with an arbitrary quad...
So after that we use the standard bezier method to find the coordinates of the point at (U,V), and the Z value that we get...
k = (Z - rayStart.z)/rayLength
where k is the scaling factor for the vector, yes?
Time to go implement and see if I *really* understood
Thanks to everyone who participated in this, particularly vanillacoke and James...
Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
I don''t see why transforming my Bezier control points into ray space is so bad.. the patch passes through the corner points, so provided the middle points are in the same position relative to the quad defined by the corner points, I don''t see a problem.
So, let me try and work my head around this...
We build a rotation matrix to get the patch into ray-space, by rotating by some function of (ray dot (0,0,1))...
We apply that matrix to all the control points of the patch.
We test the (X,Y) start position of the ray against the transformed X,Y coordinates of the control points, and figure out which set of 4 points encompass the (X,Y) start position of the ray (if any). Then, we use interpolation to get U,V coordinates on the patch.
OK, I think I''ve got that. I''ll need to find out how to collide a point with an arbitrary quad...
So after that we use the standard bezier method to find the coordinates of the point at (U,V), and the Z value that we get...
k = (Z - rayStart.z)/rayLength
where k is the scaling factor for the vector, yes?
Time to go implement and see if I *really* understood
Thanks to everyone who participated in this, particularly vanillacoke and James...
Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
hi,
i was moving, which is why i didnt reply earlier
the problem with beziers (which as far as i know have points that are not on the surface) is that determining exactly which of the interior regions of the patch that the ray can possibly intersect is the same problem as you started with. to work around it you could rebuild the bezier so that all the edge vertices and interior control points were in ray space, but finding where those points should be located to exactly duplicate the untransformed geometry but on a different reference plane would be prohibitively expensive.
if you require the control points to be on the surface, you can divide the surface on any arbitrary plane (provided the patch is not planar and the reference plane perpendicular) you know with certainty which regions the ray can potentially intersect.
as for the intersection, make 2d lines out of each edge by discarding depth. for a quad, the point that the ray maps to should be above two edges, and below the other two. anything else and it does not intersect.
once you have the uv values from interpolation, the easiest way to find out if the ray actually intersects that point on the patch is to get the patch value, and compare it against the depth values for the start and end of the ray, one should be larger, one smaller if it intersects.
glad to be of service,
james
i was moving, which is why i didnt reply earlier
the problem with beziers (which as far as i know have points that are not on the surface) is that determining exactly which of the interior regions of the patch that the ray can possibly intersect is the same problem as you started with. to work around it you could rebuild the bezier so that all the edge vertices and interior control points were in ray space, but finding where those points should be located to exactly duplicate the untransformed geometry but on a different reference plane would be prohibitively expensive.
if you require the control points to be on the surface, you can divide the surface on any arbitrary plane (provided the patch is not planar and the reference plane perpendicular) you know with certainty which regions the ray can potentially intersect.
as for the intersection, make 2d lines out of each edge by discarding depth. for a quad, the point that the ray maps to should be above two edges, and below the other two. anything else and it does not intersect.
once you have the uv values from interpolation, the easiest way to find out if the ray actually intersects that point on the patch is to get the patch value, and compare it against the depth values for the start and end of the ray, one should be larger, one smaller if it intersects.
glad to be of service,
james
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
