Tag Archives: curves

Spline Extrusions, Tubes and Knots of Sorts

Posted on by

The recent development in three.js up to the recent 49th release has been really crazy – just look at the changelog! Some work that made it in were 3d spline extrusions, which you could follow the development reading the thread in issue #905. @WestLangley‘s involvement was also a great help!

3d spline extrusion examples

[TL;DR If this post seems too boring, or just too long (as i'm trying to release some air out of my head), feel free to skip everything but try the example. You might also like to turn on camera spline animation, create your own torus knot, or create a custom tube by writing a formula there]

View tube/spline extrusion example.

Related work (spline curves, shapes extrusion geometry, text bending) were previously mentioned, but extrusion geometry did not handle 3d spline extrusion well, so the discussion brought out new features to be implemented after being left in TODO for a couple of months. The work resulted with couples of jsfiddles, created new classes like THREE.ArrowHelper, THREE.TubeGeometry, improvements to some old classes and created a couple of new examples. Read on if you like to know what went through the thought/development process back in time.

Extruding a spline != Extruding on the Z-axis

I decided to tackle this issue one night, since I barely recall the internals of ExtrudeGeometry after leaving of quite awhile, so I tried to recreate a simple version. The first approach to take the points of the spline – which spline.getPoint(), then recreate the cross-section of the shape. Looks almost like it’d work, until you the spline move vertically up the y axis and the geometry falls apart. Ohoh. WestLangley reminds me that the geometry is not orthogonal – which refers to angles kind of perpendicular or 90 degrees from the tangent. His suggestion to modify the TorusKnotGeometry (done by @oosmoxiecode) to create a TubeGeometry is a wise choice.

Not a very correct path extrusion

Normal of a 2D line != Normal of a 3D line

Ok, I recalled having to deal with a path normals in the text bending implementation. That was done by getting the tangent of the path, and invert the vector like -y / x. I thought surely there’s a formula to do the same in 3D. Looking up the wikipedia topics of normals, there were formulas for normal to a plane, normals to a face, but no, there aren’t any formulas for a vector in space. And so I begun to understand and as @profound7 reminded me that there are just infinite amount of normals to a line in space.

There are however a set of formulas in tackling this issue, as @miningold brought up, the the Frenet–Serret formulas, and that became another topic in math for me to study. From the simple understanding I have now, the Frenet–Serret or TNB frames are like your thumb and 2 fingers in either the left hand (or right hand) rule. Each direction represents the tangent, normal and binormal which are 90 degrees / orthogonally apart.

Sounds simple? Could be, but the ill-rewards of not being a diligent student in school is having to now stare painfully at this paper “Tubes and the TNB frame”. Perhaps after damaged brain cells and hairs interpreting those seemingly foreign mathematica symbols, I thought I could try explain these formulas in my own understanding.

Frenet–Serret

Frenet–Serret Formulas for dummies like zz85

Spline = an imaginary line in space which a point will travel from one end to another end over time.

Tangent = Is the change of position at a particular point of the spline. This the first derivative of position over time. Now what we need to store is simply its unit vector, by dividing its length, so its magnitude is equals to 1, since we only need its direction, not magnitude.

Normal = Change of tangent unit at a particular point / time of the spline. I was wondering for a while why this is not the 2nd derivative of the position over time – and I realized that that’s because T is a unit vector rather its change in position.

Binormal = By doing a cross multiplication of T and N, you will get a binormal perpendicular to both vectors.

Frenet–Serret frames != Magic bullet for spline extrusion

Yeah, with Frenet–Serret formulas, that means I can just plug in a formula to get the normals, and it would be simple to implement the tube geometry? Not so soon again, because I soon hit the situation that miningold was facing earlier – there were some really ugly wraps in geometry. This call for some visual debugging of the geometries normals – WestLangley was doing something similar and so we thought these helpers would be useful. Those got refactored later to THREE.ArrowHelper.

Even with Frenet–Serret formulas, fail.

What happened? Because of inflections in portions of a cat-mull rom spline, the normals may flip around really unexpectedly rapidly. On the positive side, that seems like that’s a well known problem if you search on the net. From this link from CMU provides a pretty simple and usable solution, taking the binormal of the previous segment to compute the normals and binormals for the current ones, which is the moving frame approach. With that, we could already start to implement some fanciful geometry.

Heart Tube

Moving Frames != Ending Frames

The next problem was then brought up, that is normals of the ending and starting normals of closed tubes do not match. That could be quite obvious if the radius segments were few, and joining seam would have an ugly closure. I found links to some papers on RMF Rotation Minimizing Frames (RMF) – a method which double reflects, I guess for comparing rotation changes before and after segments, in order to process the frames correctly. While I didn’t manage to understand all these, WestLangley wrote the implementation for the Parallel Transport Frame approach, making sure the tube is slowly twisting so that the starting and ending binormals. Yeah!

To test out the new TubeGeometry, I started looking for some spline formulas. I also started looking into knots because @mrdoob proposed the possibility to implementing the TorusKnot with TubeGeometry. With a little practice, you would find a defining a curve/spline object using the method THREE.Curve.create() really easy, and I also started appreciating some beauty of mathematics and formulas, in that you could create beautiful, and even complex geometries with really simple code.

Decorated Knots

If you look into curve extras source, there’s a tiny compilation of links to some pretty good resources on curves and knots. However, one resource that particularly interest me was a university paper on decorated knots. By applying certain pattern of formulas to knots, you would get interesting and beautiful geometries. I have used some of the formulas in the spline extrusion example and you could easily use those formulas too.

Decorated Knots

Real-time Knots
So if you haven’t realized, three.js is versatile and powerful enough to be a 3d/math graphing software. Many of the existing sites on knots and curves would require you to download some graphing/knotting software, or at best uses some Java applets. So no longer do you need download any stuff or plugins, you can run that in your browser. In my example, you can create your own torus-knot by defining your p,q,r parameters, or even write an entire new curve by formulas. Well, it seems that Google’s have also thought along the same lines, having enabled a webgl 3d graph plotter in their search engine (Rose Example). Probably a good time now that SwiftShader (webgl software fallback) is getting activated in Chrome too.

Real-time Knots

Camera Movements
On turning on the spline animation, you would kind of follow the direction of the spline from a distance above it. The camera orientation is stabilized using the binormals of the same frames generated for the TubeGeometry. When I started experimenting with it, the simplest way would just to rotate the camera in the direction of the spline tangents. It probably works, but with a side effect, the control of the camera’s spin may be lost. Perhaps not too bad an idea, if you want to create a dizzy effect or re-enact Joseph Kittinger’s not so successful jump (before his world famous record breaking jump). And the “Look Ahead” option kind of gives a different feel by fixing the camera view on a point, a distance away on the spline. Scaling up the geometry while on the spline camera works too.

Camera Movements

What’s next?
ExtrudeGeometry has extended a similar kind of 3d extrusion used in TubeGeometry. It can probably be more refined for its purpose. There has also been some work on ParametricGeometry, which could be used for an internal TubeGeometry refactoring. I’m planning to work on a little three.js DIY rollercoaster experiment which would probably be a good use case for testing and refining all the work here – and a 3D spline editor to come with that (since there’s already some form of 2D spline editor)

Not enough curves?
Oh, and if you are really interested in mathematics, curves and splines, I stumbled upon this really interesting lecture on this topic, touching on the practicality of curves in buildings, bridges and even roller coasters. (the video lecture is not in a very high quality, but you can also download the lecture slides and audio). Have fun!

(ps. today’s three.js 2nd anniversary according to mrdoob. initially thought i could write another post to commemorate this day, oh wells… happy three.js day!)

Curves – Base Classes

Posted on by

This is a quick write up about the Curve classes added to Three.js. If I procrastinate any further, nothing at all may be written, so I’ll start off with the base classes.

The base curve classes can be found in Curve.js. Curves have been used for Text, Shapes, and even animation so the Curve classes is the core of all these.

A curve is a generalized representation of lines. Similarly, THREE.Curve is the base class which other Curve classes extends. While you may extends a curve yourself, implemented curve classes includes

* — 2d curve classes –
* THREE.LineCurve
* THREE.QuadraticBezierCurve
* THREE.CubicBezierCurve
* THREE.SplineCurve
* THREE.ArcCurve

* — 3d curve classes –
* THREE.LineCurve3
* THREE.QuadraticBezierCurve3
* THREE.CubicBezierCurve3
* THREE.SplineCurve3

Curve classes have a common set of methods derived from THREE.Curve.
getPoint(t)
getPointAt(u)
getPoints(divisions)
getSpacedPoints(divisions)
getLength()
getLengths(divisions)
getNormalVector(t)
getTangent(t)
getUtoTmapping(u)

Okay, that’s plenty of methods, but let’s break it down.

Getting Points
Now before one can start drawing curves, you need to break down the curve to points. curve.getPoint(t) returns you a point (a 2d vector for a 2d curve, and 3d vector for 3d curve), when t is the parameter along the line (expressed from 0 to 1). Now there are times, when equi-units of t, does not give you equi-distance points eg. distance from curve.getPoint(0.1) to curve.getPoint(0.2) may be 10 units but curve.getPoint(0.2) to curve.getPoint(0.3) maybe 20 units. (This happens usually to curves, where there are many more points near its bends than at its straight ends). What getPointAt(t) does is to do its magical mappings so distance between curve.getPointAt(0.1) -> curve.getPointAt(0.2) and distance between curve.getPointAt(0.2) -> curve.getPointAt(0.3) would almost equi-distance if not equal. One example use for this is to make smooth animation for a camera along splines without moving faster or slower on different parts of the curve.

getPoints() is a convenience class to return the curve entire set of points with a given subdivision length. Internally, it usuals intervals of number from 0 to 1 with getPoint, so, use getSpacedPoints(divisions) to get points as equally spaced as possible.

Getting Lengths/Distances
getLength() returns the units distance of the curve. getLengths() builds accumulative distances based on its segments, and is used internally for equi-distance mapping, so avoid this if you do not need to use this. Likewise, getUtoTmapping(u) to used to map getPointAt() to getPoint(), while its mostly used internally, you may used it for getting a value of t to use with getTangent();

Others
getTangent() returns you a tangent vector at point t. And getNormalVector() for its respsective normal. Now, all these magically works for a subclassed curve as long as it implements getPoint(), however for more accuracy, a subclass can overwrite these methods for a more exact mathematical precision (as Line, Bezier, Spline curves did). These tangents from the curves can be used for point an object in a direction, while animating the movements around it. It is also used for the Text bending examples.

That sums up the basic explanation of the core Curve class.

History: Development of curve classes appeared in here and was possibly the by product of this and also this article

Extrusion Bevels – Three Attempts in Three.js

Posted on by

Three.js is out now at r43 with more features. Check it out! :)

In a previous post I had highlighted my approach for creating 3d geometries extruding a 2d text font (shape) along its z-axis. There have been a couple of changes for Text too – `Text` is now `TextGeometry`, much of what has been in that class has been refactored into a couple of other classes, but since we have a generic extrude geometry class `ExtrudeGeometry` which applies not only to text fonts but to any generic closed forms shapes with support holes with `Curve` and `Path` classes. Along with TextGeometry is wrapping to splines/curved paths, maybe a topic for another post ;)


