[209] | 1 | #include <assert.h>
|
---|
[191] | 2 | #include <stack>
|
---|
| 3 | using namespace std;
|
---|
| 4 | #include "KdTree.h"
|
---|
| 5 | #include "AxisAlignedBox3.h"
|
---|
| 6 | #include "Ray.h"
|
---|
| 7 | #include "MutualVisibility.h"
|
---|
[209] | 8 | #include "Exporter.h"
|
---|
| 9 | #include "Mesh.h"
|
---|
| 10 | #include "Triangle3.h"
|
---|
[191] | 11 |
|
---|
| 12 | void
|
---|
[209] | 13 | RayShaft::Init(
|
---|
| 14 | const Rectangle3 &source,
|
---|
| 15 | const Rectangle3 &target)
|
---|
[191] | 16 | {
|
---|
| 17 | mDepth = 0;
|
---|
| 18 | mSource = source;
|
---|
| 19 | mTarget = target;
|
---|
| 20 | }
|
---|
| 21 |
|
---|
| 22 |
|
---|
| 23 | Vector3
|
---|
[209] | 24 | RayShaft::GetIntersectionPoint(const int rayIndex,
|
---|
| 25 | const int depth) const
|
---|
[191] | 26 | {
|
---|
| 27 | Vector3 origin, direction;
|
---|
| 28 | GetRay(rayIndex, origin, direction);
|
---|
[223] | 29 | return origin + direction*mSamples[rayIndex].mIntersections[depth].mT;
|
---|
[191] | 30 | }
|
---|
| 31 |
|
---|
| 32 | void
|
---|
[209] | 33 | RayShaft::GetRay(const int rayIndex,
|
---|
| 34 | Vector3 &origin,
|
---|
| 35 | Vector3 &direction) const
|
---|
[191] | 36 | {
|
---|
| 37 |
|
---|
[209] | 38 | assert(rayIndex < 4);
|
---|
| 39 |
|
---|
| 40 | origin = mSource.mVertices[rayIndex];
|
---|
| 41 | direction = mTarget.mVertices[rayIndex] - origin;
|
---|
[191] | 42 | }
|
---|
| 43 |
|
---|
| 44 | void
|
---|
| 45 | MutualVisibilitySampler::PerformSplit(
|
---|
[209] | 46 | const RayShaft &sample,
|
---|
[191] | 47 | const bool splitSource,
|
---|
[209] | 48 | const int axis,
|
---|
| 49 | RayShaft &sample1,
|
---|
| 50 | RayShaft &sample2
|
---|
[191] | 51 | )
|
---|
| 52 | {
|
---|
[209] | 53 |
|
---|
[191] | 54 |
|
---|
[209] | 55 | // split the triangles
|
---|
[191] | 56 |
|
---|
| 57 | if (splitSource) {
|
---|
| 58 | sample1.mTarget = sample.mTarget;
|
---|
| 59 | sample2.mTarget = sample.mTarget;
|
---|
[209] | 60 | sample.mSource.Split(
|
---|
| 61 | axis,
|
---|
| 62 | sample1.mSource,
|
---|
| 63 | sample2.mSource);
|
---|
[191] | 64 | } else {
|
---|
[209] | 65 |
|
---|
[191] | 66 | sample1.mSource = sample.mSource;
|
---|
| 67 | sample2.mSource = sample.mSource;
|
---|
[209] | 68 |
|
---|
| 69 | sample.mTarget.Split(
|
---|
| 70 | axis,
|
---|
| 71 | sample1.mTarget,
|
---|
| 72 | sample2.mTarget);
|
---|
[191] | 73 | }
|
---|
| 74 |
|
---|
| 75 | // split the intersections
|
---|
[209] | 76 | switch (axis) {
|
---|
[191] | 77 | case 0:
|
---|
[223] | 78 | sample1.mSamples[0].mIntersections = sample.mSamples[0].mIntersections;
|
---|
| 79 | sample1.mSamples[3].mIntersections = sample.mSamples[3].mIntersections;
|
---|
[191] | 80 |
|
---|
[223] | 81 | sample2.mSamples[1].mIntersections = sample.mSamples[1].mIntersections;
|
---|
| 82 | sample2.mSamples[2].mIntersections = sample.mSamples[2].mIntersections;
|
---|
[191] | 83 | break;
|
---|
| 84 |
|
---|
| 85 | case 1:
|
---|
[223] | 86 | sample1.mSamples[0].mIntersections = sample.mSamples[0].mIntersections;
|
---|
| 87 | sample1.mSamples[1].mIntersections = sample.mSamples[1].mIntersections;
|
---|
[191] | 88 |
|
---|
[223] | 89 | sample2.mSamples[2].mIntersections = sample.mSamples[2].mIntersections;
|
---|
| 90 | sample2.mSamples[3].mIntersections = sample.mSamples[3].mIntersections;
|
---|
[191] | 91 | break;
|
---|
[209] | 92 | }
|
---|
[191] | 93 |
|
---|
[209] | 94 | // the intersections for the new shaft rays will be established
|
---|
| 95 | // later
|
---|
[191] | 96 | sample1.mDepth = sample2.mDepth = sample.mDepth+1;
|
---|
| 97 | }
|
---|
| 98 |
|
---|
| 99 | float
|
---|
[209] | 100 | MutualVisibilitySampler::GetSpatialAngle(const RayShaft &sample,
|
---|
[191] | 101 | const Vector3 &point
|
---|
| 102 | )
|
---|
| 103 | {
|
---|
[209] | 104 | const int sampleIndices[][2]={
|
---|
| 105 | (0,1,2),
|
---|
| 106 | (0,2,3)
|
---|
[191] | 107 | };
|
---|
| 108 |
|
---|
| 109 | float sum = 0.0f;
|
---|
| 110 | int i;
|
---|
| 111 |
|
---|
[209] | 112 | for (i=0; i < 2; i++) {
|
---|
[191] | 113 | Triangle3 triangle(sample.GetIntersectionPoint(sampleIndices[i][0], 0),
|
---|
[209] | 114 | sample.GetIntersectionPoint(sampleIndices[i][1], 0),
|
---|
| 115 | sample.GetIntersectionPoint(sampleIndices[i][2], 0));
|
---|
[191] | 116 | sum += triangle.GetSpatialAngle(point);
|
---|
| 117 | }
|
---|
[209] | 118 |
|
---|
[191] | 119 | return sum;
|
---|
| 120 | }
|
---|
| 121 |
|
---|
| 122 |
|
---|
| 123 | void
|
---|
[209] | 124 | MutualVisibilitySampler::ComputeError(RayShaft &sample)
|
---|
[191] | 125 | {
|
---|
| 126 | // evaluate minimal error which can be achieved by more precise evaluation
|
---|
| 127 | // if this is above the threshold do not proceed further
|
---|
| 128 |
|
---|
| 129 | float maxAngle = GetSpatialAngle(sample,
|
---|
| 130 | sample.mSource.GetCenter());
|
---|
| 131 |
|
---|
| 132 | for (int i=0; i < 3; i++) {
|
---|
| 133 | float angle = GetSpatialAngle(sample,
|
---|
| 134 | sample.mSource.mVertices[i]);
|
---|
| 135 | if (angle > maxAngle)
|
---|
| 136 | maxAngle = angle;
|
---|
| 137 | }
|
---|
| 138 |
|
---|
| 139 | sample.mError = maxAngle;
|
---|
| 140 | }
|
---|
| 141 |
|
---|
| 142 |
|
---|
| 143 | void
|
---|
| 144 | MutualVisibilitySampler::ConstructInitialSamples(
|
---|
| 145 | const AxisAlignedBox3 &source,
|
---|
| 146 | const AxisAlignedBox3 &target,
|
---|
[209] | 147 | vector<RayShaft *> &samples
|
---|
[191] | 148 | )
|
---|
| 149 | {
|
---|
[223] | 150 | Vector3 sourceCenter = source.Center();
|
---|
| 151 | Vector3 targetCenter = target.Center();
|
---|
| 152 | Vector3 normal = Normalize(sourceCenter - targetCenter );
|
---|
| 153 |
|
---|
[209] | 154 | Plane3 sourcePlane(normal, source.GetVertex(0));
|
---|
[191] | 155 | int i;
|
---|
[209] | 156 | for (i=1; i < 8; i++) {
|
---|
| 157 | Vector3 v = source.GetVertex(i);
|
---|
| 158 | if (sourcePlane.Distance(v) > 0)
|
---|
| 159 | sourcePlane = Plane3(normal, v);
|
---|
| 160 | }
|
---|
| 161 |
|
---|
[223] | 162 | Plane3 targetPlane(normal, target.GetVertex(0));
|
---|
[209] | 163 | for (i=1; i < 8; i++) {
|
---|
| 164 | Vector3 v = target.GetVertex(i);
|
---|
[223] | 165 | if (targetPlane.Distance(v) < 0)
|
---|
| 166 | targetPlane = Plane3(normal, v);
|
---|
[209] | 167 | }
|
---|
[191] | 168 |
|
---|
[209] | 169 |
|
---|
| 170 | Vector3 xBasis = CrossProd(Vector3(0,1,0), normal);
|
---|
| 171 |
|
---|
| 172 | if (Magnitude(xBasis) > 1e-6)
|
---|
| 173 | xBasis.Normalize();
|
---|
| 174 | else {
|
---|
| 175 | xBasis = CrossProd(Vector3(0,0,1), normal);
|
---|
[191] | 176 | }
|
---|
[209] | 177 |
|
---|
| 178 | Vector3 yBasis = Normalize( CrossProd(normal, xBasis) );
|
---|
[223] | 179 | // cast rays between the centers of the boxes
|
---|
| 180 | Vector3 targetRCenter = targetPlane.FindIntersection(sourceCenter,
|
---|
| 181 | targetCenter);
|
---|
[209] | 182 |
|
---|
[223] | 183 | Vector3 sourceRCenter = sourcePlane.FindIntersection(sourceCenter,
|
---|
| 184 | targetCenter);
|
---|
[209] | 185 |
|
---|
[223] | 186 |
|
---|
| 187 | Rectangle3 sourceRect;
|
---|
| 188 | Rectangle3 targetRect;
|
---|
| 189 |
|
---|
[209] | 190 |
|
---|
[223] | 191 | float scale = Magnitude(source.Size())*0.7f;
|
---|
| 192 | sourceRect.mVertices[0] = sourceRCenter - scale*xBasis - scale*yBasis;
|
---|
| 193 | sourceRect.mVertices[1] = sourceRCenter + scale*xBasis - scale*yBasis;
|
---|
| 194 | sourceRect.mVertices[2] = sourceRCenter + scale*xBasis + scale*yBasis;
|
---|
| 195 | sourceRect.mVertices[3] = sourceRCenter - scale*xBasis + scale*yBasis;
|
---|
| 196 |
|
---|
| 197 | scale = Magnitude(target.Size())*0.7f;
|
---|
| 198 | targetRect.mVertices[0] = targetRCenter - scale*xBasis - scale*yBasis;
|
---|
| 199 | targetRect.mVertices[1] = targetRCenter + scale*xBasis - scale*yBasis;
|
---|
| 200 | targetRect.mVertices[2] = targetRCenter + scale*xBasis + scale*yBasis;
|
---|
| 201 | targetRect.mVertices[3] = targetRCenter - scale*xBasis + scale*yBasis;
|
---|
| 202 |
|
---|
| 203 | AddInitialSamples(sourceRect, targetRect, samples);
|
---|
| 204 |
|
---|
| 205 | // Plane3 bottomPlane(xBasis, source.Center());
|
---|
| 206 | // Plane3 sidePlane(yBasis, source.Center());
|
---|
| 207 |
|
---|
| 208 | // // cast rays between corresponding vertices of the boxes
|
---|
| 209 | // for (i=0; i < 8; i++) {
|
---|
| 210 | // Vector3 v;
|
---|
| 211 | // bool coplanar;
|
---|
| 212 | // v = sourcePlane.FindIntersection(source.GetVertex(i),
|
---|
| 213 | // target.GetVertex(i),
|
---|
| 214 | // NULL,
|
---|
| 215 | // &coplanar);
|
---|
| 216 | // if (!coplanar) {
|
---|
| 217 | // // evaluate source and
|
---|
| 218 |
|
---|
| 219 | // }
|
---|
| 220 | // }
|
---|
| 221 |
|
---|
[209] | 222 | // AddInitialSamples(sourceRectangle, targetRectangle, samples);
|
---|
[191] | 223 | }
|
---|
| 224 |
|
---|
| 225 | void
|
---|
| 226 | MutualVisibilitySampler::AddInitialSamples(
|
---|
| 227 | const Rectangle3 &sourceRect,
|
---|
| 228 | const Rectangle3 &targetRect,
|
---|
[209] | 229 | vector<RayShaft *> &samples
|
---|
[191] | 230 | )
|
---|
| 231 | {
|
---|
| 232 |
|
---|
[209] | 233 | RayShaft *sample = new RayShaft(sourceRect,
|
---|
| 234 | targetRect);
|
---|
| 235 | samples.push_back(sample);
|
---|
| 236 | }
|
---|
[191] | 237 |
|
---|
| 238 |
|
---|
[209] | 239 | void
|
---|
| 240 | MutualVisibilitySampler::ExportSamples(vector<RayShaft *> &samples)
|
---|
| 241 | {
|
---|
| 242 | static int id = 0;
|
---|
| 243 | char filename[64];
|
---|
| 244 | if (id > 20)
|
---|
| 245 | return;
|
---|
| 246 |
|
---|
| 247 | for (int i=0; i < samples.size(); i++) {
|
---|
| 248 | sprintf(filename, "samples%04d-%02d.x3d", id++, i);
|
---|
| 249 | Exporter *exporter = Exporter::GetExporter(filename);
|
---|
[223] | 250 |
|
---|
| 251 | exporter->SetWireframe();
|
---|
| 252 | exporter->ExportBox(mSource);
|
---|
| 253 | exporter->ExportBox(mTarget);
|
---|
| 254 |
|
---|
[209] | 255 | exporter->SetFilled();
|
---|
[191] | 256 |
|
---|
[209] | 257 |
|
---|
| 258 | RayShaft *sample = samples[i];
|
---|
| 259 | Mesh *mesh = new Mesh;
|
---|
| 260 | mesh->AddRectangle(sample->mSource);
|
---|
| 261 | mesh->AddRectangle(sample->mTarget);
|
---|
| 262 | vector<Ray> rays;
|
---|
| 263 | for (int j=0; j < 4; j++) {
|
---|
| 264 | Vector3 origin, direction;
|
---|
| 265 | sample->GetRay(j, origin, direction);
|
---|
| 266 | Ray ray(origin, direction, Ray::LINE_SEGMENT);
|
---|
| 267 | rays.push_back(ray);
|
---|
[191] | 268 | }
|
---|
[209] | 269 |
|
---|
| 270 | Material m = RandomMaterial();
|
---|
| 271 | exporter->SetForcedMaterial(m);
|
---|
| 272 | MeshInstance mi(mesh);
|
---|
| 273 | exporter->ExportIntersectable(&mi);
|
---|
| 274 | exporter->ExportRays(rays, -1.0f, m.mDiffuseColor);
|
---|
| 275 | delete exporter;
|
---|
| 276 | }
|
---|
[191] | 277 | }
|
---|
| 278 |
|
---|
| 279 | int
|
---|
[223] | 280 | MutualVisibilitySampler::CastRays(RayShaft &shaft)
|
---|
| 281 | {
|
---|
| 282 | Ray ray;
|
---|
| 283 | int i;
|
---|
| 284 |
|
---|
| 285 | for (i=0; i < 4; i++) {
|
---|
| 286 | Vector3 origin, direction;
|
---|
| 287 | shaft.GetRay(i, origin, direction);
|
---|
| 288 | // determine intersections with the boxes
|
---|
| 289 | ray.Init(origin, direction, Ray::LINE_SEGMENT);
|
---|
| 290 | float stmin, stmax, ttmin, ttmax;
|
---|
| 291 | if ( mSource.GetMinMaxT(ray, &stmin, &stmax) && mTarget.GetMinMaxT(ray, &ttmin, &ttmax) ) {
|
---|
| 292 | shaft.mSamples[i].mMinT = stmax;
|
---|
| 293 | shaft.mSamples[i].mMaxT = ttmin;
|
---|
| 294 | origin = ray.Extrap(stmax);
|
---|
| 295 | direction = ray.Extrap(ttmin) - origin;
|
---|
| 296 | // reinit the ray
|
---|
| 297 | ray.Init(origin, direction, Ray::LINE_SEGMENT);
|
---|
| 298 | if (!mKdTree->CastRay(ray))
|
---|
| 299 | return VISIBLE;
|
---|
| 300 | } else {
|
---|
| 301 | shaft.mSamples[i].mMaxT = -1.0;
|
---|
| 302 | }
|
---|
| 303 | }
|
---|
| 304 | return INVISIBLE;
|
---|
| 305 | }
|
---|
| 306 |
|
---|
| 307 | int
|
---|
[191] | 308 | MutualVisibilitySampler::ComputeVisibility()
|
---|
| 309 | {
|
---|
[209] | 310 |
|
---|
[223] | 311 | vector<RayShaft *> shafts;
|
---|
| 312 | ConstructInitialSamples(mSource, mTarget, shafts);
|
---|
| 313 | ExportSamples(shafts);
|
---|
[209] | 314 |
|
---|
[223] | 315 | stack<RayShaft *> shaftStack;
|
---|
[191] | 316 |
|
---|
[209] | 317 |
|
---|
| 318 |
|
---|
[191] | 319 | Ray ray;
|
---|
[223] | 320 | // now process the shafts as long as we have something to do
|
---|
| 321 | while (!shaftStack.empty()) {
|
---|
| 322 | RayShaft *shaft = shaftStack.top();
|
---|
| 323 | shaftStack.pop();
|
---|
[191] | 324 |
|
---|
| 325 | // // cast a new ray
|
---|
| 326 | // int triangleSplitEdge = SetupExtremalRay(sample, source, ray);
|
---|
| 327 |
|
---|
[223] | 328 | if (CastRays(*shaft) == VISIBLE)
|
---|
| 329 | return VISIBLE;
|
---|
[191] | 330 |
|
---|
[223] | 331 | // // generate 2 new samples
|
---|
| 332 | // RayShaft newSamples[2];
|
---|
| 333 | // sample.Split(triangleSplitEdge, ray, newSamples[0], newSamples[1]);
|
---|
| 334 | // for (i=0; i < 2; i++) {
|
---|
| 335 | // newSamples[i].ComputeError();
|
---|
| 336 | // if (newSamples[i].mError > solidAngleThreshold) {
|
---|
| 337 | // sampleStack.push(newSamples[i]);
|
---|
| 338 | // }
|
---|
| 339 | // }
|
---|
| 340 | // }
|
---|
[191] | 341 | }
|
---|
[209] | 342 |
|
---|
[223] | 343 | for (int i=0; i < shafts.size(); i++)
|
---|
| 344 | delete shafts[i];
|
---|
[191] | 345 | return INVISIBLE;
|
---|
| 346 | }
|
---|
| 347 |
|
---|
| 348 | MutualVisibilitySampler::MutualVisibilitySampler(KdTree *kdTree,
|
---|
| 349 | AxisAlignedBox3 &source,
|
---|
| 350 | AxisAlignedBox3 &target,
|
---|
| 351 | const float solidAngleThreshold)
|
---|
| 352 | {
|
---|
| 353 | mKdTree = kdTree;
|
---|
| 354 | mSource = source;
|
---|
| 355 | mTarget = target;
|
---|
| 356 | mSolidAngleThreshold = solidAngleThreshold;
|
---|
| 357 | }
|
---|
| 358 |
|
---|
| 359 |
|
---|
| 360 | int
|
---|
| 361 | ComputeBoxVisibility(KdTree *kdTree,
|
---|
| 362 | AxisAlignedBox3 &source,
|
---|
| 363 | AxisAlignedBox3 &target,
|
---|
| 364 | const float solidAngleThreshold)
|
---|
| 365 | {
|
---|
| 366 | MutualVisibilitySampler sampler(kdTree, source, target, solidAngleThreshold);
|
---|
| 367 |
|
---|
[209] | 368 |
|
---|
[191] | 369 | int visibility = sampler.ComputeVisibility();
|
---|
| 370 |
|
---|
| 371 | return visibility;
|
---|
| 372 |
|
---|
| 373 | }
|
---|
| 374 |
|
---|