geometrische Probleme
-
Andrey schrieb:
Jester schrieb:
Wäre echt nett, wenn Dir vielleicht die Zeit nehmen würdest meinen Lösungsansatz vollkommen zu durchdenken. Zwei kleine Hinweise: Es ist Exakt und es werden keine echten Pixel verwendet.
hmm... sry, verstehe das nicht so wirklich.
um zu entscheiden, ob ein pixel "gezeichnet" wird, musst du ja wissen, ob er von den primitiven geschnitten wird oder nicht... wie bringt das denn einen weiter?
Okay, Du hast bemerkt, dass Pixel malen genau das gleiche Problem ist. Prima. Was meinst Du wie Grafikkarten zeichnen? Kollisionstests von Pixelzellen mit den Objekten? -- Nein, das wird anders gemacht. Und diese Algorithmen sollte man zur Lösung des Problems verwenden. Die sind nämlich auf diese spezielle Situation angepaßt.
Wenn die Zellen natürlich nicht die Voraussetzungen für solche Algorithmen erfüllen, dann klappt das nicht. Sind die Voraussetzungen aber erfüllt, dann sind die Algorithmen die auf Kollisionstests basieren ziemlich sicher langsamer.
btw.: wenn ich gerade selber auf dem Schlauch stehe würde ich den hier:
eher vermeiden.
-
Andrey schrieb:
rapso schrieb:
mach boundingboxen um die objekte und mach dann simple box-box tests.
jou. wenn die objekte aber sehr viel größer sind, als einzelne kästchen, solltest du das zB mit einem quad-tree rekursiv weiterunterteilen,
dafuer muestest du die boxen des quadtrees gegen die objekte testen, ich glaube gerade das war das anfangsproblem, wie primitiv vs quad testen... oder ich hab das problem falsch verstanden (kann ja auch selten mal passieren).
-
Jester schrieb:
Zu den Rasterizing-Algorithmen kann Dir rapso bestimmt einiges sagen.
ich kann sagen dass es nicht trivial ist es wirklich 100%ig sauber und schnell hinzubekommen.
Jester schrieb:
Was meinst Du wie Grafikkarten zeichnen? Kollisionstests von Pixelzellen mit den Objekten?
ehrlichgesagt machen das graphikkarten so heutzutage, seit ca geforce zeiten. natuerlich wird der bereich moeglichst eingegrenzt der zu pruefen ist, aber dann...
ich ging von kleinen primitiven aus, deswegen boundingboxes, wenn sie jedoch groeser sind wuerdich
fuer lines kannst du nach nem schnellern line-box intersectiontest suchen, da gibt es was gutes bei google.
bei tris kannst du von der mitte der mitte (oder den eckpunkten) der boxen aus versuchen bis ausserhalb der boundingbox der polygones eine linie gegen die raender testen. gerade anzahl von hits heisst die box ist ausserhalb, ungerade sagt sie waere innerhalb. duerfte sehr verlaesslich sein.
natuerlich musst du nicht komplett alle boxen testen, sndern nur die die innerhalb der boundingbox des poly sind...
-
achso, ja... an diese interpretation der fragestellung habe ich nicht gedacht
-
rapso schrieb:
Jester schrieb:
Was meinst Du wie Grafikkarten zeichnen? Kollisionstests von Pixelzellen mit den Objekten?
ehrlichgesagt machen das graphikkarten so heutzutage, seit ca geforce zeiten. natuerlich wird der bereich moeglichst eingegrenzt der zu pruefen ist, aber dann...
Echt? Nix mit schnellem Bresenham für Linien? Und für Dreiecke dann Bresenham und horizontale Verbindungslinien? Und komplexere Objekte triangulieren? Hast Du irgendwo was zu Lesen darüber wie man sowas heute macht?
Möglicherweise funktionieren diese alten Verfahren aber trotzdem noch. Dann sieht das eigentlich nach ner sehr effizienten Lösung aus.
-
Jester schrieb:
Echt? Nix mit schnellem Bresenham für Linien?
es werden locker 512pixel gleichzeitig abgearbeitet, da ist bresenham nicht so super. zudem ist subpixelgenauigkeit vorgeschrieben, das waere bei linearem interpolieren nicht so trvial zu loesen.
du brauchst zudem nicht clippen, keine teure logic die eventuel in spezialfaellen fehler macht etc.
nur ebenengleichungen, test von point in poly, was in 2d dann auch ein sehr einfacher collisiontest ist (man projeziert ja alles auf den screen).Und für Dreiecke dann Bresenham und horizontale Verbindungslinien?
niemand will horizontale linien, sondern lokale verflechtungen die sehr viele cachehits liefern.
Und komplexere Objekte triangulieren?
graphikkarten koennen eigentlich nur dreiecke.
Hast Du irgendwo was zu Lesen darüber wie man sowas heute macht?
sowas bekommt man wohl so ziemlich nicht oeffentlich, du muesstest in patenten schauen, da sind die rasterizierungsmuster oft angegeben.
-
rapso schrieb:
Jester schrieb:
Echt? Nix mit schnellem Bresenham für Linien?
es werden locker 512pixel gleichzeitig abgearbeitet, da ist bresenham nicht so super. zudem ist subpixelgenauigkeit vorgeschrieben, das waere bei linearem interpolieren nicht so trvial zu loesen.
du brauchst zudem nicht clippen, keine teure logic die eventuel in spezialfaellen fehler macht etc.
nur ebenengleichungen, test von point in poly, was in 2d dann auch ein sehr einfacher collisiontest ist (man projeziert ja alles auf den screen).Okay, die Gründe sehe ich ein. Aber für diesen konkreten Anwendungsfall sehen mir die alten Verfahren trotzdem nach ner ziemlich guten Lösung aus.
-
ich kenne keinen normalen rasterizer den concav polygone zeichnen kann. ist sicherich ne herausforderung
-
rapso schrieb:
ich kenne keinen normalen rasterizer den concav polygone zeichnen kann. ist sicherich ne herausforderung
Jo klar, die müßte man halt triangulieren. Das stellt ja aber weniger ein Problem dar.
-
Danke für eure zahlreichen Tips! Werde mir das, sobald ich wieder dazu komme, überlegen. Ziel war es ja, aufwendige Berechnungen wie Geradengleichungen, Schnittpunkte (über Matrizen) zu ersparen.
@Jester: Ja, es handelt sich um ein regelmässiges, rechteckiges Gitter.
Bei den konkaven Polygonen, muss ich wohl noch einiges mehr machen.