[Alg] polygon visibility

[Zoijar]

Ik zou dit moeten weten, maar feit is dat ik al jaren de hardware fijn alle clipping etc laat doen...

Ik wil weten of een quad zichtbaar is op het scherm. Ik hoef dus niet te clippen ofzo, alleen een ja-nee antwoord is voldoende. Zit ik dan toch vast aan sutherland-hodgman clipping en kijken of de output lijst leeg is? Misschien mis ik een simpele methode. De quad is dus niet noodzakelijk rechthoekig ofzo; gewoon een algemene transformatie van een vierkant.

[HuHu]

Misschien snap ik het niet helemaal, maar mij lijkt controleren of één van de vier hoekpunten binnen je scherm valt voldoende?

[Zoijar]

HuHu schreef op donderdag 03 juni 2010 @ 16:02:
Misschien snap ik het niet helemaal, maar mij lijkt controleren of één van de vier hoekpunten binnen je scherm valt voldoende?

Nee, want er zijn situaties dat hij dan toch zichtbaar is als dat niet zo is. Bijvoorbeeld als de quad het hele scherm vult en dus veel groter is, of als er slechts een stukje van de zijkant van een 45 graden gedraaid vierkant zichtbaar is, dan vallen de hoekpunten buiten het scherm.

[Janoz]

Moet het snel en zijn false positives geen probleem? Of moet je echt zeker weten of iets echt op het scherm staat?

(En is het 2d of 3d? Hoewel dat laatste weinig uitmaakt qua implementatie is het wel handig om te weten of we het over een frustum of een rechthoek hebben voor de clipping)

[Zoijar]

Janoz schreef op donderdag 03 juni 2010 @ 16:05:
Moet het snel en zijn false positives geen probleem? Of moet je echt zeker weten of iets echt op het scherm staat?

(En is het 2d of 3d? Hoewel dat laatste weinig uitmaakt qua implementatie is het wel handig om te weten of we het over een frustum of een rechthoek hebben voor de clipping)

- homogeen 2D op het moment (i.e. zelfs als het 3D zou zijn, is het effectief een rechthoek)
- snelheid is niet zo'n issue
- liever geen false positives, maar ook geen groot probleem. Quads die passen worden van disk gepaged en naar opengl gestuurd; die clipt verder. Maar in-pagen is relatief duur.

Het is vergelijkbaar met iets als google maps met algemene transformaties.

[ Voor 9% gewijzigd door Zoijar op 03-06-2010 16:14 ]

[Janoz]

Een heel snelle methode is om te kijken of alle vertices OF helemaal links van het scherm, OF helemaal rechts, OF helemaal boven OF helemaal onder (waar bij de OF een OR is, en geen XOR). De enige false positives die je dan nog krijgt is dat voorbeeld dat je eerder aanhaalde waarbij net een hoekje in het scherm zit, maar dan net ver genoeg weggeschoven dat hij niet meer in beeld is. Ook kun je false positives gaan krijgen wanneer de polygonen niet convex zijn en op een zelfde manier rond de hoek van je scherm staan.

[HuHu]

Zoijar schreef op donderdag 03 juni 2010 @ 16:03:
[...]

Nee, want er zijn situaties dat hij dan toch zichtbaar is als dat niet zo is. Bijvoorbeeld als de quad het hele scherm vult en dus veel groter is, of als er slechts een stukje van de zijkant van een 45 graden gedraaid vierkant zichtbaar is, dan vallen de hoekpunten buiten het scherm.

Owja, dat is ook zo. Volgens mij is het volgende dan voldoende:

- de 4 hoekpunten controleren of ze binnen je scherm vallen, zo niet:
- 4 x 4 lijn-intersecties doen met je quad en je scherm, zo niet:
- controleren of hoekpunt linksboven en rechtsonder respectievelijk linksboven en rechtsonder je scherm zitten

Als alle drie die tests falen, dan is hij niet zichtbaar volgens mij.

[Janoz]

Dan is mijn algorithme toch wat sneller .

[ Voor 28% gewijzigd door Janoz op 03-06-2010 16:24 ]

