Frequently Asked Questions
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий фpагмент (2)
- Usenet echoes (21:200/1) ------------------------------------- COMP.GRAPHICS - Msg : 24 of 30 From : 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 6,4,1,3,6 2 ... becomes: 1,2 1 2,5 1 5,7 1 7,3 1 3,1 1 6,4 2 4,1 2 1,3 2 3,6 2 ... +- 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 polygon 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 2,5 1 5,7 1 7,3 1 0,0 1 6,4 1 4,1 1 0,0 1 3,6 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, 7->3,3->6,6->4,4->1 done! 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 | | / \ | |/_________C______\| 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. etc...etc... 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 TTYL

Всего 1 фpагмент(а/ов) |пpедыдущий фpагмент (1)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ,".