referred to as the "doom era" bug.. comes from the way P3D tries to make
things speedy, but sacrifices accuracy.

need to add some kind of "slow but accurate" mode.

from chris hoge:

I'd like to take a stab at fixing the "doom-era" texture mapping "bug" in
Processing. I grabbed the latest source from Subversion, and have been
poking around it. From what I can tell, the code I would need to touch is
in PTriangle.java, and generally deals with the blocks labeled
INTERPOLATE_UV. Does that sound right?

My plan is to write a patch, then submit the code to you for integration
as you see fit (since in the bug report you mention adding a flag for
doing it the "right" way vs. the fast way).

yes, that's correct. basically the issue is that you can either do things
quick and dirty, the way they're done in sami's PTriangle code, or
"correct", which is far slower. the correct method involves getting proper
inverted perspective coords from the current matrices and the interpolation
isn't just a straight linear change across the shape.

the best way for you to do this would be as you outline--make a modified
version, add a hint to PConstants and use hint(ACCURATE_TEXTURES) or
something like that to enable it. then your code can just be used when the
hint is set.

thanks for your interest and let me know if there's any additional help i
can provide.

*** Bug 268 has been marked as a duplicate of this bug. ***

*** Bug 329 has been marked as a duplicate of this bug. ***

Code will be coming soon, just ironing out a few details...

[quoted from e-mail]

Eric Jordan wrote:
> Ben -
>
> Hi there, my name is Eric Jordan. I've been using Processing for about a
> year now (I love it - it really strips away the annoying details of
> getting a graphical Java applet up and running, which is a fantastic
> achievement), and the other day I decided to peek through the bugs db to
> see if there was anything that I could possibly help with. I noticed the
> "Doom-era" P3D texture mapping bug listed, and I see that someone else
> said they were going to take a stab at it. That was over a year ago, and
> the "bug" still exists, so am I right to assume that nothing resulted
> from that?
>
> In any case, yesterday I decided to dig into the renderer and see what I
> could figure out, and after a few false starts it finally appears that I
> (mostly?) have perspective-correct texture mapping working for 24-bit
> plain textures with 0125, though at a cost of about two extra divides
> per pixel and a matrix inversion per triangle (plus it's all still
> floating point, so there are some casts - I may try to move it to fixed
> point eventually if it seems worthwhile). I may be able to get rid of
> the inversion, I'm not sure yet. Before I try to optimize this any
> further, though, I wanted to see if this was a patch you were still
> interested in or if you've decided it's better left alone.
>
> If you would like it, I can try to fully integrate it with all the rest
> of the texturing code (there's a LOT of code duplication there, I assume
> to avoid function call overhead on the per-pixel ops, so I'll probably
> need duplicate this stuff as well to keep it consistent). Right now the
> algorithm is textbook and bare-bones: it calculates the correct texture
> coordinates for every pixel rendered. A crucial hack in production-level
> renderers is to calculate the correct coordinate for every N-th pixel
> and use a linear (quadratic if you're feeling gutsy) interpolation
> in-between, which seriously cuts the amount of time this stuff takes,
> leaving it just a tiny bit slower than the usual linear mapping method.
> If you think that would be useful, I can try to set it up.
>
> Anyhow, let me know, I'd love to be able to contribute in some small way
> to the project - thanks again for putting together such a great environment.
>
> -Eric Jordan
hi there,

thanks for writing. that'd be great if you're willing to work on it! the
issue is still open, lets actually follow up via the bug report (feel
free to just re-paste this email) so that we can have a public record
for others who come along for this stuff.

cheers,

B.

so to follow up... it's the matrix inverse per triangle (isn't it per
vertex or worse?) that is why this was left out in the original version.
ideally, this would be something that we could enable/disable based on
whether smooth() or a hint() was set, because there will be a noticeable
performance difference.

the float vs int issue can be messy. floats aren't so much worse than ints,
but converting between them produces more overhead.

you're right about the code duplication, so we'd need to figure out a way
to be clever such that it's not a matter of doubling the size of PTriangle
to implement this in all cases.. just keep an eye out for that.

as for linear v. quadratic, even just getting something simple working will
be huge, so see what happens.

thanks for your help!

edit]
Test of accurate texture rendering

