Semi-Functional

Ok.  After a long day in the trenches I have the OSX version almost back to running and with all of the targeted improvements in place.  There is a good bit of glue code that still needs to be put in place (for key presses and mouse movements and such), but the fundamentals seem to be working.

The basic idea behind what I did is this:

1. Move to a Document Type manager - using abstract factories, each document type (think Part, Assembly, Visualization, etc) registers themselves and passes a factory.  Then when anyone asks the Wildcat kernel (also a new class) for a document of a particular type it can then create it.
2. Move to a core OpenGL context - when the kernel starts it creates its own OpenGL context which can then be used to see what the capabilities of the graphics card are much more easily.  This core context is now shared with each document thus greatly reducing document creation time and graphics memory overhead.  Big improvements should come from this.
3. Building on 1 & 2 - once I moved to this new kernel arrangement I was able to clear a lot of cruft out and clean up the platform independent side of things.  This obviously has a direct impact on the platform specific code and that is what is going to take some clean up work.  But that is for tomorrow!

Hope some of this makes sense.  These are things I have wanted to do for a while and the nearly daily emails asking if such and such a graphics card is supported finally put me over the edge and I decided to just jump in and do it.

Check back in next week and hopefully things will be back up and running fully.

Cheers,

   Graham

I Think I Broke It

I decided to make some fundamental changes to the underlying way in which the Wildcat kernel interacts with OpenGL.  On the plus side it will make things much cleaner and clearer moving forward.  On the minus side: a) there is still much work to be done to get this working on any platform, and b) while it is in a running state on the OS X side, the Win32/WX side is quite horribly broken.

While I have not tried compiling the WX project, I can save you some time.  I am oh so certain that I broke many things all over the place.  I hope to wrap up the OS X work tomorrow and start working on the WX code just after that.  The downside is that I have a trip planned from Wednesday through Monday, so if I don't resurrect things by the time I leave it will be broken through at least the weekend.  Sorry!

I will try my best to post an update tomorrow.

G

Intersections and Testing

As you may have noticed, I am starting to check in some code for all of the outstanding geometric intersections.  There are nine that need to be tackled:

• Surface-Point
  
• Surface-Line
  
• Surface-Curve
  
• Surface-Surface
  
• Trimmed Surface-Point
  
• Trimmed Surface-Line
  
• Trimmed Surface-Curve
  
• Trimmed Surface-Surface
  
• Trimmed Surface-Trimmed Surface
  

Some of these will be more challenging, some less.  In order to try out these routines I am also adding code to the Topological Union operation.  The goal is still full Boolean capabilities, but baby steps first.

Also, I have been playing around with some unit testing frameworks.  I would really like to get to the point where there is a nice automated unit testing suite for Wildcat.  Moving forward it will be necessary to regression test etc.  After spending some time looking at all of the open source unit testing frameworks out there I decided to adopt googletest.

There are a million and one testing frameworks out there.  My criteria were: simplicity, cross-platform, C++ support, and open source.  Googletest has most of the features I want with seemingly little overhead.  I should start checking in the initial tests I have written in the next few days.  They will be appearing under the Testing directory (makes sense huh?).

Cheers,

   Graham

Still Here

It has been far too long since I posted any updates.  I apologize for this.  As some of you may know, my real job is as a graduate student.  I am pursuing a Ph.D. in computer science.  Obviously the end point for this process is writing and defending a dissertation.  One step before that is to propose the research you want to conduct.  

I am hoping to use much of the work already done in Wildcat as a large portion of my dissertation.  This would seem to benefit everyone.  I would get my degree and be able to move Wildcat forward at the same time.  My advisor is open to this idea, but I need to write up my proposal.  Writing this document is what is currently consuming me.  Sadly the proposal itself doesn't do much for Wildcat, it just talks about what I will eventually do.  I hope to wrap up the proposal in the next month or two, so please be patient.

Thanks to everyone who has tried Wildcat.   Your continued enthusiasm is great motivation.

Cheers,

   Graham

Boolean Operations

Today's note is going to be quick.  Just two things...

First, on Wednesday Dan pushed out a Windows binary.  This is something that a large number of people have been asking for.  Well, he posted the binary and announced it and we haven't heard a thing since.  Has anyone tried it?  Please give us some feedback and let us know if it is working for you.

Second, I am staring in earnest on the Boolean operations code.  It is very interesting, but don't let anyone ever tell you that boundary classification and boolean operations are trivial.  Wow!  I am diving deep into the literature, but wow!  This is going to be a fun adventure.

Here are a couple of the key references I am working through:

• "Set Membership Classification: A Unified Approach to Geometric Intersection Problems" by R.B. Tilove
• "Boolean Operations in Solid Modeling: Boundary Evaluation and Merging Algorithms" by A. Requicha and H. Voelcker
• "An Introduction to Solid Modeling" by M. Mantyla

There are a bunch more, but this is where I am starting.  You might start to see some code appear in the topology_* files, but I am focusing on Slice and Union for now.

Again, please let us know how the Windows version is working for you.

Cheers,

   Graham

wxWidgets Wildcat.exe

I have added a zip file for Windows. It has Wildcat.exe, various dlls, and some picture files for the toolbar buttons. I don't know how to make an installer, so read the text file that gives you some extra instructions.

Scripting Support

On the Wildcat support forum we recently got a request to add support for the Lua scripting langauge.  If you have used Wildcat you know that currently no scripting languages are supported.  This is more an issue of having higher priorities than a lack of desire.  I am focused on getting the core modeling kernel up and running and Dan is working hard on the wx port and his own work.

I must admit that I have little background in scripting languages and have never embedded an scripting engine into any of my projects.  I fully understand the value of this and look forward to adding support in Wildcat.

To me the two crucial questions are:

1. What scripting languages make sense to support?  There are so many possible languages out there that we can't possibly support them all.  Which ones do you all want?
2. How can we make supporting a large set of scripting languages as easy as possible within the kernel?  I want to make it simple and straightforward to add support for a new language if someone want it.

The Lua requester has asked if we have object model documentation of Wildcat.  The simple answer is "No."  But, I have created a Doxygen configuration file that will generate a lot of very nice documentation automatically.  You can find this file in the source tree at "truck\Documentation\Developer\Doxyfile".  You may have to slightly edit some of the paths to account for your directory structure, but with this you can easily get object models and nice code docs.

Please let me know what else you need in order to try to add scripting to Wildcat.  I am more than happy to add in a Cocoa "script" window etc.  I am we can convince Dan to do this on WX also.

Cheers,

   Graham

Slight Progress Update

Sorry for being quite lately.  I have been very busy with my real job, but we are still making progress with Wildcat.  The Windows build (using wxWidgets) looks great.  Dan has done a great job.  Thanks to him.

I have slowly been adding better support for serialization.  There are quite a few features that don't have full serialization support yet, so I have been adding that in.  My motivation for this is so that I can have a reference part to use for coding boolean operations.  It is much easier, and faster, to just have a file that is opened instead of re-creating the part each and every time. 

The next three weeks are going to be crazy busy with my job, so don't expect a lot of updates.  Check the SVN for progress.  Once we are through the middle of October thinks should be a bit better.  One thing we are still really looking for is someone willing to help coordinate the Linux port.  I think that Dan has done the heavy lifting getting the WX build running, so it should be pretty easy for someone with a linux background.  Let me know if you can help.

