Beyonds Four Sides: The need to address N Sided faces within Arbitrary Curve Networks

Background

The advantage of using surface design techniques based on arbitrary topology is that there are few constraints when it comes to how definition data is arranged. From a usability perspective, the design process is very swift and the user is not forced to plan out the definition framework in advance. However, one fundamental issue (stemms) is that most parametric surfaces appropriate for use in CAD systems are four sided and non-four sided faces can occur frequently around the ends of a hull form, in the bulbous bow, transom and around any detailed features or appendages which the user wishes to represent within the hull form. Consequently, as the user is not initially constrained from defining a network of curves which contain non-four sided faces the problem of generating a surface representation within these areas of the definition must be resolved by the software. This particular problem is not unique to tools which represent hull forms. It in fact one of the fundamental issues that must be resolved in any solid modelling tool.

There are several options open to the developer:

  • Avoid the issue by not interpreting faces with more than 4 sides. Faces with less than 4 sides can be represented by 4 sided patches with degenerate edges. Consequently, the user must avoid defining any faces with more than 4 sides which can be quite difficult to achieve. In fact, this particular approach is employed within the Lines/Pace application in Tribon M3. While it may initially seem as a short comming it is actually a well balanced compromise because this constraint make it easier to achieve a higher degree of fairness. It enforces a more regular arrangement of patches and control points which makes life much easier when it comes to removing surface distortions. However, the initial representation and changes are harder and suggest that user may want to use different hull design tools for concept, initial and production design stages.
  • The use of bounded planes may be used in the simple cases where n-sided faces occur in flat areas of the hull form such as around the parallel middle body. This is perhaps a sensible solution in this particular case but other design tools may not be able to interpret this information when the definition is shared between systems. Bounded planes are supported within the IGES file standard but only systems which support solid modelling information will be able to import these definition.

