Planet K-3D

With K-3D 0.8 effectively feature-complete, we’re just making sure that everything builds cleanly and produces consistent results on all platforms … in a number of cases, we’re seeing plugins that produce results that are visually indistinguishable to the casual user, but contain tiny numeric differences across platforms.  Usually these tiny errors are the result of rounding or slight differences in the way that different processors compute numbers, such as the sin() of a value, and can be ignored.  But in a few cases the differences are larger than we’d like, and require further attention.  As a rule of thumb, the more complex the computation, the more likely that the results will vary.  The old Polyhedron plugin was one example that computes uniform polyhedra at runtime using some pretty hairy math, and produces inconsistent results (again, not visible to the naked eye, but extremely obvious in our tests). So I’ve replaced “Polyhedron” with “UniformPolyhedron”, which stores a list of popular polyhedra instead of computing them on the fly:

The UniformPolyhedron mesh source in action ...

Tweet This Post

The new user interface work for K-3D 0.8 will likely rely heavily on Client-Side-GTK and/or Clutter …

Tweet This Post

In an effort to follow best-practices in the K-3D website, our recent overhaul switched from HTML to XHTML for our content.  As it turns-out, this wasn’t the way to go … in response to some complaints about inaccessible web pages, I’ve learned a lot about HTML-versus-XHTML at http://www.webdevout.net/articles/beware-of-xhtml … in a nutshell, it simply isn’t possible to use XHTML with certain web browsers without resorting to counterproductive hacks. We aren’t invested in XHTML in any significant way, so it turned-out to be better (and easier) to switch back to strict HTML 4. Go-figure …

Tweet This Post

Take a look at the K-3D Developer Dashboard, and you will see that, for a small project, K-3D does a significant amount of nightly testing, far more than most of the commercial firms where I’ve worked.  These nightly tests are, for the most part, constantly checking to verify that changes in the code don’t cause unwanted changes in the outputs of individual plugins.  The tests generally setup a small pipeline with a set of known inputs and parameters, then test the output against a reference file to see that they are equal.

The tricky part is that testing for equality isn’t as straightforward as you might think.  Thanks to the imprecision inherent in floating-point math, different platforms, different compilers, and even different runs with the same compiler and platform may produce slightly different results.  Accordingly, tests can’t simply check to see if a test produces a value equal to 1 … in practice such a test might produce 1, 1.00000000000003, or 0.99999999999998 and still be “correct”.  Because of this, tests can’t test for true equality, they have to test whether values are “close enough”.

Until recently, K-3D used a template class, k3d::almost_equal to handle this case.  k3d::almost_equal took a threshold as a parameter and produced a boolean result – whether two values were equal or not, taking into consideration floating-point issues and the threshold value.  The problem with this approach was that if a test was failing, it was difficult to figure-out by how much – you had to plug different values into the threshold and re-run the test to see whether the results changed or not.

Accordingly, I’ve replaced k3d::almost_equal with k3d::difference, which returns the difference between two values, leaving it up to the caller to decide how to use the difference – whether to test it against a threshold, just report the value, etc.  As you might expect, k3d::difference is templated, with specializations provided for all of the well-defined K-3D types, plus arrays, tables, primitives, and meshes.

Tweet This Post

This week I did a first test using the CARVE boolean library. Execution is MUCH faster than with CGAL, but unfortunately the ordering of mesh components is not consistent, as shown in the following screenshot, which compares two subsequent runs using CARVE.

Difference in numbering, when not sorting the output

Responding quickly to the issue I created about this, CARVE author Toby Sargeant suggested using canonicalize to sort the result. This resolved the above issue, and only one test still fails in one place. The test case applies two subsequent booleans, doing “(big cylinder – small cylinder) – torus”, as illustrated in the next picture.

Cylinders and torus before and after the boolean

It seems only one point, at the intersection of the top and bottom, still gets switched around. The next figure show the difference in numbering, point 39 and 40 got switched around, as did some of the connected edges:

Switched points and edges between two runs

Interestingly, this error is identical to what happened when we tried to use CGAL with a custom number type based on double. The top face is actually triangulated before the boolean, and this causes two edges to intersect “exactly”. Rounding errors may cause the difference in numbering.

Triangulated top face of the big cylinder

Performance wise, this dashboard run shows the difference between CARVE and CGAL. The important test here is the benchmark test, showing an improvement by a factor of 50 if only the boolean operations are taken into account. Not bad!

Tweet This Post

With changeset 415e971ad9, support for easy CPU profiling using Google Perftools. There are changes to the build system to link with the perftools library, and there is a startup plugin to automatically start profiling without the need to set environment variables.

Usage

First, build and install Google Perftools using the normal installation procedure. By default, /usr/local is searched by CMake, so keeping this default is easiest. CMake contains two relevant variables:

• K3D_ENABLE_PROFILING: Enabling this links the SDK and all modules against the profiling library, so profiling can be enabled. It also adds the google perftools include directory to the include path.
• K3D_BUILD_GOOGLE_PERFTOOLS_MODULE: Builds the startup module, which automatically activates profiling on startup. If you want to restrict profiling by adding ProfilerStart/ProfilerStop calls in your C++ code, you should disable this module.

