Recently, I came across a neat data structure called a pairing heap. Now, if you’re not familiar with the term heap it can sound confusing. That’s because it doesn’t mean much. A heap is basically a set of objects with some kind of ordering that we don’t have an intuitive word for. Discard any notions of a heap as a pile of stuff. Specifically, it is a hierarchical tree (or forest) where each parent has a certain relationship to its children (like being less than them).
Pairing heaps are used for an efficient implementation of a priority queue. A priority queue keeps track of the minimum of a set of objects, so every time you take something off the queue it is always the lowest value. Priority queues are most notably used when implementing Dijkstra’s algorithm to find the shortest path in a graph. A lot of useful algorithms are based on Dijkstra’s algorithm, including one to compute geodesic distances on meshes which is what we are using pairing heaps for.
Pairing heaps are neat because they are simple to implement and perform well in real applications. Specifically, they perform very well in amortized time. Meaning that while an individual operation may take a longer time, the aggregate of all the operations over the entire life cycle of queue is fast. They have similar properties to the more well known Fibonacci heap, but they are easier to code and often perform better.
Pairing heaps have very simple properties. Each heap is associated with an object or value. Each heap also has a set of child heaps. The value of the object is always less than (or greater than) that of its child heaps. That’s it.
The heap has a few basic operations:
min(heap) – Get the smallest value. Easy. Just look at the value at the top of the heap.
merge(heap1, heap2) – Combine two heaps. Add the heap with greatest value to the children of the other heap. Also fast.
insert(heap, value) – Add a new value. Merge the heap with a new heap only containing the new value.
removeMin(heap) – Remove the smallest object. A little more complicated. Recursively merge all the child heaps in pairs. The result is your new heap.
decreaseKey(heap, subheap, new_value) – Decrease the value of an object in the heap. removeMin on the subheap of the value you are replacing. Insert the new value into to top of the heap.
Here’s a gist of an implementation of a pairing heap in javascript
We’ve just released a new Processing 2.0 library for exporting OBJ and X3D mesh files. And it supports color meshes! Now you can export color models for 3D-printing with same commands you use to draw. Get started here: OBJExport library page.
The library works like any PGraphics, such as the PDF library. Simply call
to get the PGraphics for obj export and use regular Processing drawing commands.
I’ve also started to use GitHub to manage the code for this and other projects. You can find the github page for the library here. This page can be used to peruse the source, fork the project or report bugs.
This library is a re-release of an old library I made years ago. I had sort of forgotten about it until I got an email last week from Michael Zoellner of the Interactive Design program at Hof University. Apparently, people are still using it! He wanted to update the library to be compatible with the new Processing release.
At the same time, we’ve started to do some work color 3d printing. However, to get printable models we had to go through some tedious processing MeshLab. So, I took this opportunity to overhaul the library, adding new features like color exporting and fixing some old bugs.
We’re excited to see what the community does with the library. We’re using it to make color 3d-prints, what are you going to do? Try it out and send any feedback to jesse@n-e-r-v-o-u-s.com
The next iteration of the surface meshing algorithm from the previous post is surface remeshing. Surface meshing is the process of taking an existing mesh and generating a new mesh of the same surface. This can be useful in many scenarios — for example, we’re using a 3D modeling program to design a surface that we want to use in a simulation. Unfortunately, the mesh that the modeling software creates isn’t designed for simulation. It might have very big triangles, triangles with distorted shapes, way too many triangles, or other problems. You know, triangle problems. Surface meshing allows us to generate a new surface of roughly the same shape but with a uniform density of points and consistent elements.
The procedure is fairly straight forward:
Begin with an existing mesh.
Generate evenly spaced points on that surface. We do this by generating random points on the surface and discarding any that lie within a certain distance of a point that has already been added. We accelerate this process with a simple spatial partitioning data structure.
Run the Ball Pivot Algorithm on that set of points. The points have no connection to the original surface once they are generated.
You can play with an initial implementation here. Warning: this is very buggy and likely to crash, generate meshes with holes, or create fairly ugly meshes, depending on the settings.
A common problem we come across is needing to make meshes of complex surfaces. This can be done with many different approaches, but regardless of the method, it is often quite difficult. Especially when doing simulations on surfaces, you need a well-behaved triangle mesh, that is one with a controllable density of elements and nicely shaped triangles. This can be done by generating a set of points on that surface and then triangulating them. But triangulating surfaces embedded in 3-space is no simple task. Recently, I came across an interesting approach to this problem which works especially well with generated point clouds called the Ball-Pivot Algorithm. I implemented it in javascript (you should see it running above).
Let’s start with the basic idea of triangulation in 2D. A triangulation of a set of points is just a set of triangles that covers all those points and don’t overlap.
Now not all triangulations are created equal. We want to make triangulations whose triangles are nicely shaped, as close to equilateral as possible. This leads to better numerical stability and convergence in simulations.
This leads to something called the Delaunay triangulation. This is a really neat triangulation defined such that circumcircle of any triangle in the triangulation does not contain any other points. The circumcircle is the smallest circle enclosing the triangle. One thing that’s not entirely obvious is that this triangulation always exists. And the thing that is great about this triangulation is that it maximizes the minimum angle of the triangles. This means it gives us the best shaped triangles we can get with the points we have.
The problem comes when we make the jump from 2D to 3D. We can generalize the idea of Delaunay triangulations to 3D, giving us tetrahedron instead of triangles and circumspheres instead of circumcircles. However, what we want is surface of triangles embedded in 3-space, not a 3 dimensional solid. One way to get around this is called alpha shapes. This is a subset of the 3D Delaunay triangulation but only including faces of a certain size. Alpha shapes can create good surface triangulations; however, it is necessary to compute the full 3D Delaunay, which is complex in computation and implementation as well as numerically unstable.
So in comes the Ball-Pivot algorithm. This algorithm is nice because it works in linear time for points of a constant density, and it is exceptionally cute conceptually. The idea is you have a ball of a certain radius sitting in a triangle. This ball rolls over the edge of the triangle and keeps rolling until it hits another point. Then, that edge and the point it hits make a new triangle which is added to the triangulation, and the ball rolls over a new edge. If you start with a good triangle, such that the ball contains no other points, then the new triangle the ball rolls onto won’t contain any other points either because any point would have been hit before hand. This maintains the Delaunay property! In fact, the ball pivot algorithm produces a subset of an alpha shape.
There are a few caveats. If the curvature and density of the surface points is too high, a larger ball won’t be able to fit in the necessary crevices, missing some points. If the ball is too small, it can fall through large triangles and leave holes. While these issues can worked around, the ball pivot algorithm works best for surfaces with a consistent density of points.
Feel free to look at the code inside, but it is not optimized and not pretty. This was thrown together in 2-3 days, so it definitely lacks polish.
This week I revamped the automatic post-processing of puzzle files. Previously, there was a lot of manual work that had to be done to the file before they were ready to be laser cut. Now, I’ve reduced a lot of that labor and also made it so that the puzzle pieces will be generated with much more consistent details and nubs.
The problems
There are a number of problems that have to be found and fixed by hand. Many of these issues occur around whimsies. Some pieces are generated too small to be a usable piece. Other times pieces get merged during the simulation. This occurs when two pieces which have the same phase grow into each other during the simulation. This can occur because the simulation employs an optimization of only having 5 phases rather than each piece being its own phase. Some areas are just too thin.
Fixing overview
Fixing occurs in two stages. The first part occurs in pixels space before the boundaries have been extracted. This part hasn’t changed. The second stage works in vector space, once everything is represented as polylines. To get from the first stage to the second stage we used a modified marching squares algorithm.
The difficulty
What makes the fixing tricky is that conditions that define what needs to be fixed and how are highly non-local. I cannot simply say nothing can be under X thickness. The more material a connection holds, the thicker it needs to be. Thin areas between two merged pieces need to be split, not thickened. Even thickness is a bit tricky to calculate. Additionally, there can be conflicts where thickening one area makes another too thin.
Marching squares
To explain the fixing procedure in detail, I’ll start at the beginning with the creation of the vector representation. The pixel representation is turned into vectors with a generalized marching squares algorithm that allows for an arbitrary number of states. During this process each point only knows which points it is connected to. There is no notion of pieces having any continuity.
Computing thickness
To compute the thickness of each point, I find the distance to the nearest non-degenerate point. I don’t bother to be concerned with distance to a line segment because the curves are so dense. By non-degenerate point, I mean that points that are directly next to another should not be considered for thickness computation. So for each point I compute a local neighborhood that extends out a certain distance using a depth first search of the neighbors. The points in this neighborhood are considered degenerate.
Minimum thickness computation
To compute how thick a connection needs to be, we need to know how much material it supports. This is estimated by the linear distance along the piece from one end of the connection to the other, rather than trying to compute the actual area. We could compute this distance with a breathe first search, but that would be expensive O(n^2).
Instead, we note that two nearest points must lie within the same piece. This way if we extract each puzzle piece and label each point in the piece with the distance along it starting at an arbitrary point, we can do a simple calculation to get the distance between any two points. It is constant time.
Extracting the pieces themselves isn’t entirely trivial. This equates to finding all minimum cycles in a graph. However, we have a clue that makes this a bit easier. Each point knows the colors of the pixels that is was generated in between, and we can tag them with this information. Because of this if you trace along an arbitrary point’s neighbors that all have the same color, you get a piece. This creates a simple linear time procedure for extracting all pieces.
Thickening
The thin regions are thickened by simply moving a point away from the nearest point, such that it is the minimum distance calculated from the material supported. All points in the local neighborhood of moved point are then marked.
It should be noted that special consideration needs to be paid to boundary pieces, which need to treat the edge of the puzzle slightly differently.
Selective smoothing
All points that have been marked by the thickening process are then smoothed with a Laplacian smoothing procedure. This alleviates any strange geometry that might arise from movement.
These processes of marking, thickening, and smoothing are repeated in a relaxation procedure that resolving conflicting situations when thickening one area overly thins another.
Small and merged pieces
All of these procedures only deal with thin regions. So far, there are no automatic fixes for small and merged pieces. Instead these are marked on export for manual fixing. Merged pieces are heuristically identified simply by their size, which can lead to false positives, but that is easily distinguished by a manual operator. With the pieces already extracted, marking small are large pieces is trivial.
Results
Here are the resulting files. The two marked “extract and mark” are identical and show the output of marking the pieces before they are fixed. Click on them for a larger view.
We’re starting a new tradition at Nervous System of sharing the work we do each week. Although the timing may be suspect, this is not a new years resolution, just something we happened to think of while on holiday. Here’s a summary of week 1.
Jesse has begun working on a new design system based on models of differential growth. Currently, it’s just at the phase of initial implementation and conceptualization.
Nathan added a search box on our website with autocomplete, so you can more easily find what you are looking for. Or you can look for everything that comes in black and is 3D-printed.
Jessica is playing with our old barnacle sketch in new ways. She’s looking into making some neat organic animations and colored 3D prints.
Aaron has created a new email address for organizing all the supplies and manufacturers we work with.
For a new app we’re working on, we finally came upon the task of loading external 3D geometry. I wanted to store and load meshes with as little bandwidth and processing as possible. I’m sure this has been done before, but here is how I approached it.
Rather than loading a mesh in a common file format (eg stl or obj), processing it, and putting into arrays that I could send to a gl buffer, I wanted to load binary data that could go directly to the GPU. So I created a binary representation of a mesh that exactly mirrors the data I would send to an array buffer. It is a list of 32-bit floats representing the vertex data (6 for each vertex with position and normals) followed by a list of 16-bit integers representing triangle indices. Obviously, this is not a very general file format, but it is exactly the data I need for the shaders I was using. The only additional data is two integers at the start of the file representing the number of vertices and faces.
This data can be directly fetched with an http request as an ArrayBuffer object. This ArrayBuffer can be accessed by creating a Float32Array for the vertex data and Uint16Array for the index data. I don’t even have to allocate new storage. Both the vertex and index arrays use the same ArrayBuffer, just with different offsets.
This is surprisingly simple, and the hard work really comes in encoding the mesh data to begin with. This was in fact extra tricky because I had to deal with endian issues. Endian refers to the order in which the bytes of a number are read. Little-endian means the least significant byte comes first, and big-endian means the most significant byte comes first. When you create a TypedArray from an ArrayBuffer, it just sees a list of bytes and it doesn’t know what byte order they are in. Javascript assumes it is the same as the underlying system architecture, which can vary. It turns out the majority of common systems (x86, x86-64, IOS) are all little-endian. So I generally feel I can ignore big-endian systems and just make my files little-endian. However, Java, with which I was generating the meshes, creates big-endian numbers by default. This caused me much grief for a few hours, as everything was working fine except for the fact that my numbers were mysteriously gibberish.
Below you can find the code I used for encoding and decoding the meshes. The AJAX portion is largely copied from an online example.
Processing code for encoding an obj in binary
String folder = "SOMEFOLDER";
String file = "filename.obj";
ArrayList<PVector> srf = new ArrayList<PVector>();
ArrayList<PVector> norm = new ArrayList<PVector>();
ArrayList<int[]> faces = new ArrayList<int[]>();
void setup() {
noLoop();
}
void draw() {
loadSrf(folder+file);
writeSrf(folder+file.substring(0,file.length()-3)+"vbo");
exit();
}
void loadSrf(String name) {
srf.clear();
norm.clear();
faces.clear();
println("LOAD " + name);
String[] lines = loadStrings(name);
for(int i=0;i<lines.length;++i) {
if(lines[i].length() > 2) {
//vertices
if (lines[i].substring(0,2).equals("v ")) {
float info[] = float(split(lines[i], " "));
srf.add(new PVector(info[1],info[2],info[3]));
}
//normals
else if(lines[i].substring(0,2).equals("vn")) {
float info[] = float(split(lines[i], " "));
norm.add(new PVector(info[1],info[2],info[3]));
}
else if(lines[i].substring(0,2).equals("f ")) {
String info[] = split(lines[i], " ");
//sometimes obj's have different indices for different properties separated by '//'
int info1[] = int(split(info[1],"//"));
int info2[] = int(split(info[2],"//"));
int info3[] = int(split(info[3],"//"));
//obj has 1 based indexing and we need 0 based indexing
faces.add(new int[] {info1[0]-1,info2[0]-1,info3[0]-1});
}
}
}
}
//write the data in binary
void writeSrf(String name) {
try {
DataOutputStream dos = new DataOutputStream(new FileOutputStream(name));
dos.writeInt(srf.size());
dos.writeInt(faces.size());
PVector v;
for(int i=0;i<srf.size();++i) {
v = srf.get(i);
writeFloat(dos,v.x);
writeFloat(dos,v.y);
writeFloat(dos,v.z);
v = norm.get(i);
writeFloat(dos,v.x);
writeFloat(dos,v.y);
writeFloat(dos,v.z);
}
int[] f;
for(int i=0;i<faces.size();++i) {
f = faces.get(i);
writeShort(dos,f[0]);
writeShort(dos,f[1]);
writeShort(dos,f[2]);
}
dos.close();
} catch(Exception e) {
}
}
//write a float value little endian
void writeFloat(DataOutputStream dos, float f) throws IOException {
int i = Float.floatToIntBits(f);
dos.writeByte(i & 0xFF);
dos.writeByte((i >> 8) & 0xFF);
dos.writeByte((i >> 16) & 0xFF);
dos.writeByte((i >> 24) & 0xFF);
}
//write a 16-bit integer little endian, integers larger than 65535 will get truncated
void writeShort(DataOutputStream dos, int i) throws IOException {
dos.writeByte(i & 0xFF);
dos.writeByte((i >> 8) & 0xFF);
}
javascript file for loading meshes from a file
//load mesh object
/*
bytes 0-3 = number of vertices
bytes 4-7 = number of faces
vertex = 6x4 bytes position followed by normal
faces = 3x2 bytes as unsigned 16 bit indices
*/
function loadVBO(url, vbo) {
var xhr = new XMLHttpRequest();
xhr.onreadystatechange = function () {
if (xhr.readyState == xhr.DONE) {
if (xhr.status == 200 && xhr.response) {
loadBuffers(xhr.response,vbo);
} else {
console.log("Failed to download:" + xhr.status + " " + xhr.statusText);
}
}
}
// Open the request for the provided url
xhr.open("GET", url, true);
// Set the responseType to 'arraybuffer' for ArrayBuffer response
xhr.responseType = "arraybuffer";
xhr.send();
}
//read ArrayBuffer into gl buffers
function loadBuffers(buffer, vbo) {
var reader = new DataView(buffer);
//get number of vertices and faces
var numVertices = reader.getUint32(0);
var numFaces = reader.getUint32(4);
vbo.numVertices = numVertices;
vbo.numFaces = numFaces;
//put that data in some arrays
vbo.vertexData = new Float32Array(buffer,8,numVertices*6);
vbo.indexData = new Uint16Array(buffer, numVertices*24+8, numFaces*3);
//push that data to the GPU
vbo.vertexBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, vbo.vertexBuffer);
gl.bufferData(gl.ARRAY_BUFFER, vbo.vertexData, gl.STATIC_DRAW);
vbo.indexBuffer = gl.createBuffer();
gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, vbo.indexBuffer);
gl.bufferData(gl.ELEMENT_ARRAY_BUFFER, vbo.indexData, gl.STATIC_DRAW);
}
And to draw the data
function draw() {
//... some gl drawing stuff up here
gl.bindBuffer(gl.ARRAY_BUFFER, vbo.vertexBuffer);
gl.vertexAttribPointer(shaderProgram.vertexPositionAttribute, 3, gl.FLOAT, false,24,0);
gl.vertexAttribPointer(shaderProgram.vertexNormalAttribute, 3, gl.FLOAT, false,24,12);
gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, vbo.indexBuffer);
gl.drawElements(gl.TRIANGLES, vbo.numFaces*3, gl.UNSIGNED_SHORT, 0);
}
Jigsaw puzzles for the 21st century! Each generative puzzle is a one of a kind creation with unique art and pieces. Our goal was to marry the artistry of traditional, hand-crafted jigsaw puzzles with the possibilities of new technologies. Custom software simulates crystal growth to create an organic interlocking pattern. Our laser cutter translates this into a unique set of plywood pieces. We collaborated with contemporary digital artists who created engaging artwork for the puzzles.
The puzzles are made entirely in our studio in Somerville, MA. We print the artwork on archival paper and laser cut the puzzles from birch plywood. They come in two sizes, a round 7.5″ puzzle with 85 pieces and a rectangular 18×12″ puzzle with 410 pieces. Every puzzle is unique.
We’ve created a project page with tons of information about our inspiration, process and methods for creating these jigsaw puzzles. We invite you to explore it here: Generative Jigsaws Project Page. The project page discusses
We designed a puzzle cut generation system based on a simulation of dendritic solidification, a crystal growth process similar to the formation of snowflakes that occurs in supercooled solutions of certain metallic alloys. This system generates a unique cutting pattern, and by varying the parameter space, can produce a variety of cut styles. You can read about how our simulation works here.
The puzzle images are one of a kind, original artworks by invited generative artists. Our first series is created by Jonathan McCabe, an artist based in Melbourne who works with reaction diffusion patterns. His pieces are created by layering several reaction diffusion simulations at multiple scales. Additionally, he imparts flow and movement by combining this with a compressible fluid simulation. The result is an explosion of color and pattern reminiscent of flowers, animal patterns, and watercolor. Jonathan talks about his process on our project page here.
The first series of puzzles comes in two varieties: a 7.5″ round puzzle with approximately 85 pieces and a 18″x12″ puzzle with approximately 400 pieces. The smaller puzzles come with a selection of whimsies themed around “Microscopic Life”. Each puzzle is a veritable petri dish teeming with special pieces resembling algae, diatoms, radiolarians and other minuscule creatures. The large puzzles come with a broad range of whimsies spanning all of our interests here at Nervous System.
Our puzzles are manufactured in our studio in Somerville. We print the art on archival quality paper, mount them on birch plywood, and laser cut them. Each puzzle comes in a handcrafted wood box made in Vermont.
Come join us in the Nervous System studio for a relaxed evening of learning and playing Go – the ancient board game. While playing, we can chat about projects, simulation, 3d printing, or whatever. No experience required. Inspired by Kitchen Table Coders. Feel free to bring any drinks or snacks.
March 21st 2012
7pm-10pm
Free
561 Windsor St
Ste A206
Somerville, MA
(same building as Taza Chocolate)
In the future, we would like to run more events around creative uses of new technology, bringing together local programmers, artists, makers, and engineers. If you’re interested, come by our studio, play go, and let us know what you think.
For a while now, we’ve been wanting to switch our online apps from Java applets to HTML5. Applets are simply an outdated technology with a much clunkier, inelegant user experience. Finally, in the last two weeks, we’ve had the time to dig in and start porting our apps. Not only is the technology superior for developing HTML5 apps, but we’ve also learned a lot since we first released customization apps in 2007. We decided to tackle the most complex one first, the Cell Cycle app. In this post, I’ll go over some of the tech we used and some of the hurdles we encountered.
The Tech
The first thing we had to decide was how we wanted to go about translating our app from Processing, our development environment of choice, to Javascript. I considered rewriting the entire thing from scratch as a kind of JS learning exercise, but decided it was not worth while. The next obvious choice was to use the amazing ProcessingJS, which allows you to run pure Processing code directly in the browser. However, the 3D capabilities of PJS are somewhat limited, so I spent some time looking at other frameworks people have developed around WebGL, such as Mr. Doob’s Three.js. Despite there being some great frameworks out there, I decided that the options were too heavy handed and required too much specialization. The great thing about Processing is how subtle it is. It does exactly what you think it should without extraneous syntax getting in the way.
ProcessingJS
Ultimately, we went with a hybrid of the first two options. We used PJS so that we could reuse the core logic of the original Processing app, but we used pure JS and webGL for drawing. One of the amazing things about PJS is you can mix Processing code and Javascript directly. This allowed us to write JS drawing functions and simply replace the drawing parts of our Processing code. There is an additional benefit/detriment to this ability of PJS. You cannot only call JS functions from Processing, but can combine the object models of Java and Javascript. You have the clean and compact class definitions of Java. But you have the mutability of Javascript that avoids the “over-objectification” that is common in Java. I find this a really refreshing way of coding; however, to the casual user the mixing of Java and Javascript may end up looking like gibberish.
No Libraries
One of the unfortunate aspects of PJS is cannot directly leverage the great community that has grown up around Processing and developed so many powerful libraries to extend Processing. There is no easy way to use Processing libraries in PJS, and in many cases, it is non-trivial to port libraries to PJS. So the first thing we had to do was remove any library dependencies from our code, which included controlP5 and PeasyCam. We replaced these with our own code. This wasn’t so bad, since the app needed a UI overhaul anyway.
the old Java version
Features
The original Java version of the Cell Cycle app had a number of problems. The interface was cluttered; it was buggy; you couldn’t save and share models; you couldn’t subdivide cells on the inside of the bracelet; etc. We took this rewriting as an opportunity to fix and add a bunch of features. Originally, there were three different “view modes”: 3D, smooth, and 2D. We combined all of these into one. The model is always smooth (more on this next) and with the extra screen real estate of the browser, we can show 2D and 3D views simultaneously.
The new version autosizes! Previously there was a “radius”, which corresponds a parameter in the mesh generation but has no relation to the user. It doesn’t correspond to the inner radius or outer radius of the final piece. We updated this version so the user specifies the interior diameter of the final piece. The code then iteratively resizes the piece until the interior dimension is approximately correct. This way a user can specify a size and no matter what they do to the model afterwards, it remains the same size.
Permalinking! It is practically necessary to have permalinks to user generated content on the web these days. If you can’t tweet something or post it to facebook, it might as well not exist. Not only can you link to a model now, but you (or anyone) can continue editing. Instead of saving the mesh that gets 3D printed to our server, we save an abstract representation of the current model state. The actual 3D mesh is reconstructed upon loading. Not only does this allow geometry to be smartly reloaded for editing, but also makes the models much lighter. This saves space, bandwidth, and load times.
Optimization
The biggest amount of development we had to do was optimization. Things have to run fast in the browser. The majority of processing power goes towards generating the mesh and passing that info to the GPU with webGL. Displaying large, static models using openGL is easy. You load up a model into a VBO once, and that’s it. You can display millions of triangles at really fast frame rates. All the work is done in a preprocess, so you don’t have to worry optimization. However, when you have a large, dynamic mesh that is constantly changing, optimization becomes important.
One thing we decided is it couldn’t be completely smooth all the time. The meshes are smoothed through Catmull-Clark subdivision. The models that we send to the printer have two subdivision steps preformed on them. This is simply too much computation to be done in real time. Instead, while the model is moving we only perform one subdivision. When the model settles and stops, which happens pretty rapidly, we perform a second subdivision and store that in a VBO. Until it moves again, we do not update the VBO.
But this in and of itself was insufficient using the naive drawing methods that we had previously. The meshes are represented using a Half edge data structure. This stores connectivity information of our mesh faces in a compact way. The simple approach to drawing the mesh is to loop through all the vertices and faces of a mesh, dump that info into arrays that gets passed to the GPU. The problem is that regular JS objects and arrays are not particularly performance oriented. Simply looping a large array of objects and performing basic operations is a significant CPU drain. The key to getting around this is doing as much as possible in fixed-type arrays that were introduced into Javascript specifically for webGL. These include Uint16Array, Float32Array, etc. In my experience, these arrays are far more efficient than generic arrays. Instead of subdividing and creating a new Half edge mesh, the subdivision data goes directly into fixed-type vertex and index arrays that can be passed to webGL. Additionally, other computations, such as surface normals and volume are performed directly out of these buffer arrays. This was ultimately key to getting interactive framerates.
subscribe to RSS feed