search

alecjacobson / computer-graphics-bounding-volume-hierarchy

Computer Graphics Assignment about Bounding Volume Hierarchies
123 stars 45 forks source link

Can we assume that no two triangles are co-planar? #12

Closed velociraptor111 closed 6 years ago

velociraptor111 commented 6 years ago

For triangle_triangle_intersection.cpp I was reading the lecture slide on "Triangle-Triangle Intersection". There, two algorithms are being proposed.

Algorithm 1 works for T1 & T2 when they are not co-planar and Algorithm 2 seems very complicated to implement.

Since I believe that we did not cover this topic during class, can we use algorithm 1 (thus assuming no two triangles are co planar) for the purpose of this lab? Or any suggestions/guidance?

zhtdavis commented 6 years ago

How long does it take for you to do brute force intersection test? Mine is around 7s. On the readme it seems the demo program is using the second algorithm which is much faster.

zhtdavis commented 6 years ago
Mine is like: Method Time in seconds
brute force 7.68331193924
build trees 0.01909399033
use trees 0.00568318367
velociraptor111 commented 6 years ago

yeah, mine takes a long time as well like ~11 seconds. Did you use algorithm 1 as well?

zhtdavis commented 6 years ago

Yes.

velociraptor111 commented 6 years ago

Just to verify if I'm doing this correctly, you check for these conditions:

1) If two edges from triangle A intersect triangle B && 0 edges from triangle B intersect triangle A return true 2) If two edges from triangle B intersect triangle A && 2 edges from triangle A intersect triangle B return true 3) If 1 edge from triangle A intersect triangle B && 1 edge from triangle B intersect triangle A return true

else return false

is that all?

zhtdavis commented 6 years ago

I'm doing six ray-triangle intersection queries. Not sure this is the correct way to do it...

velociraptor111 commented 6 years ago

Yeah same, so I converted each edge basically into a ray and use the function from "ray_intersect_triangle.h" to intersect the with "ray" with the triangle. Ray origin if one of the vertex (call this A) and the direction is going from this ray to the next vertex B. (hence direction is B-A)

If ray intersects the triangle then it means that edge intersects the triangle.

not sure either lol

krsh732 commented 5 years ago

So do we need to worry about coplanar triangles?

velociraptor111 commented 5 years ago

I got the correct results .. So I think yes ..(?) also the chances of triangles exactly being coplanar are pretty slim ...