[191] | 1 | #include <stack>
|
---|
| 2 | using namespace std;
|
---|
| 3 | #include "KdTree.h"
|
---|
| 4 | #include "AxisAlignedBox3.h"
|
---|
| 5 | #include "Ray.h"
|
---|
| 6 | #include "MutualVisibility.h"
|
---|
| 7 |
|
---|
| 8 |
|
---|
| 9 | void
|
---|
| 10 | TriangleSample::Init(
|
---|
| 11 | const Triangle3 &source,
|
---|
| 12 | const Triangle3 &target)
|
---|
| 13 | {
|
---|
| 14 | mDepth = 0;
|
---|
| 15 | mSource = source;
|
---|
| 16 | mTarget = target;
|
---|
| 17 | }
|
---|
| 18 |
|
---|
| 19 |
|
---|
| 20 | Vector3
|
---|
| 21 | TriangleSample::GetIntersectionPoint(const int rayIndex,
|
---|
| 22 | const int depth) const
|
---|
| 23 | {
|
---|
| 24 | Vector3 origin, direction;
|
---|
| 25 | GetRay(rayIndex, origin, direction);
|
---|
| 26 | return origin + direction*mIntersections[rayIndex][depth].mT;
|
---|
| 27 | }
|
---|
| 28 |
|
---|
| 29 | void
|
---|
| 30 | TriangleSample::GetRay(const int rayIndex,
|
---|
| 31 | Vector3 &origin,
|
---|
| 32 | Vector3 &direction) const
|
---|
| 33 | {
|
---|
| 34 | const int indices[][2] = {
|
---|
| 35 | {0,0}, {0,1}, {0,2},
|
---|
| 36 | {1,0}, {1,1}, {1,2},
|
---|
| 37 | {2,0}, {2,1}, {2,2}
|
---|
| 38 | };
|
---|
| 39 |
|
---|
| 40 | origin = mSource.mVertices[indices[rayIndex][0]];
|
---|
| 41 | direction = mTarget.mVertices[indices[rayIndex][1]] - origin;
|
---|
| 42 | }
|
---|
| 43 |
|
---|
| 44 | void
|
---|
| 45 | MutualVisibilitySampler::PerformSplit(
|
---|
| 46 | const TriangleSample &sample,
|
---|
| 47 | const bool splitSource,
|
---|
| 48 | const int edge,
|
---|
| 49 | const Vector3 &splitPoint,
|
---|
| 50 | const Ray &ray,
|
---|
| 51 | TriangleSample &sample1,
|
---|
| 52 | TriangleSample &sample2
|
---|
| 53 | )
|
---|
| 54 | {
|
---|
| 55 |
|
---|
| 56 |
|
---|
| 57 | const Triangle3 *triangle;
|
---|
| 58 | Triangle3 *triangle1, *triangle2;
|
---|
| 59 | // split the triangles
|
---|
| 60 | if (splitSource) {
|
---|
| 61 | sample1.mTarget = sample.mTarget;
|
---|
| 62 | sample2.mTarget = sample.mTarget;
|
---|
| 63 | triangle1 = &sample1.mSource;
|
---|
| 64 | triangle2 = &sample2.mSource;
|
---|
| 65 | triangle = &sample.mSource;
|
---|
| 66 | } else {
|
---|
| 67 | sample1.mSource = sample.mSource;
|
---|
| 68 | sample2.mSource = sample.mSource;
|
---|
| 69 | triangle1 = &sample1.mTarget;
|
---|
| 70 | triangle2 = &sample2.mTarget;
|
---|
| 71 | triangle = &sample.mTarget;
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 | // split the intersections
|
---|
| 75 | switch (edge) {
|
---|
| 76 | case 0:
|
---|
| 77 | sample1.mIntersections[0] = sample.mIntersections[0];
|
---|
| 78 | sample1.mIntersections[1] = sample.mIntersections[1];
|
---|
| 79 | triangle1->mVertices[0] = triangle->mVertices[0];
|
---|
| 80 | triangle1->mVertices[1] = triangle->mVertices[1];
|
---|
| 81 |
|
---|
| 82 | sample2.mIntersections[0] = sample.mIntersections[2];
|
---|
| 83 | sample2.mIntersections[1] = sample.mIntersections[0];
|
---|
| 84 | triangle2->mVertices[0] = triangle->mVertices[2];
|
---|
| 85 | triangle2->mVertices[1] = triangle->mVertices[0];
|
---|
| 86 | break;
|
---|
| 87 |
|
---|
| 88 | case 1:
|
---|
| 89 | sample1.mIntersections[0] = sample.mIntersections[0];
|
---|
| 90 | sample1.mIntersections[1] = sample.mIntersections[1];
|
---|
| 91 | triangle1->mVertices[0] = triangle->mVertices[0];
|
---|
| 92 | triangle1->mVertices[1] = triangle->mVertices[1];
|
---|
| 93 |
|
---|
| 94 | sample2.mIntersections[0] = sample.mIntersections[1];
|
---|
| 95 | sample2.mIntersections[1] = sample.mIntersections[2];
|
---|
| 96 | triangle2->mVertices[0] = triangle->mVertices[1];
|
---|
| 97 | triangle2->mVertices[1] = triangle->mVertices[2];
|
---|
| 98 | break;
|
---|
| 99 |
|
---|
| 100 | case 2:
|
---|
| 101 | sample1.mIntersections[0] = sample.mIntersections[2];
|
---|
| 102 | sample1.mIntersections[1] = sample.mIntersections[0];
|
---|
| 103 | triangle1->mVertices[0] = triangle->mVertices[2];
|
---|
| 104 | triangle1->mVertices[1] = triangle->mVertices[0];
|
---|
| 105 |
|
---|
| 106 | sample2.mIntersections[0] = sample.mIntersections[1];
|
---|
| 107 | sample2.mIntersections[1] = sample.mIntersections[2];
|
---|
| 108 | triangle2->mVertices[0] = triangle->mVertices[1];
|
---|
| 109 | triangle2->mVertices[1] = triangle->mVertices[2];
|
---|
| 110 | break;
|
---|
| 111 | }
|
---|
| 112 |
|
---|
| 113 | // the new sample
|
---|
| 114 | sample1.mIntersections[2] = ray.intersections;
|
---|
| 115 | sample2.mIntersections[2] = ray.intersections;
|
---|
| 116 | triangle1->mVertices[2] = splitPoint;
|
---|
| 117 | triangle2->mVertices[2] = splitPoint;
|
---|
| 118 |
|
---|
| 119 | // establish the new samples
|
---|
| 120 | sample1.mDepth = sample2.mDepth = sample.mDepth+1;
|
---|
| 121 | }
|
---|
| 122 |
|
---|
| 123 | float
|
---|
| 124 | MutualVisibilitySampler::GetSpatialAngle(const TriangleSample &sample,
|
---|
| 125 | const Vector3 &point
|
---|
| 126 | )
|
---|
| 127 | {
|
---|
| 128 | const int sampleIndices[][3]={
|
---|
| 129 | (0,0,0),
|
---|
| 130 | (0,1,0),
|
---|
| 131 | (-1,-1,-1)
|
---|
| 132 | };
|
---|
| 133 |
|
---|
| 134 | float sum = 0.0f;
|
---|
| 135 | int i;
|
---|
| 136 |
|
---|
| 137 | for (i=0; i < 10; i++) {
|
---|
| 138 | Triangle3 triangle(sample.GetIntersectionPoint(sampleIndices[i][0], 0),
|
---|
| 139 | sample.GetIntersectionPoint(sampleIndices[i][1], 0),
|
---|
| 140 | sample.GetIntersectionPoint(sampleIndices[i][2], 0));
|
---|
| 141 |
|
---|
| 142 | sum += triangle.GetSpatialAngle(point);
|
---|
| 143 | }
|
---|
| 144 | return sum;
|
---|
| 145 | }
|
---|
| 146 |
|
---|
| 147 |
|
---|
| 148 | void
|
---|
| 149 | MutualVisibilitySampler::ComputeError(TriangleSample &sample)
|
---|
| 150 | {
|
---|
| 151 | // evaluate minimal error which can be achieved by more precise evaluation
|
---|
| 152 | // if this is above the threshold do not proceed further
|
---|
| 153 |
|
---|
| 154 | float maxAngle = GetSpatialAngle(sample,
|
---|
| 155 | sample.mSource.GetCenter());
|
---|
| 156 |
|
---|
| 157 | for (int i=0; i < 3; i++) {
|
---|
| 158 | float angle = GetSpatialAngle(sample,
|
---|
| 159 | sample.mSource.mVertices[i]);
|
---|
| 160 | if (angle > maxAngle)
|
---|
| 161 | maxAngle = angle;
|
---|
| 162 | }
|
---|
| 163 |
|
---|
| 164 | sample.mError = maxAngle;
|
---|
| 165 | }
|
---|
| 166 |
|
---|
| 167 |
|
---|
| 168 |
|
---|
| 169 |
|
---|
| 170 |
|
---|
| 171 | void
|
---|
| 172 | MutualVisibilitySampler::ConstructInitialSamples(
|
---|
| 173 | const AxisAlignedBox3 &source,
|
---|
| 174 | const AxisAlignedBox3 &target,
|
---|
| 175 | vector<TriangleSample *> &samples
|
---|
| 176 | )
|
---|
| 177 | {
|
---|
| 178 | // get all rectangles potentially visible from the source box
|
---|
| 179 | int i;
|
---|
| 180 | int sourceMask = 0;
|
---|
| 181 | for (i=0; i < 8; i++)
|
---|
| 182 | sourceMask |= source.GetFaceVisibilityMask(target.GetVertex(i));
|
---|
| 183 |
|
---|
| 184 | // now for each visble source face find all visible target faces
|
---|
| 185 | for (i=0; i < 6; i++) {
|
---|
| 186 | Rectangle3 sourceFace = source.GetFace(i);
|
---|
| 187 | if ( sourceMask &(1<<i) ) {
|
---|
| 188 | int mask = target.GetFaceVisibilityMask(sourceFace);
|
---|
| 189 | // construct triangle samples for all visible rectangles
|
---|
| 190 | for (int j=0; j < 6; j++)
|
---|
| 191 | if (mask & (1<<j)) {
|
---|
| 192 | AddInitialSamples(sourceFace, target.GetFace(j), samples);
|
---|
| 193 | }
|
---|
| 194 | }
|
---|
| 195 | }
|
---|
| 196 | }
|
---|
| 197 |
|
---|
| 198 | void
|
---|
| 199 | MutualVisibilitySampler::AddInitialSamples(
|
---|
| 200 | const Rectangle3 &sourceRect,
|
---|
| 201 | const Rectangle3 &targetRect,
|
---|
| 202 | vector<TriangleSample *> &samples
|
---|
| 203 | )
|
---|
| 204 | {
|
---|
| 205 | Triangle3 sourceTriangles[2];
|
---|
| 206 | Triangle3 targetTriangles[2];
|
---|
| 207 |
|
---|
| 208 | sourceTriangles[0].Init(sourceRect.mVertices[0],
|
---|
| 209 | sourceRect.mVertices[1],
|
---|
| 210 | sourceRect.mVertices[2]);
|
---|
| 211 |
|
---|
| 212 | sourceTriangles[1].Init(sourceRect.mVertices[0],
|
---|
| 213 | sourceRect.mVertices[2],
|
---|
| 214 | sourceRect.mVertices[3]);
|
---|
| 215 |
|
---|
| 216 | targetTriangles[0].Init(targetRect.mVertices[0],
|
---|
| 217 | targetRect.mVertices[1],
|
---|
| 218 | targetRect.mVertices[2]);
|
---|
| 219 |
|
---|
| 220 | targetTriangles[1].Init(targetRect.mVertices[0],
|
---|
| 221 | targetRect.mVertices[2],
|
---|
| 222 | targetRect.mVertices[3]);
|
---|
| 223 | int i, j;
|
---|
| 224 | for (i=0; i < 2; i++)
|
---|
| 225 | for (j=0; j < 2; j++) {
|
---|
| 226 | TriangleSample *sample = new TriangleSample(sourceTriangles[i],
|
---|
| 227 | targetTriangles[j]);
|
---|
| 228 | samples.push_back(sample);
|
---|
| 229 | }
|
---|
| 230 | }
|
---|
| 231 |
|
---|
| 232 | int
|
---|
| 233 | MutualVisibilitySampler::ComputeVisibility()
|
---|
| 234 | {
|
---|
| 235 | stack<TriangleSample *> sampleStack;
|
---|
| 236 |
|
---|
| 237 | Ray ray;
|
---|
| 238 | // now process the samples as long as we have something to do
|
---|
| 239 | while (!sampleStack.empty()) {
|
---|
| 240 | TriangleSample *sample = sampleStack.top();
|
---|
| 241 | sampleStack.pop();
|
---|
| 242 |
|
---|
| 243 | // // cast a new ray
|
---|
| 244 | // int triangleSplitEdge = SetupExtremalRay(sample, source, ray);
|
---|
| 245 |
|
---|
| 246 | // if (!kdTree->CastRay(ray))
|
---|
| 247 | // return VISIBLE;
|
---|
| 248 |
|
---|
| 249 | // // generate 2 new samples
|
---|
| 250 | // TriangleSample newSamples[2];
|
---|
| 251 | // sample.Split(triangleSplitEdge, ray, newSamples[0], newSamples[1]);
|
---|
| 252 | // for (i=0; i < 2; i++) {
|
---|
| 253 | // newSamples[i].ComputeError();
|
---|
| 254 | // if (newSamples[i].mError > solidAngleThreshold) {
|
---|
| 255 | // sampleStack.push(newSamples[i]);
|
---|
| 256 | // }
|
---|
| 257 | // }
|
---|
| 258 | // }
|
---|
| 259 | }
|
---|
| 260 | return INVISIBLE;
|
---|
| 261 | }
|
---|
| 262 |
|
---|
| 263 | MutualVisibilitySampler::MutualVisibilitySampler(KdTree *kdTree,
|
---|
| 264 | AxisAlignedBox3 &source,
|
---|
| 265 | AxisAlignedBox3 &target,
|
---|
| 266 | const float solidAngleThreshold)
|
---|
| 267 | {
|
---|
| 268 | mKdTree = kdTree;
|
---|
| 269 | mSource = source;
|
---|
| 270 | mTarget = target;
|
---|
| 271 | mSolidAngleThreshold = solidAngleThreshold;
|
---|
| 272 | }
|
---|
| 273 |
|
---|
| 274 |
|
---|
| 275 | int
|
---|
| 276 | ComputeBoxVisibility(KdTree *kdTree,
|
---|
| 277 | AxisAlignedBox3 &source,
|
---|
| 278 | AxisAlignedBox3 &target,
|
---|
| 279 | const float solidAngleThreshold)
|
---|
| 280 | {
|
---|
| 281 | MutualVisibilitySampler sampler(kdTree, source, target, solidAngleThreshold);
|
---|
| 282 |
|
---|
| 283 | int visibility = sampler.ComputeVisibility();
|
---|
| 284 |
|
---|
| 285 | return visibility;
|
---|
| 286 |
|
---|
| 287 | }
|
---|
| 288 |
|
---|