User:Genio84/gsoc2016/Extend progress

From BlenderWiki

Extend

This page will serve to record all my progress regarding the implementation of the Bezier curve "Extend" feature.

Whether you are just checking my progress, interested in Blender development, or would like to begin contributing but don't know how, I'll try to make this page an open window to my mind, so you get a general idea.

Let's begin deconstructing, shall we?

The departure point is a script that can be found here

https://github.com/jimflim/blender-scripts/blob/master/extend.py

Let's take a closer look at it. The "main" function sounds important.

def main(context):

Ok, so this is a function that takes in a variable "context", and does things solely based on it. What is passed to this "context" variable are the contents of "bpy.context", which is basically everything you have in your Blender scene. But we don't want everything! We want the "active_object", that is, the object the user has currently selected:

    shape_ob = context.active_object

There it is. Now the script has two modes: either we extend one endpoint to the nearest intersection, or we take two endpoints and extend them until they meet. Therefore we need to know how many, and which, endpoints are selected, so we can carry our calculations with them.

    sel_spl = [spl for spl in get_selected_bezier_splines(shape_ob) if not spl.use_cyclic_u]

    if sel_spl == None or len(sel_spl) == 0 or len(sel_spl) > 2:
        print ("wrong selection")
        return
    # case of one endpoint selected
    if len(sel_spl) == 1:
        sel_pts = selected_endpoints(sel_spl[0])
        if len(sel_pts) == 2:
            p1, p1_handle = sel_pts
            p1_extend = get_max_extent_2d(p1, p1_handle, get_shape_bounds(shape_ob))
            p2 = nearest_point(p1, get_intersections(p1, p1_extend, shape_ob))
        # case of two endpoints selected on the same spline
        elif len(sel_pts) == 4:
            p2 = intersect_line_line(sel_pts[1], sel_pts[0], sel_pts[3], sel_pts[2])[0]
        else:
            print ("wrong selection")
            return
    # case of two endpoints selected on seperate splines
    if len(sel_spl) == 2:
        sel_pts = selected_endpoints(sel_spl[0]) + selected_endpoints(sel_spl[1])
        p2 = intersect_line_line(sel_pts[1], sel_pts[0], sel_pts[3], sel_pts[2])[0]

First, we get the splines whose endpoints are selected. The program is checking the value of "use_cyclic_u" for each spline that is selected. This is to avoid applying the script to closed splines (does not make sense, extending a closed line).

Then we check the selection. If no splines are selected, or if more than two splines are selected, the program throws an error.

If one spline is selected, we get the endpoints that are selected. The function "selected_endpoints" can return either two or four elements, and that is why the two conditions are in place. If the user has selected two endpoints on the same spline, the function returns four elements. If it only selected one, it returns two. Resuming

• One endpoint selected in one spline
  • The user wants to extend that endpoint to the nearest intersection
• Two endpoints selected in one spline
  • The user wants to extend those endpoints until they intersect.

Finally, if two splines are selected, the user wants to intersect their endpoints.

Then the magic happens. The script calculates "p2", the point of intersection, under the appropriate conditions. Then, all it is necessary is to create the point of intersection, and modify the curves.

    # add point to spline(s)
    if p2 == None:
        print ("no extension found")
    else:
        print ("extended point found on: ", p2)
        if len(sel_spl) == 1:
            if len(sel_pts) == 2:
                bpy.ops.curve.handle_type_set(type='ALIGNED')
                bpy.ops.curve.vertex_add(location=(p2.to_3d()+bpy.context.object.location))
                bpy.ops.curve.handle_type_set(type='AUTOMATIC')
            elif len(sel_pts) == 4:
                bpy.ops.curve.handle_type_set(type='ALIGNED')
                bpy.ops.curve.vertex_add()
                sel_spl[0].bezier_points[0].co = p2.to_3d()
                sel_spl[0].bezier_points[-1].co = p2.to_3d()
                bpy.ops.curve.handle_type_set(type='AUTOMATIC')
        elif len(sel_spl) == 2:
            bpy.ops.curve.handle_type_set(type='ALIGNED')
            bpy.ops.curve.vertex_add()
            if sel_spl[0].bezier_points[0].select_control_point:
                sel_spl[0].bezier_points[0].co = p2.to_3d()
            else:
                sel_spl[0].bezier_points[-1].co = p2.to_3d()
            if sel_spl[1].bezier_points[0].select_control_point:
                sel_spl[1].bezier_points[0].co = p2.to_3d()
            else:
                sel_spl[1].bezier_points[-1].co = p2.to_3d()
            bpy.ops.curve.handle_type_set(type='AUTOMATIC')

