From: Robert Schneiders <rjs@magmasoft.de>
Subject: Re: Q: Isect. of 2 polyhedra meshes
Date: Fri, 30 Apr 1999 15:24:12 +0200
Newsgroups: sci.math.num-analysis

Volker,

check Michael Aftosmis' web pages (Cart3D):

http://george.arc.nasa.gov/~aftosmis/

Hope it helps


 Robert


Dr. Robert Schneiders
MAGMA Giessereitechnologie GmbH
D-52072 Aachen
Kackertstr. 11
Germany
Tel.: +49-241-88901-13
email: rjs@magmasoft.de
www:   http://www-users.informatik.rwth-aachen.de/~roberts/



Volker W. Elling wrote:

> I am interested in a fast way of computing the intersections of two
> polygon
> (2D) resp. polyhedra (3D) meshes. An intersection is a triple (i,j,A)
> where
> i,j are the indices of the polygon in the first resp. the polygon in the
> second set and A is the intersection area (or volume).
> The algorithm has to produce (implicitly or explicitly) a list of all
> nonempty intersections.
>
> My first attempt was a divide-and-conquer method
> that halves both sets based on i-coordinates (i=x or y alternatingly):
> - The median m of all i-coordinates is computed.
> - Polygons appear in the first half if the i-coordinate of all their
> vertices
>   are smaller than m, in the second half if all i-coordinates are larger
> than
>   m, and in both halves otherwise. Obviously, polygons cannot intersect
> if
>   they do not appear in the same half.
> - Divide-and-conquer stops when the set halves are not
> significantly smaller than the respective set.
>
> However, the ratio of empty vs. nonempty intersections turns out to be
> 40:1 (for rather benign 2D meshes). The computation time is roughly
> proportional to the number of times a pair of polyhedra is checked for
> intersections.
>
> What I need is
> (1) a more efficient divide-and-conquer or maybe scan-line
>     method for limiting the number of possible intersections, and
> (2) a fast method of intersecting polygons/polyhedra, especially
> optimized
>     for triangles/quadrilaterals (asymptotic complexity for a large
> number of
>     vertices does not matter, I need a fast method for few vertices).
>
> This problem appears in fluid flow or elasticity codes using Lagrangian
> coordinates: the grid moves along with the fluid/solid and becomes
> rather distorted after some time steps. It has to be "rezoned" into
> another,
> more regular, grid. The intersection area is needed for conservation of
> mass,
> heat energy, and other variables. A good solution is most likely
> interesting
> to other people on this newsgroup as well. All papers I found treat
> special
> cases only (for example, new grids parallel to coordinate axes etc).
>
> Any ideas/references?
>
> -- Volker Elling        Computer science/Mathematics, RWTH Aachen,
> Germany
>
> -- Volker Elling        Computer science/Mathematics, RWTH Aachen,
> Germany
> -- http://lem.stud.fh-heilbronn.de/~elling