Cheers,

   Graham

tool bars

I have added tool bars to the wxWidgets version of Wildcat. They are defined by the existing text file "toolbar_manifest.xml".
They all start at the top left, at the moment. I have to drag them to place.
I need to store their position for next time and allow the user to turn them on and off from the menu. The tiff files are all defined upside down!

wxWildcat

Graham, thanks for adding me as an author to your blog.
I am pleased you think wxWidgets is a good way forward for Wildcat.
It should mean that all user interface work can be done in one place, making the work easier, giving you more time to do the geometry stuff. The wxWidgets project I added is now as good for me as the MFC one. Hopefully more people will be able to build it, now that it can be built with Visual Studio 2008 Express. I'll add a toolbar next. The picture of me is from 5 minutes ago.

wxWidgets on the Way

Two posts ago I mentioned that Dan was starting on the wxWidgets port of Wildcat.  He has been making good progress and has checked in the initial code.  He has also already documented the build instructions for this project, here.  You can find pretty much everything you need to know there.  We are just getting started with this, so please be patient as we add better support.  This should make is much easier to have both a nice binary distro for Windows and also a Linux version.  If you have any questions about this work please post a message to the forum.

Cheers,

   Graham

A Quick Diversion

As I mentioned in my last post, Dan Heeks has offered to help out on Wildcat.  He is working on the paths necessary to support non-GPU machines.  Having spent nearly 18 months being the only person checking things into the repository it is kind of strange (but very welcome) to see new code appear as Dan works.  We are making good progress as Dan is now able to at least get Wildcat running and open a new document.  I never realized how much I made use of Vertex Buffer Objects (VBOs) and rectangular textures - neither of which are supported on the GMA 3100 chipset found in his computer.  Mostly I am trying to stay out of Dan's way at the moment!

Here is a quick screenshot I took this morning just for some eye candy.  Please to enjoy.

On my system sketching and extrusions are working quite nicely.  I am sure that there are profiles out there that will take it down, but even moderately complex ones are working for me as of now.

As a quick aside, since I am working away on all of the geometric intersection routines I needed a good way to quickly generate solids to intersect.  I can use any one of the existing planes and create two solids that intersect pretty easily, but I wanted a bit more.  So I have started to work on a dialog box that will allow for creation of arbitrary planes.  This is something that will absolutely be needed down the road so I figured why not now.  I have also mocked up the dialog box for pads (extrusions).  Here that one is:

Cheers,

   Graham

Intersections and Contributors

Hello,

I am working away on more of the geometric intersection algorithms.  I seem to keep getting distracted by exciting optimizations and improvements in other things.  You will see more of that in the coming days.  This should be exciting work though.

But the great news that I want to pass along is that Wildcat now has its first contributor outside of myself.  I would like to welcome Dan Heeks to the team.  He has decided to help add support for integrated-GPU platforms (i.e. GL earlier than 1.5) and to begin adding GUI support via wxWidgets.  Both of these improvements are highly anticipated and I really welcome the support.

Dan is also working on a couple of projects of his own.  The most notable is one that I hope we can eventually integrate with Wildcat.  HeeksCNC is his open source CAM software.  He blogs about it here and code is available here.  Check it out!  And thanks for joining Dan.  Its good to have some help.

More soon.  Cheers,

   G

Trimmed Surfaces are Back and Lookin' Nice

I finished up the majority of the optimizations related to trimmed surface generation.  For those that are interested I was able to remove completely any need to tessellate the projected trim profiles.  I also eliminated a lot of memory reads and writes to/from the GPU.  This was done primarily through the use of a new method I added to both NurbsCurve and NurbsSurface.

This interface is a companion to GenerateClientBuffers and GenerateServerBuffers, it is called GenerateTextureBuffers.  Now you can choose to generate curves and surfaces directly into the most efficient format for how you are going to use them.  Since there are at least four different generation paths for both curves and surfaces, I am sure that there are some holes in places, but the primary paths seem to work well.

The impact on performance is nice.  It is a bit tough to gauge exactly (I need to add better timing ability), but I estimate that the overall trimmed surface generation time was reduced by 25-50%.  Wahoo!

Pictures are coming.  Oh yeah, so is STL support.  Hmm...lots to do.

Cheers,

   Graham

No More Polygon Triangulation

First, thanks for all the great feedback last week.  I really appreciate everyone's support.  I was asked what the Windows version of Wildcat is lacking.  The core modeling functionality is identical so Win32 isn't lacking anything.  Where it is lacking is in the platform specifics and GUI.  I just don't know the Windows platform APIs well enough to do it justice.  I know that I have talked about using a purely WebKit-based UI, but now I am not so sure about this approach.  What I really need is someone interested in getting the Windows platform better supported via either Win32/MFC or wxWidgets.  Either one would be fine with me.  Wx would be great because then the Linux port would be that much easier.  If ya have some free time and want to chip in, just let me know!

Ok, about the title for today's post.  If you refer back to a post I did a couple of months ago about my approach for trimmed NURBS surfaces, one of the key steps was triangulating the projected trim curves.  This step is the only step that is on the CPU and is not the easiest to implement (I was going to move to using Shewchuck's triangle.c code).  Anyways...

So I was pulling together biblio sources for a paper I am beginning to write, and one of my sources listed another source I wasn't familiar with.  I followed the rabbit a bit and it turns out that there is a method for rendering convex polygons from their ordered boundary points in linear time.  All using the stencil buffer.  No more triangulation needed!  And now the entire trimmed surface generation algorithm will be GPU-based!!!!!  Whoot!

I am in the middle of implementing this approach.  Nothing checked in yet, but it should be up and running by the end of the week.  I will keep you posted and try to upload some screenshots for eye-candy.  It won't look crazy different, but it will be running much faster and be on a nice and clean theoretical basis.

Cheers,

   Graham

Moving Forward

Hello,

Well I am back from vacation and ready to dig in.  I got a nice chance to relax and contemplate some of the upcoming work I want to accomplish.  I also got a chance to think about what I want to prioritize and what I really need help on.

First, my highest priorities are getting both STL output and all of the remaining geometric intersection routines working.  Neither of these is too terribly difficult, but intersection will just be quite time consuming with lots of little details that need to be taken care of.  STL will be great to have so that the RepRap team can possibly start to try out Wildcat.

Second, I continue to get many requests for more Windows features and a Linux port.  I really really really want to support these platforms.  It is very important to me that Wildcat be able to include as many users as possible, and the entire kernel is being written as very platform agnostic.  But, I simply do not have the time to support these platforms myself.  Sadly, I am a Mac guy, enjoy programming for OSX, and have little desire or need to learn more platforms.  So, what I hope is out there is someone willing to help me pickup the slack for these two platforms.  The work should be mostly UI related as the kernel will continue to be developed for all three platforms.

Lastly, my "real" job is as a Ph.D. student.  For my sanity and my future I need to make sure that this keeps moving forward which will require more of my attention for the next few years.  Wildcat has been my obsession for the past three years and will continue to see significant effort from me, but I need to dial it back a bit.  Don't worry, Wildcat will still be updated almost daily, but the blog and documentation effort will see a bit of a hit.

