inside quad = true [Erledigt]

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

hectic

Sieger des IS Talentwettbewerb 2006

Betreff: inside quad = true [Erledigt]

BeitragSa, Nov 14, 2015 18:08
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich suche eine einfache Methode um festzustellen, ob sich ein Punkt (zum Beispiel die Maus) innerhalb eines Quads befindet. Allerdings soll es unabhängig der Zeichne-Drehrichtung des Quads geprüft werden.

user posted image

Die gelben Flächen gelten als Detektionsflächen. Bisher habe ich es (nur rechts rum) wie folgt gemacht:

Code: [AUSKLAPPEN]
;QUADKOLLISION
If (Y2-Y1)*(XMouse-X2)-(X2-X1)*(YMouse-Y2)=>0 Then
   If (Y3-Y2)*(XMouse-X3)-(X3-X2)*(YMouse-Y3)>0 Then
      If (Y4-Y3)*(XMouse-X4)-(X4-X3)*(YMouse-Y4)>0 Then
         If (Y1-Y4)*(XMouse-X1)-(X1-X4)*(YMouse-Y1)=>0 Then
            ;DETEKTIERT
            
         End If
      End If
   End If
End If

Und natürlich könnte man die Abfrage doppel, und somit zusätzlich, mit vertauschen Koordinaten durchlaufen lassen. Aber es muss doch eine simplere Lösung geben?
  • Zuletzt bearbeitet von hectic am Sa, Nov 14, 2015 19:48, insgesamt einmal bearbeitet

TimBo

BeitragSa, Nov 14, 2015 18:45
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi Hectic,

Version 1:
warum nicht einfach die PickingTextur auslesen ?

Version 2: berechne aber
Wenn du es sonst ganz genau wissen willst, musst du schauen, wie der Rasterizer konfiguriert ist:
https://msdn.microsoft.com/de-...85%29.aspx

Version 3:
Deine Methode scheint ja bereits zu funktionieren. Berechne doch den Mittelpunkt der 4 Punkte und sortiere sie so , dass sie "rechts rum" liegen.

Grüße,
TimBo
mfg Tim Borowski // CPU: Ryzen 2700x GPU: Nvidia RTX 2070 OC (Gigabyte) Ram: 16GB DDR4 @ 3000MHz OS: Windows 10
Stolzer Gewinner des BCC 25 & BCC 31
hat einen ersten Preis in der 1. Runde beim BWInf 2010/2011 & 2011/12 mit BlitzBasic erreicht.

hectic

Sieger des IS Talentwettbewerb 2006

BeitragSa, Nov 14, 2015 19:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi TimBo,

Zu Version 1: ich bin kein Freund von Auslagerung, die im Grunde wieder neue Probleme bringen könnten.

Zu Version 2: Ich wollte möglichst Sortierungen und Doppeltberechnungen vermeiden.

Zu Version 3: Siehe Version 2. Ich habe gehofft es direkt berechnen zu können. Bei einem Quad aber vermutlich rein mathematisch schon gar nicht möglich.

Aber danke für deine Tipps. Denn diese haben mich auf etwas anderes gebracht. Nämlich nicht den Quad, als eher diesen in zwei Triangles zu berechnen. Hat in meinem Projekt dann auch noch weitere Vorteile. Meine Lösung sieht nun wie folgt aus:

Code: [AUSKLAPPEN]
Graphics 800,800,0,2
SetBuffer BackBuffer()

Local Timer=CreateTimer(58)
ClsColor 64,64,64

Local x1,y1
Local x2,y2
Local x3,y3
Local zz#=0
Local xx,yy

While Not KeyHit(1)
   
   zz=zz+0.02
   
   For yy=0 To 800 Step 10
      For xx=0 To 800 Step 10
         
         Color pointInTriangle(x1,y1,x2,y2,x3,y3,xx,yy)*255,0,0
         
         Rect xx-5,yy-5,10,10,1
      Next
   Next
   
   x1=MouseX():y1=MouseY()
   x2=400+Sin(zz*15)*450:y2=400+Cos(zz*40)*450
   x3=400+Sin(zz*35)*450:y3=400+Cos(zz*50)*450
   
   Color(128,128,128)
   Line x1,y1,x2,y2
   Line x2,y2,x3,y3
   Line x1,y1,x3,y3
   
   Color(255,255,255)
   Text x1-20,y1-6,"eins"
   Text x2-20,y2-6,"zwei"
   Text x3-20,y3-6,"drei"
   
   WaitTimer(Timer)
   Flip 0
   Cls
Wend

Function pointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
   Local a#,b#,c#,denominator#
   
   denominator = ((y2 - y3)*(x1 - x3) + (x3 - x2)*(y1 - y3))
   a = ((y2 - y3)*(x - x3) + (x3 - x2)*(y - y3)) / denominator
   b = ((y3 - y1)*(x - x3) + (x1 - x3)*(y - y3)) / denominator
   c = 1 - a - b
   
   Return 0 <= a And a <= 1 And 0 <= b And b <= 1 And 0 <= c And c <= 1
End Function

