hi all i have a fairly interesting contact problem i'm hoping some of you may have be able to help out with. I have a large set of interconnected line segments (3D) to which i am adding new segments to one by one. one end of each new line segment is attached to the end of another of the segments in the domain. Each new node has a position prescribed to it through other equations, which can't gaurantee that the line segment created won't intersect another in the domain. I am ok with a method for detecting contacts (subdivide the space, get possible contacts with this subdivided space, then find actual contacts), but am looking for the best way to resolve these. I could have a few contacts at the same time, am restricted to only moving one point of the line segment, and need to try and keep as close to the original orientation of the original segment as possible. I would like to do this in as few a passes as possible, and have been heading down the route of trying to take into account all contacts and near contacts before deciding how to move the segment. Obviously though this is quite tricky and any other ideas you may have would be most welcome! thanks for any ideas you can offer, mike

Won't the 3D line segments pretty much never intersect with any given point because of numericasl inaccuracies? Perhaps we need a better definition of intersect, perhaps with regards to time and one line "crossing" another?

Are there any constraints on how new segments are added? e.g. can you garunatee there will never be cycles? This would change how you could detect the contacts.

i should have mentioned that all these line segments have a radius associated with them.
each segment is representing part of a pre-defined periodic function, and there are a few hundred such functions, all starting at the same point.
I can't delete contacts, i need to move the end point of the new segment to avoid contact, and the next segment will start from that new end point position.
ie i have several hundred continuous curves, and i am adding each segement of a curve into the system one by one.

Ok so its more like interconnected cylinders you are talking about rather than actual line segments. But I'll refer to them as line segments if you prefer.

The first thing that springs to my mind is that line segments which have common nodes are necessarily going to intersect, to make things simple you could just ignore intersections of line segments with common nodes.

As I understand it you are essentially trying to represent a bunch of curves defined by some mathemetical equations with line segmenents, so if this is the case you could ignore contact between segments belonging to the same curve. But if all your curves depart from the same starting point, and you decrease the segment size to a small value all curves will intersect even when ignoring contacts between line segments with common nodes. That is going to be a problem.

For solving intersection problems I suggest you have a look at this, it's partly relevant :)

http://www.gamasutra.com/resource_guide/20030121/jacobson_pfv.htm

look at the "Rigid Bodies" section, especially where it talks about colliding sticks. Your problem should be much easier to solve than that described in this paper if you are constrained to moving only one of the nodes on the line segment.

thanks all. spacedude - my curves all start from different points, albeith on the same plane (initially). i've got an algorithm pretty much sorted now, but thanks anyway.
mr rhodes, i was after a way to resolve contacts, rather than find them. There is already a nice spacial search implemented which is fine for this application. in particular i was looking for a way to guarantee contact resolution with one movement (ie not move into contact with other segments)
I ended up with a pretty simple vector calculation, in case anyone cares =)