[c/c++]Detectie van een cirkel in de 3d ruimte in 2d

[Stukfruit]

Na vele pogingen begin ik het bijna op te geven, maar omdat ik erg veel interesse heb in het vinden van een oplossing doe ik nog even een laatste poging.

Mijn doel is om uit te vinden hoe ik een cirkel in de 3d ruimte onder de muiscursor kan detecteren. Na een eerste indruk lijkt dit niet zo moeilijk; je kan bijvoorbeeld een lijn/ray van onder de muis de 3d ruimte inschieten, de cirkel voorstellen als een plane en die gebruiken om de lijn of ray op te projecteren. Daarna maak je een lokale ruimte aan op de plane, kan je in die ruimte een semi-2d test doen om te controleren welk punt op de cirkel het dichtst bij het geprojecteerde punt ligt en na een transformatie terug naar world space en de projectie terug naar 2d coordinaten kan dan uiteindelijk worden gecontroleerd hoeveel pixels de twee punten van elkaar af liggen. Liggen ze dicht genoeg bij elkaar, dan is er een hit.

Maar dit werkt niet echt, want de cirkel moet bv ook van de zijkant te detecteren zijn. En de rays van onder de muiscursor schieten daar vrolijk langs zonder ooit de plane waar de cirkel in ligt op te merken, want dat ding is oneindig flinterdun.

Voor een lijn in de 3d ruimte is het simpel (projecteer de 2 lijnpunten naar 2d en zoek uit of een punt in de buurt van dat 2d lijnsegment ligt - zie ook dit), maar een cirkel is blijkbaar wat (veel) moeilijker...

Zijn hier misschien mensen die zoiets ook wel eens hebben gedaan en weten hoe ik dit handig op kan lossen?

Als allerlaatste poging zou ik nog heel simpel de segmenten van de cirkel (zoals deze ook getekend wordt via OpenGL) kunnen gebruiken om diezelfde lijntests op uit te voeren, maar ik vind dat eigenlijk een beetje vies. En hoe groter de cirkel in 2d getekend wordt, hoe meer tests er gedaan moeten worden, wat ook niet handig is.

[Killemov]

Op zich zou de manier waarop je het in eerste instantie probeert goed te doen moeten zijn. Je zult aan je ray wel een maximale diepte mee moeten geven. Meestal is dit gewoon een door jezelf aangenomen waarde of een backend clipping van je frustum. Als je het old-skool wil proberen moet je eens naar een simpele z-sort kijken, wellicht in combinatie met id-coloring.

[Semyon]

Stukfruit schreef op woensdag 03 februari 2010 @ 00:27:
Maar dit werkt niet echt, want de cirkel moet bv ook van de zijkant te detecteren zijn. En de rays van onder de muiscursor schieten daar vrolijk langs zonder ooit de plane waar de cirkel in ligt op te merken, want dat ding is oneindig flinterdun.

Dit snap ik niet. Als je er langs schiet dan mis je toch? Dat is toch juist wat je wilt? Hij gaat dan toch ook niet door de cirkel, maar erlangs? Als je dat niet wilt, wil je dus meer dan alleen kijken of hij door de cirkel gaat. Wil je misschien kijken of hij door een plat cilindertje gaat ofzo, een cirkeltje met een kleine dikte, wat wil je precies?

Volgens mij is je probleem een definitie probleem. Als je eerst duidelijk kan stellen wat je wilt kan je daarna naar de oplossing zoeken. Maar de oplossing die je nu geeft is een oplossing voor het probleem dat je geeft, maar je bent daar niet helemaal blij mee omdat je iets meer wilt dan het probleem dat je geeft... Maar wat? Je moet het probleem even duidelijk opschrijven.

[NC83]

In principe heb je enkel de straal van je cirkel nodig en het projectie punt van je cursor nodig. Het projectie punt ligt dan binnen de cirkel als ((xm - xp)² + (ym-yp)²) - r² <= 0. Deze vergelijken houdt zelfs op voor 3D point, sphere detection. Wat deze vergelijking doet is kijken of de afstand tussen projectie punt en middelpunt cirkel kleiner of gelijk is aan de straal van je cirkel.

