I've decided to implement a viewer (and hopefully editor) for 3d Lego models on the CSE. I'm currently in the process of implementing the scan-line rendering algorithm in Java to make sure I understand the corner-cases before I attempt a z80 translation.

Something is currently going horribly awry, as this is supposed to be a solid cube:




[edit]

Drawing each of the different kinds of faces separately reveals a separate class of bug.

Need to re-depth-test after the current nearest face terminates:


I have no idea about this weird stringy bit, but it shouldn't be there:


The side-panels apparently inverted their triangle-y bits. I don't know why:

Hey so you are performing 3D transformations as well as drawing or is this just a prototype of the polygon routine?

Performed some trivial transformations, and verified that the points are going where I think they should be going. Mostly I'm just prototyping the polygon routine.

Bump. Found and fixed a couple bugs that drastically improved the output:






There are still a couple weird artifacts that I'm not sure about even for single polygons (actually, I can tell how they're being calculated, I just haven't quite figured out why), and the depth tests are obviously incorrect, but this is definite progress.


[edit]


It seems to very nearly be working correctly. I found and fixed an error with z-fighting along edges that would be overlooked because of the large pixel-jumps taken by a scanline renderer.
borked (nondeterministic effects due to set iteration):


fixed:



Also, the code is on github now, if anyone cares.

Very nice work! I see only a few small graphical glitches at the corners of those polygons; otherwise it looks like you've made great strides with this. I also may peruse your source code at some point, although I admit I'll be more enthused about the code once it starts transitioning to the calculator phase.

Thanks! =) Yeah, I have some OBOEs lurking in the boundary conditions, but I think I have a sense for how to refactor it now that I've fixed the z-fighting in a way that will work better all around. The hurdle after that is handling lines as well as polygons, and then it's porting time =)

Needed some judicious dot-producting to deal with the case involving crossing a vertex. Working now. You'll notice the two screenshots are slightly different, due to z-fighting, however both are correct-enough. Dealing with z-fighting more effectively in integer arithmetic is too annoying to consider.



Still need to deal with lines correctly though, because right now the situation isn't good. This was supposed to be a wireframe:


[edit]
Very nearly have everything working!
If we look here, everything appears to be fine and dandy.


However that is sadly just a happy accident resulting from which face is blue and which edges aren't quite working:


I have no idea what is at fault those two being missing, but I guess it's probably something either really arcane or really obvious.

[edit 2]
All done, and now with better colors to see it in action:


I had an if statement that needed an
Code:
added to it:

Code:

After a long delay, I've decided to retarget my plans for this to the CE, because I'd rather port to C than to z80, and also because yay memory mapped screens. Most of the basic data structures I needed I've now ported over. Still need to think about the more complex stuff (some sort of hash-set).

But you can look at the beginnings of the C code here:

https://github.com/elfprince13/Scanline-Rendering/tree/master/ScanLineRender/ScanLineRender

I hope to have this done in time for T^3 at the end of February.

Awesome! I've got a universal tool chain with some libraries that may be of a lot more help. Should be released on Wednesday or sooner

Alright, finished porting the bulk of the algorithm to C, and hooked up a test harness to rasterize the "LCD buffer" into a PPM image, but some bugs seem to have crept in during the process, that I'm concerned may be due to the datastructure changes and/or datastructure implementations I'm using, or possibly due to the fact that I was attempting to work with fixed-precision arithmetic, but less carefully than I ought to have. That said, there appear to be no memory leaks or crashes, so that's a good start.

As a starting point for debugging, I added extra discriminating factors to the ordering functions used by my data structures to eliminate any non-determinism between the expected behaviors of the Java and C implementations. The log files are now identical for the first 165 lines (out of thousands), which gives me a great idea of where I need to set breakpoints to catch the bugs in action.

Nice debugging trick, and best of luck figuring out what in the C++ to C port is tripping you up. Hopefully it turns out to be something easy to repair.

Alright, so, one silly bug:

Code:
was originally defined with a return type of uint8_t, so my left-to-right sorting was doing weird things. Resolving this gave me (almost!) 190 lines of log-concordance, except for a discrepancy on line 177 where they took opposite forks of an if-statement, that I suspect is setting a few incorrect flags that turn into the full-blown failure on line 192.

