PolyPainter: Direct model painting

Project Description

Texture maps are often used to enhance the appearance of 3D models. One of the difficulties in creating good texture maps is having to edit the two-imensional texture map in its native form and then rerendering the model to see how it has changed. It would be much simpler if you could paint directly on the 3D model rather than deal with the 2d texture map.

The main goal of this project was to create a working model painter, so texture maps could be painted onto the model directly. It would also need to be able to load models and texture map information from some common file format. It uses the MD2, or Quake 2, file format since it's simple, common, and is well documented on the internet.

Algorithms

The key algorithms involved served two purposes, quickly determining which triangles to paint, and accurately painting those triangles. The collision detection methods are pretty standard and were derived from other internet sources. The painting algorithm was not, so I'll go into more depth on it.

Collision

The first part of painting the model is of course figuring out which triangles to paint. Since the models are relatively simple game models, no fancy space division was neccessary. Collision detection then takes place in 3 steps of increasing cost:

1. First comes a quick comparison of the distance between the triangle and the brush, and the sum of their diameters. To facilitate this each triangle's centr and diameter (distance to the furthest vertex) are stored.
2. For any remaining triangles, the distance from the triangle's plain to the center of the brush is computerd. If this distance is greater than the brush's radius they does not intersect.
3. Finally the point on the triangle nearest to the brush is computed. This breaks down into three cases:
   • The interior of the triangle. The point on the plane nearest the brush is easy to calculate, just translate back along the plane's normal by the distance between the brush and the plain. Then sum the angles between each pair of vertexes in the triangle, if the sum is 2PI the point is inside the triangle, and the brush intersects it (sice we already know its sufficiently close to the plane.)
   • Along an edge. For each edge find the point along the ray between the vertexes that's nearest to the brush, then the distance from that point to the brush.
   • The triangle vertices. This can be done with edge calculation, by being sure to limit the nearest point on the ray to a point along the edge, not beyond either vertex.

Once it's determined that the brush intersects a triangle, it must be determined which pixels in the texture map to paint.

Painting

The painting algorithm basically involved iterating over the u,v coordinates in texture space, mapping those coordinates to x,y,z space coordinates, and checking the distance from that point to the brush.

The complete steps involved in the algorithm are:

1. First determine the minimum and maximum u,v values, and the points (in 3-space) that correspond with the u values (min,mid, and max).
2. Determine the step size for the iteration, based on the range in u or v and the texture's width or height respectively.
3. Iterate from u_min, to u_max, by u_step, for each step interpolate along the line u_min to u_max, and either u_min to u_mid or u_mid to u_max depennding on the current value for u.
4. Iterate between the interpolated v values and interpolate actual (x,y,z) coordinates.
5. Check the interpolated coorinates for intersection with the brush, and if so paint the pixel (u*texture.width, v*texture.height).

Results

The resulting program works quite well. The model painting works very well, proviing the alternative means of painting a models textures that I set out to do. That's not to say its perfect though, there are some shortcomings as well.

Since movement of the brush is limited to the plane perpendicular to the screen, painting a model can be fairly tedious, as the model must be constantly rotated to get the brush into the desired position. Just adding aditional views could greatly help with this problem, or alternative ways for painting, such as a ray-tracing spray painting type of methodology, or automatically having the brush move along the surface of triangle once it has contacted it.

Only a spherical brush is supported. I had originally wanted to have many different brush shapes, but the time to implement the aditional colision algorithms made that an impossibility.

The painting algorithm sometimes fails to paint some pixels on the edge of triangle, while also sometimes painting a shared edge pixel twice (once for each triangle). This could probably be fixed with some minor adjustment to the stepping or interpolation in the painting algorithm. Again time did not allow for this fine tuning.

Future Work

Well some of the shortcoming outlined above could make a decent project. A ray-casting based painter might have nice results and would be fun to compare.

Conclusions

In the end, it is a working model painter. Which is exactly what I set out to do. It still takes a long time to texture a model, probably longer since most paint programs have some nice features this things missing, but its a lot more fun.

References

• flipcode's Basic Collision Detection
• Real-Time Rendering's Object/Object Intersection
• David Henry's MD2 File Format article
• Polyccount's Quake 2 Models(including Suit pictured above)

Downloadables

Source

Available upon request (IOW didn't have time yet to clean it up / put in the license statements)

Binary Blob

• Linux x86