Down to C

The above analysis allows us to draw a plan to implement all this stuff in Blender's source code:

1. Get the selected object.
2. Get the selected splines.
3. Get the selected points within the splines.
   1. If one spline is selected, see how many points are selected within it.
      1. If one point is selected, extend it to the nearest intersection.
      2. If two points are selected, extend them until they intersect.
   2. If two splines are selected, intersect the respective selected endpoints.

This shall take a while to do...

(22/05/2016) I added the following code to the bottom of the "editcurve.c" file, where all the curve-related operators are implemented.

/******************** Extend curve operator ********************/

static int extend_curve_exec(bContext *C, wmOperator *op)
{
	Object *obedit = CTX_data_edit_object(C);
	ListBase *editnurb = object_editcurve_get(obedit);
	Nurb *nu;

	printf("Hello there");

	return OPERATOR_FINISHED;
}

void CURVE_OT_extend_curve(wmOperatorType *ot)
{

	/* identifiers */
	ot->name = "Extend";
	ot->description = "Extend selected vertex/vertices to nearest intersection";
	ot->idname = "CURVE_OT_extend_curve";

	/* api callbacks */
	ot->exec = extend_curve_exec;

	/* flags */
	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
}

If you ask me "Why are you setting the ot->flag to that value" I'll simply reply "Because every other function is doing it". Currently I am more concerned with implementing this than with Blender's formalism.

I already managed to get the "Hello there" string to appear on my console, by using space bar search to call the operator, and by adding a button to the interface.

Selecting the splines

The next step is to get the selected splines. The function on the original add-on that does that is the following one.

def get_selected_bezier_splines(shape_ob):
    '''
    returns selected splines
    '''
    s = []
    for i,spl in enumerate(shape_ob.data.splines):
        sel = False
        for bp in spl.bezier_points :
            if bp.select_control_point or bp.select_left_handle or bp.select_right_handle:
                sel = True
        if sel:
            s.append(spl)
    if len(s) == 0:
        s = None
    return s

Therefore the steps are:

1. Cycle through all splines in the current "curve" object.
2. Check if any of the handles are selected.
3. Return the selected splines.

There are other operators which work with the handles we have selected. An example is "Make segment", which adds a segment between two selected handles. Therefore the code for that operator is a good starting point to find how Blender keeps track of the selected splines and handles. The part that matters is

static int make_segment_exec(bContext *C, wmOperator *op)
{
	/* joins 2 curves */
	Object *obedit = CTX_data_edit_object(C);
	Curve *cu = obedit->data;
	ListBase *nubase = object_editcurve_get(obedit);
	Nurb *nu, *nu1 = NULL, *nu2 = NULL;
	BPoint *bp;
	bool ok = false;
	/* int a; */ /* UNUSED */

	/* first decide if this is a surface merge! */

	(...)
	
	/* find both nurbs and points, nu1 will be put behind nu2 */
	for (nu = nubase->first; nu; nu = nu->next) {
		(...)
	}

	(...)

}

That loop engulfs most of the code, so it must be important.

In fact, just writing

