Got Distracted

To all of those waiting for STL output, sorry, but I got distracted yesterday and today.  When I was going through the steps necessary for generating tessellated trim surface output I came up with a nice optimization that could apply to both NURBS curves and surfaces.  I won't bore you with the gritty details of the approach.  If you are really interested just drop a comment and I will reply.

In addition to being faster, this optimization uses less texture memory and requires a good deal less setup for generation that the current approach.  It did require modifying every generation shader, but the changes were pretty minor.

I have been reading "Performing Efficient NURBS Modeling Operations on the GPU" repeatedly in order to get prepared for surface-surface intersection.  One of the neat parts of their approach is that their GPU-based generation routines don't have to generate the entire curve or surface but can generate just a sub-region.  They use this ability to iterate through repeatedly (almost Newtonian like) to get within a certain accuracy.  Well, the optimization I put in place lays the groundwork for Wildcat being able to do the same sub-region generation too.  Just need to make a few more tweaks and API changes and we should be all done.

In addition I move to using PBOs to copy curve and surface generation data for server-side generation.  This should be a nice improvement.  I had avoided doing this before because I was running into some driver bugs that would hang the system when I tried to call glReadPixels.

Wow...lots done in the last two days, but little to do with STL.  Getting good STL output really is a priority, I promise.  Hopefully next week.

Cheers,

   Graham

STL taking shape

Just a quick note tonight about my progress with STL export.  I spent some of this afternoon mocking up the export and it went just as easily as I expected.  I nearly finished the whole thing, just need to implement Trimmed Surface tessellation, which I think I can knock out tomorrow.  So, hopefully by end of day tomorrow, we will have nicely working STL output.  As soon as I can I will post a sample output file on the download page.  If you want to try it out tonight, from the Part Designer screen just press 'x' and output.stl will be written to the same directory as the Wildcat root directory.  Obviously, we will need to eventually get a proper window to choose an output file name etc.

One question for those that know STL.  The top level object in the STL file appears to be "solid", with facets below that.  It is very easy to generate multiple separate solid bodies in Wildcat, how should I handle this?  Can you have more than one "solid" in a single STL file?  Should the user have to select a single body in Wildcat?  If anyone knows, please post a comment.

Cheers,

   Graham

Topology for Part Pad is Done!

Today I wrapped up a few little fixes to the topology generation for extrusions (PartPad).  See the SVN notes for a few little caveats about two possible issues that will need to be addressed later.  Now I can move on to the really exciting things.

Over the weekend I will start working on the STL methods I talked about in the last few posts.  I have no way of testing the correctness of my output though.  Does anyone out there have the ability to test STL files?  If so, I am more than happy to generate the STL file and post it for download.  Or, you can run Wildcat and do it yourself.  If you want me to do it, what shape would you like (remember only extrusions at this point)?

I have also begun more background reading on boolean operations (also known as boolean merging).  I think that I will start with trying to do planar sections of a part and then progress to Union.  Does anyone have a preference on the order in which I attack the operations?

There is still a lot of outstanding geometric intersection work that will have to be done along the way, but I don't think it will be too too difficult.  Most of it is for the two types of surfaces.  Curves and lines are pretty good at this point, though I do have to code the routines for generating NURBS curves from a series of points (point interpolation).  Piegl and Tiller (The NURBS Book) have a bunch of good algorithms for this.

Have a great weekend.

Cheers,

   Graham

Argh, more topology

I am out the other side of a busy work week last week.  Sorry for not making many updates or posts; this week should be better.  Despite being out last week I continued to receive a lot of comments regarding RepRap and STL files.  I want to talk about that for a bit and then a quick update on what I am working on this week.

I have now been contacted by several people that are either directly or loosely affiliated with the RepRap project.  This project looks great and I am very very supportive of their objectives and approach.  They have been using Art of Illusion as the "CAD" package, but it really doesn't seem to be meeting many of their needs.  I believe that in due time Wildcat will be an ideal partner.  I say in due time because Wildcat is still quite limited in its modeling abilities, boolean operations being the biggest omission currently.

After a bit of education, I now realize that exporting a Wildcat model to an STL file will be quite easy.  I need to write one routine to fully tessellate trimmed surfaces and then write a routine to output an entire part into an STL formatted file.

Full tessellation of a trimmed surface can be difficult, but I think that I have an easy and efficient way to do it.  Wildcat can already generate tessellated NURBS surfaces, trimming textures, and bounding curves.  This is really all we need.  Here are the steps as I envision this algorithm:

