i'll paypal 10$ to the first person who can tell me how to extrude along a path :(

a penny for your thoughts,
i’ve tried everything i can imagine. this is the latest incarnation of my code.

void extrudedNgon(int n, Point3 pathStart, Point3 pathEnd, float length, float radius, float radius2, float rotAngle)
{
if(n<3) return;
Vector3 path;

path.set(pathStart.x - pathEnd.x, pathStart.y -pathEnd.y, pathStart.z - pathEnd.z);
path.normalize();

Vector3 u;
Vector3 v;
Vector3 up;  up.set(path.x,-path.z,path.y);

float m[16];	


u.set(up.cross(path));		v.set(path.cross(u));	

	
m[0] =	   u.x;   m[4] =    u.y;    m[8]  =		u.z;    m[12] = pathStart.x; 
m[1] =     v.x;   m[5] =    v.y;    m[9]  =		v.z;    m[13] = pathStart.y; 
m[2] =  path.x;   m[6] =  path.y;   m[10] =  path.z;    m[14] = pathStart.z;  
m[3] =       0;   m[7] =	  0;    m[11] =		  0;    m[15] =		    1.0;

glMatrixMode(GL_MODELVIEW);
glPushMatrix();

glMultMatrixf(m);....

anyhow like i says first who can give me an answer that works for me is welcome to my money. i got so many projects on the backburner cause i can’t figure this one out. really all i wan’t to be able to do is create a local coord system given either 2 points or a vector and point, and be able to extrude along the z axis. this code gets real close but no cigar. sorry to be so blunt about this. but staring at it is not fixing the problem. and my sincerest apologies to anyone who finds this aproach unkewth or if this is somehow illegal.
much apreciated

Michael

[This message has been edited by wildeyedboyfromfreecloud (edited 03-03-2002).]

What exactly are you trying to achieve?

Do you have access to a copy of Game Programming Gems 2? There is an article in there by Carl Dougan called “The Parallel Transport Frame” that covers this exact subject. Lacking that resource, try doing a google search on “frenet frame”. The basic solution is that your logic needs to carry a coordinate system (a 4x4 matrix) thru your path and each position of the path needs to realign that coordinate system with the path’s new tangent vector. Also try looking into “Calculation of Reference Frames Along a Space Curve” (Graphics Gems), or even “Steering Behaviors for Autonomous Characters” by Craig Reynolds- I think that one can be found on the web somewhere… the problem is the same, just Craig uses it for steering characters rather than extruding along a path.

Good luck.

yeah i know its a frenet frame. i wish i knew if there was some way i could find the origional paper on the internet. there isn’t much about it online. it seems logically my code or something like it i’ve already tried would work just fine. i’m worried that their is something inherently wrong with my camera in my system that has direct access to the worldview matrix. but it doesn’t show anywhere else. i’ve gotten it nearly aligned but just maybe a sign off. i’ve played around with everything and can’t get it to do proper. and i’m worried because i have another project right now that will require the same technique. my colleges professor doesn’t see what is wrong with the algorithm. what i want to do basically be able to construct a transformation matrix from just a point and a vector. or a point and another point. where the up vector or the z axis is that vector origionating at the point.

no i’m just armed with a computer graphics text book and my wits. i can’t imagine why this doesn’t work. could someone just drop me the abolutely necesarry pseudo code. real quick. surely most everyone knows how to do this. i’m pretty embarrased that i can’t honestly. but like i said nothing is giving.

Ya the article on this in the game prog gems 2 book is very good. Try and find this paper, its once of the references in this article and see if it helps.

Hanson, Andrew J., and Ma, Hui, ‘Parallel Transport Approach to Curve Framing,’ Department of Computer Science, Indiana University, 1995.

-SirKnight

i think possibly the problem is. that i’m basically using alot of straight lines temporarilly to simulate trees. everyone seems to agree that the frenet frame approach suffers when it comes to straight lines. this may explain why some of my lines seem dead on while others deviate slightly. but i’m probably very wrong. could it be that it isn’t possible to describe an arbitrary 3D coordsystem with to vectors with out any frame of reference. that doesn’t sound right. but when you think of it the original coord system has no frame of reference. how mystifying and profound. i mean first i was just assuming up as reletively arbitrary, and forming a mutually perpendecular coordsystem around my z axis. because i didn’t really care where the x and y axis were as long as z was right and all was mutually perpendicular. well this didn’t work. so then i thought i should define up as a vector perpendicular to z. which isn’t possible in 3 deminsions. but i figured i could just drop down to two and leave the third alone. this didn’t work either. well i’m going to see what this paper has to say. btw is there any place where all public papers can be found in one place? that would be a nice book mark to have. thanks everyone. ciao

[This message has been edited by wildeyedboyfromfreecloud (edited 03-04-2002).]

i can’t find anything for stationary local coord systems from 2 points. a paper i read for simulating plants suggested a 3D turtle approach to remedy the frenet frame delima. maybe the first and second dirivitive are required to give context to the frenet frame. but i’m probably wrong. let me know if there is any truth to such conjecture if you could thanks

michael

All this frenet frame stuff is way above me at the moment, but don’t you need at least two vectors (then you can calculate a third one) to define an orientation? Make that three for an orientation and position. It doesn’t matter much, how you arrive there, you can also take a quaternion + point in space to get a rotation and origin but I just can’t see how you can define a coordinate system with just a vector between two points.

As I said, this stuff may be well above my little mind …

Vector3 up; up.set(path.x,-path.z,path.y);

If you assume this vector to be perpendicular to path, you’re wrong.
Sanity check
path dot up=xx-yz+yz=xx <- which can’t be guaranteed to be zero, hence not generally perpendicular

A generally perpendicular vector (wrt to path) is for example
up=(path.y; -path.x; 0)
BEWARE! this can evaluate to (0;0;0) which is according to the definition still perpendicular, but entirely useless!

Sanity check:
path dot up=xy-yx+0*z=0

However, I still think what you need is an extra input vector to define your ‘up’, calculation is not going to cut it.

[This message has been edited by zeckensack (edited 03-04-2002).]

Originally posted by zeckensack:
[b][quote]

Vector3 up; up.set(path.x,-path.z,path.y);

If you assume this vector to be perpendicular to path, you’re wrong.
Sanity check
path dot up=xx-yz+yz=xx <- which can’t be guaranteed to be zero, hence not generally perpendicular
[This message has been edited by zeckensack (edited 03-04-2002).][/b][/QUOTE]

reluctantly and half hazardly assumed on the off chance the clouds would part and light would shine upon me is more the fitting word.
i get what your saying. i didn’t really think that trough, keep in mind this is just the code after a lot of piddling so it may not be in its sanest form. what would occur i wonder if up.z was set to 0. i will try that as soon as my code is back to a compilable state. but i imagine that is a lot like using a standard bipolar up vector. bipolar may or may not be the official term.
if it works (0,0,0) could be checked for rather redundantly. but necesarilly because the entire coord system would fall apart under that circumstance… never mind i oculd think of a few esoteric instances when that could occur, or maybe not, i’ll just try and see how it goes rather than bending my brain around it. anyhow i think you are most probably right. well i was going to convert to a traditional skeletal system or interpolating curve system. in which transforms and and first and second dirivitives would be readibly verifiable. now that i recall when extruding along a path in most cad routines probably all requires a an x y or z plane be defined, and probably possibly an arbitrary plane; and since a plane cannot be defined from a line as far as i know i recon it is impossible. well lesson learned the hard way. i wish my text book mentioned this little caveat.
my apologies for not checking this post for consistency.

michael

are you sure about what you said about quarterions. if so i may get my quarterion class back which i had written off as useless
well not likely totally but not worth my time to invest in momentarilly

[This message has been edited by wildeyedboyfromfreecloud (edited 03-04-2002).]

Probably the most useful suggestion here is the 3D turtle approach, which is another means of describing the 2nd technique described in Carl Dougan’s paper (suggested in the 3rd post.) In Dougan’s paper, it’s called the “Fix Up” method (I think).

The basic idea is to start with a coordinate system at your original point and then push that coordinate system along your path.

Each point along your path has a direction vector pointing to the next point. The rotation axis of your coordinate system is the crossProduct of the direction vectors of your current point and the previous. If the axis is zero or either direction vector’s magnitude is zero, then you’re moving in a straight line and you don’t need to modify the coordinate system. But when you have a rotation, your rotation about that axis is “-acos( (currPointDirVec Dot prevPointDirVec) / (currMagnitude * PrevMagagnitude) )”

Everything will work fine until you change the “major axis” of your direction, once you do that your coordinate system will start to twist on you. By “changing your major axis of direction” I need to explain with a simple example:

Let’s say that your path is an “S”; the top part of the “S” is your beginning and it has a major axis of direction that is -X, but when the “S” begins to curve downwards the major axis of direction becomes -Y and the coordinate system begins to twist a little, but when you get to the middle part of the “S” when the major axis of direction is +X your coordinate system will have flipped 180 degrees.

If you’re trying to create any extruded geometry from this path, then your extrusion has pinched itself to a point where the twist flipped 180 degrees.

What to do about that, I have not figured out. I’ve tried various methods, but to no universal solution… If anyone can explain how to prevent that flip I would be quite happy and (I believe) so would the wildeyedboyfromfreecloud.

AND since this is a problem that I’ve been F***ing with on and off for quite some time, I’ll throw in another $10 to the solution provider! ANY TAKERS?!?!?!

[This message has been edited by bsenftner (edited 03-05-2002).]

[This message has been edited by bsenftner (edited 03-05-2002).]

you could probably check for the flipping by keeping track of its behavior and offsetting it when necesarry. i can’t wait to really get back into that stuff. the pinching could very well be a problem. if i have a skeleton and a curve that interpolates the joints then i could check for the pincing via the joint transforms i guess. or reset it back at every joint. ho hum, and i thought this would be a simple ordeal. there has got to be a more computationally efficient or less memory hungry way to do it though. maybe near the leafnodes i will just let them fly solo, i mean they can’t do much damage at that point anyways. thanks for the input.

michael.

[This message has been edited by wildeyedboyfromfreecloud (edited 03-05-2002).]

Hey, interesting approach!

If I understood that right, you start with a defined coordinate frame and matrix mult at each iteration. Right?

Don’t you just have to make sure that your path is tesselated enough, so that no single step exceeds a 90° angle? Or is there some arcane property of the cross product that haunts you?

Or is this maybe another thing where quaternions are the way to go? Axis/angle to quaternion is actually quite a trivial operation …

its probably because the cross product could return a negative or positive perpendicular vector depending upon the given cituation. doing so will flip your coordinate system i imagine. its like when you are computing say the v vector from the cross of the u and and n, a suitable answer could be negative v or positive v. but negative and positive are always relative so its not like you can just take the absolute value of it. you would have to monitor its turning every frame to make sure it doesn’t go 180 degrees probably. or something. but in all honestly i haven’t really thought about it so don’t take my word for it.

quarterions are the algebraic form of an affine transformation matrix. if you are using them inplace of an affine matrix you are probably wasting alot of computing for cameras and local coordinate transformations. but as far as i know a transformation matrix cannot return a heading for a point. but i’m probably wrong. well lets say at least it can’t do it intelligibly. but then i’m probably wrong again.

Well, unit quaternions can only represent rotations, so you’d have to accumulate the translation but you could save some memory. Directly rotating a vector through a quaternion (without intermediate conversion to matrix) takes 21 multiplies versus 9 for a 3x3 matrix. Converting to a rotation matrix takes 27 multiplies (just like multiplying matrices). The good things are

1. low memory footprint, 4 floats against 9 or even 16 (nice if you need to store lots of rotations)
2. multiplying quaternions is actually cheaper than matrices, 16 multiplies versus 27
3. constructing a quaternion is cheaper than constructing a rotation matrix (7 mults, 1 sine/cosine, 1 inverse square root)
4. Slerp!

How’s about this: Using the “-acos( (currPointDirVec Dot prevPointDirVec) / (currMagnitude * PrevMagagnitude) )”
technique, at each new extrusion you may or may not have introduced a pinching rotation into your extrusion… you really don’t know. That’s the gist of the extrusion thru a space curve problem. But you can take the new extrusion shape (circle, hexagon, triangle, whatever…) select one vertex and measure it’s distance from it’s previous self in the previous extrusion. Then by rotating the extrusion shape around the curve, repeatedly measure it’s distance from it’s previous self. The “correct” orientation (spin) for the new extrusion is that orientation that minimizes the distance from it’s previous self. That WILL work, but it is time consuming to spin the shape around testing distances… there’s gotta be a formula or another approach to this problem that does not require iterative testing of each new extrusion!

well i figured out my problem. here is the solution if anyone is interested. how it works is you take the point and vector to form a plane in point normal form. the normal becomes your z axis. then you choose any point in 2D s,t space and the vector from there to your point normalized becomes your x axis. then you just cross x and z to get your y axis. and walla you got it.