I hope that everyone understands.  And thank you to all of the people that have voiced their support for this project.  I am happy to go it alone, but knowing that others are out there makes this journey much more fun.

Cheers,

   Graham

AFK

On Friday I update a bunch of stuff.  Sadly, most of it is not anything to get excited about.  Primarily it was cleaning up a lot of geometry generation paths.  I was starting into the STL export work and saw the sad state of some of the older Nurbs generation code, that I wrote last summer, and decided the time would be well spent improving that since so much relies upon it.

Also, this week got a bit busy at my real job since I had to prepare for an upcoming vacation.  You won't see many updates for several days as I will be hiking in the mountains.  Sorry.  On the plus side, I did make sure that everything compiles and runs OK on Windows.  I might have introduced a bug that will crash you pretty quickly if you try to project a point onto a circle.  There just wasn't time left on Friday evening to track it down and try to fix it.  I will get there, I promise.

Cheers,

   Graham

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

Trim Texture Gen Working On GPU

I spent some time today getting point inversion working on the GPU.  Once I had the algorithm together on the CPU porting it to the GPU was straightforward.  It runs pretty nicely, but is not as completely smooth as I would like.  If you are rapidly zooming in and out you can see a little stall in the zoom while the trim textures regenerate.  I think that this will begin to improve once the curve/surface generation cache scheme is in place, but that is a ways away.  I will continue to tweek until then.

So, now the only portion of trimmed surface generation that is not on the GPU is the triangulation of the inverted trimming curve points.  I am using a poorly implemented O(n^2) algorithm (ear clipping), so at some point I want to put in the effort to clean it up.  But again, that is a ways away.

With trim surfaces back working (and better than ever) Pad is completely put back together again.  We are still experiencing some problems when triangulating complex profiles, but I have a sneaking suspicion that this is a problem with arc generation but I am known to be wrong.  I will probably spend some time over the rest of this week seeing what I can dig up.  Shafts (rotated profiles) are still very broken and will need a good amount of attention to fix up.

What's next?  There are two streams of work I want to attack next.  First is implementing the topology model for Pad.  This will allow me to begin thinking about what will be needed for the boolean operations on solids.  Second is finishing up some more of the intersection routines.  These will also be needed for boolean operations.  In case you can not tell, boolean operations are the next major piece of functionality that I want to tackle.  There is just a lot of ground work that has to be done first.  Once BO's are working well then all sorts of interesting functionality can be explored.

I realized that I have not included any pictures recently.  So here are a couple to view.  The first is just a simple Pad.  The second is the results of zooming way way in on a non axis-aligned trim surface.  You can just begin to see the visual issues that come with using the trim texture approach.  Thank goodness for auto-LOD scaling to make things a bit better.

Quick Update

After yesterday's monster post I thought I would take today off.  But as luck has it I was able to finish up a few good chunks of code that got Trimmed NURBS Surfaces back into mostly working order.  If you check out the code you should be able to create nice 3D Pads.  There are a couple of gotchas though.

First, much of the trimming process described yesterday as being on the GPU is still on the CPU.  I want to make sure I have the general algorithms correct before I put it onto the GPU, mostly because it is much harder to debug on the graphics card.

Second, LOD scaling is still a bit wonky.  Zoom way in and the trim texture gets denser, as it should.  But zoom way out and you typically only get down to 50x50 or so.  This is because I am using a method similar to the LOD for regular surface vertices.  I will be able to adjust this over time to optimize the amount of memory that the trim textures soak up.  Right now they eat a lot.

Next week I hope to move more onto the GPU and to optimize the LOD stuff, but for now trimmed surfaces are back.

Have a great weekend.

Cheers,

   Graham

Trimmed NURBS Surfaces

I recently posted about some of the NURBS intersection methods I am working on.  Of course these all depend on having robust NURBS curves and surfaces.  The third leg of this stool is trimmed NURBS surfaces.  For those that don't know what these are, here is a quick backgrounder...

Take a NURBS surface and project an arbitrarily shaped closed curve profile onto the surface.  Since the profile was closed it should divide the surface into inner and outer sections.  This primary profile defines the outer edge of the trimmed surface.  Everything outside of it is "removed" from the NURBS surface.  Everything inside of it remains.

Now add additional closed profiles inside of the primary profile.  You can use this to "punch holes" into the surface.  None of these interior profiles should overlap or touch either themselves or the exterior profile.  By combining the exterior profile and some number of interior profiles you can trim the surface into just about any shape.

So how do we store, render, and evaluate such objects?  Storing them is simple.  Just capture the underlying NURBS surface (control points, knot points, degrees, etc.) and capture the exterior and interior profiles.  If you look at trimmed_nurbs_surface.h you can see this approach in action.

Here are the minimal steps I feel are required to accurately generate a trimmed NURBS surface - I will go into detail on each step:

1. Generate underlying NURBS surface points and store in VBO
2. Evaluate profile curves and store each profile in separate VBO
3. Using point-inversion, project each point from each profile onto the NURBS surface
4. Tesselate each profile separately
5. Render all profiles into a single "trim" texture

Now how about generating the underlying NURBS surface?  Here are a few really good papers on using the GPU to work with NURBS surfaces:

1. GPU-based Trimming and Tessellation of NURBS and T-Spline Surfaces
   
2. GPU-based Appearance Preserving Trimmed NURBS Rendering
   
3. Direct Evaluation of NURBS Curves and Surfaces on the GPU
   
4. Performing Efficient NURBS Modeling Operations on the GPU
   
5. Fragment-based Evaluation of Non-Uniform B-Spline Surfaces on GPUs
   

(Links go to PDFs where I could find them, otherwise you can get author and paper information from the links)

All of these papers go about rendering NURBS curves and surfaces in pretty much the same way, using the GPU.  Control point arrays and knot point arrays are converted into float textures and passed into a fragment program that calculates the exact surface position and normal.  These are passed out into two separate textures that are then converted into VBOs.  See ns_default_plM.fsh in the Wildcat SVN code to see how the fragment program works.  My version of this works in a single pass and is quite flexible.  The end result is four VBOs

• Vertex data - X, Y, Z position for each vertex
• Normal data - Normal vector for each vertex
• Texture coordinate data - parametric [u,v] values for each vertex
• Index data - vertex ordering for each triangle in the surface

