Is my triangle intersection code correct?

Graphics and GPU Programming Programming

Started by IsItSharp March 31, 2015 09:14 AM

12 comments, last by IsItSharp 9 years ago

3,376

April 02, 2015 09:57 AM

In fact there is a lot of triangle intersection code algorithms, out of all, most interesting are:

Moller-Trumbore http://www.google.cz/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CCwQFjAC&url=http%3A%2F%2Fpublic-digital-library.googlecode.com%2Fsvn%2Ftrunk%2FCG%2FGlobal%2520Illumination%2FRay%2520Tracing%2FFast%2520Minimum%2520Storage%2520Ray-Triangle%2520Intersection.pdf&ei=dg8dVeauKIKAUYb6gKgI&usg=AFQjCNF0PrfmXHhQeqCGY63JhQ56bY4DSw&bvm=bv.89744112,d.d24&cad=rja

which is just a standard either single-side or double-side barycentric test. It doesn't need any additional storage and in general is very fast on GPUs and CPUs.

Woop http://jcgt.org/published/0002/01/05/paper.pdf

I find it very fast on the CPU. It needs more storage compared to MT test (plus for shading you will need original vertex coordinates), so I find it to behave a bit worse (on some of the GPUs) compared to MT.

Out of others - Plucker test is one of the most robust, Badouel (projection) test behave very fast on SIMD SSE on CPU, and so on. I'm also linking to (a bit older) good summary of algorithms and their comparsions in terms of speed - http://gggj.ujaen.es/docs/grapp14_jimenez.pdf

I hope this can help. I could link you to my implementation of gpu-raytracer on GitHub, but that repo is heavily WIP and I haven't pushed for few weeks (I have modifications locally), plus the setup is a bit harder as of now (but I'm working on it!). https://github.com/Zgragselus/OpenTracer ... there is obsolete CPU code with variation of barycentric test and woop test in OpenCL (which is used in runtime).

My current blog on programming, linux and stuff - http://gameprogrammerdiary.blogspot.com

IsItSharp

369

Author

April 02, 2015 12:59 PM

Hi Vilem,

i tried to convert your version of triangle intersection from here: https://github.com/Zgragselus/OpenTracer/blob/master/OpenTracer/Math/Intersection/Intersection.h to my code:


            Triangle.prototype.intersect = function(ray){
                var e1 = this.t2.sub(this.t1);
                var e2 = this.t3.sub(this.t1);
                
                var pvec = ray.direction.cross(e2);
                var det = e1.cross(pvec);
                if(det > -0.001 && det < 0.001)
                    return -1.0;
                
                var inv_det = 1.0 / det;
                var tvec = ray.origin.sub(this.t1);
                
                var bx = tvec.dot(pvec) * inv_det;
                if(bx < 0.0 || bx > 1.0)
                    return -1.0;
                
                var qvec = tvec.cross(e1);
                var by = ray.direction.dot(qvec) * inv_det;
                if(by < 0.0 || (bx+by) > 1.0)
                    return -1.0;
                
                var d = e2.dot(qvec) * inv_det; //distance?
                
                var bz = 1.0 - bx - by;
                var bw = 0.0;
                
                return d;
            }

For my algorithm i need the distance from ray.origin to the intersection point. Is d the right value to return?

Vilem Otte

3,376

April 03, 2015 02:20 AM

Yes, 'd' is the distance from camera to hitpoint.

Also, I'll do a little shameless self-promotion; some time ago I've written an article about intersection tests and their derivations here on GD - http://www.gamedev.net/page/resources/_/technical/math-and-physics/intersection-math-algorithms-learn-to-derive-r3033, where I focused mainly to show the way how to derive some different intersection and give out an idea how to derive your own (of course it is not always as trivial and in some cases not even solvable (surfaces defined by differential functions or such) ~ just using numeric approximation) .. for any of the primitives, the derivation is straight-forward (which is good!).

Also note, please don't try to run the code from that repo, it won't work (sadly I don't have time to keep it up to date right now, I've finally managed to pull some parts of the code that were license-protected by the company I've been working with ~ so I'm free to release it, yet I can't find time to re-format it into some useful library).

My current blog on programming, linux and stuff - http://gameprogrammerdiary.blogspot.com

IsItSharp

369

Author

April 03, 2015 04:22 PM

Is this code maybe correct?


            Triangle.prototype.intersect = function(ray){
                var edge1 = this.t2.sub(this.t1);
                var edge2 = this.t3.sub(this.t1);
                
                var s1 = ray.direction.cross(edge2);
                var divisor = s1.dot(edge1);
                if(divisor == 0.0)
                    return -1.0;
                
                var invDivisor = 1 / divisor;
                var distance = ray.origin.sub(this.t1);
                var barycCoord1 = distance.dot(s1) * invDivisor;
                if(barycCoord1 < 0.0 || barycCoord1 > 1.0)
                    return -1.0;
                
                var s2 = distance.cross(edge1);
                var barycCoord2 = ray.direction.dot(s2) * invDivisor;
                if(barycCoord2 < 0.0 || (barycCoord1 + barycCoord2) > 1.0)
                    return -1.0;
                var intersectionDistance = edge2.dot(s2) * invDivisor;
                return intersectionDistance;
                
            }

I think there is an error somehwere:

http://www.bilder-upload.eu/show.php?file=0bc99d-1428078863.jpg

If i use the triangles as a light i get this:

http://www.bilder-upload.eu/show.php?file=e1885c-1428079499.jpg

(i tried to build 4 walls around the sphere i don't know if my coordinates are correct).