Clarification on Assignment Output and Testing Examples

[AntonyZhuang]

I have a question regarding the assignment requirements and testing process. I wanted to confirm if the expected output for this assignment is only a 3D yellow duck, or if there are other examples we should test to ensure our code functions correctly. Are there any additional models or test cases we can use for verification?

Additionally, could you please clarify how our code will be tested and evaluated?

[Zhecheng-Wang]

There are other tasks that use different meshes (e.g. intersections). You can test A4 tasks with other models. Just add models and change the main function to load different meshes.

The submission will first be tested with a script, then I will look at the output/code of any tasks that didn't pass all tests and grade manually.

[AntonyZhuang]

Thank you for your response. I was able to get the models working, but they all appear in yellow. I attempted the following commands:./rays ../data/rubber-ducky.objand ./distances 100000 10000, but they took too long to load, and I had to quit them. Will we be tested on these commands, or the color, or should I focus on other tasks?

[Zhecheng-Wang]

Yes, we will test all tasks, but the main points of entry are distances, intersections, rays. The meshes are all yellow because there is no texture, so libigl just assigned a bright color to it. If the program takes too long to run, please first check if you have compiled in release.

[AntonyZhuang]

I’ve made progress, but I noticed that my runtime is around 50 times slower than the example provided, although still quite fast. Would you recommend further optimization, or is this acceptable?

Additionally, all the .obj files work correctly when I use rays, but they fail when using distances and intersections, leading to a segmentation fault when the tree is involved. Could you provide guidance on how I might debug this issue? Would using Valgrind on the test cases be a good approach?

[jennicao]

For the segmentation fault issue, what fixed it for me was making sure that the left subtree or right subtree exists before accessing it

[Zhecheng-Wang]

The performance is fine. As long brute force time >>> AABB time it's good.

And second jennicao's comments on checking if a tree exists before accessing it.

[AntonyZhuang]

I've made some progress, and all three methods work fine, and the output is as expected with decent visuals. However, I got this warning for intersections. Would this be considered an error, or is it normal? I ask because, based on what I read, it's incorrect when pairs are found using the tree but not brute force.

[Zhecheng-Wang]

Yes, this is considered an error. It usually implies your intersection implementation has a bug.

[AntonyZhuang]

I’m having difficulty debugging intersections in my project. I suspect the issue lies either in find_all_intersecting_pairs_using_AABBTrees.cpp or triangle_triangle_intersection.cpp. Could you help me identify where I might have made a mistake?

Here’s what I’ve done for triangle_triangle_intersection.cpp based on Möller’s 1997 paper(Moller1997b.pdf):

Convert Row Vectors to Column Vectors: I transposed the input row vectors (A0, A1, A2, B0, B1, B2) to column vectors to ensure the correct matrix operations.

Plane Equations: I computed the normal vectors for both triangles by taking the cross product of their respective edges, giving me N1 for triangle A and N2 for triangle B.

Signed Distances: I calculated the signed distance of each vertex of triangle A to triangle B's plane and vice versa. This step is intended to allow early rejection if all vertices of one triangle are on the same side of the other triangle's plane (indicating no intersection).

Intersection Line: If no early rejection occurs, I calculate the intersection line between the two planes. The direction of this line is given by N1 X N2.

Projection onto Line: I projected the vertices of both triangles onto the computed intersection line, as described in the paper, to simplify the line parameter calculations.

Compute Intervals: I calculated the intervals along the intersection line for both triangles by finding the minimum and maximum projected points.

Interval Overlap Test: Finally, I checked whether the intervals from the two triangles overlap. If they do, the triangles intersect; otherwise, they do not.

For find_all_intersecting_pairs_using_AABBTrees.cpp, I followed a BFS approach with the following logic:

// Initialize list of candidate leaf pairs
leaf_pairs ← {}
if root_A.box intersects root_B.box
  Q.insert( root_A, root_B )
while Q not empty
{
  {nodeA, nodeB} ← Q.pop
  if nodeA and nodeB are leaves
    leaf_pairs.insert( node_A, node_B )
  else if node_A is a leaf
  {
    if node_A.box intersects node_B.left.box
      Q.insert( node_A, node_B.left )
    if node_A.box intersects node_B.right.box
      Q.insert( node_A, node_B.right )
  }
  else if node_B is a leaf
  {
    if node_A.left.box intersects node_B.box
      Q.insert( node_A.left, node_B)
    if node_A.right.box intersects node_B.box
      Q.insert( node_A.right, node_B)
  }
  else
  {
    if node_A.left.box intersects node_B.left.box
      Q.insert( node_A.left, node_B.left )
    if node_A.left.box intersects node_B.right.box
      Q.insert( node_A.left, node_B.right )
    if node_A.right.box intersects node_B.right.box
      Q.insert( node_A.right, node_B.right )
    if node_A.right.box intersects node_B.left.box
      Q.insert( node_A.right, node_B.left )
  }
}

I would really appreciate it if you could point out any mistakes I might have made in these implementations. Thank you!

[AntonyZhuang]

I used SAT instead and now it works(maybe). can you have a look that the output is as expected for each of these commands

./intersections ../data/knight.obj ../data/cheburashka.obj ./distances 100000 10000 ./rays ../data/rubber-ducky.obj