intersection(::Ray, ::Mesh) broken

[kylebeggs]

As the title says, this method is broken. Below is a MWE:

julia> tet = Tetrahedron(Point(0,0,0), Point(1,0,0), Point(0,1,0), Point(1,1,1))
Tetrahedron{3,Float64}
  └─Point(0.0, 0.0, 0.0)
  └─Point(1.0, 0.0, 0.0)
  └─Point(0.0, 1.0, 0.0)
  └─Point(1.0, 1.0, 1.0)

julia> r = Ray(Point(0.5,0.5,-1), Vec(0.,0,2))
Ray{3, Float64}(Point(0.5, 0.5, -1.0), [0.0, 0.0, 2.0])

julia> intersection(r,tet)
ERROR: StackOverflowError:
Stacktrace:
 [1] intersection(f::Function, g1::Ray{3, Float64}, g2::Tetrahedron{3, Float64, StaticArraysCore.SVector{4, Point3}}) (repeats 2 times)
   @ Meshes ~/.julia/dev/Meshes/src/intersections.jl:37

I don't know enough to figure out why it says repeats 2 times.

[juliohm]

Thank you for reporting the issue. I think we should be able to implement a method for Tetrahedron by combining the results of the intersection with the facets. Something along the lines of the following pseudo-code: union(intersection(r, f) for f in facets(t))

[dorn-gerhard]

I can help with intersections - currently I finish intersections in 2D: intersection of

• [x] ray - ray (rays.jl) - current PR #297
• [x] ray - segment (raysegment.jl) - prepared, coming soon
• [x] line - ray (lineray.jl) - prepared, coming soon
• [x] line - segment (linesegment.jl) - prepared, coming soon

[kylebeggs]

Can you implement the ray-segment into the ray-triangle to check if the ray hits an edge of the triangle? We should have an option for the user to check this or not. This is needed for some algorithms. I do think there is a way to use some of the information already computed in the current ray-triangle implementation, but I haven't had time to check into it.

[juliohm]

@dorn-gerhard I think you already checked ✅ some of the implementations in your roadmap above?

[juliohm]

I edited the comment above to include a check list.

[kylebeggs]

We should be able to refactor this function into just looping through the triangles in the tetrahedron and calling intersection(ray, triangle) now.

[juliohm]

Feel free to submit a PR @kylebeggs , thanks for adding these new methods.

[juliohm]

@kylebeggs do you think you can finish this one up? :) I remember you added the latest intersection methods, maybe we are ready to cover the Tetrahedron case now.

[kylebeggs]

Yeah this should be strait forward now. I'll see if I can get to it today, if not it'll be in 1.5 weeks as im traveling

[kylebeggs]

If the ray intersects multiple triangles in the tetrahedron, should we just be returning a vector of the intersections?

[juliohm]

Maybe we should return a Multi geometry. It is a bit annoying but I think it is more consistent with the design.

Em ter., 9 de mai. de 2023 21:58, Kyle Beggs @.***> escreveu:

If the ray intersects multiple triangles in the tetrahedron, should we just be returning a vector of the intersections?

— Reply to this email directly, view it on GitHub https://github.com/JuliaGeometry/Meshes.jl/issues/290#issuecomment-1541090506, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAZQW3N6OWTQCYEDJZHOORDXFLR4XANCNFSM6AAAAAAQCP5QPA . You are receiving this because you commented.Message ID: @.***>

[kylebeggs]

I'm not familiar with that

[juliohm]

You basically wrap the vector of geometries in each intersection into a new Multi(geoms) object. This one can then be wrapped into a intersection type.

Em qua., 10 de mai. de 2023 09:18, Kyle Beggs @.***> escreveu:

I'm not familiar with that

— Reply to this email directly, view it on GitHub https://github.com/JuliaGeometry/Meshes.jl/issues/290#issuecomment-1542107372, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAZQW3MP5GT5VVDUEFLG75TXFOBSNANCNFSM6AAAAAAQCP5QPA . You are receiving this because you commented.Message ID: @.***>

[kylebeggs]

I see. This multi(geoms) object already exist or i need to create it? I haven't seen any type like that

[juliohm]

It already exists. See the test/multi.jl file for examples.

Em qui., 11 de mai. de 2023 22:30, Kyle Beggs @.***> escreveu:

