intersection.h

/*****************************************************************************
 * VCLib                                                                     *
 * Visual Computing Library                                                  *
 *                                                                           *
 * Copyright(C) 2021-2026                                                    *
 * Visual Computing Lab                                                      *
 * ISTI - Italian National Research Council                                  *
 *                                                                           *
 * All rights reserved.                                                      *
 *                                                                           *
 * This program is free software; you can redistribute it and/or modify      *
 * it under the terms of the Mozilla Public License Version 2.0 as published *
 * by the Mozilla 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              *
 * Mozilla Public License Version 2.0                                        *
 * (https://www.mozilla.org/en-US/MPL/2.0/) for more details.                *
 ****************************************************************************/
 
#ifndef VCL_MESH_ELEM_ALGORITHMS_INTERSECTION_H
#define VCL_MESH_ELEM_ALGORITHMS_INTERSECTION_H
 
#include <vclib/mesh/elements.h>
 
#include <vclib/algorithms/core.h>
#include <vclib/space/core.h>
 
namespace vcl {
 
template<FaceConcept FaceType, PointConcept PointType>
bool intersect(const FaceType& f, const Box<PointType>& box)
{
    if constexpr (TriangleFaceConcept<FaceType>) {
        return intersect(
            TriangleWrapper(
                f.vertex(0)->position(),
                f.vertex(1)->position(),
                f.vertex(2)->position()),
            box);
    }
    else {
        bool b = false;
 
        std::vector<uint> tris = earCut(f);
        for (uint i = 0; i < tris.size() && !b; i += 3) {
            b |= intersect(
                TriangleWrapper(
                    f.vertex(tris[i])->position(),
                    f.vertex(tris[i + 1])->position(),
                    f.vertex(tris[i + 2])->position()),
                box);
        }
        return b;
    }
}
 
template<PointConcept PointType, FaceConcept FaceType>
bool intersect(const Box<PointType>& box, const FaceType& f)
{
    return intersect(f, box);
}
 
template<FaceConcept FaceType, PointConcept PointType, typename SScalar>
bool intersect(
    const FaceType&              f,
    const Sphere<SScalar>&       sphere,
    PointType&                   witness,
    std::pair<SScalar, SScalar>& res)
{
    if constexpr (TriangleFaceConcept<FaceType>) {
        return intersect(
            TriangleWrapper(
                f.vertex(0)->position(),
                f.vertex(1)->position(),
                f.vertex(2)->position()),
            sphere,
            witness,
            res);
    }
    else {
        if (f.vertexCount() == 3) {
            return intersect(
                TriangleWrapper(
                    f.vertex(0)->position(),
                    f.vertex(1)->position(),
                    f.vertex(2)->position()),
                sphere,
                witness,
                res);
        }
        else {
            res.first = std::numeric_limits<SScalar>::max();
            std::pair<SScalar, SScalar> r;
 
            bool      b = false;
            PointType w;
 
            std::vector<uint> tris = earCut(f);
            for (uint i = 0; i < tris.size() && !b; i += 3) {
                b |= intersect(
                    TriangleWrapper(
                        f.vertex(tris[i])->position(),
                        f.vertex(tris[i + 1])->position(),
                        f.vertex(tris[i + 2])->position()),
                    sphere,
                    w,
                    r);
 
                if (r.first < res.first) {
                    res     = r;
                    witness = w;
                }
            }
            return b;
        }
    }
}
 
template<FaceConcept FaceType, typename SScalar>
bool intersect(const FaceType& f, const Sphere<SScalar>& sphere)
{
    Point3<SScalar>             witness;
    std::pair<SScalar, SScalar> res;
    return intersect(f, sphere, witness, res);
}
 
template<typename SScalar, FaceConcept FaceType>
bool intersect(const Sphere<SScalar>& sphere, const FaceType& f)
{
    return intersect(f, sphere);
}
 
template<Ray3Concept RayType, FaceConcept FaceType>
std::optional<typename RayType::PointType> intersection(
    const RayType&                                                      ray,
    const FaceType&                                                     face,
    std::optional<std::reference_wrapper<typename RayType::ScalarType>> t = {})
    requires std::same_as<
        typename RayType::ScalarType,
        typename FaceType::VertexType::PositionType::ScalarType>
{
    using PointType  = typename RayType::PointType;
    using ScalarType = typename PointType::ScalarType;
 
    auto triangleIntersection = [](const FaceType& f,
                                   const RayType&  r,
                                   auto t) -> std::optional<PointType> {
        return intersection(
            r,
            TriangleWrapper(
                f.vertex(0)->position(),
                f.vertex(1)->position(),
                f.vertex(2)->position()),
            t);
    };
 
    if constexpr (TriangleFaceConcept<FaceType>) {
        return triangleIntersection(face, ray, t);
    }
    else {
        if (face.vertexCount() == 3) {
            return triangleIntersection(face, ray, t);
        }
        else {
            std::vector<uint> tris = earCut(face);
            for (uint i = 0; i < tris.size(); i += 3) {
                std::optional<PointType> res = intersection(
                    ray,
                    TriangleWrapper(
                        face.vertex(tris[i])->position(),
                        face.vertex(tris[i + 1])->position(),
                        face.vertex(tris[i + 2])->position()),
                    t);
                if (res.has_value())
                    return res;
            }
            return std::nullopt;
        }
    }
}
 
template<Ray3Concept RayType, FaceConcept FaceType>
bool intersect(const RayType& ray, const FaceType& face)
{
    return intersection(ray, face).has_value();
}
 
template<FaceConcept FaceType, Ray3Concept RayType>
bool intersect(const FaceType& face, const RayType& ray)
{
    return intersect(ray, face);
}
 
} // namespace vcl
 
#endif // VCL_MESH_ELEM_ALGORITHMS_INTERSECTION_H