Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Drawing a long 3D tube #905

Closed
ashawthing opened this issue Dec 14, 2011 · 85 comments
Closed

Drawing a long 3D tube #905

ashawthing opened this issue Dec 14, 2011 · 85 comments
Labels

Comments

@ashawthing
Copy link

@ashawthing ashawthing commented Dec 14, 2011

What is the easiest way to draw a long 3D tube that follows a 3D path.

I have a collection of 3D points that represent a route through my world and I want to highlight it. If I draw it as a THREE.Line it comes out 1 pixel wide which is impossible to see, so I want it as a 3D solid.

I tried extruding a shape along a path but that has a couple of issues - the path is defined in 2D and the shape (which is also 2D) doesn't rotate as it is extruded so I get thin points in my solid.

@mrdoob
Copy link
Owner

@mrdoob mrdoob commented Dec 26, 2011

Oh... uhm...

@zz85: I guess the shape extrusion should tilt the shape every step in the direction the step is extruding?

@zz85
Copy link
Contributor

@zz85 zz85 commented Dec 28, 2011

right now extrudes only extrude perpendicularly only its z-axis, that's why only a 2d path is needed.

extruding with its angle adjust + via a 3d path is a feature that I hope to add sometime... (if i could finish my current demo first :S)

however, i think its possible to have a thick line with custom attributes. see http://alteredqualia.com/three/examples/webgl_custom_attributes_lines.html and #681

@tylorr
Copy link

@tylorr tylorr commented Mar 5, 2012

I would also really like this functionality. If is not implemented yet do you know of a simple-ish way of doing it by hand (custom vertices for a cylinder maybe)?

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 6, 2012

hmm.... I almost couldn't remember how ExtrudeGeometry's extrude path would work, so I wrote a simpler THREE.PathExtrudeGeometry with a SplineCurve3.

http://jsfiddle.net/bpSU3/

See if this extrusion works, I can probably tweak THREE.ExtrudeGeometry to work the same way.

@tylorr
Copy link

@tylorr tylorr commented Mar 6, 2012

This is great, but I also need its angle to adjust as it is extruded

EDIT: So would that involve at each step along path calculate rotationMatrix and then multiply each point in the shape by that matrix?

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 6, 2012

could you explain what is its angle adjusted as its is extruded, or are
there any examples?

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 7, 2012

@zz85 The way to do this is to hack THREE.TorusKnotGeometry.

I think what @miningold is talking about is he wants each ring to be orthogonal to the tangent vector of the centerline.

One just needs to replace the getPos() function in TorusKnotGeometry.js. with a custom callback.

Well... then there is the issue of open vs. closed ends... and whether it is a closed or open path or not.... :-)

@tylorr
Copy link

@tylorr tylorr commented Mar 7, 2012

Wow, thanks, I didn't think about that, I'll give it a try.

My paths are going to be closed, and I think I can figure something out for the ends.

EDIT: My paths are going to start at some point A and end at some other point B... not sure if that is called closed or open.

@tylorr
Copy link

@tylorr tylorr commented Mar 7, 2012

Alright I am making some progress but I have run into two problems:

  1. I am getting a twisting effect if my path is bent at all
  2. If any point along my path is the zero vector then the tube collapses to a line

I don't have enough experience with trigonometry to identify what is causing these probelms. So help (and explanations) would be lovely.

Here is a link to what I have:
http://jsfiddle.net/miningold/L6wuG/5/

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 7, 2012

Here is a fix, sort of. http://jsfiddle.net/L6wuG/6/ . This fix may prevent the twists.

This is a tricky problem, and it will take work to make it production quality, but perhaps it can work for your purposes.

Kinks will be a problem. A path that runs vertically will be a problem, too. Good luck. ;-)

@tylorr
Copy link

@tylorr tylorr commented Mar 7, 2012

This is awesome thanks.