The ideal solution is to N-sided surfaces and they do exist. A significant amount of detailed research has been undertaken in this area considering the importance of solving this problem and a wide body of work exists [ref]. There are versions of control point (NURBS type), transfinite and subdivision surfaces that can be used for this purpose. The Fairway system produced by SARC is one of the few hull design tools to support the use of N-Sided surfaces, using the Coons-Gregory patch [ref]. Another system of note is FreeDimension [ref] which uses a least squares approach to generate surface representations capable of C0, C1 and C2 continuty. The surfaces used by both of these systems have been implemented with X-Topology Surfaces to understand how they perform when compared to conventional four sided surfaces. On the bases of this implementation the following points are highlighted.

  • Speed: In general, the n-sided surfaces require more processing time than the non-four sided surfaces. This is often because, in the case of the two techniques mentioned above, intermediate surfaces are generated for each side and then combined together to produce a final shape. In comparison, a traditional Coon patch requires three "surfaces", (Blend surface in the U parametric direction, Blend surface in the V parametric direction and a surface to blend twist).
  • Data Transfering: At present, the only standards for transfering surface geometry between CAD systems exist for NURBS (4-sided, of course) let alone any non four sided techniques. Therefore any hull design system using non four sided surfaces must convert them to at least a four sided representation to allow the data to be transfered. Consequently, the transferred surface may not be the same as the user originally generated. Alternatively, the surface may be exported using facetised data which is not necessarily desirable.
  • Curvature: The mathematics behind N-sided surfaces is structured differently to conventional four sided surfaces. The techniques mentioned above, and implemented within X-Topology surfaces, all have a parameter assigned to each edge, i.e six sides mean six parameters. Therefore the process of calculating curvatures (mean, gaussian, from which the surface quality may be judge becomes much harder. The curvature calculations are generically based on bi-variate surfaces, i.e two parameters, and while algorithms for obtaining curvature may exist the author has yet to source them. It must also be kept in mind that these surfaces are more expensive to calculate than the four sided equivalent which may mean that a curvature anaylysis across a hull surface may make the design tool non interactive, i.e. take too long to assess quality between interactive surface changes.
  • Quality: While the negatives have been highlighted so far, the quality of the shaped produced when filling a face with five sides or greater is far superior than any other of the technique discussed here. This is perhaps a logical conclusion because in essence these surfaces are the "right tool for the job" and it is primarily in the practical considerations where these surfaces fall down.

A few other observations from implementing these surfaces are:

  • N-Sided surfaces prefer the boundary shape to be regular and wherever possible convex, otherwise significant distortions can result
  • It is better to use a four side patch to fill a four sided face than to use a n-sided technique. This may make the software implementation appear less generic but in most cases the faces should be four sided and four sided surface patches are more efficient in terms of processing that other versions. The Coons-Gregory patch, for example, has cases for 3, 4 and n-sided arrangements.
  • The surfaces used in FreeDimension didn't appear to perform as well as the Coons-Gregory patch. This may have been an implementation problem but there appeared to be significant degeneracies at the corners of the patch.

On the basis of evaluating these surfaces, one can conclude that they are probably best used during the early phases of a design project as it at that time when you want to use the least patches and definition to get a representative shape for analysis. Therefore, there is a greater chance of non-four sided faces occuring in a hull definition. By allowing use of these patches at this stage the shape of the design can be easily established. Once a design has been established it can be converted to convention four sided patches in the knowledge that there will not be too many significant changes to the hull and hence more time can be invested in the definition and quality of the hull surface for subsequent phases.

Subdividing 5+-Sided Faces with Four Sided Surface Patches

It is difficult to justify the use of n-sided patches unless you are interested in rapid design, surface quality and there is no requirement to transfer an accurate faired surface definition to another design system. However, when there is a practical need to maintain four sided patches throughout, techniques must be found generate the shape bounded by an n-sided face from four sided surface patches. A practical solution is to use a subdivision technique which divides the n sided face into three or four sided sub-faces withiin which four sided surface patch may be generated.

Another element that needs considering is that in a lot of cases n-sided faces may be formed at a result of T-Junctions. T-Junctions occur when a logical curve boundary is subdivided to allow a different number of faces on each side of the curve. Consequently, two adjacent edges bounding a face may be part of the same curve and junction at the vertex between the two edges is geometrically continuous. In these cases it may be possibe to locally join the edges together to reduce the number of edges bounding a face. However, joining of edges may not be appropriate if the chosen surface patch has a fixed interpolation scheme, such as a cubic bezier patch. In these cases, joining edges together may cause undesirable gaps between patches which a phenomenon to avoided.

There are two approaches which have been sucessfully used to address n-sided faces with four sided patches:

Regular Subdivision

The first approach looks very similar to the arrangement used in Catmull-Clark subdivision surfaces [ref] will be known as Regular Subdivision. This technique was employed by Chiyokura [ref] in one of the first pratical solid modelling system, DesignBASE, although a more detailed explaination may be found in more detail in [Ref] particularly in regards to the use of NURBS surfaces. The approach is very simple. An n-sided face is subdivided into n four sided patches by connecting the middle of each edge into a common central vertex. These additional edges may be formed using bezier curves so that the tangent conditions where the edges are subdivided and the continuity condition at the central vertex is maintained. Much like the n-sided patches, this approach functions well when the originating face is regular and convex.

Decomposition

A second approach which will be know as Decomposion after the early horizontal decomposition techniques which were used turn arbitrary 2D n-sided polygons into 3 or four sided polygon faces can be sucessfully used cases where the n-sided face to be filled is not regular or where T-Junctions are present but gaps may result if edges on the logical boundaries of a face were joined. It is best used when there are three or four distinct corners to the face, i.e. it is roughly triangular or rectangular in shape. This approach is mentioned by Chiyokura [ref] but at the time of writing had not been investigated. That said, this approach is used by the NAPA system to address the n-sided problem. Despite these references, the technique has never been publically documented and seems to remain with the realms of software IPR and therefore several approaches may exist.

The Decomposition approach functions by subdividing using a series of planar cuts through vertices resulting in a number of four sided sub-faces with potentially three sided sub-faces at each end of the sequence. The planar cut direction must be determined by analysing the orientation of the original face but may be simplified by restricting the selection to planes based on the princple axis direction. At each cut, a hooking curve, (name attributed to [ref]), curve must be generated. This curve is cubic and hence arises the most difficult aspect of this technique which is identifying the tangent derivative at each end of the curve. At each end of the curve, the technique must take account of whether the cut is being made between edges on a logical curve boundary or at the junction between two logical curve boundaries. The derivatives of the surrounding edges are assessed, (in X-Topology surfaces, by a somewhat hyristic method maybe - a sort of elliptical interpolation, assumes a eliptical surface tangent field at each vertex inspirect by the distribution of principle curvatures), to produce the final geometry of the hooking curves.

In X-Topology surfaces, a preprocessing stage evaluates the shape of each non-four sided face and determines whether to use Regular Subdivision or Decomposition approaches. At present steps are also being taken to allow the user to manually override the selected techique at an individual face level although at present they can force a particular technique for all affected faces.

 

Experience

The approaches discussed can be demonstrated to function effectively in filling a n-sided face with surfaces to the G1 continuity level. However, because of the abitrary nature of the definition there are often times when none of the technques will produce an entirely satifactory result and that includes the n-sided surfaces too. Irregularity in the shape of the face is often the cause, particularly in cases where the face has significant curvature, for example at the top of the bulb.

On this basis it can be concluded that these techniques are very effective at n-sided faces using both four sides and n-sides faces but that in cases of high curvature or irregular boundary shape the resulting shape may not be a asthetically pleasing as the designer desires. In this respect, these techniques can be said to produce an estimate of the the shape across a n-sided face but that to get the exact shape it may be necessary to add further definition curves to refine the definition using more four sided faces.

 

 

 

Parametric curves are defined by a single parameter defined along the length of the curve. The curve has two ends (unless it is closed). Parametric surfaces add an extra dimension to a curve and therefore, in their simplest form, have two parameters and four side. i.e. they are bi-parametric. (Other types of surfaces do exist but at this point we will restrict the conversation to surface in paractical use within CAD systems).

A method for filling n-sided holes in a surface, Savva, A.; Clapworthy, G.J. Computer Graphics International, 1998. Proceedings Volume , Issue , 22-26 Jun 1998 Page(s): 578 - 582

A COMPLETE ALGORITHM FOR REAL-TIME SPLINE-BASED CHARACTER ANIMATION, Martin D. Hash, Hash, Inc. Vancouver, Washington . (http://www.ibiblio.org/e-notes/Hash/Hash.htm).