[edit]
Oops, I appear to have forgotten to initialize a variable that was being used for a dot-product test, controlling branching. That they agreed the first two times through the test was just good luck.

[edit 2]
Fixed that, and another bug related to calculating the stop-pixel when filling a big horizontal space. There still seems to be a bug when detecting horizontal lines in the raster, but the vast majority of 12k lines of the log are now concordant.

Compare:
the (good) Java implementation:


and the (almost there) C implementation:


[edit 3]
Yay! Everything is ported over. The last problem was that I needed to flip the sign of certain dot products when comparing edges that share a vertex.


The next task is to download Mateo's SDK and point my output buffer at the LCD address space instead of at netpbm. From there I'll look into optimizations and file formats to load models instead of having to program them.

Bump: after some absolutely awful fighting with Zilog's crappy compiler, the code crashes for no discernible reason in the midst of projecting points. I'm tempted between doing *another* rewrite in assembly, and saying screw it and going back to work on a backend for LLVM, because the cost/benefit analysis really doesn't favor working with the Zilog compiler.

I'd be strongly in favor of an LLVM-based ez80 compiler, especially if you could convince some of our community members to work on it with you, now that the TI-84 Plus CE is becoming so dominant among the [e]z80 crowd.

While I definitely agree that an LLVM or even GCC based compiler would be fantastic, I don't think that is necessary. When writing programs for the CE, you must stay within the bounds of the platform. Looking through the code on github I see a lot of malloc()ing of data, and many other things that look suspicious. You have a heap size of 69090-sizeof(BSS) bytes, which looks like that may be overflowing because your BSS also looks huge. Also, using int32_t is okay since it is defined as an unsigned long in the stdint library, but it doesn't make sense if you are writing this program for an eZ80.

Yeah, adding a quick print in viewF showed that at around 0xD0F000 (a bit more), numbers started to be non-sense, so it was probably reading/writing anything but what it was supposed to.

Look at the viewF print (those are supposed to be coordinates) (oC is 'o->coords' and pE is 'projectEdge' (the caller))


The .map file says:

Code:

Mateo: I will likely swap in either a float, or some kind of fixed point 16.8 datatype for the points, but I'm not worried about that particular optimization at the moment. And that BSS is not particularly large compared to a heap size of 69090 - particularly since my allocations should nearly proportional to BSS.

Is the malloc reasonably behaved / can it be expected to return null if an alloc overflows the heap?

As a distraction from beating my head against the 84+CE C SDK I've made a few data-structure & algorithm changes to make better use of RAM.

Primitives are now of type:

Code:

rather than type:

Code:


This drastically reduces redundant copies of points, which is a win for both storage, and computational costs spent on projections/transformations, at the cost of slightly more pointer chasing. The boundary edges of the Primitive are implicit in the sequence of Point*, rather than explicitly stored as a sequence of pairs, which for complex polygons reduces the storage costs by a further factor of 2.

I also factored the render function into several sub-functions, to allow the amortization of vertical sorting/projection costs when the view doesn't change between frames (and even when it does change, it should reduce the amount of malloc/free thrashing in setup and teardown of data structures).

I've also implemented an 84+CE variant of the SafeMalloc routine, which, barring compiler/linker errors (something I ran into while testing...), should help with debugging (and is probably worth reusing in other projects).

Code:


[edit]
Alright, there appear to be some errors (oof, not looking forward to debugging this, since the PC version is correct), and it's pretty slow by virtue of running in 16bpp mode, but...


[edit 2]
Fixed the RAM clear, which was due to calling cleanup *before* my datastructure teardown. Oops.
Still no idea on the graphical glitches. Back to regular work.

Fantastic work elfprince! Your code has some very advanced items in it; I find it pretty neat that the compiler can handle it to some degree or another. (Even though it is a real beast). Looks like some kind of overflow error maybe; but that doesn't make much sense since 32 bit longs are supported. You should indeed be able to get a decent speedup by using 8bpp mode; and if you switch from [u]int32_t to just [unsigned]int; you should get an even larger speed increase. (Like, a lot) Anywho; keep up the great work! Looking spiffy.

EDIT: Also, for the safeMalloc routine, I would recommend against using _JError, and use exit(int). All a matter of preference though.


Code:

=

Code: