igl::copyleft::cgal::points_inside_component_helper Namespace Reference

Typedefs
typedef CGAL::Exact_predicates_exact_constructions_kernel	Kernel
typedef Kernel::Ray_3	Ray_3
typedef Kernel::Point_3	Point_3
typedef Kernel::Vector_3	Vector_3
typedef Kernel::Triangle_3	Triangle
typedef Kernel::Plane_3	Plane_3
typedef std::vector< Triangle >::iterator	Iterator
typedef CGAL::AABB_triangle_primitive< Kernel, Iterator >	Primitive
typedef CGAL::AABB_traits< Kernel, Primitive >	AABB_triangle_traits
typedef CGAL::AABB_tree< AABB_triangle_traits >	Tree

Functions
template<typename DerivedF , typename DerivedI >
void	extract_adj_faces (const Eigen::PlainObjectBase< DerivedF > &F, const Eigen::PlainObjectBase< DerivedI > &I, const size_t s, const size_t d, std::vector< int > &adj_faces)
template<typename DerivedF , typename DerivedI >
void	extract_adj_vertices (const Eigen::PlainObjectBase< DerivedF > &F, const Eigen::PlainObjectBase< DerivedI > &I, const size_t v, std::vector< int > &adj_vertices)
template<typename DerivedV , typename DerivedF , typename DerivedI >
bool	determine_point_edge_orientation (const Eigen::PlainObjectBase< DerivedV > &V, const Eigen::PlainObjectBase< DerivedF > &F, const Eigen::PlainObjectBase< DerivedI > &I, const Point_3 &query, size_t s, size_t d)
template<typename DerivedV , typename DerivedF , typename DerivedI >
bool	determine_point_vertex_orientation (const Eigen::PlainObjectBase< DerivedV > &V, const Eigen::PlainObjectBase< DerivedF > &F, const Eigen::PlainObjectBase< DerivedI > &I, const Point_3 &query, size_t s)
template<typename DerivedV , typename DerivedF , typename DerivedI >
bool	determine_point_face_orientation (const Eigen::PlainObjectBase< DerivedV > &V, const Eigen::PlainObjectBase< DerivedF > &F, const Eigen::PlainObjectBase< DerivedI > &I, const Point_3 &query, size_t fid)

Typedef Documentation

AABB_triangle_traits

typedef CGAL::AABB_traits<Kernel, Primitive> igl::copyleft::cgal::points_inside_component_helper::AABB_triangle_traits

Iterator

typedef std::vector<Triangle>::iterator igl::copyleft::cgal::points_inside_component_helper::Iterator

Kernel

typedef CGAL::Exact_predicates_exact_constructions_kernel igl::copyleft::cgal::points_inside_component_helper::Kernel

Plane_3

typedef Kernel::Plane_3 igl::copyleft::cgal::points_inside_component_helper::Plane_3

Point_3

typedef Kernel::Point_3 igl::copyleft::cgal::points_inside_component_helper::Point_3

Primitive

typedef CGAL::AABB_triangle_primitive<Kernel, Iterator> igl::copyleft::cgal::points_inside_component_helper::Primitive

Ray_3

typedef Kernel::Ray_3 igl::copyleft::cgal::points_inside_component_helper::Ray_3

Tree

typedef CGAL::AABB_tree<AABB_triangle_traits> igl::copyleft::cgal::points_inside_component_helper::Tree

Triangle

typedef Kernel::Triangle_3 igl::copyleft::cgal::points_inside_component_helper::Triangle

Vector_3

typedef Kernel::Vector_3 igl::copyleft::cgal::points_inside_component_helper::Vector_3

Function Documentation

determine_point_edge_orientation()

template<typename DerivedV , typename DerivedF , typename DerivedI >