Bevel and Text Geometry with Level-of-details

In this post, I talk a little about beveling, (termed fillet caps in Cinema4D), which I mistakenly labelled it as bezel at first (the round part around rolex watches). Bevel slopes or rounds the corners of an extruded block, kind of chiseling or sandpapering a wooden block in the real life analog. Beveling also seems to be a common feature in 3d programs, and you might have probably even use it in applications like photoshop or word. While seemingly a simple feature, it almost took me almost four rewrites to get to a version which I’m satisfied, of which I’m sharing my approaches below.

To start off, I wasn’t even sure whether to keep the original shape at its extruded section or at its front and back caps. Just thinking about this stirred internal debate within myself and some amount of code rewrites. After some experimentations and observations, I decided that original shape at the caps and widen shapes at extruded bodies looks better for text. It made even more sense after watching greyscale gorilla described the usage fillet caps for giving a strong look to fonts and making edges smoother in C4D.


Interesting strange effect in my WIP bevels

Expansion Around Centroids
So the first approach I jumped in quickly to code was to scale the shapes using its contour points. To know where to scale it around, for which I used the centroid, calculated by averaging all the points of the contour. Works pretty well, but what about holes? Centroid for contour points for holes are also calculated, but instead of scaling in the direction of the shape parameters outwards, they are scaled in the opposite direction inwards. This seems to work pretty well for many shapes until… you take a careful look at the tip of “e”. this strange appearance is due to the concave nature of the shape. Drawing it on paper, its pretty easy to understand why this algorithm would not work on the inside edges of concave shapes.

