# Board index » delphi » Packing 2d triangles into smallest 2d box area...

## Packing 2d triangles into smallest 2d box area...

Hi all, if I have X number of 2d triangles composed of any 2d vertices, is
it possible to rotate and move (NOT SCALE) these triangles around to fit in
the smalles possible 2d box area?  The triangles can't overlap each other,
except that it doesn't matter if an edge rests exactly ontop of another
edge.  If I can do this I can then define a box around the triangles and
change their vertices to use one corner of the box as the origin.

If you hadn't guessed, this is so I can find out the 2d box coordinates for
each
triangle vertex for texture mapping...

The algorithm doesn't have to be really fast as it is only going to be run
once after all triangles have been created...

Paul Nicholls (Delphi 5/6 Professional)
"Life is like a road - occasionally you run into potholes and get
blowouts..." - Paul Nicholls.
paul-nicho...@hotmail.com

(Replace "-" with "_" to reply)

## Re:Packing 2d triangles into smallest 2d box area...

##### Quote
> it possible to rotate and move (NOT SCALE) these triangles around to fit

in

Hmm but what if you have directional textures, like wood? If you rotate the
triangles differently, the textures will not continue correctly..

Usually, for texture mapping, you look at the final object and find a
suitable method. For anything that doesn't need to be viewed from all sides,
a cylindrical or plane mapping will be OK, and for some objects, like balls,
you will need a sphere mapping.

e.g. cylindrical:
The coordinates on the texture are found by assuming the (blown up) texture
forms a cylinder that is placed around the object (assume vertical
cylinder). Then, for each vertex, you shoot horizontally from the (vertical)
center line of your object through the vertex onto the cylinder. Then, map
this coordinate back to your (rectangular) texture coordinates.

For a triangle, you do this for the 3 vertices. When done, you have the
texture coordinates for the vertices and then you can simply linearly
interpolate over the triangle (or leave this part to the rendering
hardware).

Hope that helps,

Nils Haeck
www.simdesign.nl

##### Quote
"Paul Nicholls" <paul-nicho...@hotmail.com> wrote in message

news:3e1e3662@newsgroups.borland.com...
##### Quote
> Hi all, if I have X number of 2d triangles composed of any 2d vertices, is
> it possible to rotate and move (NOT SCALE) these triangles around to fit
in
> the smalles possible 2d box area?  The triangles can't overlap each other,
> except that it doesn't matter if an edge rests exactly ontop of another
> edge.  If I can do this I can then define a box around the triangles and
> change their vertices to use one corner of the box as the origin.

> If you hadn't guessed, this is so I can find out the 2d box coordinates
for
> each
> triangle vertex for texture mapping...

> The algorithm doesn't have to be really fast as it is only going to be run
> once after all triangles have been created...

> Paul Nicholls (Delphi 5/6 Professional)
> "Life is like a road - occasionally you run into potholes and get
> blowouts..." - Paul Nicholls.
> paul-nicho...@hotmail.com

> (Replace "-" with "_" to reply)

## Re:Packing 2d triangles into smallest 2d box area...

Ok, granted that spherical mapping would be usefull for certain models, not
to mention those directional textures like wood, but I'm thinking more of
simple models that are wouldn't map to these easily or even at all.  Some
models I had in mind were ones like a spaceship, an alien, etc.  These
models would be similar to MD2 models, and would most likely need to be
mapped manually.

This is why I want to know how to pack the triangles into a 2d box, at least
as a starting point so I can then paint onto the texture map box.

Any ideas?

##### Quote
"Nils Haeck" <n.haeck_no@spam_chello.nl> wrote in message

news:3e2215c4\$1@newsgroups.borland.com...
##### Quote
> > it possible to rotate and move (NOT SCALE) these triangles around to fit
> in

> Hmm but what if you have directional textures, like wood? If you rotate
the
> triangles differently, the textures will not continue correctly..

> Usually, for texture mapping, you look at the final object and find a
> suitable method. For anything that doesn't need to be viewed from all
sides,
> a cylindrical or plane mapping will be OK, and for some objects, like
balls,
> you will need a sphere mapping.

<SNIP>

> "Paul Nicholls" <paul-nicho...@hotmail.com> wrote in message
> news:3e1e3662@newsgroups.borland.com...
> > Hi all, if I have X number of 2d triangles composed of any 2d vertices,
is
> > it possible to rotate and move (NOT SCALE) these triangles around to fit
> in
> > the smalles possible 2d box area?  The triangles can't overlap each
other,
> > except that it doesn't matter if an edge rests exactly ontop of another
> > edge.  If I can do this I can then define a box around the triangles and
> > change their vertices to use one corner of the box as the origin.

> > If you hadn't guessed, this is so I can find out the 2d box coordinates
> for
> > each
> > triangle vertex for texture mapping...

> > The algorithm doesn't have to be really fast as it is only going to be
run
> > once after all triangles have been created...

