Raycasting to the polygon level -- questions

[Beauty]

I looked into the nice function Raycasting to the polygon level which was published in the wiki.

Unfortunately it works only for meshes. ManualObjects are ignored.
Now I think about to extend the code for usage with ManualObject.

Currently the raycasting method uses the helper function GetMeshInformation(), which returns all vertices of a mesh.
Now I wonder how it works.


So first I come up with general questions.

Code: Select all

for (int i = 0; i < static_cast<int>(index_count); i += 3)
{
    // check for a hit against this triangle
    std::pair<bool, Ogre::Real> hit = Ogre::Math::intersects(ray, vertices[indices[i]],
        vertices[indices[i+1]], vertices[indices[i+2]], true, false);
    // ...
}

The code assumes that all vertices are always groups of 3 vertices. Each group represents a triangle.
This should be fine for the rendering type OT_TRIANGLE_LIST.

But what happens if the mesh contain other rendering types? (e.g. OT_TRIANGLE_STRIP or OT_LINE_LIST)
For other rendering types I suppose that the "group of 3" assumptions fails.
The result would be wrong results.
Or in worst case the loop throws a OutOfRange exception.

Example:

* A mesh that contains one triangle and one line
* --> 5 vertices are in the vertex list
* first loop do access to indices[0], indices[1] and indices[2]
* i becomes 3 and the second loop starts
* second loop do access to indices[3], indices[4] and indices[5]
* --> CRASH, because indices[5] does not exists

What do you think?
Is my assumption correct or did I misunderstand something?

If I'm right, it would cause problems when a mesh contains lines.
Is it correct?



An other question:

For my application I want to extend the code for detecting ManualObjects.
I suppose the "logic" should be similar, but I know too less about the internals of ManualObject.
Many of my ManualObjects are a mixture of lines and triangles. Additionally I use mixes rendering types for each of them. (e.g. OT_TRIANGLE_LIST, OT_TRIANGLE_STRIP)
Some of my MOs contains different parts, created by blocks of ManualObject.::begin() ... ManualObject::end().
Are such "block" definitions similar to SubMeshes or is there no hierarchy for ManualObjects?
If all vertices are in one "flat" vertex list -- How I can figure out, which 3-pair vertices are "triangle groups".


I know, I can convert all ManualObjects to Meshes. Then I can detect them with the current code.
But some of my MOs I would prefer to keep them as MOs, because I add more triangles/lines on-the-fly.

[Mikachu]

Just answering to one of your questions:
From a ManualObject, you can get a ManualObjectSection (equivalent of Mesh/SubMesh relationship).
ManualObjectSection gives you access to RenderOperation, which points to a VertexData, and then it's similar to the wiki's code

[Beauty]

Thanks for this very good note.

[Beauty]

Oh dear, I'm again in front of a dead-end.

I don't find any class member (in ManualObject and ManualObjectSection) from which I can get the vertex data.

So I can't port these lines of code for ManualObject:

Code: Select all

VertexData vertex_data = submesh.vertexData;
VertexData vertex_data = mesh.sharedVertexData;

UPDATE
The problem with vertexData is solved.
I read again your post and recognized, that I have to access "RenderOperation" to get the vertex data.

[stealth977]

I use a small Hack to avoid crashes:

- Each submesh usually has one type of render operation, so while checking each submesh, i make sure index count is a multiple of 3, that avoids access violations (or out of index)

you would still get false hits for operations other than TRIANGLE_LIST but no crashes...

[Beauty]

On yesterday I started to code a method for ManualObjects. There I also check the renderingType of each ManualObjectSection.
Now I recognize that in the wiki code is no differentiation for the rendering types.
It would be useful to extend the code to avoid crashes or wrong results.

When your code only processes OT_TRIANGLE_LIST, then it ignores triangles defined by OT_TRIANGLE_STRIP (3 vertices for the first triangle and 1 per triangle after that) and OT_TRIANGLE_FAN (3 vertices for the first triangle and 1 per triangle after that).
So your code could cause wrong results, too.