Expansion via angled midpoints
So approach 1 seemed successful, but failed for certain use cases. How can we solve the problem of the first? One way is to perhaps break down the concave shapes such that only convex shapes remain, but that would have its sets of problems. So I took another approach – to extrude its corners based on the angles between edges. Each new corner will be extruded outwards with the angle averaged or equidistance from both sides of the lines connected to the corner, by the extruded amount. Again, a simple method, and seems to work pretty well, but on careful inspection one would notice strange looking corners especially with sharp edges. Since the expanded corners are determined by angles, there is no guarantee that the bevel amount from the edges are equal throughout and are affected by the shapes.

Corners based on Edges Offsets
In the 2nd approach, 2 connecting edges at each point is required to computed a single bevelled point. The 3rd approach starts out similarly till here, then lines are offset outwards at its edges normals (90 degrees from the edge’s slope) to obtained its extruded edges. From its offset positions, new points are calculated. In pseudo code

For each point,

Find the line connecting to the point
The normal left perpendicularly to this line is used, and

For the line connecting from the point,
the normal right perpendicularly to the line is used.

Offset lines a unit to its associated normals, and find the
intersections of these 2 new lines

Intersection would be the new point.

Now this seems to work much better for most of the cases, since new extruded bevel edges now has a equidistance to the original edges consistently. Unfortunately at sharp converging edges, a point from these sharps corners seems to be missing. In such rare cases, the intersection point of the extruded edge reserves its direction and pushes the point further away from where it should be. The work around for this is to revert to the algorithm of 2nd attempt to prevent such artifacts.

So here is it, at the end of at the bevel attempts, while not 100% perfect, has reached a state which I’m generally satisfied with the results.

If you are any more interested in this, check out the new examples and source on github https://github.com/zz85/three.js/blob/experimental/src/extras/geometries/ExtrudeGeometry.js

Stay tuned for more development updates. :)

disclaimer: i never gotten the chance to take any computer graphics classes, nor came across any papers on this topic, so please feel free to refer or suggest any better approaches if you may know.

p.s. for curved bevels, I used sinuous function of t. wonder if there’s a better way to go about this?