By default, profiles are saved to the temp dir (/tmp on linux), this can be configured using the “profile_files” path option in .k3d/options.k3d. If all goes well, you should should see a line like

DEBUG: google_perftools: saving profile data to file /tmp/k3d-profile-0.pprof

when running K-3D. A profile file is never overwritten, the index is incremented as with the preview renders. The recommended build type for profiling is RelWithDebugInfo. This ensures performance is close to the real-life case. If the call graph is unclear, a full debug build will show more details, as there are no optimizations.

Adapting pprof

By default, pprof (the profile data processing tool) only supports libs with a .so, .dylib or .dll extension. Since K-3D plugins use .module, you need to add this to the regular expression on line 3246 in the pprof perl script, like this:

if ($l =~ /^($h)-($h)\s+..x.\s+($h)\s+\S+:\S+\s+\d+\s+(\S+\.(so|dll|dylib|module)(\.\d+)*\w*)/i) {

Examples

Just for fun, I tried profiling the SDS code, by applying 6 iterations of CatmullClark on the default polysphere. The profiling file was processed using:

pprof --gv bin/k3d /tmp/k3d-profile-0.pprof

Here, the call was issued from the build dir. If you execute from somewhere else, bin/k3d should be replaced with the path to the K-3D executable. The command produces a nice call graph of the entire K-3D run, where the biggest functions represent the biggest CPU consmers. For SDS, this surprisingly turns out to be __gettimeofday:

SDS profile, full

We can get more information about this by “focusing” on the call of interest and showing more nodes, using

pprof --gv bin/k3d --focus=__gettimeofday /tmp/k3d-profile-0.pprof

Note that this was done using a debug build, not a RelWithDebInfo build, since some intermediate calls are optimized out otherwise. The resulting graph is:

The problem is obvious now: During the development, SDS code was profiled manually by adding k3d::timer calls at different points in the code. In this case, there is one in the face_center_calculator, in order to evaluate the importance of attribute data updates. As it turns out, this timing call is now dominant over the SDS calculation itself! In retrospect, adding that many timing calls was silly, but proper profiling pointed out the error very quickly indeed.

Since we have profiling support now, all timing calls were removed from the SDS code in changeset f5c14e68f4. As a result, the Catmull-Clark operation is twice as fast, and the update step is more than 3 times as fast. Not bad for a 5 minute profiling run!

Tweet This Post

Various lens shapes can be designed in K-3D using the mesh primitives and CGALBoolean operations. Using LuxRender and bidirectional path tracing allows you to accurately simulate the photon paths through the lenses. Luxrender also allows for dispersion calculations but these are not shown in the example below.
It is possible to construct a scene so that a Null node holds a set of user properties that the scene components connect to so that it becomes a master controller from which parametric adjustments can be made. The images below show the graph layout for such a scene, the 3D viewport layout and the final render in LuxRender.

By alternating the view rapidly from side to side we can give the impression of 3D space in a viewport that normaly is just a 2D projection of the selected camera’s view of the scene. I have also used fog so that the sense of depth is further enhanced. The speed and size of the shift needs to be tune-able and the timing should be sent to a chosen port to allow the incorporation of LCD shutter glasses.

Well it looks like such cute tricks are soon to be made redundant by technology such as Acer’s GD235HZ 23.6-inch 3D display.

… broken legacy filters to be updated, that is:

• FilletEdges
• CollapseEdges
• DissolveComponents
• ExtrudeFaces
• JoinPoints
• BevelFaces
• BevelPoints

Tweet This Post

This work will have a significant influence on the user interface work in K-3D 0.8:

http://www.dgp.toronto.edu/~shbae/ilovesketch.htm

Tweet This Post

Getting ready for K-3D 0.8, I am cleaning-up a lot of legacy code, basically everything that predates generic primitives.  That includes, in no particular order:

• FilletEdges
• Weld
• CollapseEdges
• DissolveComponents
• BridgeFaces
• MakeCreases
• CapHole
• ConnectVertices
• JoinPoints
• BridgeEdges
• BevelFaces
• BevelPoints
• ExtrudeFaces
• QuadricDecimation

Tweet This Post

Sweet stuff here:

http://mi.eng.cam.ac.uk/~qp202/my_papers/BMVC09/

… I’m very impressed with the performance and tracking – I could see doing interesting things with a gesture-based user interface in K-3D …

Tweet This Post

http://www.openarchitecturenetwork.org/ and http://www.architectureforhumanity.org/ are two projects that could benefit from K-3D’s architectural modelling and rendering potential.

With all of the new web services we’ve been setting-up, we wanted to have a single, go-to place to see what’s happening with K-3D.  That place is Planet K-3D.  Planet K-3D aggregates feeds from our Wiki, Blogs, Forums, and source code repositories.  If you want to stay on top of what’s new, Planet K-3D is for you …

Enjoy!

Tim

Tweet This Post

The input mesh for points needs a center property, the mesh for edges needs start and finish point properties and the input mesh for triangles needs three point properties. Not sure if an orientation property is required but it may be helpful.

A mesh filter that replaces parts of the input mesh with copies of other meshes, where the user can specify a replacement mesh for each of point|edge|triangle or quad.

For example, a simple polyhedron made from triangles can be transformed into a spaceframe with extruded beams on edges, ball joints at points and double glazed window units where there were triangular faces. I only specified triangle or quad because I can’t see how triangle AND quads could work.

For a true frame structure the initial mesh would need to be extruded so that it had thickness and then this skin must contain the required lattice of edges and triangles with differentiation between original faces, copies (the extrusion caps) and sides of the extrusions. Once you have this extrusion tool you can take a free formed or algorithmic mesh and convert it into something that can be built using CAM. Ideally boolean operations also need to be performed between the three input geometries after they are transformed for each triangle of the input mesh.

See Evolo for many examples of what then becomes possible.

The above is just one example, in another the first pass could be to just replace triangles with more triangles before applying the filter again to the  triangle part input mesh to make a space frame.

This system could be implemented as an extension to or variation of the LSystemParser module.

See also, Geometry of Multi-layer Freeform Structures for Architecture.

And for something less “useful” but still very interesting, fractal polyhedra.

Combining volume thinning, http://www.caip.rutgers.edu/~cornea/CurveSkelApp/ with http://blog.wolfire.com/2009/11/volumetric-heat-diffusion-skinning/ should allow for a very rapid set up of rigged characters of any morphology.

DOF mock up screen shot 2

Visualising Depth Of Field can be difficult therefore a method of seeing changes to camera setting in the 3D view-port prior to rendering is desirable so as to avoid lost time due to focus errors.

The grid shown below is projected out from the camera and is semi transparent so that it can interact with objects in the scene so that the user can clearly see the amount of defocusing a given part of the scene will be subject too.

See blur disk diameter.

DOF visualisation mock-up

The grid below would be generated based on the properties of the camera it is associated with and would update in real-time as those properties are adjusted.

Variably blurred grid for DOF visualisation

Ideally the grid would be a wedge shape that matched the Field of View of the camera. And for precision the user could select one or more objects and the grid would project in two planes at right angles to each other who’s long axis would run from the camera to the center of the selected object/s.

Here, you can see the new SheevaPlug computer that will soon provide firewall, web, and email services for k-3d.com!  Note the mouse for size – this is a new class of “plug” computers that are designed for commodity-server computing – with a handful of SheevaPlugs and a power-strip, you could start a render farm under your desk …

Tweet This Post

After a few issues with bugs, including dropped frames I have finally got a finished animated sun study. Here are two more plan views for Summer and Winter. Rendered with very low quality settings so I did not have to wait all day for a result.

A possible solution to having to set up UV mapping on surfaces Ptex

EnergypPlus models heating, cooling, lighting, ventilating, and other energy flows as well as water in buildings.

In K-3D there is currently no direct output plugin for this yet, but RenderEngineScript will let you write you own, using nodes with custom metadata, Plugin_Metadata, Property_Metadata and Node_Metadata

One compact yet reasonably complete reference for this topic is  Introduction to architectural science: the basis of sustainable design By Steven Szokolay

The NURBS extrude tools and curve traversal are done now, only 9 failing tests remain, so the end is in sight I’ll merge with the SF.net repo once all NURBS plugins are up-to-date again, and after that look into the win32 build (and set up my dashboard again).

Tweet This Post

NurbsCreateCap is now updated to the new mesh structure. The method of creating the cap was changed: instead of using ruled surface along two halves of the curves, the new method uses the same technique as in the disk NURBS primitive, with the option of setting a number of radial segments.

Tweet This Post

Today, I finished going over the NURBS curve plugins. The NurbsEditCurveKnotVectors plugin underwent the biggest change, and supports editing multiple curves in one go now, as well as inserting knots. Code-wise, NurbsSplitCurve was overhauled as well.

On to the NURBS patch plugins now!

Tweet This Post

While updating NurbsCurveInsertKnot, I removed the “Share degree and knotvector” flag that was present. Basically, this flag caused the knot vectors (and by necessity also the degrees) to become identical for all selected curves. This is a requirement when i.e. creating a lofted surface. Since the operation might be useful on its own, and because it’s more in line with K-3D’s pipelined architecture, I’ve created a new plugin for this. Details on the algorithm can be found on page 338 of the NURBS book.

Tweet This Post

Welcome to the K3D blog.

Tweet This Post

As part of the preparations for the release of K-3D 0.8, I am looking into updating the NURBS plugins to make them work with the latest changes in the K-3D mesh structure. While at it, I’ll also be aligning the interfaces of nurbs_curve_modifier and nurbs_patch_modifier to the k3d::nurbs_curve / k3d::nurbs_patch interfaces. This means we’ll be moving towards a series of functions operating on k3d::nurbs_curve::primitive, instead of a single nurbs_curve_modifier class that does everything.

For curves, the new methods are in modules/nurbs/nurbs_curves.h, and so far NurbsCloseCurve, NurbsCurveElevateDegree, NurbsConnectCurves and NurbsCurveInsertKnot have been updated and can be pulled from https://k3d-bart.googlecode.com/hg

Tweet This Post