Archief - 2D polygon self-intersection probleem

Yo,

Ik ben momenteel een systeempje aant uitwerken en ben op 1 subprobleempje gestrand waar ik nog geen oplossing voor heb kunnen bedenken.

Voor alle duidelijkheid, ik zoek geen kant-en-klare oplossing, een verwijzing naar relevante literatuur of ideetje in de juiste richting zou al handig zijn .

---

Ik heb een polygon, met een arbitrair aantal punten, die vervormd wordt rond een polyline (een referentiepolyline voor die polygon dus) aan de hand van polyline deformation. Deze polyline is een projectie van een 3D polyline op een 2D vlak. Een normaal resultaat van zo'n deformation ziet eruit als: http://users.telenet.be/Daedie/good.png. de referentiepolyline (die ge niet ziet) loopt dan ongeveer door het midden van die polygon volgens de buiging.

Het probleem doet zich voor wanneer de vervorming ervoor zorgt dat de polygon met zichzelf gaat overlappen. dan krijg ik iets in de stijl van: http://users.telenet.be/Daedie/bad.png. Dit resultaat is op zich logisch, maar niet wat ik wil. Wat ik zou willen is eerder iets zoals dit: http://users.telenet.be/Daedie/better.png. Het overlappend deel van de polygon moet dus eigenlijk vóór de rest liggen. De diepte-informatie die nodig is om te bepalen welk deel vanvoor zou liggen valt te bepalen uit de hierboven vermelde 3D lijn.

Mijn gedachtenstroming gaat momenteel naar het idee om de polygon op te delen in deelpolygonen en deze over elkaar te tekenen. Maar bepalen hoeveel polygonen, bestaande uit welke punten, ... daar heb ik momenteel geen antwoord op.

"De diepte-informatie die nodig is om te bepalen welk deel vanvoor zou liggen valt te bepalen uit de hierboven vermelde 3D lijn."
Je zegt dat dat lukt dus in principe kan je dus voor elk punt van de polygon opvragen wat de diepte is en dan zo tekenen?

Maar ik leid af uit je uitleg dat je denkt dat de polygon wel correct gedeformed wordt maar dat deze verkeerd getekend wordt? Maar zou het ook niet kunnen dat de deformatie niet zo netjes is en wel degelijk zo'n lelijk gat laat? Dan is dat niet zomaar overlap en moet je toch het algoritme wat aanpassen, wat me niet evident lijkt.

NeverwinterX zei:

"De diepte-informatie die nodig is om te bepalen welk deel vanvoor zou liggen valt te bepalen uit de hierboven vermelde 3D lijn."
Je zegt dat dat lukt dus in principe kan je dus voor elk punt van de polygon opvragen wat de diepte is en dan zo tekenen?

Klik om te vergroten...

Ik denk dat ik hier nog even moet verduidelijken dat ik de tekenlib gebruik van QT en daarvan de drawpolygon operatie aanroep om de polygon te tekenen. In mijn code wordt enkel de polygon opgebouwd.

Houdt er ook rekening mee dat de polygon in kwestie volledig 2D is en geen diepte kent. Enige vorm van diepte moet dus door mij geïntroduceerd worden door bijvoorbeeld in stukken te kappen en over elkaar te tekenen.

NeverwinterX zei:

Maar ik leid af uit je uitleg dat je denkt dat de polygon wel correct gedeformed wordt maar dat deze verkeerd getekend wordt? Maar zou het ook niet kunnen dat de deformatie niet zo netjes is en wel degelijk zo'n lelijk gat laat? Dan is dat niet zomaar overlap en moet je toch het algoritme wat aanpassen, wat me niet evident lijkt.

Klik om te vergroten...

Ik kan het effect reproduceren zonder enige vorm van deformation. Maar het gat op zich is volgens mij logisch als ge rekening houdt met het feit dat dit 1 2D polygon is. Door de self-intersection ligt dat stukje int midden "buiten" de polygon. Of in ieder geval ziet de tekenlib dit als buitenkant.

Het tekenresultaat is volgens mij dus zelfs gewoon correct. Wat ik wil bereiken is dus eigenlijk een toevoeging van 3D informatie.


sidenote: Het is trouwens een 2D/3D hybride techniek dat ik wil verwezenlijken, dus het is ook niet een kwestie van "gebruik beter 3D polygonen". Voor alle duidelijkheid .

Graphics Programming and Theory - GameDev.net

Post daar eens uw probleem, daar gaat ge normaal gezien wel vrij snel hulp krijgen.

edit:

En zelf eens proberen nu ik er even op gedacht heb, ik heb zelf nog nooit met die qt lib gewerkt, dus geen idee wat de mogelijkheden zijn, hoe uw code atm werkt of als het mogelijk is.

Zeker zonder code-fragmenten is het eigenlijk niet echt mogelijk oplossingen te bedenken buiten gewoon grove theorie er achter.

Nu wat ge zegt, het is inderdaad logisch dat die poly zo een rare vorm aanneemt aangezien die die probeert te "buigen" volgens die lijn.