I think the general problem is that the helper method GetMeshInformation() only returns a list of all vertices and indices. It does not contain information about the render type. Especially when a mesh contains more than one render types then the returned index list is useless.
The second problem is that RaycastFromPoint() assumes that the returned index list of GetMeshInformation() is a triangle list, which contains 3 values for each triangle. But this is wrong for triangle strips and triangle fans.


My suggestion for a better polygon raytracing:

* Add a differentiation for the rendering types to GetMeshInformation()
* For OT_TRIANGLE_STRIP and OT_TRIANGLE_FAN convert the index values to the type OT_TRIANGLE_LIST
..... * So the resulting index list would contain more elements.
..... * The resulting size has to be known when you initialize the array "indices". (important!)
..... * Example:
.......... When a (sub)mesh contains 3 triangles defined by triangle strip or fan, its index list contains 5 elements. After converting to a triangle list the (new) index list contains 9 elements.
* Rendering types of points and lines should be ignored. Or returned as extra arrays.


In general I think the performance could be improved by merging GetMeshInformation() and RaycastFromPoint().
Reason: For each mesh detected by the ray the helper method GetMeshInformation() re-creates a list of all vertices and indices. This could cause "much" CPU load for meshes with many polygons.
Currently the "ray-triangle checker method" runs through the returned lists of GetMeshInformation(). Instead it could read the vertex and index values directly from the (sub)meshes. Then there would be no need to create possibly huge lists for each query and mesh.

Additionally it could be useful to add a maxDistance parameter to RaycastFromPoint().
A ray query returns all hits, independent of the distance.
When you add a pre-check for the bounding boxes of each mesh you could avoid checking all triangles of the mesh (in the case that the distance is larger than the maxDistance).

[Beauty]

An other question related to the code:

unsigned char* vertex = static_cast<unsigned char*>(vbuf->lock(Ogre::HardwareBuffer::HBL_READ_ONLY));

// ...
for( size_t j = 0; j < vertex_data->vertexCount; ++j, vertex += vbuf->getVertexSize())
{
posElem->baseVertexPointerToElement(vertex, &pReal);
// ...
}

For each loop run the variable vertex will be increased.
But it's just "char" (8 bit). (By the way: In the Mogre port it's a byte*.)
It can't be increased again and again.
So, what's the sense of increasing vertex for each loop run?

[stealth977]

unsigned char * vertex;

its a pointer, not a char

[Beauty]

Ok, then it's a pointer to a char.
Nethertheless I don't understand its sense of

Code: Select all

vertex += vbuf->getVertexSize()

I'm just a stupid C# programmer with less C++ experience.

[hoppelmoppel]

It's a pointer to the vertex buffer(to the first elemnt of the buffer). By incrementing the pointer by the byte size of one vertex, you jump to the next vertex within the buffer. So after incrementation the pointer points to the second vertex and so on.

BR

[Mikachu]

It's a pointer to the vertex buffer(to the first elemnt of the buffer). By incrementing the pointer by the byte size of one vertex, you jump to the next vertex within the buffer. So after incrementation the pointer points to the second vertex and so on.

Just a precision on that : it's only true as the type of the pointer is unsigned char, which occupies 1 byte.
When you increment a pointer, you always do that by sizeof(pointer type) steps..

[Beauty]

I suppose the vertex buffer and index buffer in inside the RAM of the graphic card.
Is this right?

When I look to the code to read vertices, it works like this:
* get pointer to first vertex
* loop for all vertices
..... * read 1 vertex
..... * move pointer to next vertex

I suppose each time when I apply "read 1 vertex", it's a single access from the CPU to the RAM of the GPU.
In this case it should be very slow to have one access for each vertex.

Maybe it's much higher performance to read whole blocks from the GPU RAM to copy it to the main RAM.
What do you think about?

Here is the related code block from the wiki. (current implementation for vertex buffer access)

Code: Select all

const Ogre::VertexElement* posElem =
    vertex_data->vertexDeclaration->findElementBySemantic(Ogre::VES_POSITION);

