Extrusion Edge Cases

From Web3D.org
Revision as of 17:26, 29 October 2015 by Sevaa (Talk | contribs) (Proposed rule amendment)

Jump to: navigation, search

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 algorithm for generating the spine-aligned cross section plane (SCP) is ambiguous, hard to follow, sometimes ill-defined.

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 precedence as suggested by the standard:

- subtracting the next spine point from the previous one, let's call it "the angle rule" (closed spines are treated as cyclical)
- subtracting the next spine point from the current one (first point in an open spine)
- subtracting the current spine point from the previous one, let's call those two together "the endpoint rules" (last point in an open spine)
- using the spine direction, in case of a fully collinear spine (the notion of "spine direction" is not defined)
- 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. Null segments (AKA coincident points), however, are.

For SCP Z, there are the following rules, in the suggested order of preference:

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

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

Proposed rule amendment

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

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 are in conflict here, and might provide different results (see the example below, for point #3 in the example). 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.

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 suggested 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="-1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 2 0 0" crossSection="-1 0 1 1 1 0" scale="1 1 1 1 1 1 2 2 3 3 3 3"/>

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

X3DOM, Xj3D and InstantReality all produce extremely bizarre 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 Template:Overline:(0,1,0) to the said direction vector is calculated
- This rotation is applied to vectors (1,0,0) and {{Overline|(0,0,1)}, and those are the X and Z axes of the SCP.

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

Discounting that, there are 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 1 1 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 1 1 1 0 -1 0"/>

</Shape>

It looks three different ways under X3DOM, Xj3D, and InstantReality.


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 the first nonzero length spine segment, but the standard 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?


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"/>

Under Xj3D and X3DOM is doesn't appear at all. Under InstantReality, it appears, but the inner fold isn't there.


References

Resources