Let's Make Robots!

I am thinking of writing a cad tool

So I've tried about 10 different CAD programs now to try and create my robot models, and am quite simply.. ANGRY! Apologies if this post sounds a little ranty - I'm just a bit fed up, so try and read this post with your angry filter on :)

Every program seems to have it's floors or problems, that seem to come from 2 distinct areas:

  • A massive feature set, which makes it hard to learn, and often results in lots of bugs - too many features = too much to fix
  • A focus on the maths and coolness, without massive consideration of UI or visualisation

The thing is, this doesn't seem like a massively complex problem. OpenSCad demonstrates how few features you really need to build up a good 3d model - it consists of a few primitives that can be combined to do all kinds of awesome things. Unfortunately it contains lots of bugs and has very little focus on usability. Simple things like syntax highlighting, shadows or custom lights to make visualisation easier and nice material settings haven't really been focused on.

At the other end of the spectrum you have things like google sketchup which has a great interface, but when you get down to the nitty gritty with things like CSG it doesn't cut it.

Alternatively you have art packages like 3ds max or Maya. While these do their job well, they simply aren't targeted at making precise models.

And of course you've got the really powerful stuff like SolidWorks or AutoCad, but they cost a lot, and I just don't want to pirate things. As a software developer that makes me feel bad, and pirating is just a pain in the rear end anyhoo :)

So here's what I think a nice starting feature set would be (based on what I need):

  • Ability to program components (aka OpenSCad), or draw them. Initial focus on programming them as it's simpler.
  • A simple set of primitives that can be combined using CSG.
  • Entirely based on convex object combinations, which keeps the maths simple!
  • I should be able to take a diagram of a component with a list of measurements, and fairly quickly enter the bits needed to display it as a model
  • Rendering should be of a quality you'd expect out of todays machines - nice lighting, shadows and projections to indicate positioning of objects relative to each other

As a game developer I've got a fair bit of experience in UI, maths and graphics code, so really do think I should be able to do a good job. My gut says to write it in c# using wpf, eventually moving the expensive bits into a c++ library.

I'd be interested in what people think of what features are needed, and if anybody fancies helping out. I've not decided whether to actually write it yet, but it really does seem like a simple problem. Better still, there's lots of examples of bits that work well out there - there just isn't 1 program that wraps them all up in a nice package and doesn't have loads of other issues

thoughts / comments / statements that I'm insane? :)

-Chris

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

So I've had more of a think, and I reckon convexes are the way to go. It'll be based on something along the lines of this paper: http://www.cs.huji.ac.il/~arir/cda.pdf, however I intend to represent the scene solely with positive (i.e. solid cells), whereas the algorithm above has a concept of 'negative cells' - i.e. empty space. I'm going to treat these simply as a result of doing a csg subtraction of 2 positive cells. The key part comes down to clipping convexes against each other to generate new convexes.This diagram shows the basis of the algorithm in 2d, but I think extending to 3d is just a case of clipping aginst face planes instead of edge lines:

Like most algorithms it has a few floors - mainly to do with level of detail of things like spheres/cylinders. I reckon that can be handled though. Additional optimisations I can think of are avoiding excess generation of convexes (i.e. don't split a poly if it it's outside the csg region and is already convex). It does have the very nice property that it's easy to identify faces and edges, so things like sketchup style face extrusion should be easy to implement. 

There's also never a need for convex decomposition, as you never end up with convave objects, which makes the maths much much simpler. If you wanted to load meshes in then you'd need to decompose them, but 1 step at a time :)

Obviously lots more work to do, but it seems like a good foundation to build on, with a need for just 1 simple algorthm - polyhedron vs plane clipping.

 

Thinking about it, once an edge (or face in 3d) has been used to split a convex, you can actually guaruntee that 1 of those will not need to be split again. This is because the edge or face is by definition a separating line/plane, so according to the separating axis theorm, the outer convex does not overlap both polygons and can be ignored in future:

Double optimization - less work to do and less convexes generated. Win! :)

Hmmm.. and after a bit more thinking that's also how you mathematically define the overlapping convex. You keep spitting the inner convexes until you only have 1 left, and that's the overlap.

And mapping that out, if you follow edges round, those shapes only cause 3 splits:

 

Obviously you then have to do it the other way round (blue vs green instead of green vs blue), but it's a lot more efficient.

1 more brain dump then I'll probably move this to my blog :)

It occurs to me that you could use this for robot navigation quite effectively. Imagine the robot initially assumes it's in a massive field. The field is can initially be defined as positive space, i.e. assume everywhere is solid.

It then takes ping sensor or IR range finder readings at across different angles, and generates convexes from the distances. These convexes define:

  • A negative space (empty) in the convexes that define the region between the robot and the points it detected.
  • A positive space (solid) in the convexes that go from the points it detected off and out to the end of the field.

