CSG & boolean set operation
Case
article from Siggraph "Constructive Solid Geometry" By D.H.LAydlaw et al.
ands some others article,
but now I have some problem because I work on triagulated polyhedron and I
need some lines of code to understand how I can implement the boolean
operation & CSG.
Anyone can help me sending me some link where I can find some code????
Thanks in advance
M.Z.
Scramble Entertainment Lab
http://scramblelab.usr.dsi.unimi.it/
phi...@my-deja.com
"Case" <mar...@numerica.it> wrote:
> Hi I am try to implement CSG and Boolean set operation I actually read
some
> article from Siggraph "Constructive Solid Geometry" By D.H.LAydlaw et
al.
> ands some others article,
> but now I have some problem because I work on triagulated polyhedron
and I
> need some lines of code to understand how I can implement the boolean
> operation & CSG.
> Anyone can help me sending me some link where I can find some code????
> Thanks in advance
> M.Z.
Ok, here's the thing. Laidlaw's algorithm is pretty much useless for
anything more than a couple of polygons. The problem is that it splits
all polygons like crazy in order to keep them convex. This isn't so bad
in itself (most algorithms need that and opengl rendering does too), the
problem is that in order to even work the algorithm requires perfect
evaluation of previous steps. Therefore if you are trying to do some
serious combining with lots of operations applied to a single object
there is bound to be some floating point error and the algorithm will
simply puke. I have even gone as far as using exact numbers (using
infinite precision rationals with gmp) to make it work. Even so, it is
is incredible slow. After a couple of operations there are simply way to
many polygons.
I have found a better algorithm however. BSP trees. There are tons of
informations on them on the net, however most of it isn't concerned with
csg. There is some info on it in SIGGRAPH '90 (I just can't remember the
name, that is really not nice of me). With that help I have implemented
it and if you want to look at the code, you can get it from
http://open-rpg.sourceforge.net/csg/csg.html
(Feedback is always welcome)
There is also another csg library at works which you can find somewhere
on sourceforge, but I don't really understand the algorithm and I didn't
succeed in compiling it
-Filip
Sent via Deja.com http://www.deja.com/
Before you buy.
Anton Deguet
I have the same kind of problem and did not find any publication related
to CSG for any polyhedra.
It looks like CSG boolean operations have been used to start from simple
shapes (cone, box, sphere, etc) and compose them to create a complex
one. Operations (addition, soustraction, etc) are only defined between
the simple primitives.
I would be really interested to find a paper or any reference for
union/intersection between any polyhedra (let's reduce to triangular
facets).
Anton
Marco Klemm
I know only one book handling CSG operations:
"Open Geometry", Georg Glaeser
The book comes with full source code (implemented in C++ and using OpenGL
for rendering). I have not studied the sources, but I'm think that the
boolean operations are implemented between polyhedra.
http://www.amazon.com/exec/obidos/ASIN/0387985999/qid=962829088/sr=1-1/103-3780095-7695040
http://www.uni-ak.ac.at/opengeom/
Ciao, Marco
Anton Deguet
> I know only one book handling CSG operations:
> "Open Geometry", Georg Glaeser
>
> The book comes with full source code (implemented in C++ and using OpenGL
> for rendering). I have not studied the sources, but I'm think that the
> boolean operations are implemented between polyhedra.
>
> http://www.amazon.com/exec/obidos/ASIN/0387985999/qid=962829088/sr=1-1/103-3780095-7695040
> http://www.uni-ak.ac.at/opengeom/
Thank you for this reference, nevertheless, reviews on amazon web site
are not definitively positive. Apparently, code is provided for windows
only and I use linux (I could just read the code, but it might be better
to see it running). Other problem, anyone can confirm that there are
some info for intersection between polyhedra in this book (not only
sphere/box/cone/revolution)?
Anton
August Hörandl
> Anton Deguet wrote:
> >
> > I have the same kind of problem and did not find any publication related
> > to CSG for any polyhedra.
> >
....
> I know only one book handling CSG operations:
> "Open Geometry", Georg Glaeser
>
> The book comes with full source code (implemented in C++ and using OpenGL
> for rendering). I have not studied the sources, but I'm think that the
> boolean operations are implemented between polyhedra.
are there any restrictions (copyright) with the source ? any chance to use
it for an open source project ?
Gustl
ps: there is a library which does csg:
http://breplibrary.sourceforge.net/
it is used by:
http://threedom.sourceforge.net/
so there is at last some source to read ;-)
Gustl
--
August Hörandl august....@gmx.at
"Lots of folks confuse bad management with destiny." -- Kin Hubbard
Marco Klemm
>
> Marco Klemm wrote:
>
> > I know only one book handling CSG operations:
> > "Open Geometry", Georg Glaeser
> >
> > The book comes with full source code (implemented in C++ and using OpenGL
> > for rendering). I have not studied the sources, but I'm think that the
> > boolean operations are implemented between polyhedra.
> >
> > http://www.uni-ak.ac.at/opengeom/
>
> Thank you for this reference, nevertheless, reviews on amazon web site
> are not definitively positive.
I think, some reviewer have bought this book with wrong expectations.
> Apparently, code is provided for windows only and I use linux
> (I could just read the code, but it might be better to see it running).
The code is provided for Windows and Unix.
Ciao, Marco
Marco Klemm
>
> > I know only one book handling CSG operations:
> > "Open Geometry", Georg Glaeser
> >
> > The book comes with full source code (implemented in C++ and using OpenGL
> > for rendering). I have not studied the sources, but I'm think that the
> > boolean operations are implemented between polyhedra.
>
> it for an open source project ?
I do not know. I had only lend the book and can not look up.
In case of doubt, contact the author. You will find his email address
at the URL I gave in the last posting.
Ciao, Marco
Hans-Bernhard Broeker
> but now I have some problem because I work on triagulated polyhedron and I
> need some lines of code to understand how I can implement the boolean
> operation & CSG.
The fundamental problem may be that CSG only operates on volume
vs. volume intersections, unions, and the likes. You cannot do
meaningful CSG with a triangle, or any other 'surface', just like
that, AFAIK.
From CSG point of view, a polyhedron would be constructed out of a lot
of halfspaces defined by the planes of the polyhedron's
surfaces. I.e. a unit cube is defined as the intersection of these 6
halfspaces:
x <= 1
x >= 0
y <= 1
y >= 0
z <= 1
z >= 0
Any convex polyhedron can be set up in exactly the same way. Nonconvex
polyhedrons will have to be described by unions of convex polyhedra.
--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Case
Polyhedra" by P.M Hubbard, I think this is pretty better that the Laidlaw's
algortihms aspecialy for who is working with OpenGl like me, but still I
think that the BSP tree is much simpler to implement (and also I have some
to look at) so I will change my way.
Just a question the article you speak about in your post is this one:
"Merging bsp trees yields polyhedral set operations"
Naylor, b;amanatides, j;thibault, w
???????????????
Do you think that is simple to implement????
I also found another good link about CSG and BSP :
http://members.home.com/droyer/tutorials/Engine04.html
It explain in a clear way how to implement CSG with BSP.
Bye & thanks
M.Z.
<phi...@my-deja.com> wrote in message 8jvvub$kve$1...@nnrp1.deja.com...
> In article <8jtbqc$j0q$1...@pluto.sm.dsi.unimi.it>,
> "Case" <mar...@numerica.it> wrote:
> > Hi I am try to implement CSG and Boolean set operation I actually read
> some
> > article from Siggraph "Constructive Solid Geometry" By D.H.LAydlaw et
> al.
> > ands some others article,
> > but now I have some problem because I work on triagulated polyhedron
> and I
> > need some lines of code to understand how I can implement the boolean
> > operation & CSG.
David C. Browne
boolean operation process. It doesn't discuss how to intersect line
segments or polygons, but it does discuss what to do with the results of the
intersections to form the solids. It assumes that new line segments and/or
polygons have been created from the intersection results.
I don't know whether the infomation is helpful or not, but it worked for
me. The URL is
http://members.home.net/browned/boolstf.pdf
David
Anton Deguet wrote:
> I have the same kind of problem and did not find any publication related
> to CSG for any polyhedra.
>
> It looks like CSG boolean operations have been used to start from simple
> shapes (cone, box, sphere, etc) and compose them to create a complex
> one. Operations (addition, soustraction, etc) are only defined between
> the simple primitives.
>
> I would be really interested to find a paper or any reference for
> union/intersection between any polyhedra (let's reduce to triangular
> facets).
>
> Anton
--
David Browne
David....@sdrc.com
Eugene, OR
"Never apply a Star Trek solution to a Babylon 5 problem."