Hallo Zusammen,
kann mir jemand sagen, in welchem Bereich ich zum Thema Flächenbereich
fündig werden könnte. ich wuerde gerne erfahren, wie ein
Flächenvergleich genau funktioniert. Bei CSG Modellen kann ich mir von
zwei Objekten die Schnittmenge angeben lassen. Bei B-Reps ist das aber
nicht so einfach, da boolesche Operationen nur mit speziellen
Algorithmen funktionieren. Gibt es da andere Möglichkeiten? Man könnte
über Bounding Box erst einmal feststellen, ob sich Objekte
überschneiden. Aber dann kommt das Problem, dass es bei konkaven nicht
so einfach ist, zumindest habe ich das so recherchiert.
Man könnte aber auch schauen, welche punkte von Körper B in A vorkommen
bzw. die Schnittpunkte von A und B auslesen und falls ungerade, befindet
sich der Punkt von Körper B in A. Ansonsten hab ich keine Ideen.
Was genau verstehst du unter einem 'Flächenvergleich'?
> Man könnte über Bounding Box erst einmal feststellen, ob sich Objekte> überschneiden.
Bounding Box Vortests sind immer gut.
Aber das sind nur Vortests. Wenn es dir darum geht, ob 2 Objekte
interagieren, dann kann dir der Boxtest nur sagen:
"Interagieren mit Sicherheit nicht"
Aber die Umkehrung gilt nicht.
Bounding Box Vortests sind 'quick&dirty" Tests, mit denen man
feststellt, ob es überhaupt etwas zu tun gibt.
> Man könnte aber auch schauen, welche punkte von Körper B in A vorkommen
Was jetzt?
Reden wir von Körpern (3D) oder von Flächen (2D), oder von Flächen im
3D?
> Man könnte aber auch schauen, welche punkte von Körper B in A> vorkommen bzw. die Schnittpunkte von A und B auslesen und falls> ungerade, befindet sich der Punkt von Körper B in A. Ansonsten> hab ich keine Ideen.
Ich bin nicht sicher, wonach du eigentlich fragst. Aber ein
pathologischer Fall ist bei fast allen geometrischen Problemstellungen
der hier
+---------+
| |
| |
+--------------------------------+
| | | |
+--------------------------------+
| |
+---------+
Kein einziger Eckpunkt der einen Fläche befindet sich innerhalb der
anderen und vice versa. Und trotzdem 'interagieren' die beiden.
Ich betrachte es in 2d und 3D. Eventuell koennte man sogar von 3D in 2D
umwandeln bzw die z Achse zu 0 setzen und ueber nummerische Verfahren
loesen. Mir geht es darum eine Methode oder Konzept zu entwickeln, wie
es in CAD Programmen der Fall ist. Also zwei Koerper mitrinander
vergleichen und gemeinsame flaechen oder Volumen ausgeben bzw anzeigen
lassen. Ueber CSG Modellierung kein Problem, da boolesche Operationen
funktionieren. Aber beim BREP Verfahren ist das anders. Mir faellt da
auch nur nummerische Integration ein. Es gibt eine Bibliothek namens
OpenCascade, aber ich moechte ersteinmal theoretisch weiter kommen.
mike schrieb:> Ich betrachte es in 2d und 3D. Eventuell koennte man sogar von 3D in 2D> umwandeln
Ja geht in gewissen Fällen.
> bzw die z Achse zu 0 setzen
so ähnlich. Man projeziert in die Standardebene, in der der Normalvektor
die größte Komponente senkrecht drauf hat. Aber das ist jetzt ein
Mathe-Detail.
> es in CAD Programmen der Fall ist. Also zwei Koerper mitrinander> vergleichen und gemeinsame flaechen oder Volumen ausgeben bzw anzeigen> lassen.
Du musst grundsätzlich zwischen 2D und 3D unterscheiden.
Boolsche Operationen sind im 2D schon happig, im 3D wird aber alles noch
eine 10-er Potenz schwieriger.
Das Problem bei all diesen Dingen sind nicht die klaren Verschneidungen.
Die Probleme tauchen auf, wenn Flächen an Punkten und/oder Kanten
zusammenstossen, wenn Flächen zueinander koplanar sind, schleifende
Schnitte, begrenzte Rechengenaugikeit etc. Das sind die pathologischen
Problemkreise die einem bei einem Solid Modeller den Schlaf rauben.
> auch nur nummerische Integration ein. Es gibt eine Bibliothek namens> OpenCascade, aber ich moechte ersteinmal theoretisch weiter kommen.
Für 2D kannst dir zb mal Polybool ansehen.
Für 3D gibt es auch ein paar Projekte, mal nach "robust solid modelling
download" googeln. Da finden sich schon ein paar.
PS: Als CSG "Constructive Solid Geometry" bezeichnet man die Technik,
wie man aus einfachen Grundkörpern komplexere Körer durch boolsche
Operationen zusammensetzt. Ob diese einfachen Körper durch BREP oder zb
durch NURBS dargestellt werden, ist damit nicht gesagt. Bei CSG geht es
um die Möglichkeiten, die man durch kombinieren von Körpern und
Operationen in einer Baumhierarchie hat. Unabhängig davon, wie das dann
realisiert wird.
> aber ich moechte ersteinmal theoretisch weiter kommen.
2 Worte
Vektor Algebra, Vektor Algebra, Vektor Algebra
Danke. Werde mich weiter durchschlagen, um es besser zu verstehen. Ich
abe auch eine Arbeit gefunden, in der auf das Thema eingegangen wird. Es
ist nicht so einfach. Ich hab eine Bibliothek zur Konvertierung von CAD
Daten und muss anhand dieser untersuchen, ob ich einen eigenen
Algorithmus implementieren kann oder besser auf fertige geometriekernel
zugreife, aber ersteinmal muss ich mich durch den theoriekram quaelen
> ob ich einen eigenen Algorithmus
Algorithmus #wofür#
Es gibt unzählige Algorithmen die im 3D Modelling interessant sind. Das
reicht von boolschen Operationen, über Triangulierungen über
Geometrie-Simplifizierung, über Oberflächen und Volumsberechnung etc.
etc.
Wenn du boolsche Operationen robust(!) implementieren willst, dann
rechne zeitmässig mit Monaten (mehr als 10) und nicht mit Wochen.
Erst mal waere interessant zu wissen, ob die Flaeche als Satz von
Gleichungen gegeben ist, oder als Pixelhaufen.
Im Wesentlichen muss man jeweils die Flaechen auf Eins setzen, die
Umgebung auf Null, dann die beiden flaechen miteinander Multiplizieren.
Dann beleibt eine Flaeche uebrig, die zu beiden gehoert, da wo das
Resultat gleich Eins ist.
Deshalb. Es gibt die Bibliothek bzw Geometriekernel namens OpenCascade.
Dieser verwendet B-Rep Modelle, auf denen auch boolesche Operationen
angewendet werden können. Das heißt, ich müsste nur verstehen, die die
Daten meines Konverter die zu konvertierenden CAD-Daten ausliest und
könnte dann irgendwie auf die Funktionen und Algorithmen von OpenCascade
zugreifen. Wie, ist mir jedoch noch schleierhaft.
Kurze Frage: Auch wenn ich keinen eigenen Algorithmus entwickweln kann,
so muss ich doch zumindest verstehen bzw. analysieren, wie ein solcher
Vergleich überhaupt zustande kommt.
Weshalb ist die Implementierung eines solchen Algoprithmus eigentlich so
schwer? Die B-Rep Modelle enthalten doch alle Informationen bzw.
Koordinaten. Im simpelsten Fall koennte ich doch einfach den einen Punkt
bzw. die Strecke vom Koordinatenursprung zu einem Punkt von der anderen
abziehen und würde die differenz erhalten, also den gesuchten Bereich.
Wieso sind eigentlich Herzklappentransplantationen so schwer?
Man muss doch nur mit einem Messer aufschneiden, die Rippen brechen, das
Herz rausnehmen, neue Klappen einsetzen, alles wieder reinstopfen und
zunähen.
Wenn ich mir alleine deine Nomenklatur (deine Bezeichnungen) ansehe ...
du hast noch einen weiten Weg vor dir.
Vielleicht drück ich mich auch nur falsch aus. Eines steht fest, ob
B-Rep Flächenmodell oder Volumenmodell spielt noch keine Rolle, da der
einzige Unterschied ja darin besteht, dass beim Volumenmodell die
Flächenanordnung noch eine wesentliche Rolle spielt. Demnach kann ich
theoretisch auch das Flächenmodell als aller erstes heranziehen.
Ja dann mach mal
du hast 2 Flächen A (#) und B (+)
0 +++++++++++++++
9 + +
8 + +
7 + ++++++++
6 ####+##### +
5 # + # +
4 # + ##+###
3 # + + #
2 # ++++++++ #
1 # #
0- ###############
|
012345678901234567890
Das sind die Koordinaten der Eckpunkte in einer Reihenfolge, so dass
beide Flächen im Uhrzeigersinn beschrieben sind und alle Kanten in der
Beschreibung aufscheinen (der erste Punkt kommt zum Ende nochmal)
(x/y ist jeweils ein Dupel mit den jeweiligen x und y Koordinaten, 5/8
ist also der Punkt an den Koordinaten: x sei 5 und y sei 8)
A: 0/0 0/6 9/6 9/4 14/4 14/0 0/0
B: 4/2 4/10 19/10 19/7 11/7 11/2 4/2
Frage: Wie sieht das Ergebnis der Operation
A - B
aus und welche Schritte musstest du machen, um es zu erhalten?
(Mathematisch natürlich. Einfach hinmalen kann jeder. Aber wie hast du
es gerechnet? Beachte: es gibt keine Sonderfälle, alle Schnittpunkte
sind wohl definiert und es sind nur senkrechte und waagrechte Kanten im
Spiel)
Leg los. Durch die vereinfachte Geometrie ist das nicht weiter schwer.
Ich hab dir keine Fallen eingebaut und du brauchst auch noch nicht die
allgemeinen Formeln um zb die Koordinaten von Schnittpunkten zu
berechnen.
Entwirf einen ersten Algorithmus, wie du das gesuchte Problem löst.
Im einfachsten Fall fährst du einfach in einer Schleife die Kontur ab
und wenn du an einen Schnittpunkt gelangst, entscheidest du, ob du
'links' oder 'rechts' abbiegen musst um die Kontur auf der jeweils
anderen Fläche weiter abzufahren. Das ganze solang bis du rundum bist.
(Im Grunde fährst du einfach mit dem Finger entlang und wenn du auf
einen Endpunkt/Schnittpunkt kommst, entscheidest du, wo rum du mit dem
Finger weiterfahren musst)
Das ist nicht das beste Verfahren und es ist auch nicht das einzige,
aber es ist zumindest mal ein Verfahren an dem du üben kannst.
Dein Endergebnis muss die Fläche C sein, die so aussieht
0
9
8
7
6 #####
5 # #
4 # # ####
3 # # # #
2 # ######## #
1 # #
0- ###############
|
012345678901234567890
C: 0/0 0/6 4/6 4/2 11/2 11/4 14/4 14/0 0/0
(Das letztere, die Zahlenwerte sind das Ergebnis. Eine Pixellösung wird
nicht akzeptiert. Denn dann bau ich dir ganz schnell nicht so schöne
ganze Zahlen ein und dann geht nichts mehr mit Pixeln)
Kann natürlich auch sein, dass wir aneinander vorbei reden und du unter
"Vergleichen" etwas ganz anderes verstehst. Denn die Operation
"Vergleichen" ist auf Flächen ja nicht sinnvoll definiert. Was soll das
sein "Ich vergleiche A mit B". Was soll das Ergebnis dieses Vergleichs
sein? Was ist die Aussage davon?
Ich würde für das Beispiel jetzt eine Funktion schreiben, die mir mit
zwei inneinander verschachtelten Schleifen das 10x10 Feld (Feld[x][y])
anzeigt. Dann würde ich daher gehen und eine Funktion namens void
BesetzeFeld nehmen und per do-while die einzelnen Koordinaten für Fläche
A abfragen. Dann das ganze für Fläche B. Dabei kann das "+" das "#"
überschreiben. Mit einer dritten Funktion könnte ich die einzelnen
Felder abfragen und prüfen, ob die Koordinaten von B innerhalb von A
liegen. Zumindest spontan. Ist aber eine interessante Übung für C++.
Werde ich auf alle Fälle mal ausprobieren.
Ich müsste dann nur noch entscheiden, ob man bei einem Schnittpunkt
links oder rechts herum gehe ...
Mike schrieb:> Ich würde für das Beispiel jetzt eine Funktion schreiben, die mir mit> zwei inneinander verschachtelten Schleifen das 10x10 Feld (Feld[x][y])> anzeigt. Dann würde ich daher gehen und eine Funktion namens void> BesetzeFeld nehmen und per do-while die einzelnen Koordinaten für Fläche> A abfragen. Dann das ganze für Fläche B. Dabei kann das "+" das "#"> überschreiben.
Ich sagte explizit: keine Pixel!
FLäche A sei
5.876/3.1489 2.340/-8.653 3.1872/17.6500 5.876/3.1489
Entweder du willst Geometrie machen oder willst das nicht.
Dann kannst du aber nicht schummeln! Wenn du CAD machen willst, musst du
schon geometrisch exakt rechnen. Dein Maschinenbauer braucht eine exakte
ANgabe des Flächeninhalts und der Kantenlänge. Schliesslich berechnet
sich danach der Preis, den er dem Kunden für das Laserschneiden eines
Blechs verrechnen muss. Und wenn das Edelstahl ist, dann zahlt man für
jeden einzelnen Quadratzentimeter Fläche und jeden Millimeter Zuschnitt.
Wenn du berechnen musst, wieviele Kubikmeter Aushub in der Baugrube
eines Hauses anfallen, kannst du nicht hinterher sagen: Ja wenn ich das
mit 100*100*100 Voxel rechne kommen ungefähr 58m^3 raus. Bei 50*50*50
sinds aber nur 52. Dein Bauträger will wissen, wieviele LKW er bestellen
muss, die den Aushub abholen.
"Was soll das
sein "Ich vergleiche A mit B""
Wenn ich zwei Flächen vergleichen mochte, also die Schnittmenge ausgeben
moechte. Das funktioniert in CAD unter "Geometrievergleich". Es wird ein
neues Teil mit dem Referenzteil verglichen und die Änderungen farblich
markiert.
Mike schrieb:> "Was soll das> sein "Ich vergleiche A mit B"">> Wenn ich zwei Flächen vergleichen mochte, also die Schnittmenge ausgeben> moechte.
Also Schnittmenge.
Damit sind wir bei boolschen Operationen.
Vergleich könnte ja auch sein:
haben sie den gleichen Flächeninhalt
die gleiche Form
gleiche Position, Lage
gleiche Farbe
gleiche minimale X-Position
gleichen Drehsinn
...
all das könnte man unter "2 Flächen vergleichen" verstehen. Daher musst
du das mal definieren, was du unter 'vergleichen' verstehst.
Aber jetzt ist es klar: Du willst die Schnittmenge.
Ich möchte im Prinzip die Fläche ausgeben, die beide Flächen gemeinsam
haben. Daher war meine Idee auch über die nummerische Integration. Denn
es müssen Schnittpunkte existieren.
Boolesche Operationen könnte man anwenden, dafür müsste ich aber auf
eine Geometriekernel wie OpenCascade zurückgreifen.
Genau, und am einfachsten über eine Geometriekernel. Natürlich ist auch
interessant zu erfahren, wie es ohne funktionieren würde. Schließlich
werden vom Konverter verschiedene Angaben über Position, Farbe und
Material des Elements ausgelesen und das Modell dann als B-Rep
gespeichert.
Mike schrieb:> Ich möchte im Prinzip die Fläche ausgeben, die beide Flächen gemeinsam> haben. Daher war meine Idee auch über die nummerische Integration. Denn> es müssen Schnittpunkte existieren.
Müssen sie?
++++++++++++++++++++++++++
+ +
+ ############## +
+ # # +
+ # # +
+ ############## +
+ +
++++++++++++++++++++++++++
Keine Schnittpunkte. Trotzdem ist die Schnittmenge nicht leer.
Stimmt. hmm, dann fällt die nummerische Integration flach ...
Aber über die Eckpunkte kann ich auch nicht gehen, da diese auch nicht
immer innerhalb der zweiten Fläche liegen. Daher müsste ich irgendwie
prüfen, ob die Punkte innerhalb oder außerhalb der Fläche liegen:
http://burghardt.org/diss/node128.html
Das unterste Bild zeigt die Idee. Darüber könnte man zumindest eine
Aussage darüber treffen, ob sich die Punkte des Polygons B innerhalb von
denen des Polygons A befinden.
Mike schrieb:> Natürlich ist auch interessant zu erfahren, wie es ohne> funktionieren würde.
Ein Verfahren geht zb so
Berechne alle Schnittpunkte zwischen den Konturen
und unterteile die Kanten an diesen Punkten
Klassifiziere jede Kante von A in Bezug auf B:
liegt die Kante
in B
auf der Kontur von B
ausserhalb von B
(durch die Unterteilung im ersten Schritt ist sichergestellt,
dass jede Kante eindeutig in eine der 3 Kategorien fällt.
Im weiteren ignoriere ich den Fall 'auf', weil er es ist, der
die Dinge kompliziert macht.
Die Klassifizierung kann man zb machen, in dem man einen Punkt
auf der Kante nimmt (zb den Punkt in der Mitte) und den testet
ob er in B enthalten ist oder nicht)
Klassifiziere jede Kante von B in Bezug auf A:
in A
auf A
ausserhalb A
dann wird je nach gewünschter Operation zusammengefasst.
Um A - B zu berechnen benötigt man alle Kanten ...
... von A, die ausserhalb B liegen
... von B, die innerhalb A liegen
Für A + B nimmt man alle Kanten
... von A, die ausserhalb B liegen
... von B, die ausserhalb A liegen
Um A * B zu bestimmen, nimmt man alle Kanten
... von A, die innerhalb B liegen
... von B, die innerhalb A liegen
Dann muss man 'nur noch' die so ermittelten Ergebniskanten in die
richtige Reihenfolge bringen und ist fertig.
Mike schrieb:> Das unterste Bild zeigt die Idee. Darüber könnte man zumindest eine> Aussage darüber treffen, ob sich die Punkte des Polygons B innerhalb von> denen des Polygons A befinden.
klassischer Punkt in Polygon Test.
Ist bei einer boolschen Operation ungefähr (ich würde mal sagen) 5% des
Gesamtverfahrens.
Es ist ein wichtiger Test, keine Frage, aber bis dein Verfahren fertig
ist wirst du nur noch darüber lächeln, dass dir etwas so banales wie ein
Punkt in Polygon Test jemals Kopfzerbrechen bereitet hat :-) Es ist
einfach nur ein Baustein des Verfahrens, mehr nicht. So wie das
Einschrauben einer Schraube auch nur ein Baustein beim Bau eines
Flugzeugs ist.
Mike schrieb:> Also ist der Aufwand einfach zu groß.
Vor allen Dingen hab ich bei der Beschreibung des Verfahrens da oben
alles weggelassen, was die Dinge kompliziert macht!
Ich hab die ganzen Fälle 'auf' ignoriert. Ich hab alles ignoriert, was
im Zusammenhang mit Löchern in den Flächen steht. Ich hab alle Fälle von
Kolinearität beim Bestimmen der Schnittpunkte und Aufteilen der Kanten
ignoriert. Ich hab schleifende Schnitte ignoriert. Ich hab ....
> Ist es nicht einfacher, einfach> auf fertige FUnktionen wie z.B. des Geometriekernels Opencascade> zuzugreifen?
Wenn du dieses Jahr noch fertig werden willst ... mit Sicherheit.
Wenn du nur wissen willst, #OB# 2 Flächen einen gemeinsamen Anteil
haben, dann ist das einfach. 2 Flächen haben genau dann einen
gemeinsamen Anteil, wenn
* es Schnittpunkte an den Konturen gibt (einer genügt)
* es mindestens 1 Eck-Punkt von A gibt, der in B liegt oder
es mindestens 1 Eck-Punkt von B gibt, der in A liegt
Darüber hinaus kann man noch die Aussage treffen, dass A komplett in B
liegt, wenn
* es keine Schnittpunkte gibt
* mindestens 1 Punkt von A in B liegt
(denn dann müssen alle Punkte von A in B sein, sonst gäbe es ja
Schnittpunkte)
Wenn du aber wissen willst, #WIE# dieser gemeinsame Anteil aussieht,
dann wirds aufwändig.
>> Wenn du dieses Jahr noch fertig werden willst ... mit Sicherheit.
Na ja, das ist aber immerhin auch ein Ergebnis. OpenCascade ist ein
mächtiges Werkzeug, wozu also das Rad neu erfinden. Das Problem, dass
sich dabei stellt ist, wie ich nun die ausgelesenen CAD-Daten richtig
interpretiere und mit OpenCasade verbinde. Zwar erledigt OpenCascade die
arbeit, aber die Funkionen, die ich nutzen möchte, muss ich ersteinmal
richtig verwenden.
Mike schrieb:> sich dabei stellt ist, wie ich nun die ausgelesenen CAD-Daten richtig> interpretiere und mit OpenCasade verbinde.
Tja.
Da musst du durch
Das Problem aufteilen.
* Erst mal einlesen (und irgendwo zur Kontrolle anzeigen)
* Dann OpenCascade studieren
* -> jetzt hast du das Wissen um die 'Übersetzung' von der einen
Form in die andere zu machen.
So wild ist das nicht. Durch die Vorgabe BREP ist ja schon ungefähr
abgesteckt, wie das aufgebaut ist (sowohl im einen wie auch im anderen
Fall)
es gibt Punkte
2 Punkte bilden eine Kante
mehrere Kanten bilden eine Fläche
(und Flächen bilden Körper)
Sonderfälle sind jetzt
* gibt es Kreise bzw. Kreisbögen
* gibt es Löcher in den Flächen
(Löcher wirst du auf jeden Fall können müssen, weil bei boolschen
Operation recht schnell welche entstehen können)
mit dynamischen Datenstrukturen musst du halt gut stehen. Aber je nach
Programmiersprache ist das ja kein Problem.
Vielen Dank. Ich werde die Ratschläge befolgen und alles noch einmal in
Ruhe lesen. Wenn ich ersteinmal verstanden habe, weshalb es so
kompliziert ist, dann komme ich dem Ziel hoffentlich bald näher. Ich
danke dir jedenfalls für die hilfreichen Informationen.
Kurze Frage noch. Um diese ganzen Übrprüfungen durchführen zu konnen
(aus meiner Sicht theoretisch betrachtet), würde ich die Eckpunkte
beispielsweise über die gespeicherten Koordinaten berechnen oder? Wenn
mir nämlich der Konverter die CAD-Daten ausliest und als B-Rep Modell
abspeichert, dann müssen für alle Punkte auch Koordinaten existieren.
Wenn ich jetzt zum Beispiel nach deinem Verfahren zur Überprüfung gehe,
koennte ich z.B. ganz einfach von B xmin - von A xmax nehmen und würde
die differenz erhalten. Nur so als Beispiel ...
In wie fern spielen eigentlich regularisierte Operatoren oder
Triangulation eine Rolle bei diesem Thema? Könnnte oder muss man die
Flächen triangulieren und dann über Finite Elemente Mehtode gehen?
Regularisierte Operatoren spielen doch auch eine Rolle. Wenn ein
Kantenteil von B teilweise auf eine Kante von A liegt, dann wird das als
Fläche mit dargestellt ... daher die regularisierten Operatoren.
Und worin würde sich dein beschriebenes Verfahren bezüglich eines
Volumenmodells unterscheiden (bis auf Flächenanordnung)? Es müsste für
die Schnittmenge ja ausreichen, wenn man das Flächenmodell heranzieht.
Wobei neue Schnittflächen entstehen koennte, also doch Volumenmodell?
Mike schrieb:> Kurze Frage noch. Um diese ganzen Übrprüfungen durchführen zu konnen> (aus meiner Sicht theoretisch betrachtet), würde ich die Eckpunkte> beispielsweise über die gespeicherten Koordinaten berechnen oder?
Die Eckpunkte SIND die gespeicherten Koordinaten
zb:
oder
( noch komplexere Datenstrutur einsetzen. Je nachdem was man alles
braucht. Gipfel ist wohl im 3D die 'Winged Edge Data Structure'. Aber
die wird openCascade wohl nur intern verwenden und dich nicht damit
belästigen)
Du musst dir dann eben eine Datenstruktur einfallen lassen, die deinen
Bedürfnissen zur Datenhaltung entspricht und die dynamisch allokieren
und befüllen, während du das File liest.
> Wenn ich jetzt zum Beispiel nach deinem Verfahren zur Überprüfung gehe,> koennte ich z.B. ganz einfach von B xmin - von A xmax nehmen und würde> die differenz erhalten. Nur so als Beispiel ...
Das gilt aber nur in diesem Beispiel.
Weil ich alles rechtwinkelig und streng horizontal/vertikal angeordnet
habe. Mal dir mal andere Beispiele auf und du wirst schnell merken: da
geht nix mehr so einfach.
> In wie fern spielen eigentlich regularisierte Operatoren oder> Triangulation eine Rolle bei diesem Thema?
Kann man auch machen.
> Könnnte oder muss man die> Flächen triangulieren und dann über Finite Elemente Mehtode gehen?
Ähm. Finite Elemente ist ein komplett anderes Thema.
> Und worin würde sich dein beschriebenes Verfahren bezüglich eines> Volumenmodells unterscheiden (bis auf Flächenanordnung)?
Was genau verstehst du unter 'Volumenmodell'
Für mich ist das Volumenmodell (BRep) von innen hohl. Es ist für mich
nichts anderes als eine Anordnung von Flächen, die in eine bestimmte
Richtung zueinander geordnet sind und zusammen das Volumen
representieren.
Du hast weiter oben geschrieben, dass wenn wir nur wissen wollen, ob
sich die koerper schneiden, man ueberprufen muss, ob die eine flaeche in
der anderen, ausserhalb oder sich ueberschneiden. Die Frage ist nur, wie
ich das ueberpruefen kann. Das geht doch nur, wenn ich Pixel fujer Pixel
ueberpruefe oder fertige Funktionen fuer geometrievergleich nehme.
>Das geht doch nur, wenn ich Pixel fujer Pixel ueberpruefe oder fertige Funktionen
fuer geometrievergleich nehme.
Nein. Vergiss die Pixel, oder finiten Elemente Kloetzchen. Mach es mit
einem Algorithmus. Es geht naemlich. Bleibe erst in der Flaeche. Fahre
den Rand ab wie beschrieben.
Du hättest aber erwaehnt, dass man auch einzelne Punkte einjer kante
untersuchen kann. Ist es nicht so, dass uns bei BRep Modellen nur die
Punkte bzw Knoten Koordinaten liefern bzw. Enthalten? Dachte ich
zumindest.
Kann man machen wenn man das Prinzip verstanden hat...
Ich denke das wird nichts draus. Denn in der Zwischenzeit haette man den
Algorithmus 5 mal implementieren und testen koennen...
mike schrieb:> Du hättest aber erwaehnt, dass man auch einzelne Punkte einjer kante> untersuchen kann. Ist es nicht so, dass uns bei BRep Modellen nur die> Punkte bzw Knoten Koordinaten liefern bzw. Enthalten? Dachte ich> zumindest.
wenn du 2 Kanten hast
+ x1/y1
+
+
a1/b1 + a2/b2
################
+
+
+ x2/y2
An welchen Punkten kann sich am Status der + Kante in Bezug auf die #
Fläche etwas ändern? Doch wohl ja nur am Schnittpunkt. Und denk dir, hat
man 2 Kanten
x1/y1 nach x2/y2
und
a1/b1 nach a2/b2
dann kann man ausrechnen(!) ob und wo sich die beiden schneiden.
Das beginnt im Matheunterricht der (ich glaube) 10. Klasse: lineare
Gleichungen.
Wenn du die Richtung CAD gehen willst, dann solltest du schleunigst
aufhören, deine Mathe-Abneigung breitzutreten. Das ist nämlich alles
Mathe - von vorne bis hinten. Mehr als einem manchmal lieb ist. Und so
richtig interessant wird es dann, wenn man nicht im 2D sondern im 3D
rechnen muss. Da ist es besser, wenn man mit Vektoralgebra und Matrizen
auf du_und_du steht. Normaldistanz eines Punktes zu einer Ebene, die
durch eine Ebenengleichung repräsentiert wird, dürfen dir dann keine
grauen Haare mehr bereiten sondern sind etwas, was dir noch nicht mal
ein müdes Lächeln entlockt (Skalarprodukt aus der homogenen
Punktkoordinate (w gleich 1) und der Flächengleichung ausgedrückt als
4-er Vektor).
Und auch wenn "drei von vier" das genauso schon gesagt hat wie ich:
Vergiss Pixel und Finite Elemente. Die haben nichts, aber auch gar
nichts mit CAD zu tun. Mal dir 2 Strecken auf ein Blatt Papier. Die
Endpunktskoordinaten der einen Strecke seien x1s/y1s bzw x1e/y1e; die
der anderen seien x2s/y2s bzw. x2e/y2e. Und jetzt brauchst du eine
Formel, die dir die Koordinaten des Schnittpunktes xs/ys liefert, bzw.
ein Kriterium welches dir sagt: schneiden sich nicht, weil sie parallel
sind.
x1s/y1s
+ # x2s/y2s
+ #
#+ xs/ys
# +
# +
# +
x2e/y2e + x1e/y1e
Das ist eine geometrische Standardaufgabe. Genauso wie der "Punkt in
Polygontest Test" eine geometrische Standardaufgabe ist.
Wenn man CAD programmieren will, kommt man um Mathe nicht herum. Das ist
das eine. Das andere ist die Beherrschung von dynamischen
Datenstrukturen.
Im Prinzip has du recht. Ich sollte vielleicht bei den Grundlagen
anfangen. Ich kenne ja zumindest mein Ziel. Lineare gleichungssystem
kennen ich natuerlich und den Schnittpunkt erhbalte ich durch
gleichsetzen beider Gleichungen. Dann nach x aufloesen und das Ergebnis
in eine der beiden Funktionen einsetzen. Ich muss natuerlich nur noch
bestikmmten, welche Daten aus der CAD Datei ausgelesen werden und welche
ich fuer das gleichungssystem verwende. Der Ansatz ueber die Strukturen
hat mich auf ein Buch ubeer spieleprogrammierung gebracht, das hier
herumfliegt. Dort wird es aehnlich beschrieben,.
Hehe, mit Computational Geometry kann man Testcase-Schreiber mal so
richtig fordern und die Programmierer mit Sonderfällen trietzen bis sie
kotzen :)
Geometrieaufgaben fand ich bei ICPC schon immer nicht so pralle, da man
im ersten Anlauf immer was übersieht :D
mike schrieb:> Im Prinzip has du recht. Ich sollte vielleicht bei den Grundlagen> anfangen. Ich kenne ja zumindest mein Ziel. Lineare gleichungssystem> kennen ich natuerlich und den Schnittpunkt erhbalte ich durch> gleichsetzen beider Gleichungen. Dann nach x aufloesen und das Ergebnis> in eine der beiden Funktionen einsetzen.
Divide and Conquer, Plane Sweep/Sweep Line etc. sollten je nach Problem
und Datenmenge ebenso bekannt sein.
Beitrag "Re: Algorithmus gesucht"http://dna.fernuni-hagen.de/articles1980all.html
Hallo nochmal,
also nochmal kurz zu den Aufgaben. Durch die verschiedenen
Klassifizierungen oben untersuche ich Fläche A und B darauf, ob Kanten
innerhalb, außerhalb oder direkt aufeinander liegen. Also im Endeffekt
müsste ich bei meinem B-Rep-Modell jedes einzelne Polygon daraufhin
testen.
Könnte ich nicht auch über die Normale der Polygonfläche gehen? Wenn der
Strahl kein Polygon von Polygon B schneidet, dann befindet sich das
Polygon außerhalb. Und wenn der Strahl das Polygon schneidet, kann ich
ja mittels Kreuzoprodukt die Richtung der Normalvektoren von den beiden
Polygonen untersuchen. Kreuzprodukt bzw. negative Kreuzprodukt sagt mir
ja dann, ob das eine ursprüngliche Polygon innerhalb oder außerhalb
liegt. So koennte man auch bei den benachbarten Polygonen vorgehen und
ersteinmal prüfen, ob diese den Rand überschreiten ... stimmt da so in
etwa?
Mike schrieb:> innerhalb, außerhalb oder direkt aufeinander liegen. Also im Endeffekt> müsste ich bei meinem B-Rep-Modell jedes einzelne Polygon daraufhin> testen.
Exakt. Und genau da kommen dann die Box-Vortests ins Spiel.
> Könnte ich nicht auch über die Normale der Polygonfläche gehen? Wenn der> Strahl kein Polygon von Polygon B schneidet,
Wo genau beginnt denn die Normale? Wo ist denn ihr Fusspunkt auf Polygon
A? An einem Eckpunkt, im Schwerpunkt, im Umkreismittelpunkt, ... Je
nachdem, kann der Strahl das andere Polygon verfehlen oder durchgehen.
Das Konzept eines Normalvektors hilft dir, wenn du entscheiden musst, ob
ein Punkt (im 3D) über oder unter einer Fläche ist. Das kommt zwar an
vielen Stellen vor aber wenn du Schnittpunkte brauchst, musst du auch
Schnittpunkte rechnen.
> ersteinmal prüfen, ob diese den Rand überschreiten ... stimmt da so in> etwa?
Nein. Nicht wenn ich so einigermassen verstanden hast, was du vorhast.
Zuallererst mal: Schreib immer dazu, ob du 2D oder 3D arbeitest. 3D ist
nicht einfach nur 1 Koordinatenachse mehr. Die Dinge verkomplizieren
sich im 3D enorm, weil einige wichtige Konzepte aus dem 2D nicht mehr
greifen.
Dann: Nirgends woanders als in Computational Geometry gilt so sehr die
Devise: Ein Bild sagt mehr als 1000 Worte. Mach dir Skizzen. Mal dir auf
was du vorhast. Und wenn du versuchst eine Idee zu skizzieren: poste die
Skizze.
Ok, vielen Dank. Das ist nun die Frage. Die CAD-Modell ist meist
dreidimensional. Auf der anderen Seite sollte man eine Analyse immer
erst in 2D betrachten :)
Letztenendes werde ich eine fertige Bibliothek nutzen. Eventuell hilft
der Blick in die Doku, um die dort vorhandenen Algorithmen zu verstehen.
Irgendwio habe ich gelesen, dass Java 3D ebenfalls eine Bibliothek mit
Geometriefunktionen bereitstellt. Aber ich denke, dass CGAl oder
OpenCascade die richtige Wahl sind.
Hallo,
Eine Frage haette ich doch noch. Muss ich mein brep Modell, dass n eine
prc Datei gespeichert ist in OpenCascade implementieren, um boolesche
Operatoren auf brep anzuwenden? Gibt es keine einzelnen Algorithmen. Z.b
den nach hubbert fuer triangulierte breps?
Hallo,
ich bin es nochmal. Könnte man eventuell von beiden Modellen die
Bounding Box bestimmen und Schritt für Schritt kleiner machen bzw.
zerlegen? Eventuell die Modelle vorher triangulieren? Das wäre eine
einfache Lösung, aber ich müsste dazu nicht unbedingt OpenCASCADE
verwenden ... ein einfacher Vergleich würde ausreichen ...
