CGAL users discussion list

["Tomislav Maric" <>]

Hi everyone, 

I'm also interested in this problem using CGAL, as well as a similar one. 

I've found an article [3] where a polyhedron is intersected with a plane 
using the approach of first clipping all the faces, and then using the 
face-edge connectivity information, capping the polyhedron with a final face. 

This should be quite fast in CGAL if a dynamic data structure (a linked list) 
is used for the half edge data structure of Polyhedron_3. 

Is there an algorithm that could deal with non-convex polyhedrons with 
non-planar faces? Nef_3 deals with non-convex polyhedra, but not those with 
non-planar faces. 

Would it be very inefficient if I have non-convex polyhedra to intersect, and 
I create a 3D triangulation of the polyhedra, obtain a bunch of tetrahedrons, 
and intersect the resulting sets of tetrahedrons?

[3]http://www.springerlink.com/content/v3403227110614q0/

> ----- Original Message -----
> From: Sebastien Loriot (GeometryFactory)
> Sent: 04/17/12 12:11 PM
> To: 
> 
> Subject: Re: [cgal-discuss] Intersection of two CONVEX 3D polyhedrons
> 
> A simple to implement method (but far from optimal) is to compute the
> intersection of triangles from A with triangles from B (using [1] for 
> example).
> 
> You then have a set of segments, triangles and points (or nothing in
> the case the polyhedra don't intersect).
> You simply need to compute the convex hull of all the endpoints of the
> segments and triangles, and the points using [2].
> 
> Sebastien.
> 
> [1] 
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Box_intersection_d/Chapter_main.html
> [2]http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Convex_hull_3/Chapter_main.html#Subsection_16.2.3
> 
> On 04/17/2012 11:51 AM, sgdimitris wrote:
> > I would like to ask which is the easiest and fastest way to calculate the
> > intersection of two *CONVEX* 3D polyhedrons?
> > I *don't* want only to see if the two polyhedrons are intersected but also
> > to calculate the polyhedron that is their intersection!
> > Best regards,
> > Dimitris
> >
> > --
> > View this message in context: 
> > http://cgal-discuss.949826.n4.nabble.com/Intersection-of-two-CONVEX-3D-polyhedrons-tp4564202p4564202.html
> > Sent from the cgal-discuss mailing list archive at Nabble.com.
> >
> 
> 
> -- 
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss