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