static int extend_curve_exec(bContext *C, wmOperator *op)
{
	Object *obedit = CTX_data_edit_object(C);
	ListBase *editnurb = object_editcurve_get(obedit);
	Nurb *nu;
	BezTriple *bezt;
	ListBase *nubase = object_editcurve_get(obedit);

	for(nu=nubase->first; nu; nu = nu->next) {
		bezt = nu->bezt;
	}


	/*  */

	printf("Hello there");

	return OPERATOR_FINISHED;
}

and setting a breakpoint within the for loop, we see that bezt gets defined as the first handle of the first spline that is added! That way we know how to cycle through nurbs. To cycle through the handles, the "bezt++" command is used.

After digging some more through the code (especially under the "editcurve_select.c" file), I found the function select_beztriple, which shows at the lowest level how the selection information is stored. Each BezTriple has three variables, f1, f2 and f3. That function modifies the value of those variables. In fact, using the breakpoint we set previously, we see that selecting different points changes the values of those variables accordingly. There is already a macro which checks if the handles are selected

/* checks if the given BezTriple is selected */
#define BEZT_ISSEL_ANY(bezt) \
	(((bezt)->f2 & SELECT) || ((bezt)->f1 & SELECT) || ((bezt)->f3 & SELECT))

I tried to search the code for a function that would return the selected splines, but I found none. Therefore let's rewrite the above python function in C.

static ListBase *get_selected_splines(ListBase *nubase, int *r_number_splines, bool return_cyclic)
{
	/* receives a list with all splines in a "curve" object
	 * returns the first spline of a linked list with all the selected splines,
	 * along with the number of selected splines
	 * if "return_cyclic" is false, it ignores cyclic splines */

	Nurb *nu, *nu_copy;
	BezTriple *bezt;
	ListBase *spline_list = (ListBase *)MEM_callocN(sizeof(ListBase), "get_selected_splines1");
	int handles;

	for(nu=nubase->first; nu; nu = nu->next) {
		handles = nu->pntsu;
		bezt = nu->bezt;
		while (handles--) { /* cycle through all the handles. see if any is selected */
			if (BEZT_ISSEL_ANY(bezt) && (!nu->flagu || return_cyclic)) { /* this expression was deduced using truth tables */
				*r_number_splines += 1;
				nu_copy = BKE_nurb_duplicate(nu);
				nu_copy->next = NULL;
				nu_copy->prev = NULL;
				BLI_addtail(spline_list, nu_copy);
				break;
			}
			bezt++;
		}
	}
	return spline_list;
}

This function makes use of the most useful thing in Blender: ListBase!

You might be wondering why I am duplicating the Nurb. This was a way I found to make this work. I am not satisfied with it, and I might change it after GSoC is over, because it brings a few problems. The real reason is that a Nurb does not live by itself. It is part of a ListBase, which is the Blender's source built-in linked list. More info on that down below.

Get the selected handles

Once again, there is a function on the original add-on that does this. That function returns a handle to the selected handles, which is indeed useful.

The original function is

def selected_endpoints(spline_ob):
    '''
    > spline_ob:     bezier spline object
    < returns selected endpoints with handle
    '''
    if spline_ob.use_cyclic_u:
        return None
    if spline_ob.bezier_points[0].select_control_point and spline_ob.bezier_points[-1].select_control_point:
        return (spline_ob.bezier_points[0].co, spline_ob.bezier_points[0].handle_right,
                spline_ob.bezier_points[-1].co, spline_ob.bezier_points[-1].handle_left)
    elif spline_ob.bezier_points[0].select_control_point:
        return spline_ob.bezier_points[0].co, spline_ob.bezier_points[0].handle_right
    elif spline_ob.bezier_points[-1].select_control_point:
        return spline_ob.bezier_points[-1].co, spline_ob.bezier_points[-1].handle_left
    else:
        return None

This is already discriminating between use cases of the extend add-on. However, it would be better if what goes into Blender's source can be used by everyone, so let's write a similar function that returns the data (that is, the BezTriple contents) of every selected handle.

After throwing many memory addresses around, I arrived at this

