Triangle clipping, decals

[belfegor]

In order to create decals i think i need to cast bbox onto my tree collision (level) using NewtonTreeCollisionGetVertexListIndexListInAABB function on point where my ray hits.
Now, since most of my decals is small (like bullet holes) i would like/need to clip these triangles to bbox extent, but since i am not math wizard this is hard problem to solve.
I see in source folder "meshUtil" there is dgMeshEffect class, and according to function names that might help me with my problem:

Code: Select all

...
dgMeshEffect* Union (const dgMatrix& matrix, const dgMeshEffect* const clipper) const;
   dgMeshEffect* Difference (const dgMatrix& matrix, const dgMeshEffect* const clipper) const;
   dgMeshEffect* Intersection (const dgMatrix& matrix, const dgMeshEffect* const clipper) const;
   void ClipMesh (const dgMatrix& matrix, const dgMeshEffect* const clipper, dgMeshEffect** const top, dgMeshEffect** const bottom) const;
...


Is this interface fully working?
Could you PLEASE advise me, possible with some short code snippets how to use it to achieve what i want?

Thank you for your time.

[belfegor]

Bump.

With all due respect, Julio i hope you are well and in good health since i see less and less activity from you on this forum. God bless and keep you safe.

[Julio Jerez]

you have a box and you want to collect the face of a collision tree that interest that box.

what do not get is what you want to clip against against those faces, I am confused can you explain it again.

MeshUtil is no designed to be use in real time. you will have to build a mesh for the face of the tree interesting the aabb, but mesh util has a high cost for building a mesh.
There are simplex way to make the decal without having to clip face.

can you please explain it again maybe with an image.

[JoeJ]

I think what you wanna do is - let's call it 'old scool decals' ?

If you already have a list of convex polygons approx. intersecting your 'clip-box' (given by newtonGetAABB stuff f. ex.) you can do that like this:
1. Convert your clip box to six planes.
2. Use simple polygon - plane clipping to clip the scene polygons against all 6 planes in sequence.
3. Generate texturecoords for the remaining clipped polys and render.

For step 2 see example code: http://newtondynamics.com/forum/viewtopic.php?f=9&t=6785&p=47228&hilit=michael#p47228
Example code defines a plane as direction vector plus a distance value from origin to plane in that direction.
It works by cutting edges in relation to the distance from both vertices to the clip plane.
May sound complex, but it's easier than you might think


However, while this is realtime, today it might be faster to do:
Get hit point and normal by raycast and render a single quad, but clip pixels by shader if the z difference is too large.

[Julio Jerez]

well what I would do is this.
-Get the faces using the face in aabb, of the decals
-the for each face on the found on the aabb scan, calculate the project UV of the decals on the face
-if at lies one of the UV is in the triangle then that triangle is par of the decal to be rendered. is no it is filter out
this will lead to a set of face they will match the face that was rendered as the background, and has also the effect that removed z buffer fighting.
the clipping is generated at the UV coordinate at texture level but the GPU

this algorithm soudl be quite simple top implement, and I am guessing it will even render fewer fact that a clipping base method.

[belfegor]

@JoeJ
In the meantime i have found similar function to yours that clip convex poly with a plane. I am currently experimenting how i can go about this.
I think i must do something like this:

Code: Select all

NewtonTreeCollisionGetVertexListIndexListInAABB (...); // get tris in aabb

vector< Tri > vDecalTri;
for each triangle
    for each bbox plane {
          clipConvexTriOnPlane(inVerts, outVerts)
         
           assert( outVerts.size() >= 3 )
           vector< Tri > vTri;
          for ( i =0; i < outVerts.size() - 2; ++i )
                Tri t;
                t.v[0] = outVerts[0]; // start at first vertex and make trianngle fan
                t.v[1] = outVerts[i+1];
                t.v[2] = outVerts[i+2];
                vTri.push_back(t)
    }
vDecalTri.insert( vDecalTri.end(), vTri.begin(), vTri.end() ) ; // append to final triangle vector
         


Or you have better idea?

However, while this is realtime, today it might be faster to do:
Get hit point and normal by raycast and render a single quad, but clip pixels by shader if the z difference is too large.

That would look ugly.

@Julio

-the for each face on the found on the aabb scan, calculate the project UV of the decals on the face

I tried with projected coords (without clipped vertices) but it is stretched where angle difference is big and looks ugly:

[JoeJ]

Clipping is more efficient with polygons, you should work with them and convert to triangles when all planes are done.
Something like:

Code: Select all

vector<tri> trinagle
vector<tri> decals
polygon a, b; // i once figured out the max. vertex count for a clip box but forgot - <vector> slows down - fixed size array is fast
polygon *pa =&a, *pb = &b;
bool outside = false
for each triangle
{
  pa->FromTriangle(triangle)
  for each plane
  {
        ClipPolyByPlane (pb, pa, plane)  // pb = clippend, pa = source
        if (pb->numVertices < 3) {outside = true; break;}
        swap (pb, pa)
  }
  if (!outside) AddTrianglesFromPolyToOutputVector (decals, pa)
}


