TriangleIntersector

Hello folks,
I'd post to the patches but the code isn't complete. EDIT: non functional code removed

I think Axiom could really have some per-triangle intersection tests. Not every possibilities, one should rather use some physics engine in that case. But the often used basics without the need to setup any external package should be appreciated! At least the ray-triangle intersection with wich you can already do basic collision detection tricks.

The above modification made to Axiom's current TriangleIntersector is to inverse transform the ray instead transorming all the triangles, to get a much better performance. (where a Matrix4 is a parameter which defines ray-space transformation of the tri-mesh geometry)

I thought that someone can possibly pick the above and make it work or give a clue why it doesn't.

Thanks and so long.

[Borrillis]

Hello folks,
I'd post to the patches but the code isn't complete. EDIT: badly indented too - tabs vs. spaces - but your IDE will do
http://axiom.pastebin.com/f215e093f

I think Axiom could really have some per-triangle intersection tests. Not every possibilities, one should rather use some physics engine in that case. But the often used basics without the need to setup any external package should be appreciated! At least the ray-triangle intersection with wich you can already do basic collision detection tricks.

The above modification made to Axiom's current TriangleIntersector is to inverse transform the ray instead transorming all the triangles, to get a much better performance. (where a Matrix4 is a parameter which defines ray-space transformation of the tri-mesh geometry)

I thought that someone can possibly pick the above and make it work or give a clue why it doesn't.

Thanks and so long.

Thanks Andris11, I've moved this code to the wiki so that it won't get lost, and everyone is free to updat it there.

Thanks, the code I posted was really ugly and after a little revision showed up not much of a value anyway, so I removed that from the wiki again, but something could appear there though. As the current intersector isn't working properly, I'm trying to fix that and also to extend the TriangleIntersector with the following features:

- report spatial intersection point, i.e. where in world space
- report area (barycentric) coordinates of intersection (optional)
- report normal at intersection (optional)
- weight normal due to area coords (optional)
- report intersected submesh index

Yet not ready to suggest a patch, but so far it works pretty fine, the idea to inverse transform the casted ray instead of the triangle mesh was used, so that should be some good speed improvement! I hope you'll like the result.

Am assembling a little demo for that, see sceenshot. An invisible cursor is at center of screen (mouse input issues prevented it to follow the mouse). Visualised are point of intersection, intersected triangle, normal at intersection point, normals at triangle peaks and the submesh that was intersected (highlighted in blue).

Later there would appear the demo code in the wiki, but I'm quite short of time to elaborate on this much this week. So just to let you know about the intersector W.I.P., you also might have something in mind to the topic.

[Borrillis]

That looks very cool, can't wait to see the demo.

I assume the progress at 60%, so far ray-triangle intersection works very good, you can check the following files

TriangleBuilder.cs - Axiom's stuff, to be patched later
DemoRayMesh.cs

The reason I'm posting is that consideration should be made whether and how to integrate the intersector with a common SceneQuery. What do you think? I believe that's a good idea. More to it below.

demo use:

- compiles against SVN Crickhollow branch
- see demo source for list of keyboard commands
- mouse: starts off in window center regardless of system mouse position (also doesn't precisely follow it at least not with DX input), no 2D cursor visualisation ATM

design issues:

- TODO's, commented areas of code, to be polished
- uses custom Transform class to do transformations, because there were some issues with Matrix4. I hope to find out what was wrong and use Matrix4 again.
- TriangleListBuilder now builds a List<List<TriangleVertices>> (instead List<TriangleVertices>) to get a separate set of triangles per index set. This allows a one to one mapping between triangle sets and submeshes so index of submesh can be reported.

But I believe that submesh index should be handled elsewhere letting the intersector handle one triangle soup only, possibly making a TriangleIntersector per SubEntity and determine the index while iterating Entities and SubEntities in a scene query.




So first thoughts to integrating the intersector with SceneQuery


1. method RayTriMeshSceneQuery SceneManager.CreateRayTriMeshSceneQuery();
2. class DefaultRayTriMeshSceneQuery : SceneQuery
3. WorldFragmentType - add type TriMeshIntersection
4. WorldFragment - add field for TriMeshIntersection and report intersection details there (currently struct IntersectResultTriMesh in TriangleBuilder.cs)
5. Utility.Intersects() I'd try to provide general Ray-Tri tests (details will show up yet)

RayTriMeshSceneQuery would work similarly to RaySceneQuery. It will return Entities in the RaySceneQueryResultEntry.SceneObject and closest triangle intersection per entity in RaySceneQueryResultEntry.worldFragment. Other than Entity will not primarily be supported, same as RaySceneQuery. The container for each TriangleIntersector would be SubEntity since it provides a render operation, SubMesh could do too, but with SubEntity it should be better accessible from user code. As the TriangleIntersector needs to be created for object prior to op. the query could check that and create it if necessary.

So much for the generic SceneManager. For other scene managers things should be quite easy too.

What do you think?

[Borrillis]

First off, nice work, the demo is very neat.

However I did notice something strange. If there is no intersection, the number of triangles rendered is fairly low, basically the number of tri's in the mesh. But if there is an intersection, the number of triangles rendered increases significantly and the frame rate drops as well. Any ideas on why this is happening?

Well, I have noticed now too. But no serious idea.

Here the framerate varies from 130 (no intersection) down to 120 (intersection) with the knot mesh. Need to compare performance with the orig. intersector.

Triangle count varies from 3k - 35k (!) tris after switching the rendered models few times. Really don't know. Although the sphere.mesh used to visualize point of intersection has about 4k triangles (I didn't care about that so far) that shouldn't be te problem.