Ogre::HardwareVertexBufferSharedPtr vbuf =
    vertex_data->vertexBufferBinding->getBuffer(posElem->getSource());

// pointer to vertex
unsigned char* vertex =
    static_cast<unsigned char*>(vbuf->lock(Ogre::HardwareBuffer::HBL_READ_ONLY));

float* pReal;

// for each vertex
for( size_t j = 0; j < vertex_data->vertexCount; j++)
{
	  // READ VERTEX
    posElem->baseVertexPointerToElement(vertex, &pReal);
    // ...
    
    // MOVE VERTEX POINTER
    vertex += vbuf->getVertexSize();  
}

[Beauty]

An other question related to operation types and rendering performance:

A team mate told me that in current days only polygon lists are used.
The usage of polygon stripts and fans would be outdated.
Common 3D file formats would not use polygon strips/fans (althought it seems to be allowed for the Ogre mesh file format).

He has also the opinion that calculations/rendering with polygon lists would have a better performance than polygon strips and fans. (Although polygon lists need 3 times more memory.)

My team mate has some 3D knowledge, but I don't trust to everything what says.
What do you think about his statements?

[hoppelmoppel]

I suppose each time when I apply "read 1 vertex", it's a single access from the CPU to the RAM of the GPU.
In this case it should be very slow to have one access for each vertex.

Maybe it's much higher performance to read whole blocks from the GPU RAM to copy it to the main RAM.
What do you think about?

Take a look at this code:

Code: Select all

inline void baseVertexPointerToElement(void* pBase, void** pElem) const
{
     // The only way we can do this is to cast to char* in order to use byte offset
    // then cast back to void*.
    *pElem = static_cast<void*>(
    static_cast<unsigned char*>(pBase) + mOffset);
}

It seems that the buffer is not a simple array of floats, where each 3 floats are one vertex. There is some meta data or what ever. Also the pVertexBuffer->getVertexSize() method returns 32 Bytes on my system which indicates also that there is more than the simple coordinates. Of course it should be possible to copy the whole vertex data into the ram, but you would need again to iterate over every element one by one to extract the positions. After copying the buffer you could reuse the code of the baseVertexPointerToElement method in order to reduce some function calls. You could also optimize the code by taking out the

Code: Select all

vertex += vbuf->getVertexSize(); 

calls and read out the vertex size only one time. So I think you should be able to reduce the function calls by 2 * vertex count times. Dunno how much the performance gain would be

This should be also possible for the index buffer. But afaik there you wouldn't reduce the function calls .. you are rather unlocking the hardwarebuffer faster.

BR

[Beauty]

Thanks for sharing your thoughts.

Of course it should be possible to copy the whole vertex data into the ram, but you would need again to iterate over every element one by one to extract the positions.

I suppose that the CPU access to the "main" RAM is faster than access from the CPU to the GPU RAM.
In this case the performance could be better, when I copy a whole block from the GPU RAM to the main RAM and make the single extracts there.
This is my idea. If my suggestion is right, I don't know. If I'm wrong, please tell me.

[hoppelmoppel]

Well, I have absolutly no idea whether you would see any performance increase. I would suggest to load a big mesh and do some testing

[Beauty]

Today I finished the ManualObject detection part of my re-implementation.
For my quick tests I got the wanted results.

Also I applied a performance test. Although there is query to the GPU ram for each single vertex, I got good performance results.
Details:
* 1 ManualObject without indexes
* ~250,000 triangles
* ~250,000 vertices
--> Raycast check for all triangles: ~530 ms
--> about 500 trianges/vertices per millisecond

Well, the generation of the ManualObject needed a very long time and the rendering is very slow.
Also the results will be different on other PCs, but it's nice so see that the performance seems to be verry good.

Now I will extend the code for support of meshes.
Then I can compare the performance of the wiki code with my code.

[Kojack]

An other question related to operation types and rendering performance:

A team mate told me that in current days only polygon lists are used.
The usage of polygon stripts and fans would be outdated.
Common 3D file formats would not use polygon strips/fans (althought it seems to be allowed for the Ogre mesh file format).