I am ok with the kinks, but I definitely will need the path to run vertically. Do you have any suggestions for fixing this, or somewhere I could look (I don't know how to even phrase this for a google search).

EDIT:
So I figured out the problem has to do with the normal vector. So if the tangent vector is pointing straight up, should I set the normal vector to something like 1, 0, 0 or -1, 0, 0?

Another problem is when the tangent vector transitions from positive x-values to negative x-values (if z is unchanging). This causes the bitangent vector to point in the opposite direction. The problem is I don't know how to detect that in 3D space (when z is changing).

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 7, 2012

Sorry, no other ideas at this point. I think your time is better spent understanding the 10 or so lines of code that calculate the variable pos, so you will understand what the problem is and why kinks and twists happen. It's just geometry.

At that point you will be in a better position to come up with a specific solution for your particular situation -- even if it doesn't work in the general case.

@tylorr
Copy link

@tylorr tylorr commented Mar 7, 2012

Alright, I've worked on it a bit more. I've gotten close, but every time I fix one edge case, another one appears.

Here is my progress:

http://jsfiddle.net/L6wuG/10/

The interesting thing is if I go back to setting the up vector to p1 + p2 then almost all of my problems disappear:

http://jsfiddle.net/L6wuG/12/

I've determined that the problem with up = p1 + p2 is when p1 and p2 form a straight line through the origin. This makes up and tangent equal, which then screws up the cross products.

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 7, 2012

Yes, I know. But congratulations on your progress! I tried hacking something up myself, but no answers...

Setting up = p1 + p2 worked for the torus knot because it wraps around the origin and never passes through it.

If you are creating closed curves, can you restrict them to wrapping the origin and use the same trick?

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 7, 2012

okay, starting to understanding what you guys are saying :D

@miningold you can try THREE.ClosedSplineCurve3 for a closed tube :)

@tylorr
Copy link

@tylorr tylorr commented Mar 7, 2012

I am going to be using open curves, so I can't use that hack I guess

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 7, 2012

oh okay i understand, the "closed" here again refer to different things >.<

@tylorr
Copy link

@tylorr tylorr commented Mar 7, 2012

Alright to clear things up, I don't want my curve to loop. I want it to
have a start and an end.

@tylorr
Copy link

@tylorr tylorr commented Mar 8, 2012

So I found a good enough solution.

http://jsfiddle.net/L6wuG/18/

I am using up = p1 + p2, then I find the binormal (previously known as bitan). If the binormal is equal to the zero vector then I set the binormal to the previous binormal. It will cause a twist but it prevents the tube/pipe from collapsing.

@tylorr
Copy link

@tylorr tylorr commented Mar 8, 2012

Also, I discovered that this techniques is a slight variation of the Frenet–Serret formulas

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 8, 2012

@miningold Your fiddle collapsed on me.

Here is a hack. http://jsfiddle.net/L6wuG/19/. It looks like it will work. It tries to prevent twisting by using the normal computed for the previous ring. Have a look. No guarantees, though.... Provided just in the interest of helping you... :-)

@tylorr
Copy link

@tylorr tylorr commented Mar 8, 2012

@WestLangley This is awesome, thanks. I would never have thought of it.

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 8, 2012

looks great! i've gotta learn about those FrenetSerret formulas sometime!

@tylorr
Copy link

@tylorr tylorr commented Mar 8, 2012

@WestLangley I believe the hack you provided will also break if p1 and p2 end up being parallel for the very first iteration.

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 9, 2012

@miningold It was only proposed to get you through the night. It is not production quality.

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 9, 2012

finally i managed to wrap my head around those Frenet–Serret and TNB frame stuff!!

Its seems like all those twists are caused by some flipping of normals to the tangents of the cat-mull rom splines.

The solution, like what was done, uses the moving Frenet frame technique - pretty cool :)

I've modified the fiddle again, my approach is to use the derivative of the normalized tangent for the 1st iteration, then use the moving Frenet frame. I hope this works better.

http://jsfiddle.net/4NvBK/

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 9, 2012

Hmm, actually I'm not certain that solves the first iteration problem.

This version uses a arbitrary referencing binormal for the first iteration.