Het grootste probleem waar ik mee zit is dat ge eigenlijk een complete 2d weergave wilt doen van iets dat zich eigenlijk in een 3d wereld bevind, en bijvoorbeeld een triangle die een bepaalde diepte heeft zal er vanuit een een 2d perspectief anders uit zien dan gewoon een vlakke triangle.

Dus zolang ge niet effectief uw poly in 3d weergeeft en dan gewoon een camera er op van een bepaald punt gaat ge inderdaad iets moeten ineen 'hacken' om een gelijkaardig resultaat te bekomen.

sowieso zou ik ergens een diepte weergeven aan de ingebeelde lijn die uw poly moet volgen, zonder dit gaat ge nooit weten welk deel nu eigenlijk het welke overlapt.
(behalve natuurlijk als ge bepaalde regels opstelt zoals het begin van de lijn ligt altijd lager dan het einde, maar dat zal waarschijnlijk nog meer kopzorgen opleveren).

Het lastige is uw poly degelijk laten vervormen.

Een begin zou zijn om checks toe te voegen om te kijken wanneer uw poly effectief begint te overlappen (dus rekeninghouden met de breedte hiervan en de hoek van de vervorming van uw lijn).

vanaf dat gebeurt zou ge eigenlijk uw lijn moeten opsplitsen in het eerste gedeelte, dus een aparte poly die deze vorm aanneemt tot waar de buiging start, of net tot aan de overlapping.

En dan het 2de gedeelte ook als een aparte lijn/poly gebruiken, waarschijnlijk gaat ge dan problemen krijgen met het overlappen van uw 2 poly's (aangezien waar ze overlappen de onderste niet wil tekenen, dus die onderste poly gaat ge moeten aanpassen), en ook de correcte "ingebeelde" aansluiting van de 2 poly's, maar hiervoor zou ik al even moeten beginnen tekenen om eventueel problemen hiermee op te lossen.

En als uw lijn verder overlapt, kunt ge hetzelfde doen, lijn opsplitsen in het eerste gedeelte, eerste gedeelte drawen, lijn verder "onderzoeken" om te zien als er een 2de overlapping is, als die er niet is, de rest van de poly aanmaken, als er nog een overlapping is, terug opsplitsen, 2de deel drawen, enzoverder.

Geen idee als ge er iets aan hebt, of als het effectief een goed idee is, ik ben gewoon maar even luidop aan het denken.

Ik zou sowieso nog eens op dat gamedev forum posten, normaal gezien gaat ge daar nog wel goeie reacties krijgen.

Het probleem van het witte gat heb ik ondertussen kunnen fixen. Blijkbaar werd er een odd-even fill methode gebruik voor het inkleuren, met een windingfill wordt dat gat wel ingekleurd.

Maar dan zit ik natuurlijk nog steeds met die overbodige outlines die ik niet wil hebben.

Lethall zei:

Zeker zonder code-fragmenten is het eigenlijk niet echt mogelijk oplossingen te bedenken buiten gewoon grove theorie er achter.

Klik om te vergroten...

Das al meer als voldoende .

Lethall zei:

sowieso zou ik ergens een diepte weergeven aan de ingebeelde lijn die uw poly moet volgen, zonder dit gaat ge nooit weten welk deel nu eigenlijk het welke overlapt.

Klik om te vergroten...

Heb momenteel diepteinformatie op polyline niveau (dus gemiddeld eigenlijk). Voor hetgeen ge hierna bespreekt zou ik dit wel moeten uitbreiden naar diepte op lijnstuk niveau. Maar dat is niet echt een probleem.

Lethall zei:

Een begin zou zijn om checks toe te voegen om te kijken wanneer uw poly effectief begint te overlappen (dus rekeninghouden met de breedte hiervan en de hoek van de vervorming van uw lijn).

vanaf dat gebeurt zou ge eigenlijk uw lijn moeten opsplitsen in het eerste gedeelte, dus een aparte poly die deze vorm aanneemt tot waar de buiging start, of net tot aan de overlapping.

En dan het 2de gedeelte ook als een aparte lijn/poly gebruiken, waarschijnlijk gaat ge dan problemen krijgen met het overlappen van uw 2 poly's (aangezien waar ze overlappen de onderste niet wil tekenen, dus die onderste poly gaat ge moeten aanpassen), en ook de correcte "ingebeelde" aansluiting van de 2 poly's, maar hiervoor zou ik al even moeten beginnen tekenen om eventueel problemen hiermee op te lossen.

En als uw lijn verder overlapt, kunt ge hetzelfde doen, lijn opsplitsen in het eerste gedeelte, eerste gedeelte drawen, lijn verder "onderzoeken" om te zien als er een 2de overlapping is, als die er niet is, de rest van de poly aanmaken, als er nog een overlapping is, terug opsplitsen, 2de deel drawen, enzoverder.

Geen idee als ge er iets aan hebt, of als het effectief een goed idee is, ik ben gewoon maar even luidop aan het denken.

Klik om te vergroten...

In eerste instantie zie ik wel potentieel in die aanpak. Vooral het segmenteren van de referentielijn en de overlapdetectie. Kan er in ieder geval wel verder mee experimenteren.

Merci voor de hulp .