NPUSH(nged)

npush - push matrices down a tree hierarchy

npush [-h] [-?] [-v] [-f] [-x] [-r] [-s] [-d max_depth] {arg1 [arg2]…​}

BRL-CAD uses a global coordinate system in which all objects are placed. This means each region must uniquely occupy its own portion of that space in order to avoid overlapping with another region. Naively, this means that all objects defined in a .g file need to individually describe distinct volumes using unique primitives. While possible, such an approach is quite wasteful if different regions define the same shape and vary only in the positioning of that shape. A classic example is as a standard bolt used hundereds of times in assembling a machine - ideally such a shape should only need to be described once, and then instances of that shape are positioned to identify individual bolts in the overall model.

COMB trees, which describe organized hierarchies of individual shapes (or other COMB trees) in BRL-CAD, are the standard mechanism used in .g files to reusing otherwise identical object definitions in different positions and orientations. Matrices associated with instances of objects listed in COMB trees position those individual parts, and matrices at different portions of the COMB tree hierarchy can position smaller or large components of the whole. For example, the tree:

appears at first glance to define an overlap, since it includes two different regions both of which are defined using the same sphere object: sph3.s. However, if we inspect sph3_1.r and sph3_2.r more closely, we see that their definitions incorporate matrices over the instances of sph3.s:

The instance of sph3.s in sph3_1.r is offset in the X direction by 10mm, and the sph3_2.r instance is offset by 20mm. In addition, if we inspect sph3’s tree:

we see that the instance of sph3_2.r in sph3 also has a matrix offsetting its position. So the instance of sph.s defined by sph3/sph3_2.r/sph.s is offset in total by 120mm in the positive X direction relative to the global definition of sph.s

As useful as these matrices are, users frequently need to consolidate multiple levels of positioning within a COMB tree, or even eliminate them completely if a client’s code is not able to properly interpret the matrix information of a COMB hierarchy for its own processing. Thus, specific logic is available in BRL-CAD to accomplish these tasks.

The GED command npush defines logic for "moving" matrix operations within a COMB tree, without changing the position of individual object instances in the tree definition.

It is worth taking a little time to define what we are referring to when we discuss the concept of depth when it comes to applying matrix pushing operations. Consider the hierarchy:

M1, M2, etc. are matrices applied at each level of the hierarchy. When discussing M1, we would refer to that matrix as being at "depth 1" in the hierarchy, as it is defined at one level below the top of the tree. Similarly, M2 would be defined as being at depth 2, and so on.

When discussing depth in push operations, pushing a matrix to a depth means we propagate the matrices down the tree to define a matrix at the specified depth. For example, in the above example, a push of the matrices to depth 4 would result in:

where M1234 is the accumulated application of M1, M2, M3 and M4. Note the new matrix is applied at depth 4, the depth specified as the depth limit in the push. Similarly, a depth limit of 6 would result in:

where M123456 is the accumulated application of M1, M2, M3, M4, M5 and M6. Note that the final step of eliminating the matrix by updating the parameters of sph.s was not taken. That operation is defined conceptually as being at one depth lower than the matrix applied to the object. Thus, it would require a depth limit of 7 to completely eliminate all the matrices in the example and update sph.s:

Note that if an object or comb exists at different levels of the hierarchy, depth limits may produce copies of an object even if there wouldn’t otherwise be a need for those copies. Take the following example:

where 3*M1+M2 = 2*M3 (i.e., the matricies on each branch of sph_010’s tree individually evaluate out to the same result). Since sph10.s ends up in the same place in both branches of sph_010, a full push of all matrices in this tree shouldn’t need to create a copy of sph10.s with new paramenters. However, if a push is limited to depth 3, we get a different outcome in that respect:

Depth 3 is deep enough that the parameters of sph10.s in the second branch should be updated. However, in the first branch, there is an instance of sph10.s that will remain unmodified with a depth limit of three. Thus, the database needs to contain both the modified and unmodified sph10.s in order to define the requested comb tree. A subsequent full push would result in sph10.s being identical to sph10.s_01, but (at least for now) logic to automatically recognize this case and simplify it is not built in to the push logic.

The same phenomena can occur with comb trees. Consider the following example:

If sph_011 is pushed to depth 3, the matrices will be pushed to the level of sph11_g’s instance references (sph11.s, in this case.) However, if M1 != M2, sph11_g would need to have two different matrices in its tree for the same instance. Since a depth limit of 3 does not push the matrices down to parameter setting of sph11.s, a new comb must be created:

In addition to numerical depth limits, npush offers two additional specifiers that are more aware of specific types of objects in trees. The r option will push matrices down to a level just above region references, and the s option will push matrices to a level just above primitive shapes. For example, using the following hierarchy:

a r push would result in the following:

A s push, on the other hand, will take the matrices in both branches deeper:

Note that neither option alters the parameters of primitive shapes.

Worse still is a case where multiple copies of identical objects are referenced at multiple levels. Consider the following example:

If we push to depth 3, we end up with four different versions of the sph16.c tree:

The first stage of the answer is to create three new combinations and redefine the sph16a tree:

That addresses sph16_1, but the tree updates to sph16a created a new problem: now we have two different versions of the sph16a tree. To resolve that problem, we must create a new comb to replace one of the conflicting sph16a instances and redefine the sph_016 tree:

Unlike sph16a and sph16_1, sph_016 has not seen any changes to its volumetric definition. sph_016 is the "top level" object specified for this push, and as such constitutes a reliable termination point for any need to propagate tree changes. Even if any combs elsewhere in the database reference sph_016, they will not see any volumetric changes as a consequence of the operation and do not need to redefine their trees to preserve original sph_016 trees for external use in copies of sph_016.

This software is Copyright (c) 1989-2021 by the United States Government as represented by U.S. Army Research Laboratory.

Reports of bugs or problems should be submitted via electronic mail to devs@brlcad.org