http://jsfiddle.net/mcvdx/

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 9, 2012

Seems like the referencing frenet frame method is also called the Rotation Minimizing Frames (RMF) :)

http://research.microsoft.com/en-us/um/people/yangliu/publication/computation%20of%20rotation%20minimizing%20frames.pdf

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 9, 2012

@zz85 You are correct. This has been a long-standing problem.

Check out this: http://www.cs.cmu.edu/afs/andrew/scs/cs/15-462/web/old/asst2camera.html

It is the same concept I proposed in my hack #19, which seems to work, except for edge effects.

Here it is again: http://jsfiddle.net/EBtfS/

Maybe the CMU method will work better -- I havent't had time to investigate...

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 9, 2012

@WestLangley yes, the CMU's method is the one I used for my last 2 fiddles (oldB for the previous binormal:)
which is simpler (doesn't compute difference of tangent at current point and previous point)

Nice debugging arrows :) I was writing my helper arrow methods just now for investigating why frenet frame were so twisted too.

I think its more straight forward for a tube (as long N and B are perpendicular to T). It will be interesting once we add custom shapes for path extrusion.

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 23, 2012

nice work @WestLangley ! i see some geometry gymnastics going on :)

i've started to merge your changes and would be updating the examples and check if its working well..

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 25, 2012

@WestLangley i update my example a little to play around with the extrusions.

zz85/three.js@70ee0cf...72f462e

somehow the closed end doesn't stitch in certain cases, but i'm not too sure...

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 25, 2012

@zz85 you have 2 forms of the variables closed and debug -- with and without v at the end.

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 25, 2012

@WestLangley i've fixed the checkbox issue. some shapes work well, but some shapes doesn't...

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Mar 26, 2012

@zz85 Your closed variable is FALSE in every call to the TubeGeometry constructor.

@zz85
Copy link
Contributor

@zz85 zz85 commented Mar 26, 2012

nice catch @WestLangley ! turns out that the browser seems to be overwriting the closed variable. problem fixed after changing it to closed2

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 1, 2012

now that I'm using TubeGeometry internally in ExtrudeGeometry, does it make sense to refactor the TNB calculations so that they can be shared in both classes, and potentially for camera on spline which requires stabilization?

Perhaps...

var frames = new THREE.SplineFrames(spline, segments, closed);
var tangents = frames.tangents[];
var normals = frames.normals[];
var binormals = frames.binormals[];

Somehow I'm still a little torn about how the initial normals should be computed for spline extrusion - the orientation effects are perhaps more obvious for a shape extrusion compared to a tube extrusion. Perhaps we could allow the user to define their initial normal plane? Then again maybe more use cases might help, creating too large a shape extrusion geometry might also not be practical due to the large amount of vertices and faces involved.

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Apr 2, 2012

@zz85 The parallel transport frames logic in TubeGeometry is very specific to that application. In the case of a camera spline requiring stabilization, that is a similar problem, but will require different logic due to both the initial normal selection and (presumably) the desire to keep the camera level. I wouldn't refactor at this point. Wait until you see how ExtrudeGeometry works out.

And, regarding ExtrudeGeometry, do you have a link to a live example -- or is it in your fork somewhere, and I just can't find it? I'd like to understand where you are heading with this -- and what the issues are...

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 2, 2012

@WestLangley Its in my branch extrude_spline_rebasing https://github.com/zz85/three.js/tree/extrude_spline_rebasing, now I'll also push it to my master.

the link for the the example and ExtrudeGeometry is at here

the parallel transport frames is quite specific, but now they would be used in TubeGeometry, ExtrudeGeometry and used for the camera animation in webgl_geometry_extrude_splines.html

If we do not put it into a new class, we could use still refactor it as a util function like
THREE.TubeGeometry.parrellelTransportFrames(spline, segments, closed); or THREE.GeometryUtils.parrallel(spline, segments, closed);

btw, do you have a homepage or twitter? ;)

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 3, 2012

@WestLangley

