1
// Copyright (C) 2002-2011 Nikolaus Gebhardt
2
// This file is part of the "Irrlicht Engine".
3
// For conditions of distribution and use, see copyright notice in irrlicht.h
5
#ifndef __IRR_TRIANGLE_3D_H_INCLUDED__
6
#define __IRR_TRIANGLE_3D_H_INCLUDED__
18
//! 3d triangle template class for doing collision detection and other things.
24
//! Constructor for an all 0 triangle
26
//! Constructor for triangle with given three vertices
27
triangle3d(vector3d<T> v1, vector3d<T> v2, vector3d<T> v3) : pointA(v1), pointB(v2), pointC(v3) {}
30
bool operator==(const triangle3d<T>& other) const
32
return other.pointA==pointA && other.pointB==pointB && other.pointC==pointC;
35
//! Inequality operator
36
bool operator!=(const triangle3d<T>& other) const
38
return !(*this==other);
41
//! Determines if the triangle is totally inside a bounding box.
42
/** \param box Box to check.
43
\return True if triangle is within the box, otherwise false. */
44
bool isTotalInsideBox(const aabbox3d<T>& box) const
46
return (box.isPointInside(pointA) &&
47
box.isPointInside(pointB) &&
48
box.isPointInside(pointC));
51
//! Determines if the triangle is totally outside a bounding box.
52
/** \param box Box to check.
53
\return True if triangle is outside the box, otherwise false. */
54
bool isTotalOutsideBox(const aabbox3d<T>& box) const
56
return ((pointA.X > box.MaxEdge.X && pointB.X > box.MaxEdge.X && pointC.X > box.MaxEdge.X) ||
58
(pointA.Y > box.MaxEdge.Y && pointB.Y > box.MaxEdge.Y && pointC.Y > box.MaxEdge.Y) ||
59
(pointA.Z > box.MaxEdge.Z && pointB.Z > box.MaxEdge.Z && pointC.Z > box.MaxEdge.Z) ||
60
(pointA.X < box.MinEdge.X && pointB.X < box.MinEdge.X && pointC.X < box.MinEdge.X) ||
61
(pointA.Y < box.MinEdge.Y && pointB.Y < box.MinEdge.Y && pointC.Y < box.MinEdge.Y) ||
62
(pointA.Z < box.MinEdge.Z && pointB.Z < box.MinEdge.Z && pointC.Z < box.MinEdge.Z));
65
//! Get the closest point on a triangle to a point on the same plane.
66
/** \param p Point which must be on the same plane as the triangle.
67
\return The closest point of the triangle */
68
core::vector3d<T> closestPointOnTriangle(const core::vector3d<T>& p) const
70
const core::vector3d<T> rab = line3d<T>(pointA, pointB).getClosestPoint(p);
71
const core::vector3d<T> rbc = line3d<T>(pointB, pointC).getClosestPoint(p);
72
const core::vector3d<T> rca = line3d<T>(pointC, pointA).getClosestPoint(p);
74
const T d1 = rab.getDistanceFrom(p);
75
const T d2 = rbc.getDistanceFrom(p);
76
const T d3 = rca.getDistanceFrom(p);
79
return d1 < d3 ? rab : rca;
81
return d2 < d3 ? rbc : rca;
84
//! Check if a point is inside the triangle
85
/** \param p Point to test. Assumes that this point is already
86
on the plane of the triangle.
87
\return True if the point is inside the triangle, otherwise false. */
88
bool isPointInside(const vector3d<T>& p) const
90
return (isOnSameSide(p, pointA, pointB, pointC) &&
91
isOnSameSide(p, pointB, pointA, pointC) &&
92
isOnSameSide(p, pointC, pointA, pointB));
95
//! Check if a point is inside the triangle.
96
/** This method is an implementation of the example used in a
97
paper by Kasper Fauerby original written by Keidy from
99
\param p Point to test. Assumes that this point is already
100
on the plane of the triangle.
101
\return True if point is inside the triangle, otherwise false. */
102
bool isPointInsideFast(const vector3d<T>& p) const
104
const vector3d<T> f = pointB - pointA;
105
const vector3d<T> g = pointC - pointA;
107
const f32 a = f.dotProduct(f);
108
const f32 b = f.dotProduct(g);
109
const f32 c = g.dotProduct(g);
111
const vector3d<T> vp = p - pointA;
112
const f32 d = vp.dotProduct(f);
113
const f32 e = vp.dotProduct(g);
117
const f32 ac_bb = (a*c)-(b*b);
120
// return sign(z) && !(sign(x)||sign(y))
121
return (( (IR(z)) & ~((IR(x))|(IR(y))) ) & 0x80000000)!=0;
125
//! Get an intersection with a 3d line.
126
/** \param line Line to intersect with.
127
\param outIntersection Place to store the intersection point, if there is one.
128
\return True if there was an intersection, false if not. */
129
bool getIntersectionWithLimitedLine(const line3d<T>& line,
130
vector3d<T>& outIntersection) const
132
return getIntersectionWithLine(line.start,
133
line.getVector(), outIntersection) &&
134
outIntersection.isBetweenPoints(line.start, line.end);
138
//! Get an intersection with a 3d line.
139
/** Please note that also points are returned as intersection which
140
are on the line, but not between the start and end point of the line.
141
If you want the returned point be between start and end
142
use getIntersectionWithLimitedLine().
143
\param linePoint Point of the line to intersect with.
144
\param lineVect Vector of the line to intersect with.
145
\param outIntersection Place to store the intersection point, if there is one.
146
\return True if there was an intersection, false if there was not. */
147
bool getIntersectionWithLine(const vector3d<T>& linePoint,
148
const vector3d<T>& lineVect, vector3d<T>& outIntersection) const
150
if (getIntersectionOfPlaneWithLine(linePoint, lineVect, outIntersection))
151
return isPointInside(outIntersection);
157
//! Calculates the intersection between a 3d line and the plane the triangle is on.
158
/** \param lineVect Vector of the line to intersect with.
159
\param linePoint Point of the line to intersect with.
160
\param outIntersection Place to store the intersection point, if there is one.
161
\return True if there was an intersection, else false. */
162
bool getIntersectionOfPlaneWithLine(const vector3d<T>& linePoint,
163
const vector3d<T>& lineVect, vector3d<T>& outIntersection) const
165
const vector3d<T> normal = getNormal().normalize();
168
if ( core::iszero ( t2 = normal.dotProduct(lineVect) ) )
171
T d = pointA.dotProduct(normal);
172
T t = -(normal.dotProduct(linePoint) - d) / t2;
173
outIntersection = linePoint + (lineVect * t);
178
//! Get the normal of the triangle.
179
/** Please note: The normal is not always normalized. */
180
vector3d<T> getNormal() const
182
return (pointB - pointA).crossProduct(pointC - pointA);
185
//! Test if the triangle would be front or backfacing from any point.
186
/** Thus, this method assumes a camera position from which the
187
triangle is definitely visible when looking at the given direction.
188
Do not use this method with points as it will give wrong results!
189
\param lookDirection Look direction.
190
\return True if the plane is front facing and false if it is backfacing. */
191
bool isFrontFacing(const vector3d<T>& lookDirection) const
193
const vector3d<T> n = getNormal().normalize();
194
const f32 d = (f32)n.dotProduct(lookDirection);
195
return F32_LOWER_EQUAL_0(d);
198
//! Get the plane of this triangle.
199
plane3d<T> getPlane() const
201
return plane3d<T>(pointA, pointB, pointC);
204
//! Get the area of the triangle
207
return (pointB - pointA).crossProduct(pointC - pointA).getLength() * 0.5f;
211
//! sets the triangle's points
212
void set(const core::vector3d<T>& a, const core::vector3d<T>& b, const core::vector3d<T>& c)
219
//! the three points of the triangle
225
bool isOnSameSide(const vector3d<T>& p1, const vector3d<T>& p2,
226
const vector3d<T>& a, const vector3d<T>& b) const
228
vector3d<T> bminusa = b - a;
229
vector3d<T> cp1 = bminusa.crossProduct(p1 - a);
230
vector3d<T> cp2 = bminusa.crossProduct(p2 - a);
231
return (cp1.dotProduct(cp2) >= 0.0f);
236
//! Typedef for a f32 3d triangle.
237
typedef triangle3d<f32> triangle3df;
239
//! Typedef for an integer 3d triangle.
240
typedef triangle3d<s32> triangle3di;
242
} // end namespace core
243
} // end namespace irr