Featurerequest Sketcher: partielle Bestimmtheit

In diesem Forum Fragen und Diskussionen in Deutsch
Forum rules
Foren-Regeln und hilfreiche Informationen

WICHTIG: Bitte zuerst lesen, bevor Sie posten
HartmutG
Posts: 190
Joined: Fri Oct 21, 2016 10:13 am

Featurerequest Sketcher: partielle Bestimmtheit

Postby HartmutG » Thu Dec 01, 2016 12:08 pm

Hallo,

mir fiel bei der Benutzung des Sketchers auf, wie er noch angenehmer (gerade für Anfänger) durch die Kennzeichnung von partieller Bestimmtheit werden könnte:
Untere Skizze zeigt drei eigenständige Linienzüge, zwei von ihnen sind vollständig bestimmt. Was spricht dagegen, das der Sketcher diese schon mal ins Fix-Und-Fertig-Lager packt und grün kennzeichnet?

Für den Benutzer hätte das den Vorteil der Übersichtlichkeit (wieviele Posts hier waren schon "meine Skizze ist unterbestimmt, was kann ich tun", sogar ein Script gibt's dann dafür, das offentsichtlich mehr kaputt macht, falls es denn funktioniert).
Diese neue partielle Bestimmtheit widerspricht sich auch nicht mit dem übrigen Bedienkonzept, IMO gliedert sich nahtlos ein.
Für den Sketcher bedeutet das ein kleineres Gleichungssystem (schneller (und ggf. genauer?)).

Da ich keine Ahnung von der internen Architektur des Sketchers habe bleibt die Frage, ob die Ermittlung von partieller Bestimmtheit sehr viel Rechenleistung zieht oder nicht.
Der Sketcher hat ja bereits im Hintergrund ein "Fix-Und-Fertig-Lager", nämlich wenn ich externe Geometrien reinhole, dann sind die ja ebenfalls bestimmt und müssen nicht neu berechnet werden, daher gehe ich davon aus, das auf eine gewisse Codebasis für derartiges zurückgegriffen werden könnte.

Meinungen?
Gruß, HG
Attachments
partielleBestimmtheit.PNG
partielleBestimmtheit.PNG (22.62 KiB) Viewed 856 times
HartmutG
Posts: 190
Joined: Fri Oct 21, 2016 10:13 am

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby HartmutG » Thu Dec 01, 2016 2:15 pm

upps, nun ist es mir sogar schon bei einem extremst übersichtlichen Beispiel passiert, selbstverständlich ist nur ein Linienzug bestimmt. Der einzelne 30mm Strich natürlich nicht.
tom
Posts: 65
Joined: Sun Mar 29, 2015 9:20 pm

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby tom » Thu Dec 01, 2016 7:02 pm

Hallo,

Ich finde die Grundidee nicht schlecht, auch wenn sie sich wahrscheinlich nicht ganz so einfach realisieren lässt. Soweit ich die Sketcher-Implemenation aus den Diskussionen hier im Forum verstanden habe, werden alle Constraints derzeit in ein großes Gleichungssystem gepackt, welches dann numerisch gelöst wird. Je größer dieses GS wird (sprich je mehr Constraints man hat), desto langsamer wird der Solver. Eventuell wird auch die Lösung instabiler. Wenn man nun irgendwie den Sketch mit seinen Constraints vorher in voneinander unabhängige Teile zerlegen könnte, dann hätte man mehrere kleinere Gleichungssysteme zu lösen, die natürlich auch zu Einzelergebnissen führen. Diese Teilergebnisse könnte man entsprechend farblich kennzeichnen, sprich die bereits gelösten Teil-Sketches grün einfärben. Die große Frage, auf die ich mangels entsprechender mathematischer Kenntnisse auch keine Antwort kenne, ist, wie man die voneinander unabhängigen Teil-Sketches findet.
M.E. wächst der Rechenaufwand zum Lösen nichtlinearer Gleichungssysteme exponentiell mit der Anzahl der Gleichungen. Das bedeutet, dass ein Aufteilen in kleinere Teilsysteme auf jeden Fall auch auch einen Geschwindigkeitsschub bringt. Inwieweit der allerdings dann wieder von "Teilungsalgorithmus" aufgefressen wird, kann man erst sagen, wenn man einen solchen kennt.
Natürlich kann und sollte man grosse Sketches bereits manuell in kleinere aufteilen, schon rein der Übersichtlichkeit wegen. Insgeheim hoffe ich jedoch, dass oben skizzierter Ansatz noch weiter greifen könnte - nämlich, um die Elemente zu markieren, die noch nicht voll bestimmt sind. Das wäre dann ein echte Killerfeature des Sketchers.

VG Thomas
polymer
Posts: 228
Joined: Fri Sep 12, 2014 8:49 am

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby polymer » Thu Dec 01, 2016 8:07 pm

Braucht man nicht wenn man einen Sketch einfach und übersichtlich hält, also, nur so nebenbei bemerkt.

7-7-7 lässt grüßen...
HartmutG
Posts: 190
Joined: Fri Oct 21, 2016 10:13 am

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby HartmutG » Thu Dec 01, 2016 8:11 pm

Hallo Tom,
also der Solver kann einiges ab selbst in "Dumm&Stark"-Konfiguration, siehe meine Demo "FreeCAD braucht keine 7-7-7Regel". Aber natürlich sollte man immer nach höherem streben ;)
Ich habe mich auch immer davon beirren lassen "Gleichungssystem wird gelöst", nene wird es nämlich nicht. Es ist ein Iterationsverfahren, KEIN echtes Lösungsverfahren. Das hat Vor- und Nachteile: Vorteil Du kannst selbst bestimmen, wann Dir nach Deiner Hoffnung Gut auch gut genug ist. Weiterer Vorteil die Rechenleistung wird geschont. Würde da wirklich etwas gelöst, hmmm, ist zwar geiler aber die Kiste würde richtig ächtzen. AFIAR bei Newton steigen die Anforderungen auch nicht exponentiell wie bei einer echten Lösung, aber "Analysis I" ist auch schon ziemlich lange her und da wir beide nicht wissen, was da wirklich gemacht wird, reine Spekulation.