bool igl::copyleft::cgal::points_inside_component_helper::determine_point_edge_orientation	(	const Eigen::PlainObjectBase< DerivedV > &	V,
		const Eigen::PlainObjectBase< DerivedF > &	F,
		const Eigen::PlainObjectBase< DerivedI > &	I,
		const Point_3 &	query,
		size_t	s,
		size_t	d
	)

                                                              {
                // Algorithm:
                //
                // Order the adj faces around the edge (s,d) clockwise using
                // query point as pivot.  (i.e. The first face of the ordering
                // is directly after the pivot point, and the last face is
                // directly before the pivot.)
                //
                // The point is outside if the first and last faces of the
                // ordering forms a convex angle.  This check can be done
                // without any construction by looking at the orientation of the
                // faces.  The angle is convex iff the first face contains (s,d)
                // as an edge and the last face contains (d,s) as an edge.
                //
                // The point is inside if the first and last faces of the
                // ordering forms a concave angle.  That is the first face
                // contains (d,s) as an edge and the last face contains (s,d) as
                // an edge.
                //
                // In the special case of duplicated faces. I.e. multiple faces
                // sharing the same 3 corners, but not necessarily the same
                // orientation.  The ordering will always rank faces containing
                // edge (s,d) before faces containing edge (d,s).
                //
                // Therefore, if there are any duplicates of the first faces,
                // the ordering will always choose the one with edge (s,d) if
                // possible.  The same for the last face.
                //
                // In the very degenerated case where the first and last face
                // are duplicates, but with different orientations, it is
                // equally valid to think the angle formed by them is either 0
                // or 360 degrees.  By default, 0 degree is used, and thus the
                // query point is outside.
 
                std::vector<int> adj_faces;
                extract_adj_faces(F, I, s, d, adj_faces);
                const size_t num_adj_faces = adj_faces.size();
                assert(num_adj_faces > 0);
 
                DerivedV pivot_point(1, 3);
                igl::copyleft::cgal::assign_scalar(query.x(), pivot_point(0, 0));
                igl::copyleft::cgal::assign_scalar(query.y(), pivot_point(0, 1));
                igl::copyleft::cgal::assign_scalar(query.z(), pivot_point(0, 2));
                Eigen::VectorXi order;
                order_facets_around_edge(V, F, s, d,
                        adj_faces, pivot_point, order);
                assert((size_t)order.size() == num_adj_faces);
                if (adj_faces[order[0]] > 0 &&
                    adj_faces[order[num_adj_faces-1] < 0]) {
                    return true;
                } else if (adj_faces[order[0]] < 0 &&
                    adj_faces[order[num_adj_faces-1] > 0]) {
                    return false;
                } else {
                    throw "The input mesh does not represent a valid volume";
                }
                throw "The input mesh does not represent a valid volume";
                return false;
            }

References igl::copyleft::cgal::assign_scalar(), extract_adj_faces(), and igl::copyleft::cgal::order_facets_around_edge().

Referenced by determine_point_vertex_orientation().

Here is the call graph for this function:

Here is the caller graph for this function:

determine_point_face_orientation()

template<typename DerivedV , typename DerivedF , typename DerivedI >

bool igl::copyleft::cgal::points_inside_component_helper::determine_point_face_orientation	(	const Eigen::PlainObjectBase< DerivedV > &	V,
		const Eigen::PlainObjectBase< DerivedF > &	F,
		const Eigen::PlainObjectBase< DerivedI > &	I,
		const Point_3 &	query,
		size_t	fid
	)

                                                      {
                // Algorithm: A point is on the inside of a face if the
                // tetrahedron formed by them is negatively oriented.
 
                Eigen::Vector3i f = F.row(I(fid, 0));
                const Point_3 v0(V(f[0], 0), V(f[0], 1), V(f[0], 2));
                const Point_3 v1(V(f[1], 0), V(f[1], 1), V(f[1], 2));
                const Point_3 v2(V(f[2], 0), V(f[2], 1), V(f[2], 2));
                auto result = CGAL::orientation(v0, v1, v2, query);
                if (result == CGAL::COPLANAR) {
                    throw "Cannot determine inside/outside because query point lies exactly on the input surface.";
                }
                return result == CGAL::NEGATIVE;
            }

determine_point_vertex_orientation()

template<typename DerivedV , typename DerivedF , typename DerivedI >

