source: GTP/trunk/Lib/Vis/Preprocessing/src/Mesh.cpp @ 1020

Revision 1020, 17.0 KB checked in by mattausch, 18 years ago (diff)

worked on view-object space partition
fixed some loading bugs
fixeds some exporting bugs using line segments
enabling other methods for view space sampling in ViewCellsManager? OBJECT_DIRECTION_BASED_DISTRIBUTION)
added class interface for a sampling strategy

Line 
1#include "Ray.h"
2#include "Mesh.h"
3#include "MeshKdTree.h"
4#include "Triangle3.h"
5#include "ResourceManager.h"
6
7namespace GtpVisibilityPreprocessor {
8
9bool MeshDebug = false;
10
11int Intersectable::sMailId = 21843194198;
12int Intersectable::sReservedMailboxes = 1;
13
14struct SortableVertex {
15
16  Vector3 vertex;
17
18  int originalId;
19  int newId;
20  int finalPos;
21
22  SortableVertex() {}
23
24  SortableVertex(const Vector3 &v,
25                                 const int id):
26        vertex(v),
27        originalId(id),
28        newId(id)
29  {}
30 
31  friend bool operator<(const SortableVertex &a,
32                                                const SortableVertex &b)
33  {
34        if (a.vertex.x < b.vertex.x)
35          return true;
36        else
37          if (a.vertex.x > b.vertex.x)
38                return false;
39       
40        if (a.vertex.y < b.vertex.y)
41          return true;
42        else
43          if (a.vertex.y > b.vertex.y)
44                return false;
45       
46        if (a.vertex.z < b.vertex.z)
47          return true;
48        else
49          //      if (a.z > b.z)
50          return false;
51       
52        //      return false;
53  }
54
55};
56
57
58void
59Mesh::ComputeBoundingBox()
60{
61
62  mBox.Initialize();
63  VertexContainer::const_iterator vi = mVertices.begin();
64  for (; vi != mVertices.end(); vi++) {
65    mBox.Include(*vi);
66  }
67//mBox.Enlarge(1e-4f);
68}
69
70void
71Mesh::Preprocess()
72{
73        Cleanup();
74   
75        ComputeBoundingBox();
76   
77        /** true if it is a watertight convex mesh
78        */
79        mIsConvex = false;
80
81        if (mFaces.size() > MeshKdTree::mTermMinCost)
82        {
83                mKdTree = new MeshKdTree(this);
84                MeshKdLeaf *root = (MeshKdLeaf *)mKdTree->GetRoot();
85               
86                for (int i = 0; i < mFaces.size(); i++)
87                        root->mFaces.push_back(i);
88               
89                cout<<"KD";
90                mKdTree->Construct();
91
92                if (mKdTree->GetRoot()->IsLeaf())
93                {
94                        cout<<"d";
95                        delete mKdTree;
96                        mKdTree = NULL;
97                }
98        }
99}
100
101
102void
103Mesh::IndexVertices()
104{
105  int i;
106  // check whether the vertices can be simplfied and reindexed
107  vector<SortableVertex> svertices(mVertices.size());
108
109  for (i=0; i < mVertices.size(); i++)
110        svertices[i] = SortableVertex(mVertices[i], i);
111
112  sort(svertices.begin(), svertices.end());
113
114  for (i=0; i < svertices.size() - 1; i++)
115        if (svertices[i].vertex == svertices[i+1].vertex)
116          svertices[i+1].newId = svertices[i].newId;
117
118  // remove the same vertices
119  int k = 0;
120  mVertices[0] = svertices[0].vertex;
121  svertices[0].finalPos = 0;
122 
123  for (i=1; i < svertices.size(); i++) {
124        if (svertices[i].newId != svertices[i-1].newId)
125          k++;
126       
127        mVertices[k] = svertices[i].vertex;
128        svertices[i].finalPos = k;
129  }
130
131  mVertices.resize(k + 1);
132 
133  vector<int> remapBuffer(svertices.size());
134  for (i = 0; i < svertices.size(); i++)
135        remapBuffer[svertices[i].originalId] = svertices[i].finalPos;
136 
137  // remap all faces
138 
139  for (int faceIndex = 0; faceIndex < mFaces.size(); faceIndex++) {
140        Face *face = mFaces[faceIndex];
141        for (int i = 0; i < face->mVertexIndices.size(); i++) {
142          face->mVertexIndices[i] = remapBuffer[face->mVertexIndices[i]];
143        }
144  }
145}
146
147AxisAlignedBox3
148Mesh::GetFaceBox(const int faceIndex)
149{
150  Face *face = mFaces[faceIndex];
151  AxisAlignedBox3 box;
152  box.SetMin( mVertices[face->mVertexIndices[0]] );
153  box.SetMax(box.Min());
154  for (int i = 1; i < face->mVertexIndices.size(); i++) {
155    box.Include(mVertices[face->mVertexIndices[i]]);
156  }
157  return box;
158}
159
160int
161Mesh::CastRayToFace(
162                                        const int faceIndex,
163                                        Ray &ray,
164                                        float &nearestT,
165                                        int &nearestFace,
166                                        Intersectable *instance
167                                        )
168{
169  float t;
170  int hit = 0;
171  if (RayFaceIntersection(faceIndex, ray, t, nearestT) == Ray::INTERSECTION) {
172    switch (ray.GetType()) {
173    case Ray::GLOBAL_RAY:
174      ray.intersections.push_back(Ray::Intersection(t, instance, faceIndex));
175      hit++;
176      break;
177    case Ray::LOCAL_RAY:
178      nearestT = t;
179      nearestFace = faceIndex;
180      hit++;
181      break;
182    case Ray::LINE_SEGMENT:
183      if (t <= 1.0f) {
184                ray.intersections.push_back(Ray::Intersection(t, instance, faceIndex));
185                hit++;
186      }
187      break;
188    }
189  }
190  return hit;
191}
192
193int
194Mesh::CastRay(
195                          Ray &ray,
196                          MeshInstance *instance
197                          )
198{
199  if (mKdTree) {
200    return mKdTree->CastRay(ray, instance);
201  }
202 
203  int faceIndex = 0;
204  int hits = 0;
205  float nearestT = MAX_FLOAT;
206  int nearestFace = -1;
207 
208  if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
209    nearestT = ray.intersections[0].mT;
210
211       
212  for ( ;
213                faceIndex < mFaces.size();
214                faceIndex++) {
215    hits += CastRayToFace(faceIndex, ray, nearestT, nearestFace, instance);
216    if (mIsConvex && nearestFace != -1)
217      break;
218  }
219 
220  if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
221    if (ray.intersections.size())
222      ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
223    else
224      ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
225  }
226 
227  return hits;
228}
229
230int
231Mesh::CastRayToSelectedFaces(
232                                                         Ray &ray,
233                                                         const vector<int> &faces,
234                                                         Intersectable *instance
235                                                         )
236{
237  vector<int>::const_iterator fi;
238  int faceIndex = 0;
239  int hits = 0;
240  float nearestT = MAX_FLOAT;
241  int nearestFace = -1;
242
243  if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
244    nearestT = ray.intersections[0].mT;
245
246  for ( fi = faces.begin();
247                fi != faces.end();
248                fi++) {
249    hits += CastRayToFace(*fi, ray, nearestT, nearestFace, instance);
250    if (mIsConvex && nearestFace != -1)
251      break;
252  }
253 
254  if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
255    if (ray.intersections.size())
256      ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
257    else
258      ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
259  }
260 
261  return hits;
262}
263
264
265// int_lineseg returns 1 if the given line segment intersects a 2D
266// ray travelling in the positive X direction.  This is used in the
267// Jordan curve computation for polygon intersection.
268inline int
269int_lineseg(float px,
270                        float py,
271                        float u1,
272                        float v1,
273                        float u2,
274                        float v2)
275{
276  float ydiff;
277
278  u1 -= px; u2 -= px;     // translate line
279  v1 -= py; v2 -= py;
280
281  if ((v1 > 0 && v2 > 0) ||
282      (v1 < 0 && v2 < 0) ||
283      (u1 < 0 && u2 < 0))
284    return 0;
285
286  if (u1 > 0 && u2 > 0)
287    return 1;
288
289  ydiff = v2 - v1;
290  if (fabs(ydiff) < Limits::Small) {      // denominator near 0
291    if (((fabs(v1) > Limits::Small) ||
292                 (u1 > 0) || (u2 > 0)))
293      return 0;
294    return 1;
295  }
296 
297  double t = -v1 / ydiff;                 // Compute parameter
298
299  double thresh;
300
301  if (ydiff < 0.0f)
302        thresh = -1e-20;
303  else
304        thresh = 1e-20;
305
306 
307  return (u1 + t * (u2 - u1)) > thresh; //-Limits::Small;
308}
309
310
311
312// intersection with the polygonal face of the mesh
313int
314Mesh::RayFaceIntersection(const int faceIndex,
315                                                  const Ray &ray,
316                                                  float &t,
317                                                  const float nearestT
318                                                  )
319{
320  Face *face  = mFaces[faceIndex];
321
322  Plane3 plane = GetFacePlane(faceIndex);
323  float dot = DotProd(plane.mNormal, ray.GetDir());
324
325  if (MeshDebug) {
326        cout<<endl<<endl;
327        cout<<"normal="<<plane.mNormal<<endl;
328        cout<<"dot="<<dot<<endl;
329  }
330 
331       
332  // Watch for near-zero denominator
333  // ONLY single sided polygons!!!!!
334  if (ray.mFlags & Ray::CULL_BACKFACES) {
335        if (dot > -Limits::Small)
336          //  if (fabs(dot) < Limits::Small)
337          return Ray::NO_INTERSECTION;
338  } else {
339        if (fabs(dot) < Limits::Small)
340          return Ray::NO_INTERSECTION;
341  }
342 
343  t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
344
345  if (MeshDebug)
346        cout<<"t="<<t<<endl;
347
348  if (t <= Limits::Small)
349    return Ray::INTERSECTION_OUT_OF_LIMITS;
350 
351  if (t >= nearestT) {
352    return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
353  }
354 
355  int count = 0;
356  float u, v, u1, v1, u2, v2;
357  int i;
358
359  int paxis = plane.mNormal.DrivingAxis();
360
361 
362  // Project the intersection point onto the coordinate plane
363  // specified by which.
364  ray.Extrap(t).ExtractVerts(&u, &v, paxis);
365
366
367  int size = (int)face->mVertexIndices.size();
368
369  if (MeshDebug)
370        cout<<"size="<<size<<endl;
371 
372  mVertices[face->mVertexIndices[size - 1]].
373    ExtractVerts(&u1, &v1, paxis );
374 
375  //$$JB changed 12.4.2006 from 0 ^^
376  if (0 && size <= 4) {
377    // assume a convex face
378    for (i = 0; i < size; i++) {
379      mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
380      // line u1, v1, u2, v2
381      if ((v1 - v2)*(u - u1) + (u2 - u1)*(v - v1) > 0) {
382                if (MeshDebug)
383                  cout<<"exit on "<<i<<endl;
384                return Ray::NO_INTERSECTION;
385          }
386      u1 = u2;
387      v1 = v2;
388    }
389   
390    return Ray::INTERSECTION;
391  }
392 
393  // We're stuck with the Jordan curve computation.  Count number
394  // of intersections between the line segments the polygon comprises
395  // with a ray originating at the point of intersection and
396  // travelling in the positive X direction.
397  for (i = 0; i < size; i++) {
398    mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
399    count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
400    u1 = u2;
401    v1 = v2;
402  }
403
404  if (MeshDebug)
405        cout<<"count="<<count<<endl;
406
407  // We hit polygon if number of intersections is odd.
408  return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
409}
410
411int
412Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
413{
414  const int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
415 
416  // assume the face is convex and generate a convex combination
417  //
418  Face *face = mFaces[faceIndex];
419 
420  point = Vector3(0,0,0);
421  float sum = 0.0f;
422 
423  for (int i = 0; i < face->mVertexIndices.size(); i++) {
424    float r = RandomValue(0,1);
425    sum += r;
426    point += mVertices[face->mVertexIndices[i]]*r;
427  }
428  point *= 1.0f/sum;
429       
430        normal = GetFacePlane(faceIndex).mNormal;
431
432        return faceIndex;
433}
434
435int
436Mesh::GetRandomVisibleSurfacePoint(Vector3 &point,
437                                                                   Vector3 &normal,
438                                                                   const Vector3 &viewpoint,
439                                                                   const int maxTries)
440{
441  Plane3 plane;
442  int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));
443        int tries;
444  for (tries = 0; tries < maxTries; tries++) {
445    Face *face = mFaces[faceIndex];
446    plane = GetFacePlane(faceIndex);
447   
448    if (plane.Side(viewpoint) > 0) {
449      point = Vector3(0,0,0);
450      float sum = 0.0f;
451      // pickup a point inside this triangle
452      for (int i = 0; i < face->mVertexIndices.size(); i++) {
453                                float r = RandomValue(0,1);
454                                sum += r;
455                                point += mVertices[face->mVertexIndices[i]]*r;
456      }
457      point *= 1.0f/sum;
458      break;
459    }
460  }
461 
462  normal = plane.mNormal;
463  return (tries < maxTries) ? faceIndex + 1 : 0;
464}
465
466
467Plane3
468Mesh::GetFacePlane(const int faceIndex)
469{
470  Face *face = mFaces[faceIndex];
471        return Plane3(mVertices[face->mVertexIndices[0]],
472                                                                mVertices[face->mVertexIndices[1]],
473                                                                mVertices[face->mVertexIndices[2]]);
474}
475
476bool
477Mesh::ValidateFace(const int i)
478{
479        Face *face = mFaces[i];
480
481        Plane3 plane = Plane3(mVertices[face->mVertexIndices[0]],
482                                                                                                mVertices[face->mVertexIndices[1]],
483                                                                                                mVertices[face->mVertexIndices[2]]);
484       
485        if (!eq(Magnitude(plane.mNormal), 1.0f))
486                return false;
487
488        return true;
489}
490
491void
492Mesh::Cleanup()
493{
494        int toRemove = 0;
495        FaceContainer newFaces;
496        for (int i=0; i < mFaces.size(); i++)
497                if (ValidateFace(i)) {
498                        newFaces.push_back(mFaces[i]);
499                } else {
500                        cout<<"d";
501                        delete mFaces[i];
502                        toRemove++;
503                }
504       
505        if (toRemove) {
506                mFaces = newFaces;
507        }
508       
509        // cleanup vertices??
510}
511
512
513void
514Mesh::AddTriangle(const Triangle3 &triangle)
515{
516  int index = (int)mVertices.size();
517
518  for (int i=0; i < 3; i++) {
519    mVertices.push_back(triangle.mVertices[i]);
520  }
521 
522  AddFace(new Face(index + 0, index + 1, index + 2) );
523}
524
525void
526Mesh::AddRectangle(const Rectangle3 &rect)
527{
528  int index = (int)mVertices.size();
529
530  for (int i=0; i < 4; i++) {
531    mVertices.push_back(rect.mVertices[i]);
532  }
533 
534  AddFace(new Face(index + 0, index + 1, index + 2, index + 3) );
535}
536
537void
538Mesh::AssignRandomMaterial()
539
540        mMaterial = MaterialManager::GetSingleton()->CreateResource();
541 
542        Material randMat = RandomMaterial();
543
544        mMaterial->mDiffuseColor = randMat.mDiffuseColor;
545        mMaterial->mSpecularColor = randMat.mSpecularColor;
546        mMaterial->mAmbientColor = randMat.mAmbientColor;
547}
548
549
550Mesh *CreateMeshFromBox(const AxisAlignedBox3 &box)
551{
552        Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
553
554        // add 8 vertices of the box
555        const int index = (int)mesh->mVertices.size();
556       
557        for (int i=0; i < 8; ++ i)
558        {
559        Vector3 v;
560                box.GetVertex(i, v);
561                mesh->mVertices.push_back(v);
562        }
563
564        mesh->AddFace(new Face(index + 0, index + 1, index + 3, index + 2) );
565        mesh->AddFace(new Face(index + 0, index + 2, index + 6, index + 4) );
566        mesh->AddFace(new Face(index + 4, index + 6, index + 7, index + 5) );
567 
568        mesh->AddFace(new Face(index + 3, index + 1, index + 5, index + 7) );
569        mesh->AddFace(new Face(index + 0, index + 4, index + 5, index + 1) );
570        mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) );
571 
572        return mesh;
573}
574
575
576Mesh::Mesh(const int id, const int vertices, const int faces):
577mFaces(),
578mMaterial(NULL),
579mKdTree(NULL),
580mVertices(),
581mIsConvex(false),
582mIsWatertight(false),
583mId(id)
584{
585    mVertices.reserve(vertices);
586    mFaces.reserve(faces);
587}
588
589
590Mesh::Mesh(const int id):
591mId(id), mVertices(), mFaces(), mMaterial(NULL), mKdTree(NULL)
592{}
593
594
595// apply transformation to each vertex
596void Mesh::ApplyTransformation(const Matrix4x4 &m)
597{
598        VertexContainer::iterator it, it_end = mVertices.end();
599
600        for (it = mVertices.begin(); it != it_end; ++ it)
601        {
602                (*it) = m * (*it);       
603        }
604}
605
606
607Mesh::Mesh(const Mesh &rhs):
608mKdTree(NULL)
609{
610        mVertices = rhs.mVertices;
611        mFaces.reserve(rhs.mFaces.size());
612        mId = rhs.mId;
613        mMaterial = rhs.mMaterial;
614       
615        FaceContainer::const_iterator it, it_end = rhs.mFaces.end();
616
617        for (it = rhs.mFaces.begin(); it != it_end; ++ it)
618        {
619                Face *face = *it;
620                mFaces.push_back(new Face(*face));
621        }
622}
623
624
625Mesh& Mesh::operator=(const Mesh& m)
626{
627    if (this == &m)
628                return *this;
629 
630        CLEAR_CONTAINER(mFaces);
631
632        mVertices = m.mVertices;
633        mFaces.reserve(m.mFaces.size());
634        mMaterial = m.mMaterial;
635        // note: we don't copy id on purpose
636        //mId = m.mId;
637       
638        FaceContainer::const_iterator it, it_end = m.mFaces.end();
639
640        for (it = m.mFaces.begin(); it != it_end; ++ it)
641        {
642                Face *face = *it;
643                mFaces.push_back(new Face(*face));
644        }
645
646        return *this;
647}
648
649
650Mesh::~Mesh()
651{
652        for (int i=0; i < mFaces.size(); ++ i)
653                delete mFaces[i];
654
655        DEL_PTR(mKdTree);
656}
657 
658
659void Mesh::Clear()
660{
661        mVertices.clear();
662        mFaces.clear();
663
664        DEL_PTR(mKdTree);
665}
666
667/********************************************************/
668/*                      MeshInstance implementation             */
669/********************************************************/
670
671int
672MeshInstance::CastRay(
673                                          Ray &ray
674                                          )
675{
676  int res = mMesh->CastRay(ray, this);
677  return res;
678}
679
680int
681MeshInstance::CastRay(
682                                          Ray &ray,
683                                          const vector<int> &faces
684                                          )
685{
686  return mMesh->CastRayToSelectedFaces(ray, faces, this);
687}
688
689
690
691int
692MeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
693{
694  return mMesh->GetRandomSurfacePoint(point, normal);
695}
696
697int
698MeshInstance::GetRandomVisibleSurfacePoint(Vector3 &point,
699                                                                                   Vector3 &normal,
700                                                                                   const Vector3 &viewpoint,
701                                                                                   const int maxTries)
702{
703        return mMesh->GetRandomVisibleSurfacePoint(point, normal, viewpoint, maxTries);
704}
705
706
707void MeshInstance::SetMaterial(Material *mat)
708{
709        mMaterial = mat;
710}
711
712Material *MeshInstance::GetMaterial() const
713{
714        return mMaterial;
715}
716
717
718/*************************************************************/
719/*           TransformedMeshInstance implementation          */
720/*************************************************************/
721
722TransformedMeshInstance::TransformedMeshInstance(Mesh *mesh):
723MeshInstance(mesh)
724{
725    mWorldTransform = IdentityMatrix();
726}
727
728
729int TransformedMeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
730{
731  int index = mMesh->GetRandomSurfacePoint(point, normal);
732  point = mWorldTransform*point;
733  normal = TransformNormal(mWorldTransform, normal);
734  return index;
735}
736
737
738int TransformedMeshInstance::CastRay(Ray &ray)
739{
740        ray.ApplyTransform(Invert(mWorldTransform));
741       
742        const int res = mMesh->CastRay(ray, this);
743        ray.ApplyTransform(mWorldTransform);
744
745    return res;
746}
747
748int TransformedMeshInstance::CastRay(Ray &ray, const vector<int> &faces)
749{
750        ray.ApplyTransform(Invert(mWorldTransform));
751
752        const int res = mMesh->CastRayToSelectedFaces(ray, faces, this);
753        ray.ApplyTransform(mWorldTransform);
754
755         return res;
756}
757
758
759void TransformedMeshInstance::ApplyWorldTransform(const Matrix4x4 &m)
760{
761        mWorldTransform = m * mWorldTransform;
762}
763
764
765void TransformedMeshInstance::LoadWorldTransform(const Matrix4x4 &m)
766{
767        mWorldTransform = m;
768}
769
770
771void TransformedMeshInstance::GetWorldTransform(Matrix4x4 &m) const
772{
773        m = mWorldTransform;
774}
775
776
777AxisAlignedBox3 TransformedMeshInstance::GetBox() const
778{
779    return Transform(mMesh->mBox, mWorldTransform);
780}
781
782
783void TransformedMeshInstance::GetTransformedMesh(Mesh &transformedMesh) const
784{
785        // copy mesh
786        transformedMesh = *mMesh;
787        transformedMesh.ApplyTransformation(mWorldTransform);
788}
789
790}
Note: See TracBrowser for help on using the repository browser.