Der Teilungsalgorithmus hingegen dürfte IMHO ziemlich linear agieren. Also dem wird es vermutlich egal sein, kommt natürlich alles auf die Programmierung drauf an.

Egal: Darum ging es mir auch garnicht, sondern darum, dass es einfach ein super-cooles Feature für eine angenehmere Bedienung wäre. IMHO ist der Sketcher ein echtes verdientes Aushängeschild von FreeCAD.

Genau "braucht kein Mensch" ist natürlich auch ein Argument an die Sache ranzugehen. Warum braucht man überhaupt den Sketcher? Wofür braucht man überhaupt FreeCAD? OpenSCAD rockz!!!1111

Gruß, HG
ickby
Posts: 2922
Joined: Wed Oct 05, 2011 7:36 am

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby ickby » Thu Dec 01, 2016 8:24 pm

Das Problem ist mathematisch hochkomplex. In kommerziellen Systemen wird zusätzlich zu den numerischen auf Graphen-basierte Algorithmen zurückgegriffen, es gibt aber keinen geschlossenen Algorithmus der garantiert alle Lösungen zu finden. Entsprechend sind implementierung extrem Aufwendig (abhandlung unendlich vieler Sonderfälle) und robuste Lösungen sind nicht garantiert. Es gibt einige wenige Bücher dazu, aber auch allerhand frei verfügbare Paper. Google liefert einiges zur Theorie. Nur halt keine Lösung des Problems.

Man kann es natürlich mit brute force machen. Aber dann muss man schon für 20 elemente 1e6 Jacobimatrizen aufstellen und ihren Rang bestimmen, was ewig dauert. Das will niemand :)

Für den 3D Assembly Solver habe ich angefangen eine Graph-Basierte Lösung zu schreiben, da 3D assembly wesentlich komplizierter zu lösen ist als 2d (da sind auch die numerischen Verfahren nicht mehr robust). Aber dem User anzeigen, was schon fest ist, werden wir trotzdem nicht. Wenn man das macht muss man sicherstellen das es alles anzeigt. Und das können wir nicht.
HartmutG
Posts: 190
Joined: Fri Oct 21, 2016 10:13 am

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby HartmutG » Fri Dec 02, 2016 9:50 am

Danke für den kleinen Einblick hinter die Kulissen, die Zusammenarbeit von Solver/Iterationsverfahren ist ja auch wirklich gelungen, eigentlich kein Grund daran rumzufummeln, es tut ja wie es soll. War ja nur 'ne Idee wie man diesen Newtonschen Brute Force etwas entlasten könnte.

