• New BRL-CAD Database Format, Version 5
• Index
• Goals
• Features for possible inclusion
• Features beyond the scope of this effort
• Document Structure
• Background and Terminology
• Format of Data Elements/Database External Format
• I. Definition of A Generic Database Object
• Object Structure
• Flags
• Object_Type
• Major_Type = 0: Database-Support Private Objects
• Major_Type = 1: BRL-CAD Nongeometry Objects
• Major_Type = 2: BRL-CAD Geometry Objects
• Major_Type = 3: Opaque Binary Objects
• Major_Type = 4: Atribute-Only Objects
• Object Length
• Object Name
• Object Attributes
• Object Body
• Padding and Length Rounding
• Compressed Objects
• II. Overall Database Organization
• III. Details of the Object Body element when used for holding BRL-CAD nongeometric Objects
• Combinations (Groups and Regions)
• Storing Binary Trees in Combinations
• New On-Disk (External) Format for Combinations
• IV. Details of the Object Body element when used for holding BRL-CAD Geometry
• Ellipsoids
• The Sphere
• The ARB8
• Halfspace Solid
• The other geometric types
• V. A Proposal for Parametric Databases
• Highly Interactive Coupling Between Variables and the MGED Display
• Requirements for the new Selector Node
• Random Unresolved Questions
• VI. Community Feedback on the Proposal
• David P. Kitzinger, ARA
• John Keyser, UNC
• VII. Database library application programming interface (API)
• VIII. Appendix: Earlier Proposals for Database Organization

Goals

Revising BRL-CAD to use a new database format (v5) is intended to provide an evolutionary, upward-compatible capability with a minimal implementation and deployment burden. Overall, the goal is that there will be few, if any, visible changes to the end-user. Specific goals include:

• Double-precision floating point numbers (15 decimal digits of significance) in the definition of the primitive solids instead of single-precision (7 decimal digits of significance). As the size of the "virtual world" being modeled increases (to 12 km square and beyond), single-precision is no longer sufficient to maintain millimeter-size accuracy in worlds larger than about 100-m square.
• Binary machine-independent ".g" file format, eliminating the necessity for the g2asc and asc2g programs. (They will still exist, however, for diagnostic purposes.)
• Unlimited-length object names (instead of the current 16-character restriction). This will be beneficial, for instance, when adding prefix strings in combining several large databases.
• Real boolean trees.??????As opposed to what - maybe an explanation of what we have now.
• Unlimited-length object attribute names, including a human-only comment attribute.
• Ability to store arbitrary data (texture maps, for example) as opaque ???objects within ".g" database, as well as in outboard files.
• Built-in data compression to reduce disk storage needs of objects.

Features for possible inclusion (Retain???)

• Parametric database. Variable substitutions.
• Selector nodes. Supports level-of-detail and multiple applications.

Features beyond the scope of this effort (Retain????)

• Changing from a global name space to a hierarchical name space.
• Changing from a single-file ".g" database to a format where each database object is stored in a separate file in the UNIX (????? word "UNIX" necessary) file system.
• Storing a database "table of contents" in a file, rather than rebuilding it at the start of each application.

Document Structure (????is this redundant with the Index)

• I. Definition of a Single, Generic Database Object
• II. How Objects Are Grouped into a Database
• III. Details of BRL-CAD-Specific Nongeometric Database Object Types
• IV. Details of BRL-CAD-Specific Geometric Database Object Types
• V. Extensions for Deferred Implementation
• VI. Community Feedback on the Proposal
• VII. Database Library Application Programming Interface (API)
• VIII. Appendix: Earlier Proposals for Database Organization

Background and Terminology

The database is organized as a directed acyclic graph (DAG), which comprises

• primitive solids - the minimal elements of the DAG.
• combinations - the nonminimal elements of the DAG, some of which are specially marked as regions. The maximal elements of the DAG are called tops.
• arcs - contain boolean operators and 4x4 homogeneous transformation matrices.

Format of Data Elements/Database External Format

• Numbers are stored in binary for storage efficiency, for speed of reading and writing, and for preventing errors from creeping in due to repetitive conversion between binary and an ASCII string representation. This eliminates the need to use the old g2asc and asc2g to move databases between machines of different architectures.
• All data in the object wrapper are stored in a machine-independent format, as follows:

• All floating point numbers are stored as IEEE double-precision, in big-endian order, where byte 0 is on the left end of the word.
• All integers are stored as either unsigned or twos-complement signed binary numbers in either 8, 16, 32, or 64 bits, in big-endian order.
• All character strings are stored in the ASCII 8-bit character set. A string is stored as an integer followed by an array of 8-bit characters. The last character in the array is always a null byte. The integer indicates the number of bytes in the array including the terminating null.

I. Definition of a Generic Database Object

The database access library stores objects as a collection of data with a globally unique name and places no interpretation on the content of those data. The object is the smallest granularity of an item in the database; objects must be read from and written to the database in a single atomic operation.

In the case of librt, each database object will contain exactly one combination node or leaf (solid) node.

Object Structure

The Object Header consists of:

• An 8-bit Magic1 element that holds a specific magic number value used for database integrity checking.
• A 16-bit Flags element consisting of three 8-bit fields: HFlags, AFlags, and BFlags, described later.
• A 16-bit Object_Type element organized into two 8-bit-wide fields: the Major_Type and the Minor_Type.
• An Object_Length element that indicates the total number of bytes required for this object, including the magic numbers.
• An Object_Name element that is a string holding a name unique to that object and drawn from a name space that is global to the database. Like other strings, it consists of two fields, Length and Data. In the case of the Object_Name element, these are referred to as Name_Length and Name_Data, respectively. Note: The Object_Name element is mandatory for all allocated storage in the database. Database free-space managment objects are the only objects for which the Object_Name element is optional.