bool igl::copyleft::cgal::points_inside_component_helper::determine_point_vertex_orientation	(	const Eigen::PlainObjectBase< DerivedV > &	V,
		const Eigen::PlainObjectBase< DerivedF > &	F,
		const Eigen::PlainObjectBase< DerivedI > &	I,
		const Point_3 &	query,
		size_t	s
	)

                                                    {
                std::vector<int> adj_vertices;
                extract_adj_vertices(F, I, s, adj_vertices);
                const size_t num_adj_vertices = adj_vertices.size();
 
                std::vector<Point_3> adj_points;
                for (size_t i=0; i<num_adj_vertices; i++) {
                    const size_t vi = adj_vertices[i];
                    adj_points.emplace_back(V(vi,0), V(vi,1), V(vi,2));
                }
 
                // A plane is on the exterior if all adj_points lies on or to
                // one side of the plane.
                auto is_on_exterior = [&](const Plane_3& separator) -> bool{
                    size_t positive=0;
                    size_t negative=0;
                    size_t coplanar=0;
                    for (const auto& point : adj_points) {
                        switch(separator.oriented_side(point)) {
                            case CGAL::ON_POSITIVE_SIDE:
                                positive++;
                                break;
                            case CGAL::ON_NEGATIVE_SIDE:
                                negative++;
                                break;
                            case CGAL::ON_ORIENTED_BOUNDARY:
                                coplanar++;
                                break;
                            default:
                                throw "Unknown plane-point orientation";
                        }
                    }
                    auto query_orientation = separator.oriented_side(query);
                    bool r =
                        (positive == 0 && query_orientation == CGAL::POSITIVE)
                        ||
                        (negative == 0 && query_orientation == CGAL::NEGATIVE);
                    return r;
                };
 
                size_t d = std::numeric_limits<size_t>::max();
                Point_3 p(V(s,0), V(s,1), V(s,2));
                for (size_t i=0; i<num_adj_vertices; i++) {
                    const size_t vi = adj_vertices[i];
                    for (size_t j=i+1; j<num_adj_vertices; j++) {
                        Plane_3 separator(p, adj_points[i], adj_points[j]);
                        if (separator.is_degenerate()) {
                            throw "Input mesh contains degenerated faces";
                        }
                        if (is_on_exterior(separator)) {
                            d = vi;
                            assert(!CGAL::collinear(p, adj_points[i], query));
                            break;
                        }
                    }
                    if (d < (size_t)V.rows()) break;
                }
                if (d > (size_t)V.rows()) {
                    // All adj faces are coplanar, use the first edge.
                    d = adj_vertices[0];
                }
                return determine_point_edge_orientation(V, F, I, query, s, d);
            }

References determine_point_edge_orientation(), extract_adj_vertices(), and Eigen::PlainObjectBase< Derived >::rows().

Here is the call graph for this function:

extract_adj_faces()

template<typename DerivedF , typename DerivedI >

void igl::copyleft::cgal::points_inside_component_helper::extract_adj_faces	(	const Eigen::PlainObjectBase< DerivedF > &	F,
		const Eigen::PlainObjectBase< DerivedI > &	I,
		const size_t	s,
		const size_t	d,
		std::vector< int > &	adj_faces
	)

                                               {
                const size_t num_faces = I.rows();
                for (size_t i=0; i<num_faces; i++) {
                    Eigen::Vector3i f = F.row(I(i, 0));
                    if (((size_t)f[0] == s && (size_t)f[1] == d) ||
                        ((size_t)f[1] == s && (size_t)f[2] == d) ||
                        ((size_t)f[2] == s && (size_t)f[0] == d)) {
                        adj_faces.push_back((I(i, 0)+1) * -1);
                        continue;
                    }
                    if (((size_t)f[0] == d && (size_t)f[1] == s) ||
                        ((size_t)f[1] == d && (size_t)f[2] == s) ||
                        ((size_t)f[2] == d && (size_t)f[0] == s)) {
                        adj_faces.push_back(I(i, 0)+1);
                        continue;
                    }
                }
            }

References Eigen::PlainObjectBase< Derived >::rows().

Referenced by determine_point_edge_orientation().

Here is the call graph for this function:

Here is the caller graph for this function:

extract_adj_vertices()

template<typename DerivedF , typename DerivedI >

void igl::copyleft::cgal::points_inside_component_helper::extract_adj_vertices	(	const Eigen::PlainObjectBase< DerivedF > &	F,
		const Eigen::PlainObjectBase< DerivedI > &	I,
		const size_t	v,
		std::vector< int > &	adj_vertices
	)

                                                                  {
                std::set<size_t> unique_adj_vertices;
                const size_t num_faces = I.rows();
                for (size_t i=0; i<num_faces; i++) {
                    Eigen::Vector3i f = F.row(I(i, 0));
                    if ((size_t)f[0] == v) {
                        unique_adj_vertices.insert(f[1]);
                        unique_adj_vertices.insert(f[2]);
                    } else if ((size_t)f[1] == v) {
                        unique_adj_vertices.insert(f[0]);
                        unique_adj_vertices.insert(f[2]);
                    } else if ((size_t)f[2] == v) {
                        unique_adj_vertices.insert(f[0]);
                        unique_adj_vertices.insert(f[1]);
                    }
                }
                adj_vertices.resize(unique_adj_vertices.size());
                std::copy(unique_adj_vertices.begin(),
                        unique_adj_vertices.end(),
                        adj_vertices.begin());
            }

References Eigen::PlainObjectBase< Derived >::rows().

Referenced by determine_point_vertex_orientation().

Here is the call graph for this function:

Here is the caller graph for this function: