OCCT

// Copyright (c) 2025 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#include <BRep_Builder.hxx>
#include <BRep_Tool.hxx>
#include <BRepBuilderAPI_MakeFace.hxx>
#include <BRepBuilderAPI_MakeVertex.hxx>
#include <BRepMesh_IncrementalMesh.hxx>
#include <GeomAPI_ProjectPointOnSurf.hxx>
#include <Geom_Surface.hxx>
#include <NCollection_DynamicArray.hxx>
#include <IMeshTools_Parameters.hxx>
#include <Poly_Triangulation.hxx>
#include <Precision.hxx>
#include <TopLoc_Location.hxx>
#include <TopoDS.hxx>
#include <TopoDS_Face.hxx>
#include <TopoDS_Vertex.hxx>
#include <gp_Pln.hxx>
#include <gp_Pnt.hxx>

#include <gtest/gtest.h>

#include <cmath>

namespace
{

//! Helper function to add an internal vertex to a face.
//! Projects the vertex onto the face surface and adds it with proper UV parameters.
//! @param theFace The face to add the vertex to (must be Free)
//! @param thePoint The 3D point to add as internal vertex
//! @return The created internal vertex, or null vertex if failed
TopoDS_Vertex addInternalVertexToFace(TopoDS_Face& theFace, const gp_Pnt& thePoint)
{
  const occ::handle<Geom_Surface>  aSurf = BRep_Tool::Surface(theFace);
  const GeomAPI_ProjectPointOnSurf aProjection(thePoint, aSurf);
  if (!aProjection.IsDone() || aProjection.NbPoints() == 0)
  {
    return TopoDS_Vertex();
  }

  double aU, aV;
  aProjection.Parameters(1, aU, aV);

  TopoDS_Vertex aVertex = BRepBuilderAPI_MakeVertex(aProjection.Point(1));
  aVertex.Orientation(TopAbs_INTERNAL);

  BRep_Builder aBuilder;
  aBuilder.UpdateVertex(aVertex, aU, aV, theFace, Precision::Confusion());
  aBuilder.Add(theFace, aVertex);

  return aVertex;
}

//! Checks triangulation nodes for valid coordinates (no extreme values).
//! @param theTri The triangulation to check
//! @param theLoc The location transformation
//! @return True if all nodes are valid, false if any invalid nodes detected
bool hasOnlyValidNodes(const occ::handle<Poly_Triangulation>& theTri, const TopLoc_Location& theLoc)
{
  constexpr double aMaxValidCoord = 1.0e10; // Reasonable max for valid geometry

  for (int i = 1; i <= theTri->NbNodes(); ++i)
  {
    const gp_Pnt aPoint = theTri->Node(i).Transformed(theLoc);
    if (std::abs(aPoint.X()) > aMaxValidCoord || std::abs(aPoint.Y()) > aMaxValidCoord
        || std::abs(aPoint.Z()) > aMaxValidCoord)
    {
      return false;
    }
  }
  return true;
}

//! Check if any triangle has degenerate indices (duplicate node indices).
//! @param theTri The triangulation to check
//! @return True if all triangles have unique node indices, false otherwise
bool hasOnlyValidTriangles(const occ::handle<Poly_Triangulation>& theTri)
{
  for (int i = 1; i <= theTri->NbTriangles(); ++i)
  {
    int aN1, aN2, aN3;
    theTri->Triangle(i).Get(aN1, aN2, aN3);
    if (aN1 == aN2 || aN2 == aN3 || aN1 == aN3)
    {
      return false;
    }
  }
  return true;
}

//! Find the closest triangulation node to a given 3D point.
//! @param theTri The triangulation to search
//! @param theLoc The location transformation
//! @param thePoint The target point
//! @return Pair of closest node index and distance to the point.
std::pair<int, double> findClosestNode(const occ::handle<Poly_Triangulation>& theTri,
                                       const TopLoc_Location&                 theLoc,
                                       const gp_Pnt&                          thePoint)
{
  int    aClosestIdx = 0;
  double aMinDistSq  = std::numeric_limits<double>::max();

  for (int i = 1; i <= theTri->NbNodes(); ++i)
  {
    const gp_Pnt aNode  = theTri->Node(i).Transformed(theLoc);
    const double aDist2 = thePoint.SquareDistance(aNode);
    if (aDist2 < aMinDistSq)
    {
      aMinDistSq  = aDist2;
      aClosestIdx = i;
    }
  }

  return {aClosestIdx, std::sqrt(aMinDistSq)};
}

} // namespace