Je hoeft niet het preciese punt op de cirkel te vinden waar de muis cursor is zodra je weet dat de cursor zich binnen de straal bevindt weet je dat de cirkel onder de muis cursor bevindt.

Als je het lijnstuk hebt kun je in feite met een for loop kijken of deze lijn de cirkel snijdt door middel van het oplossen van de vergelijken. Stap niet sneller dan de diameter van de cirkel over je lijn en zelfs dan heb je kans dat je de cirkel mist. Maar als je een kleine afwijking toestaat kun je ray marching toepassen en dan wordt het probleem een cirkel-cirkel intersectie en die ook op te lossen met bovenstaande vergelijking enkel moet je niet de vergeten het kwadraat van de straal van de tweede cirkel bij de eerste op te tellen.

[ Voor 72% gewijzigd door NC83 op 03-02-2010 01:12 ]

[.oisyn]

Je wil een ray-torus intersectie, maar ipv het jezelf moeilijk te maken zou ik de cirkel gewoon converteren naar lijnstukken.

Killemov schreef op woensdag 03 februari 2010 @ 00:51:
Op zich zou de manier waarop je het in eerste instantie probeert goed te doen moeten zijn.

Alleen als het vlak waarin de cirkel ligt loodrecht op de kijkvector ligt. Je wilt de detectie namelijk doen met minimale afstanden in image space (pixels), op het moment dat je vrijwel haaks op het vlak kijkt kan een intersectie van de ray met het vlak in world space heel ver van de cirkel afliggen, terwijl hij er op het scherm maar een paar pixels naast zit.

NC83 schreef op woensdag 03 februari 2010 @ 01:01:
In principe heb je enkel de straal van je cirkel nodig en het projectie punt van je cursor nodig. Het projectie punt ligt dan binnen de cirkel als ((xm - xp)² + (ym-yp)²) - r² <= 0.

Jij hebt het over een schijf, de TS heeft het over een cirkel. Een cirkel bestaat alleen uit z'n rand, een schijf bestaat uit de rand plus dat wat er binnenin ligt. Daarnaast werkt je beredening niet, zoals ik hierboven al zei.

[ Voor 26% gewijzigd door .oisyn op 03-02-2010 01:18 ]

[Stukfruit]

Killemov schreef op woensdag 03 februari 2010 @ 00:51:
Op zich zou de manier waarop je het in eerste instantie probeert goed te doen moeten zijn. Je zult aan je ray wel een maximale diepte mee moeten geven. Meestal is dit gewoon een door jezelf aangenomen waarde of een backend clipping van je frustum. Als je het old-skool wil proberen moet je eens naar een simpele z-sort kijken, wellicht in combinatie met id-coloring.

Maximale diepte is geen probleem, het gaat niet om erg veel cirkels en ze zitten altijd binnen het frustum. Id coloring is waar ik hier juist van af wil komen

Semyon schreef op woensdag 03 februari 2010 @ 01:00:
Dit snap ik niet. Als je er langs schiet dan mis je toch? Dat is toch juist wat je wilt? Hij gaat dan toch ook niet door de cirkel, maar erlangs? Als je dat niet wilt, wil je dus meer dan alleen kijken of hij door de cirkel gaat. Wil je misschien kijken of hij door een plat cilindertje gaat ofzo, een cirkeltje met een kleine dikte, wat wil je precies?

In dit geval niet, want zoals .oisyn al goed opmerkte is het de bedoeling dat de cirkel in screen space een paar pixels naast de cursor kan liggen, terwijl dat in de 3d ruimte helemaal niet het geval is.

De cirkels kunnen verschillende groottes hebben, en het gaat echt om een cirkel waarvan ik wil weten op welke plek op de rand van de cirkel de muiscursor het dichtst in de buurt komt.

Zie ook onderstaande afbeelding:


Rond de rand (niet de schijf) van die cirkel wil ik bijvoorbeeld 5 pixels (in screen space!) ruimte hebben waarin de cirkel gedetecteerd kan worden. Dit moet echt in pixels zijn, vandaar het rare onderwerp van dit topic. Binnen de aangegeven streep/punten op de afbeelding wil ik rond de hele rand van de cirkel in die ruimte de cirkel kunnen waarnemen.