He has also the opinion that calculations/rendering with polygon lists would have a better performance than polygon strips and fans. (Although polygon lists need 3 times more memory.)

My team mate has some 3D knowledge, but I don't trust to everything what says.
What do you think about his statements?

Tom Forsyth back in 2006: http://home.comcast.net/~tom_forsyth/bl ... #Strippers
Strips and fans can be better than a triangle list, but not better than an indexed triangle list. The biggest problem is that without directx10 or so, you can only do a single strip or fan per batch. So a model made from several small fans is rather bad for performance compared to a list.

Ogre supports non indexed triangle strips, fans and lists, indexed triangle strips, fans and lists, non indexed line lists, indexed line lists, non indexed point lists, indexed point lists.

[Beauty]

Interesting details. Thanks.

The linked post is related to graphic cards 5 years ago.
Do you know the current state? Do they still need one batch per strip?

Well, I still recognized that the usage of indices is useful.
What's related the performance when you compare indexed lists with indexed strips?
Will indexed strips also need one batch for each strip?

In the future I will use indices for larger ManualObjects.
In the past I didn't know enough about them. Maybe I will add further index related information to the ManualObject wiki page.

[Beauty]

Ok, now I added a few lines to the wiki:

__Notes:__
* For large ManualObjects it's suggested to use __indices__. This reduces redundant vertices in the vertex buffer.
* __Strips and fans__ (without index), also reduce vertex redundancy, but have the disadvantage that they need one batch for each strip. This is bad for performance, especially when there are many short strips.

[Kojack]

There are some ways around it. You can make one strip act as several by using degenerate triangles (infinitely thin) to connect them. So you double up some vertices to break the strip pattern. That doesn't work on fans though.
Apparently in dx10 you can give a special value somewhere and it stops the strip and starts a new one within the same draw call. No idea if that works on fans either.

Mesh Magick has the ATI Tootle lib within it. Tootle can optimise a mesh to get best vertex cache use by reordering your vertices and indices. Getting good vertex cache use can increase performance without changing visual appearance, especially if you have heavy vertex shaders.

[Beauty]

My new casting code also has an option to check terrain.
With my application I only can make tests with the TerrainSceneManager.

What's about ray queries with other terrain related sceneManagers or the new Terrain Component?
Will they give a response by field "worldFragment" of RaySceneQueryResultEntry?
Or instead by field "movable"? (e.g. if the terrain was created as mesh)
If the terrain response is a movable: Is the MovableType "Entity" or "TerrainMipMap" or something else?

[Beauty]

When I wrote my last post I didn't see that you still gave an answer.
You have good ideas.

Nethertheless I still not know one point:
What happens when I use indices?
Will it also cause one batch for each strip/fan?
Or is this disadvantage only related to non-indexed strips/fans?

[Beauty]

Strange behaviour.

I made tests with the sinbad model from the Ogre SDK (without use of animation).
For some unknown reasons, in several cases the common ray query doesn't return a result for the bounding box.
For example the ray goes through the head, but the ray scene query contains 0 results.
Often this happens for the whole head. But when I move my ray origin position, it's possible to find positions, where it's detectable again.

Has anybody an idea what could be the reason?
Remember: This issue is not related to the polygon level. The behaviour happens for the common AABB ray query.

[Blasphemer]

Hey Beauty,

I'm attempting to extend the polygon ray-cast code as well at the moment. I've been trying to get it to work with the ManualObject but I haven't been able to get it to work.

It looks like you're actually dealing with the internal vertices of the ManualObject (through the manual object section) whereas I have been trying to do:

Code: Select all

    var manualObject = entry.movable as ManualObject;
    manualObject.ConvertToMesh("Poo", "General");
    ...

which just explodes violently in a ball of flame and black smoke (i.e. my good old friend, the access violation exception)...

If you could provide me with the code to access the ManualObject directly it would save me some time


EDIT: I just saw you added it to the wiki...
http://www.ogre3d.org/forums/viewtopic.php?f=1&t=67528