Optimistic version control has the potential to confer a multitude of benefits to the architecture community, including enhanced collaboration and parallel working, but its adoption is currently stymied by a lack of three-way merging algorithms that work with the binary file formats commonly used by architects. This thesis demonstrates diffing, patching, and three-way merging algorithms for one such file format, openNURBS, which was developed by Robert McNeel & Associates for its Rhinoceros 3D modeling software. Typically associated with the .3dm file extension, openNURBS excels at representing complex curves and surfaces using non-uniform rational basis splines (NURBS) but also supports meshes, subdivision surfaces, Bézier splines, and elementary geometries such as points, lines, and planes. McNeel has released openNURBS, as well as a software development kit (SDK) for reading and writing files in that format, as open source under an MIT-like license. This license allows anyone to integrate openNURBS into their own software, or to publish enhancements to openNURBS itself, increasing the likelihood that openNURBS will become a widely-accepted data exchange format in the future (Robert McNeel & Associates, n.d.).
The openNURBS SDK provides an object-oriented application programming interface (API) for examining and manipulating 3D models in the openNURBS format. Object-oriented programming (OOP) rose to prominence in the 1980s and 90s with the emergence of graphical user interfaces (GUIs) and languages such as C++ and Java and has remained the dominant programming paradigm ever since. OOP centers on the concept of the object, "an individual, identifiable item, either real or abstract, which contains data about itself and descriptions of its manipulations of the data" (Armstrong 2006). The data storage mechanisms of an object are variously referred to as its attributes, fields, or properties, and the procedures it can perform are known as its methods. Objects are typically derived from a class, which provides a template for the organization and behavior of a set of related objects (known as instances of the class) and typically represents some real-world concept or entity. Sets of classes are used in OOP to model (in the conceptual sense) the problem domain of a software system.
OpenNURBS presents a 3D model as an instance of the ONX_Model class, which provides access to the model's components, settings, and metadata as well as methods for reading and writing .3dm files. A component of a model is any of its constituent parts, such as a layer, line type, or geometric entity. All components are instances of the ON_ModelComponent class, and as such, share certain common attributes and behaviors. Each is identified by a UUID, which is unique across all possible openNURBS models, and an index, which defines its position in the .3dm file relative to other components of the same type. Each component also has a name attribute, by which it can be assigned a human-readable label, and a status to indicate whether it is locked or hidden.
In OOP, inheritance refers to the ability of one class to incorporate and extend the properties and behaviors of another. The relationship between a child class and its parent is analogous to the relationship between a square and a quadrilateral: The square inherits the characteristics of the quadrilateral (such as having four sides) and builds upon them by defining new characteristics (such as those four sides having equal length) of its own. OpenNURBS defines sixteen child classes of ON_ModelComponent that play specific roles within a model while inheriting the common characteristics described in the previous paragraph. They are:
ON_Bitmap
An embedded raster image.
ON_DimStyle
A collection of settings, including arrowheads and number formats, that can be applied to annotation objects such as dimension lines and text notes.
ON_Group
A collection of related geometric objects.
ON_HatchPattern
A pattern of lines used to fill a hatched region.
ON_HistoryRecord
A connection between a complex geometric object and the simpler ones used to create it that permits modifications to the simpler objects to be passed on to the more complex one.
ON_InstanceDefinition
A reusable collection of geometric objects. Unlike an ON_Group, multiple references to an instance definition can be placed in a model and will remain linked so that modifications to one are propagated to the others.
ON_Layer
A category into which geometric objects can be sorted.
ON_Linetype
A pattern of dashes and spaces that can be applied to a line or other curve.
ON_Material
A set of physical and optical properties that affect the appearance of a rendered object.
ON_ModelGeometryComponent
A geometric object such as a point, curve, surface, or solid.
ON_TextStyle
A collection of type-related settings, including font name and weight, that can be applied to textual objects.
ON_TextureMapping
A set of parameters that control how a texture is projected onto a non-planar surface during rendering.
Most of these classes expose a fairly straightforward, if somewhat lengthy, list of properties and methods pertaining to the aspects of the model they represent. For example, the ON_Material class defines a m_shine property to describe the shininess of the material it represents. The ON_Linetype class exposes an AppendSegment method to add a new dash or space to a line pattern and a DeleteSegment method to remove an existing one.
Instances of ON_ModelGeometryComponent, which comprise the bulk of a typical openNURBS model, are organized somewhat differently in that their characteristics are stored in a pair of objects nested within the geometry component. One of these nested objects is an instance of ON_3dmObjectAttributes and is responsible for holding non-geometric information such as the component's color, layer, and material. The other stores the geometry itself and is an instance of one of the dozens of child classes of ON_Geometry. Each child class represents a different type of geometrical object with a distinct set of properties: An ON_Point represents a point and contains a single coordinate triple, and an ON_LineCurve represents a line defined by a start point and an end point. Appendix B provides a complete listing of the types of geometry supported by openNURBS.
3.2Programming Languages
OpenNURBS is written in C++, a statically-typed compiled language designed by Bjarne Stroustrup and first released to the public in 1985. C++ is known for its speed and efficiency and is most commonly used today in resource-constrained environments, such as microcontrollers, and computationally intensive applications such as graphics. However, C++ also has a reputation for being difficult to write, debug and comprehend, and lacks features such as automatic memory management that are expected of a modern programming language.
Bindings for openNURBS are also available in three other programming languages through a collection of libraries known as rhino3dm. The first of these languages, Python, is a dynamically-typed interpreted language created by Guido van Rossum and first released in 1991. Its design philosophy, which emphasizes simplicity, readability, and unambiguousness, has led Python to become one of the most widely-used programming languages in contemporary software development
(Peters 2004; TIOBE 2022).
Rhino3dm also offers a library for JavaScript, a dynamically-typed interpreted language most commonly used in web applications. JavaScript was created by Brendan Eich at Netscape and was first introduced in that company's Navigator web browser in 1995. The language was subsequently adopted by Microsoft for the Internet Explorer browser and later standardized as ECMAScript in 1997.
C# is a statically-typed compiled language developed by Anders Hejlsberg at Microsoft and first published in 2000. Although the C# language was standardized by ECMA in 2002 and ISO/IEC in 2003, the Microsoft-produced compiler and associated .NET libraries remained proprietary until the mid-2010s. Even today, C# is typically associated with applications developed for Microsoft's Windows operating system. McNeel's Rhinoceros 3D modeling software, which originated on Windows, is written in C#, and many programs that read and write openNURBS models rely on its C# bindings.
Of the four programming languages described above, only the original C++ implementation of openNURBS offers complete access to all facets of an openNURBS model. The C# library contains the vast majority of the functionality present in the C++ SDK, and the Python and JavaScript libraries are each subsets of what is available through C#. Initial explorations for this thesis were conducted in C++ in anticipation of a program that would eventually need access to virtually all parts of an openNURBS model. However, it became apparent that the idiosyncrasies of the C++ language posed an unacceptable impediment to rapid prototype development. Therefore, development was switched to Python, a language with broad support from the open source community and which would support rapid iteration of prototype applications for diffing, patching, and merging openNURBS models.
During the development of this thesis, the limitations of the Python bindings to openNURBS necessitated contributions to the open-source rhino3dm project. These contributions are detailed in Appendix C.
3.3The Unix Philosophy
Previous investigations into the intersection of version control and design have tended to suffer from an overly broad focus which has led to the development of expansive platforms rather than purpose-specific tools. Several have implemented entirely new geometry- or design-oriented version control systems instead of developing discrete tools for diffing or the visualization of diffs that could expand on the strengths of existing VCSs. Some have even implemented their own 3D modeling environments (Sakai and Tsunoda 2015) or added such extraneous features as real-time chat (Zhang 2021), essentially “reinventing the wheel” by creating new implementations of already well-defined applications.
In contrast, this thesis seeks to develop a set of programs that are intentionally narrow in scope and are designed to work as components of a larger system rather than as systems unto themselves. The three programs will focus on the problems of diffing, patching, and three-way merging of openNURBS models, respectively, and will ignore "superfluous" issues such as the visualization of diffs or the creation of a graphical user interface (GUI) for merging openNURBS models. Although such features may be desirable in the broader scope of optimistic version control for architecture, they are not immediately relevant to solving the problems of diffing, patching, and three-way merging of openNURBS models.
In maintaining a narrow scope for its programmatic output, this thesis abides by the Unix philosophy which, in the words of Douglas McIlroy, states that developers should:
Write programs that do one thing and do it well. Write programs to work together. Write programs that handle text streams, because that is a universal interface. (Salus 1994, 52).
The Unix philosophy encourages the development of modular and reusable tools from which solutions to larger problems can be composed. As an example, let us consider the traditional Unix commands ls and wc. The ls command lists the names of files and folders in a directory, printing each name on a separate line of the output. The wc command, when used with the -l option, counts the number of lines in a file. By piping the output of ls into wc -l, we create a new command that counts the number of files and folders in a directory. This combined command, ls | wc -l, accomplishes a more complex task that neither of its simpler constituent commands can do alone.
The programs developed as part of this thesis are meant to be used in combination with other programs as well. By combining them with an existing VCS, end users can enjoy the full breadth of features provided by that VCS and have those features extended to openNURBS models. This thesis will demonstrate the integration of its programs into a Git repository so that common Git operations such as commits and merges can be performed on openNURBS models transparently and in a fully optimistic manner.
3.4Delta Format
The Unix philosophy also encourages the use of plain text as a data exchange format between programs. Text is a "universal interface" not only in the sense that it can be read by multiple programs, but also because it can be interpreted by humans as well. Plain text has the capacity to be self-describing by including not only data, but also the context necessary to understand those data. Storing information in self-describing plain text files greatly simplifies testing of software that uses that information and allows for further processing and analysis of that information by other applications (Hunt and Thomas 2000).
The output format of the diffing program described in this thesis (and, consequentially, the input format of its patching program) is inspired by the plain text "unified" format supported by the standard diff and patch commands and favored by most modern VCSs (MacKenzie, Eggert, and Stallman 2021b). It is hoped that by mimicking the unified diff format, the openNURBS delta format described here may retain at least some compatibility with existing diff analysis tools.
As in a unified diff, an openNURBS diff begins with a two-line preamble that lists the names of the two files that were compared and the times at which they were last modified. For example, the preamble
corresponds to a diff between two files, olderModel.3dm and newerModel.3dm, that were last modified roughly 25 hours and 36 minutes apart at the beginning of October 2022.
Following the preamble, both a unified diff and an openNURBS delta consist of a series of hunks, or groups of related changes. In the unified format, a hunk describes a set of changes that occur within a few lines of one another. Because openNURBS is a binary format that does not have lines, the hunks in an openNURBS delta correspond to the sets of changes made within individual model components.
Each hunk starts with a header line that indicates the type of component, its UUID, and the operation performed on it and begins and ends with a pair of @ symbols. The operation is encoded in the first non-whitespace character after the initial @ symbols: a plus sign indicates that the component was added to the model, a minus sign indicates that the component was removed from the model, and a tilde indicates that the component was modified. The component type, which immediately follows the operation symbol, corresponds to the list of component types presented in Section 3.1 unless the component is an instance of ON_ModelGeometryComponent, in which case the name of its geometry type is used instead. For example, the line
@@ ~Layer 6f9cb61e-f062-4751-aca1-5cc587ccd0ae @@
introduces the hunk for a modified layer identified by a UUID beginning with 6f9c, and the line
introduces the hunk for a newly created geometric component that contains a LineCurve and is identified by a UUID beginning with f497.
The openNURBS delta format simplifies the openNURBS data model by depicting components as having a flat set of properties that can be expressed as a list of key-value pairs. Whereas the openNURBS SDK places the CastsShadows property on an ON_ObjectRenderingAttributes object which is nested inside an ON_3dmObjectAttributes object which is linked to the component, the openNURBS delta format presents that property as belonging directly to the component itself. In doing so, it presents a readily comprehensible data model to end users who wish to inspect the output of a diff and streamlines the reconciliation process during merges.
A list of colon-separated key-value pairs follows the header of each hunk. For components that were added to the model, this list includes all of the properties of the component whose values differ from their defaults, which provides sufficient information to recreate the component in a future patch or merge operation. For example, the hunk for the LineCurve mentioned above might include the lines
StartPoint: (1, 0, 0)
EndPoint: (9, 0, 0)
Layer: 6f9cb61e-f062-4751-aca1-5cc587ccd0ae
which would indicate that the newly created line runs horizontally for eight units and was placed on the layer identified by a UUID beginning with 6f9c. Note that a LineCurve has many properties besides StartPoint, EndPoint, and Layer, but they are not included in the hunk because they still have their default values. A full listing of the properties supported by each component type is given in Appendix D.
The names and values of the non-default properties of deleted components are similarly enumerated in their respective hunks. Their inclusion makes the delta bidirectional so that a patch operation can be applied in reverse to transform a newer version of a model back into an older version.
For components that were modified, the list of key-value pairs enumerates the properties whose values have changed along with a representation of how their values have changed. Most changes will be represented as substitutions of one value for another. For example, the hunk for the aforementioned modified layer might include the lines
Name: "Layer 01" -> "Lines"
Color: (200, 0, 0, 255) -> (0, 255, 255, 255)
which would indicate that the layer was renamed from "Layer 01" to "Lines" and that its color was changed from red to cyan.
a. The identity matrix represents no change to the geometry.b. A translation 2 units in the x direction, 3 units in the y direction, and 5 units in the z direction.c. Uniform scaling by one-half centered on the origin.d. Uniform scaling by one-half centered on the origin.e. Transformations b, c, and d combined into a single matrix.f. The inverse of transformation e.Figure 3.1. Example transformation matrices
Changes to certain geometric properties will be expressed as 4×4 matrices, which are capable of representing a multitude of geometric transformations, including translation, rotation, scaling, and shearing, in a singular and consistent data structure (Figure 3.1). These matrices, which are common in 3D computer graphics, can be used to transform any type of geometry in an openNURBS model, and can be inverted, composed with other matrices, and decomposed into sets of simpler transformations. In the openNURBS delta format, these matrices will be expressed in row-major order, which lists the sixteen values in the matrix from left to right beginning with the top row and proceeding to to the bottom. The matrix shown in Figure 3.1b, for example, would be written as
transform(1 0 0 2; 0 1 0 3; 0 0 1 5; 0 0 0 1)
3.5System Architecture
The goal of this thesis is to develop a suite of three command-line programs that implement diffing, patching, and three-way merging for openNURBS models and to demonstrate their integration into a Git repository so that common operations such as commits and merges can be performed on openNURBS models transparently and in a fully optimistic manner. The programs will be named 3dmdiff, 3dmpatch, and 3dmdiff3, respectively, after the standard programs used to perform these operations on plain text files and the .3dm file extension conventionally used to identify openNURBS models.
A significant amount of code will be shared among these three programs. Key concepts such as components and properties remain the same regardless of whether one is diffing, patching, or merging; they are simply used in different ways depending on which operation is being performed. This situation lends itself to a layered architecture, a software design pattern in which the application's responsibilities are divided among multiple levels, each of which relies on the functionality of the one below it. Layered architectures are generally organized such that the lowest level defines fundamental concepts (using classes) in as generalized a manner as possible, and each level above it employs those concepts in an increasingly specialized fashion. This arrangement promotes code reuse by allowing new specializations to be constructed on top of existing layers as well as by permitting one implementation of the set of concepts expressed by a layer to be exchanged for another. A layered architecture can also advance the testability of an application, help developers more easily comprehend its code, and simplify dependency management (Buschmann et al. 1996; Fowler 2002).
Figure 3.2. The layered architecture of the 3dmdiff suite
The base of the layered architecture of the 3dmdiff suite (Figure 3.2) will consist of an abstract model that defines the elemental concepts, such as components, properties, values, and deltas, around which the programs are based. The fundamental algorithms involved in diffing, patching, and three-way merging will also be defined at this level of the application in a way that is agnostic of openNURBS or the details of the rhino3dm library. This separation will encourage a clearer expression of the ideas underpinning the application and will allow the software to be more easily modified to use a different openNURBS library, or even to work with a different file format entirely, at some point in the future.
The next layer will consist of a collection of adapters that connect the generalized classes of the abstract model to the particulars of the openNURBS format as implemented in the rhino3dm library. Specific component types and properties will be defined at this level, and peculiarities of the openNURBS format, such as components being addressed both by UUID and by index, will be dealt with.
The 3dmdiff, 3dmpatch, and 3dmdiff3 programs themselves form the third and uppermost layer of the application. They will be responsible for collecting user input, reading and writing files, and employing the functionality provided by the adapter layer to accomplish their respective tasks.
