User:HooglyBoogly/GSoC2019/Notes

Project Home

This is a work in progress document! It will be updated as I make progress. At the end I'll try to make sure all the information here is correct though.

Modifications

New Inputs

1. Custom profile boolean option
2. Profile curve
3. Vertices at curve nodes option
4. Symmetrical case option?

Custom Profile Struct

There are two options for this.

1. This would be an ordered list of X-Y pairs of nodes on the curve graph and their handle positions.
2. The other option is that there is a suitable storage already associated with the curves that come from the curve builder. And it might be simpler to try to use this existing system.

The second option proved a better path here with the CurveMapping code. The harder part is removing the assumption that the path will be a function, in other words removing the sorting that the code does to the CurveMapPoints. For the sampling this is done by walking down the path of the curve instead of down the X axis. For the drawing I will have to see how the parts below the line are shaded and correct that and remove the sorting as the points are moved around.

Sampling the Custom Profile Struct

Either way the custom profile is stored, it will have to be sampled, both during the construction and finally with the nseg vertices. The sampling is much more complicated with curves because there is no closed form solution for the distance along a curve, it just has to be subdivided and added up. So I'm focussing on straight lines between the points.

The CurveMapping struct contains CurveMap structs that contain CurveMapPoint structs with X and Y positions. I built the ability to travel linearly along the list of points to find the position for the ith segment vertex in 2D. Creating a table of known positions and them sampling it later will probably be important for performance though.

Finding Even Profile Spacing

There may need to be a replacement for set_profile_spacing(). This may necessitate knowing how long the curve is in total and having the ability to travel down the curve a set amount (total length / nseg).

However, there won't be a requirement for even profile spacing if the "Vertices at curve nodes" option is on. This could be a simple case to start out with.

Profile Drawing User Interface

I hope to be able to reuse the existing CurveMapping user interface template to some extend. Hopefully I will be able to make a different mode with the type argument that will draw the UI specifically for a profile curve, but separating it out into separate code would be possible too, and not too bad. I will get advice about that decision there before I progress too far.

The largest difficulty will be changing the profile curve into something that doesn't have to be a function and-- as mentioned above-- sampling that, because this will be completely new functionality for the curve mapping code.

Challenges that came up and how I resolved them:

1. The curve mapping template doesn't draw in the modifier UI.

Piping New Data to Bevel Modifier

There are quite a few files and definitions that have to be modified to accept the new arguments:

1. properties_data_modifier.py: The modifier UI
2. bmesh_opdefines.c: The BMesh operator call for the bevel tool. (Tools must run through another step while modifiers are called directly from the C code)
3. bmo_bevel.c: The bevel exec call
4. bmesh_bevel.c: The obvious one (the actual operator code)
5. bmesh_bevel.h: Just a short header file for the own include
6. DNA_modifier_types.h: Holds the modifier data that's recieved from the UI
7. rna_modifier.c: The types / info for the new properties
8. MOD_bevel.c: Locations and declarations for flags and struct

Adding the Custom Profile Information

After adding the sampled custom profile points (2D) to the ProfileSpacing struct I mentioned below, the question becomes whether the mapping from that to 3D in the Profile struct will need to be different. Because the points I've created are still in the 0 to 1 range, I wouldn't think there would have to be any change in the mapping. The only thing I can think of is that the calculate_profile function which does the mapping divides the profile in to two pieces, which I would need to change.

Regularizing Profile Orientation Along Contiguous Beveled Edges (UPDATE SECTION)

One of the problems I'm introducing with custom bevel profiles is the orientation of the profile. One of the problems is more normal-- as I modify the way that the profiles get built, I might mistakenly flip the indices of the profile vertices, so the connections to the next profile along the line will be flipped, creating a whole segment of messed up geometry.

The other (possibly more problematic) situation is when the code chooses a different orientation for the profile, so the shape is rotated the other direction compared to another profile. The indices could match up or they couldn't, either way the connection to the next profile will not be correct. These two situations I described are likely part of the same problem, and the only way to fix it will be to maintain consistent orientation of the profile along contiguous beveled edges.

(OUT OF DATE:) There are two types of contiguous beveled edges: cycles and chains. I need to write code that travels down beveled edges to find these contiguous sections. As it travels along the edges it will carry over the orientation of the custom profile by making sure it starts at the same side of the bevel, or the new BoundVert that's linked to the last one with an edge. Here's the process:

1. Start at a random BevVert.
2. Travel along each EdgeHalf connected to the vertex, marking which of the BoundVerts the profile will start at when a new vertex is reached.
3. Stop when there is no continuation of the beveled edge, or when the next BevVert has already been visited.
4. As long as there is still another unvisited BevVert, start the process there again, and in the end all of the BevVerts will be visited.

This should give enough information to pick which BoundVert to start building the bevel profile from in build_vmesh. However, I'm not sure how this will interact with intersections of >2 beveled edges. As soon as a beveled edge comes into one of these larger intersections the profile will be messed up to some extent anyway, so maybe I should treat the a >2 way intersection as another stopping point for the travelling code. But then it's not clear that anything would happen on a shape like a cube where all of the BevVerts have 3 incident beveled edges.

