Wie kann ich den normalen Vektor (oder den Griff) des Dreiecks finden, das ein Strahl schneidet?

Question

Ich habe einen Strahl und eine Anzahl von 3D-Punkten, die ich trianguliere und in einen AABBtree füttere, was mir erlaubt, den Schnittpunkt des Strahls mit dem Gitter zu finden. Jetzt möchte ich auch den normalen Vektor des Dreiecks kennen, das der Strahl schneidet.

Ich projiziere die Punkte in die x-y-Ebene und verwende Delaunay-Vernetzung. Ich führe dann die 3D-Punkte in die AABBtree-Struktur ein. Idealerweise möchte ich diesen Teil nicht ändern.

Das Finden der Schnittmenge mit first_intersection() ist einfach.
Wie finde ich die Normale des geschnittenen Dreiecks?

edit: Das Problem ist, dass boost::get<KernelSCD::Point_3>(&(intersection->first)) nur gibt mir den tatsächlichen Schnittpunkt. Um den normalen Vektor zum durchschnittenen Dreieck zu finden, brauche ich den Griff des durchschnittenen Dreiecks. Wie bekomme ich das?

Dies ist mein Code:

// CGAL includes for AABB tree for intersection detection 
#include <CGAL/AABB_tree.h> 
#include <CGAL/AABB_traits.h> 
#include <CGAL/AABB_triangle_primitive.h> 
#include <CGAL/Simple_cartesian.h> 

// CGAL includes for Delaunay triangulation 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> 
#include <CGAL/Delaunay_triangulation_2.h> 
#include <CGAL/Triangulation_vertex_base_with_info_2.h> 
#include <CGAL/Polygon_mesh_processing/compute_normal.h> 

#include <CGAL/Simple_cartesian.h> 
#include <CGAL/AABB_tree.h> 
#include <CGAL/AABB_traits.h> 
#include <CGAL/Surface_mesh.h> 
#include <CGAL/AABB_face_graph_triangle_primitive.h> 
#include <CGAL/Polygon_mesh_processing/compute_normal.h> 
#include <CGAL/Polygon_mesh_processing/orientation.h> 

#include <iostream> 
#include <string> 
#include <vector> 
#include <fstream> 


