triangle3d.h

Go to the documentation of this file.

// Copyright (C) 2002-2012 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h
 
#ifndef __IRR_TRIANGLE_3D_H_INCLUDED__
#define __IRR_TRIANGLE_3D_H_INCLUDED__
 
#include "line3d.h"
#include "plane3d.h"
#include "aabbox3d.h"
 
namespace saga
{
namespace core
{
 
  template <class T>
  class triangle3d
  {
  public:
 
    triangle3d() {}
    triangle3d(const glm::vec3& v1, const glm::vec3& v2, const glm::vec3& v3) : pointA(v1), pointB(v2), pointC(v3) {}
 
    bool operator==(const triangle3d<T>& other) const
    {
      return other.pointA==pointA && other.pointB==pointB && other.pointC==pointC;
    }
 
    bool operator!=(const triangle3d<T>& other) const
    {
      return !(*this==other);
    }
 
 
    bool isTotalInsideBox(const aabbox3d<T>& box) const
    {
      return (box.isPointInside(pointA) &&
        box.isPointInside(pointB) &&
        box.isPointInside(pointC));
    }
 
 
    bool isTotalOutsideBox(const aabbox3d<T>& box) const
    {
      return ((pointA.x > box.MaxEdge.X && pointB.x > box.MaxEdge.X && pointC.x > box.MaxEdge.X) ||
 
        (pointA.y > box.MaxEdge.Y && pointB.y > box.MaxEdge.Y && pointC.y > box.MaxEdge.Y) ||
        (pointA.z > box.MaxEdge.Z && pointB.z > box.MaxEdge.Z && pointC.z > box.MaxEdge.Z) ||
        (pointA.x < box.MinEdge.X && pointB.x < box.MinEdge.X && pointC.x < box.MinEdge.X) ||
        (pointA.y < box.MinEdge.Y && pointB.y < box.MinEdge.Y && pointC.y < box.MinEdge.Y) ||
        (pointA.z < box.MinEdge.Z && pointB.z < box.MinEdge.Z && pointC.z < box.MinEdge.Z));
    }
 
 
    glm::vec3 closestPointOnTriangle(const glm::vec3& p) const
    {
      const glm::vec3 rab = line3d<T>(pointA, pointB).getClosestPoint(p);
      const glm::vec3 rbc = line3d<T>(pointB, pointC).getClosestPoint(p);
      const glm::vec3 rca = line3d<T>(pointC, pointA).getClosestPoint(p);
 
      const T d1 = glm::distance(rab, p);
      const T d2 = glm::distance(rbc, p);
      const T d3 = glm::distance(rca, p);
 
      if (d1 < d2)
        return d1 < d3 ? rab : rca;
 
      return d2 < d3 ? rbc : rca;
    }
 
    /*
    \param p Point to test. Assumes that this point is already
    on the plane of the triangle.
    \return True if the point is inside the triangle, otherwise false. */
    bool isPointInside(const glm::vec3& p) const
    {
      glm::vec3 adouble((double)pointA.x, (double)pointA.y, (double)pointA.z);
      glm::vec3 bdouble((double)pointB.x, (double)pointB.y, (double)pointB.z);
      glm::vec3 cdouble((double)pointC.x, (double)pointC.y, (double)pointC.z);
      glm::vec3 pdouble((double)p.x, (double)p.y, (double)p.z);
      return (isOnSameSide(pdouble, adouble, bdouble, cdouble) &&
        isOnSameSide(pdouble, bdouble, adouble, cdouble) &&
        isOnSameSide(pdouble, cdouble, adouble, bdouble));
    }
 
 
    bool isPointInsideFast(const glm::vec3& p) const
    {
      const glm::vec3 a = pointC - pointA;
      const glm::vec3 b = pointB - pointA;
      const glm::vec3 c = p - pointA;
 
      const double dotAA = glm::dot(a, a);
      const double dotAB = glm::dot(b, b);
      const double dotAC = glm::dot(a, c);
      const double dotBB = glm::dot(b, b);
      const double dotBC = glm::dot(b, c);
 
      // get coordinates in barycentric coordinate system
      const double invDenom =  1/(dotAA * dotBB - dotAB * dotAB);
      const double u = (dotBB * dotAC - dotAB * dotBC) * invDenom;
      const double v = (dotAA * dotBC - dotAB * dotAC) * invDenom;
 
      // We count border-points as inside to keep downward compatibility.
      // Rounding-error also needed for some test-cases.
      return (u > -ROUNDING_ERROR_float) && (v >= 0) && (u + v < 1+ROUNDING_ERROR_float);
 
    }
 
 
 
