The 3dmdiff, 3dmpatch, and 3dmdiff3 programs developed for this thesis and described in Chapter 4 have been successfully shown to accomplish each of their respective intended tasks. Furthermore, the procedure described in Section 5.2 has been used to integrate these programs into a Git repository, and two branches in that repository which contained separately modified versions of the same openNURBS model were able to be merged. This thesis has therefore successfully demonstrated the possibility of enabling optimistic version control for openNURBS models and, by extension, other binary file formats used in the architecture profession using an off-the-shelf version control system.
However, the 3dmdiff, 3dmpatch, and 3dmdiff3 programs as they exist today are far too limited in their support for openNURBS component and geometry types to be of practical use to architects. As of this writing, only ON_Layer, ON_Linetype, ON_Group, and ON_Material components are able to be diffed, patched, and merged, along with ON_ModelGeometryComponent instances containing ON_Point, ON_ArcCurve, ON_LineCurve, and ON_TextDot geometries. Even among these eight component types, not all properties are fully supported. The 3dmpatch program, for example, is not yet able to change the stacking order of layers, and 3dmdiff is unable to examine the textures assigned to a material.
In order to progress beyond the proof-of-concept stage, a significantly broader set of component types and properties must be supported. This will require developing algorithms to handle complex geometric shapes such as polylines, Bézier splines, and NURBS curves and surfaces which are defined by a variable number of control points. These algorithms must be able to detect the addition and deletion of control points between versions of such geometric components, and to do so, they must determine which control points in one version of a shape correspond to the control points in another version of the same shape. Unlike the components in an openNURBS model, control points do not come with a unique ID that can be used to identify them across model versions. They cannot be reliably identified by their position within the shape’s overall list of control points because items may have been added to or removed from that list, nor can they be compared by value because the shape itself may have been moved, rotated, or transformed in some other way.
The most promising solution to this dilemma is to employ a registration algorithm such as those used for aligning point cloud data collected by 3D scanners as well as in computer vision applications. A point registration algorithm would not only be able to identify correspondences between two sets of control points, but would also produce a best-fit transformation matrix for converting one version of a complex geometric shape into another. One potential difficulty is that these algorithms minimize the average error rate across all the points in the data set, often resulting in a matrix that fails to transform any points in the source data set to the exact location of its counterpart in the target data set. A more desirable outcome for the purposes of diffing would be to arrive at a matrix that produces an exact solution for as many points as possible and distributes any error among the remaining points (Figure 6.1). Additionally, existing registration algorithms are designed to work with data sets consisting of millions of points; it remains to be seen how well they would perform in situations where the number of points often does not exceed a few dozen.
Figure 6.1. Two approaches to point registration. A square (left, in blue) is transformed into a trapezoid (red) by moving its lower right corner inward. A typical point registration algorithm might attempt to minimize the error rate between the old and new sets of control points by producing a result similar to the center diagram. A better alternative for diffing applications would match as many of the points exactly as possible.
In addition to singular geometric types such as points, curves, and surfaces, openNURBS also supports composite geometries such as ON_PolyCurve and ON_Brep which are made up of simpler shapes linked together to form a complex whole. The naïve approach to comparing these geometric constructs would be to examine each of their constituent parts independently of the parent geometry. However, this strategy ignores the efficiencies that could be gained by recognizing that those parts share vertices and edges, and that movement of one edge or face of a composite geometry may be the result of a change to one of its neighbors. The changes to a cube, for example, that has had one of its faces twisted could be documented in a delta that records only the rotation of that one face. The naïve approach, however, would result in a more complex delta that also records changes to the four adjacent faces that were deformed as a result of the rotation. The procedures and algorithms necessary for efficiently handling these types of situations and producing minimal deltas will need to be examined in future work.
→
Figure 6.2. A twisted cube. Should a delta describing the differences between these two shapes record only the rotation of the top face, or should it also explicitly include the deformation of the faces that adjoin it?
Floating Point Numbers
Storing integers in a computing system is a relatively simple matter of converting the integer to a base two representation and writing the binary digits to an appropriately-sized section of computer memory. Non-integral real numbers, however, are not so straightforward to deal with. Most computer programs use a floating-point representation for such numbers, which breaks them into two integers called a significand and an exponent. The significand stores the significant digits of the number, while the exponent controls the position of the radix point, which separates the integer part of the number from its fractional part. Increasing or decreasing the exponent causes the radix point to "float" to the right or left, respectively, relative to the number's significant digits. Figure 6.3 shows several examples of floating-point numbers in base ten; floating-point figures in a computer program would, of course, use base two (“IEEE Standard for Binary Floating-Point Arithmetic” 1985).
Figure 6.3. Examples of floating-point numbers
Floating-point representation allows for space-efficient storage and fast computation of a wide range of numerical values. Unfortunately, limits on the precision of floating-point numbers due to a finite number of bits being allocated to store the significand and exponent in computer memory can cause them to suffer from round-off errors. In the same way that certain fractions cannot be represented exactly in a limited number of decimal digits (0.333, for example, is close but not precisely equal to $\frac{1}{3}$), other numerical values cannot be represented exactly in base two floating point. The rounding errors that result from approximating such numbers can accumulate during mathematical operations, leading to surprising or unexpected results such as the ones below.
print(0.1 + 0.2 == 0.3) # outputs False
print(0.1 + 0.2) # outputs 0.30000000000000004
The equality operator (==) in Python and most other languages performs a bit-for-bit comparison of floating-point numbers, ignoring the potential for round-off errors and leading to situations where two numbers that should be considered equal are reported as not being so. A better approach to comparing floating-point numbers involves the use of a tolerance: if the absolute value of the difference between the two numbers is less than the tolerance, then they are considered equal. OpenNURBS itself uses this method frequently, and 3dmdiff should adopt it as well in order to produce more meaningful deltas. The openNURBS format stores tolerances for distances and angles within each model that would be ideally suited for this purpose. Alternatively, a command line option could be added to 3dmdiff and 3dmdiff3 to explicitly set a tolerance to be used for comparing floating-point values.
Beyond UUIDs
The 3dmdiff, 3dmpatch, and 3dmdiff3 programs rely on UUIDs to quickly and unambiguously find correspondences between the components of openNURBS models. This reliance is not without its drawbacks, however, as it leaves the programs unable to detect semantic relationships between objects in different versions of a model. If two editors, for example, were each to add an object of roughly the same size and shape to the same place in their respective versions of a model, a human mind would recognize that these objects are likely to represent the same thought or entity and attempt to reconcile their differences to arrive at a more complete understanding of that thought or entity. On the other hand, 3mddiff would treat the two objects as completely unrelated because they do not share a common UUID, and after merging the two versions with 3mddiff3, the model would be left with two of what should have been recognized as the same object overlapping one another in three-dimensional space.
Temporal and evolutionary relationships are also lost through a singular reliance on UUIDs. When a component in an openNURBS model is duplicated, it receives a new UUID that is unrelated to that of its predecessor. Ideally, 3dmdiff would be able to detect the relationship between the predecessor and the copy and use that information to construct a more meaningful delta, but its current dependence on UUIDs to detect object correspondences makes this impossible.
The utility of 3dmdiff, 3dmpatch, and 3dmdiff3 would be greatly enhanced by incorporating some heuristic to check for object correspondences based on attributes other than the component's UUID. Unlike the future work discussed in the previous two sections, detection of semantic relationships is a non-trivial problem and a subject of active research with respect to many different fields and types of data. Carra and Pellacini (2019) developed a set of heuristics for matching scene objects, shape data, textures, and animation frames in SceneGit which may be adaptable for the types of components present in openNURBS models.
Future work must also evaluate other potential strategies for object correspondence detection, including point cloud registration and machine learning techniques.
Conflict Resolution
The current behavior of 3dmpatch and 3dmdiff3 is to abort a patch or merge operation when conflicting edits are detected. Such a reaction is unacceptable for most real-world scenarios, so future work must include the ability to handle conflicts in a more intelligent fashion. One option would be to set aside the conflicting edits for manual inspection and proceed to apply the non-conflicting edits to the patch or merge as usual. This is the approach taken by GNU patch, which writes a description of each conflict to a reject file.
Alternatively, 3dmpatch and 3dmdiff3 could ask the user to choose between predefined methods of resolving a conflict. Git provides a precedent for such behavior: During a merge, a user can use the command git checkout --ours to select the version of a conflicted file from the current branch, and the command git checkout --theirs to select the version from the branch being imported. A conflict found during an openNURBS patch operation would need to present three options:
To apply the conflicting update, if possible, and proceed with the remainder of the patch.
To skip the conflicting update and proceed with the remainder of the patch.
To abort the entire patch operation.
A conflict found during a merge, on the other hand, would need to present four alternatives:
To use the value of the conflicting property from "my" version of the model.
To use the value of the conflicting property from "your" version of the model.
To keep the original value of the conflicting property and discard the changes made in "my" and "your" versions of the model.
To abort the entire merge operation.
Asking the user to choose between options such as these would be a simple method of implementing interactive conflict resolution, at least from the programmer's standpoint. Unfortunately, this strategy ignores the possibility that the most appropriate resolution to a conflict may be a novel creation of the user rather than a preexisting choice. Furthermore, text prompts in a command-line application do a poor job of explaining where in a model a conflict has been detected or what the various alternatives look like. Git and GNU diff3 handles these problems by inserting conflict markers around problematic sections of a file that prevented it from being automatically merged. For example, suppose two programmers both decide to augment a rather simplistic function:
# A function that divides one number by another
def divide(numerator, denominator):
return numerator / denominator
One adds a new parameter that, when set to False, prevents the function from raising an exception when the denominator is zero:
The changes made by these two programmers conflict with one another, and would result in conflict markers being added to the source file during a merge:
The programmer in charge of resolving the conflict would then have the option choosing what aspects of each version to discard or retain before completing the merge, perhaps resulting in a hybrid version such as:
# A function that divides one number by another
def divide(numerator, denominator,
shouldRaise=True, whenDividingByZero=math.nan):
if not shouldRaise and denominator == 0:
return whenDividingByZero
return numerator / denominator
The insertion of conflict markers is an acceptable means of highlighting merge conflicts in plain text files, but is unsuitable for handling conflicts in openNURBS models because the openNURBS file format has no provision for storing or displaying alternative or conflicting information about a component. Furthermore, resolving conflicts in 3D geometric data demands the ability to visualize the conflict graphically and in three dimensions, a facility that line-based solutions such as conflict markers cannot provide. Future work should therefore devise a way to visualize and resolve conflicts from within an openNURBS modeling application, possibly through a plugin for McNeel's Rhinoceros software.
Optimism in the Real World
Finally, the efficacy of optimistic version control techniques within an architectural workflow must be validated under real-life conditions. Although this thesis has shown that it is possible to diff, patch, and merge openNURBS models in a version control repository, it remains to be seen how architectural professionals would react to this promising yet unfamiliar workflow and whether its adoption would result in quantifiable benefits to the industry. Furthermore, it remains possible (although unlikely, in the opinion of this researcher) that the potential for edit conflicts during concurrent editing of a file as complex as a 3D model is simply too great for optimistic version control to be a viable method of enhancing collaboration in architectural practice.
Conclusion
This thesis has demonstrated the possibility of enabling optimistic version control for openNURBS models by implementing a suite of programs that provide facilities for diffing, patching, and three-way merging of files in that format and describing how those programs can be integrated into a Git repository. Furthermore, it has delineated an abstract model through which the capabilities of those programs can be expanded, and support for diffing, patching, and three-way merging of other file formats may be realized. By pursuing and building upon the techniques presented in this thesis, the architecture community can gain the benefits of concurrent work, enhanced collaboration, and rapid exploration of design alternatives that optimistic version control has to offer.
→