I see. This multi(geoms object already exist or i need to create it? I haven't seen any type like that

— Reply to this email directly, view it on GitHub https://github.com/JuliaGeometry/Meshes.jl/issues/290#issuecomment-1544976943, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAZQW3PEIX4FDAXE3PFWGA3XFWHFFANCNFSM6AAAAAAQCP5QPA . You are receiving this because you commented.Message ID: @.***>

[kylebeggs]

We would need to make changes to Multi to make this work. Currently, it only supports PointOrGeometry. Either we need to loosen that type restriction or create a new type altogether like MultiIntersection or something like that.

[juliohm]

Good point. This came up in other contexts before. I wonder if we should looses this type restriction and allow mixed collections of points and geometries. Would you like to give this a try @kylebeggs? I am assuming you have an intersection case that is represented by points + triangles, is that right?

[kylebeggs]

We do allow mixed collections, the issue is that the return type is an Intersection which is not a point or geometry. We need to add Intersection to the Union{Point{Dim,T},Geometry{Dim,T}} and then probably change the name from PointOrGeometry because hat wouldn't make sense anymore.

[juliohm]

I don't know if I followed. Our Intersection holds any type as the geometry:

https://github.com/JuliaGeometry/Meshes.jl/blob/5f64dea3cf27cd555fec90d9eda6498bb6cc1c69/src/intersections.jl#L123-L126

We need to loosen the type restriction in our Multi geometry? That is the proposal?

https://github.com/JuliaGeometry/Meshes.jl/blob/5f64dea3cf27cd555fec90d9eda6498bb6cc1c69/src/geometries.jl#L147-L149

[kylebeggs]

I think what you have in mind is inserting the geometry from the intersections into Multi? I was thinking we really should be wrapping Intersection into some kind of Multi type so you don't lose the IntersectionType. One way to make this work is to loosen the type restriction on Multi but I like the idea that it should just be a wrapper around a vector of homogeneous types. I think there are a few options:

1. We make an abstract Multi type and then subtypes for each type to wrap. This have the advantage of homogeneous types in the vector

abstract type Multi end

struct MultiGeom{Dim,T,I<:Geometry{Dim,T}} <: Multi
  items::Vector{I} 
end

struct MultiIntersection{Dim,T,I<:Intersection} <: Multi
  items::Vector{I} 
end

struct MultiDomain{Dim,T,I<:Domain} <: Multi
  items::Vector{I} 
end

...

2. We don't restrict Multi at all, and move it out of geometries.jl because that wouldn't make for it to live there anymore.

struct Multi{Dim,T,I}
  items::Vector{I} 
end

3. We simply add in Intersection to the Union

struct Multi{Dim,T,I<:Union{Point{Dim, T}, Geometry{Dim, T}, Intersection}}
  items::Vector{I} 
end

Personally I think option 1 is best.

[juliohm]

I think what you have in mind is inserting the geometry from the intersections into Multi?

Yes, we can take this mixed set of geometries and feed into a multi-geometry. The associated intersection type can be IntersectingGeometries or a generic name that translates the idea that the shape of the intersection is pretty arbitrary.

If you feel that there are specific combinations of geometries inside the multi-geometry that deserve their own intersection type, we can do that as well.

[juliohm]

@kylebeggs any advance with this one? We can introduce a new Intersecting intersection type to hold this Multi geometry. Notice that we did a major refactoring of the intersection types in the latest releases to support more combinations of geometries and domains.

[kylebeggs]

Hi @juliohm, sorry I have been really busy with a few projects of my own and this issue isn't needed for my progress on that. I'm going to try to wrap this up, however. I think it would be best to start a draft PR so you can see the function I put together and suggest the correct types we should be using. I need to review the refactor you mentioned.

[juliohm]

Based on our discussion, what you really need to express is intersection(ray, boundary(tetra)) where the boundary is a Mesh. I will update the title of the issue and close the draft PR so that we start fresh with a method for Mesh.

[kylebeggs]

This issue has gone on a tangent unrelated to the root of the original issue. There is an issue for both intersection(::Ray, ::Tetrahedron) and intersection(::Ray, ::Mesh). I haven't tested any further with other types which don't have methods defined for that concrete type, but I'm pretty sure the problem is the fallback method for intersection https://github.com/JuliaGeometry/Meshes.jl/blob/master/src/intersections.jl#L100 just continues to call itself giving a stack overflow.

We need to either define methods for each combination of geometries and print an error message that method hasn't been defined yet, or change the design such that we don't fall back to this line and infinitely call itself and you get a MethodError: no method matching (my preference). If you are fine with a stack overflow error for undefined intersection methods then you can close the issue.

Good idea to unassign me, I just can't dedicate any time to this issue right now as it is unrelated to my progress. I have been swamped. Sorry.

[juliohm]

Yes, there are many algorithms that we use fallbacks assuming that simpler cases are already handled. When a method is not found, sometimes we enter in infinite recursion. The ideal fix is to implement the method for the requested geometry. We could also consider another design with a different fallback, but I couldn't find a clean design that was expressive enough for the task.

Hope you are advancing with your work, come back when you have free time :)

[juliohm]

Closing as not urgent. It seems like you managed to achieve what you wanted back then. Let's reopen when we hit the missing method again.

[kylebeggs]

Yes, I just iterated through the elements of the mesh and checked the intersection for each.