Context Navigation

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

Revision 354, 10.3 KB checked in by bittner, 19 years ago (diff)
sampling node selection changes

Line
1	#include "Ray.h"
2	#include "Mesh.h"
3	#include "MeshKdTree.h"
4	#include "Triangle3.h"
5
6	int Intersectable::sMailId = 21843194198;
7
8	void
9	Mesh::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
38	AxisAlignedBox3
39	Mesh::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
51	int
52	Mesh::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
84	int
85	Mesh::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
120	int
121	Mesh::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.
158	inline int
159	int_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
196	int
197	Mesh::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	int
269	Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
270	{
271	int faceIndex = RandomValue(0, mFaces.size()-1);
272
273	// assume the face is convex and generate a convex combination
274	//
275	Face *face = mFaces[faceIndex];
276	point = Vector3(0,0,0);
277	float sum = 0.0f;
278	for (int i = 0; i < face->mVertexIndices.size(); i++) {
279	float r = RandomValue(0,1);
280	sum += r;
281	point += mVertices[face->mVertexIndices[i]]*r;
282	}
283	point *= 1.0f/sum;
284
285	normal = GetFacePlane(faceIndex).mNormal;
286
287	return faceIndex;
288	}
289
290	int
291	Mesh::GetRandomVisibleSurfacePoint(Vector3 &point,
292	Vector3 &normal,
293	const Vector3 &viewpoint,
294	const int maxTries
295	)
296	{
297	Plane3 plane;
298	int faceIndex = RandomValue(0, mFaces.size()-1);
299	for (int tries = 0; tries < maxTries; tries++) {
300	Face *face = mFaces[faceIndex];
301	plane = GetFacePlane(faceIndex);
302
303	if (plane.Side(viewpoint) > 0) {
304	point = Vector3(0,0,0);
305	float sum = 0.0f;
306	// pickup a point inside this triangle
307	for (int i = 0; i < face->mVertexIndices.size(); i++) {
308	float r = RandomValue(0,1);
309	sum += r;
310	point += mVertices[face->mVertexIndices[i]]*r;
311	}
312	point *= 1.0f/sum;
313	break;
314	}
315	}
316
317	normal = plane.mNormal;
318	return (tries < maxTries) ? faceIndex + 1 : 0;
319	}
320
321
322	int
323	MeshInstance::CastRay(
324	Ray &ray
325	)
326	{
327	int res = mMesh->CastRay(ray, this);
328	return res;
329	}
330
331	int
332	MeshInstance::CastRay(
333	Ray &ray,
334	const vector<int> &faces
335	)
336	{
337	return mMesh->CastRayToSelectedFaces(ray, faces, this);
338	}
339
340
341
342	int
343	MeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
344	{
345	return mMesh->GetRandomSurfacePoint(point, normal);
346	}
347
348	int
349	MeshInstance::GetRandomVisibleSurfacePoint(Vector3 &point,
350	Vector3 &normal,
351	const Vector3 &viewpoint,
352	const int maxTries
353	)
354	{
355	return mMesh->GetRandomVisibleSurfacePoint(point, normal, viewpoint, maxTries);
356	}
357
358
359	int
360	TransformedMeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
361	{
362	int index = mMesh->GetRandomSurfacePoint(point, normal);
363	point = mWorldTransform*point;
364	normal = TransformNormal(mWorldTransform, normal);
365	return index;
366	}
367
368	Plane3
369	Mesh::GetFacePlane(const int faceIndex)
370	{
371	Face *face = mFaces[faceIndex];
372	return Plane3(mVertices[face->mVertexIndices[0]],
373	mVertices[face->mVertexIndices[1]],
374	mVertices[face->mVertexIndices[2]]);
375	}
376
377	bool
378	Mesh::ValidateFace(const int i)
379	{
380	Face *face = mFaces[i];
381
382	Plane3 plane = Plane3(mVertices[face->mVertexIndices[0]],
383	mVertices[face->mVertexIndices[1]],
384	mVertices[face->mVertexIndices[2]]);
385
386	if (!eq(Magnitude(plane.mNormal), 1.0f))
387	return false;
388
389	return true;
390	}
391
392	void
393	Mesh::Cleanup()
394	{
395	int toRemove = 0;
396	FaceContainer newFaces;
397	for (int i=0; i < mFaces.size(); i++)
398	if (ValidateFace(i)) {
399	newFaces.push_back(mFaces[i]);
400	} else {
401	cout<<"d";
402	delete mFaces[i];
403	toRemove++;
404	}
405
406	if (toRemove) {
407	mFaces = newFaces;
408	}
409
410	// cleanup vertices??
411	}
412
413	int
414	TransformedMeshInstance::CastRay(
415	Ray &ray
416	)
417	{
418	ray.ApplyTransform(Invert(mWorldTransform));
419	int res = mMesh->CastRay(ray, this);
420	ray.ApplyTransform(mWorldTransform);
421
422	return res;
423	}
424
425
426	void
427	Mesh::AddTriangle(const Triangle3 &triangle)
428	{
429	int index = mVertices.size();
430
431	for (int i=0; i < 3; i++) {
432	mVertices.push_back(triangle.mVertices[i]);
433	}
434
435	AddFace(new Face(index + 0, index + 1, index + 2) );
436	}
437
438	void
439	Mesh::AddRectangle(const Rectangle3 &rect)
440	{
441	int index = mVertices.size();
442
443	for (int i=0; i < 4; i++) {
444	mVertices.push_back(rect.mVertices[i]);
445	}
446
447	AddFace(new Face(index + 0, index + 1, index + 2, index + 3) );
448	}

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

Download in other formats: