Context Navigation

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

Revision 492, 10.5 KB checked in by bittner, 19 years ago (diff)
Large merge - viewcells seem not functional now

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: