Curves

Curve Functions as Voxels

  • Posted on December 1, 2014 at 12:11 am
Voxel posts

  1. Intro
  2. Cartesian Functions
  3. Spherical Functions
  4. Curve functions (this post)

Curve functions are defined as a circular co-ordinate function extruded along the length of a parametric curve. Hence, just like Cartesian and spherical functions, we have just two inputs (in this case the angle θ and parametric variable s) and three outputs (the x, y, z co-ordinates of the surface point):

(x, y, z) = f(s, θ).

This is constructed from the parametric curve

(x, y, z) = p(s)

and the radius functions

r = q(s, θ).

Practically speaking there’s some ambiguity here, because the angle θ needs to be given an orientation. One rotational axis is defined by the tangent to the curve, but where does that leave the other two so we know where to start our rotation from? To solve this we use the Frenet-frame of the curve to define an orthogonal co-ordinate space independently at each point along its length. It’s generally a good solution because it tries to maintain a consistent orientation along the length of the curve (although this can fail rather miserably if the curve becomes a straight line, which is a discussion for another time) while also being independently defined at each point on the curve. This last point is important in order to be able to calculate the curve surface points in parallel using the GPU.

This arrangement works well transforming from parameters to surface co-ordinates. But for a voxel map we need the reverse: take a voxel co-ordinate (x, y, z) and establish how far it is from the curve. We have the equation of our curve and can write an equation to capture the distance, but actually solving the equation is a different matter.

How far away is a voxel from the curve?

How far away is a voxel from the curve

What we need is a solution to the following equation.

dp(s) / ds = 0

Calculating the algebraic form of dp(s) / ds isn’t hard (we do it already for the lighting calculations), but solving the equation can be. We’d have to rearrange the equation to establish it in terms of s. It could have multiple solutions, as the diagram above shows. In short, given p(s) is user defined and could be practically any function, we simply can’t rely on being able to solve the equation.

So is there nothing we can do? We can’t find the parametric variables that relate to a specific voxel algebraically. This is a real shame; it means we have to use a different approach entirely. The solution I’ve come up with is to effectively rasterise an approximation of the volume as a series of tetrahedrons that can make up the volume. Sadly this is less accurate and less efficient than the ideal algebraic approach, but at least it seems to work and reasonably well.

A tetrahedron is the 3D primitive counterpart to a triangle (the 2D primitive): we can represent any solid approximately as a series of tetrahedrons just as we can approximate any surface as a series of triangles. We can similarly render the solid into a 3D texture as a series of tetrahedrons in the same way we usually render a surface as triangles onto a 2D texture.

To understand this better, think of the tube defined by our curve as if it were partitioned into a series of cuboids, as in the diagram below. In the diagram the cuboids form a very crude approximation of the cross-section of the tube. This is crude partly because of the low number of cuboids used (in practice we’d usually want more) and partly because of my poor Blender skills (which you’ll just have to try to look past).

Cross section following a path

Cross section following a path

Here’s how one of those cuboids might look:

One of the cuboids making up the approximated curve

One of the cuboids making up the approximated curve

Our voxel space is made up of a series of slices (each slice has the same z co-ordinates but with varying x-y co-ordinates) so we need to be able to slice this cuboid. Performing slicing directly on the cuboid turns out to be hard (for me, at least), so the solution is to convert each cuboid into five tetrahedrons, like this:

Splitting up a cuboid into tetrahedrons

Splitting up a cuboid into tetrahedrons

This is actually really easy to do, because every vertex of each tetrahedron is just one of the vertices of the cuboid: we just need to pick them out in the right order.

Slicing a tetrahedron is a lot easier. Assuming (for the sake of simplicity) we don’t slice along one of the edges, a plane will always cut the edges of the tetrahedron in either three or four points. If it’s three points, we can just join them to create the triangle that represents the slice through the tetrahedron. If it’s four points, we have a quadrilateral, which we can turn into two triangles. We have to take a bit of care over this to avoid accidentally choosing the concave variant where two of the lines cross:

Choosing the right corners to use for the triangles

Choosing the right corners to use for the triangles

To avoid this, we check whether two of the lines cross, and if they do, reorder the vertices to fix it. We end up with two triangle which we can then rasterize onto the surface slicing the volume. Computers have been rasterizing triangles since the dawn of time (well, at least 1967, which is as good as).