    bool getIntersectionWithLimitedLine(const line3d<T>& line,
      glm::vec3& outIntersection) const
    {
      return getIntersectionWithLine(line.start,
        line.getVector(), outIntersection) &&
        isBetweenPoints(outIntersection, line.start, line.end);
    }
 
 
 
    bool getIntersectionWithLine(const glm::vec3& linePoint,
      const glm::vec3& lineVect, glm::vec3& outIntersection) const
    {
      if (getIntersectionOfPlaneWithLine(linePoint, lineVect, outIntersection))
        return isPointInside(outIntersection);
 
      return false;
    }
 
 
 
    bool getIntersectionOfPlaneWithLine(const glm::vec3& linePoint,
      const glm::vec3& lineVect, glm::vec3& outIntersection) const
    {
      // Work with double to get more precise results (makes enough difference to be worth the casts).
      const glm::vec3 linePointdouble(linePoint.x, linePoint.y, linePoint.z);
      const glm::vec3 lineVectdouble(lineVect.x, lineVect.y, lineVect.z);
      glm::vec3 outIntersectiondouble;
 
      core::triangle3d<double> triangledouble(glm::vec3((double)pointA.x, (double)pointA.y, (double)pointA.z)
                    ,glm::vec3((double)pointB.x, (double)pointB.y, (double)pointB.z)
                    , glm::vec3((double)pointC.x, (double)pointC.y, (double)pointC.z));
      const glm::vec3 normaldouble = glm::normalize(triangledouble.getNormal());
      double t2;
 
      if (core::iszero (t2 = glm::dot(normaldouble, lineVectdouble)))
        return false;
 
      double d = glm::dot(triangledouble.pointA, normaldouble);
      double t = -(glm::dot(normaldouble, linePointdouble) - d) / t2;
      outIntersectiondouble = linePointdouble + (lineVectdouble * float(t));
 
      outIntersection.x = (T)outIntersectiondouble.x;
      outIntersection.y = (T)outIntersectiondouble.y;
      outIntersection.z = (T)outIntersectiondouble.z;
      return true;
    }
 
 
 
    glm::vec3 getNormal() const
    {
      return glm::cross(pointB - pointA, pointC - pointA);
    }
 
 
    bool isFrontFacing(const glm::vec3& lookDirection) const
    {
      const glm::vec3 n = getNormal().normalize();
      const float d = (float) glm::dot(n, lookDirection);
      return F32_LOWER_EQUAL_0(d);
    }
 
    plane3d<T> getPlane() const
    {
      return plane3d<T>(pointA, pointB, pointC);
    }
 
    T getArea() const
    {
      return glm::length(glm::cross(pointB - pointA, pointC - pointA)) * 0.5f;
 
    }
 
    void set(const glm::vec3& a, const glm::vec3& b, const glm::vec3& c)
    {
      pointA = a;
      pointB = b;
      pointC = c;
    }
 
    glm::vec3 pointA;
    glm::vec3 pointB;
    glm::vec3 pointC;
 
  private:
    // Using double instead of <T> to avoid integer overflows when T=int (maybe also less floating point troubles).
    bool isOnSameSide(const glm::vec3& p1, const glm::vec3& p2,
      const glm::vec3& a, const glm::vec3& b) const
    {
      glm::vec3 bminusa = b - a;
      glm::vec3 cp1 = glm::cross(bminusa, p1 - a);
      glm::vec3 cp2 = glm::cross(bminusa, p2 - a);
      double res = glm::dot(cp1, cp2);
      if (res < 0)
      {
        // This catches some floating point troubles.
        // Unfortunately slightly expensive and we don't really know the best epsilon for iszero.
        glm::vec3 cp1 = glm::cross(glm::normalize(bminusa), (p1 - a));
        cp1 = glm::normalize(cp1);
        if (core::iszero(cp1.x, (double)ROUNDING_ERROR_float)
          && core::iszero(cp1.y, (double)ROUNDING_ERROR_float)
          && core::iszero(cp1.z, (double)ROUNDING_ERROR_float))
        {
          res = 0.f;
        }
      }
      return (res >= 0.0f);
    }
  };
 
 
  typedef triangle3d<float> triangle3df;
 
  typedef triangle3d<std::int32_t> triangle3di;
 
} // namespace core
} // namespace saga
 
#endif