static ListBase *get_selected_handles(Nurb* nu, int *r_num_sel_handles)
{
	/* Takes in the first element of a linked list of nurbs
	 * and returns a ListBase with the BezTriple of the selected handles. */
	BezTriple *bezt;
	LinkData *link;
	ListBase *sel_handles = (ListBase *)MEM_callocN(sizeof(ListBase), "get_selected_handles1");
	int a;

	*r_num_sel_handles = 0;
	while (nu) {
		a = nu->pntsu;
		bezt = nu->bezt;
		while (a--) {
			if (BEZT_ISSEL_ANY(bezt)) {
				link = MEM_callocN(sizeof(LinkData), "get_selected_handles2");
				link->data = bezt;
				BLI_addtail(sel_handles, link);
				*r_num_sel_handles = *r_num_sel_handles + 1;
			}
			bezt++;
		}
		nu = nu->next;
	}

	return sel_handles;
}

There we go. This returns all the selected BezTriple.

However, this is not quite it. It only makes sense to extend the first and the last handles of a spline. However, there is nothing within the BezTriple to give us that information. We can only get that information while going through the spline. Therefore, let's implement the "selected_endpoints" function, as it was on the original add-on.

static void get_selected_endpoints(Nurb* nu, BezTriple **r_handle_list)
{
	/* Takes in a nurb and returns an array with the selected endpoints BezTriple */
	BezTriple *first_bezt, *last_bezt;
	int a;
	r_handle_list[0] = r_handle_list[1] = NULL;

	a = nu->pntsu - 1;
	first_bezt = last_bezt = nu->bezt;

	while (a--) {
		last_bezt++;
	}

	if (BEZT_ISSEL_ANY(first_bezt) && BEZT_ISSEL_ANY(last_bezt))
	{
		r_handle_list[0] = first_bezt;
		r_handle_list[1] = last_bezt;
	}
	else if (BEZT_ISSEL_ANY(first_bezt))
	{
		r_handle_list[0] = first_bezt;
		r_handle_list[1] = NULL;
	}
	else if (BEZT_ISSEL_ANY(last_bezt))
	{
		r_handle_list[0] = NULL;
		r_handle_list[1] = last_bezt;
	}
}

If both endpoints are selected, we get an array with two addresses. If only one is selected, we get an array with a NULL pointer and an address. If none is selected, we get an array with two NULL pointers.

Finishing

Other functions are required to implement the extend tool, but those are mostly mathematical operations.

The final code of the tool can be found in the file editcurve.c.

Curves in Blender's Source Code

Have you ever wondered why things appear in Blender as they do? I never really understood why Bezier curves were added that way (one handle tilted 45 degrees). Well, turns out the creation of default primitives is the perfect place to understand the structure of the code. Therefore, I will make a small interregnum in the implementation of the extend operator and proceed to analyze the curve data structure.

Howard Trickey shared with me a set of notes he compiled on the topic. Some of this analysis stems directly from his work.

There is a lot happening when you hit ⇧ ShiftA, so let's break that down. The function calls are in this order:

1. curve_prim_add(C, op, CU_BEZIER | CU_PRIM_CURVE);
   • calls
2. curvesurf_prim_add(C, op, CU_BEZIER | CU_PRIM_CURVE, 0);
   • which calls
3. ED_object_add_type(C, OB_CURVE, name, loc, rot, true, layer); (with name="BezierCurve")
   • which calls
4. BKE_object_obdata_add_from_type
   • which notes that it is “BezierCurve” and therefore calls
5. BKE_curve_add(bmain, name, OB_CURVE);
   • which in turn calls
6. BKE_curve_init(Curve *cu)

If you start a debugger and follow Blender along these lines, you will be somewhat disappointed by the final function call if you expected to get the Bezier default curve by then. There is even a comment somewhere which states that these functions are only initializing general variables, nothing specific.

