Prior to release 5.0, the triangulation functionality offered within the LightWorks ADS was limited to a single, simple triangulation method. Users could triangulate polygonal geometry, but the triangulation was not guaranteed to be optimal, and there was no opportunity to further triangulate a mesh which was already made up of triangles.
As of release 5.0, all of these restrictions have been removed. It is now possible to insist on a simple triangulation being optimal (a Constrained Delaunay Triangulation results). It is now possible to add vertices before triangulation, so that a long, thin polygon will not be triangulated into long, thin triangles, and it is also possible to further triangulate a triangle mesh so that more, smaller, triangles result.
This section outlines the new API for polygonal triangulation.
The high-level meshing routine within ligeops, is LiPrimitiveTriangulate:
LtStatus LiPrimitiveTriangulate ( LtPrim triangulate_me, LtTriangulate triangulate_method )
This repeatedly calls a simple "triangulate this polygon" routine, with every polygon of the given primitive. Only primitives of type LI_PRIM_TYPE_POLY and LI_PRIM_TYPE_MESH will be processed by this routine. Passing in a primitive of any other type, will result in a non-zero return value.
The LtTriangulate parameter specifies the particular triangulation method that the caller wishes to see employed. Prior to release 5.0 of the LightWorks ADS, the only triangulation method available, was LI_TRIANGULATE_SIMPLE. As of release 5.0, the ADS has been extended so that 4 triangulation methods are now available. Further details are given, here.
The previous section leaves us with some unanswered questions - how is the new triangulation code to know which triangulation method should be applied, when? How does it know what parameters to use, once it has established the triangulation method?
We introduce meshing refinements, akin to facet refinements, and the (associated) meshing criteria:
typedef LtGenericPtr LtMeshingRefinement; typedef LtEnum LtMeshingCriterion;
A meshing refinement points to a data structure whose specifics are hidden from the API user. However, the user is able to store information relevant to meshing, within a refinement, and then attach the refinement to zero or more primitives.
A meshing refinement has a number of meshing criteria associated with it; each criterion representing one part of the sum of information that makes up the refinement.
When a primitive is passed to LiPrimitiveTriangulate, any primitive-specific meshing requirements (defined by a meshing refinement, attached to the primitive) will be utilised. A meshing refinement can also be set as the global default – to apply in the absence of any primitive-specific information. This default refinement is set and read via the control variable LI_CONTROL_MESHING_REFINEMENT, whose type is an LtMeshingRefinement, and whose default value is NULL.
The following routines are available to the API user, for the creation, copying, destruction and debugging of meshing refinements:
Tools for controlling which criteria are associated with which refinements, are outlined here:
Tools that allow us to associate different meshing refinements with different primitives, are outlined here:
The following example illustrates the effect of a simple call to LiPrimitiveTriangulate, where no use of meshing refinements is made:
If the same call had been preceded by a routine which ensured that the global meshing refinement had its LI_MESH_CRIT_EDGE_SWAPPING set to LI_EDGE_SWAP_ALL, then the following image would have resulted:
If the first call had instead been preceded by a routine which ensured that the global meshing refinement had its LI_MESH_CRIT_MAX_EDGE_VERTS set to TRUE, and its LI_MESH_CRIT_MAX_EDGE_LENGTH set to some appropriate value, then the following image would have resulted:
Note that this triangulation is clearly suffering from our failure to allow internal edges to be swapped. Also, it is not a particularly good candidate for MAX_EDGE_VERTS edge splitting, before triangulation; this is best left to long, thin polygons, where a real advantage can be gained. In the next image, we not only allow pre-triangulation edge splitting, we also allow all suitable internal edges to be swapped:
The triangulation is still far from ideal. The following example illustrates what happens when MAX_EDGE_VERT edge splitting is dropped, and the mesh is simply meshed into 200 triangles, using LI_TRIANGULATE_POLY_COUNT, with edge swapping allowed:
The final example, below, illustrates a LI_TRIANGULATE_MAX_EDGE_LENGTH triangulation:
As described above, the core ligeops triangulation code (LiPrimitiveTriangulate) has recently been markedly extended. It is now possible to swap edges in a triangle mesh, so that a Constrained Delaunay Triangulation results. It is now also possible to mesh until there are a specified number of triangles in the resultant mesh. Similarly, one can mesh until every edge in the mesh is no longer than a specified maximum edge length.
On the face of things, this functionality is extremely rich. Indeed, for all but the most demanding users of LiPrimitiveTriangulate, this functionality is extremely rich. However, if a user wishes to make multiple successive calls to LiPrimitiveTriangulate, with the same primitive (each time generating a finer mesh) then performance issues will raise their head.
Consider the following scenario: An advanced user calls LiPrimitiveTriangulate to achieve a "maximum edge length" triangulation, and then calls it again, straight away, to achieve a "polygon count" triangulation. The problem here is that LiPrimitiveTriangulate will create edge adjacency information at the beginning of the first call, maintain the data through the first triangulation, and destroy it when done. At the start of the second call, this data will have to be re-created; a somewhat expensive process for complex meshes.
For users that wish to make multiple consecutive calls to LiPrimitiveTriangulate, for each primitive, this destroy/re-create overhead will surely become expensive, for large scenes. Since one of these users is the LightWorks radiosity module, action has already been taken to avoid the high cost of such calls.
We introduce:
LtStatus
LiPrimitiveHierarchicalTriangulate (
LtPrim prim,
LtGref refinements
);
This takes a single primitive, and a linked list of meshing refinements (LtMeshingRefinement). Its behaviour is outlined in the following enumerated list:
Steps 6 & 7 are repeated until the last meshing refinement is reached, at which point LiPrimitiveHierarchicalTriangulate will:
N.B., The "first meshing refinement" is the one that is pointed to by "refinements->next". This is because a generic reference is always assumed to point at the LAST list element. Care must be taken to ensure this convention is observed, by the caller.
The function's return value is equal to the return values of the various calls to LiPrimitiveTriangulate, bitwise OR-ed together. (Unless something like invalid input was encountered, and we never got as far as triangulating anything).
Invalid input to LiPrimitiveHierarchicalTriangulate includes:
Restricted information.
© LightWork Design Ltd. All information contained in
this document is the copyright of LightWork Design Ltd. (unless stated
otherwise) and may not be used or reproduced with prior written consent.