Fragen zu NURBS und zum Reverse Engineering Modul

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

WICHTIG: Bitte zuerst lesen, bevor Sie posten
User avatar
shoogen
Veteran
Posts: 2823
Joined: Thu Dec 01, 2011 5:24 pm

Re: Fragen zu NURBS und zum Reverse Engineering Modul

Post by shoogen »

ickby wrote:und meiner Ansicht nach ist da der least-squares ansatz der beste. Aber kann auch sein das ich deinen Ansatz falsch verstehe.
Ich stimme dir vollkommen zu, und danke dir auch für den Link. Meine Frage zielte aber darauf ab dem Benutzer das Auswählen der Punkte zu erleichtern.
wmayer
Founder
Posts: 20241
Joined: Thu Feb 19, 2009 10:32 am
Contact:

Re: Fragen zu NURBS und zum Reverse Engineering Modul

Post by wmayer »

Aus graphentheoretischer Sicht ist das nicht allzu kompliziert. In FreeCAD ist die Mesh-Datenstruktur so aufgebaut, dass ein Dreick (Facet) seine drei Eckpunkte und seine drei Nachbar-Dreiecke kennt. Dabei speichert es lediglich Indexe (unsigned long) ab, die auf das konkrete Facet oder Punkt in dem Facet-Array bzw. Punkte-Array verweist. Eine eigene Datenstruktur für Kanten gibt es nicht, da diese sich direkt aus den Facets ergibt und so nur unnötig Speicherplatz verbrauchen würde.

Nun hat man alle Zutaten beisammen, um von einem gegeben Punkt die Kontur des Kreises zu finden. Natürlich geht das nur dort, wo der Kreis durch Randpunkte beschrieben ist.
Hier die Schritten im Groben:
1. Nutzer klickt auf Punkt bzw. Randdreieck. Somit erhält man direkt via OpenInventor den Index für Dreieck bzw. Punkt
2a. Bei Dreieck kann man sofort prüfen, ob es ein Randdreieck ist. Falls nicht -> Abbruch
2b. Bei Punkt muss man einmal über das Facet-Array iterieren, um an das Dreieck zu kommen. Laufzeit ist dabei linear und braucht wohl nicht optimiert zu werden.
3. Nun geht man durch alle Dreiecke durch und sammelt alle Randkanten. Dabei hat man den Index des Anfangs- und Endpunkts.
4. Nun sortiert man die unsortierten Kanten so um, dass der Endpunkt einer Kante mit dem Anfangspunkt einer anderen Kante übereinstimmt. Am Ende hat man eine List von Liste von Kanten. Eine Liste von Kanten beschreibt dabei immer eine geschlossene Kurve.
Anm: Es gibt schon fertige Algorithmen im Mesh-Modul dazu. Man kann diesen Schritt schon vorab durchführen und in einer Datenstruktur speichern.
5. Man sucht sich nun die Randkurve heraus, die zu dem Dreieck bzw. Punkt gehört.
6. Man holt sich die 3d-Punkte der Randkurve
7. Jetzt benötigt man einen guten Approximationsalgorithmus für Kreise. Der Algorithmus sollte neben Radius, Mittelpunkt und Normalenrichtung der Ebene Eckwerte wie quadratisches Mittel und maximale Abweichung zurückliefern.
User avatar
shoogen
Veteran
Posts: 2823
Joined: Thu Dec 01, 2011 5:24 pm

Re: Fragen zu NURBS und zum Reverse Engineering Modul

Post by shoogen »

wmayer wrote:Natürlich geht das nur dort, wo der Kreis durch Randpunkte beschrieben ist.
In meiner (naiven) Vorstellung ist "Rand" eine Kante die Bestandteil eines Dreiecks ist, zu der es aber keine Gegenkante mit den gleichen Punkten mit entgengesetzer Orientierung gibt. (Gäbe es eine Kante (mit der gleichen Orientierung) mehrfach wäre das Mesh meinem Verständnis nach non-mainfold)
Ein Mesh das einen Rand nach der obigen Definition hätte wäre aber nicht watertight. Das würde die Funktion aber sehr einschränken.

Werner, hab ich das mit dem Rand richtig verstanden?

Eine Andere Defintion von Rand wäre: "mindestens ein an die Kante angrenzendes Facet hat einen Punkt ausserhalb der Ebene"
Allerdings würde man Schritt 4 nicht mehr Vorausberechnen können.
wmayer
Founder
Posts: 20241
Joined: Thu Feb 19, 2009 10:32 am
Contact:

Re: Fragen zu NURBS und zum Reverse Engineering Modul

Post by wmayer »

Werner, hab ich das mit dem Rand richtig verstanden?
Ja!
Ein Mesh das einen Rand nach der obigen Definition hätte wäre aber nicht watertight. Das würde die Funktion aber sehr einschränken.
Das ist ein guter Punkt. Bei einem Solid würde man mit obigem Verfahren überhaupt keine Randkanten finden, sonst wäre es auch kein Solid. In so einem Fall müsste man ganz anders vorgehen:
1. Man hat als Eingabe ein Dreieck
2. Bei einem "Loch" gibt es dann mindestens eine Kante dessen Nachbardreieck eine vom Startdreieck verschiedene Normale hat
3. Ich starte einen Region-Growing-Algorithmus (gibt es schon) mit einer speziellen Visitor-Klasse
4. Die Visitor-Klasse bekommt immer ein Nachbardreieck zum gerade besuchten Dreieck. Es überprüft gewisse Kriterien und liefert zurück, ob es das Dreieck akzeptiert oder nicht.
Hier: das neue Dreieck hat auch eine Kante, dessen Nachbardreieck eine andere Normale hat
5. So hangelt man sich im Prinzip dem "Loch" entlang und findet die Punkte.
Post Reply