Making the triangles of a 3d model automatically fit into a rectangle w/o overlapping?
Paul Nicholls
to make the triangles (after being rotated, not scaled) of a 3d model
automatically fit into a rectangle (or square) without the triangles
overlapping?
If I could do this, then it would make texturing of the model much faster as
I could then just concentrate on painting the texture on the triangles
directly in 3d mode or on the 2d texture that the triangles are now sitting
in.
Are there any algorithms for doing the packing of the triangles into a
rectangle or square without overlapping, or does someone have a link to a
paper? The automatic way would be way preferable to manually placing and
rotating the triangles into the texture box <g>.
Thanks in advance,
Paul Nicholls (Delphi 5 Professional)
"Life is like a road - occasionally you run into potholes or get
blowouts." -
Paul Nicholls
HomePage: www.southcom.com.au/~phantom
Email: paul-n...@hotmail.com
(Replace "-" with "_" to reply)
Jens Gruschel
> to make the triangles (after being rotated, not scaled) of a 3d model
> automatically fit into a rectangle (or square) without the triangles
> overlapping?
I wrote such an algorithm in the days of TurboPascal. I cannot find it any
more, but I can tell you what the idea behind it was:
At first do clipping at the top and bottom edge, after that (using the same
algorithm, but x and y swapped) do clipping at the left and right edge. You
have to do all sides separatly (for example at first upper, then lower, then
left, the right). Doing clipping means: Find all points outside your
rectangle (only compare the value that's interesting for one side, for
example: if p.y < rect.top) that are connected to each other (in a chain),
let's call them p[m] to p[n]. Only p[m] and p[n] are interesting (points
between don't change anything because they and all lines connected with them
are outside). Also interesting are p[m-1] and p[n+1], the next points
inside. Replace p[m] to p[n] with with exactly two points a and b that are
exactly on the edge of the rectangle, the formula for the upper edge is:
a.y := rect.top;
a.x := (a.y - p[m-1].y) * (p[m].x - p[m-1].x) / (p[m].y - p[m-1].y)
b.y := rect.top;
b.x := (b.y - p[n+1].y) * (p[n].x - p[n+1].x) / (p[n].y - p[n+1].y)
Not 100% sure, I have not tested this algorithm (but it's not as complicated
as it looks, draw a sketch and you will see).
Do this for all chains of points, that are connected to each other and
outside the rectangle (beyond the same side).
The lower edge works the same, but replace rect.top by rect.bottom. The left
and right edge formulas are identical, but swap x and y.
Now you might also need z-coordinates of the new points, again we have the
same formula:
a.z := (a.y - p[m-1].y) * (p[m].z - p[m-1].z) / (p[m].y - p[m-1].y)
Texture-coordinates (or point brightness, color etc.) should work the same.
Jens
P.S. I just noticed you only have triangles, this should make things even
more easy.
Maynard Philbrook
look up regions in the Win32 help..
Paul Nicholls
you wrote :(
The way I figure things is I have to rotate each triangle in the model so
the normal faces out of the screen and try to pack them into the rectangle
(possibly with rotating in the XY plane to help with fitting them in).
After fitting them into the rectangle I can then easily get the texture
coords...
--
Paul Nicholls (Delphi 5 Professional)
"Life is like a road - occasionally you run into potholes or get
blowouts." -
Paul Nicholls
HomePage: www.southcom.com.au/~phantom
Email: paul-n...@hotmail.com
(Replace "-" with "_" to reply)
"Jens Gruschel" <grus...@esteam.de> wrote in message
news:3d491207$1_1@dnews...
Jens Gruschel
description
> you wrote :(
Seems I did not understand your question. My answer was for drawing the
polygons with your own routine, while making sure they are not outside a
(2D) rectangle on the screen. It seems you want to transform your object
into a (3D) box. But - sorry - I don't think I know an answer for this one.
And I'm still not sure I understood what exactly you want.
Jens
Nils Haeck
Why do you want to rotate the triangle to fit best? This could lead to
strange results with fixtures that have directional aspects in them (like
the nerve of wood etc).
And here's a solution:
Assume you have a triangle with points P Q R (their actual orientation need
not be as displayed):
R
/ \
/ \
P-----Q
Your left/right/top/bottom side will be (assuming X to right, Y upwards):
MinX := Min(Min(P.X, Q.X), R.X);
MaxX := Max(Max(P.X, Q.X), R.X);
MinY := Min(Min(P.Y, Q.Y), R.Y);
MaxY := Max(Max(P.Y, Q.Y), R.Y);
Then, find the scale factor and transform back:
Scale := Min(Width / (MaxX - MinX), Height / (MaxY - MinY));
Here, Width / Height are for your texture.
Now the transform:
New_P.X := (P.X - MinX) * Scale;
New_P.Y := (P.Y - MinY) * Scale;
etc idem for Q and R.
Now for the actual fill: your problem resembles the "painters algorithm
problem". You may want to have a look at this in any of the literature. I
also think that Jens' explanation was some version of that.
Note: for the rotated case I also know a solution, it will however involve
much more maths, and also it could introduce the problems as I mentioned
above with directional textures:
You'll have to rotate the triangle PQR first, so that one of its sides is
horizontal, then fit it to the box as above. Do this also with its edge
vertical. Repeat, for other two edges. Find the biggest scale factor of all
these cases, and this best case is your result. This solution involves some
2D basic math to rotate points.
Hope this helps,
Nils Haeck
www.abc-view.com
Paul Nicholls <paul-n...@hotmail.com> wrote in message
news:3d49c1ce$1_1@dnews...
Greg Albright
Get a book on ray tracing to get the math, I can't do it in my head, or
in the length of a usenet post.
With math do the following
1.Construct a plane that intersects with the screens clipping plane.
2.convert the mouse location into UV coordinate on the clipping plane.
3.from that you can generate a vector from the viewer location to the
the UV coordinates of the screen plane
4.project that vector out into modal space, see if it intersects with
your model using... term escapes me...
5.for each poly in your model, see if the vector(now normalized to modal
space) intersects it.
6. find the intersection with the smalles (or is it largest) z length...
anyhow choose the one that intersects closest to the observer
7.transform the ray around poly space now, some quick addition and
subtraction... and voila, you have the uv coord of the poly, the modal
its on.
8.Approximate that location onto your texture map
9. set the color.
You can also use this technique with fewer steps to find the UV of the
sphere or cylinder around the modal for the global texture maps that
everyone likes to use:)
I suspect there is a patent on this technique, so don't sell the code
that does this.
Paul Nicholls
That is basically what I want to be able to do with my program at some
point, but AFTER the model's triangles have been made to fit into the
texture rectangle/square <g>
--
Paul Nicholls (Delphi 5 Professional)
"Life is like a road - occasionally you run into potholes or get
blowouts." -
Paul Nicholls
HomePage: www.southcom.com.au/~phantom
Email: paul-n...@hotmail.com
(Replace "-" with "_" to reply)
"Greg Albright" <galb...@nospam.dundee.net> wrote in message
news:3D4B5EA6...@nospam.dundee.net...
Paul Nicholls
news:3d4b37f1_2@dnews...
> Just a question,
>
> Why do you want to rotate the triangle to fit best? This could lead to
> strange results with fixtures that have directional aspects in them (like
> the nerve of wood etc).
>
> Now for the actual fill: your problem resembles the "painters algorithm
> problem".
I'm not sure why you wrote that?
<SNIP>
<G> Either I haven't understood completely what you wrote Nils, or I didn't
write clearly what I wanted in my first post, but what I want is an
automatic way of mapping a model's triangles into a texture rectangle/square
so all the triangles fit in the 2D texture and don't overlap. This means
that at least each triangle has to be rotated around the Y and Z axis to
face the viewer so it can be mapped into the texture map correctly.
After the triangle has been rotated it can be then fitted into the texture
so it doesn't overlap.
At this point I then know the texture coordinates of each vertex for the
triangle, at which point I can paint either the triangles directly in the
texture map or paint onto the model in 3d mode and have that point paint
onto the texture.
Paul Nicholls
texture rectangle/square so all the triangles fit in the 2D texture and
don't overlap. This means that at least each triangle has to be rotated
around the Y and Z axis to face the viewer so it can be mapped into the
texture map correctly.
After the triangle has been rotated it can be then fitted into the texture
so it doesn't overlap.
At this point I then know the texture coordinates of each vertex for the
triangle, at which point I can paint either the triangles directly in the
texture map or paint onto the model in 3d mode and have that point paint
onto the texture.
--
Paul Nicholls (Delphi 5 Professional)
"Life is like a road - occasionally you run into potholes or get
blowouts." -
Paul Nicholls
HomePage: www.southcom.com.au/~phantom
Email: paul-n...@hotmail.com
(Replace "-" with "_" to reply)
"Jens Gruschel" <grus...@esteam.de> wrote in message
news:3d4a83ba$1_2@dnews...