The demo creates all meshes in CreateScene, per frame does AttachObject/DetachObject or sets MovableObject.IsVisible also modifies dynamic vertex buffers of ManualObject instances whose are used to visualize intersected triangle and the normals. To do the highlighting it creates and destroys a material pass for each subentity to be highlighted.

Will keep this in mind for later.

The other runtime issues would be that some meshes are not rendered correctly, the knot mesh isn't correctly textured, dragon's wing webs are not rendered when looking from the bottom side of them (the above screenshot shows that actually, triangles get culled), btw. the cube.mesh doesn't have proper normals.

Are the rendering issues known for Crickhollow?

[Borrillis]

The other runtime issues would be that some meshes are not rendered correctly, the knot mesh isn't correctly textured, dragon's wing webs are not rendered when looking from the bottom side of them (the above screenshot shows that actually, triangles get culled), btw. the cube.mesh doesn't have proper normals.

Are the rendering issues known for Crickhollow?

Not all of them are known. I would check to see if the same problems occur in Ogre ( 1.2 minimally ). If they do, then it's a Model problem not a rendering one.

[Borrillis]

Well, I have noticed now too. But no serious idea.

Me either, I did take a look into what the demo was doing but didn't see anything obvious.

Here the framerate varies from 130 (no intersection) down to 120 (intersection) with the knot mesh. Need to compare performance with the orig. intersector.

That would be interesting to see. I did try to revert back, but there were too many interface changes.

Triangle count varies from 3k - 35k (!) tris after switching the rendered models few times. Really don't know. Although the sphere.mesh used to visualize point of intersection has about 4k triangles (I didn't care about that so far) that shouldn't be the problem.

Each mesh show a definite increase. I think the knot is the most obvious though.

The demo creates all meshes in CreateScene, per frame does AttachObject/DetachObject or sets MovableObject.IsVisible also modifies dynamic vertex buffers of ManualObject instances whose are used to visualize intersected triangle and the normals. To do the highlighting it creates and destroys a material pass for each subentity to be highlighted.

Will keep this in mind for later.

The ManualObject instances should only double the number or Triangles though, at most.

... Need to compare performance with the orig. intersector.

That would be interesting to see. I did try to revert back, but there were too many interface changes.

Yes several things have changed. A quick comparsion of the different approaches transform-mesh vs. inverse-transform-ray (anyway both with the new code structure) shows a fine speed improvement. Test against knot.mesh, 2880 triangles, P4/3Ghz:

0.012 sec (old - transform mesh)
0.006 sec (new - inverse transform ray)

I'm a little disappointed though, 0.006 sec means about 36% of a frametime at 60FPS, that doesn't sound very well IMHO. Will try to compare with the original approach later too.

Test against knot.mesh, 2880 triangles, P4/3Ghz:

0.012 sec (old - transform mesh)
0.006 sec (new - inverse transform ray)

That was caused by using an indexer to retrieve vertices of a triangle, oops! Now I'm getting roughly

0.008 sec (old - transform mesh)
0.001 sec (new - inverse transform ray)

which is better (sorry for the low precision however)

[Borrillis]

Nice!

I have gained more speed by partitioning the triangles into octree (seems approx 6x faster than the previous). However there are always some intersections missed. Could be caused by precission errors while casting the ray through octree, or also by improper distribution of the tris into cells. Am a little stuck but hope to solve it soon.
Including the code though for overview.

TriangleBuilder.cs
DemoRayMesh.cs

Demo changes: press 'X' to change the ray-trimesh intersection algorithm (Brute, Generic, Octree).

Brute - something very close to the original approach in TriangleIntersector, transforms all triangles before testing
Generic - inverse transforms ray, not triangles
Octree - same as Generic + partitions triangles

A simple Strategy-pattern abstraction appeared in the code to get that interchangeability. Initially for testing purposes only, anyway it should be nice to have a choice what do you think?

No more highlighting of subentities, index of subentity cannot be conveniently determined ATM, so far I believe that obtaining the index should rather be handled by a SceneQuery or in user code...

The container for each TriangleIntersector would be SubEntity since it provides a render operation, SubMesh could do too, but with SubEntity it should be better accessible from user code.

No, since sub entities can share submeshes. In my current insight, for Entity/SubEntity querying, the SubMesh would be the best place to store a single triangle set.

Btw. there appeared a few new intersection tests that could extend the Utility.Intersects() set of methods (after tested yet).

simple methods:

ray/segment-triangle
plane-triangle
aabb-triangle
aabb-segment

requiring intersector instance:

ray/segment-mesh
plane-mesh


The issue with increased rendered triangle count on intersection (as reported by the engine) is still there.

...there are always some intersections missed. Could be caused by precission errors while casting the ray through octree, or also by improper distribution of the tris into cells. Am a little stuck but hope to solve it soon.

No success, the idea seems to be fine in theory, but there appear imprecisions while the ray is being split up inside octree cells. As a result the implementation possibly can't be robust enough, at least I couldn't make it. Am going to try some other approach. This paper seems to provide a fast algorithm.

If anyone has a good tip on ray-octree traversal algorithm, please share it. Also an algorithm for determining octree cells intersected by a plane will be useful, the current approach uses plane-aabb tests to get the cells, but there should exist something more optimised for the octree case.
Thanks!

Yet to clear up my intent about this, I want to provide ray-trimesh and plane-trimesh intersection tests to Axiom. This will be useful for content creation tools, presentations and games that rely on cursor picking.