Extrusion Edge Cases

From Web3D.org
Revision as of 08:39, 29 October 2015 by Sevaa (Talk | contribs)

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.

Problem issues

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 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" (open 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, suggested implicitly by the "coincident points have the same SCP" line in the spec

For Y, collinear spine segments are not a problem. Null segments (AKA conincident points), however, are.

For 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 Z calculation, both null and collinear spine segments warrant special treatment.

Coincident Spine Points

Conincident spine points are allowed under the spec. For those, the rules for generating Y are in conflict. First, the difference of the adjacent spine points might not be a null vector; the subtraction rule and the reuse/lookahead rule are in conflict here, and might provide different results. The standard doesn't specify which one takes precedence. If the reuse rule is only supposed to kick in if the subtraction rule returns a null vector, the standard might say so.

The spirit of the spec, however, might suggest that the applicability of the angle/endpoint rules for both Y and Z can be extended by replacing the notions of the next/previous point with next/previous distinct point.With this amendment, the reuse/look-ahead rule becomes unnecessary. However, this might throw off existing implementations. Again, some existing implementations might be non-compliant with the current spec as it is.


The case of three coincident spine points.


For point #1, the angle rule and the reuse rule produce the matching results for SCP Y - 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 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 suggested 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 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.

Collinear spines

If the spine is collinear (and thus allows for no SCP-Z calculation), the standard calls for generating the SCP in the following manner:

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

There are some problems with that algorithm.

1. If the vector in step A happens to be (0,-1,0), the rotation in step B is not unique.

2. If the spine goes: (0,0,0) - (0,1,0) - (0,0,0), it's collinear, but the standard doesn't specify what constitutes the "spine direction". Common sense suggests the first nonzero length spine segment, but the standard doesn't say so.

Also, it's worth noting that the popular implementations out there don't follow those rules.

Possible solutions

Resolved issues