Unfolding
First the model must be unfolded into 2D space. We must maintain the proper
area relationships and prevent any form of overlapping in the 2D space.
To do this, the project loads the model into a BREP, selects a starting face
for a chart, and then progressively grows the chart by unfolding faces that
are connected to the chart. It only adds those faces to the chart which don't
cause overlaps in the 2D space. This process is repeated until all of the
polygons from the model are in a chart.
The images to the right show various charts. Purple lines are bounding boxes
and blue lines are convex hulls of the charts.
The challenge to this stage is building as few charts as possible using as
many faces as possible, while maintaining high density charts. The
images to the right illustrate that some charts have quite a bit of dead/unused
space. Phase 2 of the project will address optimization of the charts to
minimize this.
Packing
Once the model has been unfolded, the charts need to be packed into the
space of the final textures. To achieve this, the project rotates all the
charts such that their maximum diagonal is vertical, and then sorts them
by decreasing height.
The first algorithm developed for packing was a simple algorithm where it
would incrementally work across the texture space adding the next smallest
chart. If it didn't fit, we would proceed to the next line where it was
guaranteed to fit. Each row would alternate between packing them in lefttoright order.
and packing them in righttoleft order. This allows a bit better compression,
which was the next step. It compressed the packing by sliding the newly placed
chart down until it would intersect the charts below it, then backed it off.
This helped optimize some of the utilization of space.
The 3rd image on the right illustrates the packing for a helicopter model. It
packed it fairly well but it wasn't able to use as much of the space as we had hoped.
Notice how the upper right corner is empty.
To fix these problems, a different packing algorithm was developed. The new
algorithm keeps a skyline of the bounding boxes of currently packed charts. It is
quickly able to find the best span in the skyline that would fit the next chart
to be added. In the 4th picture, it can be seen that the same helicopter model now
packs much nicer. In that image, the current skyline is drawn in green. The skyline
technique is extremely fast.
