Intersection of two triangles

Is there a way to get all the intersection points/lines between two geometries?
If not, what about the intersection line between two triangles?

I need this for Java3D but if there's such code in Ardor3D or JOGL, I could translate them to Java3D. So any solution is appreciated.

Hi,
I'm not sure how far you've investigated so far, nor what your end goal is exactly so I'll give you some pointers and we can go from there.

Firstly, as far as I'm aware intersection points are all you an get out of Java3D collision, and in fact most (all?) physics colliders. I don't recall anything handing a line equation back as a result ( presumably in some sort of z = mx+ny + c style vector3f).

The most common way to get collision/intersections in Java3D is by using Behaviors, that report when things are colliding, like this
https://www.java-tips.org/other-api-tips-100035/119-java3d/2242-collision-detection-with-java3d.html
or
http://www.java2s.com/Code/Java/3D/TickTockCollision.htm
But this is probably not what you want as it just reports nodes that collide.

However the Picking API does a more useful job.

The com.sun.j3d.utils.pickfast.PickTool from j3dutils project will return PickResult out of any scene branch for a given ray, cone, cylinder or segment, but NOT shape.
So although this is a start it probably isn't what you need without extension.
It does show how the BranchGroups have utility methods for picking that end up using the PickInfo methods for picking and eventually arrive at the various intersect* methods of GeometryArrayRetained which is exactly the sort of intersection code you want.
However because you can't add new PickShapes the only way to use this for geometry/geometry would be to build a bounding polytope shape from one of your geometries.

So if you are examining a single geometry versus the rest of your scene graph this is probably a fine way to do it. If you want a general purpose all geometries against each other, you'd need to use the collision behaviors then for each wake up do a more detailed PickResult via a bounding polytope for one of them.

Note for any of the above you need to set the java3d picking system to use GEOMETRY not BOUNDS and set the various capabilities on each Node, which is easiest to do using the J3dUtils PickTool.setCapabilities() method.

Finally, in my code I mainly want mouse picking from the Canvas3D so I use the com.sun.j3d.utils.pickfast package which does the job very well.

For general physics-like work I use the excellent JBullet http://jbullet.advel.cz/ which is really very good, but might be a large hammer if all you want is intersection data.

Hope this gives you some pointers, please have a look at the various areas I mentioned then get back to us with more detail on what you need done.



 




 

Thanks for the detailed reply Phil.
What I'm trying to do is to find the intersection line/curve between two mesh and draw them.
So I don't need the equation of the line, a series of intersection points will do fine.

The J3D collision behavior, does it detect collision based on bounding boxes or exact geometry? If all it does is use bounding boxes then it's useless to me because my meshes are near each other so their bounds are always in collision.

I think I will use the PickTool as you suggested, the pickSegment in particular. I can convert a triangle mesh into 3 line segments, then use pickSegment to check if at least 2 of those line segments intersect with another mesh. If so, draw a line between those 2 intersection points. It won't be perfect, but probably sufficient.

Now I have to decide if I should use PickTool at all. It might be faster if I implement my own lineSegment+Triangle check code because j3D because PickTool does a whole bunch of extra things that I don't need such as: sub-primitive picked (that is, the point, line, triangle or quad), the closest vertex to the center of the pick shape, and the intersection's normal, color and texture coordinates.

Also PickTool seem to require ALLOW_GEOMETRY_READ, ALLOW_FORMAT_READ, ALLOW_COUNT_READ, and ALLOW_COORDINATE_READ plus the ALLOW_COORDINATE_INDEX_READ. All these would be not necessary in my own implementation since I already have access to coordinates array and I wonder if these capabilities would slow down rendering.

Saeid,
The collision behavior can be set to USE_GEOMETRY using the speedHint, which as you say is the only useful options, the bounds are almost always to course too be wanted.

I agree the PickTool does more than you need, and if you want to run a bunch of collision it probably won't be maximum speed.

If you do do your own intersection code, don't forget to run a gross comparison using the bounds first then the fine grain using the geometry data.

If you are using 1.6 then you don't need to set the *_READ capabilities as at some point in Java3D's history a default read capabilities got shoved in, possibly just as it was being made open source, so most read capabilites are turned on by default. This has killed the biggest advantage of a retained mode scene graph, the compilation of branches. So turning them on will have no impact on performance. In 1.7 where this is a flag to not use them by default, in cases where scene graphs are simple you can get amazing performance improvements. But that's not relevant here.

Phil.

runiter wrote

if there's such code in Ardor3D

https://github.com/gouessej/Ardor3D/blob/master/ardor3d-core/src/main/java/com/ardor3d/intersection/TriangleTriangleIntersect.java#L41

philjord wrote

This has killed the biggest advantage of a retained
mode scene graph, the compilation of branches. So turning them on will have
no impact on performance. In 1.7 where this is a flag to not use them by
default, in cases where scene graphs are simple you can get amazing
performance improvements. But that's not relevant here.

I always wondered how the meshes are retained differently based on these flags and exactly what improvements are achieved by using them. Can you point me to any documentation that explains various retained mode optimizations? Do you have any benchmark testing results that show the magnitude of improvements?

@gouessej
Thanks for link to that Ardor3D class. Exactly what I was looking for!

There isn't much documention except for here
https://github.com/philjord/java3d-core/blob/master/docs/perf_guide.txt#L100

But it basically automatically bakes in transformations and merges geometries into big fat geometries that share attributes.
For a fairly complex scenegraph like you might get in a game it can make a huge difference. My Morrowind port went from 1fps to about 6fps once I got compilation going, for a complex scene.
Running on a slow RT like AndroidRT it makes more difference than a good JIT like the sun JRE.

However I haven't actually spent time to get a repeatable and consistent benchmark out for it.

gouessej wrote

runiter wrote

if there's such code in Ardor3D

https://github.com/gouessej/Ardor3D/blob/master/ardor3d-core/src/main/java/com/ardor3d/intersection/TriangleTriangleIntersect.java#L41

@gouessej
The link you provided just returns a Boolean that tells if there is a collision between two triangles or not. Do you know of a code that returns the actual intersection?

Phil

Ardor3d has a collision tree than can create bounding boxes of not only of meshes but also of sub-section of large meshes:

https://github.com/Renanse/Ardor3D/blob/master/ardor3d-core/src/main/java/com/ardor3d/bounding/CollisionTree.java

Is there a similar thing in Java3D already? If not I guess I'll have to convert the above code to j3d myself.

No,
The BHTree internal classes do the sub space division/search work, and they are used by the picking/collision code internally.

But there is nothing to automatically sub divide large meshes.

So I think you will be best to just convert it, given that the picking/collision doesn't generate the right sort of return results.