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

Revision 340, 9.2 KB checked in by bittner, 19 years ago (diff)

mesh cleanup added

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