Posts tagged with 'curve'

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

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

The importance of great literature

  • Posted on September 3, 2012 at 11:30 am
Implicit Representation of Parametric Curves and Surfaces

Implicit Representation of Parametric Curves and Surfaces

I’ve recently been working on the question of whether mathematical surfaces can be rendered entirely using Shaders in a resolution-independent way, by avoiding the need to simplify the curve using triangles first. As part of the research in to this I found myself reading Sederberg, Anderson and Goldman’s 1984 paper “Implicit Representation of Parametric Curves and Surfaces” (available from ScienceDirect). Although not a new paper by computing standards, it’s definitely one of the best papers I’ve read in a long time, and goes to show that previous work is important not just from a legacy perspective.

It’s not just the contemporary relevance of the paper that demonstrates this point, but also its content. As the authors explain at the end of the paper, they present “two important examples of problems deemed unsolvable in the CAD literature, which are, in fact, solvable using century-old theorems.”

I’m not sure why I’ve been quite so surprised by this; I’m sure most people will consider this obvious. I should also add that Sederberg is very well cited in the rasterisation literature. However, it’s nice to come across such a clear example of less recent research that remains essential (and enjoyable) reading today.

I recommend the paper if you’ve not already read it. It’s very well written and contains some fascinating but clearly explained work.

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.

Interactive Functy function viewing

  • Posted on July 20, 2012 at 12:12 am

One of the obvious but neat consequences of having the new STL export functionality from Functy is that the generated models can be imported in to other things. One of these things… well, p3d.in provides a clever HTML5 in-browser model renderer, which means the models can now be rendered interactively directly into this site (or indeed any others). Check out this version of a ball made from string, generated as a couple of curve functions in Functy. Just click and drag to rotate the model. And if you like it, you can even print a copy in 3D!

Rendering tubes with shaders

  • Posted on June 26, 2012 at 11:57 pm

One of the main aims with Functy has always been to allow functions to be rendered using shaders on the GPU and using the function derivative to generate normals. This should be faster than rendering on the CPU. Defining the normals mathematically should also give more accurate results, and since we have the functions to play around with, it just seems like the sensible thing to do.

This presented a bit of a challenge for the new curve functions though. As is so often the case when using shaders, the problem is one of parallelism. If you have a function, the position of each vector in the model should be independent of the others and therefore a prime target for parallelism. With a curve you have the path of the curve and the radius at a particular point determined mathematically as long as you have the position along the curve, s and the rotation around the curve p given to you. However, what isn’t necessarily pre-determined is the orientation of the curve.

To explain this a bit further, consider the curve in the diagram below. Notice how the vectors perpendicular to the curve change direction as you move along the curve. These vectors are used to define the thickness of the curve at a particular point. In two-dimensions this is fine, as there’s no ambiguity about which direction these vectors should be pointing in.

Binormal along a curve in 2D

Normal along a curve in 2D.

However, lets now consider this in 3D. Suddenly these vectors can rotate around the axis of the curve, and while the vector must always lie within the plane perpendicular to the curve, there’s still an infinite number of possible directions that the vector can point.

Binormal along a curve in 3D

Normal along a curve in 3D.

In Functy, we use all of these directions, because the p variable defines a full rotation around the curve, so that it becomes a tube (rather than a line). But we still need to decide which direction the zero angle should point.

Some how or other a choice has to be made for this. There are a number of possibilities. We could set it randomly. However, this means there will be no consistency from one piece of the curve to the next, and if the cross section isn’t a circle, will result in a random twisting of the curve. This would look rubbish, so it’s not an option.

In my 3D Celtic Knot program I came up against exactly the same problem. Since it was essential for the start and end of a curve to match up exactly, I used an iterative approach there. For each piece, the rotation between the previous and next point on the curve is calculated and the perpendicular vector transformed by this in order to establish its new position. At the end of the curve an adjustment is made to ensure pairs of curves will always fit perfectly together. This is possible because the maximum adjustment needed will never be more than 2π/x radians where x is the number of segments that make up the cross section of the curve (called the Radial Accuracy in Functy).

However, unfortunately this technique can’t be easily parallelised since the orientation of each piece depends on the last, meaning that it couldn’t be translated easily into shader code. For Functy I therefore needed a different solution.

Luckily for me this isn’t a new problem, and the solution came in the form of Frenet Frames. A Frenet Frame is an orthogonal set of axes that’s defined based on the curvature and torsion of the curve at a particular point. Since it’s (in general) canonically defined at each point on the curve, it can be calculated independently from the other points, by calculating the derivatives and second-derivatives of the curve. More specifically, it requires that the tangent, normal and binormal vectors of the curve be calculated. There’s a decent explanation in the Wikipedia section “Other expressions of the frame”, and there’s also a neat Wolfram Demonstration too.

Since these three vectors can be calculated using the derivative of the curve, there’s no need to iterate along the curve, which makes it perfect for calculation using shaders. This is now implemented in Functy, and it seems to work pretty well. On my laptop, which has a decent but not mindblowing graphics card, animating a Frenet curve on the GPU using shader code is considerably faster than using the CPU.

The only problem is that this method has a tendency to generate curves with twists in. That is, the axis can make sudden rotations around the direction of the curve. In general this isn’t a problem, but can cause the curve to ‘pinch’ if the resolution of the pieces is too low. Below is a particularly extreme example.

Twist in curve due to Frenet frame rotation.

Twist in curve due to Frenet frame rotation.

Usually it’s not as bad as this, but it’s a shame nonetheless. For the benefit to be had from parallelisation I’m willing to live with it.

Top