Path: chuka.playstation.co.uk!tjs
From: tjs@cs.monash.edu.au (Toby Sargeant)
Newsgroups: scee.yaroze.programming.3d_graphics
Subject: Re: Poly Intersections
Date: 6 Jan 1999 04:11:22 GMT
Organization: PlayStation Net Yaroze (SCEE)
Lines: 83
Message-ID: <slrn795oj5.434.tjs@longford.cs.monash.edu.au>
References: <3689671E.AA01BBAB@hinge.mistral.co.uk> <slrn78vqlb.f0.tjs@longford.cs.monash.edu.au> <36908BCA.F33C961E@hinge.mistral.co.uk> <slrn792f0j.brn.tjs@longford.cs.monash.edu.au> <3692B711.E94081A4@hinge.mistral.co.uk>
NNTP-Posting-Host: longford.cs.monash.edu.au
X-Newsreader: slrn (0.9.4.3 UNIX)

[WARNING. What follows are the deluded ramblings of a person desparately
avoiding working on his thesis.]

On Wed, 06 Jan 1999 01:06:25 +0000, Craig Graham wrote:
>
>
>Toby Sargeant wrote:
>
>> Another thing you might like to consider for RSDAnim is presplitting
>> pathological polygons that are guaranteed to cause incorrect overlaps when
>> z-sorted.
>
<snip>
>Unfortunately, you cann't pre-calculate this as it depends on which direction
>you're looking at. Rotate the model and what hides what changes, and the
>ordering of the Z overlapping polys changes.

Not (totally) true.

You can determine if average z sorting will cause a problem by checking for
overlap of polygon bounding spheres. They're not minimal bounding spheres, so
they're trivial to calculate. Then it's just a matter of choosing polygons to
split until the bounding spheres don't overlap. It's not a perfect approach,
because it may well end up with more polygons than are strictly necessary. The
big problem is the bounding sphere test, which is a lot more strict than it
needs to be. If there's a better test, then this'd be much more feasible.

There only infalible test I can come up with is rather complex though:

for a pair of polygons (assuming positive z is into the screen):
* find a plane that divides the object space into 2 halves, s.t. one polygon
  is in each half.
* pick a point on the plane, and make a pair of vectors from it to the average
  points of the two polygons v1:(x_1,y_1,z_1),v2:(x_2,y_2,z_2). v1 is the
  vector to the polygon that's on the opposite side of the dividing plane to
  the viewpoint.
* define a unit rotation vector r:(x_r,y_r,z_r) s.t. x_r,y_r are aribitrary,
  (although obviously related) and z_r is negative.
* apply the rotation vector to v1 and v2, to get 2 equations for z_1' and z_2'
  in terms of v1,v2 and r. solve the equation z_1'<z_2' subject to the
  constraints on r.
* if there's a solution to the equation, then the polygons can overlap
  incorrectly.

Unfortunately, solving equations like that is a real pain, and probably not
worth the effort.

Another way to approach it may well be to create a full bsp tree, and then
collect nodes that are `safe'.

>> Maybe it's feasible to sort polygons into groups such that each polygon in
>> the group sorts neatly, and each group also sorts neatly, and then use many
>> different OTs to sort and merge. In the limit (1 polygon per group), this is
>> BSP, which I have no doubt would be very slow, given that you have to go
>> through the ordering tables to draw polygons, but it might prove to be a
>> reasonable tradeoff for reasonably large groups of polygons.
>
>If you were going to BSP tree, you'd have to generate a TMD with multiple
>objects in it, one object for each 'safe' group of polys which can be classed
>as a 'polygon' for the purposes of the BSP.
>Sort each convex solid (safe polygroup object) into a seperate OT, then
>sort the OT's via the BSP tree....

Exactly. I have a feeling that it'd be slow(er), but it'd be an interesting
challenge.

>> Has anyone considered alternatives to ordering tables? I know they're
>> reasonably fast, but they need a lot of memory to be accurate, and they're
>> always going to handle inconvex solids badly.
>
>You can reduce the amount of memory used and up the accuracy a bit by either
>using huge models, or using larger values for the shift value when sorting.
>You've just got to be careful your largest magnitude coordinate shifted left
>by N is less than 1<<OT_LENGTH. Using a mix of shift values (not in the same
>OT) can possibly allow variable accuracy.

But it doesn't change that fact that z sorting is always fallible. And then
there's the fact that the limit of achievable accuracy is still governed by
the length of the ordering table. Multiple ordering tables is probably the
best solution to the accuracy problems, but for complex models, it still
relies on decomposing objects down into `safe' subobjects.

Toby.