Home Products Download Order Contacts


Subject: Joining points to form 3D convex polygon


I have a problem which has come up during my attempt to solve another

I am trying to find the intersection between a 3D triangle and a convex
polyhedron. I have managed to work out a way of doing this by working
out where each edge of the triangle intersects the polyhedron and also
where each edge of the polyhedron intersects the triangle.

The problem is, what I end up with are a series of points, all of which
are either on the edges of or within the triangle (i.e. all in the same
arbitrary 3D plane) but I cannot see an easy way to determine how to
traverse these points to describe the resultant convex polygon in 3D.

I have started out by trying to work out every single scenario of
intersection and treat each one as a separate case to determine the
order of the points, however this is proving very time consuming and I
am not convinced I will cover all cases as it can be hard to visualise
the different scenarios for this problem.

Another idea occurred to me which is that if I can work out the
shortest path between all the points, this will by definition be the
path that describes the convex polygon.

My questions are:

1) Is that correct and will it always work?
2) Is there a straightforward algorithm to do this? The maximum number
of points will be 10 I think.
3) Whatever I come up with will have to be reasonably fast as I am
having to perform this intersection calculation many different times
although it is not "real-time" e.g. game or anything, it is a CAD
4) Is there an easier way to achieve what I am trying here?




View All Messages in comp.graphics.algorithms


Re: Joining points to form 3D convex polygon

Copyright 2006 WatermarkFactory.com. All Rights Reserved.