So we have our sequence of simplification: curve volume, cuboids, tetrahedrons, triangles, voxels. It’s a bit long-winded, but we get there in the end. The inefficiency is compounded by the fact we end up performing this ‘volume rasterization’ repeatedly for each slice of the voxel space. We could do it all in one go, but that would require the entire voxel space to be held in memory while the render is performed. Given the amount of data involved (e.g. a 1024 × 1024 × 1024 voxel space would require a gigabyte of RAM) rendering each slice individually is considerably more memory-efficient, if not time-efficient.

The final results are generally good, although it’s still an approximation as compared to the results for Cartesian and spherical functions. As far as I can tell, there’s no straightforward way to avoid this based on Functy’s current design.

Here’s the images from the original post showing how all three curves - Cartesian, spherical and curve - are voxelised into a set of slices making up their combined volume.

Cartesian, spherical ad curve functions creating a scene in Functy

Cartesian, spherical ad curve functions creating a scene in Functy

The three volumes voxelised into slices

The three volumes voxelised into slices

Voxel Volumes

  • Posted on November 28, 2014 at 8:37 pm

One of the main feature additions of the latests version of Functy has been the ability to export as SVX files. Functy could already export in PLY and STL, but both of these are triangle based. They represent the 3D functions as surfaces defined by carefully aligned triangle meshes. Rendering objects using a graphics card also uses the same triangulation process, so exporting as PLY or STL is a very natural extension of the existing rendering.
The SVX format is different though. It stores the models as a voxel image (a voxel being a three dimensional pixel, for those who didn’t grow up through the 90s demo scene). As a result, SVX doesn’t just store the surface, but also the volume of a function.
Turning a triangulated surface into a voxelated volume isn’t necessarily straightforward, but Functy has the advantage of having all its objects originate as purely mathematical forms. In theory, this means voxel rendering them as volumes should be quite easily.
What I found in practice is that for Cartesian functions and spherical functions this is true: they can be turned into voxel volumes in a very natural way. Curve functions are a different story though. In the next few posts I’ll go through each of the processes separately, to give an idea about how the solutions for each of the three function types were coded.

Voxel posts

  1. Intro (this post)
  2. Cartesian Functions
  3. Spherical Functions
  4. Curve functions

Projections

  • Posted on July 30, 2013 at 6:10 pm

The sun was out in Liverpool today, creating crisp and long evening shadows. So it seemed like a great opportunity to take photos of recent 3D printed Functy objects. The full images are rather large, but show the grain of the printing, which I think is rather interesting in itself. Click on the images for the full views.

The original Lissajous is up on deviantArt and Shapeways; the alien egg is also on deviantArt and Shapeways.

Lissajous Looping

  • Posted on July 15, 2013 at 12:40 am

Following on from my previous post, I thought it’d be interesting to make an animated render of the Lissajous figure. If you have an APNG-capable browser (e.g. Firefox) you can see the result on DeviantArt.

While it’s neat to be able to print static versions of these Lissajous figures, in the future I’m sure it’ll be possible to make the fully moving version as well. Now that would be really something!

Static version of the render - click for the animated version

Static Lissajous render - click for the animated version

Lissajous Loops

  • Posted on July 11, 2013 at 8:11 pm

Sines and Cosines have been responsible for some of the most elegant mathematical constructs. Lissajous curves are a particularly simple, yet elegant example. Put simply, a Lissajous is a parametric curve where each axis follows a sinusoidal path. By tweaking the amplitude and cycle length for each axis, a myriad of different patterns can be generated, from circles to intricately woven lattices.

The parametric curves in Functy are particularly suitable for generating nice Lissajous curves, and as usual, they can be output for 3D printing. The results of pumping them through a 3D printer, courtesy of Shapeways, can be seen in the photos below, along with a Blender Cycles render of one of the curves.

If you fancy getting really up-close-and-personal with them, you can order your own copies as unusual desk ornaments, from the Shapeways site.

3D printed Lissajous curves

3D printed Lissajous curves

3D rendered Lissajous curve

Rendered Lissajous curve

Network structures

  • Posted on December 29, 2012 at 4:05 am

As part of an experimental game project I’ve been trying to use the Functy rendering routines to visualise network structures. At the moment it’s at a very early stage, but has - I think - already generated some interesting results.