[Zoijar]

Janoz schreef op donderdag 03 juni 2010 @ 16:17:
Een heel snelle methode is om te kijken of alle vertices OF helemaal links van het scherm, OF helemaal rechts, OF helemaal boven OF helemaal onder (waar bij de OF een OR is, en geen XOR). De enige false positives die je dan nog krijgt is dat voorbeeld dat je eerder aanhaalde waarbij net een hoekje in het scherm zit, maar dan net ver genoeg weggeschoven dat hij niet meer in beeld is. Ook kun je false positives gaan krijgen wanneer de polygonen niet convex zijn en op een zelfde manier rond de hoek van je scherm staan.

Misschien is dat wel genoeg ja. De polygonen zijn convex want het zijn lineaire transformaties van rechthoeken, dus dat is geen probleem. Dat FP geval is volgens mij niet zo makkelijk op te sporen zonder algemene clipping. (op zich kan dat ook wel, maar ik heb geen zin om dat nu te implementeren )

HuHu schreef op donderdag 03 juni 2010 @ 16:21:
[...]

Owja, dat is ook zo. Volgens mij is het volgende dan voldoende:

- de 4 hoekpunten controleren of ze binnen je scherm vallen, zo niet:
- 4 x 4 lijn-intersecties doen met je quad en je scherm, zo niet:
- controleren of hoekpunt linksboven en rechtsonder respectievelijk linksboven en rechtsonder je scherm zitten

Als alle drie die tests falen, dan is hij niet zichtbaar volgens mij.

Hmm ja, volgens mij werkt dat ook, maar is eigenlijk gewoon brute-force algemene clipping. SH doet dat dan sneller door edges die volledig out zijn meteen weg te gooien en niet tegen de rest te testen.

[ Voor 27% gewijzigd door Zoijar op 03-06-2010 16:28 ]

[Janoz]

Je zou natuurlijk alle quads die door de border test heen komen nog kunnen clippen. In principe kun je, zodra je weet in welke gebieden de vertices liggen, die randgevallen redelijk snel identificeren en hier wat uitgebreidere tests op loslaten.

[Zoijar]

Wat als ik voor de gevallen die er doorheen komen de omgekeerde test doe: of de viewport helemaal links/rechts/boven/onder de quad ligt? Is daar nog iets mee te doen...

[Janoz]

Neem de volgende schematische weergave met quadranten:

code:

  |    |
--+----+--
  |    |
--+----+--
  |    |

Bij de eerste test bepaal je in welke delen de vertices van je quad vallen en kun je redelijk snel een berg die sowieso niet in beeld is afserveren. Van wat er over blijft zijn er een aantal configuraties die sowieso in beeld vallen en een paar die mogelijk alsnog buiten beeld zijn. Die paar polygonen kun je vervolgens met ingewikkeldere test matchen (als het de moeite is). Dit zou kunenn door te kijken of de edges van de quads de edges van het viewport snijden.

[Zoijar]

Volgens mij werkt je eerste oplossing prima; dat komt neer op de visibility van de AABB. Je zit er nooit veel verder naast dan 1.5x de quad grootte. Aangezien die zo dicht bij de rand liggen is de kans groot dat die binnenkort ook zichtbaar worden en dan staan ze alvast gecached.

[.oisyn]

Separating axis theorem. Is in 2d vrij simpel. Als A de quad van het scherm is en B de polygoon, dan doe je voor elke plane van A en elke plane van B: projecteer A en B op de normal van die plane en test op 1D overlap. 100% accuraat, geen false positives (of false negatives).

De planes van A is wat feitelijk hier al in de topic genoemd is. Maar als je ook nog de planes van B zelf test, dan haal je de overige false positives eruit .

Als je quads rechthoeken zijn (dus met hoeken van 90 graden) is de projectie heel simpel te berekenen. Zo niet, dan moet je even alle vertices langs lopen om de min en max te bepalen. De projectie van A is helemaal simpel, aangezien dat een axis aligned rectangle is. Als je A beschrijft met een center vector en een extents vector, dan is de projectie:

code:

float c = n * quad.center;
float x = abs(n) * quad.extents;
float min = c - x;
float max = c + x;

waarbij abs() op een vector simpelweg een component-wise absolute is. En de * is een dotproduct.

[ Voor 74% gewijzigd door .oisyn op 03-06-2010 17:57 ]

[.oisyn]

Werkt trouwens ook in 3D als je tegen het frustum wilt testen. Scheelt je wellicht een projectie, maar aan de andere kant is de test ook wat duurder (voor elke combinatie van een edge van het frustum en een edge van je quad moet je nog een plane normal maken (cross product) om tegen te testen)

[Soultaker]

De separating axis theorem lijkt me de meest simpele en efficient methode om from scratch te programmeren, maar als je al wat primitieven hebt kun je ook wel een ad-hoc methode construeren.

Met twee verschillende polygonen (zeg A en B) zijn er precies vier verschillende situaties:

1. A en B overlappen gedeeltelijk
2. B ligt volledig in A
3. A ligt volledig in B
4. A en B zijn gescheiden

De vraag is of situatie 4 zich voordoet. Dat is te bepalen door de andere situaties uit te sluiten. Situatie 1 is het geval wanneer een van de lijnstukken van A een van de lijnstukken van B snijdt. Situatie 2 wanneer alle punten van B binnen A liggen (en omgekeerd voor situatie 3). Al deze dingen zijn eenvoudig te bepalen als je al functies hebt om te bepalen of lijnstukken elkaar snijden en of een punt in een polygon ligt.

(In het geval dat A en B hetzelfde zijn werkt die methode nog steeds, alleen zijn dan toevallig situaties 2 en 3 tegelijk waar.)

[ Voor 7% gewijzigd door Soultaker op 04-06-2010 08:35 ]

[.oisyn]

Ik ben eigenlijk wel benieuwd hoe je het nou hebt aangepakt, en waar het voor was

[Zoijar]

Oh, sorry, ik was het topic even vergeten Bedankt voor de tips in ieder geval!

Ik denk dat ik maar de separating axis theorem ga gebruiken. Ik moet het toch from-scratch maken, en dat is vrij simpel te implementeren, werkt goed, en is efficient. Op het moment gebruik ik het alleen een kant op (dus effectief de AABB van de quad, wat Janoz zei)

Het is voor een aligned image stack viewer; plaatjes uit verschillende type microscopen/scanners van zeg 40k bij 40k (1.6 gigapixel...die laad je niet even in een texture ) die onderling over elkaar gelegd moeten worden en afgebeeld (vandaar support voor een similarity transform en eventueel later een projectie). Eigenlijk moet ik het ook andersom aanpakken: gewoon meteen kijken welke set visible is, ipv elk blokje af te gaan en te kijken of het zichtbaar is. Denk dat ik dat later sowieso verander... maar ik heb tegenwoordig weinig tijd om te programmeren, dus ik heb vaak even quick'n'dirty "RAD" oplossingen nodig om een concept te testen.

[ Voor 6% gewijzigd door Zoijar op 08-06-2010 15:21 ]

[Big Womly]

via het Z-Buffer Algorithm?

[.oisyn]

Zoijar schreef op dinsdag 08 juni 2010 @ 15:18:
Eigenlijk moet ik het ook andersom aanpakken: gewoon meteen kijken welke set visible is, ipv elk blokje af te gaan en te kijken of het zichtbaar is.

Dat lijkt me nuttiger ja. De hoekpunten van je scherm backprojecten op de image, zodat je veel efficienter de juiste deelgebieden eruit kunt halen. Tenminste, ik neem aan dat die images verder zijn opgedeeld in een regulier grid om dat hanteerbaar te houden?

Maar interessant project

Big Womly schreef op dinsdag 08 juni 2010 @ 15:31:
via het Z-Buffer Algorithm?

Dank voor deze klok-klepel reactie

[Mischa_NL]

Klinkt als perfect voor een quadtree!
Dynamisch in en uitladen en visibility tegen de quadtree testen.