The full "Curve" data structure is a little bit too large to add to this page (we are reaching a point where we have more code than text, and that is not the purpose of this page). The values initialized are:

        copy_v3_fl(cu->size, 1.0f);
	cu->flag = CU_FRONT | CU_BACK | CU_DEFORM_BOUNDS_OFF | CU_PATH_RADIUS;
	cu->pathlen = 100;
	cu->resolu = cu->resolv = (cu->type == OB_SURF) ? 4 : 12;
	cu->width = 1.0;
	cu->wordspace = 1.0;
	cu->spacing = cu->linedist = 1.0;
	cu->fsize = 1.0;
	cu->ulheight = 0.05;
	cu->texflag = CU_AUTOSPACE;
	cu->smallcaps_scale = 0.75f;
	/* XXX: this one seems to be the best one in most cases, at least for curve deform... */
	cu->twist_mode = CU_TWIST_MINIMUM;
	cu->bevfac1 = 0.0f;
	cu->bevfac2 = 1.0f;
	cu->bevfac1_mapping = CU_BEVFAC_MAP_RESOLU;
	cu->bevfac2_mapping = CU_BEVFAC_MAP_RESOLU;

	cu->bb = BKE_boundbox_alloc_unit();

If you look at this carefully, with the curve properties panel by your side, you can almost see the correspondence.

Well, turns out, many calls later, we reach the function ED_curve_add_nurbs_primitive, within "editcurve_add.c", which does indeed set the handles as we are used to see them.

Ladies and gentlemen, may I present you, the default Bezier curve:

if (cutype == CU_BEZIER) {
				nu->pntsu = 2;
				nu->bezt = (BezTriple *)MEM_callocN(2 * sizeof(BezTriple), "addNurbprim1");
				bezt = nu->bezt;
				bezt->h1 = bezt->h2 = HD_ALIGN;
				bezt->f1 = bezt->f2 = bezt->f3 = SELECT;
				bezt->radius = 1.0;

				bezt->vec[1][0] += -grid;
				bezt->vec[0][0] += -1.5f * grid;
				bezt->vec[0][1] += -0.5f * grid;
				bezt->vec[2][0] += -0.5f * grid;
				bezt->vec[2][1] +=  0.5f * grid;
				for (a = 0; a < 3; a++) mul_m4_v3(mat, bezt->vec[a]);

				bezt++;
				bezt->h1 = bezt->h2 = HD_ALIGN;
				bezt->f1 = bezt->f2 = bezt->f3 = SELECT;
				bezt->radius = bezt->weight = 1.0;

				bezt->vec[0][0] = 0;
				bezt->vec[0][1] = 0;
				bezt->vec[1][0] = grid;
				bezt->vec[1][1] = 0;
				bezt->vec[2][0] = grid * 2;
				bezt->vec[2][1] = 0;
				for (a = 0; a < 3; a++) mul_m4_v3(mat, bezt->vec[a]);

				BKE_nurb_handles_calc(nu);
			}

Now we are getting somewhere! The information regarding the handles is stored in the variable "bezt". This is a variable with the structure of a "BezTriple" (or Bezier triple). The definition is in the file "DNA_curve_types.h". Looking at the above code, one would guess the handle coordinates are stored in the field "vec". This is a 3x3 array. Some nice soul left a comment explaining what each of the elements of the array are.

 * - vec[0][0] = x location of handle 1
 * - vec[0][1] = y location of handle 1
 * - vec[0][2] = z location of handle 1 (not used for FCurve Points(2d))
 * - vec[1][0] = x location of control point
 * - vec[1][1] = y location of control point
 * - vec[1][2] = z location of control point
 * - vec[2][0] = x location of handle 2
 * - vec[2][1] = y location of handle 2
 * - vec[2][2] = z location of handle 2 (not used for FCurve Points(2d))

However, I would say that the most important part of the above default curve definition is this tiny line:

bezt++;

Took me a while to realize its importance.