Next up is evaluating each curve in a profile and building an array for each profile.  Curves are evaluated using the same method as surfaces (see above).  Instead of generating four VBOs, curves only need one - vertex position (curves don't need normals, tex-coords, or indices).  All of the curve point data for the entire profile is store in one VBO in a clock-wise ordering.  This ordering is important to remember!

Third step is projecting each point onto the surface.  You have to do this because a profile curve may not lie directly on the surface.  Plus we want to get each point from 3D "real-world" space to 2D "parametric" space.  Meaning, each point must be located in the [u,v] parametric space of the NURBS surface.  This is important because when we render the trim profiles we render them into a texture that goes from [0,1] in both the u and v directions.  Make sense?  Ok, so to do this we again use a fragment shader with access to textures containing all of the NURBS surface control points and knot points.  The shader takes a single point input (the profile curve point) and outputs the point-inverse into another texture.  This texture is then converted into a VBO.  Now we have a VBO for all points in a profile that are all in [u,v] space.  Paper 4, section 4.2 goes into a little more detail about this step.

Fourth step is tessellating the profile (also called polygon triangulation).  Why do we have to tessellate?  Fundamentally each profile is a closed regular polygon, but it may be either concave or convex.  If every profile were convex no tessellation would be necessary, but in order to handle concave profiles we must tessellate.  I have not found a good parallelized (or GPU-based) tessellation routine.  For now I am using a CPU-bound version of ear-clipping, but I may move to using Triangle (by Johnathan Shewchuck).  The input to this is the VBO of [u,v] points.  The output is an index for triangle ordering.  There really should be a good way to do this on the GPU, just haven't gotten there yet.

The last step is rendering all of these profiles into a trimming texture.  This process is very simple.  I set up a FBO that covers the [0,1] space for both the U and V axis.  The FBO is cleared to be all zeros.  The outer profile is rendered into the FBO (using the tessellation index) filling its internal area with ones.  Each inner profile is then rendered filling their interiors with zeros again.  In the end we have a texture that has ones where there is a surface, and zeros where there is not a surface.

When it comes time to render the trimmed NURBS surface we start just like a regular NURBS surface.  One extra step is added in the fragment shader.  A quick texture lookup is performed into the trim texture to get the value of the texture for the [u,v] of the fragment.  If the value of the texture is one, the fragment is rendered, if the texture value is zero the fragment is discarded.  Simple and easy, right?

This method is very high-performance.  With the exception of the tessellation step the entire process runs on the GPU in just four passes.  I have run tests where >6 million vertices are evaluated and trimmed in a second.  Not too bad.  If adaptive LOD scaling is added, this should be the final approach needed to make Wildcat very very fast.

So where are we at?  Steps 1, 2, 4, and 5 are pretty much all done.  I will be spending the next couple of days working on finishing the GPU version of step 3 (point-inversion) and cleaning up the code to support LOD.  Hopefully by early next week trimmed surfaces will be back.

If you have some insight into how to either avoid the tessellation step or how to parallelize it on the GPU please let me know.  This would make a big difference.

Cheers,

   Graham

Platforms and Installers

Last night I decided for some crazy reason that I wanted to get the PPC/Tiger version up and running.  So I spent a couple of hours and figured out three things.  First, the Accelerate framework for Mac makes major use of the SSE2 instruction set.  So I had to work around this with a couple of better crafted #ifdefs.  Second, the Tiger version of glext.h is missing two of the extensions I make use of for some of the high-end generation routines (GL_EXT_transform_feedback and GL_EXT_geometry_shader4).  Again, a couple of good #ifdefs seem to have taken care of this.  Finally, there must have been a couple of 32-bit to 64-bit changes going from Tiger to Leopard that I was not aware of since I still have a few issues left with the GUI calls.  I hope to clear this up tonight and get everything compiling for 32-bit and PPC and Tiger.  Weeeee!

Also, I took a look at InnoSetup for creating a good Windows installer.  What a massive improvement over deployment projects within Visual Studio.  Way way way way way way better.  I have an installer mostly done and just need to wrap up two things.  First, I need a good stable version of Wildcat that is worthy of a binary distribution.  Second, I need to determine exactly what .dll's need to be distributed with the app.  Mostly these will be VS run-time files.  I should have this done later this week.

Tomorrow I hope to finish up with CCI and CLI and begin moving on to SLI, SCI, and SSI.  I also need to fix up trim surface generation.  That is still very broken.  Blah.

Cheers,

   Graham

GPU Curve-Curve Intersection

I was traveling this weekend so I printed out a couple of recent conference papers to read while in the airports.  The SolidModeling annual conference was just held in early June.  Usually it has some very interesting results for those of us that dabble in solid modeling.  I came across a paper that was an extension of something I saw last year.

Sara McMains' research group out of UCB has been doing some great work on GPU-based NURBS generation and manipulation.  My research last summer that culminated in the genesis of Wildcat parallels much of what her group published in "Direct Evaluation of NURBS curves and surfaces on the GPU."  The approach you see in Wildcat for using the GPU to generate NURBS curves and surfaces is very similar to hers.

This year her group has followed that paper with "Performing Efficient NURBS Modeling Operations on the GPU."  I will let you read it because it is pretty good.  They tend to use too many passes on the GPU while I consolidate down to one or maybe two passes, but I like their approach.  I have not reviewed it in detail, but their stream-reduction algorithm seems very promising.

So, today I took some time and reworked my curve-curve intersection (CCI) algorithm to use the GPU akin to what you see in the McMains paper.  Overall it seems to work really well.  We are probably getting a 20-50x improvement in performance.  Not too bad.  There are still a couple of details to clean up, but this should be the way of the future for Wildcat.

Also, I got some good messages over the weekend about a broken Windows build.  I cleaned up the VS project (and moved all of the code to a VC9 project).  So you Windows folks, please try again.  Tomorrow I am going to take a shot at surface-surface intersection.  Should be pretty easy since I can pattern off of CCI.

Cheers,

   Graham

PartPad is back from the dead - almost

When I set about restructuring the 3D feature code I quickly killed the Pad and Shaft features.  They both died in the aftermath of auto-LOD and topological-correctness.  Between the checkins I made yesterday and those from today, I am happy to say that Pad is back!

Here is a quick review of the primary changes:

1.  Instead of having one surface for the top of the pad regardless of the number of separate bodies there should be one top and one bottom per body.  This is almost done.  I am up to the last step of where the actual surfaces are generated.  All of the data necessary is now in place.  Should be done tomorrow.
2. Topology model generation wasn't even a thought in the old version.  Now as the extrusion points, curves, and surfaces are being generated they are recorded in way to greatly ease the topology model creation.  Again, I am just up to the point of creating the topology model.  I am going to spend tonight figuring out the algorithm details and tomorrow hope to implement and do some testing.
3. Points!  An eagle-eyed user would have noticed that no points were ever generated with a Pad.  I only had curves and surfaces.  Now points are there and are correct.  Yahoo.
4. Initial code is in place to eventually support pads that go "UpTo".  Here is the list of types I want to be able to support: Dimension, UpToNext, UpToLast, UpToPlane, UpToSurface.  Right now only Dimension works, but we shouldn't have to change the object interface much in the future.

Lastly, the code is much more efficient and logical now.  When I first wrote it I just wanted to make sure that it worked.  Now it not only works but works well.  I hope to finish up all of the little details tomorrow.  Next week I want to get shaft back working.

Once these two are back I can move on to boolean operations with the solids.  That will be the crazy cool stuff.

Cheers,

   Graham

Topology Models

Before I get Pad and Shaft back working I want to finish the initial topology implementation.  If I am going to spend a lot of time reworking the 3D features I want to make sure I can incorporate full topology support.  What is topology support you ask?  Great question...

You see, geometry is only half the picture.  Geometry itself doesn't understand the relationships between various curves and surfaces.  Take a cube for example.  The geometry of a face from the cube doesn't know (or need to know) all of the edges that bound it.  Instead there is a co-model that just captures these adjacency relationships.  This information becomes very useful (and is pretty necessary) for operations like Union, Subtract, Intersect, and Slice (these the the boolean operations).

I am using a topology model called the Radial Edge data structure.  It was developed by Kevin Weiler as part of his Ph.D. research.  The best source of information about it is in his dissertation, "Topological Structures for Geometric Modeling."  The radial edge structure is a variant of the venerable Winged Edge structure described by Bruce Baumgart.  The biggest improvement is the ability of the radial edge structure to model non-manifold topology (NMT).

Solid models should be 2-manifold.  This means that an edge is bordered by exactly 2 surfaces.  This means that all objects being represented are solids.  There would be no lines, points, or surfaces that are not part of a solid.  This isn't exactly what we want.  Take sheet metal for example.  Most CAD packages represent sheet metal with just a surface, there is no thickness.  Our topology model needs to be able to handle this.  So that is why we need NMT.

Anyway, you can find a good bit of info about NMT and 2-manifolds on the web.  Most of the solid modeling kernels are able to handle NMT.  I am going to spent the next couple of days getting the data structures into place.  It will take way way longer to get the boolean operations working.  But with data structures available I can then patch up some of the 3D features (pad especially).

Cheers,

   Graham

P.S.  I really want to get to a useable version of the software before I create a Windows installer, so it could be a few days (or a week or two).  If you want to try out the app, you can download MS Visual Studio 2008 (there is a free version) and compile the code yourself.  Sorry for asking this of you.

Development Update

It has been a few days since my last progress update and there has indeed been progress.  Automatic level of detail scaling is pretty much done for NURBS curves and surfaces.  Trimmed NURBS surfaces are a whole different matter.  Let's talk about the first two...

Each NURBS curve and surface maintains lists of vectors for control point and knot points.  Using this data there are at least three methods of generating buffers of vertex data.  I call them "High", "Medium", and "Low".  This refers to the theoretical performance of each path.  The high path makes use of very recent GPU enhancements.  The medium path can be used on GPUs that may be a few years old.  The low path is purely CPU bound.  There are also one or two specialty routines optimized for certain conditions (think surfaces with only four control points and such).

Each of these paths can now place their generated vertex output into either server side (on GPU memory) or client side (on CPU memory) buffers depending on which is requested.  This is done as a "service", in that vertex buffers can be generated for anything, not just rendering.  For example, the current curve-curve intersection algorithm generates a buffer of vertex data for each curve and then uses this data to test for intersection, all on the CPU.

In order to get LOD scaling I needed to re-implement the way that these buffers were being generated and maintained.  Previously each curve or surface could only manage generating one buffer which then had to be reused for both rendering and intersection and whatever else.  Now buffer management is up to whatever asked for the buffer to be generated and memory capacity is the only limit.

I was already passing in the current camera zoom factor into all rendering methods but was not making use of it.  Now the zoom factor is used to determine an optimal level-of-detail.  If this LOD is close to the LOD of the render buffer nothing happens.  If the ratio of optimal-LOD to current-LOD gets too far off then a new render buffer is generated.  Overall a pretty good approach I think.

At some point I want to implement a vertex buffer caching scheme.  Right now if the rendering routine generates a buffer and then an intersection routine also generates a buffer with the same LOD then two identical buffers get generated.  It would be great to better coordinate between them somehow

When it comes to intersection routines my previous estimates of expected code completion were way way off.  I pretty much ended up scrapping all of the prior code and started over.  There was good reason for this but it required a lot more work.  I now have 6 of the 15 routines nearly done.  The remaining 9 are all of the ones for NURBS surfaces and trimmed NURBS surfaces.  I have an approach in mind for these, it will just take time.

While doing all this work I noticed how incredibly crappy my implementation of trimmed NURBS surfaces was.  It worked, just not all that well.  I have decided to rewrite most of it.  Right now it is mostly trashed.  This also led me to look at the code for Pad and Shaft (the two 3D features I had implemented).  They were pretty weak also, mostly just proof-of-concept code.  I have completely gutted them and it will take a couple of weeks to get them back in shape.  As a result the code I will check in this weekend will fix all of the stuff from above, but will kill off any 3D stuff for now.  It all compiles but will SEGFAULT quickly upon use.  Progress!?!?

Cheers,

   Graham

Why not wxWidgets or Qt

I have had a number of people ask me about why I have chosen to not use a cross-platform GUI toolkit like wxWidgets.  There are several reasons for this and so I wanted to explain my reasoning.  There are a bunch of very good choices for GUI toolkits.  I spent a good amount of time evaluating a selection of them: GTK+, Qt, wxWidgets, Fox, and others.  I decided that I wanted to try something a bit different for two primary reasons.

As I see it, there are four primary GUI components that all contribute to the Wildcat user experience:

1. Primary rendering window
2. Toolbars
3. Menus (both context and primary)
4. Dialog windows

The primary render window is pretty straightforward to implement and get right.  I have it mostly up and running on Mac and Windows, and GTK+ for Linux should not be difficult.  The primary render window won't change much over time.  It renders using OpenGL.  It's a window.

Toolbars are a more complex issue.  What is a toolbar?  A toolbar looks really different on Mac vs. Windows.  Toolbars need to be very flexible and change constantly depending on the tasks the users is executing.  They need to be dynamic and configurable.  I have a first shot at the Mac version, and hope to incorporate the Windows ribbon interface down the road.

Menus are similar to toolbars.  They change a lot, very dynamic.  But I don't feel they are as complex as toolbars since they tend to not be user configurable.  I have not done much with them yet on either Mac or Windows.  In time...

Lastly, dialog windows.  For CAD applications the dialog windows seem to define a lot of the user experience, but they are slowly giving way to a better mouse interaction models.  I want traditional dialog boxes, but not in a traditional way.  I want them to be much more customizable.  Read on to see where I am going with this.

So, back to the two primary reason I have decided not to go with a cross-platform toolkit.  Here we go...

Reason 1: Cross-platform does not mean platform specific

As I mentioned above toolbars on Mac are a very different concept than toolbars on Windows.  On Windows they are strips of icons that typically dock to a portion of a window.  The OS X interface is moving towards a "pallet" concept.  The toolbars are placed together into a separate tabbed window that sits to the side of the primary window.  Can you imagine the Windows ribbon on a Mac.  Not going to happen.

For another example look at multi-document interface applications like MS Word.  If you open a bunch of Word docs on Windows you get one window with many child windows within it.  On Mac you get multiple windows.  Same concept, very different approach.

My feeling is that as users approach an application for the first time they tend to have all of the memes of the OS in mind and are expecting a similar experience.  That is what makes a Mac a Mac.  This philosophy is much stronger on Mac than Windows.  MS has taken a hands-off approach and you tend to see a wider range of look-and-feel on Windows.

When I looked at the cross-platform toolkits they all seemed to make your application look the same regardless of what OS it ran on.  In my opinion it should be the other way, your app should look like the OS it is running on.  While this may increase developer effort, I feel that it will pay for itself with a better user experience.

Reason 2: I want traditional dialog window, but not in a traditional way

In the intro to this post I spoke about dialog window being fundamental to the CAD user experience.  If Wildcat doesn't use a cross-platform toolkit doesn't that mean every dialog window will have to be re-coded for each platform?  The traditional answer would be yes.  I think that I may have a way around this...

I have embedded the open source WebKit HTML rendering engine into Wildcat.  All Wildcat dialog windows are actually simple platform windows with a web browser pointing to a local file.  Here are the advantages to this approach:

• Cross-platform solution - WebKit runs on Mac, Win32, and has a GTK+ port
• High-performance JavaScript engine for free - now we have a scripting engine for Wildcat operations too
• Change the CSS, change the look-and-feel - this makes it possible to easily "skin" Wildcat to provide a new or different look
• HTML is really easy to program - Who hasn't created a web page?
• Dynamic generation - why not generate HTML on the fly?  Crazy idea, I know.

OK you say...interesting approach.  How do you tie the dialog window actions to the core app and visa-verse?  WebKit has JavaScript hooks for all pages it renders.  I created similar hooks in Wildcat that allow data and events to be passed back and forth.

There are slight performance implications to this approach, but they are really minor and the user should never even know what is happening.  It should make it very easy to expand and change Wildcat.  There may still be hurdles I have not foreseen, but as of now it seems to be working quite well.

I have only implemented this for the Mac.  If you are using a Mac when you first start Wildact you are asked what type of document you want to work on.  That window is just a web browser pointing to docTypeSelector.html.  Give it a try.  Kind of fun.

Let me know what you think.

Cheers,

   Graham

Great Response

As many of you know I sent an article to upFront.eZine about Wildcat.  I wanted to introduce more people to the application and start to build an audience.  I am really overwhelmed by the response.  Throughout today I have been getting a great stream of emails from around the world asking about Wildcat.  Wow!!!  Thanks Ralph.

A lot of people are trying out Wildcat.  There are some mixed results.  Most of the users appear to be Windows folks, so they are having to compile the code themselves.  I hope to have a Windows binary installer out soon so please bear with me.  If you are having problems please post your question to the Wildcat mailing list here.  I am getting back to everyone pretty quickly.

I also wanted to let you know about the progress I have been making over the last few days.  I got automatic level-of-detail working for all curves and am very close to completing surfaces.  I also completely rewrote the chunk of code that handles all types of geometric intersection but it still has a couple more days worth of work to go.

I made the mistake of checking in part of this code yesterday so if you download from the SVN you may get some pretty funky behavior when trying to use either Pad or Shaft.  This should be fixed as soon as I get the intersection code working again.

Thanks for all the great feedback.  And please let me know if you want to help out, especially on getting the Windows port up to speed.  My MFC/Win32 skills are complete garbage.

Cheers,

   Graham

Tasks Update

Yesterday I outlined my top development priorities.  Being a hot and lazy Saturday here in Nashville, not much is getting done, but I thought that I would update you on my progress yesterday.  I was able to get the majority of the groundwork done for all of the various geometric intersection routines.  With 5 types of geometry (point, line, NurbsCurve, NurbsSurface, and TrimmedNurbsSurface), there are 25 possible ordered intersections.  That is easily reduced to 15 types when order is not a factor.  Of those 15, I pretty much wrapped up 3 of them.  But I also outlined the other 12.  Now I have to get level-of-detail stuff working and then I can wrap up intersections.

For LOD I was able to layout nearly all of what needs to be done.  It should take me only a couple of days this next week to implement and test.  So, I hope that by the end of next week you all will get to start experiencing some of the new code.

Have a great weekend.  Cheers,

   Graham

What I'm Working On

Today I will layout a bit of the items I am working on.  Since starting up this blog and the code site, I haven't been able to spend quite as much time coding as I would have liked, but it has been fruitful to begin getting the application into others' hands.  I am still working through a couple of deployment bugs (most notably a .dll dependency issue for the Windows version), but hopefully I will have solid versions and installers for both platforms soon.

Also, I have had someone express an interest in starting some of the work for porting Wildcat to Linux and GTK+.  This should be really straightforward since Mac already uses GCC 4.2.  The GTK+ GUI work will be the main hurdle.  For the time being, the Mac version will continue to lead the pack for GUI and overall functionality.

Ok, here are my top development priorities right now:

1)  Automatic level-of-detail scaling for all geometry - this means that as you zoom in and out the level of detail of each piece of geometry will react accordingly.  Right now geometry is generated once and you are stuck with it.  Zoom way in on a circle and it starts to get chunky.  Also, this will enable out-of-view culling.  Meaning that if a portion of the geometry is not visible on the screen, it just won't be drawn.  A nice optimization as we try to move towards more complex geometry and assemblies.

