I had one further thought on this overnight: if you expand the planes bounding a convex object out to infinity then you get a series of convex cells surrounding the object. Which cell you're in exactly determines which faces you can see and the natural way to figure out which convex cell a player is in is a BSP tree. So you could reduce the face visibility check from its current linear time to logarithmic time - 5 or 6 checks for the Cobra Mk 3 (the most complicated model I've tried) rather than 30 odd and always 3 rather than 6 for the cube (the simplest).
It definitely helps to talk about this stuff... On Thursday, May 27, 2010, Thomas Harte <[email protected]> wrote: > My own routine. It's in the drawline.z80s file, and it should be safe > to swap it out for any other function as long as it accepts the same > input and leaves the same registers intact (I think just IX and IY, > but go with whatever the comment in that file says rather than what > I'm saying now). > > My understanding was that the way that they've generalised the pixel > plotting step to support different drawing modes and to do viewport > testing within the line routine means that the ROM routines would be > slower than my RAM routines. My routines benefit from only ever doing > one of two things: > > - drawing a solid, single pixel wide line that is definitely entirely > on the screen (ie, no need to test per pixel) > - erase an old line, being allowed also to blank out any other pixels > the routine feels like (which in practice means that it calculates the > correct (x, y) for each pixel then just zeroes that byte in video > memory, actually blanking two pixels) > > The latter could probably be faster if you halved the notional x > resolution in which you're drawing and blanked out four pixels rather > than two (to deal with occasions when the rounded version pixels the > byte one to the side of the one that the non-rounded routine would > have picked). I haven't experimented there. > > On Thu, May 27, 2010 at 3:19 PM, Roger Jowett <[email protected]> wrote: >> how are lines drawn using rom routine or your own? >> >> On 27 May 2010 15:14, Thomas Harte <[email protected]> wrote: >>> Removing hidden line removal would save the time calculating face >>> visibility but then add to transformation and drawing costs. >>> >>> The code at present always does a calculation for every defined face, >>> always considers a calculation for every defined line and performs >>> calculations for vertices only if they are used as part of the model >>> as it is visible for that draw operation. Vertices that are connected >>> only to lines that aren't visible aren't transformed. >>> >>> If I were to rewrite it, I would adjust that so that, as a first >>> measure, a calculation is performed for every defined face but lines >>> that aren't connected to visible faces are never even considered. >>> That's not a massive win in performance terms because all it does for >>> lines at the minute is run through reading a couple of flags and >>> proceeding or discarding based on the combination of those. However, >>> if I were then able to add a broad phase to the face stuff* then it'd >>> really start to pay off down the hierarchy. >>> >>> * as in, a prepatory step that interrogates some sort of hierarchical >>> structure and hence discards large swathes of faces without doing a >>> calculation for each. Usually it saves time even if it is able to >>> reject, say, only 90% of invisible faces and then you have to do the >>> face-by-face tests on each of the remaining potentially visible set. >>> I've never been 100% on the best, or even a necessarily suitable >>> hierarchical form. >>> >>> On Thu, May 27, 2010 at 12:51 PM, Roger Jowett <[email protected]> >>> wrote: >>>> so no hidden line removal speeds things up a bit... >>>> http://www.worldofspectrum.org/infoseekid.cgi?id=0003126 >>>> theres a screen shot only the roads were solid line the objects seemed >>>> to be dots and not hidden line either >>>> think in th erooms things were all solid >>>> can be seen better in this screen shot >>>> >>>> http://www.worldofspectrum.org/infoseek.cgi?regexp=^Mercenary%3a+The+Second+City$&pub=^Novagen+Software+Ltd$&loadpics=1 >>>> >>>> thought battle carrier command were pretty solid/shaded 3dnot vecotrs? >>>> >>>> On 27 May 2010 12:08, Thomas Harte <[email protected]> wrote: >>>>> Without being able to answer on the Timex or the extent to which the >>>>> RAM upgrade would benefit 128k emulation, was Mercenary the one where >>>>> they appeared to be drawing on only every other scanline? It's >>>>> possible I've merged it with Battle Command (filled polys, draws only >>>>> every other line) in my memory. >>>>> >>>>> I'm not completely sure on the external RAM modules, but my >>>>> understanding is that they're not contended at all, which would be a >>>>> substantial speed improvement for the 3d calculation parts of this >>>>> sort of code and some improvement to the pixel throwing. >>>>> >>>>> Technically my code can do display without hidden line removal, it's >>>>> just a consequence of the algorithm rather than a deliberately >>>>> designed feature. It's the Elite method, each line is considered a >>>>> potential edge and connected to two faces. If either face is visible >>>>> then the line is drawn. The links are pointers, so you'd set both >>>>> pointers to a face that isn't connected as part of the model (so the >>>>> code won't recalculate whether it is visible when you draw) and has >>>>> the visibility flag set. >>>>> >>>>> On Thu, May 27, 2010 at 9:30 AM, Roger Jowett <
