Home > User Guide > Display and User Input > Faceting

The Faceting Algorithm

When the api_facet_unfaceted_entities function is called with a pointer to the entity list, the process that the Faceter follows can be divided into four general phases: edge discretization, grid spacing determination, face subdivision, and triangulation. These general phases are implemented in the faceting steps described in this section. The following assumptions are made in the description of the faceting algorithm steps:

Note:  Refinements attached to a face take precedence over the refinements attached to their owning body. A common difficulty is sometimes encountered when changing a body's refinement may have no effect on one or more faces; those faces probably have refinements of their own that either need to be updated or removed.

The faceter carries out the following operations:

  1. A working face is created for each ACIS face.
  2. A working edge is created for each ACIS edge. The working edge class contains the normal deviation, surface tolerance, and maximum edge length refinements. A working edge gets the lower of the two values from two adjacent faces.
  3. Each working edge is discretized, or subdivided, using the three refinements in step 2. A list of points for each working edge is created. Spline edges are recursively subdivided until all the refinements are satisfied. When there are adjacent edges, the last point from the previous edge is the first point on the working edge. Likewise, the first point of the next edge is the last point on the working edge. In the edge discretization phase, the edges are discretized to be about the same as the smallest grid spacing among connected faces. Thus, it is crucial that the application provide all the faces that are to be faceted in one step (using one of the functions api_facet_unfaceted_entity or api_facet_unfaceted_entities).
  4. In the face subdivision phase, a grid in parameter space is laid on each working face. A uv node set structure is created for each working face. The points from the point list of the working edges are added to this structure. Then, the initial uv node loops on each face are created.

    On planar faces and cylindrical faces, the cells on the grid are rectangular in the object space. For spherical, conical, and toroidal faces, the cells are not rectangular in the object space, but they are planar. For spline faces, the cells are not planar, but the grid is laid in an adaptive fashion that puts more cells in areas of higher curvature than in areas of lower curvature.

    When the grid is laid on the face, the grid lines in general do not intersect the edges at the discretization points. A refinement can be used to specify whether these intersection points will be inserted into the edge discretization. If they are not inserted, faceting will place triangles between the edge and the interior cells, regardless of the refinement.
  5. If the grid mode is set to either AF_GRID_INTERIOR, AF_GRID_ONE_DIR, or AF_GRID_TO_EDGES, then the faceter determines the number of uv isoparametric lines to be inserted for each working face based on the normal tolerance, surface tolerance, the maximum facet edge length, and the maximum number of grid lines and the minimum number of u_grid lines and v_grid lines as specified by the refinements. The uv isoparametric lines are equally spaced for analytical surfaces and are variably space for spline surfaces. In the grid spacing determination phase, faceting determines the appropriate grid to lay on each face according to the specified refinements. For AF_GRID_ONE_DIR, spherical faces have nodes that are evenly spaced only in the parametric U direction, and the V direction spacing is variable.
  6. If the grid mode is set to AF_GRID_TO_EDGES, the grid intersects the edges and creates facet nodes. This is accomplished by inserting the point list from the working edge into the faces uv point set.
  7. If a facet edge lying on a faces edge is wider than the uv spacing, the facet edges are subdivided accordingly. This adds more points to the uv points.
  8. If the grid mode is set to AF_GRID_TO_EDGES, the boundary points from the faces uv node set are inserted into the corresponding working edge point list.
  9. The points from the adjacent faces are verified to be in the uv node set of the face. If not, and if the grid mode is set to AF_GRID_TO_EDGES, the point list from the working edge is inserted into the faces uv point set as in step 6.
  10. The mesh for each face is created using the uv node set collected thus far and the triangulation phase.
    1. If the face has holes, bridge edges are added between exterior and interior edges.
    2. If the grid mode is set to either AF_GRID_INTERIOR, AF_GRID_ONE_DIR, or AF_GRID_TO_EDGES, then the bridge edges are split based on the uv grid. In addition, edges are inserted between existing uv nodes on opposing edges and are split by the uv grid.
    3. If triangulation mode is not AF_TRIANG_NONE, then the face nodes are triangulated up to the number of fringes specified in the mode (for example, AF_TRIANG_FRINGE_1, AF_TRIANG_FRINGE_2, etc.). If the mode is AF_TRIANG_ALL, then the whole grid is triangulated. A refinement AF_ADJUST_MODE, permits smoothing the facets if desired. The adaptive mesh algorithm (option adaptive_triang) subdivides when no grid mode is used and AF_TRIANG_ALL is used.
    4. If triangulation mode is not AF_TRIANG_NONE and if the grid mode is not AF_GRID_TO_EDGES, then there are some triangles that need to be subdivided based on the refinement controls given by the surface tolerance, the normal tolerance, and the maximum edge length tolerance. The midpoint of a facet edge is now used when testing for compliance to the normal tolerance.
  11. The resulting face nodes and polygons for each face are output through the appropriate mesh manager to a derived MESH class. For example, the INDEXED_MESH_MANAGER creates an INDEXED_MESH, while the POLYGON_POINT_MESH_MANAGER creates a POLYGON_POINT_MESH, and the LINKED_MESH_MANAGER creates a LINKED_MESH.
  12. If the application derived its own mesh manager for the purposes of saving the facet data in its own data structure, that would be carried out now. The derived class would redefine the inherited methods and enhance them to carry out the special needs of the application. For example, a class derived from the INDEXED_MESH_MANAGER would need announce_counts, announce_indexed_node, and announce_indexed_polynode methods. In addition, this is where information from the VERTEX_TEMPLATE class would be filled out for each node.
  13. A mesh (for example, INDEXED_MESH instance) is attached to each face using ATTRIB_EYE_ATTACHED_MESH. ATTRIB_EYE_ATTACHED_MESH takes an entity (face) pointer and a mesh pointer.
  14. At the very end of faceting, the mesh manager is freed.