> > Paul Nicholls (Delphi 5/6 Professional)
> > "Life is like a road - occasionally you run into potholes and get
> > blowouts..." - Paul Nicholls.
> > paul-nicho...@hotmail.com

> > (Replace "-" with "_" to reply)

## Re:Packing 2d triangles into smallest 2d box area...

I'm sorry, but you have totally lost me there Alexander, why would the
convex hull help me? I am confused :(

##### Quote
"Alexander Weidauer" <weida...@uni-greifswald.de> wrote in message

news:3E22CDEE.6060901@uni-greifswald.de...
##### Quote
> Paul Nicholls wrote:
> > Hi all, if I have X number of 2d triangles composed of any 2d vertices,
is
> > it possible to rotate and move (NOT SCALE) these triangles around to fit
in
> > the smalles possible 2d box area?  The triangles can't overlap each
other,
> > except that it doesn't matter if an edge rests exactly ontop of another
> > edge.  If I can do this I can then define a box around the triangles and
> > change their vertices to use one corner of the box as the origin.

<SNIP>
> You can determin the convex hull of these triangulation points a 2d
> convex polygon and dertemning the area.
> Then you know the number of possible turns and the angle.
> They are the number of segments and the angles between define them.
> If you have a point inside the polygon you can turn the polygon and
> determin the box with the smallest extention. To dermin the convex hull
> I' ve written a API for the Triangle tool from Jonathan Shewchuk
> see http://www.triplexware.huckfinn.de

## Re:Packing 2d triangles into smallest 2d box area...

If you determin the convex hull you get the polygon surrounding
the points defining your triangles but it is convex, that means
if you connect each point of the polygon with a line you will never
leave the polygon. If you turn the polygon so that a every edge
of the polygon lies horizontically you can test the rest
if a surrrounding box whitch is defined by the points of the polygon is
the the smallest on. Thats all.

Bye Alex

## Re:Packing 2d triangles into smallest 2d box area...

Thanks for the info, I don't suppose you'd have some pseudo-code on how to
do some of this?

##### Quote
"Alex Weidauer" <alex.weida...@huckfinn.de> wrote in message

news:3E2DC4AF.8040106@huckfinn.de...
##### Quote
> If you determin the convex hull you get the polygon surrounding
> the points defining your triangles but it is convex, that means
> if you connect each point of the polygon with a line you will never
> leave the polygon. If you turn the polygon so that a every edge
> of the polygon lies horizontically you can test the rest
> if a surrrounding box whitch is defined by the points of the polygon is
> the the smallest on. Thats all.

> Bye Alex

## Re:Packing 2d triangles into smallest 2d box area...

##### Quote
Paul Nicholls wrote:
> Thanks for the info, I don't suppose you'd have some pseudo-code on how to
> do some of this?

Hi,

I' ve some code, a API to create triangulations and convec hulls
in delphi, a point and pointlist container, and a turning tool and
a affine transforamation passpoint tool and...
OK, I' will make you a image of the problem solution and a
pseudo(code) send it to your email but it will need
a little bit time (two days). Is it ok.

Bye Alex

## Re:Packing 2d triangles into smallest 2d box area...

Ok Alex, thanks for taking the time to do this for me :)

There is no rush :-)

Just remember to replace the '-' with '_' in my address when you send it...

##### Quote
"Alex Weidauer" <alex.weida...@huckfinn.de> wrote in message

news:3E2DCE32.4070903@huckfinn.de...
##### Quote
> Paul Nicholls wrote:
> > Thanks for the info, I don't suppose you'd have some pseudo-code on how
to
> > do some of this?

> Hi,

> I' ve some code, a API to create triangulations and convec hulls
> in delphi, a point and pointlist container, and a turning tool and
> a affine transforamation passpoint tool and...
> OK, I' will make you a image of the problem solution and a
> pseudo(code) send it to your email but it will need
> a little bit time (two days). Is it ok.

> Bye Alex

## Re:Packing 2d triangles into smallest 2d box area...

Paul,
What you are talking about sounds uncannily like a lightmap packing
algorithm. If it is, then there are a lot of ways to go about it, and
thinking of them as 2D triangles is definitely NOT the way. I am currently
working on a lightmap packer, and may be of some assistance if this is the
case.

If not, then u might try a "greedy" algorithm, that  minimizes the
amount of wastage on the texture, by sorting the triangles by size (bounding
box and/or area), and then putting them in largest to smallest. you could
also do a series of 90 degree rotates, so that each time u put a triangle
in, you minimize the texture wastage.

Hope this helps,
Ananth B.

##### Quote
"Paul Nicholls" <paul-nicho...@hotmail.com> wrote in message

news:3e1e3662@newsgroups.borland.com...
##### Quote
> Hi all, if I have X number of 2d triangles composed of any 2d vertices, is
> it possible to rotate and move (NOT SCALE) these triangles around to fit
in
> the smalles possible 2d box area?  The triangles can't overlap each other,
> except that it doesn't matter if an edge rests exactly ontop of another
> edge.  If I can do this I can then define a box around the triangles and
> change their vertices to use one corner of the box as the origin.

