1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24
25 #include "pxr/pxr.h"
26 #include "pxr/base/gf/bbox3d.h"
27 #include "pxr/base/gf/math.h"
28 #include "pxr/base/gf/ostreamHelpers.h"
29
30 #include "pxr/base/tf/type.h"
31
32 PXR_NAMESPACE_OPEN_SCOPE
33
TF_REGISTRY_FUNCTION(TfType)34 TF_REGISTRY_FUNCTION(TfType)
35 {
36 TfType::Define<GfBBox3d>();
37 }
38
39 void
_SetMatrices(const GfMatrix4d & matrix)40 GfBBox3d::_SetMatrices(const GfMatrix4d &matrix)
41 {
42 const double PRECISION_LIMIT = 1.0e-13;
43 double det;
44
45 _isDegenerate = false;
46 _matrix = matrix;
47 _inverse = matrix.GetInverse(&det, PRECISION_LIMIT);
48
49 // Check for degenerate matrix:
50 if (GfAbs(det) <= PRECISION_LIMIT) {
51 _isDegenerate = true;
52 _inverse.SetIdentity();
53 }
54 }
55
56 double
GetVolume() const57 GfBBox3d::GetVolume() const
58 {
59 if (_box.IsEmpty())
60 return 0.0;
61
62 // The volume of a transformed box is just its untransformed
63 // volume times the determinant of the upper-left 3x3 of the xform
64 // matrix. Pretty cool, indeed.
65 GfVec3d size = _box.GetSize();
66 return fabs(_matrix.GetDeterminant3() * size[0] * size[1] * size[2]);
67 }
68
69 GfRange3d
ComputeAlignedRange() const70 GfBBox3d::ComputeAlignedRange() const
71 {
72 if (_box.IsEmpty())
73 return _box;
74
75 // Method: James Arvo, Graphics Gems I, pp 548-550
76
77 // Translate the origin and use the result as the min and max.
78 GfVec3d trans(_matrix[3][0], _matrix[3][1], _matrix[3][2]);
79 GfVec3d alignedMin = trans;
80 GfVec3d alignedMax = trans;
81
82 const GfVec3d &min = _box.GetMin();
83 const GfVec3d &max = _box.GetMax();
84
85 for (int j = 0; j < 3; j++) {
86 for (int i = 0; i < 3; i++) {
87 double a = min[i] * _matrix[i][j];
88 double b = max[i] * _matrix[i][j];
89 if (a < b) {
90 alignedMin[j] += a;
91 alignedMax[j] += b;
92 }
93 else {
94 alignedMin[j] += b;
95 alignedMax[j] += a;
96 }
97 }
98 }
99
100 return GfRange3d(alignedMin, alignedMax);
101 }
102
103 GfBBox3d
Combine(const GfBBox3d & b1,const GfBBox3d & b2)104 GfBBox3d::Combine(const GfBBox3d &b1, const GfBBox3d &b2)
105 {
106 GfBBox3d result;
107
108 // If either box is empty, use the other as is
109 if (b1.GetRange().IsEmpty())
110 result = b2;
111 else if (b2.GetRange().IsEmpty())
112 result = b1;
113
114 // If both boxes are degenerate, combine their projected
115 // boxes. Otherwise, transform the degenerate box into the space
116 // of the other box and combine the results in that space.
117 else if (b1._isDegenerate) {
118 if (b2._isDegenerate)
119 result = GfBBox3d(GfRange3d::GetUnion(b1.ComputeAlignedRange(),
120 b2.ComputeAlignedRange()));
121 else
122 result = _CombineInOrder(b2, b1);
123 }
124 else if (b2._isDegenerate)
125 result = _CombineInOrder(b1, b2);
126
127 // Non-degenerate case: Neither box is empty and they are in
128 // different spaces. To get the best results, we'll perform the
129 // merge of the two boxes in each of the two spaces. Whichever
130 // merge ends up being smaller (by volume) is the one we'll use.
131 // Note that we don't use ComputeAlignedRange() as part of the test.
132 // This is because projecting almost always adds a little extra
133 // space and it gives an unfair advantage to the box that is more
134 // closely aligned to the coordinate axes.
135 else {
136 GfBBox3d result1 = _CombineInOrder(b1, b2);
137 GfBBox3d result2 = _CombineInOrder(b2, b1);
138
139 // Test within a tolerance (based on volume) to make this
140 // reasonably deterministic.
141 double v1 = result1.GetVolume();
142 double v2 = result2.GetVolume();
143 double tolerance = GfMax(1e-10, 1e-6 * GfAbs(GfMax(v1, v2)));
144
145 result = (GfAbs(v1 - v2) <= tolerance ? result1 :
146 (v1 < v2 ? result1 : result2));
147 }
148
149 // The _hasZeroAreaPrimitives is set to true if either of the
150 // input boxes has it set to true.
151 result.SetHasZeroAreaPrimitives(b1.HasZeroAreaPrimitives() ||
152 b2.HasZeroAreaPrimitives());
153
154 return result;
155 }
156
157 GfBBox3d
_CombineInOrder(const GfBBox3d & b1,const GfBBox3d & b2)158 GfBBox3d::_CombineInOrder(const GfBBox3d &b1, const GfBBox3d &b2)
159 {
160 // Transform b2 into b1's space to get b2t
161 GfBBox3d b2t;
162 b2t._box = b2._box;
163 b2t._matrix = b2._matrix * b1._inverse;
164 b2t._inverse = b1._matrix * b2._inverse;
165
166 // Compute the projection of this box into b1's space.
167 GfRange3d proj = b2t.ComputeAlignedRange();
168
169 // Extend b1 by this box to get the result.
170 GfBBox3d result = b1;
171 result._box.UnionWith(proj);
172 return result;
173 }
174
175 GfVec3d
ComputeCentroid() const176 GfBBox3d::ComputeCentroid() const
177 {
178 GfVec3d a = GetRange().GetMax();
179 GfVec3d b = GetRange().GetMin();
180
181 return GetMatrix().Transform( .5 * (a + b) );
182 }
183
184 std::ostream &
operator <<(std::ostream & out,const GfBBox3d & b)185 operator<<(std::ostream& out, const GfBBox3d& b)
186 {
187 return out
188 << "[("
189 << Gf_OstreamHelperP(b.GetRange()) << ") ("
190 << Gf_OstreamHelperP(b.GetMatrix()) << ") "
191 << (b.HasZeroAreaPrimitives() ? "true" : "false")
192 << ']';
193 }
194
195 PXR_NAMESPACE_CLOSE_SCOPE
196