Week 21 (December 26)¶
This week I added support for window resizing, which applies to sub-windows.
Added near/far clipping to 3D view drawing code, supporting edges partially behind the view or past the far clip plane. Sounds like detail but perspective drawing didn’t work properly without it.
Also added vertex selection operator which converts view context into a ray which is stored in operator properties. Seems simple too but needed to add vector property functions and macro for unpacking vectors.
Note, some hot days and Christmas took time away from regular dev :).
There are a lot of basics to continue on with, probably continue with window management and basic operators, since there are still quite a few areas that aren’t well defined - such as floating windows (pop-ups, needed for menus), splitting & removing windows.
Also how to split runtime and on-disk data for window management.
- Edit-mesh pointer selection operator RB:f6843dc9
- Add ‘unpack’ macro to avoid expanding in-line RB:ef0b7dc3
- Add vector projection functions RB:c67be126
- Use floating point coords for window sizes (avoids rounding errors with window resizing) RB:e7e48907
- Window resizing support (Initial support for recursive window re-arrangement) RB:8934e07f
- Blend colors correctly when clipping RB:989c0bb1
- Line & vertex drawing now clips between near/far planes RB:fcb8fc6a RB:3e23b907
- Add plane math functions RB:4c4b40e5
- Move global event handlers into window-elements RB:ec2af244
Week 20 (December 19)¶
This week I added initial Wayland support as planned, this took a bit longer then expected (2-3 days), and the method of updating the final image is quite slow however its served its purpose as a way to keep multiple back-ends available. (it will likely be easier to improve performance then write from scratch later on).
I also got basic windowing support started - so there is support for multiple regions for drawing and event handling, tested by adding view navigation modal operators.
Continue, working on the windowing system, more basic operators.
Wrote a small utility for cargo out-of-source builds. A wrapper for
cargoto automatically handle locating build outside the source tree.
(avoids having to configure all my development tools to ignore build files).
Week 19 (December 12)¶
This week I got modal operators working, as well as basic window event handlers which was necessary.
Now interactive view zoom and orbit are working.
Also added color-blended line drawing so partially selected edges can draw, blending the selected vertex with the unselected.
Investigate using an alternative driver to
Mainly to avoid unintended coupling with the behavior of
I’ll look into using
GLFW since its well supported in Rust,
although there is no need for OpenGL, it looks like they are supporting Vulkan too.
Not sure how long this will take, after that I’ll start on a basic, hierarchical windowing system so I can properly test different contexts and per-region event handlers.
- Basic working modal operators, 3D view zoom and rotate. RB:7b193041
- Pass event into invoke function RB:ebf88159
- Use operator properties RB:5eeacc75
- Use color blending for partially selected edges RB:966cec6d
- Add blended line drawing RB:03486e35
- Add color interpolation functions RB:4dfb4ada
- Allow defaults to be used for operator types RB:2310cd72
- Add select toggle & pick operators RB:c90a5f1a
Up until RB:7b193041
Week 18 (December 5)¶
This week I added an initial SDL application which imports the
and passes events into it.
Also got very basic event system and keymap and operators working together together.
Added a sample select-invert tool.
Work on operator API, add modal operators and test some basic view navigation (orbit for example).
Add other simple operators too.
Generally work towards working view-port and mesh editing so it can start to be used.
- BMesh: selection flushing RB:79553dab
- Simple wide-line drawing useful for scaling the interface. RB:f54dee40
- Initial keymap & operators RB:8526e04d
- Remove totsel variables, can be calculated and cached when needed. RB:6d9e1775
option_expand_allmacro & tests. RB:8f9907eb
- Event system (initial work) - just print events. RB:d70f1806
- Windowed SDL application RB:29fb8efa
- Split data creation from window drawing RB:b57e92b5
Week 17 (November 28)¶
This week I joined together the basic components to create a very basic application which adds a mesh, draws it in the viewport and writes out an image.
Also spent some time to get a good clipped line drawing function working, surprisingly I couldn’t find a good, existing implementation of this, ended up modifying code from upainter updating it with some minor improvements with tests in its own git repository. See: bresenham-line-plot-clip-py.
Next week start on an interactive windowed application, basic event system and keymap.
Add basic preferences struct RB:6c177c1e
Move macros into a reusable crate RB:72760da8
Added a line drawing method that can clip within a rectangle. RB:04ea8722
Initial application crate: draws a torus, writes to an image. RB:5a736881
enum_int_macrosfor C line enums, similar to
Add mini png writing crate
Single file uncompressed PNG writer, useful for visualizing test output. RB:fa3a8bda
Add stub application for tests RB:c4b839a3
up until: RB:6c177c1e
Week 16 (November 21)¶
This week I spent time to implement a real iterator for memory pool (as planned) and continued fleshing out the BMesh API.
But otherwise didn’t get as much done as I’d have liked.
Make a start on software rendering, useful for viewport testing.
Possibly add a simple
SDL test application.
- Add obj test exporter RB:35a40731
- Add torus primitive RB:3a1d7d95
- Implement mempool iterator,
PtrMutlike named functions (shorter syntax) RB:018cf068
up until: RB:35a40731
Week 15 (November 14)¶
This week I added more bmesh functions as well as triangulate, using polyfill_2d module.
Continue adding bmesh functions, possibly loop into writing a proper memory pool iterator since currently its first converting to a vector.
Add loop separate tests RB:a51d64d1
Utility macro for tests RB:1b18210a
math lib: add 2d math functions RB:63e44d14
BM_face_triangulatewith tests. RB:cdcff29a
Replace index lookups with raw pointers for the
polyfill_2dtessellation library. RB:053d1e73
Add remaining query functions RB:f6088e31
Support for comparing with wrapped and raw pointers RB:968e67d6
struct_bitflag_implnow supports direct comparison with ints RB:8aa0f488
info_expandmacro, handy utility RB:b78ad2bb
Use ‘Into’ for pointer args which can be constant or mutable. RB:c32cd602
Support for comparing
Add select functions RB:8b0ca16c
up until: RB:a51d64d1
Week 14 (November 7)¶
This week I continued to refine the API and add functionality.
Continue adding more advanced bmesh functions.
Move macro loop execution logic into its own macro RB:7d7a1fe5
BM_faces_joinand related functions
Comments on why
PtrConst.to_mutis needed. RB:b93f881e
up until: RB:b7b5f06d
Week 13 (October 31)¶
This week I got the basics of the bmesh API’s working.
Also spent time on figuring out how to structure macros, modules, tests... etc.
Add more advanced bmesh editing functions.
- Write tool for extracting function stubs from bmesh C code RB:b7b5f06d
- Support vert/edge count functions RB:01156904
- Rewrite macro to support
derive& primitive tests. RB:ced1b9d9
- Port over various minor methods RB:777614a1
- Support topology aware
- Use own type for flags & add macro for defining flags types. RB:515636e8
- Support face-create. RB:45559358
- Move pointer wrapper into its own module RB:81f57b76
- Improve pointer access RB:85c13f5a
- Use pointer convenience wrapper RB:87b17a20
- add initial tests RB:2e175fd8
up until: RB:b7b5f06d
Week 12 (October 24)¶
This week I started porting BMesh from C to Rust, with the initial memory pool module.
Setup basic BMesh API an tests.
up until: RB:dc3ffecb
Week 11 (October 17)¶
I’ve taken 3 weeks off, however I did explore some development I was curious about in this time, albeit in a more relaxed manner.
Start on porting Blender’s BMesh mesh editing API to Rust.
I’d previously noticed that Blender’s range-tree structure wasn’t as optimal as it could be,
set which added/removed items on every range adjustment.
Since a range-tree is a generally useful data structure, and may be useful for keeping track of used memory in a memory-pool for example.
I decided to look into writing a portable range-tree implementation which could be easily ported between languages.
Ported and extended a left-leaning rb-tree to Python with tests, see: btree-mini-py.
Wrote a Python Range-Tree tree with tests, see: rangetree-py.
Ported to Rust, using generic types - so a range-tree can be defined for any kind of number, see: rangetree-rs.
Added memory pool for efficient element allocation, and submitted this as my first package to
crates.io, see: crates.io.
Finally I ported this to C, and committed it to Blender, replacing it’s C++ implementation, giving a ~15% speedup to dynamic-topology sculpting with undo See commit.
Week 10 (October 10)¶
Some time off, see week 11.
Week 9 (October 3)¶
Some time off, see week 11.
Week 8 (September 26)¶
This week I added PNG support, added majority turn policy, split the bitmat tracer into crates and other minor improvements.
Finish up with bitmap tracing, nearly done already. Possibly start on some new project.
- Add debug pass option (Useful for visualizing intermediate steps). RT:c622cfc3
- Add turn-policy option:
BLACK, WHITE, MAJORITY, MINORITY. RT:9eb79d32
- Add initial PNG format support, with
- Split modules into crates RT:069c2c0a
- Add grouping for argument parsing RT:090eee6b
- Use curve smoothing for centerline tracing RT:f529ab79
- Fix error where sign was incorrectly used for ‘offset’ method RT:16384a2f
Week 7 (September 19)¶
This week I discarded the tessellating method of center-line extraction in favor of iterative pixel based thinning.
While extracting center-lines from tessellation worked reasonably well, it didn’t handle joins well and would have needed more work to correct end-points.
Instead I used: 3-D medial surface/axis thinning algorithms. Computer Vision, Graphics, and Image Processing, 56(6):462-478, 1994.
Which is intended for voxels but works for 2D shapes too. The resulting center-lines suffer a little from pixel-aligned stepping which is noticeable on thicker lines, while further work could be done here - I rather get an initial version of this tracing application working first.
Finally, center-line tracing was added as a command line option and integrated, adding support for non-cyclic curves.
Generally keep on finishing things up,
possibly split out some modules into crates,
add support for other image formats besides
- Use skeletonize center line extraction instead of extracting from tessellation. RT:5ab11eab
- Add support for detecting loop-outlines RT:0450cd19
- Exit when handling argument parsing instead of panicking. RT:86b2cc37
- Add scale argument, also handle error in arguments. RT:f5a499b8
--modeargument (outline & center-line). RT:39979421
Week 6 (September 12)¶
This week I looked into getting better quality polygon extracted from the bitmap, before fitting the curve. This is needed since the tangents for curve fitting depend on having a relatively smooth curve.
When performing a close-fit, pixel stair-casing artifacts are visible.
I found an implementation of the “Depixelizing Pixel Art” algorithm, called depixel.
Spent an afternoon looking into this, (ported to Python3 and worked around a bug), but ultimately I found this method is too focused on extracting a shape from low resolution pixel art, which doesn’t work so well to fit higher resolution shapes.
I looked into center-line extraction, since from what I can see - existing open-source tracing programs don’t support this.
While I got it working on a basic level, the method Im using currently gives some annoying artifacts with varying width lines, so I’ll need to look into ways to better find the inner path.
Further investigate center line extraction and (as noted last week), tie up loose ends.
Add triangle beautify, (initial center-line extraction) RT:96dd93d9
Add bitmap tessellation (triangulates from a bitmap outline). RT:26e0d380
Improved polygon smoothing (Avoid loosing volume, keep corners). RT:96c0c8ee
Change policy for diagonally touching pixels
Consider them connected, this could be made configurable. RT:ac402aad
Avoid cloning for threaded calculation RT:1bb4d839
Optimize curve fitting, avoid excess checking RT:15c1b93d
Re-fitting improve split index selection
Use the most distant point in the case of removing the knot. This tends to select the best place to split the curve.
Add a small
argparselibrary to help with argument parsing and print a
Week 5 (September 5)¶
This week mostly went as planned, with curve fitting entirely ported from
curve-fit-nd to Rust and got image loading working
using the simple
PPM image format so arbitrary images can be traced.
Generally tie up loose ends and prepare to make an initial release of the curve fitting tool.
Possibly re-visit polygon from bitmap conversion which works but is a bit rough.
Image reader for the PPM image format. RT:99660fe3
Initial multi-threading support. (Currently duplicates input polygon, need to investigate how to avoid). RT:77031883
Cleanup: de-duplicate recalculation next/prev pairs RT:b57dce08
Cleanup: use a separate array for heap access (Simplifies logic for borrow checker). RT:b9e2e2ae
Support for corner detection RT:c5eb26b7
Simple improvements to polygon pre-processing
- Perform a single subdivision after smoothing. This helps, giving an extra tangent to use when fitting knots.
- Caller defined maximum length threshold, helps to give even density.
Support N-dimensional curve fitting RT:f92556b0
Single-curve fitting support added RT:f69cf5f5
Refit ‘remove’ support RT:1cecaaa5
Refitting now works RT:94032828
Week 4 (August 29)¶
This week I didn’t manage to pull everything together but did manage to get polygon fitting working on a basic level.
It turns out Vladimir Agafonkin’s only works on polygons that have 2 endpoints (not cyclic polygon loops), so I’ll look into some different ways to simplify polygons later, for now I can continue without it.
This week I spent a lot of time to get different parts of the tracing program working together so I could test its working on a very basic level.
By the end of the week I had simple curve fitting working to trace a bitmap, however this is mainly to validate the basics, so I can then finish implementing details and see they work as expected.
This is taking longer then expected since I’m still learning a lot about Rust and how to structure things.
Try to finish off both the curve fitting (which fits a single curve). And re-fitting, which adjusts spline placement over the polygon for an optimal result.
Week 3 (August 22)¶
This week I made a start on my bitmap tracing utility, this is my attempt to create a stand-alone utility in Rust which is useful to other people (not just a toy project).
This is a rough equivalent to Potrace, for now I’m not reading its code, I’ll first put this together figuring out things myself, perhaps I come up with some better/different alternatives, or not, either way it helps with learning. And I rather not do a direct port of Potrace to Rust.
Once its working, I’ll see if its worth following some similar methods to Potrace if they’re an improvement.
This is currently quite messy, but I would like to get something working on a very basic level, I can focus on improving individual algorithms afterwards, once everything works.
I started a new repository for this, called raster-retrace.
Also got basic cubic curve fitting working, but didn’t commit this to a public repository yet, will include in raster-retrace.
Make a version of Vladimir Agafonkin’s line simplification library which supports connected polygons.
To have this working I’ll need a min-heap (binary-heap). Rust’s built-in
BinaryHeapdoesn’t support removal of any element within the heap (only the top), so I’ll need to write a small min-heap for this.
Attempt to pull everything together into the raster-retrace repository,
- raster to polygon.
- polygon smoothing.
- polygon to cubic splines.
Eventually I’ll need to support image loading too, however I’m not so happy with the state of image loading libraries in Rust.
image crate is written for games,
includes filters and editing operations, image writing (which is fine but I don’t need it),
and some formats aren’t fully working,
I’d rather use FFI to access
libjpeg directly since I only need to load data.
Poly filling (2D raster filling)
This was a direct port of Darel Rex Finley’s Efficient Polygon Fill Algorithm.
Improved on the overall performance by avoiding a search on all segments for every y-step. (using a sweep-line with in-out events).
Also back-ported these changes to Blender’s C code, updating its polygon filling to use this method: See Patch.
For 10,000 points I measured the method to be ~11x faster, however rounding the X value slows this down to ~7x.
And for reference: See standalone C99 version.
- Reserve coords + 1, In keeping with original method by Darel Rex Finley. RE:e96b0751
- Rename vars, skip segments out of y range RE:9faaceee
- More efficient removal of points RE:8a6832be
- Improve edge comparison RE:b749fb1b
- Replace node_x with a persistent scan-line RE:ea77b931
- Use events, much more efficient RE:c2d61dc4
- Add tests RE:8fbaf7a7
- Use rounded result so reversing the polygon gives identical results RE:b510317e
- Use immutable reference RE:e0cba838
- Replace tuples w/ fixed sized arrays RE:cd81b34a
Week 2 (August 15)¶
This week I got polyfill 2d tessellation port, of the libGDX tessellation algorithm. (including kd-tree optimizations).
I also wrote a PNG image writer (from scratch), to be easily used in tests.
This took more time then expected since Rust doesn’t include a zlib encoder,
I looked into linking to zlib, which can work but isn’t essential,
In the end I include a zlib encoding logic which doesn’t do any compression,
nevertheless I needed to include checksum methods (
Work towards, bezier curve fitting port, this will have to be broken up into a few steps.
- Loading the image from a file (will likely use existing image crate).
- Convert the image to a polygon. (possibly simplify it?).
- Apply curve fitting algorithm.
- Write it out to a known file format (SVG, EPS...)
Up until RE:c8afa3d7
Week 1 (August 8)¶
This week I started writing some very basic Rust examples, am very much a beginner, so am trying out having basic algorithms work in isolated test cases.
Even though drawing lines and polygons is very simple, looked into implementing them as both callback and iterators.
Write more example tests.
- Port my ear-clipping tessellator to Rust, (including tests).
- Write a stand-alone PNG writing function (using only zlib).
Otherwise, there are some other small experiments to investigate, before tackling bigger projects.
Compared with more popular languages, theres a real lack of existing beginner questions for Rust, I’m also not sure what is/isn’t possible - so asked quite a lot of questions.
Up until RE:fa20ff40