So let's break this down. The block starts with a Nurb object ("nu"), and then proceeds to add data to the handles. However the way it switches from the first handle to the second is by incrementing the variable "bezt". This is because bezt is defined as an array with two elements:

nu->bezt = (BezTriple *)MEM_callocN(2 * sizeof(BezTriple), "addNurbprim1");

How Bezier burves are interpolated

If you open the Blender console and write

from mathutils.geometry import interpolate_bezier

spline = C.active_object.data.splines[0]

interpolate_bezier(spline.bezier_points[0].co, spline.bezier_points[0].handle_right,
                   spline.bezier_points[1].handle_left, spline.bezier_points[0].co, spline.resolution_u + 1)

you will get an array with lots of points (if you select the default curve, you will get an array with 12 points).

If you start inputting those points as the coordinates of the 3D cursor, you will notice that these are actually the points of the Bezier curve!

So what is going on under the hood? bpy details aside, the function responsible for these calculations is

void BKE_curve_forward_diff_bezier(float q0, float q1, float q2, float q3, float *p, int it, int stride)

big header! The end result will be stored in p (which should be called r_p, by the way; this shows that this part of the code was written before the style guide), which is an array. Unlike Python, where you can store arrays inside arrays, in C everything is the same array. Furthermore, this function only returns you the points between two handles (that is, four points)!

It works this way:

1. The user has to feed in the x coordinates of points P0, P1, P2 and P3, along with it, which is the resolution of the segment (12, by default), and the stride. The stride is the offset between two consecutive corresponding coordinates. In English, it is the distance in the final array between two consecutive x values, for example.
2. The function calculates all the x coordinates, and stores them in p.
3. The user repeats the process with the y and z coordinates.

Along with this tool, I implemented the following functions that interpolate points of Bezier splines:

• interpolate_all_segments - all points on a given Nurb
• linear_spline_list - all points in a curve object

ListBase

Linked lists are data structures that allow us to have dynamically allocated arrays when we actually have just static ones. While in Python you can simply append elements to an array, in C you have a big 1D array called computer memory, which is also being used by all the other programs in your computer, and where you have all your variables stored in. When you create an array in C, the computer allocates some memory for that array, and that's it! You get what you asked for. If you want to add an element to that array, you can run a command called realloc, but you run the risk of overwriting some of your other variables, corrupting the memory, and causing the program to crash. Another way of crashing the program is by trying to access an element out of the array. In this case, you either get junk (random memory contents) or a segmentation fault. This tells us even another thing. If the computer allows you to read beyond the contents of the array, how are you going to know its length, as in Python. Short answer: you can't, unless you recorded that before.

(One) solution to all these problems: Linked List, or ListBase, as used in Blender.

You can find many information about linked lists on the Internet, so I will only address the ListBase

There is some information about ListBase on Blender's wiki [1], but it is a little bit outdated.

The ListBase data structure is defined as

typedef struct ListBase  {
	void *first, *last;
} ListBase;

that is, a pointer to the first and the last element of the ListBase. These can be any data structure as long as they contain a *next and *prev field. For example, the Nurb data structure

typedef struct Nurb {
	struct Nurb *next, *prev;	/* multiple nurbs per curve object are allowed */
	(...)
} Nurb;

can be added to a ListBase.

For a more general approach, the LinkData structure can be used.

typedef struct LinkData {
	struct LinkData *next, *prev;
	void *data;
} LinkData;

This way, one can store virtually anything inside a ListBase.

There are a series of built-in functions to work with ListBase. To mention a few:

• BLI_addtail - adds an element to the end of the ListBase
• BLI_addhead - adds an element to the start of the ListBase
• BLI_remlink - remove a certain link from the ListBase
• BLI_pophead
• BLI_poptail - equivalent to pop function in Python, for head and tail respectively
• BLI_listbase_count - get the length of the ListBase

and there are many more.

[1] https://wiki.blender.org/index.php/Dev:Source/Data_Structures/Double_Linked_List