The screenshot below shows a network of 60 nodes, each one rendered as a spherical co-ordinate function, joined together using links rendered as curves. I just plucked some simple functions out of the air to see what the results would be like but am hoping to extend it with more interesting shapes as things progress.

Functy rendered network structure

Functy rendered network structure

The various parts of the network are a little hard to discern with a static image, but when I tried to capture a video the result was a mess of fuzzy artefacts (I think there must be something going wrong with my screen capture software), so I gave up on that.

The next step, after neatening up the code, is to arrange better animation of the nodes and links, with dynamic movement based on things like the forces between the nodes. I’m hoping this will produce some really nice effects, and if anything comes of it I’ll put a bit more effort into getting a successful video capture.

Comparing implicit and parametric functions

  • Posted on September 7, 2012 at 10:00 am

In an earlier post I talked about Sederberg et al.’s paper that uses Elimination Theory to demonstrate how parametric curves can be represented in implicit form. Reading through the literature it quickly becomes clear that this is important work if you’re interested in rendering parametric curves or surfaces. Unfortunately it can be difficult to get to grips with the theory without also being able to play around with the functions themselves. Consequently I’d expected to spend much of my summer writing software to render the different types of curves for exploring them and play around with their different representations.

That was, until I realised Functy was quite capable of doing it already. Functy’s parametric curves are already perfectly suited to the rendering of parametric equations. This part might be obvious. Less obvious for me was that the colouring of a flat Cartesian surface is perfect for the rendering of the implicit form.

Above are a couple of screenshots showing the two types of function. These are both taken from the example in another paper by Sederberg, Anderson and Goldman about “Implicitization, Inversion, and Intersection of Planar Rational Cubic Curves” (available from ScienceDirect). The curve is a quartic monoid which can be expressed parametrically and implicitly as follows.

Implicitly:

(x4 - 2x3y + 3x2y2 - xy3 +y4) + (2x3 - x2y + xy2 + 3y3) = 0

Parametrically:

x = - (3t3 + t2 - t + 2) / (t4 - t3 + 3t2 - 2t + 1)

y = - (3t4 + t3 - t2 + 2t) / (t4 - t3 + 3t2 - 2t + 1)

In the screenshots the red line is the parametric version of the curve for t in the interval (0, 1). The other colours on the surface represent the values of the implicit function. Note that the implicit function actually lies at the boundary of the yellow and blue areas. You can see this slightly better in the 3D version, where the height represents the value of the implicit function. The actual curve occurs only where this is zero - in other words where the surface cuts through the plane z = 0.

It was reassuring to see that the parametric curve matches the implicit version. It’s also interesting to note that the implicit version is rendered entirely using the shaders in a resolution-independent way. It’s possible to zoom in as much as you like without getting pixelisation. This is exciting for me since, although it’s not what I’m really trying to achieve (that would be too easy!), it hints at the possibility.

3D printed Functy rings

  • Posted on August 9, 2012 at 8:00 am

A parcel arrived from Shapeways recently containing some of the 3D printed ring prototypes I generated using Functy. The models were exported directly from Functy and converted into STY format before being directly uploaded to Shapeways for printing. All based on sine/cosine curves, there’s a flat version, a slightly bulging version and an irregular version. Since Shapeways did such a brilliant job printing the prototypes, the next step is to get them to print them in silver. Click on the links if you fancy having your own printed!

The Functy function files for all of these rings are up in the repository and will be included as example files in the next full release.

Animated Blender Render

  • Posted on August 7, 2012 at 11:54 am

After prompting by Tony’s superb gallery of images, I’ve spent a bit of time playing around using Blender to render models created using Functy.

This has also prompted a bit of extra functionality, and I’m hoping it will soon be able to export out multiple models from Functy to support animated functions. Using the current experimental code (there’s no front-end yet, but it’s in the pipeline) I managed to generate a kind of animated mercury whirlpool. It’s up on deviantart, and if you’re happy to wait for the download, please do take a look at the full animated version.

Brilliant Functy Renders by Tony Ralano

  • Posted on July 29, 2012 at 2:17 pm

Tony Ralano has been creating some amazing renders by combining Functy models with his impressive Blender and 3DS Max skills. The image below is an example of a function exported out, then manipulated and rendered using Blender.

Functy 724 by Tony Ralano

Functy 724 by Tony Ralano

Check out the original on deviantart. Tony’s gallery also contains a whole load of his other amazing creations. I plan to post up some more of Tony’s images over the next few weeks.

Top