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

Revision 209, 8.2 KB checked in by bittner, 19 years ago (diff)

data added

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