// Test for bug #929: Internal vertices not bound in output triangulation from BRepMesh
// When a TopoDS_Face contains TopAbs_INTERNAL vertices, mesh generated by BRepMesh_IncrementalMesh
// should produce valid triangulation nodes for these vertices.

TEST(BRepMesh_BaseMeshAlgoTest, InternalVerticesAreBound)
{
  // Create a simple planar face
  const gp_Pln aPlane(gp_Pnt(0.0, 0.0, 0.0), gp::DZ());
  const double aUMin = 0.0, aUMax = 100.0;
  const double aVMin = 0.0, aVMax = 50.0;
  TopoDS_Face  aFace = BRepBuilderAPI_MakeFace(aPlane, aUMin, aUMax, aVMin, aVMax);

  // Add internal vertices on the face
  const gp_Pnt aInternalPts[3] = {gp_Pnt(40.0, 20.0, 0.0),
                                  gp_Pnt(60.0, 30.0, 0.0),
                                  gp_Pnt(77.0, 33.0, 0.0)};

  for (int i = 0; i < 3; ++i)
  {
    const TopoDS_Vertex aVertex = addInternalVertexToFace(aFace, aInternalPts[i]);
    ASSERT_FALSE(aVertex.IsNull()) << "Failed to add internal vertex " << i;
  }

  // Mesh with internal vertices mode enabled
  IMeshTools_Parameters aParams;
  aParams.Deflection           = 1.0;
  aParams.Angle                = 0.5;
  aParams.InternalVerticesMode = true;

  const BRepMesh_IncrementalMesh aMesher(aFace, aParams);
  ASSERT_TRUE(aMesher.IsDone()) << "Meshing should succeed";

  // Get triangulation
  TopLoc_Location                       aLoc;
  const occ::handle<Poly_Triangulation> aTri = BRep_Tool::Triangulation(aFace, aLoc);
  ASSERT_FALSE(aTri.IsNull()) << "Triangulation should be created";

  // Verify all nodes are valid (not uninitialized)
  EXPECT_TRUE(hasOnlyValidNodes(aTri, aLoc))
    << "All triangulation nodes should have valid coordinates";

  // Verify triangles are valid (no degenerate triangles)
  EXPECT_TRUE(hasOnlyValidTriangles(aTri)) << "All triangles should have unique node indices";

  // Verify internal vertices are present in the triangulation with correct coordinates
  const double aTolerance = 1.0e-6;
  for (int i = 0; i < 3; ++i)
  {
    auto [aClosestIdx, aMinDist] = findClosestNode(aTri, aLoc, aInternalPts[i]);
    EXPECT_GT(aClosestIdx, 0) << "Should find a closest node for internal vertex " << i;
    EXPECT_LT(aMinDist, aTolerance)
      << "Internal vertex " << i << " should be present in triangulation (dist=" << aMinDist << ")";
  }
}

