[openGL] Zichtbare vertices vinden

[Verwijderd]

Voor vertex selection in mijn applicatie heb ik een lijst met vertices nodig die zichtbaar zijn als mijn model gerenderd wordt. Ik wil dus geen vertices in mijn lijst hebben die achter driehoeken verscholen liggen. Heeft iemand een idee hoe dit voor elkaar te krijgen is?

[dusty]

Wiskunde.

[Verwijderd]

In dit geval zou het dan worden:

- Verzamel alle punten van de driehoeken die met de normaal naar je toe staan gericht.
- Ga voor elk punt na of hij verscholen wordt door een driehoek.
- Bereken voor elk punt zijn 2d scherm coordinaten

Dit is erg rekenintensief. Ik had gehoopt dat OpenGL hierbij kon helpen.

[Soultaker]

Ik zou me kunnen voorstellen dat je eventueel de Z-buffer van OpenGL zou kunnen gebruiken om uit te zoeken welke pixels bij welke polygonen horen, maar zelfs als dat mogelijk is (ken helaas de API niet), heb je dan informatie over polygonen en niet over de vertices. OpenGL kan echter ook wel vertices, renderen, maar ik kan me voorstellen dat je dan allemaal lastige randgevallen krijgt, van vertices die wiskundig gezien beiden zichtbaar zijn, maar door de beperkte resolutie van je Z-buffer elkaar toch overlappen.

Als het exact moet, is het dus toch handig om het softwarematig (en handmatig) te doen.

[Janoz]

Aan OpenGL zul je waarschijnlijk erg weinig hebben. Het kosten baten plaatje van deze operatie is bij realtime rendering namelijk niet zo gunstig. De tijd die het kost om deze punten te vinden is namelijk veel groter dan ze gewoon maar te tekenen. Meestal word gewoon backface culling icm frustrum clipping gewerkt. Occlusion wordt over het algemeen gewoon opgelost met een z-buffer.

[Verwijderd]

Kijk eens naar glFeedbackBuffer en glSelectBuffer.

[.oisyn]

Je zou als eerste stap naar de normals van de omliggende faces kunnen kijken. Als die allemaal backfacing zijn, is je vertex ook niet zichtbaar

Zitten er frontfacing polygonen bij, dan moet je uiteindelijk gewoon een lijn trekken vanuit het oogpunt naar de vertex doet, zoals een raytracer dat doet.

[.oisyn]

Verwijderd schreef op 23 September 2003 @ 10:45:
Kijk eens naar glFeedbackBuffer en glSelectBuffer.

Je kunt daar zelf beter eens naar kijken, dan kom je erachter dat de topicstarter daar helemaal niets aan heeft

[Verwijderd]

Verwijderd schreef op 23 September 2003 @ 10:45:
Kijk eens naar glFeedbackBuffer en glSelectBuffer.

Dat heb ik gedaan. Die functies gebruik ik voor vele andere dingen. Helaas voldoen ze hiervoor niet.

Ik doe het nu maar met de hand. Inderdaad zoals .oisyn zegt op de "ray trace" manier. Ik hoop alleen dat het snel genoeg is. Daarna kan ik wel met behulp van glFeedbackBuffer de 2d window coordinaten vinden om te kijken waar de cursor het meest dichtbij is.

[.oisyn]

Daarna kan ik wel met behulp van glFeedbackBuffer de 2d window coordinaten vinden om te kijken waar de cursor het meest dichtbij is.

dat kun je natuurlijk ook zelf berekenen, het is niet sneller als je het door OpenGL laat doen. Sterker nog, als je hardware t&l hebt, dan is het zelfs langzamer, omdat de videokaart er niet voor gemaakt is om data terug te sturen

[Janoz]

[b][message=18815084,noline]Kurzweil_ schreef op 23 september 2003 @
Ik doe het nu maar met de hand. Inderdaad zoals .oisyn zegt op de "ray trace" manier. Ik hoop alleen dat het snel genoeg is. Daarna kan ik wel met behulp van glFeedbackBuffer de 2d window coordinaten vinden om te kijken waar de cursor het meest dichtbij is.

Even de glFeedbackBuffer buiten beschouwing laten (ik denk, net als oisyn, dat je dit sowieso beter zonder openGl op kunt lossen) is het misschien handiger om dit andersom te doen. Een muisklik is in principe niet meer dan een lijn door 3d. Om een marge te hebben kun je er ook een frustrum of een afgeknote kegel van maken (uitlopende vorm is om te compenseren dat een vertex die ver weg ligt, nog steeds x pixels naast de muisklik ligt). Als je eerst je objecten tegen dit frustrum clipt en vervolgens de overgebleven vertices van de overgebleven objecten gaat checken (of nog een keer clippen) scheelt dit behoorlijk wat tijd. De overgebleven vertices kun je vervolgens redelijk snel clippen aangezien je al een selectie hebt van alles wat binnen het frustrum ligt en dus voor de vertex zou kunnen liggen.

[Verwijderd]

Ik moet wel eerst alle vertices hebben aangezien de gebruiker feedback moet hebben over welke vertex er geselecteerd gaat worden als hij klikt.
Als een gebruiker klaar is met roteren (de muisknop los laat) worden de zichtbare vertices berekend. Tijdens een mousemove wordt er gewoon door de lijst met vertices geitereerd. De dichtstbijzijnde vertex wordt dan ge-highlight.