2)  Topologically correct Pad and Shaft operations - right now if you sketch two circles that don't overlap or touch and extrude them, the kernel will treat them as one surface.  Obviously this is not correct, they should be two surfaces.  This was done originally as an optimization, but now I see the folly of my ways.  All of the infrastructure needed for this is now in place, I just have to spend a lot of time massaging the relatively complex pad and shaft operations to be smarter.

3)  Manifold/Non-Manifold topology representation.  All solid geometry should be 2-manifold.  This just means that it is a valid solid.  This is necessary to provide boolean operations (add, subtract, and union).  Most of the data structure work is in place, now I just need to clean that up and add topological operations to all 3D features (pad and shaft right now).  Strangely, this work is completely separate from #2 above.  For more detail about this topic read "Topological Structures for Geometric Modeling" by Kevin Weiler.  This is a great dissertation about non-manifold topology and boolean operations.

4)  Geometric intersections.  There are four basic types of geometry in Wildcat: point, line, curve, and surface.  I started with no line primitive, but there are way too many optimizations for lines so they got added as a separate class.  All curves and surfaces are 64-bit NURBS representations.  This provides for extremely accurate geometry.  With 5 classes there are 15 possible types of intersection, here is their status:

• Point-Point: 100% done
• Point-Line: 90% done
• Point-Curve: 75% done - need to clean up point-to-curve projection algorithm
• Point-Surface: 50% done - need to clean up point-to-surface projection algorithm
• Point-TrimSurface: 0% done
• Line-Line: 75% done - need to handle overlap case, not just single-point intersection
• Line-Curve: 75% done - need to handle overlap case, not just point intersections
• Line-Surface: 0% done
• Line-TrimSurface: 0% done
• Curve-Curve: 75% done - need to handle overlap case, not just point intersections
• Curve-Surface: 0% done
• Curve-TrimSurface: 0% done
• Surface-Surface: 0% done
• Surface-TrimSurface: 0% done
• TrimSurface-TrimSurface: 0% done

