Date: 5 Apr 1995 16:42:44 -0500 From: "Jan Cocatre-Zilgien" Subject: Re: bilinear surface & line To: "Dave Rusin" Reply to: RE>>bilinear surface & line segment intersection Well, what I call bilinear surface is the most direct trajectory surface of a line segment tumbling into 3-D space during some as-small-as-you-want time dt. It is a kind of hyberbolic paraboloid saddle-like surface. I know the position of the 2 endpoints of the line segment at time t, and at time t+dt, and want to find out if the "sweep" the segment has made during dt intersects another line segment, completely known and fixed in space. Tough! Any more hints? Jan ---------------------------- Date: 04-05-95 3:06 PM To: Cocatre-Zilgien, Jan From: Dave Rusin In article you write: >Help! > > Given a bilinear surface (the surface taut like a soapy liquid film) >between 4 points in 3-D space, is there a simple way to know if some >arbitrary line segment between 2 points intersects it? I don't need the >coordinates of the intersection if it exists, only if it intersects or >not. I don't know what a 'bilinear surface' is -- z=a+bx+cy+dxy? -- but it's easy to describe the segment as the set of points P1*t + P2*(1-t) as t ranges from 0 to 1. If you have a description of the surface by one equation and several inequalities, you can always (1) Find the values of t for which P1*t + P2*(1-t) satisfies the equation; (2) reject any values of t not in (0,1); (3) reject any values of t which fail any of the inequalities. This method actually computes the point of intersection (well, it computes t anyway); depending on the presentation of the surface this may not be necessary but I'd have to see the surface to decide. dave #000# ============================================================================== Date: Wed, 5 Apr 95 22:37:54 CDT From: rusin (Dave Rusin) To: jan_cocatre-zilgien@qms1.life.uiuc.edu Subject: Re: bilinear surface & line >Well, what I call bilinear surface is the most direct trajectory surface of a >line segment tumbling into 3-D space during some as-small-as-you-want time dt. >It is a kind of hyberbolic paraboloid saddle-like surface. I know the position >of the 2 endpoints of the line segment at time t, and at time t+dt, and want >to find out if the "sweep" the segment has made during dt intersects another >line segment, completely known and fixed in space. Tough! Any more hints? Interesting. A surface which consists of straight lines (not necessarily parallel to each other) is known as a "ruled surface". An example is those ornaments people hang to blow in the wind which consist of an array of parallel sticks which are then given each a slight rotation from the one before it, resulting in an overall helix shape. I assume this is the kind of surface you wish to describe. Over a short period of time, I guess we can assume the endpoints of the segment move linearly, from points P0 and Q0 to P1 and Q1 respectively. Then over a shorter fraction u of this time, the endpoints move to an intermediate point u P1 + (1-u) P0 and similarly for Q. There is the minor point here that even if dist(P0,Q0)=dist(P1,Q1), it's not true that this equals dist(P(u),Q(u)) for all u between 0 and 1, but we'll ignore this for now. An intermediate point on the segment is parameterized by the fraction v of the distance it lies between P and Q. In particular, the line segment joining the points P(u) and Q(u) (which will be the set of points occupied by the tumbling segment at time u, since tumbling won't change the straightness) is the set of points v P(u) + (1-v) Q(u) for v between 0 and 1. Thus the surface you describe is the set of points parameterized by vu P1 + v(1-u) P0 + (1-v)u Q1 + (1-v)(1-u) Q0, or (Q0) + v (P0 - Q0) + u (Q1 - Q0) + uv (P1 - P0 - Q1 + Q0) as u and v range from 0 to 1 (independently). If you like coordinates, you can write each of the four terms in parentheses in coordinate form as (a1, a2, a3), ..., (d1, d2, d3); then the points are those of the form (a1 + v b1 + u c1 + uv d1, a2+..., a3+...). Now you ask if this surface meets a line segment. Again I can write the curve parametrically, but in my experience it's a little more cumbersome to deal with intersections of two curves both given parametrically (but you can certainly proceed that way too). I might for example describe the line as the set of points satisfying two linear equations in x y and z (that is, write the line as the intersection of two planes). There are infinitely many such expressions for a given line. For example, the line going through (0,0,0) and (1,2,3) may be described by -3x+1z=0, -2x+1y=0. Anyway, see which points on the paramterized surface lie on this line. You need for example -3(a1 + v b1 + u c1 + uv d1) + 1(a3+vb3+uc3+uvd3)=0 and another such equation. With everything else known, this gives two quadratic equations in two unknowns u and v. Solve them by elimination or substitution or whatever to find out what u and v are. You'll usually get more than one solution, but the key issue is whether any of them have both u and v between 0 and 1. That's precisely what it takes for a point on the original surface to lie on the line. Ah, now you notice I dropped the word "... segment". What you have just determined is the set of points in the surface segment which meet the line; to see if these points are actually in the line _segment_, you need some characterization of the segment. Probably you'll have the coordinates of the endpoints R and S. Then the segment is the set of points t R + (1-t) S = S + t (R-S) with t between 0 and 1. If you found any points W in the previous paragraph, be sure to compute the value of t necessary to write W = S + t(R-S); then the point W is a point of intersection with the line _segment_ iff t is between 0 and 1. All this is really straightforward in the sense that it generalizes to any two curves or surfaces which can be described parametrically. Thus if you don't like the bogus assumption that the endpoints of the tumbling segment move linearly, you can substitute whatever parametric expression you do have for their position. The algebra of eliminating u and v will be harder, of course, but in principle the plan of attack is the same. Hope this helps. dave ============================================================================== Date: 6 Apr 1995 11:49:30 -0500 From: "Jan Cocatre-Zilgien" Subject: Re: bilinear surface & line To: "Dave Rusin" Reply to: RE>>bilinear surface & line segment intersection? Thank you very much. That's food for thought. You are right that I want to avoid writing the curves parametrically! In case you wonder what all this is for, it is to be incorporated in a dynamics simulation of wireframe legged machines, where a leg segment can "sidesweep" one from another leg. Jan