If there are many other edges with the same angle to the current edge, should you really even continue at all? So maybe this should just keep track of whether there is ambiguity, and if there is, it will just stop travelling. And it should probably only try to find the best route through a vert when there are less than 4 or so beveled edges comint into it.

Passing Along the Choice of BoundVert for Profile Start

(UP TO DATE:)

Possibly the most obvious idea for how deciding which side of the beveled edge the profile should start on is just by distance to the last profile start. On reaching the next EdgeHalf the new BoundVert that was closest to the BoundVert that was last marked as the profile start would also be marked as the profile start point, and the opposite BoundVert would be marked as the end point. But after looking at this method further, it's clear that this method doesn't work when the sequence of beveled edges curves-- the orientation can flip when the beveled path turns back on itself and the profile start is on the outside of the curve.

This means a more more complicated method will be needed to carry over the profile's orientation to the next edge. The solution I came up with is this (assume we've just travelled to a a new EdgeHalf and we marked one of the last EdgeHalf's BoundVerts as the profile start):

Case 1: Travelling into a BevVert

In this case the last profile start vertex is on the other side of the (full) edge.

1. Choose one of the EdgeHalf's BoundVerts.

2. Visit all BMVerts connected to that BoundVert's BMVert.

3. See if any of the vertices meet these three conditions:

   1. Have a BoundVert
   2. That BoundVert was marked as the start of its bevel profile
   3. That BoundVert was the one we last marked as the start of its profile

4. If the conditions are met, BoundVert selected in part 1 should be the profile's start. If they aren't met, the start should be on the other side.

Case 2: Travelling out of a BevVert

In this case the last profile start vertex is on the other side of the BevVert.

I'm still thinking about this case, but maybe I can travel around the BevVert's boundary edges and check which of the two BoundVert choices is more steps away from the last BoundVert.

 

Backlog

There are backlog items here, along with notes and smaller items tagged with HANS-TODO: in the code.

Here are tasks that I will need to come back to, but I'm passing over for the moment to make faster progress towards the most important goals. The more important are on top.

1. The bevel tool crashes on invocation. (Slots to bmesh-op issue)
2. There is a memory leak of the CurveMapping struct (Where to free it?)
3. Fix the drawing to not assume a X<->Y map in the profile widget
4. Don't sort the list of CurveMapPoints only in a "path" widget
5. Sampling the profile path with curved interpolation
6. Discarding const qualifier into CurveMapping code warning
7. Merge the sampled custom profile points with the normal points when all cases are completed
8. Versioning for old bevel modifiers so the profile curve is filled with a new curve_mapping. Maybe this just needs a check for whether the pointer to the profile curve is null, but right now even opening an old file with a CurveMapping, the pointer goes bad.

Finished Backlog items:

1. ...

 

BMesh Bevel Implementation Notes

Questions

There are questions here, and more questions in the code labelled HANS-QUESTION:, although I generally remove those when I answer them.

• Is there any parallel computation with BM_ITER_MESH? No, there isn't, but it's fast enough without it, at least the speed-up probably wouldn't be worth the effort. Plus the outcome sometimes depends on the order of the calculations so parallelization would be even harder.
• I'm curious about the reasoning for calling build_boundary() multiple times rather than finding the correct parameters for each BevVert first and build the structure properly then. I guess you need to have the structure built to do the calculations anyway. The actually vertices are only created on the first call to build boundary. Anyways the recalculations and optimizations need the initial state created the first time. Essentially it's just the same function doing different things.
• Which code creates the boundaries on the edge of the BevVerts? The boundary profiles are created in build_vmesh, where it seems like most of the mesh is created.
• Does "Custom Profiles" directly conflict with "Only Vertices?" I would think it does. If so, it would be nice to gray out them to gray out each other when one of them is selected. Although I suspect there are other conflicting settings that don't do that currently.
• What case arrises with just two edges coming together at a single vertex? (with the vertex bevel tool). I thought this was the definition of the weld case.
• What is the case called for the middle edge of a two face strip?
• Is there a good way to get the BevVert that an EdgeHalf is connected to?

Important Functions in bmesh_bevel.c

In approximate order of appearance in BM_mesh_bevel()

• bevel_vert_construct: "Construction around the vertex" Clarify what this means

• build_boundary: Creates the list of BoundVerts with their initial positions

• bevel_limit_offset: Finds the biggest that the width can be without colliding into other geometry

• adjust_offsets: Finds the best solution to the graph of bevel width dependencies by solving the cycle and chain cases separately. Rebuilds the boundary structure with the better widths.

• build_vmesh: Creates the BMesh vertexes for both the boundary and the interior of the mesh. Creates a bunch of NewVerts

  • calculate_profile: This is the function that actually gives the coordinate values for the BoundVert's profile. Currently works by sampling the super-ellipse (Also samples at powers of 2 to just beyond the number of segments for the construction of the ADJ pattern)