As you can see, anything Surface/TrimSurface related needs work.  This is a very complex space with lots of research having been done.  There are a ton of different Surface-Surface-Intersection (SSI) algorithms out there.  I am currently cleaning up some of the general intersection infrastructure and then plan on taking a shot at SSI.

5)  Boolean operations.  These functions will allow for realistic and complex 3D parts to be created.  They are absolutely fundamental to getting the Wildcat kernel where it needs to be.  They are also wildly complex and rely upon nearly all of the above work.  This is the #1 item I want to get working, but I have a ways to go.

6)  Geometric constraint solving.  2D sketches can be created and have basic constraints added to them, but right now these constraints do nothing but look good.  There is really only one GCM engine in commercial use (by D-Cubed - a division of UGS), and a handful of academic ones.  I have spent a great deal of time looking into this, and I think that with a few months of good work I could get one working.  This is important but a lower priority than Boolean Operations.

Wow, lots to do.  When these items are in place it should be possible to quickly add the tools to build nearly any type of 3D part.  This is when I see Wildcat really starting to take off.  I have no idea how long it will take but summers do tend to be my productive time.  This being said, I would really love to get help.  If you want to take a shot at any of these items, please feel free to contact me.

Cheers,

   Graham

System Requirements

I have been getting feedback from a few users and this is proving very useful.  I have not previously published what the system requirements are for running Wildcat, so here goes:

