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

Revision 1344, 17.6 KB checked in by mattausch, 18 years ago (diff)

worked on triangle processing. logical units will be created by grouping objects
using their visibility definitions.

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