• Any padding bytes necessary to bring the total size of the object in bytes to an integral multiple of 8.
• An 8-bit Magic2 element that holds a specific magic number value used for database integrity checking.

• An object may optionally have an Object_Attributes element consisting of a pair of fields: Attribute_Length and Attribute_Data. From the point of view of the database interface specification, the names and values of these attributes are opaque????; a standardized import/export encoding API will be provided.
• An object may optionally have an Object_Body element consisting of a pair of fields, Body_Length and Body_Data. From the point of view of the database interface specification, the format of the data is opaque??.

????Need a description that says that an object can now have (1) EITHER an attribute OR a body, (2) BOTH an attribute and a body, or (3) NEITHER an attribute nor a body.

The routines db_get_external() and db_put_external() are used to move objects in external format between memory and the database disk file. The routines db_wrap_external() and db_unwrap_external() are used to wrap and unwrap the

(already in external form) in a standardized database object's wrapper.

Flags

DLI flag

The DLI flag is not available to the higher database access layers.

Implementation note: Before writing a new object into the database in a free area, the library should read the object header from the database and confirm that the space is indeed free. Similarly, additions to the end should be checked by ensuring that the file hasn't been extended. In case the check fails, the database write should fail, the user should be notified, and the internal library mode (not the operating system file access permissions) should be changed over to read-only access so that no further attempts to write will be issued. These checks will provide protection against two or more users trying to modify the same database simultaneously and accidentally stepping on each other. In the NFS world, file locking isn't a strong enough assurance.

Wid flags