For Windows Systems

• Windows XP
• Pentium 4 class processor or better (1.5GHz+ preferred)
• At least 50MB of disk space
• At least 1GB of RAM
• OpenGL 2.1 capable video card with 128MB of RAM

Note: The graphics card requirement is the most important.  All aspects of Wildcat presume that you have a relatively recent video card and up-to-date OpenGL drivers.

For Mac OS X

• OS X 10.5 Leopard (Tiger may work, but I have not tried)
• Intel 32/64-bit processor
• At least 50MB of disk space
• At least 1GB of RAM
• OpenGL 2.1 capable video card with 128MB of RAM

Note: Apple provides a software fallback path for machines that don't have compatible video cards.  While I have not tested this, it should at least make it so that all Intel Macs can run Wildcat.

My Development and Testing Setup

Just to help folks out on what I am working with and to give you an idea of what should work here are the two systems I use on a daily basis:

Primary Development -

Apple MacBook Pro

OS X 10.5.3

2.4 GHz Intel Core 2 Duo processor

2GB RAM

40GB HD partition

nVidia GeForce 8600M GT w/ 256MB video RAM

XCode 3.1 development environment

Windows Development -

MS Windows XP SP 2

2.2 GHZ Intel Core 2 Duo processor

2GB RAM

160GB HD partition

ATI Radeon HD 2400 XT w/258MB video RAM

MS Visual Studio 2005 development environment

For just running Wildcat you should not need Visual Studio or XCode.  They are necessary only if you are planning to compile Wildcat yourself.  I am going to post this content into the Wiki also.  Please let me know if you have any questions.

Cheers,

   Graham

Setting Expectations

I want to set some expectations about Wildcat.  People are starting to look at the application and are starting to use it, all of which makes me very excited.  But this also means that people are pushing it in ways that I have not.  Again this is a good thing.

As of right now Wildcat is not capable of replacing any existing CAD application.  There are just too many gaps in its functionality.  What I hope it can do it show what is possible.  I am continuing to work on it daily, but one person does not a CAD app make.

In an effort to properly set expectations here is a quick list of major things that Wildcat currently can NOT do:

• No boolean operations (add, subtraction, union) of solids
• No geometric constraint solving
• No part assemblies
• No drafting
• No dress up features (fillets, drafts, chamfers, etc.)
• No changing the name of any feature
• No setting the color of any feature
• No importing or exporting on non-native file format
• No analysis (FEA, CFD, etc.)
• No a lot of other things

I have been concentrating on getting basic infrastructure in place and getting good 2D sketching and basic 3D part features (extrude and revolve) working.  I want to work on all of the list above, it will just take time.

Over the last year Wildcat has evolved substantially.  There is still a really really really long way for it to go.  I would love and appreciate help and I have tried to make the code approachable and understandable.  If you would like to jump in and help turn Wildcat into the application we all want it to be, please contact me at graham.hemingway@gmail.com.

Cheers,

   Graham

Application Installers - Part Deux

There should now be automated installers for both Windows and Mac posted.  They should both work well, but let me know if you have any issues.  Due to platform differences the two installers do quite different things.

Windows

Since Windows does not have a "bundle" in the Mac sense I am just locating everything inside one simple directory.  The installer should create \Wildcat wherever the app is installer (into Programs Files by default).  Inside \Wildcat there should be six file and one sub-folder.  The files are the primary executable (Wildcat.exe) and the five dependency libraries.  The sub-folder should be named Resources.  It contains all of the .tiff image, configuration XML files, and OpenGL shaders (.vsh, .gsh, .fsh).  With this, you should be good to go.

Mac OS X

On Mac there is a "bundle" concept.  All of the *.app objects in the /Applications directory are not single object, they are actually folders.  Inside these folders are most of the necessary files for the applications.  On Mac the only external dependency library Wildcat requires is xerces.  On Mac the xerces dylib has to be installed into /usr/local/lib.  In addition, Mac is much more specific about the permissions on all of the files.

With all of this in mind the Mac installer should copy Wildcat.app to the selected location (/Applications by default).  It will also copy xerces-c.28.0.dylib into /usr/local/lib and create two symbolic links (xerces-c.dylib and xerces-c.28.dylib) in the same directory.  These both point to the actual library.

Down the road I really need to improve the Mac installer to conditionally install xerces only if it does not already exist.  Have a try with either the Windows or the Mac version.  I welcome feedback.

Cheers,

   Graham

Application Installers

Last week I began posting the source code for Wildcat CAD here.  I also want to provide binaries for both Mac and Windows.  I have never really distributed applications before, so I did not have all the details down.

I found out there there is quite a difference between developing the code and just trying to run it.  There has been a dependencies directory in the source code from the beginning, but I hit a couple of snags in distribution.  On OS X the application would not run and exited with an error about not being able to find the xerces-c library (I use xerces for easy XML parsing and generation).  I opened a bug on this and today set about trying to make a nice installer for Mac.

Mac has some really easy deployment tools included in the developer package.  So I have spent a bit of time working with it, and I think (still in testing), that I now have a basic OS X installer.  I should wrap up testing on the installer by EOD today and will close the bug.  One important point.  Right now the OS X version of Wildcat CAD only supports 10.5 and Intel.  If there is sufficient demand I will see about putting out a Tiger version and maybe a PPC version.

In the grand scheme of things having nice installers is probably pretty low on the functionality list, but I really want to encourage users to try out the software and having a drop-dead easy deployment is a really important part of this.  Maybe I will even work on some code today.  Tomorrow is Windows installer day!

Cheers,

   Graham

Editing Sketches

In the past few posts you have been introduced to 2D sketching in Wildcat CAD, and have learned about some of the basic sketch constraints you can apply to 2D features.  In this post I will briefly discuss how to edit various sketch features.

First of all, you can select any sketch feature by clicking on it.  It should turn red.  You can also click-drag a selection box around features.  Using this method you can select multiple features.  Likewise, by holding down the Command key (OS X) or the Ctrl key (Windows) you can click select multiple feature.  You can only edit one feature at a time.

Points

Points are so simple, just grab the point and drag it to where you want it.

Lines

Lines can be edited in two ways.  First, you can grab the end of the line and just move that end around, or second, you can grab the line in the middle and it will move the entire line.  If you are moving the entire line then its orientation (slope) and length will not change just its horizontal and vertical position in the sketch.

Axis lines behave just like regular lines.  They can be adjusted from either end or positioned by grabbing the middle.

Circle

