CGAL users discussion list

[Bart Janssens <>]

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