> If you hadn't guessed, this is so I can find out the 2d box coordinates
for
> each
> triangle vertex for texture mapping...

> The algorithm doesn't have to be really fast as it is only going to be run
> once after all triangles have been created...

> Paul Nicholls (Delphi 5/6 Professional)
> "Life is like a road - occasionally you run into potholes and get
> blowouts..." - Paul Nicholls.
> paul-nicho...@hotmail.com

> (Replace "-" with "_" to reply)

## Re:Packing 2d triangles into smallest 2d box area...

:) I suppose it could be the same algorithm as lightmap packing, but they
are only going to be texture map coordinates into 1 texture.
Just one question, why is thinking of them as 2D triangles not the way to do
it?  This would have been after I'd gotten all of the 3d triangles and
rotated them so they faced out of the screen and then treat them as 2d to
pack into the rectangle...

I think a greedy algorithm would work just fine for me, but if I shouldn't
think of them as 2d triangles, how should I think of them?

BTW you are very active at the moment in the posting department, good for
you :)

##### Quote
"Ananth B." <ana...@agnisoft.com> wrote in message

news:3e479b03@newsgroups.borland.com...
##### Quote
> Paul,
>    What you are talking about sounds uncannily like a lightmap packing
> algorithm. If it is, then there are a lot of ways to go about it, and
> thinking of them as 2D triangles is definitely NOT the way. I am currently
> working on a lightmap packer, and may be of some assistance if this is the
> case.

>     If not, then u might try a "greedy" algorithm, that  minimizes the
> amount of wastage on the texture, by sorting the triangles by size
(bounding
> box and/or area), and then putting them in largest to smallest. you could
> also do a series of 90 degree rotates, so that each time u put a triangle
> in, you minimize the texture wastage.

## Re:Packing 2d triangles into smallest 2d box area...

Hi Paul,
When u assign different triangles of mesh into a single texture, and
then render the resulting mesh, the edges will be smoothed out due to
bilinear or trilinear filtering. This is highly unwanted when u have 2
triangles that SHOULD NOT be blurred in this fashion. It might produces
unwanted jaggies along corners and might look ugly.
What I'm doing in my lightmapper is as follows.

1. Group all triangles that have the same plane equation.
2. Split each group by triangle connectivity (this is an iterative
procedure, because A could be conncted to B, and B connected to C, but A,B
and C are in the same group). Also, you might want to limit the connectivity
based on program specific parameters, I, for example, _DO NOT_ connect
triangles that have different emissivity values.
3. So now, u have a list of groups of triangles, where each group lies on
the same plane, and each group is connected. _After_ this point, it is
beneficial to think of them as 2D triangles, because we have already
exploited all of the spatial information.
4.  I call each group a combined poly, and use a simple area mapping (there
are other methods also available) to assign texture coodinates, like so : If
this "combined poly" covered 10x7 game units and the relation between game
units and lightmap texels are 2 game units = 1 texel, then on a 256x256
lightmap we would have to allocate,
5x3.5 texels. This would be rounded off to 5x4 texels, and the resulting
square piece would have texture coordinates startU,startV to startU + 5/256,
startV + 4/256

5. Of course, some optimizations u could think off straight away are stuff
like gathering the combined polys, and the assigning them after sorting my
size, etc, but that would depend greatly upon the nature of the application
(whether texture memory size is a concern, or texture trashing is more of a
concern)

As for my postings, I believe in this adage "No pain, no gain. No give, no
get" (^_^)

Hope this helps

Regards,
Ananth B.

##### Quote
"Paul Nicholls" <paul-nicho...@hotmail.com> wrote in message

news:3e4833c5\$1@newsgroups.borland.com...
##### Quote
> :) I suppose it could be the same algorithm as lightmap packing, but they
> are only going to be texture map coordinates into 1 texture.
> Just one question, why is thinking of them as 2D triangles not the way to
do
> it?  This would have been after I'd gotten all of the 3d triangles and
> rotated them so they faced out of the screen and then treat them as 2d to
> pack into the rectangle...

> I think a greedy algorithm would work just fine for me, but if I shouldn't
> think of them as 2d triangles, how should I think of them?

> BTW you are very active at the moment in the posting department, good for
> you :)

> "Ananth B." <ana...@agnisoft.com> wrote in message
> news:3e479b03@newsgroups.borland.com...
> > Paul,
> >    What you are talking about sounds uncannily like a lightmap packing
> > algorithm. If it is, then there are a lot of ways to go about it, and
> > thinking of them as 2D triangles is definitely NOT the way. I am
currently
> > working on a lightmap packer, and may be of some assistance if this is
the
> > case.

> >     If not, then u might try a "greedy" algorithm, that  minimizes the
> > amount of wastage on the texture, by sorting the triangles by size
> (bounding
> > box and/or area), and then putting them in largest to smallest. you
could
> > also do a series of 90 degree rotates, so that each time u put a
triangle
> > in, you minimize the texture wastage.