Back to General and Gameplay Programming

raytracer problem

General and Gameplay Programming Programming

Started by Makaan March 05, 2010 12:42 PM

12 comments, last by nmi 14 years, 1 month ago

Makaan

100

Author

March 05, 2010 12:42 PM

Hello, My raytraces uses for all the computations double variables. My triangle intersection code is the following:


bool	Triangle::Intersect(const Line& line,const double maxDist, IntersectionData& data)
{
    Vector edge1 = _b - _a;
    Vector edge2 = _c - _a;
      
  
    Vector pvec = line.dx() ^ edge2;
    
    double det = edge1*pvec; 
    
    // no intersection
    if(det > -0.0000000001 && det < 0.0000000001) return false;
        
    double invDet = 1/det;
    
    Vector tvec = line.x0() - _a;
    
    double u = (tvec*pvec) * invDet;
    if(u < 0.0000000001 || u > 1.0000000001) return false;
    
    Vector qvec = tvec^edge1;
    
    double v = (line.dx()*qvec) * invDet;
    if(v < 0.0000000001 || (u + v) > 1.0000000001) return false;
    
    double dist = (edge2*qvec) * invDet;
    
    if(dist < 0.0000000001) return false;
    
    data._vec = line.x0() + line.dx()*dist;
    data._distance = dist;
    data._line = &line;
    data._geometry = this;
    data._normal = _face_normal;
    return true;
}

Note that i compare with 0.00000000001 instead of 0.0 because in the case of 0.0 i get very busted images (i use gcc , and i haven't tried this on windows). The problem is that if i have 2 triangles virtually, one next to each other, the rays pass right in between the triangles, and i get artifacts near all the edges. How can i solve this? Image Example (lots of reflections and one light).Note the black lines near all edges. demo

Thanks, Makaan

ApochPiQ

23,138

March 05, 2010 09:18 PM

Try using -epsilon instead of +epsilon when testing your u and v coordinates. Your current logic will reject a tiny strip of collisions along the edges of triangles.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

taz0010

277

March 05, 2010 10:24 PM

You can often prevent this from happening through careful use of < vs <=. But it doesn't look like this will work for barycentric coordinates. You can switch to an algorithm that doesn't suffer from this problem though. Try using this one:
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
(Their winding number method is the fastest of the two)
It's a very fast method for doing point-in-polygon, but will be slower than your method if you represent your geometry as triangles instead of n sided polygons.

Or you could write a point-in-triangle method that doesn't have this fp accuracy problem. Try doing 3 successive point-to-line distance tests to see if the point is behind each side in the triangle. No need for line segment checks here. Check against the infinite line. This should cause boundary points to be detected in at least one of the triangles.

szecs

2,990

March 06, 2010 02:52 AM

Maybe not the best solution, but I simply marked the triangles processed/unprocessed
I found it useful for refraction too.

[size=2]Portfolio [size=2]| Youtube channel | Paper modeller development blog | Journal

nmi

978

March 06, 2010 03:55 AM

Quote:Original post by Makaan
Note that i compare with 0.00000000001 instead of 0.0 because in the case of 0.0 i get very busted images (i use gcc , and i haven't tried this on windows).
The problem is that if i have 2 triangles virtually, one next to each other, the rays pass right in between the triangles, and i get artifacts near all the edges.
How can i solve this?

So it looks like you are using this method:
http://www.graphics.cornell.edu/pubs/1997/MT97.pdf

I use it in may raytracer too and it works fine. I compare with EPS=1e-10 and using floats instead of doubles and this works fine. The difference between your and my implementation is the check of the u and v values. In my implementation I'm checking u and v against 0 and 1 without epsilon and the det with epsilon. So maybe you want to change this to get rid of the black lines.

Makaan

100

Author

March 06, 2010 06:15 AM

Quote:
Try using -epsilon instead of +epsilon when testing your u and v coordinates. Your current logic will reject a tiny strip of collisions along the edges of triangles.

I have changed u and v tests to

if(u < -0.000001 || u > 1.000001) return false;

The image is a little bit better. The intersection between triangles in the same plane doesn't have gaps but on different planes there are still gaps (a lot less but still).

I have also tried a changing < and <= to see now the image is affected. The best result i get with only -epsilon and epsilon testing.

Quote:
In my implementation I'm checking u and v against 0 and 1 without epsilon and the det with epsilon. So maybe you want to change this to get rid of the black lines.

Just to show you how busted 0.0 and 1.0 (or 0 and 1) tests are i added an image:
scene

I belive the problem is in line:

if(dist < 0.000001) return false;

because at the corners, when the ray reflects, the distance is very small ,almost zero (which is less than .000001), therefore i just discard valid intersection at corners ( i tested the primary rays and none passes in between triangles).
The problem is that i can't put < 0.0 because the image gets really busted (as shown above).

Thanks,
Raxvan

nmi

978

March 06, 2010 06:38 AM

Quote:Original post by Makaan
Quote:
In my implementation I'm checking u and v against 0 and 1 without epsilon and the det with epsilon. So maybe you want to change this to get rid of the black lines.

Just to show you how busted 0.0 and 1.0 (or 0 and 1) tests are i added an image:
...

The problem is maybe in the code that calls the intersection test. You are right to allow the "tunnel effect" for the ray (i.e. it can move without intersecting to prevent it sticking on the object it came from). However, this test should not be in the code that performs the ray-triangle intersection, but in the function that calls it.

So this is the code from my raytracer:

    // ray-triangle intersection    bool intersectRayTri(vec3 o, vec3 d, vec3 a, vec3 b, vec3 c, float& t) {    	// http://www.graphics.cornell.edu/pubs/1997/MT97.pdf    	// two-sided triangles are checked    	vec3 e1 = b - a;    	vec3 e2 = c - a;    	vec3 pvec = cross(d, e2);    	float det = dot(e1, pvec);    	if (det > -EPS && det < EPS)    		return false;    	float invDet = 1.0 / det;    	vec3 tvec = o - a;    	float u = dot(tvec, pvec) * invDet;    	if (u < 0.0 || u > 1.0)    		return false;    	vec3 qvec = cross(tvec, e1);    	float v = dot(d, qvec) * invDet;    	if (v < 0.0 || u + v > 1.0)    		return false;    	t = dot(e2, qvec) * invDet;    	return true;    }

And this how you would call it (simplified by just iterating over the triangles, you should use an acceleration structure instead):

    bool intersect(vec3 o, vec3 d, Intersection& is) {    	// iterate over every triangle    	bool hit = false;    	float t_min = INF;    	for (int i = 0; i < numTriangles; i++) {    		Triangle& tri = triangles;    		vec3 a = tri.a;    		vec3 b = tri.b;    		vec3 c = tri.c;    		float t = INF;    		if (intersectRayTri(o, d, a, b, c, t) && T_MIN < t && t < t_min) {    			hit = true;    			t_min = t;    			is.t = t;    			is.p = o + t * d;    			// set other intersection parameters...    		}    	}    	return hit;    }

Here, INF is a very big number or infinity, as you wish. T_MIN is the "tunneling distance", in my raytracer its 0.001, but you can also make it smaller (for instance if distances are measured in m, then set it to 1e-6 which is one µm).

Then your image should look fine: