Rule-Based Mesh Growing and Generalized Subdivision Meshes
No Thumbnail Available
Date
Jan 2002
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Maierhofer
Text.PhDThesis
Abstract
In dieser Arbeit pr¨asentieren wir eine verallgemeinerte Methode zur prozeduralen Erzeugung und Manipulation von Meshes, die im wesentlichen auf zwei verschiedenen Mechanismen beruht: generalized subdivision meshes und rule-based mesh growing. Herk¨ommliche Subdivision-Algorithmen beruhen darauf, dass eine genau definierte, spezifische Subdivision-Vorschrift in wiederholter Folge auf ein Mesh angewendet wird um so eine Reihe von immer weiter verfeinerten Meshes zu generieren. Die Vorschrift ist dabei so gew¨ahlt, dass die Ecken und Kanten des Basis-Meshs gegl¨attet werden und die Reihe zu einer Grenzfl¨ache konvergiert welche festgelegten Stetigkeitsanspr¨uchen gen¨ugt. Im Gegensatz dazu erlaubt ein verallgemeinerter Ansatz die Anwendung verschiedener Vorschriften bei jedem Subdivision-Schritt. Konvergenz wird im wesentlichen dadurch erreicht, dass die absolute Gr¨oße der durchgef¨uhrten geometrischen Ver¨anderungen von Schritt zu Schritt geringer wird. Bei genauerer Betrachtung stellt man jedoch fest, dass es in vielen F¨allen von Vorteil w¨are die st¨arkere Ausdruckskraft von Subdivision-Vorschriften ohne die oben genannte Einschr¨ankung zu nutzen. Wir schlagen deshalb vor, die Erzeugung eines Submeshs M(n+1) aus einem spezifischen Mesh M(n) in zwei eigenst¨andige Operationen zu zerlegen. Die erste Operation, genannt mesh refinement, bezeichnet dabei die Verfeinerung des Meshs durch das Einf¨ugen neuer Eckpunkte und die Festlegung der dadurch neu entstehenden Nachbarschaftsbeziehungen zwischen Eckpunkten, Kanten und Fl¨achen, ohne dabei jedoch bereits die konkreten Positionen der Eckpunkte festzulegen. Erst die zweite Operation, genannt vertex placement, berechnet konkrete Positionen f¨ur die Eckpunkte. Um dem Anwender eine gr¨oßtm¨ogliche Flexibilit¨at bei der Spezifikation von Subdivision Surfaces zu bieten, schaffen wir die M¨oglichkeit verschiedene refinement und vertex placement Operatoren in sogenannten mesh operator sequences, das sind beliebige Sequenzen von Operatoren, zu kombinieren, und diese dann auf konkrete Meshes anzuwenden. Rule-based mesh growing ist eine Erweiterung von parametrisierten Lindenmayer Systemen (pL-Systemen), die jedoch nicht auf der Basis einzelner Symbole, sondern auf der Basis von Symbolen die in einer Nachbarschaftsbeziehung stehen, operieren. Einzelne Symbole repr¨asentieren dabei Fl¨achen eines Meshs. Dieser Mechanismus erlaubt es, in kontrollierter Art und Weise, komplexe Details in Meshes einzuf¨ugen und zwar genau dort wo dies gew¨unscht wird. Um die Systematik von pL-Systemen auch im Kontext eines Mesh-basierten Rendering-Systems nutzen zu k¨onnen, f¨uhren wir mesh-based pL-systems (Mesh-basierte pL-Systeme) ein. Hierbei wird jedes parametrisierte Symbol (linke Seite einer Ersetzungsregel) mit einer oder mehreren Fl¨achen in einem oder mehreren Meshes in Beziehung gesetzt beziehungsweise verkn¨upft. Die rechte Seite einer Ersetzungsregel ist nun nicht mehr eine lineare Sequenz von Symbolen, sondern ein Mesh dessen Fl¨achen wiederum Symbole zugeordnet sind. Die Topologie eines Objekts, welches mit Hilfe eines solchen Mesh-basierten pL-Systems erzeugt wird, ist automatisch durch die Nachbarschaftsbeziehungen des Meshs festgelegt, und es ist deshalb nicht mehr, so wie dies bei herk¨ommlichen pL-Systemen der Fall ist, n¨otig, spezielle Gruppierungssymbole zu verwenden. Werden beide Mechanismen kombiniert, so erh¨alt man ein Werkzeug mit dem man eine große Anzahl von komplexen Formen und Objekten modellieren kann und mit dessen Hilfe diese auch ¨außerst kompakt repr¨asentiert werden k¨onnen. Wir zeigen dies anhand einer Integration der beschriebenen Mechanismen in ein bestehendes Rendering-System. Die Mesh-basierten pL-Systeme werden dabei mit Hilfe von directed cyclic graphs (gerichteten zyklischen Graphen) abgebildet, welche die oben genannte kompakte Repr¨asentation der Modelle erm¨oglichen und durch den, von Fraktalen und L-Systemen her bekannten, Effekt der database amplification in der Lage sind aus einer solch kompakten Datenbasis komplexe Strukturen zu erzeugen. Auf der Basis dieser Implementierung der grundlegenden Konzepte unseres Ansatzes erstellen wir schliesslich einen Prototypen eines interaktiven Pflanzeneditors mit der M¨oglichkeit diverse Parameter semiautomatisch aus Photographien von Pflanzen zu extrahieren um so auch die praktische Anwendbarkeit unseres Ansatzes zu demonstrieren. - As a general approach to procedural mesh definition we propose two mechanisms for mesh modification: generalized subdivision meshes and rule-based mesh growing. In standard subdivision, a specific subdivision rule is applied to a mesh to get a succession of meshes converging to a limit surface. A generalized approach allows different subdivision rules at each level of the subdivision process. By limiting the variations introduced at each level, convergence can be ensured however in a number of cases it may be of advantage to exploit the expressivity of different subdivision steps at each level, without imposing any limits. We propose to split the process of generating a submesh M(n+1) from a specific mesh M(n) into two distinct operations. The first operation, which we call mesh refinement, is the logical introduction of all the new vertices in the submesh. This operation yields all the connectivity information for the vertices of the submesh without specifiying the positions of these newly introduced vertices. The second operation, which we call vertex placement, is the calculation of the actual vertex positions. In order to obtain maximum flexibility in generating subdivision surfaces, we make it possible for the user to independently specify both of these operations, by offering a number of refinement and vertex placement operators, which may be arbitrarely combined in user-specified mesh operator sequences, which in turn are applied to particular meshes. Rule-based mesh growing is an extension of parametric Lindenmayer systems (pL-systems) to not only work on symbols, but connected symbols, representing faces in a mesh. This mechanism allows the controlled introduction of more complex geometry in places where it is needed to model fine detail. In order to use pL-systems in the context of a mesh-based modeling system, we introduce mesh-based pL-systems, by associating each parameterized symbol of the system with one or more faces in one or more meshes. Thus the right-hand side of each production rule is not a linear sequence of symbols, but a template mesh with each face again representing a symbol. Thereby the topological structure of an object generated with such a meshbased pL-system is automatically encoded in the connectivity information of the mesh, and we do not need to introduce grouping symbols in order to encode the hierarchical structure, like it is necessary in standard pL-systems. Using both these mechanisms in combination, a great variety of complex objects can be easily modeled and compactly represented. We demonstrate this by including the proposed framework in a general-purpose rendering system. Directed cyclic graphs are used to represent mesh-based pL-systems, and from this compact representation complex geometry is generated due to the effect of database amplification, known from fractals and L-systems. Finally, this implementation of the main concepts of our approach is used as a basis for an interactive plant editor, and an appositional user interface for semi-automatic parameter extraction from photographs of plants, in order to demonstrate the applicability of our approach to real-world applications.
Description