следующий фpагмент (2)- Usenet echoes (21:200/1) ------------------------------------- COMP.GRAPHICS -
Msg : 24 of 30
From : email@example.com 2:5030/144.99 22 May 94 15:08:00
To : All 25 May 94 08:04:08
Subj : (1) Polygon Gluing
I solved my own polygon glueing together problem this afternoon. Not that
anyone cares, but here is how I will be doing it:
To glue many triangles together without causing a hole or degenerate polygon
(poly with angles > 180) these are the steps:
First, seperate each polygon into invidual connections like so:
eg 1,2,5,7,3,1 1
becomes: 1,2 1
... +- assigned polygon number
Now, you scan through your connection list for opposite pairs of connection
data within your list.
Eg 1,2 => scan for 2,1
2,5 => scan for 5,2
5,7 => scan for 7,5
3,1 => scan for 1,3 (match found)
Now you know there is a match, you do these steps to glue it.
1) Renumber all of the second match polygon numbers to equal the first polygone
numbers (eg all 2's become 1's) This is to make all those lines part of one
2) Delete both lines in the pair found. eg nullify/remove lines 3,1 and 1,3
Now the side is glued. You should end up with:
becomes: 1,2 1
... +- assigned polygon number
Now to find out what our resulting polygon looks like: simply follow the
connection data around untill you come back in a circle. 1->2,2->5,5->7,
So our resulting polygone is 1,2,5,7,3,6,4,1 glued!
But this does not work for polygones thats have holes in the middle or have
angles > 180! so the following steps must be added: After glueing a side...
3) Push what lines we removed onto the stack (in case we need to reconstruct)
4) Test BOTH ends of the glued line to see if there is an angle > 180
5) If the recursive test fails, pop lines changed and reconstruct.
Because each test may be recursive, the line must be glued before testing, and
then unglued if the test fails. This is so recursive tests already have the
information that the side was glued.
When you find a pair of opposite connections, you know that edge
can be glued together. But before you do, you need to know if glueing them
will cause a degenterate polygon (eg, the final poly will have angles > 180)
To test this you call the original routine that glues them together to test
either end of the glued side.
These 4 polygons could make one surface (humans know this, computers don't)
|\ H /|
eg: | \F A/ |
| \ / |
I| \____B_____/ |G
| / \ |
| E/ \D |
| / \ |
For our first glue, we will test to see if poly AHFB and poly ADG can be
glued to make poly FBDGH.
So, If you are about to glue together line A, you need to find out if the
ends (GH) and (BD) will be degenerate (which one will, because BD has
an angle > 180)
We know that angle GH is okay! But angle BD is not! so, we must then
recursivly call our test-for-glue routine to find out if sides B and D will
be glued. First, if we scanned line D, we would look for an opposite pair
of connections lines (and we would find them), then look at the ends of D.
One end of line D is BA (ignored because thats where we came from), but the
other end, lines GC is okay because GC does not make an angle > 180!
We will then scan for an opposite pair of connections along line B (see above).
and we would find them...we would test for > 180, we would find angle FE is
> 180, call again to test F and test E. Both can be glued and when glued, do
not produce an angle > 180!!!.
So, if you know it can be glued, but it is degenerate, you must test if line
B can be glued. If it can, you can glue A. But B is dependant on F and E.
This compounded/tree like testing is how I glue a poly together while
making sure that arrangements that have holes in them or really odd shapes
are still glued together without having any angles > 180. If you follow this
through for the above example you will find that all lines can be glued
together and you will end up with one big polygon HICG. This works even if you
put a couple of holes in them, the routine works around the holes and never
loses the original shape. You know you are finished your testing tree when
ALL end surfaces can be glued without producing an angle > 180 - even if
many middle surfaces within the tree produce angles > 180.
From diagram A A is tested to be glued
above: / \ + backwards pair for A found
/ \ + HG is okay!
/ \ + BD is > 180
BD HG |+ D is tested to be glued
/ \ | + backwards pair for D found
/ \ | + GC is okay!
/ \ +- B is tested to be glued
FE GC + backwards pair for B found
/ \ + FE is > 180
/ \ |+ E is tested to be glued
/ \ | + backwards pair for E found
CI IH | + IH is okay!
+- F is tested to be glued
+ backwards pair for F found
+ CI is okay! (tree ends)
Therefore, to glue together many triangles into fewer poly's, you recursivly
call the glueing single side routine untill all glued sides either succeed or
fail. To glue together the topmost side of this recursive tree, ALL dependant
sides must also be capable of being glued together AND without causing an
angle >180. If not, the original side, will cause a hole or degenerate
polygon, and cannot be glued together.
This is much easier to demonstrate on paper. But if you work one through
you should get the idea. Draw some really wierd shapes and you'll see!
Internet/Usenet: BRIAN.MCCARTHY@CANREM.COM and talk to John
design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm
Of Illusion 1994-2000,
При перепечатке материалов этой страницы
пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ,