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.
Also ist der Aufwand einfach zu groß. Ist es nicht einfacher, einfach auf fertige FUnktionen wie z.B. des Geometriekernels Opencascade zuzugreifen?
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:
1 | struct Point |
2 | {
|
3 | double x; |
4 | doubly y; |
5 | };
|
6 | |
7 | |
8 | struct Face |
9 | {
|
10 | int nrPoints; |
11 | struct Point* Points; |
12 | };
|
13 | |
14 | // A: 0/0 0/6 9/6 9/4 14/4 14/0 0/0
|
15 | |
16 | struct Point Points[] = { { 0.0, 0.0 }, |
17 | { 0.0, 6.0 }, |
18 | { 9.0, 6.0 }, |
19 | { 9.0, 4.0 }, |
20 | { 14.0, 4.0 }, |
21 | { 14.0, 0.0 } }; |
22 | |
23 | struct Face FaceA = { sizeof(Points)/sizeof(Points[0]), Points ); |
oder
1 | struct Point |
2 | {
|
3 | double x; |
4 | doubly y; |
5 | };
|
6 | |
7 | struct Edge |
8 | {
|
9 | struct Point* startPoint; |
10 | struct Point* endPoint; |
11 | };
|
12 | |
13 | struct Face |
14 | {
|
15 | int nrEdges; |
16 | struct Edge* Edges; |
17 | };
|
18 | |
19 | // A: 0/0 0/6 9/6 9/4 14/4 14/0 0/0
|
20 | |
21 | struct Point Points[] = { { 0.0, 0.0 }, |
22 | { 0.0, 6.0 }, |
23 | { 9.0, 6.0 }, |
24 | { 9.0, 4.0 }, |
25 | { 14.0, 4.0 }, |
26 | { 14.0, 0.0 } }; |
27 | |
28 | struct Edge Edges[] = { { &Points[0], &Points[1] }, |
29 | { &Points[1], &Points[2] }, |
30 | { &Points[2], &Points[3] }, |
31 | { &Points[3], &Points[4] }, |
32 | { &Points[4], &Points[5] }, |
33 | { &Points[5], &Points[0] } }; |
34 | |
35 | struct Face FaceA = { sizeof(Edges)/sizeof(Edges[0]), Edges }; |
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.
Nein, 2D ist 2D und 3D ist 3D. Das sind einfach 2 verschiedene paar Stiefel.
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 ...
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.