The Object_Wid flag, at the high end of HFlags, encodes the width of the Object_Length field. The Name_Wid flag, in bits 3 and 4 of HFlags, encodes the width of the Name_Length field (when the name element is present; see the N bit, shown later.). Attribute_Wid (or Body_Wid, as the case may be) encodes the width of the Attribute_Length field (when the Object_Attributes (or Object_Attributes) element is present. http://ftp.arl.mil/~mike/papers/brlcad5.0/newdb.html - bbitSee the P bit, below.)??????????.

The rationale for allowing the width of the Object_Length field to be specified independently of the other widths is to save space on objects in which the values in many of the length fields nearly overflow the specified field width, so that their sum requires a wider field. For example, for four 255-byte interior fields, the corresponding length fields need be no more than 8 bits wide, so the choice Interior_Wid=00 suffices, but their combined length of 1020 bytes would require Object_Wid=01. Because all of the length fields besides Object_Length must have the same width, the largest of the values stored in these length fields determines the value of Interior_Wid required. Both Object_Wid and Interior_Wid may vary from object to object. It is expected that the routines that write an object to the disk will use the narrowest width possible for each object.

Each of the N and the two P flag bits indicate the presence (1) or absence (0) of the corresponding element. This eliminates the need to specify a length of zero for optional fields that are not present in a given object.

• Header flags (HFlags):
• The "N" bit indicates whether the Name element (consisting of Name_Length and Object_Name fields) is present in the noncompressible basic header immediately following the Object_Length field. The width of the Name_Length field is specified by the Name_Wid field.
• Interior flags (AFlags and BFlags):
• The ``P'' bit indicates whether the Attributes (or, alternatively, Body) element consisting of Attribute_Length and Attribute_Data (or Body_Length and Body_Data) fields, is present in the Object_Interior.
• The 3-bit ``ZZZ'' flag indicates the compression, if any, of the object Attributes (or Body):

The remaining flag bits ``r'' in HFlags, AFlags, and BFlags are reserved for the design committee to waste on additional optional fields in the object.

Object_Type

Each different Major_Type value is assigned to a different class of database objects. The following values are defined in this specification:
 

The remainder are available for extending the types of objects that may be stored in the database, allowing BRL-CAD users to extend the database for their own particular purposes far beyond what the "attribute" method permits.

Major_Type = 0: Reserved

Major_Type = 1: BRL-CAD Nongeometry Objects

?????Should "Grip" and "Joint" objects be of this type, or Major_Type = 2?

??????Consistency:  Some tables have titles and other do not.  Do we care?

Major_Type = 2: BRL-CAD Geometry Objects

The details of these Minor_Types are provided in Section IV.

Major_Type = 3: Attribute-Only Objects

For example, if several objects need to have the same shader parameters, it would be possible to create one attribute-only object to hold these common attributes and serve as a simple form of "macro". Objects that needed to share these attributes could all reference the same attribute object. If the attribute object is altered, then all of the objects that reference it would be updated together. Without this capability, the user would have to update each element individually to alter the attributes.

Conventions will have to be established regarding which attributes of an attribute-only object will be used when a macro reference is performed. For example, rt shaders will only be interested in the value of the "oshader=" attribute, while librt's tree-walker might also be interested in the "rgb=", "giftmater=", "nsn=", "material=", and "los=" attributes (assuming that a convention was developed so that a combination could macro-reference an attribute-only object too).

An attribute-only object may not have an object body; thus, flag bit B must always be zero for this type of object.

As used by the rt family of applications codes, these attribute-only objects will contain "macros" for shaders. The shader name and its parameters shall be encoded as a single ASCII string, which is the value of the "oshader=" attribute. An rt shader named "macro" (or equivalent) would take a single parameter "obj=", which would specify the name of the attribute-only object in the database from which the actual shader and shader parameter information would be extracted.

There will be one attribute-only object with a reserved object name of "_GLOBAL" that will be used to contain various kinds of states that are global to the entire ".g" database and that had previously been found in the database header itself. There will be the following BRL-CAD-specific attributes whose meaning is predefined for the _GLOBAL object:

Bulk Binary Objects (Major_Types 8-31)

MGED and standalone commands must be built to store/extract these opaque?? binary objects between a ".g" file and stdin/stdout/auxiliary files. A user might want to use those same MGED commands to store/extract the binary object body of any object for external processing. An easy example to imagine is the importing and exporting of texture maps for external processing, but the same commands could be used for importing and exporting solid parameters in their external binary form.

These objects may be referenced in combination nodes, for organizational purposes, but they cannot be drawn in MGED or raytraced, and doing so would result in a warning message being printed by the tree walker as that arc is traversed. This class may be used by all applications and layers.

The data's purpose may be placed in the "purpose=" attribute. (????????Need a table/registry of presently known values for this attribute.)

Routines that retrieve bulk binary objects should check the minor type and the "purpose=" attribute and send a warning message in the event of a mismatch, but best-effort processing of the object should continue. This will permit some degree of error checking, which should benefit novice users without standing in the way of "creatively" reusing one set of data, (e.g., using one array of values as both a height field and a bwtexture). This allows common data perversion practices, such as interpreting an array of floats as an array of bytes, to continue.

Each application will need to have its own syntax for the user to specify whether the data source is an outboard file or a raw-binary object. For example, the current RT sh_texture module uses the keyword file="name" to indicate an outboard file; that might be supplemented with an additional obj="name" possibility for retrieving from an inboard raw-binary object.

Major_Type = 8: Experimental Binary Objects

Major_Type = 9: Uniform Array Binary Objects

Point of Discussion?????Has ramifications... we have to implement type advising, so that applications that use these data can compare the type provided in the minor type code with the type that they're expecting and advise the user (with a warning message) that there is a potential type mismatch.
 

The 3-bit ``Atom'' flag indicates the fundamental data type of the atomic elements in the array according to the following scheme:
 

The ``S'' bit indicates whether an integer type is signed (1) or unsigned (0). Floats and doubles (i.e., atomic types with the highest atom bit equal to 0) are explicitly signed, so they will have the ``S'' bit equal to 1. (The bit patterns corresponding to unsigned floats and doubles are reserved for possible other use.)

The 2-bit ``Wid'' flag specifies the length (in atomic elements) of the array elements:
 

The remaining Minor_Type bits ``r'' are reserved for the design committee to waste on gratuitous other stuff, possibly including extensions of the ``Atom'' and/or ``Wid'' flags.

As examples, data in PIX(5) format, which might be used for a texture map, would have Minor_Type ``0010 0100'', indicating a triple of unsigned char, and CMYK data might be stored with Minor_Type ``0011 1011'', indicating a quadruple of doubles.

The data's purpose (e.g., height field, texture, bump, displacement, etc.) may be placed in the "purpose=" attribute. ?????Point of Discussion???(Need a table/registry of presently known values for this attribute.)

Major_Type = 10: MIME-Typed Binary Objects

Major_Type = 16-31: Registered-Type Binary Objects

Major_Type = 255: Database Layer Internal Objects

A Minor_Type of 2 indicates that this is a database header.

Object Length

Object Name

The name is specified in 8-bit ASCII. There is no support for UNICODE. The name is null-terminated, and the null byte is included in Name_Length.

See the section on DLI flags. In the case of Free objects, the name is not retained. Undeleted objects have a different DLI flag code.

Object Attributes

binding attributes to values.

These are ASCII strings of unlimited length. These attributes are intended for direct use by programs. There will be a WWW registry of attribute names presently in use to prevent two application developers from using the same attribute_name for different purposes.

For attribute names and attribute values, The decision was taken to support 8-bit ASCII only. The on-disk encoding of this will simply be:

where NULL represents a byte with all bits zero. The NULL in place of anameN+1 signals the end of the attribute data, simplifying the job of the reader. 

Every object in the database may have zero or more attributes attached to it; the meaning of these attributes will vary depending on which application or library processes them.

There are several aname conventions that all BRL-CAD applications are expected to respect. There will be a WWW extendable registry of "in-use" anames, so that independent applications developers may select aname strings for their own use without fear of name conflicts later. The initial registry would include:

Object Body

Padding and Length Rounding

Magic1 (1byte)
HFlags = 000xxxxx (1 byte)
AFlags = 0000xx00 (1 byte)
BFlags = 0000xx00 (1 byte)
ObjType = Free (2 bytes)
ObjLen = 7 (1 byte)
Magic2 (1 byte).

The minimal valid object is thus the following Free object:

Magic1 (1byte)
HFlags = 00000010 (1 byte), Wid=00, N=0, DLI=02
IFlags????? = 00000000 (1 byte), Wid=00, A=0, B=0, ZZZ=000
Object_Type = RESERVED (2 bytes)
Object_Length = 1 (1 byte)
Pad (1byte)
Magic2 (1 byte).

Magic1 (1byte)
HFlags = 000xxx01 (1 byte), Wid=00, N=0, DLI=01
IFlags????? = 0000x000 (1 byte), Wid=00, A=0, B=0, ZZZ=000
Object_Type = RESERVED (2 bytes)
Object_Length = 1 (1 byte)
Pad (1byte)
Magic2 (1 byte)

The hex and ASCII dump of this object would look something this:

 
76 01 00 00 00 01 00 35 |v......5|

Magic1 (1byte)
HFlags = 001xxxxx (1 byte), Wid=00, N=1, DLI=00
IFlags ?????= 0000xxxx (1 byte), Wid=00, A=0, B=0, ZZZ=000
Object_Type = OPAQUE?????_BINARY (2 bytes)
Object_Length = 8 (1 byte)
Name_Length = 2 (1 byte)
Object Name (1 character + null byte) (2 bytes)
Pad (6 bytes)
Magic2 (1 byte).

Magic1 (1 byte)
HFlags = 001xxxxx (1 byte)
IFlags???? = 00x1xxxx (1 byte)
Object Type (2 bytes)
Object Length = 16 (1 byte)
Name Length = 2 (1 byte)
Object Name (1 character + null byte) (2 bytes)
Body Length = 1 (1 byte)
Body Data (1 byte)
Pad (4 bytes)
Magic2 (1 byte).

Consider the external form of a sample object with the HFlags byte set to 01100000 (so Object_Wid=01, N=1) and the Interior_flags byte set to 01110000 (so Interior_Wid=01, A=1, B=1, and ZZZ=00). All length fields are thus 16 bits wide, each of the Object_Name, Object_Body, and Object_Attributes elements is present, and the object interior is not compressed. Then the object might have the following byte layout:
 

In practice, this particular object could have been encoded with 8-bit-long fields.

The reason 1 byte of magic number at each end of an object suffices is because the byte before the Magic1 byte of an object should be the Magic2 byte of the previous object. That fact plus the 8-byte alignment constraint will make it possible to reliably locate the start of each undamaged object in the database even if portions of the database have been corrupted.

Extension mechanism: If additional database fields need to be added in subsequent revisions, they will be placed in the Object_Footer just above any pad bytes. The new fields will seem to older versions of the database reader to be pad bytes, and so will be silently skipped.

Compressed Objects

When the ZZZ bits are 000, the object has not been compressed and needs no special processing. When the ZZZ flag is nonzero, the on-disk object has been compressed. When the interior of a compressed object is needed, an extra processing step is added: after reading the object into memory in a db_external structure, the decompression algorithm is run on the interior of the object, resulting in a new db_external structure. The table of values for the ZZZ flag has been given earlier.
 

After decompression, the object would look as described earlier, but the value of ObjectLength in the decompressed object would be different than the value of ObjectLength in the compressed object.

Decompression of compressed objects will be automatic and will be performed only when needed. For example, objects will not be decompressed when scanning the database (e.g., to build the in-memory table of contents). Compression will only be performed by user command; it is envisioned that MGED will be given compress and decompress commands to allow the user to have complete control over the speed/space tradeoffs.

Compression support is mandatory for any implementation of a database reader library; it is optional for an implementation of a database writer library.

Point of Discussion????Proposal: The Object_Attributes and Object_Body should be separately compressed. This way, if only one or the other is needed, only that portion needs to be decompressed. Also, the ASCII strings of the attributes and the binary data of the body are likely to need different treatment for compression. Some compression algorithms can be given "hints" that they are compressing 16- or 32-bit-wide binary data, rather than streams of 8-bit characters.

????Statement about the compression algorithm being specified by ZZZ bits in AFlags for attributes and BFlags for body.???

In the compressed form, an extra field that has the uncompressed length is added.
 

II. Overall Database Organization

where the length of each object is potentially quite different.

Each (nonfree) object must have a name that is unique in a global name space. The object's name is its retrieval key. In its most basic form, the database can be thought of as a relational database (table) with a single key.

Traditionally, BRL-CAD databases with no commonly named objects can simply be concatenated. When this is done, it results in a second header in the middle of the file, which makes such concatenation easy to detect. (Note: If two or more objects have the same name, when the concatenated database is opened, there will be only one object with that name--the last one encountered.)

III. Details of the Object Body Element when Used for Holding BRL-CAD Nongeometric Objects

Combinations (Groups and Regions)

• oshader= Optical Shader name and parameters.
• material= Genuine Material name, a string key into an outboard application-specific material parameter database.
• rgb? giftmater? los? etc... (Point of discussion????)

Storing Binary Trees in Combinations

The 2-bit ``Wid'' flag specifies the size of the ``Matrix Count'', ``Leaf Count'', ``Expression Length'', and ``Expression Depth'' fields with the same semantics used in the ``Wid'' flags of HFlags, AFlags, and BFlags above. The ``Matrix Count'' field indicates the number of matrices in the ``Matrices'' section, the ``Leaf Count'' field indicates the number of leaves in the ``Leaves'' section, and the ``Expression Length'' indicates the sum of the number of operators and the number of operands in the ``Expression'' section. The ``Expression Depth'' field indicates the maximum size of a stack (in number of operands or subexpressions) required to parse the expression.

The ``Matrices'' section is a list of matrices, each recorded as 16 IEEE doubles in network order.

The ``Leaves'' section is a list of 2 * LeafCount members:
 

where ``name_i'' is the name of the ith leaf and ``mi_i'' is the index into the ``Matrices'' section for the corresponding matrix. To avoid having to store identity matrices, the ``mi_i'' value of 2^w - 1, where w is the value encoded by the ``Wid'' flag (See the ``Wid'' flags of HFlags, AFlags, and BFlags above.) (in other words, all bits of ``mi_i'' are set), is defined to indicate the identity matrix.

The ``Expression'' section records the tree in postfix (a.k.a., reverse Polish) notation using the following encoding:
 

Each time the ``operand'' token is popped from the stack, it will be interpreted as ``the next element in the `Leaves' section''.

An empty ``Expression'' section (which implies that``Expression Length'' and ``Expression Depth'' both equal 0) has the special interpretation that every operator is a union.

As an example, the combination with expression and matrices as follows:
 

could be written out as:
 

IV. Details of the Object Body Element when Used for Holding BRL-CAD Geometry

Ellipsoids

The A, B, and C vectors define a local coordinate system for the ellipsoid. The lengths of the vectors establish the three radii of the ellipsoid, each in the direction of its respective vector.

The Sphere

It is more storage-efficient, and less prone to tolerance errors, to store spheres explicitly represented as a center point V and a radius r. Each number is stored in 8 bytes as double-precision IEEE floating point, written in big-endian order, so the object body for this solid will require ((1 * 3) + 1) * 8 = 32 bytes. The layout of Body_Data for the sphere is
 

The possible drawback to this change is that the vectors A, B, and C traditionally stored for the sphere are an explicit local coordinate system. This fact is used to aim existing spherical light sources, as the center of the beam of light is focused down the solid's -Z axis, which is transformed into the desired aim direction either via rotating the A, B, and C vectors or by transforming the local coordinate system of the solid with the homogeneous transform matrices in the arcs of the model DAG. It is not clear how this functionality could be preserved, except perhaps by making sure that light sources were explicitly modeled as ellipsoids rather than as spheres (perhaps with equal-length vectors). This would be something that an automatic database converter could guess at by looking for combinations with material type light and a single member that is an ellipsoid, but manual repairs would probably still be necessary.

The Nonmanifold-Geometry Solid

Version

A version number of the on-disk format of the NMG.

Kind Count Array

An array of 26 counts. Each count represents the number of structures of a particular kind.

Model

Long containing DISK_MODEL_MAGIC, a Long Version (Always zero), serialized BU_LIST of regions.

NMG Region

Long DISK_REGION_MAGIC, serialized BU_LIST of regions, serialized pointer to model, serialized pointer to region attributes, serialized BU_LIST of shells.

NMG Region Attribute

Long DISK_REGION_A_MAGIC, serialized point of minimums of bounding box, serialized point of maximums of bounding box.

Shell

Long DISK_SHELL_MAGIC, serialized BU_LIST of shells that are in the same NMG region, serialized pointer to owning region, serialized pointer to shell attributes, serialized BU_LIST of face uses in this shell, serialized BU_LIST of loop uses in this shell (edge groups), serialized BU_LIST of edge uses (if shell has wires), serialized pointer to a single vertexuse (if shell only has one vertex).

Shell Attribute

Long DISK_SHELL_A_MAGIC, serialized point of minimums of bounding box, serialized point of maximums of bounding box.

Face Use

Long DISK_FACEUSE_MAGIC, serialized BU_LIST of faceuses (of which this is one) that are part of this shell, serialized pointer to the owning shell, serialized pointer to the face use mate of this faceuse, long orientation, serialized pointer to the face, serialized BU_LIST of loops in this faceuse.

Face

Long DISK_FACE_MAGIC, serialized BU_LIST of faces (of which this is one) that reference the same face geometry, serialized pointer to the owning faceuse, serialized pointer to the face geometry used, long flag describing if face normal is flipped.

Face Geometry(Plane)

Long DISK_FACE_G_PLANE_MAGIC, serialized BU_LIST of faces sharing this surface, serialized plane equation of this face (Normal and distance from origin to plane).

Face Geometry(SNURB)

Long DISK_FACE_G_SNURB_MAGIC, serialized BU_LIST of faces sharing this surface, long U dimension order, long V dimension order, long U dimension knot size, long V dimension knot size, U knots, V knots, long US size, long VS size, long number of control points, list of control points.

Point of discussion?????????Of which I don't understand *half* of the above sentence and I don't believe it is totally correct.

Point of discussion????Use of "use" in the following chapters. consistency in one word vs. two.

Loop Use

Long DISK_LOOPUSE_MAGIC, serialized BU_LIST of the loop uses that belong to the owning face, serialized poiter to faceuse or shell that owns the loopuse, serialize loop use mate pointer, long orientation flag, serialized pointer to loop, serialized BU_LIST of edge uses or *A* vertex pointer.

Loop

Long DISK_LOOP_MAGIC, serialize pointer to owning loop use, serialized pointer to loop geometry.

Loop Geometry

Long DISK_LOOP_G_MAGIC, serialized minimums of bounding box, serialized maximums of bounding box.

Edge Use

Long DISK_EDGEUSE_MAGIC, serialized BU_LIST of edge uses that make up this loop or wire edge, serialized pointer to loopuse/shell owner of this edge use, serialized pointer to edge use mate, serialized pointer to the radially adjacent face use(or zero for wire edges), serialized pointer to edge, long flag for orientation, serialized pointer to the first vertex use of this edge use in this orientation, serialized pointer to linear segment or curved segment.

Edge

Long DISK_EDGE_MAGIC, long flag for is this a real (modeled) edge or an artifact from tesselatio??????, serialized pointer to one use of this edge.

Edge Geometry(Linear)

Long DISK_EDGE_G_LSEG_MAGIC, serialized BU_LIST of edge uses on this line. Point (3tuple of doubles), direction (3tuple of doubles).

Edge Geometry(CNURB)

Long DISK_EDGE_G_CNURB_MAGIC, serialized list of edge uses on this curve, long curve order, long size of knot, ??? of knot(?s), long curve size, long point type, long list of control points.

Vertex Use

Long DISK_VERTEXUSE_MAGIC, serialized BU_LIST of vertex uses of which this is one (CTJ ERROR), serialized pointer to shell/loopuse/edgeuse owner of this verte us???, serialized pointer to the vertex, serialized pointer to the plane/cnurb.

Vertex Use Attribute(Planer)

Long DISK_VERTEXUSE_A_PLANE_MAGIC, Normal (3tuple of doubles) which should be a unit vector.

Vertex Use Attribute(CNURB)

Long DISK_VERTEXUSE_A_CNURB_MAGIC, parameter space 3 tuple of U, V, and W.

Vertex

Long DISK_VERTEX_MAGIC, serialized BU_LIST of vertex uses of this vertex, serialized pointer to the vertex geometry.

Vertex Geometry

Long DISK_VERTEX_G_MAGIC, point (3tuple of doubles)

Unused*4

There are four entries in the kind table that are not used??????.

Doubles Array

Unknown? Nothing?

The ARB8

In the v4 format, the ARB8 is stored as a base point V and seven vectors, making spatial translation computationally inexpensive. In the v5 format, the ARB8 will be stored as eight points in space to prevent values from mutating due to repeated vector addition and subtraction of V. The layout of Body_Data for the ARB8 is

The TOR

Halfspace Solid

VDOT(P,N) - d == 0
or
VDOT(P,S) - S[3] == 0

N[X]*x + N[Y]*y + N[Z]*z - d == 0
or
S[X]*x + S[Y]*y + S[Z]*z - S[3] == 0

The other geometric types

ARS,
POLYSOLID,
B-Spline Solid,
ARBN Solid,
PIPE/Wire Solid,
Particle Solid,
NMG Solid,
TGC Solid (includes REC),
Torus (TOR) Solid,
Grip Pseudo-Solid (Leaf) and Joint Pseudo-Solid,
Right Parabolic Cylinder (RPC),
Right Hyperbolic Cylinder (RHC),
Elliptical Paraboloid (EPA),
Elliptical Hyperboloid (EHY),
Elliptical Torus (ETO),
Extruded Bitmap (EBM) Solid,
Volumetric (VOL) Solid,
Height-field (HF) Solid,

V. A Proposal for Parametric Databases

These TCL variables can be set by prior code execution (e.g., from commands given in MGED or from commands placed on the RT command line or in an RT animation script), as well as by TCL code included in the Header object(s)'s object-body field. In order to prevent long dependency chains between objects from being formed, only substitution of existing variables can be performed when an object is read -- formulas and procedure calls will not be permitted at substitution time. As a result, all variables will have been given values before any objects are retrieved from the database.

If variables depend on the values of other variables, then the user must take into account the order of assignment, just as with other types of programs.

Those binary numeric fields in the object that are to be substituted will be filled with an IEEE Signaling NaN pattern, to distinguish it from a valid binary number. Each object will need to have an additional variable-length field that will be used to hold the replacement variable list. Two possible strategies:

• There are a large number of Signaling NaN patterns available; a convention can be established so that the low bits of the NaN can be used as a replacement variable index, designating whether the value of the first, second, third, etc., variable named in the replacement variable list should be used.
• The replacement variable list could be of the form

        field_number=variable_name,
        field_number=variable_name,...

In this proposal, two different interfaces will be required for reading objects from the database:

• Evaluated read -- transparently evaluate the object, substituting the numeric values for any variables so that the object can be operated on or drawn.
• Unevaluated read -- leave the variables themselves in the object so that applications may provide a means of modifying the parameterized representation of the object.

Some other function will be required to get and put the objects in an internal symbolic form. It might be wise to make this have semantics as close as possible to the form of Glenn Durfee's TCL MGED "db get" command. That is, the editable symbolic form should be an ASCII text string in a format suitable for further TCL processing. As get/put operations on the symbolic form will be quite rare relative to the operation to get the numeric form, the extra overhead of using an ASCII representation is negligible.

There would be a great consistency advantage to be gained if the symbolic substitutions could be handled by the same routines as the "db get" support. The "db get" routines are presently local to TCL MGED, but the "get" and "put" operations need to become standard function table interfaces to the g_xxx.c modules in LIBRT. This raises the related question of how bulky objects like NMGs, B-splines, and height fields should be represented in their ASCII forms.

String parameters, such as the optical shader parameter string, can be passed through the TCL interpreter if a left-square-bracket (''['') character is seen in the string. This would permit the normal TCL syntax to invoking the TCL interpreter to be used. In this example, the following two lines have the same effect:

        plastic shine=[$shine] diffuse=[dfunc($statevar)]
        [plastic shine=$shine diffuse=dfunc($statevar)]

Highly Interactive Coupling Between Variables and the MGED Display

The tree walker should keep an auxiliary table that is indexed by database variable name. For each database variable that has been seen while walking the tree, there will be a list of db_full_path structures for every solid dependent on that variable, and a flag variable indicating whether the presently loaded version of each solid is out of date with respect to the variables on which it depends. (What data structure to use for the many-to-many mapping of variables to full paths?) The tree walker will automatically associate a TCL hooked function with each TCL variable on this list. Whenever a new value is assigned to a TCL variable, the dependent solids will be marked as out of date, but no other action will be taken.

Application code (TCL code or C code) will be able to call a library routine to "flush" the modifications, that is, to re-process all out-of-date solids to bring their internal representations (whether wireframes on an mged screen or prepped solids for raytracing) into sync with the variables on which they depend. It is envisioned that there will a library routine (db_variable_flush) that the application can call, providing a pointer to an application-provided function that will be called once with each out-of-date full path. In the case of mged, after processing each batch of input commands and events and before updating the screen, db_variable_flush would be called with a handler that essentially reruns the mged "e" command for each stale full path, so that the vlist would be regenerated before the screen update. As long as the number and complexity of the solids to be regenerated per screen update are modest, this will be highly interactive.

The simplest version of a TCL command to implement a Tk scale widget that would have this auto-update property would look something like this:

        scale .sliders.f.kX -label "Change Variable ANTENNA_HEIGHT" \
                -variable antenna_height \
                -command "mged_variable_flush"

Requirements for the new Selector Node

This might be accomplished in several ways:

• Adopt something similar to the layers concept from traditional drafting packages. Each combination could be assigned to an arbitrary list of layers, and only regions belonging to layers that had been made active would be processed by db_walk_tree().
• Evaluate the value of an (optional) named TCL variable as a boolean. If the value is nonzero, then the combination is active; otherwise it is not. For more power, a TCL function string might be evaluated here, but that raises the possibility of potentially unresolvable dependency chains leading to endless recursion.
• Evaluate the value of a (mandatory) TCL variable, the value of which is an index that will be used to select one of N different members of the combination (departing arcs of the DAG).

Random Unresolved Questions

Make the rtgeom.h-object-to-TCL conversion routines another access method for geometric objects. Question: How to convert nurbs, NMGs, HFs, etc.?

Perhaps export the C symbol for the rt_structparse table that corresponds to the rtgeom.h structure.

It would be nice if there were some way of "mounting" or "including" a subtree from a second ".g" file into the context of the current ".g" file, even if only on a read-only basis. Issues: name conflicts, ambiguity of names in full-path specs, multiple dbip in play for a "single" ".g" file, back/up references from the included subtree.

VI. Community Feedback on the Proposal

David P. Kitzinger, ARA

From: "David P. Kitzinger" 
Subject: Re: Input Sought on V5 Database Format

A couple of thoughts on the database format. First, ARA would like some
resemblance of dynamically created geometry (geometry that gets 
introduced or turned on/off during an interrogation cycle).

While we've talked about being able to update the database and perform
incremental preps (which probably doesn't require database changes, just
new routines to accomplish the aforesaid), it may be attractive to
provide a mechanism whereby the client code can tell BRLCAD to ignore
or turn off a piece of geometry. This would require an extra bit
in the database for entities that BRLCAD code maintains.

Another perhaps minor feature that might be useful is the notion of 
database versions. Because a .g can be copied, the UNIX timestamp
is not adequate to know which version of a .g file is most up to date.
Also, if folks perform extra preprocessing on a .g file and save the
data offboard in another file, the possibility for out-of-sync problems
exist. It might be nice if the database could maintain a version number
field for the entire database, perhaps along with a field for the login
of the user making the last change. mged and/or libwdb routines would
then increment the version number whenever alterations to the .g file
occur, no matter how insignificant the change might be. mged could display
this info when it first brings up the file, and an access routine could
be provided to permit client code to check versions. This basically is
revision control, but unburdens client code from trying to manage the
same info off-board (since a modeler can always get into the .g and
bypass any extra layers an application might wish to maintain, there is
always risk when the application attempts to control this). Of course,
if a modeler goes outside of BRLCAD, like cat'ing .g files together instead
of using "concat", there may be problems but this should be rare.
Perhaps having the database maintain a checksum for the .g would also catch
even these problems.

What is really needed is a better method for interfacing to RCS, which can deal with branches off the main path of development, and can even perform merges between two branches. I don't know how well RCS would work on binary databases. Perhaps if we could supply RCS a BRL-CAD-specific item-by-item comparison function....?

I'm certainly more familiar with the BRLCAD interrogation routines than
actually constructing BRL-CAD models. Whenever certain operations
occur, old data in the .g file is marked ID_FREE and left in place.
Depending on the construction approach, this can leave rather large
pockets that make the file large and artificially jack-up memory usage
when interrogating. I solve this by converting to asc and then back to
.g file to eliminate these pockets. Is there an existing mged command
now that does basically the same thing?? Can the new database be designed
to minimize/utilize these holes and/or can you provide routines/mged 
commands to "compact" the database?? Since you are going to an IEEE
format g2asc will no longer be needed so my old approach will no longer
work.

• Create a solid S1 (S1 is added to end of DB, 1 granule). Put S1 in region R (R is added to end of DB, 2 granules).

        +----+----+----+
        | S1 |  R... R | End
        +----+----+----+

• Create solid S2 (S2 is added to end of DB, 1 granule). Add S2 to R (new version of R is added to end of DB, 3 granules, leaving 2 granule hole).

        +----+----+----+----+----+----+----+
        | S1 |  Hole   | S2 |  R........R  | End
        +----+----+----+----+----+----+----+

• Create solid S3 (placed in 1st granule of hole). Add S3 to R (new R added to end of DB, 4 granules, leaving 3 granule hole).

        +----+----+----+----+----+----+----+----+----+----+----+
        | S1 | S3 |Hole| S2 | Hole....Hole |  R..............R | End
        +----+----+----+----+----+----+----+----+----+----+----+

• etc.etc.

As for the second part of your suggestion, it would be very easy to add a command to MGED to compact out all the free granules. It could be implemented in two ways: in place, which would risk database damage if the system (or program) crashed while it was happening, and compaction by copying, which would risk running the disk out of space while operating, but would leave the original uncompacted file untouched in case of failure. I prefer #2. I propose the command name "compact".

Another question regards construction rules. mged allows me to construct
a region by combining solids, other regions, and even groups with
boolean operations. As far as I
can tell this all seems to work fine, I've rendered some examples of such
regions and they seemed correct, although warning
messages are occasionally issued. Is this supposed to work? Is this a valid
construction method? When I shoot a ray through a top level region,
are lower pieces (groups and regions) treated as an integral part of the
overall region (i.e. does the partition list reflect only the top level
region?). Can this be clarified in the database format document or
somewhere else? It obviously is a powerful method, so if you don't 
officially support some permutation of the above, would you consider it
for the next release?

Being able to boolean things from "upper level" combinations is also supported. In this case, a copy of the boolean operation is propagated downward to all affected regions, accumulating transformations as you would expect. This is especially nice for doing "cutaway views". Both of these things are features of the "new" tree walker in Release 4.

Keep up the good work,
                                           /|     /--\   /|
                                          / |    /   |  / |
David P. Kitzinger                       /__|   /___/  /__|
Staff Scientist                         /   |  /   |  /   |
                                       /    | /    | /    |
Applied Research Associates, Inc.        (505) 883-3636
4300 San Mateo Blvd. NE, Suite A-220     (505) 883-3673 FAX
Albuquerque, NM 87110                    kitzinger@ara.com

John Keyser, UNC

From: John Keyser 
Subject: Comments on database v5 proposal - handling transformations.
Date: Thu, 18 Jul 1996 11:20:15 -0400 (EDT)

        You spend some time in the version 5 proposal dealing with potential 
ways of handling the transformations for binary trees in the new database
format.  I thought of two other possibilities that might be possible, although
they certainly have their drawbacks.  For one, these methods might cause
too much havoc with the "cleanness" of the data structures.  Second, they
might pose problems for backward compatibility.  Also, they could cause the
tree to be larger than desired, but probably not by too much.  I am not
familiar with animation scripts so I cannot say how they would be affected.
        The first solution would be to create transformation _nodes_ that
are unary operators.  This would allow you to represent the tree similar
to the conceptual model of what is happening - a transformation node would
separate an object from the combination.  The in-memory model would be
exactly as desired.  This would mean having three types of nodes - primitive 
solids, combinations, and transformations.
        The second solution (and the one that seems better to me) would
be to have a transformation _primitive_ defined.  Thus, using the  
(A u B) - (C + D) example, a tree would look like:

                              -
                             / \
                            /   \
                           /     \
                          /       \
                         /         \
                        /           \
                       /             \
                      ?               ?
                     / \             / \
                    /   \           /   \
                   /     \         /     \
                  u      M1       +      M2
                 / \             / \
                /   \           /   \
               /     \         /     \
              ?       ?       ?       ?
             / \     / \     / \     / \
            /   \   /   \   /   \   /   \
           A    Ma B    Mb C    Mc D    Md
                         

Where the ? nodes could be any operation.  One advantage of this would
be that you could reference the same transformation matrix from several places
(thus making it more certain that you were applying a consistent transform
at several places in the tree).
        Both methods seem to handle "chains" of transformations (such as might 
occur when an arc is deleted) fine (transformations do not need to be 
combined).  Also the idea of a "selector node" could be used to allow a user 
to change translations easily.  Another big advantage would be that for
identity matrices, nothing would need to be stored - no need for tolerancing.

                                        - John Keyser
                                          keyser@cs.unc.edu

VII. Database library application programming interface (API)

The primary API for the database revolves around the routines rt_db_put_internal() and rt_db_get_internal(), plus the "internal" data structures vectored out from struct rt_db_internal: union tree for combinations, from "h/raytrace.h", and the family of struct rt_xxx_internal structures from "h/rtgeom.h".

The main issue for the database API becomes one of how a retrieved and "unwrapped" in-memory database object looks to an application. The most natural way would be to have a variable-length array of structures something like this:

        struct attributes  {
                char    *aname;
                char    type;
                long    len;
                genptr_t value;
        } attrib[];

Then, to retrieve a BRL-CAD object (in external form) from the database, one would merely call:

        db_get_external(ext, dp);
        db_unwrap_v5_external(atab, ext);
        id = db_get_integer_attribute( atab, "t" );
        buf = db_get_block_attribute( atab, "b" );

The main questions are:

• What is the runtime penalty for having to build up a "symbol table" of attribute names for each object as it's being pulled in off the disk, and then searching it with strcmp() calls for every retrieval?
• What is the disk storage penalty for storing frequently recurring attribute names on the disk using the same straightforward and general encoding used for all the other attributes?
• How much inefficiency (in terms of number of data copies) is engendered by having to marshal up lots of small, variable-length attribute name and value strings, to build the object interior, which is then (optionally) compressed and marshalled up with the variable-length name string and finally provided in external form? Would a kernel mbuf-like data structure help? Enough?

  VIII. Appendix: Earlier Proposals for Database Organization

$Header: /vld/mike/public_html/papers/brlcad5.0/RCS/newdb.html,v 1.70 2000/06/30 15:07:48 jra Exp $
Collected by Mike Muuss
E-mail comments to mailto:acst@arl.mil