Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!rpi!bu.edu!att!pacbell.com!ucsd!nosc!crash!jcs From: jcs@crash.cts.com (John Schultz) Newsgroups: comp.graphics Subject: Re: checking whether 2 2D polygons overlap Keywords: polygon overlap 2D Message-ID: <6139@crash.cts.com> Date: 7 Dec 90 01:51:48 GMT References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP> Organization: Crash TimeSharing, El Cajon, CA Lines: 26 In <18082@netcom.UUCP> rodent@netcom.UUCP (Richard Noah) writes: [stuff deleted] >Is there an algorithm that always works? If there is, it's a closely >gaurded secret of the high priests of computer graphics. I've tried for >years to find an algorithm that will work in all cases, spending months >coding, testing, and ending up in defeat. The BSP (binary space partition algorithm) tree will work for all cases. The only disadvantage is the need to split polygons with intersecting planes. These splits are done *before* runtime (for real time work), so this algorithm is very good when you can crank out polygons at high speed. You can also do splits for the Newell et all algorithm *during* runtime, and thus is will work for all cases (but slower). >If anyone could mention/describe/point to a SINGLE ALGORITHM ANYWHERE >that depth-sorts correctly, I would be indebted forever. Would one of >the high priests reading this group care to reveal this secret to the >masses? See "Computer Graphics, Principles and Practice", by Foley et all. It presents a lucid explanation of BSPs and the depth sort method with splits. John Brought to you by Super Global Mega Corp .com