Autor |
Beitrag |
Noop
Hält's aus hier
Beiträge: 12
Win 98 SE, Win 2000, Win XP SP1, Win XP SP2, Win 2003 Server
D5 Ent., D7 Prof
|
Verfasst: So 20.02.05 17:24
Erstmal zum Mathematischen "Problem":
Man stelle sich ein 3D-Gitter vor (Link zum Bild: hier klicken!), wo ein Strahl durchgeschossen wird.
Der Strahl wird durch den Anfangspunkt "Start" und den Endpunkt "Stop" definiert durch der Prozedur CalculateCollision(Start, Stop, output); berechnet und ermittelt, durch welche gedachte Wand im 3D-Gitter und wo in der gedachten Wand der Strahl überall auftrifft auf dem Weg von Start nach Stop.
Mathematisch heißt das, wann immer auf der Reise vom X-Wert, der Y-Wert oder der Z-Wert der Restwert (hinterm Komma) 0 ist, wird der Wert zur Liste der Treffpunkte hinzugefüht.
Ich habe das mit folgendem Code gelöst:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136:
| type float=extended;
PPoint3DF=^TPoint3DF; TPoint3DF=record x, y, z: single; end;
PPointCL=^TPointCL; TPointCL=record x, y, z: extended; ck:byte; end; TPointCLArray=array of TPointCL;
...
function QFrac(q:extended):extended; begin if q>=0then result:=Frac(q)else result:=1-Frac(-q); end;
function QInt(q:extended):extended; begin result:=abs(floor(q)); if q<0then result:=floor(-1-result); end;
function QSgn(q:extended):shortint; begin result:=0; if q<0then result:=-1; if q>0then result:=1; end;
function ESgn(q:extended):shortint; begin result:=0; if q>=0then result:=1; end;
function EqSgn(q,r:extended):shortint; begin result:=0; if q>=0then result:=1-result; if r>=0then result:=1-result; end;
function CalculateCollision(start,stop:TPoint3DF;var output:TPointCLArray): integer; var i:integer;r:byte; xs,ys,zs,q:extended; xp,yp,zp:extended; qx,qy,qz:extended; qd:extended; p:TPointCL; begin if (Length(output)=0) then begin result:=0; exit; end; i:=0; xs:=stop.x - start.x; ys:=stop.y - start.y; zs:=stop.z - start.z; q:=0; qd:=((Abs(xs)+Abs(ys)+Abs(zs))*1000); if qd=0 then qd:=1 else qd:=1/qd; while i<length(output) do begin q:=q+qd; xp:=start.x+xs*q; yp:=start.y+ys*q; zp:=start.z+zs*q; if xs=0then qx:=high(integer)else qx:=(QInt(xp)+1*ESgn(xs)-start.x)/xs; if ys=0then qy:=high(integer)else qy:=(QInt(yp)+1*ESgn(ys)-start.y)/ys; if zs=0then qz:=high(integer)else qz:=(QInt(zp)+1*ESgn(zs)-start.z)/zs; if(qx<=qy)and(qx<=qz)then begin q:=qx;r:=1; if q>1 then break; p.x:=start.x+xs*q; p.y:=start.y+ys*q; p.z:=start.z+zs*q; p.ck:=r;output[i]:=p;Inc(i); if i>=length(output) then Continue; if (Frac(p.y)=0) and (ys<>0) then begin p.ck:=2;output[i]:=p;Inc(i); if i>=length(output) then Continue; end; if (Frac(p.z)=0) and (zs<>0) then begin p.ck:=3;output[i]:=p;Inc(i); if i>=length(output) then Continue; end; Continue; end; if(qy<=qx)and(qy<=qz)then begin q:=qy;r:=2; if q>1 then break; p.x:=start.x+xs*q; p.y:=start.y+ys*q; p.z:=start.z+zs*q; p.ck:=r;output[i]:=p;Inc(i); if i>=length(output) then Continue; if (Frac(p.x)=0) and (xs<>0) then begin p.ck:=1;output[i]:=p;Inc(i); if i>=length(output) then Continue; end; if (Frac(p.z)=0) and (zs<>0) then begin p.ck:=3;output[i]:=p;Inc(i); if i>=length(output) then Continue; end; Continue; end; if(qz<=qx)and(qz<=qy)then begin q:=qz;r:=3; if q>1 then break; p.x:=start.x+xs*q; p.y:=start.y+ys*q; p.z:=start.z+zs*q; p.ck:=r;output[i]:=p;Inc(i); if i>=length(output) then Continue; if (Frac(p.x)=0) and (xs<>0) then begin p.ck:=1;output[i]:=p;Inc(i); if i>=length(output) then Continue; end; if (Frac(p.y)=0) and (ys<>0) then begin p.ck:=2;output[i]:=p;Inc(i); if i>=length(output) then Continue; end; Continue; end; end; result:=i; |
(
PS Sollte ich irgendeine Unterfunktion vergessen habe, meldet es
PPS Die Arraylänge von output muss vorher mit SetLength gesetzt werden. Diese Länge ist dann das Maximum.
)
Wie kann ich die Berechnung beschleunigen? Die scheint leider etwas langsam zu sein
Was könnte ich verbessern? Oder gibt welche andere (hochoptimierte) Funktion oder hochentwickeltes Prinzip soll ich verfolgen?
Zuletzt bearbeitet von Noop am So 20.02.05 19:05, insgesamt 2-mal bearbeitet
|
|
UGrohne
Beiträge: 5502
Erhaltene Danke: 220
Windows 8 , Server 2012
D7 Pro, VS.NET 2012 (C#)
|
Verfasst: So 20.02.05 17:25
Hallo,
der Titel Deines Beitrages ist nicht aussagekräftigt genug. Man weiß nicht genau, um was es geht. Bitte ändere ihn entsprechend!
Dies kannst Du tun, indem Du in Deinem ersten Beitrag auf "Edit" klickst und den Titel dort änderst.
Dazu hier auch noch der Auszug aus den Richtlinien:
Richtlinien hat folgendes geschrieben: | 1.2 Beiträge
Bitte formuliere den Betreff Deiner Beiträge so, dass andere Mitglieder anhand dieser bereits das eigentliche Thema festmachen können. Beiträge wie etwa "Eine Anfängerfrage" oder "Weiß jemand, wie das geht?" lassen den Leser im Unklaren darüber, was das Thema der Diskussion ist. Eine Pseudocodezeile oder die Nennung des Objektes, um welches es sich in dem Beitrag handelt, helfen da schon mehr weiter. Wenn Du beispielsweise wissen möchtest, wie es möglich ist, eine Integer-Variable in das String-Format zu konvertieren, würde ein Beitrag wie etwa "Integer zu String" oder "Integerkonvertierung" anderen Forenmitgliedern einen kurzen Überblick über die eigentliche Fragestellung verschaffen. So ist es möglich gezielter Lösungen für Probleme zu finden. Zudem solltest du immer daran denken: Der Fragesteller möchte etwas von den anderen Usern - nicht umgekehrt. |
Vielen Dank
Gruß,
uwe
|
|
Spaceguide
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: So 20.02.05 18:24
Ich hab jetzt nicht wirklich verssucht deinen Quellcode zu analysieren (kannst du auch nicht von uns erwarten), aber wenn du einen Strahl mit einem regulären Gitter schneiden willst, kannst du wohl auch irgendeinen Linien-Algorithmus nehmen und ihn auf 3D erweitern.
Double statt Extended nehmen bringt auch ein paar Prozent
|
|
sourcehunter
Beiträge: 482
Win XP | Suse 10.1
Delphi 2005 Pers.
|
Verfasst: So 20.02.05 18:30
So wie ich das beim Überfliegen verstanden hab, gehst du auf dem Strahl entlang, oder? Wenn du schonmal Vektorrechnug gehabt hattest(z.B. in der Schule), dann sollte dir dieses Stichwort das Problem Schnitt von Gerade und Ebene in die Gedanken rufen. Falls du daimt nichts anfangen kannst, dann frag nochmal naah, ich hab grad keine Zeit ins Detail zu gehn.
_________________ Linux und OpenSource rulez!
|
|
Noop
Hält's aus hier
Beiträge: 12
Win 98 SE, Win 2000, Win XP SP1, Win XP SP2, Win 2003 Server
D5 Ent., D7 Prof
|
Verfasst: So 20.02.05 18:50
Ich hatte noch keine Vektoralgebra, aber ich weiß aber trotzdem das man Formeln zB in so einer Richtung wie diese
(Fläche)
x = x1*t + x2*s( + x3)
y = y1*t + y2*s( + y3)
z = z1*t + z2*s( + z3)
(Strahl)
x = x4 + xf*f
y = y4 + yf*f
z = z4 + zf*f
verwenden könnte.
Aber ich habe keine Idee, wie ich so eine Formel für die Suche aller Schnittpunkte einsetzen könnte. (also das er nur die Punkte ausgibt, wo X, Y oder/und Z eine ganze Zahl ist (also Int(A)=A), das sind nämlich die Punkte, die auf einer Wand im Gitter liegt)
PS was ich möchte, hab ich als Bild visualisiert, die bunten Flächen, also die Wände, dessen Koordinaten bin ich interessiert - nicht nur eine Wand, sondern alle Wände, die der Strahl durchbricht von Start nach Stop
|
|
Ich Bins
Beiträge: 197
Win XP Prof
D5 Prof
|
Verfasst: So 20.02.05 20:19
Ich seh das genauso wie sourcehunter, du nimmst einfach nacheinander jede Ebene des Gitters, und guckst, ob und wenn ja in welchem Punkt, der Strahl diese Ebene schneidet. Muss man halt (denk ich mal) für jede Ebene machen, aber dürfte nicht so aufwändig sein.
_________________ Diese Nachricht wurde mit einer Taschenlampe in das offenliegende Ende eines Glasfaserkabels gemorst!
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 20.02.05 20:31
Folgende Units sollten Dir für die Schnittpunktberechnung weiterhelfen:
cvs.sourceforge.net/viewcvs.py/omorphia/omorphia/maths/OMathVector.pas
cvs.sourceforge.net/viewcvs.py/omorphia/omorphia/maths/OMathGeometry.pas
Bei Fragen zu diesen Units einfach ne PN an mich. (Und stör dich nicht an dem ASM dort ^^)
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
|