Hab ich aus folgenden Link konvertiert: http://totologic.blogspot.de/2...-test.html
Download der Draw3D2 V.1.1 für schnelle Echtzeiteffekte über Blitz3D

TimBo

BeitragSa, Nov 14, 2015 22:45
Antworten mit Zitat
Benutzer-Profile anzeigen
alles klar Smile

was du noch machen kannst, ist in der Implmentatino von Boost zu schauen:
http://www.boost.org/doc/libs/...hin_2.html
die scheinen soetwas zu haben.


oder auch in der Implementation von SharpDX, denke, dass sie auch eine solche Funktion Punkt in Dreieck haben.

Das "schwere" ist einen stabilen Algorithmus zu bauen.
Habe das Buch RealTimeRendering gerade nicht zur Hand, sonst hätte ich da auch mal geschaut.

Wie hast du das gelöst, dass du ganz genau wie der Rasterizer entscheidest, ob du innerhalb bist oder nicht?
Gibt es bei dir keine Fälle, bei der die Lösung deines Ansatzes andere Ergebnisse bringt, als man auf dem Bildschirm sieht? Sprich die Maus ist über keinem Pixel des Dreiecks und trotzdem ist deine Berechnung true.

Grüße,
TimBo
mfg Tim Borowski // CPU: Ryzen 2700x GPU: Nvidia RTX 2070 OC (Gigabyte) Ram: 16GB DDR4 @ 3000MHz OS: Windows 10
Stolzer Gewinner des BCC 25 & BCC 31
hat einen ersten Preis in der 1. Runde beim BWInf 2010/2011 & 2011/12 mit BlitzBasic erreicht.

hectic

Sieger des IS Talentwettbewerb 2006

BeitragSo, Nov 15, 2015 1:08
Antworten mit Zitat
Benutzer-Profile anzeigen
Die Formel aus dem Anfangspost ist absolut genau. Das habe ich extra mit mehreren Hundertausend Rechenzyklen zwischen genau zwei rotierenden Quads geprüft. Es durften in diesem Testscenario niemals zwei Quads gleichzeitig selektiert, wie auch dass beide einfach übersehen werden, vorkommen. Die Kameraperspektive, da die Draw3D2 eben auch 2D-Elemente die sich frei um 3D-Raum befinden selektieren kann, spielt hierbei keine Rolle. Ich war selbst verblüfft, dass nicht ein einziger Rundungsfehler vorgekommen war.

Beispielcode findet sich in der Draw3D2\Draw3D2 Stuff, 3D Board Game.bb aus der Draw3D2. Siehe Signatur. Hier handelt es sich um ein Schachbrett welches im 3D-Raum positioniert ist. Mit der Maus kann man auf dem rotierbarem Schachbrett die Quads auswählen die durch ein Glow gekennzeichnet werden. Der Fall das mal kein Quad oder zwei auf einmal aufleuchten, kommt nicht vor. Die Prüfung erfolgt hier keinesfalls durch Ausschlussverfahren. Zeichnet man die Quads einfach mal nicht mit dem Abstand von 64 zueinander, dann überlappen sich diese und Doppeltgenzeichnungen sind gegeben, oder es entstehen eben Lücken.

Ob die Dreiecksvariante auch so perfekt ist, hab ich noch nicht geprüft. Letztendlich müsste es durch die ">" oder "=>" genau deklariert werden können. Natürlich werde ich auch hier die bestmögliche Variante suchen und eben erneut alles durchprüfen, dass eben keine Fehler entstehen.
Download der Draw3D2 V.1.1 für schnelle Echtzeiteffekte über Blitz3D

DAK

BeitragSo, Nov 15, 2015 9:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Was du auch machen kannst, ist, du stellst die vier Geradengleichungen der Kanten auf. Dann setzt du deinen Punkt, den du testen willst, in alle dieser Gleichungen ein und nimmst dann das Produkt der vier Ergebnisse. Ist das Produkt > 0, dann liegt der Punkt drinnen, ist es = 0, dann ist der Punkt auf einer der Geraden. Ist er < 0, dann ist er draußen. Wichtig dabei ist, dass für =0 auch die Verlängerungen der Geraden zählen, also kann da der Punkt auch außerhalb liegen, also check am Besten nur auf >0.
Gewinner der 6. und der 68. BlitzCodeCompo
 

Kruemelator

BeitragDi, Nov 17, 2015 11:50
Antworten mit Zitat
Benutzer-Profile anzeigen
Prüfe ob dein Punkt im Dreieck (1,2,3) und (3,4,1) liegt. Liegt er in nur einem der beiden hast du einen Treffer. Liegt er in keinem hast du keinen Treffer. Wenn der in beiden liegt dann musst du prüfen ob er auf der Gerade (1,3) liegt, tut er das dann ist es ein Treffer. Ist der Punkt aber nicht auf der Geraden dann liegt er mittig in beiden Dreieck was bedeuten würde dass das Quad ein Kreuz bildet und der Punkt außerhalb liegt (bei deinen Beispielen solletst du mal die Flächen der Dreiecke (1,2,3) und (3,4,1) unterschiedlich einfärben dann wird meine Idee verständlich )

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group