Revision Notes
| revision 12: | Moved Current issues section down. |
| revision 11: | All lines in the file that were greater than 80 columns were re- formatted to fit in 80 columns. This re-formatting is NOT reflected in the revision numbers at the beginning of each line. All references to NOWIND (other than this one) were removed. Any first-person references in this revision came from Travis Cobbs. |
| revision 10: | All lines that are indicated as being revision 10 are actually from revisions 0 through 10. Given the nearly 3 years between revision 10 and revision 11, I felt that it was easier to read this way. |
Current issues
Purpose
Establish a standard for backface-culling (ie, clipping) processing in LDraw-compatible rendering programs. This standard will include language extensions, definitions and expected processing effects.
In this document, this standard will be called the BFC extension.
The standard must allow cross-compatible DAT files. That is, LDraw- compatible rendering programs must render clipping-enabled DAT files correctly, and renderers which include the BFC extensions must render non- clippable DAT files correctly.
To make this standard useful and effective, the LDraw parts library must be updated to follow the new standard. Since it would be difficult to rewrite the entire library in one update, the standard will allow for a mix of extended and unextended files in one rendering.
Definitions
Certified. A DAT file is certified if it complies with the specifications in this document, includes a 0 BFC statement before the first operational command, and does not contain a no 0 BFC NOCERTIFY statement.
Clipping. In this document, the term clipping refers to the process of performing back-face culling. It should be noted that clipping has other meanings in other graphics contexts.
Invert. Turning a subfile inside out, usually performed on geometric primitives. When backface culling is used, inversion is needed, or interior surfaces will never be rendered. Because polygons are one-sided, interior primitives need to have their surfaces face inward, rather than outward.
Operational Command-Line. Any statement in a DAT file with linetype 1 through 5. In other words, the Subfile, Line, Triangle, Quad, and Conditional Line statements.
Part. A DAT file which represents a complete real-world building element. These files are stored in the ldraw\parts\ directory.
Polygon. A 2D surface created by LDraw's linetype 3 (triangle) or 4 (quadrilateral) command.
Primitive. A DAT file, typically small, which models a geometric shape or a standard attribute of building elements, such as studs or the cross-axle shape. These files are kept in ldraw\p\. In other graphics contexts, the term primitive refers to the basic geometric shapes provided by the rendering environment.
Subfile. A DAT file referenced from another file, via a linetype 1 command. Or any file which is lower in the file-reference tree than the current file. Or any file which is the subfile of the current file (or thus of any of its subfiles).
Subpart. A DAT file which is only a portion of a complete element. Does not necessarily correspond to a discrete portion of a real-world building element. These files are kept in the ldraw\parts\s\ directory.
Superfile. The file which referenced the current file. More generally, any file which is higher in the current file-reference branch than the current file.
Winding. This is the order vertices are specified in a polygon command. The order by be either clockwise or counter-clockwise (AKA anti-clockwise), and is based on viewing the polygon from its front side.
Clockwise winding (vertices numbered 0 through 3):
0 -> 1 ^ | | v 3 <- 2
Counter-clockwise winding:
0 <- 3 | ^ v | 1 -> 2
Language Extension Functionality
The BFC language extension allows DAT files to specify and control the following conditions:
Compliance. DAT files which follow the BFC extension must be clearly and unambiguously marked. It is also useful to allow non-compliant files to be marked as well. Having the compliancy stated plainly simplifies the task of the rendering program, and makes it easier for humans to read files later.
Control of the compliance/non-compliance state will only affect the current file. Subfiles will be affected indirectly, because it is not possible to clip subfiles of non-BFC files, but the compliancy of the subfiles will not be affected. That is, it is not possible to clip a BFC subfile when it is referenced by a non-BFC superfile, but the same BFC subfile may be clipped when referenced from a BFC superfile.
Winding. It must be possible for a file to specify the winding order of the polygon commands in that file, clockwise, counterclockwise, or unknown. Allowing the winding to be set at the file level is primarily a convenience for file authors. Setting winding to unknown is one way to prevent specific polygons from being clipped.
Changing the winding setting will only affect the current file. It will not alter the winding for super- or sub-files, and it will not modify the clipping for subfiles.
Clipping. It must be possible to enable and disable clipping during the processing of a file. But even when clipping is currently enabled, it may not be possible to actually clip on polygons. Polygons can be tested for clipping only when the following conditions apply: - All superfiles (in the current reference branch) are certified. - The current file is certified. - No superfile has disabled clipping prior to referencing this subfile. Unless all of these conditions are met at the time a subfile is rendered, no clipping is possible.
If the clipping state is modified, it affects all lines following the CLIP/NOCLIP statement, until the end of the current file or another CLIP/NOCLIP statement is encountered. When subfiles are referenced, they will receive a flag indicating the accumulated clipping state, but there is no sense of a global clipping mode.
Inversion. Sometimes, it is desireable to reverse the surfaces of a subfile; to turn the subfile 'inside out'.
One common example of inversion is the cylinder primitive. Cylinder primitives are designed so the surfaces face outward from the center. In 3D tubes, a pair of cylinder primitives are used to model the tube; one outer cylinder is oriented normally, and the inside cylinder, scaled slightly smaller, is required to face inward. This is accomplished by flagging the inner cylinder as being inverted.
Inversion accumulates down the reference branch. If the current file is being rendered inverted, then any subfiles of the current file are also rendered as inverted.
Inversion is a boolean operation--inverting a file that is already inverted will give the file the normal orientation. So if the current file is inverted, and a subfile is flagged as inverted, the subfile will be rendered with normal orientation, that is, right-side-out.
As a practical matter, rendering engines can accomplish inversion simply by switching the order of winding -- treat CCW files as as CW, and vice versa. This must happen in conjunction with the other settings, of course.
Language extensions
There is a single meta-statement in the BFC language extension, the 0 BFC statement. The statement includes options to specify BFC-related operations.
Syntax:
0 BFC [CERTIFY|NOCERTIFY] [CLIP|NOCLIP] [CW|CCW] [INVERTNEXT]
Only one option in each pair of brackets [ ] may be specified in a single BFC statement, any number of the options may be specified in one statement, and the options may be specified in any order on the statement.
The BFC meta-statement (along with all of its options) is case-sensitive, and must always be in all caps.
The BFC meta-statement shall ignore repeating whitespace, and accept any number of spaces or tabs as equivalent to a single space.
All BFC commands that act on succeeding lines in the file shall ignore empty lines.
In order for a file to be processed with back-face culling, there must be at least one 0 BFC meta-statement before the first operational command line. If there is no such 0 BFC statement in the file, BFC processing will be disabled for that file.
CERTIFY
This tag indicates the DAT file is compatible with the backface-culling extension. Every DAT file must be clearly labeled if it is compliant. One way to accomplish is to place 0 BFC CERTIFY at the beginning of the file, before the first operational command-line.
A second way to specify a file as compliant is to use any option, except for the NOCERTIFY option, on a 0 BFC meta-statement, before the first operational command-line. This is an acceptable alternative, but the 0 BFC CERTIFY method is recommended and prefered.
Files in the LDraw.org Parts Library, if they are BFC compliant, are required to have an explicit 0 BFC CERTIFY line in their header.
If a file has no 0 BFC statement at the beginning, then BFC processing will be disabled for that file, and any files referenced from that file.
NOCERTIFY
This BFC tag specifies that the file containing the tag is not compliant with the BFC specification--the polygons are not wound correctly, or the subfile references are not properly inverted. Hopefully, this tag will appear rarely. If the NOCERTIFY option is used, it must appear before any operational line-commands, and no other BFC tags may be specified on the same line. Any other BFC statements in the same file will be ignored.
CLIP
This option sets the clip-mode to enabled. This allows clipping, if all other conditions for clipping are met.
NOCLIP
This option sets the clip-mode to disabled. Any subfiles referenced with clip-mode disabled will not be eligible for clipping.
There may be any number of changes to the clip-state in a file, although it is recommended that such changes be kept to a minimum.
If neither the CLIP nor NOCLIP option is specified in a file's leading 0 BFC statement, then that file's local clip-state is initially set to enabled (CLIP).
CW
This option sets polygon winding to clockwise.
CCW
This option sets polygon winding to counter-clockwise.
There may be any number of changes to the winding direction in a file, although it is recommended that changes to winding be kept to a minimum.
If no winding tag is specified for a file, the local winding state will be defaulted to counter-clockwise (CCW).
INVERTNEXT
This option inverts a subfile. It may only be used immediately before a subfile command line (intervening blank lines are allowed), and it only influences the immediately following subfile command.
Example:
0 BFC INVERTNEXT 1 16 0 0 0 1 0 0 0 1 0 0 0 1 somefile.dat 1 16 0 0 0 1 0 0 0 1 0 0 0 1 another.dat
In this example, somefile.dat would be rendered as inverted. Another.dat would not be inverted.
For further information, see "Inversion" in the Language Extension Functionality section.
Rendering Engine Guidelines
This section gives some suggestions for the design of rendering programs, in order to achieve correct renderings. Any program may violate these guidelines, if there is another way to achieve a valid rendering.
Matrix Reversals. Rendering engines will need to correct for orientation matrices which inadvertently or deliberately reverse a subfile.
Normal transformation:
1 16 0 0 0 1 0 0 0 1 0 0 0 1 somefile.dat'Reversed' transformation:
1 16 0 0 0 1 0 0 0 -1 0 0 0 1 somefile.dat
If the rendering engine does not detect and adjust for reversed matrices, the winding of all polygons in the subfile will be switched, causing the subfile to be rendered incorrectly.
The typical method of determining that an orientation matrix is reversed is to calculate the determinant of the matrix. If the determinant is negative, then the matrix has been reversed.
The typical way to adjust for matrix reversals is to switch the expected winding of the polygon vertices. That is, if the DAT specifies the winding as CW, and the orientation matrix is reversed, the rendering program would proceed as if the winding is CCW.
Inverted Subfiles. Generally, it is not possible to determine that a subfile reference is inverted or normal (which is the reason for the 0 BFC INVERTNEXT meta-statement). In particular, the rendering engine should *not* use the determinant of the orientation matrix to determine if the subfile is intended to be inverted (see 'Matrix Reversals', above).
One important special case is this: part files are never inverted. Parts are complex files which would be essentially useless if they were inverted. Assuming part files are never inverted allows the rendering engine to apply BFC-processing on certified parts, even if the calling files (i.e., the main model file(s)) aren't certified.
No assumptions can be made about models which make direct use of primitives or polygon commands, so a rendering engine should not simply treat uncertified model files as certified.
Clipping State. The rendering engine can default to either allow or disable clipping at the start of processing. Presumably, the user will be given the ability to control this state.
Degenerate Matrices. Some orientation matrices do not allow calculation of a determinate. This calculation is central to BFC processing. If an orientation matrix for a subfile is degenerate, then clipping will not be possible for that subfile (or its subfiles).
Parts Library Guidelines
The LDraw Parts Library includes all parts, primitives, and subparts distributed with LDraw or in an ldraw.org parts update.
New parts will not be required to be compliant with this extension. They will be required to carry a 0 BFC tag, indicating either compliance or non-compliance.
New primitives will be required to be certified before being accepted for release.
It is desirable for all files to use the same winding. When possible, files should use counter-clockwise winding. The actual winding for any part is left to the file author. Primitives should always use CCW winding.
Primitives should generally be written so that polygons face outward, or upward. Exceptions are allowed for polygons which model inward- or downward-facing surfaces.
As noted in the Language extensions section, all BFC compliant files in the parts library will have an explicit 0 BFC CERTIFY line in their header.
Rendering Processing
This section presents a possible model for writing the core processing loop in an LDraw/BFC rendering program. BFC-relevant logic is included, as much other logic (as possible) is excluded. It should not be assumed that this pseudo-code represents the most effecient way to implement BFC.
The function BFC() returns a boolean value, indicating whether a polygon should be rendered or culled. As the nature of this routine does not impact the BFC standard, the logic for BFC() is not included in the following pseudo-code. There is information about BFC processing available from many locations, including http://www.lugnet.com/cad/dev/.
Recursive Procedure RenderFile
Parameters:
ModelFile string // File to render
AccumClip boolean // global clipping value yes/no
AccumInvert boolean // current inversion normal/inverted
AccumTransformMatrix matrix // current transformation
Colour integer // current colour
Declare
LocalClip boolean Initial TRUE
Winding bivalue(CCW, CW) Initial CCW
Certified trivalue(TRUE, FALSE, UNKNOWN) Initial UNKNOWN
InvertNext boolean Initial FALSE
Command DATCommandLine // Structure containing parameters from a single
// DAT command-line.
OpenFile(ModelFile)
Do Until EOF(ModelFile)
Get Next Command
If Command.Colour = 16 Then
Command.Colour = Colour
ElseIf Command.Colour = 24 Then
Command.Colour = EdgeColour(Colour)
End If
Case Command.LineType
BFC
If Certified is UNKNOWN and no Option in Command is NOCERTIFY Then
Certified = TRUE
End If
Do for each Option in Command
Case Option
CERTIFY
Assert Certified != FALSE
// Triggers error if file has been NOCERTIFY'ed
Certified = TRUE
NOCERTIFY
Assert Certified != TRUE
// Triggers error if file has been CERTIFY'ed
Certified = FALSE
CLIP: LocalClip = TRUE
NOCLIP: LocalClip = FALSE
CCW
If AccumInvert Then
Winding = CW
Else
Winding = CCW
CW
If AccumInvert Then
Winding = CCW
Else
Winding = CW
INVERTNEXT
InvertNext = TRUE
End Case
End Do
SUBFILE
If Certified is UNKNOWN Then
Certified = FALSE
Case Certified
TRUE
RenderFile Command.Subfile,
(AccumClip and LocalClip),
(AccumInvert xor InvertNext),
Command.TransformMatrix * AccumTransformMatrix,
Command.Colour
FALSE, UNKNOWN
RenderFile Command.Subfile,
FALSE,
(AccumInvert xor InvertNext),
Command.TransformMatrix * AccumTransformMatrix,
Command.Colour
LINE, CONDITIONAL_LINE
If Certified is UNKNOWN Then
Certified = FALSE
Deal with primitive command
TRIANGLE, QUAD
If Certified is UNKNOWN Then
Certified = FALSE
End If
If AccumClip and LocalClip And (Certified is TRUE) Then
If BFC(Command, AccumTransformMatrix, Winding) Then
Render Command
Else
Don't render Command
Else
Render Command
End If
End Case
If Command.LineType != BFC Then
InvertNext = FALSE
ElseIf No Option in Command is INVERTNEXT Then
InvertNext = FALSE
End If
Loop
End Procedure
Guidelines for Part and Primitives authors
(Section to be developed)