TEST(BRepMesh_BaseMeshAlgoTest, MultipleInternalVertices)
{
  // Test with more internal vertices to ensure the fix handles multiple vertices correctly
  const gp_Pln aPlane(gp_Pnt(0.0, 0.0, 0.0), gp::DZ());
  const double aSize = 100.0;
  TopoDS_Face  aFace = BRepBuilderAPI_MakeFace(aPlane, 0.0, aSize, 0.0, aSize);

  // Add a grid of internal vertices (5x5 = 25 vertices)
  const int                        aGridSize = 5;
  NCollection_DynamicArray<gp_Pnt> anInternalPts;
  for (int i = 1; i < aGridSize; ++i)
  {
    for (int j = 1; j < aGridSize; ++j)
    {
      double       aX = (aSize * i) / aGridSize;
      double       aY = (aSize * j) / aGridSize;
      const gp_Pnt aPt(aX, aY, 0.0);
      anInternalPts.Append(aPt);
      const TopoDS_Vertex aVertex = addInternalVertexToFace(aFace, aPt);
      ASSERT_FALSE(aVertex.IsNull())
        << "Failed to add internal vertex at (" << aX << ", " << aY << ")";
    }
  }

  IMeshTools_Parameters aParams;
  aParams.Deflection           = 1.0;
  aParams.Angle                = 0.5;
  aParams.InternalVerticesMode = true;

  const BRepMesh_IncrementalMesh aMesher(aFace, aParams);
  ASSERT_TRUE(aMesher.IsDone()) << "Meshing should succeed";

  TopLoc_Location                       aLoc;
  const occ::handle<Poly_Triangulation> aTri = BRep_Tool::Triangulation(aFace, aLoc);
  ASSERT_FALSE(aTri.IsNull()) << "Triangulation should be created";

  EXPECT_TRUE(hasOnlyValidNodes(aTri, aLoc))
    << "All triangulation nodes should have valid coordinates";
  EXPECT_TRUE(hasOnlyValidTriangles(aTri)) << "All triangles should have unique node indices";

  // Verify all internal vertices are present
  constexpr double aTolerance  = 1.0e-6;
  int              aFoundCount = 0;
  for (const auto& aPoint : anInternalPts)
  {
    auto [aClosestIdx, aMinDist] = findClosestNode(aTri, aLoc, aPoint);
    if (aClosestIdx > 0 && aMinDist < aTolerance)
    {
      ++aFoundCount;
    }
  }
  EXPECT_EQ(aFoundCount, anInternalPts.Size())
    << "All " << anInternalPts.Size() << " internal vertices should be present in triangulation";
}

TEST(BRepMesh_BaseMeshAlgoTest, InternalVerticesModeDisabled)
{
  // Verify that when InternalVerticesMode is disabled, internal vertices are not included
  const gp_Pln aPlane(gp_Pnt(0.0, 0.0, 0.0), gp::DZ());
  TopoDS_Face  aFace = BRepBuilderAPI_MakeFace(aPlane, 0.0, 100.0, 0.0, 50.0);

  const gp_Pnt        aInternalPt(50.0, 25.0, 0.0);
  const TopoDS_Vertex aVertex = addInternalVertexToFace(aFace, aInternalPt);
  ASSERT_FALSE(aVertex.IsNull()) << "Failed to add internal vertex";

  // Mesh with internal vertices mode DISABLED
  IMeshTools_Parameters aParams;
  aParams.Deflection           = 1.0;
  aParams.Angle                = 0.5;
  aParams.InternalVerticesMode = false;

  const BRepMesh_IncrementalMesh aMesher(aFace, aParams);
  ASSERT_TRUE(aMesher.IsDone()) << "Meshing should succeed";

  TopLoc_Location                       aLoc;
  const occ::handle<Poly_Triangulation> aTri = BRep_Tool::Triangulation(aFace, aLoc);
  ASSERT_FALSE(aTri.IsNull()) << "Triangulation should be created";

  // Triangulation should still be valid
  EXPECT_TRUE(hasOnlyValidNodes(aTri, aLoc))
    << "All triangulation nodes should have valid coordinates";
  EXPECT_TRUE(hasOnlyValidTriangles(aTri)) << "All triangles should have unique node indices";

  // Internal vertex should NOT be in the triangulation (or at least not as a fixed point)
  // The mesh should have fewer nodes when internal vertices are disabled
  auto [aClosestIdx, aMinDist] = findClosestNode(aTri, aLoc, aInternalPt);

  // The internal vertex might still be close to some mesh node, but it shouldn't be exact
  // For a simple planar face, the mesh might have very few nodes
  // This test mainly ensures the mesh is still valid when mode is disabled
  EXPECT_TRUE(aClosestIdx > 0) << "Mesh should have nodes";
}