1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4  * License, v. 2.0. If a copy of the MPL was not distributed with this
5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 
7 #include "Matrix.h"
8 #include "Quaternion.h"
9 #include "Tools.h"
10 #include <algorithm>
11 #include <ostream>
12 #include <math.h>
13 #include <float.h>  // for FLT_EPSILON
14 
15 #include "mozilla/FloatingPoint.h"  // for UnspecifiedNaN
16 
17 namespace mozilla {
18 namespace gfx {
19 
20 /* Force small values to zero.  We do this to avoid having sin(360deg)
21  * evaluate to a tiny but nonzero value.
22  */
FlushToZero(double aVal)23 double FlushToZero(double aVal) {
24   // XXX Is double precision really necessary here
25   if (-FLT_EPSILON < aVal && aVal < FLT_EPSILON) {
26     return 0.0f;
27   } else {
28     return aVal;
29   }
30 }
31 
32 /* Computes tan(aTheta).  For values of aTheta such that tan(aTheta) is
33  * undefined or very large, SafeTangent returns a manageably large value
34  * of the correct sign.
35  */
SafeTangent(double aTheta)36 double SafeTangent(double aTheta) {
37   // XXX Is double precision really necessary here
38   const double kEpsilon = 0.0001;
39 
40   /* tan(theta) = sin(theta)/cos(theta); problems arise when
41    * cos(theta) is too close to zero.  Limit cos(theta) to the
42    * range [-1, -epsilon] U [epsilon, 1].
43    */
44 
45   double sinTheta = sin(aTheta);
46   double cosTheta = cos(aTheta);
47 
48   if (cosTheta >= 0 && cosTheta < kEpsilon) {
49     cosTheta = kEpsilon;
50   } else if (cosTheta < 0 && cosTheta >= -kEpsilon) {
51     cosTheta = -kEpsilon;
52   }
53   return FlushToZero(sinTheta / cosTheta);
54 }
55 
56 template <>
Rotation(Float aAngle)57 Matrix Matrix::Rotation(Float aAngle) {
58   Matrix newMatrix;
59 
60   Float s = sinf(aAngle);
61   Float c = cosf(aAngle);
62 
63   newMatrix._11 = c;
64   newMatrix._12 = s;
65   newMatrix._21 = -s;
66   newMatrix._22 = c;
67 
68   return newMatrix;
69 }
70 
71 template <>
Rotation(Double aAngle)72 MatrixDouble MatrixDouble::Rotation(Double aAngle) {
73   MatrixDouble newMatrix;
74 
75   Double s = sin(aAngle);
76   Double c = cos(aAngle);
77 
78   newMatrix._11 = c;
79   newMatrix._12 = s;
80   newMatrix._21 = -s;
81   newMatrix._22 = c;
82 
83   return newMatrix;
84 }
85 
86 template <>
operator *(const Matrix4x4 & aMatrix) const87 Matrix4x4 MatrixDouble::operator*(const Matrix4x4& aMatrix) const {
88   Matrix4x4 resultMatrix;
89 
90   resultMatrix._11 = this->_11 * aMatrix._11 + this->_12 * aMatrix._21;
91   resultMatrix._12 = this->_11 * aMatrix._12 + this->_12 * aMatrix._22;
92   resultMatrix._13 = this->_11 * aMatrix._13 + this->_12 * aMatrix._23;
93   resultMatrix._14 = this->_11 * aMatrix._14 + this->_12 * aMatrix._24;
94 
95   resultMatrix._21 = this->_21 * aMatrix._11 + this->_22 * aMatrix._21;
96   resultMatrix._22 = this->_21 * aMatrix._12 + this->_22 * aMatrix._22;
97   resultMatrix._23 = this->_21 * aMatrix._13 + this->_22 * aMatrix._23;
98   resultMatrix._24 = this->_21 * aMatrix._14 + this->_22 * aMatrix._24;
99 
100   resultMatrix._31 = aMatrix._31;
101   resultMatrix._32 = aMatrix._32;
102   resultMatrix._33 = aMatrix._33;
103   resultMatrix._34 = aMatrix._34;
104 
105   resultMatrix._41 =
106       this->_31 * aMatrix._11 + this->_32 * aMatrix._21 + aMatrix._41;
107   resultMatrix._42 =
108       this->_31 * aMatrix._12 + this->_32 * aMatrix._22 + aMatrix._42;
109   resultMatrix._43 =
110       this->_31 * aMatrix._13 + this->_32 * aMatrix._23 + aMatrix._43;
111   resultMatrix._44 =
112       this->_31 * aMatrix._14 + this->_32 * aMatrix._24 + aMatrix._44;
113 
114   return resultMatrix;
115 }
116 
117 // Intersect the polygon given by aPoints with the half space induced by
118 // aPlaneNormal and return the resulting polygon. The returned points are
119 // stored in aDestBuffer, and its meaningful subspan is returned.
120 template <typename F>
IntersectPolygon(Span<Point4DTyped<UnknownUnits,F>> aPoints,const Point4DTyped<UnknownUnits,F> & aPlaneNormal,Span<Point4DTyped<UnknownUnits,F>> aDestBuffer)121 Span<Point4DTyped<UnknownUnits, F>> IntersectPolygon(
122     Span<Point4DTyped<UnknownUnits, F>> aPoints,
123     const Point4DTyped<UnknownUnits, F>& aPlaneNormal,
124     Span<Point4DTyped<UnknownUnits, F>> aDestBuffer) {
125   if (aPoints.Length() < 1 || aDestBuffer.Length() < 1) {
126     return {};
127   }
128 
129   size_t nextIndex = 0;  // aDestBuffer[nextIndex] is the next emitted point.
130 
131   // Iterate over the polygon edges. In each iteration the current edge
132   // is the edge from *prevPoint to point. If the two end points lie on
133   // different sides of the plane, we have an intersection. Otherwise,
134   // the edge is either completely "inside" the half-space created by
135   // the clipping plane, and we add curPoint, or it is completely
136   // "outside", and we discard curPoint. This loop can create duplicated
137   // points in the polygon.
138   const auto* prevPoint = &aPoints[aPoints.Length() - 1];
139   F prevDot = aPlaneNormal.DotProduct(*prevPoint);
140   for (const auto& curPoint : aPoints) {
141     F curDot = aPlaneNormal.DotProduct(curPoint);
142 
143     if ((curDot >= 0.0) != (prevDot >= 0.0)) {
144       // An intersection with the clipping plane has been detected.
145       // Interpolate to find the intersecting curPoint and emit it.
146       F t = -prevDot / (curDot - prevDot);
147       aDestBuffer[nextIndex++] = curPoint * t + *prevPoint * (1.0 - t);
148       if (nextIndex >= aDestBuffer.Length()) {
149         break;
150       }
151     }
152 
153     if (curDot >= 0.0) {
154       // Emit any source points that are on the positive side of the
155       // clipping plane.
156       aDestBuffer[nextIndex++] = curPoint;
157       if (nextIndex >= aDestBuffer.Length()) {
158         break;
159       }
160     }
161 
162     prevPoint = &curPoint;
163     prevDot = curDot;
164   }
165 
166   return aDestBuffer.To(nextIndex);
167 }
168 
169 template Span<Point4DTyped<UnknownUnits, Float>> IntersectPolygon(
170     Span<Point4DTyped<UnknownUnits, Float>> aPoints,
171     const Point4DTyped<UnknownUnits, Float>& aPlaneNormal,
172     Span<Point4DTyped<UnknownUnits, Float>> aDestBuffer);
173 template Span<Point4DTyped<UnknownUnits, Double>> IntersectPolygon(
174     Span<Point4DTyped<UnknownUnits, Double>> aPoints,
175     const Point4DTyped<UnknownUnits, Double>& aPlaneNormal,
176     Span<Point4DTyped<UnknownUnits, Double>> aDestBuffer);
177 
178 }  // namespace gfx
179 }  // namespace mozilla
180