Aber damit ich es wirklich verstehe, eine letzte kleine Frage: Das Faktum "Bestimmtheit" vs. unter-/überbestimmt. Wie wird das ermittelt? Wird das erst im Verlauf des bzw. durch das Iterationsverfahrens festgestellt, oder ist das ein ganz anderer Algorithmus der unabhängig vom Iterationsverfahren greifen kann?
Danke&Gruß, HG
ickby
Posts: 2922
Joined: Wed Oct 05, 2011 7:36 am

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby ickby » Fri Dec 02, 2016 10:24 am

HartmutG wrote: Aber damit ich es wirklich verstehe, eine letzte kleine Frage: Das Faktum "Bestimmtheit" vs. unter-/überbestimmt. Wie wird das ermittelt?
Danke&Gruß, HG
Man Bestimmt den Rang der Jacobimatrix des Gleichungssystems und vergleicht ihn mit der Anzahl an freien Parametern. bei Gleichheit ist das System vollständig bestimmt. Das passiert außerhalb des Iterationsverfahrens.
HartmutG
Posts: 190
Joined: Fri Oct 21, 2016 10:13 am

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby HartmutG » Fri Dec 02, 2016 10:30 am

ickby wrote:
HartmutG wrote: Aber damit ich es wirklich verstehe, eine letzte kleine Frage: Das Faktum "Bestimmtheit" vs. unter-/überbestimmt. Wie wird das ermittelt?
Danke&Gruß, HG
Man Bestimmt den Rang der Jacobimatrix des Gleichungssystems und vergleicht ihn mit der Anzahl an freien Parametern. bei Gleichheit ist das System vollständig bestimmt. Das passiert außerhalb des Iterationsverfahrens.
na, das ist doch super, dann ist doch alles vorhanden. Für jeden einzelnen freistehenden Linienzug einmal aufsetzen und schon hat man die Entscheidung ob schon grün oder noch schwarz, ob Fix-Und-Fertig-Lager oder weiterhin im "großen Teich". Oder was habe ich jetzt leider immernoch nicht verstanden?
tom
Posts: 65
Joined: Sun Mar 29, 2015 9:20 pm

Re: Featurerequest Sketcher: partielle Bestimmtheit

Postby tom » Sat Dec 03, 2016 11:50 am

ickby wrote:Das Problem ist mathematisch hochkomplex. In kommerziellen Systemen wird zusätzlich zu den numerischen auf Graphen-basierte Algorithmen zurückgegriffen, es gibt aber keinen geschlossenen Algorithmus der garantiert alle Lösungen zu finden.
Dass das hochkomplex ist, merke ich auch schon eine Weile. Ich verfolge ja auch mit Interesse die Entwicklung bezüglich robuster Referenzen und suche auch selbst nach brauchbaren Lösungen. Bin jedoch bisher kläglich daran gescheitert. Doch zurück zum Thema: An zusätzliche Graphen zur Lösung des Problems hatte ich auch gedacht. In meinem Kopf existiert derzeit folgender Algorithmus, von einander unabhängige Teile eines Sketches zu lösen:
  • Zunächst wird ein Graph mit den Elementen des Sketches als Knoten (Vertexes und Edges). Die Constraints des Sketches bilden die Kanten im Graphen, wobei sie jene Knoten verbinden, die direkt von den Constraints berührt werden. Die Art des Contraints ist für die Kante im Graphen ohne Belang.
  • Nun werden Spanning Trees im Graphen gesucht. Die Spanning Trees müssen nicht zwingenderweise minimal sein. Es reicht, sie überhaupt zu finden. Die Operation kostet O(n), wobei n die Anzahl der Knoten im Graphen ist. Die Spanning Trees umfassen jeweils die von uns gesuchten voneinander unabhängigen Teile des Sketches.
  • Pro Spanning Tree wird nun ein Gleichungssystem aufgestellt und wie bisher auch gelöst.
Könnte das funktionieren?
ickby wrote:Aber dem User anzeigen, was schon fest ist, werden wir trotzdem nicht. Wenn man das macht muss man sicherstellen das es alles anzeigt. Und das können wir nicht.
Den Satz habe ich nicht ganz verstanden.

VG Thomas