int main (int argc, char *argv[]) 
{ 
    typedef CGAL::Simple_cartesian<double> KernelSCD; 
    typedef KernelSCD::Triangle_3 Triangle_3; 
    typedef std::list<Triangle_3>::iterator IteratorTriangle; 
    typedef CGAL::AABB_triangle_primitive<KernelSCD, IteratorTriangle> Primitive; 
    typedef CGAL::AABB_traits<KernelSCD, Primitive> AABB_triangle_traits; 
    typedef CGAL::AABB_tree<AABB_triangle_traits> Tree; 
    typedef CGAL::Simple_cartesian<double> K; 
    typedef CGAL::Triangulation_vertex_base_with_info_2<unsigned, K> Vb; 
    typedef CGAL::Triangulation_data_structure_2<Vb>     Tds; 
    typedef CGAL::Delaunay_triangulation_2<K, Tds>      Delaunay; 
    typedef Delaunay::Point            PointD; 
    typedef Delaunay::Vertex_handle          Vertex_handle; 
    typedef KernelSCD::Point_3 Point_3; 
    typedef KernelSCD::Vector_3 Vector_3; 
    typedef KernelSCD::Ray_3 Ray_3; 
    typedef boost::optional<Tree::Intersection_and_primitive_id<Ray_3>::Type> Ray_intersection; 
    typedef Tree::Primitive_id AABB_primitive_id; 


    Delaunay dt; 
    std::vector< std::pair<PointD, unsigned> > points_2d; 
    std::vector<Point_3> points_3d; 

    Tree tree_3d_map_; 
    std::list<Triangle_3> triangles_; 

    std::vector<double> verts = { 0, 0, 100, 
            0, 1, 101, 
            1, 0, 102, 
            1, 1, 103, 
           10, 0, 104, 
            0, 10, 105, 
           10, 10, 106}; 

    // Filling Delaunay triangulation 
    for (int i = 0; i+2 < verts.size(); i += 3) { 
     points_2d.push_back(std::make_pair(PointD(verts.at(i), verts.at(i + 1)), i/3)); 
     points_3d.push_back(Point_3(verts.at(i), verts.at(i + 1), verts.at(i + 2))); 
    } 
    dt.insert(points_2d.begin(), points_2d.end()); 

    // Filling AABB tree 
    int v0, v1, v2; 
    for (Delaunay::Finite_faces_iterator it = dt.finite_faces_begin(); it != dt.finite_faces_end(); it++){ 
     v0 = it->vertex(0)->info(); 
     v1 = it->vertex(1)->info(); 
     v2 = it->vertex(2)->info(); 
     triangles_.push_back(Triangle_3(points_3d.at(v0), points_3d.at(v1), points_3d.at(v2))); 
    } 
    tree_3d_map_.insert(triangles_.begin(), triangles_.end()); 

    Point_3 p1(.4, .5, 0.1); 
    Vector_3 v(0, 0, 1); 
    Ray_3 ray(p1, v); 

    // Find point where the ray intersects the mesh for the first time 
    Ray_intersection intersection = tree_3d_map_.first_intersection(ray); 

    if (intersection){ 
     if (boost::get<KernelSCD::Point_3>(&(intersection->first))){ 
      const KernelSCD::Point_3* p = boost::get<KernelSCD::Point_3>(&(intersection->first)); 
      std::cout << "First intersection: " << p->x() << ", " << p->y() << ", " << p->z() << std::endl; 

      AABB_primitive_id primitive_id = intersection->second; 
      //                    Fails: 
      //                   | | | | 
      //                   v v v v 
      //KernelSCD::Vector_3 v = CGAL::Polygon_mesh_processing::compute_face_normal(primitive_id,points_3d); 
      //std::cout << "v: " << v.x() << ", " << v.y() << ", " << v.z() << std::endl; 
     } 
    }  


    /* If I use a Surface_mesh, it works: 
    typedef CGAL::Surface_mesh<Point_3> Mesh; 
    typedef CGAL::AABB_face_graph_triangle_primitive<Mesh> PrimitiveM; 
    typedef CGAL::AABB_traits<KernelSCD, PrimitiveM> Traits; 
    typedef CGAL::AABB_tree<Traits> TreeM; 
    typedef boost::optional<TreeM::Intersection_and_primitive_id<Ray_3>::Type> Ray_intersectionM; 
    typedef TreeM::Primitive_id AABB_primitive_idM; 

    std::ifstream input("tetrahedron.off"); 
    Mesh mesh; 
    input >> mesh; 
    TreeM tree; 
    tree.insert(faces(mesh).first, faces(mesh).second, mesh); 
    Ray_intersectionM intersection2 = tree.first_intersection(ray); 
    if (intersection2){ 
     if (boost::get<Point_3>(&(intersection2->first))){ 
      const Point_3* p = boost::get<Point_3>(&(intersection2->first)); 
      std::cout << "First intersection: " << *p << std::endl; 

      AABB_primitive_idM primitive_id = intersection2->second; 

      // Works: 
      Vector_3 v = CGAL::Polygon_mesh_processing::compute_face_normal(primitive_id,mesh); 
      std::cout << "v: " << v.x() << ", " << v.y() << ", " << v.z() << std::endl; 
     } 
    }*/ 

    std::cout << "done" << std::endl; 
    std::cin.get(); 
    return 0; 
} 

Answer 1

Vielleicht etwas verpasst ich habe, ist aber nicht, dass die Anwendung von einfachen Vektor-Mathematik? Wenn Sie die 3 Punkte Ihres Dreiecks kennen, können Sie einen Vektor von Punkt [0] zu Punkt [1] und von Punkt [0] zu Punkt [2] erstellen und das Kreuzprodukt erstellen. Das Ergebnis ist ein Vektor, der senkrecht zu Ihren beiden Vektoren ist (normal Ihres Dreiecks).