1. Generate tessellation of underlying NURBS surface
2. Generate trimming texture
3. Generate bounding curve points and place into triangle.c array and mark as boundary (if you are not familiar with triangle.c please see this - very fast Delaunay triangulator)
4. Test every underlying surface point against the trim texture (basically do a quick reverse lookup to see if for a given [u,v] it is in the filled portion of the trim texture - if it is in the texture then add it to the "output" list and mark as interior
5. Now we have a list of all tessellation points (either marked as boundary or interior) - pass this list to triangle.c and let it output the best triangulation.  And we are done!

Not too bad eh?  Should be very little code to write and should be at least moderately efficient.  There could be some complications in making sure that all of the surface-surface boundaries align nicely, but I think that I have ways of dealing with this.  This approach will also let Wildcat do nice LOD scaling on all types of surfaces.  Hopefully I can get this working in beta form in the later portion of this week.  Once this is done then all I have to do it write everything out to an STL file.  Then test, test, test.

So, what am I working on now?  As I mentioned last week, I really want to get topology working for Part Pad operations.  I continue to be amazed at how complex this is for such a conceptually simple operation (I am really not looking forward to topology for swept solids!).  I spent my downtime last week working on the algorithm and I am implementing it this week.  After a day of working on it, I am about half way done, but I have left the really tough part for last.  My brain is numb.  Working on STL output will serve as a good distraction.  Once this is done I can finally start working on some of the boolean routines.

Talk to you all tomorrow.  Cheers,

   Graham

I must be full of BS

My post yesterday highlighted how little I actually know.  I had a number of readers post comments pointing out that the STL format is not at all what I said.  Yes, it is the standard format for rapid prototyping, but no, it has nothing to do with taking thin slices.

After a bit more reading  (something I should have done before yesterday), I see now that the STL format only requires the tessellated surface geometry of the part itself, no sectioning.  There are very easy routines within Wildcat (see WCNurbsSurface::GenerateClientBuffers for example) that can already provide this (even to a nearly-arbitrary accuracy thanks to native 64-bit NURBS geometry).  Since trimmed NURBS surfaces are not actually fully tessellated for display it would require some work to get them to output triangles, but not too much.  I think that I could write that routine in a couple of days.

An outline of an STL exporter would look something like this:

1. User generates part and executes exporter
2. Query surfaces of the WCPart object to get list of surfaces
3. Generate appropriately accurate tessellation for each surface (already includes normals for each triangle)
4. Order output and write to file

It really should be that easy.  I think.  I was looking around online for documentation of the STL format and only came across one document that looked semi-official, here.  Is this still accurate?

If this is a priority for uses, I can move this up.  It would be way too cool to see parts from Wildcat.  Of course they will be very simple parts, but parts none the less.   Let me know.

Cheers,

   Graham

CAM and STL

I got an interesting comment yesterday with some discussion about one of the emerging low-cost rapid prototyping machines (www.reprap.org).  As with almost all RP machines this one takes input in the form of an STL file.  STL is a plain text format that defines each of the thin layers that compose the object.

Once I get basic Boolean operations running in Wildcat, it should be straightforward to generate STL files.  The basic approach is to intersect the model with a flat plane and get the intersection polygon.  Then move the plane up a bit and intersect again.  Repeat a lot.  So, should be easy, right?

As I mentioned before, I am very busy with my real job this week so I probably won't get much of a chance to work on Wildcat.  I am hoping to finalize the topology algorithm for Pad and then implement early next week.  We will have to see if that holds up.

Cheers,

   Graham

Lots O' Fixes

Over the long weekend I started to take a look at some of the issues I have noticed creeping up.  First and foremost are the problems we were having properly recognizing complex sketch profile hierarchies.  This turns out to be almost completely a problem with two things:

1. Crappy programming on my part.  Last week I put in place some code to make sure that the parametric values returned for all intersections are within [0,1].  This is accomplished wiht a simple bit of code -- STDMIN(1.0, STDMAX(0.0, value)).  Easy right, but I was stupid and put this code in before I finished checking for intersection.  Well if you do that then everything looks like an intersection!  D'oh.  Ok, easy fix once I figured it out.
2. Still many issues on the GPU approach to intersection.  When I run an intersection through the GPU the result is a long output list of points.  -1 indicates no intersection at that point, anything else is a hit.  Because of tolerances an intersection is almost always indicated with a series of hits.  Just a few hits is probably a point, lots of hits is probably an overlap of some type.  Well, what is the cutoff between the two?  I don't yet have a great answer for this, but an slowly working towards a decent solution that will should scale well.

So at this point things are working better.  Topology models are being partially built for Pads, and GPU-based trimmed surface generation and intersection are mostly working.  Not too bad.  But still a long ways to go.

Just to let you know, I am going to be really busy with work (real work, not Wildcat work) this week so check-ins and blog postings might suffer a bit.  Hopefully I can still sneak some time here and there.

Cheers,

   Graham

It's Topo Time

I spent more of today working on the topology model generation for PadPart.  I am still working through details of the algorithm (oh so many questions left unanswered), but at least a little of the topo model is now working.  A Pad will generate a model, the correct number of shells, and the faces for each shell.  You can even delete the model and do a bit of printing of model info.

Hopefully by the end of this week topo-gen for Pad will be done.  Then I can start into the Boolean operations and such.

Cheers,

   Graham

More GPU Intersection Routines

I spent today working on two things.  I'll talk about the first one second.  This afternoon I started getting code together for the remaining intersection routines - focusing on GPU deployment.  I won't go into a lot of detail about it all, but now curve-line intersection is on the GPU.  It still has a few details to get figured out (so might not be returning any hits at all at the moment), but should be ship-shape by tomorrow.  Tomorrow I also plan on trying a first pass on surface-point, surface-line, and surface-curve.  Should be interesting.

So now what I spent more of the day on and got nowhere.  Right now the GPU code for NURBS curve and surface generation work well and have been tested on nVidia GPUs, mostly on the G80 found in the current MacBook Pro.  I have an ATI HD 2400 XT based Windows XP machine that I have been using for my Win32 development and I had not gotten GPU-based generation running on it.  Today I thought would be the day I got it all up and working.

After spending about 4 hours trying to figure out ways around ATI's crappy support for integers in GLSL I gave up.  I don't want to convert the routines to entirely float-based since I know the int versions work well on good GPUs.  I might take another shot at ATI support in a few days, but for now I need to get some space between me and ATI.  Blah!

Cheers,

   Graham