• bevel_build_edge_polygons: Builds the polygons along a beveled edge

• bevel_extend_edge_data: Used for carrying over edge data from the original mesh to the new geometry.

• bevel_rebuild_existing_polygons: Rebuilds the original geometry that was attached to the bevels.

  • bev_rebuild_polygon: Rebuilds a face that had at least one beveled vertex

• bevel_reattach_wires: Also used for reattaching original geometry, this just for wire edges

• bevel_harden_normals: Largely separate feature to keep the original faces looking flat

• bevel_set_weighted_normal_face_strength: Figure out what face strength is

Storing the Profile Information

The profile information is stored in a couple of places. The first is the ProfileSpacing struct which contains the 2D locations of the vertices in the profile, and also their higher power of 2 counterparts. It's called "profile spacing" because what it originally stored was the result of the calculations for the even spacing along the superellipse function. The ProfileSpacing struct is stored commonly for the entire bevel operation.

Further along in the calculation the profile information is stored in the Profile struct that's attached to every BoundVert. The profile struct stores the 3D coordinates of every location in the profile and other information related to the mapping of the 2D coords into 3D: control points along the profile, and infomation about the plane the coordinates are mapped onto.

Weld Bevel Case

The simplest case for bevel is when just two lines come together at a point and the point is converted into the new bevel profile. This case is detected in build_vmesh when both:

• The number of selected vertices around the BevVert is only 2. (bv->selcount == 2)
• There are only 2 BoundVerts total around the VMesh. (vm->count == 2)

The mesh vert kind M_NONE is used for the weld case, because the only thing that's built is the profile of the edge.

Terminal Edge Case

The terminal edge case occurs when there is only 1 beveled edge coming into a vertex. This doesn't seem to need much work except for giving it the new sampled profile.

One thing that could be a problem is the triangle fan mesh type (for when there are 3 other edges besides the beveled edge). Because the profile could overlap with itself, there may need to be a more complicated solution to fill the end of the profile. Hopefully it's possible to use some existing mesh fill method rather than writing a new one to cap the profiles when.

 

Bevel Documentation Notes

Questions

• How is it possible that a boundary arc has half the number of "rings of quads" as the number of segments? The boundary arc is created in halves, one from each EdgeHalf that connects to it. This strategy works fine when you can assume that the profiles are symmetrical and they will necessarily meet in the middle of the two edges that bound it. Removing this assumption will likely be one of the difficult parts of the problem.
• Why do the bound verts that connect to two beveled edges not have two ebev pointers? It looks like the ebev pointer is just a pointer to the edge counterclockwise from the bound vert, but what is the use of that?
• Why would there be multiple NewVerts in each BevVert if there is only going to be one final vertex at each position anyway?
• The indexing of NewVerts is also confusing. I only see two indexes for each vertex on the diagrams. And I'm not quite sure about the motivation for those choices of indices.
• How much should I internalize the formulas for the new vertex positions in the new vertex positions? At what level of abstraction do you usually work at?
• If the subdivisions steps to create the VMesh give a power of two number of segments, how do you step down to the specified nseg after going past it? There is basically interpolation downsampling that happens after the power of 2 profiles are created. The reason this needs to happen is the subdivision process of building the ADJ pattern.
• I'm finding it difficult to get a good understanding of all the math in the section about solving for the best bevel widths. Is it worth it to spend more time with this? It doesn't seem like my project will touch this part of the code.

Creating the Beveled Vertices

A Boundary Arc is the profile at the end of an edge where it meets a beveled vertex.

Each beveled vertex becomes a BevVert.

Each BevVert contains a bunch of EdgeHalfs which are the edges going into the vertex, and not just the beveled ones. The EdgeHalfs have a counterclockwise order.

After the beveled EdgeHalfs are finished, the BoundVerts are created, and are also linked together in a counterclockwise circular list. Any beveled EdgeHalf will be connected to two BoundVerts.

EdgeHalfs point to BoundVerts, one pointer for each direction left and right. And each BoundVert has two pointers to the bound edge halves as well, one for "first," and one for "last," which use a counterclockwise order.

The BevVert's mesh data is kept in another struct called VMesh, which is mostly an array of new vertices (with their coordinates and BMesh vertex pointer).

Each boundary arc is divided in two and a verte is added to the center of the beveled vert to join them. The mesh is created with a subdivision process where new verts are added in between existing ones (first the face vertices then the edge vertices). The coordinates are changed as more subdivisions happen.

The theta values for parameterizing the superellipse function are precomputed at the beginning to give even spacing. And the subdivision steps use the parameterization too, so powers of two need to be calculated to the number of segments.

Adjusting the widths to maintain ...?

A graph of edge width requirements is created, with priorities for consistent widths in this order: adjacent beveled edges, the two ends of a beveled edge, beveled edges with a non-beveled edge in between, opposite sides of the same beveled edge (which the code ignores).