Jump to content
  • Advertisement
Sign in to follow this  
bjarnia

Ray-Triangle intersection issue in RayTracing

This topic is 3664 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey So I'm programming a RayTracer from scratch, and I just added support for triangles. I am using this algorithm for ray-triangle intersection: http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf The results are good except for the odd triangle. I think the triangle is orthogonal to the lightsource when this happens. See pic: http://www.steik.org/dump/out.png You can see a couple of triangles there in the middle that look like they are completely in shadow. The shading function is fine (I can add a sphere and it will be perfectly shaded, as will the teapot if I take out shadow checking), so I'm certain that the problem is in the intersection function. The problem might be that the teapot that I use has predefined normal at each vertex that I use for shading, but the intersection function uses the vertexes to do it's thing. If that is the problem however, I am not sure how to solve it, so I'm open to suggestions :) But of course, the intersection testing is totally decoupled from the shading function, so for the intersection test I don't have information about the light. Might as well post some code... the top is the shading function, followed by the intersection stuff..

Shade()
{
	else if (light->type == LightBase::DIRECTIONAL)
		{	
			LightDirectional* ld = (LightDirectional*)scene->lights;

			float dist = TestRay(Ray(pos, ld->dir), scene);
			bool isInShadow = !(dist == 0);

			if (!isInShadow) 
			{				
				// Calculate color.. this part works
			}
		}
}

float RayTracer::TestRay(Ray ray, Scene* scene)
{
	vector<ISect> *isects = Intersections(ray, scene);

	float dist;
	if (isects->empty())
		dist = 0;
	else
		dist = (*isects)[0].dist;
	
	delete isects;
	return dist;
}

vector<ISect> *RayTracer::Intersections(Ray& ray, Scene* scene)
{
	vector<ISect> *list = new vector<ISect>();

	for (int i = 0; i < scene->sceneObjects.size(); i++)
	{
		ISect inter = scene->sceneObjects->Intersect(ray);

		if (inter.valid && inter.dist > 0)
			list->push_back(inter);
	}

	struct isectSort
	{	bool operator()(ISect a, ISect b) { return a.dist < b.dist; }	};

	std::sort(list->begin(), list->end(), isectSort());
	
	return list;
}
and well.. since i'm posting code anyway, here is the triangle intersection test:

	inline virtual ISect Intersect(Ray& _ray)
	{
		// From the paper "Fast Minimum Storage Ray Triangle Intersection"
		// Tomas Möller
		// Ben Trumbore

		Vec3 tvec, pvec, qvec;
		float det, inv_det;
		float u, v, t;

		Vec3 edge1 = Vec3::Minus(v1, v0);
		Vec3 edge2 = Vec3::Minus(v2, v0);
		pvec = Vec3::CrossP(_ray.dir, edge2);
		det = Vec3::DotP(edge1, pvec);

		if (det > -EPSILON && det < EPSILON)
			return ISect(); // false, no intersection

		inv_det = 1.0 / det;

		tvec = Vec3::Minus(_ray.start, v0);

		u = Vec3::DotP(tvec, pvec) * inv_det;

		if (u < 0.0 || u > 1.0)
			return ISect(); // false, no intersection

		qvec = Vec3::CrossP(tvec, edge1);

		v = Vec3::DotP(_ray.dir, qvec) * inv_det;



		if (v < 0.0 || (u + v) > 1.0)
			return ISect(); // false, no intersection

		t = Vec3::DotP(edge2, qvec) * inv_det;

		return ISect(this, _ray, t);
	}

Share this post


Link to post
Share on other sites
Advertisement
I'm guessing here: while for the shading you use the interpolated normal, I think that you check if the shading must be performed at all for a given light by doing a dot product between the light ray and the triangle normal. In some cases this will report that the triangle is backfacing the light, even when at least PART of the surface would be visible according to the interpolated normals.

Hope this help.

PS. Whay do you store all the intersected triangles? Usually you retun just the closer one (and this enabled a few optimizations in the intersecting routines). Do you use it to handle overlapping transparent surfaces or for other reasons?

EDIT: you could try a test to see if the problem is what I suspect: try rendering the same scene using the true triangle normal: if I got it, the problematic triangles should be fully shadowed, while every triangle that looks at least partially lit will be fully lit.

Share this post


Link to post
Share on other sites
Did check whether the normal you are using for shading is actually unit length?
When interpolating normals it often happens that they use unit length properties.

Looking at the picture however I think the problem lies somewhere else, look at the edge artifacts at the middle/bottom

Share this post


Link to post
Share on other sites
Thanks for replying.

Performance is not really an issue at this point (image quality first), so I haven't thought about optimizations to the intersection routine.

Yes, I make sure the normal used for lighting is unit length.

True triangle normal:


Interpolated normals from dataset:



Same as above, but no checking if it's shadow (if it's occluded by other triangles in the scene)



As cignox1 suggested, the problematic triangles are fully shadowed when renderin with true normals.

I considered your suggestion;

Quote:
I'm guessing here: while for the shading you use the interpolated normal, I think that you check if the shading must be performed at all for a given light by doing a dot product between the light ray and the triangle normal. In some cases this will report that the triangle is backfacing the light, even when at least PART of the surface would be visible according to the interpolated normals.


But as I said previously, the problem is not in the shading function. This can be observed from the above pictures. When the problem occours I don't even evaluate the shading function because the triangle is judged to be completely shaded.

Hmmm... :o

[Edited by - bjarnia on November 27, 2008 5:25:53 AM]

Share this post


Link to post
Share on other sites
I think that those triangles occlude themself: when the shadowray is shot, the ray hit the same triangle it was originated from. A solution might be to discard from the shadow test the triangle where the ray originated.
This happens because you use fake normals, but the true shape of the triangle is planar: that is, this works for shading, but shadowing breaks and reveals the true poligonal shape.

Share this post


Link to post
Share on other sites
Looks like it worked!

I multiplied the starting position of the shadow ray by 1.01 so it wouldn't "originate in it self", and that seems to have taken care of the problem.
It's a hack.. but i'm happy with the results :)

Thanks!

(sorry for diff color! forgot what the previous setting was :) )

Share this post


Link to post
Share on other sites
Quote:
Original post by bjarnia
Looks like it worked!

I multiplied the starting position of the shadow ray by 1.01 so it wouldn't "originate in it self", and that seems to have taken care of the problem.
It's a hack.. but i'm happy with the results :)

Thanks!


Sorry, I didn't suggested you that because I thought you already were doing this, since not using this hack usually lead to strange pixels here and there.
However, this very problem is often called 'acne problem', and you should add an epsilon to any ray originating by an intersection (reflection, transmission and shadow, usually). Most of the people use the surface normal to offset the origin point (the intersection point) and thought it is a hack, is (as far as I know) the most used trick to avoid those kind of errors.

As I said, not doing this resulted (at least in my RT) in strange pixels similar to noise appearing randomly all over the image and I'm a bit surprised that you didn't have the same problem with your reflection code...

Glad you found the solution.

Share this post


Link to post
Share on other sites
Thanks again!

I queued up 200 frames or so for rendering while sleeping and noticed another problem when I woke up, when the light had moved, but this (and the original problem) was fixed by adding the normal multiplied by 0.01 to the position, instead of just increasing the position a bit.

Don't have any books or nothin on raytracing, just doing this for fun, so I'm not aware of what is "generally done" >_<

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!