Rule-Based Mesh Growing and Generalized Subdivision Meshes (2002)

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.