Oops, I just wrote a whole long reply to your last comment, but it got
eaten up when I added the attachment...in any case, the attachment is an
applet I compiled that shows this stuff working in a real basic case -
instructions on the index.html page. I have some ideas about the other
stuff that I'll elaborate on later today; unfortunately I have to run out
at the moment, so it will have to wait. The brief version: it is actually
one matrix inversion per triangle, and I have some idea about how to get
rid of even that, but I'll need to see if it pans out. If you wanted to
add some specialized constructors or flags for triangles, we could probably
avoid almost all of the per-triangle preprocessing stuff and just pay the
penalty of the divisions in the per-pixel loop. But for now, I'm just
working on getting it all linked together in a not-too-nasty way, so I'll
be back with more...

I've just about completed this thing (though for now I can't get rid of the
float->int casts for extremely irritating reasons), but I've run across
another bug right alongside this one, so I figured I'd see what the best
course of action is before I finish up. Here's the problem: the triangle
texturing code as it stands wraps every pixel write in a try-catch to make
sure nothing blows up if we make a call to a non-existent location in the
texture array. This sounds fine, because we generally shouldn't ever be in
such a scenario unless round-off error or something like that pushes us
outside; it would seem that the try-catch is merely on the lookout for an
exceptional situation, like if someone somehow did something Very Naughty
like reallocating a texture array without going through the proper channels
or something like that.

However, in reality, my testing seems to show that exceptions are being
thrown all the time due to the bilinear smoothing - it's regularly reading
pixels outside the array along the edges, not just in extreme situations.
This is a big performance drag, as I'm sure you're aware; an exception is
not something we can afford to be throwing on a regular basis in a pixel loop.

Perhaps this should be filed as another bug? If you'd like I can do so, or
I could just fix this up with either a bounds check inside the loop or an
adjustment of the edge-handling. Rather than just patching this as is,
however, it occurs to me that in the process of fixing this up it would be
extremely easy to add wrap-around or pinned-to-edge textures like in
OpenGL, which would automatically take care of any outside-of-array issues.
Currently the triangle constructors themselves seem to restrict the range
of textures you can input, but in many cases it is very useful to let them
wrap. Any thoughts on this?

thanks for all your work on this, it's fantastic.

please file a new bug for the texture error issue, so that we have a
separate record of the issue. i'd be happy to have these two things fixed
independently of one another.

as for texture wrapping, that can actually also be filed as a separate bug
(file as an enhancement). if you fix them all together, just mark the other
two as having a dependency on this one (hm, or did we remove that..) if
you're interested in fixing, that would be great, though only if you're
willing to fix the opengl version as well since it's a low priority feature
and would otherwise make more work for me.. :)

this is great news, i can't wait to see how it all turns out.

edit]
Altered PGraphics3D, PConstants, and PTriangle files (added accurate texture
code)

Okay, I just uploaded what I've gotten so far as far as this bug goes.
Sorry, these are just the raw java files that I changed - how exactly do
you make a patch again?

A test applet is up at http://www.gamefight.org/Tunnel/ so you can see this
working.

I set this up so that it calculates a true texture coordinate every 2^N
pixels and interpolates in between, as generally calculating every pixel is
really slow. By default, I have N set at 3, which seems to cut a decent
line between performance and accuracy. The code is not so pretty - I had
do duplicate a lot to fit it in with the way things are done. The problem
is that there are several things to optimize for - average speed,
best/worst case speeds, file size, and good code design - and all of these
things are mutually exclusive. I tried to find middle ground, but it's not
necessarily optimal. Currently it seems to run at about halfway between
the speeds of the unoptimized (but simple and accurate - every pixel
calculated) algorithm and the default linear interpolation. But it would
be easy to alter this to target smaller file size or something else...

The API changes are:

- added hint ENABLE_ACCURATE_TEXTURES
- added PTriangle.setInterpPower(int) to set the power of 2 used for
texture interpolation while in accurate mode

I was forced to add several private variables to PTriangle, and a few
public ones to PGraphics3D, as well as pass a few things to PTriangle
during rendering that otherwise would not have been there (camera space
coordinates, mainly). Also this code depends on the fact that the near
clipping plane and screen dimensions are set in PGraphics3D.frustum() - if
funny business with the transformation matrices happens elsewhere, it won't
work right.

Take a look, let me know what changes would be helpful.

very very cool.. will try to get this patched in shortly, should be in for
0125.

submitting whole source files is preferred for now, so that i can just do
the diffs directly. thanks!

re: comment #9 and uv coordinates... might this also be related to bug #102? Just
wanted to suggest that perhaps worth looking at both problems simultaneously if
clamp/wrap were to be added to the uv's.

