Freesteel Blog » We have some slicing

We have some slicing

Monday, January 5th, 2015 at 9:00 pm Written by:

It’s been a lot of work, and I need a break. This has now outperformed my target over New Year period moping around Bull Pot Farm while everyone else goes caving.

I am now able to make numerous slices on this impellor model made of 38474 triangles with an angle change tolerance between contour sample points of 18degrees in about 5 to 10 seconds per slice using Pypy (or 80 seconds in Python3). The code is at Use it at your peril. It’s just beginning to work, and the next thing I will do is break it.

Here are some pictures of the results of slicing an impellor shape that’s 20mm in diameter with a sphere of radius 0.2 using the command:

pypy -O –stl=stlsamples/impellor1.stl -v -tswapyz -r0.2 -n52

Slices with ball radius 0.2 with the STL model shown

Offset slices without the STL model so you can see all the internal contours from the ball rolling along the inside surfaces of the model. These internal contours will need to be detected by connectivity and deleted.
View down the top so you can see the inner and outer offset slices of the central cylindrical through-hole.

From my initial profiling, 99% of the time is spent in the two functions MakePointZoneRF() and CutbarRF(). This is fantastic news as this is where all the point-line-triangle distance/offset-intersection calculations are done. And it’s intended to be very GPU-friendly. (I don’t actually have any experience with GPUs yet, but it could happen now I’ve got a real world use case.)

The current code in that area is an embarrassment. I’ve reused the barmesh structure to hold the triangles, which I probably shouldn’t be doing, and boxing it very crudely into some form of boxing so that we don’t need to scan the whole thirty-eight thousand triangles to find the closest approach to a given point p.

A function like DistLamPtrianglePZ(self, p0, p1, p2) shows how much there is room for improvement, because I’m recalculating the triangle normal every time I interact with the same triangle.

I should probably encode all the triangle geometry into a few numpy structures, listing all the points, then listing indexes of points for edges and triangles, with corresponding lists of all the precalculated edge lengths and triangle normals. Then all this data can be dispatched to Cython or PyOpenCL modules to implement those parallel calls to MakePointZoneRF() and CutbarRF() with extreme speed.

Once that’s working, I can get back to the internal structures of the barmesh, which has this kind shape in a single slice.

zoomed in:
The cyan lines are the calculated slice contours, and the white lines are the boundaries of the subdivision cells, with the nodes painted red when they are within the volume defined as points that are less than 0.2mm distant from the model. The cyan contour line cuts cell edges that have a red node at only one end.

Oh, I nearly forgot. Two days ago I hit a horrible snag with some of the parallelism, which I solved with reference to the Four colour theorem.

The basic algorithm is you consider each cell — a connected convex polygon outlined in white with some of the vertices painted red to signify they are inside the area — and consider the piece of contour through it (drawn in cyan).

If the normals at each end of the contour line deviate by more than 18 degrees and it’s not yet too short (see the shoulddivide() function), then we cut the cell perpendicularly to the contour line inserting new nodes on the cell as necessary.

If you do this for two cells that are adjacent to each other, there’s a chance you might insert subdivisions on the same edge. This is difficult to make work with parallel programming if the computation of both insertions were made assuming that there was no insertions already.

However, the four-folour theorem says that I need only four colours to paint all the cells of the barmesh so that no two cells share the same colour. Then if I only subdivide cells of a single colour per iteration, there can’t be any clashes.

I use a greedy algorithm to paint the cells with different colours, as follows:

for cell in allcells:
    cell.colour = -1

for cell in allcells:
    cell.colour = 0
    while cell.colour in [ncell.colour  for ncell in cell.neighbourcells()]:
        cell.colour += 1

The number of colours this uses in practice is up to six. I don’t actually need exactly four colours (which is the optimum), but it’s nice to know that it’s such a small number.

1 Comment

  • 1. Jeff replies at 15th January 2015, 3:24 am :

    hi,Julian,I’m Jeff,a student from china, thank you for posting this,I want to know why you choose Barmesh to represent the triangle mesh, but not a more reliable half edge structure.

    could you give more information about your Barmesh structure?

    Thank you!

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>