Subject: CGAL users discussion list
List archive
- From: Bart Janssens <>
- To:
- Cc: "Timothy M. Shead" <>
- Subject: Boolean operations and conversion from non-exact math
- Date: Sat, 25 Aug 2007 00:14:45 +0200
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:from:to:subject:date:user-agent:cc:mime-version:content-type:message-id:sender; b=m4Gxod5y0mRhqT441X/WwnH2nemtSf1nFFXV6+G6kgpXadvBXi0Fb00BRSVXSkkrI5OgqUZXf9ze8gmplRmtHDZBpbSUg8IgsJ+ON0sttCvwABhU5SUJz6uZ4hn4ulVUs5u5c10pd4Z8QSjQmKerAYyQiK7SVOHK1uD9CsM+8d0=
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:
CGAL error: assertion violation!
Expr: c.has_on(p1)&&c.has_on(p2)
File: /usr/include/CGAL/Nef_S2/Sphere_segment.h
Line: 57
I am using an Extended_homogeneous<CGAL::Gmpz> kernel, but the rotation is
applied in K-3D, before the conversion to an exact number type. Is it
possible the error is triggered by rounding errors that happen during the
transformation, which cause i.e. faces to be no longer coplanar?
Any help would be greatly appreciated, as I am immensely stuck on this one :)
For those willing to dig that deep, I have attached the code of the k3d::mesh
to CGAL::Nef_polyhedron_3 converter. It follows the canvas of the built-in
polyhedron_to_nef_polyhedron converter, which I am not using because I need
support for open polygons.
regards,
Bart
Attachment:
cubes.jpg
Description: JPEG image
#ifndef K3D_TO_NEF_H_ #define K3D_TO_NEF_H_ // K-3D // Copyright (c) 1995-2007, Timothy M. Shead // // Contact: // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public // License as published by the Free Software Foundation; either // version 2 of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // // You should have received a copy of the GNU General Public // License along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA // // As a special exception, you have permission to link this program // with the CGAL (http://www.cgal.org) library and distribute executables, as long as you // follow the requirements of the GNU GPL in regard to all of the // software in the executable aside from CGAL. /** \file \brief Converts a K-3D mesh to a Nef polyhedron. Based on polyhedron_3_to_nef3 from CGAL \author Bart Janssens () */ #include "conversion.h" #include <CGAL/Nef_3/SNC_structure.h> namespace libk3dbooleans { typedef CGAL::Plane_3<Kernel> Plane; typedef CGAL::Vector_3<Kernel> Vector; typedef Nef_polyhedron::SNC_structure SNC_structure; /// Create a Point_3 from the given k3d::point3 Point_3 to_cgal_point3(const k3d::point3& Point) { NT common_denominator = 1; Rational x = CGAL::to_rational<Rational>(Point[0]); common_denominator *= x.denominator(); Rational y = CGAL::to_rational<Rational>(Point[1]); common_denominator *= y.denominator(); Rational z = CGAL::to_rational<Rational>(Point[2]); common_denominator *= z.denominator(); return Point_3(x.numerator()*common_denominator/x.denominator(), y.numerator()*common_denominator/y.denominator(), z.numerator()*common_denominator/z.denominator(), common_denominator); } /// Returns the plane containing the face given to operator(). struct face_plane { face_plane(const k3d::mesh& Mesh) : m_mesh(Mesh) {} Plane operator()(size_t face) { k3d::normal3 normal = k3d::normal(*m_mesh.polyhedra->edge_points, *m_mesh.polyhedra->clockwise_edges, *m_mesh.points, m_mesh.polyhedra->loop_first_edges->at(face)); if (normal == k3d::normal3(0.0,0.0,0.0)) k3d::log() << error << "k3d_to_nef.h: m_mesh to convert contains a face with a 0 normal vector" << std::endl; Vector orthogonal_vector(normal[0],normal[1],normal[2]); k3d::point3 plane_point = m_mesh.points->at(m_mesh.polyhedra->edge_points->at(m_mesh.polyhedra->loop_first_edges->at(face))); return(Plane(to_cgal_point3(plane_point), orthogonal_vector)); } const k3d::mesh& m_mesh; }; void k3d_to_nef(const k3d::mesh& Mesh, const k3d::matrix4& Matrix, SNC_structure& S) { typedef SNC_structure::SNC_decorator SNC_decorator; typedef SNC_structure::SM_decorator SM_decorator; typedef SNC_structure::Vertex_handle Vertex_handle; typedef SNC_structure::SVertex_handle SVertex_handle; typedef SNC_structure::SHalfedge_handle SHalfedge_handle; typedef SNC_structure::SFace_handle SFace_handle; typedef SNC_structure::Sphere_point Sphere_point; typedef SNC_structure::Sphere_segment Sphere_segment; typedef SNC_structure::Sphere_circle Sphere_circle; typedef Polyhedron::Halfedge_around_vertex_const_circulator Halfedge_around_vertex_const_circulator; if(!k3d::validate_polyhedra(Mesh)) return; const k3d::mesh::indices_t& face_first_loops = *Mesh.polyhedra->face_first_loops; const k3d::mesh::counts_t& face_loop_counts = *Mesh.polyhedra->face_loop_counts; const k3d::mesh::selection_t& face_selection = *Mesh.polyhedra->face_selection; const k3d::mesh::indices_t& loop_first_edges = *Mesh.polyhedra->loop_first_edges; const k3d::mesh::indices_t& edge_points = *Mesh.polyhedra->edge_points; const k3d::mesh::indices_t& clockwise_edges = *Mesh.polyhedra->clockwise_edges; k3d::mesh::points_t points = *Mesh.points; // Make sure transformations are accounted for for (size_t point = 0; point != points.size(); ++point) points[point] = Matrix*points[point]; std::vector<Plane> planes(face_first_loops.size()); std::transform(face_first_loops.begin(), face_first_loops.end(), planes.begin(), face_plane(Mesh)); for (size_t i = 0; i != planes.size(); ++i) { Vector n = planes[i].orthogonal_vector(); k3d::log() << debug << "Normal for face " << i << ": " << n.x() << ", " << n.y() << ", " << n.z() << std::endl; } // Calculate companions std::vector<size_t> companions(edge_points.size()); std::map<std::pair<size_t, size_t>, size_t > edge_end_points; // maps edge start and endpoint to edge number std::vector<size_t> first_in_edges(points.size()); // Store an incoming edge for each point size_t edge_count = edge_points.size(); for (size_t edge = 0; edge != edge_count; ++edge) edge_end_points[std::make_pair(edge_points[edge], edge_points[clockwise_edges[edge]])] = edge; for (size_t edge = 0; edge != edge_count; ++edge) { size_t start_point = edge_points[edge]; size_t end_point = edge_points[clockwise_edges[edge]]; first_in_edges[end_point] = edge; size_t companion = edge; std::map<std::pair<size_t, size_t>, size_t >::iterator it = edge_end_points.find(std::make_pair(end_point, start_point)); if (it != edge_end_points.end()) { companion = it->second; } else { // volume is not closed, user should be notified. assert_not_reached(); } companions[edge] = companion; } // Provide an edge-to-face link std::vector<size_t> face_for_edge(edge_points.size()); for (size_t face = 0; face != face_first_loops.size(); ++face) { for (size_t loop = 0; loop != face_loop_counts[face]; ++loop) { size_t first_edge = loop_first_edges[face_first_loops[face] + loop]; for(size_t edge = first_edge; ; ) { face_for_edge[edge] = face; edge = clockwise_edges[edge]; if(edge == first_edge) break; } } } for (size_t point = 0; point != points.size(); ++point) { Vertex_handle nv = S.new_vertex(); Point_3 pvpoint = to_cgal_point3(points[point]); nv->point() = pvpoint; nv->mark() = true; SM_decorator SM(&*nv); size_t prev_edge = first_in_edges[point]; size_t edge = prev_edge; size_t first_edge = prev_edge; Point_3 pe_target_0 = to_cgal_point3(points[edge_points[first_edge]]); Point_3 sp_point_0(CGAL::ORIGIN+(pe_target_0-pvpoint)); Sphere_point sp_0(sp_point_0); SVertex_handle sv_0 = SM.new_svertex(sp_0); sv_0->mark() = true; edge = companions[clockwise_edges[edge]]; SVertex_handle sv_prev = sv_0; do { Point_3 pe_target = to_cgal_point3(points[edge_points[edge]]); Point_3 sp_point = CGAL::ORIGIN+(pe_target-pvpoint); Sphere_point sp(sp_point); SVertex_handle sv = SM.new_svertex(sp); sv->mark() = true; Plane ss_plane(CGAL::ORIGIN, planes[face_for_edge[prev_edge]].opposite().orthogonal_vector()); Sphere_circle ss_circle(ss_plane); SHalfedge_handle e = SM.new_shalfedge_pair(sv_prev, sv); e->circle() = ss_circle; e->twin()->circle() = ss_circle.opposite(); e->mark() = e->twin()->mark() = true; sv_prev = sv; prev_edge = edge; edge = companions[clockwise_edges[edge]]; } while(edge != first_edge); Plane ss_plane(CGAL::ORIGIN, planes[face_for_edge[prev_edge]].opposite().orthogonal_vector()); Sphere_circle ss_circle(ss_plane); SHalfedge_handle e = SM.new_shalfedge_pair(sv_prev, sv_0); e->circle() = ss_circle; e->twin()->circle() = ss_circle.opposite(); e->mark() = e->twin()->mark() = true; // create faces SFace_handle fint = SM.new_sface(); SFace_handle fext = SM.new_sface(); SM.link_as_face_cycle(e, fint); SM.link_as_face_cycle(e->twin(), fext); // mark faces properly... fint->mark() = true; fext->mark() = false; SM.check_integrity_and_topological_planarity(); } } } // end namespace #endif /*K3D_TO_NEF_H_*/
- Boolean operations and conversion from non-exact math, Bart Janssens, 08/25/2007
- Re: Boolean operations and conversion from non-exact math, Bart Janssens, 08/26/2007
- Re: [cgal-discuss] Re: Boolean operations and conversion from non-exact math, Peter Hachenberger, 08/27/2007
- Re: [cgal-discuss] Re: Boolean operations and conversion from non-exact math, Bart Janssens, 08/27/2007
- Re: [cgal-discuss] Re: Boolean operations and conversion from non-exact math, Peter Hachenberger, 08/27/2007
- Re: Boolean operations and conversion from non-exact math, Bart Janssens, 08/26/2007
Archive powered by MHonArc 2.6.16.