Sign in to follow this  
Gumgo

Splitting decals between triangles

Recommended Posts

I'm planning to implement 2d decals but I'm not quite sure how to fix the problem of when a bullet creates a decal along the edge of a triangle. I want the decal to wrap along the triangles it intersects. Static "scene" geometry (walls, floor, ceiling, etc.), which is only made of triangles (no quads or any other type of polygons), is the only type of geometry that I want to be able to receive decals. Here's what I've thought up, but I'm not sure how to do this. (Included in the scene geometry would be a list of edges. Each edge has 1 or two triangle IDs and each triangle has 3 edge IDs.) 1 Create a temporary list of triangle IDs (empty at first). 2 Find the "main" triangle, the one the bullet hits, add to the list. 3 Create a decal (quad) on that triangle. 4 For each edge on the triangle the decal crosses, 5 Find the other triangle corresponding to that edge. 6 If the triangle is on the triangle list already, break, else 7 Add that triangle to the list of triangles 8 Copy the decal to that triangle and, 9 Rotate the decal along the splitting edge such that the decal's normal is the triangle's normal 10 Repeat from step 4 for each edge on the newly selected triangle the copied decal crosses So in pseudocode (sorry if my C++ syntax is weird, been programming in maxscript)
void add_decal_recursive( int tri_id, decal * dec, vector * tri_list )
{
    if (tri_list_contains_tri_id( tri_list, tri_id )) // hehehe...
        return;
    tri_list->push_back( tri_id );
    decal decal_copy;
    for (int i = 0; i < 3; ++i)
    {
        if (!triangle[tri_id].decal_crosses_edge( dec, i ))
            continue;
        next_tri_id = edge[triangle[tri_id].edge[i]].get_other_triangle( tri_id );
        decal_copy = decal_rotate_along_edge( triangle[tri_id].edge[i], dec );
        triangle[next_tri_id].add_decal( &decal_copy );
        add_decal_recursive( next_tri_id, &decal_copy, tri_list );
    }
}

void add_decal( int initial_tri_id, decal * dec )
{
    vector <int> tri_list;
    triangle[initial_tri_id].add_decal( dec );
    add_decal_recursive( initial_tri_id, dec, &tri_list );
}
However this is just a guess, maybe there is a better way to do this. If this way is good, how would I do the "rotate along edge to line up with triangle's normal" step?

Share this post


Link to post
Share on other sites
Find the triangle you hit.
Find all triangles within a radius facing the same direction as the hit triangle.

project them onto the plane of the first triangle.
calculate uv coordinates of your decal.
store the original triangles with the new uv coordinates in a temporary buffer for rendering.

Share this post


Link to post
Share on other sites
Sorry if I interrupt, but I was about to ask the same question some day :) What if the polygons you hit are very big, while the decal should be small? I guess you can cut the polygons off by (everything outside a box or sphere with size/radius X must be removed). But how to do that? A simple example, I'll hit only 1 huge polygon. How to cut out a little box or sphere?

Greetings,
Rick

Share this post


Link to post
Share on other sites
Basiror, I'm not quite sure what you mean, could you explain a bit more? The only way I know of how to do decals is to use the stencil buffer.

Share this post


Link to post
Share on other sites
I think he means:
1.- Check on which polygon you want the decal mapped. Usually you know this because you did collision detection between bullet/polygon or something.

2.- Find 'nearby' neighbour polygons. How you can do this quickly depends on your model structure implementation. Maybe you can find them with the same technique you used for collision detection. Or, store the neighbour polygon(s) for each polygon so you directly access them.
Anyway, you check if that polygon is inside or intersects your decal radius. If a decal is on a corner, there should be at least 1 other polygon very nearby.

You end up with a little list of polygons copied from the original mesh.

3.- Use the main(first) polygon axis for UV mapping. You can find the main axis (X,Y or Z) by checking which component of the normal is "the strongest". Now you can calculate new UV coordinates for the list of polygons. In case axis is X, the most left Z point will get texcoord.u = 0, the most right Z coord texcoord.u = 1, top y coordinate will get texcoord.v=0, and the bottom texcoord.v = 1. Interpolate everything in between.


Maybe I missed something or understood "project them onto the plane" wrong, but 1 thing is missing here, and there is 1 little problem. First, I think there should be a step between 2 and 3 that cuts off big polygons. In case you hit a gigantic wall, you don't want such a big decal mesh. Either we modify the decal mesh, or we only render the center pixels and adjust the uv coords. Second problem is that you texcoords will be stretched out around the corner. Although you see this often in games (Doom3 for example), so maybe we find it acceptable.

I'm curious. I need to build a decal 'paster' soon as well. Help us! :)

Greetings,
Rick

Share this post


Link to post
Share on other sites
Ok again.

You have hit a triangle, find its neighbours and their neighbours' neighbours and so on that are inside/touching the bounding sphere of your decal

Now you project all the triangles onto a common plane, maybe spanned by the nearest vertex+normal

and calculate the uv coordinates.

If you got large triangles, you can clip them using the radius of the bounding sphere

The algorithm looks as follows:

a) Find two intersections of adjacent triangle edges with the sphere
b) Get the line between the two intersections(I1,I2) and calculate its normal facing away from the sphere origin

deltaSphere = sphereorigin -I1;
tempNormal= cross(deltaSphere,I2-I1)
clippingplaneNormal = cross(tempNormal,I2-I1)

c) Now calculate the distance D between the line/clipping plane and the sphere origin
d) move the line/clipping plane further away deltaD units, deltaD = Radius-D.
Radius > D in any case.
Just adjust the distance component of the plane equation by deltaD
e) clip the triangle against the new clipping plane

This will result in a polygon that has to be triangulated in the end and can be used to calculate the uv coordinates.


The reason we shift the clipping plane is to guarantee that the whole surface area inside the sphere is covered.

Share this post


Link to post
Share on other sites
hmmm... I understand the polygon/neighbour picking part and howto generate UV coordinates. But I don't see how the clipping works for big polygons:
http://img509.imageshack.us/my.php?image=decalspb3.jpg

When checking intersection points in the picture situation, I can find 2 on each polygons... How to create a (circle shaped) decal with that?

A long time ago, I read somewhere a similiar approach, but then people suggested to use a box for clipping, like you can see on the right in this picture. Sounds fine, but how to clip with a box in that case?

By the way, is it just me, or is it really hard to find demo's on this topic? There are difficult mathematical papers, describing how to map stuff on non-convex polygons, but a "simple" demo can't be found. That's odd, because quite many programs/games are using it I think.

Greetings,
Rick

Share this post


Link to post
Share on other sites
The main poly won t be clipped since the clipping plane from step d) does not touch the triangle

Neighbour1 will be clipped to a rectangle

You always clip away the part that is on the front face of the clipping plane. The sphere origin is always on the back

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this