Overgrowth takes place in the savage world of Lugaru where rabbits, wolves and other animals are forced to use paws, claws and medieval weaponry to engage each other in battle. Combining 3rd person adventure platforming with intricate melee combat, Overgrowth achieves a unique feel. Overgrowth also benefits from Wolfire's brand new Phoenix Engine which has been built from the ground up to allow the use of cutting edge graphics, animation, and physics. Add to these exciting features Overgrowth’s realistic artificial intelligence and streamlined control system and the result is an astoundingly immersive experience.

Report article RSS Feed How to project decals

This is a technical explanation of how decals are actually projected geometrically onto complicated objects.

Posted by jeffr on Jun 24th, 2009

We've been talking a lot about decals recently, showing off our editor and explaining how the shading works. However, we haven't explained how the decals are actually projected geometrically onto complicated objects. We've been getting some questions about that, and I remember how hard it was to find information about decals when I was getting started, so here's an overview of the decal projection algorithm I created for Overgrowth. Let's start with this scene here.

Decal

It's a bit too clean for me... I want to add a decal to give it some subtle weathering. To place a decal, I need to first set up the projector. The projector is just a 3D rectangular prism with three properties: size, position, and orientation. Of these, the orientation can be the most confusing. For decal projectors, I represent the orientation as an orthogonal basis, which is a set of three vectors that are all perpendicular to each other. For example as the XYZ axes form an orthogonal basis, as do 'forward', 'up', and 'right'. This gives us a complete orientation in 3D space, and is easier to think about than matrices and quaternions.

Decal

The secret to projecting decals is to not think about creating a mesh that conforms to the model. Instead, think of it as starting with the model, and cutting away everything that is not in the projector box. I found that thinking of the problem like this made it easier to figure out what to do. Let's start by checking which triangles in the scene intersect with the decal projector. I first implemented this in a brute force fashion, and once that was working, changed it to work hierarchically using octrees [to bring the runtime from O(n) to O(logn)].

Decal

Next is the hardest part: we have to crop the triangles so that they don't extend out from the projector. Why is this important? Think about firing a thousand machine gun shots at a wall that is made of just two triangles. If we don't crop our bullet holes, we will have to draw the entire wall a thousand times! Since the wall is so much bigger on the screen than the bullet holes, this will use up too much fillrate, and bring the framerate to a crawl. However, with decal cropping, I can do this and maintain maximum framerate!

So now that you're convinced that decal cropping is important, how do we actually do it? Cutting arbitrary 3D triangles to fit in an arbitrary 3D box is a daunting task. To make it easier, I thought about it in 2D. We can transform the triangles from world space to projector space, crop them, and transform them back. This makes the problem much simpler. In projector space, the projector box is just a square from (0,0) to (1,1), like this:

Decal

A triangle in projector space might look like this:

Decal

So now all we have to do is crop the triangle to fit in the square. This seems like a tricky task itself, but we can break it down even more. First, we can start with one border at a time. Let's pick the left border. To crop the triangle, we start by marking every vertex in violation of the rule -- in this case, the leftmost one. Then we look at every line between a marked vertex and an unmarked vertex, and add a vertex at the point at which it crosses the border.

Decal

We can then simply remove the marked vertex (or vertices), and move onto the next border.

Decal

Once we've checked all the borders, we have a cropped triangle!

Decal

After doing this for every triangle, and projecting back into world space, we have a cropped decal mesh.

Decal

If we keep track of each vertex's coordinates in projector space, those are also the projected texture coordinates! That's why I set up the projector space to be (0,0) to (1,1) -- that's the range that OpenGL uses for texture coordinates. Here's what the decal looks like using those texture coordinates on a test texture.

Decal

Now we can just substitute in our real decal texture, and we're done!

Decal

Here's the original camera angle with the finished decal applied. It's a pretty subtle effect, but I think the extra detail helps make the damaged area look more realistic -- nothing would be able to take a huge chunk out of that block without scuffing up the surfaces around it.

Decal

So that's an overview of how decal projection works in Overgrowth! If you're not familiar with linear algebra, you might be confused about how to transform triangles from one space to another, and why it's important to have a complete orientation. I could write a blog post explaining vector spaces and transformations in game development terms, but I'm not sure if anybody would be interested. Do you have any other technical subjects you would like me to talk about?
(permalink)


Track us on ModDB (see our cool page)
and also join:
- Facebook
- Steam
- Twitter
- YouTube

Post comment Comments
chris_sloany
chris_sloany Jun 24 2009, 2:42pm says:

blew right over my head! lol. but cool, i never knew how much complicated thinking would have to go into making something like that. but

+3 votes     reply to comment
calmflow
calmflow Jun 24 2009, 3:57pm says:

Where Babies come from? Joking.

Great article though, i'm sure many beginners and indie developers will appreciate that article.

+2 votes     reply to comment
Jupiter
Jupiter Jun 24 2009, 4:11pm says:

Now I remember why I screwed up my linear algebra exam last week :P

+1 vote     reply to comment
Armageddon104
Armageddon104 Jun 24 2009, 5:05pm says:

Amazing! So much work!

+1 vote     reply to comment
mflux
mflux Jun 24 2009, 6:33pm says:

"I could write a blog post explaining vector spaces and transformations in game development terms, but I'm not sure if anybody would be interested. Do you have any other technical subjects you would like me to talk about?"

Hell Yes

+2 votes     reply to comment
Dra6o0n
Dra6o0n Jun 25 2009, 1:24am says:

I looked and compared the pictures but I don't notice any significant changes???

+1 vote     reply to comment
jeffr Author
jeffr Jun 25 2009, 1:45am replied:

The second one has the decal the article is talking about projected onto it. :)

+1 vote   reply to comment
Eagle0600
Eagle0600 Sep 10 2009, 9:10am replied:

I can see it, and it's an amazing effect.

+1 vote     reply to comment
vfn4i83
vfn4i83 Jun 25 2009, 10:26pm says:

I've been interested in that engine for a long time, but just got in love since the first time I see that Wolf Symbol projected into the objects.

Great work.

+1 vote     reply to comment
SinKing
SinKing Jun 27 2009, 9:10am says:

It's not in your mod profile. Somehow the link is missing or I cannot find it there.

EDIT: I see why - I was looking for it in video tutorials, because I thought I had watched a video about this. Must have been a dream...

+1 vote     reply to comment
karyudo
karyudo Jul 14 2009, 11:07pm says:

Seriously...this sort of feature (if resource friendly) should be in every editor out there!

+1 vote     reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Icon
Overgrowth
Platforms
Windows, Mac, Linux
Developer & Publisher
Wolfire Games
Contact
Send Message
Official Page
Wolfire.com
Release Date
TBD
Game Watch
Track this game
News
Browse
News
Report Abuse
Report article
Related Games
Overgrowth
Overgrowth Single & Multiplayer Adventure
Related Engines
Custom Built
Custom Built Commercial Released Sep 1, 2007
Related Groups
Wolfire Games
Wolfire Games Developer & Publisher with 3 members