I’ve made something, and probably should have posted and requested for feedback earlier.
I’m not sure if this is in line with your vision, @sgold, but here’s a list of what I did and the reasoning behind it:
I couldn’t justify the complexity and code duplication for decoupling algorithms from the data structure. So instead, I aimed for decoupling the data structure from the data storage.
I implemented Blender’s BMesh: Source/Modeling/BMesh/Design - Blender Developer Wiki
- Hopefully sufficient connectivity information in all cases.
- Support for non-manifold meshes (Edge with more than 2 connected faces. Traversal around T-structures and bowties where two faces share only one common vertex.)
- Support for edges with no adjacent faces (lines, wireframe meshes)
- If required, constraints could be added to only allow for manifold structures.
- Downside is that the extended compatibility introduces more complexity.
- No holes in faces. But the link above suggests that this feature could be added.
- In theory, the euler operators (listed in the link above) should be sufficient to work with the data structure and no knowledge about BMesh is required.
- To use it at the low level, it will require some learning. But when you learn how to handle BMesh in Java, that knowledge can also be used to write Python scripts for Blender.
- Blender code can be used as reference or ported to Java.
For storing properties of the elements (Vertex, Edge, Face, Loop) I implemented a “horizontal object pool”, backed by primitive arrays.
-
The library is basically a wrapper around arrays and additionally provides connectivity information and an API for algorithms.
-
Each property type is stored in an own array. When a new property type is added (e.g. UV coords), a new array is created.
-
The alternative would be to store the properties directly in the element classes (e.g. Vertex.color). This can still work by providing the BMesh object with own factories for the elements.
- However, when storing the properties in the element classes directly, they are set during initialization.
- During initialization it is not known which algorithms are used and what data they require.
- Adding more properties to element classes during runtime would be more difficult and less efficient.
- With arrays, algorithms can generate new per-element properties during runtime. BMeshData takes care of the allocation.
-
The properties are associated with an element type.
- There’s a Vec3Property that is associated with the Vertex class and stores its position.
- Another instance of Vec3Property could be associated with the Face class to store a face normal.
- The property classes use a generic parameter to enforce this association with an element type:
Vec3Property<Vertex> for vertex positions, Vec3Property<Face> for face normals
- That way the program won’t even compile if a property is used for the wrong elements. If it were possible, misuse could lead to runtime crashes or subtler errors.
-
Properties are similar to Java’s reflection API for fields. Accessing a value:
Vector3f val = property.get(vertex);
-
When a new element is created, the arrays are automatically resized if needed (similar to ArrayList).
-
Those arrays can be sent directly to the OpenGL buffers. No need to iterate over the elements.
- This can happen on a per-property basis. For example, if no normals were changed, that property-array doesn’t have to be sent back.
-
The BMeshData class maintains a free-list that stores deleted elements (=gaps in the arrays). When an element is removed, the slots in the array are remembered and reused for future elements.
-
If elements were removed, the array first has to be compacted and the gaps removed before it can be sent back to OpenGL.
-
It would be possible to use OpenGL Buffers directly as the backend for the properties.
-
But using an own array allows the library to work in a separate thread.
-
Benchmarks suggest that for widespread modifications of many elements, it’s faster to copy the OpenGL buffer to a Java array, modify the contents, and then send the array back in one call.
-
However, if modifications are only sparse, it would be faster to directly write to the OpenGL buffers.
-
Planned: Remember dirty regions in the array so only modified parts have to be sent back to OpenGL.
I implemented a simple conversion from a JME Mesh to BMesh that reconstructs connectivity information. I tested different methods for vertex deduplication.
- The comparison paper posted by @sailsman63 above states that the 1-way sorted method was fastest for them.
- For me, the hash based implementation is almost twice as fast in all cases even though it queries the HashMap up to 27 times (3^3 box) per insertion.
- The hash based deduplication is also more versatile since it works incrementally: The mapping is ready again right after insertion.
- The 1-way sorted method first needs to sort all vertices after inserting new ones.
I made a debug visualization that shows the state of the BMesh data structure. Loops (basically fragments of a face) are visualized at the edges of each face. In the pictures below, green means they are connected to an adjacent face.
The Loops follow the winding order of the face. Direction is from the dark end to the brighter end.
- Planned: A visual step-by-step debugger for algorithms to see what it’s doing.
BMesh to JME conversion: Exists rudimentarily in BMeshVisualization.
- Planned: Maintain the index buffer with automatic vertex duplication and only send it to OpenGL when needed.
- Planned: Automatic triangulation of quads and polygons. For repeated modifications, faces could store the triangulation in a property. With a dirty flag only changed faces need to be triangulated again.
Possible applications:
- Programmatic modelling. Create and manipulate meshes in Java depending on parameters.
- Chaining of algorithms.
- Verification, debugging, analysis and manipulation tools, possibly integrated with @jayfella’s plugin dev kit.
- Extrusion along paths (e.g. bezier). Create roads or dynamic meshes like a curved hose.
- Mesh simplification. Removal of features for LOD. Reduce details to normal map.
- Mesh subdivision and smoothing.
- Physics-independent realtime deformation, for example when objects crash into eachother.
- Realtime decomposition, for example when objects explode. Fuzzy edges. Break at thin regions. Repeated breaking.
- CSG / Boolean operators. Union, difference or intersection of meshes without hidden faces.
- Optimize mesh with triangle strips / line strips. Merge coplanar faces.
- Generate uv coords. Texture mapping.
- Alternative to working with arrays/buffers directly. Generate indices, normals, texture coords automatically while working with quads.
Do you have any opinions or hints on the general concept, the API or implementation details?
Any more use cases? Wishlist?
Meanwhile I’ll continue to implement the euler operators and conversion methods.
Code is here: GitHub - FennelFetish/jBMesh
Example of an operator: https://github.com/FennelFetish/jBMesh/blob/master/src/meshlib/operator/ExtrudeFace.java
jme Mesh to BMesh Conversion Benchmark: https://github.com/FennelFetish/BMesh/blob/master/src/meshlib/ConversionBenchmark.java
Buffer Benchmark: https://github.com/FennelFetish/BMesh/blob/master/src/meshlib/FloatBufferBenchmark.java
Results: Buffer Benchmark Results · GitHub
BMesh debug visualization of a torus. Face normals shown as lines.
Same torus with operators applied to all faces: Extrusion, scale, translation
