Skip to Content.
Sympa Menu

cgal-discuss - Re: Boolean operations and conversion from non-exact math

Subject: CGAL users discussion list

List archive

Re: Boolean operations and conversion from non-exact math


Chronological Thread 
  • From: Bart Janssens <>
  • To:
  • Cc: "Timothy M. Shead" <>
  • Subject: Re: Boolean operations and conversion from non-exact math
  • Date: Sun, 26 Aug 2007 14:25:15 +0200
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:from:to:subject:date:user-agent:cc:references:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:message-id:sender; b=QpPGKnz6AT3SbsvAiiNCf6IGuedQtA83ZhEbI/2MHvqcJKMNBRAwupANd1hzJEP+FwAEkwcyfeL0lVTgl1eVje9Jold9gqXBFkOoO/TEW83/I2zX0iyqQTG4BDUTmzb+b/MrSyrE9BdsD6VfAnFzSYMo1ZZtcKyimBCzvn6j+Qg=

On Saturday 25 August 2007 00:14:45 Bart Janssens wrote:
> Hi all,
>
> I have made some more progress in using CGAL to do booleans in K-3D. I have
> written a converter from k3d::mesh to CGAL::Nef_polyhedron_3, and it
> appears to work on two cubes that have their edges parallel to the
> coordinate system. I can calculate the difference of two such cubes, as
> shown in the attached image. The cubes consist of 6 quadrilateral polygons,
> so there is no triangulation prior to passing them to CGAL.
>
> The problem arises when I complicate matters only slightly, and attempt to
> rotate one of the cubes. When I do that, I get the following error from
> create_volumes() called by build_external_structure() called on the rotated
> cube:

I've done some more checking, and after removing some glaring errors from the
normal calculation part in my code, I can now rotate the cubes around a
single axis, though more complicated rotations definitely result in
non-planar polygons to appear.

I think I basically have two options here:
1. Attempt to make the corners of the polygons coplanar, i.e. by calculating
intersections between planes surrounding the corner and then moving the point
to the intersection. I am not sure if this can work in general, though.

2. Triangulate all polyhedra before calling the boolean operations.

3. A combination of the above: attempt 1, if it is detected to be impossible,
use 2.

The reason I'm not going for triangulation right away is that the CGAL
booleans result in nice meshes that use a minimum of geometry to represent
the boolean mesh, which is much nicer to work with than a triangulated mesh.

Any recommendations welcome!

regards,

Bart



Archive powered by MHonArc 2.6.16.

Top of Page