inside quad = true [Erledigt]

Übersicht

BlitzBasic

Allgemein

	hectic Sieger des IS Talentwettbewerb 2006 Betreff: inside quad = true [Erledigt]	Sa, Nov 14, 2015 18:08 Antworten mit Zitat
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. Die gelben Flächen gelten als Detektionsflächen. Bisher habe ich es (nur rechts rum) wie folgt gemacht: Code: [AUSKLAPPEN] [EINKLAPPEN] ;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?

hectic

Sieger des IS Talentwettbewerb 2006

Betreff: inside quad = true [Erledigt]

Sa, Nov 14, 2015 18:08
Antworten mit Zitat

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	Sa, Nov 14, 2015 18:45 Antworten mit Zitat
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.

TimBo

Sa, Nov 14, 2015 18:45
Antworten mit Zitat

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	Sa, Nov 14, 2015 19:47 Antworten mit Zitat
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] [EINKLAPPEN] 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(zz15)450:y2=400+Cos(zz40)450 x3=400+Sin(zz35)450:y3=400+Cos(zz50)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

hectic

Sieger des IS Talentwettbewerb 2006

Sa, Nov 14, 2015 19:47
Antworten mit Zitat

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	Sa, Nov 14, 2015 22:45 Antworten mit Zitat
alles klar 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.

TimBo

Sa, Nov 14, 2015 22:45
Antworten mit Zitat

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

	hectic Sieger des IS Talentwettbewerb 2006	So, Nov 15, 2015 1:08 Antworten mit Zitat
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

hectic

Sieger des IS Talentwettbewerb 2006

So, Nov 15, 2015 1:08
Antworten mit Zitat

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	So, Nov 15, 2015 9:46 Antworten mit Zitat
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

DAK

So, Nov 15, 2015 9:46
Antworten mit Zitat

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	Di, Nov 17, 2015 11:50 Antworten mit Zitat
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 )

Kruemelator

Di, Nov 17, 2015 11:50
Antworten mit Zitat

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 )

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

inside quad = true [Erledigt]

hectic

Betreff: inside quad = true [Erledigt]

TimBo

hectic

TimBo

hectic

DAK

Kruemelator