Sunday, September 1, 2013

Circumscribed triangles: helpers for efficient tesselation and Voronoi surfaces

Any triangle can be circumscribed by a circle. The circumcenter is located at the intersection of the perpendicular bisector of the sides of the triangle. Any two sides will work; using all three sides gives the same results as two sides. 

Circumscribed triangles are the basis for a Delaunay triangulation of a surface. The idea behind the Delaunay triangulation is that the triangle are distributed on the surface such that no vertex is inside a circumcircle. This method of triangulation works well when the sample of points on a surface varies depending on the detail and curvature of the surface at various points. The circumcenters in the Delaunay triangulation also define a Voronoi diagram. Voronoi diagrams seem to explain many biological and natural forms and are used in many applications of surface tessellation, and mapping.  

Andrew Kudless has famously made use of Voronoi diagrams and honeycomb structures in this architecture and art.

Of course, the location can be calculated with trigonometry and geometry. An example is shown in, but I am not sure that it works in all situations and the math is pretty intensive. The method described below is largely a graphical method that is very intuitive.By making use of helper surfaces, it is easy to construct the points that drive the geometry. 

Create a new family. Choose the template for Curtain Panel Pattern Based. One could also use Generic Model Adaptive or Generic Model Pattern-Based.  

Click on the blue pattern and change the type to a flat triangle.

The strategy is to create the perpendicular bisectors by defining planes as helper objects to keep the coordinate systems unambiguous. Since the circumcenter can be found from the perpendicular bisector of any two sides, choose two sides of the triangle and use Create form to make two extruded planes.

Draw a reference line on each plane so that it is at the midpoint of the original reference line. Extrude these to make planes. 

These planes bisect the sides of the triangle. Lengthen the planes to make them always long enough to intersect. Where they intersect is the circumcenter. These helper planes do not need to be tall; set them to be of a reasonable size.

Flex your model after every operation. It is easy to draw objects on the wrong plane or work plane.

Since it is important to keep the objects on the plane defined by the triangle, it is also helpful to have a helper surface at that plane. Pick the reference lines of the triangle and create a triangular surface. This will be used extensively as a workplane.

Set the workplane to be the surface.

Next, place a reference point by face on the bottom edge of one of the helper bisectors. It should snap to the edge. Draw a circle with its center point on the reference point. Pick the circle and change its host to be the reference point.

Move the reference point to the circumcenter. The easiest way to do this is to select the point and choose the Host by intersection option. Click the other bisector and the point and the circle should jump to the intersection.

There may be a way to lock the radius of the circle using one of the vertices, but I don’t know how. It is simple to calculate the radius. For a calculation of the diameter of the circumcircle, see:

Of course, the radius is 1/2 the diameter, so
  • r = (d / sin (a))/2

where r is the radius, d is the length of a side of the triangle, and a is the angle of the opposite angle.

Use an angular dimension and a linear dimension to measure the side of the triangle and the angle. Two factors require very careful attention. First, set the workplane to be the helper triangle. The angle and length must be measured on the plane of the triangle. Second, the dimensions must be to the adaptive points and original reference lines of the pattern. This is required to allow the dimensions to be used as Reporting dimensions in equations.

Create Labels for the angle a and the side d and make them into reporting dimensions of the right type. Create another parameter for the radius and attach it to the radius of the circle.

Put in the equation for calculating the radius and you should get the circumcircle. Flex the model to make sure that it works.

Draw model lines for the circle and the triangle using the Pick lines tool. Lock them to the reference lines.

In a separate file, create a conceptual mass family and draw a surface. Load the circumcircle family. Divide the surface and apply the circumcircle to it.
The helper objects are not necessary for simply inspecting the triangles and circles. A refinement of the circumcircle family is to create parameters for controlling whether the helpers are visible or not. Create Yes/No parameters and attach them to the visibility attribute of the helper surfaces, the triangle and the circle. I made these Type parameters so that I could turn on and off all of the panels easily. I also created three types with different visibility settings for the helper objects.

It is easy to turn on or off the visibility of panels. To isolate the helpers of a single panel, apply the hidden type to everything and then change the type of the panel that you want to inspect. 

My intention behind this tool is to develop cooperative tools that help me manually subdivide a surface with an arbitrary mesh and then construct a Voronoi surface on it. The mesh will have a tight sampling when the curvature is sharp or there is a lot of detail, and a coarse sampling when there is little change in surface angle. I want to be able to manipulate the mesh to keep the Voronoi facets reasonably flat to allow for construction from flat materials.  I will experiment with this circumcircle tool to gain experience in crating irregular meshes and see if I can devise a way to gain feedback on the curvature as I apply facets. 

1 comment:

  1. Thanks for your post. Your work is quite impressive.
    and i updated a post about this issue in my blog.