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

Revision 382, 10.4 KB checked in by bittner, 19 years ago (diff)

vsspreprocessor update

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 t;
169  float ydiff;
170
171  u1 -= px; u2 -= px;     // translate line
172  v1 -= py; v2 -= py;
173
174  if ((v1 > 0 && v2 > 0) ||
175      (v1 < 0 && v2 < 0) ||
176      (u1 < 0 && u2 < 0))
177    return 0;
178
179  if (u1 > 0 && u2 > 0)
180    return 1;
181
182  ydiff = v2 - v1;
183  if (fabs(ydiff) < Limits::Small) {      // denominator near 0
184    if (((fabs(v1) > Limits::Small) ||
185                                 (u1 > 0) || (u2 > 0)))
186      return 0;
187    return 1;
188  }
189
190  t = -v1 / ydiff;                // Compute parameter
191
192  return (u1 + t * (u2 - u1)) > 0;
193}
194
195
196
197// intersection with the polygonal face of the mesh
198int
199Mesh::RayFaceIntersection(const int faceIndex,
200                                                                                                        const Ray &ray,
201                                                                                                        float &t,
202                                                                                                        const float nearestT
203                                                                                                        )
204{
205  Face *face  = mFaces[faceIndex];
206
207  Plane3 plane = GetFacePlane(faceIndex);
208  float dot = DotProd(plane.mNormal, ray.GetDir());
209 
210  // Watch for near-zero denominator
211  // ONLY single sided polygons!!!!!
212  if (dot > -Limits::Small)
213    //  if (fabs(dot) < Limits::Small)
214    return Ray::NO_INTERSECTION;
215 
216  t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
217 
218  if (t <= Limits::Small)
219    return Ray::INTERSECTION_OUT_OF_LIMITS;
220 
221  if (t >= nearestT) {
222    return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
223  }
224 
225  int count = 0;
226  float u, v, u1, v1, u2, v2;
227  int i;
228
229  int paxis = plane.mNormal.DrivingAxis();
230
231  // Project the intersection point onto the coordinate plane
232  // specified by which.
233  ray.Extrap(t).ExtractVerts(&u, &v, paxis);
234
235
236  int size = face->mVertexIndices.size();
237
238  mVertices[face->mVertexIndices[size - 1]].
239    ExtractVerts(&u1, &v1, paxis );
240 
241  if (0 && size <= 4) {
242    // assume a convex face
243    for (i = 0; i < size; i++) {
244      mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
245      // line u1, v1, u2, v2
246      if ((v2 - v1)*(u1 - u) > (u2 - u1)*(v1 - v))
247                                return Ray::NO_INTERSECTION;
248      u1 = u2;
249      v1 = v2;
250    }
251   
252    return Ray::INTERSECTION;
253  }
254 
255  // We're stuck with the Jordan curve computation.  Count number
256  // of intersections between the line segments the polygon comprises
257  // with a ray originating at the point of intersection and
258  // travelling in the positive X direction.
259  for (i = 0; i < size; i++) {
260    mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
261    count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
262    u1 = u2;
263    v1 = v2;
264  }
265
266  // We hit polygon if number of intersections is odd.
267  return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
268}
269
270int
271Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
272{
273  int faceIndex = RandomValue(0, mFaces.size()-1);
274 
275  // assume the face is convex and generate a convex combination
276  //
277  Face *face = mFaces[faceIndex];
278  point = Vector3(0,0,0);
279  float sum = 0.0f;
280  for (int i = 0; i < face->mVertexIndices.size(); i++) {
281    float r = RandomValue(0,1);
282    sum += r;
283    point += mVertices[face->mVertexIndices[i]]*r;
284  }
285  point *= 1.0f/sum;
286       
287        normal = GetFacePlane(faceIndex).mNormal;
288
289        return faceIndex;
290}
291
292int
293Mesh::GetRandomVisibleSurfacePoint(Vector3 &point,
294                                                                                                                                         Vector3 &normal,
295                                                                                                                                         const Vector3 &viewpoint,
296                                                                                                                                         const int maxTries
297                                                                                                                                         )
298{
299  Plane3 plane;
300  int faceIndex = RandomValue(0, mFaces.size()-1);
301        int tries;
302  for (tries = 0; tries < maxTries; tries++) {
303    Face *face = mFaces[faceIndex];
304    plane = GetFacePlane(faceIndex);
305   
306    if (plane.Side(viewpoint) > 0) {
307      point = Vector3(0,0,0);
308      float sum = 0.0f;
309      // pickup a point inside this triangle
310      for (int i = 0; i < face->mVertexIndices.size(); i++) {
311                                float r = RandomValue(0,1);
312                                sum += r;
313                                point += mVertices[face->mVertexIndices[i]]*r;
314      }
315      point *= 1.0f/sum;
316      break;
317    }
318  }
319 
320  normal = plane.mNormal;
321  return (tries < maxTries) ? faceIndex + 1 : 0;
322}
323
324
325int
326MeshInstance::CastRay(
327                                                                                        Ray &ray
328                                                                                        )
329{
330  int res = mMesh->CastRay(ray, this);
331  return res;
332}
333
334int
335MeshInstance::CastRay(
336                                                                                        Ray &ray,
337                                                                                        const vector<int> &faces
338                                                                                        )
339{
340  return mMesh->CastRayToSelectedFaces(ray, faces, this);
341}
342
343
344
345int
346MeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
347{
348  return mMesh->GetRandomSurfacePoint(point, normal);
349}
350
351int
352MeshInstance::GetRandomVisibleSurfacePoint(Vector3 &point,
353                                                                                                                                                                         Vector3 &normal,
354                                                                                                                                                                         const Vector3 &viewpoint,
355                                                                                                                                                                         const int maxTries
356                                                                                                                                                                         )
357{
358        return mMesh->GetRandomVisibleSurfacePoint(point, normal, viewpoint, maxTries);
359}
360
361
362int
363TransformedMeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
364{
365  int index = mMesh->GetRandomSurfacePoint(point, normal);
366  point = mWorldTransform*point;
367  normal = TransformNormal(mWorldTransform, normal);
368  return index;
369}
370
371Plane3
372Mesh::GetFacePlane(const int faceIndex)
373{
374  Face *face = mFaces[faceIndex];
375        return Plane3(mVertices[face->mVertexIndices[0]],
376                                                                mVertices[face->mVertexIndices[1]],
377                                                                mVertices[face->mVertexIndices[2]]);
378}
379
380bool
381Mesh::ValidateFace(const int i)
382{
383        Face *face = mFaces[i];
384
385        Plane3 plane = Plane3(mVertices[face->mVertexIndices[0]],
386                                                                                                mVertices[face->mVertexIndices[1]],
387                                                                                                mVertices[face->mVertexIndices[2]]);
388       
389        if (!eq(Magnitude(plane.mNormal), 1.0f))
390                return false;
391
392        return true;
393}
394
395void
396Mesh::Cleanup()
397{
398        int toRemove = 0;
399        FaceContainer newFaces;
400        for (int i=0; i < mFaces.size(); i++)
401                if (ValidateFace(i)) {
402                        newFaces.push_back(mFaces[i]);
403                } else {
404                        cout<<"d";
405                        delete mFaces[i];
406                        toRemove++;
407                }
408       
409        if (toRemove) {
410                mFaces = newFaces;
411        }
412       
413        // cleanup vertices??
414}
415
416int
417TransformedMeshInstance::CastRay(
418                                                                                                                                 Ray &ray
419                                                                                                                                 )
420{
421  ray.ApplyTransform(Invert(mWorldTransform));
422  int res = mMesh->CastRay(ray, this);
423  ray.ApplyTransform(mWorldTransform);
424 
425  return res;
426}
427
428
429void
430Mesh::AddTriangle(const Triangle3 &triangle)
431{
432  int index = mVertices.size();
433
434  for (int i=0; i < 3; i++) {
435    mVertices.push_back(triangle.mVertices[i]);
436  }
437 
438  AddFace(new Face(index + 0, index + 1, index + 2) );
439}
440
441void
442Mesh::AddRectangle(const Rectangle3 &rect)
443{
444  int index = mVertices.size();
445
446  for (int i=0; i < 4; i++) {
447    mVertices.push_back(rect.mVertices[i]);
448  }
449 
450  AddFace(new Face(index + 0, index + 1, index + 2, index + 3) );
451}
Note: See TracBrowser for help on using the repository browser.