I've now done the refactoring to contain TNB calculations in THREE.TubeGeometry.FrenetFrames and have special care that that TubeGeometry and ExtrudeGeometry are not broken. I think this is better because there's less duplication of code, and more also efficient than ExtrudeGeometry to use TubeGeometry internally. Also, if there's another algorithm to calculate the TNBs, one just have to swap out the FrenetFrames() function.

zz85/three.js@ecb2059...bbfb804

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Apr 3, 2012

@zz85 OK. Sorry, I am not able to help with this right now, but I will make sure to have a look.

EDIT: Your changes to TubeGeometry do not look right to me. In particular, line 126 cannnot be commented out.

        // vec.cross( tangents[ 0 ], normal ).normalize();

643a338

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 3, 2012

thanks. strangely enough, i'm not sure how the code got there, but things felt like it was still running. fixed that section of the code now.

zz85@1e1a02d

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Apr 3, 2012

@zz85

i'm not sure how the code got there

Uh, dude, this doesn't sound good to me. :/

What was your rationale for re-entering alternative methods of computing the initial Frenet frame in TubeGeometry? Was the algorithm not working properly?

643a338

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 3, 2012

TubeGeometry should work working really well now. I think I was testing the effects of the initial frame with ExtrudeGeometry's extrude path. For example if you are extruding a smiley face shape along a spline, you might want to orientating the eyes to be facing up. The same algorithm might work well too, I should have tested it a little more...

https://github.com/zz85/three.js/blob/bbfb8044f55e2d6dd0b047eb7286c27204dadd6c/examples/webgl_geometry_extrude_shapes.html#L181

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 10, 2012

@WestLangley what do non-planar means? would it be better to tessellate the tube into triangles like http://prideout.net/blog/?p=44 ?

@WestLangley
Copy link
Collaborator

@WestLangley WestLangley commented Apr 10, 2012

@zz85

what do non-planar means?

The four vertices of each extruded quad face are not in the same plane.

would it be better to tessellate the tube into triangles

I think it would. However, I asked this question in #1664, and I don't think there was a conclusion yet. Maybe you can stir the pot a little. ;-)

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 11, 2012

okay, i could give it a shot implementing tubegeometry with parametricsurface :)

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 11, 2012

tada!! Triangulated TubeGeometry using ParametricGeometry internally...

http://jsbin.com/opebux/3/edit#javascript,live

@mrdoob
Copy link
Owner

@mrdoob mrdoob commented Apr 12, 2012

Looks good! :D

@zz85
Copy link
Contributor

@zz85 zz85 commented Apr 18, 2012

@WestLangley interesting article about perpendicular vectors :) http://blog.selfshadow.com/2011/10/17/perp-vectors/

@ashawthing
Copy link
Author

@ashawthing ashawthing commented Apr 30, 2012

I started this thread at least 4 months ago and I can't believe the outcome of my original message. Brilliant work, I really appreciate it and I'm sure plenty of other people will or do already.

I'm using the tube to highlight a walk route in a walk planner and it almost does what I want it to do. The problem is when the route takes a 90 degree turn (e.g. to cross the road), the SplineCurve3 generates a large arc instead of a sharp turn.

Before I create my own path object which ensures that every interpolated point returned is on the direct path between points can anybody suggest a way of doing what I want without creating a new path type of path?

BTW - I tried duplicating each of my points in the source to SplineCurve3 and this gives me a better looking route with sharper turns but it contains a little loop (knot) at each turn.

@zz85
Copy link
Contributor

@zz85 zz85 commented May 2, 2012

@ashawthing since SplineCurve uses the catmull-rom curve, the bends are not supposed to be sharp. You could try using LineCurve with CurvePath. I not sure about using Path since its more for 2d for now.

@amoffat
Copy link

@amoffat amoffat commented Aug 20, 2012

I know this is a really old issue, but I found a great resource for using quaternions to minimize torsion while retaining periodicity ftp://ftp.cs.indiana.edu/pub/hanson/Siggraph01QuatCourse/quatvis3.pdf

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.