Similar to lines, there are two ways to edit circles.  The first way is to grab it anywhere on the circle itself.  This will allow you to change the radius of the circle.  If you grab the center point of the circle you can then edit the horizontal and vertical position.

Arcs

If you are not familiar, a two-point arc is drawn by first clicking the center-point of the arc, then clicking the start of the arc, finally clicking the end of the arc.  In essence, the first two clicks define the radius, hence two-point.  A three-point arc is drawn by clicking one end point, then clicking the second end point, then finally clicking a third point somewhere else on the arc.  It takes all three clicks to define the radius of the arc.

If you grab any part of an arc itself you can adjust its radius.  The orientation and arc-angle will remain the same.  If you grab the center-point of the arc you can reposition it within the sketch.  As of now, there is no way to adjust the arc-angle or the location of the start or end point.  This is something I want to add down the road.

Ellipses

Ellipses have multiple adjustments that can be made.  First is by grabbing the ellipse anywhere on the boundary, except where you see the point on the semi-major and semi-minor axis, or on the center point.  This will allow you to reposition the ellipse.  If you grab the semi-minor axis point you can adjust the radius of the semi-minor axis.  If you grab the semi-major axis point you can adjust that radius and also change the orientation of the ellipse overall.

There is currently a "bug" that needs to be fixed in ellipse editing.  You have to be sufficiently zoomed in on the ellipse to be able to grab either the semi-major or semi-minor points.  Otherwise you will only be able to adjust the position of the ellipse.  If this is happening to you, just zoom in more on the point you are trying to grab.

Conic Sections

As of now you are not able to edit conic sections.  Down the road I plan on adding this capability.  Sorry!

Well, that's all for today.  There are just a couple more posts left on how to use the Sketcher Workbench in Wildcat CAD.  Keep an eye out on the Wiki for some tutorials.  I will also try to update these posts as I make fixes and enhancements.

Cheers,

   Graham

Sketch Constraints

In the last post I discussed some of the initial 2D sketching capabilities of Wildcat CAD. In this post I will expand on that a bit and talk about the dimensional and geometric constraints that can be added to 2D sketches. Here is a quick status on all of the planned constraints:

Dimensional Constraints

• Length
• Angle
• Distance (works for some features but not all)
• Radius

Geometric Constraints

• Fix
• Coincidence (line-line only as of now)
• Horizontal
• Vertical

To Be Implemented Constraints

• Semi-major & semi-minor axis
• Concentric
• Tangent
• Parallel
• Midpoint
• Perpendicular
• Symmetric
• Equidistant point

In the picture below you can see a selection of these constraints:

Where the lines of the rectangle meet (created using the Rectangle profile tool), you can see small points. These are the coincidence constraints.  Next to mostly horizontal or vertical lines you can see the appropriate constraint.  I created an angle constraint between the two lines in the upper left corner.  Both the arc and the circle have radius constraints.

It is important to note that as of right now these constraints are not being using to properly constrain the sketch.  It is our goal to move in that direction in the near future, but for now the constraints are just visual objects.

If you move the lines or edit the arc and circle, you should see the dimensional constraints change value.  If you change a line from vertical to not vertical, the vertical constraint will not go away.  This concept applies to all geometric constraints for now.

As with all other sketch features, constraints created in a sketch are show in the specification tree when in 3D mode.

Tomorrow I will add some more detail about editing sketches.

Cheers,

   Graham

P.S.  In addition to adding comments to this blog, you can also visit the Wildcat CAD discussion group. 

Initial Capabilities - Sketcher Basics

In the first post I provided some of the background on why I have started Wildcat CAD.  In this post I want to outline what capabilities are currently available in Wildcat and what are the highest priority planned improvements.

2D sketching is pretty well supported at this point.  I have implemented the following 2D primitives:

• Conic Arc (both 2-point and 3-point)
• Circle (center-radius)
• Axis of revolution
• Conic section
• Ellipse
• Line
• Point
• Rectangle (resolves to 4 lines)

With these primitives I have been able to draft a wi

de variety of 2D sketch profiles.  Once you have drawn a sketch and exit back to 3D design (called Part Design Workbench) the sketch is automatically analyzed and Sketch Profiles are generated.  Below are two quick sample sketches I drew:

A Sketch Profile is an ordered series of 2D primitives that are connected by their end points.  Profiles can also be linear - no more than two primitives ever connect at a single end point.  They can also be open or closed - closed will separate the sketch into two portions, inside and out.  For doing something like a 3D extrude (called a Pad), a profile must be connected, linear, and closed.

Pretty much all of the 2D primitives are editable.  Just grab them and they can be moved around.  They will not stay connected to other primitives though.  That is a function of sketch constraints.  Constraints are not yet working, but a lot of the infrastructure is in place so hopefully they won't take took much longer.

If you want to try out making your own sketch, try following the Sketcher Tutorial.

Cheers,

Graham

Welcome to Wildcat CAD

Hello,

This is the first post as I begin to make Wildcat CAD more public.  Today I am going to give you a bit of background on why I created Wildcat and where I want it to head.  In the future I will try to limit myself to more technical aspects of the app.  All code can be downloaded from here.

From as young as I can remember I have loved to design and build things.  Cars, boats, robots, and especially airplanes have always been active in my imagination.  For various reasons I decided to pursue computer science related fields and wound up in graduate school slows gaining ground on a Ph.D.  This was three years ago.

After I graduated from college (about 9 years ago), I went began to look seriously into buying a CAD package to begin designing all that stuff in my head.  I was shocked to learn that the packages were massively expensive ($6k for a "cheap" one and $20k+ for the top-of-the-line).  Plus they all seemed very difficult to use and placed way too much emphasis on buying education from a reseller and too little on just helping the user.

Over the last nine years I have seem the open source software movement gain traction and always hoped that a good quality CAD package would make its way onto the scene.  Needless to say, after all these years there just were not any good choices.  OpenCascade, BRL, and AvocadoCAD all missed the mark as far as I was concerned.  In future posts I will go into more detail on each of these packages and what they lack in my opinion.

Around a year ago I made the decision to try developing my own CAD framework.  I have spent a great deal of the last year working through the basics and am ready to show the world what I have been working on.  I can not stress enough that Wildcat CAD is just at the beginning of its path.  Over the next few years I hope to bring it to where I need it to be.  And I hope that some of you will join me.

Here are some details about the initial release:

1. C/C++ based
2. B-Rep 3D solid modeling kernel
3. 64-bit precision NURBS-based curves and surfaces
4. Developed on OS X, ported to Windows (really want to do linux also at some point)
5. External dependencies: xerces, OpenGL, STL (freetype, libtiff, and pthreads on Windows)
6. Minimal GUI as of now, mostly mouse and keyboard shortcuts
7. File-based persistence using XML-based structure
8. No import/export capabilities yet

This is really just the technical aspects of Wildcat.  In the next post or so I will go into detail about what user capabilities are/are not present.  I will also start to talk about what functionality I am working on and where I could use the most help from anyone willing to lend a hand.

The tag line for the Wildcat CAD website is "Open Source CAD - finally" because I believe the time has come to have a good open source alternative to the closed legacy CAD vendor applications.  I think that many of you agree with this feeling.

Cheers,

Graham