From: Robert Schneiders 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