Adaptive Faceting

Because ACIS supports various types of geometric representation (for example, planar, conical, toroidal, and spline surfaces), faceting relies on the curvature measurements of each faceted face to capture the underlying geometry. All types of surface geometry, except spline, can be well approximated with a regular grid whose lines are equidistant in parameter space. However, due to their intrinsic free form nature, spline surfaces necessitate a different approach.

Adaptive faceting is employed to lay a grid of non-equidistant lines, rather than a regular grid, for spline surfaces. The non-regular grid is based on the curvature computation of the spline surface at some parameter space sampling locations. Sampled curvature distribution controls the density of grid lines in the parameter space. Higher curvature areas get a greater number of grid lines, while lower curvature areas get fewer lines. In all cases, faceting tries to satisfy the refinement criteria set by the application.

The adaptive faceting algorithm now subdivides internal triangles according to the specified refinements in the case of faceting a body with triangles when no uv grid is selected. The option adaptive_triangles can be used when refinements is set to AF_TRIANG_ALL and also it is preferable to set adjust mode to AF_ADJUST_ALL.

Incremental Faceting

Incremental faceting saves computation time when only a few faces of a model have undergone some changes. This is accomplished by attaching a mark attribute to each faceted face when passing its facets to the mesh manager.

A mark attribute is lost when its owner face is engaged in any Boolean operation or a transformation operation other than translation or rotation. Therefore, a faceted face that has undergone a change will no longer be marked as faceted.

The API function api_mark_faceted_faces allows the user to select whether or not to attach mark attributes to faceted faces. If marking faceted faces is selected, a subsequent call to either of the functions api_facet_unfaceted_entity or api_facet_unfaceted_entities causes only the unmarked faces (that is, those that have changed since last faceted) to be faceted.

Related topics:

Refinements
Mesh Managers
Step-by-Step Faceting
Discarding or Keeping Facet Data
Faceting Functions and Classes
Faceting Using Scheme

[Top]

© 1989-2007 Spatial Corp., a Dassault Systèmes company. All rights reserved.