Context Navigation

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
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 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
198	int
199	Mesh::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
270	int
271	Mesh::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
292	int
293	Mesh::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
325	int
326	MeshInstance::CastRay(
327	Ray &ray
328	)
329	{
330	int res = mMesh->CastRay(ray, this);
331	return res;
332	}
333
334	int
335	MeshInstance::CastRay(
336	Ray &ray,
337	const vector<int> &faces
338	)
339	{
340	return mMesh->CastRayToSelectedFaces(ray, faces, this);
341	}
342
343
344
345	int
346	MeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
347	{
348	return mMesh->GetRandomSurfacePoint(point, normal);
349	}
350
351	int
352	MeshInstance::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
362	int
363	TransformedMeshInstance::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
371	Plane3
372	Mesh::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
380	bool
381	Mesh::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
395	void
396	Mesh::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
416	int
417	TransformedMeshInstance::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
429	void
430	Mesh::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
441	void
442	Mesh::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.

Download in other formats: