Triangle Tests

(L) [2006/07/01] [toxie] [Triangle Tests] Wayback!

Just a quick question: What are you guys using at the moment for testing ray-triangle intersections?

Cause my own experiments with various tri-tests all resulted in quiet some missed intersections per frame.

F.e.:

Barycentric Coordinate Tests (Badouel, Wald, etc.) suffer from incorrect plane-intersections and thus also incorrect u,v coordinates.

Pluecker Test fails if the ray origin is far away from the actual triangle.

So any suggestions?
_________________
what do you expect to do if you don't know what to do when you've got nothing to do?

(L) [2006/07/02] [toxie] [Triangle Tests] Wayback!

Jesus! This is maybe the most weird (=computational overdose) thingie to test a point if in triangle EVER! =)

But actually you still have a problem if you don't get an exact point on the triangle plane?!

(=ray origin far away from triangle)
_________________
what do you expect to do if you don't know what to do when you've got nothing to do?

(L) [2006/07/02] [lycium] [Triangle Tests] Wayback!

hehehe yeah it's crazy ;) i thought long and hard about how to make a worse test- no result! of course, i don't use it...

i'm interested to know, btw, how bad that "far away from triangle" problem is with plücker co-ords (in practise). surely if you're that far away missing a triangle here and there isn't such a big deal, or? (1. rays miss triangles anyway and 2. with many triangles per pixel at those distance i don't think you'll hear people shouting "hey!! there's a triangle missing under that pixel!")

(L) [2006/07/03] [playmesumch00ns] [Triangle Tests] Wayback!

Well it is a problem if that triangle should be occluding a super-bright object like the sun, even if you're shooting many rays per pixel, something very bright will still create a bright pinprick on that pixel [SMILEY Smile]

(L) [2006/07/03] [lycium] [Triangle Tests] Wayback!

playmesumch00ns, this is an example of (a manifestation of) the kind of problems toxie is addressing... to rephrase the question, which i answered in the negative, "does anyone know of any really robust [single precision] ray/tri intersection tests, or how the aforementioned precision problems can be overcome?"

that silly test i posted isn't really in the picture at all, it's just there for amusement value, or to set a lower quality bound ;)

(L) [2006/07/03] [fpsunflower] [Triangle Tests] Wayback!

[LINK http://jgt.akpeters.com/papers/LofstedtAkenineMoller05/]

That article might be of interest to this thread. The source code zip has implementations of most ray/tri tests I know about.

(L) [2006/07/11] [beason] [Triangle Tests] Wayback!

It's both reassuring and disappointing that other people are experiencing the same precision problems and trade-offs that I've seen in triangle intersection.

One thing I've done, and this is for shadow testing or more precisely, triangle sampling for soft shadows, when I have two algorithms that have different advantages (speed vs accuracy vs precision) is do a carefully constructed heuristic for choosing the most-likely best algorithm and then using that algorithm. In my case this made for really ugly and complicated code but decent results. In other words, it wasn't as fast as possible but the results were still good in just about every case, which is better than you can do if you just picked one of the algorithms all the time.

This may be unrealistic for ray-tri intersection, so it would be nice if there was a clear winner. In my case I use double precision MT, similar to fpsunflower.

(L) [2006/09/21] [tbp] [Triangle Tests] Wayback!

Warning: thread necromancy.

I've been hunting 'noise' in my packet traversal, where neighboring packets which should have followed the exact same path didn't, uncovering various funny sources of randomized ulp in the process. Those packets, a priori, were not tricky.

It turns out the culprit is my nth variation around a packet Wald's intersection implementation - mono-ray intersections using the same pre-baked data are sane - handing out noisy intersection points.

So this is my anecdotal evidence for numerical susceptibleness in Wald's, or more precisely implementation of.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

Triangle Tests back