Difference between revisions of "Extrusion Edge Cases"

Revision as of 15:04, 30 October 2015

The Extrusion node specification has ambiguities [1]

This wiki page supports discussion on the x3d-public mailing list regarding Extrusion specification edge cases that make consistent modeling difficult.

The Existing Spec

The key algorithm for the Extrusion node deals with calculation of the spine-aligned cross section plane (SCP) for every point of the spine. The algorithm boils down to determining two vectors for every spine point - Y and Z. X is then calculated by cross product of those two.

For SCP Y, there are the following rules, in order of appearance in the spec:

- subtracting the next spine point from the previous one, let's call it "the angle rule" (closed spines are treated as cyclic)
- for the first point in an open spine, subtracting the next spine point from the current one
- for the last point in an open spine, subtracting the current spine point from the previous one, let's call those two together "the endpoint rules"
- for entirely collinear spine - using the spine direction, let's call it "the rotation rule"
- reuse and look-ahead within the point cluster, suggested implicitly by the "coincident points have the same SCP" line in the spec

For SCP Y, collinear spine segments are not a problem, the basic angle rule works for those. Null segments (AKA coincident points), however, are.

For SCP Z, there are the following rules, in the same order:

- cross product of the two adjacent spine segments, let's call it "the angle rule"
- if available, reuse of the previous Z
- if not, look-ahead to the first defined Z
- for entirely collinear splines, the Z axis of the coordinate system, rotated, AKA "the rotation rule"

For SCP Z calculation, both null and collinear spine segments warrant special treatment.

Proposed Amendment for the Angle/Endpoint Rules

The spec does mention the desire that the SCP Y approximate the tangent to the spine. In spirit of that, we might extend the angle/endpoint rules for both Y and Z by replacing the notions of the next/previous point with next/previous distinct point. With this amendment in place, the reuse/look-ahead rule for Y becomes unnecessary.

For spines with all distinct points, this rule extension will produce no difference in tesselation. As for the geometries with matching points, their treatment is wildly inconsistent under existing implementations as it is, so the harm will be minimal.

See the example below for the effect of this rule.

Problems with the Spec

Coincident Spine Points and Y

Coincident spine points are allowed under the spec. For those, the rules for generating Y are in conflict. The difference of the adjacent spine points might not be a null vector; the angle rule and the reuse/look-ahead rule might provide different results (see the example below, point #3). The standard doesn't specify which rule takes precedence. If the reuse rule is only supposed to kick in if the subtraction rule returns a null vector, the standard might as well say so.

Example

The case of three coincident spine points. We have a cluster of three coincident points in the middle. Let's consider the generation of the CSP Y for the middle points of this spine.

File:Threecoin.jpg

For point #1, the angle rule produces the vector (01) (in red).

For point #2, the angle rule produces a null Y. The reuse rule suggests the vector (01) (in red). The proposed extended angle rule, on the other hand, would produce Y as the vector (04) (in green).

For point #3, the angle rule would produce (34) (in yellow), but the reuse rule would produce (01) (red). This is a case of two rules producing valid but different results. That's why some kind of clarification of rule precedence in the spec would be necessary. The same unresolved contradiction in rules would arise even in case of two conincident points in the middle of a spine.

The extended angle rule would still produce (04) (green) for point # 3.

It's worth noting that for a spine like this, none of the existing rules for Z would produce a nonnull SCP Z for any of the points. The extended angle rule, however, would; the Z would be produced as (10)×(34)

A similar example can be drawn up for an open spine with two conincident spine points in the beginning or in the end.

The following geometry implements the example:

<Extrusion spine="-5 0 0 0 0 0 4 4 0 4 4 0 4 4 0 8 0 0" crossSection="-1 0 0 1 1 0 -1 0" scale="1 1 1 1 1 1 2 2 3 3 3 3"/>

The first spine point at (-5,0,0) was added to give it a valid SCP Z.

X3DOM, Xj3D and InstantReality all produce different shapes for such a geometry.

Rules for Collinear Spines

If the spine is entirely collinear (and thus doesn't allow for SCP Z calculation by the angle rule), the standard calls for generating the SCP in the following manner ("the rotation rule"):

- The direction of the spine is determined (as a unit vector)
- The rotation that takes the vector (0,1,0) to the said direction vector is calculated
- This rotation is applied to vectors (1,0,0) and (0,0,1), and those are the X and Z axes of the SCP.

X3DOM implements the rotation rule in a weird way. Under X3DOM, an extrusion in X or Z direction looks completely flat.

Discounting that, there are still some problems with the rule.

Straight spine in -Y direction

If the vector in the 1st step happens to be (0,-1,0), the rotation in the 2nd step is not unique. X3DOM, InstantReality, and Xj3D implement this case in three different ways. Consider the following scene:

<Shape> <Appearance><Material diffuseColor="0 0.5 0.5"/></Appearance> <Extrusion spine="0 0 0 0 1 0" solid="false" crossSection="-1 0 0 2 1 0 -1 0"/> </Shape>

<Shape> <Appearance><Material diffuseColor="0 0.5 0.5"/></Appearance> <Extrusion spine="3 1 0 3 0 0" solid="false" crossSection="-1 0 0 2 1 0 -1 0"/> </Shape>

It looks one way under X3DOM and InstantReality, another way under Xj3D.

Public Example

The Harrier model in the Savage model archive actually has extrusions in the -Y direction. Both wings of the airplane (node DEFs Left_Wing and Right_Wing) are implemented that way. Under X3DOM and Xj3D, the wings are misrendered. From the look of the model, it's obvious that the author expected the SCP to be spanned by (-1,0,0) and (0,0,1). InstantReality displays this model as expected, at least the wings are not backwards, like they are under X3DOM.

Spine with ambiguous direction

The spec doesn't specify what constitutes the "spine direction". It refers to to "the vector formed by the spine points", but depending on the choice of points, it might be a different vector (up to the sign), or even a null one. Common sense suggests using a nonnull spine segment, but the spec doesn't say so. And it seems like the implementors use, instead, the first and the last point of the spine, which is simpler, but open to errors. If the spine goes: (0,0,0) - (0,1,0) - (0,0,0), it's collinear, but what is its direction?

Floating Point Rounding

The spec calls for conditionals based upon floating point arithmetic results, specifically, the determination of collinearity. Floating point calculations being inherently imprecise, this is a huge can of worms. Details to follow.

Determination of point coincidence, however, is a safe operation, as long as spine coordinates were hand-written and not tool-generated.

Example

Consider the following geometry:

<Extrusion spine="0 0 0 0 1 0 0 0 0" solid="false" scale="1 1 1.2 1.2 1.4 1.4" beginCap="false" endCap="false"/>

It's supposed to represent two square frusta, where the bottom base of the smaller one is glued to the top base of the larger one.

Under X3DOM, it appears entirely flat. Under InstantReality, it appears, but one frustum is visible while the other is not. Under Xj3D, it doesn't appear at all.

References

Resources