On Apr 2, 12:50=A0pm, Geoffrey Summerhayes <sumr...@[EMAIL PROTECTED]
> wrote:
> On Apr 2, 12:25=A0pm, IsaacKuo <mech...@[EMAIL PROTECTED]
> wrote:
> > However, Bentley-Ottmann is a good start. =A0First, you use Bentley-
> > Ottmann
> > while ignoring the Z dimension to determine candidate intersections.
> > Then
> > you calculate the distance between the lines of the candidates to
> > determine
> > whether they are "close enough".
> > The distance between two line segments is calculated by first
> > determining the unit normal. =A0Do this by calculating the cross
> > product of the line segment vectors, and normalize to a length
> > of one. =A0This gives you a unit vector which is perpendicular to
> > both of the line segments. =A0Then, take the difference between
> > two points of either line (i.e. take either endpoint of each line
> > segment), and dot product it with that unit normal. =A0The
> > absolute value of this dot product is the distance between the
> > two lines. =A0If that value is less then "epsilon", your arbitrary
> > value for "close enough", then the line segments intersect.
> Actually, since you have a possible point of intersection
> (x-y) wouldn't it be simpler to determine the z on both
> lines at that point and compare the difference to epsilon?
> If they do intersect, it has to occur at that point.
That's a possibility, but it's has more aliasing effects. By
calculating the true distance, you're essentially looking for
intersections between cylinders. There very tips of the
cylinders are chopped off in a way which isn't symmetric,
but that's a pretty small "error".
What you suggest will make the critical distance sensitive
to line segment alignment. For line segments which are
mostly parallel to the XY plane, then the segments need
to be closer than epsilon. But if a line segment is angled
at theta from the Z axis, then the critical distance is
epsilon/sin(theta).
Depending on the application, that might mean an artificially
low number of intersections with line segments that are
mostly aligned to the Z axis and/or an artificially high number
of intersections with line segments that are roughly parallel
to the XY plane.
> The only problem is that Bentley-Ottmann doesn't really
> work in 3d. Unlike 2d, it's possible for the 'above' and
> 'below' lines not to intersect, but still have others that
> do, so you can't reject it during the search.
> So the only way I can see of using the algorithm, is to
> keep all the possible intersections during the xy pass
> and run through the points and the lines that intersected
> there and check the z afterwards.
Right, with the caveat that checking for 3d intersections
afterward may not be so obvious. It's going to depend on
exactly what you're doing with the results.
Isaac Kuo
|