It's easy to demonstrate that P3D's texturing is off a tiny bit (even in the absence of
this "doom era" bug on z-flat geometry) and there's a "weird" conversion in PTriangle
that seems highly suspect - I wonder if it was done to under-convert the coordinates
as an attempt to reduce clipping? This is the one I'm referring to:

(u[0] * TEX_WIDTH) * 65500f
shouldn't that be:
(u[0] * TEX_WIDTH) * 65535f // (if need last fixedpoint on [0,width) )
or
(u[0] * (TEX_WIDTH-1)) * 65536f // (if need last integer on [0,width))

Also evident if you compare setUV(float*6) and setUV(float[]*2) -- the 6 float
version seems more correct (though still has that odd 65500) but PGraphics3D is
using the array version which uses the conversion above.

Or, it'd be nice to document the source if there is in fact a legitimate reason for using
that 65500 value so it doesn't get brought up again by some other nitpicker like
myself. :-D

(In reply to comment #14)
Oops! Nevermind, I must've had old source, 65500 gone from setUV(float*6) --
sorry for cluttering up the bugs db, feel free to delete this and prior post.

(In reply to comment #15)
You know, while going through that code I couldn't figure out that 65500,
either...btw, it's still in the version of the file that I'm seeing. What
I'm assuming is that as you suspect, it was an attempt to avoid going off
the end of the array. Or it was just considered "close enough" for rock 'n
roll, I'm not entirely sure.

Besides, it seems that we may actually _need_ a range check when we're
doing the rasterization -- for bilinear interpolation you need to handle
the edge rows separately. In this case it doesn't make much sense to use
hacks like 65500 vs. 65536 to deal with this stuff...

This is starting to get off topic, becoming more relevant to bug 546 than
this one, but one hack that I've sometimes used to handle things like this
is just to go ahead and make the image array a row or two longer than it
actually is, filling in the extra rows with either the bottom row pixels or
looping back to the first pixels. This has the effect under bilinear
interpolation of trading a slightly (very slight) higher memory footprint
and a bit of bookkeeping to track the unmodified size of the image against
the speed benefit of removing a range check from the pixel loop, which can
be quite beneficial. Alas, to do looping textures or clamped textures, a
range check must happen per pixel unless you're a lot more clever than I
am...[though you could loop the texture in memory, I suppose, and generate
a large enough looped image, but that seems wasteful and not very efficient
if you never see the whole thing...]

And BTW, in the fix for this bug (103) I think I added some sort of a
bounds check that's good enough to catch every bilinear interpolation
off-array thing except the one at the last pixel in the image.

sami didn't provide additional documentation, but my assumption is that
65500 is used so that you can use bit shifting and don't have to worry
testing for overflows.

now applied in svn, please take a look. we're right about to release 0125
so i'd hate to have a regression, but you're getting so many edits in
there, i don't want to wait too much longer since you'll be getting out of
sync.

my thinking now is that we won't use hint(), and that smooth() will
actually control it. i think smooth() is instead going to mean something to
the effect of "smooth whatever possible".

release 0125 adds hint(ENABLE_ACCURATE_TEXTURES) thanks to the help of
ewjordan. woohoo!

we may just use this hint() whenever smooth() is called, will have to see.

The one problem that I see at the moment with setting through smooth is
that people may quite innocently end up calling smooth() to smooth lines
and stuff while using ortho mode, which, by enabling the perspective
correction, would give very bad results - alas, I didn't consider the
possibility of turning on perspective textures in ortho mode, so I didn't
build in any code to check it. Trust me, using perspective correction in a
perspective-less mode gives extremely unexpected results, since a) ortho()
doesn't set the variables that the texturing needs, and b) even if it did
(or if I computed them from the projection matrix), the distance to screen
plane would effectively be infinite in ortho mode. It's probably better to
be safe and check this situation just in case, and add in a rigorous check
to make sure the matrices have been set by a frustum call rather than some
other way (this would also avoid problems if people set the projection
matrix themselves). I'll have this done somewhat soon, but in the
meantime, I'll defer to you to decide what to do re: the smooth() hint.
People aren't really used to using smooth with P3D anyhow since it's been
disabled for a while, so maybe it won't be that big a deal if this is in
until the next maintenance release, but if you are going to put this
behavior into 0125 and can give me a day or so heads up I'll forego a
complete solution for a quick and dirty temporary fix.

i'm gonna try to release 0125 today, just waiting on reference and examples
updates from casey; but i think we're fine for now.. it's a hint() method,
not a regular api command, so it's fairly obscure and limited to those who
bother to read the release notes. we can look into a better solution for
future releases (i hope to have 0126 out sometime this month).