# Triangle Packing-Problem

Theory and Question

We define a normalized triangle $T$ as an ordered list of six points s.t. $p \in [0,1)$ for all $p \in T$.

Let $T = [x_0, y_0, x_1, y_1, x_2, y_2]$ be a normalized triangle. We can then define the function $$f_T : M(\mathbb{N}) \times (0,1]^3 \rightarrow \mathbb{N}$$ $$f_T(A, w_0, w_1, w_2) \mapsto A\Bigg[ \bigg\lfloor\frac{x_0 w_0 + x_1 w_1 + x_2 w_2}{w_0 + w_1 + w_2} m\bigg\rfloor, \bigg\lfloor\frac{y_0 w_0 + y_1 w_1 + y_2 w_2}{w_0 + w_1 + w_2} n\bigg\rfloor \Bigg]$$ where $A[ \cdot, \cdot ]$ refers to the corresponding entry in the $m$-by-$n$ matrix $A \in M(\mathbb{N})$.

Given a finite set of matrices $\mathcal{M}$ and for every matrix $A \in \mathcal{M}$ a normalized triangle $T_A$, find an $m$-by-$n$ matrix $B \in M(\mathbb{N})$ with $\max(m,n)$ minimal, so that there exists a normalized triangle $T_A^*$ for every $T_A$ s.t. $$f_{T_A}(A, w_0, w_1, w_2) = f_{T_A^*}(B, w_0, w_1, w_2) ~~ \forall ~ w_j \in [0,1), ~ j = 0,1,2$$

The problem can be solved by brute force. However that will be incredibility slow. I'm looking for a clever idea/approach to efficiently find $B$ and the $T_A^*$. Optimality of the solution is not required if this means reduction in complexity.

Motivation

Consider any 3D object that consists of cubes (http://en.wikipedia.org/wiki/Voxel). The naive approach is to render two colored triangles for each visible side of every voxel (graphic engines can deal very efficiently with triangles). However this gets very slow when thousands of voxels are visible. Hence different (fewer) triangles are computed to do more efficient rendering as can be seen in the right image.  Unfortunately this means we can no longer simply color the triangles. We need a "colored paper" or textures as they're called to show the correct colors. Each triangle uses a texture (rectangular image) and defines three points inside it to do the drawing from the texture into the triangle (similar to the $f_T$ function defined above).

This means a lot of different textures are used if we create one for every triangle. In the engine every texture needs to be loaded and produces some overhead. Hence it is desired to keep the overall amount of textures small (preferably one texture for every object in the world). Since many engines have restrictions on how big a texture can be, a "compressed" texture is desired.

In the object shown above it would be no problem to place all textures next to each other into one image and use that as B, however voxel objects are often very complex with edges and huge amount of voxel.

• Mathematicians may not know what a "voxel" is... This would be great for Computer Science cs.stackexchange.com or Scientific Computing scicomp.stackexchange.com. Feb 17, 2014 at 18:05
• @johnmangual You might be right, but the problem is mathematical imo, even though the motivation relates to CS. I will consider having it moved if I don't get a good answer here. Note: Added a link to the wikipedia page of a voxel. Feb 17, 2014 at 18:50