If your readings are fairly accurate, the robot can be 'sure' that it's negative space is correct. However it's positive space is none-definite, as there could be more negative spaces further off in the distance it doesn't yet know about.

Thus the map is build up by doing:

  • Generate a convex by turning head and taking readings until a concave edge is hit
  • New map = current map AND NOT(new convex) - or in english, chop the new convex out of the current map :)

Would be a cheap way of building a map of an area, and could probably be extended to 3d by taking readings at different horizontal and vertical orientations.

Quick diagram to show it...

Could probably then combine with a stereo image feed to verify results and build up 3d image map of the room. One thing I might change for this would be to store the resutls as a voxel field, then you can assign a 'certainty' to each voxel, which might make working with the real world a bit more effective. 

I suppose it all depends on what you are trying to acheive. I've ended up using Google Sketchup simply because it was free and easy to learn. I found it had a few limitations but then there are plenty of plugins written for it (many are free) that add additional features.

I think these plugins are written using "Ruby Script".

Perhaps it will be easiest to simply create plugins to suit your needs.
This way you can take advantage of their UI which you admitted you liked.

Programming aside, the math behind a good CAD program is pretty intense. If it were me, I would make a branch of one of the open source programs rather than start from scratch. 

Isn’t the project of writing new cad software... a bit on the optimistic side?

So I've tried about 10 different CAD programs now to try and create my robot models, and am quite simply.. ANGRY!”
Maybe instead of jumping from one application to another you should try to learn one really well?
… could the issue be a user problem and not a cad software problem? How complex are your robot model plans anyway?

If you’re that good a programmer, why don’t you write some great plugins for Sketchup instead?

I don't think it's on the optimistic side - it's just a tricky problem, so will need more thinking than a not-so-tricky problem :) 

You're quite right about it partly being a user problem - I'm sure I'd get more out of these programs if I spent longer. The problem is that I've hit problems in each of them that simply aren't things you can learn your way around. 13dcad for example I could definitely get a lot better at, but it's exporters aren't very good and it's quite crashy.

I guess I like to look at these things the other way around - as a child it took me a long time to build mega space ships with lego, but I was enticed and had a clear path to improving from the get go. It's a simple product with powerful results. You don't need videos and a manual to learn it. CAD (especially when it's mainly about designing models) is ultimately not a complex thing, so it shouldn't be complex to learn. Maybe that's impossible to acheive, but I think it's worth trying.

Sktechup was an interesting one, but it had some key problems with recognising objects as solids, and the versions that support csg are expensive anyway. And again - why should you have to write plugins to make cad software do cad well? :)

Probly sounds a little cocky, and like I said, I'm only wandering down this line of thought right now to see where it goes. Maybe I won't, maybe I'll write half of it and get bored, or maybe I'll write an awesomely simple cad program. 

 

Chris... shure you are aware that most problems look simple from 50'000 feet above. The closer you get and the more you learn about the problem the more elaborate the topic gets.

But necessity is the mother of invention. There is tons of reasons to roll you own CAD.

Reading your introduction it seems that you would start from scratch. If not and you consider using open source work from others, do you already have gathered a list of open source components that one could use? Any solid modeler and ray tracer components that you favor?

...and yes Chris: You are insane ;-)

 

I'm sure I'm massively underestimating how complex it is - that's partly why I posted this in the first place :)

I can see some of the path to creating one though - a few components at a slightly lower level, so the problem isn't viewed entirely from 50000ft. My main thinking is:

  • I'll start with scene defined by code, however the code will be .net. Loading a file will simply be running a .net function that the user supplies. This'll mean things like debugging and code parsing will be free, as excellent .net tools are already available. I'll write my scenes in c#, but any language that compiles to .net will be supported for free.
  • My plan is to represent the scene as a tree of convex hulls, making csg much easier. Unions just become a clipping of convexes against each other, and intersections/differences (from what I've worked out so far) basically involve splitting 1 convex against the planes of another. It'll take more memory, but allows me to do lots of work in world space (not camera), meaning I can persist a lot more data, and it's much more gpu friendly than writing a ray tracer, and much easier than writing a gpu marching cubes

That basically gets me started. If I can hook those bits together I'll be able to define a scene using c# code, and should be able to render complex scenes in real time. After that, well there's lots of additions that can be done over time, some that spring to mind being a more powerful ui, interactive scene building that generates code, exporters, lighting, materials and colour, 2d extrusion.... the list goes on. But the key is, once I can define my scenes I'll be able to work out what's most valuable next and progress from there.

Other open source software is a tricky one. Right now I kind of want to avoid being nudged in certain directions by taking on other solutions. I reckon I'll take a closer look at them once I work out what problems i want to solve and what I think isn't worth re-inventing.

So that's my plan roughly at the moment. Scene tree defined in c#, objects represented by sets of convex polyhedra, c# high level with c++ doing the hard stuff, render it, then work out what to do next :)

 

C# and wpf??? Those don't likely work so well in a linux environment, mono aside.