On Apr 2, 2:08=A0pm, IsaacKuo <mech...@[EMAIL PROTECTED]
> wrote:
> 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. =A0By
> calculating the true distance, you're essentially looking for
> intersections between cylinders. =A0There 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. =A0For line segments which are
> mostly parallel to the XY plane, then the segments need
> to be closer than epsilon. =A0But 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.
>
Ok, I'll admit that, hadn't really thought that all the
way through. Might make an early acceptance test, but I'm
not sure if it would save any processing time.
> > 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. =A0It's going to depend on
> exactly what you're doing with the results.
Depends a lot on the input data too, I can think of some
degenerate cases where AABB + line-to-line testing would
come out on top.
----
Geoff
|
