Making Bezier Surface Patches in SL

I've searched the forums, and other than a few cursory discussions mentioning them I cannot find anything that talks about this subject.

I am very annoyed with the SL editing tools and the building limitations. One of the things that has been on my "to do" list for about six months now is to make a huge, gently curving, looping roadway/racetrack/rollercoaster in one of the island sandboxes.

Trying to build that by hand does not work because of the precise alignments and complex math involved. (I know, because I've tried.)

Meanwhile I know what spline curves are, from Adobe Illustrator. I've fiddled with NURBS just a little. I understand how control point points work. The problem is the math and translating it into actual geometry.

Fortunately it looks like even a math-idiot like me can probably hack something into working by borrowing from the work of others. Here is some code I hacked together using an OpenGL tutorial to get the basics of bezier curve code working:

// Spline creation script, converted from the C++ source from:
//
//  NeHe Productions: OpenGL Lesson #28
//  http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=28
//
// NOTE: I am NOT a mathemetician, nor do I really understand this.
//       This is just a hack to try and make this work.
//         - Scalar Tardis, Oct 2006
//
//  A few simple prims are used to show data in-world:
//    Endpoint ... shows endpoints of each strip
//    Control  ... shows control points on each strip
//    Arrow     ... centered on 0,0,0 rotation, shows relationships
//    Point    ... draws out the curve of each spline

// NOTE: Original C++ code, probably not necessary in LSL
// Adds 2 Points. Don't Just Use '+' ;)
vector pointAdd(vector p, vector q) {
    p.x += q.x;        p.y += q.y;        p.z += q.z;
    return(p);
}

// NOTE: Original C++ code, probably not necessary in LSL
// Multiplies A Point And A Constant. Don't Just Use '*'
vector pointTimes(float c, vector p) {
    p.x *= c;    p.y *= c;    p.z *= c;
    return p;
}

// NOTE: Original C++ code, probably not necessary in LSL
// Function For Quick Point Creation
vector makePoint(float a, float b, float c) {
    vector p;
    p.x = a;    p.y = b;    p.z = c;
    return p;
}

// Calculates 3rd Degree Polynomial Based On Array Of 4 Points
// And A Single Variable (u) Which Is Generally Between 0 And 1
//
// HACK: LSL does not understand p[0] to p[3] so we gotta do
//       this a different way
vector Bernstein(float u, vector p0, vector p1, vector p2, vector p3) {

    vector a = pointTimes(llPow(u,3), p0);
    vector b = pointTimes(3 * llPow(u,2) * (1 - u), p1);
    vector c = pointTimes(3 * u * llPow((1 - u),2), p2);
    vector d = pointTimes(llPow((1-u),3), p3);

    vector r = pointAdd(pointAdd(a, b), pointAdd(c, d));

    return r;
}

vector readarray(integer position, string xpos, string ypos, string zpos)
    {
    vector vec;
    integer offset = position * 7;
    vec.x = (float)llGetSubString(xpos,offset, offset + 6);
    vec.y = (float)llGetSubString(ypos,offset, offset + 6);
    vec.z = (float)llGetSubString(zpos,offset, offset + 6);
    return vec;
}

default
{
state_entry()
{
    llSay(0, "Ready.");
}

touch_start(integer total_number)
{

    // HACK: LSL does not understand storing the control points as
    //        p[0] to p[3] so we gotta do this the hard way
    string bezx; string bezy; string bezz;
    
    // 16 control points, in four strips of four:
    // begining point, beginning control, ending control, ending point
    bezx = bezx + "-00.750"; bezy = bezy + "-00.750"; bezz = bezz + "-00.500"; //00
    bezx = bezx + "-00.250"; bezy = bezy + "-00.750"; bezz = bezz + " 00.000"; //01
    bezx = bezx + " 00.250"; bezy = bezy + "-00.750"; bezz = bezz + " 00.000"; //02
    bezx = bezx + " 00.750"; bezy = bezy + "-00.750"; bezz = bezz + "-00.500"; //03
    
    bezx = bezx + "-00.750"; bezy = bezy + "-00.250"; bezz = bezz + "-00.750"; //04
    bezx = bezx + "-00.250"; bezy = bezy + "-00.250"; bezz = bezz + " 00.500"; //05
    bezx = bezx + " 00.250"; bezy = bezy + "-00.250"; bezz = bezz + " 00.500"; //06
    bezx = bezx + " 00.750"; bezy = bezy + "-00.250"; bezz = bezz + "-00.750"; //07
    
    bezx = bezx + "-00.750"; bezy = bezy + " 00.250"; bezz = bezz + " 00.000"; //08
    bezx = bezx + "-00.250"; bezy = bezy + " 00.250"; bezz = bezz + "-00.500"; //09
    bezx = bezx + " 00.250"; bezy = bezy + " 00.250"; bezz = bezz + "-00.500"; //10
    bezx = bezx + " 00.750"; bezy = bezy + " 00.250"; bezz = bezz + " 00.000"; //11
    
    bezx = bezx + "-00.750"; bezy = bezy + " 00.750"; bezz = bezz + "-00.500"; //12
    bezx = bezx + "-00.250"; bezy = bezy + " 00.750"; bezz = bezz + "-01.000"; //13
    bezx = bezx + " 00.250"; bezy = bezy + " 00.750"; bezz = bezz + "-01.000"; //14
    bezx = bezx + " 00.750"; bezy = bezy + " 00.750"; bezz = bezz + "-00.500"; //15
    
    
    integer count;
    vector mypos = llGetPos();
    rotation myrot = llGetRot();
    vector primpos;
    
    vector begpntnorm;
    vector begctlnorm;
    vector endpntnorm;
    vector endctlnorm;

    vector begpnt;
    vector begctl;
    vector endpnt;
    vector endctl;

    float step;
    
    //// point 0 and 3 are endpoints. I designate 0 as begpoint, 3 as endpoint
    //// point 1 is the control for 0
    //// point 2 is the control for 3

    llSay(0,"Drawing Control Points...");
    for (count = 0; count < 4; count++)
    {
        begpntnorm = readarray(count * 4 + 0,bezx,bezy,bezz);
        begctlnorm = readarray(count * 4 + 1,bezx,bezy,bezz);
        endctlnorm = readarray(count * 4 + 2,bezx,bezy,bezz);
        endpntnorm = readarray(count * 4 + 3,bezx,bezy,bezz);

        begpnt = mypos + begpntnorm * 5;
        begctl = mypos + begctlnorm * 5;
        endctl = mypos + endctlnorm * 5;
        endpnt = mypos + endpntnorm * 5;

        llRezObject("Endpoint",begpnt,ZERO_VECTOR, ZERO_ROTATION,0);
        llRezObject("Control" ,begctl,ZERO_VECTOR, ZERO_ROTATION,0);
        llRezObject("Control" ,endctl,ZERO_VECTOR, ZERO_ROTATION,0);
        llRezObject("Endpoint",endpnt,ZERO_VECTOR, ZERO_ROTATION,0);

        // This section does not work. the rotations are all wrong.. ??        
        llRezObject("Arrow",begpnt,<0,0,0>, (llEuler2Rot(llVecNorm(begpnt - begctl)) ),0);
        llRezObject("Arrow",begctl,<0,0,0>, (llEuler2Rot(llVecNorm(begpnt - begctl)) ),0);
        llRezObject("Arrow",endctl,<0,0,0>, (llEuler2Rot(llVecNorm(endpnt - endctl)) ),0);
        llRezObject("Arrow",endpnt,<0,0,0>, (llEuler2Rot(llVecNorm(endctl - endpnt)) ),0);

        for (step = 0; step <= 1; step = step + .1)
        {
            primpos = Bernstein( step, begpntnorm, begctlnorm, endctlnorm, endpntnorm);
            llRezObject("Point",<mypos.x + (primpos.x * 5),mypos.y + (primpos.y * 5),
                mypos.z + (primpos.z * 5)>,<0,0,0>,<0,0,0,0>,0);
        }        
    }

}
}

The next big step (at least for me) is showing the relationship of control points to end points. They may be further apart than 10 meters for big builds, and so I am trying to just put arrows on the endpoint and the control point, and make the arrows point at each other to form an imaginary line.

But so far my attempts at rotating the arrows to point at each other is not working, and I don't see how to fix it using llRezObject rotation.

This is quite annoying because I am going to HAVE to figure this out if I am going to rez up the flat pieces that join all the lines together to form a surface.

I can already see that the rezzed prims are going to need to communicate with the main prim, so they can self-resize and reshape using llSetPrimitiveParams, though that is still way outside of my LSL-coding skillset..

Mostly I am writing this code in an attempt to get the attention of the forum's math experts. Would ya mind helping me fix up this mess?

The more I look at this sample code, the more confused I get about it. The way this sample code works is to draw four parrallel bezier curves that each slope up and down.

The original C++ code then interpolates points between strips and generates triangles. Yes... I see that.

However, it seems very strange to be using 8 end-points and 8 control-points in parallel to make "one" patch. This does not seem to be the simplest way to store and calculate a patch.


The sample method:

p01----p02----p03----p04

p05----p06----p07----p08

p09----p10----p11----p12

p13----p14----p15----p16

As far as I can tell... P05 is an endpoint for strip #2, but could also be the control point for p01 in strip #1, if the data were rendered like this instead:

p01    p02    p03    p04
 |      |      |      |
p05    p06    p07    p08
 |      |      |      |
p09    p10    p11    p12
 |      |      |      | 
p13    p14    p15    p16

This 16-point method is just too confusing for me.


It seems to me that the simplest bezier patch would really just use four corner-points that are interpolated across both the x and y axis together, and use two control points for each corner-point:

p01---p02         p03---p04
 |                       |
p12                     p05


p11                     p06
 |                       |
p10---p09         p08---p07

This to me seems the simplest and most rational patch layout.

Though as a non-mathemetician I don't know if this is true or not.

Some more thinking on this...

With the 12 point method, I'm essentially simplifying the controls, which will restrict the shapes the patch can have but make controlling it easier.

In order to calculate the patch, it still needs 16 points to work with. The missing four in the center area would need to be be an average of the position of the other corner control points:

p01---p02---p03---p04
 |                 | 
p12   (a)   (b)   p05

point (a) = (p02 + p12)
point (b) = (p03 + p05)

I do not know if point (a) should be perfectly aligned on the x,y,z grid, or tucked in closer to p01 as if on an ellipse between p02 and p12. I will have to play with it..

For a patch with the control points within 5 meters of the corner, it would be possible to use a single prim at each corner to store the data for the corner point and its two control points.

A thin hollow rectangle could do the job nicely.... and the normal client move/rotate editing controls could be directly used to move/rotate the corner and control points.

Moving along to eventually chaining two patches together, the two adjacent patches share two corner points, so only six prims are needed to store/edit the data for both patches.

(prim)--(prim)--(prim)
   | patch | patch |
   |   1   |   2   |
(prim)--(prim)--(prim)

By stitching four patches together to form a sheet, nine of these prims can store the corner and control point data for all four patches.

(prim)--(prim)--(prim)
   | patch | patch |
   |   1   |   2   |
(prim)--(prim)--(prim)
   | patch | patch |
   |   3   |   4   |
(prim)--(prim)--(prim)

The more I think about this the more I like the idea of using prims to store/control patch data. They have effectively become the same as a handle in any drawing program I've ever used.

Hmm, can a prim know when it has been edited? If a prim can know if it has been edited, then it'd be possible to dynamically update a large grid of surface patches. (And if it cannot detect an edit, people could just touch it after editing it.)

Lets look at my last bit of ASCII art, and update it further....

(P000.003)------(P001.003)------(P002.003)
     |               |               |
     | patch 000.002 | patch 001.002 |
     |               |               |
(P000.002)------(P001.002)------(P002.002)
     |               |               |
     | patch 000.001 | patch 001.001 |
     |               |               |
(P000.001)------(P001.001)------(P002.001)        (Controller)
     |               |               |
     | patch 000.000 | patch 001.000 |
     |               |               |
(P000.000)------(P001.000)------(P002.000)

Startup:
Controller shouts on channel: "Control Points REPORT!"
P002.002 shouts: <38.50000, 145.50000, 21.75000><2.50240, 4.10051, 0.25000>
P002.001 shouts: <38.50000, 136.43483, 21.75000><2.50240, 4.10051, 0.25000>
P000.002 shouts: <25.08829, 145.50000, 21.75000><2.50240, 4.10051, 0.25000>
P000.001 shouts: <25.08829, 136.43483, 21.75000><2.50240, 4.10051, 0.25000>
P001.002 shouts: <32.75000, 145.50000, 21.75000><2.50240, 4.10051, 0.25000>
P001.000 shouts: <32.75000, 128.43704, 21.75000><2.50240, 4.10051, 0.25000>
P002.000 shouts: <38.82343, 128.43704, 21.75000><2.50240, 4.10051, 0.25000>
P001.001 shouts: <32.75000, 136.43483, 21.75000><2.50240, 4.10051, 0.25000>
P000.000 shouts: <25.41172, 128.43704, 21.75000><2.50240, 4.10051, 0.25000>
(etc)
Controller captures prim data in a table
- Out of order data works because the prim name defines its array location
Controller draws each patch using the prim data
Controller goes into idle listener state.

Live Editing:
User edits size of prim P001.002
User touches prim to start update
P001.002 shouts: UPDATED <32.75000, 145.50000, 21.75000><3.50240, 4.10051, 0.25000>
Based on the prim name P001.002, Controller needs to refresh these patches:
- Patch 000.001
- Patch 001.001
- Patch 000.002
- Patch 001.002
Controller goes back into idle listener state.

Ahhh... I see a potentially faster, better way. Each patch is made up of a grid of prims that need to move around anytime the control points change.

Since they'd already need to listen for commands from the master prim, I can probably distribute the code to update positions across each individual prim in the patches. This would parallelize updates and speed up the movement to the new alignment.


BUT, this is going to be very listener heavy... each patch will have a minimum of 9 patch sections (assuming I can use squares rather than triangles to pull this off -- otherwise I need a minimum of 18 triangles per patch), plus an average of 3 control points per patch.

A nicely curving racetrack with scooped sidewalls is going to be 3 patches wide by maybe 20 patches around, which is a minumum of about 720 listeners across all surfaces. I have no idea, but this sounds very high and may adversely impact sim performance.

Currently I just build to make stuff work in sandboxes without regard to prim limits. (I'm only learning after all.) But 720 listeners - minimum - sounds pretty high up there.


But once the track is in place and properly positioned, it can be "baked" -- the control points can delete themselves, and the individual surface listeners can turn themselves off leaving the prims frozen in place..

Perhaps it'd be possible to "build and bake" a track in small sections, to keep the listeners down, with perhaps just 3-6 patches active at any given moment. Once baked, the next patches rezz up and the build continues.

After spending about 9 hours trying to work out the basics of message passing plus another 9 fiddling with triginomtry math problems, I managed to put together a basic four-handle bezier patch-maker. It kinda sorta works, but there are some corner calculations I need to work on correcting.



But at least the basics with movable in-world control handles is working.

That looks pretty good, but yeah, it's going to be less primmy later on?

This is a test, this is only a test. I am hoping to use a single flat prim up to 10x10 meters for large flat areas, though the bigger they get the less smooth the curves will be.

Rectangular prims can work as long as the patch curves are mostly linear in at least one direction. When you start rotation the corners on Z to flare it in and out.. I don't think a rectangle prim is going to be able to skew/taper enough to match it.

Though the next challenge is determining how exactly to get rectangular prims to move around and align so there are now gaps between prims. I'll probably have to pick apart the various free "ShapeMaker" tools to try and figure out how that math works.


I'm a little afraid to post the code at this point because it is probably horrific and breaks all sorts of rules I don't know about because I don't know LSL well enough yet.

On the bright side. You will by the time you are finished with this project

Ahem.

Well, I came to the conclusion that using prims as handles actually does not give the flexibility and control needed to make this work. And actually it appears to be making the mechanism MORE complicated than if I just use individual prims for the control points.

So I am scrapping the previous system and going with a full grid of 16 control points. The big problem here will be keeping track of what control point is associated with what patch, so I've decided to number and color-code them with alternating black/white for each patch.

Here's the build so far with all control points completed, showing two patches and all the control points I have built. I don't need to make any more than this, and you may notice there are many with the same markings even in this build...

http://img527.imageshack.us/my.php?image=twopatchesv205se9.jpg

So this route might not be so complicated after all.