Overgrowth is an awesome indie game! We're four guys working more than full time on this until it's done. We hope you will follow our development on ModDB and on our blog! We update our blog every day: click here to subscribe.

Image RSS Feed Latest Screens
Translucent Plant Shader Initial Screenshots Initial Screenshots
Blog RSS Feed Report abuse Latest News: Triangle Mesh Voxelization (aka LEGO rabbits)

19 comments by jeffr on Dec 4th, 2009 digg this super bookmark


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?



Track us
on ModDB (visit our page)

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

Media RSS Feed Latest Video
Downloads RSS Feed Latest Downloads
Overgrowth Spray For Source Games

Overgrowth Spray For Source Games

Jul 29, 2009 Sprays 7 comments

If you feel like promoting your favourite indie game while playing your favourite Source game. To use it: unzip the file, start your Source game, press...

Overgrowth Main Theme

Overgrowth Main Theme

Jan 14, 2009 Full Version 1 comment

Music for the upcoming sequel to Lugaru: The Rabbit's Foot.

Comments  (10 - 20 of 293)
hero_kenshin
hero_kenshin Nov 17 2009, 11:20pm says:

How long has it taken you to make you engine.

can i has it ?

Hahah kidding :P

+4 votes     reply to comment
0bas0
0bas0 Nov 14 2009, 2:19pm says:

Euphoria, will probably become middleware in some years when other companies will make software that is like euphoria, but that will take some years ;)

+4 votes     reply to comment
Dra6o0n
Dra6o0n Nov 19 2009, 9:04am replied:

You do know that technology is much faster than you expect it to develop? With some slow and fast speeds goings on, the results are unexpected.

In less than one year, Euphoria will be outdated already...
In under 3 months, technological advances will be a heap of times better than before... It's just the physical aspect of it being developed, as we humans are too clingy to our money...

and to top it off:
YAY for Open Source industries!
Double YAY for freebies!

+1 vote     reply to comment
Nebcake
Nebcake Nov 9 2009, 8:44pm says:

That will look awesome if you managed to get some of the your concepts into the game

+3 votes     reply to comment
jeffr
jeffr Nov 9 2009, 10:03pm replied:

We are too small to get our calls returned by distributors at the moment. :( Maybe once we have made more of a name for ourselves though!

+3 votes     reply to comment
Necromunger
Necromunger Nov 18 2009, 3:42pm replied:

you could sell it over steam

0 votes     reply to comment
revengous
revengous Nov 12 2009, 10:42pm replied:

too small? your the 1 game I want right now =D

screw MW2, Overgrowth FTW!

+3 votes     reply to comment
Arthasz
Arthasz Nov 13 2009, 9:08am replied:

i agree. screw MW2 :D.

+3 votes     reply to comment
Darthlex
Darthlex Nov 14 2009, 2:17am replied:

Agreeing to agreeing

+4 votes     reply to comment
Feillyne
Feillyne Nov 16 2009, 8:30am replied:

Long live indies!

+2 votes     reply to comment
Post a Comment

Only registered members can share their thoughts. So come on! Join the community today (totally free) and do things you never thought possible.

Icon
Overgrowth
Platforms
PC, Linux, Mac
Developer & Publisher
Wolfire Games
Engine
Custom Built
Contact
Send Message
Official Page
Wolfire.com
Release Date
TBD
Game Watch
Track this game
Bookmark
Digg Super bookmark
Style
Genre
Adventure
Theme
Fighter
Players
Single & Multiplayer
Project
Indie
Boxshot
Boxshot
Statistics
Rank
39 of 1,321
Last Update
3 days ago
Watchers
968 members
Addons
1
Files
1
News
91
Features
8