source: trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.cpp @ 534

Revision 534, 10.6 KB checked in by bittner, 18 years ago (diff)

vss preprocessor void space identification fixed - by default it is off
Line 
1#include "Ray.h"
2#include "Mesh.h"
3#include "MeshKdTree.h"
4#include "Triangle3.h"
5
6int Intersectable::sMailId = 21843194198;
7int Intersectable::sReservedMailboxes = 1;
8
9void
10Mesh::Preprocess()
11{
12        Cleanup();
13       
14        mBox.Initialize();
15  VertexContainer::const_iterator vi = mVertices.begin();
16  for (; vi != mVertices.end(); vi++) {
17    mBox.Include(*vi);
18  }
19 
20  /** true if it is a watertight convex mesh */
21  mIsConvex = false;
22 
23  if (mFaces.size() > MeshKdTree::mTermMinCost) {
24    mKdTree = new MeshKdTree(this);
25    MeshKdLeaf *root = (MeshKdLeaf *)mKdTree->GetRoot();
26    for (int i = 0; i < mFaces.size(); i++)
27      root->mFaces.push_back(i);
28    cout<<"KD";
29    mKdTree->Construct();
30
31    if (mKdTree->GetRoot()->IsLeaf()) {
32      cout<<"d";
33      delete mKdTree;
34                        mKdTree = NULL;
35    }
36  }
37}
38
39AxisAlignedBox3
40Mesh::GetFaceBox(const int faceIndex)
41{
42  Face *face = mFaces[faceIndex];
43  AxisAlignedBox3 box;
44  box.SetMin( mVertices[face->mVertexIndices[0]] );
45  box.SetMax(box.Min());
46  for (int i = 1; i < face->mVertexIndices.size(); i++) {
47    box.Include(mVertices[face->mVertexIndices[i]]);
48  }
49  return box;
50}
51
52int
53Mesh::CastRayToFace(
54                                                                                const int faceIndex,
55                                                                                Ray &ray,
56                                                                                float &nearestT,
57                                                                                int &nearestFace,
58                                                                                Intersectable *instance
59                                                                                )
60{
61  float t;
62  int hit = 0;
63  if (RayFaceIntersection(faceIndex, ray, t, nearestT) == Ray::INTERSECTION) {
64    switch (ray.GetType()) {
65    case Ray::GLOBAL_RAY:
66      ray.intersections.push_back(Ray::Intersection(t, instance, faceIndex));
67      hit++;
68      break;
69    case Ray::LOCAL_RAY:
70      nearestT = t;
71      nearestFace = faceIndex;
72      hit++;
73      break;
74    case Ray::LINE_SEGMENT:
75      if (t <= 1.0f) {
76                                ray.intersections.push_back(Ray::Intersection(t, instance, faceIndex));
77                                hit++;
78      }
79      break;
80    }
81  }
82  return hit;
83}
84
85int
86Mesh::CastRay(
87                          Ray &ray,
88                          MeshInstance *instance
89                          )
90{
91  if (mKdTree) {
92    return mKdTree->CastRay(ray, instance);
93  }
94 
95  int faceIndex = 0;
96  int hits = 0;
97  float nearestT = MAX_FLOAT;
98  int nearestFace = -1;
99 
100  if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
101    nearestT = ray.intersections[0].mT;
102
103       
104  for ( ;
105                faceIndex < mFaces.size();
106                faceIndex++) {
107    hits += CastRayToFace(faceIndex, ray, nearestT, nearestFace, instance);
108    if (mIsConvex && nearestFace != -1)
109      break;
110  }
111 
112  if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
113    if (ray.intersections.size())
114      ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
115    else
116      ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
117  }
118 
119  return hits;
120}
121
122int
123Mesh::CastRayToSelectedFaces(
124                                                         Ray &ray,
125                                                         const vector<int> &faces,
126                                                         Intersectable *instance
127                                                         )
128{
129  vector<int>::const_iterator fi;
130  int faceIndex = 0;
131  int hits = 0;
132  float nearestT = MAX_FLOAT;
133  int nearestFace = -1;
134
135  if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
136    nearestT = ray.intersections[0].mT;
137
138  for ( fi = faces.begin();
139                                fi != faces.end();
140                                fi++) {
141    hits += CastRayToFace(*fi, ray, nearestT, nearestFace, instance);
142    if (mIsConvex && nearestFace != -1)
143      break;
144  }
145 
146  if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
147    if (ray.intersections.size())
148      ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
149    else
150      ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
151  }
152 
153  return hits;
154}
155
156
157// int_lineseg returns 1 if the given line segment intersects a 2D
158// ray travelling in the positive X direction.  This is used in the
159// Jordan curve computation for polygon intersection.
160inline int
161int_lineseg(float px,
162                        float py,
163                        float u1,
164                        float v1,
165                        float u2,
166                        float v2)
167{
168  float ydiff;
169
170  u1 -= px; u2 -= px;     // translate line
171  v1 -= py; v2 -= py;
172
173  if ((v1 > 0 && v2 > 0) ||
174      (v1 < 0 && v2 < 0) ||
175      (u1 < 0 && u2 < 0))
176    return 0;
177
178  if (u1 > 0 && u2 > 0)
179    return 1;
180
181  ydiff = v2 - v1;
182  if (fabs(ydiff) < Limits::Small) {      // denominator near 0
183    if (((fabs(v1) > Limits::Small) ||
184                 (u1 > 0) || (u2 > 0)))
185      return 0;
186    return 1;
187  }
188 
189  double t = -v1 / ydiff;                 // Compute parameter
190
191  double thresh;
192  if (ydiff < 0.0f)
193        thresh = -1e20;
194  else
195        thresh = 1e20;
196
197 
198  return (u1 + t * (u2 - u1)) > thresh; //-Limits::Small;
199}
200
201
202
203// intersection with the polygonal face of the mesh
204int
205Mesh::RayFaceIntersection(const int faceIndex,
206                                                  const Ray &ray,
207                                                  float &t,
208                                                  const float nearestT
209                                                  )
210{
211  Face *face  = mFaces[faceIndex];
212
213  Plane3 plane = GetFacePlane(faceIndex);
214  float dot = DotProd(plane.mNormal, ray.GetDir());
215 
216  // Watch for near-zero denominator
217  // ONLY single sided polygons!!!!!
218  if (ray.mFlags & Ray::CULL_BACKFACES) {
219        if (dot > -Limits::Small)
220          //  if (fabs(dot) < Limits::Small)
221          return Ray::NO_INTERSECTION;
222  } else {
223        if (fabs(dot) < Limits::Small)
224          return Ray::NO_INTERSECTION;
225  }
226 
227  t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
228 
229  if (t <= Limits::Small)
230    return Ray::INTERSECTION_OUT_OF_LIMITS;
231 
232  if (t >= nearestT) {
233    return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
234  }
235 
236  int count = 0;
237  float u, v, u1, v1, u2, v2;
238  int i;
239
240  int paxis = plane.mNormal.DrivingAxis();
241
242  // Project the intersection point onto the coordinate plane
243  // specified by which.
244  ray.Extrap(t).ExtractVerts(&u, &v, paxis);
245
246
247  int size = (int)face->mVertexIndices.size();
248
249  mVertices[face->mVertexIndices[size - 1]].
250    ExtractVerts(&u1, &v1, paxis );
251 
252  if (0 && size <= 4) {
253    // assume a convex face
254    for (i = 0; i < size; i++) {
255      mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
256      // line u1, v1, u2, v2
257      if ((v1 - v2)*(u - u1) + (u2 - u1)*(v - v1) > 0)
258                return Ray::NO_INTERSECTION;
259      u1 = u2;
260      v1 = v2;
261    }
262   
263    return Ray::INTERSECTION;
264  }
265 
266  // We're stuck with the Jordan curve computation.  Count number
267  // of intersections between the line segments the polygon comprises
268  // with a ray originating at the point of intersection and
269  // travelling in the positive X direction.
270  for (i = 0; i < size; i++) {
271    mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
272    count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
273    u1 = u2;
274    v1 = v2;
275  }
276
277  // We hit polygon if number of intersections is odd.
278  return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
279}
280
281int
282Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
283{
284  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
285 
286  // assume the face is convex and generate a convex combination
287  //
288  Face *face = mFaces[faceIndex];
289  point = Vector3(0,0,0);
290  float sum = 0.0f;
291  for (int i = 0; i < face->mVertexIndices.size(); i++) {
292    float r = RandomValue(0,1);
293    sum += r;
294    point += mVertices[face->mVertexIndices[i]]*r;
295  }
296  point *= 1.0f/sum;
297       
298        normal = GetFacePlane(faceIndex).mNormal;
299
300        return faceIndex;
301}
302
303int
304Mesh::GetRandomVisibleSurfacePoint(Vector3 &point,
305                                                                                                                                         Vector3 &normal,
306                                                                                                                                         const Vector3 &viewpoint,
307                                                                                                                                         const int maxTries
308                                                                                                                                         )
309{
310  Plane3 plane;
311  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
312        int tries;
313  for (tries = 0; tries < maxTries; tries++) {
314    Face *face = mFaces[faceIndex];
315    plane = GetFacePlane(faceIndex);
316   
317    if (plane.Side(viewpoint) > 0) {
318      point = Vector3(0,0,0);
319      float sum = 0.0f;
320      // pickup a point inside this triangle
321      for (int i = 0; i < face->mVertexIndices.size(); i++) {
322                                float r = RandomValue(0,1);
323                                sum += r;
324                                point += mVertices[face->mVertexIndices[i]]*r;
325      }
326      point *= 1.0f/sum;
327      break;
328    }
329  }
330 
331  normal = plane.mNormal;
332  return (tries < maxTries) ? faceIndex + 1 : 0;
333}
334
335
336int
337MeshInstance::CastRay(
338                                          Ray &ray
339                                          )
340{
341  int res = mMesh->CastRay(ray, this);
342  return res;
343}
344
345int
346MeshInstance::CastRay(
347                                          Ray &ray,
348                                          const vector<int> &faces
349                                          )
350{
351  return mMesh->CastRayToSelectedFaces(ray, faces, this);
352}
353
354
355
356int
357MeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
358{
359  return mMesh->GetRandomSurfacePoint(point, normal);
360}
361
362int
363MeshInstance::GetRandomVisibleSurfacePoint(Vector3 &point,
364                                                                                                                                                                         Vector3 &normal,
365                                                                                                                                                                         const Vector3 &viewpoint,
366                                                                                                                                                                         const int maxTries
367                                                                                                                                                                         )
368{
369        return mMesh->GetRandomVisibleSurfacePoint(point, normal, viewpoint, maxTries);
370}
371
372
373int
374TransformedMeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
375{
376  int index = mMesh->GetRandomSurfacePoint(point, normal);
377  point = mWorldTransform*point;
378  normal = TransformNormal(mWorldTransform, normal);
379  return index;
380}
381
382Plane3
383Mesh::GetFacePlane(const int faceIndex)
384{
385  Face *face = mFaces[faceIndex];
386        return Plane3(mVertices[face->mVertexIndices[0]],
387                                                                mVertices[face->mVertexIndices[1]],
388                                                                mVertices[face->mVertexIndices[2]]);
389}
390
391bool
392Mesh::ValidateFace(const int i)
393{
394        Face *face = mFaces[i];
395
396        Plane3 plane = Plane3(mVertices[face->mVertexIndices[0]],
397                                                                                                mVertices[face->mVertexIndices[1]],
398                                                                                                mVertices[face->mVertexIndices[2]]);
399       
400        if (!eq(Magnitude(plane.mNormal), 1.0f))
401                return false;
402
403        return true;
404}
405
406void
407Mesh::Cleanup()
408{
409        int toRemove = 0;
410        FaceContainer newFaces;
411        for (int i=0; i < mFaces.size(); i++)
412                if (ValidateFace(i)) {
413                        newFaces.push_back(mFaces[i]);
414                } else {
415                        cout<<"d";
416                        delete mFaces[i];
417                        toRemove++;
418                }
419       
420        if (toRemove) {
421                mFaces = newFaces;
422        }
423       
424        // cleanup vertices??
425}
426
427int
428TransformedMeshInstance::CastRay(
429                                                                 Ray &ray
430                                                                 )
431{
432  ray.ApplyTransform(Invert(mWorldTransform));
433  int res = mMesh->CastRay(ray, this);
434  ray.ApplyTransform(mWorldTransform);
435 
436  return res;
437}
438
439
440void
441Mesh::AddTriangle(const Triangle3 &triangle)
442{
443  int index = (int)mVertices.size();
444
445  for (int i=0; i < 3; i++) {
446    mVertices.push_back(triangle.mVertices[i]);
447  }
448 
449  AddFace(new Face(index + 0, index + 1, index + 2) );
450}
451
452void
453Mesh::AddRectangle(const Rectangle3 &rect)
454{
455  int index = (int)mVertices.size();
456
457  for (int i=0; i < 4; i++) {
458    mVertices.push_back(rect.mVertices[i]);
459  }
460 
461  AddFace(new Face(index + 0, index + 1, index + 2, index + 3) );
462}
Note: See TracBrowser for help on using the repository browser.