My thoughts on the 3 methods:

Julios: if you fire 20 bullets on a big polygon, you need to render big polygon 20 times? fillrate consuming
To avoid stretch, skip triangles if fabs(dot(hitray, trinorm)) < threshold

PolyClip: CPU consuming

Shader: Z-fighting - usually 3D APIs offer a way to set a Z tolerance, you can also fake offset in shader
if Z-Buffer stores far/Z, constant tolerance should do, if it stores Z directly, it should grow with distance
To overcome issues like: Hitpoint near edge - decal only on one poly but it should be on two...?
You can draw a screenspace box, compute uv per pixel like in screenshot, and blend by distance from hitpoint plane.
You could even use 3D texture for decal to allow larger distance without stretched look - cool.

[belfegor]

I am sorry but you are bit unclear to me. Please treat me like a baby when explaining things.

Clipping is more efficient with polygons...

Polygon is a triangle or a set of adjacent triangles with same normal (flat surface)? Right?
If so should i then split triangle soup into groups of polygons before sending to clipping function? I don't see it now how to do it, and it might end up difficult, note that i will try my best.

i once figured out the max. vertex count for a clip box but forgot - <vector> slows down - fixed size array is fast

Is it possible then to predetermined (safe) max tri count so i can reserve some space instead allocating all the time?
Please, since you mention that you knew once, can you do it again and help me out?

Thank you for your time and patience.

EDIT:

Julios: if you fire 20 bullets on a big polygon, you need to render big polygon 20 times? fillrate consuming

Exactly.

[JoeJ]

"Clipping is more efficient with polygons..."

I sayed that because looking at your code i thought you take the polygon output form the plane clipping,
convert it to triangles, and clip all those triangles with the next plane.
I may got you wrong but the point is:

You clip a triangle by the first plane, output is a polygon with 4 vertices (worst case).
You can proceed with the next plane either by making 2 triangles from that polygon and do double the work, or better: Continue with the polygon as is.
That's why i simply swap the polygon pointers to use output from previous step as input for the next step.

This also should allow us to calulate the maximal vertex count the polygon needs to allow clipping a triangle against 6 planes.
If each plane can add one vertex at most, max count should be 3 + 6. (not sure 100%)
So, if you make your polygon struct like this:

struct polygon
{
vertex v[9];
int numVertices;
}

... it should be enough to allow box or frustum clipping triangles in any case.

There's surely no need to fuse adjacent trinangles to polygons before the process,
just create a 3 point polygon for each triangle.


I have the impression you tend to overuse std::vector.
If you would do this:

struct polygon
{
std::vector <vertex> v;
}

... what happens in the worst case is that for each vertex you add the array needs to be copied all over.
That's let's guess 3 x slower than it needs to be - if all that happens on the stack.
But if it happens on heap, the slowdown can become huge.

Take that with a grain of salt - i'm oldscool and things may have changed... there are surely lots of test cases where you could proove me wrong.
But there are also surely cases where difference IS big, soo keep it in mind

[belfegor]

Thank you for your help so far.
I will try this in next couple of days when i get free time off the job and probably come here for more tips if i don't succeed.

[Julio Jerez]

Julios: if you fire 20 bullets on a big polygon, you need to render big polygon 20 times? fillrate consuming
To avoid stretch, skip triangles if fabs(dot(hitray, trinorm)) < threshold
PolyClip: CPU consuming

That's is no what I meant.
here is more detal.

say you have a decal manager tha keeo track of every decal on the screen.
each decal point to a list of faces that it touched.

each time a Face is affected by a decalm, you add a new facr teh list of faces tha nee to ne rendered.
you also save a render to texture image of the face.
there you produce an texture that containt the image of the decal, tsho tetirue is genertaed each time any decal changes.
all of the clipping si doen by UV tricks, and all you do is rendring lot of small texture to a larger one.
The texture will have on bullte, the two bullets, and so on

Julios: if you fire 20 bullets on a big polygon, you need to render big polygon 20 times? fillrate consuming

not, you render the 20 bullets using UV shifting 20 time to an off screen image. but those 20 time do no haven in the same frame
it only happen each time the offcreeen decal is touche by a new bullet or a new bullet is remioved.
In fact I wodul no even bother cleaning old bullet hole holes.

then you render the poligon wit the exact same poligon faces twice.

Basically you cna generalize the compelet featore like this,
you make a secung mesh of the object that you wna to render.
the secund mesh have all the UV set to zero.
each face o fteh buidledn have a assigned texture tah is blank

each time a decal touches a face, you figer out when on teh face teh decal is to be rendered, you find that texture and you render that decal to thar texture. the you add that face to the displalist
The you simply render that display list with some alpha blended or some blend shader.
no where you need to do any clipping.