triangle3d.h

Go to the documentation of this file.

// Copyright (C) 2002-2011 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 "vector3d.h"
#include "line3d.h"
#include "plane3d.h"
#include "aabbox3d.h"

namespace irr
{
namespace core
{

        template <class T>
        class triangle3d
        {
        public:

                triangle3d() {}
                triangle3d(vector3d<T> v1, vector3d<T> v2, vector3d<T> 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));
                }


                core::vector3d<T> closestPointOnTriangle(const core::vector3d<T>& p) const
                {
                        const core::vector3d<T> rab = line3d<T>(pointA, pointB).getClosestPoint(p);
                        const core::vector3d<T> rbc = line3d<T>(pointB, pointC).getClosestPoint(p);
                        const core::vector3d<T> rca = line3d<T>(pointC, pointA).getClosestPoint(p);

                        const T d1 = rab.getDistanceFrom(p);
                        const T d2 = rbc.getDistanceFrom(p);
                        const T d3 = rca.getDistanceFrom(p);

                        if (d1 < d2)
                                return d1 < d3 ? rab : rca;

                        return d2 < d3 ? rbc : rca;
                }


                bool isPointInside(const vector3d<T>& p) const
                {
                        const vector3d<T> a = pointC - pointA;
                        const vector3d<T> b = pointB - pointA;
                        const vector3d<T> c = p - pointA;
                        
                        const f64 dotAA = a.dotProduct( a);
                        const f64 dotAB = a.dotProduct( b);
                        const f64 dotAC = a.dotProduct( c);
                        const f64 dotBB = b.dotProduct( b);
                        const f64 dotBC = b.dotProduct( c);
                         
                        // get coordinates in barycentric coordinate system
                        const f64 invDenom =  1/(dotAA * dotBB - dotAB * dotAB); 
                        const f64 u = (dotBB * dotAC - dotAB * dotBC) * invDenom;
                        const f64 v = (dotAA * dotBC - dotAB * dotAC ) * invDenom;
                 
                        // We count border-points as inside to keep downward compatibility.
                        // That's why we use >= and <= instead of > and < as more commonly seen on the web.
                        return (u >= 0) && (v >= 0) && (u + v <= 1);
                }


                bool isPointInsideFast(const vector3d<T>& p) const
                {
                        const vector3d<T> f = pointB - pointA;
                        const vector3d<T> g = pointC - pointA;

                        const f32 a = f.dotProduct(f);
                        const f32 b = f.dotProduct(g);
                        const f32 c = g.dotProduct(g);

                        const vector3d<T> vp = p - pointA;
                        const f32 d = vp.dotProduct(f);
                        const f32 e = vp.dotProduct(g);

                        f32 x = (d*c)-(e*b);
                        f32 y = (e*a)-(d*b);
                        const f32 ac_bb = (a*c)-(b*b);
                        f32 z = x+y-ac_bb;

                        // return sign(z) && !(sign(x)||sign(y))
                        return (( (IR(z)) & ~((IR(x))|(IR(y))) ) & 0x80000000)!=0;
                }



                bool getIntersectionWithLimitedLine(const line3d<T>& line,
                        vector3d<T>& outIntersection) const
                {
                        return getIntersectionWithLine(line.start,
                                line.getVector(), outIntersection) &&
                                outIntersection.isBetweenPoints(line.start, line.end);
                }



                bool getIntersectionWithLine(const vector3d<T>& linePoint,
                        const vector3d<T>& lineVect, vector3d<T>& outIntersection) const
                {
                        if (getIntersectionOfPlaneWithLine(linePoint, lineVect, outIntersection))
                                return isPointInside(outIntersection);

                        return false;
                }



                bool getIntersectionOfPlaneWithLine(const vector3d<T>& linePoint,
                        const vector3d<T>& lineVect, vector3d<T>& outIntersection) const
                {
                        const vector3d<T> normal = getNormal().normalize();
                        T t2;

                        if ( core::iszero ( t2 = normal.dotProduct(lineVect) ) )
                                return false;

                        T d = pointA.dotProduct(normal);
                        T t = -(normal.dotProduct(linePoint) - d) / t2;
                        outIntersection = linePoint + (lineVect * t);
                        return true;
                }



                vector3d<T> getNormal() const
                {
                        return (pointB - pointA).crossProduct(pointC - pointA);
                }


                bool isFrontFacing(const vector3d<T>& lookDirection) const
                {
                        const vector3d<T> n = getNormal().normalize();
                        const f32 d = (f32)n.dotProduct(lookDirection);
                        return F32_LOWER_EQUAL_0(d);
                }

                plane3d<T> getPlane() const
                {
                        return plane3d<T>(pointA, pointB, pointC);
                }

                T getArea() const
                {
                        return (pointB - pointA).crossProduct(pointC - pointA).getLength() * 0.5f;

                }

                void set(const core::vector3d<T>& a, const core::vector3d<T>& b, const core::vector3d<T>& c)
                {
                        pointA = a;
                        pointB = b;
                        pointC = c;
                }

                vector3d<T> pointA;
                vector3d<T> pointB;
                vector3d<T> pointC;

        private:
                bool isOnSameSide(const vector3d<T>& p1, const vector3d<T>& p2,
                        const vector3d<T>& a, const vector3d<T>& b) const
                {
                        vector3d<T> bminusa = b - a;
                        vector3d<T> cp1 = bminusa.crossProduct(p1 - a);
                        vector3d<T> cp2 = bminusa.crossProduct(p2 - a);
                        return (cp1.dotProduct(cp2) >= 0.0f);
                }
        };


        typedef triangle3d<f32> triangle3df;

        typedef triangle3d<s32> triangle3di;

} // end namespace core
} // end namespace irr

#endif