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 Triangle Mesh Voxelization (aka LEGO rabbits)

In my recent post on automatic skinning, one of the steps involved creating a voxel representation of the character. I couldn't find any explanations of how to do this on the Internet, so I decided to write my own!

Posted by jeffr on Dec 4th, 2009

In my recent post on automatic skinning, one of the steps involved creating a voxel representation of the character. I couldn't find any explanations of how to do this on the Internet, so I decided to write my own!

What is a voxel?

"Voxel" is short for "volume pixel". A pixel is a single square in a 2D image, and a voxel is a single cube in a 3D lattice. Voxel models are useful in games because they aren't hollow like triangle meshes are, so we can use them for 'deep' physical simulations such as heat diffusion, fracture, and soft physics. I used voxels extensively when working with Alec Rivers to visualize his RealMatter technology, and when testing out destructible cover for an unreleashed shooter project.

Here is the example model that I used for the previous post again -- the triangle surface is on the left, and the voxel model is on the right.


So how do we make a voxel model?

A voxel model is a bounded 3D grid, so the first step is to decide its basic characteristics. How big is each block, and what are the dimensions of the grid?

The size of each block depends on what you need it for -- in this case we are using it for attaching the mesh to the bones, so we only need enough resolution to make sure that important details like the mouth and fingers are not lost. Let's say each block is 1 cubic cm in size.

The dimensions of the grid have to be big enough to fit the entire model, but no bigger (to avoid inefficiency). This is fairly simple -- we can just set the dimensions equal to the size of the bounding box of the surface triangles (the smallest box that encloses every point) rounded up to the nearest centimeter. Here's a picture of the voxel grid:


Now we have to decide which voxels are solid (intersecting the model), and which voxels are not. The method I used is a two-step process. First, we solidify a shell representing the surface, and second, we fill it in using a scanline fill algorithm. This is most clearly illustrated by looking at a single slice -- first we have just the triangle surface, next the voxel shell, and finally the filled voxel model.


Calculating the shell is pretty straightforward. For every triangle, I check every voxel in the triangle's bounding box to see if it intersects. If it does, the voxel is made solid.

Filling the shell is a little more complicated. We can see this best by looking at a single row as it's filled in. You can think of a pen scanning from left to right that goes down to the paper when it hits an outside edge and raises again when it hits an inside edge. We start out on the left with the pen up, shown here as a green square.


There is no surface here and the pen is up, so we just move onto the next square without changing anything.


Here there are some intersecting surface triangles! We send a horizontal ray from left to right through the center of the voxel to see what it intersects. If the last triangle it intersects is facing to the left, then we lower the pen. Otherwise, we keep it raised.

Here is a close-up of this voxel. The small white lines represent the triangle normals (which way is 'out').


The last (and only) triangle that the pen intersects faces to the left, so we lower the pen! Here we illustrate that by changing the pen from green to red.


Since the pen is down, it fills in empty voxels as it steps to the right.


This process continues until we get to the next intersection. Fill, step to the right. Fill, step to the right.


Here's a close-up of this intersection test. The rule is the same as before: If the last triangle the pen intersects is facing to the left, then we keep the pen lowered, otherwise, we raise it up.


In this case the last (and again, only) triangle is facing to the right, so we raise the pen.


As it keeps moving out of the model, the pen is raised, so it fills no voxels. When we repeat this process for every row, the whole slice is filled in!


Here is a 3D view of half of the model: first, a surface slice, next, the voxel shell, and finally, the filled voxel model.


That's all there is to it! I hope this helps you use voxel models in your own projects. Do you have any ideas about better ways to voxellize triangle meshes, or any questions about how this works?(permalink)



Track us
on ModDB (visit our page)

Please join us here too:
Facebook icon ModDB icon Steam icon Twitter icon YouTube icon

Post comment Comments
Killer_man_1996
Killer_man_1996 Dec 4 2009, 9:15pm says:

OMG i love the link with that demostration...

it sounds cool for physics simulation

+5 votes     reply to comment
Nebcake
Nebcake Dec 4 2009, 9:30pm says:

Wow that looks awesome

+5 votes     reply to comment
Warrow
Warrow Dec 4 2009, 9:45pm says:

That's really cool, but... What's the point? :D

+3 votes     reply to comment
Silverfisk Creator
Silverfisk Dec 4 2009, 10:16pm replied:

"In my recent post on automatic skinning, one of the steps involved creating a voxel representation of the character. I couldn't find any explanations of how to do this on the Internet, so I decided to write my own!"
Quote from the first two sentences of this post. :P

+5 votes   reply to comment
Fragvergnugen
Fragvergnugen Dec 5 2009, 1:37pm replied:

If you wanted, you could voxelize a 3D model and use it in a voxel-based graphics engine. Like this one:
Voxelstein3d.sourceforge.net

+1 vote     reply to comment
gokusuper5
gokusuper5 Feb 11 2010, 9:43am replied:

Hmm could use this to cut bunnies...GORE FTW!!!

+1 vote     reply to comment
thefrog
thefrog Dec 4 2009, 11:05pm says:

So this is must how they predict those big *** lego things...

Tricky bastards

+5 votes     reply to comment
Darkbladecr
Darkbladecr Dec 5 2009, 6:25am says:

looks like a lot of work for one model, but I'm sure the results are amazing :)

+1 vote     reply to comment
Cryrid
Cryrid Dec 5 2009, 8:58am says:

This might be useful and quite the time saver for smaller or minor characters, but I think I'd prefer the degree of control weight editing gives (especially for main / important characters). It only takes 1-2 hours, and ends up being worth it

+1 vote     reply to comment
ShinobiNFC
ShinobiNFC Dec 5 2009, 11:38am replied:

well you always have to start with an initial skin job that you refine. I would much rather start with this implementation than the default weighting in max or XSI.

+1 vote     reply to comment
Cryrid
Cryrid Dec 5 2009, 2:52pm replied:

Even the default values a 3d app provides doesn't take long to fix. Pose, select an area, slide the value until its right. Voila. Again I can see it being helpful for certain characters, but for others it seems like it would be far easier / faster (more control) to set up and refine traditionally.

+1 vote     reply to comment
Kamikazi[Uk]
Kamikazi[Uk] Dec 5 2009, 9:36am says:

Always really tackle the complex programming head on great job again.

+1 vote     reply to comment
Ekonk
Ekonk Dec 5 2009, 11:20am says:

So what we're seeing is a mega-detailed hitbox, or am I wrong? Never heard of voxelization before, so I don't know.

+1 vote     reply to comment
Croco15
Croco15 Dec 5 2009, 12:56pm says:

Cool.

+1 vote     reply to comment
AlekZanDer
AlekZanDer Dec 5 2009, 1:27pm says:

This is something really annoying while you are making it.

+1 vote     reply to comment
Minuit
Minuit Dec 5 2009, 6:34pm replied:

Lol?

+2 votes     reply to comment
eXeC64
eXeC64 Dec 5 2009, 2:20pm says:

Good job!

+1 vote     reply to comment
Orac|
Orac| Dec 6 2009, 3:43am says:

Interesting link. Will Overgrowth use any form of "destructible cover"? It definitely looks like fun to damage the game's environment further than the usual splatters which are common place in FPS, RPG, and most other forms of dramatic gameplay.

+2 votes     reply to comment
ShinobiNFC
ShinobiNFC Dec 6 2009, 9:50am says:

This is awesome information, I'm loving these articles.

+1 vote     reply to comment
Ichiman94
Ichiman94 Dec 6 2009, 12:59pm says:

trianglemesh collision is smother than blocky voxelcollision

+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