NC83 schreef op woensdag 03 februari 2010 @ 01:01:
In principe heb je enkel de straal van je cirkel nodig en het projectie punt van je cursor nodig. Het projectie punt ligt dan binnen de cirkel als ((xm - xp)² + (ym-yp)²) - r² <= 0. Deze vergelijken houdt zelfs op voor 3D point, sphere detection. Wat deze vergelijking doet is kijken of de afstand tussen projectie punt en middelpunt cirkel kleiner of gelijk is aan de straal van je cirkel.

Dat gebruik ik inderdaad om in screen space te controleren of twee punten dicht genoeg bij elkaar in de buurt liggen (wat idd ook werkt na het terugprojecteren van de 2 punten zoals ik in de ts omschreef), maar zoals ook al door .oisyn opgemerkt wil ik juist de rand hebben

.oisyn schreef op woensdag 03 februari 2010 @ 01:11:
Je wil een ray-torus intersectie, maar ipv het jezelf moeilijk te maken zou ik de cirkel gewoon converteren naar lijnstukken.

Daar heb ik inderdaad ook nog aan gedacht, maar is het dan ook nog mogelijk om (zoals hierboven geschreven) bv 5 pixels rondom de cirkel te hebben als ruimte waarin de cirkel gedetecteerd kan worden?

Voor zover ik weet kan dat met een ray-torus intersectie helaas niet echt. Misschien mis ik een techniek waar ik nog niet van weet?

Alleen als het vlak waarin de cirkel ligt loodrecht op de kijkvector ligt. Je wilt de detectie namelijk doen met minimale afstanden in image space (pixels), op het moment dat je vrijwel haaks op het vlak kijkt kan een intersectie van de ray met het vlak in world space heel ver van de cirkel afliggen, terwijl hij er op het scherm maar een paar pixels naast zit.

[...]

Jij hebt het over een schijf, de TS heeft het over een cirkel. Een cirkel bestaat alleen uit z'n rand, een schijf bestaat uit de rand plus dat wat er binnenin ligt. Daarnaast werkt je beredening niet, zoals ik hierboven al zei.

Juist, dat is het idd precies

[Soultaker]

Ik zou iets lames doen als de cirkel op het scherm projecteren, en dan de detectie gewoon in het 2D scherm doen, niet in de 3D ruimte. Een cirkel onder parallelprojectie wordt een ellips; de afstand (in pixels) van een punt tot een ellips zou niet zo ingewikkeld moeten zijn. Andere projecties zijn wellicht tricky, maar dan kun je nog lamer je cirkel benaderen met een aantal punten en hetzelfde doen.

[.oisyn]

Stukfruit schreef op woensdag 03 februari 2010 @ 09:50:
Daar heb ik inderdaad ook nog aan gedacht, maar is het dan ook nog mogelijk om (zoals hierboven geschreven) bv 5 pixels rondom de cirkel te hebben als ruimte waarin de cirkel gedetecteerd kan worden?

Good point, je zou de dikte van de torus dynamisch kunnen instellen afhankelijk van de afstand tot de camera, maar je zal altijd hebben dat de rand die dichterbij de camera ligt er dan dikker op het scherm uitziet dan de rand die er verder vanaf ligt.

Soultaker schreef op woensdag 03 februari 2010 @ 10:17:
Andere projecties zijn wellicht tricky, maar dan kun je nog lamer je cirkel benaderen met een aantal punten en hetzelfde doen.

Zoals ik al zei, dan kun je beter gewoon de cirkel opdelen in lijnstukken. Vervolgens kun je de intersectie gewoon in 2d doen, na de transformatie van de 3d lijnstukken naar screen space

[Stukfruit]

Tja, ik vreeste er eigenlijk al een beetje voor dat het de enige mogelijkheid zou worden

Nouja, ik laat het nog even rusten en dan zien we wel of er nog een beter idee komt opborrelen. Voorlopig werkt projectie van de cirkel naar screen space op zich wel goed. Bedankt voor het meedenken iig