[Verwijderd]

.oisyn schreef op 23 September 2003 @ 11:41:
[...]

dat kun je natuurlijk ook zelf berekenen, het is niet sneller als je het door OpenGL laat doen. Sterker nog, als je hardware t&l hebt, dan is het zelfs langzamer, omdat de videokaart er niet voor gemaakt is om data terug te sturen

Oh, dat is wel handig om te weten. Ach, als ik toch al alles met de hand doe kan dit er ook nog wel bij.

[Verwijderd]

Das balen zeg:

Ga voor elk punt na of hij verscholen wordt door een driehoek.

Dit deel duurt dus echt veel te lang.

Heeft iemand nog een andere oplossing voor mijn probleem?
Nog even voor de duidelijkheid mijn huidige algoritme:

- Ik heb een model bestaande uit driehoeken.
- Ik verwijder alle driehoeken met een normaal van mij af
- Ik maak een lijst met alle punten van de overgebleven driehoeken
- Voor elk punt kijk ik of hij achter een driehoek ligt. Dit laatste doe ik voor het gemak in 2d.

Het laatste punt is in tegenstelling tot de andere punten exponentieel in tijd en dit duurt daarom veel te lang.

[ Voor 54% gewijzigd door Verwijderd op 23-09-2003 15:08 ]

[.oisyn]

Verwijderd schreef op 23 September 2003 @ 14:55:
Das balen zeg:

Dit deel duurt dus echt veel te lang.

dat ligt meer aan jouw code/algoritme dan aan het idee zelf

Heeft iemand nog een andere oplossing voor mijn probleem?
Nog even voor de duidelijkheid mijn huidige algoritme:

- Ik heb een model bestaande uit driehoeken.
- Ik verwijder alle driehoeken met een normaal van mij af
- Ik maak een lijst met alle punten van de overgebleven driehoeken
- Voor elk punt kijk ik of hij achter een driehoek ligt. Dit laatste doe ik voor het gemak in 2d.

Het laatste punt is in tegenstelling tot de andere punten exponentieel in tijd en dit duurt daarom veel te lang.

waarom doe je dat voor elk punt? Je wilt toch alleen bepaalde punten weten, namelijk die het dichtst bij je muis ligt?

[Verwijderd]

waarom doe je dat voor elk punt? Je wilt toch alleen bepaalde punten weten, namelijk die het dichtst bij je muis ligt?

Verwijderd schreef op 23 September 2003 @ 12:57:
Ik moet wel eerst alle vertices hebben aangezien de gebruiker feedback moet hebben over welke vertex er geselecteerd gaat worden als hij klikt.
Als een gebruiker klaar is met roteren (de muisknop los laat) worden de zichtbare vertices berekend. Tijdens een mousemove wordt er gewoon door de lijst met vertices geitereerd. De dichtstbijzijnde vertex wordt dan ge-highlight.

Ik wil het van te voren uitrekenen omdat het vervelend voor de gebruiker is als er tijdens een mousemove dingen worden berekend. Ik zou inderdaad tijdens een mousemove alleen in een straal van 50 pixels kunnen zoeken naar punten en kijken of die punten wel zichtbaar zijn. Toch is het soms wel handig als er een vertex ge-highlight wordt als je redelijk ver van een vertex vandaan bent. Zo kun je makkelijk de rand van een model selecteren.

[ Voor 9% gewijzigd door Verwijderd op 23-09-2003 15:39 ]

[Janoz]

Het lijkt me dat veel minder dan 50 pixels ook voldoende is. Het lijkt me niet dat mensen perse verwachten dat elke muisklik een geselecteerd punt oplevert. Waneer er geen punt in de buurt van mijn cursor is verwacht ik ook niet dat er wat op gaat lichten en dat ik wat selecteer als ik druk. In dat geval kun je de frustrum oplossing van mij gebruiken om een flinke reductie (en dus optimalisatie) in het aantal vertices te krijgen.

Altijd de dichtsbijzijnde zichtbare vertex vinden is inderdaad een erg dure operatie.

[Verwijderd]

Altijd de dichtsbijzijnde zichtbare vertex vinden is inderdaad een erg dure operatie.

Als het probleem niet op te lossen is veranderen we de specificaties maar Alleen in een kleine straal zoeken en dan houd ik ook maar een cache bij met vertices waarvan ik het antwoord al weet.

[Soultaker]

Als je model en viewport vast staan (wat het geval lijkt te zijn, als je de boel wilt precalculeren/cachen), dan kun je natuurlijk ook eenmalig de 2D-projectie uitvoeren en per vertex het 2D-gebied vastleggen waarbinnen alle punten het dichtst bij die vertex liggen. Dat is een verzameling van schermvullende, niet-overlappende convexe polygonen, waar je dus makkelijk op kan testen. Als het om run-time efficientie gaat kun je nog een quadtree gebruiken om het aantal tests te reduceren.

[Verwijderd]

Als het om run-time efficientie gaat kun je nog een quadtree gebruiken om het aantal tests te reduceren.

Daar had ik ook al aan gedacht maar ik vrees dat het maken van een quadtree ook al te lang duurt om "even" te berekenen elke keer dat de gebruiker heeft geroteerd. In elk geval heb ik weer ideeen om weer een dagje te programmeren. Bedankt allemaal!